Network Working Group Enke Chen
Internet Draft Naiming Shen
Expiration Date: March 2005 Redback Networks
Advertisement of the Group Best Paths in BGP
draft-chen-bgp-group-path-update-02.txt
1. Status of this Memo
By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
2. Abstract
In this document we first identify the (neighbor-AS based) Group Best
Paths for an address prefix as the sufficient subset that can be
advertised by a BGP route reflector or a BGP confederation ASBR to
eliminate the MED-type route oscillations in a network. We then
propose a BGP extension to support the advertisement of the Group
Best Paths by a route reflector or a confederation ASBR. The
extension also allows the advertisement of all the paths in a group
that survive the MED comparison, thus achieving the same routing
consistency as the full IBGP mesh. The proposed mechanisms are
designed such that the vast majority of the BGP speakers in a network
need only minor software changes in order to deploy the mechanisms.
Chen & Shen [Page 1]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
3. Introduction
The current BGP update procedures [1, 2, 3] can be characterized as
"best path based" as an UPDATE message only deals with the
advertisement of the best paths which are identified by the address
prefixes.
As documented in [4], the routing information reduction by BGP Route
Reflection [2] or BGP Confederation [3] can result in persistent IBGP
route oscillations with certain routing setup and network topologies.
Except for a couple artificially engineered network topologies, the
MED attribute [1] has played a pivotal role in virtually all of the
known persistent IBGP route oscillations. For the sake of brevity,
we use the term "MED-type route oscillation" hereafter to refer to a
persistent IBGP route oscillation in which the MED plays a role.
In order to eliminate the MED-type route oscillations and to achieve
consistent routing in a network, clearly a route reflector or a
confederation ASBR needs to advertise more than just the best path
for an address prefix. Various efforts have been made trying to
extend BGP to advertise multiple paths for an address prefix. We
believe, however, that we should first tackle the most fundamental
issue of identifying the "right" subset of paths for an address
prefix that needs to be advertised by a route reflector or a
confederation ASBR, and then introduce BGP extensions to support such
route advertisements. In addition, the solution needs to have
reasonable implementation and deployment properties.
In this document we first identify the (neighbor-AS based) Group Best
Paths for an address prefix as the sufficient subset that can be
advertised by a BGP route reflector or a BGP confederation ASBR to
eliminate the MED-type route oscillations in a network. We then
propose a BGP extension to support the advertisement of the Group
Best Paths by a route reflector or a confederation ASBR. The
extension also allows the advertisement of all the paths in a group
that survive the MED comparison, thus achieving the same routing
consistency as the full IBGP mesh. The proposed mechanisms are
designed such that the vast majority of the BGP speakers in a network
need only minor software changes in order to deploy the mechanisms.
Chen & Shen [Page 2]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
4. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [9].
5. What to Advertise
The term neighbor-AS for a route refers to the neighboring AS from
which the route was received. The calculation of the neighbor-AS is
specified in Sect. 9.1.2.2 of [1], and Section 7.2 of [3]. By
definition the MED is comparable only among routes with the same
neighbor-AS. As a result, the route selection procedures specified
in [1] would conceptually involve two steps: first organize the paths
for an address prefix into groups according to their respective
neighbor-AS's, and calculate the most preferred one (termed "Group
Best Path") for each of the groups; Then calculate the overall best
path among all the Group Best Paths. Note that the overall best path
would naturally be a Group Best Path.
Observe that in a network that maintains a full IBGP mesh all the BGP
speakers have consistent and equivalent routing information. Such a
network is thus free of the MED-type route oscillations and other
routing inconsistencies (e.g., forwarding loops). Observe also that
only the paths that survive the (Local_Pref, AS-PATH Length, Origin,
MED) comparisons [1] would contribute to the route selection in the
network.
Based on these observations, in this section we identify two sets of
paths that are appropriate for advertisement by a route reflector or
a confederation ASBR. The first set would involve smaller number of
paths, and would be sufficient to eliminate the MED-type route
oscillations (subject to certain commonly adopted topological
constrains). The second set may involve larger number of paths, and
would achieve the same routing consistency as the full IBGP mesh.
5.1. Advertise the Group Best Paths
As a generally recommended and widely adopted practice, a route
reflection cluster or a confederation sub-AS should be designed such
that the IGP metrics for links within a cluster (or confederation
sub-AS) are smaller than the IGP metrics for the links between the
clusters (or confederation sub-AS). This practice helps achieve
consistent routing within a route reflection cluster or a
confederation sub-AS.
Chen & Shen [Page 3]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
When the aforementioned practice for devising a route reflection
cluster or confederation sub-AS is followed in a network, we claim
that the advertisement of all the Group Best Paths by a route
reflector or a confederation ASBR is sufficient to eliminate the MED-
type route oscillations in the network. This claim can be validated
as the following.
Consider a route reflection cluster that sources one or more paths
that would survive the (Local_Pref, AS-PATH Length, Origin, MED)
comparisons among all the paths in the network. One of these
surviving paths would be selected as the Group Best Path by the route
reflector in the cluster. Due to the constrain on the IGP metrics as
described previously, this path would remain as the Group Best Path
and would be advertised to all other clusters even after a path is
received from another cluster.
On the other hand, when no path in a route reflection cluster would
survive the (Local_Pref, AS-PATH Length, Origin, MED) comparisons
among all the paths in the network, the Group Best Path (when exists)
for a route reflector would be from another cluster. Clearly the
advertise of the Group Best Path by the route reflector to the
clients only depends on the paths received from other clusters.
Therefore there is no MED-type route oscillation in the network as
the advertisement of a Group Best Path to a peer does not depend on
the paths received from that peer.
The claim for the confederation can be validated similarly.
Note that a Group Best Path for an address prefix can be identified
by the combination of the address prefix and the neighbor-AS.
It should be noted that the approach of advertising the Group Best
Paths requires certain topological constrains to be satisfied in
order to eliminate the MED-type route oscillation. In addition, the
BGP speakers still depend on the route selection by the route
reflector or the confederation ASBR. As the route selection involves
the comparison of the nexthop's IGP metrics which are specific to a
particular BGP speaker, the routing information advertised by a route
reflector or a confederation ASBR may still be inadequate to avoid
other routing inconsistencies such as forwarding loops in certain
networks.
Chen & Shen [Page 4]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
5.2. Advertise the Group Multi-Paths
In order to guarantee routing consistency and to remove the
topological constrains for route reflection or confederation, a route
reflector or a confederation ASBR may advertise all the paths in each
group that survive the MED comparison (the step prior to the IGP
metric comparison) in route selection. This approach would achieve
the same routing consistency as the full IBGP mesh. These paths are
termed Group Multi-Paths hereafter.
For a route in an AS (or Confederation), let us use the term "AS-
Advertiser" hereafter to refer to the BGP Identifier of the BGP
speaker that originates the route in the AS (or Confederation). Then
a Group Multi-Path for an address prefix can be identified by the
combination of the address prefix and the AS-Advertiser.
The AS-Advertiser can be derived from the ORIGINATOR_ID attribute [2]
or the BGP Identifier of the remote BGP speaker, except for the
scenario in which the route reflection is used within a confederation
Sub-AS as the ORIGINATOR_ID would just carry the BGP Identifier of a
BGP speaker within a particular confederation sub-AS. To deal with
that, in this document we resurrect the "ADVERTISER" attribute
proposed in [10] with the following slightly updated definition:
The ADVERTISER attribute of a route is an optional, non-transitive
attribute that can be used to carry the BGP Identifier of the BGP
speaker that originates the route in an AS (or Confederation). The
Type Code of the ADVERTISER attribute is 12 (assigned by IANA).
Therefore the AS-Advertiser for a path can be obtained from the
following fields exclusively:
- first the ADVERTISER attribute if it is present;
- then the ORIGINATOR_ID attribute if it is present;
- then the BGP Identifier of the BGP speaker from which the path
is received.
Chen & Shen [Page 5]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
6. NLRI Encoding for Route Withdraw
The current NLRI encodings specified in [1, 5, 6] suffice for a
reachable route in an UPDATE message as the neighbor-AS is implicitly
carried in the AS-PATH attribute, and the AS-Advertiser can be
carried in the existing fields as described in the previous section.
To withdraw a path with a particular neighbor-AS or an AS-Advertiser,
the current NLRI encodings are revised by prepending the neighbor-AS
or AS-Advertiser to the existing encodings. That is, the NLRI
encodings specified in [1] and [5] are revised as the following:
+----------------------------------------+
| Neighbor-AS / AS-Advertiser (4 octets) |
+----------------------------------------+
| Length (1 octet) |
+----------------------------------------+
| Prefix (variable) |
+----------------------------------------+
and the NLRI encoding specified in [6] is modified as the following:
+----------------------------------------+
| Neighbor-AS / AS-Advertiser (4 octets) |
+----------------------------------------+
| Length (1 octet) |
+----------------------------------------+
| Label (3 octets) |
+----------------------------------------+
.............................
+----------------------------------------+
| Prefix (variable) |
+----------------------------------------+
The usage of the revised NLRI encodings is specified in the Operation
section.
Chen & Shen [Page 6]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
7. Grouped Path Update Capability
The "Grouped Path Update Capability" is a new BGP capability [7].
The Capability Code for this capability is specified in the "IANA
Considerations" section of this document. The Capability Length field
of this capability is one octet. The Capability Value field has only
one field, Send-Mode, which specifies the procedures the BGP speaker
would like to follow in sending updates. The Send-Mode field may
have one of the following values:
Value Symbolic Name
0 Single Best Path
1 Group Best Path
2 Group Multi-Paths
When advertising the capability to an internal peer, or to a
confederation external peer, a BGP speaker conveys to the peer that
the speaker is capable of receiving updates based on all the Send-
Mode values from the peer. In addition, as detailed in the Operation
section, the procedures the speaker would follow in sending updates
is determined by the setting of the Send-Mode field of the capability
advertised and whether the "Grouped Path Update Capability" is
received from the peer.
8. Operation
A BGP speaker that has implemented the procedures for receiving
updates based on all of the Send-Mode values SHOULD advertise the
"Grouped Path Update Capability" to its internal peers and
confederation external peers using BGP Capabilities advertisement
[7]. The setting of the Send-Mode field depends on the
configuration.
The "Grouped Path Update Capability" SHOULD not be advertised to an
external peer. A BGP speaker MUST ignore the "Grouped Path Update
Capability" from a peer that is neither internal nor confederation
external.
A BGP speaker MUST follow the existing best path based update
procedures with a peer unless the BGP speaker advertises the "Grouped
Path Update Capability" and also receives the capability from the
peer.
Consider that two BGP speakers A and B advertise the "Grouped Path
Update Capability" to each other. The NLRI encodings in an UPDATE
message MUST follow the ones specified in [1, 5, 6] unless the Send-
Chen & Shen [Page 7]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
Mode field of the capability advertised by one speaker is set to
"Group Best Path" or "Group Multi-Paths" in which case that speaker
MUST use the revised NLRI encodings specified in this document to
withdraw a path.
In addition, the following procedures MUST be followed in formatting
and processing UPDATE messages between the two BGP speakers.
- When Speaker A sets the Send-Mode field to "Single Best Path"
in the Capability advertised, it means that Speaker A would
follow the existing best path based update procedures in route
advertisement.
Speaker B MUST follow the best path based update procedures in
processing UPDATE messages received from Speaker A.
- When Speaker A sets the Send-Mode field to "Group Best Path" in
the Capability advertised, then Speaker A MUST generate a route
update based on the combination of the address prefix and the
neighbor-AS.
Speaker B MUST use the combination of the address prefix and the
neighbor-AS to identify the path being updated from Speaker A.
Note that Speaker B must first calculate the neighbor-AS from
the AS-PATH attribute of the UPDATE message when processing a
reachable route received from Speaker A.
- When Speaker A sets the Send-Mode field to "Group Multi-Paths"
in the Capability advertised, then Speaker A MUST generate a
route update based on the combination of the address prefix
and the AS-Advertiser.
Speaker B MUST use the combination of the address prefix and the
AS-Advertiser to identify the path being updated from Speaker A.
Note that Speaker B must first calculate the AS-Advertiser when
processing a reachable route received from Speaker A.
Chen & Shen [Page 8]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
9. Route Reflection and Confederation
As discussed in the "What To Advertise" section, a route reflector or
a confederation ASBR should advertise either the Group Best Paths or
the Group Multi-Paths (instead of the overall best path). The
procedures for sending updates by a route reflector or a
confederation ASBR are revised as follows.
9.1. Route Reflection
Depending on the configuration a route reflector SHOULD set the Send-
Mode field to either "Group Best Path" or "Group Multi-Paths" in the
"Grouped Path Update Capability" advertised to an IBGP peer.
A route reflector SHOULD advertise to its clients all the Group Best
Paths (or the Group Multi-Paths) received from its non-client IBGP
peers.
A route reflector SHOULD advertise to its non-client IBGP peers all
the Group Best Paths (or the Group Multi-Paths) received from its
clients.
A route reflector MAY also advertise to its clients all the Group
Best Paths (or Group Multi-Paths) received from its clients.
A route reflector MUST propagate the ADVERTISER attribute (if
present) of a route when advertising the route to an internal peer.
9.2. Confederation
Depending on the configuration a confederation ASBR SHOULD set the
Send-Mode field to either "Group Best Path" or "Group Multi-Paths" in
the "Grouped Path Update Capability" advertised to an IBGP peer, and
to a confederation external peer.
A confederation ASBR SHOULD advertise to its IBGP peers all the Group
Best Paths (or the Group Multi-Paths) received from its confederation
external peers.
A confederation ASBR SHOULD advertise to confederation external peers
all the Group Best Paths (or the Group Multi-Paths) learned from its
IBGP peers.
A confederation ASBR MUST propagate the ADVERTISER attribute (if
present) of a route when advertising the route to an internal peer or
a confederation external peer.
Chen & Shen [Page 9]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
In a network that plans to deploy the "Group Multi-Paths" based
updates, if the ADVERTISER attribute does not exist for a reachable
route, a confederation ASBR MUST create the ADVERTISER attribute
(based on the ORIGINATOR_ID attribute or an appropriate BGP
Identifier) when advertising the route to a confederation external
peer.
9.3. Update Optimization
A Group Best Path or a Group Multi-Path does not need to be
advertised if it is lost to another Group Best Path in route
selection prior to Step C - MED Comparison specified in Sect. 9.1.2.2
[1]. This optimization is recommended in order to minimize the
number of paths advertised.
10. Deployment Considerations
While the route reflectors or confederation ASBRs in a network need
to advertise the Group Best Paths or Group Multi-Paths, the vast
majority of the BGP speakers in the network only need to receive the
Group Best Paths or Group Multi-Paths, which would involve just minor
software changes:
- Advertise the "Grouped Path Update Capability" with the
Send-Mode set to "Single Best Path".
- Process received UPDATE messages based on the address prefix
and the neighbor-AS, and based on the address prefix and the
AS-Advertiser.
To deploy the mechanism of advertising the Group Best Paths in a
network, it is recommended that the BGP speakers (one at a time) be
first upgraded to a software version that supports the new
capability, and be configured to advertise the new capability with
the Send-Mode field set to "Single Best Path". Then on a per route
reflection cluster or confederation sub-AS basis, the route
reflectors or the confederation ASBRs are re-configured to set the
Send-Mode field to "Group Best Path" in the capability advertised.
It should be emphasized that in order to eliminate the MED-type route
oscillations in a network using the approach of advertising the Group
Best Paths, the recommended practice for devising a route reflection
cluster or confederation sub-AS with respect to the IGP metrics
should be followed.
Chen & Shen [Page 10]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
It is expected that the approach of advertising the Group Best Paths
would be adequate to achieve consistent routing for the vast majority
of the networks. For a network that has large number of alternate
paths, the approach should be a good choice as the number of paths
advertised by a reflector or a confederation ASBR is bounded by the
number of the neighbor-AS's for a particular address prefix. The
additional states for an address prefix would also be per neighbor-AS
based rather than per path based. The number of the neighbor-AS's for
a particular address prefix is typically small because of the small
number of upstream providers for a customer and the nature of
advertising only customer routes at the inter-exchange points.
The approach of advertising the Group Best Paths, however, may still
be inadequate for certain networks to avoid other routing
inconsistencies such as forwarding loops. The required topological
constrains could also be operationally challenging. In these cases
the approach of advertising the Group Multi-Paths may be used. In
general this approach would result in larger number of paths to be
advertised, and may require per-path states to be maintained. Note
that the number of paths that need to be maintained and advertised
can be greatly reduced by accepting the IGP metric based MEDs from
other peering networks.
11. IANA Considerations
This document defines a new BGP capability (Grouped Path Update
Capability). The capability code needs to be assigned.
12. Security Considerations
This extension to BGP does not change the underlying security issues
inherent in the existing BGP [8].
13. Acknowledgments
The authors would like to thank Jenny Yuan, John Scudder and Pedro
Marques for their comments and suggestions.
Chen & Shen [Page 11]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
14. References
14.1. References
[1] Rekhter, Y., T. Li, and S. Hares, "A Border Gateway Protocol 4
(BGP-4)", draft-ietf-idr-bgp4-23.txt, November 2003.
[2] Bates, T., R. Chandra, and E. Chen "BGP Route Reflection - An
Alternative to Full Mesh IBGP", RFC 2796, Arpil 2000.
[3] Traina, P., D. McPherson, and J. Scudder, "Autonomous System
Confederations for BGP", draft-ietf-idr-rfc3065bis-02.txt,
May 2004.
[4] D. McPherson, V, Gill, D. Walton, and A. Retana, "Border Gateway
Protocol (BGP) Persistent Route Oscillation Condition",
RFC 3345, August 2002.
[5] Bates, T., R. Chandra, D. Katz, and Y. Rekhter, "Multiprotocol
Extension for BGP-4", RFC 2858, June 2000.
[6] Rekhter, R. and E. Rosen, "Carrying Label Information in BGP-4",
RFC 3107, May 2001.
[7] Chandra, R., Scudder, J., "Capabilities Advertisement with
BGP-4", draft-ietf-idr-rfc2842bis-02.txt, April 2002.
[8] Heffernan, A., "Protection of BGP Sessions via the TCP MD5
Signature Option", RFC 2385, August 1998.
[9] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[10] Haskin, D., " A BGP/IDRP Route Server alternative to a full mesh
routing", RFC 1863, October 1995.
Chen & Shen [Page 12]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
15. Authors' Addresses
Enke Chen
Redback Networks Inc.
300 Holger Way.
San Jose, CA 95134
EMail: enke@redback.com
Naiming Shen
Redback Networks Inc.
300 Holger Way.
San Jose, CA 95134
EMail: naiming@redback.com
16. Intellectual Property Notice
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.
Chen & Shen [Page 13]
Internet Draft draft-chen-bgp-group-path-update-02.txt September 2004
17. Full Copyright Notice
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 the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Chen & Shen [Page 14]