rfc2676.txt

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

   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]

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]

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]

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]

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]

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