external BGP links, or
b) there are no other acceptable routes to the network
(as listed in the UPDATE message) that have been
received over external BGP links.
When a BGP speaker receives an unreachable route from a BGP peer over
external BGP link, it shall advertise that route to all other BGP
speakers in its autonomous system, indicating that it has become
unreachable, if the following condition occur:
a) a corresponding acceptable route to the same destination
was considered to be the best one among all routes to that
destination that have been received over external BGP links
(that is the local system has been advertising the
route to all other BGP speakers in its autonomous system
before it received the UPDATE message that reported it
as unreachable).
Whenever a BGP speaker selects a new route (among all the routes
received from external and internal BGP peers), or determines that
the reachable destinations within its own autonomous system have
changed, it shall generate an UPDATE message and forward it to each
of its external peers (peers connected via external BGP links).
If a route in the UPDATE was received over an internal link, it is
not propagated over any other internal link. This restriction is due
to the fact that all BGP speakers within a single AS form a
completely connected graph (see above).
If the UPDATE message is propagated over an external link, then the
local AS number is prepended to the AS_PATH attribute, and the
NEXT_HOP attribute is updated with an IP address of the router that
should be used as a next hop to the network. If the UPDATE message
is propagated over an internal link, then the AS_PATH attribute and
the NEXT_HOP attribute are passed unmodified.
Generally speaking, the rules for comparing routes among several
alternatives are outside the scope of this document. There are two
exceptions:
- If the local AS appears in the AS path of the new route being
considered, then that new route cannot be viewed as better than
any other route. If such a route were ever used, a routing loop
would result.
- In order to achieve successful distributed operation, only routes
with a likelihood of stability can be chosen. Thus, an AS must
avoid using unstable routes, and it must not make rapid
spontaneous changes to its choice of route. Quantifying the terms
"unstable" and "rapid" in the previous sentence will require
experience, but the principle is clear.
10. Detection of Inter-AS Policy Contradictions
Since BGP requires no central authority for coordinating routing
policies among ASs, and since routing policies are not exchanged via
the protocol itself, it is possible for a group of ASs to have a set
of routing policies that cannot simultaneously be satisfied. This
may cause an indefinite oscillation of the routes in this group of
ASs.
To help detect such a situation, all BGP speakers must observe the
following rule. If a route to a destination that is currently used
by the local system is determined to be unreachable (e.g., as a
result of receiving an UPDATE message for this route with the
UNREACHABLE attribute), then, before switching to another route, this
local system must advertize this route as unreachable to all the BGP
neighbors to which it previously advertized this route.
This rule will allow other ASs to distinguish between two different
situations:
- The local system has chosen to use a new route because the old
route become unreachable.
- The local system has chosen to use a new route because it
preferred it over the old route. The old route is still
viable.
In the former case, an UPDATE message with the UNREACHABLE attribute
will be received for the old route. In the latter case it will not.
In some cases, this may allow a BGP speaker to detect the fact that
its policies, taken together with the policies of some other AS,
cannot simultaneously be satisfied. For example, consider the
following situation involving AS A and its neighbor AS B. B
advertises a route with a path of the form <B,...>, where A is not
present in the path. A then decides to use this path, and advertises
<A,B,...> to all its neighbors. B later advertises <B,...,A,...>
back to A, without ever declaring its previous path <B,...> to be
unreachable. Evidently, A prefers routes via B and B prefers routes
via A. The combined policies of A and B, taken together, cannot be
satisfied. Such an event should be noticed, logged locally, and
brought to the attention of AS A's administration. The means to do
this, however, lies outside the scope of this document. Also outside
the document is a more complete procedure for detecting such
contradictions of policy.
While the above rules provide a mechanism to detect a set of routing
policies that cannot be satisfied simultaneously, the protocol itself
does not provide any mechanism for suppressing the route oscillation
that may result from these unsatisfiable policies. The reason for
doing this is that routing policies are viewed as external to the
protocol and as determined by the local AS administrator.
Appendix 1. BGP FSM State Transitions and Actions.
This Appendix discusses the transitions between states in the BGP FSM
in response to BGP events. The following is the list of these states
and events.
BGP States:
1 - Idle
2 - Connect
3 - Active
4 - OpenSent
5 - OpenConfirm
6 - Established
BGP Events:
1 - BGP Start
2 - BGP Stop
3 - BGP Transport connection open
4 - BGP Transport connection closed
5 - BGP Transport connection open failed
6 - BGP Transport fatal error
7 - ConnectRetry timer expired
8 - Holdtime timer expired
9 - KeepAlive timer expired
10 - Receive OPEN message
11 - Receive KEEPALIVE message
12 - Receive UPDATE messages
13 - Receive NOTIFICATION message
The following table describes the state transitions of the BGP FSM
and the actions triggered by these transitions.
Event Actions Message Sent Next State
--------------------------------------------------------------------
Idle (1)
1 Initialize resources none 2
Start ConnectRetry timer
Initiate a transport connection
others none none 1
Connect(2)
1 none none 2
3 Complete initialization OPEN 4
Clear ConnectRetry timer
5 Restart ConnectRetry timer none 3
7 Restart ConnectRetry timer none 2
Initiate a transport connection
others Release resources none 1
Active (3)
1 none none 3
3 Complete initialization OPEN 4
Clear ConnectRetry timer
5 Close connection 3
Restart ConnectRetry timer
7 Restart ConnectRetry timer none 2
Initiate a transport connection
others Release resources none 1
OpenSent(4)
1 none none 4
4 Close transport connection none 3
Restart ConnectRetry timer
6 Release resources none 1
10 Process OPEN is OK KEEPALIVE 5
Process OPEN failed NOTIFICATION 1
others Close transport connection NOTIFICATION 1
Release resources
OpenConfirm (5)
1 none none 5
4 Release resources none 1
6 Release resources none 1
9 Restart KeepAlive timer KEEPALIVE 5
11 Complete initialization none 6
Restart Holdtime timer
13 Close transport connection 1
Release resources
others Close transport connection NOTIFICATION 1
Release resources
Established (6)
1 none none 6
4 Release resources none 1
6 Release resources none 1
9 Restart KeepAlive timer KEEPALIVE 6
11 Restart Holdtime timer KEEPALIVE 6
12 Process UPDATE is OK UPDATE 6
Process UPDATE failed NOTIFICATION 1
13 Close transport connection 1
Release resources
others Close transport connection NOTIFICATION 1
Release resources
---------------------------------------------------------------------
The following is a condensed version of the above state transition
table.
Events| Idle | Active | Connect | OpenSent | OpenConfirm | Estab
| (1) | (2) | (3) | (4) | (5) | (6)
|--------------------------------------------------------------
1 | 2 | 2 | 3 | 4 | 5 | 6
| | | | | |
2 | 1 | 1 | 1 | 1 | 1 | 1
| | | | | |
3 | 1 | 4 | 4 | 1 | 1 | 1
| | | | | |
4 | 1 | 1 | 1 | 3 | 1 | 1
| | | | | |
5 | 1 | 3 | 3 | 1 | 1 | 1
| | | | | |
6 | 1 | 1 | 1 | 1 | 1 | 1
| | | | | |
7 | 1 | 2 | 2 | 1 | 1 | 1
| | | | | |
8 | 1 | 1 | 1 | 1 | 1 | 1
| | | | | |
9 | 1 | 1 | 1 | 1 | 5 | 6
| | | | | |
10 | 1 | 1 | 1 | 1 or 5 | 1 | 1
| | | | | |
11 | 1 | 1 | 1 | 1 | 6 | 6
| | | | | |
12 | 1 | 1 | 1 | 1 | 1 | 1 or 6
| | | | | |
13 | 1 | 1 | 1 | 1 | 1 | 1
| | | | | |
---------------------------------------------------------------
Appendix 2. Comparison with RFC1163
To detect and recover from BGP connection collision, a new field (BGP
Identifier) has been added to the OPEN message. New text (Section
6.8) has been added to specify the procedure for detecting and
recovering from collision.
The new document no longer restricts the border router that is passed
in the NEXT_HOP path attribute to be part of the same Autonomous
System as the BGP Speaker.
New document optimizes and simplifies the exchange of the information
about previously reachable routes.
Appendix 3. Comparison with RFC1105
All of the changes listed in Appendix 2, plus the following.
Minor changes to the RFC1105 Finite State Machine were necessary to
accommodate the TCP user interface provided by 4.3 BSD.
The notion of Up/Down/Horizontal relations present in RFC1105 has
been removed from the protocol.
The changes in the message format from RFC1105 are as follows:
1. The Hold Time field has been removed from the BGP header and
added to the OPEN message.
2. The version field has been removed from the BGP header and
added to the OPEN message.
3. The Link Type field has been removed from the OPEN message.
4. The OPEN CONFIRM message has been eliminated and replaced
with implicit confirmation provided by the KEEPALIVE message.
5. The format of the UPDATE message has been changed
significantly. New fields were added to the UPDATE message
to support multiple path attributes.
6. The Marker field has been expanded and its role broadened to
support authentication.
Note that quite often BGP, as specified in RFC1105, is referred to
as BGP-1, BGP, as specified in RFC1163, is referred to as BGP-2, and
BGP, as specified in this document is referred to as BGP-3.
Appendix 4. TCP options that may be used with BGP
If a local system TCP user interface supports TCP PUSH function, then
each BGP message should be transmitted with PUSH flag set. Setting
PUSH flag forces BGP messages to be transmitted promptly to the
receiver.
If a local system TCP user interface supports setting precedence for
TCP connection, then the BGP transport connection should be opened
with precedence set to Internetwork Control (110) value (see also
[6]).
Appendix 5. Implementation Recommendations
This section presents some implementation recommendations.
5.1 Multiple Networks Per Message
The BGP protocol allows for multiple networks with the same AS path
and next-hop gateway to be specified in one message. Making use of
this capability is highly recommended. With one network per message
there is a substantial increase in overhead in the receiver. Not only
does the system overhead increase due to the reception of multiple
messages, but the overhead of scanning the routing table for flash
updates to BGP peers and other routing protocols (and sending the
associated messages) is incurred multiple times as well. One method
of building messages containing many networks per AS path and gateway
from a routing table that is not organized per AS path is to build
many messages as the routing table is scanned. As each network is
processed, a message for the associated AS path and gateway is
allocated, if it does not exist, and the new network is added to it.
If such a message exists, the new network is just appended to it. If
the message lacks the space to hold the new network, it is
transmitted, a new message is allocated, and the new network is
inserted into the new message. When the entire routing table has been
scanned, all allocated messages are sent and their resources
released. Maximum compression is achieved when all networks share a
gateway and common path attributes, making it possible to send many
networks in one 4096-byte message.
When peering with a BGP implementation that does not compress
multiple networks into one message, it may be necessary to take steps
to reduce the overhead from the flood of data received when a peer is
acquired or a significant network topology change occurs. One method
of doing this is to limit the rate of flash updates. This will
eliminate the redundant scanning of the routing table to provide
flash updates for BGP peers and other routing protocols. A
disadvantage of this approach is that it increases the propagation
latency of routing information. By choosing a minimum flash update
interval that is not much greater than the time it takes to process
the multiple messages this latency should be minimized. A better
method would be to read all received messages before sending updates.
5.2 Processing Messages on a Stream Protocol
BGP uses TCP as a transport mechanism. Due to the stream nature of
TCP, all the data for received messages does not necessarily arrive
at the same time. This can make it difficult to process the data as
messages, especially on systems such as BSD Unix where it is not
possible to determine how much data has been received but not yet
processed.
One method that can be used in this situation is to first try to read
just the message header. For the KEEPALIVE message type, this is a
complete message; for other message types, the header should first be
verified, in particular the total length. If all checks are
successful, the specified length, minus the size of the message
header is the amount of data left to read. An implementation that
would "hang" the routing information process while trying to read
from a peer could set up a message buffer (4096 bytes) per peer and
fill it with data as available until a complete message has been
received.
5.3 Processing Update Messages
In BGP, all UPDATE messages are incremental. Once a particular
network is listed in an Update message as being reachable through an
AS path and gateway, that piece of information is expected to be
retained indefinitely.
In order for a route to a network to be removed, it must be
explicitly listed in an Update message as being unreachable or with
new routing information to replace the old. Note that a BGP peer will
only advertise one route to a given network, so any announcement of
that network by a particular peer replaces any previous information
about that network received from the same peer.
One useful optimization is that unreachable networks need not be
advertised with their original attributes. Instead, all unreachable
networks could be sent in a single message, perhaps with an AS path
consisting of the local AS only and with an origin set to INCOMPLETE.
This approach has the obvious advantage of low overhead; if all
routes are stable, only KEEPALIVE messages will be sent. There is no
periodic flood of route information.
However, this means that a consistent view of routing information
between BGP peers is only possible over the course of a single
transport connection, since there is no mechanism for a complete
update. This requirement is accommodated by specifying that BGP peers
must transition to the Idle state upon the failure of a transport
connection.
5.4 BGP Timers
BGP employs three timers: ConnectRetry, Holdtime, and KeepAlive.
Suggested value for the ConnectRetry timer is 120 seconds.
Suggested value for the Holdtime timer is 90 seconds.
Suggested value for the KeepAlive timer is 30 seconds.
An implementation of BGP shall allow any of these timers to be
configurable.
5.5 Frequency of Route Selection
An implementation of BGP shall allow a border router to set up the
minimum amount of time that must elapse between selection and
subsequent advertisement of better routes received by a given BGP
speaker from BGP speakers located in adjacent ASs.
Since fast convergence is needed within an AS, deferring selection
does not apply to selection of better routes chosen as a result of
UPDATEs from BGP speakers located in the advertising speaker's own
AS. To avoid long-lived black holes, it does not apply to
advertisement of previously selected routes which have become
unreachable. In both of these situations, the local BGP speaker must
select and advertise such routes immediately.
If a BGP speaker received better routes from BGP speakers in adjacent
ASs, but have not yet advertised them because the time has not yet
elapsed, the reception of any routes from other BGP speakers in its
own AS shall trigger a new route selection process that will be based
on both updates from BGP speakers in the same AS and in adjacent ASs.
References
[1] Mills, D., "Exterior Gateway Protocol Formal Specification", RFC
904, BBN, April 1984.
[2] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET
Backbone", RFC1092, T.J. Watson Research Center, February 1989.
[3] Braun, H-W., "The NSFNET Routing Architecture", RFC1093,
MERIT/NSFNET Project, February 1989.
[4] Postel, J., "Transmission Control Protocol - DARPA Internet
Program Protocol Specification", RFC793, DARPA, September 1981.
[5] Rekhter, Y., and P. Gross, "Application of the Border Gateway
Protocol in the Internet", RFC1268, T.J. Watson Research Center,
IBM Corp., ANS, October 1991.
[6] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
Specification", RFC791, DARPA, September 1981.
Security Considerations
Security issues are not discussed in this memo.
Authors' Addresses
Kirk Lougheed
cisco Systems, Inc.
1525 O'Brien Drive
Menlo Park, CA 94025
Phone: (415) 326-1941
Email: LOUGHEED@CISCO.COM
Yakov Rekhter
T.J. Watson Research Center IBM Corporation
P.O. Box 218
Yorktown Heights, NY 10598
Phone: (914) 945-3896
Email: YAKOV@WATSON.IBM.COM