idnits 2.17.1 draft-guerin-qos-routing-ospf-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. 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 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 16 instances of too long lines in the document, the longest one being 7 characters in excess of 72. ** The abstract seems to contain references ([Moy98], [Con]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 1754 has weird spacing: '...v].hops then...' -- 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 (14 April 1998) is 9480 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'AGK99' -- Possible downref: Non-RFC (?) normative reference: ref. 'AGKT98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Alm92' -- Possible downref: Non-RFC (?) normative reference: ref. 'AT98' -- Possible downref: Non-RFC (?) normative reference: ref. 'BP95' -- Possible downref: Non-RFC (?) normative reference: ref. 'Car79' -- Possible downref: Non-RFC (?) normative reference: ref. 'CLR90' -- Possible downref: Non-RFC (?) normative reference: ref. 'Con' -- Possible downref: Non-RFC (?) normative reference: ref. 'GJ79' -- Possible downref: Non-RFC (?) normative reference: ref. 'GKH97' -- Possible downref: Non-RFC (?) normative reference: ref. 'GKR97' -- Possible downref: Non-RFC (?) normative reference: ref. 'GO97' -- Possible downref: Non-RFC (?) normative reference: ref. 'GOW97' -- Possible downref: Non-RFC (?) normative reference: ref. 'KNB98' -- Possible downref: Non-RFC (?) normative reference: ref. 'LO98' ** Obsolete normative reference: RFC 1583 (ref. 'Moy94') (Obsoleted by RFC 2178) -- Possible downref: Non-RFC (?) normative reference: ref. 'Prz95' -- Possible downref: Non-RFC (?) normative reference: ref. 'SPG97' -- Possible downref: Non-RFC (?) normative reference: ref. 'ST83' -- Possible downref: Non-RFC (?) normative reference: ref. 'Tan89' -- Possible downref: Non-RFC (?) normative reference: ref. 'YPG97' Summary: 10 errors (**), 0 flaws (~~), 2 warnings (==), 23 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force G.Apostolopoulos/R. Guerin/S. Kamat 2 INTERNET DRAFT IBM/UPenn/IBM 3 A. Orda/T. Przygienda/D. Williams 4 Technion/Lucent/IBM 5 14 April 1998 7 QoS Routing Mechanisms and OSPF Extensions 8 draft-guerin-qos-routing-ospf-05.txt 10 Status of This Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note 17 that other groups may also distribute working documents as 18 Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at 22 any time. It is inappropriate to use Internet- Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Abstract 35 This memo describes extensions to the OSPF [Moy98] protocol to 36 support QoS routes. The focus of this document is on the algorithms 37 used to compute QoS routes and on the necessary modifications to OSPF 38 to support this function, e.g., the information needed, its format, 39 how it is distributed, and how it is used by the QoS path selection 40 process. Aspects related to how QoS routes are established and 41 managed are also briefly discussed. The goal of this document is 42 to identify a framework and possible approaches to allow deployment 43 of QoS routing capabilities with the minimum possible impact to the 44 existing routing infrastructure. 46 In addition, experience from an implementation of the proposed 47 extensions in the GateD environment [Con], along with performance 48 measurements is presented. 50 Contents 52 Status of This Memo i 54 Abstract i 56 1. Introduction 1 57 1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 1 58 1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 3 60 2. Path Selection Information and Algorithms 5 61 2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 5 62 2.2. Advertisement of Link State Information . . . . . . . . . 6 63 2.3. Path Selection . . . . . . . . . . . . . . . . . . . . . 8 64 2.3.1. Path Computation Algorithm . . . . . . . . . . . 10 66 3. OSPF Protocol Extensions 15 67 3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . . 16 68 3.2. Encoding Resources as Extended TOS . . . . . . . . . . . 17 69 3.2.1. Encoding bandwidth resource . . . . . . . . . . . 18 70 3.2.2. Encoding Delay . . . . . . . . . . . . . . . . . 20 71 3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . . 20 72 3.4. Calculating the Inter-area Routes . . . . . . . . . . . . 21 73 3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . . 21 75 4. A Reference Implementation based on GateD 21 76 4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . . 22 77 4.2. Implementing the QoS Extensions of OSPF . . . . . . . . . 22 78 4.2.1. Design Objectives and Scope . . . . . . . . . . . 22 79 4.2.2. Architecture . . . . . . . . . . . . . . . . . . 24 80 4.3. Major Implementation Issues . . . . . . . . . . . . . . . 24 81 4.4. Bandwidth and Processing Overhead of QoS Routing . . . . 28 83 5. Security Considerations 31 85 A. Pseudocode for the BF Based Pre-Computation Algorithm 32 87 B. On-Demand Dijkstra Algorithm for QoS Path Computation 34 89 C. Precomputation Using Dijkstra Algorithm 37 91 D. Explicit Routing Support 41 93 1. Introduction 95 In this document, we describe a set of proposed additions to the 96 OSPF routing protocol (these additions have been implemented on top 97 of the GateD [Con] implementation of OSPF V2 [Moy98]) to support 98 Quality-of-Service (QoS) routing in IP networks. Support for QoS 99 routing can be viewed as consisting of three major components: 101 1. Obtain the information needed to compute QoS paths and select a 102 path capable of meeting the QoS requirements of a given request, 104 2. Establish the path selected to accommodate a new request, 106 3. Maintain the path assigned for use by a given request. 108 Although we touch upon aspects related to the last two components, 109 the focus of this document is on the first one. In particular, we 110 discuss the metrics required to support QoS, the extension to the 111 OSPF link state advertisement mechanism to propagate updates of QoS 112 metrics, and the modifications to the path selection to accommodate 113 QoS requests. The goal of the extensions described in this document 114 is to improve performance for QoS flows (likelihood to be routed on 115 a path capable of providing the requested QoS), with minimal impact 116 on the existing OSPF protocol and its current implementation. Given 117 the inherent complexity of QoS routing, achieving this goal obviously 118 implies trading-off ``optimality'' for ``simplicity'', but we believe 119 this to be required in order to facilitate deployment of QoS routing 120 capabilities. 122 In addition to describing the proposed extensions to the OSPF 123 protocol, this document also reports experimental data based on 124 performance measurements of an implementation done on the GateD 125 platform (see Section 4). 127 1.1. Overall Framework 129 We consider a network (1) that supports both best-effort packets and 130 packets with QoS guarantees. The way in which the network resources 131 are split between the two classes is irrelevant, except for the 132 assumption that each QoS capable router in the network is able to 133 dedicate some of its resources to satisfy the requirements of QoS 135 ---------------------------- 136 1. In this document we commit the abuse of notation of calling a 137 ``network'' the interconnection of routers and networks through which 138 we attempt to compute a QoS path. 140 packets. QoS capable routers are also assumed capable of identifying 141 and advertising resources that remain available to new QoS flows. 142 In addition, we limit ourselves to the case where all the routers 143 involved support the QoS extensions described in this document, 144 i.e., we do not consider the problem of establishing a route in a 145 heterogeneous environment where some routers are QoS-capable and 146 others are not. Furthermore, in this document, we focus on the 147 case of unicast flows, although many of the additions we define are 148 applicable to multicast flows as well. 150 We assume that a flow with QoS requirements specifies them in 151 some fashion that is accessible to the routing protocol. For 152 example, this could correspond to the arrival of an RSVP [RZB+97] 153 PATH message, whose TSpec is passed to routing together with the 154 destination address. After processing such a request, the routing 155 protocol returns the path that it deems the most suitable given the 156 flow's requirements. Depending on the scope of the path selection 157 process, this returned path could range from simply identifying the 158 best next hop, i.e., a hop-by-hop path selection model, to specifying 159 all intermediate nodes to the destination, i.e., an explicit route 160 model. The nature of the path being returned impacts the operation 161 of the path selection algorithm as it translates into different 162 requirements for constructing and returning the appropriate path 163 information. However, it does not affect the basic operation of the 164 path selection algorithm (2). 166 For simplicity and also because it is the model currently supported 167 in the implementation (see Section 4 for details), in the rest of 168 this document we focus on the hop-by-hop path selection model. The 169 additional modifications required to support an explicit routing 170 model are discussed in appendix D, but are peripheral to the main 171 focus of this document which concentrates on the specific extensions 172 to the OPSF protocol to support computation of QoS routes. 174 In addition to the problem of selecting a QoS path and possibly 175 reserving the corresponding resources, one should note that the 176 successful delivery of QoS guarantees requires that the packets of 177 the associated ``QoS flow'' be forwarded on the selected path. This 178 typically requires the installation of corresponding forwarding state 179 in the router. For example, with RSVP [RZB+97] flows a classifier 180 entry is created based on the filter specs contained in the RESV 181 message. In the case of a Differentiated Service [KNB98] setting, 183 ---------------------------- 184 2. This is true for uni-cast flows, but in the case of multi-cast flows, 185 hop-by-hop and an explicit routing clearly have different 186 implications. 188 the classifier entry may be based on the destination address (or 189 prefix) and the corresponding value of the DS byte. The mechanisms 190 described in this document are at the control path level and are, 191 therefore, independent of data path mechanisms such as the packet 192 classification method used. Nevertheless, it is important to notice 193 that consistent delivery of QoS guarantees implies stability of 194 the data path. In particular, while it is possible that after a 195 path is first selected, network conditions change and result in the 196 appearance of ``better'' paths, such changes should be prevented 197 from unnecessarily affecting existing paths. In particular, 198 switching over to a new (and better) path should be limited to 199 specific conditions, e.g., when the initial selection turns out to 200 be inadequate or extremely ``expensive''. This aspect is beyond the 201 scope of QoS routing and belongs to the realm of path management, 202 which is outside the main focus of this document. However, because 203 of its potentially significant impact on the usefulness of QoS 204 routing, we briefly outline a possible approach to path management. 206 Avoiding unnecessary changes to QoS paths requires that state 207 information be maintained for each QoS path after it has been 208 selected. This state information is used to track the validity of 209 the path, i.e., is the current path adequate or should QoS routing 210 be queried again to generate a new and potentially better path. 211 We say that a path is ``pinned'' when its state specifies that 212 QoS routing need not be queried anew, while a path is considered 213 ``un-pinned'' otherwise. The main issue is then to define how, when, 214 and where path pinning and un-pinning is to take place, and this 215 will typically depend on the mechanism used to request QoS routes. 216 For example, when the RSVP protocol is the mechanism being used, it 217 is desirable that path management be kept as synergetic as possible 218 with the existing RSVP state management. In other words, pinning 219 and un-pinning of paths should be coordinated with RSVP soft states, 220 and structured so as to require minimal changes to RSVP processing 221 rules. A broad RSVP-routing interface that enables this is described 222 in [GKR97]. Use of such an interface in the context of reserving 223 resources along an explicit path with RSVP is discussed in [GLG+97]. 224 Details of path management and a means for avoiding loops in case of 225 hop-by-hop path setup can be found in [GKH97], and are not addressed 226 further in this document. 228 1.2. Simplifying Assumptions 230 In order to achieve our goal of minimizing impact to the existing 231 protocol and implementation, we impose certain restrictions on 232 the range of extensions we initially consider to support QoS. The 233 first restriction is on the type of additional (QoS) metrics that 234 will be added to Link State Advertisements (LSAs) for the purpose 235 of distributing metrics updates. Specifically, the extensions to 236 LSAs that we initially consider, include only available bandwidth 237 and delay. In addition, path selection is itself limited to 238 considering only bandwidth requirements. In particular, the path 239 selection algorithm selects paths capable of satisfying the bandwidth 240 requirement of flows, while at the same time trying to minimize the 241 amount of network resources that need to be allocated, i.e., minimize 242 the number of hops used. 244 This focus on bandwidth is adequate in most instances, and meant to 245 keep initial complexity at an acceptable level. However, it does 246 not fully capture the complete range of potential QoS requirements. 247 For example, a delay-sensitive flow of an interactive application 248 could be put on a path using a satellite link, if that link provided 249 a direct path and had plenty of unused bandwidth. This would clearly 250 be an undesirable choice. Our approach to preventing such poor 251 choices, is to assign delay-sensitive flows to a ``policy'' that 252 would eliminate from the network all links with high propagation 253 delay, e.g., satellite links, before invoking the path selection 254 algorithm. In general, multiple policies could be used to capture 255 different requirements, each presenting to the path selection 256 algorithm a correspondingly pruned network topology, on which 257 the same algorithm would be used to generate an appropriate path. 258 Alternatively, different algorithms could be used depending on the 259 QoS requirements expressed by an incoming request. Such extensions 260 are beyond the scope of this document, which limits itself to 261 describing the case of a single metric, bandwidth. However, it is 262 worth pointing out that a simple extension to the path selection 263 algorithm proposed in this document allows us to directly account 264 for delay, under certain conditions, when rate-based schedulers are 265 employed, as in the Guaranteed Service proposal [SPG97]; details can 266 be found in [GOW97]. 268 Another important aspect to ensure that introducing support for QoS 269 routing has the minimal possible impact, is to develop a solution 270 that has the smallest possible computing overhead. Additional 271 computations are unavoidable, but it is desirable to keep the 272 computational cost of QoS routing at a level comparable to that of 273 traditional routing algorithms. One possible approach to achieve 274 this goal, is to allow pre-computation of QoS routes. This is the 275 method that was chosen for the implementation of the QoS extensions 276 to OSPF and is, therefore, the one described in detail in this 277 document. Alternative approaches are briefly reviewed in appendices. 278 However, it should be noted that although several alternative path 279 selection algorithms are possible, the same algorithm should be used 280 consistently within a given routing domain. This requirement may 281 be relaxed when explicit routing is used, as the responsibility for 282 selecting a QoS path lies with a single entity, the origin of the 283 request, which then ensures consistency even if each router uses 284 a different path selection algorithm. Nevertheless, the use of a 285 common path selection algorithm within an AS is recommended, if not 286 necessary, for proper operation. 288 A last aspect of concern regarding the introduction of QoS routing, 289 is to control the overhead associated with the additional link 290 state updates caused by more frequent changes to link metrics. 291 The goal is to minimize the amount of additional update traffic 292 without adversely affecting the performance of path selection. In 293 Section 2.2, we present a brief discussion of various alternatives 294 that trade accuracy of link state information for protocol overhead. 295 Potential enhancements to the path selection algorithm, which seek 296 to (directly) account for the inaccuracies in link metrics, are 297 described in [GOW97], while a comprehensive treatment of the subject 298 can be found in [GO97, LO98]. In Section 4, we also describe the 299 design choices made in a reference implementation, to allow future 300 extensions and experimentation with different link state update 301 mechanisms. 303 The rest of this document is structured as follows. In Section 2, 304 we describe the general design choices and mechanisms we rely 305 on to support QoS request. This includes details on the path 306 selection metrics, link state update extensions, and the path 307 selection algorithm itself. Section 3 focuses on the specific 308 extensions that the OSPF protocol requires, while Section 4 describes 309 their implementation in the GateD platform and also presents some 310 experimental results. Section 5 briefly addresses security issues 311 that the proposed schemes may raise. Finally, several appendices 312 provide additional material of interest, e.g., alternative path 313 selection algorithms and support for explicit routes, but somewhat 314 outside the main focus of this document. 316 2. Path Selection Information and Algorithms 318 This section reviews the basic building blocks of QoS path selection, 319 namely the metrics on the which the routing algorithm operates, the 320 mechanisms used to propagate updates for these metrics, and finally 321 the path selection algorithm itself. 323 2.1. Metrics 325 The process of selecting a path that can satisfy the QoS requirements 326 of a new flow relies on both the knowledge of the flow's requirements 327 and characteristics, and information about the availability of 328 resources in the network. In addition, for purposes of efficiency, 329 it is also important for the algorithm to account for the amount of 330 resources the network has to allocate to support a new flow. In 331 general, the network prefers to select the ``cheapest'' path among 332 all paths suitable for a new flow, and it may even decide not to 333 accept a new flow for which a feasible path exists, if the cost of 334 the path is deemed too high. Accounting for these aspects involves 335 several metrics on which the path selection process is based. They 336 include: 338 - Link available bandwidth: As mentioned earlier, we currently 339 assume that most QoS requirements are derivable from a 340 rate-related quantity, termed ``bandwidth.'' We further assume 341 that associated with each link is a maximal bandwidth value, 342 e.g., the link physical bandwidth or some fraction thereof that 343 has been set aside for QoS flows. Since for a link to be capable 344 of accepting a new flow with given bandwidth requirements, at 345 least that much bandwidth must be still available on the link, 346 the relevant link metric is, therefore, the (current) amount of 347 available (i.e., unallocated) bandwidth. Changes in this metric 348 need to be advertised as part of extended LSAs, so that accurate 349 information is available to the path selection algorithm. 351 - Link propagation delay: This quantity is meant to identify high 352 latency links, e.g., satellite links, which may be unsuitable for 353 real-time requests. This quantity also needs to be advertised 354 as part of extended LSAs, although timely dissemination of 355 this information is not critical as this parameter is unlikely 356 to change (significantly) over time. As mentioned earlier, 357 link propagation delay can be used to decide on the pruning of 358 specific links, when selecting a path for a delay sensitive 359 request; also, it can be used to support a related extension, as 360 described in [GOW97]. 362 - Hop-count: This quantity is used as a measure of the path cost 363 to the network. A path with a smaller number of hops (that can 364 support a requested connection) is typically preferable, since 365 it consumes fewer network resources. As a result, the path 366 selection algorithm will attempt to find the minimum hop path 367 capable of satisfying the requirements of a given request. Note 368 that contrary to bandwidth and propagation delay, hop count is a 369 metric that does not affect LSAs, and it is only used implicitly 370 as part of the path selection algorithm. 372 2.2. Advertisement of Link State Information 374 The new link metrics identified in the previous section need to 375 be advertised across the network, so that each router can compute 376 accurate and consistent QoS routes. It is assumed that each router 377 maintains an updated database of the network topology, including the 378 current state (available bandwidth and propagation delay) of each 379 link. As mentioned before, the distribution of link state (metrics) 380 information is based on extending OSPF mechanisms. The detailed 381 format of those extensions is described in Section 3, but in addition 382 to how link state information is distributed, another important 383 aspect is when such distribution is to take place. 385 One option is to mandate periodic updates, where the period of 386 updates is determined based on a tolerable corresponding load on 387 the network and the routers. The main disadvantage of such an 388 approach is that major changes in the bandwidth available on a link 389 could remain unknown for a full period and, therefore, result in 390 many incorrect routing decisions. Ideally, routers should have the 391 most current view of the bandwidth available on all links in the 392 network, so that they can make the most accurate decision of which 393 path to select. Unfortunately, this then calls for very frequent 394 updates, e.g., each time the available bandwidth of a link changes, 395 which is neither scalable nor practical. In general, there is a 396 trade-off between the protocol overhead of frequent updates and the 397 accuracy of the network state information that the path selection 398 algorithm depends on. We outline next a few possible link state 399 update policies, which strike a practical compromise. 401 The basic idea is to trigger link state advertisements only when 402 there is a significant change in the value of metrics since the last 403 advertisement. The notion of significance of a change can be based 404 on an ``absolute'' scale or a ``relative'' one. An absolute scale 405 means partitioning the range of values that a metric can take into 406 equivalence classes and triggering an update whenever the metric 407 changes sufficiently to cross a class boundary (3). A relative 408 scale, on the other hand, triggers updates when the percentage change 409 in the metric value exceeds a predefined threshold. Independent of 410 whether a relative or an absolute change trigger mechanism is used, a 411 periodic trigger constraint can also be added. This constraint can 412 be in the form of a hold-down timer, which is used to force a minimum 413 spacing between consecutive updates. Alternatively, a transmit 414 timer can also be used to ensure the transmission of an update after 415 a certain time has expired. Such a feature can be useful if link 416 state updates advertising bandwidth changes are sent unreliably. The 417 current protocol extensions described in Section 3 as well as the 418 implementation of Section 4 do not consider such an option as metric 420 ---------------------------- 421 3. Some hysteresis mechanism should be added to suppress updates when 422 the metric value oscillates around a class boundary. 424 updates are sent using the standard, and reliable, OSPF flooding 425 mechanism. However, this is clearly an extension worth considering 426 as it can help lower substantially the protocol overhead associated 427 with metrics updates. 429 In both the relative and absolute change approaches, the metric value 430 advertised in an LSA can be either the actual or a quantized value. 431 Advertising the actual metric value is more accurate and, therefore, 432 preferable when metrics are frequently updated. On the other hand, 433 when updates are less frequent, e.g., because of a low sensitivity 434 trigger or the use of hold-down timers, advertising quantized 435 values can be of benefit. This is because it can help increase 436 the number of equal cost paths and, therefore, improve robustness 437 to metrics inaccuracies. In general, there is a broad space of 438 possible trade-offs between accuracy and overhead and selecting an 439 appropriate design point is difficult and depends on many parameters 440 (see [AGKT98] for a more detailed discussion of these issues). As 441 a result, in order to help acquire a better understanding of these 442 issues, the implementation described in Section 4 supports a range 443 of options that allow exploration of the available design space. In 444 addition, Section 4 also reports experimental data on the traffic 445 load and processing overhead generated by links state updates for 446 different configurations. 448 2.3. Path Selection 450 There are two major aspects to computing paths for QoS requests. The 451 first is the actual path selection algorithm itself, i.e., which 452 metrics and criteria it relies on. The second is when the algorithm 453 is actually invoked. 455 The topology on which the algorithm is run is, as with the standard 456 OSPF path selection, a directed graph where vertices (4) consist of 457 routers and networks (transit vertices) as well as stub networks 458 (non-transit vertices). When computing a path, stub networks are 459 added as a post-processing step, which is essentially similar to what 460 is done with the current OSPF routing protocol. The optimization 461 criteria used by the path selection are reflected in the costs 462 associated with each interface in the topology and how those costs 463 are accounted for in the algorithm itself. As mentioned before, 464 the cost of a path is a function of both its hop count and the 465 amount of available bandwidth. As a result, each interface has 466 associated with it a metric, which corresponds to the amount of 468 ---------------------------- 469 4. In this document, we use the terms node and vertex interchangeably. 471 bandwidth that remains available on this interface. This metric is 472 combined with hop count information to provide a cost value, whose 473 goal is to pick a path with the minimum possible number of hops 474 among those that can support the requested bandwidth. When several 475 such paths are available, the preference is for the path whose 476 available bandwidth (i.e., the smallest value on any of the links 477 in the path) is maximal. The rationale for the above rule is the 478 following: we focus on feasible paths (as accounted by the available 479 bandwidth metric) that consume a minimal amount of network resources 480 (as accounted by the hop-count metric); and the rule for selecting 481 among these paths is meant to balance load as well as maximize the 482 likelihood that the required bandwidth is indeed available. 484 It should be noted that standard routing algorithms are typically 485 single objective optimizations, i.e., they may minimize the 486 hop-count, or maximize the path bandwidth, but not both. Double 487 objective path optimization is a more complex task, and, in general, 488 it is an intractable problem [GJ79]. Nevertheless, because of the 489 specific nature of the two objectives being optimized (bandwidth and 490 hop count), the complexity of the above algorithm is competitive 491 with even that of standard single-objective algorithms. For readers 492 interested in a thorough treatment of the topic, with insights into 493 the connection between the different algorithms, linear algebra and 494 modification of metrics, [Car79] is recommended. 496 Before proceeding with a more detailed description of the path 497 selection algorithm itself, we briefly review the available options 498 when it comes to deciding when to invoke the algorithm. The two 499 main options are: 1) to perform on-demand computations, that is, 500 trigger a computation for each new request, and 2) to use some form 501 of pre-computation. The on-demand case involves no additional issues 502 in terms of when computations should be triggered, but running the 503 path selection algorithm for each new request can be computationally 504 expensive (see [AT98] for a discussion on this issue). On the other 505 hand, pre-computing paths amortizes the computational cost over 506 multiple requests, but each computation instance is usually more 507 expensive than in the on-demand case (paths are computed to all 508 destinations and for all possible bandwidth requests rather than for 509 a single destination and a given bandwidth request). Furthermore, 510 depending on how often paths are recomputed, the accuracy of the 511 selected paths may be lower. In this document, we primarily focus 512 on the case of pre-computed paths, which is also the only method 513 currently supported in the reference implementation described in 514 Section 4. In this case, clearly, an important issue is when such 515 pre-computation should take place. The two main options we consider 516 are periodic pre-computations and pre-computations after a given (N) 517 number of updates have been received. The former has the benefit of 518 ensuring a strict bound on the computational load associated with 519 pre-computations, while the latter can provide for a more responsive 520 solution (5). Section 4 provides some experimental results comparing 521 the performance and cost of periodic pre-computations for different 522 period values. 524 2.3.1. Path Computation Algorithm 526 This section describes a path selection algorithm, which for a given 527 network topology and link metrics (available bandwidth), pre-computes 528 all possible QoS paths, while maintaining a reasonably low 529 computational complexity. Specifically, the algorithm pre-computes 530 for any destination a minimum hop count path with maximum bandwidth, 531 and has a computational complexity comparable to that of a standard 532 Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest 533 path algorithm is adapted to compute paths of maximum available 534 bandwidth for all hop counts. It is a property of the BF algorithm 535 that, at its h-th iteration, it identifies the optimal (in our 536 context: maximal bandwidth) path between the source and each 537 destination, among paths of at most h hops. In other words, the 538 cost of a path is a function of its available bandwidth, i.e., the 539 smallest available bandwidth on all links of the path, and finding 540 a minimum cost path amounts to finding a maximum bandwidth path. 541 However, because the BF algorithm progresses by increasing hop count, 542 it essentially provides for free the hop count of a path as a second 543 optimization criteria. 545 Specifically, at the kth (hop count) iteration of the algorithm, the 546 maximum bandwidth available to all destinations on a path of no more 547 than k hops is recorded (together with the corresponding routing 548 information). After the algorithm terminates, this information 549 provides for all destinations and bandwidth requirements, the path 550 with the smallest possible number of hops and sufficient bandwidth 551 to accommodate the new request. Furthermore, this path is also the 552 one with the maximal available bandwidth among all the feasible paths 553 with at most these many hops. This is because for any hop count, the 554 algorithm always selects the one with maximum available bandwidth. 556 ---------------------------- 557 5. Various hybrid methods can also be envisioned, e.g., periodic 558 computations except if more than a given number of updates are 559 received within a shorter interval, or periodic updates except if the 560 change in metrics corresponding to a given update exceeds 561 a certain threshold. Such variations are, however, not considered in 562 this document. 564 We now proceed with a more detailed description of the algorithm 565 and the data structure used to record routing information, i.e., 566 the QoS routing table that gets built as the algorithm progresses 567 (the pseudo-code for the algorithm can be found in Appendix A). 568 As mentioned before, the algorithm operates on a directed graph 569 consisting only of transit vertices (routers and networks), with 570 stub-networks subsequently added to the path(s) generated by the 571 algorithm. The metric associated with each edge in the graph is the 572 bandwidth available on the corresponding interface. Let us denote by 573 b(n;m) the available bandwidth on the link from node n to m. The 574 vertex corresponding to the router where the algorithm is being run, 575 i.e., the computing router, is denoted as the ``source node'' for the 576 purpose of path selection. The algorithm proceeds to pre-compute 577 paths from this source node to all possible destination networks and 578 for all possible bandwidth values. At each (hop count) iteration, 579 intermediate results are recorded in a QoS routing table, which has 580 the following structure: 582 The QoS routing table: 584 - a KxH matrix, where K is the number of destinations (vertices 585 in the graph) and H is the maximal allowed (or possible) number 586 of hops for a path. 588 - The (n;h) entry is built during the hth iteration (hop count 589 value) of the algorithm, and consists of two fields: 591 * bw: the maximum available bandwidth, on a path of at most h 592 hops between the source node (router) and destination node 593 n; 595 * neighbor: this is the routing information associated with 596 the h (or less) hops path to destination node n, whose 597 available bandwidth is bw. In the context of hop-by-hop 598 path selection (6), the neighbor information is simply the 599 identity of the node adjacent to the source node on that 600 path. As a rule, the ``neighbor'' node must be a router and 601 not a network, the only exception being the case where the 602 network is the destination node (and the selected path is the 603 single edge interconnecting the source to it). 605 Next, we provide additional details on the operation of the algorithm 606 and how the entries in the routing table are updated as the algorithm 608 ---------------------------- 609 6. Modifications to support explicit routing are discussed in 610 Appendix D. 612 proceeds. For simplicity, we first describe the simpler case 613 where all edges count as ``hops,'' and later explain how zero-hop 614 edges are handled. Zero-hop edges arise in the case of transit 615 networks vertices, where only one of the two incoming and outgoing 616 edges should be counted in the hop count computation, as they both 617 correspond to the same physical hop. Accounting for this aspect 618 requires distinguishing between network and router nodes, and the 619 steps involved are detailed later in this section as well as in the 620 pseudo-code of Appendix A. 622 When the algorithm is invoked, the routing table is first initialized 623 with all bw fields set to 0 and neighbor fields cleared. Next, the 624 entries in the first column (which corresponds to one-hop paths) of 625 the neighbors of the computing router are modified in the following 626 way: the bw field is set to the value of the available bandwidth 627 on the direct edge from the source. The neighbor field is set to 628 the identity of the neighbor of the computing router, i.e., the next 629 router on the selected path. 631 Afterwards, the algorithm iterates for at most H iterations 632 (considering the above initial iteration as the first). The value 633 of H could be implicit, i.e., the diameter of the network or, in 634 order to better control the worst case complexity, it can be set 635 explicitly thereby limiting path lengths to at most H hops. In the 636 latter case, H must be assigned a value larger than the length of 637 the minimum hop-count path to any node in the graph. 639 At iteration h, we first copy column h-1 into column h. In 640 addition, the algorithm keeps a list of nodes that changed their 641 bw value in the previous iteration, i.e., during the (h-1)-th 642 iteration. The algorithm then looks at each link (n;m) where n is 643 a node whose bw value changed in the previous iteration, and checks 644 the maximal available bandwidth on an (at most) h-hop path to node 645 m whose final hop is that link. This amounts to taking the minimum 646 between the bw field in entry (n;h-1) and the link metric value 647 b(n;m) kept in the topology database. If this value is higher than 648 the present value of the bw field in entry (m;h), then a better 649 (larger bw value) path has been found for destination m and with at 650 most h hops. The bw field of entry (m;h) is then updated to reflect 651 this new value. In the case of hop-by-hop routing, the neighbor 652 field of entry (m;h) is set to the same value as in entry (n;h-1). 653 This records the identity of the first hop (next hop from the source) 654 on the best path identified thus far for destination m and with h 655 (or less) hops. 657 As mentioned earlier, extending the above algorithm to handle 658 zero-hop edges is needed due to the possible use of multi-access 659 networks, e.g., T/R, E/N, etc., to interconnect routers. Such 660 entities are also represented by means of a vertex in the OSPF 661 topology, but a network connecting two routers should clearly 662 be considered as a single hop path rather than a two hop path. 663 For example, consider three routers A, B, and C connected over 664 an Ethernet network N, which the OSPF topology represents as in 665 Figure 1. 667 A----N----B 668 | 669 | 670 C 672 Figure 1: Zero-Hop Edges 674 In the example of Figure 1, although there are directed edges in both 675 directions, an edge from the network to any of the three routers 676 must have zero ``cost'', so that it is not counted twice. It should 677 be noted that when considering such environments in the context 678 of QoS routing, it is assumed that some entity is responsible for 679 determining the ``available bandwidth'' on the network, e.g., a 680 subnet bandwidth manager. The specification and operation of such an 681 entity is beyond the scope of this document. 683 Accommodating zero-hop edges in the context of the path selection 684 algorithm described above is done as follows: At each iteration h 685 (starting with the first), whenever an entry (m;h) is modified, it 686 is checked whether there are zero-cost edges (m;k) emerging from 687 node m. This is the case when m is a transit network. In that 688 case, we attempt to further improve the entry of node k within the 689 current iteration, i.e., entry (k;h) (rather than entry (k;h+1)), 690 since the edge (m;k) should not count as an additional hop. As with 691 the regular operation of the algorithm, this amounts to taking the 692 minimum between the bw field in entry (m;h) and the link metric 693 value b(m;k) kept in the topology database (7). If this value is 694 higher than the present value of the bw field in entry (k;h), then 695 the bw field of entry (k;h) is updated to this new value. In the 697 ---------------------------- 698 7. Note, that this does not say anything on 699 whether to differentiate between outgoing and incoming bandwidth on a 700 shared media network. As a matter of fact, a reasonable option is to 701 set the incoming bandwidth (from network to router) to infinity, and 702 only use the outgoing bandwidth value to characterize bandwidth 703 availability on the shared network. 705 case of hop-by-hop routing, the neighbor field of entry (k;h) is set, 706 as usual, to the same value as in entry (m;h) (which is also the 707 value in entry (n;h-1)). 709 Note that while for simplicity of the exposition, the issue of equal 710 cost, i.e., same hop count and available bandwidth, is not detailed 711 in the above description, it can be easily supported. It only 712 requires that the neighbor field be expanded to record the list of 713 next (previous) hops, when multiple equal cost paths are present. 715 Addition of Stub Networks 717 As was mentioned earlier, the path selection algorithm is run 718 on a graph whose vertices consist only of routers and transit 719 networks and not stub networks. This is intended to keep the 720 computational complexity as low as possible as stub networks can 721 be added relatively easily through a post-processing step. This 722 second processing step is similar to the one used in the current OSPF 723 routing table calculation [Moy98], with some differences to account 724 for the QoS nature of routes. 726 Specifically, after the QoS routing table has been constructed, all 727 the router vertices are again considered. For each router, stub 728 networks whose links appear in the router's link advertisements will 729 be processed to determine QoS routes available to them. The QoS 730 routing information for a stub network is similar to that of routers 731 and transit networks and consists of an extension to the QoS routing 732 table in the form of an additional row. The columns in that new row 733 again correspond to paths of different hop counts, and contain both 734 bandwidth and next hop information. We also assume that an available 735 bandwidth value has been advertised for the stub network. As before, 736 how this value is determined is beyond the scope of this document. 737 The QoS routes for a stub network S are constructed as follows: 739 Each entry in the row corresponding to stub network S has its bw(s) 740 field initialized to zero and its neighbor set to null. When a stub 741 network S is found in the link advertisement of router V, the value 742 bw(S,h) in the hth column of the row corresponding to stub network S 743 is updated as follows: 745 bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ), 747 where bw(V,h) is the bandwidth value of the corresponding column 748 for the QoS routing table row associated with router V, i.e., 749 the bandwidth available on an h hop path to V, and b(V,S) is the 750 advertised available bandwidth on the link from V to S. The above 751 expression essentially states that the bandwidth of a h hop path to 752 stub network S is updated using a path through router V, only if the 753 minimum of the bandwidth of the h hop path to V and the bandwidth on 754 the link between V and S is larger than the current value. 756 Update of the neighbor field proceeds similarly whenever the 757 bandwidth of a path through V is found to be larger than or equal 758 to the current value. If it is larger, then the neighbor field 759 of V in the corresponding column replaces the current neighbor 760 field of S. If it is equal, then the neighbor field of V in the 761 corresponding column is concatenated with the existing field for S, 762 i.e., the current set of neighbors for V is added to the current set 763 of neighbors for S. 765 Extracting Forwarding Information from Routing Table 767 When the QoS paths are precomputed, the forwarding information for 768 a flow with given destination and bandwidth requirement needs to be 769 extracted from the routing table. The case of hop-by-hop routing is 770 simpler than that of explicit routing. This is because, only the 771 next hop needs to be returned instead of an explicit route. 773 Specifically, assume a new request to destination, say, d, and 774 with bandwidth requirements B. The index of the destination 775 vertex identifies the row in the QoS routing table that needs to be 776 checked to generate a path. Assuming that the QoS routing table was 777 constructed using the Bellman-Ford algorithm presented later in this 778 section, the search then proceeds by increasing index (hop) count 779 until an entry is found, say at hop count or column index of h, with 780 a value of the bw field which is equal to or larger than B. This 781 entry points to the initial information identifying the selected 782 path. 784 If the path computation algorithm stores multiple equal cost paths, 785 then some degree of load balancing can be achieved at the time of 786 path selection. A next hop from the list of equivalent next hops can 787 be chosen in a round robin manner, or randomly with a probability 788 that is weighted by the actual available bandwidth on the local 789 interface. The latter is the method used in the implementation 790 described in Section 4. 792 The case of explicit routing is discussed in Appendix D. 794 3. OSPF Protocol Extensions 796 As stated earlier, one of our goals is to limit the additions to the 797 existing OSPF V2 protocol, while still providing the required level 798 of support for QoS based routing. To this end, all of the existing 799 OSPF mechanisms, data structures, advertisements, and data formats 800 remain in place. The purpose of this section of the document is to 801 describe the extensions to the OSPF protocol needed to support QoS as 802 outlined in the previous sections. 804 3.1. QoS -- Optional Capabilities 806 The OSPF Options field is present in OSPF Hello packets, Database 807 Description packets and all LSAs. The Options field enables OSPF 808 routers to support (or not support) optional capabilities, and to 809 communicate their capability level to other OSPF routers. Through 810 this mechanism, routers of differing capabilities can be mixed 811 within an OSPF routing domain. Currently, the OSPF standard [Moy98] 812 specifies the following 5 bits in the options octet: 814 +-----------------------------------------------+ 815 | * | * | DC | EA | N/P | MC | E | * | 816 +-----------------------------------------------+ 818 Note that the least significant bit (`T' bit) that was used to 819 indicate TOS routing capability in the older OSPF specification 820 [Moy94] has been removed. However, for backward compatibility with 821 previous versions of the OSPF specification, TOS-specific information 822 can be included in router-LSAs, summary-LSAs and AS-external-LSAs. 824 We propose to reclaim the `T' bit as an indicator of router's QoS 825 routing capability and refer to it as the `Q' bit. In fact, QoS 826 capability can be viewed as an extension of the TOS-capabilities and 827 QoS routing as a form of TOS-based routing. A router sets this bit 828 in its hello packets to indicate that it is capable of supporting 829 such routing. When this bit is set in a router or summary links 830 link state advertisement, it means that there are QoS fields to 831 process in the packet. When this bit is set in a network link 832 state advertisement it means that the network described in the 833 advertisement is QoS capable. 835 We need to be careful in this approach so as to avoid confusing any 836 old style (i.e., RFC 1583 based) TOS routing implementations. The 837 TOS metric encoding rules of QoS fields introduced further in this 838 section will show how this is achieved. Additionally, unlike the 839 RFC 1583 specification that unadvertised TOS metrics be treated to 840 have same cost as TOS 0, for the purpose of computing QOS routes, 841 unadvertised TOS metrics (on a hop) indicate lack of connectivity for 842 the specific TOS metrics (for that hop). 844 3.2. Encoding Resources as Extended TOS 846 Introduction of QoS should ideally not influence the compatibility 847 with existing OSPFv2 routers. To achieve this goal, necessary 848 extensions in packet formats must be defined in a way that either 849 is understood by OSPFv2 routers, ignored, or in the worst case 850 ``gracefully'' misinterpreted. Encoding of QoS metrics in the 851 TOS field which fortunately enough is longer in OSPF packets than 852 officially defined in [Alm92], allows us to mimic the new facility as 853 extended TOS capability. OSPFv2 routers will either disregard these 854 definitions or consider those unspecified. Specific precautions 855 are taken to prevent careless OSPF implementations from influencing 856 traditional TOS routers (if any) when misinterpreting the QoS 857 extensions. 859 For QoS resources, 32 combinations are available through the use 860 of the fifth bit in TOS fields contained in different LSAs. Since 861 [Alm92] defines TOS as being four bits long, this definition never 862 conflicts with existing values. Additionally, to prevent naive 863 implementations that do not take all bits of the TOS field in OSPF 864 packets into considerations, the definitions of the `QoS encodings' 865 is aligned in their semantics with the TOS encoding. Only bandwidth 866 and delay are specified as of today and their values map onto 867 `maximize throughput' and `minimize delay' if the most significant 868 bit is not taken into account. Accordingly, link reliability and 869 jitter could be defined later if necessary. 871 OSPF encoding RFC 1349 TOS values 872 ___________________________________________ 873 0 0000 normal service 874 2 0001 minimize monetary cost 875 4 0010 maximize reliability 876 6 0011 877 8 0100 maximize throughput 878 10 0101 879 12 0110 880 14 0111 881 16 1000 minimize delay 882 18 1001 883 20 1010 884 22 1011 885 24 1100 886 26 1101 887 28 1110 888 30 1111 890 OSPF encoding `QoS encoding values' 891 ------------------------------------------- 893 32 10000 894 34 10001 895 36 10010 896 38 10011 897 40 10100 bandwidth 898 42 10101 899 44 10110 900 46 10111 901 48 11000 delay 902 50 11001 903 52 11010 904 54 11011 905 56 11100 906 58 11101 907 60 11110 908 62 11111 910 Representing TOS and QoS in OSPF. 912 3.2.1. Encoding bandwidth resource 914 Given the fact that the actual metric field in OSPF packets only 915 provides 16 bits to encode the value used and that links supporting 916 bandwidth ranging into Gbits/s are becoming reality, linear 917 representation of the available resource metric is not feasible. The 918 solution is exponential encoding using appropriately chosen implicit 919 base value and number bits for encoding mantissa and the exponent. 920 Detailed considerations leading to the solution described are not 921 presented here but can be found in [Prz95]. 923 Given a base of 8, the 3 most significant bits should be reserved for 924 the exponent part and the remaining 13 for the mantissa. This allows 925 a simple comparison for two numbers encoded in this form, which is 926 often useful during implementation. 928 The following table shows bandwidth ranges covered when using 929 different exponents and the granularity of possible reservations. 931 exponent 932 value x range (2^13-1)*8^x step 8^x 933 ------------------------------------------------- 934 0 8,191 1 935 1 65,528 8 936 2 524,224 64 937 3 4,193,792 512 938 4 33,550,336 4,096 939 5 268,402,688 32,768 940 6 2,147,221,504 262,144 941 7 17,177,772,032 2,097,152 943 Ranges of Exponent Values for 13 bits, 944 base 8 Encoding, in Bytes/s 946 The bandwidth encoding rule may be summarized as: ``represent 947 available bandwidth in 16 bit field as a 3 bit exponent (with assumed 948 base of 8) followed by a 13 bit mantissa as shown below 950 0 8 16 951 | | | 952 ----------------- 953 |EXP| MANT | 954 ----------------- 956 and advertise 2's complement of the above representation.'' 958 Thus, the above encoding advertises a numeric value that is 960 2^16 -1 -(exponential encoding of the available bandwidth): 962 This has the property of advertising a higher numeric value for lower 963 available bandwidth, a notion that is consistent with that of cost. 965 Although it may seem slightly pedantic to insist on the property 966 that less bandwidth is expressed higher values, it has, besides 967 consistency, a robustness aspect in it. A router with a poor OSPF 968 implementation could misuse or misunderstand bandwidth metric as 969 normal administrative cost provided to it and compute spanning trees 970 with a ``normal'' Dijkstra. The effect of a heavily congested link 971 advertising numerically very low cost could be disastrous in such 972 a scenario. It would raise the link's attractiveness for future 973 traffic instead of lowering it. Evidence that such considerations 974 are not speculative, but similar scenarios have been encountered, can 975 be found in [Tan89]. 977 Concluding with an example, assume a link with bandwidth of 8 978 Gbits/s = 1024^3 Bytes/s, its encoding would consist of an exponent 979 value of 6 since 1024^3= 4,096*8^6, which would then have a 980 granularity of 8^6 or approx. 260 kBytes/s. The associated binary 981 representation would then be %(110) 0 1000 0000 0000% or 53,248 (8). 982 The bandwidth cost (advertised value) of this link when it is idle, 983 is then the 2's complement of the above binary representation, i.e., 984 %(001) 1 0111 1111 1111% which corresponds to a decimal value of 985 (2^16 - 1) - 53,248 = 12,287. Assuming now a current reservation 986 level of 6;400 Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of 987 available bandwidth on the link. The encoding of this available 988 bandwidth of 1'600 Mbits/s is 6,400 * 8^5, which corresponds to 989 a granularity of 8^5 or approx. 30 kBytes/s, and has a binary 990 representation of %(101) 1 1001 0000 0000% or decimal value of 991 47,360. The advertised cost of the link with this load level, is 992 then %(010) 0 0110 1111 1111%, or (2^16-1) -47,360 = 18,175. 994 Note that the cost function behaves as it should, i.e., the less 995 bandwidth is available on a link, the higher the cost and the less 996 attractive the link becomes. Furthermore, the targeted property of 997 better granularity for links with less bandwidth available is also 998 achieved. It should, however, be pointed out that the numbers given 999 in the above examples match exactly the resolution of the proposed 1000 encoding, which is of course not always the case in practice. This 1001 leaves open the question of how to encode available bandwidth 1002 values when they do not exactly match the encoding. The standard 1003 practice is to round it to the closest number. Because we are 1004 ultimately interested in the cost value for which it may be better 1005 to be pessimistic than optimistic, we choose to round costs up and, 1006 therefore, bandwidth down. 1008 3.2.2. Encoding Delay 1010 Delay is encoded in microseconds using the same exponential method 1011 as described for bandwidth except that the base is defined to be 4 1012 instead of 8. Therefore, the maximum delay that can be expressed is 1013 (2^13-1) *4^7 i.e., approx. 134 seconds. 1015 3.3. Packet Formats 1017 Given the extended TOS notation to account for QoS metrics, 1018 no changes in packet formats are necessary except for the 1020 ---------------------------- 1021 8. exponent in parenthesis 1022 (re)introduction of T-bit as the Q-bit in the options field. Routers 1023 not understanding the Q-bit should either not consider the QoS 1024 metrics distributed or consider those as `unknown' TOS. 1026 To support QoS, there are additions to two Link State Advertisements, 1027 the Router Links Advertisement and the Summary Links Advertisement. 1028 As stated above, a router identifies itself as supporting QoS by 1029 setting the Q-bit in the options field of the Link State Header. 1030 When a router that supports QoS receives either the Router Links or 1031 Summary Links Advertisement, it should parse the QoS metrics encoded 1032 in the received Advertisement. 1034 3.4. Calculating the Inter-area Routes 1036 This document proposes a very limited use of OSPF areas, that is, it 1037 is assumed that summary links advertisements exist for all networks 1038 in the area. This document does not discuss the problem of providing 1039 support for area address ranges and QoS metric aggregation. This is 1040 left for further studies. 1042 3.5. Open Issues 1044 Support for AS External Links, Virtual Links, and incremental updates 1045 for summary link advertisements are not addressed in this document 1046 and are left for further study. For Virtual Links that do exist, it 1047 is assumed for path selection that these links are non-QoS capable 1048 even if the router advertises QoS capability. Also, as stated 1049 earlier, this document does not address the issue of non-QoS routers 1050 within a QoS domain. 1052 4. A Reference Implementation based on GateD 1054 In this section we report on the experience gained from implementing 1055 the pre-computation based approach of Section 2.3.1 in the 1056 GateD [Con] environment. First, we briefly introduce the GateD 1057 environment, and then present some details on how the QoS extensions 1058 were implemented in this environment. Finally, we discuss issues 1059 that arose during the implementation effort and present some 1060 measurement based results on the overhead that the QoS extensions 1061 impose on a QoS capable router and a network of QoS routers. For 1062 further details on the implementation study, the reader is referred 1063 to [AGK99]. Additional performance evaluation based on simulations 1064 can be found in [AGKT98]. 1066 4.1. The Gate Daemon (GateD) Program 1068 GateD [Con] is a popular, public domain (9) program that provides a 1069 platform for implementing routing protocols on hosts running the Unix 1070 operating system. The distribution of the GateD software also includes 1071 implementations of many popular routing protocols, including the OSPF 1072 protocol. The GateD environment offers a variety of services useful for 1073 implementing a routing protocol. These services include a) support for 1074 creation and management of timers, b) memory management, c) a simple 1075 scheduling mechanism, d) interfaces for manipulating the host's routing 1076 table and accessing the network, and e) route management (e.g., route 1077 prioritization and route exchange between protocols). 1079 All GateD processing is done within a single Unix process, and 1080 routing protocols are implemented as one or several tasks. A GateD 1081 task is a collection of code associated with a Unix socket. The 1082 socket is used for the input and output requirements of the task. 1083 The main loop of GateD contains, among other operations, a select() 1084 call over all task sockets to determine if any read/write or error 1085 conditions occurred in any of them. GateD implements the OSPF link 1086 state database using a radix tree for fast access to individual link 1087 state records. In addition, link state records for neighboring 1088 network elements (such as adjacent routers) are linked together at 1089 the database level with pointers. GateD maintains a single routing 1090 table that contains routes discovered by all the active routing 1091 protocols. Multiple routes to the same destination are prioritized 1092 according to a set of rules and administrative preferences and 1093 only a single route is active per destination. These routes are 1094 periodically downloaded in the host's kernel forwarding table. 1096 4.2. Implementing the QoS Extensions of OSPF 1098 4.2.1. Design Objectives and Scope 1100 One of our major design objectives was to gain substantial experience 1101 with a functionally complete QoS routing implementation while 1102 containing the overall implementation complexity. Thus, our 1103 architecture was modular and aimed at reusing the existing OSPF 1104 code with only minimal changes. QoS extensions were localized to 1105 specific modules and their interaction with existing OSPF code was 1106 kept to a minimum. Besides reducing the development and testing 1107 effort, this approach also facilitated experimentation with different 1109 ---------------------------- 1110 9. Access to some of the more recent versions of the GateD software is 1111 restricted to the GateD consortium members. 1113 alternatives for implementing the QoS specific features such as 1114 triggering policies for link state updates and QoS route table 1115 computation. Several of the design choices were also influenced by 1116 our assumptions regarding the core functionalities that an early 1117 prototype implementation of QoS routing must demonstrate. Some of 1118 the important assumptions/requirements are: 1120 - Support for only hop-by-hop routing. This affected the path 1121 structure in the QoS routing table as it only needs to store next 1122 hop information. As mentioned earlier, the structure can be 1123 easily extended to allow construction of explicit routes. 1125 - Support for path pre-computation. This required the creation of 1126 a separate QoS routing table and its associated path structure, 1127 and was motivated by the need to minimize processing overhead. 1129 - Full integration of the QoS extensions into the GateD framework, 1130 including configuration support, error logging, etc. This was 1131 required to ensure a fully functional implementation that could 1132 be used by others. 1134 - Ability to allow experimentation with different approaches, e.g., 1135 use of different update and pre-computation triggering policies 1136 with support for selection and parameterization of these policies 1137 from the GateD configuration file. 1139 - Decoupling from local traffic and resource management components, 1140 i.e., packet classifiers and schedulers and local call admission. 1141 This is supported by providing an API between QoS routing and the 1142 local traffic management module, which hides all internal details 1143 or mechanisms. Future implementations will be able to specify 1144 their own mechanisms for this module. 1146 - Interface to RSVP. The implementation assumes that RSVP [RZB+97] 1147 is the mechanism used to request routes with specific QoS 1148 requirements. Such requests are communicated through an 1149 interface based on [GKR97], and used the RSVP code developed at 1150 ISI, version 4.2a2 [RZB+97]. 1152 In addition, our implementation also relies on several of the 1153 simplifying assumptions made earlier in this document, namely: 1155 - The scope of QoS route computation is currently limited to a 1156 single area. 1158 - All routers within the area are assumed to run a QoS enabled 1159 version of OSPF, i.e., inter-operability with non-QoS aware 1160 versions of the OSPF protocol is not considered. 1162 - All interfaces on a router are assumed to be QoS capable. 1164 4.2.2. Architecture 1166 The above design decisions and assumptions resulted in the 1167 architecture shown in Figure 2. It consists of three major 1168 components: the signaling component (RSVP in our case); the QoS 1169 routing component; and the traffic manager. In the rest of this 1170 section we concentrate on the structure and operation of the QoS 1171 routing component. As can be seen in Figure 2, the QoS routing 1172 extensions are further divided into the following modules: 1174 - Update trigger module determines when to advertise local link 1175 state updates. This module implements a variety of triggering 1176 policies: periodic, threshold based triggering, and class based 1177 triggering. This module also implements a hold-down timer 1178 that enforces minimum spacing between two consecutive update 1179 triggerings from the same node. 1181 - Pre-computation trigger module determines when to perform QoS 1182 path pre-computation. So far, this module implements only 1183 periodic pre-computation triggering. 1185 - Path pre-computation module computes the QoS routing table based 1186 on the QoS specific link state information as described in 1187 Section 2.3.1. 1189 - Path selection and management module selects a path for a request 1190 with particular QoS requirements, and manages it once selected, 1191 i.e., reacts to link or reservation failures. Path selection 1192 is performed as described in Section 2.3.1. Path management 1193 functionality is not currently supported. 1195 - QoS routing table module implements the QoS specific routing 1196 table, which is maintained independently of the other GateD 1197 routing tables. 1199 - Tspec mapping module maps request requirements expressed in the 1200 form of RSVP Tspecs and Rspecs into the bandwidth requirements 1201 that QoS routing uses. 1203 4.3. Major Implementation Issues 1205 Mapping the above design to the framework of the GateD implementation 1206 of OSPF led to a number of issues and design decisions. These 1207 issues mainly fell under two categories: a) interoperation of the 1208 +--------------------------------------------------+ 1209 | +-----------------------------+ | 1210 | | QoS Route Table Computation | | 1211 | +-----------------------------+ | 1212 | | | | 1213 | V | | 1214 | +-----------------+ | | 1215 +-------------->| QoS Route Table | | | 1216 | | +-----------------+ | | 1217 | | | | 1218 | | +----------------------+ +---------------+ | 1219 | | | Core OSPF Functions | | Precomputation| | 1220 | | | + | | Trigger | | 1221 | | | (Enhanced) Topology | +---------------+ | 1222 | | | Data Base | | | 1223 | | +----------------------+ | | 1224 | | | | | | 1225 | | | +----------------------------+ | 1226 | | | | Receive and update QoS-LSA | | 1227 | | | +----------------------------+ | 1228 | | | | | 1229 | | | +----------------+ | 1230 | | | | Local Interface| | 1231 | | | | Status Monitor | | 1232 | | | +----------------+ | 1233 +----------------+ | | | | 1234 | Path Selection | | +--------------+ +----------------+ | 1235 | & Management | | | Build and | | Link State | | 1236 +----------------+ | | Send QoS-LSA |----------| Update Trigger | | 1237 | | +--------------+ +----------------+ | 1238 +----------------+ | | | 1239 | QoS Parameter | | | | 1240 | Mapping | | OSPF with QoS Routing Extensions | | 1241 |----------------+ +-------------------------------------------|------+ 1242 | | 1243 +----------------+ +----------+ 1244 | QoS Route | | Local | 1245 | Request Client |<---------------------------------------->| Resource | 1246 | (e.g. RSVP) | | Manager | 1247 +----------------+ +----------+ 1249 Figure 2: The software architecture 1251 QoS extensions with pre-existing similar OSPF mechanisms, and b) 1252 structure, placement, and organization of the QoS routing table. 1253 Next, we briefly discuss these issues and justify the resulting 1254 design decisions. 1256 The ability to trigger link state updates in response to changes 1257 in bandwidth availability on interfaces is an essential component 1258 of the QoS extensions. Mechanisms for triggering these updates 1259 and controlling their rate have been mentioned in Section 2.2. In 1260 addition, OSPF implements its own mechanism for triggering link state 1261 updates as well as its own hold down timer, which may be incompatible 1262 with what is used for the QoS link state updates. We handle such 1263 potential conflicts as follows. First, since OSPF triggers updates 1264 on a periodic basis with low frequency, we expect these updates to 1265 be only a small part of the total volume of updates generated. As 1266 a result, we chose to maintain the periodic update triggering of 1267 OSPF. Resolving conflicts in the settings of the different hold down 1268 timer settings requires more care. In particular, it is important 1269 to ensure that the existing OSPF hold down timer does not interfere 1270 with QoS updates. One option is to disable the existing OSPF timer, 1271 but protection against transient overloads calls for some hold down 1272 timer, albeit with a small value. As a result, the existing OSPF 1273 hold down timer was kept, but reduced its value to 1 second. This 1274 value is low enough (actually is the lowest possible, since GateD 1275 timers have a maximum resolution of 1 second) so that it does not 1276 interfere with the generation of the QoS link state updates, which 1277 will actually often have hold down timers of their own with higher 1278 values. An additional complexity is that the triggering of QoS 1279 link state updates needs to be made aware of updates performed by 1280 OSPF itself. This is necessary, as regular OSPF updates also carry 1281 bandwidth information, and this needs to be considered by QoS updates 1282 to properly determine when to trigger a new link state update. 1284 Another existing OSPF mechanism that has the potential to interfere 1285 with the extensions needed for QoS routing, is the support for 1286 delayed acknowledgments that allows aggregation of acknowledgments 1287 for multiple LSAs. Since link state updates are maintained in 1288 retransmission queues until acknowledged, excessive delay in the 1289 generation of the acknowledgement combined with the increased 1290 rates of QoS updates may result in overflows of the retransmission 1291 queues. To avoid these potential overflows, this mechanism was 1292 bypassed altogether and LSAs received from neighboring routers were 1293 immediately acknowledged. Another approach which was considered but 1294 not implemented, was to make QoS LSAs unreliable, i.e., eliminate 1295 their acknowledgments, so as to avoid any potential interference. 1296 Making QoS LSAs unreliable would be a reasonable design choice 1297 because of their higher frequency compared to the regular LSAs and 1298 the reduced impact that the loss of a QoS LSA has on the protocol 1299 operation. Note that the loss of a QoS LSA does not interfere with 1300 the base operation of OSPF, and only transiently reduces the quality 1301 of paths discovered by QoS routing. 1303 The structure and placement of the QoS routing table also raises some 1304 interesting implementation issues. Pre-computed paths are placed 1305 into a QoS routing table. This table is implemented as a set of path 1306 structures, one for each destination, which contain all the available 1307 paths to this destination. In order to be able to efficiently locate 1308 individual path structures, an access structure is needed. In order 1309 to minimize the develpement effort, the radix tree structure used 1310 for the regular GateD routing tables was reused. In addition, the 1311 QoS routing table was kept independent of the GateD routing tables 1312 to conform to the design goal of localizing changes and minimizing 1313 the impact on the existing OSPF code. An additional reason for 1314 maintaining the QoS routing separate and self-contained is that it is 1315 re-computed under conditions that are different from those used for 1316 the regular routing tables. 1318 Furthermore, since the QoS routing table is re-built frequently, 1319 it must be organized so that its computation is efficient. A 1320 common operation during the computation of the QoS routing table 1321 is mapping a link state database entry to the corresponding path 1322 structure. In order to make this operation efficient, the link 1323 state database entries were extended to contain a pointer to the 1324 corresponding path structure. In addition, when a new QoS routing 1325 table is to be computed, the previous one must be de-allocated. 1326 This is accomplished by traversing the radix tree in-order, and 1327 de-allocating each node in the tree. This full de-allocation of the 1328 QoS routing table is potentially wasteful, especially since memory 1329 allocation and de-allocation is an expensive operation. Furthermore, 1330 because path pre-computations are typically not triggered by changes 1331 in topology, the set of destinations will usually remain the same 1332 and correspond to an unchanged radix tree. A natural optimization 1333 would then be to de-allocate only the path structures and maintain 1334 the radix tree. A further enhancement would be to maintain the 1335 path structures as well, and attempt to incrementally update them 1336 only when required. However, despite the potential gains, these 1337 optimizations have not been included in the initial implementation. 1338 The main reason is that they involve subtle and numerous checks to 1339 ensure the integrity of the overall data structure at all times, 1340 e.g., correctly remove failed destinations from the radix tree and 1341 update the tree accordingly. 1343 4.4. Bandwidth and Processing Overhead of QoS Routing 1345 After completing the implementation outlined in the previous 1346 sections, it was possible to perform an experimental study of 1347 the cost and nature of the overhead of the QoS routing extensions 1348 proposed in this document. In particular, using a simple setup 1349 consisting of two interconnected routers, it is possible to measure 1350 the cost of individual QoS routing related operations. These 1351 operations are: a) computation of the QoS routing table, b) 1352 selection of a path from the QoS routing table, c) generation of a 1353 link state update, and d) reception of a link state update. Note 1354 that the last two operations are not really specific to QoS routing 1355 since regular OSPF also performs them. Nevertheless, we expect the 1356 more sensitive update triggering mechanisms required for effective 1357 QoS routing to result in increased number of updates, making the 1358 cost of processing updates an important component of the QoS routing 1359 overhead. An additional cost dimension is the memory required 1360 for storing the QoS routing table. Scaling of the above costs 1361 with increasing sizes of the topology database was investigated by 1362 artificially populating the topology databases of the routers under 1363 measurement. 1365 Table 1 shows how the measured costs depend on the size of the 1366 topology. The topology used in the measurements was built by 1367 replicating a basic building block consisting of four routers 1368 connected with transit networks in a rectangular arrangement. The 1369 details of the topology and the measurements can be found in [AGK99]. 1370 The system running the GateD software was an IBM IntelliStation Z Pro 1371 with a Pentium Pro processor at 200 MHz, 64 MBytes or real memory, 1372 running FreeBSD 2.2.5-RELEASE and GateD 4. From the results of 1373 Table 1, one can observe that the cost of path pre-computation is 1374 not much higher than that of the regular SPF computation. However, 1375 path pre-computation may need to be performed much more often 1376 than the SPF computation, and this can potentially lead to higher 1377 processing costs. This issue was investigated in a set of subsequent 1378 experiments, that are described later in this section. The other 1379 cost components reported in Table 1 include memory, and it can be 1380 seen that the QoS routing table requires roughly 80% more memory 1381 than the regular routing table. Finally, the cost of selecting a 1382 path is found to be very small compared to the path pre-computation 1383 times. As expected, all the measured quantities increase as the size 1384 of the topology increases. In particular, the storage requirements 1385 and the processing costs for both SPF computation and QoS path 1386 pre-computation scale almost linearly with the network size. 1388 In addition to the stand alone costs reported in Table 1, it 1389 is important to assess the actual operational load induced by 1390 QoS routing in the context of a large network. Since it is not 1392 ______________________________________________________________________________ 1393 |______Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_| 1394 |_____Regular_SPF_time_(microsec)_____|215_|_440_|_747__|_1158_|_1621_|_2187_| 1395 |Path_Pre-computation_time_(microsec)_|736_|_1622|_2883_|_4602_|_6617_|_9265_| 1396 |___SPF_routing_table_size_(bytes)____|2608|_4984|_8152_|_12112|_16864|_22408| 1397 |___QoS_routing_table_size_(bytes)____|3924|_7952|_13148|_19736|_27676|_36796| 1398 |___Path_Selection_time_(microsec)____|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_| 1400 Table 1: Stand alone QoS routing costs 1402 practical to reproduce a large scale network in a lab setting, 1403 the approach used was to combine simulation and measurements. 1404 Specifically, a simulation was used to obtain a time stamped trace 1405 of QoS routing related events that occur in a given router in a 1406 large scale network. The trace was then used to artificially induce 1407 similar load conditions on a real router and its adjacent links. 1408 In particular, it was used to measure the processing load at the 1409 router and bandwidth usage that could be attributed to QoS updates. 1410 A more complete discussion of the measurement method and related 1411 considerations can be found in [AGK99]. 1413 The use of a simulation further allows the use of different 1414 configurations, where network topology is varied together with other 1415 QoS parameters such as a) period of pre-computation, and b) threshold 1416 for triggering link state updates. The results reported here were 1417 derived using two types of topologies. One based on a regular but 1418 artificial 8x8 mesh network, and another (isp) which has been used 1419 in several previous studies [AGKT98, AT98] and that approximates the 1420 network of a nation-wide ISP. As far as pre-computation periods are 1421 concerned, three values of 1, 5 and 50 seconds were chosen, and for 1422 the triggering of link state update thresholds of 10% and 80% were 1423 used. These values were selected as they cover a wide range in terms 1424 of precision of pre-computed paths and accuracy of the link state 1425 information available at the routers. Also note that 1 second is the 1426 smallest pre-computation period allowed by GateD. 1428 Table 2 provides results on the processing load at the router 1429 driven by the simulation trace, for the two topologies and different 1430 combinations of QoS parameters, i.e., pre-computation period and 1431 threshold for triggering link state updates. Table 3 gives the 1432 bandwidth consumption of QoS updates on the links adjacent to the 1433 router. 1435 ________________________________________________________________ 1436 |_____________________|_________Pre-computation_Period_________| 1437 |Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___| 1438 |_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__| 1439 |_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_| 1441 isp 1443 ________________________________________________________________ 1444 |_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)| 1445 |_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)| 1447 8x8 mesh 1448 Table 2: Router processing load and (bandwidth blocking). 1450 In Table 2, processing load is expressed as the percentage of the 1451 total CPU resources that are consumed by GateD processing. The 1452 same table also shows the routing performance that is achieved 1453 for each combination of QoS parameters, so that comparison of the 1454 different processing cost/routing performance trade-offs can be 1455 made. Routing performance is measured using the bandwidth blocking 1456 ratio, defined as the sum of requested bandwidth of the requests 1457 that were rejected over the total offered bandwidth. As can be 1458 seen from Table 2, processing load is low even when the QoS routing 1459 table is recomputed every second, and LSAs are generated every time 1460 the available bandwidth on a link changes by more than 10% of the 1461 last advertised value. This seems to indicate that given today's 1462 processor technology, QoS routing should not be viewed as a costly 1463 enhancement, at least not in terms of its processing requirements. 1464 Another general observation is that while network size has obviously 1465 an impact, it does not seem to drastically affect the relative 1466 influence of the different parameters. In particular, despite the 1467 differences that exist between the isp and mesh topologies, changing 1468 the pre-computation period or the update threshold translates into 1469 essentially similar relative changes. 1471 Similar conclusions can be drawn for the update traffic shown in 1472 Table 3. In all cases, this traffic is only a small fraction of 1473 the link's capacity. Clearly, both the router load and the link 1474 bandwidth consumption depend on the router and link that was the 1475 target of the measurements and will vary for different choices. The 1476 results shown here are meant to be indicative, and a more complete 1477 discussion can be found in [AGK99]. 1479 _______________________________________ 1480 |_Link_state_threshold_|_______________| 1481 |_________10%__________|3112_bytes/sec_| 1482 |_________80%__________|177_bytes/sec__| 1484 isp 1485 ________________________________________ 1486 |_________10%__________|15438_bytes/sec_| 1487 |_________80%__________|1053_bytes/sec__| 1489 8x8 mesh 1490 Table 3: Link state update traffic 1492 Summarizing, by carrying out the implementation of the proposed QoS 1493 routing extensions to OSPF we demonstrated that such extensions are 1494 fairly straightforward to implement. Furthermore, by measuring 1495 the performance of the real system we were able to demonstrate 1496 that the overheads associated with QoS routing are not excessive, 1497 and are definitely within the capabilities of modern processor and 1498 workstation technology. 1500 5. Security Considerations 1502 The QoS extensions proposed in this document do not raise any 1503 security considerations that are in addition to the ones associated 1504 with regular OSPF. The security considerations of OSPF are presented 1505 in [Moy98]. However, it should be noted that this document assumes 1506 the availability of some entity responsible for assessing the 1507 legitimacy of QoS requests. For example, when the protocol used for 1508 initiating QoS requests is the RSVP protocol, this capability can be 1509 provided through the use of RSVP Policy Decision Points and Policy 1510 Enforcement Points as described in [YPG97]. Similarly, a policy 1511 server enforcing the acceptability of QoS requests by implementing 1512 decisions based on the rules and languages of [RMK+98], would also 1513 be capable of providing the desired functionality. 1515 APPENDICES 1517 A. Pseudocode for the BF Based Pre-Computation Algorithm 1519 Note: The pseudocode below assumes a hop-by-hop forwarding approach in 1520 updating the neighbor field. The modifications needed to support 1521 explicit route construction are straightforward. The pseudocode 1522 also does not handle equal cost multi-paths for simplicity, but the 1523 modification needed to add this support are straightforward. 1525 Input: 1526 V = set of vertices, labeled by integers 1 to N. 1527 L = set of edges, labeled by ordered pairs (n,m) of vertex labels. 1528 s = source vertex (at which the algorithm is executed). 1529 For all edges (n,m) in L: 1530 * b(n,m) = available bandwidth (according to last received update) 1531 on interface associated with the edge between vertices n and m. 1532 * If(n,m) outgoing interface corresponding to edge (n,m) when n is 1533 a router. 1534 H = maximum hop-count (at most the graph diameter). 1536 Type: 1537 tab_entry: record 1538 bw = integer, 1539 neighbor = integer 1..N. 1541 Variables: 1542 TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry record, such 1543 that: 1544 TT[n,h].bw is the maximum available bandwidth (as known 1545 thus far) on a path of at most h hops between 1546 vertices s and n, 1547 TT[n,h].neighbor is the first hop on that path (a neighbor 1548 of s). It is either a router or the destination n. 1550 S_prev: list of vertices that changed a bw value in the TT table 1551 in the previous iteration. 1552 S_new: list of vertices that changed a bw value (in the TT table 1553 etc.) in the current iteration. 1555 The Algorithm: 1557 begin; 1559 for n:=1 to N do /* initialization */ 1560 begin; 1561 TT[n,0].bw := 0; 1562 TT[n,0].neighbor := null 1563 TT[n,1].bw := 0; 1564 TT[n,1].neighbor := null 1565 end; 1566 TT[s,0].bw := infinity; 1568 reset S_prev; 1569 for all neighbors n of s do 1570 begin; 1571 TT[n,1].bw := max( TT[n,1].bw, b[s,n]); 1572 if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n); 1573 /* need to make sure we are picking the maximum */ 1574 /* bandwidth path for routers that can be reached */ 1575 /* through both networks and point-to-point links */ 1576 if (n is a router) then 1577 S_prev := S_prev union {n} 1578 /* only a router is added to S_prev, */ 1579 /* if it is not already included in S_prev */ 1580 else /* n is a network: */ 1581 /* proceed with network--router edges, without */ 1582 /* counting another hop */ 1583 for all (n,k) in L, k <> s, do 1584 /* i.e., for all other neighboring routers of n */ 1585 begin; 1586 TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw ); 1587 /* In case k could be reached through another path */ 1588 /* (a point-to-point link or another network) with */ 1589 /* more bandwidth, we do not want to update TT[k,1].bw */ 1590 if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw ) 1591 /* If we have updated TT[k,1].bw by going through */ 1592 /* network n */ 1593 then TT[k,1].neighbor := If(s,n); 1594 /* neighbor is interface to network n */ 1595 if ( {k} not in S_prev) then S_prev := S_prev union {k} 1596 /* only routers are added to S_prev, but we again need */ 1597 /* to check they are not already included in S_prev */ 1598 end 1599 end; 1601 for h:=2 to H do /* consider all possible number of hops */ 1602 begin; 1603 reset S_new; 1604 for all vertices m in V do 1605 begin; 1606 TT[m,h].bw := TT[m,h-1].bw; 1607 TT[m,h].neighbor := TT[m,h-1].neighbor 1608 end; 1609 for all vertices n in S_prev do 1610 /* as shall become evident, S_prev contains only routers */ 1611 begin; 1612 for all edges (n,m) in L do 1613 if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then 1614 begin; 1615 TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]); 1616 TT[m,h].neighbor := TT[n,h-1].neighbor; 1617 if m is a router then S_new := S_new union {m} 1618 /* only routers are added to S_new */ 1619 else /* m is a network: */ 1620 /* proceed with network--router edges, without counting them as */ 1621 /* another hop */ 1622 for all (m,k) in L, k <> n, 1623 /* i.e., for all other neighboring routers of m */ 1624 if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then 1625 begin; 1626 /* Note: still counting it as the h-th hop, as (m,k) is a */ 1627 /* network--router edge */ 1628 TT[k,h].bw := min( TT[m,h].bw, b[m,k]); 1629 TT[k,h].neighbor := TT[m,h].neighbor; 1630 S_new := S_new union {k} 1631 /* only routers are added to S_new */ 1632 end 1633 end 1634 end; 1635 S_prev := S_new; 1636 /* the two lists can be handled by a toggle bit */ 1637 if S_prev=null then h=H+1 /* if no changes then exit */ 1638 end; 1640 end. 1642 B. On-Demand Dijkstra Algorithm for QoS Path Computation 1644 In the main text, we described an algorithm that allows 1645 pre-computation of QoS routes. However, it may be feasible in 1646 some instances, e.g., limited number of requests for QoS routes, 1647 to instead perform such computations on-demand, i.e., upon receipt 1648 of a request for a QoS route. The benefit of such an approach is 1649 that depending on how often recomputation of pre-computed routes is 1650 triggered, on-demand route computation can yield better routes by 1651 using the most recent link metrics available. Another benefit of 1652 on-demand path computation is the associated storage saving, i.e., 1653 there is no need for a QoS routing table. This is essentially the 1654 standard trade-off between memory and processing cycles. 1656 In this section, we briefly describe how a standard Dijkstra 1657 algorithm can, for a given destination and bandwidth requirement, 1658 generate a minimum hop path that can accommodate the required 1659 bandwidth and also has maximum bandwidth. Because the Dijkstra 1660 algorithm is already used in the current OSPF route computation, 1661 only differences from the standard algorithm are described. Also, 1662 while for simplicity we do not consider here zero-hop edges, the 1663 modification required for supporting them is straightforward. 1665 The algorithm essentially performs a minimum hop path computation, 1666 on a graph from which all edges, whose available bandwidth is less 1667 than that requested by the flow triggering the computation, have been 1668 removed. This can be performed either through a pre-processing step, 1669 or while running the algorithm by checking the available bandwidth 1670 value for any edge that is being considered (see the pseudocode that 1671 follows). Another modification to a standard Dijkstra based minimum 1672 hop count path computation, is that the list of equal cost next 1673 (previous) hops which is maintained as the algorithm proceeds, needs 1674 to be sorted according to available bandwidth. This is to allow 1675 selection of the minimum hop path with maximum available bandwidth. 1676 Alternatively, the algorithm could also be modified to, at each step, 1677 only keep among equal hop count paths the one with maximum available 1678 bandwidth. This would essentially amount to considering a cost that 1679 is function of both hop count and available bandwidth. 1681 Note: The pseudocode below assumes a hop-by-hop forwarding approach in 1682 updating the neighbor field. Addition of routes to stub networks is 1683 done in a second phase as usual. The modifications needed to support 1684 explicit route construction are straightforward. The pseudocode 1685 also does not handle equal cost multi-paths for simplicity, but the 1686 modifications needed to add this support are also easily done. 1688 Input: 1689 V = set of vertices, labeled by integers 1 to N. 1690 L = set of edges, labeled by ordered pairs (n,m) of vertex labels. 1691 s = source vertex (at which the algorithm is executed). 1692 For all edges (n,m) in L: 1693 * b(n,m) = available bandwidth (according to last received update) 1694 on interface associated with the edge between vertices n and m. 1695 * If(n,m) = outgoing interface corresponding to edge (n,m) when n is 1696 a router. 1697 d = destination vertex. 1698 B = requested bandwidth for the flow served. 1700 Type: 1701 tab_entry: record 1702 hops = integer, 1703 neighbor = integer 1..N, 1704 ontree = boolean. 1706 Variables: 1707 TT[1..N]: topology table, whose (n) entry is a tab_entry 1708 record, such that: 1709 TT[n].bw is the available bandwidth (as known 1710 thus far) on a shortest-path between 1711 vertices s and n, 1712 TT[n].neighbor is the first hop on that path (a neighbor 1713 of s). It is either a router or the destination n. 1714 S: list of candidate vertices; 1715 v: vertex under consideration; 1717 The Algorithm: 1719 begin; 1720 for n:=1 to N do /* initialization */ 1721 begin; 1722 TT[n].hops := infinity; 1723 TT[n].neighbor := null; 1724 TT[n].ontree := FALSE; 1725 end; 1726 TT[s].hops := 0; 1728 reset S; 1729 v:= s; 1730 while v <> d do 1731 begin; 1732 TT[v].ontree := TRUE; 1733 for all edges (v,m) in L and b(v,m) >= B do 1734 begin; 1735 if m is a router 1736 begin; 1737 if not TT[m].ontree then 1738 begin; 1739 /* bandwidth must be fulfilled since all links >= B */ 1740 if TT[m].hops > TT[v].hops + 1 then 1741 begin 1742 S := S union { m }; 1743 TT[m].hops := TT[v].hops + 1; 1744 TT[m].neighbor := v; 1745 end; 1746 end; 1747 end; 1748 else /* must be a network, iterate over all attached routers */ 1749 begin; /* each network -- router edge treated as zero hop edge */ 1750 for all (m,k) in L, k <> v, 1751 /* i.e., for all other neighboring routers of m */ 1752 if not TT[k].ontree and b(m,k) >= B then 1753 begin; 1754 if TT[k].hops > TT[v].hops then 1755 begin; 1756 S := S union { k }; 1757 TT[k].hops := TT[v].hops; 1758 TT[k].neighbor := v; 1759 end; 1760 end; 1761 end; 1762 end; /* of all edges from the vertex under consideration */ 1764 if S is empty then 1765 begin; 1766 v=d; /* which will end the algorithm */ 1767 end; 1768 else 1769 begin; 1770 v := first element of S; 1771 S := S - {v}; /* remove and store the candidate to consider */ 1772 end; 1773 end; /* from processing of the candidate list */ 1774 end. 1776 C. Precomputation Using Dijkstra Algorithm 1778 This appendix outlines a Dijkstra-based algorithm that allows 1779 pre-computation of QoS routes for all destinations and bandwidth 1780 values. The benefit of using a Dijkstra-based algorithm is a greater 1781 synergy with existing OSPF implementations. The solution to compute 1782 all ``best'' paths is to consecutively compute shortest path spanning 1783 trees starting from a complete graph and removing links with less 1784 bandwidth than the threshold used in the previous computation. This 1785 yields paths with possibly better bandwidth but of course more hops. 1786 Despite the large number of Dijkstra computations involved, several 1787 optimizations such as incremental spanning tree computation can be 1788 used and allow for efficient implementations in terms of complexity 1789 as well as storage since the structure of computed paths leans itself 1790 towards path compression [ST83]. Details including measurements and 1791 applicability studies can be found in [Prz95] and [BP95]. 1793 A variation of this theme is to trade the ``accuracy'' of the 1794 pre-computed paths, (i.e., the paths being generated may be of a 1795 larger hop count than needed) for the benefit of using a modified 1796 version of Dijkstra shortest path algorithm and also saving on 1797 some computations. This loss in accuracy comes from the need to 1798 rely on quantized bandwidth values, which are used when computing 1799 a minimum hop count path. In other words, the range of possible 1800 bandwidth values that can be requested by a new flow is mapped into 1801 a fixed number of quantized values, and minimum hop count paths are 1802 generated for each quantized value. For example, one could assume 1803 that bandwidth values are quantized as low, medium, and high, and 1804 minimum hop count paths are computed for each of these three values. 1805 A new flow is then assigned to the minimum hop path that can carry 1806 the smallest quantized value, i.e., low, medium, or high, larger than 1807 or equal to what it requested. We restrict our discussion here to 1808 this ``quantized'' version of the algorithm. 1810 Here too, we discuss the elementary case where all edges count as 1811 ``hops'', and note that the modification required for supporting 1812 zero-hop edges is straightforward. 1814 As with the BF algorithm, the algorithm relies on a routing table 1815 that gets built as the algorithm progresses. The structure of the 1816 routing table is as follows: 1818 The QoS routing table: 1820 - a K x Q matrix, where K is the number of vertices and Q is the 1821 number of quantized bandwidth values. 1823 - The (n;q) entry contains information that identifies the 1824 minimum hop count path to destination n, which is capable of 1825 accommodating a bandwidth request of at least bw[q] (the qth 1826 quantized bandwidth value). It consists of two fields: 1828 * hops: the minimal number of hops on a path between the 1829 source node and destination n, which can accommodate a 1830 request of at least bw[q] units of bandwidth. 1832 * neighbor: this is the routing information associated with 1833 the minimum hop count path to destination node n, whose 1834 available bandwidth is at least bw[q]. With a hop-by-hop 1835 routing approach, the neighbor information is simply the 1836 identity of the node adjacent to the source node on that 1837 path. 1839 The algorithm operates again on a directed graph where vertices 1840 correspond to routers and transit networks. The metric associated 1841 with each edge in the graph is as before the bandwidth available on 1842 the corresponding interface, where b(n;m) is the available bandwidth 1843 on the edge between vertices n and m. The vertex corresponding to 1844 the router where the algorithm is being run is selected as the source 1845 node for the purpose of path selection, and the algorithm proceeds to 1846 compute paths to all other nodes (destinations). 1848 Starting with the highest quantization index, Q, the algorithm 1849 considers the indices consecutively, in decreasing order. For each 1850 index q, the algorithm deletes from the original network topology all 1851 links (n;m) for which b(n;m) < bw[q], and then runs on the remaining 1852 topology a Dijkstra-based minimum hop count algorithm (10) between 1853 the source node and all other nodes (vertices) in the graph. Note 1854 that as with the Dijkstra used for on-demand path computation, the 1855 elimination of links such that b(n;m) < bw[q] could also be performed 1856 while running the algorithm. 1858 After the algorithm terminates, the q-th column in the routing table 1859 is updated. This amounts to recording in the hops field the hop 1860 count value of the path that was generated by the algorithm, and by 1861 updating the neighbor field. As before, the update of the neighbor 1862 field depends on the scope of the path computation. In the case 1863 of a hop-by-hop routing decision, the neighbor field is set to the 1864 identity of the node adjacent to the source node (next hop) on the 1865 path returned by the algorithm. However, note that in order to 1866 ensure that the path with the maximal available bandwidth is always 1867 chosen among all minimum hop paths that can accommodate a given 1868 quantized bandwidth, a slightly different update mechanism of the 1869 neighbor field needs to be used in some instances. Specifically, 1870 when for a given row, i.e., destination node n, the value of the 1871 hops field in column q is found equal to the value in column q+1 1872 (here we assume q= bw[r] do 1942 begin; 1943 if m is a router 1944 begin; 1945 if not TT[m,r].ontree then 1946 begin; 1947 /* bandwidth must be fulfilled since all links >= bw[r] */ 1948 if TT[m,r].hops > TT[v,r].hops + 1 then 1949 begin 1950 S := S union { m }; 1951 TT[m,r].hops := TT[v,r].hops + 1; 1952 TT[m,r].neighbor := v; 1953 end; 1954 end; 1955 end; 1956 else /* must be a network, iterate over all attached 1957 routers */ 1958 begin; 1959 for all (m,k) in L, k <> v, 1960 /* i.e., for all other neighboring routers of m */ 1961 if not TT[k,r].ontree and b(m,k) >= bw[r] then 1962 begin; 1963 if TT[k,r].hops > TT[v,r].hops + 2 then 1964 begin; 1965 S := S union { k }; 1966 TT[k,r].hops := TT[v,r].hops + 2; 1967 TT[k,r].neighbor := v; 1968 end; 1969 end; 1970 end; 1971 end; /* of all edges from the vertex under consideration */ 1972 end; /* from processing of the candidate list */ 1973 end; /* of ``quantize'' steps */ 1974 end. 1976 D. Explicit Routing Support 1978 As mentioned before, the scope of the path selection process can 1979 range from simply returning the next hop on the QoS path selected for 1980 the flow, to specifying the complete path that was computed, i.e., 1981 an explicit route. Obviously, the information being returned by the 1982 path selection algorithm differs in these two cases, and constructing 1983 it imposes different requirements on the path computation algorithm 1984 and the data structures it relies on. While the presentation of 1985 the path computation algorithms focused on the hop-by-hop routing 1986 approach, the same algorithms can be applied to generate explicit 1987 routes with minor modifications. These modifications and how they 1988 facilitate constructing explicit routes are discussed next. 1990 The general approach to facilitate construction of explicit routes 1991 is to update the neighbor field differently from the way it is done 1992 for hop-by-hop routing as described in Section 2.3. Recall that in 1993 the path computation algorithms the neighbor field is updated to 1994 reflect the identity of the router adjacent to the source node on 1995 the partial path computed. This facilitates returning the next hop 1996 at the source for the specific path. In the context of explicit 1997 routing, the neighbor information is updated to reflect the identity 1998 of the previous router on the path. 2000 In general, there can be multiple equivalent paths for a given hop 2001 count. Thus, the neighbor information is stored as a list rather 2002 than single value. Associated with each neighbor, additional 2003 information is stored to facilitate load balancing among these 2004 multiple paths at the time of path selection. Specifically, we store 2005 the advertised available bandwidth on the link from the neighbor to 2006 the destination in the entry. 2008 With this change, the basic approach used to extract the complete 2009 list of vertices on a path from the neighbor information in the QoS 2010 routing table is to proceed `recursively' from the destination to 2011 the origin vertex. The path is extracted by stepping through the 2012 precomputed QoS routing table from vertex to vertex, and identifying 2013 at each step the corresponding neighbor (precursor) information. The 2014 process is described as recursive since the neighbor node identified 2015 in one step becomes the destination node for table look up in the 2016 next step. Once the source router is reached, the concatenation of 2017 all the neighbor fields that have been extracted forms the desired 2018 explicit route. This applies to algorithms of Section 2.3.1 and 2019 Appendix C. If at a particular stage there are multiple neighbor 2020 choices (due to equal cost multi-paths), one of them can be chosen 2021 at random with a probability that is weighted, for example, by the 2022 associated bandwidth on the link from the neighbor to the (current) 2023 destination. 2025 Specifically, assume a new request to destination, say, d, and with 2026 bandwidth requirements B. The index of the destination vertex 2027 identifies the row in the QoS routing table that needs to be checked 2028 to generate a path. The row is then searched to identify a suitable 2029 path. If the Bellman-Ford algorithm of Section 2.3.1 was used, the 2030 search proceeds by increasing index (hop) count until an entry is 2031 found, say at hop count or column index of h, with a value of the bw 2032 field that is equal to or greater than B. This entry points to the 2033 initial information identifying the selected path. If the Dijkstra 2034 algorithm of Appendix C is used, the first quantized value qB such 2035 that qB >= B is first identified, and the associated column then 2036 determines the first entry in the QoS routing table that identifies 2037 the selected path. 2039 Once this first entry has been identified, reconstruction of the 2040 complete list of vertices on the path proceeds similarly, whether the 2041 table was built using the algorithm of Section 2.3.1 or Appendix C. 2042 Specifically, in both cases, the neighbor field in each entry points 2043 to the previous node on the path from the source node and with the 2044 same bandwidth capabilities as those associated with the current 2045 entry. The complete path is, therefore, reconstructed by following 2046 the pointers provided by the neighbor field of successive entries. 2048 In the case of the Bellman-Ford algorithm of Section 2.3.1, this 2049 means moving backwards in the table from column to column, using at 2050 each step the row index pointed to by the neighbor field of the entry 2051 in the previous column. Each time, the corresponding vertex index 2052 specified in the neighbor field is pre-pended to the list of vertices 2053 constructed so far. Since we start at column h, the process ends 2054 when the first column is reached, i.e., after h steps, at which 2055 point the list of vertices making up the path has been reconstructed. 2057 In the case of the Dijkstra algorithm of Appendix C, the backtracking 2058 process is similar although slightly different because of the 2059 different relation between paths and columns in the routing table, 2060 i.e., a column now corresponds to a quantized bandwidth value instead 2061 of a hop count. The backtracking now proceeds along the column 2062 corresponding to the quantized bandwidth value needed to satisfy the 2063 bandwidth requirements of the flow. At each step, the vertex index 2064 specified in the neighbor field is pre-pended to the list of vertices 2065 constructed so far, and is used to identify the next row index to 2066 move to. The process ends when an entry is reached whose neighbor 2067 field specifies the origin vertex of the flow. Note that since there 2068 are as many rows in the table as there are vertices in the graph, 2069 i.e., N, it could take up to N steps before the process terminates. 2071 Note that the identification of the first entry in the routing table 2072 is identical to what was described for the hop-by-hop routing case. 2073 However, as described in this section, the update of the neighbor 2074 fields while constructing the QoS routing tables, is being performed 2075 differently in the explicit and hop-by-hop routing cases. Clearly, 2076 two different neighbor fields can be kept in each entry and updates 2077 to both could certainly be performed jointly, if support for both 2078 explicit routing and hop-by-hop routing is needed. 2080 References 2082 [AGK99] G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation 2083 and performance meassurements of QoS routing extensions to 2084 OSPF. In Proceedings of Infocomm'99, page to appear, New 2085 York, NY, April 1999. 2087 [AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi. 2088 QoS routing: A performance perspective. In Proceedings of 2089 ACM SIGCOMM'98, Vancouver, Canada, October 1998. 2091 [Alm92] P. Almquist. Type of Service in the Internet Protocol 2092 Suite. INTERNET-RFC, July 1992. 2094 [AT98] G. Apostolopoulos and S. K. Tripathi. On reducing the 2095 processing cost of on-demand QoS path computation. In 2096 Proceedings of ICNP'98, pages 80--89, Austin, TX, October 2097 1998. 2099 [BP95] J.-Y. Le Boudec and T. Przygienda. A Route Pre-Computation 2100 Algorithm for Integrated Services Networks. Journal of 2101 Network and Systems Management, 3(4), 1995. 2103 [Car79] B. Carre. Graphs and Networks. Oxford University Press, 2104 ISBN 0-19-859622-7, Oxford, UK, 1979. 2106 [CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. 2107 Introduction to Algorithms. MIT Press, Cambridge, MA, 2108 1990. 2110 [Con] Merit GateD Consortium. The Gate Daemon (GateD) project. 2112 [GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. 2113 Freeman, San Francisco, 1979. 2115 [GKH97] R. Guerin, S. Kamat, and S. Herzog. QoS Path Management 2116 with RSVP. In Proceedings of the 2nd IEEE Global Internet 2117 Mini-Conference, Phoenix, AZ, November 1997. 2119 [GKR97] R. Guerin, S. Kamat, and E. Rosen. An extended RSVP 2120 routing interface. INTERNET-DRAFT, June 1997. work in 2121 progress. 2123 [GLG+97] Der-Hwa Gan, T. Li, R. Guerin, E. Rosen, and S. Kamat. 2124 Setting up reservations on explicit paths using RSVP. 2125 INTERNET-DRAFT, December 1997. work in progress. 2127 [GO97] R. Guerin and A. Orda. QoS-Based Routing in Networks 2128 with Inaccurate Information: Theory and Algorithms. In 2129 Proceedings of INFOCOM'97, pages 75--83, Kobe, Japan, April 2130 1997. 2132 [GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing 2133 Mechanisms and OSPF Extensions. In Proceedings of the 2nd 2134 IEEE Global Internet Mini-Conference, Phoenix, AZ, November 2135 1997. 2137 [KNB98] F. Baker K. Nichols, S. Blake and D. Black. Definition of 2138 the differentiated services field (DS field) in the IPv4 2139 and IPv6 headers. INTERNET-DRAFT, October 1998. work in 2140 progress. 2142 [LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with 2143 Uncertain Parameters. IEEE/ACM Transactions on Networking, 2144 6(6):768--778, December 1998. 2146 [Moy94] J. Moy. OSPF Version 2. INTERNET-RFC 1583, March 1994. 2148 [Moy98] J. Moy. OSPF Version 2. INTERNET-RFC 2328, April 1998. 2150 [Prz95] A. Przygienda. Link State Routing with QoS in ATM 2151 LANs. Ph.D. Thesis Nr. 11051, Swiss Federal Institute of 2152 Technology, April 1995. 2154 [RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, 2155 D. Verma, G. Powers, and R. Yavatkar. Schema for 2156 differentiated services and integrated services in 2157 networks. INTERNET-DRAFT, October 1998. work in progress. 2159 [RZB+97] R. Braden (Ed.), L. Zhang, S. Berson, S. Herzog, and 2160 S. Jamin. Resource reSerVation Protocol (RSVP) version 1, 2161 functional specification. INTERNET-DRAFT, June 1997. work 2162 in progress. 2164 [SPG97] S. Shenker, C. Partridge, and R. Guerin. Specification of 2165 Guaranteed Quality of Service -- RFC No. 2212. Internet 2166 RFC, November 1997. 2168 [ST83] D.D. Sleator and R.E. Tarjan. A Data Structure for Dynamic 2169 Trees. Journal of Computer Systems, 26, 1983. 2171 [Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989. 2173 [YPG97] R. Yavatkar, D. Pendarakis, and R. Guerin. A framework for 2174 policy-based admission control. INTERNET-DRAFT, November 2175 1997. work in progress. 2177 Authors' Address 2179 George Apostolopoulos 2180 IBM T.J. Watson Research Center 2181 P.O. Box 704 2182 Yorktown Heights, NY 10598 2183 georgeap@watson.ibm.com 2184 VOICE +1 914 784-6204 2185 FAX +1 914 784-6205 2187 Roch Guerin 2188 University Of Pennsylvania 2189 Department of Electrical Engineering, Rm 367 GRW 2190 200 South 33rd Street 2191 Philadelphia, PA 19104--6390 2192 guerin@ee.upenn.edu 2193 VOICE +1 215-898-9351 2195 Sanjay Kamat 2196 IBM T.J. Watson Research Center 2197 P.O. Box 704 2198 Yorktown Heights, NY 10598 2199 sanjay@watson.ibm.com 2200 VOICE +1 914 784-7402 2201 FAX +1 914 784-6205 2203 Ariel Orda 2204 Dept. Electrical Engineering 2205 Technion - I.I.T 2206 Haifa, 32000 - ISRAEL 2207 ariel@ee.technion.ac.il 2208 VOICE +011 972-4-8294646 2209 FAX +011 972-4-8323041 2211 Tony Przygienda 2212 Bell Labs, Lucent Technologies 2213 prz@dnrc.bell-labs.com 2214 VOICE +1 732 949-5936 2215 Doug Williams 2216 IBM T.J. Watson Research Center 2217 P.O. Box 704 2218 Yorktown Heights, NY 10598 2219 dougw@watson.ibm.com 2220 VOICE +1 914 784-5047 2221 FAX +1 914 784-6318