idnits 2.17.1 draft-nair-qos-based-routing-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-24) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 11 longer pages, the longest (page 6) being 62 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 73 instances of lines with control characters in the document. ** The abstract seems to contain references ([15], [20], [2], [22-24], [21], [16], [3], [17], [4], [18], [5], [19], [6], [25], [7], [26], [8], [27], [9], [28], [23-25], [10], [12], [13], [14], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 69 looks like a reference -- Missing reference section? '2' on line 449 looks like a reference -- Missing reference section? '4' on line 107 looks like a reference -- Missing reference section? '5' on line 414 looks like a reference -- Missing reference section? '6' on line 642 looks like a reference -- Missing reference section? '7' on line 291 looks like a reference -- Missing reference section? '8' on line 312 looks like a reference -- Missing reference section? '9' on line 648 looks like a reference -- Missing reference section? '10' on line 360 looks like a reference -- Missing reference section? '20' on line 606 looks like a reference -- Missing reference section? '23-25' on line 448 looks like a reference -- Missing reference section? '12' on line 618 looks like a reference -- Missing reference section? '13' on line 499 looks like a reference -- Missing reference section? '3' on line 560 looks like a reference -- Missing reference section? '14' on line 579 looks like a reference -- Missing reference section? '15' on line 585 looks like a reference -- Missing reference section? '16' on line 588 looks like a reference -- Missing reference section? '17' on line 592 looks like a reference -- Missing reference section? '18' on line 599 looks like a reference -- Missing reference section? '19' on line 602 looks like a reference -- Missing reference section? '21' on line 606 looks like a reference -- Missing reference section? '22-24' on line 612 looks like a reference -- Missing reference section? '25' on line 632 looks like a reference -- Missing reference section? '26' on line 634 looks like a reference -- Missing reference section? '27' on line 637 looks like a reference -- Missing reference section? '28' on line 645 looks like a reference Summary: 11 errors (**), 0 flaws (~~), 2 warnings (==), 28 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Bala Rajagopalan 2 draft-nair-qos-based-routing-00.txt Bellcore 3 Raj Nair 4 Ascom Nexen 5 June, 11, 1996 7 Quality of Sevice (QoS)-Based Routing in the Internet - Some Issues 9 Status of this Memo 11 This document is an Internet Draft. Internet Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its Areas, 13 and its Working Groups. Note that other groups may also distribute 14 working documents as Internet Drafts. 16 Internet Drafts are draft documents valid for a maximum of six 17 months. Internet Drafts may be updated, replaced, or obsoleted by 18 other documents at any time. It is not appropriate to use Internet 19 Drafts as reference material or to cite them other than as a "working 20 draft" or "work in progress." 22 To learn the current status of any Internet Draft, please check the 23 1id-abstracts.txt listing contained in the Internet Drafts Shadow 24 Directories on ds.internic.net, nic.nordu.net, ftp.nisc.sri.com or 25 munnari.oz.au. 27 Distribution of this memo is unlimited. 29 This Internet Draft expires December, 16, 1996. 31 Abstract 33 There are many reasons to consider QoS-based routing as a component of 34 the integrated services Internet. But several questions arise with 35 regard to its development: what are the requirements on QoS-based 36 routing in the Internet? What sort of a routing architecture is 37 practical? What are the technical and policy issues that arise in 38 realizing a QoS-based Internet routing architecture? This draft is an 39 attempt to generate some discussion on these topics. To this end we 40 present some potential requirements on path computation, efficiency, 41 robustness and scalability, and describe some issues in realizing a 42 QoS-based routing architecture. Our conclusions are that QoS-based 43 routing is a challenging problem, and that it may be best to address 44 the intradomain, interdomain and scalability aspects separately in 45 developing the routing architecture. 47 1. INTRODUCTION 49 The internet is being used increasingly for transport of multimedia 50 information such as image, voice and video. With the increase in 51 sophistication of desktop computers, and the availability of networked 52 multimedia applications, the Internet is likely to see more of this 53 type of traffic. This type of usage, however, is ad-hoc in that the IP 54 network architecture has been designed for "best-effort" delivery, 55 without any guarantees on throughput or delay. It has been recoginzed 56 that to adequately support realtime traffic flows with bandwidth and 57 delay requirements, the following features should be present in the 58 Internet [1]: 60 - new service classes beyond best-effort to provide certain guarantees 61 on throughput and delay to applications; 63 - a mechanism that allows applications to signal to the network their 64 quality of service (QoS) requirements; and 66 - traffic management mechanisms in hosts and routers 68 The IETF has been working on the first two issues: defining service 69 classes in addition to best-effort [1], and a resource reservation 70 protocol (RSVP) [2] that applications may use to reserve network 71 resources to get the level of service they desire. Traffic management 72 features are also being built by router vendors. An issue being 73 discussed now is whether a routing architecture that allows the dynamic 74 discovery of QoS-accommodating paths in the network for data flows, in 75 the presence of changes in network topology and loading, is required. 76 In our opinion, without QoS-based routing, the definition of new 77 service classes and signalling protocols may only be of limited use in 78 supporting real-time applications. 80 Our assumption is that it is not economical to overprovision network 81 resources in order to obviate the need for QoS mechanisms. Under these 82 circumstances, there is a justifiable need for QoS-based routing. 83 First, without it, protocols like RSVP may convey the QOS requirements 84 of a flow to routers, but there is no guarantee that an existing 85 acceptable path between the sender and the receiver(s) will be found 86 and utilized. An alternative, suggested often, is to let routers keep 87 track of multiple paths and attempt flow setup by trial and error along 88 these paths. This technique does not scale well with network diameter, 89 and the blocking probability and setup time may be high. 91 Second, economic network engineering depends on the use of an 92 efficient routing scheme. For instance, with a traditional IP routing 93 algorithm, a single fixed path is selected for all traffic between a 94 pair of nodes. To assure the desired QoS, this path must be engineered 95 to accommodate the peak traffic demand between the node pair. This 96 results in the inefficient use of resources, since there may be other 97 underutilized paths between the same node pair. On the other hand, a 98 QoS-based routing algorithm would allow the network capacity to be 99 engineered efficiently by virtue of its ability to take into account 100 the current network state in making routing decisions. 102 Finally, a network state-dependent routing scheme can compensate for 103 imprecise network engineering. Specifically, when the traffic load 104 exceeds the engineered limits due to exceptional circumstances (e.g., 105 focussed overload after failures), a QoS-based routing scheme allows 106 more traffic to be routed and a more graceful performance degradation 107 as compared to a state-insensitive routing scheme [4]. Indeed, these 108 are the reasons for the development of state-dependent routing schemes 109 for long distance phone networks [5] and ATM networks [6]. QoS-based 110 routing must therefore be considered an essential component of the 111 overall scheme to provide QoS guarantees to applications in the 112 Internet. 114 Given the need for QoS-based routing, the following questions arise: 115 what are the requirements on QoS-based routing in the Internet? What 116 sort of a routing architecture is practical? What are the technical and 117 policy issues that arise in realizing a QoS-based Internet routing 118 architecture? This draft is an attempt to generate some discussion on 119 these topics. To this end, in the next section, we point out some 120 potential requirements. In Sections 3 and 4, we describe some issues 121 that arise in developing a QoS-based routing architecture satisfing 122 these requirements. Related work is outlined in Section 5, and summary 123 and conclusions are presented in Section 6. 125 2. SOME REQUIREMENTS ON QOS-BASED IP ROUTING 127 The foremost issue in developing a QoS-based IP routing architecture 128 is the definition of the requirements it must satisfy. Given the 129 organization of the internet, the nature of the traffic, the service 130 classes being considered, and the requirements of the users, there 131 could be many requirements on QoS-based routing. To make a start, we 132 may consider the following preliminary requirements: 134 Metrics and Paths 135 ----------------- 137 - Support for multiple path metrics (bandwidth, delay, etc.). The 138 definition of the metrics would be based on the service classes defined 139 by the intserv WG. 141 - The ability to dynamically determine paths satisfying multiple 142 constraints (e.g., bandwidth and delay). 144 - QoS support for multiple types of flows, i.e., unicast and 145 many-to-many multicast. 147 Robustness 148 ---------- 150 - The ability to detect and respond to dynamically changing QoS 151 capabilities of a link. 153 - The ability to continue routing in the presence of multiple, 154 simultaneous failures in the network. 156 Efficiency 157 ---------- 159 - The ability to route short-lived data flows with minimal overhead. 161 - The ability to utilize network resources efficiently, through load 162 spreading, global admission control techniques and the like. 164 - Minimization of routing overheads. 166 - Support for resource control, i.e., the ability to limit resource 167 consumption by different classes of traffic. 169 Scalability and Priority 170 ------------------------ 172 - The ability to scale to large numbers of nodes and links, and to a 173 large network diameter. 175 - Support for prioritizing flows, and to permit high priority flows to 176 be established with precedence over lower priority flows. 178 Interdomain and Policy 179 ---------------------- 181 An area that requires some thought is the requirements for 182 interdomain routing. Specifically, the nature of the information that 183 is exchaged at the border of two domains must be determined. If the 184 information exchange is compact, the interdomain routing scheme can be 185 relatively simple (Section 3.8). In any case, the ability to introduce 186 policy constraints on routing information flow at the boundary between 187 two organizations is required. 189 Other 190 ----- 192 Other requirements, such as mobility support, may be defined. 194 These are complex requirements, and a number of challenging problems 195 must be solved to satisfy them. The resulting routing scheme can be 196 expected to be more sophisticated than the existing internet routing 197 schemes. It is, however, encouraging that recent Internet routing work, 198 such as Nimrod and Source Demand Routing, has addressed scalability, 199 on-demand route computation and source routing issues. The ATM Forum 200 PNNI work illustrates an effort to develop a scalable, QoS-based 201 routing architecture. To what extent the ideas developed under these 202 efforts may be incorported in the QoS-based routing architecture for 203 the Internet is a subject that requires much discussion. This draft 204 does not address that question. Instead, our objective is to describe 205 some of the problems that arise in realizing a QoS-based Internet 206 routing architecture. 208 To this end, we first consider intradomain routing, without 209 scalability requirements. As a reference routing architecture for this 210 case, link state routing with distributed intelligence seems to be a 211 reasonable choice. To build QoS-based routing features in this 212 architecture, algorithm design issues, for instance, computing "low 213 cost" multicast distribution trees for flows, or efficient broadcast 214 schemes for propagating QoS information must be addressed. Other 215 problems that involve policy and scalability issues in the global, 216 multiply administered internet may be addressed separately, once the 217 requirements are determined. This approach allows us to focus on two 218 distinct classes of problems that arise in realizing the QoS-based 219 routing architecture for the Internet. 221 Following the requirements above, the intradomain link state 222 architecture should allow a router determine a feasible path for a 223 given unicast flow on demand. For multicast flows with dynamic receiver 224 sets, QoS-based routing should allow the dynamic, incremental 225 computation of QoS-accommodating multicast trees. Under link state 226 routing, each router in an autonomous system (AS) monitors the QoS 227 available on each directly attached link, and its own resource 228 availability. This information is broadcast to other routers in the 229 AS on a periodic and/or event-driven basis. Based on the view of the 230 network state, a router may determine the path for a given flow. Source 231 routing, along with local and global admission control techniques may 232 be used to accept or reject a flow along the path. Also, routers may 233 recognize the priorities of flows (perhaps signalled via RSVP) and 234 implement a mechanism to ensure a high rate of success for guaranteeing 235 QoS for high priority flows. 237 The issues that arise in intradomain QoS-based routing may be broadly 238 classified as follows: 240 - How do routers determine the QoS capability of each outgoing link 241 and reserve link resources? Note that some of these links may be 242 virtual, over ATM networks. 244 - How do routers propagate the QoS knowledge to remote routers to aid 245 in path selection? 247 - How are QoS-accommodating paths computed by routers for unicast 248 flows? 250 - How are QoS-accommodating paths computed for multicast flows? 252 - What is the mechanism for prioritizing flows? 254 - What is the mechanism for resource control? 256 - What are the performance impacts of dealing with many short-lived 257 flows (e.g., web page accesses)? 259 - How does the RSVP model fit with the QoS-based routing architecture? 261 Each of these points is discussed in the next section. Scalability and 262 interdomain routing issues are described briefly in Section 4. 264 3. INTRADOMAIN ROUTING ISSUES 266 3.1 QoS Determination and Resource Reservation 268 The integrated services working group of the IETF has concentrated on 269 local resource management within routers. In particular, the notion of 270 "admission control" has been introduced that allows a router to make a 271 decision as to whether a given flow may be accepted or rejected based 272 on local resource availability. The admission control process 273 requires knowledge of the QoS available on all links attached to a 274 router. It is still an open issue, however, as to how the QoS values 275 are computed for various link types such as multiple access links. The 276 resolution of this issue is in the domain of the ISSLL working group. 278 The intricacies of this problem may be appreciated when the case of a 279 router connected to a large non-broadcast multiple access network, such 280 as ATM, is considered. In this case, a router may have multiple next 281 hop choices, with corresponding paths across the ATM network, each with 282 possibly different QoS availability. The issues are, how does a router 283 determine what the routing options are across an ATM network, what the 284 QoS availability over each available route is, and what QoS value to 285 advertise for the ATM link when QoS-based routing is implemented in the 286 wider internet. To put this problem in perspective, the currently 287 defined standards for IP routing over ATM, such as NHRP, allow the 288 selection of a single exit point in the ATM network for an IP datagram. 289 With QoS requirements on IP flows, there may not be an ATM path which 290 accommodates the given QoS from the entry router to the exit router 291 returned by NHRP. An approach like IPNNI [7] would be helpful here, 292 although with some complexity. A related problem is the reservation 293 of resources over a broadcast network, say an ethernet. Because access 294 to the network is distributed, some coordination is required among 295 routers in reserving resources. 297 3.2 Knowledge Propagation 299 The link state architecture requires routers to broadcast the local 300 resource status (such as available link capacity, delay measurements, 301 etc.) and the local topology information to all other routers in the 302 AS. The broadcast of status information from one router to others might 303 be an expensive process in terms of communication and processing 304 overheads. So far, intradomain routing has been based on fixed link 305 metrics (i.e., minimum hop, or shortest-path based on static metrics). 306 In this environment, efficiency of information propagation has not been 307 an issue. Thus, routing algorithms such as OSPF have used flooding with 308 periodic refreshing as a means to propagate updates. Given that 309 linkstate routing is essential for efficient QoS-based routing, 310 flooding-type mechanisms are not suitable for information broadcasting. 311 Alternative techniques to reduce broadcast overheads, such as 312 tree-based forwarding, have been proposed [8]. These have to be 313 implemented. In addition, link status information such as utilization 314 can be volatile, i.e., their values can change significantly in a short 315 period of time with the admittance of real-time flows. How should such 316 information be quantized in order to reduce the update generation rate 317 is an issue to be resolved. Clearly, the less accurate the information, 318 the less likely that a feasible path will be found by a source router. 319 On the other hand, the overheads of keeping very accurate information 320 at each router may be high. Aggregation of status information reduces 321 the frequency of update generation, but how it affects routing 322 algorithm performance has to be determined. 324 3.3 Unicast Path Computation Algorithms 326 Given the availability of network state information at each router, 327 how should paths be computed for unicast flows? The computation of a 328 "feasible" path for a given flow is not difficult: a router just 329 eliminates all infeasible links and nodes, i.e., those that cannot 330 support the requested QoS, from its local representation of the network 331 topology and finds an end-to-end path in the remaining topology. But as 332 studies in circuit-switched networks have shown that even in limited 333 topologies this sort of "feasible-path routing" is unacceptable, i.e., 334 it results in the admission of lesser number of flows into the network 335 than what is possible otherwise. Moreover, as noted above, aggregation 336 of link status information is usually lossy. This aggrevates the 337 problem of flow blocking. 339 Feasible-path routing corresponds to the notion of local admission 340 control defined by the IETF's integrated services group; a flow is 341 routed over a path as long as it passes the admission control criterion 342 of each router along the path. While this type of admission control 343 is required to control the subscription of resources at a router, it 344 does not take into account any global view of resource consumption by 345 individual flows. Efficiency in routing is achieved only when an 346 additional layer of admission control is implemented. This higher level 347 admission control procedure would consider the resource requirement 348 of each flow in relation to the available resources along a path in 349 order to determine whether it is profitable overall to admit the flow 350 [9]. Thus, an individual flow may be rejected even if there are 351 feasible paths to route it, if it is found that admitting the flow 352 would result in an overall decline in the number of flows carried by 353 the network. The formulation of this higher level admission control, 354 with fairness to all flows desiring entry to the network, is an area 355 that requires work. 357 Path computation with multiple QoS constraints on a flow is a 358 difficult problem. Indeed, for some combinations of QoS constraints, 359 the problem is NP-complete. However, algorithms have been proposed for 360 computing paths with combined bandwidth and delay constraints [10], and 361 such algorithms can be incorporated in the routing scheme. 363 3.4 Flow Prioritization 365 Given that critical flows must be accorded higher priority than other 366 types of flows, a mechanism must be implemented in the network to 367 recognize flow priorities. It is assumed that RSVP can be used to 368 signal the priority of a flow. There are then two aspects to 369 prioritizing flows. First, there must be a policy to decide how 370 different users are allowed to set priorities for flows they 371 originate. The network must be able to verify that a given flow is 372 allowed to claim a priority level signalled for it. Second, the routing 373 scheme must ensure that a path with the requested QoS will be found for 374 a flow with a probability that increases with the priority of the flow. 375 In other words, for a given network load, a high priority flow should 376 be more likely to get a certain QoS from the network than a lower 377 priority flow requesting the same QoS. 379 The policy and verification aspects are outside the scope of this 380 draft. The routing mechanism for implementing flow priorities may be 381 based on preemption combined with dynamic rerouting of lower priority 382 flows. For example, assuming a small, fixed number of priority levels 383 (e.g., 16), each router may broadcast the resources locally allocated 384 to flows of each priority level. A router, when computing a path, 385 first attempts to find a path that has the necessary unallocated 386 resources to support the QoS requirements of the flow. If such a path 387 cannot be found, the router attempts to finds a path where adequate 388 resources may be freed by displacing lower priority flows. In the end, 389 a high priority flow may be routed by preempting resources allocated to 390 lower priority flows. Routers may attempt to dynamically reroute 391 preempted flows using the same procedure. 393 Routing procedures for flow prioritization may thus be complex. 394 Identification and evaluation of different procedures are areas that 395 require investigation. 397 3.5 Resource Control 399 Given the existence of multiple service classes, it is necessary to 400 engineer a network to carry the forecasted traffic demands of each 401 class. To do this, a network administrator may logically partition 402 router and link resources among various service classes. Strict 403 partitioning, however, may result in inefficient use of network 404 resources, since there may be periods of time during which there may be 405 excessive traffic load under one class and light load under another. It 406 is thus desirable to allow unused resources to be allotted traffic that 407 needs them. This type of sharing, however, must be done in a controlled 408 fashion in order to prevent traffic under some service class from 409 taking up more resources than what was engineered for it for prolonged 410 periods of time. This is the job of the routing scheme. This may be 411 done via preemption, in a manner not contradictory to the priority 412 assignment of active traffic flows. Non-preemptive dynamic resource 413 sharing techniques are possible, as illustrated by the Real Time 414 Network Routing architecture of the AT&T phone network [5]. The 415 design of an appropriate resource sharing scheme, and its incorporation 416 into the QoS-based routing scheme is a challenging issue. In 417 particular, the overheads incurred by the routing scheme in the 418 implementation of logical resource partitioning and dynamic sharing is 419 an issue that must be studied carefully. 421 3.6 Short-Lived Flows 423 The QoS-based routing model incurs certain overheads during flow 424 establishment, for example, computing a source route. Whether this 425 overhead is disproportionate compared to the length of the sessions is 426 an issue. In general, this problem arises in virtual circuit networks 427 such as ATM, where many short-lived SVCs result in increased call 428 set-up overheads.Even without QoS-based routing, RSVP flow 429 establishment overheads are incurred for each session. An area worth 430 investigation is the minimization of routing-related overheads during 431 flow establishment. One approach that is useful is cacheing recently 432 computed routes, so that new sessions to the same destination do not 433 cause recomputation of paths. The issue of efficient flow set-up in 434 general needs investigation. 436 3.7 QoS-Based Routing for Multicast Flows 438 Computing QoS accommodating paths for multicast flows is a tricky 439 problem, especially if the notion of higher level admission control 440 (Section 3.3) is included. The dynamism in the receiver set allowed by 441 IP multicast also adds to the problem. In any case, routers in an AS 442 must keep track of the id of subnets where group members are present, 443 along with the QoS requested by them, in order to compute the 444 appropriate multicast trees. This corresponds to an enhanced MOSPF-type 445 algorithm [20]. As receivers leave or join a multicast group, existing 446 trees from different sources may have to be incrementally modified. 447 Many such heuristic incremental algorithms are presently known 448 [23-25]. Computing optimal shared trees based on the shared reservation 449 style [2] may require new algorithms. Finally, scalability is an issue 450 with algorithms that require knowledge of receiver sets. 452 3.8 RSVP and QoS-Based Routing 454 The QoS-based routing model has some implications on signalling. 455 Specifically, under this routing model, the QoS desired for a flow must 456 be specified before a path can be computed. In contrast, under RSVP, a 457 path must exist before a reservation can be made. RSVP utilizes PATH 458 messages to notify the receivers of a session and the traffic 459 characteristics at the sender, and to establish the flow's path state 460 in the routers. With QoS-based routing, the latter function is not 461 useful since the flow path is computed based only on the receivers' 462 reservation. Using the current RSVP model with QoS-based routing, a 463 unicast flow establishment would require a PATH message sent from the 464 source to the receiver along a best effort path, say, and a RESERVE 465 message sent over a QoS-accommodating flow computed by a router close 466 to the receiver. 468 With regard to multicast flows, the path for a multicast flow under 469 the current RSVP specifications is the IP multicast tree of the source. 470 To receive a flow, a host must first join the multicast group, and 471 hence the multicast tree for a given source. To request a certain QoS 472 for the flow, each receiver must send a RESERVE message towards the 473 root of the tree, reserving link and router resources enroute. The 474 set of receivers of a multicast flow is dynamic, and transparent to 475 the source of the flow. The multicast routing protocol dynamically 476 maintains a tree per source, in which the leaves are the current set of 477 receivers. This protocol establishes the multicast tree independently 478 of the QoS requirements of flows subsequently routed over it. Thus, 479 there is no guarantee that a leaf would be successful in reserving 480 the resources to get the desired QoS. 482 One solution for QoS-based multicast routing is to separate RSVP PATH 483 message flow and actual data flow from a source. Thus, a basic 484 multicast routing protocol would provide a tree for delivering PATH 485 messages to any receiver joining the group. The reception of a RESERVE 486 message by a router would trigger an algorithm to (incrementally) 487 compute a new tree for the data flow, i.e., addition/deletion of 488 branches to the existing tree, as discussed in the previous section. 490 4. SCALING AND INTERDOMAIN ROUTING 492 4.1 Scaling by Hierarchical Aggregation 494 A scalable intradomain routing architecture is needed to handle the 495 thousands of nodes that may exist within an AS. Scaling by hierarchical 496 aggregation is a common techique, as exemplified by the ATM Forum PNNI 497 routing scheme [12]. Hierarchical aggregation, however, introduces 498 problems with regard to the accuracy of the aggregated state 499 information [13]. Also, the aggregation of paths under multiple 500 constraints is difficult. One of the difficulties is the risk of 501 accepting a flow based on inaccurate information, but not being able to 502 support the QoS requirements of flow because the capabilities of the 503 actual paths that are aggregated are not known at the source. Much 504 study is needed to understand and characterize the performance impacts 505 of aggregating path metric information. Meanwhile, a way to compensate 506 for inaccuracies is to use crankback, i.e., dynamic search for 507 alternate paths as a flow is being routed. Crankback, however, 508 increases the time to set up a flow, and also results in overall poor 509 utilization of resources. Thus, crankback is the mechanism of last 510 resort, and the minimization of its use is a problem that requires 511 work. 513 4.2 Interdomain Routing 515 Many issues arise when multiple ASs, each implementing QoS-based 516 routing within their networks, interface. Efficient end-to-end 517 QoS-based routing across multiple ASs require some exchange of 518 information between them, but individual ASs may not wish to reveal 519 too much information. For instance, it may not be possible or 520 desirable for an AS to reveal internal topology information to others. 521 Also, even if there are no policy constraints on exporting information, 522 overall scalability of the internet routing architecture may not allow 523 this. Thus, the issue is what (minimal) information should be exchanged 524 between different autonomous systems to implement end-to-end QoS-based 525 routing? 527 It is desirable that information flow across ASs should be much more 528 abridged than what flows inside an AS. For example, fairly stable QoS 529 information applicable to the entire network may be advertised. This 530 means that an AS should engineer its network carefully to ensure that 531 it can meet the QoS advertised. Compact information flow may allow the 532 implementation of QoS-based routing through enhanced versions of 533 traditional interdomain protocols such as BGP. 535 The precise definition of an interdomain routing architecture, which 536 accommodates QoS and also aids in establishing routing policies is an 537 area that requires work. The scalability of any proposed architecture 538 must be evaluated, along with its efficiency in large configurations. 539 Finally, interdomain QoS-based multicast routing is a challenging 540 problem. 542 5. PROGNOSIS AND RELATED WORK 544 QoS-based routing in the Internet is indeed a daunting problem. To 545 make some progress in this area, it may be necessary to make a modest 546 beginning and concentrate on a intradomain routing protocol, say, a 547 QoS-enhanced version of OSPF. Scalability via hierarhical aggregation, 548 in our opininon, is problem that can be separately tackled. Similarly, 549 interdomain routing is also an orthogonal issue. At the intradomain 550 level, the development of a routing scheme incorporating some of the 551 basic requirements outlined in this draft is achievable. Indeed, 552 commercially available proprietary routing solutions for frame relay 553 and ATM networks from vendors such as Cascade, FORE, Stratacom and 554 others demonstrate many of the desirable QoS-based routing features. 555 The following is a summary of related work in various areas, and the 556 missing pieces. 558 5.1 IP Routing Schemes 560 Among intradomain routing schemes, OSPF [3] is a link state routing 561 protocol, utilizing distributed state information. Under OSPF, 562 network topology, as well as an administratively configurable metric 563 for each link are propagated throughout the network using flooding. 564 Each node has its own view of the network state, and a shortest path 565 algorithm is used to compute the destination-based routing table. OSPF 566 allows the definition of a two-level routing hierarchy, and hence a 567 good degree of scaling. As compared to OSPF, a link state QoS-based 568 routing requires the dynamic distribution of link and nodal state 569 information, as the corresponding resource availability changes. For 570 scaling purposes, this would require a tree-based update propagation 571 scheme instead of flooding. Also, instead of destination-based 572 routing tables, a QoS-based routing scheme would use on-demand path 573 computation during flow establishment. This places an overhead on 574 routers, and efficient schemes have to be designed to minimize this 575 overhead. Finally, source routing, at least for flow establishment, has 576 to be used instead of destination oriented next hop forwarding. Some 577 state information will also be maintained by routers about each flow. 579 Interdomain routing protocols, such as BGP [14], primarily focus on 580 the control of information flow between administratively distinct 581 routing domains. As such, they do not maintain fine state information 582 about routing domains. Rather, topological reachability of domains, 583 subject to user-defined preferences for alternate route selection, is 584 the goal. Thus, BGP uses an enhanced distance-vector routing scheme 585 (called, path vector [15]), with destination-oriented hop by hop 586 forwarding. QoS-enhanced BGP requires work. 588 Among the newer approaches, Source Demand Routing (SDR) [16] allows 589 on-demand path computation by routers and the implementation of 590 strict and loose source source routing. The SDR approach can be used 591 for both intradomain and interdomain source routing. The Nimrod 592 architecture [17] has a number of concepts built in to handle 593 scalability and specialized path computation. These are applicable in 594 addressing the relevant aspects of QoS-based routing. 596 5.2 Internet Multicasting 598 IP multicasting is mainly concerned with establishing multicast trees 599 subject to changes in topology and receiver group membership [18]. IP 600 multicast schemes utilize the underlying unicast routing protocols to 601 establish the multicast trees. For example, the Multicast OSPF (MOSPF) 602 [19] works with OSPF. As with QoS-enhanced OSPF, it is possible to 603 consider a QoS-accommodating MOSPF. 605 More recent multicast routing protocols, such as Core-Based Trees 606 [20], and Protocol-Independent Multicast [21] do not rely on specific 607 types of unicast routing schemes. They may need extensive revision to 608 accommodate QoS. The MOSPF mode of operation is in fact more suitable 609 for QoS-based multicast routing, since it is possible to tap the 610 networkwide QoS status from the underlying link state routing scheme. 611 Given the availability of QoS information, many heuristic algorithms to 612 compute multicast trees are known [22-24]. The incorporation of flow 613 aggregation and the sharing of multicast trees by several sources, as 614 defined under RS-VP, into these algorithms requires work. 616 5.3 ATM Routing 618 The ATM PNNI routing scheme [12] is a hierarchical link state 619 QoS-based routing scheme. It incorporates mechanisms for QoS-based path 620 computation and scalability, but it does not address some of the 621 problems outlined earlier: routing of many-to-many multicast flows of 622 the type required by RSVP; interdomain policy routing issues; QoS 623 measurements on shared links; global admission control; flow 624 prioritization; efficient broadcast of state information; and 625 performance issues. 627 There has recently been some work on SVC routing schemes for ATM 628 networks. This research illustrates various approaches to achieving 629 higher throughput from routing schemes, as compared to single path 630 shortest-path routing. The flows considered usually have a single QoS 631 requirement, i.e., bandwidth. The following is a sampling of work in 632 this area. In [25], Sibal and Desimone describe a routing strategy for 633 multihop networks, modelled after the reservation-based alternate 634 routing strategy for two-hop phone networks [26]. This generalized 635 algorithm is based on distance vector routing, and allows only a 636 single bandwidth value for all flows. It also assumes that the input 637 traffic distribution is known apriori. In [27], Bahk and Zarki analyze 638 the throughput performance of several heuristic algorithms for 639 QoS-based routing. These algorithms are simple variants of 640 shortest-path, and some of them require coarse link state information. 641 Mitra, Morrison and Ramakrishnan present a scheme for optimal network 642 design [6] that assumes centralized routing and a small number of 643 bandwidth classes. Also, input traffic is assumed to have certain 644 characteristics. Gawlick, Kalmanek and Ramakrishnan present an 645 on-demand routing scheme for PVCs [28] and show its superiority over 646 shortestpath. This algorithm too is centralized. Finally, Ahmadi, Chen 647 and Guerin present a routing and admission control heuristic algorithm, 648 again with better performance than shortest-path [9]. 650 The contributions of prior research in this area is of significant 651 importance, lending some insights into unicast path computation 652 procedures. The practical aspects of routing, such as overhead 653 reduction, and efficiency under a mix of traffic and information 654 aggregation, scalability, etc., have not been investigated thoroughly. 655 The definition of a practical IP QoS-based routing architecture, and 656 its implementation, requires new work as outlined in this draft. 658 6. SUMMARY AND CONCLUSIONS 660 There are many reasons to consider QoS-based routing as an essential 661 component of the overall integrated services Internet infrastructure. 662 The first step in developing a QoS-based routing architecture is the 663 specification of its requirements. In particular, the requirements for 664 interdomain routing need much discussion. In this draft, we presented 665 some potential requirements on path computation, efficiency, robustness 666 and scalability, and described some issues in realizing a QoS-based 667 routing architecture. Given that QoS-based routing is a challenging 668 problem, it may be best to consider the intradomain, interdomain and 669 scalability aspects separately. 671 REFERENCES 673 1. R. Braden, D. Clark, and S. Shenker, "Integrated Services in the 674 Internet Architecture: An Overview," RFC 1633, July, 1994. 676 2. L. Zhang, S. E. Deering, D. Estrin, S. Shenker and D. Zappala, 677 "RSVP: A New Resource Reservation Protocol," Technical Report 95-607, 678 ISI, University of Southern California, 1995. 680 3. J. Moy, "OSPF Version 2," RFC 1583, March, 1994. 682 4. J. M. Akinpelu, "The Overload Performance of Engineered Networks 683 with Non-Hierarchical Routing," AT&T Technical Journal, Vol. 63, pp. 684 1261-1281, 1984. 686 5. G. R. Ash, J. S. Chen, A. E. Frey and B. D. Huang, "RealTime 687 Network Routing in a Dynamic Class-of-Service Network," Proceedings of 688 ITC 13, 1992. 690 6. D. Mitra, J. Morrison, and K. G. Ramakrishnan, "ATM Network Design 691 and Optimization: A Multirate Loss Network Framework," Proceedings of 692 IEEE INFOCOM `96, 1996. 694 7. R.Callon et al, "Issues and Approaches for Integrated PNNI" ATM 695 Forum 96-0355, April 1996. 697 8. B. Rajagopalan, "Efficient Link State Routing," Unpublished Report, 698 available from the author, braja@bellcore.com. 700 9. H. Ahmadi, J. Chen, and R. Guerin, "Dynamic Routing and Call 701 Control in High-Speed Integrated Networks," Proceedings of ITC-13, pp. 702 397-403, 1992. 704 10. Z. Wang and J. Crowcroft, "QoS Routing for Supporting Resource 705 Reservation," available at http:// 706 boom.cs.ucl.ac.uk/staff/zwang/pub.htm. 708 11. R. G. Moskowitz, "Why in the World is the Web So Slow?," Network 709 Computing, March, 15, 1996. 711 12. ATM Forum PNNI subworking group, "Private Network - Network 712 Specification Interface v1.0 (PNNI 1.0)", afpnni-0055.00, March 1996. 714 13. W. C. Lee, "Topology Aggregation for Hierarchical Routing in ATM 715 Networks," ACM SIGCOMM Computer Communication Review, 1995. 717 14. Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)," 718 Internet Draft, September, 1992. 720 15. B. Rajagopalan and M. Faiman, "A Responsive Distributed Algorithm 721 for Shortest-Path Routing within Autonomous Systems," Journal of 722 Internetworking Research, pp. 51-69, March, 1991. 724 16. D. Estrin, T. Li, Y. Rekhter, K. Varadhan, and D. Zappala, "Source 725 Demand Routing: Packet Format and Forwarding Specification (Version 726 1)," RFC 1940, May, 1996. 728 17. I. Castineyra, J. N. Chiappa, and M. Steenstrup, "The Nimrod 729 Routing Architecture," Internet Draft, 730 draft-ietfnimrod-routing-arch-01.txt, Febrauary, 1996. 732 18. S. E. Deering and D. P. Cheriton, "Multicast Routing in Datagram 733 Internetworks and Extended LANs," ACM Transactions on Computer Systems, 734 pp. 85-110, May, 1990. 736 19. J. Moy, "MOSPF: Analysis and Experience," RFC 1585, March, 1994. 738 20. A. Ballardie, J. Crowcroft and P. Francis, "Core-Based Trees: A 739 Scalable Multicast Routing Protocol," Proceedings of SIGCOMM `94. 741 21. S. E. Deering, D. Estrin, D. Farinnacci, V. Jacobson, C-G. Liu, 742 and L. Wei, "An Architecture for Wide-Area Multicast Routing," 743 Technical Report, 94-565, ISI, University of Southern California, 1994. 745 22. B. M. Waxman, "Routing of Multipoint Connections," IEEE JSAC, pp. 746 1617-1622, December, 1988. 748 23. X. Jiang, "Path Finding Algorithms for Broadband Multicast," in 749 High Speed Networking, III, Elsevier Science Publishers, 1991. 751 24. C-H. Chow, "On Multicast Path Finding Algorithms," Proceedings of 752 the IEEE INFOCOM `91, pp. 1274-1283, 1991. 754 25. S. Sibal and A. Desimone, "Controlling Alternate Routing in 755 General-Mesh Packet Flow Networks," Proceedings of ACM SIGCOMM `95, 756 1995. 758 26. D. Mitra and J. B. Seery, "Comparative Evaluations of Randomized 759 and Dynamic Routing Strategies for CircuitSwitched Networks," IEEE 760 Trans. on Communications, pp. 102-116, January, 1991. 762 27. S. Bahk and M. El Zarki, "Dynamic Multi-Path Routing and How it 763 Compares with Other Dynamic Routing Algorithms for High Speed Wide Area 764 Networks," Proceedings of SIGCOMM `92, pp. 53-64, 1992. 766 28. R. Gawlick, C. R. Kalmanek, and K. G. Ramakrishnan, "On-Line 767 Routing of Permanent Virtual Circuits," Computer Communications, March, 768 1996. 770 AUTHORS' ADDRESSES 772 Bala Rajagopalan Raj Nair 773 Bellcore Ascom Nexen 774 445 South Street, Rm 1A-257B 289 Great Rd. 775 Morristown, NJ 07960 Acton, MA 01720 776 U.S.A U.S.A 778 Ph: +1-201-829-4261 Ph: +1-508-266-4536 779 Email: braja@bellcore.com Email: nair@nexen.com