draft-ietf-idr-bgp-analysis-04.txt   draft-ietf-idr-bgp-analysis-05.txt 
INTERNET-DRAFT D. Meyer INTERNET-DRAFT D. Meyer
draft-ietf-idr-bgp-analysis-04.txt K. Patel draft-ietf-idr-bgp-analysis-05.txt K. Patel
Category Informational Category Informational
Expires: March 2004 September 2003 Expires: December 2004 June 2004
BGP-4 Protocol Analysis BGP-4 Protocol Analysis
<draft-ietf-idr-bgp-analysis-04.txt> <draft-ietf-idr-bgp-analysis-05.txt>
Status of this Document Status of this Document
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is subject to all provisions
all provisions of Section 10 of RFC2026. of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other 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.html
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html
This document is a product of the IDR Working Group. Comments should This document is a product of the IDR Working Group WG. Comments
be addressed to the authors, or the mailing list at idr@ietf.org. should be addressed to the authors, or the mailing list at
idr@ietf.org.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2003). 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 RFC 1264 [RFC1264]. In order to fulfill described in Section 6.0 of [RFC1264]. In order to fulfill the
the requirement, this report augments RFC 1774 [RFC1774] and requirement, this report augments [RFC1774] and summarizes the key
summarizes the key features of BGP protocol, and analyzes the features of BGP-4 protocol, and analyzes the protocol with respect to
protocol with respect to scaling and performance. 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 . . . . . . . . . . . . . . . . . . . . . . . 8 3. BGP Capabilities . . . . . . . . . . . . . . . . . . . . . . . 7
4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 8 4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 7
5. Implementation Guidelines. . . . . . . . . . . . . . . . . . . 8 5. Implementation Guidelines. . . . . . . . . . . . . . . . . . . 7
6. BGP Performance characteristics and Scalability. . . . . . . . 9 6. BGP Performance characteristics and Scalability. . . . . . . . 8
6.1. Link bandwidth and CPU utilization. . . . . . . . . . . . . 9 6.1. Link bandwidth and CPU utilization. . . . . . . . . . . . . 8
6.1.1. CPU utilization. . . . . . . . . . . . . . . . . . . . . 10 6.1.1. CPU utilization. . . . . . . . . . . . . . . . . . . . . 9
6.1.2. Memory requirements. . . . . . . . . . . . . . . . . . . 11 6.1.2. Memory requirements. . . . . . . . . . . . . . . . . . . 10
7. BGP Policy Expressiveness and its Implications . . . . . . . . 12 7. BGP Policy Expressiveness and its Implications . . . . . . . . 11
7.1. Existence of Unique Stable Routings . . . . . . . . . . . . 13 7.1. Existence of Unique Stable Routings . . . . . . . . . . . . 12
7.2. Existence of Stable Routings. . . . . . . . . . . . . . . . 15 7.2. Existence of Stable Routings. . . . . . . . . . . . . . . . 13
8. Applicability. . . . . . . . . . . . . . . . . . . . . . . . . 16 8. Applicability. . . . . . . . . . . . . . . . . . . . . . . . . 14
9. Intellectual Property. . . . . . . . . . . . . . . . . . . . . 17 9. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 15
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 10. Security Considerations . . . . . . . . . . . . . . . . . . . 16
11. Security Considerations . . . . . . . . . . . . . . . . . . . 18 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 12. References. . . . . . . . . . . . . . . . . . . . . . . . . . 17
13. References. . . . . . . . . . . . . . . . . . . . . . . . . . 18 12.1. Informative References . . . . . . . . . . . . . . . . . . 17
13.1. Informative References . . . . . . . . . . . . . . . . . . 18 13. Author's Addresses. . . . . . . . . . . . . . . . . . . . . . 19
14. Author's Addresses. . . . . . . . . . . . . . . . . . . . . . 19 14. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 19
15. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 19 15. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20
16. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 20
1. Introduction 1. Introduction
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 protocol was published in RFC TCP/IP internets. Version 1 of the BGP-4 protocol was published in
1105 [RFC1105]. Since then BGP versions 2, 3, and 4 have been [RFC1105]. Since then BGP versions 2, 3, and 4 have been developed.
developed. Version 2 was documented in RFC 1163 [RFC1163]. Version Version 2 was documented in [RFC1163]. Version 3 is documented in
3 is documented in RFC 1267 [RFC1267]. Version 4 is documented in [RFC1267]. Version 4 is documented in the [BGP4] (version 4 of BGP
the [BGP4] (version 4 of BGP will hereafter be referred to as BGP). will hereafter be referred to as BGP). The changes between versions
The changes between versions are explained in Appendix A of [BGP4]. are explained in Appendix A of [BGP4]. Possible applications of BGP
Possible applications of BGP in the Internet are documented in RFC in the Internet are documented in [RFC1772].
1772 [RFC1772].
BGP introduced support for Classless InterDomain Routing [CIDR]. BGP introduced support for Classless InterDomain Routing [CIDR].
Since earlier versions of BGP lacked the support for CIDR, they are Since earlier versions of BGP lacked the support for CIDR, they are
considered obsolete and unusable in today's Internet. 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 BGP
protocol. BGP is an inter-autonomous system routing protocol; it is protocol. BGP is an inter-autonomous system routing protocol; it is
designed to be used between multiple autonomous systems. BGP assumes designed to be used between multiple autonomous systems. BGP assumes
that routing within an autonomous system is done by an intra- that routing within an autonomous system is done by an intra-
autonomous system routing protocol. BGP also assumes that data autonomous system routing protocol. BGP also assumes that data
packets are routed from source towards destination independent of the packets are routed from source towards destination independent of the
source. BGP does not make any assumptions about intra-autonomous source. BGP does not make any assumptions about intra-autonomous
system routing protocols deployed within the various autonomous system routing protocols deployed within the various autonomous
systems. Specifically, BGP does not require all autonomous systems systems. Specifically, BGP does not require all autonomous systems to
to run the same intra-autonomous system routing protocol (i.e., run the same intra-autonomous system routing protocol (i.e., interior
interior gateway protocol or IGP). 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 routing
protocol, and as such it imposes no constraints on the underlying protocol, and as such it imposes no constraints on the underlying
Internet topology. The information exchanged via BGP is sufficient interconnect topology of the autonomous systems. The information
to construct a graph of autonomous systems connectivity from which exchanged via BGP is sufficient to construct a graph of autonomous
routing loops may be pruned and many routing policy decisions at the systems connectivity from which routing loops may be pruned and many
autonomous system level may be enforced. routing policy 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 attributes
and aggregation of network layer reachability information (NLRI). and aggregation of network layer reachability information (NLRI).
Path attributes provide BGP with flexibility and extensibility. Path Path attributes provide BGP with flexibility and extensibility. Path
attributes are partitioned into well-known and optional. The attributes are partitioned into well-known and optional. The
provision for optional attributes allows experimentation that may provision for optional attributes allows experimentation that may
involve a group of BGP routers without affecting the rest of the involve a group of BGP routers without affecting the rest of the
Internet. New optional attributes can be added to the protocol in Internet. New optional attributes can be added to the protocol in
much the same way that new options are added to, say, the Telnet much the same way that new options are added to, say, the Telnet
protocol [RFC854]. protocol [RFC854].
One of the most important path attributes is the Autonomous System One of the most important path attributes is the Autonomous System
Path, or AS_PATH. AS reachability information traverses the Path, or AS_PATH. Autonomous System's (AS) reachability information
Internet, this information is augmented by the list of autonomous traverses the Internet, this information is augmented by the list of
systems that have been traversed thus far, forming the AS_PATH. The autonomous systems that have been traversed thus far, forming the
AS_PATH allows straightforward suppression of the looping of routing AS_PATH. The AS_PATH allows straightforward suppression of the
information. In addition, the AS_PATH serves as a powerful and looping of routing information. In addition, the AS_PATH serves as a
versatile mechanism for policy-based routing. 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 rarely
used in the Internet [ROUTEVIEWS]. 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 modified
distance vector algorithm referred to as a "Path Vector" algorithm distance vector algorithm referred to as a "Path Vector" algorithm
that uses path information to avoid traditional distance vector that uses path information to avoid traditional distance vector
problems. Each route within BGP pairs destination with path problems. Each route within BGP pairs destination with path
information to that destination. Path information (also known as information to that destination. Path information (also known as
AS_PATH information) is stored within the AS_PATH attribute in BGP. AS_PATH information) is stored within the AS_PATH attribute in BGP.
This allows BGP to reconstruct large portions of overall topology The path information assist BGP in detecting AS loops thereby
whenever required. 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 exchange of
complete routing information, a pair of BGP routers exchanges only complete routing information, a pair of BGP routers exchanges only
changes to that information. Such an incremental update design changes to that information. Such an incremental update design
requires reliable transport between a pair of BGP routers to function requires reliable transport between a pair of BGP routers to function
correctly. BGP solves this problem by using TCP for reliable correctly. BGP solves this problem by using TCP for reliable
transport. transport. TCP further assist BGP in limiting congestion to the
advertised window limits.
In addition to incremental updates, BGP has added the concept of In addition to incremental updates, BGP has added the concept of
route aggregation so that information about groups of networks may be route aggregation so that information about groups of destinations
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, BGP
specifies how routing information is exchanged both between BGP specifies how routing information is exchanged both between BGP
speakers in different autonomous systems, and between BGP speakers speakers in different autonomous systems, and between BGP speakers
within a single autonomous system. 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 speaker's set
skipping to change at page 7, line 4 skipping to change at page 2, line 179
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 different BGP events that operate on above mentioned states
of BGP FSM for its peers. These BGP events are used for initiating and of BGP FSM for BGP peers. These BGP events are either mandatory or
terminating peer connections. They also assist BGP in identifying any optional. They are triggered by the protocol logic as part of the BGP
persistent peer connection oscillations and provide a mechanism or using an operator intervention via a configuration interface to
for controlling them. the BGP protocol.
Following are different BGP events:
Manual Start: Manually start the peer connection.
Manual Stop: Manually stop the peer connection.
Automatic Start: Local system automatically starts the peer
connection.
Manual start with
passive TCP flag: Local system administrator manually starts the
peer connection with peer in passive mode.
Automatic start
with passive TCP flag: Local system administrator automatically starts
the peer connection with peer in passive mode.
Automatic start
with bgp_stop_flap
option set: Local system administrator automatically starts
the peer connection with peer oscillation
damping enabled.
Automatic start with
bgp_stop_flap option
set and passive TCP
establishment
option set: Local system administrator automatically starts
the peer connection with peer oscillation
damping enabled and with peer in passive mode.
Automatic stop: Local system automatically stops the
BGP connection.
Both, Manual Start and Manual Stop are mandatory BGP events. All These BGP events are of following types: Optional events linked to
other events are optional. Optional Session attributes, Administrative Events, Timer Events,
TCP Connection based Events, and BGP Message-based Events. Both,
the FSM and the BGP events are explained in details 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, way to introduce new features within the protocol. In particular, the
the BGP capability mechanism allows peers to negotiate various BGP capability mechanism allows a BGP speaker to advertise to its
optional features during startup. This allows the base BGP protocol peers during startup various optional features supported by the
to contain only essential functionality, while at the same time speaker (and receive similar information from the peers). This allows
providing a flexible mechanism for signaling protocol extensions. the base BGP protocol to contain only essential functionality, while
at the same time providing a flexible mechanism for signaling
protocol extensions.
4. BGP Persistent Peer Oscillations 4. BGP Persistent Peer Oscillations
Ideally, whenever a BGP speaker detects an error in any peer Ideally, whenever a BGP speaker detects an error in any peer
connection, it shuts down the peer and changes its FSM state to IDLE. connection, it shuts down the peer and changes its FSM state to IDLE.
BGP speaker requires a Start event to re-initiate its idle peer BGP speaker requires a Start event to re-initiate its idle peer
connection. If the error remains persistent and BGP speaker connection. If the error remains persistent and BGP speaker generates
generates Start event automatically then it may result in persistent Start event automatically then it may result in persistent peer
peer flapping. However, although peer oscillation is found to be flapping. However, although peer oscillation is found to be wide-
wide-spread in BGP implementations, methods for preventing persistent spread in BGP implementations, methods for preventing persistent peer
peer oscillations are outside the scope of base BGP protocol oscillations 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 bound, 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
occasionally changes in generally stable routes. occasional changes in generally stable routes.
A BGP implementation under high load conditions should empty as much
inbound routing updates from its input streams, processing only the
most recent route if the route for a given NLRI changes multiple
times. TCP also provides blocking on the writes on the sender side.
A BGP implementation under load should expect blocks on write calls
and send only the most recent routes when sockets unblock rather than
sending entire history.
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 loosing 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
skipping to change at page 9, line 30 skipping to change at page 2, line 250
In this section, we provide "order of magnitude" answers to the In this section, we provide "order of magnitude" answers to the
questions of how much link bandwidth, router memory and router CPU questions of how much link bandwidth, router memory and router CPU
cycles the BGP protocol will consume under normal conditions. In cycles the BGP protocol will consume under normal conditions. In
particular, we will address the scalability of BGP and its particular, we will address the scalability of BGP and its
limitations. limitations.
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 mean AS distance of the number of routes in the Internet by N, the total path attributes (for
Internet by M (distance at the level of an autonomous system, all N routes) received from a peer as A, and assume that the networks
expressed in terms of the number of autonomous systems), the total are uniformly distributed among the autonomous systems, then the
number of unique AS paths by A, and assume that the networks are worst case amount of bandwidth consumed during the initial exchange
uniformly distributed among the autonomous systems, then the worst between a pair of BGP speakers (P) is
case amount of bandwidth consumed during the initial exchange between
a pair of BGP speakers is
BW = O(N + (M * A))
BW = O((N + A) * P)
The following table illustrates the typical amount of bandwidth The following table illustrates the typical amount of bandwidth
consumed during the initial exchange between a pair of BGP speakers consumed during the initial exchange between a pair of BGP-4 speakers
based on the above assumptions (ignoring bandwidth consumed by the based on the above assumptions (ignoring bandwidth consumed by the
BGP Header). For purposes of the estimates here, we will calculate BGP-4 Header). For purposes of the estimates here, we will calculate
BW = 4 * (N + (M * A)). BW = (((4 * N) + A) * P).
# NLRI Mean AS Distance # AS's Bandwidth (MR)
---------- ---------------- ------ ----------------
40,000 15 400 184,000 bytes
100,000 10 10,000 800,000 bytes
120,000 10 15,000 1,080,000 bytes
140,000 15 20,000 1,760,000 bytes
[note that most of this bandwidth is consumed by the NLRI exchange]
BGP was created specifically to reduce the size of the set of NLRI 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. entries which have to be carried and exchanged by border routers.
The aggregation scheme, defined in RFC 1519 [RFC1519], describes the The aggregation scheme, defined in [RFC1519],describes the provider-
provider-based aggregation scheme in use in today's Internet. 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 has provided over BGP-3. If we simply enumerate processing that BGP-4 has provided over BGP-3. If we simply
all aggregate blocks into their individual class-based networks, we enumerate all aggregate blocks into their individual class-based
would not take into account "dead" space that has been reserved for networks, we would not take into account "dead" space that has been
future expansion. The best metric for determining the success of reserved for future expansion. The best metric for determining the
BGP's aggregation is to sample the number NLRI entries in the success of BGP's aggregation is to sample the number NLRI entries in
globally connected Internet today and compare it to projected growth the globally connected Internet today and compare it to projected
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 120,000 network entries [ROUTEVIEWS]. by BGP is approximately 120,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 the Internet. If the utilization depends only on the stability of its network which
Internet is stable, then the only link bandwidth and router CPU relates to BGP in terms of BGP UPDATE message announcments. If the
cycles consumed by BGP are due to the exchange of the BGP KEEPALIVE 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
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 periods of Internet instability, changes to the reachability During the periods of network instability, BGP routers within the
information are passed between routers in UPDATE messages. The network are generating routing updates that are exchanged using the
greatest overhead per UPDATE message occurs when each UPDATE message BGP UPDATE messages. The greatest overhead per UPDATE message occurs
contains only a single network. It should be pointed out that in when each UPDATE message contains only a single network. It should
practice routing changes exhibit strong locality with respect to the pointed out that in practice routing changes exhibit strong locality
AS path. That is, routes that change are likely to have common AS with respect to the route attributes. That is, routes that change
path. In this case, multiple networks can be grouped into a single are likely to have common route attributes. In this case, multiple
UPDATE message, thus significantly reducing the amount of bandwidth networks can be grouped into a single UPDATE message, thus
required (see also Appendix F.1 of [BGP4]). significantly reducing the amount of bandwidth required (see also
Appendix F.1 of [BGP4]).
Since in the steady state the link bandwidth and router CPU cycles
consumed by the BGP protocol are dependent only on the stability of
the Internet, it follows that BGP should have no scaling problems in
the areas of link bandwidth and router CPU utilization. This assumes
that as the Internet grows, the overall stability of the inter-AS
connectivity of the Internet can be controlled. In particular, while
the size of the IPv4 Internet routing table is bounded by O(232 * M),
(where M is a slow-moving function describing the AS
interconnectivity of the network), no such bound can be formulated
for the dynamic properties (i.e., stability) of BGP. Although, the
dynamic properties of the network cannot be quantitatively bounded,
they can be controlled within BGP. Beyond certain changes in the
network, BGP can start to suppress such changes using BGP Route Flap
Damping [RFC2439], pacing of its route updates, or BGP would be
unable to keep up with the changes and force suppression of multiple
changes over very short periods by causing the BGP peer socket to
block on the sender.
6.1.2. Memory requirements 6.1.2. Memory requirements
To quantify the worst case memory requirements for BGP, we denote the To quantify the worst case memory requirements for BGP, we denote the
total number of networks in the Internet by N, the mean AS distance total number of networks in the Internet by N, the mean AS distance
of the Internet by M (distance at the level of an autonomous system, of the Internet by M (distance at the level of an autonomous system,
expressed in terms of the number of autonomous systems), the total expressed in terms of the number of autonomous systems), the total
number of unique AS paths as A. Then the worst case memory number of unique AS paths as A. Then the worst case memory
requirements (MR) can be expressed as requirements (MR) can be expressed as
skipping to change at page 12, line 13 skipping to change at page 2, line 335
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 route as R, and number of bytes number of bytes required to store a network as R, and number of bytes
required to store one AS in an AS path as P. It is assumed that each required to store one AS in an AS path as P. It is assumed that each
network is encoded as four bytes, each AS is encoded as two bytes, network is encoded as four bytes, each AS is encoded as two bytes,
and each networks is reachable via some fraction of all of the peers and each networks is reachable via some fraction of all of the peers
(# BGP peers/per net). For purposes of the estimates here, we will (# BGP peers/per net). For purposes of the estimates here, we will
calculate MR = ((N * R) + (M * A) * P) calculate MR = (((N * R) + (M * A) * P) * S).
# Networks Mean AS Distance # AS's # BGP peers/per net Memory Req (MR) # Networks Mean AS Distance # AS's # BGP peers/per net Memory Req
(N) (M) (A) (P) (MR)
---------- ---------------- ------ ------------------- -------------- ---------- ---------------- ------ ------------------- --------------
100,000 20 3,000 20 1,040,000 100,000 20 3,000 20 10,400,000
100,000 20 15,000 20 1,040,000 100,000 20 15,000 20 20,000,000
120,000 10 15,000 100 75,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
forwarding table (and ignoring implementation details). In BGP RIB table (and ignoring implementation details). In particular,
particular, we derive upper bounds for the size of the forwarding we derive upper bounds for the size of the BGP RIB table. For
table. For example, at the time of this writing, the forwarding example, at the time of this writing, the BGP RIB tables of a typical
tables of a typical backbone router carry on the order of 120,000 backbone router carry on the order of 120,000 entries. Given this
entries. Given this number, one might ask whether it would be number, one might ask whether it would be possible to have a
possible to have a functional router with a table that will have functional router with a table that will have 1,000,000 entries.
1,000,000 entries. Clearly the answer to this question is more Clearly the answer to this question is more related to how BGP is
related to how BGP is implemented. A robust BGP implementation with a implemented. A robust BGP implementation with a reasonable CPU and
reasonable CPU and memory should not have issues scaling to such memory should not have issues scaling to such limits.
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 (see RFC 2622 [RFC2622] actually a part of the protocol specification ([RFC2622] for an
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 vendor-
independent standards. 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 provided 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
skipping to change at page 15, line 36 skipping to change at page 2, line 456
While this example is relatively simple, many operators may fail to While this example is relatively simple, many operators may fail to
recognize that the true source of the problem is that the BGP recognize that the true source of the problem is that the BGP
policies of ASes can interact in unexpected ways, and that these policies of ASes can interact in unexpected ways, and that these
interactions can result in multiple stable routings. One can imagine interactions can result in multiple stable routings. One can imagine
that the interactions could be much more complex in the real that the interactions could be much more complex in the real
Internet. We suspect that such anomalies will only become more Internet. We suspect that such anomalies will only become more
common as BGP continues to evolve with richer policy expressiveness. common as BGP continues to evolve with richer policy expressiveness.
For example, extended communities provide an even more flexible means For example, extended communities provide an even more flexible means
of signaling information within and between autonomous systems than of signaling information within and between autonomous systems than
is possible with RFC 1997 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, RFC 3345 [RFC3345] routing will ever be found). For example, [RFC3345] documents
documents several scenarios that lead to route oscillations several scenarios that lead to route oscillations associated with the
associated with the use of the Multi-Exit Discriminator or MED, use of the Multi-Exit Discriminator or MED, attribute. Route
attribute. Route oscillation will happen in BGP when a set of oscillation will happen in BGP when a set of policies has no
policies has no solution. That is, when there is no stable routing solution. That is, when there is no stable routing that satisfies
that satisfies the constraints imposed by policy, then BGP has no the constraints imposed by policy, then BGP has no choice by to keep
choice by to keep trying. In addition, BGP configurations can have a trying. In addition, BGP configurations can have a stable routing,
stable routing, yet the protocol may not be able to find it; BGP can yet the protocol may not be able to find it; BGP can "get trapped"
"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
skipping to change at page 17, line 7 skipping to change at page 2, line 514
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 allow 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 extensibility in
mind, new and/or evolving requirements can be addressed via existing mind, new and/or evolving requirements can be addressed via existing
mechanisms. mechanisms.
To summarize, BGP is well suitable as an inter-autonomous system To summarize, BGP is well suitable as an inter-autonomous system
routing protocol for the IPv4 Internet that is based on IP [RFC791] routing protocol for any internet that is based on IP [RFC791] as the
as the Internet Protocol and "hop-by-hop" routing paradigm. internet protocol and "hop-by-hop" routing paradigm.
9. Intellectual Property
The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it
has made any effort to identify any such rights. Information on the
IETF's procedures with respect to rights in standards-track and
standards-related documentation can be found in BCP-11. Copies of
claims of rights made available for publication and any assurances of
licenses to be made available, or the result of an attempt made to
obtain a general license or permission for the use of such
proprietary rights by implementors or users of this specification can
be obtained from the IETF Secretariat.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard. Please address the information to the IETF Executive
Director.
10. 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 versions of
this document. Tim Griffin, Randy Presuhn, Curtis Villamizar and this document. Tim Griffin, Randy Presuhn, Curtis Villamizar and
Atanu Ghosh also provided many insightful comments on earlier Atanu Ghosh also provided many insightful comments on earlier
versions of this document. versions of this document.
11. Security Considerations 10. Security Considerations
This document presents an analysis of the BGP protocol and as such BGP provides flexible mechanisms with varying levels of complexity
presents no new security implications for BGP. for security purposes. BGP sessions are authenticated using BGP
session addresses and the assigned AS number. Since BGP sessions use
TCP (and IP) for reliable transport, BGP sessions are further
authenticated and secured by any authentication and security
mechanisms used by TCP and IP.
12. IANA Considerations BGP uses TCP MD5 option for validating data and protecting against
spoofing of TCP segments exhanged between its sessions. The usage of
TCP MD5 option for BGP is described at length in [RFC 2385]. The TCP
MD5 Key management is discussed in [RFC 3562]. BGP data encryption is
provided using IPsec mechanism which encrypts the IP payload data
(including TCP and BGP data). The IPsec mechanism can be used in
both, the transport mode as well as the tunnel mode. The IPsec
mechanism is described in [RFC 2406]. Both, the TCP MD5 option and
the IPsec mechanism are not widely deployed security mechanisms for
BGP in today's Internet and hence it is difficult to guage their real
performance impact when using with BGP. However, since both the
mechanisms are TCP and IP based security mechanisms, the Link
Bandwidth, CPU utilization and router memory consumed by BGP protocol
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
IP) based CPU intensive attacks. It is a simple mechanism which
suggests the use of filtering BGP (TCP) segments using the IP TTL
value carried within the IP header of BGP (TCP) segments exchanged
between the EBGP sessions. The BGP TTL mechanism is described in
[BTSH]. Usage of [BTSH] impacts performance in a similar way as using
any ACL policies for BGP.
Such flexible TCP and IP based security mechanisms, allow BGP to
prevent insertion/deletion/modification of BGP data, any snooping of
the data, session stealing, etc. However, BGP is vulnerable to the
same security attacks that are present in TCP. The [BGP-VUL]
explains in depth about the BGP security vulneribility. At the time
of this writing, several efforts are underway for creating and
defining an appropriate security infrastructure within the BGP
protocol to provide authentication and security for its routing
information; some of which include [SBGP] and [SOBGP].
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.
13. References 12. References
13.1. Informative References 12.1. Informative 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-20.txt. Work in progress.
[CIDR] Fuller, V., Li, T., Yu, J., and K. Varadhan,
"Classless Inter-Domain Routing (CIDR): an Address
Assignment and Aggregation Strategy", RFC 1519,
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.
[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
Protocol BGP", RFC 1105, June 1989. Protocol BGP", RFC 1105, June 1989.
skipping to change at page 19, line 12 skipping to change at page 2, line 615
Address Assignment and Aggregation Strategy", RFC Address Assignment and Aggregation Strategy", RFC
1519, September 1993. 1519, September 1993.
[RFC1771] Rekhter, Y., and T. Li, "A Border Gateway [RFC1771] Rekhter, Y., and T. Li, "A Border Gateway
Protocol 4 (BGP-4)", RFC 1771, March 1995. Protocol 4 (BGP-4)", RFC 1771, March 1995.
[RFC1772] Rekhter, Y., and P. Gross, Editors, "Application [RFC1772] Rekhter, Y., and P. Gross, Editors, "Application
of the Border Gateway Protocol in the Internet", of the Border Gateway Protocol in the Internet",
RFC 1772, March 1995. RFC 1772, March 1995.
[RFC1774] Traina, P., "BGP-4 protocol analysis",
RFC 1774, March, 1995.
[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.
[RFC2439] Villamizar, C., Chandra, R., and R. Govindan,
"BGP Route Flap Damping", RFC 2439, November
1998.
[RFC2622] Alaettinoglu, C., et. al., "Routing Policy [RFC2622] Alaettinoglu, C., et. al., "Routing Policy
Specification Language (RPSL)" RFC 2622, May, Specification Language (RPSL)" RFC 2622, May,
1998. 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
the TCP MD5 Signature Option", RFC 3562,
July, 2003.
[RFC2406] Kent, S., Atkinson, R., "IP Encapsulating Security
Payload (ESP)", RFC 2406, November, 1998.
[ROUTEVIEWS] Meyer, D., "The Route Views Project", [ROUTEVIEWS] Meyer, D., "The Route Views Project",
http://www.routeviews.org http://www.routeviews.org
14. Author's Addresses [SBGP] Lynn, C., Mikkelson, J., and K. Seo, "Secure BGP S-BGP",
Internet-Draft, Work in Progress.
[soBGP] White, R., "Architecture and Deployment Considerations for
Secure Origin BGP (soBGP)", Internet-Draft, Work in Progress.
[BGP_VULN] Murphy, S., "BGP Security Vulnerabilities Analysis",
draft-ietf-idr-bgp-vuln-00.txt. work in progress
13. Author's Addresses
David Meyer David Meyer
Email: dmm@1-4-5.net Email: dmm@1-4-5.net
Keyur Patel Keyur Patel
Cisco Systems Cisco Systems
Email: keyupate@cisco.com Email: keyupate@cisco.com
15. Full Copyright Statement 14. Full Copyright Statement
Copyright (C) The Internet Society (2003). All Rights Reserved. Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78 and
except as set forth therein, the authors retain all their rights.
This document and translations of it may be copied and furnished to This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of Internet organizations, except as needed for the purpose of
skipping to change at line 747 skipping to change at page 2, line 698
The limited permissions granted above are perpetual and will not be The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
15. Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
16. Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 

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