rfc2676.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,311 行 · 第 1/5 页

   cost of a path is a function of both its hop count and the amount of
   available bandwidth.  As a result, each interface has associated with
   it a metric, which corresponds to the amount of bandwidth that
   remains available on this interface.  This metric is combined with
   hop count information to provide a cost value, whose goal is to pick
   a path with the minimum possible number of hops among those that can
   support the requested bandwidth.  When several such paths are
   available, the preference is for the path whose available bandwidth
   (i.e., the smallest value on any of the links in the path) is
   maximal.  The rationale for the above rule is the following:  we
   focus on feasible paths (as accounted by the available bandwidth
   metric) that consume a minimal amount of network resources (as
   accounted by the hop-count metric); and the rule for selecting among
   these paths is meant to balance load as well as maximize the
   likelihood that the required bandwidth is indeed available.

   It should be noted that standard routing algorithms are typically
   single objective optimizations, i.e., they may minimize the hop-
   count, or maximize the path bandwidth, but not both.  Double
   objective path optimization is a more complex task, and, in general,
   it is an intractable problem [GJ79].  Nevertheless, because of the
   specific nature of the two objectives being optimized (bandwidth and
   hop count), the complexity of the above algorithm is competitive with
   even that of standard single-objective algorithms.  For readers
   interested in a thorough treatment of the topic, with insights into
   the connection between the different algorithms, linear algebra and
   modification of metrics, [Car79] is recommended.

   Before proceeding with a more detailed description of the path
   selection algorithm itself, we briefly review the available options
   when it comes to deciding when to invoke the algorithm.  The two main
   options are:  1) to perform on-demand computations, that is, trigger



Apostolopoulos, et al.        Experimental                     [Page 10]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   a computation for each new request, and 2) to use some form of pre-
   computation.  The on-demand case involves no additional issues in
   terms of when computations should be triggered, but running the path
   selection algorithm for each new request can be computationally
   expensive (see [AT98] for a discussion on this issue).  On the other
   hand, pre-computing paths amortizes the computational cost over
   multiple requests, but each computation instance is usually more
   expensive than in the on-demand case (paths are computed to all
   destinations and for all possible bandwidth requests rather than for
   a single destination and a given bandwidth request).  Furthermore,
   depending on how often paths are recomputed, the accuracy of the
   selected paths may be lower.  In this document, we primarily focus on
   the case of pre-computed paths, which is also the only method
   currently supported in the reference implementation described in
   Section 4.  In this case, clearly, an important issue is when such
   pre-computation should take place.  The two main options we consider
   are periodic pre-computations and pre-computations after a given (N)
   number of updates have been received.  The former has the benefit of
   ensuring a strict bound on the computational load associated with
   pre-computations, while the latter can provide for a more responsive
   solution (5).  Section 4 provides some experimental results comparing
   the performance and cost of periodic pre-computations for different
   period values.

2.3.1. Path Computation Algorithm

   This section describes a path selection algorithm, which for a given
   network topology and link metrics (available bandwidth), pre-computes
   all possible QoS paths, while maintaining a reasonably low
   computational complexity.  Specifically, the algorithm pre-computes
   for any destination a minimum hop count path with maximum bandwidth,
   and has a computational complexity comparable to that of a standard
   Bellman-Ford shortest path algorithm.  The Bellman-Ford (BF) shortest
   path algorithm is adapted to compute paths of maximum available
   bandwidth for all hop counts.  It is a property of the BF algorithm
   that, at its h-th iteration, it identifies the optimal (in our
   context:  maximal bandwidth) path between the source and each
   destination, among paths of at most h hops.  In other words, the cost
   of a path is a function of its available bandwidth, i.e., the
   smallest available bandwidth on all links of the path, and finding a
   minimum cost path amounts to finding a maximum bandwidth path.
   However, because the BF algorithm progresses by increasing hop count,
   it essentially provides for free the hop count of a path as a second
   optimization criteria.

   Specifically, at the kth (hop count) iteration of the algorithm, the
   maximum bandwidth available to all destinations on a path of no more
   than k hops is recorded (together with the corresponding routing



Apostolopoulos, et al.        Experimental                     [Page 11]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   information).  After the algorithm terminates, this information
   provides for all destinations and bandwidth requirements, the path
   with the smallest possible number of hops and sufficient bandwidth to
   accommodate the new request.  Furthermore, this path is also the one
   with the maximal available bandwidth among all the feasible paths
   with at most these many hops.  This is because for any hop count, the
   algorithm always selects the one with maximum available bandwidth.

   We now proceed with a more detailed description of the algorithm and
   the data structure used to record routing information, i.e., the QoS
   routing table that gets built as the algorithm progresses (the
   pseudo-code for the algorithm can be found in Appendix A).  As
   mentioned before, the algorithm operates on a directed graph
   consisting only of transit vertices (routers and networks), with
   stub-networks subsequently added to the path(s) generated by the
   algorithm.  The metric associated with each edge in the graph is the
   bandwidth available on the corresponding interface.  Let us denote by
   b(n;m) the available bandwidth on the link from node n to m.  The
   vertex corresponding to the router where the algorithm is being run,
   i.e., the computing router, is denoted as the "source node" for the
   purpose of path selection.  The algorithm proceeds to pre-compute
   paths from this source node to all possible destination networks and
   for all possible bandwidth values.  At each (hop count) iteration,
   intermediate results are recorded in a QoS routing table, which has
   the following structure:

