diff options
Diffstat (limited to 'doc/rfc/rfc2676.txt')
| -rw-r--r-- | doc/rfc/rfc2676.txt | 2803 |
1 files changed, 2803 insertions, 0 deletions
diff --git a/doc/rfc/rfc2676.txt b/doc/rfc/rfc2676.txt new file mode 100644 index 0000000..7cd3cce --- /dev/null +++ b/doc/rfc/rfc2676.txt @@ -0,0 +1,2803 @@ + + + + + + +Network Working Group G. Apostolopoulos +Request for Comments: 2676 D. Williams +Category: Experimental IBM + S. Kamat + Lucent + R. Guerin + UPenn + A. Orda + Technion + T. Przygienda + Siara Systems + August 1999 + + + QoS Routing Mechanisms and OSPF Extensions + +Status of this Memo + + This memo defines an Experimental Protocol for the Internet + community. It does not specify an Internet standard of any kind. + Discussion and suggestions for improvement are requested. + Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (1999). All Rights Reserved. + +Abstract + + This memo describes extensions to the OSPF [Moy98] protocol to + support QoS routes. The focus of this 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. 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. + + In addition, experience from an implementation of the proposed + extensions in the GateD environment [Con], along with performance + measurements is presented. + + + + + + + + +Apostolopoulos, et al. Experimental [Page 1] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +Table of Contents + + 1. Introduction 3 + 1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3 + 1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5 + 2. Path Selection Information and Algorithms 7 + 2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7 + 2.2. Advertisement of Link State Information . . . . . . . . . 8 + 2.3. Path Selection . . . . . . . . . . . . . . . . . . . . .10 + 2.3.1. Path Computation Algorithm . . . . . . . . . . .11 + 3. OSPF Protocol Extensions 16 + 3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . .17 + 3.2. Encoding Resources as Extended TOS . . . . . . . . . . .17 + 3.2.1. Encoding bandwidth resource . . . . . . . . . . .19 + 3.2.2. Encoding Delay . . . . . . . . . . . . . . . . .21 + 3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . .21 + 3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22 + 3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22 + 4. A Reference Implementation based on GateD 22 + 4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22 + 4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23 + 4.2.1. Design Objectives and Scope . . . . . . . . . . .23 + 4.2.2. Architecture . . . . . . . . . . . . . . . . . .24 + 4.3. Major Implementation Issues . . . . . . . . . . . . . . .25 + 4.4. Bandwidth and Processing Overhead of QoS Routing . . . .29 + 5. Security Considerations 32 + A. Pseudocode for the BF Based Pre-Computation Algorithm 33 + B. On-Demand Dijkstra Algorithm for QoS Path Computation 36 + C. Precomputation Using Dijkstra Algorithm 39 + D. Explicit Routing Support 43 + Endnotes 45 + References 46 + Authors' Addresses 48 + Full Copyright Statement 50 + + + + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 2] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +1. Introduction + + In this document, we describe a set of proposed additions to the OSPF + routing protocol (these additions have been implemented on top of the + GateD [Con] implementation of OSPF V2 [Moy98]) to support Quality- + of-Service (QoS) routing in IP networks. Support for QoS routing can + be viewed as consisting of three major components: + + 1. Obtain the information needed to compute QoS paths and select a + path capable of meeting the QoS requirements of a given request, + + 2. Establish the path selected to accommodate a new request, + + 3. Maintain the path assigned for use by a given request. + + Although we touch upon aspects related to the last two components, + the focus of this document is on the first one. In particular, we + discuss the metrics required to support QoS, the extension to the + OSPF link state advertisement mechanism to propagate updates of QoS + metrics, and the modifications to the path selection to accommodate + QoS requests. The goal of the extensions described in this document + is to improve performance for QoS flows (likelihood to be routed on a + path capable of providing the requested QoS), with minimal impact on + the existing OSPF protocol and its current implementation. 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. + + In addition to describing the proposed extensions to the OSPF + protocol, this document also reports experimental data based on + performance measurements of an implementation done on the GateD + platform (see Section 4). + +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, 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 capable of identifying + and advertising resources that remain available to new 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 a + heterogeneous environment where some routers are QoS-capable and + others are not. Furthermore, in this document, we focus on the case + + + +Apostolopoulos, et al. Experimental [Page 3] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + 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 specifies them in some + fashion that is accessible to the routing protocol. For example, + this could correspond to the arrival of an RSVP [RZB+97] PATH + message, whose TSpec is passed to routing together with the + destination address. After processing such a request, the routing + protocol returns the path that it deems the most suitable given the + flow's requirements. Depending on the scope of the path selection + process, this returned path could range from simply identifying the + best next hop, i.e., a hop-by-hop path selection model, to specifying + all intermediate nodes to the destination, i.e., an explicit route + model. The nature of the path being returned impacts the operation + of the path selection algorithm as it translates into different + requirements for constructing and returning the appropriate path + information. However, it does not affect the basic operation of the + path selection algorithm (2). + + For simplicity and also because it is the model currently supported + in the implementation (see Section 4 for details), in the rest of + this document we focus on the hop-by-hop path selection model. The + additional modifications required to support an explicit routing + model are discussed in appendix D, but are peripheral to the main + focus of this document which concentrates on the specific extensions + to the OPSF protocol to support computation of QoS routes. + + In addition to the problem of selecting a QoS path and possibly + reserving the corresponding resources, one should note that the + successful delivery of QoS guarantees requires that the packets of + the associated "QoS flow" be forwarded on the selected path. This + typically requires the installation of corresponding forwarding state + in the router. For example, with RSVP [RZB+97] flows a classifier + entry is created based on the filter specs contained in the RESV + message. In the case of a Differentiated Service [KNB98] setting, + the classifier entry may be based on the destination address (or + prefix) and the corresponding value of the DS byte. The mechanisms + described in this document are at the control path level and are, + therefore, independent of data path mechanisms such as the packet + classification method used. Nevertheless, it is important to notice + that consistent delivery of QoS guarantees implies stability of the + data path. In particular, while it is possible that after a path is + first selected, network conditions change and result in the + appearance of "better" paths, such changes should be prevented from + unnecessarily affecting existing paths. In particular, switching + over to a new (and better) path should be limited to specific + conditions, e.g., when the initial selection turns out to be + inadequate or extremely "expensive". This aspect is beyond the scope + + + +Apostolopoulos, et al. Experimental [Page 4] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + of QoS routing and belongs to the realm of path management, which is + outside the main focus of this document. However, because of its + potentially significant impact on the usefulness of QoS routing, we + briefly outline a possible approach to path management. + + Avoiding unnecessary changes to QoS paths requires that state + information be maintained for each QoS path after it has been + selected. This state information is used to track the validity of + the path, i.e., is the current path adequate or should QoS routing be + queried again to generate a new and potentially better path. We say + that a path is "pinned" when its state specifies that QoS routing + need not be queried anew, while a path is considered "un-pinned" + otherwise. The main issue is then to define how, when, and where + path pinning and un-pinning is to take place, and this will typically + depend on the mechanism used to request QoS routes. For example, + when the RSVP protocol is the mechanism being used, it is desirable + that path management be kept as synergetic as possible with the + existing RSVP state management. In other words, pinning and un- + pinning of paths should be coordinated with RSVP soft states, and + structured so as to require minimal changes to RSVP processing rules. + A broad RSVP-routing interface that enables this is described in + [GKR97]. Use of such an interface in the context of reserving + resources along an explicit path with RSVP is discussed in [GLG+97]. + Details of path management and a means for avoiding loops in case of + hop-by-hop path setup can be found in [GKH97], and are not addressed + further in this document. + +1.2. Simplifying Assumptions + + In order to achieve our goal of minimizing impact to the existing + protocol and implementation, we impose certain restrictions on the + range of extensions we initially consider to support QoS. The first + restriction is on the type of additional (QoS) metrics that will be + added to Link State Advertisements (LSAs) for the purpose of + distributing metrics updates. Specifically, the extensions to LSAs + that we initially consider, include only available bandwidth and + delay. In addition, path selection is itself limited to considering + only bandwidth requirements. In particular, the path selection + algorithm selects paths capable of satisfying the bandwidth + requirement of flows, while at the same time trying to minimize the + amount of network resources that need to be allocated, i.e., minimize + the number of hops used. + + This focus on bandwidth is adequate in most instances, and meant to + keep initial complexity at an acceptable level. However, it 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 + + + +Apostolopoulos, et al. Experimental [Page 5] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + direct path and had plenty of unused bandwidth. This would clearly + be an undesirable 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, multiple policies could be used to capture different + requirements, each presenting to the path selection algorithm a + correspondingly pruned network topology, on which the same algorithm + would be used to generate an appropriate path. Alternatively, + different algorithms could be used depending on the QoS requirements + expressed by an incoming request. Such extensions are beyond the + scope of this document, which limits itself to describing the case of + a single metric, bandwidth. However, it is worth pointing out that a + simple extension to the path selection algorithm proposed in this + document allows us to directly account for delay, under certain + conditions, when rate-based schedulers are employed, as in the + Guaranteed Service proposal [SPG97]; details can be found in [GOW97]. + + Another important aspect to ensure that introducing support for QoS + routing has the minimal possible impact, is to develop a solution + that has the smallest possible computing overhead. Additional + computations are unavoidable, but it is desirable to keep the + computational cost of QoS routing at a level comparable to that of + traditional routing algorithms. One possible approach to achieve + this goal, is to allow pre-computation of QoS routes. This is the + method that was chosen for the implementation of the QoS extensions + to OSPF and is, therefore, the one described in detail in this + document. Alternative approaches are briefly reviewed in appendices. + However, it should be noted that although several alternative path + selection algorithms are possible, the same algorithm should be used + consistently within a given routing domain. This requirement may be + relaxed when explicit routing is used, as the responsibility for + selecting a QoS path lies with a single entity, the origin of the + request, which then ensures consistency even if each router uses a + different path selection algorithm. Nevertheless, the use of a + common path selection algorithm within an AS is recommended, if not + necessary, for proper operation. + + A last aspect of concern regarding the introduction of QoS routing, + is to control the overhead associated with the additional link state + updates caused by more frequent changes to link metrics. The goal is + to minimize the amount of additional update traffic without adversely + affecting the performance of path selection. In Section 2.2, we + present a brief discussion of various alternatives that trade + accuracy of link state information for protocol overhead. Potential + enhancements to the path selection algorithm, which seek to + (directly) account for the inaccuracies in link metrics, are + described in [GOW97], while a comprehensive treatment of the subject + + + +Apostolopoulos, et al. Experimental [Page 6] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + can be found in [LO98, GO99]. In Section 4, we also describe the + design choices made in a reference implementation, to allow future + extensions and experimentation with different link state update + mechanisms. + + The rest of this document is structured as follows. In Section 2, we + describe the general design choices and mechanisms we rely on to + support QoS request. This includes details on the path selection + metrics, link state update extensions, and the path selection + algorithm itself. Section 3 focuses on the specific extensions that + the OSPF protocol requires, while Section 4 describes their + implementation in the GateD platform and also presents some + experimental results. Section 5 briefly addresses security issues + that the proposed schemes may raise. Finally, several appendices + provide additional material of interest, e.g., alternative path + selection algorithms and support for explicit routes, but somewhat + outside the main focus of this document. + +2. Path Selection Information and Algorithms + + This section reviews the basic building blocks of QoS path selection, + namely the metrics on the which the routing algorithm operates, the + mechanisms used to propagate updates for these metrics, and finally + the path selection algorithm itself. + +2.1. Metrics + + 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 to support a new flow. In + general, the network prefers to select the "cheapest" path among all + paths suitable for a new flow, and it may even decide not to accept a + new flow for which a feasible path exists, if the cost of the path is + deemed 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 currently + 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., + + + +Apostolopoulos, et al. Experimental [Page 7] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + unallocated) bandwidth. Changes in this metric need to be + advertised as part of extended LSAs, so that accurate information + is available to the path selection algorithm. + + - Link propagation delay: This quantity is meant to identify high + latency links, e.g., satellite links, which may be unsuitable for + real-time requests. This quantity also needs to be advertised as + part of extended LSAs, although timely dissemination of this + information is not critical as this parameter is unlikely to + change (significantly) over time. As mentioned earlier, link + propagation delay can be used to decide on the pruning of specific + links, when selecting a path for a delay sensitive request; also, + it can be used to support a related extension, as described in + [GOW97]. + + - 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 typically preferable, since it + consumes fewer network resources. As a result, the path selection + algorithm will attempt to find the minimum hop path capable of + satisfying the requirements of a given request. Note that + contrary to bandwidth and propagation delay, hop count is a metric + that does not affect LSAs, and it is only used implicitly as part + of the path selection algorithm. + +2.2. Advertisement of Link State Information + + The new link metrics identified in the previous section need to be + advertised across the network, so that each router can compute + accurate and consistent QoS routes. It is assumed that each router + maintains an updated database of the network topology, including the + current state (available bandwidth and propagation delay) of each + link. As mentioned before, the distribution of link state (metrics) + information is based on extending OSPF mechanisms. The detailed + format of those extensions is described in Section 3, but in addition + to how link state information is distributed, another important + aspect is when such distribution is to take place. + + One option is to mandate 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. Ideally, routers should have the most + current view of the bandwidth available on all links in the network, + so that they can make the most accurate decision of which path to + select. Unfortunately, this then calls for very frequent updates, + e.g., each time the available bandwidth of a link changes, which is + + + +Apostolopoulos, et al. Experimental [Page 8] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + neither scalable nor practical. In general, there is a trade-off + between the protocol overhead of frequent updates and the accuracy of + the network state information that the path selection algorithm + depends on. We outline next a few possible link state update + policies, which strike a practical compromise. + + The basic idea is to trigger link state advertisements only when + there is a significant change in the value of metrics since the last + advertisement. The notion of significance of a change can be based + on an "absolute" scale or a "relative" one. An absolute scale means + partitioning the range of values that a metric can take into + equivalence classes and triggering an update whenever the metric + changes sufficiently to cross a class boundary (3). A relative + scale, on the other hand, triggers updates when the percentage change + in the metric value exceeds a predefined threshold. Independent of + whether a relative or an absolute change trigger mechanism is used, a + periodic trigger constraint can also be added. This constraint can + be in the form of a hold-down timer, which is used to force a minimum + spacing between consecutive updates. Alternatively, a transmit timer + can also be used to ensure the transmission of an update after a + certain time has expired. Such a feature can be useful if link state + updates advertising bandwidth changes are sent unreliably. The + current protocol extensions described in Section 3 as well as the + implementation of Section 4 do not consider such an option as metric + updates are sent using the standard, and reliable, OSPF flooding + mechanism. However, this is clearly an extension worth considering + as it can help lower substantially the protocol overhead associated + with metrics updates. + + In both the relative and absolute change approaches, the metric value + advertised in an LSA can be either the actual or a quantized value. + Advertising the actual metric value is more accurate and, therefore, + preferable when metrics are frequently updated. On the other hand, + when updates are less frequent, e.g., because of a low sensitivity + trigger or the use of hold-down timers, advertising quantized values + can be of benefit. This is because it can help increase the number + of equal cost paths and, therefore, improve robustness to metrics + inaccuracies. In general, there is a broad space of possible trade- + offs between accuracy and overhead and selecting an appropriate + design point is difficult and depends on many parameters (see + [AGKT98] for a more detailed discussion of these issues). As a + result, in order to help acquire a better understanding of these + issues, the implementation described in Section 4 supports a range of + options that allow exploration of the available design space. In + addition, Section 4 also reports experimental data on the traffic + load and processing overhead generated by links state updates for + different configurations. + + + + +Apostolopoulos, et al. Experimental [Page 9] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +2.3. Path Selection + + There are two major aspects to computing paths for QoS requests. The + first is the actual path selection algorithm itself, i.e., which + metrics and criteria it relies on. The second is when the algorithm + is actually invoked. + + The topology on which the algorithm is run is, as with the standard + OSPF path selection, a directed graph where vertices (4) 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. 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, which corresponds to the amount of bandwidth that + remains available on this interface. This metric is combined with + hop count information to provide a cost value, whose goal is to pick + 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 is meant to balance load as well as maximize the + likelihood that the required bandwidth is indeed available. + + 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, because of the + specific nature of the two objectives being optimized (bandwidth and + hop count), the complexity of the above algorithm is competitive with + even that of standard single-objective algorithms. For readers + interested in a thorough treatment of the topic, with insights into + the connection between the different algorithms, linear algebra and + modification of metrics, [Car79] is recommended. + + Before proceeding with a more detailed description of the path + selection algorithm itself, we briefly review the available options + when it comes to deciding when to invoke the algorithm. The two main + options are: 1) to perform on-demand computations, that is, trigger + + + +Apostolopoulos, et al. Experimental [Page 10] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + a computation for each new request, and 2) to use some form of pre- + computation. The on-demand case involves no additional issues in + terms of when computations should be triggered, but running the path + selection algorithm for each new request can be computationally + expensive (see [AT98] for a discussion on this issue). On the other + hand, pre-computing paths amortizes the computational cost over + multiple requests, but each computation instance is usually more + expensive than in the on-demand case (paths are computed to all + destinations and for all possible bandwidth requests rather than for + a single destination and a given bandwidth request). Furthermore, + depending on how often paths are recomputed, the accuracy of the + selected paths may be lower. In this document, we primarily focus on + the case of pre-computed paths, which is also the only method + currently supported in the reference implementation described in + Section 4. In this case, clearly, an important issue is when such + pre-computation should take place. The two main options we consider + are periodic pre-computations and pre-computations after a given (N) + number of updates have been received. The former has the benefit of + ensuring a strict bound on the computational load associated with + pre-computations, while the latter can provide for a more responsive + solution (5). Section 4 provides some experimental results comparing + the performance and cost of periodic pre-computations for different + period values. + +2.3.1. Path Computation Algorithm + + This section describes a path selection algorithm, which for a given + network topology and link metrics (available bandwidth), pre-computes + all possible QoS paths, while maintaining a reasonably low + computational complexity. Specifically, the algorithm pre-computes + for any destination a minimum hop count path with maximum bandwidth, + and has a computational complexity comparable to that of a standard + Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest + path algorithm 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, because the BF algorithm progresses by increasing hop count, + it essentially provides 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 + + + +Apostolopoulos, et al. Experimental [Page 11] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + information). After the algorithm terminates, this information + provides 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 at most these many hops. This is 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 (the + pseudo-code for the algorithm can be found in Appendix A). 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 + b(n;m) the available bandwidth on the link from node n to 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 KxH 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. In the context of hop-by-hop + path selection (6), 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, the only exception being the case where the + network is the destination node (and the selected path is + the single edge interconnecting the source to it). + + + +Apostolopoulos, et al. Experimental [Page 12] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + Next, we provide additional details on the operation of the algorithm + and how the entries in the routing table are 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 are + handled. Zero-hop edges arise in the case of transit networks + vertices, where only one of the two incoming and outgoing edges + should be counted in the hop count computation, as they both + correspond to the same physical hop. Accounting for this aspect + requires distinguishing between network and router nodes, and the + steps involved are detailed later in this section as well as in the + pseudo-code of Appendix A. + + 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. The neighbor field is set to the + identity of the neighbor of the computing router, i.e., the next + router on the selected path. + + Afterwards, the algorithm iterates for at most H iterations + (considering the above initial iteration as the first). The value of + H could be implicit, i.e., the diameter of the network or, in order + to better control the worst case complexity, it can be set explicitly + thereby limiting path lengths to at most H hops. In the latter case, + H must be assigned a value larger than the length of the minimum + hop-count path to any node in the graph. + + 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)-th iteration. + The algorithm then looks at each link (n;m) where n is a node whose + bw value changed in the previous iteration, and checks the maximal + available bandwidth on an (at most) 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 b(n;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 at most h hops. The bw field + of entry (m;h) is then updated to reflect this new value. In the + case of hop-by-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. + + + + + + +Apostolopoulos, et al. Experimental [Page 13] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + As mentioned earlier, extending the above algorithm to handle zero- + hop edges is needed due to the possible use of multi-access networks, + e.g., T/R, E/N, etc., to interconnect routers. Such entities are + also represented by means of a vertex in the OSPF topology, but a + network connecting two routers should clearly be considered as a + single hop path rather than a two hop path. For example, consider + three routers A, B, and C connected over an Ethernet network N, which + the OSPF topology represents as in Figure 1. + + A----N----B + | + | + C + + + + Figure 1: Zero-Hop Edges + + + In the example of Figure 1, although there are directed edges in both + directions, an edge from the network to any of the three routers must + have zero "cost", so that it is not counted twice. It should be + noted that when considering such environments in the context of QoS + routing, it is assumed that some entity is responsible for + determining the "available bandwidth" on the network, e.g., a subnet + bandwidth manager. The specification and operation of such an entity + is beyond the scope of this document. + + Accommodating zero-hop edges in the context of the path selection + algorithm described above is done as follows: 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. + This is the case when m is a transit network. In that case, we + attempt to further improve the entry of node k within the current + iteration, 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 + b(m;k) kept in the topology database (7). 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 + hop-by-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)). + + + + + + + +Apostolopoulos, et al. Experimental [Page 14] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + 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 can be easily supported. It only + requires that the neighbor field be expanded to record the list of + next (previous) hops, when multiple equal cost paths are present. + +Addition of Stub Networks + + As was mentioned earlier, the path selection algorithm is run on a + graph whose vertices consist only of routers and transit networks and + not stub networks. This is intended to keep the computational + complexity as low as possible as stub networks can be added + relatively easily through a post-processing step. This second + processing step is similar to the one used in the current OSPF + routing table calculation [Moy98], with some differences to account + for the QoS nature of routes. + + Specifically, after the QoS routing table has been constructed, all + the router vertices are again considered. For each router, stub + networks whose links appear in the router's link advertisements will + be processed to determine QoS routes available to them. The QoS + routing information for a stub network is similar to that of routers + and transit networks and consists of an extension to the QoS routing + table in the form of an additional row. The columns in that new row + again correspond to paths of different hop counts, and contain both + bandwidth and next hop information. We also assume that an available + bandwidth value has been advertised for the stub network. As before, + how this value is determined is beyond the scope of this document. + The QoS routes for a stub network S are constructed as follows: + + Each entry in the row corresponding to stub network S has its bw(s) + field initialized to zero and its neighbor set to null. When a stub + network S is found in the link advertisement of router V, the value + bw(S,h) in the hth column of the row corresponding to stub network S + is updated as follows: + + bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ), + + where bw(V,h) is the bandwidth value of the corresponding column for + the QoS routing table row associated with router V, i.e., the + bandwidth available on an h hop path to V, and b(V,S) is the + advertised available bandwidth on the link from V to S. The above + expression essentially states that the bandwidth of a h hop path to + stub network S is updated using a path through router V, only if the + minimum of the bandwidth of the h hop path to V and the bandwidth on + the link between V and S is larger than the current value. + + + + + +Apostolopoulos, et al. Experimental [Page 15] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + Update of the neighbor field proceeds similarly whenever the + bandwidth of a path through V is found to be larger than or equal to + the current value. If it is larger, then the neighbor field of V in + the corresponding column replaces the current neighbor field of S. + If it is equal, then the neighbor field of V in the corresponding + column is concatenated with the existing field for S, i.e., the + current set of neighbors for V is added to the current set of + neighbors for S. + +Extracting Forwarding Information from Routing Table + + When the QoS paths are precomputed, the forwarding information for a + flow with given destination and bandwidth requirement needs to be + extracted from the routing table. The case of hop-by-hop routing is + simpler than that of explicit routing. This is because, only the + next hop needs to be returned instead of an explicit route. + + Specifically, assume a new request to destination, say, d, and with + bandwidth requirements B. The index of the destination vertex + identifies the row in the QoS routing table that needs to be checked + to generate a path. Assuming that the QoS routing table was + constructed using the Bellman-Ford algorithm presented later in this + section, the search then proceeds by increasing index (hop) count + until an entry is found, say at hop count or column index of h, with + a value of the bw field which is equal to or larger than B. This + entry points to the initial information identifying the selected + path. + + If the path computation algorithm stores multiple equal cost paths, + then some degree of load balancing can be achieved at the time of + path selection. A next hop from the list of equivalent next hops can + be chosen in a round robin manner, or randomly with a probability + that is weighted by the actual available bandwidth on the local + interface. The latter is the method used in the implementation + described in Section 4. + + The case of explicit routing is discussed in Appendix D. + +3. OSPF Protocol Extensions + + As stated earlier, one of our goals is to limit the additions to the + existing OSPF V2 protocol, while still providing the required level + of support for QoS based routing. To this end, all of the existing + OSPF mechanisms, data structures, advertisements, and data formats + remain in place. The purpose of this section of the document is to + describe the extensions to the OSPF protocol needed to support QoS as + outlined in the previous sections. + + + + +Apostolopoulos, et al. Experimental [Page 16] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +3.1. QoS -- Optional Capabilities + + The OSPF Options field is present in OSPF Hello packets, Database + Description packets and all LSAs. The Options field enables OSPF + routers to support (or not support) optional capabilities, and to + communicate their capability level to other OSPF routers. Through + this mechanism, routers of differing capabilities can be mixed within + an OSPF routing domain. Currently, the OSPF standard [Moy98] + specifies the following 5 bits in the options octet: + + +-----------------------------------------------+ + | * | * | DC | EA | N/P | MC | E | * | + +-----------------------------------------------+ + + Note that the least significant bit (`T' bit) that was used to + indicate TOS routing capability in the older OSPF specification + [Moy94] has been removed. However, for backward compatibility with + previous versions of the OSPF specification, TOS-specific information + can be included in router-LSAs, summary-LSAs and AS-external-LSAs. + + We propose to reclaim the `T' bit as an indicator of router's QoS + routing capability and refer to it as the `Q' bit. In fact, QoS + capability can be viewed as an extension of the TOS-capabilities and + QoS routing as a form of TOS-based routing. A router sets this bit + in its hello packets to indicate that it is capable of supporting + such routing. When this bit is set in a router or summary links link + state advertisement, it means that there are QoS fields to process in + the packet. When this bit is set in a network link state + advertisement it means that the network described in the + advertisement is QoS capable. + + We need to be careful in this approach so as to avoid confusing any + old style (i.e., RFC 1583 based) TOS routing implementations. The + TOS metric encoding rules of QoS fields introduced further in this + section will show how this is achieved. Additionally, unlike the RFC + 1583 specification that unadvertised TOS metrics be treated to have + same cost as TOS 0, for the purpose of computing QOS routes, + unadvertised TOS metrics (on a hop) indicate lack of connectivity for + the specific TOS metrics (for that hop). + +3.2. Encoding Resources as Extended TOS + + Introduction of QoS should ideally not influence the compatibility + with existing OSPFv2 routers. To achieve this goal, necessary + extensions in packet formats must be defined in a way that either is + understood by OSPFv2 routers, ignored, or in the worst case + "gracefully" misinterpreted. Encoding of QoS metrics in the TOS + field which fortunately enough is longer in OSPF packets than + + + +Apostolopoulos, et al. Experimental [Page 17] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + officially defined in [Alm92], allows us to mimic the new facility as + extended TOS capability. OSPFv2 routers will either disregard these + definitions or consider those unspecified. Specific precautions are + taken to prevent careless OSPF implementations from influencing + traditional TOS routers (if any) when misinterpreting the QoS + extensions. + + For QoS resources, 32 combinations are available through the use of + the fifth bit in TOS fields contained in different LSAs. Since + [Alm92] defines TOS as being four bits long, this definition never + conflicts with existing values. Additionally, to prevent naive + implementations that do not take all bits of the TOS field in OSPF + packets into considerations, the definitions of the `QoS encodings' + is aligned in their semantics with the TOS encoding. Only bandwidth + and delay are specified as of today and their values map onto + `maximize throughput' and `minimize delay' if the most significant + bit is not taken into account. Accordingly, link reliability and + jitter could be defined later if necessary. + + OSPF encoding RFC 1349 TOS values + ___________________________________________ + 0 0000 normal service + 2 0001 minimize monetary cost + 4 0010 maximize reliability + 6 0011 + 8 0100 maximize throughput + 10 0101 + 12 0110 + 14 0111 + 16 1000 minimize delay + 18 1001 + 20 1010 + 22 1011 + 24 1100 + 26 1101 + 28 1110 + 30 1111 + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 18] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + OSPF encoding `QoS encoding values' + + ------------------------------------------- + 32 10000 + 34 10001 + 36 10010 + 38 10011 + 40 10100 bandwidth + 42 10101 + 44 10110 + 46 10111 + 48 11000 delay + 50 11001 + 52 11010 + 54 11011 + 56 11100 + 58 11101 + 60 11110 + 62 11111 + + Representing TOS and QoS in OSPF. + +3.2.1. Encoding bandwidth resource + + Given the fact that the actual metric field in OSPF packets only + provides 16 bits to encode the value used and that links supporting + bandwidth ranging into Gbits/s are becoming reality, linear + representation of the available resource metric is not feasible. The + solution is exponential encoding using appropriately chosen implicit + base value and number bits for encoding mantissa and the exponent. + Detailed considerations leading to the solution described are not + presented here but can be found in [Prz95]. + + Given a base of 8, the 3 most significant bits should be reserved for + the exponent part and the remaining 13 for the mantissa. This allows + a simple comparison for two numbers encoded in this form, which is + often useful during implementation. + + The following table shows bandwidth ranges covered when using + different exponents and the granularity of possible reservations. + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 19] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + exponent + value x range (2^13-1)*8^x step 8^x + ------------------------------------------------- + 0 8,191 1 + 1 65,528 8 + 2 524,224 64 + 3 4,193,792 512 + 4 33,550,336 4,096 + 5 268,402,688 32,768 + 6 2,147,221,504 262,144 + 7 17,177,772,032 2,097,152 + + Ranges of Exponent Values for 13 bits, + base 8 Encoding, in Bytes/s + + The bandwidth encoding rule may be summarized as: "represent + available bandwidth in 16 bit field as a 3 bit exponent (with assumed + base of 8) followed by a 13 bit mantissa as shown below and advertise + 2's complement of the above representation." + + 0 8 16 + | | | + ----------------- + |EXP| MANT | + ----------------- + + Thus, the above encoding advertises a numeric value that is + + 2^16 -1 -(exponential encoding of the available bandwidth): + + This has the property of advertising a higher numeric value for lower + available bandwidth, a notion that is consistent with that of cost. + + Although it may seem slightly pedantic to insist on the property that + less bandwidth is expressed higher values, it has, besides + consistency, a robustness aspect in it. A router with a poor OSPF + implementation could misuse or misunderstand bandwidth metric as + normal administrative cost provided to it and compute spanning trees + with a "normal" Dijkstra. The effect of a heavily congested link + advertising numerically very low cost could be disastrous in such a + scenario. It would raise the link's attractiveness for future + traffic instead of lowering it. Evidence that such considerations + are not speculative, but similar scenarios have been encountered, can + be found in [Tan89]. + + + + + + + +Apostolopoulos, et al. Experimental [Page 20] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + Concluding with an example, assume a link with bandwidth of 8 Gbits/s + = 1024^3 Bytes/s, its encoding would consist of an exponent value of + 6 since 1024^3= 4,096*8^6, which would then have a granularity of 8^6 + or approx. 260 kBytes/s. The associated binary representation would + then be %(110) 0 1000 0000 0000% or 53,248 (8). The bandwidth cost + (advertised value) of this link when it is idle, is then the 2's + complement of the above binary representation, i.e., %(001) 1 0111 + 1111 1111% which corresponds to a decimal value of (2^16 - 1) - + 53,248 = 12,287. Assuming now a current reservation level of 6;400 + Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of available + bandwidth on the link. The encoding of this available bandwidth of + 1'600 Mbits/s is 6,400 * 8^5, which corresponds to a granularity of + 8^5 or approx. 30 kBytes/s, and has a binary representation of %(101) + 1 1001 0000 0000% or decimal value of 47,360. The advertised cost of + the link with this load level, is then %(010) 0 0110 1111 1111%, or + (2^16-1) -47,360 = 18,175. + + Note that the cost function behaves as it should, i.e., the less + bandwidth is available on a link, the higher the cost and the less + attractive the link becomes. Furthermore, the targeted property of + better granularity for links with less bandwidth available is also + achieved. It should, however, be pointed out that the numbers given + in the above examples match exactly the resolution of the proposed + encoding, which is of course not always the case in practice. This + leaves open the question of how to encode available bandwidth values + when they do not exactly match the encoding. The standard practice + is to round it to the closest number. Because we are ultimately + interested in the cost value for which it may be better to be + pessimistic than optimistic, we choose to round costs up and, + therefore, bandwidth down. + +3.2.2. Encoding Delay + + Delay is encoded in microseconds using the same exponential method as + described for bandwidth except that the base is defined to be 4 + instead of 8. Therefore, the maximum delay that can be expressed is + (2^13-1) *4^7 i.e., approx. 134 seconds. + +3.3. Packet Formats + + Given the extended TOS notation to account for QoS metrics, no + changes in packet formats are necessary except for the + (re)introduction of T-bit as the Q-bit in the options field. Routers + not understanding the Q-bit should either not consider the QoS + metrics distributed or consider those as `unknown' TOS. + + + + + + +Apostolopoulos, et al. Experimental [Page 21] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + To support QoS, there are additions to two Link State Advertisements, + the Router Links Advertisement and the Summary Links Advertisement. + As stated above, a router identifies itself as supporting QoS by + setting the Q-bit in the options field of the Link State Header. + When a router that supports QoS receives either the Router Links or + Summary Links Advertisement, it should parse the QoS metrics encoded + in the received Advertisement. + +3.4. Calculating the Inter-area Routes + + This document proposes a very limited use of OSPF areas, that is, it + is assumed that summary links advertisements exist for all networks + in the area. This document does not discuss the problem of providing + support for area address ranges and QoS metric aggregation. This is + left for further studies. + +3.5. Open Issues + + Support for AS External Links, Virtual Links, and incremental updates + for summary link advertisements are not addressed in this document + and are left for further study. For Virtual Links that do exist, it + is assumed for path selection that these links are non-QoS capable + even if the router advertises QoS capability. Also, as stated + earlier, this document does not address the issue of non-QoS routers + within a QoS domain. + +4. A Reference Implementation based on GateD + + In this section we report on the experience gained from implementing + the pre-computation based approach of Section 2.3.1 in the GateD + [Con] environment. First, we briefly introduce the GateD + environment, and then present some details on how the QoS extensions + were implemented in this environment. Finally, we discuss issues + that arose during the implementation effort and present some + measurement based results on the overhead that the QoS extensions + impose on a QoS capable router and a network of QoS routers. For + further details on the implementation study, the reader is referred + to [AGK99]. Additional performance evaluation based on simulations + can be found in [AGKT98]. + +4.1. The Gate Daemon (GateD) Program + + GateD [Con] is a popular, public domain (9) program that provides a + platform for implementing routing protocols on hosts running the Unix + operating system. The distribution of the GateD software also + includes implementations of many popular routing protocols, including + the OSPF protocol. The GateD environment offers a variety of + services useful for implementing a routing protocol. These services + + + +Apostolopoulos, et al. Experimental [Page 22] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + include a) support for creation and management of timers, b) memory + management, c) a simple scheduling mechanism, d) interfaces for + manipulating the host's routing table and accessing the network, and + e) route management (e.g., route prioritization and route exchange + between protocols). + + All GateD processing is done within a single Unix process, and + routing protocols are implemented as one or several tasks. A GateD + task is a collection of code associated with a Unix socket. The + socket is used for the input and output requirements of the task. + The main loop of GateD contains, among other operations, a select() + call over all task sockets to determine if any read/write or error + conditions occurred in any of them. GateD implements the OSPF link + state database using a radix tree for fast access to individual link + state records. In addition, link state records for neighboring + network elements (such as adjacent routers) are linked together at + the database level with pointers. GateD maintains a single routing + table that contains routes discovered by all the active routing + protocols. Multiple routes to the same destination are prioritized + according to a set of rules and administrative preferences and only a + single route is active per destination. These routes are + periodically downloaded in the host's kernel forwarding table. + +4.2. Implementing the QoS Extensions of OSPF + +4.2.1. Design Objectives and Scope + + One of our major design objectives was to gain substantial experience + with a functionally complete QoS routing implementation while + containing the overall implementation complexity. Thus, our + architecture was modular and aimed at reusing the existing OSPF code + with only minimal changes. QoS extensions were localized to specific + modules and their interaction with existing OSPF code was kept to a + minimum. Besides reducing the development and testing effort, this + approach also facilitated experimentation with different alternatives + for implementing the QoS specific features such as triggering + policies for link state updates and QoS route table computation. + Several of the design choices were also influenced by our assumptions + regarding the core functionalities that an early prototype + implementation of QoS routing must demonstrate. Some of the + important assumptions/requirements are: + + - Support for only hop-by-hop routing. This affected the path + structure in the QoS routing table as it only needs to store next + hop information. As mentioned earlier, the structure can be + easily extended to allow construction of explicit routes. + + + + + +Apostolopoulos, et al. Experimental [Page 23] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + - Support for path pre-computation. This required the creation of a + separate QoS routing table and its associated path structure, and + was motivated by the need to minimize processing overhead. + + - Full integration of the QoS extensions into the GateD framework, + including configuration support, error logging, etc. This was + required to ensure a fully functional implementation that could be + used by others. + + - Ability to allow experimentation with different approaches, e.g., + use of different update and pre-computation triggering policies + with support for selection and parameterization of these policies + from the GateD configuration file. + + - Decoupling from local traffic and resource management components, + i.e., packet classifiers and schedulers and local call admission. + This is supported by providing an API between QoS routing and the + local traffic management module, which hides all internal details + or mechanisms. Future implementations will be able to specify + their own mechanisms for this module. + + - Interface to RSVP. The implementation assumes that RSVP [RZB+97] + is the mechanism used to request routes with specific QoS + requirements. Such requests are communicated through an interface + based on [GKR97], and used the RSVP code developed at ISI, version + 4.2a2 [RZB+97]. + + In addition, our implementation also relies on several of the + simplifying assumptions made earlier in this document, namely: + + - The scope of QoS route computation is currently limited to a + single area. + + - All routers within the area are assumed to run a QoS enabled + version of OSPF, i.e., inter-operability with non-QoS aware + versions of the OSPF protocol is not considered. + + - All interfaces on a router are assumed to be QoS capable. + +4.2.2. Architecture + + The above design decisions and assumptions resulted in the + architecture shown in Figure 2. It consists of three major + components: the signaling component (RSVP in our case); the QoS + routing component; and the traffic manager. In the rest of this + section we concentrate on the structure and operation of the QoS + routing component. As can be seen in Figure 2, the QoS routing + extensions are further divided into the following modules: + + + +Apostolopoulos, et al. Experimental [Page 24] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + - Update trigger module determines when to advertise local link + state updates. This module implements a variety of triggering + policies: periodic, threshold based triggering, and class based + triggering. This module also implements a hold-down timer that + enforces minimum spacing between two consecutive update + triggerings from the same node. + + - Pre-computation trigger module determines when to perform QoS path + pre-computation. So far, this module implements only periodic + pre-computation triggering. + + - Path pre-computation module computes the QoS routing table based + on the QoS specific link state information as described in Section + 2.3.1. + + - Path selection and management module selects a path for a request + with particular QoS requirements, and manages it once selected, + i.e., reacts to link or reservation failures. Path selection is + performed as described in Section 2.3.1. Path management + functionality is not currently supported. + + - QoS routing table module implements the QoS specific routing + table, which is maintained independently of the other GateD + routing tables. + + - Tspec mapping module maps request requirements expressed in the + form of RSVP Tspecs and Rspecs into the bandwidth requirements + that QoS routing uses. + +4.3. Major Implementation Issues + + Mapping the above design to the framework of the GateD implementation + of OSPF led to a number of issues and design decisions. These issues + mainly fell under two categories: a) interoperation of the QoS + extensions with pre-existing similar OSPF mechanisms, and b) + structure, placement, and organization of the QoS routing table. + Next, we briefly discuss these issues and justify the resulting + design decisions. + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 25] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + +--------------------------------------------------+ + | +-----------------------------+ | + | | QoS Route Table Computation | | + | +-----------------------------+ | + | | | | + | V | | + | +-----------------+ | | + +-------------->| QoS Route Table | | | + | | +-----------------+ | | + | | | | + | | +----------------------+ +---------------+ | + | | | Core OSPF Functions | | Precomputation| | + | | | + | | Trigger | | + | | | (Enhanced) Topology | +---------------+ | + | | | Data Base | | | + | | +----------------------+ | | + | | | | | | + | | | +----------------------------+ | + | | | | Receive and update QoS-LSA | | + | | | +----------------------------+ | + | | | | | + | | | +----------------+ | + | | | | Local Interface| | + | | | | Status Monitor | | + | | | +----------------+ | ++----------------+ | | | | +| Path Selection | | +--------------+ +----------------+ | +| & Management | | | Build and | | Link State | | ++----------------+ | | Send QoS-LSA |----------| Update Trigger | | + | | +--------------+ +----------------+ | ++----------------+ | | | +| QoS Parameter | | | | +| Mapping | | OSPF with QoS Routing Extensions | | +|----------------+ +-------------------------------------------|------+ + | | ++----------------+ +----------+ +| QoS Route | | Local | +| Request Client |<---------------------------------------->| Resource | +| (e.g. RSVP) | | Manager | ++----------------+ +----------+ + + + + Figure 2: The software architecture + + + + + + + +Apostolopoulos, et al. Experimental [Page 26] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + The ability to trigger link state updates in response to changes in + bandwidth availability on interfaces is an essential component of the + QoS extensions. Mechanisms for triggering these updates and + controlling their rate have been mentioned in Section 2.2. In + addition, OSPF implements its own mechanism for triggering link state + updates as well as its own hold down timer, which may be incompatible + with what is used for the QoS link state updates. We handle such + potential conflicts as follows. First, since OSPF triggers updates + on a periodic basis with low frequency, we expect these updates to be + only a small part of the total volume of updates generated. As a + result, we chose to maintain the periodic update triggering of OSPF. + Resolving conflicts in the settings of the different hold down timer + settings requires more care. In particular, it is important to + ensure that the existing OSPF hold down timer does not interfere with + QoS updates. One option is to disable the existing OSPF timer, but + protection against transient overloads calls for some hold down + timer, albeit with a small value. As a result, the existing OSPF + hold down timer was kept, but reduced its value to 1 second. This + value is low enough (actually is the lowest possible, since GateD + timers have a maximum resolution of 1 second) so that it does not + interfere with the generation of the QoS link state updates, which + will actually often have hold down timers of their own with higher + values. An additional complexity is that the triggering of QoS link + state updates needs to be made aware of updates performed by OSPF + itself. This is necessary, as regular OSPF updates also carry + bandwidth information, and this needs to be considered by QoS updates + to properly determine when to trigger a new link state update. + + Another existing OSPF mechanism that has the potential to interfere + with the extensions needed for QoS routing, is the support for + delayed acknowledgments that allows aggregation of acknowledgments + for multiple LSAs. Since link state updates are maintained in + retransmission queues until acknowledged, excessive delay in the + generation of the acknowledgement combined with the increased rates + of QoS updates may result in overflows of the retransmission queues. + To avoid these potential overflows, this mechanism was bypassed + altogether and LSAs received from neighboring routers were + immediately acknowledged. Another approach which was considered but + not implemented, was to make QoS LSAs unreliable, i.e., eliminate + their acknowledgments, so as to avoid any potential interference. + Making QoS LSAs unreliable would be a reasonable design choice + because of their higher frequency compared to the regular LSAs and + the reduced impact that the loss of a QoS LSA has on the protocol + operation. Note that the loss of a QoS LSA does not interfere with + the base operation of OSPF, and only transiently reduces the quality + of paths discovered by QoS routing. + + + + + +Apostolopoulos, et al. Experimental [Page 27] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + The structure and placement of the QoS routing table also raises some + interesting implementation issues. Pre-computed paths are placed + into a QoS routing table. This table is implemented as a set of path + structures, one for each destination, which contain all the available + paths to this destination. In order to be able to efficiently locate + individual path structures, an access structure is needed. In order + to minimize the develpement effort, the radix tree structure used for + the regular GateD routing tables was reused. In addition, the QoS + routing table was kept independent of the GateD routing tables to + conform to the design goal of localizing changes and minimizing the + impact on the existing OSPF code. An additional reason for + maintaining the QoS routing separate and self-contained is that it is + re-computed under conditions that are different from those used for + the regular routing tables. + + Furthermore, since the QoS routing table is re-built frequently, it + must be organized so that its computation is efficient. A common + operation during the computation of the QoS routing table is mapping + a link state database entry to the corresponding path structure. In + order to make this operation efficient, the link state database + entries were extended to contain a pointer to the corresponding path + structure. In addition, when a new QoS routing table is to be + computed, the previous one must be de-allocated. This is + accomplished by traversing the radix tree in-order, and de-allocating + each node in the tree. This full de-allocation of the QoS routing + table is potentially wasteful, especially since memory allocation and + de-allocation is an expensive operation. Furthermore, because path + pre-computations are typically not triggered by changes in topology, + the set of destinations will usually remain the same and correspond + to an unchanged radix tree. A natural optimization would then be to + de-allocate only the path structures and maintain the radix tree. A + further enhancement would be to maintain the path structures as well, + and attempt to incrementally update them only when required. + However, despite the potential gains, these optimizations have not + been included in the initial implementation. The main reason is that + they involve subtle and numerous checks to ensure the integrity of + the overall data structure at all times, e.g., correctly remove + failed destinations from the radix tree and update the tree + accordingly. + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 28] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +4.4. Bandwidth and Processing Overhead of QoS Routing + + After completing the implementation outlined in the previous + sections, it was possible to perform an experimental study of the + cost and nature of the overhead of the QoS routing extensions + proposed in this document. In particular, using a simple setup + consisting of two interconnected routers, it is possible to measure + the cost of individual QoS routing related operations. These + operations are: a) computation of the QoS routing table, b) + selection of a path from the QoS routing table, c) generation of a + link state update, and d) reception of a link state update. Note + that the last two operations are not really specific to QoS routing + since regular OSPF also performs them. Nevertheless, we expect the + more sensitive update triggering mechanisms required for effective + QoS routing to result in increased number of updates, making the cost + of processing updates an important component of the QoS routing + overhead. An additional cost dimension is the memory required for + storing the QoS routing table. Scaling of the above costs with + increasing sizes of the topology database was investigated by + artificially populating the topology databases of the routers under + measurement. + + Table 1 shows how the measured costs depend on the size of the + topology. The topology used in the measurements was built by + replicating a basic building block consisting of four routers + connected with transit networks in a rectangular arrangement. The + details of the topology and the measurements can be found in [AGK99]. + The system running the GateD software was an IBM IntelliStation Z Pro + with a Pentium Pro processor at 200 MHz, 64 MBytes or real memory, + running FreeBSD 2.2.5-RELEASE and GateD 4. From the results of Table + 1, one can observe that the cost of path pre-computation is not much + higher than that of the regular SPF computation. However, path pre- + computation may need to be performed much more often than the SPF + computation, and this can potentially lead to higher processing + costs. This issue was investigated in a set of subsequent + experiments, that are described later in this section. The other + cost components reported in Table 1 include memory, and it can be + seen that the QoS routing table requires roughly 80% more memory than + the regular routing table. Finally, the cost of selecting a path is + found to be very small compared to the path pre-computation times. + As expected, all the measured quantities increase as the size of the + topology increases. In particular, the storage requirements and the + processing costs for both SPF computation and QoS path pre- + computation scale almost linearly with the network size. + + + + + + + +Apostolopoulos, et al. Experimental [Page 29] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +________________________________________________________________________ +|Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_| +|Regular_SPF_time_(microsec)____|215_|_440_|_747__|_1158_|_1621_|_2187_| +|Pre-computation_time_(microsec)|736_|_1622|_2883_|_4602_|_6617_|_9265_| +|SPF_routing_table_size_(bytes)_|2608|_4984|_8152_|_12112|_16864|_22408| +|QoS_routing_table_size_(bytes)_|3924|_7952|_13148|_19736|_27676|_36796| +|Path_Selection_time_(microsec)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_| + + Table 1: Stand alone QoS routing costs + + In addition to the stand alone costs reported in Table 1, it is + important to assess the actual operational load induced by QoS + routing in the context of a large network. Since it is not practical + to reproduce a large scale network in a lab setting, the approach + used was to combine simulation and measurements. Specifically, a + simulation was used to obtain a time stamped trace of QoS routing + related events that occur in a given router in a large scale network. + The trace was then used to artificially induce similar load + conditions on a real router and its adjacent links. In particular, + it was used to measure the processing load at the router and + bandwidth usage that could be attributed to QoS updates. A more + complete discussion of the measurement method and related + considerations can be found in [AGK99]. + + The use of a simulation further allows the use of different + configurations, where network topology is varied together with other + QoS parameters such as a) period of pre-computation, and b) threshold + for triggering link state updates. The results reported here were + derived using two types of topologies. One based on a regular but + artificial 8x8 mesh network, and another (isp) which has been used in + several previous studies [AGKT98, AT98] and that approximates the + network of a nation-wide ISP. As far as pre-computation periods are + concerned, three values of 1, 5 and 50 seconds were chosen, and for + the triggering of link state update thresholds of 10% and 80% were + used. These values were selected as they cover a wide range in terms + of precision of pre-computed paths and accuracy of the link state + information available at the routers. Also note that 1 second is the + smallest pre-computation period allowed by GateD. + + Table 2 provides results on the processing load at the router driven + by the simulation trace, for the two topologies and different + combinations of QoS parameters, i.e., pre-computation period and + threshold for triggering link state updates. Table 3 gives the + bandwidth consumption of QoS updates on the links adjacent to the + router. + + + + + + +Apostolopoulos, et al. Experimental [Page 30] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + ________________________________________________________________ + |_____________________|_________Pre-computation_Period_________| + |Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___| + |_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__| + |_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_| + + isp + + ________________________________________________________________ + |_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)| + |_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)| + + 8x8 mesh + + Table 2: Router processing load and (bandwidth blocking). + + In Table 2, processing load is expressed as the percentage of the + total CPU resources that are consumed by GateD processing. The same + table also shows the routing performance that is achieved for each + combination of QoS parameters, so that comparison of the different + processing cost/routing performance trade-offs can be made. Routing + performance is measured using the bandwidth blocking ratio, defined + as the sum of requested bandwidth of the requests that were rejected + over the total offered bandwidth. As can be seen from Table 2, + processing load is low even when the QoS routing table is recomputed + every second, and LSAs are generated every time the available + bandwidth on a link changes by more than 10% of the last advertised + value. This seems to indicate that given today's processor + technology, QoS routing should not be viewed as a costly enhancement, + at least not in terms of its processing requirements. Another + general observation is that while network size has obviously an + impact, it does not seem to drastically affect the relative influence + of the different parameters. In particular, despite the differences + that exist between the isp and mesh topologies, changing the pre- + computation period or the update threshold translates into + essentially similar relative changes. + + Similar conclusions can be drawn for the update traffic shown in + Table 3. In all cases, this traffic is only a small fraction of the + link's capacity. Clearly, both the router load and the link + bandwidth consumption depend on the router and link that was the + target of the measurements and will vary for different choices. The + results shown here are meant to be indicative, and a more complete + discussion can be found in [AGK99]. + + + + + + + +Apostolopoulos, et al. Experimental [Page 31] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + _______________________________________ + |_Link_state_threshold_|_______________| + |_________10%__________|3112_bytes/sec_| + |_________80%__________|177_bytes/sec__| + + isp + ________________________________________ + |_________10%__________|15438_bytes/sec_| + |_________80%__________|1053_bytes/sec__| + + 8x8 mesh + + Table 3: Link state update traffic + + Summarizing, by carrying out the implementation of the proposed QoS + routing extensions to OSPF we demonstrated that such extensions are + fairly straightforward to implement. Furthermore, by measuring the + performance of the real system we were able to demonstrate that the + overheads associated with QoS routing are not excessive, and are + definitely within the capabilities of modern processor and + workstation technology. + +5. Security Considerations + + The QoS extensions proposed in this document do not raise any + security considerations that are in addition to the ones associated + with regular OSPF. The security considerations of OSPF are presented + in [Moy98]. However, it should be noted that this document assumes + the availability of some entity responsible for assessing the + legitimacy of QoS requests. For example, when the protocol used for + initiating QoS requests is the RSVP protocol, this capability can be + provided through the use of RSVP Policy Decision Points and Policy + Enforcement Points as described in [YPG97]. Similarly, a policy + server enforcing the acceptability of QoS requests by implementing + decisions based on the rules and languages of [RMK+98], would also be + capable of providing the desired functionality. + + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 32] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +APPENDICES + +A. Pseudocode for the BF Based Pre-Computation Algorithm + + Note: The pseudocode below assumes a hop-by-hop forwarding approach + in updating the neighbor field. The modifications needed to support + explicit route construction are straightforward. The pseudocode also + does not handle equal cost multi-paths for simplicity, but the + modification needed to add this support are straightforward. + +Input: + V = set of vertices, labeled by integers 1 to N. + L = set of edges, labeled by ordered pairs (n,m) of vertex labels. + s = source vertex (at which the algorithm is executed). + For all edges (n,m) in L: + * b(n,m) = available bandwidth (according to last received update) + on interface associated with the edge between vertices n and m. + * If(n,m) outgoing interface corresponding to edge (n,m) when n is + a router. + H = maximum hop-count (at most the graph diameter). + +Type: + tab_entry: record + bw = integer, + neighbor = integer 1..N. + +Variables: + TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry + record, such that: + TT[n,h].bw is the maximum available bandwidth (as + known thus far) on a path of at most h hops + between vertices s and n, + TT[n,h].neighbor is the first hop on that path (a + neighbor of s). It is either a router or the + destination n. + + S_prev: list of vertices that changed a bw value in the TT table + in the previous iteration. + S_new: list of vertices that changed a bw value (in the TT table + etc.) in the current iteration. + +The Algorithm: + +begin; + + for n:=1 to N do /* initialization */ + begin; + TT[n,0].bw := 0; + + + +Apostolopoulos, et al. Experimental [Page 33] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + TT[n,0].neighbor := null + TT[n,1].bw := 0; + TT[n,1].neighbor := null + end; + TT[s,0].bw := infinity; + + reset S_prev; + for all neighbors n of s do + begin; + TT[n,1].bw := max( TT[n,1].bw, b[s,n]); + if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n); + /* need to make sure we are picking the maximum */ + /* bandwidth path for routers that can be reached */ + /* through both networks and point-to-point links */ + if (n is a router) then + S_prev := S_prev union {n} + /* only a router is added to S_prev, */ + /* if it is not already included in S_prev */ + else /* n is a network: */ + /* proceed with network--router edges, without */ + /* counting another hop */ + for all (n,k) in L, k <> s, do + /* i.e., for all other neighboring routers of n */ + begin; + TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw ); + /* In case k could be reached through another path */ + /* (a point-to-point link or another network) with */ + /* more bandwidth, we do not want to update TT[k,1].bw */ + if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw ) + /* If we have updated TT[k,1].bw by going through */ + /* network n */ + then TT[k,1].neighbor := If(s,n); + /* neighbor is interface to network n */ + if ( {k} not in S_prev) then S_prev := S_prev union {k} + /* only routers are added to S_prev, but we again need */ + /* to check they are not already included in 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 + end; + + + +Apostolopoulos, et al. Experimental [Page 34] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + 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. + + + + + + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 35] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +B. On-Demand Dijkstra Algorithm for QoS Path Computation + + In the main text, 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 + 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, 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 (see the pseudocode that + follows). 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. + + Note: The pseudocode below assumes a hop-by-hop forwarding approach + in updating the neighbor field. Addition of routes to stub networks + is done in a second phase as usual. The modifications needed to + support explicit route construction are straightforward. The + pseudocode also does not handle equal cost multi-paths for + simplicity, but the modifications needed to add this support are also + easily done. + + + + + +Apostolopoulos, et al. Experimental [Page 36] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +Input: + V = set of vertices, labeled by integers 1 to N. + L = set of edges, labeled by ordered pairs (n,m) of vertex labels. + s = source vertex (at which the algorithm is executed). + For all edges (n,m) in L: + * b(n,m) = available bandwidth (according to last received update) + on interface associated with the edge between vertices n and m. + * If(n,m) = outgoing interface corresponding to edge (n,m) when n is + a router. + d = destination vertex. + B = requested bandwidth for the flow served. + +Type: + tab_entry: record + hops = integer, + neighbor = integer 1..N, + ontree = boolean. + +Variables: + TT[1..N]: topology table, whose (n) entry is a tab_entry + record, such that: + TT[n].bw is the available bandwidth (as known + thus far) on a shortest-path between + vertices s and n, + TT[n].neighbor is the first hop on that path (a + neighbor of s). It is either a router or the + destination n. + S: list of candidate vertices; + v: vertex under consideration; + +The Algorithm: + +begin; + for n:=1 to N do /* initialization */ + begin; + TT[n].hops := infinity; + TT[n].neighbor := null; + TT[n].ontree := FALSE; + end; + TT[s].hops := 0; + + reset S; + v:= s; + while v <> d do + begin; + TT[v].ontree := TRUE; + for all edges (v,m) in L and b(v,m) >= B do + begin; + + + +Apostolopoulos, et al. Experimental [Page 37] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + if m is a router + begin; + if not TT[m].ontree then + begin; + /* bandwidth must be fulfilled since all links >= B */ + if TT[m].hops > TT[v].hops + 1 then + begin + S := S union { m }; + TT[m].hops := TT[v].hops + 1; + TT[m].neighbor := v; + end; + end; + end; + else /* must be a network, iterate over all attached routers */ + begin; /* each network -- router edge treated as zero hop edge */ + for all (m,k) in L, k <> v, + /* i.e., for all other neighboring routers of m */ + if not TT[k].ontree and b(m,k) >= B then + begin; + if TT[k].hops > TT[v].hops then + begin; + S := S union { k }; + TT[k].hops := TT[v].hops; + TT[k].neighbor := v; + end; + end; + end; + end; /* of all edges from the vertex under consideration */ + + if S is empty then + begin; + v=d; /* which will end the algorithm */ + end; + else + begin; + v := first element of S; + S := S - {v}; /* remove and store the candidate to consider */ + end; + end; /* from processing of the candidate list */ +end. + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 38] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +C. Precomputation Using Dijkstra Algorithm + + This appendix 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 solution to compute all + "best" paths is to consecutively compute shortest path spanning trees + starting from a complete graph and removing links with less bandwidth + than the threshold used in the previous computation. This yields + paths with possibly better bandwidth but of course more hops. + Despite the large number of Dijkstra computations involved, several + optimizations such as incremental spanning tree computation can be + used and allow for efficient implementations in terms of complexity + as well as storage since the structure of computed paths leans itself + towards path compression [ST83]. Details including measurements and + applicability studies can be found in [Prz95] and [BP95]. + + A variation of this theme is to trade the "accuracy" of the pre- + computed paths, (i.e., the paths being generated may be of a larger + hop count than needed) for the benefit of using a modified version of + Dijkstra shortest path algorithm and also saving on some + computations. This loss in accuracy comes from the need to rely on + quantized bandwidth values, which 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 value, i.e., low, medium, or high, larger than or + equal to what it requested. We restrict our discussion here to this + "quantized" version of the algorithm. + + 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. + + + + + +Apostolopoulos, et al. Experimental [Page 39] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + - The (n;q) entry contains information that identifies the minimum + hop count path to destination n, which 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, which can accommodate a request of at + least bw[q] units of bandwidth. + + * neighbor: this is the routing information associated with the + minimum hop count path to destination node n, whose available + bandwidth is at least bw[q]. With a hop-by-hop routing + approach, the neighbor information is simply the identity of + the node adjacent to the source node 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 + the corresponding interface, where b(n;m) is 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 b(n;m) < bw[q], and then runs on the remaining + topology a Dijkstra-based minimum hop count algorithm (10) 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 b(n;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. 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 + + + +Apostolopoulos, et al. Experimental [Page 40] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + assume q<Q), i.e., paths that can accommodate bw[q] and bw[q+ 1] have + the same hop count, then the algorithm copies the value of the + neighbor field from entry (n;q+1) into that of entry (n;q). + + Note: The pseudocode below assumes a hop-by-hop forwarding approach + in updating the neighbor field. The modifications needed to support + explicit route construction are straightforward. The pseudocode also + does not handle equal cost multi-paths for simplicity, but the + modification needed to add this support have been described above. + Details of the post-processing step of adding stub networks are + omitted. + +Input: + V = set of vertices, labeled by integers 1 to N. + L = set of edges, labeled by ordered pairs (n,m) of vertex labels. + s = source vertex (at which the algorithm is executed). + bw[1..Q] = array of bandwidth values to "quantize" flow requests to. + For all edges (n,m) in L: + * b(n,m) = available bandwidth (according to last received update) + on interface associated with the edge between vertices n and m. + * If(n,m) = outgoing interface corresponding to edge (n,m) when n is + a router. + +Type: + tab_entry: record + hops = integer, + neighbor = integer 1..N, + ontree = boolean. + +Variables: + TT[1..N, 1..Q]: topology table, whose (n,q) entry is a tab_entry + record, such that: + TT[n,q].bw is the available bandwidth (as known + thus far) on a shortest-path between + vertices s and n accommodating bandwidth b(q), + TT[n,q].neighbor is the first hop on that path (a + neighbor of s). It is either a router or the + destination n. + S: list of candidate vertices; + v: vertex under consideration; + q: "quantize" step + +The Algorithm: + +begin; + for r:=1 to Q do + begin; + for n:=1 to N do /* initialization */ + + + +Apostolopoulos, et al. Experimental [Page 41] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + begin; + TT[n,r].hops := infinity; + TT[n,r].neighbor := null; + TT[n,r].ontree := FALSE; + end; + TT[s,r].hops := 0; + end; + for r:=1 to Q do + begin; + S = {s}; + while S not empty do + begin; + v := first element of S; + S := S - {v}; /* remove and store the candidate to consider */ + TT[v,r].ontree := TRUE; + for all edges (v,m) in L and b(v,m) >= bw[r] do + begin; + if m is a router + begin; + if not TT[m,r].ontree then + begin; + /* bandwidth must be fulfilled since all links >= bw[r] */ + if TT[m,r].hops > TT[v,r].hops + 1 then + begin + S := S union { m }; + TT[m,r].hops := TT[v,r].hops + 1; + TT[m,r].neighbor := v; + end; + end; + end; + else /* must be a network, iterate over all attached + routers */ + begin; + for all (m,k) in L, k <> v, + /* i.e., for all other neighboring routers of m */ + if not TT[k,r].ontree and b(m,k) >= bw[r] then + begin; + if TT[k,r].hops > TT[v,r].hops + 2 then + begin; + S := S union { k }; + TT[k,r].hops := TT[v,r].hops + 2; + TT[k,r].neighbor := v; + end; + end; + end; + end; /* of all edges from the vertex under consideration */ + end; /* from processing of the candidate list */ + end; /* of "quantize" steps */ + + + +Apostolopoulos, et al. Experimental [Page 42] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +end. + +D. Explicit Routing Support + + As mentioned before, the scope of the path selection process can + range from simply returning the next hop on the QoS path selected for + the flow, to specifying the complete path that was computed, i.e., an + explicit route. Obviously, the information being returned by the + path selection algorithm differs in these two cases, and constructing + it imposes different requirements on the path computation algorithm + and the data structures it relies on. While the presentation of the + path computation algorithms focused on the hop-by-hop routing + approach, the same algorithms can be applied to generate explicit + routes with minor modifications. These modifications and how they + facilitate constructing explicit routes are discussed next. + + The general approach to facilitate construction of explicit routes is + to update the neighbor field differently from the way it is done for + hop-by-hop routing as described in Section 2.3. Recall that in the + path computation algorithms the neighbor field is updated to reflect + the identity of the router adjacent to the source node on the partial + path computed. This facilitates returning the next hop at the source + for the specific path. In the context of explicit routing, the + neighbor information is updated to reflect the identity of the + previous router on the path. + + In general, there can be multiple equivalent paths for a given hop + count. Thus, the neighbor information is stored as a list rather + than single value. Associated with each neighbor, additional + information is stored to facilitate load balancing among these + multiple paths at the time of path selection. Specifically, we store + the advertised available bandwidth on the link from the neighbor to + the destination in the entry. + + With this change, the basic approach used to extract the complete + list of vertices on a path from the neighbor information in the QoS + routing table is to proceed `recursively' from the destination to the + origin vertex. The path is extracted by stepping through the + precomputed QoS routing table from vertex to vertex, and identifying + at each step the corresponding neighbor (precursor) information. The + process is described as recursive since the neighbor node identified + in one step becomes the destination node for table look up in the + next step. Once the source router is reached, the concatenation of + all the neighbor fields that have been extracted forms the desired + explicit route. This applies to algorithms of Section 2.3.1 and + Appendix C. If at a particular stage there are multiple neighbor + choices (due to equal cost multi-paths), one of them can be chosen at + random with a probability that is weighted, for example, by the + + + +Apostolopoulos, et al. Experimental [Page 43] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + associated bandwidth on the link from the neighbor to the (current) + destination. + + Specifically, assume a new request to destination, say, d, and with + bandwidth requirements B. The index of the destination vertex + identifies the row in the QoS routing table that needs to be checked + to generate a path. The row is then searched to identify a suitable + path. If the Bellman-Ford algorithm of Section 2.3.1 was used, the + search proceeds by increasing index (hop) count until an entry is + found, say at hop count or column index of h, with a value of the bw + field that is equal to or greater than B. This entry points to the + initial information identifying the selected path. If the Dijkstra + algorithm of Appendix C is used, the first quantized value qB such + that qB >= B is first identified, and the associated column then + determines the first entry in the QoS routing table that identifies + the selected path. + + Once this first entry has been identified, reconstruction of the + complete list of vertices on the path proceeds similarly, whether the + table was built using the algorithm of Section 2.3.1 or Appendix C. + Specifically, in both cases, the neighbor field in each entry points + to the previous node on the path from the source node and with the + same bandwidth capabilities as those associated with the current + entry. The complete path is, therefore, reconstructed by following + the pointers provided by the neighbor field of successive entries. + + In the case of the Bellman-Ford algorithm of Section 2.3.1, this + means moving backwards in the table from column to column, using at + each step the row index pointed to by the neighbor field of the entry + in the previous column. Each time, the corresponding vertex index + specified in the neighbor field is pre-pended to the list of vertices + constructed so far. Since we start at column h, the process ends + when the first column is reached, i.e., after h steps, at which point + the list of vertices making up the path has been reconstructed. + + In the case of the Dijkstra algorithm of Appendix C, the backtracking + process is similar although slightly different because of the + different relation between paths and columns in the routing table, + i.e., a column now corresponds to a quantized bandwidth value instead + of a hop count. The backtracking now proceeds along the column + corresponding to the quantized bandwidth value needed to satisfy the + bandwidth requirements of the flow. At each step, the vertex index + specified in the neighbor field is pre-pended to the list of vertices + constructed so far, and is used to identify the next row index to + move to. The process ends when an entry is reached whose neighbor + field specifies the origin vertex of the flow. Note that since there + are as many rows in the table as there are vertices in the graph, + i.e., N, it could take up to N steps before the process terminates. + + + +Apostolopoulos, et al. Experimental [Page 44] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + Note that the identification of the first entry in the routing table + is identical to what was described for the hop-by-hop routing case. + However, as described in this section, the update of the neighbor + fields while constructing the QoS routing tables, is being performed + differently in the explicit and hop-by-hop routing cases. Clearly, + two different neighbor fields can be kept in each entry and updates + to both could certainly be performed jointly, if support for both + xplicit routing and hop-by-hop routing is needed. + +Endnotes + + 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 compute a QoS path. + + 2. This is true for uni-cast flows, but in the case of multi-cast + flows, hop-by-hop and an explicit routing clearly have different + implications. + + 3. Some hysteresis mechanism should be added to suppress updates when + the metric value oscillates around a class boundary. + + 4. In this document, we use the terms node and vertex + interchangeably. + + 5. Various hybrid methods can also be envisioned, e.g., periodic + computations except if more than a given number of updates are + received within a shorter interval, or periodic updates except if + the change in metrics corresponding to a given update exceeds a + certain threshold. Such variations are, however, not considered + in this document. + + 6. Modifications to support explicit routing are discussed in + Appendix D. + + 7. Note, that this does not say anything on whether to differentiate + between outgoing and incoming bandwidth on a shared media network. + As a matter of fact, a reasonable option is to set the incoming + bandwidth (from network to router) to infinity, and only use the + outgoing bandwidth value to characterize bandwidth availability on + the shared network. + + 8. exponent in parenthesis + + 9. Access to some of the more recent versions of the GateD software + is restricted to the GateD consortium members. + + + + + +Apostolopoulos, et al. Experimental [Page 45] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + 10. Note that a Breadth-First-Search (BFS) algorithm [CLR90] could + also be used. It has a lower complexity, but would not allow + reuse of existing code in an OSPF implementation. + +References + + [AGK99] G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation + and performance meassurements of QoS routing extensions to + OSPF. In Proceedings of INFOCOM'99, pages 680--688, New + York, NY, March 1999. + + [AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi. + QoS routing: A performance perspective. In Proceedings of + ACM SIGCOMM'98, pages 17--28, Vancouver, Canada, October + + [Alm92] Almquist, P., "Type of Service in the Internet Protocol + Suite", RFC 1349, July 1992. + + [AT98] G. Apostolopoulos and S. K. Tripathi. On reducing the + processing cost of on-demand QoS path computation. In + Proceedings of ICNP'98, pages 80--89, Austin, TX, October + 1998. + + [BP95] J.-Y. Le Boudec and T. Przygienda. A Route Pre-Computation + Algorithm for Integrated Services Networks. Journal of + Network and Systems Management, 3(4), 1995. + + [Car79] B. Carre. Graphs and Networks. Oxford University Press, + ISBN 0-19-859622-7, Oxford, UK, 1979. + + [CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. + Introduction to Algorithms. MIT Press, Cambridge, MA, 1990. + + [Con] Merit GateD Consortium. The Gate Daemon (GateD) project. + + [GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. + Freeman, San Francisco, 1979. + + [GKH97] R. Guerin, S. Kamat, and S. Herzog. QoS Path Management + with RSVP. In Proceedings of the 2nd IEEE Global Internet + Mini-Conference, pages 1914-1918, Phoenix, AZ, November + + [GKR97] Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP + Routing Interface, Work in Progress. + + [GLG+97] Der-Hwa G., Li, T., Guerin, R., Rosen, E. and S. Kamat, + "Setting Up Reservations on Explicit Paths using RSVP", Work + in Progress. + + + +Apostolopoulos, et al. Experimental [Page 46] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + [GO99] R. Guerin and A. Orda. QoS-Based Routing in Networks with + Inaccurate Information: Theory and Algorithms. IEEE/ACM + Transactions on Networking, 7(3):350--364, June 1999. + + + [GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing Mechanisms + and OSPF Extensions. In Proceedings of the 2nd IEEE Global + Internet Mini-Conference, pages 1903-1908, Phoenix, AZ, + November 1997. + + [KNB98] Nichols, K., Blake, S., Baker F. and D. Black, "Definition + of the Differentiated Services Field (DS Field) in the IPv4 + and IPv6 Headers", RFC 2474, December 1998. + + [LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with + Uncertain Parameters. IEEE/ACM Transactions on Networking, + 6(6):768--778, December 1998. + + [Moy94] Moy, J., "OSPF Version 2", RFC 1583, March 1994. + + [Moy98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. + + [Prz95] A. Przygienda. Link State Routing with QoS in ATM LANs. + Ph.D. Thesis Nr. 11051, Swiss Federal Institute of + Technology, April 1995. + + [RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, D. + Verma, G. Powers, and R. Yavatkar. Schema for + differentiated services and integrated services in networks. + INTERNET-DRAFT, October 1998. work in progress. + + [RZB+97] Braden, R., Editor, Zhang, L., Berson, S., Herzog, S. and S. + Jamin, "Resource reSerVation Protocol (RSVP) Version 1, + Functional Specification", RFC 2205, September 1997. + + [SPG97] Shenker, S., Partridge, C. and R. Guerin, "Specification of + Guaranteed Quality of Service", RFC 2212, November 1997. + + [ST83] D.D. Sleator and R.E. Tarjan. A Data Structure for Dynamic + Trees. Journal of Computer Systems, 26, 1983. + + [Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989. + + [YPG97] Yavatkar, R., Pendarakis, D. and R. Guerin, "A Framework for + Policy-based Admission Control", INTERNET-DRAFT, April 1999. + Work in Progress. + + + + + +Apostolopoulos, et al. Experimental [Page 47] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +Authors' Addresses + + George Apostolopoulos + IBM T.J. Watson Research Center + P.O. Box 704 + Yorktown Heights, NY 10598 + + Phone: +1 914 784-6204 + Fax: +1 914 784-6205 + EMail: georgeap@watson.ibm.com + + + Roch Guerin + University Of Pennsylvania + Department of Electrical Engineering, Rm 367 GRW + 200 South 33rd Street + Philadelphia, PA 19104--6390 + + Phone: +1 215-898-9351 + EMail: guerin@ee.upenn.edu + + + Sanjay Kamat + Bell Laboratories + Lucent Technologies + Room 4C-510 + 101 Crawfords Corner Road + Holmdel, NJ 07733 + + Phone: (732) 949-5936 + email: sanjayk@dnrc.bell-labs.com + + + Ariel Orda + Dept. Electrical Engineering + Technion - I.I.T + Haifa, 32000 - ISRAEL + + Phone: +011 972-4-8294646 + Fax: +011 972-4-8323041 + EMail: ariel@ee.technion.ac.il + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 48] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + + Tony Przygienda + Siara Systems + 300 Ferguson Drive + Moutain View + California 94043 + + Phone: +1 732 949-5936 + Email: prz@siara.com + + + Doug Williams + IBM T.J. Watson Research Center + P.O. Box 704 + Yorktown Heights, NY 10598 + + Phone: +1 914 784-5047 + Fax: +1 914 784-6318 + EMail: dougw@watson.ibm.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 49] + +RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999 + + +Full Copyright Statement + + Copyright (C) The Internet Society (1999). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF + MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + + + + + + + + + + + + + +Apostolopoulos, et al. Experimental [Page 50] + |