rfc2386.txt

<VC++网络游戏建摸与实现>源代码

Crawley, et. al.             Informational                     [Page 10]

RFC 2386           A Framework for QoS-based Routing         August 1998


   route tables), the router could select a path randomly from a
   "window" of paths which meet the needs of the flow and satisfy one of
   three additional criteria: best-fit, first-fit or worst-fit. Note
   that there is a similarity between the allocation of bandwidth and
   the allocation of memory in a multiprocessing system. First-fit seems
   to be appropriate for a system with a high real-time flow arrival
   rates; and worst-fit is ideal for real-time flows with high holding
   times.  This rather nonintuitive result was shown in [NC94].

3.6.5  Path Properties

   Path computation by itself is merely a search technique, e.g.,
   Shortest Path First (SPF) is a search technique based on dynamic
   programming. The usefulness of the paths computed depends to a large
   extent on the metrics used in evaluating the cost of a path with
   respect to a flow.

   Each link considered by the path computation engine must be evaluated
   against the requirements of the flow, i.e., the cost of providing the
   services required by the flow must be estimated with respect to the
   capabilities of the link. This requires a uniform method of combining
   features such as delay, bandwidth, priority and other service
   features.  Furthermore, the costs must reflect the lost opportunity
   of using each link after routing the flow.

3.6.6  Performance Objectives

   One common objective during path computation is to improve the total
   network throughput.  In this regard, merely routing a flow on any
   path that accommodates its QoS requirement is not a good strategy. In
   fact, this corresponds to uncontrolled alternate routing [SD95] and
   may adversely impact performance at higher traffic loads.  It is
   therefore necessary to consider the total resource allocation for a
   flow along a path, in relation to available resources, to determine
   whether or not the flow should be routed on the path.  Such a
   mechanism is referred to in this document as "higher level admission
   control". The goal of this is to ensure that the "cost" incurred by
   the network in routing a flow with a given QoS is never more than the
   revenue gained.  The routing cost in this regard may be the lost
   revenue in potentially blocking other flows that contend for the same
   resources. The formulation of the higher level admission control
   strategy, with suitable administrative hooks and with fairness to all
   flows desiring entry to the network, is an issue.  The fairness
   problem arises because flows with smaller reservations tend to be
   more successfully routed than flows with large reservations, for a
   given engineered capacity.  To guarantee a certain level of





Crawley, et. al.             Informational                     [Page 11]

RFC 2386           A Framework for QoS-based Routing         August 1998


   acceptance rate for "larger" flows, without over-engineering the
   network, requires a fair higher level admission control mechanism.
   The application of higher level admission control to multicast
   routing is discussed later.

3.7   Administrative Control

   There are several administrative control issues. First, within an AS
   employing state-dependent routing, administrative control of routing
   behavior may be necessary. One example discussed earlier was higher
   level admission control. Some others are described in this section.
   Second, the control of interdomain routing based on policy is an
   issue.  The discussion of interdomain routing is defered to Section
   5.

   Two areas that need administrative control, in addition to
   appropriate routing mechanisms, are handling flow priority with
   preemption, and resource allocation for multiple service classes.

3.7.1  Flow Priorities and Preemption

   If there are critical flows that must be accorded higher priority
   than other types of flows, a mechanism must be implemented in the
   network to recognize flow priorities. There are two aspects to
   prioritizing flows.  First, there must be a policy to decide how
   different users are allowed to set priorities for flows they
   originate. The network must be able to verify that a given flow is
   allowed to claim a priority level signaled for it. Second, the
   routing scheme must ensure that a path with the requested QoS will be
   found for a flow with a probability that increases with the priority
   of the flow. In other words, for a given network load, a high
   priority flow should be more likely to get a certain QoS from the
   network than a lower priority flow requesting the same QoS. Routing
   procedures for flow prioritization can be complex.  Identification
   and evaluation of different procedures are areas that require
   investigation.

3.7.2 Resource Control

   If there are multiple service classes, it is necessary to engineer a
   network to carry the forecasted traffic demands of each class. To do
   this, router and link resources may be logically partitioned among
   various service classes. It is desirable to have dynamic partitioning
   whereby unused resources in various partitions are dynamically
   shifted to other partitions on demand [ACFH92]. Dynamic sharing,
   however, must be done in a controlled  fashion in order to prevent
   traffic under some service class from taking up more resources than




Crawley, et. al.             Informational                     [Page 12]

RFC 2386           A Framework for QoS-based Routing         August 1998


   what was engineered for it for prolonged periods of time. The design
   of such a resource sharing scheme, and its incorporation into the
   QoS-based routing scheme are significant issues.

3.8   QoS-Based Routing for Multicast Flows

   QoS-based multicast routing is an important problem, especially if
   the notion of higher level admission control is included. The
   dynamism in the receiver set allowed by IP multicast, and receiver
   heterogeneity add to the problem. With straightforward implementation
   of distributed heuristic algorithms for multicast path computation
   [W88, C91], the difficulty is essentially one of scalability. To
   accommodate QoS, multicast path computation at a router must have
   knowledge of not only the id of subnets where group members are
   present, but also the identity of branches in the existing tree. In
   other words, routers must keep flow-specific state information. Also,
   computing optimal shared trees based on the shared reservation style
   [BZBH97], may require new algorithms.  Multicast routing is discussed
   in some detail in Section 6.

