rfc3221.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,299 行 · 第 1/5 页

Network Working Group                                          G. Huston
Request for Comments: 3221                   Internet Architecture Board
Category: Informational                                    December 2001


                             Commentary on
                  Inter-Domain Routing in the Internet

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2001).  All Rights Reserved.

Abstract

   This document examines the various longer term trends visible within
   the characteristics of the Internet's BGP table and identifies a
   number of operational practices and protocol factors that contribute
   to these trends.  The potential impacts of these practices and
   protocol properties on the scaling properties of the inter-domain
   routing space are examined.

   This document is the outcome of a collaborative exercise on the part
   of the Internet Architecture Board.

Table of Contents

   1.   Introduction.................................................  2
   2.   Network Scaling and Inter-Domain Routing  ...................  2
   3.   Measurements of the total size of the BGP Table  ............  4
   4.   Related Measurements derived from BGP Table  ................  7
   5.   Current State of inter-AS routing in the Internet  .......... 11
   6.   Future Requirements for the Exterior Routing System  ........ 14
   7.   Architectural Approaches to a scalable Exterior
          Routing Protocol........................................... 15
   8.   Directions for Further Activity  ............................ 21
   9.   Security Considerations  .................................... 22
   10.  References  ................................................. 23
   11.  Acknowledgements  ........................................... 24
   12.  Author's Address  ........................................... 24
   13.  Full Copyright Statement  ................................... 25





Huston                       Informational                      [Page 1]

RFC 3221           Commentary on Inter-Domain Routing      December 2001


1.  Introduction

   This document examines the various longer term trends visible within
   the characteristics of the Internet's BGP table and identifies a
   number of operational practices and protocol factors that contribute
   to these trends.  The potential impacts of these practices and
   protocol properties on the scaling properties of the inter-domain
   routing space are examined.

   These impacts include the potential for exhaustion of the existing
   Autonomous System number space, increasing convergence times for
   selection of stable alternate paths following withdrawal of route
   announcements, the stability of table entries, and the average prefix
   length of entries in the BGP table.  The larger long term issue is
   that of an increasingly denser inter-connectivity mesh between ASes,
   causing a finer degree of granularity of inter-domain policy and
   finer levels of control to undertake inter-domain traffic
   engineering.

   Various approaches to a refinement of the inter-domain routing
   protocol and associated operating practices that may provide superior
   scaling properties are identified as an area for further
   investigation.

   This document is the outcome of a collaborative exercise on the part
   of the Internet Architecture Board.

2.   Network Scaling and Inter-Domain Routing

   Are there inherent scaling limitations in the technology of the
   Internet or its architecture of deployment that may impact on the
   ability of the Internet to meet escalating levels of demand? There
   are a number of potential areas to search for such limitations.
   These include the capacity of transmission systems, packet switching
   capacity, the continued availability of protocol addresses, and the
   capability of the routing system to produce a stable view of the
   overall topology of the network.  In this study we will look at this
   latter capability with the objective of identifying some aspects of
   the scaling properties of the Internet's routing system.

   The basic structure of the Internet is a collection of networks, or
   Autonomous Systems (ASes) that are interconnected to form a connected
   domain.  Each AS uses an interior routing system to maintain a
   coherent view of the topology within the AS, and uses an exterior
   routing system to maintain adjacency information with neighboring
   ASes to create a view of the connectivity of the entire system.





Huston                       Informational                      [Page 2]

RFC 3221           Commentary on Inter-Domain Routing      December 2001


   This network-wide connectivity is described in the routing table used
   by the BGP4 protocol (referred to as the Routing Information Base, or
   RIB).  Each entry in the table refers to a distinct route.  The
   attributes of the route, together with local policy constraints, are
   used to determine the best path from the local AS to the AS that is
   originating the route.  Determining the 'best path' in this case is
   determining which routing advertisement and associated next hop
   address is the most preferred by the local AS.  Within each local
   BGP-speaking router this preferred route is then loaded into the
   local RIB (Loc-RIB).  This information is coupled with information
   obtained from the local instance of the interior routing protocol to
   form a Forwarding Information Base (or FIB), for use by the local
   router's forwarding engine.

   The BGP routing system is not aware of finer level of topology of the
   network on a link-by-link basis within the local AS or within any
   remote AS.  From this perspective BGP can be seen as an inter-AS
   connectivity maintenance protocol, as distinct from a link-level
   topology management protocol, and the BGP routing table can be viewed
   as a description of the current connectivity of the Internet using an
   AS as the basic element of connectivity computation.

   There is an associated dimension of policy determination within the
   routing table.  If an AS advertises a route to a neighboring AS, the
   local AS is offering to accept traffic from the neighboring AS which
   is ultimately destined to addresses described by the advertised
   routing entry.  If the local AS does not originate the route, then
   the inference is that the local AS is willing to undertake the role
   of transit provider for this traffic on behalf of some third party.
   Similarly, an AS may or may not choose to accept a route from a
   neighbor.  Accepting a route implies that under some circumstances,
   as determined by the local route selection parameters, the local AS
   will use the neighboring AS to reach addresses spanned by the route.
   The BGP routing domain is intended to maintain a coherent view of the
   connectivity of the inter-AS domain, where connectivity is expressed
   as a preference for 'shortest paths' to reach any destination address
   as modulated by the connectivity policies expressed by each AS, and
   coherence is expressed as a global constraint that none of the paths
   contains loops or dead ends.  The elements of the BGP routing domain
   are routing entries, expressed as a span of addresses.  All addresses
   advertised within each routing entry share a common origin AS and a
   common connectivity policy.  The total size of the BGP table is
   therefore a metric of the number of distinct routes within the
   Internet, where each route describes a contiguous set of addresses
   that share a common origin AS and a common reachability policy.






