Subject: [RADIR] problem statement (first cut)

From: Thomas Narten <[email-masked]>
Date: Fri, 06 Apr 2007 14:44:34 -0400

Here's a first cut. There is a whole section on "causes" that I think
should be filled in for completeness, but I haven't done so yet.

Thomas

Network Working Group                                          T. Narten
Internet-Draft                                             April 6, 2007
Intended status: Informational
Expires: October 8, 2007

                Routing and Addressing Problem Statement
               draft-narten-ram-problem-statement-00.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on October 8, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Narten                   Expires October 8, 2007                [Page 1]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

Abstract

   Problem statement for the route scaling problem.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terms and Definitions  . . . . . . . . . . . . . . . . . . . .  4
   3.  Background . . . . . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Pressures To Deaggregate . . . . . . . . . . . . . . . . . . .  6
     4.1.  Traffic Engineering  . . . . . . . . . . . . . . . . . . .  6
     4.2.  Multihoming  . . . . . . . . . . . . . . . . . . . . . . .  6
     4.3.  End Site Renumbering . . . . . . . . . . . . . . . . . . .  6
     4.4.  Acquisitions and Mergers . . . . . . . . . . . . . . . . .  6
     4.5.  RIR IPv4 Policies favor Conservation over Aggregation  . .  6
   5.  Pressures on Routing Update Rate . . . . . . . . . . . . . . .  7
     5.1.  Interconnection Richness . . . . . . . . . . . . . . . . .  7
     5.2.  Multihoming  . . . . . . . . . . . . . . . . . . . . . . .  7
     5.3.  Traffic Engineering  . . . . . . . . . . . . . . . . . . .  7
     5.4.  Questionable Operational Practices?  . . . . . . . . . . .  7
   6.  Problem Statement  . . . . . . . . . . . . . . . . . . . . . .  8
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   8.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 10
   9.  Informative References . . . . . . . . . . . . . . . . . . . . 11
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12
   Intellectual Property and Copyright Statements . . . . . . . . . . 13

Narten                   Expires October 8, 2007                [Page 2]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

1.  Introduction

   Prompted in part by the recent IAB workshop on Routing & Addressing
   [RAWS-REPORT], there has been a renewed focus on the problem of
   routing scalability within the Internet.  The issue itself is not
   new, with discussions dating back at least 10-15 years [GSE, ...].

   This document attempts to define the "problem", with the aim of
   describing the essential aspects so that the community has a way of
   evaluating whether proposed solutions actually address or impact the
   underlying problem or "pain points" in a significant manner.

Narten                   Expires October 8, 2007                [Page 3]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

2.  Terms and Definitions

   Default Free Zone (DFZ):  Default Free Zone (DFZ): That part of the
      Internet where routers maintain full routing tables.  Many routers
      maintain only partial routes, having explicit routes for "local"
      destinations plus a "default" for everything else.  For such
      routers, building and maintaining routing tables is relatively
      simple because the amount of information learned and maintained
      can be small.  In contrast, routers in the DFZ maintain complete
      information about all reachable destinations, which numbers in the
      hundreds of the thousands of entries.

   Routing Information Base (RIB):  Routing Information Base (RIB): The
      data structures a router maintains that hold the information about
      destinations (i.e., prefixes) and paths to those destinations.
      The amount of the state information maintained is dependent on a
      number of factors, including the number individual prefixes, the
      number of BGP peers, the number of distinct paths, etc.

   Forwarding Information Base (FIB):  Forwarding Information Base (FIB)
      The actual routing table used while making forwarding decisions
      for individual packets.  The FIB is a compact, optimized version
      of the FIB, containing only the information needed to actually
      forward individual packets, i.e., mapping a packet's destination
      address to an outgoing interface and next-hop.

Narten                   Expires October 8, 2007                [Page 4]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

3.  Background

   The core problem is that within the DFZ, both the size of the RIB/FIB
   and the update rate of routing updates are increasing at a rate that
   threatens to overwhelm the ability of the routing infrastructure to
   build and maintain stable routing tables that converge within an
   acceptable time frame.  Specifically:

   o  The number of individual prefixes that are propagated into the DFZ
      is increasing at a super-linear rate.  The reasons behind this
      increase are varied and discussed below.  However, each individual
      prefix appears in routing updates, requires state in the RIB (and
      possibly the FIB), and consumes processing resources when updates
      related to the prefix are received.

   o  The rate of routing updates is increasing, requiring routers to
      process updates at an increased rate (xxx: can we say anything
      about the trends of this rate?).  The rate increase is also driven
      by a number of factors (discussed below).

   This super linear growth may present a scalability problem for
   current and/or future routers with regard to the resources needed to
   process a larger and increasingly dynamic amount of routing
   information, to store an increasing amount of associated state
   information in the RIB, populating a growing FIB, performing
   forwarding lookups at line rate on the FIB, and initialization of the
   RIB and FIB at boot time.

   Scaling each of these structures may cause an unsustainable increase
   in power consumption, heat, size, and the cost of routing kits,
   and/or may cause an unsustainable decrease in the usable lifespan of
   a router (decreasing the depreciation models) thus reducing the
   return on investment and/or requiring continuous rolling upgrades.

Narten                   Expires October 8, 2007                [Page 5]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

4.  Pressures To Deaggregate

   There are number of factors behind the increase in the number of
   prefixes appearing in the DFZ.  From a theoretical perspective, the
   number of prefixes in the DFZ can be minimized through aggressive
   aggregation [RFC4632].  In practice, strict adherence to the CIDR
   principles is difficult.

4.1.  Traffic Engineering

   Simply include Section 3.1.3 of RAWS Report?

