rfc2676.txt

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

   Note that while for simplicity of the exposition, the issue of equal
   cost, i.e., same hop count and available bandwidth, is not detailed
   in the above description, it can be easily supported.  It only
   requires that the neighbor field be expanded to record the list of
   next (previous) hops, when multiple equal cost paths are present.

Addition of Stub Networks

   As was mentioned earlier, the path selection algorithm is run on a
   graph whose vertices consist only of routers and transit networks and
   not stub networks.  This is intended to keep the computational
   complexity as low as possible as stub networks can be added
   relatively easily through a post-processing step.  This second
   processing step is similar to the one used in the current OSPF
   routing table calculation [Moy98], with some differences to account
   for the QoS nature of routes.

   Specifically, after the QoS routing table has been constructed, all
   the router vertices are again considered.  For each router, stub
   networks whose links appear in the router's link advertisements will
   be processed to determine QoS routes available to them.  The QoS
   routing information for a stub network is similar to that of routers
   and transit networks and consists of an extension to the QoS routing
   table in the form of an additional row.  The columns in that new row
   again correspond to paths of different hop counts, and contain both
   bandwidth and next hop information.  We also assume that an available
   bandwidth value has been advertised for the stub network.  As before,
   how this value is determined is beyond the scope of this document.
   The QoS routes for a stub network S are constructed as follows:

   Each entry in the row corresponding to stub network S has its bw(s)
   field initialized to zero and its neighbor set to null.  When a stub
   network S is found in the link advertisement of router V, the value
   bw(S,h) in the hth column of the row corresponding to stub network S
   is updated as follows:

      bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),

   where bw(V,h) is the bandwidth value of the corresponding column for
   the QoS routing table row associated with router V, i.e., the
   bandwidth available on an h hop path to V, and b(V,S) is the
   advertised available bandwidth on the link from V to S.  The above
   expression essentially states that the bandwidth of a h hop path to
   stub network S is updated using a path through router V, only if the
   minimum of the bandwidth of the h hop path to V and the bandwidth on
   the link between V and S is larger than the current value.





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


   Update of the neighbor field proceeds similarly whenever the
   bandwidth of a path through V is found to be larger than or equal to
   the current value.  If it is larger, then the neighbor field of V in
   the corresponding column replaces the current neighbor field of S.
   If it is equal, then the neighbor field of V in the corresponding
   column is concatenated with the existing field for S, i.e., the
   current set of neighbors for V is added to the current set of
   neighbors for S.

Extracting Forwarding Information from Routing Table

   When the QoS paths are precomputed, the forwarding information for a
   flow with given destination and bandwidth requirement needs to be
   extracted from the routing table.  The case of hop-by-hop routing is
   simpler than that of explicit routing.  This is because, only the
   next hop needs to be returned instead of an explicit route.

   Specifically, assume a new request to destination, say, d, and with
   bandwidth requirements B.  The index of the destination vertex
   identifies the row in the QoS routing table that needs to be checked
   to generate a path.  Assuming that the QoS routing table was
   constructed using the Bellman-Ford algorithm presented later in this
   section, the search then proceeds by increasing index (hop) count
   until an entry is found, say at hop count or column index of h, with
   a value of the bw field which is equal to or larger than B.  This
   entry points to the initial information identifying the selected
   path.

   If the path computation algorithm stores multiple equal cost paths,
   then some degree of load balancing can be achieved at the time of
   path selection.  A next hop from the list of equivalent next hops can
   be chosen in a round robin manner, or randomly with a probability
   that is weighted by the actual available bandwidth on the local
   interface.  The latter is the method used in the implementation
   described in Section 4.

   The case of explicit routing is discussed in Appendix D.

3. OSPF Protocol Extensions

   As stated earlier, one of our goals is to limit the additions to the
   existing OSPF V2 protocol, while still providing the required level
   of support for QoS based routing.  To this end, all of the existing
   OSPF mechanisms, data structures, advertisements, and data formats
   remain in place.  The purpose of this section of the document is to
   describe the extensions to the OSPF protocol needed to support QoS as
   outlined in the previous sections.




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


