Internet Engineering Task Force R. Guerin/A. Orda/D. Williams INTERNET DRAFT IBM/Technion/IBM 5 November 1996 QoS Routing Mechanisms and OSPF Extensions draft-guerin-qos-routing-ospf-00.txt Status of This Memo This document is an Internet-Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months, and may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material, or to cite them other than as a ``working draft'' or ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the internet-drafts Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract This memo describes extensions to the OSPF protocol to support QoS routes. The focus of the document is on the algorithms used to compute QoS routes and on the necessary modifications to OSPF to support this function, e.g., the information needed, its format, how it is distributed, and how it is used by the QoS path selection process. Aspects related to how QoS routes are established and managed are also briefly discussed, but the development of detailed specifications is left for further study. The goal of this document is to identify a framework and possible approaches to allow deployment of QoS routing capabilities with the minimum possible impact to the existing routing infrastructure. Guerin,Orda,Williams Expires 10 May 1997 [Page i] Internet Draft QoS Routing Mechanisms 5 November 1996 Contents Status of This Memo i Abstract i 1. Introduction 1 1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 1 1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 2 2. Path Selection Information and Algorithms 3 2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Advertisement of Link State Information . . . . . . . . . 5 2.3. Path Selection Algorithms . . . . . . . . . . . . . . . . 6 2.3.1. Algorithm for exact pre-computed QoS paths . . . 7 2.3.2. Algorithm for on-demand computation of QoS paths 10 2.3.3. Algorithm for approximate pre-computed QoS paths 11 3. Establishment and Maintenance of QoS Routes 14 4. OSPF Protocol Enhancements 15 4.1. QoS -- Optional Capabilities . . . . . . . . . . . . . . 15 4.2. Packet Formats . . . . . . . . . . . . . . . . . . . . . 16 4.2.1. Router Links Advertisements . . . . . . . . . . . 16 4.2.2. Summary Link Advertisement . . . . . . . . . . . 17 4.3. Calculating the inter-area routes . . . . . . . . . . . . 18 4.4. Open Issues . . . . . . . . . . . . . . . . . . . . . . . 18 A. Construction of Path Information 19 A.1. Source routed paths . . . . . . . . . . . . . . . . . . . 19 A.2. Hop-by-Hop Routing . . . . . . . . . . . . . . . . . . . 21 B. Computational Complexity 21 C. Extension: Handling Propagation Delays 22 D. Zero-Hop Edges 23 E. Sample Path Establishment Scenario 24 F. Pseudocode for BF Algorithm 26 Guerin,Orda,Williams Expires 10 May 1997 [Page ii] Internet Draft QoS Routing Mechanisms 5 November 1996 1. Introduction In this document we describe a set of proposed additions to the OSPF routing protocol (the additions are built on top of OSPF V2) to support Quality-of-Service (QoS) routing in IP. In particular we discuss the metrics required to support QoS, the associated link advertisement mechanisms, the path selection algorithm, as well as aspects of route establishment (pinning and unpinning). Our goals are to define an approach which while achieving the goals of improving performance for QoS flows (likelihood to be routed on a path capable of providing the requested QoS), does so with the least possible impact on the existing OSPF protocol. Given the inherent complexity of QoS routing, achieving this goal obviously implies trading-off ``optimality'' for ``simplicity'', but we believe this to be required in order to facilitate deployment of QoS routing capabilities. 1.1. Overall Framework We consider a network (1) that supports both best-effort packets and packets with QoS guarantees. The way in which the network resources are split between the two classes is irrelevant to our proposal, except for the assumption that each QoS capable router in the network is able to dedicate some of its resources to satisfy the requirements of QoS packets. QoS capable routers are also assumed able to identify and advertise the amount of their resources that remain available for additional QoS flows. In addition, we limit ourselves to the case where all the routers involved support the QoS extensions described in this document, i.e., we do not consider the problem of establishing a route in an heterogeneous environment with routers that are QoS-capable and others that are not. Furthermore, in this document we focus on the case of unicast flows, although many of the additions we define are applicable to multicast flows as well. We assume that a flow with QoS requirements will specify them in some fashion that is accessible to the routing protocol. For example, this could correspond to the arrival of an RSVP [RZB+96] PATH message, whose TSpec is passed to routing together with the destination address. After processing such a request, the routing protocol returns a path that it deems the most suitable given the flow's requirements. Depending on the scope of the path selection ---------------------------- 1. In this document we commit the abuse of notation of calling a ``network'' the interconnection of routers and networks through which we attempt to acompute a QoS path. Guerin,Orda,Williams Expires 10 May 1997 [Page 1] Internet Draft QoS Routing Mechanisms 5 November 1996 process, this returned path could range from simply identifying the best next hop, i.e., a traditional hop-by-hop routing, to specifying all intermediate nodes to the destination, i.e., a source route. Note that this decision impacts the operation of the path selection algorithm as it translates into different requirements in order to construct and return the appropriate path information. Note also that extension to multicast paths will impact differently a source routed and a hop-by-hop approach. Once a suitable path has been identified, the flow is assigned to it (pinning) and remains assigned to it until it either releases the path (unpinning) or deems that it has become unsuitable, e.g., because of link failure or unavailability of the necessary resources. Note that resources reservation and/or accounting should help limit the frequency of the latter. In this document, we focus on the aspect of selecting an appropriate path based on information on link metrics and flow requirements. There are obviously many other aspects that need to be specified in order to define a complete proposal for QoS routing. Issues such as those mentioned above on the scope of the path selection process and when/how paths are pinned and unpinned, must certainly be addressed and they are briefly discussed in this draft during the exposition of the path selection algorithms and then more specifically in Section 3. The discussion of a complete solution to these problems is, however, deferred to [GOW96]. 1.2. Simplifying Assumptions In order to achieve our goal of a minimum impact to the existing protocol, we impose certain restrictions on the range of requirements the QoS path selection algorithm needs to deal with directly. Specifically, a policy scheme is used to a priori prune from the network, those portions that would be unsuitable given the requirements of the flow. This limits the ``optimization'' performed by the path selection to a containable set of parameters, which helps keep complexity at an acceptable level. Specifically, the path selection algorithm will focus on selecting a path that is capable of satisfying the bandwidth requirement of the flow, while at the same time trying to minimize the amount of network resources that need to be allocated to support the flow, i.e., minimize the number of hops used. This focus on bandwidth is adequate in most instances, but does not fully capture the complete range of potential QoS requirements. For example, a delay-sensitive flow of an interactive application could be put on a path using a satellite link, if that link provided a Guerin,Orda,Williams Expires 10 May 1997 [Page 2] Internet Draft QoS Routing Mechanisms 5 November 1996 direct path and had plenty of unused bandwidth. This would clearly not be a desirable choice. Our approach to preventing such poor choices, is to assign delay-sensitive flows to a policy that would eliminate from the network all links with high propagation delay, e.g., satellite links, before invoking the path selection algorithm. In general, each existing policy would present to the path selection algorithm its correspondingly pruned network topology, and the same algorithm would then be used to generate an appropriate path. Another important aspect in minimizing the impact of QoS routing is to develop a solution that has the smallest possible computing overhead. Additional computations are unavoidable, but it is desirable to keep the total cost of QoS routing at a level comparable to that of traditional routing algorithms. In this document, we describe several alternatives to the path selection algorithm, that represent different trade-offs between simplicity, accuracy, and computational cost. In particular, we specify algorithms that generate exact solutions based either on pre-computations or on-demand computations. We also describe algorithms that allow pre-computations at the cost of some loss in accuracy, but with possibly lower complexity or greater ease of implementation. It should be mentioned, that while several alternative algorithms are described in this document, the same algorithm needs to be used consistently within a given routing domain. This requirement can be relaxed when a source routed approach is used as the responsibility of selecting a QoS path lies with a single entity, the origin of the request, which ensures consistency. Hence, it may then be possible for each router to use a different path selection algorithm. However, in general, the use of a common path selection algorithm is recommended, if not necessary, for proper operation. The rest of this document is structured as follows. In Section 2, we describe the path computation process and the information that it relies on. In Section 3 we briefly review some issues associated with path management and their implications. As mentioned earlier, detailed discussions on these topics is deferred to [GOW96]. In Section 4, we go over the extensions to OSPF that are needed in order to support the path selection process of Section 2. Finally, several appendices provide details on the different path selection algorithms described in Section 2, and outline several additional work items. 2. Path Selection Information and Algorithms This section describes several path selection algorithms that can be used to generate QoS capable routes based on different trade-offs between accuracy, computational complexity, and ease of implementation. In addition, the section also covers aspects related Guerin,Orda,Williams Expires 10 May 1997 [Page 3] Internet Draft QoS Routing Mechanisms 5 November 1996 to the type of information, i.e., metrics, on which the algorithms operate, and how that information is made available, i.e., link state advertisements. The discussion on these topics is of a generic nature, and OSPF specific details are provided in Section 4. 2.1. Metrics As stated earlier, the process of selecting a path that can satisfy the QoS requirements of a new flow relies on both the knowledge of the flow's requirements and characteristics, and information about the availability of resources in the network. In addition, for purposes of efficiency, it is also important for the algorithm to account for the amount of resources the network has to allocate in order to support a new flow. In general, the network prefers to select the ``cheapest'' among all paths suitable for a new flow. Furthermore, the network may also decide not to accept a new flow for which it identified a feasible path, if it deems the cost of the path to be too high. Accounting for these aspects involves several metrics on which the path selection process is based. They include: - Link available bandwidth: As mentioned earlier, we assume that most QoS requirements are derivable from a rate-related quantity, termed ``bandwidth''. We further assume that associated with each link is a maximal bandwidth value, e.g., the link physical bandwidth or some fraction thereof that has been set aside for QoS flows. Since for a link to be capable of accepting a new flow with given bandwidth requirements, at least that much bandwidth must be still available on the link, the relevant link metric is, therefore, the (current) amount of available (i.e., unallocated) bandwidth. - Hop-count: This quantity is used as a measure of the path cost to the network. A path with a smaller number of hops (that can support a requested connection) is preferable, since it consumes less network resources. While as a general rule each edge in the graph on which the path is computed should be counted as one hop, some edges, specifically those that connect a transit network to a router, should not be taken into account. (See Appendix D for a detailed explanation.) - Policy: As previously discussed, policies are used to identify the set of links in the network that need to be considered when running the path selection algorithm. In particular, policies are used to prune from the network links that are incompatible, performance or characteristics wise, with the requirements of a flow. A specific policy example of special importance, is the elimination of high latency links when considering path Guerin,Orda,Williams Expires 10 May 1997 [Page 4] Internet Draft QoS Routing Mechanisms 5 November 1996 selection for delay sensitive flows. The use of policies to handle specific requirements allows considerable simplification in the optimization task to be performed by the path selection algorithm. 2.2. Advertisement of Link State Information It is assumed that each router maintains an updated database of the network topology, including the current state (available bandwidth) of each link. As described in Section 4, the distribution of link state (metrics) information is based on extending OSPF mechanisms. However, in addition to how link state information is distributed, another important aspect is when such distribution is to take place. Ideally, one would want routers to have the most current view of the bandwidth available on all links in the network, so that they can make the most accurate decision on which path to select. Unfortunately, this then calls for very frequent updates, e.g., close to every time the available bandwidth of a link changes, which is neither scalable nor practical. Alternatively, one may opt for a simple mechanism based on periodic updates, where the period of updates is determined based on a tolerable corresponding load on the network and the routers. The main disadvantage of such an approach is that major changes in the bandwidth available on a link could remain unknown for a full period and, therefore, result in many incorrect routing decisions. As a result, we propose to use a simple hybrid update mechanism, that attempts to reconcile accuracy of link state information with the need for the smallest possible overhead. Periodic updates are used, say every T seconds, to notify nodes of any change of more than ffi in the available bandwidth of a link, and event-driven updates are generated immediately whenever the change in available link bandwidth since the last update exceeds . The values for T, ffi, and depend on network size, link speed, processing capabilities, and overall traffic patterns, but typical values would be: T 30sec, ffi 10%, 40%. Note that implicit in the above description is the the fact that regardless of bandwidth changes, we also impose a minimum interval between consecutive updates, e.g., we do not allow any particular LSA to get updated more than once every MinLSInterval (5) seconds, in order to prevent the possibility of overload. Guerin,Orda,Williams Expires 10 May 1997 [Page 5] Internet Draft QoS Routing Mechanisms 5 November 1996 2.3. Path Selection Algorithms There are several aspects to the path selection algorithms. The main ones include the optimization criteria it relies on, the exact topology on which it is run, and when it is invoked. As mentioned before, invocation of the path selection algorithm can be either per flow, or when warranted by changes in link states when the algorithm used allows precomputation of paths (more on this below). The topology on which the algorithm is run is, as with the standard OSPF path selection, a directed graph where vertices (2) consist of routers and networks (transit vertices) as well as stub networks (non-transit vertices). When computing a path, stub networks are added as a post-processing step, which is essentially similar to what is done with the current OSPF routing protocol. In addition, for each policy supported on a router, the topology used by the path selection algorithm is correspondingly pruned to reflect the constraints imposed by the policy, and in some instances the flow requirements. The optimization criteria used by the path selection are reflected in the costs associated with each interface in the topology and how those costs are accounted for in the algorithm itself. As mentioned before, the cost of a path is a function of both its hop count and the amount of available bandwidth. As a result, each interface has associated with it a metric, that corresponds to the amount of bandwidth which remains available on this interface. This metric is combined with hop count information to provide a cost value, in a manner that depends on the exact form of the path selection algorithm. It will, therefore, be detailed in the corresponding sections below, but all the different alternatives that are described share a common goal. That is, they all aim at picking a path with the minimum possible number of hops among those that can support the requested bandwidth. When several such paths are available, the preference is for the path whose available bandwidth (i.e., the smallest value on any of the links in the path) is maximal. The rationale for the above rule is the following: we focus on feasible paths (as accounted by the available bandwidth metric) that consume a minimal amount of network resources (as accounted by the hop-count metric); and the rule for selecting among these paths aims at balancing load as well as maximizing the likelihood that the required bandwidth will indeed be available. ---------------------------- 2. In this document, we use the terms node and vertex interchangeably. Guerin,Orda,Williams Expires 10 May 1997 [Page 6] Internet Draft QoS Routing Mechanisms 5 November 1996 It should be noted that standard routing algorithms are typically single objective optimizations, i.e., they may minimize the hop-count, or maximize the path bandwidth, but not both. Double objective path optimization is a more complex task, and, in general, it is an intractable problem [GJ79]. Nevertheless, as we will see, because of the specific nature of the two objectives being optimized (bandwidth and hop count), the complexity of our proposed algorithm(s) is competitive with even that of standard single-objective algorithms. 2.3.1. Algorithm for exact pre-computed QoS paths In this section, we describe a path selection algorithm, that for a given network topology and link metrics (available bandwidth) allows us to pre-compute all possible QoS paths, and also has a reasonably low computational complexity. Specifically, the algorithm allows us to pre-compute for any destination a minimum hop count path with maximum bandwidth, and has a computational complexity comparable to that of a standard shortest path algorithm (3). The path selection algorithm is based on a Bellman-Ford (BF) shortest path algorithm, which is adapted to compute paths of maximum available bandwidth for all hop counts. It is a property of the BF algorithm that, at its h-th iteration, it identifies the optimal (in our context: maximal bandwidth) path between the source and each destination, among paths of at most h hops. In other words, the cost of a path is a function of its available bandwidth, i.e., the smallest available bandwidth on all links of the path, and finding a minimum cost path amounts to finding a maximum bandwidth path. However, we also take advantage of the fact that the BF algorithm progresses by increasing hop count, to essentially get for free the hop count of a path as a second optimization criteria. Specifically, at the kth (hop count) iteration of the algorithm, the maximum bandwidth available to all destinations on a path of no more than k hops is recorded (together with the corresponding routing information). After the algorithm terminates, this information enables us to identify for all destinations and bandwidth requirements, the path with the smallest possible number of hops and sufficient bandwidth to accommodate the new request. Furthermore, this path is also the one with the maximal available bandwidth among all the feasible paths with this minimum number of hops. This is ---------------------------- 3. See Appendix B for a more comprehensive discussion on the aspect of computational complexity. Guerin,Orda,Williams Expires 10 May 1997 [Page 7] Internet Draft QoS Routing Mechanisms 5 November 1996 because for any hop count, the algorithm always selects the one with maximum available bandwidth. We now proceed with a more detailed description of the algorithm and the data structure used to record routing information, i.e., the QoS routing table that gets built as the algorithm progresses (pseudo-code for the algorithm can be found in Appendix F). As mentioned before, the algorithm operates on a directed graph consisting only of transit vertices (routers and networks), with stub-networks subsequently added to the path(s) generated by the algorithm. The metric associated with each edge in the graph is the bandwidth available on the corresponding interface. Let us denote by bn;mthe available bandwidth on the edge between vertices n and m. The vertex corresponding to the router where the algorithm is being run, i.e., the computing router, is denoted as the ``source node'' for the purpose of path selection. The algorithm proceeds to pre-compute paths from this source node to all possible destination networks and for all possible bandwidth values. At each (hop count) iteration, intermediate results are recorded in a QoS routing table, which has the following structure: The QoS routing table: - a Kx H matrix, where K is the number of destinations (vertices in the graph) and H is the maximal allowed (or possible) number of hops for a path. - The (n;h) entry is built during the hth iteration (hop count value) of the algorithm, and consists of two fields: * bw: the maximum available bandwidth, on a path of at most h hops between the source node (router) and destination node n; * neighbor: this is the routing information associated with the h (or less) hops path to destination node n, whose available bandwidth is bw. The specific nature of this information depends on the scope of the path being selected, i.e., is it simply a next hop or is a complete source route being specified. In both cases, this information is constructed and recorded at each iteration of the algorithm, but it is obtained and used differently. + When the scope of the path being selected is simply the next hop, i.e., hop-by-hop path selection, the neighbor information is simply the identity of the node adjacent to the source node on that path. As a rule, the ``neighbor'' node must be a router and not a network (see Guerin,Orda,Williams Expires 10 May 1997 [Page 8] Internet Draft QoS Routing Mechanisms 5 November 1996 Appendix D), the only exception being the case that the network is the destination node (and the selected path is the single edge interconnecting the source to it). + When the path being selected is a complete source route, the neighbor information is the previous router (4), i.e., preceding the destination node n, on that path. Next, we provide additional details on the operation of the algorithm and how the entries in the routing table are being updated as the algorithm proceeds. For simplicity, we first describe the simpler case where all edges count as ``hops'', and later explain how zero-hop edges (see Appendix D) are handled. When the algorithm is invoked, the routing table is first initialized with all bw fields set to 0 and neighbor fields cleared. Next, the entries in the first column (which corresponds to one-hop paths) of the neighbors of the computing router are modified in the following way: the bw field is set to the value of the available bandwidth on the direct edge from the source. Modification of the neighbor field depends on the scope of path selection. For next-hop routing, it is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path. For source-routing, it is set to the identity of the computing router itself. Afterwards, the algorithm iterates for at most H iterations (considering the above initial iteration as the first). H can be either the maximum possible hop count of any path, i.e., an implicit value, or it can be set explicitly in order to limit path lengths to some maximum value (5) to better control worst case complexity. At iteration h, we first copy column h - 1 into column h. In addition, the algorithm keeps a list of nodes that changed their bw value in the previous iteration, i.e., during the h- 1-st iteration. The algorithm then looks at each link (n;m) and checks the maximal available bandwidth on an h-hop path to node m whose final hop is that link. This amounts to taking the minimum between the bw field in entry (n;h -1) and the link metric value bn;m kept in the topology database. If this value is higher than the present value of the bw field in entry (m;h), then a better (larger bw value) path has been found for destination m and with h hops. The bw field of entry ---------------------------- 4. See Appendix A for details on how the complete source route is constructed based on the neighbor information kept in the table. 5. This maximum value should be larger than the length of the minimum hop-count path to any node in the graph. Guerin,Orda,Williams Expires 10 May 1997 [Page 9] Internet Draft QoS Routing Mechanisms 5 November 1996 (m;h) is then updated to reflect this new value. In the case of next-hop routing, the neighbor field of entry (m;h) is set to the same value as in entry (n;h - 1). This records the identity of the first hop (next hop from the source) on the best path identified thus far for destination m and with h (or less) hops. In the case of source routing, the neighbor field of entry (m;h) is set to the identity of node n. This records the identity of the previous hop on the best path identified thus far for destination m and with h (or less) hops. As described in Appendix A, this allows recursive construction of the complete source route simply by back-tracking from entry to entry in the table. We conclude by describing how zero-hop edges are handled. At each iteration h (starting with the first), whenever an entry (m;h) is modified, it is checked whether there are zero-cost edges (m;k) emerging from node m, which is the case when m is a transit network (see Appendix D). In that case, we attempt to improve the entry of node k that corresponds to the h-th hop, i.e., entry (k;h) (rather than entry (k;h + 1)), since the edge (m;k) should not count as an additional hop. As with the regular operation of the algorithm, this amounts to taking the minimum between the bw field in entry (m;h) and the link metric value bm;kkept in the topology database. If this value is higher than the present value of the bw field in entry (k;h), then the bw field of entry (k;h) is updated to this new value. In the case of next-hop routing, the neighbor field of entry (k;h) is set, as usual, to the same value as in entry (m;h) (which is also the value in entry (n;h - 1)). In the case of source routing, the neighbor field of entry (k;h) is set to the identity of node n. This records the identity of the previous router on the identified path. Note that while for simplicity of the exposition, the issue of equal cost, i.e., same hop count and available bandwidth, is not detailed in the above description, it is straightforward to add this support. It only requires that the neighbor field be expanded to record the list of next (previous) hops, when multiple equal cost paths are present. 2.3.2. Algorithm for on-demand computation of QoS paths In the previous section, we described an algorithm that allows pre-computation of QoS routes. However, it may be feasible in some instances, e.g., limited number of requests for QoS routes, to instead perform such computations on-demand, i.e., upon receipt of a request for a QoS route. The benefit of such an approach is that depending on how often recomputation of pre-computed routes is triggered, on-demand route computation can yield better routes by using the most recent link metrics available. Another benefit of Guerin,Orda,Williams Expires 10 May 1997 [Page 10] Internet Draft QoS Routing Mechanisms 5 November 1996 on-demand path computation is the associated storage saving, i.e., there is no need for a QoS routing table. This is essentially the standard trade-off between memory and processing cycles. In this section, we briefly describe how a standard Dijkstra algorithm can, for a given destination and bandwidth requirement, generate a minimum hop path that can accommodate the required bandwidth and also has maximum bandwidth. Because the Dijkstra algorithm is already used in the current OSPF route computation, only differences from the standard algorithm are described. Also, while for simplicity we do not consider here zero-hop edges (see Appendix D), the modification required for supporting them is straightforward. The algorithm essentially performs a minimum hop path computation, on a graph from which all edges, whose available bandwidth is less than that requested by the flow triggering the computation, have been removed. This can be performed either through a pre-processing step, or while running the algorithm by checking the available bandwidth value for any edge that is being considered. Another modification to a standard Dijkstra based minimum hop count path computation, is that the list of equal cost next (previous) hops which is maintained as the algorithm proceeds, needs to be sorted according to available bandwidth. This is to allow selection of the minimum hop path with maximum available bandwidth. Alternatively, the algorithm could also be modified to, at each step, only keep among equal hop count paths the one with maximum available bandwidth. This would essentially amount to considering a cost that is function of both hop count and available bandwidth. 2.3.3. Algorithm for approximate pre-computed QoS paths This section outlines a Dijkstra-based algorithm that allows pre-computation of QoS routes for all destinations and bandwidth values. The benefit of using a Dijkstra-based algorithm is a greater synergy with existing OSPF implementations. The cost is, however, a loss in the ``accuracy'' of the pre-computed paths, i.e., the paths being generated may be of a larger hop count than needed. This loss in accuracy comes from the need to rely on quantized bandwidth values, that are used when computing a minimum hop count path. In other words, the range of possible bandwidth values that can be requested by a new flow is mapped into a fixed number of quantized values, and minimum hop count paths are generated for each quantized value. For example, one could assume that bandwidth values are quantized as low, medium, and high, and minimum hop count paths are computed for each of these three values. A new flow is then assigned to the minimum hop path that can carry the smallest quantized Guerin,Orda,Williams Expires 10 May 1997 [Page 11] Internet Draft QoS Routing Mechanisms 5 November 1996 value, i.e., low, medium, or high, larger than or equal to what it requested. Here too, we discuss the elementary case where all edges count as ``hops'', and note that the modification required for supporting zero-hop edges is straightforward. As with the BF algorithm, the algorithm relies on a routing table that gets built as the algorithm progresses. The structure of the routing table is as follows: The QoS routing table: - a K x Q matrix, where K is the number of vertices and Q is the number of quantized bandwidth values. - The (n;q) entry contains information that identifies the minimum hop count path to destination n, that is capable of accommodating a bandwidth request of at least bw[q] (the qth quantized bandwidth value). It consists of two fields: * hops: the minimal number of hops on a path between the source node and destination n, that can accommodate a request of at least bw[q] units of bandwidth. * neighbor: this is again the routing information associated with the minimum hop count path to destination node n, whose available bandwidth is at least bw[q]. As before, the specific nature of this information depends on the scope of the path being selected. + When the scope of the path being selected is simply the next hop, i.e., hop-by-hop path selection, the neighbor information is simply the identity of the node adjacent to the source node on that path. + When the path being selected is a complete source route, the neighbor information is the previous node (6), i.e., preceding the destination node n, on that path. The algorithm operates again on a directed graph where vertices correspond to routers and transit networks. The metric associated with each edge in the graph is as before the bandwidth available on ---------------------------- 6. See Appendix A for details on how the complete source route is constructed based on the neighbor information kept in the table. Guerin,Orda,Williams Expires 10 May 1997 [Page 12] Internet Draft QoS Routing Mechanisms 5 November 1996 the corresponding interface, where bn;mis the available bandwidth on the edge between vertices n and m. The vertex corresponding to the router where the algorithm is being run is selected as the source node for the purpose of path selection, and the algorithm proceeds to compute paths to all other nodes (destinations). Starting with the highest quantization index, Q, the algorithm considers the indices consecutively, in decreasing order. For each index q, the algorithm deletes from the original network topology all links (n;m) for which bn;m< bw[q], and then runs on the remaining topology a Dijkstra-based minimum hop count algorithm (7) between the source node and all other nodes (vertices) in the graph. Note that as with the Dijkstra used for on-demand path computation, the elimination of links such that bn;m < bw[q] could also be performed while running the algorithm. After the algorithm terminates, the q-th column in the routing table is updated. This amounts to recording in the hops field the hop count value of the path that was generated by the algorithm, and by updating the neighbor field. As before, the update of the neighbor field depends on the scope of the path computation. In the case of a hop-by-hop routing decision, the neighbor field is set to the identity of the node adjacent to the source node (next hop) on the path returned by the algorithm. Conversely, if the algorithm is expected to generate a complete source route, the neighbor field is set to the predecessor of the destination node on the path returned by the algorithm. However, note that in order to ensure that the path with the maximal available bandwidth is always chosen among all minimum hop paths that can accommodate a given quantized bandwidth, a slightly different update mechanism of the neighbor field needs to be used in some instances. Specifically, when for a given row, i.e., destination node n, the value of the hops field in column q is found equal to the value in column q+1 (here we assume q s, do /* i.e., for all other neighboring routers of n */ begin; TT[k,1].bw := min( TT[n,1].bw, b[n,k]); TT[k,1].neighbor := k; /* first neighbor in a multi-hop path is a router */ S_prev := S_prev union {k} /* only routers are added to S_prev */ end end; for h:=2 to H do /* consider all possible number of hops */ begin; reset S_new; for all vertices m in V do begin; TT[m,h].bw := TT[m,h-1].bw; TT[m,h].neighbor := TT[m,h-1].neighbor Guerin,Orda,Williams Expires 10 May 1997 [Page 27] Internet Draft QoS Routing Mechanisms 5 November 1996 end; for all vertices n in S_prev do /* as shall become evident, S_prev contains only routers */ begin; for all edges (n,m) in L do if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then begin; TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]); TT[m,h].neighbor := TT[n,h-1].neighbor; if m is a router then S_new := S_new union {m} /* only routers are added to S_new */ else /* m is a network: */ /* proceed with network--router edges, without counting them as */ /* another hop */ for all (m,k) in L, k <> n, /* i.e., for all other neighboring routers of m */ if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then begin; /* Note: still counting it as the h-th hop, as (m,k) is a */ /* network--router edge */ TT[k,h].bw := min( TT[m,h].bw, b[m,k]); TT[k,h].neighbor := TT[m,h].neighbor; S_new := S_new union {k} /* only routers are added to S_new */ end end end; S_prev := S_new; /* the two lists can be handled by a toggle bit */ if S_prev=null then h=H+1 /* if no changes then exit */ end; end. References [BG92] D. Bertsekas and R. G. Gallager. Data Networks. Prentice Hall, Englewood Cliffs, NJ, 2nd edition, 1992. [CGR94] B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest Paths Algorithms: Theory and Experimental Evaluation. In Proceedings of the 5th Annual ACM SIAM Symposium on Discrete Algorithms, pages 516--525, Arlington, VA, January 1994. Guerin,Orda,Williams Expires 10 May 1997 [Page 28] Internet Draft QoS Routing Mechanisms 5 November 1996 [CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990. [GGPS96] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan. Efficient Network QoS Provisioning Based on per Node Traffic Shaping. IEEE/ACM Transactions on Networking, 4(4):482--501, August 1996. [GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979. [GOW96] R. Guerin, A. Orda, and D. Williams. Establishment and management of QoS routes. Research report, IBM, T. J. Watson Research Center, 1996. (work in progress). [Her96] S. Herzog. RSVP Extensions for Policy Control. (draft-ietf-rsvp-policy-ext-01.[ps,txt]. Internet Draft, November 1996. [PG94] A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Multiple Node Case. IEEE/ACM Transactions on Networking, 2:137--150, 1994. [RZB+96] R. Braden (Ed.), L. Zhang, S. Berson, S. Herzog, and S. Jamin. Resource reSerVation Protocol (RSVP) version 1, functional specification (draft-ietf-rsvp-spec-13.ps). INTERNET-DRAFT, Internet Engineering Task Force - RSVP WG, July 1996. Authors' Address Roch Guerin IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598 guerin@watson.ibm.com VOICE +1 914 784-7038 FAX +1 914 784-6318 Ariel Orda Dept. Electrical Engineering Technion - I.I.T Haifa, 32000 - ISRAEL Guerin,Orda,Williams Expires 10 May 1997 [Page 29] Internet Draft QoS Routing Mechanisms 5 November 1996 ariel@ee.technion.ac.il VOICE +011 972-4-8294646 FAX +011 972-4-8323041 Doug Williams IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598 dougw@watson.ibm.com VOICE +1 914 784-5047 FAX +1 914 784-6318 Guerin,Orda,Williams Expires 10 May 1997 [Page 30]