Internet Engineering Task Force R. Guerin/A. Orda/D. Williams
`INTERNET DRAFT IBM/Technion/IBM
` 5 November 1996
`
` QoS Routing Mechanisms and OSPF Extensions
` draft-guerin-qos-routing-ospf-00.txt
`
`Status of This Memo
`
` This document is an Internet-Draft. Internet Drafts are working
` documents of the Internet Engineering Task Force (IETF), its Areas,
` and its Working Groups. Note that other groups may also distribute
` working documents as Internet Drafts.
`
` Internet Drafts are draft documents valid for a maximum of six
` months, and may be updated, replaced, or obsoleted by other documents
` at any time. It is not appropriate to use Internet Drafts as
` reference material, or to cite them other than as a ‘‘working draft’’
` or ‘‘work in progress.’’
`
` To learn the current status of any Internet-Draft, please check
` the ‘‘1id-abstracts.txt’’ listing contained in the internet-drafts
` Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net
` (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific
` Rim).
`
`Abstract
`
` This memo describes extensions to the OSPF protocol to support QoS
` routes. The focus of the document is on the algorithms used to
` compute QoS routes and on the necessary modifications to OSPF to
` support this function, e.g., the information needed, its format,
` how it is distributed, and how it is used by the QoS path selection
` process. Aspects related to how QoS routes are established and
` managed are also briefly discussed, but the development of detailed
` specifications is left for further study. The goal of this
` document is to identify a framework and possible approaches to allow
` deployment of QoS routing capabilities with the minimum possible
` impact to the existing routing infrastructure.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page i]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. i
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` Contents
`
`Status of This Memo i
`
`Abstract i
`
` 1. Introduction 1
` 1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 1
` 1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 2
`
` 2. Path Selection Information and Algorithms 3
` 2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 4
` 2.2. Advertisement of Link State Information . . . . . . . . . 5
` 2.3. Path Selection Algorithms . . . . . . . . . . . . . . . . 6
` 2.3.1. Algorithm for exact pre-computed QoS paths . . . 7
` 2.3.2. Algorithm for on-demand computation of QoS paths 10
` 2.3.3. Algorithm for approximate pre-computed QoS paths 11
`
` 3. Establishment and Maintenance of QoS Routes 14
`
` 4. OSPF Protocol Enhancements 15
` 4.1. QoS -- Optional Capabilities . . . . . . . . . . . . . . 15
` 4.2. Packet Formats . . . . . . . . . . . . . . . . . . . . . 16
` 4.2.1. Router Links Advertisements . . . . . . . . . . . 16
` 4.2.2. Summary Link Advertisement . . . . . . . . . . . 17
` 4.3. Calculating the inter-area routes . . . . . . . . . . . . 18
` 4.4. Open Issues . . . . . . . . . . . . . . . . . . . . . . . 18
`
` A. Construction of Path Information 19
` A.1. Source routed paths . . . . . . . . . . . . . . . . . . . 19
` A.2. Hop-by-Hop Routing . . . . . . . . . . . . . . . . . . . 21
`
` B. Computational Complexity 21
`
` C. Extension: Handling Propagation Delays 22
`
` D. Zero-Hop Edges 23
`
` E. Sample Path Establishment Scenario 24
`
` F. Pseudocode for BF Algorithm 26
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page ii]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. ii
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
`1. Introduction
`
` In this document we describe a set of proposed additions to the
` OSPF routing protocol (the additions are built on top of OSPF V2)
` to support Quality-of-Service (QoS) routing in IP. In particular we
` discuss the metrics required to support QoS, the associated link
` advertisement mechanisms, the path selection algorithm, as well
` as aspects of route establishment (pinning and unpinning). Our
` goals are to define an approach which while achieving the goals of
` improving performance for QoS flows (likelihood to be routed on a
` path capable of providing the requested QoS), does so with the least
` possible impact on the existing OSPF protocol. Given the inherent
` complexity of QoS routing, achieving this goal obviously implies
` trading-off ‘‘optimality’’ for ‘‘simplicity’’, but we believe this
` to be required in order to facilitate deployment of QoS routing
` capabilities.
`
`1.1. Overall Framework
`
` We consider a network (1) that supports both best-effort packets
` and packets with QoS guarantees. The way in which the network
` resources are split between the two classes is irrelevant to our
` proposal, except for the assumption that each QoS capable router in
` the network is able to dedicate some of its resources to satisfy the
` requirements of QoS packets. QoS capable routers are also assumed
` able to identify and advertise the amount of their resources that
` remain available for additional QoS flows. In addition, we limit
` ourselves to the case where all the routers involved support the QoS
` extensions described in this document, i.e., we do not consider the
` problem of establishing a route in an heterogeneous environment with
` routers that are QoS-capable and others that are not. Furthermore,
` in this document we focus on the case of unicast flows, although many
` of the additions we define are applicable to multicast flows as well.
`
` We assume that a flow with QoS requirements will specify them
` in some fashion that is accessible to the routing protocol. For
` example, this could correspond to the arrival of an RSVP [RZB+96]
` PATH message, whose TSpec is passed to routing together with the
` destination address. After processing such a request, the routing
` protocol returns a path that it deems the most suitable given the
` flow’s requirements. Depending on the scope of the path selection
`
`----------------------------
`1. In this document we commit the abuse of notation of calling a
` ‘‘network’’ the interconnection of routers and networks through which
` we attempt to acompute a QoS path.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 1]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 1
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` process, this returned path could range from simply identifying the
` best next hop, i.e., a traditional hop-by-hop routing, to specifying
` all intermediate nodes to the destination, i.e., a source route.
` Note that this decision impacts the operation of the path selection
` algorithm as it translates into different requirements in order to
` construct and return the appropriate path information. Note also
` that extension to multicast paths will impact differently a source
` routed and a hop-by-hop approach.
`
` Once a suitable path has been identified, the flow is assigned to
` it (pinning) and remains assigned to it until it either releases
` the path (unpinning) or deems that it has become unsuitable, e.g.,
` because of link failure or unavailability of the necessary resources.
` Note that resources reservation and/or accounting should help limit
` the frequency of the latter.
`
` In this document, we focus on the aspect of selecting an appropriate
` path based on information on link metrics and flow requirements.
` There are obviously many other aspects that need to be specified in
` order to define a complete proposal for QoS routing. Issues such as
` those mentioned above on the scope of the path selection process and
` when/how paths are pinned and unpinned, must certainly be addressed
` and they are briefly discussed in this draft during the exposition of
` the path selection algorithms and then more specifically in Section
` 3. The discussion of a complete solution to these problems is,
` however, deferred to [GOW96].
`
`1.2. Simplifying Assumptions
`
` In order to achieve our goal of a minimum impact to the existing
` protocol, we impose certain restrictions on the range of requirements
` the QoS path selection algorithm needs to deal with directly.
` Specifically, a policy scheme is used to a priori prune from
` the network, those portions that would be unsuitable given the
` requirements of the flow. This limits the ‘‘optimization’’ performed
` by the path selection to a containable set of parameters, which helps
` keep complexity at an acceptable level. Specifically, the path
` selection algorithm will focus on selecting a path that is capable of
` satisfying the bandwidth requirement of the flow, while at the same
` time trying to minimize the amount of network resources that need to
` be allocated to support the flow, i.e., minimize the number of hops
` used.
`
` This focus on bandwidth is adequate in most instances, but does not
` fully capture the complete range of potential QoS requirements. For
` example, a delay-sensitive flow of an interactive application could
` be put on a path using a satellite link, if that link provided a
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 2]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 2
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` direct path and had plenty of unused bandwidth. This would clearly
` not be a desirable choice. Our approach to preventing such poor
` choices, is to assign delay-sensitive flows to a policy that would
` eliminate from the network all links with high propagation delay,
` e.g., satellite links, before invoking the path selection algorithm.
` In general, each existing policy would present to the path selection
` algorithm its correspondingly pruned network topology, and the same
` algorithm would then be used to generate an appropriate path.
`
` Another important aspect in minimizing the impact of QoS routing
` is to develop a solution that has the smallest possible computing
` overhead. Additional computations are unavoidable, but it is
` desirable to keep the total cost of QoS routing at a level comparable
` to that of traditional routing algorithms. In this document, we
` describe several alternatives to the path selection algorithm,
` that represent different trade-offs between simplicity, accuracy,
` and computational cost. In particular, we specify algorithms
` that generate exact solutions based either on pre-computations or
` on-demand computations. We also describe algorithms that allow
` pre-computations at the cost of some loss in accuracy, but with
` possibly lower complexity or greater ease of implementation. It
` should be mentioned, that while several alternative algorithms are
` described in this document, the same algorithm needs to be used
` consistently within a given routing domain. This requirement can be
` relaxed when a source routed approach is used as the responsibility
` of selecting a QoS path lies with a single entity, the origin of
` the request, which ensures consistency. Hence, it may then be
` possible for each router to use a different path selection algorithm.
` However, in general, the use of a common path selection algorithm is
` recommended, if not necessary, for proper operation.
`
` The rest of this document is structured as follows. In Section 2,
` we describe the path computation process and the information that it
` relies on. In Section 3 we briefly review some issues associated
` with path management and their implications. As mentioned earlier,
` detailed discussions on these topics is deferred to [GOW96]. In
` Section 4, we go over the extensions to OSPF that are needed in order
` to support the path selection process of Section 2. Finally, several
` appendices provide details on the different path selection algorithms
` described in Section 2, and outline several additional work items.
`
`2. Path Selection Information and Algorithms
`
` This section describes several path selection algorithms that
` can be used to generate QoS capable routes based on different
` trade-offs between accuracy, computational complexity, and ease of
` implementation. In addition, the section also covers aspects related
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 3]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 3
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` to the type of information, i.e., metrics, on which the algorithms
` operate, and how that information is made available, i.e., link state
` advertisements. The discussion on these topics is of a generic
` nature, and OSPF specific details are provided in Section 4.
`
`2.1. Metrics
`
` As stated earlier, the process of selecting a path that can satisfy
` the QoS requirements of a new flow relies on both the knowledge of
` the flow’s requirements and characteristics, and information about
` the availability of resources in the network. In addition, for
` purposes of efficiency, it is also important for the algorithm to
` account for the amount of resources the network has to allocate in
` order to support a new flow. In general, the network prefers to
` select the ‘‘cheapest’’ among all paths suitable for a new flow.
` Furthermore, the network may also decide not to accept a new flow
` for which it identified a feasible path, if it deems the cost of the
` path to be too high. Accounting for these aspects involves several
` metrics on which the path selection process is based. They include:
`
` - Link available bandwidth: As mentioned earlier, we assume that
` most QoS requirements are derivable from a rate-related quantity,
` termed ‘‘bandwidth’’. We further assume that associated with
` each link is a maximal bandwidth value, e.g., the link physical
` bandwidth or some fraction thereof that has been set aside for
` QoS flows. Since for a link to be capable of accepting a new
` flow with given bandwidth requirements, at least that much
` bandwidth must be still available on the link, the relevant link
` metric is, therefore, the (current) amount of available (i.e.,
` unallocated) bandwidth.
`
` - Hop-count: This quantity is used as a measure of the path cost
` to the network. A path with a smaller number of hops (that can
` support a requested connection) is preferable, since it consumes
` less network resources. While as a general rule each edge in the
` graph on which the path is computed should be counted as one hop,
` some edges, specifically those that connect a transit network to
` a router, should not be taken into account. (See Appendix D for
` a detailed explanation.)
`
` - Policy: As previously discussed, policies are used to identify
` the set of links in the network that need to be considered when
` running the path selection algorithm. In particular, policies
` are used to prune from the network links that are incompatible,
` performance or characteristics wise, with the requirements of
` a flow. A specific policy example of special importance, is
` the elimination of high latency links when considering path
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 4]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 4
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` selection for delay sensitive flows. The use of policies to
` handle specific requirements allows considerable simplification
` in the optimization task to be performed by the path selection
` algorithm.
`
`2.2. Advertisement of Link State Information
`
` It is assumed that each router maintains an updated database of the
` network topology, including the current state (available bandwidth)
` of each link. As described in Section 4, the distribution of link
` state (metrics) information is based on extending OSPF mechanisms.
` However, in addition to how link state information is distributed,
` another important aspect is when such distribution is to take place.
`
` Ideally, one would want routers to have the most current view
` of the bandwidth available on all links in the network, so that
` they can make the most accurate decision on which path to select.
` Unfortunately, this then calls for very frequent updates, e.g.,
` close to every time the available bandwidth of a link changes, which
` is neither scalable nor practical. Alternatively, one may opt for
` a simple mechanism based on periodic updates, where the period of
` updates is determined based on a tolerable corresponding load on the
` network and the routers. The main disadvantage of such an approach
` is that major changes in the bandwidth available on a link could
` remain unknown for a full period and, therefore, result in many
` incorrect routing decisions.
`
` As a result, we propose to use a simple hybrid update mechanism, that
` attempts to reconcile accuracy of link state information with the
` need for the smallest possible overhead. Periodic updates are used,
` say every T seconds, to notify nodes of any change of more than ffi
` in the available bandwidth of a link, and event-driven updates are
` generated immediately whenever the change in available link bandwidth
` since the last update exceeds . The values for T, ffi, and depend
` on network size, link speed, processing capabilities, and overall
` traffic patterns, but typical values would be: T 30sec, ffi 10%,
` 40%. Note that implicit in the above description is the the
` fact that regardless of bandwidth changes, we also impose a minimum
` interval between consecutive updates, e.g., we do not allow any
` particular LSA to get updated more than once every MinLSInterval (5)
` seconds, in order to prevent the possibility of overload.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 5]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 5
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
`2.3. Path Selection Algorithms
`
` There are several aspects to the path selection algorithms. The
` main ones include the optimization criteria it relies on, the exact
` topology on which it is run, and when it is invoked.
`
` As mentioned before, invocation of the path selection algorithm can
` be either per flow, or when warranted by changes in link states when
` the algorithm used allows precomputation of paths (more on this
` below).
`
` The topology on which the algorithm is run is, as with the standard
` OSPF path selection, a directed graph where vertices (2) consist of
` routers and networks (transit vertices) as well as stub networks
` (non-transit vertices). When computing a path, stub networks are
` added as a post-processing step, which is essentially similar to
` what is done with the current OSPF routing protocol. In addition,
` for each policy supported on a router, the topology used by the
` path selection algorithm is correspondingly pruned to reflect the
` constraints imposed by the policy, and in some instances the flow
` requirements.
`
` The optimization criteria used by the path selection are reflected
` in the costs associated with each interface in the topology and how
` those costs are accounted for in the algorithm itself. As mentioned
` before, the cost of a path is a function of both its hop count and
` the amount of available bandwidth. As a result, each interface
` has associated with it a metric, that corresponds to the amount of
` bandwidth which remains available on this interface. This metric
` is combined with hop count information to provide a cost value,
` in a manner that depends on the exact form of the path selection
` algorithm. It will, therefore, be detailed in the corresponding
` sections below, but all the different alternatives that are described
` share a common goal. That is, they all aim at picking a path with
` the minimum possible number of hops among those that can support
` the requested bandwidth. When several such paths are available,
` the preference is for the path whose available bandwidth (i.e., the
` smallest value on any of the links in the path) is maximal. The
` rationale for the above rule is the following: we focus on feasible
` paths (as accounted by the available bandwidth metric) that consume
` a minimal amount of network resources (as accounted by the hop-count
` metric); and the rule for selecting among these paths aims at
` balancing load as well as maximizing the likelihood that the required
` bandwidth will indeed be available.
`
`----------------------------
`2. In this document, we use the terms node and vertex interchangeably.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 6]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 6
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` It should be noted that standard routing algorithms are typically
` single objective optimizations, i.e., they may minimize the
` hop-count, or maximize the path bandwidth, but not both. Double
` objective path optimization is a more complex task, and, in
` general, it is an intractable problem [GJ79]. Nevertheless, as
` we will see, because of the specific nature of the two objectives
` being optimized (bandwidth and hop count), the complexity of our
` proposed algorithm(s) is competitive with even that of standard
` single-objective algorithms.
`
`2.3.1. Algorithm for exact pre-computed QoS paths
`
` In this section, we describe a path selection algorithm, that for a
` given network topology and link metrics (available bandwidth) allows
` us to pre-compute all possible QoS paths, and also has a reasonably
` low computational complexity. Specifically, the algorithm allows
` us to pre-compute for any destination a minimum hop count path with
` maximum bandwidth, and has a computational complexity comparable to
` that of a standard shortest path algorithm (3).
`
` The path selection algorithm is based on a Bellman-Ford (BF)
` shortest path algorithm, which is adapted to compute paths of maximum
` available bandwidth for all hop counts. It is a property of the BF
` algorithm that, at its h-th iteration, it identifies the optimal (in
` our context: maximal bandwidth) path between the source and each
` destination, among paths of at most h hops. In other words, the
` cost of a path is a function of its available bandwidth, i.e., the
` smallest available bandwidth on all links of the path, and finding
` a minimum cost path amounts to finding a maximum bandwidth path.
` However, we also take advantage of the fact that the BF algorithm
` progresses by increasing hop count, to essentially get for free the
` hop count of a path as a second optimization criteria.
`
` Specifically, at the kth (hop count) iteration of the algorithm,
` the maximum bandwidth available to all destinations on a path of
` no more than k hops is recorded (together with the corresponding
` routing information). After the algorithm terminates, this
` information enables us to identify for all destinations and bandwidth
` requirements, the path with the smallest possible number of hops and
` sufficient bandwidth to accommodate the new request. Furthermore,
` this path is also the one with the maximal available bandwidth among
` all the feasible paths with this minimum number of hops. This is
`
`----------------------------
`3. See Appendix B for a more comprehensive discussion on the aspect of
` computational complexity.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 7]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 7
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` because for any hop count, the algorithm always selects the one with
` maximum available bandwidth.
`
` We now proceed with a more detailed description of the algorithm
` and the data structure used to record routing information, i.e.,
` the QoS routing table that gets built as the algorithm progresses
` (pseudo-code for the algorithm can be found in Appendix F). As
` mentioned before, the algorithm operates on a directed graph
` consisting only of transit vertices (routers and networks), with
` stub-networks subsequently added to the path(s) generated by the
` algorithm. The metric associated with each edge in the graph is the
` bandwidth available on the corresponding interface. Let us denote
` by bn;mthe available bandwidth on the edge between vertices n and
` m. The vertex corresponding to the router where the algorithm is
` being run, i.e., the computing router, is denoted as the ‘‘source
` node’’ for the purpose of path selection. The algorithm proceeds to
` pre-compute paths from this source node to all possible destination
` networks and for all possible bandwidth values. At each (hop count)
` iteration, intermediate results are recorded in a QoS routing table,
` which has the following structure:
`
`The QoS routing table:
`
` - a Kx H matrix, where K is the number of destinations (vertices
` in the graph) and H is the maximal allowed (or possible) number
` of hops for a path.
`
` - The (n;h) entry is built during the hth iteration (hop count
` value) of the algorithm, and consists of two fields:
`
` * bw: the maximum available bandwidth, on a path of at most h
` hops between the source node (router) and destination node
` n;
`
` * neighbor: this is the routing information associated with
` the h (or less) hops path to destination node n, whose
` available bandwidth is bw. The specific nature of this
` information depends on the scope of the path being selected,
` i.e., is it simply a next hop or is a complete source
` route being specified. In both cases, this information is
` constructed and recorded at each iteration of the algorithm,
` but it is obtained and used differently.
`
` + When the scope of the path being selected is simply
` the next hop, i.e., hop-by-hop path selection, the
` neighbor information is simply the identity of the node
` adjacent to the source node on that path. As a rule, the
` ‘‘neighbor’’ node must be a router and not a network (see
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 8]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 8
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` Appendix D), the only exception being the case that the
` network is the destination node (and the selected path is
` the single edge interconnecting the source to it).
`
` + When the path being selected is a complete source route,
` the neighbor information is the previous router (4),
` i.e., preceding the destination node n, on that path.
`
` Next, we provide additional details on the operation of the algorithm
` and how the entries in the routing table are being updated as the
` algorithm proceeds. For simplicity, we first describe the simpler
` case where all edges count as ‘‘hops’’, and later explain how
` zero-hop edges (see Appendix D) are handled.
`
` When the algorithm is invoked, the routing table is first initialized
` with all bw fields set to 0 and neighbor fields cleared. Next, the
` entries in the first column (which corresponds to one-hop paths) of
` the neighbors of the computing router are modified in the following
` way: the bw field is set to the value of the available bandwidth on
` the direct edge from the source. Modification of the neighbor field
` depends on the scope of path selection. For next-hop routing, it is
` set to the identity of the neighbor of the computing router, i.e.,
` the next router on the selected path. For source-routing, it is set
` to the identity of the computing router itself.
`
` Afterwards, the algorithm iterates for at most H iterations
` (considering the above initial iteration as the first). H can be
` either the maximum possible hop count of any path, i.e., an implicit
` value, or it can be set explicitly in order to limit path lengths to
` some maximum value (5) to better control worst case complexity.
`
` At iteration h, we first copy column h - 1 into column h. In
` addition, the algorithm keeps a list of nodes that changed their bw
` value in the previous iteration, i.e., during the h- 1-st iteration.
` The algorithm then looks at each link (n;m) and checks the maximal
` available bandwidth on an h-hop path to node m whose final hop is
` that link. This amounts to taking the minimum between the bw field
` in entry (n;h -1) and the link metric value bn;m kept in the topology
` database. If this value is higher than the present value of the bw
` field in entry (m;h), then a better (larger bw value) path has been
` found for destination m and with h hops. The bw field of entry
`
`----------------------------
`4. See Appendix A for details on how the complete source route is
` constructed based on the neighbor information kept in the table.
`5. This maximum value should be larger than the length of the minimum
` hop-count path to any node in the graph.
`
`Guerin,Orda,Williams Expires 10 May 1997 [Page 9]
`
`Petitioners The Mangrove Partners Master Fund, Ltd., Apple Inc., and Black Swamp IP, LLC
`IPR2015-01047, Ex. 1040, p. 9
`
`

`
`
`Internet Draft QoS Routing Mechanisms 5 November 1996
`
` (m;h) is then updated to reflect this new value. In the case of
` next-hop routing, the neighbor field of entry (m;h) is set to the
` same value as in entry (n;h - 1). This records the identity of the
` first hop (next hop from the source) on the best path identified
` thus far for destination m and with h (or less) hops. In the case
` of source routing, the neighbor field of entry (m;h) is set to the
` identity of node n. This records the identity of the previous hop
` on the best path identified thus far for destination m and with h
` (or less) hops. As described in Appendix A, this allows recursive
` construction of the complete source route simply by back-tracking
` from entry to entry in the table.
`
` We conclude by describing how zero-hop edges are handled. At each
` iteration h (starting with the first), whenever an entry (m;h) is
` modified, it is checked whether there are zero-cost edges (m;k)
` emerging from node m, which is the case when m is a transit network
` (see Appendix D). In that case, we attempt to improve the entry of
` node k that corresponds to the h-th hop, i.e., entry (k;h) (rather
` than entry (k;h + 1)), since the edge (m;k) should not count as an
` additional hop. As with the regular operation of the algorithm, this
` amounts to taking the minimum between the bw f