4.2.  Multihoming

   Simply include Section 3.1.2 of RAWS Report?

4.3.  End Site Renumbering

   Pain of end site renumbering leads to demand for PI assignments, each
   of which translates into a prefix in the DFZ.

4.4.  Acquisitions and Mergers

4.5.  RIR IPv4 Policies favor Conservation over Aggregation

   Especially in IPv4, subsequent allocations not always from same block
   as previous allocation...

Narten                   Expires October 8, 2007                [Page 6]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

5.  Pressures on Routing Update Rate

5.1.  Interconnection Richness

5.2.  Multihoming

5.3.  Traffic Engineering

5.4.  Questionable Operational Practices?

Narten                   Expires October 8, 2007                [Page 7]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

6.  Problem Statement

   There is a need for a more scalable approach to routing and
   addressing that:

   1.  stabilizes or reduces the growth rate of the size of the DFZ
       routing load

   2.  provides multihoming for end sites

   3.  Supports ISP and enterprise TE needs

   4.  Allows end sites to switch providers without requiring a
       renumbering of internal end site devices.

Narten                   Expires October 8, 2007                [Page 8]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

7.  Security Considerations

   None.

Narten                   Expires October 8, 2007                [Page 9]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

8.  Acknowledgments

   The initial version of this document was produced by the Routing and
   Addressing Directorate. (http://www.ietf.org/IESG/content/radir.html)

Narten                   Expires October 8, 2007               [Page 10]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

9.  Informative References

   [RFC4632]  Fuller, V. and T. Li, "Classless Inter-domain Routing
              (CIDR): The Internet Address Assignment and Aggregation
              Plan", BCP 122, RFC 4632, August 2006.

Narten                   Expires October 8, 2007               [Page 11]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

Author's Address

   Thomas Narten

Narten                   Expires October 8, 2007               [Page 12]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   [email-masked].

Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).

Narten                   Expires October 8, 2007               [Page 13]


_______________________________________________
RADIR mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/radir

---

From: "John G. Scudder" <[email-masked]>
Date: Tue, 17 Apr 2007 20:27:29 -0700

Here's a revision where I've tried to remedy my misgivings.  It's not  
my finest piece of writing but you should get the idea.  I've also  
corrected several editorial nits I noticed.  I've also attached a diff.

--John

>                draft-narten-ram-problem-statement-00.txt
[snip]

---

From: Jason Schiller <[email-masked]>
Date: Wed, 18 Apr 2007 17:50:11 -0400 (EDT)

John,

I am mostly amenable to the changes.

I think there are two things that are missing.

The first is that the scalibility challange does not solely result from
the DFZ.  Local information for a large ISP is also a significant
contributer compounding the scalibility challenge.  Not sue where that
text should be worked in.

The second is business driver of ROI with regard to depreciation models,
and a possible compression of the upgrade cycle leading to at the worst,
rolling upgrades...

How about:

   Regardless of whether it is possible to scale routing hardware to
   keep pace with these factors while keeping other aspects such as
   power consumption, volume and cost within acceptable bounds, if
   growth continues it is clear that for any given piece of routing
   equipment, its scaling limits will eventually be exceeded (although
   one must acknowledge that other limits exist with respect to factors
   unrelated to the growth of the routing system, such as packet rate,
   one such could be the limiting factor).  It is desirable to maintain
   or increase the useful lifespan of routing equipment, by improving
   the scaling properties of the routing and addressing system.  This
   will reduce the pressure to compress upgrade cycles allowing 
   continued support of the currently utilized depreciation models
   and return on investment scheduals. 
   
   Furthermore, the growth pattern observed is influenced by the scaling
   properties of the current system.  If the system had better scaling
   properties, it is possible that certain applications which are
   currently untenable, for example ubiquitous multihoming, might become
   widespread.  It is desirable that the routing and addressing system
   exert the least possible backpressure on end user applications and
   deployment scenarios, to enable the broadest possible use of the
   Internet.

___Jason

==========================================================================
Jason Schiller                                               (703)886.6648
Senior Internet Network Engineer                         fax:(703)886.0512
Public IP Global Network Engineering                       [email-masked]
UUNET / Verizon                         [email-masked]

The good news about having an email address that is twice as long is that
it increases traffic on the Internet.

On Tue, 17 Apr 2007, John G. Scudder wrote:

> Date: Tue, 17 Apr 2007 20:27:29 -0700
> From: John G. Scudder <[email-masked]>
> To: Thomas Narten <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [RADIR] problem statement (first cut)
>

---

From: Thomas Narten <[email-masked]>
Date: Thu, 19 Apr 2007 10:28:51 -0400

> text should be worked in.

I understand that. At the same time, it's clear that the DFZ is really
critical, because that can make/break the Internet as we know it. Lead
to Balkanization, etc.

For internal routes, one can argue that the extent of this problem is
at least partly a result of internal ISP decisions that have been
made, as opposed to global ones being forced from the outside. That
changes the nature of the debate as to how problematic this is.

I'm not saying that that makes the problem irrelevant, but it mean
it's more complicated to argue how big a problem is. E.g., do _all_
ISPs agree with this, or does the degree of pain vary among ISPs?

> and a possible compression of the upgrade cycle leading to at the worst,

yes. we need to describe this in terms that don't get us into the
cursed "business model" discussion that the IETF has to stay out of,
but I think we need to address it more concretely than we have so far.
Perhaps we can talk about it more generically in terms of common
business practices. 

>    and return on investment scheduals.

This is all very abstract, and many people just won't understand the
degree to which this is really a problem. I suspect.

Thomas

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 19 Apr 2007 11:06:31 -0700

> How about:
[text]

WFM.

--John