draft-ietf-idr-bgp-analysis-01.txt   draft-ietf-idr-bgp-analysis-02.txt 
INTERNET-DRAFT David Meyer INTERNET-DRAFT David Meyer
draft-ietf-idr-bgp-analysis-01.txt Keyur Patel draft-ietf-idr-bgp-analysis-02.txt Keyur Patel
Category Informational Category Informational
Expires: October 2003 April 2003 Expires: October 2003 April 2003
BGP-4 Protocol Analysis BGP-4 Protocol Analysis
<draft-ietf-idr-bgp-analysis-01.txt> <draft-ietf-idr-bgp-analysis-02.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 in full conformance with
all provisions of Section 10 of RFC2026. all provisions 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.
skipping to change at page 3, line 23 skipping to change at page 3, line 23
4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 8 4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 8
5. BGP Performance characteristics and Scalability. . . . . . . . 8 5. BGP Performance characteristics and Scalability. . . . . . . . 8
5.1. Link bandwidth and CPU utilization. . . . . . . . . . . . . 8 5.1. Link bandwidth and CPU utilization. . . . . . . . . . . . . 8
5.1.1. CPU utilization. . . . . . . . . . . . . . . . . . . . . 9 5.1.1. CPU utilization. . . . . . . . . . . . . . . . . . . . . 9
5.1.2. Memory requirements. . . . . . . . . . . . . . . . . . . 11 5.1.2. Memory requirements. . . . . . . . . . . . . . . . . . . 11
6. BGP Policy Expressiveness and its Implications . . . . . . . . 12 6. BGP Policy Expressiveness and its Implications . . . . . . . . 12
6.1. Existence of Unique Stable Routings . . . . . . . . . . . . 13 6.1. Existence of Unique Stable Routings . . . . . . . . . . . . 13
6.2. Existence of Stable Routings. . . . . . . . . . . . . . . . 14 6.2. Existence of Stable Routings. . . . . . . . . . . . . . . . 14
7. Applicability. . . . . . . . . . . . . . . . . . . . . . . . . 15 7. Applicability. . . . . . . . . . . . . . . . . . . . . . . . . 15
8. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 16 8. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 16
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 9. Informative References . . . . . . . . . . . . . . . . . . . . 17
10. Author's Address. . . . . . . . . . . . . . . . . . . . . . . 18 10. Author's Addresses. . . . . . . . . . . . . . . . . . . . . . 18
11. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 18 11. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 18
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 protocol was published in RFC
1105 [RFC1105]. Since then BGP versions 2, 3, and 4 have been 1105 [RFC1105]. Since then BGP versions 2, 3, and 4 have been
developed. Version 2 was documented in RFC 1163 [RFC1163]. Version 3 developed. Version 2 was documented in RFC 1163 [RFC1163]. Version 3
is documented in RFC 1267 [RFC1267]. Version 4 is documented in the is documented in RFC 1267 [RFC1267]. Version 4 is documented in the
[BGP4] (version 4 of BGP will hereafter be referred to as BGP). The [BGP4] (version 4 of BGP will hereafter be referred to as BGP). The
skipping to change at page 5, line 6 skipping to change at page 5, line 6
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 AS_PATH. AS One of the most important path attributes is the Autonomous System
reachability information traverses the Internet, this information is Path, or AS_PATH. AS reachability information traverses the Internet,
augmented by the list of autonomous systems that have been traversed this information is augmented by the list of autonomous systems that
thus far, forming the AS_PATH. The AS_PATH allows straightforward have been traversed thus far, forming the AS_PATH. The AS_PATH allows
suppression of the looping of routing information. In addition, the straightforward suppression of the looping of routing information. In
AS_PATH serves as a powerful and versatile mechanism for policy-based addition, the AS_PATH serves as a powerful and versatile mechanism
routing. 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
skipping to change at page 6, line 10 skipping to change at page 6, line 10
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
of configured peers for the BGP operation. A BGP implementation of configured peers for the BGP operation. A BGP implementation
requires that a BGP speaker must connect to and listen on TCP port requires that a BGP speaker must connect to and listen on TCP port
179 for accepting any new BGP connections from it's peers. The BGP 179 for accepting any new BGP connections from its peers. The BGP
Finite State Machine, or FSM, must be initiated and maintained for Finite State Machine, or FSM, must be initiated and maintained for
each new incoming and outgoing peer connections. However, in steady each new incoming and outgoing peer connections. However, in steady
state operation, there will be only one BGP FSM per connection per state operation, there will be only one BGP FSM per connection per
peer. peer.
There may exist a temporary period where in a BGP peer may have There may exist a temporary period where in a BGP peer may have
separate incoming and outgoing connections resulting into two separate incoming and outgoing connections resulting into two
different BGP FSMs for a peer (instead of one). This can be resolved different BGP FSMs for a peer (instead of one). This can be resolved
following BGP connection collision rules defined in the [BGP4]. following BGP connection collision rules defined in the [BGP4].
skipping to change at page 6, line 42 skipping to change at page 6, line 42
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 operates 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 its peers. These BGP events are used for initiating and
terminating peer connections. They also assist BGP in identifying any terminating peer connections. They also assist BGP in identifying any
persistent peer connection oscillations and provides mechanism persistent peer connection oscillations and provide a mechanism
for controlling it. for controlling them.
Following are different BGP events: Following are different BGP events:
Manual Start: Manually start the peer connection. Manual Start: Manually start the peer connection.
Manual Stop: Manually stop the peer connection. Manual Stop: Manually stop the peer connection.
Automatic Start: Local system automatically starts the peer Automatic Start: Local system automatically starts the peer
connection. connection.
skipping to change at page 7, line 22 skipping to change at page 7, line 22
peer connection with peer in passive mode. peer connection with peer in passive mode.
Automatic start Automatic start
with passive TCP flag: Local system administrator automatically starts with passive TCP flag: Local system administrator automatically starts
the peer connection with peer in passive mode. the peer connection with peer in passive mode.
Automatic start Automatic start
with bgp_stop_flap with bgp_stop_flap
option set: Local system administrator automatically starts option set: Local system administrator automatically starts
the peer connection with peer oscillation the peer connection with peer oscillation
damping enabled damping enabled.
Automatic start with Automatic start with
bgp_stop_flap option bgp_stop_flap option
set and passive TCP set and passive TCP
establishment establishment
option set: Local system administrator automatically starts option set: Local system administrator automatically starts
the peer connection with peer oscillation the peer connection with peer oscillation
damping enabled and with peer in passive mode. damping enabled and with peer in passive mode.
Automatic stop: Local system automatically stops the Automatic stop: Local system automatically stops the
BGP connection. BGP connection.
Both, Manual Start and Manual Stop are mandatory BGP events. All Both, Manual Start and Manual Stop are mandatory BGP events. All
other events are optional. other events are optional.
3. BGP Capabilities 3. BGP Capabilities
The BGP Capability mechanism [RFC2842] provides easy and flexible way The BGP Capability mechanism [RFC2842] provides an easy and flexible
to introduce new features within the protocol. In particular, the BGP way to introduce new features within the protocol. In particular, the
capability mechanism allows peers to negotiate various optional BGP capability mechanism allows peers to negotiate various optional
features during startup. This allows the base BGP protocol to contain features during startup. This allows the base BGP protocol to contain
only essential functionality, while at the same time providing a only essential functionality, while at the same time providing a
flexible mechanism for signaling protocol extensions. 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 error remains persistent and BGP speaker generates connection. If the error remains persistent and BGP speaker generates
Start event automatically then it may result in persistent peer Start event automatically then it may result in persistent peer
flapping. However, although peer oscillation is found to be wide- flapping. However, although peer oscillation is found to be wide-
spread in BGP implementations, methods for preventing persistent peer spread in BGP implementations, methods for preventing persistent peer
oscillations are outside the scope of base BGP protocol oscillations are outside the scope of base BGP protocol
specification. specification.
5. BGP Performance characteristics and Scalability 5. BGP Performance characteristics and Scalability
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.
It is important to note that BGP does not require all the routers It is important to note that BGP does not require all the routers
within an autonomous system to participate in the BGP protocol. In within an autonomous system to participate in the BGP protocol. In
particular, only the border routers that provide connectivity between particular, only the border routers that provide connectivity between
the local autonomous system and their adjacent autonomous systems the local autonomous system and their adjacent autonomous systems
need participate in BGP. The ability to constraint the set of BGP need participate in BGP. The ability to constrain the set of BGP
speakers is one way to address scaling issues. speakers is one way to address scaling issues.
5.1. Link bandwidth and CPU utilization 5.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 mean AS distance of the
Internet by M (distance at the level of an autonomous system, 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 autonomous systems in the Internet by A, and assume that number of autonomous systems in the Internet by A, and assume that
skipping to change at page 9, line 36 skipping to change at page 9, line 36
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 has provided over BGP-3. If we simply enumerate
all aggregate blocks into their individual class-based networks, we all aggregate blocks into their individual class-based networks, we
would not take into account "dead" space that has been reserved for would not take into account "dead" space that has been reserved for
future expansion. The best metric for determining the success of future expansion. The best metric for determining the success of
BGP's aggregation is to sample the number NLRI entries in the BGP's aggregation is to sample the number NLRI entries in the
globally connected Internet today and compare it to projected growth globally connected Internet today and compare it to projected growth
rates before BGP was deployed. 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 approximately 120,000 network entries [ROUTEVIEWS]. by BGP is approximately 120,000 network entries [ROUTEVIEWS].
5.1.1. CPU utilization 5.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 the Internet. If the
Internet is stable, then the only link bandwidth and router CPU Internet is stable, then the only link bandwidth and router CPU
cycles consumed by BGP are due to the exchange of the BGP KEEPALIVE 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
skipping to change at page 10, line 16 skipping to change at page 10, line 15
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 periods of Internet instability, changes to the reachability
information are passed between routers in UPDATE messages. If we information are passed between routers in UPDATE messages. If we
denote the number of routing changes per second by C, then in the denote the number of routing changes per second by C, then in the
worst case the amount of bandwidth consumed by the BGP can be worst case the amount of bandwidth consumed by the BGP can be
expressed as O(C * M). The greatest overhead per UPDATE message expressed as O(C * M). The greatest overhead per UPDATE message
occurs when each UPDATE message contains only a single network. It occurs when each UPDATE message contains only a single network. It
should be pointed out that in practice routing changes exhibit strong should be pointed out that in practice routing changes exhibit strong
locality with respect to the AS path. That is routes that change are locality with respect to the AS path. That is, routes that change are
likely to have common AS path. In this case multiple networks can be likely to have common AS path. In this case, multiple networks can be
grouped into a single UPDATE message, thus significantly reducing the grouped into a single UPDATE message, thus significantly reducing the
amount of bandwidth required (see also Appendix F.1 of [BGP4]). amount of bandwidth required (see also Appendix F.1 of [BGP4]).
Since in the steady state the link bandwidth and router CPU cycles Since in the steady state the link bandwidth and router CPU cycles
consumed by the BGP protocol are dependent only on the stability of 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 Internet, it follows that BGP should have no scaling problems in
the areas of link bandwidth and router CPU utilization. This assumes the areas of link bandwidth and router CPU utilization. This assumes
that as the Internet grows, the overall stability of the inter-AS that as the Internet grows, the overall stability of the inter-AS
connectivity of the Internet can be controlled. In particular, while connectivity of the Internet can be controlled. In particular, while
the size of the IPv4 Internet routing table is bounded by O(2^32 * the size of the IPv4 Internet routing table is bounded by O(2^32 *
M), (where M is a slow-moving function describing the AS M), (where M is a slow-moving function describing the AS
interconnectivity of the network), no such bound can be formulated interconnectivity of the network), no such bound can be formulated
for the dynamic properties (i.e., stability) of BGP. Finally, since for the dynamic properties (i.e., stability) of BGP. Finally, since
the dynamic properties of the network cannot be quantitatively the dynamic properties of the network cannot be quantitatively
bounded, stability must be addressed via heuristics such as BGP bounded, stability must be addressed via heuristics such as BGP
Route Flap Dampening [RFC2439]. Due to the nature of BGP, such Route Flap Damping [RFC2439]. Due to the nature of BGP, such damping
dampening should be viewed as a local to an autonomous system matter should be viewed as a matter local to an autonomous system matter
(see also Appendix F.2 of [BGP4]). (see also Appendix F.2 of [BGP4]).
It may also be instructive to compare bandwidth and CPU requirements It may also be instructive to compare bandwidth and CPU requirements
of BGP with EGP. While with BGP the complete information is exchanged of BGP with the Exterior Gateway Protocol (EGP). While with BGP the
only at the connection establishment time, with EGP the complete complete information is exchanged only at the connection
information is exchanged periodically (usually every 3 minutes). Note establishment time, with EGP the complete information is exchanged
that both for BGP and for EGP the amount of information exchanged is periodically (usually every 3 minutes). Note that both for BGP and
roughly on the order of the networks reachable via a peer that sends for EGP the amount of information exchanged is roughly on the order
the information. Therefore, even if one assumes extreme instabilities of the number of networks reachable via a peer that sends the
of BGP, its worst case behavior will be the same as the steady state information. Therefore, even if one assumes extreme instabilities of
behavior of it's predecessor, EGP. BGP, its worst case behavior will be the same as the steady state
behavior of its predecessor, EGP.
Operational experience with BGP showed that the incremental update Operational experience with BGP showed that the incremental update
approach employed by BGP provides qualitative improvement in both approach employed by BGP provides qualitative improvement in both
bandwidth and CPU utilization when compared with complete periodic bandwidth and CPU utilization when compared with complete periodic
updates used by EGP (see also presentation by Dennis Ferguson at the updates used by EGP (see also presentation by Dennis Ferguson at the
Twentieth IETF, March 11-15, 1991, St.Louis). Twentieth IETF, March 11-15, 1991, St.Louis).
5.1.2. Memory requirements 5.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
skipping to change at page 11, line 21 skipping to change at page 11, line 21
number of autonomous systems in the Internet by A, and the total number of autonomous systems in the Internet by A, and the total
number of BGP speakers that a system is peering with by K (note that number of BGP speakers that a system is peering with by K (note that
K will usually be dominated by the total number of the BGP speakers K will usually be dominated by the total number of the BGP speakers
within a single autonomous system). Then the worst case memory within a single autonomous system). Then the worst case memory
requirements (MR) can be expressed as requirements (MR) can be expressed as
MR = O((N + M * A) * K) MR = O((N + M * A) * K)
It is interesting to note that prior to the introduction of BGP in It is interesting to note that prior to the introduction of BGP in
the NSFNET Backbone, memory requirements on the NSFNET Backbone the NSFNET Backbone, memory requirements on the NSFNET Backbone
routers running EGP were on the order of O(N *K). Therefore, the routers running EGP were on the order of O(N *K).
extra overhead in memory incurred by modern routers running BGP is
less than 7 percent.
Since a mean AS distance M is a slow moving function of the Since a mean AS distance M is a slow moving function of the
interconnectivity ("meshiness") of the Internet, for all practical interconnectivity ("meshiness") of the Internet, for all practical
purposes the worst case router memory requirements are on the order purposes the worst case router memory requirements are on the order
of the total number of networks in the Internet times the number of of the total number of networks in the Internet times the number of
peers the local system is peering with. We expect that the total peers the local system is peering with. We expect that the total
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
scaling properties are linearly related to the total number of properties are linearly related to the total number of networks in
networks in the Internet. the Internet.
The following table illustrates typical memory requirements of a The following table illustrates typical memory requirements of a
router running BGP. It is assumed that each network is encoded as router running BGP. It is assumed that each network is encoded as
four bytes, each AS is encoded as two bytes, and each networks is four bytes, each AS is encoded as two bytes, and each networks is
reachable via some fraction of all of the peers (# BGP peers/per reachable via some fraction of all of the peers (# BGP peers/per
net). For purposes of the estimates here, we will calculate MR = net). For purposes of the estimates here, we will calculate MR =
((N*4) + (M*A)*2) * K. ((N*4) + (M*A)*2) * K.
# 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 (MR)
---------- ---------------- ------ ------------------- -------------- ---------- ---------------- ------ ------------------- --------------
skipping to change at page 12, line 4 skipping to change at page 11, line 46
reachable via some fraction of all of the peers (# BGP peers/per reachable via some fraction of all of the peers (# BGP peers/per
net). For purposes of the estimates here, we will calculate MR = net). For purposes of the estimates here, we will calculate MR =
((N*4) + (M*A)*2) * K. ((N*4) + (M*A)*2) * K.
# 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 (MR)
---------- ---------------- ------ ------------------- -------------- ---------- ---------------- ------ ------------------- --------------
100,000 20 3,000 20 1,040,000 100,000 20 3,000 20 1,040,000
100,000 20 15,000 20 1,040,000 100,000 20 15,000 20 1,040,000
120,000 10 15,000 100 75,000,000 120,000 10 15,000 100 75,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 forwarding table (and ignoring implementation details). In
particular, we derive upper bounds for the size of the forwarding particular, we derive upper bounds for the size of the forwarding
table. For example, at the time of this writing, the forwarding table. For example, at the time of this writing, the forwarding
tables of a typical backbone router carries on the order of 120,000 tables of a typical backbone router carry on the order of 120,000
entries. Given this number, one might ask whether it would be entries. Given this number, one might ask whether it would be
possible to have a functional router with a table that will have possible to have a functional router with a table that will have
1,000,000 entries. Clearly the answer to this question is independent 1,000,000 entries. Clearly the answer to this question is independent
of BGP. Interestingly, in his review of the BGP protocol for the BGP of BGP. Interestingly, in his review of the BGP protocol for the BGP
review committee in March of 1990, Paul Tsuchiya noted that "BGP does review committee in March of 1990, Paul Tsuchiya noted that "BGP does
not scale well. This is not really the fault of BGP. It is the fault not scale well. This is not really the fault of BGP. It is the fault
of the flat IP address space. Given the flat IP address space, any of the flat IP address space. Given the flat IP address space, any
routing protocol must carry network numbers in its updates." The routing protocol must carry network numbers in its updates." The
introduction of the provider based aggregation schemes (e.g., CIDR introduction of the provider based aggregation schemes (e.g., RFC
[RFC1519]) have sought to address this issue, to the extent possible, 1519 [RFC1519]) have sought to address this issue, to the extent
within the context of current addressing architectures. possible, within the context of current addressing architectures.
6. BGP Policy Expressiveness and its Implications 6. 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
routing policies are usually the first thing that comes to a network 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 (see RFC 2622 [RFC2622]
for an example of such a policy language). In addition, the BGP for an 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.
skipping to change at page 14, line 7 skipping to change at page 14, line 7
AS1 ------> AS2 AS1 ------> AS2
/|\ | /|\ |
| | | |
| | | |
| \|/ | \|/
AS3 ------- AS4 AS3 ------- AS4
That is, the AS3-AS4 link is intended to be used only when the That is, the AS3-AS4 link is intended to be used only when the
AS2-AS4 link is down (for outbound traffic, AS4 simply gives routes AS2-AS4 link is down (for outbound traffic, AS4 simply gives routes
from AS2 a higher local preference). This is a common scenario in from AS2 a higher local preference). This is a common scenario in
today's Internet. But note that this configuration has another today's Internet. But note that this configuration has another stable
stable solution: solution:
AS1 ------- AS2 AS1 ------- AS2
| | | |
| | | |
| | | |
\|/ \|/ \|/ \|/
AS3 ------> AS4 AS3 ------> AS4
In this case, AS3 does not translate the "depref my route" community In this case, AS3 does not translate the "depref my route" community
received from AS4 into a "depref my route" community for AS1, and so received from AS4 into a "depref my route" community for AS1, and so
skipping to change at page 14, line 46 skipping to change at page 14, line 46
possible with RFC 1997 communities. At the same time, applications of possible with RFC 1997 communities. At the same time, applications of
communities by network operators are evolving to address complex communities by network operators are evolving to address complex
issues of inter-domain traffic engineering. issues of inter-domain traffic engineering.
6.2. Existence of Stable Routings 6.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, RFC 3345 [RFC3345]
documents several scenarios that lead to route oscillations documents several scenarios that lead to route oscillations
associated with the use of MEDs. Route oscillation will happen in BGP associated with the use of the Multi-Exit Discriminator or MED,
when a set of policies has no solution. That is, when there is no attribute. Route oscillation will happen in BGP when a set of
stable routing that satisfies the constraints imposed by policy, then policies has no solution. That is, when there is no stable routing
BGP has no choice by to keep trying. In addition, BGP configurations that satisfies the constraints imposed by policy, then BGP has no
can have a stable routing, yet the protocol may not be able to find choice by to keep trying. In addition, BGP configurations can have a
it; BGP can "get trapped" down a blind alley that has no solution. stable routing, yet the protocol may not be able to find it; BGP can
"get trapped" 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.
7. Applicability 7. Applicability
skipping to change at page 16, line 13 skipping to change at page 16, line 14
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 the IPv4 Internet that is based on IP [RFC791]
as the Internet Protocol and "hop-by-hop" routing paradigm. Finally, as the Internet Protocol and "hop-by-hop" routing paradigm. Finally,
BGP is equally applicable to IPv6 [RFC2460] internets. BGP is equally applicable to IPv6 [RFC2460] internets.
8. Acknowledgments 8. 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 also provided many insightful comments on this document. Tim Griffin and Randy Presuhn also provided many
earlier versions of this document. insightful comments on earlier versions of this document.
9. References 9. Informative References
[BGP4] Rekhter, Y., T. Li., and Hares. S, 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-19.txt. Work in progress. draft-ietf-idr-bgp4-19.txt. Work in progress.
[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 Reynolds, J., "TELNET PROTOCOL [RFC854] Postel, J. and J. Reynolds, "TELNET PROTOCOL
SPECIFICATION", RFC 854, May, 1983. SPECIFICATION", RFC 854, May, 1983.
[RFC1105] Lougheed, K., and Rekhter, Y, "Border Gateway [RFC1105] Lougheed, K., and Y. Rekhter, "Border Gateway
Protocol BGP", RFC 1105, June 1989. Protocol BGP", RFC 1105, June 1989.
[RFC1163] Lougheed, K., and Rekhter, Y, "Border Gateway [RFC1163] Lougheed, K., and Rekhter, Y, "Border Gateway
Protocol BGP", RFC 1105, June 1990. Protocol BGP", RFC 1105, June 1990.
[RFC1264] Hinden, R., "Internet Routing Protocol [RFC1264] Hinden, R., "Internet Routing Protocol
Standardization Criteria", RFC 1264, October 1991. Standardization Criteria", RFC 1264, October 1991.
[RFC1267] Lougheed, K., and Rekhter, Y, "Border Gateway [RFC1267] Lougheed, K., and Rekhter, Y, "Border Gateway
Protocol 3 (BGP-3)", RFC 1105, October 1991. Protocol 3 (BGP-3)", RFC 1105, October 1991.
skipping to change at page 17, line 45 skipping to change at page 17, line 45
[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.
[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 Govindan, R., [RFC2439] Villamizar, C., Chandra, R., and R. Govindan,
"BGP Route Flap Damping", RFC 2439, November "BGP Route Flap Damping", RFC 2439, November
1998. 1998.
[RFC2460] Deering, S, and R. Hinden, "Internet Protocol, [RFC2460] Deering, S, and R. Hinden, "Internet Protocol,
Version 6 (IPv6) Specification", RFC 2460, Version 6 (IPv6) Specification", RFC 2460,
December, 1998. December, 1998.
[RFC2622] C. Alaettinoglu, et al., "Routing Policy [RFC2622] C. Alaettinoglu, 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
Retana, A, "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.
[ROUTEVIEWS] Meyer, David, "The Route Views Project", [ROUTEVIEWS] Meyer, D., "The Route Views Project",
http://www.routeviews.org http://www.routeviews.org
10. Author's Address 10. Author's Addresses
David Meyer David Meyer
Email: dmm@maoz.com Email: dmm@maoz.com
Keyur Patel Keyur Patel
Cisco Systems Cisco Systems
Email: keyupate@cisco.com Email: keyupate@cisco.com
11. Full Copyright Statement 11. Full Copyright Statement
 End of changes. 

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