Appendix 2. Comparison with RFC1267
BGP-4 is capable of operating in an environment where a set of
reachable destinations may be expressed via a single IP prefix. The
concept of network classes, or subnetting is foreign to BGP-4. To
accommodate these capabilities BGP-4 changes semantics and encoding
associated with the AS_PATH attribute. New text has been added to
define semantics associated with IP prefixes. These abilities allow
BGP-4 to support the proposed supernetting scheme [9].
To simplify configuration this version introduces a new attribute,
LOCAL_PREF, that facilitates route selection procedures.
The INTER_AS_METRIC attribute has been renamed to be MULTI_EXIT_DISC.
A new attribute, ATOMIC_AGGREGATE, has been introduced to insure that
certain aggregates are not de-aggregated. Another new attribute,
AGGREGATOR, can be added to aggregate routes in order to advertise
which AS and which BGP speaker within that AS caused the aggregation.
To insure that Hold Timers are symmetric, the Hold Time is now
negotiated on a per-connection basis. Hold Times of zero are now
supported.
Appendix 3. Comparison with RFC1163
All of the changes listed in Appendix 2, plus the following.
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 4. Comparison with RFC1105
All of the changes listed in Appendices 2 and 3, 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, BGP, as specified in RFC1267 is referred to as BGP-3, and
BGP, as specified in this document is referred to as BGP-4.
Appendix 5. 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 6. Implementation Recommendations
This section presents some implementation recommendations.
6.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 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 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.
6.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.
6.3 Reducing route flapping
To avoid excessive route flapping a BGP speaker which needs to
withdraw a destination and send an update about a more specific or
less specific route shall combine them into the same UPDATE message.
6.4 BGP Timers
BGP employs five timers: ConnectRetry, Hold Time, KeepAlive,
MinASOriginationInterval, and MinRouteAdvertisementInterval The
suggested value for the ConnectRetry timer is 120 seconds. The
suggested value for the Hold Time is 90 seconds. The suggested value
for the KeepAlive timer is 30 seconds. The suggested value for the
MinASOriginationInterval is 15 seconds. The suggested value for the
MinRouteAdvertisementInterval is 30 seconds.
An implementation of BGP MUST allow these timers to be configurable.
6.5 Path attribute ordering
Implementations which combine update messages as described above in
6.1 may prefer to see all path attributes presented in a known order.
This permits them to quickly identify sets of attributes from
different update messages which are semantically identical. To
facilitate this, it is a useful optimization to order the path
attributes according to type code. This optimization is entirely
optional.
6.6 AS_SET sorting
Another useful optimization that can be done to simplify this
situation is to sort the AS numbers found in an AS_SET. This
optimization is entirely optional.
6.7 Control over version negotiation
Since BGP-4 is capable of carrying aggregated routes which cannot be
properly represented in BGP-3, an implementation which supports BGP-4
and another BGP version should provide the capability to only speak
BGP-4 on a per-peer basis.
6.8 Complex AS_PATH aggregation
An implementation which chooses to provide a path aggregation
algorithm which retains significant amounts of path information may
wish to use the following procedure:
For the purpose of aggregating AS_PATH attributes of two routes,
we model each AS as a tuple <type, value>, where "type" identifies
a type of the path segment the AS belongs to (e.g., AS_SEQUENCE,
AS_SET), and "value" is the AS number. Two ASs are said to be the
same if their corresponding <type, value> tuples are the same.
The algorithm to aggregate two AS_PATH attributes works as
follows:
a) Identify the same ASs (as defined above) within each AS_PATH
attribute that are in the same relative order within both
AS_PATH attributes. Two ASs, X and Y, are said to be in the
same order if either:
- X precedes Y in both AS_PATH attributes, or - Y precedes X
in both AS_PATH attributes.
b) The aggregated AS_PATH attribute consists of ASs identified
in (a) in exactly the same order as they appear in the AS_PATH
attributes to be aggregated. If two consecutive ASs identified
in (a) do not immediately follow each other in both of the
AS_PATH attributes to be aggregated, then the intervening ASs
(ASs that are between the two consecutive ASs that are the
same) in both attributes are combined into an AS_SET path
segment that consists of the intervening ASs from both AS_PATH
attributes; this segment is then placed in between the two
consecutive ASs identified in (a) of the aggregated attribute.
If two consecutive ASs identified in (a) immediately follow
each other in one attribute, but do not follow in another, then
the intervening ASs of the latter are combined into an AS_SET
path segment; this segment is then placed in between the two
consecutive ASs identified in (a) of the aggregated attribute.
If as a result of the above procedure a given AS number appears
more than once within the aggregated AS_PATH attribute, all, but
the last instance (rightmost occurrence) of that AS number should
be removed from the aggregated AS_PATH attribute.
References
[1] Mills, D., "Exterior Gateway Protocol Formal Specification", STD
18, RFC904, 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", T.J. Watson Research Center, IBM
Corp., ANS, RFC1655, T.J. Watson Research Center, MCI, July
1994.
[6] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
Specification", STD 5, RFC791, DARPA, September 1981.
[7] "Information Processing Systems - Telecommunications and
Information Exchange between Systems - Protocol for Exchange of
Inter-domain Routeing Information among Intermediate Systems to
Support Forwarding of ISO 8473 PDUs", ISO/IEC IS10747, 1993
[8] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter-
Domain Routing (CIDR): an Address Assignment and Aggregation
Strategy", RFC1519, BARRNet, cisco, MERIT, OARnet, September
1993.
[9] Rekhter, Y., and T. Li, "An Architecture for IP Address
Allocation with CIDR", RFC1518, T.J. Watson Research Center,
cisco, September 1993.
Security Considerations
Security issues are not discussed in this memo.
Editors' Addresses
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
Tony Li
cisco Systems, Inc.
1525 O'Brien Drive
Menlo Park, CA 94025