As per Relevance of the word autonomous, we have this rfc below:
Network Working Group P. Traina,
Request for Comments: 1774 cisco
Category: Informational March 1995
BGP-4 Protocol
Status of this
This memo provides information for the Internet community. This
does not specify an Internet standard of any kind. Distribution
this memo is unlimited
The purpose of this report is to document how the requirements
advancing a routing protocol to Draft Standard have been satisfied
the Border Gateway Protocol version 4 (BGP-4). This report
the key features of BGP, and analyzes the protocol with respect
scaling and performance. This is the first of two reports on the
protocol
BGP-4 is an inter-autonomous system routing protocol designed
TCP/IP internets. Version 1 of the BGP protocol was published in
1105. Since then BGP versions 2, 3, and 4 have been developed
Version 2 was documented in RFC 1163. Version 3 is documented
RFC1267. The changes between versions are explained in Appendix 2
[1].
Possible applications of BGP in the Internet are documented in [2].
Please send comments to iwg@ans.net
Key features and algorithms of the BGP-4 protocol
This section summarizes the key features and algorithms of the
protocol. BGP is an inter-autonomous system routing protocol; it
designed to be used between multiple autonomous systems. BGP
that routing within an autonomous system is done by an intra
autonomous system routing protocol. BGP does not make any
about intra-autonomous system routing protocols employed by
various autonomous systems. Specifically, BGP does not require
autonomous systems to run the same intra-autonomous system
protocol
BGP is a real inter-autonomous system routing protocol. It imposes
constraints on the underlying Internet topology. The
exchanged via BGP is sufficient to construct a graph of
systems connectivity from which routing loops may be pruned and
Traina [Page 1]
RFC 1774 BGP-4 Protocol Analysis March 1995
routing policy decisions at the autonomous system level may
enforced
The key features of the protocol are the notion of path
and aggregation of network layer reachability information (NLRI).
Path attributes provide BGP with flexibility and expandability.
attributes are partitioned into well-known and optional.
provision for optional attributes allows experimentation that
involve a group of BGP routers without affecting the rest of
Internet. New optional attributes can be added to the protocol
much the same fashion as new options are added to the
protocol, for instance
One of the most important path attributes is the AS-PATH.
reachability information traverses the Internet, this information
augmented by the list of autonomous systems that have been
thus far, forming the AS-PATH. The AS-PATH allows
suppression of the looping of routing information. In addition,
AS-PATH serves as a powerful and versatile mechanism for policy-
routing
BGP-4 enhances the AS-PATH attribute to include sets of
systems as well as lists. This extended format allows
aggregate routes to carry path information from the more
routes used to generate the aggregate
BGP uses an algorithm that cannot be classified as either a
distance vector, or a pure link state. Carrying a complete AS path
the AS-PATH attribute allows to reconstruct large portions of
overall topology. That makes it similar to the link state algorithms
Exchanging only the currently used routes between the peers makes
similar to the distance vector algorithms
To conserve bandwidth and processing power, BGP uses
updates, where after the initial exchange of complete
information, a pair of BGP routers exchanges only changes (deltas)
that information. Technique of incremental updates requires
transport between a pair of BGP routers. To achieve
functionality BGP uses TCP as its transport
In addition to incremental updates, BGP-4 has added the concept
route aggregation so that information about groups of networks
represented as a single entity
BGP is a self-contained protocol. That is, it specifies how
information is exchanged both between BGP speakers in
autonomous systems, and between BGP speakers within a
Traina [Page 2]
RFC 1774 BGP-4 Protocol Analysis March 1995
autonomous system
To allow graceful coexistence with EGP and OSPF, BGP provides
for carrying both EGP and OSPF derived exterior routes BGP
allows to carry statically defined exterior routes or routes
by other IGP information
BGP performance characteristics and
In this section we'll try to answer the question of how much
bandwidth, router memory and router CPU cycles does the BGP
consume under normal conditions. We'll also address the
of BGP, and look at some of its limits
BGP does not require all the routers within an autonomous system
participate in the BGP protocol. Only the border routers that
connectivity between the local autonomous system and its
autonomous systems participate in BGP. Constraining the set
participants is just one way of addressing the scaling issue
Link bandwidth and CPU
Immediately after the initial BGP connection setup, the
exchange complete set of routing information. If we denote the
number of routes in the Internet by N, the mean AS distance of
Internet by M (distance at the level of an autonomous system
expressed in terms of the number of autonomous systems), the
number of autonomous systems in the Internet by A, and assume
the networks are uniformly distributed among the autonomous systems
then the worst case amount of bandwidth consumed during the
exchange between a pair of BGP speakers
MR = O(N + M * A
The following table illustrates typical amount of bandwidth
during the initial exchange between a pair of BGP speakers based
the above assumptions (ignoring bandwidth consumed by the
Header).
# NLRI Mean AS Distance # AS's
---------- ---------------- ------ ---------
10,000 15 300 49,000
20,000 8 400 86,000 bytes *
40,000 15 400 172,000
100,000 20 3,000 520,000
* the actual "size" of the Internet at the the time of
document's
Traina [Page 3]
RFC 1774 BGP-4 Protocol Analysis March 1995
Note that most of the bandwidth is consumed by the exchange of
Network Layer Reachability Information (NLRI).
BGP-4 was created specifically to reduce the amount of NLRI
carried and exchanged by border routers. BGP-4, along with CIDR [4]
has introduced the concept of the "Supernet" which describes
power-of-two aggregation of more than one class-based network
Due to the advantages of advertising a few large aggregate
instead of many smaller class-based individual networks, it
difficult to estimate the actual reduction in bandwidth
processing that BGP-4 has provided over BGP3. If we simply
all aggregate blocks into their individual class-based networks,
would not take into account "dead" space that has been reserved
future expansion. The best metric for determining the success
BGP-4's aggregation is to sample the number NLRI entries in
globally connected Internet today and compare it to projected
rates before BGP-4 was deployed
In January of 1994, router carrying a full routing load for
globally connected Internet had approximately 19,000 network
(this number is not exact due to local policy variations). The
deployment working group estimated that the growth rate at that
was over 1000 new networks per month and increasing. Since
widespread deployment of BGP-4, the growth rate has
significantly and a sample done at the end of November 1994
approximately 21,000 entries present, as opposed to the
30,000.
CPU cycles consumed by BGP depends only on the stability of
Internet. If the Internet is stable, then the only link bandwidth
router CPU cycles consumed by BGP are due to the exchange of the
KEEPALIVE messages. The KEEPALIVE messages are exchanged only
peers. The suggested frequency of the exchange is 30 seconds.
KEEPALIVE messages are quite short (19 octets), and require
no processing. Therefore, the bandwidth consumed by the
messages is about 5 bits/sec. Operational experience confirms
the overhead (in terms of bandwidth and CPU) associated with
KEEPALIVE messages should be viewed as negligible. If the
is unstable, then only the changes to the reachability
(that are caused by the instabilities) are passed between
(via the UPDATE messages). If we denote the number of routing
per second by C, then in the worst case the amount of
consumed by the BGP can be expressed as O(C * M). The
overhead per UPDATE message occurs when each UPDATE message
only a single network. It should be pointed out that in
routing changes exhibit strong locality with respect to the AS path
That is routes that change are likely to have common AS path. In
Traina [Page 4]
RFC 1774 BGP-4 Protocol Analysis March 1995
case multiple networks can be grouped into a single UPDATE message
thus significantly reducing the amount of bandwidth required (
also Appendix 6.1 of [1]).
Since in the steady state the link bandwidth and router CPU
consumed by the BGP protocol are dependent only on the stability
the Internet, but are completely independent on the number
networks that compose the Internet, it follows that BGP should
no scaling problems in the areas of link bandwidth and router
utilization, as the Internet grows, provided that the
stability of the inter-AS connectivity (connectivity between ASs)
the Internet can be controlled. Stability issue could be addressed
introducing some form of dampening (e.g., hold downs). Due to
nature of BGP, such dampening should be viewed as a local to
autonomous system matter (see also Appendix 6.3 of [1]). It
important to point out, that regardless of BGP, one should
underestimate the significance of the stability in the Internet
Growth of the Internet has made the stability issue one of the
crucial ones. It is important to realize that BGP, by itself,
not introduce any instabilities in the Internet. Current
in the NSFNET show that the instabilities are largely due to
ill-behaved routing within the autonomous systems that compose
Internet. Therefore, while providing BGP with mechanisms to
the stability issue, we feel that the right way to handle the
is to address it at the root of the problem, and to come up
intra-autonomous routing schemes that exhibit reasonable stability
It also may be instructive to compare bandwidth and CPU
of BGP with EGP. While with BGP the complete information is
only at the connection establishment time, with EGP the
information is exchanged periodically (usually every 3 minutes).
that both for BGP and for EGP the amount of information exchanged
roughly on the order of the networks reachable via a peer that
the information (see also Section 5.2). Therefore, even if
assumes extreme instabilities of BGP, its worst case behavior will
the same as the steady state behavior of EGP
Operational experience with BGP showed that the incremental
approach employed by BGP presents an enormous improvement both in
area of bandwidth and in the CPU utilization, as compared
complete periodic updates used by EGP (see also presentation
Dennis Ferguson at the Twentieth IETF, March 11-15, 1991, St.Louis).
Traina [Page 5]
RFC 1774 BGP-4 Protocol Analysis March 1995
Memory
To quantify the worst case memory requirements for BGP, denote
total number of networks in the Internet by N, the mean AS
of the Internet by M (distance at the level of an autonomous system
expressed in terms of the number of autonomous systems), the
number of autonomous systems in the Internet by A, and the
number of BGP speakers that a system is peering with by K (note
K will usually be dominated by the total number of the BGP
within a single autonomous system). Then the worst case
requirements (MR) can be expressed
MR = O((N + M * A) * K
In the current NSFNET Backbone (N = 2110, A = 59, and M = 5) if
network is stored as 4 octets, and each autonomous system is
as 2 octets then the overhead of storing the AS path information (
addition to the full complement of exterior routes) is less than 7
percent of the total memory usage
It is interesting to point out, that prior to the introduction of
in the NSFNET Backbone, memory requirements on the NSFNET
routers running EGP were on the order of O(N * K). Therefore,
extra overhead in memory incurred by the NSFNET routers after
introduction of BGP is less than 7 percent
Since a mean AS distance grows very slowly with the total number
networks (there are about 60 autonomous systems, well over 2,000
networks known in the NSFNET backbone routers, and the mean
distance of the current Internet is well below 5), for all
purposes the worst case router memory requirements are on the
of the total number of networks in the Internet times the number
peers the local system is peering with. We expect that the
number of networks in the Internet will grow much faster than
average number of peers per router. Therefore, scaling with
to the memory requirements is going to be heavily dominated by
factor that is linearly proportional to the total number of
in the Internet
The following table illustrates typical memory requirements of
router running BGP. It is assumed that each network is encoded as 4
bytes, each AS is encoded as 2 bytes, and each networks is
via some fraction of all of the peers (# BGP peers/per net).
Traina [Page 6]
RFC 1774 BGP-4 Protocol Analysis March 1995
# Networks Mean AS Distance # AS's # BGP peers/per net Memory
---------- ---------------- ------ ------------------- ----------
2,100 5 59 3 27,000
4,000 10 100 6 108,000
10,000 15 300 10 490,000
100,000 20 3,000 20 1,040,000
To put memory requirements of BGP in a proper perspective, let's
to put aside for a moment the issue of what information is used
construct the forwarding tables in a router, and just focus on
forwarding tables themselves. In this case one might ask about
limits on these tables. For instance, given that right now
forwarding tables in the NSFNET Backbone routers carry well
20,000 entries, one might ask whether it would be possible to have
functional router with a table that will have 200,000 entries
Clearly the answer to this question is completely independent of BGP
On the other hand the answer to the original questions (that
asked with respect to BGP) is directly related to the
question. Very interesting comments were given by Paul Tsuchiya
his review of BGP in March of 1990 (as part of the BGP
committee appointed by Bob Hinden). In the review he said that, "
does not scale well. This is not really the fault of BGP. It is
fault of the flat IP address space. Given the flat IP address space
any routing protocol must carry network numbers in its updates."
the introduction of CIDR [4] and BGP-4, we have attempted to
this limitation. Unfortunately, we cannot erase history nor
BGP-4 solve the problems inherent with inefficient assignment
future address blocks
To reiterate, BGP limits with respect to the memory requirements
directly related to the underlying Internet Protocol (IP),
specifically the addressing scheme employed by IP. BGP would
much better scaling in environments with more flexible
schemes. It should be pointed out that with only very
additions BGP was extended to support hierarchies of
system [8]. Such hierarchies, combined with an addressing scheme
would allow more flexible address aggregation capabilities, can
utilized by BGP-like protocols, thus providing practically
scaling capabilities
Applicability of
In this section we'll try to answer the question of what
is BGP well suited, and for what is it not suitable? Partially
question is answered in the Section 2 of [1], where the
states the following
Traina [Page 7]
RFC 1774 BGP-4 Protocol Analysis March 1995
"To characterize the set of policy decisions that can be
using BGP, one must focus on the rule that an AS advertises to
neighbor ASs only those routes that it itself uses. This
reflects the "hop-by-hop" routing paradigm generally
throughout the current Internet. Note that some policies
be supported by the "hop-by-hop" routing paradigm and thus
techniques such as source routing to enforce. For example,
does not enable one AS to send traffic to a neighbor AS
that the traffic take a different route from that taken by
originating in the neighbor AS. On the other hand, BGP
support any policy conforming to the "hop-by-hop"
paradigm. Since the current Internet uses only the "hop-by-hop
routing paradigm and since BGP can support any policy
conforms to that paradigm, BGP is highly applicable as an inter-
routing protocol for the current Internet."
While BGP is well suitable for the current Internet, it is
almost a necessity for the current Internet as well.
experience with EGP showed that it is highly inadequate for
current Internet. Topological restrictions imposed by EGP
unjustifiable from the technical point of view, and
from the practical point of view. Inability of EGP to
handle information exchange between peers is a cause of
routing instabilities in the operational Internet. Finally
information provided by BGP is well suitable for enforcing a
of routing policies
Rather than trying to predict the future, and overload BGP with
variety of functions that may (or may not) be needed, the
of BGP took a different approach. The protocol contains only
functionality that is essential, while at the same time
flexible mechanisms within the protocol itself that allow to
its functionality. Since BGP was designed with flexibility
expandability in mind, we think it should be able to address new
evolving requirements with relative ease. The existence proof of
statement may be found in the way how new features (like repairing
partitioned autonomous system with BGP) are already introduced in
protocol
To summarize, BGP is well suitable as an inter-autonomous
routing protocol for the current Internet that is based on IP (
791) as the Internet Protocol and "hop-by-hop" routing paradigm.
is hard to speculate whether BGP will be suitable for
environments where internetting is done by other than IP protocols
or where the routing paradigm will be different
Traina [Page 8]
RFC 1774 BGP-4 Protocol Analysis March 1995
Security
Security issues are not discussed in this memo
The BGP-4 protocol has been developed by the IDR/BGP Working Group
the Internet Engineering Task Force. I would like to express
to Yakov Rekhter for providing RFC 1265. This document is only
minor update to the original text. I'd also like to explicitly
Yakov Rekhter and Tony Li for their review of this document as
as their constructive and valuable comments
Editor's
Paul
cisco Systems, Inc
170 W. Tasman Dr
San Jose, CA 95134
EMail: pst@cisco.
Traina [Page 9]
RFC 1774 BGP-4 Protocol Analysis March 1995
[1] Rekhter, Y., and T., Li, "A Border Gateway Protocol 4 (BGP-4)",
RFC 1771, T.J. Watson Research Center, IBM Corp., cisco Systems
March 1995.
[2] Rekhter, Y., and P. Gross, Editors, "Application of the
Gateway Protocol in the Internet", RFC 1772, T.J. Watson
Center, IBM Corp., MCI, March 1995.
[3] Willis, S., Burruss, J., and J. Chu, "Definitions of
Objects for the Fourth Version of the Border Gateway
(BGP-4) using SMIv2", RFC 1657, Wellfleet Communications Inc.,
IBM Corp., July 1994.
[4] Fuller V., Li. T., Yu J., and K. Varadhan, "Classless Inter
Domain Routing (CIDR): an Address Assignment and
Strategy", RFC 1519, BARRNet, cisco, MERIT, OARnet,
1993.
[6] Moy J., "Open Shortest Path First Routing Protocol (Version 2)",
RFC 1257, Proteon, August 1991.
[7] Varadhan, K., Hares S., and Y. Rekhter, "BGP4/IDRP for IP---
Interaction", Work in Progress
[8] ISO/IEC 10747, Kunzinger, C., Editor, "Inter-Domain
Protocol", October 1993.
Traina [Page 10]
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
