draft-ietf-idr-bgp-analysis-06.txt   draft-ietf-idr-bgp-analysis-07.txt 
INTERNET-DRAFT D. Meyer INTERNET-DRAFT D. Meyer
draft-ietf-idr-bgp-analysis-06.txt K. Patel draft-ietf-idr-bgp-analysis-07.txt K. Patel
Category Informational Category Informational
Expires: February 2005 August 2004 Expires: June 2005 December 2004
BGP-4 Protocol Analysis BGP-4 Protocol Analysis
<draft-ietf-idr-bgp-analysis-06.txt> <draft-ietf-idr-bgp-analysis-07.txt>
Status of this Memo Status of this Memo
Status of this Memo Status of this Memo
This document is an Internet-Draft and is subject to all This document is an Internet-Draft and is subject to all
provisions of section 3 of RFC 3667. By submitting this provisions of section 3 of RFC 3667. By submitting this
Internet-Draft, each author represents that any applicable patent Internet-Draft, each author represents that any applicable patent
or other IPR claims of which he or she is aware have been or will or other IPR claims of which he or she is aware have been or will
be disclosed, and any of which he or she become aware will be be disclosed, and any of which he or she become aware will be
disclosed, in accordance with RFC 3668. disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet
Task Force (IETF), its areas, and its working groups. Note that Engineering Task Force (IETF), its areas, and its working
other groups may also distribute working documents as groups. Note that other groups may also distribute working
Internet-Drafts. documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use documents at any time. It is inappropriate to use
Internet-Drafts as reference material or to cite them other than Internet-Drafts as reference material or to cite them other
as "work in progress." than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed
http://www.ietf.org/shadow.html. at http://www.ietf.org/shadow.html.
This document is a product of the IDR Working Group WG. Comments should be This document is a product of the IDR Working Group
addressed to the authors, or the mailing list at idr@ietf.org. WG. Comments should be addressed to the authors, or the
mailing list at idr@ietf.org.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved. Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract Abstract
The purpose of this report is to document how the requirements for The purpose of this report is to document how the requirements for
advancing a routing protocol from Draft Standard to full Standard advancing a routing protocol from Draft Standard to full Standard
have been satisfied by Border Gateway Protocol version 4 (BGP-4). have been satisfied by Border Gateway Protocol version 4 (BGP-4).
This report satisfies the requirement for "the second report", as This report satisfies the requirement for "the second report", as
described in Section 6.0 of [RFC1264]. In order to fulfill the described in Section 6.0 of [RFC1264]. In order to fulfill the
requirement, this report augments [RFC1774] and summarizes the key requirement, this report augments [RFC1774] and summarizes the key
features of BGP-4 protocol, and analyzes the protocol with respect to features of BGP-4 protocol, and analyzes the protocol with respect
scaling and performance. to scaling and performance.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Key Features and algorithms of the BGP protocol. . . . . . . . 4 2. Key Features and algorithms of the BGP protocol. . . . . . . . 4
2.1. Key Features. . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Key Features. . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. BGP Algorithms. . . . . . . . . . . . . . . . . . . . . . . 5 2.2. BGP Algorithms. . . . . . . . . . . . . . . . . . . . . . . 5
2.3. BGP Finite State Machine (FSM). . . . . . . . . . . . . . . 6 2.3. BGP Finite State Machine (FSM). . . . . . . . . . . . . . . 6
3. BGP Capabilities . . . . . . . . . . . . . . . . . . . . . . . 7 3. BGP Capabilities . . . . . . . . . . . . . . . . . . . . . . . 7
4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 7 4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 7
skipping to change at page 4, line 16 skipping to change at page 4, line 16
BGP-4 is an inter-autonomous system routing protocol designed for BGP-4 is an inter-autonomous system routing protocol designed for
TCP/IP internets. Version 1 of the BGP-4 protocol was published in TCP/IP internets. Version 1 of the BGP-4 protocol was published in
[RFC1105]. Since then BGP versions 2, 3, and 4 have been developed. [RFC1105]. Since then BGP versions 2, 3, and 4 have been developed.
Version 2 was documented in [RFC1163]. Version 3 is documented in Version 2 was documented in [RFC1163]. Version 3 is documented in
[RFC1267]. Version 4 is documented in the [BGP4] (version 4 of BGP [RFC1267]. Version 4 is documented in the [BGP4] (version 4 of BGP
will hereafter be referred to as BGP). The changes between versions will hereafter be referred to as BGP). The changes between versions
are explained in Appendix A of [BGP4]. Possible applications of BGP are explained in Appendix A of [BGP4]. Possible applications of BGP
in the Internet are documented in [RFC1772]. in the Internet are documented in [RFC1772].
BGP introduced support for Classless InterDomain Routing [CIDR]. BGP introduced support for Classless Inter-Domain Routing
Since earlier versions of BGP lacked the support for CIDR, they are [RFC1519]. Since earlier versions of BGP lacked the support
considered obsolete and unusable in today's Internet. for CIDR, they are considered obsolete and unusable in
today's Internet.
2. Key Features and algorithms of the BGP protocol 2. Key Features and algorithms of the BGP protocol
This section summarizes the key features and algorithms of the BGP This section summarizes the key features and algorithms of the
protocol. BGP is an inter-autonomous system routing protocol; it is BGP protocol. BGP is an inter-autonomous system routing
designed to be used between multiple autonomous systems. BGP assumes protocol; it is designed to be used between multiple
that routing within an autonomous system is done by an intra- autonomous systems. BGP assumes that routing within an
autonomous system routing protocol. BGP also assumes that data autonomous system is done by an intra-autonomous system
packets are routed from source towards destination independent of the routing protocol. BGP also assumes that data packets are
source. BGP does not make any assumptions about intra-autonomous routed from source towards destination independent of the
system routing protocols deployed within the various autonomous source. BGP does not make any assumptions about
systems. Specifically, BGP does not require all autonomous systems to intra-autonomous system routing protocols deployed within the
run the same intra-autonomous system routing protocol (i.e., interior various autonomous systems. Specifically, BGP does not require
gateway protocol or IGP). all autonomous systems to run the same intra-autonomous system
routing protocol (i.e., interior gateway protocol or IGP).
Finally, note that BGP is a real inter-autonomous system routing Finally, note that BGP is a real inter-autonomous system
protocol, and as such it imposes no constraints on the underlying routing protocol, and as such it imposes no constraints on the
interconnect topology of the autonomous systems. The information underlying interconnect topology of the autonomous
exchanged via BGP is sufficient to construct a graph of autonomous systems. The information exchanged via BGP is sufficient to
systems connectivity from which routing loops may be pruned and many construct a graph of autonomous systems connectivity from
routing policy decisions at the autonomous system level may be which routing loops may be pruned and many routing policy
enforced. decisions at the autonomous system level may be enforced.
2.1. Key Features 2.1. Key Features
The key features of the protocol are the notion of path attributes The key features of the protocol are the notion of path
and aggregation of network layer reachability information (NLRI). attributes and aggregation of Network Layer Reachability
Information (NLRI).
Path attributes provide BGP with flexibility and extensibility. Path Path attributes provide BGP with flexibility and
attributes are partitioned into well-known and optional. The extensibility. Path attributes are partitioned into well-known
provision for optional attributes allows experimentation that may and optional. The provision for optional attributes allows
involve a group of BGP routers without affecting the rest of the experimentation that may involve a group of BGP routers
Internet. New optional attributes can be added to the protocol in without affecting the rest of the Internet. New optional
much the same way that new options are added to, say, the Telnet attributes can be added to the protocol in much the same way
protocol [RFC854]. that new options are added to, say, the Telnet protocol [RFC854].
One of the most important path attributes is the Autonomous System One of the most important path attributes is the Autonomous
Path, or AS_PATH. As the reachability information traverses the System Path, or AS_PATH. As the reachability information
Internet, this (AS_PATH) information is augmented by the list of traverses the Internet, this (AS_PATH) information is
autonomous systems that have been traversed thus far, forming the augmented by the list of autonomous systems that have been
AS_PATH. The AS_PATH allows straightforward suppression of the traversed thus far, forming the AS_PATH. The AS_PATH allows
looping of routing information. In addition, the AS_PATH serves as a straightforward suppression of the looping of routing
powerful and versatile mechanism for policy-based routing. information. In addition, the AS_PATH serves as a powerful and
versatile mechanism for policy-based routing.
BGP enhances the AS_PATH attribute to include sets of autonomous BGP enhances the AS_PATH attribute to include sets of autonomous
systems as well as lists via the AS_SET attribute. This extended systems as well as lists via the AS_SET attribute. This extended
format allows generated aggregate routes to carry path information format allows generated aggregate routes to carry path information
from the more specific routes used to generate the aggregate. It from the more specific routes used to generate the aggregate. It
should be noted however, that as of this writing, AS_SETs are rarely should be noted however, that as of this writing, AS_SETs are
used in the Internet [ROUTEVIEWS]. rarely used in the Internet [ROUTEVIEWS].
2.2. BGP Algorithms 2.2. BGP Algorithms
BGP uses an algorithm that is neither a pure distance vector BGP uses an algorithm that is neither a pure distance vector
algorithm or a pure link state algorithm. It is instead a modified algorithm or a pure link state algorithm. It is instead a
distance vector algorithm referred to as a "Path Vector" algorithm modified distance vector algorithm referred to as a "Path
that uses path information to avoid traditional distance vector Vector" algorithm that uses path information to avoid
problems. Each route within BGP pairs destination with path traditional distance vector problems. Each route within BGP
information to that destination. Path information (also known as pairs destination with path information to that
AS_PATH information) is stored within the AS_PATH attribute in BGP. destination. Path information (also known as AS_PATH
The path information assist BGP in detecting AS loops thereby information) is stored within the AS_PATH attribute in
allowing BGP speakers select loop free routes. BGP. The path information assists BGP in detecting AS loops
thereby allowing BGP speakers select loop free routes.
BGP uses an incremental update strategy in order to conserve BGP uses an incremental update strategy in order to conserve
bandwidth and processing power. That is, after initial exchange of bandwidth and processing power. That is, after initial
complete routing information, a pair of BGP routers exchanges only exchange of complete routing information, a pair of BGP
changes to that information. Such an incremental update design routers exchanges only changes to that information. Such an
requires reliable transport between a pair of BGP routers to function incremental update design requires reliable transport between
correctly. BGP solves this problem by using TCP for reliable a pair of BGP routers to function correctly. BGP solves this
transport. TCP further assist BGP in limiting congestion to the problem by using TCP for reliable transport.
advertised window limits.
In addition to incremental updates, BGP has added the concept of In addition to incremental updates, BGP has added the concept
route aggregation so that information about groups of destinations of route aggregation so that information about groups of
destinations
that use hierarchical address assignment (e.g., CIDR) may be that use hierarchical address assignment (e.g., CIDR) may be
aggregated and sent as a single Network Layer Reachability (NLRI). aggregated and sent as a single Network Layer Reachability
(NLRI).
Finally, note that BGP is a self-contained protocol. That is, BGP Finally, note that BGP is a self-contained protocol. That is,
specifies how routing information is exchanged both between BGP BGP specifies how routing information is exchanged both
speakers in different autonomous systems, and between BGP speakers between BGP speakers in different autonomous systems, and
within a single autonomous system. between BGP speakers within a single autonomous system.
2.3. BGP Finite State Machine (FSM) 2.3. BGP Finite State Machine (FSM)
The BGP FSM is a set of rules that are applied to a BGP speaker's set The BGP FSM is a set of rules that are applied to a BGP
of configured peers for the BGP operation. A BGP implementation speaker's set of configured peers for the BGP operation. A BGP
requires that a BGP speaker must connect to and listen on TCP port implementation requires that a BGP speaker must connect to and
179 for accepting any new BGP connections from its peers. The BGP listen on TCP port 179 for accepting any new BGP connections
Finite State Machine, or FSM, must be initiated and maintained for from its peers. The BGP Finite State Machine, or FSM, must be
each new incoming and outgoing peer connections. However, in steady initiated and maintained for each new incoming and outgoing
state operation, there will be only one BGP FSM per connection per peer connections. However, in steady state operation, there
peer. will be only one BGP FSM per connection per peer.
There may exist a temporary period where in a BGP peer may have There may be a short period during which a BGP peer may have
separate incoming and outgoing connections resulting into two separate incoming and outgoing connections resulting in the
different BGP FSMs for a peer (instead of one). This can be resolved creation of two different BGP FSMs relating to a peer (instead
following BGP connection collision rules defined in the [BGP4]. of one). This can be resolved by following the BGP connection
collision rules defined in the [BGP4] specification.
Following are different states of BGP FSM for its peers: The BGP FSM has the following states associated with each of its
peers:
IDLE: State when BGP peer refuses any incoming IDLE: State when BGP peer refuses any incoming
connections. connections.
CONNECT: State in which BGP peer is waiting for CONNECT: State in which BGP peer is waiting for
its TCP connection to be completed. its TCP connection to be completed.
ACTIVE: State in which BGP peer is trying to acquire a ACTIVE: State in which BGP peer is trying to acquire a
peer by listening and accepting TCP connection. peer by listening and accepting TCP connection.
OPENSENT: BGP peer is waiting for OPEN message from its OPENSENT: BGP peer is waiting for OPEN message from its
peer. peer.
OPENCONFIRM: BGP peer is waiting for KEEPALIVE or NOTIFICATION OPENCONFIRM: BGP peer is waiting for KEEPALIVE or NOTIFICATION
message from its peer. message from its peer.
ESTABLISHED: BGP peer connection is established and exchanges ESTABLISHED: BGP peer connection is established and exchanges
UPDATE, NOTIFICATION, and KEEPALIVE messages with UPDATE, NOTIFICATION, and KEEPALIVE messages with
its peer. its peer.
There are different BGP events that operate on above mentioned states There are an number of BGP events that operate on above
of BGP FSM for BGP peers. These BGP events are either mandatory or mentioned states of the BGP FSM for BGP peers. Support of
optional. They are triggered by the protocol logic as part of the BGP these BGP events are either mandatory or optional. They are
or using an operator intervention via a configuration interface to triggered by the protocol logic as part of the BGP or using an
the BGP protocol. operator intervention via a configuration interface to the BGP
protocol.
These BGP events are of following types: Optional events linked to These BGP events are of following types: Optional events
Optional Session attributes, Administrative Events, Timer Events, linked to Optional Session attributes, Administrative Events,
TCP Connection based Events, and BGP Message-based Events. Both, Timer Events, TCP Connection based Events, and BGP
the FSM and the BGP events are explained in details in [BGP4]. Message-based Events. Both the FSM and the BGP events are
explained in detail in [BGP4].
3. BGP Capabilities 3. BGP Capabilities
The BGP Capability mechanism [RFC2842] provides an easy and flexible The BGP Capability mechanism [RFC2842] provides an easy and flexible
way to introduce new features within the protocol. In particular, the way to introduce new features within the protocol. In particular, the
BGP capability mechanism allows a BGP speaker to advertise to its BGP capability mechanism allows a BGP speaker to advertise to its
peers during startup various optional features supported by the peers during startup various optional features supported by the
speaker (and receive similar information from the peers). This allows speaker (and receive similar information from the peers). This allows
the base BGP protocol to contain only essential functionality, while the base BGP protocol to contain only essential functionality, while
at the same time providing a flexible mechanism for signaling at the same time providing a flexible mechanism for signaling
protocol extensions. protocol extensions.
4. BGP Persistent Peer Oscillations 4. BGP Persistent Peer Oscillations
Ideally, whenever a BGP speaker detects an error in any peer Whenever a BGP speaker detects an error in any peer connection, it
connection, it shuts down the peer and changes its FSM state to IDLE. shuts down the peer and changes its FSM state to IDLE. BGP speaker
BGP speaker requires a Start event to re-initiate its idle peer requires a Start event to re-initiate its idle peer connection. If
connection. If the error remains persistent and BGP speaker generates the error remains persistent and BGP speaker generates Start event
Start event automatically then it may result in persistent peer automatically then it may result in persistent peer flapping.
flapping. However, although peer oscillation is found to be wide- However, although peer oscillation is found to be wide-spread in BGP
spread in BGP implementations, methods for preventing persistent peer implementations, methods for preventing persistent peer oscillations
oscillations are outside the scope of base BGP protocol are outside the scope of base BGP protocol specification.
specification.
5. Implementation Guidelines 5. Implementation Guidelines
A robust BGP implementation is work conserving. This means that if A robust BGP implementation is work conserving. This means that if
the number of prefixes is bound, arbitrarily high levels of route the number of prefixes is bounded, arbitrarily high levels of route
change can be tolerated with bounded impact on route convergence for change can be tolerated with bounded impact on route convergence for
occasional changes in generally stable routes. occasional changes in generally stable routes.
A robust implementation of BGP should have the following A robust implementation of BGP should have the following
characteristics: characteristics:
1. It is able to operate in almost arbitrarily high levels 1. It is able to operate in almost arbitrarily high levels
of route flap without loosing peerings (failing to send of route flap without losing peerings (failing to send
keepalives) or loosing other protocol adjacencies as a keepalives) or loosing other protocol adjacencies as a
result of BGP load. result of BGP load.
2. Instability of a subset of routes should not affect the 2. Instability of a subset of routes should not affect the
route advertisements or forwarding associated with the set route advertisements or forwarding associated with the set
of stable routes. of stable routes.
3. High levels of instability and peers of different CPU speed 3. High levels of instability and peers of different CPU speed
or load resulting in faster or slower processing of routes or load resulting in faster or slower processing of routes
should not cause instability and should have a bounded should not cause instability and should have a bounded
skipping to change at page 8, line 42 skipping to change at page 9, line 4
6.1. Link bandwidth and CPU utilization 6.1. Link bandwidth and CPU utilization
Immediately after the initial BGP connection setup, BGP peers Immediately after the initial BGP connection setup, BGP peers
exchange complete set of routing information. If we denote the total exchange complete set of routing information. If we denote the total
number of routes in the Internet by N, the total path attributes (for number of routes in the Internet by N, the total path attributes (for
all N routes) received from a peer as A, and assume that the networks all N routes) received from a peer as A, and assume that the networks
are uniformly distributed among the autonomous systems, then the are uniformly distributed among the autonomous systems, then the
worst case amount of bandwidth consumed during the initial exchange worst case amount of bandwidth consumed during the initial exchange
between a pair of BGP speakers (P) is between a pair of BGP speakers (P) is
BW = O((N + A) * P) BW = O((N + A) * P)
BGP-4 was created specifically to reduce the size of the set of NLRI
entries which have to be carried and exchanged by border routers. BGP-4 was created specifically to reduce the size of the set
The aggregation scheme, defined in [CIDR],describes the provider- of NLRI entries which have to be carried and exchanged by
based aggregation scheme in use in today's Internet. border routers. The aggregation scheme, defined in [RFC1519],
describes the provider-based aggregation scheme in use in
today's Internet.
Due to the advantages of advertising a few large aggregate blocks Due to the advantages of advertising a few large aggregate blocks
instead of many smaller class-based individual networks, it is instead of many smaller class-based individual networks, it is
difficult to estimate the actual reduction in bandwidth and difficult to estimate the actual reduction in bandwidth and
processing that BGP-4 has provided over BGP-3. If we simply processing that BGP-4 has provided over BGP-3. If we simply
enumerate all aggregate blocks into their individual class-based enumerate all aggregate blocks into their individual class-based
networks, we would not take into account "dead" space that has been networks, we would not take into account "dead" space that has been
reserved for future expansion. The best metric for determining the reserved for future expansion. The best metric for determining the
success of BGP's aggregation is to sample the number NLRI entries in success of BGP's aggregation is to sample the number NLRI entries in
the globally connected Internet today and compare it to projected the globally connected Internet today and compare it to projected
growth rates before BGP was deployed. growth rates before BGP was deployed.
At the time of this writing, the full set of exterior routes carried At the time of this writing, the full set of exterior routes carried
by BGP is approximately 134,000 network entries [ROUTEVIEWS]. by BGP is approximately 134,000 network entries [ROUTEVIEWS].
6.1.1. CPU utilization 6.1.1. CPU utilization
An important and fundamental feature of BGP is that BGP's CPU An important and fundamental feature of BGP is that BGP's CPU
utilization depends only on the stability of its network which utilization depends only on the stability of its network which
relates to BGP in terms of BGP UPDATE message announcments. If the relates to BGP in terms of BGP UPDATE message announcements. If the
BGP network is stable: all the BGP routers within its network are in BGP network is stable: all the BGP routers within its network are in
the steady state; then the only link bandwidth and router CPU cycles the steady state; then the only link bandwidth and router CPU cycles
consumed by BGP are due to the exchange of the BGP KEEPALIVE consumed by BGP are due to the exchange of the BGP KEEPALIVE
messages. The KEEPALIVE messages are exchanged only between peers. messages. The KEEPALIVE messages are exchanged only between peers.
The suggested frequency of the exchange is 30 seconds. The KEEPALIVE The suggested frequency of the exchange is 30 seconds. The KEEPALIVE
messages are quite short (19 octets), and require virtually no messages are quite short (19 octets), and require virtually no
processing. As a result, the bandwidth consumed by the KEEPALIVE processing. As a result, the bandwidth consumed by the KEEPALIVE
messages is about 5 bits/sec. Operational experience confirms that messages is about 5 bits/sec. Operational experience confirms that
the overhead (in terms of bandwidth and CPU) associated with the the overhead (in terms of bandwidth and CPU) associated with the
KEEPALIVE messages should be viewed as negligible. KEEPALIVE messages should be viewed as negligible.
During the periods of network instability, BGP routers within the During periods of network instability, BGP routers within the network
network are generating routing updates that are exchanged using the are generating routing updates that are exchanged using the BGP
BGP UPDATE messages. The greatest overhead per UPDATE message occurs UPDATE messages. The greatest overhead per UPDATE message occurs
when each UPDATE message contains only a single network. It should be when each UPDATE message contains only a single network. It should be
pointed out that in practice routing changes exhibit strong locality pointed out that in practice routing changes exhibit strong locality
with respect to the route attributes. That is, routes that change with respect to the route attributes. That is, routes that change
are likely to have common route attributes. In this case, multiple are likely to have common route attributes. In this case, multiple
networks can be grouped into a single UPDATE message, thus networks can be grouped into a single UPDATE message, thus
significantly reducing the amount of bandwidth required (see also significantly reducing the amount of bandwidth required (see also
Appendix F.1 of [BGP4]). Appendix F.1 of [BGP4]).
6.1.2. Memory requirements 6.1.2. Memory requirements
skipping to change at page 10, line 31 skipping to change at page 10, line 32
number of networks in the Internet will grow much faster than the number of networks in the Internet will grow much faster than the
average number of peers per router. As a result, BGP's memory average number of peers per router. As a result, BGP's memory
scaling properties are linearly related to the total number of scaling properties are linearly related to the total number of
networks in the Internet. networks in the Internet.
The following table illustrates typical memory requirements of a The following table illustrates typical memory requirements of a
router running BGP. We denote average number of routes advertised by router running BGP. We denote average number of routes advertised by
each peer as N, the total number of unique AS paths as A, the mean AS each peer as N, the total number of unique AS paths as A, the mean AS
distance of the Internet as M (distance at the level of an autonomous distance of the Internet as M (distance at the level of an autonomous
system, expressed in terms of the number of autonomous systems), system, expressed in terms of the number of autonomous systems),
number of bytes required to store a network as R, and number of bytes number of octets required to store a network as R, and number of
required to store one AS in an AS path as P. It is assumed that each bytes required to store one AS in an AS path as P. It is assumed
network is encoded as four bytes, each AS is encoded as two bytes, that each network is encoded as four bytes, each AS is encoded as two
and each networks is reachable via some fraction of all of the peers bytes, and each networks is reachable via some fraction of all of the
(# BGP peers/per net). For purposes of the estimates here, we will peers (# BGP peers/per net). For purposes of the estimates here, we
calculate MR = (((N * R) + (M * A) * P) * S). will calculate MR = (((N * R) + (M * A) * P) * S).
# Networks Mean AS Distance # AS's # BGP peers/per net Memory Req # Networks Mean AS Distance # AS's # BGP peers/per net Memory Req
(N) (M) (A) (P) (MR) (N) (M) (A) (P) (MR)
---------- ---------------- ------ ------------------- -------------- ---------- ---------------- ------ ------------------- --------------
100,000 20 3,000 20 10,400,000 100,000 20 3,000 20 10,400,000
100,000 20 15,000 20 20,000,000 100,000 20 15,000 20 20,000,000
120,000 10 15,000 100 78,000,000 120,000 10 15,000 100 78,000,000
140,000 15 20,000 100 116,000,000 140,000 15 20,000 100 116,000,000
In analyzing BGP's memory requirements, we focus on the size of the In analyzing BGP's memory requirements, we focus on the size of the
BGP RIB table (and ignoring implementation details). In particular, BGP RIB table (ignoring implementation details). In particular, we
we derive upper bounds for the size of the BGP RIB table. For derive upper bounds for the size of the BGP RIB table. For example,
example, at the time of this writing, the BGP RIB tables of a typical at the time of this writing, the BGP RIB tables of a typical backbone
backbone router carry on the order of 120,000 entries. Given this router carry on the order of 120,000 entries. Given this number, one
number, one might ask whether it would be possible to have a might ask whether it would be possible to have a functional router
functional router with a table that will have 1,000,000 entries. with a table that will have 1,000,000 entries. Clearly the answer to
Clearly the answer to this question is more related to how BGP is this question is more related to how BGP is implemented. A robust BGP
implemented. A robust BGP implementation with a reasonable CPU and implementation with a reasonable CPU and memory should not have
memory should not have issues scaling to such limits. issues scaling to such limits.
7. BGP Policy Expressiveness and its Implications 7. BGP Policy Expressiveness and its Implications
BGP is unique among deployed IP routing protocols in that routing is BGP is unique among deployed IP routing protocols in that routing is
determined using semantically rich routing policies. Although determined using semantically rich routing policies. Although
routing policies are usually the first thing that comes to a network routing policies are usually the first thing that comes to a network
operator's mind concerning BGP, it is important to note that the operator's mind concerning BGP, it is important to note that the
languages and techniques for specifying BGP routing policies are not languages and techniques for specifying BGP routing policies are not
actually a part of the protocol specification ([RFC2622] for an actually a part of the protocol specification ([RFC2622] for an
example of such a policy language). In addition, the BGP example of such a policy language). In addition, the BGP
specification contains few restrictions, either explicitly or specification contains few restrictions, either explicitly or
implicitly, on routing policy languages. These languages have implicitly, on routing policy languages. These languages have
typically been developed by vendors and have evolved through typically been developed by vendors and have evolved through
interactions with network engineers in an environment lacking vendor- interactions with network engineers in an environment lacking
independent standards. vendor-independent standards.
The complexity of typical BGP configurations, at least in provider The complexity of typical BGP configurations, at least in provider
networks, has been steadily increasing. Router vendors typically networks, has been steadily increasing. Router vendors typically
provided hundreds of special commands for use in the configuration of provide hundreds of special commands for use in the configuration of
BGP, and this command set is continually expanding. For example, BGP BGP, and this command set is continually expanding. For example, BGP
communities [RFC1997] allow policy writers to selectively attach tags communities [RFC1997] allow policy writers to selectively attach tags
to routes and use these to signal policy information to other BGP- to routes and use these to signal policy information to other
speaking routers. Many providers allow customers, and sometimes BGP-speaking routers. Many providers allow customers, and
peers, to send communities that determine the scope and preference of sometimes peers, to send communities that determine the scope
their routes. These developments have more and more given the task and preference of their routes. These developments have
of writing BGP configurations aspects associated with open-ended increasingly given the task of writing BGP configurations
programming. This has allowed network operators to encode complex aspects associated with open-ended programming. This has
policies in order to address many unforeseen situations, and has allowed network operators to encode complex policies in order
opened the door for a great deal of creativity and experimentation in to address many unforeseen situations, and has opened the door
routing policies. This policy flexibility is one of the main reasons for a great deal of creativity and experimentation in routing
policies. This policy flexibility is one of the main reasons
why BGP is so well suited to the commercial environment of the why BGP is so well suited to the commercial environment of the
current Internet. current Internet.
However, this rich policy expressiveness has come with a cost that is However, this rich policy expressiveness has come with a cost
often not recognized. In particular, it is possible to construct that is often not recognized. In particular, it is possible
locally defined routing policies that can lead to unexpected global to construct locally defined routing policies that can lead to
routing anomalies such as (unintended) nondeterminism and to protocol unexpected global routing anomalies such as (unintended)
divergence. If the interacting policies causing such anomalies are non-determinism and to protocol divergence. If the
defined in different autonomous systems, then these problems can be interacting policies causing such anomalies are defined in
very difficult to debug and correct. In the following sections, we different autonomous systems, then these problems can be very
describe two such cases relating to the existence (or lack thereof) difficult to debug and correct. In the following sections, we
of stable routings. describe two such cases relating to the existence (or lack
thereof) of stable routings.
7.1. Existence of Unique Stable Routings 7.1. Existence of Unique Stable Routings
One can easily construct sets of policies for which BGP can not One can easily construct sets of policies for which BGP can not
guarantee that stable routings are unique. This can be illustrated guarantee that stable routings are unique. This can be illustrated
by the following simple example. Consider the example of four by the following simple example. Consider the example of four
Autonomous Systems, AS1, AS2, AS3, and AS4. AS1 and AS2 are peers, Autonomous Systems, AS1, AS2, AS3, and AS4. AS1 and AS2 are peers,
and they provide transit for AS3 and AS4 respectively, Suppose and they provide transit for AS3 and AS4 respectively, Suppose
further that AS3 provides transit for AS4 (in this case AS3 is a further that AS3 provides transit for AS4 (in this case AS3 is a
customer of AS1, and AS4 is a multihomed customer of both AS3 and customer of AS1, and AS4 is a multihomed customer of both AS3 and
skipping to change at page 13, line 45 skipping to change at page 13, line 45
of signaling information within and between autonomous systems than of signaling information within and between autonomous systems than
is possible with [RFC1997] communities. At the same time, is possible with [RFC1997] communities. At the same time,
applications of communities by network operators are evolving to applications of communities by network operators are evolving to
address complex issues of inter-domain traffic engineering. address complex issues of inter-domain traffic engineering.
7.2. Existence of Stable Routings 7.2. Existence of Stable Routings
One can also construct a set of policies for which BGP can not One can also construct a set of policies for which BGP can not
guarantee that a stable routing exists (or worse, that a stable guarantee that a stable routing exists (or worse, that a stable
routing will ever be found). For example, [RFC3345] documents routing will ever be found). For example, [RFC3345] documents
several scenarios that lead to route oscillations associated with the several scenarios that lead to route oscillations associated
use of the Multi-Exit Discriminator or MED, attribute. Route with the use of the Multi-Exit Discriminator or MED,
attribute. Route
oscillation will happen in BGP when a set of policies has no oscillation will happen in BGP when a set of policies has no
solution. That is, when there is no stable routing that satisfies solution. That is, when there is no stable routing that satisfies
the constraints imposed by policy, then BGP has no choice by to keep the constraints imposed by policy, then BGP has no choice by to keep
trying. In addition, BGP configurations can have a stable routing, trying. In addition, BGP configurations can have a stable routing,
yet the protocol may not be able to find it; BGP can "get trapped" yet the protocol may not be able to find it; BGP can "get trapped"
down a blind alley that has no solution. down a blind alley that has no solution.
Protocol divergence is not, however, a problem associated solely with Protocol divergence is not, however, a problem associated solely with
use of the MED attribute. This potential exists in BGP even without use of the MED attribute. This potential exists in BGP even without
the use of the MED attribute. Hence, like the unintended the use of the MED attribute. Hence, like the unintended
nondeterminism described in the previous section, this type of nondeterminism described in the previous section, this type of
protocol divergence is an unintended consequence of the unconstrained protocol divergence is an unintended consequence of the unconstrained
nature of BGP policy languages. nature of BGP policy languages.
8. Applicability 8. Applicability
In this section we answer the question of which environments is BGP In this section we identify the environments for which BGP well
well suited, and for which environments it is not suitable. This suited, and for which environments it is not suitable. This question
question is partially answered in Section 2 of BGP [BGP4], which is partially answered in Section 2 of BGP [BGP4], which states:
states:
"To characterize the set of policy decisions that can be enforced "To characterize the set of policy decisions that can be
using BGP, one must focus on the rule that an AS advertises to its enforced using BGP, one must focus on the rule that an AS
neighbor ASs only those routes that it itself uses. This rule advertises to its neighbor ASs only those routes that it
reflects the "hop-by-hop" routing paradigm generally used itself uses. This rule reflects the "hop-by-hop" routing
throughout the current Internet. Note that some policies cannot paradigm generally used throughout the current Internet.
be supported by the "hop-by-hop" routing paradigm and thus require Note that some policies cannot be supported by the
techniques such as source routing to enforce. For example, BGP "hop-by-hop" routing paradigm and thus require techniques
does not enable one AS to send traffic to a neighbor AS intending such as source routing to enforce. For example, BGP does
that the traffic take a different route from that taken by traffic not enable one AS to send traffic to a neighbor AS
originating in the neighbor AS. On the other hand, BGP can intending that the traffic take a different route from
support any policy conforming to the "hop-by-hop" routing that taken by traffic originating in the neighbor AS. On
paradigm. Since the current Internet uses only the "hop-by-hop" the other hand, BGP can support any policy conforming to
routing paradigm and since BGP can support any policy that the "hop-by-hop" routing paradigm. Since the current
conforms to that paradigm, BGP is highly applicable as an inter-AS Internet uses only the "hop-by-hop" routing paradigm and
routing protocol for the current Internet." since BGP can support any policy that conforms to that
paradigm, BGP is highly applicable as an inter-AS routing
protocol for the current Internet."
One of the important points here is that the BGP protocol contains One of the important points here is that the BGP protocol contains
only the functionality that is essential, while at the same time only the functionality that is essential, while at the same time
providing a flexible mechanism within the protocol that allow us to providing a flexible mechanism within the protocol that allows us to
extend its functionality. For example, BGP capabilities provide an extend its functionality. For example, BGP capabilities provide an
easy and flexible way to introduce new features within the protocol. easy and flexible way to introduce new features within the protocol.
Finally, since BGP was designed with flexibility and extensibility in Finally, since BGP was designed with flexibility and
mind, new and/or evolving requirements can be addressed via existing extensibility in mind, new and/or evolving requirements can be
mechanisms. addressed via existing mechanisms.
To summarize, BGP is well suitable as an inter-autonomous system To summarize, BGP is well suited as an inter-autonomous system
routing protocol for any internet that is based on IP [RFC791] as the routing protocol for any internet that is based on IP [RFC791]
internet protocol and "hop-by-hop" routing paradigm. as the internet protocol and "hop-by-hop" routing paradigm.
9. Acknowledgments 9. Acknowledgments
We would like to thank Paul Traina for authoring previous versions of We would like to thank Paul Traina for authoring previous
this document. Tim Griffin, Randy Presuhn, Curtis Villamizar and versions of this document. Elwyn Davies, Tim Griffin, Randy
Atanu Ghosh also provided many insightful comments on earlier Presuhn, Curtis Villamizar and Atanu Ghosh also provided many
versions of this document. insightful comments on earlier versions of this document.
10. Security Considerations 10. Security Considerations
BGP provides flexible mechanisms with varying levels of complexity BGP provides flexible mechanisms with varying levels of complexity
for security purposes. BGP sessions are authenticated using BGP for security purposes. BGP sessions are authenticated using BGP
session addresses and the assigned AS number. Since BGP sessions use session addresses and the assigned AS number. Since BGP
TCP (and IP) for reliable transport, BGP sessions are further sessions use TCP (and IP) for reliable transport, BGP sessions
authenticated and secured by any authentication and security are further authenticated and secured by any authentication
mechanisms used by TCP and IP. and security mechanisms used by TCP and IP.
BGP uses TCP MD5 option for validating data and protecting against BGP uses TCP MD5 option for validating data and protecting against
spoofing of TCP segments exhanged between its sessions. The usage of spoofing of TCP segments exchanged between its sessions. The usage
TCP MD5 option for BGP is described at length in [RFC 2385]. The TCP of TCP MD5 option for BGP is described at length in [RFC 2385]. The
MD5 Key management is discussed in [RFC 3562]. BGP data encryption is TCP MD5 Key management is discussed in [RFC 3562]. BGP data
provided using IPsec mechanism which encrypts the IP payload data encryption is provided using IPsec mechanism which encrypts the IP
(including TCP and BGP data). The IPsec mechanism can be used in payload data (including TCP and BGP data). The IPsec mechanism can
both, the transport mode as well as the tunnel mode. The IPsec be used in both, the transport mode as well as the tunnel mode. The
mechanism is described in [RFC 2406]. Both, the TCP MD5 option and IPsec mechanism is described in [RFC 2406]. Both, the TCP MD5 option
the IPsec mechanism are not widely deployed security mechanisms for and the IPsec mechanism are not widely deployed security mechanisms
BGP in today's Internet and hence it is difficult to guage their real for BGP in today's Internet and hence it is difficult to gauge their
performance impact when using with BGP. However, since both the real performance impact when using with BGP. However, since both the
mechanisms are TCP and IP based security mechanisms, the Link mechanisms are TCP and IP based security mechanisms, the Link
Bandwidth, CPU utilization and router memory consumed by BGP protocol Bandwidth, CPU utilization and router memory consumed by BGP protocol
using it would be same as any other TCP and IP based protocols. using it would be same as any other TCP and IP based protocols.
BGP uses IP TTL value to protect its EBGP sessions from any TCP (or BGP uses IP TTL value to protect its External BGP (EBGP) sessions
IP) based CPU intensive attacks. It is a simple mechanism which from any TCP (or IP) based CPU intensive attacks. It is a simple
suggests the use of filtering BGP (TCP) segments using the IP TTL mechanism which suggests the use of filtering BGP (TCP) segments
value carried within the IP header of BGP (TCP) segments exchanged using the IP TTL value carried within the IP header of BGP (TCP)
between the EBGP sessions. The BGP TTL mechanism is described in segments exchanged between the EBGP sessions. The BGP TTL mechanism
[BTSH]. Usage of [BTSH] impacts performance in a similar way as using is described in [RFC3682]. Usage of [RFC3682] impacts performance in
any ACL policies for BGP. a similar way as using any ACL policies for BGP.
Such flexible TCP and IP based security mechanisms, allow BGP to Such flexible TCP and IP based security mechanisms, allow BGP to
prevent insertion/deletion/modification of BGP data, any snooping of prevent insertion/deletion/modification of BGP data, any snooping of
the data, session stealing, etc. However, BGP is vulnerable to the the data, session stealing, etc. However, BGP is vulnerable to the
same security attacks that are present in TCP. The [BGP-VUL] same security attacks that are present in TCP. The [BGP-VUL]
explains in depth about the BGP security vulneribility. At the time explains in depth about the BGP security vulnerability. At the time
of this writing, several efforts are underway for creating and of this writing, several efforts are underway for creating and
defining an appropriate security infrastructure within the BGP defining an appropriate security infrastructure within the BGP
protocol to provide authentication and security for its routing protocol to provide authentication and security for its routing
information; some of which include [SBGP] and [SOBGP]. information; some of which include [SBGP] and [SOBGP].
11. IANA Considerations 11. IANA Considerations
This document presents an analysis of the BGP protocol and hence This document presents an analysis of the BGP protocol and hence
presents no new IANA considerations. presents no new IANA considerations.
12. References 12. References
12.1. Normative References 12.1. Normative References
[BGP4] Rekhter, Y., T. Li., and S. Hares, Editors, "A [BGP4] Rekhter, Y., T. Li., and S. Hares, Editors, "A
Border Gateway Protocol 4 (BGP-4)", Border Gateway Protocol 4 (BGP-4)",
draft-ietf-idr-bgp4-20.txt. Work in progress. draft-ietf-idr-bgp4-2.txt. Work in progress.
[CIDR] Fuller, V., Li, T., Yu, J., and K. Varadhan, [RFC1519] Fuller, V., Li, T., Yu, J., and K. Varadhan,
"Classless Inter-Domain Routing (CIDR): an Address "Classless Inter-Domain Routing (CIDR): an Address
Assignment and Aggregation Strategy", RFC 1519, Assignment and Aggregation Strategy", RFC 1519,
September, 1993. September, 1993.
[RFC791] "INTERNET PROTOCOL", DARPA INTERNET PROGRAM [RFC791] "INTERNET PROTOCOL", DARPA INTERNET PROGRAM
PROTOCOL SPECIFICATION, RFC 791, September, PROTOCOL SPECIFICATION, RFC 791, September,
1981. 1981.
[RFC1997] Chandra. R, and T. Li, "BGP Communities [RFC1997] Chandra. R, and T. Li, "BGP Communities
Attribute", RFC 1997, August, 1996. Attribute", RFC 1997, August, 1996.
[RFC2385] Heffernan, A., "Protection of BGP Sessions via
the TCP MD5 Signature Option", RFC 2385,
August, 1998.
[RFC2842] Chandra, R. and J. Scudder, "Capabilities [RFC2842] Chandra, R. and J. Scudder, "Capabilities
Advertisement with BGP-4", RFC 2842, May 2000. Advertisement with BGP-4", RFC 2842, May 2000.
[RFC3345] McPherson, D., Gill, V., Walton, D., and [RFC3345] McPherson, D., Gill, V., Walton, D., and
A. Retana, "Border Gateway Protocol (BGP) Persistent A. Retana, "Border Gateway Protocol (BGP) Persistent
Route Oscillation Condition", RFC 3345, Route Oscillation Condition", RFC 3345,
August, 2002. August, 2002.
[BTSH] Gill, V., Heasley, J., and D. Meyer, "The BGP TTL
Security Hack (BTSH)", draft-gill-btsh-02.txt.
Work in progress.
[RFC2385] Heffernan, A., "Protection of BGP Sessions via
the TCP MD5 Signature Option", RFC 2385,
August, 1998.
[RFC3562] Leech, M., "Key Management Considerations for [RFC3562] Leech, M., "Key Management Considerations for
the TCP MD5 Signature Option", RFC 3562, the TCP MD5 Signature Option", RFC 3562,
July, 2003. July, 2003.
[soBGP] White, R., "Architecture and Deployment Considerations for [RFC3682] Gill, V., Heasley, J., and D. Meyer, "The
Secure Origin BGP (soBGP)", Internet-Draft, Work in Progress. Generalized TTL Security Mechanism (GTSM)", RFC
3682, February, 2004.
[SOBGP] White, R., "Architecture and Deployment
Considerations for Secure Origin BGP (soBGP)",
draft-white-sobgp-architecture-00.txt. Work in
Progress.
[BGP_VULN] Murphy, S., "BGP Security Vulnerabilities Analysis", [BGP_VULN] Murphy, S., "BGP Security Vulnerabilities Analysis",
draft-ietf-idr-bgp-vuln-00.txt. work in progress draft-ietf-idr-bgp-vuln-01.txt. Work in progress
[SBGP] Lynn, C., Mikkelson, J., and K. Seo, "Secure BGP S-BGP", [SBGP] Lynn, C., Mikkelson, J., and K. Seo, "Secure BGP S-BGP",
Internet-Draft, Work in Progress. Internet-Draft, Work in Progress.
12.2. Informative References 12.2. Informative References
[RFC854] Postel, J. and J. Reynolds, "TELNET PROTOCOL [RFC854] Postel, J. and J. Reynolds, "TELNET PROTOCOL
SPECIFICATION", RFC 854, May, 1983. SPECIFICATION", RFC 854, May, 1983.
[RFC1105] Lougheed, K., and Y. Rekhter, "Border Gateway [RFC1105] Lougheed, K., and Y. Rekhter, "Border Gateway
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/