3.9    Routing Overheads

   The overheads incurred by a routing scheme depend on the type of the
   routing scheme, as well as the implementation. There are three types
   of overheads to be considered: computation, storage and
   communication. It is necessary to understand the implications of
   choosing a routing mechanism in terms of these overheads.

   For example, considering link state routing, the choice of the update
   propagation mechanism is important since network state is dynamic and
   changes relatively frequently. Specifically, a flooding mechanism
   would result in many unnecessary message transmissions and
   processing.  Alternative techniques, such as tree-based forwarding
   [R96], have to be considered. A related issue is the quantization of
   state information to prevent frequent updating of dynamic state.
   While coarse quantization reduces updating overheads, it may affect
   the performance of the routing scheme.  The tradeoff has to be
   carefully evaluated.  QoS-based routing incurs certain overheads
   during flow establishment, for example, computing a source route.
   Whether this overhead is disproportionate compared to the length of
   the sessions is an issue. In general, techniques for the minimization
   of routing-related overheads during flow establishment must be
   investigated. Approaches that are useful include pre-computation of
   routes, caching recently used routes, and TOS routing based on hints
   in packets (e.g., the TOS field).






Crawley, et. al.             Informational                     [Page 13]

RFC 2386           A Framework for QoS-based Routing         August 1998


3.10   Scaling by Hierarchical Aggregation

   QoS-based routing should be scalable, and hierarchical aggregation is
   a common technique for scaling (e.g., [PNNI96]). But this introduces
   problems with regard to the accuracy of the aggregated state
   information [L95]. Also, the aggregation of paths under multiple
   constraints is difficult. One of the difficulties is the risk of
   accepting a flow based on inaccurate information, but not being able
   to support the QoS requirements of flow because the capabilities of
   the actual paths that are aggregated are not known during route
   computation.  Performance impacts of aggregating path metric
   information must therefore be understood. A way to compensate for
   inaccuracies is to use crankback, i.e., dynamic search for alternate
   paths as a flow is being routed. But crankback increases the time to
   set up a flow, and may adversely affect the performance of the
   routing scheme under some circumstances. Thus, crankback must be used
   judiciously, if at all, along with a higher level admission control
   mechanism.

4. INTRADOMAIN ROUTING REQUIREMENTS

   At the intradomain level, the objective is to allow as much latitude
   as possible in addressing the QoS-based routing issues. Indeed, there
   are many ideas about how QoS-based routing services can be
   provisioned within ASs. These range from on-demand path computation
   based on current state information, to statically provisioned paths
   supporting a few service classes.

   Another aspect that might invite differing solutions is performance
   optimization. Based on the technique used for this, intradomain
   routing could be very sophisticated or rather simple. Finally, the
   service classes supported, as well as the specific QoS engineered for
   a service class, could differ from AS to AS. For instance, some ASs
   may not support guaranteed service, while others may. Also, some ASs
   supporting the service may be engineered for a better delay bound
   than others. Thus, it requires considerable thought to determine the
   high level requirements for intradomain routing that both supports
   the overall view of QoS-based routing in the Internet and allows
   maximum autonomy in developing solutions.

   Our view is that certain minimum requirements must be satisfied by
   intradomain routing in order to be qualified as "QoS-based" routing.
   These are:

   - The routing scheme must route a flow along a path that can
     accommodate its QoS requirements, or indicate that the flow cannot
     be admitted with the QoS currently being requested.




Crawley, et. al.             Informational                     [Page 14]

RFC 2386           A Framework for QoS-based Routing         August 1998


   - The routing scheme must indicate disruptions to the current route
     of a flow due to topological changes.

   - The routing scheme must accommodate best-effort flows without any
     resource reservation requirements. That is, present best effort
     applications and protocol stacks need not have to change to run in
     a domain employing QoS-based routing.

   - The routing scheme may optionally support QoS-based multicasting
     with receiver heterogeneity and shared reservation styles.

   In addition, the following capabilities are also recommended:

   - Capabilities to optimize resource usage.

   - Implementation of higher level admission control procedures to
     limit the overall resource utilization by individual flows.

   Further requirements along these lines may be specified. The
   requirements should capture the consensus view of QoS-based routing,
   but should not preclude particular approaches (e.g., TOS-based
   routing) from being implemented. Thus, the intradomain requirements
   are expected to be rather broad.

5. INTERDOMAIN ROUTING

   The fundamental requirement on interdomain QoS-based routing is
   scalability.  This implies that interdomain routing cannot be based
   on highly dynamic network state information. Rather, such routing
   must be aided by sound network engineering and relatively sparse
   information exchange between independent routing domains. This
   approach has the advantage that it can be realized by straightforward
   extensions of the present Internet interdomain routing model. A
   number of issues, however, need to be addressed to achieve this, as
   discussed below.