Network Working Group L. Benmohamed INTERNET-DRAFT Johns Hopkins University draft-liang-bgp-qos-00.txt C. Liang Expires: December 21, 2006 Johns Hopkins University E. Naber Johns Hopkins University A. Terzis Johns Hopkins University June 19, 2006 QoS Enhancements to BGP in Support of Multiple Classes of Service Status of This Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract This document specifies the requirements posed on multi-domain Quality of Service (QoS) routing protocols that provide multiple classes of service with multi-dimensional QoS requirements. In particular, it discusses enhancements to Border Gateway Protocol version 4 (BGPv4) that allow nodes to discover multiple paths with associated QoS attributes. In addition, this documents discusses the details of several new algorithms, such as the dominant path selection algorithm (DPSA). 1. Introduction BGPv4 is the dominating inter-domain routing protocol in the Internet. It was designed with minimal overhead traffic for scalability, and it offers extensive policy support for business needs. Information sharing among External Border Gateway Protocol Benmohamed, et al. Expires December 21, 2006 [Page 1]
Internet-Draft BGP QoS Enhancements June 2006 (eBGP) peers is limited. The only information passed from an AS to its neighbors is the set of destination network prefixes reachable from itself and the sequence of ASs to each destination network prefix. Many emerging needs in commercial and military networking have exposed limitations of the current eBGP. These future IP networks will support a very diverse mix of applications with very diverse QoS requirements. In addition, some of these networks may consist of a diverse set of component networks (wireless and wireline, fixed and mobile with different degrees of mobility, long-term and short-term ad-hoc), and these component networks may have dynamic service capabilities. Therefore, different paths between the same endpoints may have very different QoS characteristics, and these QoS characteristics may be time-variant. Having the capability to specify QoS requirements in routing, session admission, packet scheduling, buffer management, service restoration priority, degree of security protection, and similar other decisions will become an important need in future IP networks. This document specifies BGPv4 enhancements that allow multi-topology (exposing multiple routes) and QoS-aware routing, using several QoS metrics of importance to different applications. Unlike some other similar work, our enhancements support multiple QoS metrics and do not require any changes in the inter-domain routing architecture that BGPv4 is based upon. Since the enhanced BGP does not limit routers to advertise only one route for each destination prefix, we define the notion of dominant paths to keep the amount of information transfer to the minimum needed to be scalable. The enhanced BGP also incorporates mechanisms, such as Multiprotocol Label Switching (MPLS), and defines network-wide traffic classes to pin the route taken by packets with the same QoS requirements. 2. BGPv4 Enhancements There are five enhancements to BGPv4 that enable multi-paths and QoS- aware routing: (1) Exchanging potentially multiple paths per destination prefix. (2) Maintaining multiple QoS metrics for each path. (3) Pruning the set of known paths to a dominant set while maintaining optimality. (4) Choosing a particular path from this dominant set for the unique QoS requirements of a traffic class. (5) Enforcing the selected route. BGPv4 restricts each router to advertise to its neighbors only one Benmohamed, et al. Expires December 21, 2006 [Page 2]
Internet-Draft BGP QoS Enhancements June 2006 route per destination prefix. This information hiding behavior can prevent a router from learning the particular path that most appropriately addresses the QoS requirements for a given traffic class. Enhancement (1) removes this limitation, allowing each BGP router to advertise a set of dominant paths. Enhancement (2) associates a list of QoS metrics with each link, which are then used to make route decision. Details on how path QoS metrics are embedded in BGP_UPDATE messages and maintained will be discussed in more detail in later sections. The notion of dominant paths is enhancement (3), and it prevents each BGP router from advertising every path it knows. Dominant paths are selected by dominant path selection algorithm (DPSA), which is discussed in more detail in later sections. Exchanging all of these additional paths and QoS attributes is pointless unless the QoS-aware routing path decision is actually enforced. Enhancement (5) can be implemented with various mechanisms, which are discussed in our previous work [1]. We have chosen to run MPLS on route assignment by enhancement (4) to pin the path for each application's data flow. Class-assignment algorithm of enhancement (4) will be discussed in more detail in later sections. Incorporating these enhancements requires updating BGPv4 path selection process accordingly. - BGPv4 first manipulates path attributes, such as Local_Pref and AS_Path, so that routes from one or some neighbors are enabled. However, in order for QoS routing to be effective by being able to choose among a larger set of routes, routes from all neighbors should ideally be enabled. - In BGPv4 path selection process, each border router (BR) that terminates an enabled route selects itself among all enabled routes as an AS egress point. Then, non-egress nodes selects one of these egress points. Instead, under QoS routing, all enabled routes to a destination D received at a BR (from both iBGP and eBGP peers) undergo DPSA where a set of dominant paths is selected. This set of dominant paths is maintained for routing and advertisement. 2.1 Maintaining Path QoS Metrics The BGPv4 UPDATE message includes the AS_PATH attribute, which stores the sequence of ASs to reach the associated destination prefixes. In order to retain the structure of the BGPv4 UPDATE message, path QoS metrics are embedded in the AS_PATH attribute. This extension of the AS_PATH attribute has been modeled after TLV (Type-Length-Value) model. The TLV model provides a flexible architecture that will support the specific metrics that we are currently interested in, and it also provides support for any additional metrics in the future. Figure 1 and 2 show the old format and the new format of AS-PATH attribute: Benmohamed, et al. Expires December 21, 2006 [Page 3]
Internet-Draft BGP QoS Enhancements June 2006 ----------------------- | Length of | Path to | | Attribute | Prefix | ----------------------- Figure 1: BGPv4 AS_PATH attribute format ------------------------------------------------------------------ | Length of | # Metrics | Type | Length | Value | | Attribute | = N | (Metric 1) | (Metric 1) | (Metric 1) | ... ------------------------------------------------------------------ ---------------------------------------------------- | Type | Length | Value | Path to | ... | (Metric N) | (Metric N) | (Metric N) | Prefix | ---------------------------------------------------- Figure 2: Extended AS_PATH attribute format Each path QoS metric value is the accumulation of the QoS metric value of all the links that the path consists of. Therefore, maintaining path QoS metrics is a combined effort of each node along that path. The general accumulation rules are: - When advertising a path to another AS, the advertising node combines its intra-AS metric values with the metric values accumulated for the path thus far. - When receiving a path from another AS, the receiving node combines the metric values on the link that connects the receiving node to the advertising node with the metric values accumulated for the path thus far. 2.2 Dominant Path Select Algorithm (DPSA) For QoS requirements with a single metric, such as bandwidth, it is sufficient to know a path with the largest available bandwidth. If the best path is not feasible, then no other paths are. However, for QoS requirements with multiple metrics, such as bandwidth and delay, there might not be a single best path. The notion of dominant path is defined as a path where there is no other path with all QoS metrics being better. If a path P dominates a set S of paths, then paths in S do not need to be advertised as path P is the only one needed to make QoS routing decisions. Indeed, if a connection request cannot be supported by P then no path in S can satisfy the request. To illustrate DPSA, we will look at a small network topology with six paths from the source to the destination node. In addition, this network topology has two QoS metrics of interest: delay and bandwidth. ^ Benmohamed, et al. Expires December 21, 2006 [Page 4]
Internet-Draft BGP QoS Enhancements June 2006 | BANDWIDTH | | P3 P4 | P2 P5 | P1 P6 | -+---------------------------DELAY-> | Figure 3: Delay and bandwidth QoS characteristics of the six paths Figure 3 shows the delay and bandwidth QoS characteristics of the six paths in the network. DPSA selects P1, P2, and P3 to be the dominant paths because they are not covered by any other paths. P4, P5, and P6 are covered by P3 because P3 is equal or better in all QoS metrics. For each destination prefix in the Loc-Routing Information Base (Loc- RIB), we have to select a set of dominant paths for advertisement. Therefore, DPSA should be logically placed between Loc-RIB and BGPv4 Output Policy Engine. If there are more than one potentially dominant paths with all QoS metrics being equal, then the tie- breaking strategies described below narrows down to only one path. The first strategy is to prefer paths with the lowest AS hop counts, and the second strategy is to prefer paths with the lowest next-hop IP address. 2.3 Route Assignment For Each Traffic Class There are various mechanisms that can be used to pin the selected path for a particular application's data flow. We have chosen to run MPLS on the notion of traffic classes. A set of network-wide traffic classes are pre-defined on every node, and the task of class- assignment algorithm is to assign at most dominant one path to each traffic class under every destination prefix. For each traffic class, the algorithm starts by selecting a set of paths that can satisfy the QoS requirements of the traffic class. Then, from this set of paths, the best path is assigned to the traffic class. For QoS requirements with bandwidth and delay, the best path can be defined as the path with the largest Euclidean distance from the traffic class requirement. For each destination prefix in the Loc-Routing Information Base (Loc- RIB), we have to assign at most one dominant path to each traffic class. Therefore, class-assignment assignment should be logically placed between Loc-RIB and Forwarding Information Base (FIB). If there are more than one suitable paths for a traffic class, then the tie-breaking strategies described below narrows down to only one path. The first strategy is to prefer paths with the lowest AS hop counts, and the second strategy is to prefer paths with the lowest Benmohamed, et al. Expires December 21, 2006 [Page 5]
Internet-Draft BGP QoS Enhancements June 2006 next-hop IP address. 2.4 Forwarding Decision Forwarding decision at data plane depends on two information: packet destination address and packet traffic class. Both IPv4 Type of Service (TOS) field and IPv6 Priority field can store the identifier of the traffic class the packet belongs to. Longest-prefix-matching algorithm is first performed on the packet destination address to find the most specific destination address prefix in FIB. Since there might be multiple routes under a given address prefix in FIB, packet traffic class identifier is then used to match the route with the same traffic class identifier. The packet is dropped either if longest-prefix-matching algorithm does not return a destination address prefix from FIB, or if there is no route matching packet traffic class. 3. Relevant Results Simulation results on the dynamic behavior and the scalability of enhanced BGP are discussed in our previous work [2]. In addition, a proof of DPSA convergence under the assumption of synchronous operation is also presented in our previous work [2]. 4. Security Considerations This document does not directly concern security. It is believed that this extension inherits security issues in BGPv4. 5. IANA Considerations This document has no actions for IANA. 6. Informative References [1] L. Benmohamed, B. Doshi, T. DeSimone, R. Cole, "Inter-Domain Routing with Multi-Dimensional QoS Requirements", IEEE Milcom 2005 [2] L. Benmohamed, C. Liang, E. Naber, A. Terzis, "QoS Enhancements to BGP in Support of Multiple Classes of Service", June 2006 7. Authors' Addresses Lotfi Benmohamed Johns Hopkins University - Applied Physics Laboratory 11100 Johns Hopkins Road Laurel MD, 20723 US EMail: lotfi.benmohamed@jhuapl.edu Benmohamed, et al. Expires December 21, 2006 [Page 6]
Internet-Draft BGP QoS Enhancements June 2006 Chieh-Jan Mike Liang Johns Hopkins University - Computer Science Department 3400 North Charles Street, 224 NEB Baltimore MD, 21218 US EMail: cliang4@cs.jhu.edu Eric Naber Johns Hopkins University - Applied Physics Laboratory 11100 Johns Hopkins Road Laurel MD, 20723 US EMail: eric.naber@jhuapl.edu Andreas Terzis Johns Hopkins University - Computer Science Department 3400 North Charles Street, 224 NEB Baltimore MD, 21218 US Phone: +1 410 516 5847 EMail: terzis@cs.jhu.edu Copyright Notice Copyright (C) The Internet Society (2006). 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. Benmohamed, et al. Expires December 21, 2006 [Page 7]