As per Relevance of the word bandwidth, we have this rfc below:
Network Working Group Y. Rekhter,
Request for Comments: 1265 T.J. Watson Research Center, IBM Corp
October 1991
BGP Protocol
1. Status of this Memo
This memo provides information for the Internet community. It
not specify an Internet standard. Distribution of this memo
unlimited
2. Introduction
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 (BGP). This report summarizes the
feature of BGP, and analyzes the protocol with respect to scaling
performance. This is the first of two reports on the BGP protocol
BGP is an inter-autonomous system routing protocol designed for
TCP/IP internets. Version 1 of the BGP protocol was published in
1105. Since then BGP versions 2 and 3 have been developed. Version 2
was documented in RFC 1163. Version 3 is documented in [1].
changes between versions 1, 2 and 3 are explained in Appendix 3
[1].
Possible applications of BGP in the Internet are documented in [2].
Please send comments to iwg@rice.edu
3. Acknowledgements
The BGP protocol has been developed by the IWG/BGP Working Group
the Internet Engineering Task Force. We would like to express
deepest thanks to Guy Almes (Rice University) who was the
chairman of the IWG Working Group. We also like to explicitly
Bob Braden (ISI) and Bob Hinden (BBN) for the review of this
as well as their constructive and valuable comments
4. Key features and algorithms of the BGP 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
BGP Working Group [Page 1]
RFC 1265 BGP Protocol Analysis October 1991
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
routing policy decisions at the autonomous system level may
enforced
The key feature of the protocol is the notion of Path Attributes
This feature provides 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
the AS-PATH. As reachability information traverses the Internet,
information is augmented by the list of autonomous systems that
been traversed thusfar, forming the AS-PATH. The AS-PATH
straightforward suppression of the looping of routing information.
addition, the AS-PATH serves as a powerful and versatile
for policy-based routing
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
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
autonomous system
To allow graceful coexistence with EGP, BGP provides support
carrying EGP derived exterior routes. BGP also allows to
BGP Working Group [Page 2]
RFC 1265 BGP Protocol Analysis October 1991
statically defined exterior routes
5. BGP performance characteristics and scalability
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
5.1 Link bandwidth and CPU utilization
Immediately after the initial BGP connection setup, the
exchange complete set of routing information. If we denote the
number of networks 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
O(N + M * A
(provided that an implementation supports multiple networks
message as outlined in Appendix 5 of [1]). This information
roughly on the order of the number of networks reachable via
peer (see also Section 5.2).
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).
# Networks Mean AS Distance # AS's
---------- ---------------- ------ ---------
2,100 5 59 9,000
4,000 10 100 18,000
10,000 15 300 49,000
100,000 20 3,000 520,000
Note that most of the bandwidth is consumed by the exchange of
Network Reachability Information
BGP Working Group [Page 3]
RFC 1265 BGP Protocol Analysis October 1991
After the initial exchange is completed, the amount of bandwidth
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
case multiple networks can be grouped into a single UPDATE message
thus significantly reducing the amount of bandwidth required (
also Appendix 5 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 5 of [1]). We'd like
point out, that regardless of BGP, one should not underestimate
significance of the stability in the Internet. Growth of the
will make the stability issue one of the most crucial one. It
important to realize that BGP, by itself, does not introduce
instabilities in the Internet. Current observations in the
show that the instabilities are largely due to the ill-
routing within the autonomous systems that compose the Internet
Therefore, while providing BGP with mechanisms to address
stability issue, we feel that the right way to handle the issue is
address it at the root of the problem, and to come up with intra
autonomous routing schemes that exhibit reasonable stability
It also may be instructive to compare bandwidth and CPU
BGP Working Group [Page 4]
RFC 1265 BGP Protocol Analysis October 1991
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).
5.2 Memory requirements
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
BGP Working Group [Page 5]
RFC 1265 BGP Protocol Analysis October 1991
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).
# 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
2,000 entries, one might ask whether it would be possible to have
functional router with a table that will have 20,000 entries.
the answer to this question is completely independent of BGP. On
other hand the answer to the original questions (that was asked
respect to BGP) is directly related to the latter question.
interesting comments were given by Paul Tsuchiya in his review of
in March of 1990 (as part of the BGP review committee appointed
Bob Hinden). In the review he said that, "BGP does not scale well
This is not really the fault of BGP. It is the fault of the flat
address space. Given the flat IP address space, any routing
must carry network numbers in its updates." To reiterate, BGP
with respect to the memory requirements are directly related to
underlying Internet Protocol (IP), and specifically the
scheme employed by IP. BGP would provide much better scaling
environments with more flexible addressing schemes. It should
pointed out that with very minor additions BGP can be extended
support hierarchies of autonomous system. Such hierarchies,
with an addressing scheme that would allow more flexible
aggregation capabilities, can be utilized by BGP, thus
practically unlimited scaling capabilities of the protocol
BGP Working Group [Page 6]
RFC 1265 BGP Protocol Analysis October 1991
6. Applicability of BGP
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
"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 used
the current Internet. Note that some policies cannot be supported
the "hop-by-hop" routing paradigm and thus require techniques such
source routing to enforce. For example, BGP does not enable one
to send traffic to a neighbor AS intending that the traffic take
different route from that taken by traffic originating in
neighbor AS. On the other hand, BGP can support any
conforming to the "hop-by-hop" routing paradigm. Since the
Internet uses only the "hop-by-hop" routing paradigm and since
can support any policy that conforms to that paradigm, BGP is
applicable as an inter-AS 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.
BGP Working Group [Page 7]
RFC 1265 BGP Protocol Analysis October 1991
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
[1] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP
3)", RFC 1267, cisco Systems, T.J. Watson Research Center,
Corp., October 1991.
[2] Rekhter, Y., and P. Gross, Editors, "Application of the
Gateway Protocol in the Internet", RFC 1268, T.J. Watson
Center, IBM Corp., ANS, October 1991.
Security
Security issues are not discussed in this memo
Author's
Yakov
T.J. Watson Research Center IBM
P.O. Box 218
Yorktown Heights, NY 10598
Phone: (914) 945-3896
EMail: yakov@watson.ibm.
IETF BGP WG mailing list: iwg@rice.
To be added: iwg-request@rice.
BGP Working Group [Page 8]
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
