AS_PATH, which precedes tuple Y in the aggregated AS_PATH,
X precedes Y in each AS_PATH in the initial set, which
contains Y, regardless of the type of Y.
- No tuple of type AS_SET with the same value SHALL appear
more than once in the aggregated AS_PATH.
- Multiple tuples of type AS_SEQUENCE with the same value may
appear in the aggregated AS_PATH only when adjacent to
another tuple of the same type and value.
An implementation may choose any algorithm that conforms to
these rules. At a minimum, a conformant implementation SHALL
be able to perform the following algorithm that meets all of
the above conditions:
- determine the longest leading sequence of tuples (as
defined above) common to all the AS_PATH attributes of the
routes to be aggregated. Make this sequence the leading
sequence of the aggregated AS_PATH attribute.
- set the type of the rest of the tuples from the AS_PATH
attributes of the routes to be aggregated to AS_SET, and
append them to the aggregated AS_PATH attribute.
- if the aggregated AS_PATH has more than one tuple with the
same value (regardless of tuple’s type), eliminate all but
one such tuple by deleting tuples of the type AS_SET from
the aggregated AS_PATH attribute.
- for each pair of adjacent tuples in the aggregated AS_PATH,
if both tuples have the same type, merge them together, as
long as doing so will not cause a segment with a length
greater than 255 to be generated.
Appendix F, Section F.6 presents another algorithm that
satisfies the conditions and allows for more complex policy
configurations.
ATOMIC_AGGREGATE:
If at least one of the routes to be aggregated has
ATOMIC_AGGREGATE path attribute, then the aggregated route
SHALL have this attribute as well.
AGGREGATOR:
Any AGGREGATOR attributes from the routes to be aggregated MUST
NOT be included in the aggregated route. The BGP speaker
performing the route aggregation MAY attach a new AGGREGATOR
attribute (see Section 5.1.7).
9.3. Route Selection Criteria
Generally, additional 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 (provided that the speaker is configured to
accept such routes). If such a route were ever used, a routing
loop could result.
- In order to achieve a successful distributed operation, only
routes with a likelihood of stability can be chosen. Thus, an
AS SHOULD avoid using unstable routes, and it SHOULD NOT make
rapid, spontaneous changes to its choice of route. Quantifying
the terms "unstable" and "rapid" (from the previous sentence)
will require experience, but the principle is clear. Routes
that are unstable can be "penalized" (e.g., by using the
procedures described in [RFC2439]).
9.4. Originating BGP routes
A BGP speaker may originate BGP routes by injecting routing
information acquired by some other means (e.g., via an IGP) into BGP.
A BGP speaker that originates BGP routes assigns the degree of
preference (e.g., according to local configuration) to these routes
by passing them through the Decision Process (see Section 9.1).
These routes MAY also be distributed to other BGP speakers within the
local AS as part of the update process (see Section 9.2). The
decision of whether to distribute non-BGP acquired routes within an
AS via BGP depends on the environment within the AS (e.g., type of
IGP) and SHOULD be controlled via configuration.
10. BGP Timers
BGP employs five timers: ConnectRetryTimer (see Section 8), HoldTimer
(see Section 4.2), KeepaliveTimer (see Section 8),
MinASOriginationIntervalTimer (see Section 9.2.1.2), and
MinRouteAdvertisementIntervalTimer (see Section 9.2.1.1).
Two optional timers MAY be supported: DelayOpenTimer, IdleHoldTimer
by BGP (see Section 8). Section 8 describes their use. The full
operation of these optional timers is outside the scope of this
document.
ConnectRetryTime is a mandatory FSM attribute that stores the initial
value for the ConnectRetryTimer. The suggested default value for the
ConnectRetryTime is 120 seconds.
HoldTime is a mandatory FSM attribute that stores the initial value
for the HoldTimer. The suggested default value for the HoldTime is
90 seconds.
During some portions of the state machine (see Section 8), the
HoldTimer is set to a large value. The suggested default for this
large value is 4 minutes.
The KeepaliveTime is a mandatory FSM attribute that stores the
initial value for the KeepaliveTimer. The suggested default value
for the KeepaliveTime is 1/3 of the HoldTime.
The suggested default value for the MinASOriginationIntervalTimer is
15 seconds.
The suggested default value for the
MinRouteAdvertisementIntervalTimer on EBGP connections is 30 seconds.
The suggested default value for the
MinRouteAdvertisementIntervalTimer on IBGP connections is 5 seconds.
An implementation of BGP MUST allow the HoldTimer to be configurable
on a per-peer basis, and MAY allow the other timers to be
configurable.
To minimize the likelihood that the distribution of BGP messages by a
given BGP speaker will contain peaks, jitter SHOULD be applied to the
timers associated with MinASOriginationIntervalTimer, KeepaliveTimer,
MinRouteAdvertisementIntervalTimer, and ConnectRetryTimer. A given
BGP speaker MAY apply the same jitter to each of these quantities,
regardless of the destinations to which the updates are being sent;
that is, jitter need not be configured on a per-peer basis.
The suggested default amount of jitter SHALL be determined by
multiplying the base value of the appropriate timer by a random
factor, which is uniformly distributed in the range from 0.75 to 1.0.
A new random value SHOULD be picked each time the timer is set. The
range of the jitter’s random value MAY be configurable.
Appendix A. Comparison with RFC 1771
There are numerous editorial changes in comparison to [RFC1771] (too
many to list here).
The following list the technical changes:
Changes to reflect the usage of features such as TCP MD5
[RFC2385], BGP Route Reflectors [RFC2796], BGP Confederations
[RFC3065], and BGP Route Refresh [RFC2918].
Clarification of the use of the BGP Identifier in the AGGREGATOR
attribute.
Procedures for imposing an upper bound on the number of prefixes
that a BGP speaker would accept from a peer.
The ability of a BGP speaker to include more than one instance of
its own AS in the AS_PATH attribute for the purpose of inter-AS
traffic engineering.
Clarification of the various types of NEXT_HOPs.
Clarification of the use of the ATOMIC_AGGREGATE attribute.
The relationship between the immediate next hop, and the next hop
as specified in the NEXT_HOP path attribute.
Clarification of the tie-breaking procedures.
Clarification of the frequency of route advertisements.
Optional Parameter Type 1 (Authentication Information) has been
deprecated.
UPDATE Message Error subcode 7 (AS Routing Loop) has been
deprecated.
OPEN Message Error subcode 5 (Authentication Failure) has been
deprecated.
Use of the Marker field for authentication has been deprecated.
Implementations MUST support TCP MD5 [RFC2385] for authentication.
Clarification of BGP FSM.
Appendix B. Comparison with RFC 1267
All the changes listed in Appendix A, plus the following.
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 the 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
[RFC1518, RFC1519].
To simplify configuration, this version introduces a new attribute,
LOCAL_PREF, that facilitates route selection procedures.
The INTER_AS_METRIC attribute has been renamed 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 to advertise which AS
and which BGP speaker within that AS caused the aggregation.
To ensure that Hold Timers are symmetric, the Hold Timer is now
negotiated on a per-connection basis. Hold Timers of zero are now
supported.
Appendix C. Comparison with RFC 1163
All of the changes listed in Appendices A and B, 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 router that is passed in the
NEXT_HOP path attribute to be part of the same Autonomous System as
the BGP Speaker.
The new document optimizes and simplifies the exchange of information
about previously reachable routes.
Appendix D. Comparison with RFC 1105
All of the changes listed in Appendices A, B, and C, plus the
following.
Minor changes to the [RFC1105] Finite State Machine were necessary to
accommodate the TCP user interface provided by BSD version 4.3.
The notion of Up/Down/Horizontal relations presented in RFC 1105 has
been removed from the protocol.
The changes in the message format from RFC 1105 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 RFC 1105, is referred to
as BGP-1; BGP, as specified in [RFC1163], is referred to as BGP-2;
BGP, as specified in RFC 1267 is referred to as BGP-3; and BGP, as
specified in this document is referred to as BGP-4.
Appendix E. TCP Options that May Be Used with BGP
If a local system TCP user interface supports the TCP PUSH function,
then each BGP message SHOULD be transmitted with PUSH flag set.
Setting PUSH flag forces BGP messages to be transmitted to the
receiver promptly.
If a local system TCP user interface supports setting the DSCP field
[RFC2474] for TCP connections, then the TCP connection used by BGP
SHOULD be opened with bits 0-2 of the DSCP field set to 110 (binary).
An implementation MUST support the TCP MD5 option [RFC2385].
Appendix F. Implementation Recommendations
This section presents some implementation recommendations.
Appendix F.1. Multiple Networks Per Message
The BGP protocol allows for multiple address prefixes with the same
path attributes to be specified in one message. Using this
capability is highly recommended. With one address prefix 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 that contain many address prefixes
per path attribute set from a routing table that is not organized on
a per path attribute set basis is to build many messages as the
routing table is scanned. As each address prefix is processed, a
message for the associated set of path attributes is allocated, if it
does not exist, and the new address prefix is added to it. If such a
message exists, the new address prefix is appended to it. If the
message lacks the space to hold the new address prefix, it is
transmitted, a new message is allocated, and the new address prefix
is inserted into the new message. When the entire routing table has
been scanned, all allocated messages are sent and their resources are
released. Maximum compression is achieved when all destinations
covered by the address prefixes share a common set of path
attributes, making it possible to send many address prefixes in one
4096-byte message.
When peering with a BGP implementation that does not compress
multiple address prefixes 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 when 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.
Appendix F.2. Reducing Route Flapping
To avoid excessive route flapping, a BGP speaker that needs to
withdraw a destination and send an update about a more specific or
less specific route should combine them into the same UPDATE message.
Appendix F.3. Path Attribute Ordering
Implementations that combine update messages (as described above in
Section 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 that 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.
Appendix F.4. 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.
Appendix F.5. Control Over Version Negotiation
Because BGP-4 is capable of carrying aggregated routes that cannot be
properly represented in BGP-3, an implementation that supports BGP-4
and another BGP version should provide the capability to only speak
BGP-4 on a per-peer basis.
Appendix F.6. Complex AS_PATH Aggregation
An implementation that chooses to provide a path aggregation
algorithm retaining 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 ASes 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 ASes (as defined above) within each
AS_PATH attribute that are in the same relative order within
both AS_PATH attributes. Two ASes, 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 ASes identified
in (a), in exactly the same order as they appear in the
AS_PATH attributes to be aggregated. If two consecutive
ASes identified in (a) do not immediately follow each other
in both of the AS_PATH attributes to be aggregated, then the
intervening ASes (ASes that are between the two consecutive
ASes that are the same) in both attributes are combined into
an AS_SET path segment that consists of the intervening ASes
from both AS_PATH attributes. This segment is then placed
between the two consecutive ASes identified in (a) of the
aggregated attribute. If two consecutive ASes identified in
(a) immediately follow each other in one attribute, but do
not follow in another, then the intervening ASes of the
latter are combined into an AS_SET path segment. This
segment is then placed between the two consecutive ASes
identified in (a) of the aggregated attribute.
c) For each pair of adjacent tuples in the aggregated AS_PATH,
if both tuples have the same type, merge them together if
doing so will not cause a segment of a length greater than
255 to be generated.
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.
Security Considerations
A BGP implementation MUST support the authentication mechanism
specified in RFC 2385 [RFC2385]. The authentication provided by this
mechanism could be done on a per-peer basis.
BGP makes use of TCP for reliable transport of its traffic between
peer routers. To provide connection-oriented integrity and data
origin authentication on a point-to-point basis, BGP specifies use of
the mechanism defined in RFC 2385. These services are intended to
detect and reject active wiretapping attacks against the inter-router
TCP connections. Absent the use of mechanisms that effect these
security services, attackers can disrupt these TCP connections and/or
masquerade as a legitimate peer router. Because the mechanism
defined in the RFC does not provide peer-entity authentication, these
connections may be subject to some forms of replay attacks that will
not be detected at the TCP layer. Such attacks might result in
delivery (from TCP) of "broken" or "spoofed" BGP messages.
The mechanism defined in RFC 2385 augments the normal TCP checksum
with a 16-byte message authentication code (MAC) that is computed
over the same data as the TCP checksum. This MAC is based on a one-
way hash function (MD5) and use of a secret key. The key is shared
between peer routers and is used to generate MAC values that are not
readily computed by an attacker who does not have access to the key.
A compliant implementation must support this mechanism, and must
allow a network administrator to activate it on a per-peer basis.
RFC 2385 does not specify a means of managing (e.g., generating,
distributing, and replacing) the keys used to compute the MAC. RFC
3562 [RFC3562] (an informational document) provides some guidance in
this area, and provides rationale to support this guidance. It notes
that a distinct key should be used for communication with each
protected peer. If the same key is used for multiple peers, the
offered security services may be degraded, e.g., due to an increased
risk of compromise at one router that adversely affects other
routers.
The keys used for MAC computation should be changed periodically, to
minimize the impact of a key compromise or successful cryptanalytic
attack. RFC 3562 suggests a crypto period (the interval during which
a key is employed) of, at most, 90 days. More frequent key changes
reduce the likelihood that replay attacks (as described above) will
be feasible. However, absent a standard mechanism for effecting such
changes in a coordinated fashion between peers, one cannot assume
that BGP-4 implementations complying with this RFC will support
frequent key changes.
Obviously, each should key also be chosen to be difficult for an
attacker to guess. The techniques specified in RFC 1750 for random
number generation provide a guide for generation of values that could
be used as keys. RFC 2385 calls for implementations to support keys
"composed of a string of printable ASCII of 80 bytes or less." RFC
3562 suggests keys used in this context be 12 to 24 bytes of random
(pseudo-random) bits. This is fairly consistent with suggestions for
analogous MAC algorithms, which typically employ keys in the range of
16 to 20 bytes. To provide enough random bits at the low end of this
range, RFC 3562 also observes that a typical ACSII text string would
have to be close to the upper bound for the key length specified in
RFC 2385.
BGP vulnerabilities analysis is discussed in [RFC4272].
IANA Considerations
All the BGP messages contain an 8-bit message type, for which IANA
has created and is maintaining a registry entitled "BGP Message
Types". This document defines the following message types:
Name Value Definition
---- ----- ----------
OPEN 1 See Section 4.2
UPDATE 2 See Section 4.3
NOTIFICATION 3 See Section 4.5
KEEPALIVE 4 See Section 4.4
Future assignments are to be made using either the Standards Action
process defined in [RFC2434], or the Early IANA Allocation process
defined in [RFC4020]. Assignments consist of a name and the value.
The BGP UPDATE messages may carry one or more Path Attributes, where
each Attribute contains an 8-bit Attribute Type Code. IANA is
already maintaining such a registry, entitled "BGP Path Attributes".
This document defines the following Path Attributes Type Codes:
Name Value Definition
---- ----- ----------
ORIGIN 1 See Section 5.1.1
AS_PATH 2 See Section 5.1.2
NEXT_HOP 3 See Section 5.1.3