As per Relevance of the word december, we have this rfc below:
Network Working Group G.
Request for Comments: 3221 Internet Architecture
Category: Informational December 2001
Commentary
Inter-Domain Routing in the
Status of this
This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited
Copyright
Copyright (C) The Internet Society (2001). All Rights Reserved
This document examines the various longer term trends visible
the characteristics of the Internet's BGP table and identifies
number of operational practices and protocol factors that
to these trends. The potential impacts of these practices
protocol properties on the scaling properties of the inter-
routing space are examined
This document is the outcome of a collaborative exercise on the
of the Internet Architecture Board
Table of
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
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.
This document examines the various longer term trends visible
the characteristics of the Internet's BGP table and identifies
number of operational practices and protocol factors that
to these trends. The potential impacts of these practices
protocol properties on the scaling properties of the inter-
routing space are examined
These impacts include the potential for exhaustion of the
Autonomous System number space, increasing convergence times
selection of stable alternate paths following withdrawal of
announcements, the stability of table entries, and the average
length of entries in the BGP table. The larger long term issue
that of an increasingly denser inter-connectivity mesh between ASes
causing a finer degree of granularity of inter-domain policy
finer levels of control to undertake inter-domain
engineering
Various approaches to a refinement of the inter-domain
protocol and associated operating practices that may provide
scaling properties are identified as an area for
investigation
This document is the outcome of a collaborative exercise on the
of the Internet Architecture Board
2. Network Scaling and Inter-Domain
Are there inherent scaling limitations in the technology of
Internet or its architecture of deployment that may impact on
ability of the Internet to meet escalating levels of demand?
are a number of potential areas to search for such limitations
These include the capacity of transmission systems, packet
capacity, the continued availability of protocol addresses, and
capability of the routing system to produce a stable view of
overall topology of the network. In this study we will look at
latter capability with the objective of identifying some aspects
the scaling properties of the Internet's routing system
The basic structure of the Internet is a collection of networks,
Autonomous Systems (ASes) that are interconnected to form a
domain. Each AS uses an interior routing system to maintain
coherent view of the topology within the AS, and uses an
routing system to maintain adjacency information with
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
by the BGP4 protocol (referred to as the Routing Information Base,
RIB). Each entry in the table refers to a distinct route.
attributes of the route, together with local policy constraints,
used to determine the best path from the local AS to the AS that
originating the route. Determining the 'best path' in this case
determining which routing advertisement and associated next
address is the most preferred by the local AS. Within each
BGP-speaking router this preferred route is then loaded into
local RIB (Loc-RIB). This information is coupled with
obtained from the local instance of the interior routing protocol
form a Forwarding Information Base (or FIB), for use by the
router's forwarding engine
The BGP routing system is not aware of finer level of topology of
network on a link-by-link basis within the local AS or within
remote AS. From this perspective BGP can be seen as an inter-
connectivity maintenance protocol, as distinct from a link-
topology management protocol, and the BGP routing table can be
as a description of the current connectivity of the Internet using
AS as the basic element of connectivity computation
There is an associated dimension of policy determination within
routing table. If an AS advertises a route to a neighboring AS,
local AS is offering to accept traffic from the neighboring AS
is ultimately destined to addresses described by the
routing entry. If the local AS does not originate the route,
the inference is that the local AS is willing to undertake the
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
neighbor. Accepting a route implies that under some circumstances
as determined by the local route selection parameters, the local
will use the neighboring AS to reach addresses spanned by the route
The BGP routing domain is intended to maintain a coherent view of
connectivity of the inter-AS domain, where connectivity is
as a preference for 'shortest paths' to reach any destination
as modulated by the connectivity policies expressed by each AS,
coherence is expressed as a global constraint that none of the
contains loops or dead ends. The elements of the BGP routing
are routing entries, expressed as a span of addresses. All
advertised within each routing entry share a common origin AS and
common connectivity policy. The total size of the BGP table
therefore a metric of the number of distinct routes within
Internet, where each route describes a contiguous set of
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
1990s two critical factors identified in the study were,
surprisingly, routing and addressing [2]. As more devices connect
the Internet they consume addresses, and the associated function
maintaining reachability information for these addresses, with
assumption of an associated growth in the number of distinct
networks and the number of distinct connectivity policies,
ever larger routing tables. The work in studying the limitations
the 32 bit IPv4 address space produced a number of outcomes
including the specification of IPv6 [3], as well as the refinement
techniques of network address translation [4] intended to allow
degree of transparent interaction between two networks
different address realms. Growth in the routing system is
directly addressed by these approaches, as the routing space is
cross product of the complexity of the inter-AS topology of
network, multiplied by the number of distinct connectivity
multiplied by the degree of fragmentation of the address space.
example, use of NAT may reduce the pressure on the number of
addresses required by a single connected network, but it does
necessarily imply that the network's connectivity policies can
subsumed within the aggregated policy of a single upstream provider
When an AS advertises a block of addresses into the exterior
space this entry is generally carried across the entire
routing domain of the Internet. To measure the
characteristics of the global routing table, it is necessary
establish a point in the default-free part of the exterior
domain and examine the BGP routing table that is visible at
point
3. Measurements of the total size of the BGP
Measurements of the size of the routing table were somewhat
to start, and a number of measurements were taken at
monthly intervals from 1988 until 1992 by Merit [5]. This effort
resumed in 1994 by Erik-Jan Bos at Surfnet in the Netherlands,
commenced measuring the size of the BGP table at hourly intervals
1994. This measurement technique was adopted by the author in 1997,
using a measurement point located at the edge of AS 1221 at
in Australia, again using an hourly interval for the measurement
The initial measurements were of the number of routing
contained within the set of selected best paths. These
were expanded to include the number of AS numbers, number of
paths, and a set of measurements relating to the prefix size
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
table growth that spans some 13 years in total and includes a
detailed view spanning the most recent seven years [6]. Looking
just the total size of the BGP routing table over this period, it
possible to identify four distinct phases of inter-AS
practice in the Internet
3.1 Pre-CIDR
The initial characteristics of the routing table size from 1988
April 1994 show definite characteristics of exponential growth.
continued unchecked, this growth would have lead to saturation of
available BGP routing table space in the non-default routers of
time within a small number of years
Estimates of the time at which this would've happened varied
from study to study, but the overall general theme of
observations was that the growth rates of the BGP routing table
exceeding the growth in hardware and software capability of
deployed network, and that at some point in the mid-1990's, the
table size would have grown to the point where it was larger than
capabilities of available equipment to support
3.2 CIDR
The response from the engineering community was the introduction of
hierarchy into the inter-domain routing system. The intent of
hierarchical routing structure was to allow a provider to merge
routing entries for its customers into a single routing entry
spanned its entire customer base. The practical aspects of
change was the introduction of routing protocols that dispensed
the requirement for the Class A, B and C address delineation
replacing this scheme with a routing system that carried an
prefix and an associated prefix length. This approached was
Classless Inter-Domain Routing (CIDR) [5].
A concerted effort was undertaken in 1994 and 1995 to deploy
routing in the Internet, based on encouraging deployment of
CIDR-capable version of the BGP protocol, BGP4 [7].
The intention of CIDR was one of hierarchical provider
aggregation, where a network provider was allocated an address
from an address registry, and the provider announced this
block into the exterior routing domain as a single entry with
single routing policy. Customers of the provider were encouraged
use a sub-allocation from the provider's address block, and
smaller routing elements were aggregated by the provider and
directly passed into the exterior routing domain. During 1994
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
blocks was matched by a corresponding reduction in the number
address announcements as a result of CIDR aggregation
3.3 CIDR
For the next four years until the start of 1998, CIDR
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
in the routing system at this time. The short term (hourly
variation in the number of announced routes reduced, both as
percentage of the number of announced routes, and also in
terms. One of the other benefits of using large aggregate
blocks is that instability at the edge of the network is
immediately propagated into the routing core. The instability at
last hop is absorbed at the point where an aggregate route is used
place of a collection of more specific routes. This, coupled
widespread adoption of BGP route flap damping, was very effective
reducing the short term instability in the routing space during
period
3.4 Current
In late 1998 the trend of growth in the BGP table size
radically, and the growth for the period 1998 - 2000 is again
all the signs of a re-establishment of a growth trend with
correlation to an exponential growth model. This change in
growth trend appears to indicate that pressure to use
address allocations and CIDR has been unable to keep pace with
levels of growth of the Internet, and some additional factors
impact the growth in the BGP table size have become more prominent
the Internet. This has lead to a growth pattern in the total size
the BGP table that has more in common with a compound growth
than a linear model. A good fit of the data for the period
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
weakening of the hierarchical model of connectivity and
within the Internet. To identify the characteristics of this
trend it is necessary to look at a number of related
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
at various measurement points in the Internet. Some
points where the local AS has a relative larger number of
specific routes show a steady state for the first half of 2001
no appreciable growth, while other measurement points where the
AS has had a lower number of more specific routes initially show
continuation of table size growth. There are a number of
observed discontinuities in the data for 2001, corresponding
events where a significant number of more specific entries have
replaced by an encompassing aggregate prefix
4. Related Measurements derived from BGP
The level of analysis of the BGP routing table has been extended
an effort to identify the factors contributing to this growth, and
determine whether this leads to some limiting factors in
potential size of the routing space. Analysis includes measuring
number of ASes in the routing system, and the number of distinct
paths, the range of addresses spanned by the table and average
of each routing entry
4.1 AS Number
Each network that is multi-homed within the topology of the
and wishes to express a distinct external routing policy must use
unique AS number to associate its advertised addresses with such
policy. In general, each network is associated with a single AS,
the number of ASes in the default-free routing table tracks
number of entities that have unique routing policies. There are
exceptions to this, including large global transit providers
varying regional policies, where multiple ASes are associated with
single network, but such exceptions are relatively uncommon
The number of unique ASes present in the BGP table has been
since late 1996, and the trend of AS number deployment over the
four years is also one that matches a compound growth model with
growth rate of 51% per year. As of the start of May 2001 there
some 10,700 ASes visible in the BGP table. At a continued rate
growth of 51% p.a., the 16 bit AS number space will be fully
by August 2005. Work is underway within the IETF to modify the
protocol to carry AS numbers in a 32-bit field. [8] While
protocol modifications are relatively straightforward, the
responsibility rests with the operations community to devise
transition plan that will allow gradual transition into this
AS number space
Huston Informational [Page 7]
RFC 3221 Commentary on Inter-Domain Routing December 2001
4.2 Address
It is also possible to track the total amount of address
advertised within the BGP routing table. At the start of 2001
routing table encompassed 1,081,131,733 addresses, or some 25.17%
the total IPv4 address space, or 25.4% of the usable unicast
address space. By September 2001 this has growth to 1,123,124,472
addresses, or some 26% of the IPv4 address space. This has
from 1,019,484,655 addresses in November 1999. However, there are
number of /8 prefixes that are periodically announced and
from the BGP table, and if the effects of these prefixes is removed
a compound growth model against the previous 12 months of data
this metric yields a best fit model of growth of 7% per year in
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
in terms of growth in the number of connected devices is
behind various forms of NAT gateways. In terms of solving
perceived finite nature of the address space identified just under
decade ago, this explanation would tend to indicate that the
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
fragments supporting distinct policies in the BGP table, as
small address blocks may encompass arbitrarily large networks
behind one or more NAT gateways. There are alternative
of this difference between the growth of the table and the growth
address space, including a trend towards discrete exterior
policies being applied to finer address blocks
4.3 Granularity of Table
The intent of CIDR aggregation was to support the use of
aggregate address announcements in the BGP routing table. To
whether this is still the case the average span of each
announcement has been tracked for the past 12 months. The
indicates a decline in the average span of a BGP advertisement
16,000 individual addresses in November 1999 to 12,100 in
2000. As of September 2001 this span has been further reduced to
average 10,700 individual addresses per routing entry.
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.
observations of the average prefix length used to route traffic
operation networks in late 2000 indicate an average length of 18.1
[11]. This trend towards finer-grained entries in the routing
is potentially cause for concern, as it implies the increasing
Huston Informational [Page 8]
RFC 3221 Commentary on Inter-Domain Routing December 2001
of traffic over greater numbers of increasingly smaller
table entries. This, in turn, has implications for the design
high speed core routers, particularly when extensive use is made of
small number of very high speed cached forwarding entries within
switching subsystem of a router's design
A similar observation can be made regarding the number of
advertised per AS. In December 1999 each AS advertised an average
161,900 addresses (equivalent to a prefix length /14.69, and
January 2001 this average has fallen to 115,800 addresses,
equivalent prefix length of /15.18.
This points to increasingly finer levels of routing detail
announced into the global routing domain. This, in turn,
the observation that the efficiencies of hierarchical
structures are no longer being fully realized within the
Internet. Instead, increasingly finer levels of routing detail
being announced globally in the BGP tables. The most likely cause
this trend of finer levels of routing granularity is an
dense interconnection mesh, where more networks are moving from
single-homed connection with hierarchical addressing and routing
multi-homed connections without any hierarchical structure. The
for this increasingly dense connectivity mesh in the Internet
well be the declining unit costs of communications bearer
coupled with a common perception that richer sets of
yields greater levels of service resilience
4.4 Prefix Length
In addition to looking at the average prefix length, the analysis
the BGP table also includes an examination of the number
advertisements of each prefix length
An extensive program commenced in the mid-nineties to move away
intense use of the Class C space and to encourage providers
advertise larger address blocks, as part of the CIDR effort.
has been reinforced by the address registries who have used
allocation blocks that correspond to a prefix length of /19 and,
recently, /20.
These measures were introduced in the mid-90's when there were
20,000 - 30,000 entries in the BGP table. Some six years later
April 2001 it is interesting to note that of the 108,000 entries
the routing table, some 59,000 entries have a /24 prefix.
absolute terms the /24 prefix set is the fastest growing set in
BGP routing table. The routing entries of these smaller
blocks also show a much higher level of change on an hourly basis
While a large number of BGP routing points perform route
Huston Informational [Page 9]
RFC 3221 Commentary on Inter-Domain Routing December 2001
damping, nevertheless there is still a very high level
announcements and withdrawals of these entries in this
area of the routing table when viewed using a perspective of
updates per prefix length. Given that the numbers of these
prefixes are growing rapidly, there is cause for some concern
the total level of BGP flux, in terms of the number of
and withdrawals per second may be increasing, despite the
from flap damping. This concern is coupled with the
that, in terms of BGP stability under scaling pressure, it is not
absolute size of the BGP table that is of prime importance, but
rate of dynamic path re-computations that occur in the wake
announcements and withdrawals. Withdrawals are of particular
due to the number of transient intermediate states that the
distance vector algorithm explores in processing a withdrawal
Current experimental observations indicate a typical convergence
of some 2 minutes to propagate a route withdrawal across the
domain. [10]
An increase in the density of the BGP mesh, coupled with an
in the rate of such dynamic changes, does have serious
in maintaining the overall stability of the BGP system as
continues to grow. The registry allocation policies also have
some impact on the routing table prefix distribution. The
registry practice was to use a minimum allocation unit of a /19,
the 10,000 prefix entries in the /17 to /19 range are a
of this policy decision. More recently, the allocation policy
allows for a minimum allocation unit of a /20 prefix, and the /20
prefix is used by some 4,300 entries as of January 2001, and
relative terms is one of the fastest growing prefix sets. The
of entries corresponding to very small address blocks (smaller than
/24), while small in number as a proportion of the total BGP
table, is the fastest growing in relative terms. The number of /25
through /32 prefixes in the routing table is growing faster, in
of percentage change, than any other area of the routing table.
prefix length filtering were in widespread use, the practice
announcing a very small address block with a distinct routing
would have no particular beneficial outcome, as the address
would not be passed throughout the global BGP routing domain and
propagation of the associated policy would be limited in scope.
growth of the number of these small address blocks, and the
of AS paths associated with these routing entries, points to
relatively limited use of prefix length filtering in today'
Internet. In the absence of any corrective pressure in the form
widespread adoption of prefix length filtering, the very rapid
of global announcements of very small address blocks is likely
continue. In percentage terms, the set of prefixes spanning /25
/32 show the largest growth rates
Huston Informational [Page 10]
RFC 3221 Commentary on Inter-Domain Routing December 2001
4.5 Aggregation and
With the CIDR routing structure it is possible to advertise a
specific prefix of an existing aggregate. The purpose of this
specific announcement is to punch a 'hole' in the policy of
larger aggregate announcement, creating a different policy for
specifically referenced address prefix
Another use of this mechanism is to perform a rudimentary form
load balancing and mutual backup for multi-homed networks. In
model a network may advertise the same aggregate advertisement
each connection, but then advertise a set of specific
for each connection, altering the specific advertisements such
the load on each connection is approximately balanced. The two
of holes can be readily discerned in the routing table - while
approach of policy differentiation uses an AS path that is
from the aggregate advertisement, the load balancing and
backup configuration uses the same As path for both the aggregate
the specific advertisements. While it is difficult to
whether the use of such more specific advertisements was intended
be an exception to a more general rule or not within the
intent of CIDR deployment, there appears to be very widespread use
this mechanism within the routing table. Some 59,000 advertisements
or 55% of the total number of routing table entries, are being
to punch policy holes in existing aggregate announcements. Of
the overall majority of some 42,000 routes use distinct AS paths,
that it does appear that this is evidence of finer levels
granularity of connection policy in a densely interconnected space
While long term data is not available for the relative level of
advertisements as a proportion of the full routing table, the
level does strongly indicate that policy differentiation at a
level within existing provider aggregates is a significant driver
overall table growth
5. Current State of inter-AS routing in the
The resumption of compound growth trends within the BGP table,
the associated aspects of finer granularity of routing entries
the table form adequate grounds for consideration of
refinements to the Internet's exterior routing protocols
potential refinements to current operating practices of inter-
connectivity. With the exception of the 16 bit AS number space
there is no particular finite limit to any aspect of the BGP table
The motivation for such activity is that a long term pattern
continued growth at current rates may once again pose a
condition where the capacity of the available processors may
exceeded by some aspect of the Internet routing table
Huston Informational [Page 11]
RFC 3221 Commentary on Inter-Domain Routing December 2001
5.1 A denser interconnectivity
The decreasing unit cost of communications bearers in many part
the Internet is creating a rapidly expanding market in
points and other forms of inter-provider peering. A model
extensive interconnection at the edges of the Internet is
supplanting the deployment model of a single-homed network with
single upstream provider. The underlying deployment model of
was that of a single-homed network, allowing for a strict
of supply providers. The business imperatives driving this
mesh of interconnection in the Internet are substantial, and
casualty in this case is the CIDR-induced dampened growth of the
routing table
5.2 Multi-Homed small networks and service
It would appear that one of the major drivers of the recent growth
the BGP table is that of small networks, advertised as a /24
entry in the routing table, multi-homing with a number of peers
upstream providers. In the appropriate environment where there are
number of networks in relatively close proximity, using
relationships can reduce total connectivity costs, as compared
using a single upstream service provider. Equally significantly
multi-homing with a number of upstream providers is seen as a
of improving the overall availability of the service. In essence
multi-homing is seen as an acceptable substitute for upstream
resiliency. This has a potential side effect that when multi-
is seen as a preferable substitute for upstream provider resiliency
the upstream provider cannot command a price premium for
resiliency as an attribute of the provided service, and therefore
little economic incentive to spend the additional money required
engineer resiliency into the network. The actions of the network'
multi-homed clients then become self-fulfilling. One way
characterize this behavior is that service resiliency in the
is becoming the responsibility of the customer, not the
provider
In such an environment resiliency still exists, but rather than
a function of the bearer or switching subsystem, resiliency
provided through the function of the BGP routing system.
question is not whether this is feasible or desirable in
individual case, but whether the BGP routing system can
adequately to continue to undertake this role
Huston Informational [Page 12]
RFC 3221 Commentary on Inter-Domain Routing December 2001
5.3 Traffic Engineering via
Further driving this growth in the routing table is the use
selective advertisement of smaller prefixes along different paths
an effort to undertake traffic engineering within a multi-
environment. While there is considerable effort being undertaken
develop traffic engineering tools within a single network using
as the base flow management tool, inter-provider tools to
similar outcomes are considerably more complex when using
switching techniques
At this stage the only tool being used for inter-provider
engineering is that of the BGP routing table. Such use of
appears to place additional fine-grained prefixes into the
table. This action further exacerbates the growth and
pressures being placed on the BGP routing domain
5.4 Lack of Common Operational
There is considerable evidence of a lack of uniformity of
practices within the inter-domain routing space. This includes
use and setting of prefix filters, the use and setting of
damping parameters and level of verification undertaken on
advertisements by both the advertiser and the recipient. There
some extent of 'noise' in the routing table where
appear to be propagated well beyond their intended domain
applicability, and also where withdrawals and advertisements are
being adequately damped close to the origin of the route flap.
diversity of operating practices also extends to policies
accepting advertisements that are more specific advertisements
existing provider blocks
5.5 CIDR and Hierarchical
The current growth factors at play in the BGP table are not
susceptible to another round of CIDR deployment pressure within
operator community. The denser interconnectivity mesh,
increasing use of multi-homing with smaller address prefixes,
extension of the use of BGP to perform roles related to inter-
traffic engineering and the lack of common operating practices
point to a continuation of the trend of growth in the total size
the BGP routing table, with this growth most apparent
advertisements of smaller address blocks, and an increasing trend
these small advertisements to be punching a connectivity
'hole' in an existing provider aggregate advertisement
Huston Informational [Page 13]
RFC 3221 Commentary on Inter-Domain Routing December 2001
It may be appropriate to consider how to operate an Internet with
BGP routing table that has millions of small entries, rather than
expectation of a hierarchical routing space with at most tens
thousands of larger entries in the global routing table
6. Future Requirements for the Exterior Routing
It is beyond the scope of this document to define a scalable inter
domain routing environment and associated routing protocols
operating practices. A more modest goal is to look at the
of routing systems as understood and identify those aspects of
systems that may be applicable to the inter-domain environment as
potential set of requirements for inter-domain routing tools
6.1
The overall intent is scalability of the routing environment
Scalability can be expressed in many dimensions, including number
discrete network layer reachability entries, number of discrete
policy entries, level of dynamic change over a unit of time of
entries, time to converge to a coherent view of the connectivity
the network following changes, and so on
The basic objective behind this expressed requirement for
is that the most likely near to medium trend in the structure of
Internet is a continuation in the pattern of dense
between a large number of discrete network entities, and
impetus behind hierarchical aggregating structures. It is not
objective to place any particular metrics on scalability within
examination of requirements, aside from indicating that a
view would encompass a scale of connectivity in the inter-
space that is at least two orders of magnitude larger than
metrics of the current environment
6.2 Stability and
Any routing system should behave in a stable and predictable fashion
What is inferred from the predictability requirement is the
that under identical environmental conditions the routing
should converge to the same state. Stability implies that
routing state should be maintained for as long as the
conditions remain constant. Stability also implies a
property that minor variations in the network's state should
cause large scale instability across the entire network while a
stable routing state is reached. Instead, routing changes should
propagated only as far as necessary to reach a new stable state,
that the global requirement for stability implies some degree
locality in the behavior of the system
Huston Informational [Page 14]
RFC 3221 Commentary on Inter-Domain Routing December 2001
6.3
Any routing system should have adequate convergence properties.
adequate it is implied that within a finite time following a
in the external environment, the routing system will have reached
shared common description of the network's topology that
describes the current state of the network and is stable. In
case finite time implies a time limit that is bounded by some
limit, and this upper limit reflects the requirements of the
system. In the case of the Internet this convergence time
currently of the order of hundreds of seconds as an upper bound
convergence. This long convergence time is perceived as having
negative impact on various applications, particularly those that
time critical. A more useful upper bound for convergence is of
order of seconds or lower if it is desired to support a broad
of application classes
It is not a requirement to be able to undertake full convergence
the inter-domain routing system in the sub-second timescale
6.4 Routing
The greater the amount of information passed within the
system, and the greater the frequency of such information exchanges
the greater the level of expectation that the routing system
maintain an accurate view of the connectivity of the network
Equally, the greater the amount of information passed within
routing system, and the higher the frequency of information exchange
the higher the level of overhead consumed by operation of the
system. There is an element of design compromise in a routing
to pass enough information across the system to allow each
element to have adequate local information to reach a coherent
view of the network, yet ensure that the total routing overhead
low
7. Architectural approaches to a scalable Exterior Routing
This document does not attempt to define an inter-domain
protocol that possess all the attributes as listed above, but
number of architectural considerations can be identified that
form an integral part of the protocol design process
7.1 Policy opaqueness vs. policy
The two major approaches to routing protocols are distance vector
link state
Huston Informational [Page 15]
RFC 3221 Commentary on Inter-Domain Routing December 2001
In the distance vector protocol a routing node gathers
from its neighbors, applies local policy to this information and
distributes this updated information to its neighbors. In this
the nature of the local policy applied to the routing information
not necessarily visible to the node's neighbors, and the process
converting received route advertisements into advertised
advertisements uses a local policy process whose policy rules are
visible externally. This scenario can be described as '
opaque'. The side effect of such an environment is that a
party cannot remotely compute which routes a network may accept
which may be re-advertised to each neighbor
In link state protocols a routing node effectively broadcasts
local adjacencies, and the policies it has with respect to
adjacencies, to all nodes within the link state domain. Every
can perform an identical computation upon this set of adjacencies
associated policies in order to compute the local forwarding table
The essential attribute of this environment is that the routing
has to announce its routing policies, in order to allow a remote
to compute which routes will be accepted from which neighbor,
which routes will be advertised to each neighbor and what, if any
attributes are placed on the advertisement. Within an
routing domain the local policies are in effect metrics of each
and these polices can be announced within the routing domain
any consequent impact
In the exterior routing domain it is not the case
interconnection policies between networks are always
transparent. Various permutations of supplier /
relationships and peering relationships have associated
qualifications that are not publicly announced for
competitive reasons. The current diversity of
arrangements appears to be predicated on policy opaqueness, and
mandate a change to a model of open interconnection policies may
contrary to operational business imperatives
An inter-domain routing tool should be able to support models
interconnection where the policy associated with the
is not visible to any third party. If the architectural choice is
constrained one between distance vector and link state, then
consideration would appear to favor the continued use of a
vector approach to inter-domain routing. This choice, in turn,
implications on the convergence properties and stability of
inter-domain routing environment. If there is a broader spectrum
choice, the considerations of policy-opaqueness would still apply
Huston Informational [Page 16]
RFC 3221 Commentary on Inter-Domain Routing December 2001
7.2 The number of routing
The current issues with the trend behaviors of the BGP space can
coarsely summarized as the growth in the number of distinct
objects, the increased level of dynamic behaviors of these
(in the form of announcements and withdrawals).
This entails evaluating possible measures that can address the
rate in the number of objects in the inter-domain routing table,
separately examining measures that can reduce the level of
change in the routing table. The current routing
defines a basic unit of a route object as an originating AS
and an address prefix
In looking at the growth rate in the number of route objects,
salient observation is that the number of route objects is
byproduct of the density of the interconnection mesh and the
of discrete points where policy is imposed of route objects.
approach to reduce the growth in the number of objects is to
each object to describe larger segments of infrastructure. Such
approach could use a single route object to describe a set of
prefixes, or a collection of ASs, or a combination of the two.
most direct form of extension would be to preserve the
that each routing object represents an indivisible policy entity
However, given that one of the drivers of the increasing number
route objects is a proliferation of discrete route objects, it is
immediately apparent that this form of aggregation will prove
in addressing the growth in the number of route objects
If single route objects are to be used that encompass a set
address prefixes and a collection of ASs, then it appears
to define additional attributes within the route object to
qualify the policies associated with the object in terms of
prefixes, specific ASs and specific policy semantics that may
considered as policy exceptions to the overall
Another approach to reduce the number of route objects is to
the scope of advertisement of each routing object, allowing
object to be removed and proxy aggregated into some larger
once the logical scope of the object has been reached. This
would entail the addition of route attributes that could be used
define the circumstances where a specific route object would
subsumed by an aggregate route object without impacting the
objectives associated with the original set of advertisements
Huston Informational [Page 17]
RFC 3221 Commentary on Inter-Domain Routing December 2001
7.3 Inter-domain Traffic
Attempting to place greater levels of detail into route objects
intended to address the dual role of the current BGP system as
an inter-domain connectivity maintenance protocol and as an
traffic engineering tool
In the current environment, advertisement of more specific
with unique policy but with the same origin AS is often intended
create a traffic engineering response, where incoming traffic to
AS may be balanced across multiple paths. The outcome is that
control of the relative profile of load is placed with
originating AS. The way this is achieved is by using
knowledge of the remote AS's route selection policy to
limit the number of egress choices available to a remote AS.
most common route selection policy is the preference for
specific prefixes over larger address blocks. By
specific prefixes along specific neighbor AS connections
specific route attributes, traffic destined to these addresses
passed through the selected transit paths. This limitation of
allows the originating AS to override the potential policy choices
all other ASs, imposing its traffic import policies at a higher
than the remote AS's egress policies
An alternative approach is the use of a class of traffic
attributes that are attached to an aggregate route object.
intent of such attributes is to direct each remote AS to respond
the route object in a manner that equates to the current response
more specific advertisements, but without the need to
specific prefix route objects. However, even this approach
route objects to communicate traffic engineering policy, and the
risk remains that the route table is used to carry fine-
traffic path policies
An alternative direction is to separate the functions of
maintenance and traffic engineering, using the routing protocol
identify a number of viable paths from a source AS to a
AS, and use a distinct collection of traffic engineering tools
allow a traffic source AS to make egress path selections that
the desired traffic service profile for the traffic
There is one critical difference between traffic
approaches as used in intra-domain environments and the
inter-domain operating practices. Whereas the intra-
environment uses the ingress network element to make the
path choice to the egress point, the inter domain traffic
has the opposite intent, where a downstream AS (or egress point)
attempting to influence the path choice of an upstream AS (or
Huston Informational [Page 18]
RFC 3221 Commentary on Inter-Domain Routing December 2001
point). If explicit traffic engineering were undertaken within
inter-domain space, it is highly likely that the current
would be altered. Instead of the downstream element attempting
constrain the path choices of an upstream element, a
approach is the downstream element placing a number of
constraints on the upstream elements, and the upstream elements
a combination of these advisory constraints, dynamic
relating to path service characteristics and local policies to
an egress choice
From the perspective of the inter-domain routing environment,
measures offer the potential to remove the advertisement of
routes for traffic engineering purposes. However, there is a need
adding traffic engineering information into advertised route blocks
requiring the definition of the syntax and semantics of
engineering attributes that can be attached to route objects
7.4 Hierarchical Routing
The CIDR routing model assumed a hierarchy of providers, where
each level in the hierarchy the routing policies and address space
networks at the lower level of hierarchy were subsumed by the
level up (or 'upstream') provider. The connectivity policy
by this model is also a hierarchical model, where
connections within a single level of the hierarchy are not
beyond the networks of the two parties
A number of external factors are increasing the density
interconnection including decreasing unit costs of
services and the increasing use of exchange points to augment point
to-point connectivity models with point-to-multi-point facilities
The outcome of these external factors is a significant reduction
the hierarchical nature of the inter-domain space. Such a trend
be viewed with concern given the common approach of using
as a tool for scaling routing systems. BGP falls within
approach, and relies on hierarchies in the address space to
the number of independently routing objects. The outcomes of
characteristic of the Internet in terms of the routing space is
increasing number of distinct route policies that are associated
each multi-homed network within the Internet
One way to limit the proliferation of such policies across the
inter-domain space is to associate attributes to such
that specify the conditions whereby a remote transit AS may proxy
aggregate this route object with other route objects
Huston Informational [Page 19]
RFC 3221 Commentary on Inter-Domain Routing December 2001
7.5 Extend or Replace
A final consideration is to consider whether these requirements
best be met by an approach of a set of upward-compatible
to BGP, or by a replacement to BGP. No recommendation is made here
and this is a topic requiring further investigation
The general approach in extending BGP appears to lie in
the number of supported transitive route attributes, allowing
route originator greater control in specifying the scope
propagation of the route and the intended outcome in terms of
and traffic engineering. It may also be necessary to allow
sessions to negotiate additional functionality intended to
the convergence behavior of the protocol. Whether such changes
produce a scalable and useful outcome in terms of inter-
routing remains, at this stage, an open question
An alternative approach is that of a replacement protocol, and
an approach may well be based on the adoption of a link-
behavior. The issues of policy opaqueness and link-state
have been described above. The other major issue with such
approach is the need to limit the extent of link state flooding
where the inter-domain space would need some further levels
imposed structure similar to intra-domain areas. Such structure
well imply the need for an additional set of operator inter
relationships such as mutual transit, and this may prove
to adapt to existing practices
The potential sets of actions include more than extend or replace
BGP protocol. A third approach is to continue to use BGP as
basic means of propagating route objects and their associated
paths and other attributes, and use one or more overlay protocols
support inter-domain traffic engineering and other forms of inter
domain policy negotiation. This approach would appear to offer
means of transition for the large installed base currently using BGP
as their inter-domain routing protocol, placing
functionality in the overlay protocols while leaving the
functionality of BGP4 intact. The resultant inter-
between BGP and the overlay protocols would require very
attention, as this would be the most critical aspect of such
approach
Huston Informational [Page 20]
RFC 3221 Commentary on Inter-Domain Routing December 2001
8. Directions for Further
While there may exist short term actions based on providing
incentives for network operators to remove redundant or
grouped entries from the BGP routing table, such actions are
term palliative measures, and will not provide long term answers
the need to a scalable inter-domain routing protocol
One potential short term protocol refinement is to allow a set
grouped advertisements to be aggregated into a single
advertisement. This form of proxy aggregation would take a set
bit-wise aligned routing entries with matching route attributes,
under certain well identified circumstances, aggregate these
entries into a single re-advertised aggregate routing entry.
technique removes information from the routing system, and some
must be taken to define a set of proxy aggregation conditions that
not materially alter the flow of traffic, or the ability
originating ASes to announce routing policy
A further refinement to this approach is to consider the
of the syntax and semantics of a number of additional
attributes. Such attributes could define the extent to
specific route advertisements should be propagated in the inter
domain space, allowing the advertisement to be subsumed by a
aggregate advertisement at the boundary of this domain. This
be used to form part of the preconditions of automated
aggregation of specific routes, and also limit the extent to
announcement and withdrawals are propagated across the
domain
It is unclear that such measures would result in substantial
term changes to the scaling and convergence properties of BGP4.
Taking the requirement set enumerated in section 6 of this document
one approach to the longer term requirements may be to preserve
number of attributes of the current BGP protocol, while refine
aspects of the protocol to improve its scaling and
properties. A minimal set of alterations could retain the
System concept to allow for boundaries of information summarization
as well as retaining the approach of associating each
advertisement with an originating AS. The concept of
opaqueness would also be retained in such an approach, implying
each AS accepts a set of route advertisements, applies local
constraints, and re-advertises those advertisements permitted by
local policy constraints. It could be feasible to
alterations to the distance vector path selection algorithm
particularly as it relates to intermediate states during
of a route withdrawal. It is also feasible to consider the use
compound route attributes, allowing a route object to include
Huston Informational [Page 21]
RFC 3221 Commentary on Inter-Domain Routing December 2001
aggregate route, and a number of specifics of the aggregate route
and attach attributes that may apply to the aggregate or a
address prefix. Such route attributes could be used to
multi-homing and inter-domain traffic engineering mechanisms.
overall intent of this approach is to address the major
in the inter-domain routing space without using an increasing set
globally propagated specific route objects
A potential applied research topic is to consider the feasibility
de-coupling the requirements of inter-domain connectivity
with the applications of policy constraints and the issues of sender
and/or receiver-managed traffic engineering requirements. Such
approach may use a link-state protocol as a means of maintaining
consistent view of the topology of inter-domain network, and then
some form of overlay protocol to negotiate policy requirements
each AS, and use a further overlay to support inter-domain
engineering requirements. The underlying assumption of such
approach is that by dividing up the functional role of inter-
routing into distinct components each component will have
scaling and convergence properties which in turn to result
superior properties for the entire routing system. Obviously,
assumption requires some testing
Research topics with potential longer term application include
approach of drawing a distinction between a network's identity,
network's location relative to other networks, and a feasible
between a source and destination network that satisfies
policy and traffic engineering constraints. Again the intent of
an approach would be to divide the current routing function into
number of distinct scalable components
9. Security
Any adopted inter-domain routing protocol needs to be secure
disruption. Disruption comes from two primary sources
- Accidental
- Malicious
Given past experience with routing protocols, both can be
sources of harm
Given that it is not reasonable to guarantee the security of all
routers involved in the global Internet inter-domain routing system
there is also every reason to believe that malicious attacks may
from peer routers, in addition to coming from external sources
Huston Informational [Page 22]
RFC 3221 Commentary on Inter-Domain Routing December 2001
A protocol design should therefore consider how to minimize
damage to the overall routing computation that can be caused by
single or small set of misbehaving routers
The routing system itself needs to be resilient against accidental
malicious advertisements of a route object by a route server
entitled to generate such an advertisement. This implies
things, including the need for cryptographic validation
announcements, cryptographic protection of various critical
messages and an accurate and trusted database of routing
via which authorization can be checked
10.
[1] Bradner, S., "The Internet Standards Process -- Revision 3",
BCP 9, RFC 2026, October 1996.
[2] Clark, D., Chapin, L., Cerf, V., Braden, R. and R. Hobby
"Towards the Future Internet Architecture", RFC 1287,
1991.
[3] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6)
Specification, RFC 2460, December 1998.
[4] Srisuresh, P. and K. Egevang, "Traditional IP Network
Translator (Traditional NAT)", RFC 3022, January 2001.
[5] Fuller, V., Li, T., Yu, J. and K. Varadhan, "Classless Inter
Domain Routing (CIDR): an Address Assignment and
Strategy", RFC 1519, September 1993.
[6] Huston, G., "The BGP Routing Table", The Internet
Journal, vol. 4, No. 1, March 2001.
[7] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
RFC 1771, March 1995.
[8] Vohara, Q. and E. Chen, "BGP support for four-octet AS
space", Work in Progress
[9] Hain, T., "Architectural Implications of NAT", RFC 2993,
November 2000.
[10] Labovitz, C., Ahuja, A., Bose, A. and J. Jahanian, "
Internet Routing Convergence", Proceedings ACM SIGCOMM 2000,
August 2000.
Huston Informational [Page 23]
RFC 3221 Commentary on Inter-Domain Routing December 2001
[11] Lothberg, P., personal communication, December 2000.
11.
This document is the outcome of a collaborative effort of the IAB
and the editor acknowledges the contributions of the members of
IAB in the preparation of the document. The contributions of
Leslie, Thomas Narten and Abha Ahuja in reviewing this document
also acknowledged
12.
Internet Architecture
Email: iab@ietf.
Geoff
5/490 Northbourne
Dickson ACT 2602
EMail: gih@telstra.
Huston Informational [Page 24]
RFC 3221 Commentary on Inter-Domain Routing December 2001
13. Full Copyright
Copyright (C) The Internet Society (2001). All Rights Reserved
This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English
The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns
This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE
Funding for the RFC Editor function is currently provided by
Internet Society
Huston Informational [Page 25]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