3.1. QoS -- Optional Capabilities

   The OSPF Options field is present in OSPF Hello packets, Database
   Description packets and all LSAs.  The Options field enables OSPF
   routers to support (or not support) optional capabilities, and to
   communicate their capability level to other OSPF routers.  Through
   this mechanism, routers of differing capabilities can be mixed within
   an OSPF routing domain.  Currently, the OSPF standard [Moy98]
   specifies the following 5 bits in the options octet:

           +-----------------------------------------------+
           |  *  |  *  | DC  |  EA | N/P |  MC |  E  |  *  |
           +-----------------------------------------------+

   Note that the least significant bit (`T' bit) that was used to
   indicate TOS routing capability in the older OSPF specification
   [Moy94] has been removed.  However, for backward compatibility with
   previous versions of the OSPF specification, TOS-specific information
   can be included in router-LSAs, summary-LSAs and AS-external-LSAs.

   We propose to reclaim the `T' bit as an indicator of router's QoS
   routing capability and refer to it as the `Q' bit.  In fact, QoS
   capability can be viewed as an extension of the TOS-capabilities and
   QoS routing as a form of TOS-based routing.  A router sets this bit
   in its hello packets to indicate that it is capable of supporting
   such routing.  When this bit is set in a router or summary links link
   state advertisement, it means that there are QoS fields to process in
   the packet.  When this bit is set in a network link state
   advertisement it means that the network described in the
   advertisement is QoS capable.

   We need to be careful in this approach so as to avoid confusing any
   old style (i.e., RFC 1583 based) TOS routing implementations.  The
   TOS metric encoding rules of QoS fields introduced further in this
   section will show how this is achieved.  Additionally, unlike the RFC
   1583 specification that unadvertised TOS metrics be treated to have
   same cost as TOS 0, for the purpose of computing QOS routes,
   unadvertised TOS metrics (on a hop) indicate lack of connectivity for
   the specific TOS metrics (for that hop).

3.2. Encoding Resources as Extended TOS

   Introduction of QoS should ideally not influence the compatibility
   with existing OSPFv2 routers.  To achieve this goal, necessary
   extensions in packet formats must be defined in a way that either is
   understood by OSPFv2 routers, ignored, or in the worst case
   "gracefully" misinterpreted.  Encoding of QoS metrics in the TOS
   field which fortunately enough is longer in OSPF packets than



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


   officially defined in [Alm92], allows us to mimic the new facility as
   extended TOS capability.  OSPFv2 routers will either disregard these
   definitions or consider those unspecified.  Specific precautions are
   taken to prevent careless OSPF implementations from influencing
   traditional TOS routers (if any) when misinterpreting the QoS
   extensions.

   For QoS resources, 32 combinations are available through the use of
   the fifth bit in TOS fields contained in different LSAs.  Since
   [Alm92] defines TOS as being four bits long, this definition never
   conflicts with existing values.  Additionally, to prevent naive
   implementations that do not take all bits of the TOS field in OSPF
   packets into considerations, the definitions of the `QoS encodings'
   is aligned in their semantics with the TOS encoding.  Only bandwidth
   and delay are specified as of today and their values map onto
   `maximize throughput' and `minimize delay' if the most significant
   bit is not taken into account.  Accordingly, link reliability and
   jitter could be defined later if necessary.

        OSPF encoding   RFC 1349 TOS values
        ___________________________________________
        0               0000 normal service
        2               0001 minimize monetary cost
        4               0010 maximize reliability
        6               0011
        8               0100 maximize throughput
        10              0101
        12              0110
        14              0111
        16              1000 minimize delay
        18              1001
        20              1010
        22              1011
        24              1100
        26              1101
        28              1110
        30              1111














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


        OSPF encoding   `QoS encoding values'

        -------------------------------------------
        32             10000
        34             10001
        36             10010
        38             10011
        40             10100 bandwidth
        42             10101
        44             10110
        46             10111
        48             11000 delay
        50             11001
        52             11010
        54             11011
        56             11100
        58             11101
        60             11110
        62             11111

        Representing TOS and QoS in OSPF.

3.2.1. Encoding bandwidth resource

   Given the fact that the actual metric field in OSPF packets only
   provides 16 bits to encode the value used and that links supporting
   bandwidth ranging into Gbits/s are becoming reality, linear
   representation of the available resource metric is not feasible.  The
   solution is exponential encoding using appropriately chosen implicit
   base value and number bits for encoding mantissa and the exponent.
   Detailed considerations leading to the solution described are not
   presented here but can be found in [Prz95].

   Given a base of 8, the 3 most significant bits should be reserved for
   the exponent part and the remaining 13 for the mantissa.  This allows
   a simple comparison for two numbers encoded in this form, which is
   often useful during implementation.