Huston                       Informational                      [Page 3]

RFC 3221           Commentary on Inter-Domain Routing      December 2001


   When the scaling properties of the Internet were studied in the early
   1990s two critical factors identified in the study were, not
   surprisingly, routing and addressing [2].  As more devices connect to
   the Internet they consume addresses, and the associated function of
   maintaining reachability information for these addresses, with an
   assumption of an associated growth in the number of distinct provider
   networks and the number of distinct connectivity policies, implies
   ever larger routing tables.  The work in studying the limitations of
   the 32 bit IPv4 address space produced a number of outcomes,
   including the specification of IPv6 [3], as well as the refinement of
   techniques of network address translation [4] intended to allow some
   degree of transparent interaction between two networks using
   different address realms.  Growth in the routing system is not
   directly addressed by these approaches, as the routing space is the
   cross product of the complexity of the inter-AS topology of the
   network, multiplied by the number of distinct connectivity policies
   multiplied by the degree of fragmentation of the address space.  For
   example, use of NAT may reduce the pressure on the number of public
   addresses required by a single connected network, but it does not
   necessarily imply that the network's connectivity policies can be
   subsumed within the aggregated policy of a single upstream provider.

   When an AS advertises a block of addresses into the exterior routing
   space this entry is generally carried across the entire exterior
   routing domain of the Internet.  To measure the common
   characteristics of the global routing table, it is necessary to
   establish a point in the default-free part of the exterior routing
   domain and examine the BGP routing table that is visible at that
   point.

3.  Measurements of the total size of the BGP Table

   Measurements of the size of the routing table were somewhat sporadic
   to start, and a number of measurements were taken at approximate
   monthly intervals from 1988 until 1992 by Merit [5].  This effort was
   resumed in 1994 by Erik-Jan Bos at Surfnet in the Netherlands, who
   commenced measuring the size of the BGP table at hourly intervals in
   1994.  This measurement technique was adopted by the author in 1997,
   using a measurement point located at the edge of AS 1221 at Telstra
   in Australia, again using an hourly interval for the measurement.
   The initial measurements were of the number of routing entries
   contained within the set of selected best paths.  These measurements
   were expanded to include the number of AS numbers, number of AS
   paths, and a set of measurements relating to the prefix size of
   routing table entries.






Huston                       Informational                      [Page 4]

RFC 3221           Commentary on Inter-Domain Routing      December 2001


   This data  contains a view of the dynamics of the Internet's routing
   table growth that spans some 13 years in total and includes a very
   detailed view spanning the most recent seven years [6].  Looking at
   just the total size of the BGP routing table over this period, it is
   possible to identify four distinct phases of inter-AS routing
   practice in the Internet.

3.1  Pre-CIDR Growth

   The initial characteristics of the routing table size from 1988 until
   April 1994 show definite characteristics of exponential growth.  If
   continued unchecked, this growth would have lead to saturation of the
   available BGP routing table space in the non-default routers of the
   time within a small number of years.

   Estimates of the time at which this would've happened varied somewhat
   from study to study, but the overall general theme of these
   observations was that the growth rates of the BGP routing table were
   exceeding the growth in hardware and software capability of the
   deployed network, and that at some point in the mid-1990's, the BGP
   table size would have grown to the point where it was larger than the
   capabilities of available equipment to support.

3.2  CIDR Deployment

   The response from the engineering community was the introduction of a
   hierarchy into the inter-domain routing system.  The intent of the
   hierarchical routing structure was to allow a provider to merge the
   routing entries for its customers into a single routing entry that
   spanned its entire customer base.  The practical aspects of this