Subject: [RADIR] Revision 3 of problem statement

From: Thomas Narten <[email-masked]>
Date: Fri, 27 Apr 2007 16:58:09 -0400

Here is the full text. It incorporates the new text I sent out before
the call, a revised paragraph from Marla (as discussed on the call)
and some additional wordsmithing.

The sense of the call was that we were getting close. John & Vijay,
could you please have a look and let us know what you think?

Our next call is Tuesday, 11AM PDT/2PM EDT, and it would be good to
wrap up the problem statement enough to send it on to Russ and Olaf.

Thomas

Network Working Group                                          T. Narten
Internet-Draft                                            April 27, 2007
Intended status: Informational
Expires: October 29, 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 29, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Narten                  Expires October 29, 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
     3.1.  Technical Challenge  . . . . . . . . . . . . . . . . . . .  5
     3.2.  Business Challenge . . . . . . . . . . . . . . . . . . . .  5
     3.3.  Alignment of Incentives  . . . . . . . . . . . . . . . . .  6
   4.  Pressures To Deaggregate . . . . . . . . . . . . . . . . . . .  8
     4.1.  Traffic Engineering  . . . . . . . . . . . . . . . . . . .  8
     4.2.  Multihoming  . . . . . . . . . . . . . . . . . . . . . . .  8
     4.3.  End Site Renumbering . . . . . . . . . . . . . . . . . . .  8
     4.4.  Acquisitions and Mergers . . . . . . . . . . . . . . . . .  8
     4.5.  RIR IPv4 Policies favor Conservation over Aggregation  . .  8
   5.  Pressures on Routing Update Rate . . . . . . . . . . . . . . .  9
     5.1.  Interconnection Richness . . . . . . . . . . . . . . . . .  9
     5.2.  Multihoming  . . . . . . . . . . . . . . . . . . . . . . .  9
     5.3.  Traffic Engineering  . . . . . . . . . . . . . . . . . . .  9
     5.4.  Questionable Operational Practices?  . . . . . . . . . . .  9
   6.  Problem Statement  . . . . . . . . . . . . . . . . . . . . . . 10
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 11
   8.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 12
   9.  Informative References . . . . . . . . . . . . . . . . . . . . 13
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 14
   Intellectual Property and Copyright Statements . . . . . . . . . . 15

Narten                  Expires October 29, 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 29, 2007                [Page 3]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

2.  Terms and Definitions

   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 number in the hundreds of the
      thousands of entries.

   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 state
      information maintained is dependent on a number of factors,
      including the number of individual prefixes, the number of BGP
      peers, the number of distinct paths, etc.  The RIB may also
      include information about unused ("backup") paths for a given
      prefix as well as the active path(s) used for forwarding.

   Forwarding Information Base (FIB):  The actual table used while
      making forwarding decisions for individual packets.  The FIB is a
      compact, optimized version of the RIB, 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.  The FIB only stores information about paths
      actually used for forwarding; it typically does not store
      information about backup paths.

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

3.  Background

   Within the DFZ, both the size of the RIB/FIB and the update rate of
   routing updates have historically increased at a greater than linear
   rate.  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 or converge more slowly if
      they cannot.  The rate increase is driven by a number of factors
      (discussed below).

   This super linear growth presents a scalability challenge for current
   and/or future routers.  There are two aspects to the challenge.  The
   first one is purely technical: can we build routers (i.e., hardware &
   software) actually capable handling the load, both today and going
   forward?  The second challenge is one of economics: is the cost of
   developing, building and deploying such routers economically
   sustainable, given current and realistic business models that govern
   how ISPs operate as businesses?

3.1.  Technical Challenge

   The technical challenge of building routers relates to the resources
   needed to process a larger and increasingly dynamic amount of routing
   information.  More specifically, routers must maintain an increasing
   amount of associated state information in the RIB, they must be
   capable of populating a growing FIB, they must perform forwarding
   lookups at line rates (while accessing the FIB) and they must be able
   to initialize the RIB and FIB at boot time.  Moreover, this activity
   must take place within acceptable time frames (i.e., the overall
   system must converge and stabilize within an acceptable time period).
   Finally, the hardware needed to achieve this cannot have unreasonable
   power consumption or cooling demands.

3.2.  Business Challenge

   Even if it is technically possible to build routers capable of
   meeting the technical and operational requirements, it is also
   necessary that the overall cost to build, maintain and deploy such
   equipment meet reasonable business expectations.  ISPs, after all,
   are run as businesses.  As such, they must be able to plan, develop

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

   and construct viable business plans that provide an acceptable return
   on investment (i.e., one acceptable to investors).

   One aspect of planning concerns assumptions about the expected usable
   lifetime of purchased equipment.  Businesses typically expect that
   once deployed, equipment can remain in use for some projected amount
   of time (e.g., 3-5 years).  That is, in the absence of a need to
   upgrade in order to provide new services or functionality (e.g.,
   increased traffic, additional customers, etc.), deployed equipment
   should remain usable.  An increase in the resources required to
   support larger or more dynamic routing tables, however, can undermine
   such assumptions, forcing upgrades earlier than had been planned or
   forecast.  This undermining of planning is particularly problematic
   when the increase in routing demand originates external to the ISP,
   and the ISP has no way to control or limit it (e.g., the increased
   demand comes from being part of the DFZ).

   From a business perspective, it is desirable to maintain or increase
   the useful lifespan of routing equipment, by improving the scaling
   properties of the routing and addressing system. [xxx: I'd like to
   strengthen this point somehow..]

3.3.  Alignment of Incentives

   Today's growth pattern is influenced by the scaling properties of the
   current system.  If the system had better scaling properties, we
   would be able support and enable more widespread usage of certain
   applications such as multihoming and traffic engineering.  Currently
   the system does not allow everyone to multihome, as there are some
   barriers to multihoming due to operational practices that try to
   strike a balance between the amount of multihoming and preservation
   of routing slots.  It is desirable that the routing and addressing
   system exert the least possible back pressure on end user
   applications and deployment scenarios, to enable the broadest
   possible use of the Internet.

   One aspect of the current architecture is a misalignment of cost and
   benefit.  Injecting individual prefixes into the DFZ creates a small
   amount "pain" for those routers that are part of the DFZ.  Each
   individual prefix has a small cost, but the aggregate sum of all
   prefixes is significant, and leads to the core problem at hand.
   Those that inject prefixes into the DFZ do not generally pay the cost
   associated with the individual prefix -- it is carried by the routers
   in the DFZ.  But the originator of the prefix receives the benefit.
   Hence, there is misalignment of incentives between those receiving
   the benefit and those bearing the cost of providing the benefit.
   Consequently, incentives are not aligned properly to produce a
   natural balance between the cost and benefit of maintaining routing

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

   tables.

Narten                  Expires October 29, 2007                [Page 7]

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 an additional 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 29, 2007                [Page 8]

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 29, 2007                [Page 9]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

6.  Problem Statement

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

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

   2.  allows any end site wishing to multihome to do so

   3.  Supports ISP and enterprise TE needs

   4.  Allows end sites to switch providers while minimizing
       configuration changes to internal end site devices.

   5.  Provides meaningful benefits to the parties who bear the costs of
       deploying and maintaining the technology.

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

7.  Security Considerations

   None.

Narten                  Expires October 29, 2007               [Page 11]

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 29, 2007               [Page 12]

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 29, 2007               [Page 13]

Internet-Draft  Routing and Addressing Problem Statement      April 2007

Author's Address

   Thomas Narten (Editor)

Narten                  Expires October 29, 2007               [Page 14]

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 29, 2007               [Page 15]


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