idnits 2.17.1 draft-liang-bgp-qos-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5 on line 346. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 19, 2006) is 6514 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 6 errors (**), 0 flaws (~~), 2 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group L. Benmohamed 2 INTERNET-DRAFT Johns Hopkins University 3 draft-liang-bgp-qos-00.txt C. Liang 4 Expires: December 21, 2006 Johns Hopkins University 5 E. Naber 6 Johns Hopkins University 7 A. Terzis 8 Johns Hopkins University 9 June 19, 2006 11 QoS Enhancements to BGP in Support of Multiple Classes of Service 13 Status of This Memo 15 By submitting this Internet-Draft, each author represents that any 16 applicable patent or other IPR claims of which he or she is aware 17 have been or will be disclosed, and any of which he or she becomes 18 aware will be disclosed, in accordance with Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/1id-abstracts.html 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html 36 Abstract 38 This document specifies the requirements posed on multi-domain 39 Quality of Service (QoS) routing protocols that provide multiple 40 classes of service with multi-dimensional QoS requirements. In 41 particular, it discusses enhancements to Border Gateway Protocol 42 version 4 (BGPv4) that allow nodes to discover multiple paths with 43 associated QoS attributes. In addition, this documents discusses the 44 details of several new algorithms, such as the dominant path 45 selection algorithm (DPSA). 47 1. Introduction 49 BGPv4 is the dominating inter-domain routing protocol in the 50 Internet. It was designed with minimal overhead traffic for 51 scalability, and it offers extensive policy support for business 52 needs. Information sharing among External Border Gateway Protocol 53 (eBGP) peers is limited. The only information passed from an AS to 54 its neighbors is the set of destination network prefixes reachable 55 from itself and the sequence of ASs to each destination network 56 prefix. 58 Many emerging needs in commercial and military networking have 59 exposed limitations of the current eBGP. These future IP networks 60 will support a very diverse mix of applications with very diverse QoS 61 requirements. In addition, some of these networks may consist of a 62 diverse set of component networks (wireless and wireline, fixed and 63 mobile with different degrees of mobility, long-term and short-term 64 ad-hoc), and these component networks may have dynamic service 65 capabilities. Therefore, different paths between the same endpoints 66 may have very different QoS characteristics, and these QoS 67 characteristics may be time-variant. Having the capability to 68 specify QoS requirements in routing, session admission, packet 69 scheduling, buffer management, service restoration priority, degree 70 of security protection, and similar other decisions will become an 71 important need in future IP networks. 73 This document specifies BGPv4 enhancements that allow multi-topology 74 (exposing multiple routes) and QoS-aware routing, using several QoS 75 metrics of importance to different applications. Unlike some other 76 similar work, our enhancements support multiple QoS metrics and do 77 not require any changes in the inter-domain routing architecture that 78 BGPv4 is based upon. Since the enhanced BGP does not limit routers 79 to advertise only one route for each destination prefix, we define 80 the notion of dominant paths to keep the amount of information 81 transfer to the minimum needed to be scalable. The enhanced BGP also 82 incorporates mechanisms, such as Multiprotocol Label Switching 83 (MPLS), and defines network-wide traffic classes to pin the route 84 taken by packets with the same QoS requirements. 86 2. BGPv4 Enhancements 88 There are five enhancements to BGPv4 that enable multi-paths and QoS- 89 aware routing: 91 (1) Exchanging potentially multiple paths per destination prefix. 93 (2) Maintaining multiple QoS metrics for each path. 95 (3) Pruning the set of known paths to a dominant set while 96 maintaining optimality. 98 (4) Choosing a particular path from this dominant set for the 99 unique QoS requirements of a traffic class. 101 (5) Enforcing the selected route. 103 BGPv4 restricts each router to advertise to its neighbors only one 104 route per destination prefix. This information hiding behavior can 105 prevent a router from learning the particular path that most 106 appropriately addresses the QoS requirements for a given traffic 107 class. Enhancement (1) removes this limitation, allowing each BGP 108 router to advertise a set of dominant paths. Enhancement (2) 109 associates a list of QoS metrics with each link, which are then used 110 to make route decision. Details on how path QoS metrics are embedded 111 in BGP_UPDATE messages and maintained will be discussed in more 112 detail in later sections. The notion of dominant paths is 113 enhancement (3), and it prevents each BGP router from advertising 114 every path it knows. Dominant paths are selected by dominant path 115 selection algorithm (DPSA), which is discussed in more detail in 116 later sections. Exchanging all of these additional paths and QoS 117 attributes is pointless unless the QoS-aware routing path decision is 118 actually enforced. Enhancement (5) can be implemented with various 119 mechanisms, which are discussed in our previous work [1]. We have 120 chosen to run MPLS on route assignment by enhancement (4) to pin the 121 path for each application's data flow. Class-assignment algorithm of 122 enhancement (4) will be discussed in more detail in later sections. 124 Incorporating these enhancements requires updating BGPv4 path 125 selection process accordingly. 127 - BGPv4 first manipulates path attributes, such as Local_Pref and 128 AS_Path, so that routes from one or some neighbors are enabled. 129 However, in order for QoS routing to be effective by being able to 130 choose among a larger set of routes, routes from all neighbors 131 should ideally be enabled. 133 - In BGPv4 path selection process, each border router (BR) that 134 terminates an enabled route selects itself among all enabled 135 routes as an AS egress point. Then, non-egress nodes selects one 136 of these egress points. Instead, under QoS routing, all enabled 137 routes to a destination D received at a BR (from both iBGP and 138 eBGP peers) undergo DPSA where a set of dominant paths is 139 selected. This set of dominant paths is maintained for routing 140 and advertisement. 142 2.1 Maintaining Path QoS Metrics 144 The BGPv4 UPDATE message includes the AS_PATH attribute, which stores 145 the sequence of ASs to reach the associated destination prefixes. In 146 order to retain the structure of the BGPv4 UPDATE message, path QoS 147 metrics are embedded in the AS_PATH attribute. This extension of the 148 AS_PATH attribute has been modeled after TLV (Type-Length-Value) 149 model. The TLV model provides a flexible architecture that will 150 support the specific metrics that we are currently interested in, and 151 it also provides support for any additional metrics in the future. 152 Figure 1 and 2 show the old format and the new format of AS-PATH 153 attribute: 155 ----------------------- 156 | Length of | Path to | 157 | Attribute | Prefix | 158 ----------------------- 159 Figure 1: BGPv4 AS_PATH attribute format 161 ------------------------------------------------------------------ 162 | Length of | # Metrics | Type | Length | Value | 163 | Attribute | = N | (Metric 1) | (Metric 1) | (Metric 1) | ... 164 ------------------------------------------------------------------ 166 ---------------------------------------------------- 167 | Type | Length | Value | Path to | 168 ... | (Metric N) | (Metric N) | (Metric N) | Prefix | 169 ---------------------------------------------------- 170 Figure 2: Extended AS_PATH attribute format 172 Each path QoS metric value is the accumulation of the QoS metric 173 value of all the links that the path consists of. Therefore, 174 maintaining path QoS metrics is a combined effort of each node along 175 that path. The general accumulation rules are: 177 - When advertising a path to another AS, the advertising node 178 combines its intra-AS metric values with the metric values 179 accumulated for the path thus far. 181 - When receiving a path from another AS, the receiving node 182 combines the metric values on the link that connects the receiving 183 node to the advertising node with the metric values accumulated 184 for the path thus far. 186 2.2 Dominant Path Select Algorithm (DPSA) 188 For QoS requirements with a single metric, such as bandwidth, it is 189 sufficient to know a path with the largest available bandwidth. If 190 the best path is not feasible, then no other paths are. However, for 191 QoS requirements with multiple metrics, such as bandwidth and delay, 192 there might not be a single best path. The notion of dominant path 193 is defined as a path where there is no other path with all QoS 194 metrics being better. If a path P dominates a set S of paths, then 195 paths in S do not need to be advertised as path P is the only one 196 needed to make QoS routing decisions. Indeed, if a connection 197 request cannot be supported by P then no path in S can satisfy the 198 request. 200 To illustrate DPSA, we will look at a small network topology with six 201 paths from the source to the destination node. In addition, this 202 network topology has two QoS metrics of interest: delay and 203 bandwidth. 205 ^ 206 | 207 BANDWIDTH 208 | 209 | P3 P4 210 | P2 P5 211 | P1 P6 212 | 213 -+---------------------------DELAY-> 214 | 215 Figure 3: Delay and bandwidth QoS characteristics of the six 216 paths 218 Figure 3 shows the delay and bandwidth QoS characteristics of the six 219 paths in the network. DPSA selects P1, P2, and P3 to be the dominant 220 paths because they are not covered by any other paths. P4, P5, and 221 P6 are covered by P3 because P3 is equal or better in all QoS 222 metrics. 224 For each destination prefix in the Loc-Routing Information Base (Loc- 225 RIB), we have to select a set of dominant paths for advertisement. 226 Therefore, DPSA should be logically placed between Loc-RIB and BGPv4 227 Output Policy Engine. If there are more than one potentially 228 dominant paths with all QoS metrics being equal, then the tie- 229 breaking strategies described below narrows down to only one path. 230 The first strategy is to prefer paths with the lowest AS hop counts, 231 and the second strategy is to prefer paths with the lowest next-hop 232 IP address. 234 2.3 Route Assignment For Each Traffic Class 236 There are various mechanisms that can be used to pin the selected 237 path for a particular application's data flow. We have chosen to 238 run MPLS on the notion of traffic classes. A set of network-wide 239 traffic classes are pre-defined on every node, and the task of class- 240 assignment algorithm is to assign at most dominant one path to each 241 traffic class under every destination prefix. For each traffic 242 class, the algorithm starts by selecting a set of paths that can 243 satisfy the QoS requirements of the traffic class. Then, from this 244 set of paths, the best path is assigned to the traffic class. For 245 QoS requirements with bandwidth and delay, the best path can be 246 defined as the path with the largest Euclidean distance from the 247 traffic class requirement. 249 For each destination prefix in the Loc-Routing Information Base (Loc- 250 RIB), we have to assign at most one dominant path to each traffic 251 class. Therefore, class-assignment assignment should be logically 252 placed between Loc-RIB and Forwarding Information Base (FIB). If 253 there are more than one suitable paths for a traffic class, then the 254 tie-breaking strategies described below narrows down to only one 255 path. The first strategy is to prefer paths with the lowest AS hop 256 counts, and the second strategy is to prefer paths with the lowest 257 next-hop IP address. 259 2.4 Forwarding Decision 261 Forwarding decision at data plane depends on two information: packet 262 destination address and packet traffic class. Both IPv4 Type of 263 Service (TOS) field and IPv6 Priority field can store the identifier 264 of the traffic class the packet belongs to. Longest-prefix-matching 265 algorithm is first performed on the packet destination address to 266 find the most specific destination address prefix in FIB. Since 267 there might be multiple routes under a given address prefix in FIB, 268 packet traffic class identifier is then used to match the route with 269 the same traffic class identifier. The packet is dropped either if 270 longest-prefix-matching algorithm does not return a destination 271 address prefix from FIB, or if there is no route matching packet 272 traffic class. 274 3. Relevant Results 276 Simulation results on the dynamic behavior and the scalability of 277 enhanced BGP are discussed in our previous work [2]. In addition, a 278 proof of DPSA convergence under the assumption of synchronous 279 operation is also presented in our previous work [2]. 281 4. Security Considerations 283 This document does not directly concern security. It is believed 284 that this extension inherits security issues in BGPv4. 286 5. IANA Considerations 288 This document has no actions for IANA. 290 6. Informative References 292 [1] L. Benmohamed, B. Doshi, T. DeSimone, R. Cole, "Inter-Domain 293 Routing with Multi-Dimensional QoS Requirements", IEEE Milcom 2005 295 [2] L. Benmohamed, C. Liang, E. Naber, A. Terzis, "QoS Enhancements 296 to BGP in Support of Multiple Classes of Service", June 2006 298 7. Authors' Addresses 300 Lotfi Benmohamed 301 Johns Hopkins University - Applied Physics Laboratory 302 11100 Johns Hopkins Road 303 Laurel MD, 20723 304 US 306 EMail: lotfi.benmohamed@jhuapl.edu 307 Chieh-Jan Mike Liang 308 Johns Hopkins University - Computer Science Department 309 3400 North Charles Street, 224 NEB 310 Baltimore MD, 21218 311 US 313 EMail: cliang4@cs.jhu.edu 315 Eric Naber 316 Johns Hopkins University - Applied Physics Laboratory 317 11100 Johns Hopkins Road 318 Laurel MD, 20723 319 US 321 EMail: eric.naber@jhuapl.edu 323 Andreas Terzis 324 Johns Hopkins University - Computer Science Department 325 3400 North Charles Street, 224 NEB 326 Baltimore MD, 21218 327 US 329 Phone: +1 410 516 5847 330 EMail: terzis@cs.jhu.edu 332 Copyright Notice 334 Copyright (C) The Internet Society (2006). 336 This document is subject to the rights, licenses and restrictions 337 contained in BCP 78, and except as set forth therein, the authors 338 retain all their rights. 340 This document and the information contained herein are provided on an 341 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 342 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 343 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 344 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 345 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 346 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.