rfc3221.txt

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

   change was the introduction of routing protocols that dispensed with
   the requirement for the Class A, B and C address delineation,
   replacing this scheme with a routing system that carried an address
   prefix and an associated prefix length.  This approached was termed
   Classless Inter-Domain Routing (CIDR) [5].

   A concerted effort was undertaken in 1994 and 1995 to deploy CIDR
   routing in the Internet, based on encouraging deployment of the
   CIDR-capable version of the BGP protocol, BGP4 [7].

   The intention of CIDR was one of hierarchical provider address
   aggregation, where a network provider was allocated an address block
   from an address registry, and the provider announced this entire
   block into the exterior routing domain as a single entry with a
   single routing policy.  Customers of the provider were encouraged to
   use a sub-allocation from the provider's address block, and these
   smaller routing elements were aggregated by the provider and not
   directly passed into the exterior routing domain.  During 1994 the



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


   size of the routing table remained relatively constant at some 20,000
   entries as the growth in the number of providers announcing address
   blocks was matched by a corresponding reduction in the number of
   address announcements as a result of CIDR aggregation.

3.3  CIDR Growth

   For the next four years until the start of 1998, CIDR proved
   effective in damping unconstrained growth in the BGP routing table.
   During this period, the BGP table grew at an approximate linear rate,
   adding some 10,000 entries per year.

   A close examination of the table reveals a greater level of stability
   in the routing system at this time.  The short term (hourly)
   variation in the number of announced routes reduced, both as a
   percentage of the number of announced routes, and also in absolute
   terms.  One of the other benefits of using large aggregate address
   blocks is that instability at the edge of the network is not
   immediately propagated into the routing core.  The instability at the
   last hop is absorbed at the point where an aggregate route is used in
   place of a collection of more specific routes.  This, coupled with
   widespread adoption of BGP route flap damping, was very effective in
   reducing the short term instability in the routing space during this
   period.

3.4  Current Growth

   In late 1998 the trend of growth in the BGP table size changed
   radically, and the growth for the period 1998 - 2000 is again showing
   all the signs of a re-establishment of a growth trend with strong
   correlation to an exponential growth model.  This change in the
   growth trend appears to indicate that pressure to use hierarchical
   address allocations and CIDR has been unable to keep pace with the
   levels of growth of the Internet, and some additional factors that
   impact the growth in the BGP table size have become more prominent in
   the Internet.  This has lead to a growth pattern in the total size of
   the BGP table that has more in common with a compound growth model
   than a linear model.  A good fit of the data for the period from
   January 1999 until December 2000 is a compound growth model of 42%
   growth per year.

   An initial observation is that this growth pattern points to some
   weakening of the hierarchical model of connectivity and routing
   within the Internet.  To identify the characteristics of this recent
   trend it is necessary to look at a number of related characteristics
   of the routing table.





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


   BGP table size data for the first half of 2001 shows different trends
   at various measurement points in the Internet.  Some measurement
   points where the local AS has a relative larger number of more
   specific routes show a steady state for the first half of 2001 with
   no appreciable growth, while other measurement points where the local
   AS has had a lower number of more specific routes initially show a
   continuation of table size growth.  There are a number of commonly
   observed discontinuities in the data for 2001, corresponding to
   events where a significant number of more specific entries have been
   replaced by an encompassing aggregate prefix.

4.  Related Measurements derived from BGP Table

   The level of analysis of the BGP routing table has been extended in
   an effort to identify the factors contributing to this growth, and to
   determine whether this leads to some limiting factors in the
   potential size of the routing space.  Analysis includes measuring the
   number of ASes in the routing system, and the number of distinct AS
   paths, the range of addresses spanned by the table and average span
   of each routing entry.

4.1  AS Number Consumption

   Each network that is multi-homed within the topology of the Internet
   and wishes to express a distinct external routing policy must use a
   unique AS number to associate its advertised addresses with such a
   policy.  In general, each network is associated with a single AS, and
   the number of ASes in the default-free routing table tracks the
   number of entities that have unique routing policies.  There are some
   exceptions to this, including large global transit providers with
   varying regional policies, where multiple ASes are associated with a
   single network, but such exceptions are relatively uncommon.

   The number of unique ASes present in the BGP table has been tracked
   since late 1996, and the trend of AS number deployment over the past
   four years is also one that matches a compound growth model with a
   growth rate of 51% per year.  As of the start of May 2001 there were
   some 10,700 ASes visible in the BGP table.  At a continued rate of
   growth of 51% p.a., the 16 bit AS number space will be fully deployed
   by August 2005.  Work is underway within the IETF to modify the BGP
   protocol to carry AS numbers in a 32-bit field. [8]  While the
   protocol modifications are relatively straightforward, the major
   responsibility rests with the operations community to devise a
   transition plan that will allow gradual transition into this larger
   AS number space.






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