The QoS routing table:

   -  a KxH matrix, where K is the number of destinations (vertices in
      the graph) and H is the maximal allowed (or possible) number of
      hops for a path.

   -  The (n;h) entry is built during the hth iteration (hop count
      value) of the algorithm, and consists of two fields:

         *  bw:  the maximum available bandwidth, on a path of at most h
            hops between the source node (router) and destination node
            n;

         *  neighbor:  this is the routing information associated with
            the h (or less) hops path to destination node n, whose
            available bandwidth is bw.  In the context of hop-by-hop
            path selection (6), the neighbor information is simply the
            identity of the node adjacent to the source node on that
            path.  As a rule, the "neighbor" node must be a router and
            not a network, the only exception being the case where the
            network is the destination node (and the selected path is
            the single edge interconnecting the source to it).



Apostolopoulos, et al.        Experimental                     [Page 12]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Next, we provide additional details on the operation of the algorithm
   and how the entries in the routing table are updated as the algorithm
   proceeds.  For simplicity, we first describe the simpler case where
   all edges count as "hops," and later explain how zero-hop edges are
   handled.  Zero-hop edges arise in the case of transit networks
   vertices, where only one of the two incoming and outgoing edges
   should be counted in the hop count computation, as they both
   correspond to the same physical hop.  Accounting for this aspect
   requires distinguishing between network and router nodes, and the
   steps involved are detailed later in this section as well as in the
   pseudo-code of Appendix A.

   When the algorithm is invoked, the routing table is first initialized
   with all bw fields set to 0 and neighbor fields cleared.  Next, the
   entries in the first column (which corresponds to one-hop paths) of
   the neighbors of the computing router are modified in the following
   way:  the bw field is set to the value of the available bandwidth on
   the direct edge from the source.  The neighbor field is set to the
   identity of the neighbor of the computing router, i.e., the next
   router on the selected path.

   Afterwards, the algorithm iterates for at most H iterations
   (considering the above initial iteration as the first).  The value of
   H could be implicit, i.e., the diameter of the network or, in order
   to better control the worst case complexity, it can be set explicitly
   thereby limiting path lengths to at most H hops.  In the latter case,
   H must be assigned a value larger than the length of the minimum
   hop-count path to any node in the graph.

   At iteration h, we first copy column h-1  into column h.  In
   addition, the algorithm keeps a list of nodes that changed their bw
   value in the previous iteration, i.e., during the (h-1)-th iteration.
   The algorithm then looks at each link (n;m) where n is a node whose
   bw value changed in the previous iteration, and checks the maximal
   available bandwidth on an (at most) h-hop path to node m whose final
   hop is that link.  This amounts to taking the minimum between the bw
   field in entry (n;h-1) and the link metric value b(n;m) kept in the
   topology database.  If this value is higher than the present value of
   the bw field in entry (m;h), then a better (larger bw value) path has
   been found for destination m and with at most h hops.  The bw field
   of entry (m;h) is then updated to reflect this new value.  In the
   case of hop-by-hop routing, the neighbor field of entry (m;h) is set
   to the same value as in entry (n;h-1).  This records the identity of
   the first hop (next hop from the source) on the best path identified
   thus far for destination m and with h (or less) hops.






Apostolopoulos, et al.        Experimental                     [Page 13]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   As mentioned earlier, extending the above algorithm to handle zero-
   hop edges is needed due to the possible use of multi-access networks,
   e.g., T/R, E/N, etc., to interconnect routers.  Such entities are
   also represented by means of a vertex in the OSPF topology, but a
   network connecting two routers should clearly be considered as a
   single hop path rather than a two hop path.  For example, consider
   three routers A, B, and C connected over an Ethernet network N, which
   the OSPF topology represents as in Figure 1.

                           A----N----B
                                |
                                |
                                C



                        Figure 1: Zero-Hop Edges


   In the example of Figure 1, although there are directed edges in both
   directions, an edge from the network to any of the three routers must
   have zero "cost", so that it is not counted twice.  It should be
   noted that when considering such environments in the context of QoS
   routing, it is assumed that some entity is responsible for
   determining the "available bandwidth" on the network, e.g., a subnet
   bandwidth manager.  The specification and operation of such an entity
   is beyond the scope of this document.

   Accommodating zero-hop edges in the context of the path selection
   algorithm described above is done as follows:  At each iteration h
   (starting with the first), whenever an entry (m;h) is modified, it is
   checked whether there are zero-cost edges (m;k) emerging from node m.
   This is the case when m is a transit network.  In that case, we
   attempt to further improve the entry of node k within the current
   iteration, i.e., entry (k;h) (rather than entry (k;h+1)), since the
   edge (m;k) should not count as an additional hop.  As with the
   regular operation of the algorithm, this amounts to taking the
   minimum between the bw field in entry (m;h) and the link metric value
   b(m;k) kept in the topology database (7).  If this value is higher
   than the present value of the bw field in entry (k;h), then the bw
   field of entry (k;h) is updated to this new value.  In the case of
   hop-by-hop routing, the neighbor field of entry (k;h) is set, as
   usual, to the same value as in entry (m;h) (which is also the value
   in entry (n;h-1)).







Apostolopoulos, et al.        Experimental                     [Page 14]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999