RFC 2676
QoS Routing Mechanisms and OSPF Extensions
QoS Routing Mechanisms and OSPF Extensions 🦋
Okay bestie, this is RFC 2676 📜 and it's giving vintage, because it dates from August 1999. It was written by G. Apostolopoulos, D. Williams, S. Kamat, R. Guerin, A. Orda and T. Przygienda, who came from IBM, Lucent, UPenn, Technion and Siara Systems. It's an Experimental document in the Network Working Group stream. There's no Obsoletes or Updates line on it, so it doesn't list anything it replaces or updates. ✨
Status of this Memo 🌸
This memo defines an Experimental Protocol for the Internet community. It is not an Internet standard of any kind, so don't treat it like one 🙈. The authors are asking for discussion and suggestions for improvement, and anyone can distribute it without limit.
Copyright Notice 💜
Copyright (C) The Internet Society (1999). All Rights Reserved.
Abstract 🧚
This memo extends the OSPF [Moy98] protocol so it can support QoS routes 🚀. The main focus is on the algorithms used to compute QoS routes, plus the changes OSPF needs in order to do that. That covers what information is needed, what format it takes, how it's distributed, and how the QoS path selection process uses it. How QoS routes get set up and managed is also touched on briefly. The big goal is a framework and some possible approaches that let QoS routing be deployed with the least possible disruption to the existing routing infrastructure 💅.
The authors also share experience from implementing the proposed extensions in the GateD environment [Con], along with performance measurements 📊.
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 501. Introduction 🌈
Okay so in this doc we're describing a bunch of new additions to the OSPF routing protocol 🛣️. These additions were built on top of the GateD [Con] implementation of OSPF V2 [Moy98], and they add Quality-of-Service (QoS) routing to IP networks. Honestly, QoS routing is three big jobs:
- Get the info needed to compute QoS paths, then pick a path that can meet the QoS requirements of a given request 🎯,
- Set up the chosen path so it can carry a new request 🔧,
- Keep the path assigned to a given request running 🔒.
We do touch on the last two, but the main focus is the first one 💖. We talk about the metrics needed to support QoS, the extension to the OSPF link state advertisement mechanism that spreads QoS metric updates around, and the changes to path selection so it can handle QoS requests ✨. The whole point is to make things better for QoS flows, meaning how likely they are to be routed on a path that actually gives the QoS they asked for, while changing the existing OSPF protocol and its current implementation as little as possible 🫶. The catch is that QoS routing is seriously complicated, so the authors admit that getting there means trading "optimality" for "simplicity" 🙈. They think that trade is necessary to get QoS routing deployed at all 💅.
Besides describing the OSPF extensions, this doc also reports experimental data from performance measurements of an implementation on the GateD platform (see Section 4) 📊.
1.1. Overall Framework 🧚
Picture a network (1) that supports both best-effort packets and packets with QoS guarantees 🌐. How the network resources are split between those two classes doesn't matter here. The one assumption is that each QoS capable router can dedicate some of its resources to meeting the requirements of QoS packets. These QoS capable routers are also assumed to be able to identify and advertise the resources that are still free for new QoS flows 🦋. Also, this doc only looks at the case where every router involved supports the QoS extensions described here. So we are not dealing with setting up a route in a mixed environment where some routers are QoS-capable and others aren't 🙅♀️. Last thing: this doc focuses on unicast flows, though a lot of the additions also work for multicast flows too 💜.
We assume that a flow with QoS requirements states them in some way the routing protocol can access 🔍. For example, this could be an RSVP [RZB+97] PATH message showing up, where its TSpec gets handed to routing along with the destination address. Once the request is processed, the routing protocol returns the path it thinks fits the flow's requirements best 🏆. Depending on how wide the path selection scope is, that returned path could be as simple as the best next hop (a hop-by-hop path selection model), or it could list every intermediate node all the way to the destination (an explicit route model) 🗺️. The kind of path returned changes what the selection algorithm has to build and hand back, but it doesn't change how the basic path selection algorithm works (2) 🔥.
For simplicity, and because that's what the implementation supports (see Section 4 for details), the rest of this document sticks to the hop-by-hop path selection model 🎀. The changes needed for an explicit routing model are in appendix D, but they're kind of on the side. The main event is the specific OSPF extensions for computing QoS routes 💅.
Now, picking a QoS path and maybe reserving resources on it is only part of the story 📦. The QoS guarantees only get delivered if the packets of that "QoS flow" actually travel the selected path. That usually means installing matching forwarding state in the router 🔐. With RSVP [RZB+97] flows, for example, a classifier entry gets created from the filter specs in the RESV message 🧾. With a Differentiated Service [KNB98] setup, the classifier entry might be based on the destination address (or prefix) and the matching DS byte value 🏷️. The mechanisms in this document live at the control path level, so they don't depend on the data path stuff like which packet classification method is used 🧠. Still, consistent QoS delivery needs the data path to be stable 🛑. Even though network conditions might change after a path is first picked and make "better" paths show up, those changes shouldn't mess with existing paths for no reason 😤. Switching to a new (and better) path should only happen under specific conditions, like when the first pick turns out to be inadequate or extremely "expensive" 💸. This is outside the scope of QoS routing and falls under path management, which isn't the main focus here. But since it could hugely affect how useful QoS routing is, the doc briefly sketches one possible approach to path management 🌸.
Avoiding pointless changes to QoS paths means keeping state about each QoS path once it's been selected 📝. That state tracks whether the path is still valid. Is the current path good enough, or should QoS routing be queried again to find a new and maybe better one? 🤔 A path is "pinned" when its state says QoS routing doesn't need to be queried again, and it's "un-pinned" otherwise 📌. The big question is how, when and where pinning and un-pinning happen, and that usually depends on which mechanism is used to request QoS routes 🧩. If RSVP is the mechanism, it's ideal for path management to fit as closely as possible with the existing RSVP state management ⭐. Pinning and un-pinning should line up with RSVP soft states and be structured so RSVP processing rules need minimal changes 💖. A broad RSVP-routing interface that does this is described in [GKR97]. Using that kind of interface to reserve resources along an explicit path with RSVP is discussed in [GLG+97]. Details on path management and on avoiding loops in hop-by-hop path setup are in [GKH97], and this doc doesn't cover them any further 🦋.
1.2. Simplifying Assumptions ✨
okay so, to keep the impact on the existing protocol and implementations as tiny as possible 🥺, we're putting some limits on which QoS extensions we even look at. Limit #1 is about what extra QoS metrics get stuffed into Link State Advertisements (LSAs) so they can spread metric updates. For now we're only considering available bandwidth and delay 🦋. Path selection is also limited to bandwidth needs. The algorithm hunts for paths that can handle a flow's bandwidth requirement, and it also tries to use as few network resources as possible, which means using the fewest hops 💅.
Bandwidth alone is honestly good enough for most cases, and it keeps the early complexity chill 🫶. It still misses a bunch of QoS requirements though. Imagine a delay-sensitive flow from an interactive app getting routed over a satellite link just because it's the direct path and has lots of spare bandwidth 💀. That's a big no. So our fix is to put delay-sensitive flows under a "policy" that deletes every high-propagation-delay link (satellite links, for example) from the network before the path selection algorithm even runs 🛰️. Multiple policies could handle different requirements, each one giving the algorithm its own pruned topology, and the same algorithm would run on each one to find a suitable path 🌈. Or, you could use different algorithms depending on the QoS requirements in the incoming request. Those extensions are outside this document's scope, though, which only covers the single metric of bandwidth 🙈. Still, it's worth knowing that a simple tweak to the path selection algorithm proposed here can account for delay too, under certain conditions, when rate-based schedulers are in use, like in the Guaranteed Service proposal [SPG97]. The details are in [GOW97] 📚.
Another big priority is keeping QoS routing's computing overhead as small as possible. Some extra computation is unavoidable, but the goal is for QoS routing's cost to stay close to what traditional routing algorithms cost 🧚. One way to get there is to pre-compute QoS routes. This is the approach chosen for the QoS extensions to OSPF, so it's the one this document explains in detail 💜. Other approaches get a quick look in the appendices. Also, even though several path selection algorithms are possible, the same algorithm should be used consistently within a given routing domain 😭. This rule can be relaxed when explicit routing is used, because then one entity, the origin of the request, is responsible for picking the QoS path. That keeps things consistent even if each router runs a different algorithm 👑. Still, using a common path selection algorithm within an AS is recommended, if not strictly necessary, for things to work properly 🎀.
The last thing we're worried about is the extra overhead from additional link state updates, since link metrics will change more often 🌸. The aim is to keep the extra update traffic low without hurting path selection performance ⭐. Section 2.2 walks through several options that trade accuracy of link state information against protocol overhead 🍓. Improvements to the path selection algorithm that try to directly account for inaccurate link metrics are described in [GOW97], and a full treatment of the subject is in [LO98, GO99] 🔥. Section 4 also covers the design choices made in a reference implementation, which leaves room for future extensions and experiments with different link state update mechanisms 🧪.
Here's the roadmap 🗺️. Section 2 covers the general design choices and mechanisms we use to support QoS requests, including the path selection metrics, the link state update extensions, and the path selection algorithm itself 💖. Section 3 focuses on the specific extensions OSPF needs 🫧. Section 4 describes how they're implemented in the GateD platform and shares some experimental results 📊. Section 5 briefly covers the security issues the proposed schemes might raise 🔐. Finally, several appendices give extra material, like alternative path selection algorithms and support for explicit routes. They're a bit outside the main focus of this document, but still good to know 🦋.
2. Path Selection Information and Algorithms 💅
This section goes over the basic building blocks of QoS path selection. Those are the metrics the routing algorithm works with, the mechanisms used to spread updates for those metrics, and finally the path selection algorithm itself 🌷.
2.1. Metrics 💜
Selecting a path that can meet the QoS requirements of a new flow depends on two things: knowing the flow's requirements and characteristics, and knowing what resources the network has available 🌐. For efficiency, the algorithm also needs to account for how many resources the network has to allocate to support the new flow 🧮. In general, the network prefers to pick the "cheapest" path out of all the paths that suit the new flow. It may even choose to turn down a new flow that has a feasible path, if the cost of that path is considered too high 💸. Several metrics make this work, and the path selection process is based on them. They include:
- Link available bandwidth: As we mentioned earlier, we currently assume that most QoS requirements can be derived from a rate-related quantity called "bandwidth." We also assume each link has a maximal bandwidth value, such as the link's physical bandwidth or some fraction of it that's been set aside for QoS flows 🎀. For a link to accept a new flow with given bandwidth requirements, at least that much bandwidth must still be available on it. So the relevant link metric is the current amount of available (meaning unallocated) bandwidth ✨. Changes to this metric need to be advertised as part of extended LSAs, so the path selection algorithm has accurate information 🫶.
- Link propagation delay: This quantity is meant to spot high-latency links, like satellite links, which may not be good for real-time requests 🛰️. It also needs to be advertised as part of extended LSAs. But timely spreading of this info isn't critical, since this parameter isn't likely to change much over time 🐢. As we mentioned earlier, link propagation delay can be used to prune specific links when selecting a path for a delay-sensitive request. It can also support a related extension described in [GOW97] 🌈.
- Hop-count: This quantity is used as a measure of the path cost to the network 🛤️. A path with fewer hops (that can still support the requested connection) is typically preferable, since it uses fewer network resources 🍓. So the path selection algorithm will try to find the minimum-hop path that can satisfy the requirements of a given request 🎯. Note that unlike bandwidth and propagation delay, hop count is a metric that doesn't affect LSAs. It's only used implicitly as part of the path selection algorithm 🙈.
2.2. Advertisement of Link State Information ✨
okay so the new link metrics from the last bit need to get advertised across the whole network 📡 so every router can work out accurate, consistent QoS routes. each router keeps its own updated map of the topology, including the current state of every link (available bandwidth and propagation delay) 🗺️ and the way the link state (metrics) info gets distributed is built on extending OSPF mechanisms 🔥. the detailed format of those extensions is in Section 3, but ngl the when is just as important as the how ⏰.
option one is periodic updates, where the period is picked based on how much load the network and routers can tolerably handle 💅. the downside is that a big change in a link's available bandwidth could sit unknown for a whole period 😭, which means lots of wrong routing decisions. ideally routers would have the freshest possible view of the bandwidth on every link so they can pick the best path 👑. but then you'd need super frequent updates, like every single time a link's available bandwidth changes, and that is neither scalable nor practical 💀. basically there's a trade-off between the protocol overhead of frequent updates and how accurate the network state info is for the path selection algorithm to rely on 🦋. next up are a few link state update policies that strike a practical compromise 🎀.
the core idea is to only trigger link state advertisements when the metric has changed significantly since the last advertisement 🌸. "significant" can be judged on an "absolute" scale or a "relative" one. an absolute scale splits the range of possible metric values into equivalence classes and triggers an update whenever the metric moves enough to cross a class boundary (3) ✨. a relative scale triggers updates when the percentage change in the metric value goes past a predefined threshold 📈. no matter which of those trigger mechanisms you use, you can also add a periodic trigger constraint 🧚. one version is a hold-down timer, which forces a minimum spacing between consecutive updates ⏳. another is a transmit timer, which makes sure an update gets sent once a certain amount of time has passed 🫶. that second one can be really useful if link state updates advertising bandwidth changes are sent unreliably 🙈. the current protocol extensions in Section 3 and the implementation in Section 4 don't do this, because metric updates go out over the standard, reliable OSPF flooding mechanism 🔒. still, it's clearly an extension worth looking into, since it could substantially lower the protocol overhead tied to metrics updates 🍓.
with both the relative and absolute approaches, the metric value in an LSA can be either the actual value or a quantized one 💖. advertising the actual value is more accurate, so it's the better pick when metrics get updated often 🎯. but when updates are rarer, like with a low-sensitivity trigger or hold-down timers, quantized values can be a win 🌈. the reason is that they can increase the number of equal cost paths, which makes things more robust against metric inaccuracies 💜. overall there's a whole big space of accuracy-versus-overhead trade-offs, and picking the right design point is genuinely hard and depends on lots of parameters (see [AGKT98] for a more detailed discussion of these issues) 🤓. so to help you get a better handle on all this, the implementation in Section 4 supports a range of options so you can explore the design space yourself 🔍. Section 4 also reports experimental data on the traffic load and processing overhead that link state updates generate under different configurations 📊.
2.3. Path Selection 👑
there are two major pieces to computing paths for QoS requests 💅. the first is the path selection algorithm itself, meaning which metrics and criteria it relies on 🧠. the second is when the algorithm actually gets invoked ⚡.
the topology the algorithm runs on is, just like standard OSPF path selection, a directed graph 🕸️. its vertices (4) are routers and networks (transit vertices) plus stub networks (non-transit vertices) 🧩. when computing a path, stub networks get added as a post-processing step, which is basically similar to what the current OSPF routing protocol does 🫶. the optimization criteria are reflected in the costs attached to each interface in the topology, and in how those costs get accounted for inside the algorithm 🎀. as mentioned before, a path's cost depends on both its hop count and the amount of available bandwidth 💖. so each interface has a metric attached to it, which corresponds to how much bandwidth is still available on that interface 📶. this metric gets combined with hop count information to produce a cost value, and the goal is to pick the path with the minimum possible number of hops among the ones that can support the requested bandwidth 🦋. when several of those paths are available, the preference goes to the one whose available bandwidth (the smallest value on any of its links) is maximal 📈. the logic behind all this is: we focus on feasible paths (checked against the available bandwidth metric) that use up a minimal amount of network resources (checked against the hop-count metric) ✅; then the rule for choosing among those paths is meant to balance load and maximize the likelihood that the required bandwidth is really there 🌸.
ok heads up, standard routing algorithms are usually single objective optimizations 🙃. they might minimize hop count, or maximize path bandwidth, but not both 💀. double objective path optimization is a way more complex task, and in general it's an intractable problem [GJ79] 😭. BUT because of how specific the two objectives are (bandwidth and hop count), the complexity of the above algorithm is competitive with even that of standard single-objective algorithms 🔥. if you want a thorough treatment of the topic, with insights into how the different algorithms connect to each other, linear algebra, and modification of metrics, [Car79] is the one to read 📚🌈.
before getting into the nitty-gritty of the path selection algorithm, let's quickly look at the options for deciding when to invoke it ⏰. the two main ones are: 1) on-demand computations, meaning you trigger a computation for each new request, and 2) some form of pre-computation 🧚. on-demand has no extra issues around when computations should be triggered, but running the path selection algorithm for every new request can get computationally expensive (see [AT98] for a discussion on this) 🥵. pre-computing paths, on the other hand, spreads the computational cost across multiple requests 💫. the catch is that each computation instance is usually more expensive than in the on-demand case, since paths get computed to all destinations and for all possible bandwidth requests instead of for a single destination and a given bandwidth request 🫠. plus, depending on how often paths get recomputed, the accuracy of the selected paths may be lower 📉. in this document we mainly focus on pre-computed paths, which is also the only method the reference implementation in Section 4 currently supports 🎀. in that case, an important question is when the pre-computation should happen 🤔. the two main options we look at are periodic pre-computations and pre-computations after a given (N) number of updates have been received 💖. the first one gives you a strict bound on the computational load from pre-computations 🔒, while the second can be a more responsive solution 🏃♀️ (5). Section 4 has some experimental results comparing the performance and cost of periodic pre-computations for different period values 📊💜.
2.3.1. Path Computation Algorithm ✨
okay bestie, this section is where the magic happens 🔮 It describes a path selection algorithm that, for a given network topology and link metrics (available bandwidth), pre-computes all possible QoS paths while keeping the computational complexity reasonably low 💅 Specifically, for any destination it pre-computes a minimum hop count path with maximum bandwidth, and it has a computational complexity comparable to that of a standard Bellman-Ford shortest path algorithm 🦋 The Bellman-Ford (BF) shortest path algorithm gets adapted to compute paths of maximum available bandwidth for all hop counts. The best part is that at its h-th iteration, BF identifies the optimal (in our context: maximal bandwidth) path between the source and each destination, among paths of at most h hops 😭
So the cost of a path is a function of its available bandwidth, meaning the smallest available bandwidth on all the links of that path. Finding a minimum cost path is the same thing as finding a maximum bandwidth path 🌈 And because BF progresses by increasing hop count, you basically get the hop count of a path as a second optimization criterion for free 🎀
Here's the flow. At the kth (hop count) iteration, the maximum bandwidth available to all destinations on a path of no more than k hops gets recorded, together with the corresponding routing information 🍓 Once the algorithm terminates, this information gives you, for all destinations and bandwidth requirements, the path with the smallest possible number of hops and sufficient bandwidth to accommodate the new request. This path is also the one with the maximal available bandwidth among all the feasible paths with at most that many hops. Why? Because for any hop count, the algorithm always selects the one with maximum available bandwidth 👑
Now for the deeper dive, including the pseudo-code (which lives in Appendix A 🧚) and the data structure used to record routing information: the QoS routing table that gets built as the algorithm progresses. As mentioned before, the algorithm operates on a directed graph made up only of transit vertices (routers and networks). Stub-networks get added to the path(s) generated by the algorithm afterwards. The metric on each edge is the bandwidth available on the corresponding interface. We'll write b(n;m) for the available bandwidth on the link from node n to m. The vertex for the router running the algorithm (the computing router) is called the "source node" for path selection. The algorithm pre-computes paths from this source node to all possible destination networks and for all possible bandwidth values 💖 At each (hop count) iteration, intermediate results get recorded in a QoS routing table with 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 isbw. 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).
Next up, how the entries get updated as the algorithm proceeds 🫶 For simplicity, we first look at the simpler case where all edges count as "hops," and later we'll explain how zero-hop edges are handled. Zero-hop edges show up with transit network vertices, where only one of the two incoming and outgoing edges should be counted in the hop count computation, since they both correspond to the same physical hop 🙈 Handling this means distinguishing between network and router nodes, and the steps 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. Then the entries in the first column (which corresponds to one-hop paths) for the neighbors of the computing router get modified: the bw field is set to the value of the available bandwidth on the direct edge from the source, and the neighbor field is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path 🌸
After that, the algorithm iterates for at most H iterations (counting the above initial iteration as the first). The value of H could be implicit, i.e., the diameter of the network, or, to better control the worst case complexity, it can be set explicitly to limit 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. The algorithm also keeps a list of nodes that changed their bw value in the previous iteration, i.e., during the (h-1)-th iteration. Then it 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 with at most h hops, and the bw field of entry (m;h) gets 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 so far for destination m with h (or fewer) hops 🔥
Now, zero-hop edges. These are needed because of the possible use of multi-access networks, e.g., T/R, E/N, etc., to interconnect routers. Such entities are also represented by a vertex in the OSPF topology, but a network connecting two routers should clearly be considered a single hop path rather than a two hop path 💅 For example, take 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 EdgesIn 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 🦋
Here's how the algorithm handles zero-hop edges. At each iteration h (starting with the first), whenever an entry (m;h) is modified, it's checked whether there are zero-cost edges (m;k) emerging from node m. This is the case when m is a transit network. If so, 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)) 💜
Last but not least: for simplicity, the issue of equal cost (same hop count and available bandwidth) is not detailed in the description above, but 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. iykyk 🎀
okay so the path selection algorithm runs on a graph whose vertices are ONLY routers and transit networks, not stub networks 💅 that's on purpose, to keep the computation as lowkey cheap as possible, since stub networks can be bolted on afterwards in a post-processing step. this second step is basically like the one OSPF already uses for its normal routing table [Moy98], just with some tweaks because QoS routes are their own whole thing 🦋
Addition of Stub Networks
so after the QoS routing table is built, we loop back through all the router vertices again ✨ for each router, we look at the stub networks whose links show up in that router's link advertisements, and work out which QoS routes can reach them. the QoS info for a stub network is giving the same energy as routers and transit networks. it lives in the QoS routing table as an extra row, and the columns in that row still match paths with different hop counts. each column holds both a bandwidth value and next hop info 🫶 we also assume that an available bandwidth value has been advertised for the stub network. how that number gets decided is out of scope for this doc, so don't come for me about it 🙈
here's how the QoS routes for a stub network S get built:
Every entry in the row for stub network S starts with its bw(s) field set to zero, and its neighbor set set to null. then, whenever stub network S shows up in router V's link advertisement, the value bw(S,h) in column h of S's row gets updated like this:
bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),in that formula, bw(V,h) is the bandwidth value in the matching column of router V's row in the QoS routing table. that's 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. basically the bandwidth of an h hop path to stub network S only gets updated through router V if the smaller of the two (the h hop path to V, and the V to S link) is bigger than what's already there 🔥
the neighbor field gets updated in a similar way, whenever a path through V has bandwidth larger than or equal to the current value. if it's larger, the neighbor field of V in that column replaces S's current neighbor field 👑 if it's equal, then V's neighbor field in that column gets concatenated with S's existing field. so the current set of neighbors for V gets added onto the current set of neighbors for S 🧚
Extracting Forwarding Information from Routing Table
once the QoS paths are precomputed, we need to pull out the forwarding info for a flow that has a given destination and a bandwidth requirement, straight from the routing table 🍓 hop-by-hop routing is the easier case compared to explicit routing, because only the next hop has to be returned instead of a whole explicit route. literally less work 💀
so say there's a new request for destination d, with bandwidth requirement B. the index of the destination vertex picks out which row of the QoS routing table gets checked to make a path. assuming the QoS routing table was built with the Bellman-Ford algorithm (which we'll cover later in this section), the search keeps going by increasing index (hop) count until it finds an entry, say at hop count or column index h, whose bw field is equal to or larger than B. that entry points to the initial information that identifies the chosen path ✨
if the path computation algorithm stores multiple equal cost paths, then you can get some load balancing at path selection time 🌈 a next hop from that list of equivalent next hops can be picked round robin, or randomly, with a probability weighted by the actual available bandwidth on the local interface. the second option is the one used in the implementation described in Section 4 💖
the explicit routing case is covered in Appendix D 🎀
3. OSPF Protocol Extensions ✨
okay so one of our big goals is to keep the additions to the existing OSPF V2 protocol as small as possible, while still giving the level of QoS based routing support we need 🫶 so all the existing OSPF mechanisms, data structures, advertisements, and data formats stay right where they are. this section is where we describe the OSPF extensions needed to support QoS, as set up in the earlier sections 🦋
3.1. QoS -- Optional Capabilities 🎀
the OSPF Options field shows up in OSPF Hello packets, Database Description packets, and all LSAs. it lets OSPF routers support (or not support) optional capabilities, and tell other OSPF routers what their capability level is. that's the whole trick that lets routers with different capabilities coexist inside one OSPF routing domain 🌸 right now the OSPF standard [Moy98] specifies the following 5 bits in the options octet:
+-----------------------------------------------+
| * | * | DC | EA | N/P | MC | E | * |
+-----------------------------------------------+quick side note: the least significant bit (the `T' bit) that used to signal TOS routing capability in the older OSPF spec [Moy94] has been removed 🙈 still, for backward compatibility with earlier OSPF versions, TOS-specific info can be included in router-LSAs, summary-LSAs, and AS-external-LSAs.
here's the plot twist 😭 we propose to reclaim the T' bit as an indicator of a router's QoS routing capability, and call it the Q' bit. honestly, QoS capability can be seen as an extension of the TOS capabilities, and QoS routing is basically a form of TOS-based routing 💜 a router sets this bit in its hello packets to say it can support that kind of routing. when this bit is set in a router or summary links link state advertisement, it means there are QoS fields to process in the packet. when it's set in a network link state advertisement, it means the network described in that advertisement is QoS capable ✨
we have to be careful here so we don't confuse any old style (i.e., RFC 1583 based) TOS routing implementations 😬 the TOS metric encoding rules for the QoS fields, introduced later in this section, show how that's handled. also, unlike RFC 1583, which says unadvertised TOS metrics should be treated as having the same cost as TOS 0, when computing QoS routes, unadvertised TOS metrics (on a hop) mean there's no connectivity for those specific TOS metrics (for that hop) 🚫 bestie, that's a whole plot twist 🍓
3.2. Encoding Resources as Extended TOS 🌸
introducing QoS shouldn't ideally mess with compatibility with existing OSPFv2 routers 💅 so the necessary extensions in packet formats have to be defined in a way that either gets understood by OSPFv2 routers, gets ignored, or in the worst case gets "gracefully" misinterpreted. the nice thing is the TOS field in OSPF packets is longer than what's officially defined in [Alm92], so encoding QoS metrics there lets us mimic the new facility as an extended TOS capability ✨ OSPFv2 routers will either disregard these definitions or treat them as unspecified. there are also specific precautions so that careless OSPF implementations can't mess with traditional TOS routers (if any exist) when they misinterpret the QoS extensions 🛡️
for QoS resources, 32 combinations are available by using the fifth bit in the TOS fields in different LSAs. since [Alm92] defines TOS as being four bits long, this never conflicts with existing values 🙌 and to stop naive implementations that don't look at every bit of the TOS field in OSPF packets from getting confused, the QoS encodings' line up in meaning with the TOS encodings. right now only bandwidth and delay are specified, and their values map onto maximize throughput' and `minimize delay' if you ignore the most significant bit. link reliability and jitter could be defined later if we need them 🦋
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
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 ✨
okay so bestie, the metric field in OSPF packets only gives us 16 bits 😭, and links with bandwidth in the Gbits/s range are literally becoming a thing. So a straight linear encoding of the available resource metric is not feasible 💀. The solution is exponential encoding, using a carefully chosen implicit base value and a split of bits between the mantissa and the exponent 🧚. The detailed reasoning behind this solution isn't in here, but you can find it 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 gives us a simple comparison for two numbers encoded this way, which is super useful when you're implementing it 🎀.
The following table shows the bandwidth ranges covered by different exponents, and the granularity of possible reservations 🌸.
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/sThe bandwidth encoding rule can be summed up 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 |
-----------------So the encoding above 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, which lines up nicely with the idea of cost 🫶.
Now, it might seem a bit pedantic to insist that less bandwidth means a higher number, but it also gives us robustness 🛡️. A router with a poor OSPF implementation could misuse or misunderstand the bandwidth metric as a normal administrative cost, and then compute spanning trees with a "normal" Dijkstra 💀. In that scenario, a heavily congested link advertising a numerically very low cost could be disastrous. It would make the link more attractive for future traffic instead of less 😱. These aren't just theoretical worries, either: similar scenarios have actually been encountered, and you can read about them in [Tan89] 👀.
Let's end with an example 🍓. Say we have a link with a bandwidth of 8 Gbits/s = 1024^3 Bytes/s. Its encoding has an exponent value of 6, since 1024^3= 4,096*8^6. That gives it a granularity of 8^6, or approx. 260 kBytes/s. The associated binary representation is %(110) 0 1000 0000 0000%, or 53,248 (8). The bandwidth cost (advertised value) of this link when it's idle is the 2's complement of the binary representation above, which is %(001) 1 0111 1111 1111%. That corresponds to a decimal value of (2^16 - 1) - 53,248 = 12,287 🌈.
Now say the current reservation level is 6;400 Mbits/s = 200 * 1024^2. That leaves 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. That corresponds to a granularity of 8^5, or approx. 30 kBytes/s, and has the binary representation %(101) 1 1001 0000 0000%, or decimal value 47,360. The advertised cost of the link at this load level is then %(010) 0 0110 1111 1111%, or (2^16-1) -47,360 = 18,175 ✨.
Note that the cost function behaves exactly as it should: the less bandwidth is available on a link, the higher the cost, and the less attractive the link becomes 💖. The targeted property of better granularity for links with less bandwidth available is also achieved 🦋. It's worth pointing out that the numbers in the examples above match the resolution of the proposed encoding exactly, which obviously isn't always the case in practice 🙈. That leaves open the question of how to encode available bandwidth values that don't exactly match the encoding. The standard practice is to round to the closest number. But since we're ultimately interested in the cost value, and it can 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 bandwidth, except the base is defined to be 4 instead of 8 🌸. So the maximum delay that can be expressed is (2^13-1) *4^7 i.e., approx. 134 seconds 🫠.
3.3. Packet Formats 📦
Since we're using 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 that don't understand the Q-bit should either not consider the QoS metrics distributed, or consider those as `unknown' TOS.
To support QoS, there are additions to two Link State Advertisements: the Router Links Advertisement and the Summary Links Advertisement 💜. As mentioned 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. Basically, it assumes that summary links advertisements exist for all networks in the area 🫶. It doesn't discuss the problem of providing support for area address ranges and QoS metric aggregation. That's left for further studies 🔭.
3.5. Open Issues 🚧
Support for AS External Links, Virtual Links, and incremental updates for summary link advertisements isn't addressed in this document, and is left for further study 📝. For Virtual Links that do exist, it's assumed for path selection that these links are non-QoS capable, even if the router advertises QoS capability. Also, as stated earlier, this document doesn't 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 we 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, then present some details on how the QoS extensions were implemented in it. Finally, we discuss issues that came up during the implementation effort, and share some measurement based results on the overhead that the QoS extensions impose on a QoS capable router and on a network of QoS routers 📊. For further details on the implementation study, check out [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 GateD distribution also includes implementations of many popular routing protocols, including OSPF. The GateD environment offers a variety of services that are useful for implementing a routing protocol 🧰. These 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, and 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. On top of that, 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 into the host's kernel forwarding table 🫡.
4.2. Implementing the QoS Extensions of OSPF 🛠️
4.2.1. Design Objectives and Scope ✨
okay bestie, so one of our big goals was getting substantial experience with a totally functional QoS routing implementation 💅 while keeping the overall complexity from getting out of hand 🙈 So the architecture was modular and reused the existing OSPF code with only minimal changes. The QoS stuff got localized into specific modules, and their interaction with the existing OSPF code was kept to a minimum. Not only did that cut down on dev and testing effort, it also made it way easier to experiment with different options for the QoS-specific features, like triggering policies for link state updates and QoS route table computation 🦋 Some of the design choices were also shaped by what we assumed a early prototype of QoS routing had to show off. Here are the important assumptions and requirements:
- Support for only hop-by-hop routing. This affected the path structure in the QoS routing table, since it only needs to store next hop information. As mentioned earlier, the structure can be easily extended to allow construction of explicit routes. 🧚
- Support for path pre-computation. This required creating a separate QoS routing table and its associated path structure, and it 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 so the implementation would be fully functional and usable by others 🫶
- Ability to experiment with different approaches, e.g., different update and pre-computation triggering policies, with support for selecting and parameterizing 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 handled by an API between QoS routing and the local traffic management module, which hides all the 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 leans 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., interoperability 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 design decisions and assumptions above resulted in the architecture shown in Figure 2. It has three major components: the signaling component (RSVP in our case), the QoS routing component, and the traffic manager. For the rest of this section we're zeroing in on the structure and operation of the QoS routing component. As you can see in Figure 2, the QoS routing extensions are further divided into the following modules:
- 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. It 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 onto the GateD implementation of OSPF led to a bunch of issues and design decisions. These issues mostly fell into 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'll briefly talk through these issues and justify the resulting design decisions. 💅
+--------------------------------------------------+
| +-----------------------------+ |
| | 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 architectureokay bestie, so the big question here is how we trigger link state updates when bandwidth availability changes on an interface 🦋 this is literally an essential part of the QoS extensions ✨ Section 2.2 already talked about the triggering and rate-control mechanisms, but OSPF has its own triggering mechanism and its own hold down timer, and those might not play nicely with the QoS updates 😭 so here's how we handled the drama:
- Periodic triggering stays. OSPF triggers its updates periodically and at a low frequency, so we expect those to be only a small part of the total volume of updates. So we kept OSPF's periodic triggering as it was 🌸
- The hold down timer got a glow-up. Turning off the existing OSPF timer was one option, but protection against transient overloads calls for some hold down timer, even a small one 🙈 So we kept the existing OSPF hold down timer and reduced its value to 1 second. That's the lowest possible value, since GateD timers have a maximum resolution of 1 second 💅 It's low enough that it won't get in the way of QoS link state updates, which will often have hold down timers of their own with higher values 🎀
- QoS updates need to know what OSPF is doing. Regular OSPF updates also carry bandwidth information, so the QoS update triggering has to be aware of updates OSPF performs itself. Otherwise it can't properly figure out when to trigger a new link state update 🧚
Another existing OSPF mechanism that could interfere with the QoS routing extensions is delayed acknowledgments 👀 This is the feature that lets OSPF bundle up acknowledgments for multiple LSAs into one go. Link state updates stay in retransmission queues until they're acknowledged, so if the acknowledgment gets delayed too long, and the QoS updates are coming in at higher rates, those queues could overflow 💀 To avoid that mess, we bypassed this mechanism completely, and LSAs received from neighboring routers get acknowledged immediately ✨
We also considered (but didn't implement) making QoS LSAs unreliable, which means getting rid of their acknowledgments altogether so there's no chance of interference 🦋 honestly that would be a reasonable design choice, because QoS LSAs show up much more often than regular LSAs, and losing one has a smaller impact on the protocol. Losing a QoS LSA doesn't interfere with the base operation of OSPF. It only transiently reduces the quality of the paths discovered by QoS routing 🌈
The structure and placement of the QoS routing table is also a juicy implementation topic 🍓 Pre-computed paths get placed into a QoS routing table. This table is built as a set of path structures, one for each destination, and each one holds all the available paths to that destination. To find individual path structures efficiently, you need an access structure 🧚 To keep development effort down, we reused the radix tree structure that the regular GateD routing tables already use 💖 We also kept the QoS routing table independent of the GateD routing tables. That fits the design goal of localizing changes and minimizing the impact on the existing OSPF code ✨ It's also a good reason for keeping QoS routing separate and self-contained: it gets re-computed under conditions that are different from the ones used for the regular routing tables 🎀
Since the QoS routing table is rebuilt frequently, it must be organized so that its computation is efficient 💅 A common operation during that computation is mapping a link state database entry to its corresponding path structure. To make this fast, the link state database entries were extended to contain a pointer to the corresponding path structure 🔥
When a new QoS routing table is about to be computed, the previous one has to be de-allocated 😭 This is done by traversing the radix tree in-order and de-allocating each node in the tree. Honestly that full de-allocation can be pretty wasteful, especially since memory allocation and de-allocation are expensive operations 💀 Also, path pre-computations are typically not triggered by changes in topology, so the set of destinations usually stays the same and matches an unchanged radix tree 👑 That opens the door to a natural optimization: de-allocate only the path structures and keep the radix tree. A further enhancement would be to keep the path structures as well and attempt to incrementally update them only when required 🦋 Even though these gains are tempting, these optimizations weren't included in the initial implementation. The main reason is that they involve subtle and numerous checks to make sure the integrity of the overall data structure holds at all times, for example correctly removing failed destinations from the radix tree and updating the tree accordingly 🙈
4.4. Bandwidth and Processing Overhead of QoS Routing
After finishing the implementation described in the previous sections, we were able to run an experimental study of the cost and nature of the overhead of the QoS routing extensions proposed in this document 🧪 Using a simple setup of two interconnected routers, we could measure the cost of individual QoS routing related operations ✨ Those operations are:
- computation of the QoS routing table,
- selection of a path from the QoS routing table,
- generation of a link state update, and
- reception of a link state update.
Note that the last two operations aren't really specific to QoS routing, since regular OSPF performs them too 🌸 Even so, we expect the more sensitive update triggering mechanisms that effective QoS routing requires to result in more updates. That makes the cost of processing updates an important part of the QoS routing overhead 💅 Another cost dimension is the memory needed to store the QoS routing table 💜 To see how the costs scale as the topology database grows, we artificially populated 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 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 of real memory, running FreeBSD 2.2.5-RELEASE and GateD 4 💻
So what do the results tell us? 👀 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 that can potentially lead to higher processing costs. We investigated this issue in a set of subsequent experiments, which are described later in this section 🔥 The other cost components in Table 1 include memory, and the QoS routing table requires roughly 80% more memory than the regular routing table 🌈 Finally, 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 topology gets bigger. In particular, the storage requirements and the processing costs for both SPF computation and QoS path pre-computation scale almost linearly with network size 💖
________________________________________________________________________
|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 costsOkay so the stand-alone numbers in Table 1 are pretty chill 🧚, but the real question is what QoS routing does to a busy network. You can't just spin up a giant network in a lab, so the authors mixed a simulation with real measurements 💅. They ran a simulation that spits out a timestamped trace of QoS routing events happening on one router in a big network. Then they replayed that trace on a real router and its neighbouring links to create similar load conditions 🦋. That let them measure how much processing the router did and how much bandwidth the QoS updates ate up. If you want the full scoop on the method and the fine print, it's in [AGK99] 📚.
The simulation also lets you mess with the setup, like changing the topology and other QoS knobs: a) the pre-computation period, and b) the threshold that triggers link state updates 🎀. The results came from two topologies. The first is a regular but artificial 8x8 mesh network. The second is isp, which has shown up in several earlier studies [AGKT98, AT98] and roughly copies a nation-wide ISP 🌈. For pre-computation periods they picked 1, 5 and 50 seconds, and for the link state update thresholds they picked 10% and 80% ✨. Those values were chosen because they cover a wide range of how precise the pre-computed paths are and how accurate the link state info at the routers is. Also, 1 second is the smallest pre-computation period GateD lets you use 🙈.
Table 2 shows the processing load on the router, driven by the simulation trace, for both topologies and each mix of pre-computation period and update threshold 💖. Table 3 shows how much bandwidth the QoS updates eat on the links next to that router 🍓.
________________________________________________________________
|_____________________|_________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, the processing load is the percentage of total CPU resources that GateD processing eats up 🔥. The table also shows how well routing performs for each combo of QoS parameters, so you can compare the trade-offs between processing cost and routing performance 💜. Routing performance is measured with the bandwidth blocking ratio. That's the sum of requested bandwidth for requests that got rejected, divided by the total offered bandwidth 🫶. Looking at Table 2, processing load stays low even when the QoS routing table is recomputed every second, and LSAs get generated whenever a link's available bandwidth changes by more than 10% of the last advertised value 😭. So with today's processors, QoS routing doesn't look like a costly upgrade, at least not when it comes to processing 👑. Another thing: network size obviously matters, but it doesn't seem to drastically change how much each parameter matters. Even though isp and mesh are very different, changing the pre-computation period or the update threshold causes basically similar relative changes 🌸.
Table 3 tells the same kind of story for update traffic ✨. In every case, this traffic is only a small slice of the link's capacity 🦋. Obviously the router load and link bandwidth use depend on which router and link got measured, and they'll change for other choices 💅. So treat these results as a rough indication. The fuller discussion is in [AGK99] 🧚.
_______________________________________
|_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 trafficSumming it all up: by actually implementing the proposed QoS routing extensions to OSPF, we showed they're fairly straightforward to build 🎀. And by measuring the real system, we showed the QoS routing overheads aren't excessive, and they're definitely within what modern processor and workstation tech can handle 🌈💖.
5. Security Considerations ✨
Okay bestie, serious moment 🙈. The QoS extensions in this document don't raise any security considerations beyond the ones that come with regular OSPF 🔐. The security considerations for OSPF are covered in [Moy98]. But here's the important part 💀: this document assumes there's some entity responsible for checking whether QoS requests are legit 👑. For example, when the protocol used to start QoS requests is RSVP, that job can be handled with RSVP Policy Decision Points and Policy Enforcement Points, as described in [YPG97] 🛡️. Likewise, a policy server that decides whether QoS requests are acceptable, using the rules and languages from [RMK+98], would also do the job 💜.
APPENDICES 🧚
A. Pseudocode for the BF Based Pre-Computation Algorithm
Heads up, this pseudocode is a little bit of a main character 💅. It assumes a hop-by-hop forwarding approach when it updates the neighbor field 🦋. Supporting explicit route construction needs only straightforward changes 🌸. It also doesn't handle equal cost multi-paths, just to keep things simple 🙈, but adding that support would be straightforward too 🍓.
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;
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;
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.B. On-Demand Dijkstra Algorithm for QoS Path Computation ✨
okay so in the main text we walked through an algorithm that lets you precompute QoS routes 🧠 but sometimes it's totally fine to do the math on-demand instead, the second a QoS route request shows up 💅. the glow-up here is that, depending on how often you recompute those precomputed routes, on-demand can give you better routes because it uses the most recent link metrics available 🦋. another perk is storage! there's no need for a QoS routing table at all 💜. it's basically the classic memory vs. processing cycles trade-off, periodt 🎀.
in this section we give you the quick version of how a standard Dijkstra algorithm can, for a given destination and bandwidth requirement, find a minimum hop path that can fit the required bandwidth and also has the maximum bandwidth 🌈. since OSPF already runs Dijkstra for its regular route computation, we only talk about what's different 🌸. zero-hop edges get left out for simplicity, but supporting them is straightforward ✨.
the algorithm is basically a minimum hop path computation on a graph where every edge with less available bandwidth than the flow asking for it has been removed 🔥. you can do that removal in a pre-processing step, or check the available bandwidth of each edge while the algorithm runs (see the pseudocode that follows 👀). the other tweak is that the list of equal cost next (previous) hops, which gets maintained as the algorithm goes, needs to be sorted by available bandwidth. that's how you pick the minimum hop path with the most bandwidth 👑. or, alternatively, at each step you could keep only the equal hop count path with the maximum available bandwidth. that works out to a cost that's a function of both hop count and available bandwidth 🍓.
Note: the pseudocode below assumes a hop-by-hop forwarding approach when updating the neighbor field 🧚. adding routes to stub networks happens in a second phase, as usual. changes needed to support explicit route construction are straightforward. the pseudocode also doesn't handle equal cost multi-paths, just to keep things simple, but adding that support is also pretty easy to do 🫶.
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;
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.C. Precomputation Using Dijkstra Algorithm
this appendix sketches a Dijkstra-based algorithm for precomputing QoS routes for all destinations and bandwidth values 🌟. the big win of going Dijkstra-based is that it plays really nicely with existing OSPF implementations 💖. the way to compute all the "best" paths is to run shortest path spanning trees one after another, starting from a complete graph and removing any links with less bandwidth than the threshold used in the previous computation 🦋. this gets you paths with possibly better bandwidth, but of course more hops 🙈. yes, that's a lot of Dijkstra runs, but several optimizations, like incremental spanning tree computation, can keep things efficient in both complexity and storage. the structure of the computed paths also leans itself toward path compression [ST83] 💅. details, measurements and applicability studies can be found in [Prz95] and [BP95] 📚.
a variation on this theme is to trade some "accuracy" in the precomputed paths (the paths generated might have a larger hop count than needed) for a simpler, modified Dijkstra shortest path algorithm, and some saved computation too 🌈. the loss in accuracy comes from relying on quantized bandwidth values, which are used when computing a minimum hop count path 🍓. so the range of possible bandwidth values a new flow can request gets mapped onto a fixed number of quantized values, and minimum hop count paths are generated for each quantized value. for example, you could say bandwidth values are quantized as low, medium, and high, and minimum hop count paths get computed for each of those three. a new flow then gets assigned to the minimum hop path that can carry the smallest quantized value (low, medium, or high) that's larger than or equal to what it asked for ✨. we're only going to talk about this "quantized" version here 🎀.
again, we're looking at the elementary case where all edges count as "hops", and the change needed to support zero-hop edges is straightforward 🫶.
like with the BF algorithm, this one relies on a routing table that gets built as the algorithm progresses 💜. the routing table is structured like this:
The QoS routing table:
- a K x Q matrix, where K is the number of vertices and Q is the number of quantized bandwidth values.
- The (n;q) entry contains information that identifies the minimum hop count path to destination n, 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 runs on a directed graph again, where vertices correspond to routers and transit networks 🌸. the metric on each edge 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 router where the algorithm is running becomes the source node for path selection, and the algorithm computes paths to all the other nodes (destinations) 👑.
starting with the highest quantization index, Q, the algorithm works through the indices one by one, in decreasing order 🔥. for each index q, it deletes from the original network topology every link (n;m) where b(n;m) < bw[q], and then runs a Dijkstra-based minimum hop count algorithm (10) on what's left, between the source node and all the other nodes (vertices) in the graph 🧚. just like with the Dijkstra used for on-demand path computation, removing links where b(n;m) < bw[q] could also be done while the algorithm is running 👀.
once the algorithm finishes, the q-th column of the routing table gets updated 🦋. that means recording the hop count of the path the algorithm generated in the hops field, and updating the neighbor field. same as before, how the neighbor field gets updated depends on the scope of the path computation. for hop-by-hop routing decisions, the neighbor field is set to the identity of the node adjacent to the source node (the next hop) on the path the algorithm returned 💖. but here's the twist: to make sure the path with the maximal available bandwidth is always picked among all minimum hop paths that can accommodate a given quantized bandwidth, a slightly different update for the neighbor field is needed in some cases 🌈. specifically, when, for a given row (destination node n), the hops value in column q equals the value in column q+1 (here we assume q<Q), meaning paths that can accommodate bw[q] and bw[q+ 1] have the same hop count, then the algorithm copies the neighbor value from entry (n;q+1) into entry (n;q) 💅.
Note: the pseudocode below would assume a hop-by-hop forwarding approach when updating the neighbor field 🫶. the changes needed to support explicit route construction are straightforward. the pseudocode also doesn't handle equal cost multi-paths, for simplicity, but the change needed to add that support has already been described above 🍓. details of the post-processing step that adds stub networks are left out 🙈.
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 */
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 */
end.D. Explicit Routing Support ✨
Okay so, path selection can go two ways. Either it just hands back the next hop for the flow, or it gives you the whole path it computed, which is called an explicit route 💅. Those two outputs are different, so building them asks different things from the algorithm and the data structures underneath. We've been talking about hop-by-hop routing this whole time, but the same algorithms can make explicit routes with a few small tweaks. Let's go! 🦋
The big idea is to update the neighbor field differently than you do for hop-by-hop routing (the way described in Section 2.3). Remember, in the path computation algorithms the neighbor field points to the router adjacent to the source on the partial path. That's how the source gets its next hop. For explicit routing, the neighbor info instead points to the previous router on the path. It's giving reverse engineering 🌸
There can be several equivalent paths for the same hop count, so the neighbor info gets stored as a list instead of a single value. Each neighbor also carries extra info so load balancing can happen between those paths when it's time to pick one. Specifically, we store the advertised available bandwidth on the link from that neighbor to the destination in the entry. 💖
To pull out the full list of vertices, you go backwards from the destination to the origin vertex, recursively. You step through the precomputed QoS routing table from vertex to vertex, and at each step you look at the corresponding neighbor (precursor) info. It's called recursive because the neighbor you find in one step becomes the destination for the table lookup in the next step. Once you reach the source router, you concatenate all the neighbor fields you pulled out and boom, that's your explicit route 👑. This works for the algorithm in Section 2.3.1 and for Appendix C. If there are multiple neighbor choices at a stage (because of equal cost multi-paths), you can pick one at random, with the odds weighted by, for example, the bandwidth on the link from that neighbor to the current destination 🎲
Now say there's a new request to destination d with bandwidth requirement B. The destination's index picks the row in the QoS routing table you need to check, and then you search that row for a suitable path. If you used the Bellman-Ford algorithm from Section 2.3.1, you search by increasing index (hop count) until you find an entry, say at hop count or column index h, whose bw field is equal to or greater than B. That entry points to the initial info identifying the selected path. If you used the Dijkstra algorithm from Appendix C, you first find the first quantized value qB such that qB >= B, and the associated column tells you the first entry in the routing table that identifies the selected path. 🧚
Once you've found that first entry, rebuilding the full vertex list works the same way whether the table came from Section 2.3.1 or Appendix C. In both cases the neighbor field in each entry points to the previous node on the path from the source node, with the same bandwidth capabilities as the current entry. So you follow the neighbor pointers of successive entries and the complete path is reconstructed. ✨
With the Bellman-Ford algorithm from Section 2.3.1, this means moving backwards through the table, column by column, and at each step using the row index that the neighbor field of the entry in the previous column points to. Every time, the vertex index in the neighbor field gets pre-pended to the list you've built so far. Since we start at column h, the process ends after h steps, once the first column is reached, and then the list of vertices making up the path is done. 🎀
With the Dijkstra algorithm from Appendix C, backtracking is similar but slightly different, because a column now corresponds to a quantized bandwidth value instead of a hop count. You follow the column matching the quantized bandwidth value needed to satisfy the flow's bandwidth requirements. At each step the vertex index in the neighbor field is pre-pended to the list built so far, and it's used to find the next row to move to. The process ends when you reach an entry whose neighbor field specifies the origin vertex of the flow. 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 ends 😭
Finding the first entry in the routing table is identical to what's described for the hop-by-hop case. The difference is that when building the QoS routing tables, the neighbor fields get updated differently for explicit and hop-by-hop routing. If you need to support both, you can keep two different neighbor fields in each entry and update both of them together. 🫶
Endnotes 🎀
- 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.
- This is true for uni-cast flows, but in the case of multi-cast flows, hop-by-hop and explicit routing clearly have different implications.
- Some hysteresis mechanism should be added to suppress updates when the metric value oscillates around a class boundary.
- In this document, we use the terms node and vertex interchangeably.
- 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.
- Modifications to support explicit routing are discussed in Appendix D.
- 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.
- Exponent in parentheses.
- Access to some of the more recent versions of the GateD software is restricted to the GateD consortium members.
- 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 ✨
bestie, this is the reading list 📚💅 Every single source the RFC leans on is listed here, so scroll and enjoy the vintage vibes 🧚
[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.
[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.Authors' Addresses 🌸
Meet the squad behind this whole thing 🫶 Here's how to reach each of them, typos and all:
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
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.comFull Copyright Statement 📜
Legal time, but make it cute 🎀 This is the copyright part, so the wording stays serious even though the vibe is light.
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. 💖 And that's a wrap on RFC 2676, periodt ✨
📦 where this page comes from
- ietf: rfc2676 1999-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms