Network Working Group G. Apostolopoulos
`Request for Comments: 2676 D. Williams
`Category: Experimental IBM
` S. Kamat
` Lucent
` R. Guerin
` UPenn
` A. Orda
` Technion
` T. Przygienda
` Siara Systems
` August 1999
`
` QoS Routing Mechanisms and OSPF Extensions
`
`Status of this Memo
`
` This memo defines an Experimental Protocol for the Internet
` community. It does not specify an Internet standard of any kind.
` Discussion and suggestions for improvement are requested.
` Distribution of this memo is unlimited.
`
`Copyright Notice
`
` Copyright (C) The Internet Society (1999). All Rights Reserved.
`
`Abstract
`
` This memo describes extensions to the OSPF [Moy98] protocol to
` support QoS routes. The focus of this document is on the algorithms
` used to compute QoS routes and on the necessary modifications to OSPF
` to support this function, e.g., the information needed, its format,
` how it is distributed, and how it is used by the QoS path selection
` process. Aspects related to how QoS routes are established and
` managed are also briefly discussed. The goal of this document is to
` identify a framework and possible approaches to allow deployment of
` QoS routing capabilities with the minimum possible impact to the
` existing routing infrastructure.
`
` In addition, experience from an implementation of the proposed
` extensions in the GateD environment [Con], along with performance
` measurements is presented.
`
`Apostolopoulos, et al. Experimental [Page 1]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 1
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
`Table of Contents
`
` 1. Introduction 3
` 1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3
` 1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5
` 2. Path Selection Information and Algorithms 7
` 2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
` 2.2. Advertisement of Link State Information . . . . . . . . . 8
` 2.3. Path Selection . . . . . . . . . . . . . . . . . . . . .10
` 2.3.1. Path Computation Algorithm . . . . . . . . . . .11
` 3. OSPF Protocol Extensions 16
` 3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . .17
` 3.2. Encoding Resources as Extended TOS . . . . . . . . . . .17
` 3.2.1. Encoding bandwidth resource . . . . . . . . . . .19
` 3.2.2. Encoding Delay . . . . . . . . . . . . . . . . .21
` 3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . .21
` 3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22
` 3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22
` 4. A Reference Implementation based on GateD 22
` 4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22
` 4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23
` 4.2.1. Design Objectives and Scope . . . . . . . . . . .23
` 4.2.2. Architecture . . . . . . . . . . . . . . . . . .24
` 4.3. Major Implementation Issues . . . . . . . . . . . . . . .25
` 4.4. Bandwidth and Processing Overhead of QoS Routing . . . .29
` 5. Security Considerations 32
` A. Pseudocode for the BF Based Pre-Computation Algorithm 33
` B. On-Demand Dijkstra Algorithm for QoS Path Computation 36
` C. Precomputation Using Dijkstra Algorithm 39
` D. Explicit Routing Support 43
` Endnotes 45
` References 46
` Authors’ Addresses 48
` Full Copyright Statement 50
`
`Apostolopoulos, et al. Experimental [Page 2]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 2
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
`1. Introduction
`
` In this document, we describe a set of proposed additions to the OSPF
` routing protocol (these additions have been implemented on top of the
` GateD [Con] implementation of OSPF V2 [Moy98]) to support Quality-
` of-Service (QoS) routing in IP networks. Support for QoS routing can
` be viewed as consisting of three major components:
`
` 1. Obtain the information needed to compute QoS paths and select a
` path capable of meeting the QoS requirements of a given request,
`
` 2. Establish the path selected to accommodate a new request,
`
` 3. Maintain the path assigned for use by a given request.
`
` Although we touch upon aspects related to the last two components,
` the focus of this document is on the first one. In particular, we
` discuss the metrics required to support QoS, the extension to the
` OSPF link state advertisement mechanism to propagate updates of QoS
` metrics, and the modifications to the path selection to accommodate
` QoS requests. The goal of the extensions described in this document
` is to improve performance for QoS flows (likelihood to be routed on a
` path capable of providing the requested QoS), with minimal impact on
` the existing OSPF protocol and its current implementation. Given the
` inherent complexity of QoS routing, achieving this goal obviously
` implies trading-off "optimality" for "simplicity", but we believe
` this to be required in order to facilitate deployment of QoS routing
` capabilities.
`
` In addition to describing the proposed extensions to the OSPF
` protocol, this document also reports experimental data based on
` performance measurements of an implementation done on the GateD
` platform (see Section 4).
`
`1.1. Overall Framework
`
` We consider a network (1) that supports both best-effort packets and
` packets with QoS guarantees. The way in which the network resources
` are split between the two classes is irrelevant, except for the
` assumption that each QoS capable router in the network is able to
` dedicate some of its resources to satisfy the requirements of QoS
` packets. QoS capable routers are also assumed capable of identifying
` and advertising resources that remain available to new QoS flows. In
` addition, we limit ourselves to the case where all the routers
` involved support the QoS extensions described in this document, i.e.,
` we do not consider the problem of establishing a route in a
` heterogeneous environment where some routers are QoS-capable and
` others are not. Furthermore, in this document, we focus on the case
`
`Apostolopoulos, et al. Experimental [Page 3]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 3
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` of unicast flows, although many of the additions we define are
` applicable to multicast flows as well.
`
` We assume that a flow with QoS requirements specifies them in some
` fashion that is accessible to the routing protocol. For example,
` this could correspond to the arrival of an RSVP [RZB+97] PATH
` message, whose TSpec is passed to routing together with the
` destination address. After processing such a request, the routing
` protocol returns the path that it deems the most suitable given the
` flow’s requirements. Depending on the scope of the path selection
` process, this returned path could range from simply identifying the
` best next hop, i.e., a hop-by-hop path selection model, to specifying
` all intermediate nodes to the destination, i.e., an explicit route
` model. The nature of the path being returned impacts the operation
` of the path selection algorithm as it translates into different
` requirements for constructing and returning the appropriate path
` information. However, it does not affect the basic operation of the
` path selection algorithm (2).
`
` For simplicity and also because it is the model currently supported
` in the implementation (see Section 4 for details), in the rest of
` this document we focus on the hop-by-hop path selection model. The
` additional modifications required to support an explicit routing
` model are discussed in appendix D, but are peripheral to the main
` focus of this document which concentrates on the specific extensions
` to the OPSF protocol to support computation of QoS routes.
`
` In addition to the problem of selecting a QoS path and possibly
` reserving the corresponding resources, one should note that the
` successful delivery of QoS guarantees requires that the packets of
` the associated "QoS flow" be forwarded on the selected path. This
` typically requires the installation of corresponding forwarding state
` in the router. For example, with RSVP [RZB+97] flows a classifier
` entry is created based on the filter specs contained in the RESV
` message. In the case of a Differentiated Service [KNB98] setting,
` the classifier entry may be based on the destination address (or
` prefix) and the corresponding value of the DS byte. The mechanisms
` described in this document are at the control path level and are,
` therefore, independent of data path mechanisms such as the packet
` classification method used. Nevertheless, it is important to notice
` that consistent delivery of QoS guarantees implies stability of the
` data path. In particular, while it is possible that after a path is
` first selected, network conditions change and result in the
` appearance of "better" paths, such changes should be prevented from
` unnecessarily affecting existing paths. In particular, switching
` over to a new (and better) path should be limited to specific
` conditions, e.g., when the initial selection turns out to be
` inadequate or extremely "expensive". This aspect is beyond the scope
`
`Apostolopoulos, et al. Experimental [Page 4]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 4
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` of QoS routing and belongs to the realm of path management, which is
` outside the main focus of this document. However, because of its
` potentially significant impact on the usefulness of QoS routing, we
` briefly outline a possible approach to path management.
`
` Avoiding unnecessary changes to QoS paths requires that state
` information be maintained for each QoS path after it has been
` selected. This state information is used to track the validity of
` the path, i.e., is the current path adequate or should QoS routing be
` queried again to generate a new and potentially better path. We say
` that a path is "pinned" when its state specifies that QoS routing
` need not be queried anew, while a path is considered "un-pinned"
` otherwise. The main issue is then to define how, when, and where
` path pinning and un-pinning is to take place, and this will typically
` depend on the mechanism used to request QoS routes. For example,
` when the RSVP protocol is the mechanism being used, it is desirable
` that path management be kept as synergetic as possible with the
` existing RSVP state management. In other words, pinning and un-
` pinning of paths should be coordinated with RSVP soft states, and
` structured so as to require minimal changes to RSVP processing rules.
` A broad RSVP-routing interface that enables this is described in
` [GKR97]. Use of such an interface in the context of reserving
` resources along an explicit path with RSVP is discussed in [GLG+97].
` Details of path management and a means for avoiding loops in case of
` hop-by-hop path setup can be found in [GKH97], and are not addressed
` further in this document.
`
`1.2. Simplifying Assumptions
`
` In order to achieve our goal of minimizing impact to the existing
` protocol and implementation, we impose certain restrictions on the
` range of extensions we initially consider to support QoS. The first
` restriction is on the type of additional (QoS) metrics that will be
` added to Link State Advertisements (LSAs) for the purpose of
` distributing metrics updates. Specifically, the extensions to LSAs
` that we initially consider, include only available bandwidth and
` delay. In addition, path selection is itself limited to considering
` only bandwidth requirements. In particular, the path selection
` algorithm selects paths capable of satisfying the bandwidth
` requirement of flows, while at the same time trying to minimize the
` amount of network resources that need to be allocated, i.e., minimize
` the number of hops used.
`
` This focus on bandwidth is adequate in most instances, and meant to
` keep initial complexity at an acceptable level. However, it does not
` fully capture the complete range of potential QoS requirements. For
` example, a delay-sensitive flow of an interactive application could
` be put on a path using a satellite link, if that link provided a
`
`Apostolopoulos, et al. Experimental [Page 5]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 5
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` direct path and had plenty of unused bandwidth. This would clearly
` be an undesirable choice. Our approach to preventing such poor
` choices, is to assign delay-sensitive flows to a "policy" that would
` eliminate from the network all links with high propagation delay,
` e.g., satellite links, before invoking the path selection algorithm.
` In general, multiple policies could be used to capture different
` requirements, each presenting to the path selection algorithm a
` correspondingly pruned network topology, on which the same algorithm
` would be used to generate an appropriate path. Alternatively,
` different algorithms could be used depending on the QoS requirements
` expressed by an incoming request. Such extensions are beyond the
` scope of this document, which limits itself to describing the case of
` a single metric, bandwidth. However, it is worth pointing out that a
` simple extension to the path selection algorithm proposed in this
` document allows us to directly account for delay, under certain
` conditions, when rate-based schedulers are employed, as in the
` Guaranteed Service proposal [SPG97]; details can be found in [GOW97].
`
` Another important aspect to ensure that introducing support for QoS
` routing has the minimal possible impact, is to develop a solution
` that has the smallest possible computing overhead. Additional
` computations are unavoidable, but it is desirable to keep the
` computational cost of QoS routing at a level comparable to that of
` traditional routing algorithms. One possible approach to achieve
` this goal, is to allow pre-computation of QoS routes. This is the
` method that was chosen for the implementation of the QoS extensions
` to OSPF and is, therefore, the one described in detail in this
` document. Alternative approaches are briefly reviewed in appendices.
` However, it should be noted that although several alternative path
` selection algorithms are possible, the same algorithm should be used
` consistently within a given routing domain. This requirement may be
` relaxed when explicit routing is used, as the responsibility for
` selecting a QoS path lies with a single entity, the origin of the
` request, which then ensures consistency even if each router uses a
` different path selection algorithm. Nevertheless, the use of a
` common path selection algorithm within an AS is recommended, if not
` necessary, for proper operation.
`
` A last aspect of concern regarding the introduction of QoS routing,
` is to control the overhead associated with the additional link state
` updates caused by more frequent changes to link metrics. The goal is
` to minimize the amount of additional update traffic without adversely
` affecting the performance of path selection. In Section 2.2, we
` present a brief discussion of various alternatives that trade
` accuracy of link state information for protocol overhead. Potential
` enhancements to the path selection algorithm, which seek to
` (directly) account for the inaccuracies in link metrics, are
` described in [GOW97], while a comprehensive treatment of the subject
`
`Apostolopoulos, et al. Experimental [Page 6]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 6
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` can be found in [LO98, GO99]. In Section 4, we also describe the
` design choices made in a reference implementation, to allow future
` extensions and experimentation with different link state update
` mechanisms.
`
` The rest of this document is structured as follows. In Section 2, we
` describe the general design choices and mechanisms we rely on to
` support QoS request. This includes details on the path selection
` metrics, link state update extensions, and the path selection
` algorithm itself. Section 3 focuses on the specific extensions that
` the OSPF protocol requires, while Section 4 describes their
` implementation in the GateD platform and also presents some
` experimental results. Section 5 briefly addresses security issues
` that the proposed schemes may raise. Finally, several appendices
` provide additional material of interest, e.g., alternative path
` selection algorithms and support for explicit routes, but somewhat
` outside the main focus of this document.
`
`2. Path Selection Information and Algorithms
`
` This section reviews the basic building blocks of QoS path selection,
` namely the metrics on the which the routing algorithm operates, the
` mechanisms used to propagate updates for these metrics, and finally
` the path selection algorithm itself.
`
`2.1. Metrics
`
` The process of selecting a path that can satisfy the QoS requirements
` of a new flow relies on both the knowledge of the flow’s requirements
` and characteristics, and information about the availability of
` resources in the network. In addition, for purposes of efficiency,
` it is also important for the algorithm to account for the amount of
` resources the network has to allocate to support a new flow. In
` general, the network prefers to select the "cheapest" path among all
` paths suitable for a new flow, and it may even decide not to accept a
` new flow for which a feasible path exists, if the cost of the path is
` deemed too high. Accounting for these aspects involves several
` metrics on which the path selection process is based. They include:
`
` - Link available bandwidth: As mentioned earlier, we currently
` assume that most QoS requirements are derivable from a rate-
` related quantity, termed "bandwidth." We further assume that
` associated with each link is a maximal bandwidth value, e.g., the
` link physical bandwidth or some fraction thereof that has been set
` aside for QoS flows. Since for a link to be capable of accepting
` a new flow with given bandwidth requirements, at least that much
` bandwidth must be still available on the link, the relevant link
` metric is, therefore, the (current) amount of available (i.e.,
`
`Apostolopoulos, et al. Experimental [Page 7]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 7
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` unallocated) bandwidth. Changes in this metric need to be
` advertised as part of extended LSAs, so that accurate information
` is available to the path selection algorithm.
`
` - Link propagation delay: This quantity is meant to identify high
` latency links, e.g., satellite links, which may be unsuitable for
` real-time requests. This quantity also needs to be advertised as
` part of extended LSAs, although timely dissemination of this
` information is not critical as this parameter is unlikely to
` change (significantly) over time. As mentioned earlier, link
` propagation delay can be used to decide on the pruning of specific
` links, when selecting a path for a delay sensitive request; also,
` it can be used to support a related extension, as described in
` [GOW97].
`
` - Hop-count: This quantity is used as a measure of the path cost to
` the network. A path with a smaller number of hops (that can
` support a requested connection) is typically preferable, since it
` consumes fewer network resources. As a result, the path selection
` algorithm will attempt to find the minimum hop path capable of
` satisfying the requirements of a given request. Note that
` contrary to bandwidth and propagation delay, hop count is a metric
` that does not affect LSAs, and it is only used implicitly as part
` of the path selection algorithm.
`
`2.2. Advertisement of Link State Information
`
` The new link metrics identified in the previous section need to be
` advertised across the network, so that each router can compute
` accurate and consistent QoS routes. It is assumed that each router
` maintains an updated database of the network topology, including the
` current state (available bandwidth and propagation delay) of each
` link. As mentioned before, the distribution of link state (metrics)
` information is based on extending OSPF mechanisms. The detailed
` format of those extensions is described in Section 3, but in addition
` to how link state information is distributed, another important
` aspect is when such distribution is to take place.
`
` One option is to mandate periodic updates, where the period of
` updates is determined based on a tolerable corresponding load on the
` network and the routers. The main disadvantage of such an approach
` is that major changes in the bandwidth available on a link could
` remain unknown for a full period and, therefore, result in many
` incorrect routing decisions. Ideally, routers should have the most
` current view of the bandwidth available on all links in the network,
` so that they can make the most accurate decision of which path to
` select. Unfortunately, this then calls for very frequent updates,
` e.g., each time the available bandwidth of a link changes, which is
`
`Apostolopoulos, et al. Experimental [Page 8]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 8
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` neither scalable nor practical. In general, there is a trade-off
` between the protocol overhead of frequent updates and the accuracy of
` the network state information that the path selection algorithm
` depends on. We outline next a few possible link state update
` policies, which strike a practical compromise.
`
` The basic idea is to trigger link state advertisements only when
` there is a significant change in the value of metrics since the last
` advertisement. The notion of significance of a change can be based
` on an "absolute" scale or a "relative" one. An absolute scale means
` partitioning the range of values that a metric can take into
` equivalence classes and triggering an update whenever the metric
` changes sufficiently to cross a class boundary (3). A relative
` scale, on the other hand, triggers updates when the percentage change
` in the metric value exceeds a predefined threshold. Independent of
` whether a relative or an absolute change trigger mechanism is used, a
` periodic trigger constraint can also be added. This constraint can
` be in the form of a hold-down timer, which is used to force a minimum
` spacing between consecutive updates. Alternatively, a transmit timer
` can also be used to ensure the transmission of an update after a
` certain time has expired. Such a feature can be useful if link state
` updates advertising bandwidth changes are sent unreliably. The
` current protocol extensions described in Section 3 as well as the
` implementation of Section 4 do not consider such an option as metric
` updates are sent using the standard, and reliable, OSPF flooding
` mechanism. However, this is clearly an extension worth considering
` as it can help lower substantially the protocol overhead associated
` with metrics updates.
`
` In both the relative and absolute change approaches, the metric value
` advertised in an LSA can be either the actual or a quantized value.
` Advertising the actual metric value is more accurate and, therefore,
` preferable when metrics are frequently updated. On the other hand,
` when updates are less frequent, e.g., because of a low sensitivity
` trigger or the use of hold-down timers, advertising quantized values
` can be of benefit. This is because it can help increase the number
` of equal cost paths and, therefore, improve robustness to metrics
` inaccuracies. In general, there is a broad space of possible trade-
` offs between accuracy and overhead and selecting an appropriate
` design point is difficult and depends on many parameters (see
` [AGKT98] for a more detailed discussion of these issues). As a
` result, in order to help acquire a better understanding of these
` issues, the implementation described in Section 4 supports a range of
` options that allow exploration of the available design space. In
` addition, Section 4 also reports experimental data on the traffic
` load and processing overhead generated by links state updates for
` different configurations.
`
`Apostolopoulos, et al. Experimental [Page 9]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 9
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
`2.3. Path Selection
`
` There are two major aspects to computing paths for QoS requests. The
` first is the actual path selection algorithm itself, i.e., which
` metrics and criteria it relies on. The second is when the algorithm
` is actually invoked.
`
` The topology on which the algorithm is run is, as with the standard
` OSPF path selection, a directed graph where vertices (4) consist of
` routers and networks (transit vertices) as well as stub networks
` (non-transit vertices). When computing a path, stub networks are
` added as a post-processing step, which is essentially similar to what
` is done with the current OSPF routing protocol. The optimization
` criteria used by the path selection are reflected in the costs
` associated with each interface in the topology and how those costs
` are accounted for in the algorithm itself. As mentioned before, the
` cost of a path is a function of both its hop count and the amount of
` available bandwidth. As a result, each interface has associated with
` it a metric, which corresponds to the amount of bandwidth that
` remains available on this interface. This metric is combined with
` hop count information to provide a cost value, whose goal is to pick
` a path with the minimum possible number of hops among those that can
` support the requested bandwidth. When several such paths are
` available, the preference is for the path whose available bandwidth
` (i.e., the smallest value on any of the links in the path) is
` maximal. The rationale for the above rule is the following: we
` focus on feasible paths (as accounted by the available bandwidth
` metric) that consume a minimal amount of network resources (as
` accounted by the hop-count metric); and the rule for selecting among
` these paths is meant to balance load as well as maximize the
` likelihood that the required bandwidth is indeed available.
`
` It should be noted that standard routing algorithms are typically
` single objective optimizations, i.e., they may minimize the hop-
` count, or maximize the path bandwidth, but not both. Double
` objective path optimization is a more complex task, and, in general,
` it is an intractable problem [GJ79]. Nevertheless, because of the
` specific nature of the two objectives being optimized (bandwidth and
` hop count), the complexity of the above algorithm is competitive with
` even that of standard single-objective algorithms. For readers
` interested in a thorough treatment of the topic, with insights into
` the connection between the different algorithms, linear algebra and
` modification of metrics, [Car79] is recommended.
`
` Before proceeding with a more detailed description of the path
` selection algorithm itself, we briefly review the available options
` when it comes to deciding when to invoke the algorithm. The two main
` options are: 1) to perform on-demand computations, that is, trigger
`
`Apostolopoulos, et al. Experimental [Page 10]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1039, p. 10
`
`

`
`
`RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
`
` a computation for each new request, and 2) to use some form of pre-
` computation. The on-demand case involves no additional issues in
` terms of when computations should be triggered, but running the path
` selection algorithm for each new request can be computationally
` expensive (see [AT98] for a discussion on this issue). On the other
` hand, pre-computing paths amortizes the computational cost over
` multiple requests, but each computation instance is usually more
` expensive than in the on-demand case (paths are computed to all
` destinations and for all possible bandwidth requests rather than for
` a single destination and a given bandwidth request). Furthermore,
` depending on how often paths are recomputed, the accuracy of the
` selected paths may be lower. In this document, we primarily focus on
` the case of pre-computed paths, which is also the only method
` currently supported in the reference implementation described in
` Section 4. In this case, clearly, an important issue is when such
` pre-computation should take place. The two main options we consider
` are periodic pre-computations and pre-computations after a given (N)
` number of updates have been received. The former has the benefit of
` ensuring a strict bound on the computational load associated with
` pre-computations, while the latter can provide for a more responsive
` solution (5). Section 4 provides some experimental results comparing
` the performance and cost of periodic pre-computations for different
` period values.
`
`2.3.1. Path Computation Algorithm
`
` This section describes a path selection algorithm, which for a given
` network topology and link metrics (available bandwidth), pre-computes
` all possible QoS paths, while maintaining a reasonably low
` computational complexity. Specifically, the algorithm pre-computes
` for any destination a minimum hop count path with maximum bandwidth,
` and has a computational complexity comparable to that of a standard
` Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest
` path algorithm is adapted to compute paths of maximum available
` bandwidth for all hop counts. It is a property of the BF algorithm
`