4.2  Address Consumption

   It is also possible to track the total amount of address space
   advertised within the BGP routing table.  At the start of 2001 the
   routing table encompassed 1,081,131,733 addresses, or some 25.17% of
   the total IPv4 address space, or 25.4% of the usable unicast public
   address space.  By September 2001 this has growth to 1,123,124,472
   addresses, or some 26% of the IPv4 address space.  This has grown
   from 1,019,484,655 addresses in November 1999.  However, there are a
   number of /8 prefixes that are periodically announced and withdrawn
   from the BGP table, and if the effects of these prefixes is removed,
   a compound growth model against the previous 12 months of data of
   this metric yields a best fit model of growth of 7% per year in the
   total number of addresses spanned by the routing table.

   Compared to the 42% growth in the number of routing advertisements,
   the growth in the amount of address space advertised is far lower.
   One possible explanation is that much of the growth of the Internet
   in terms of growth in the number of connected devices is occurring
   behind various forms of NAT gateways.  In terms of solving the
   perceived finite nature of the address space identified just under a
   decade ago, this explanation would tend to indicate that the Internet
   appears so far to have embraced the approach of using NATs,
   irrespective of their various perceived functional shortcomings. [9]
   This explanation also supports the observation of smaller address
   fragments supporting distinct policies in the BGP table, as such
   small address blocks may encompass arbitrarily large networks located
   behind one or more NAT gateways.  There are alternative explanations
   of this difference between the growth of the table and the growth of
   address space, including a trend towards discrete exterior routing
   policies being applied to finer address blocks.

4.3  Granularity of Table Entries

   The intent of CIDR aggregation was to support the use of large
   aggregate address announcements in the BGP routing table.  To confirm
   whether this is still the case the average span of each BGP
   announcement has been tracked for the past 12 months.  The data
   indicates a decline in the average span of a BGP advertisement from
   16,000 individual addresses in November 1999 to 12,100 in December
   2000.  As of September 2001 this span has been further reduced to an
   average 10,700 individual addresses per routing entry.  This
   corresponds to an increase in the average prefix length from /18.03
   to /18.44 by December 2000 and a /18.6 by September 2001.  Separate
   observations of the average prefix length used to route traffic in
   operation networks in late 2000 indicate an average length of 18.1
   [11].  This trend towards finer-grained entries in the routing table
   is potentially cause for concern, as it implies the increasing spread



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


   of traffic over greater numbers of increasingly smaller forwarding
   table entries.  This, in turn, has implications for the design of
   high speed core routers, particularly when extensive use is made of a
   small number of very high speed cached forwarding entries within the
   switching subsystem of a router's design.

   A similar observation can be made regarding the number of addresses
   advertised per AS.  In December 1999 each AS advertised an average of
   161,900 addresses (equivalent to a prefix length /14.69, and in
   January 2001 this average has fallen to 115,800 addresses, an
   equivalent prefix length of /15.18.

   This points to increasingly finer levels of routing detail being
   announced into the global routing domain.  This, in turn, supports
   the observation that the efficiencies of hierarchical routing
   structures are no longer being fully realized within the deployed
   Internet.  Instead, increasingly finer levels of routing detail are
   being announced globally in the BGP tables.  The most likely cause of
   this trend of finer levels of routing granularity is an increasingly
   dense interconnection mesh, where more networks are moving from a
   single-homed connection with hierarchical addressing and routing into
   multi-homed connections without any hierarchical structure.  The spur
   for this increasingly dense connectivity mesh in the Internet may
   well be the declining unit costs of communications bearer services
   coupled with a common perception that richer sets of adjacencies
   yields greater levels of service resilience.

4.4  Prefix Length Distribution

   In addition to looking at the average prefix length, the analysis of
   the BGP table also includes an examination of the number of
   advertisements of each prefix length.

   An extensive program commenced in the mid-nineties to move away from
   intense use of the Class C space and to encourage providers to
   advertise larger address blocks, as part of the CIDR effort.  This
   has been reinforced by the address registries who have used provider
   allocation blocks that correspond to a prefix length of /19 and, more
   recently, /20.

   These measures were introduced in the mid-90's when there were some
   20,000 - 30,000 entries in the BGP table.  Some six years later in
   April 2001 it is interesting to note that of the 108,000 entries in
   the routing table, some 59,000 entries have a /24 prefix.  In
   absolute terms the /24 prefix set is the fastest growing set in the
   BGP routing table.  The routing entries of these smaller address
   blocks also show a much higher level of change on an hourly basis.
   While a large number of BGP routing points perform route flap



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


   damping, nevertheless there is still a very high level of
   announcements and withdrawals of these entries in this particular
   area of the routing table when viewed using a perspective of route
   updates per prefix length.  Given that the numbers of these small
   prefixes are growing rapidly, there is cause for some concern that
   the total level of BGP flux, in terms of the number of announcements
   and withdrawals per second may be increasing, despite the pressures
   from flap damping.  This concern is coupled with the observation
   that, in terms of BGP stability under scaling pressure, it is not the
   absolute size of the BGP table that is of prime importance, but the