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]