rfc3247.txt

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

Charny, et. al.              Informational                      [Page 6]

RFC 3247                Supplemental Information              March 2002


   scheduling implementation.  The smaller E, the smaller the difference
   between the configured rate and the actual rate achieved by the
   scheduler.

   While RLC guarantees the desired rate to the EF aggregate in all
   intervals (0,t) to within a specified error, it may nevertheless
   result in large gaps in service.  For example, suppose that (a large
   number) N of identical EF packets of length L arrived from different
   interfaces to the EF queue in the absence of any non-EF traffic.
   Then any work-conserving scheduler will serve all N packets at link
   speed.  When the last packet is sent at time NL/C, where C is the
   capacity of output link, F'(N) will be equal to NL/R.  That is, the
   scheduler is running ahead of ideal, since NL/C < NL/R for R < C.
   Suppose now that at time NL/C a large number of non-EF packets
   arrive, followed by a single EF packet.  Then the scheduler can
   legitimately delay starting to send the EF packet until time
   F'(N+1)=(N+1)L/R + E - L/C.  This means that the EF aggregate will
   have no service at all in the interval (NL/C, (N+1)L/R + E - L/C).
   This interval can be quite large if R is substantially smaller than
   C.  In essence, the EF aggregate can be "punished" by a gap in
   service for receiving faster service than its configured rate at the
   beginning.

   The new EF definition alleviates this problem by introducing the term
   min(D(j-1), F(j-1)) in the recursion.  Essentially, this means that
   the fluid finishing time is "reset" if that packet is sent before its
   "ideal" departure time.  As a consequence of that, for the case where
   the EF aggregate is served in the FIFO order, suppose a packet
   arrives at time t to a server satisfying the EF definition.  The
   packet will be transmitted no later than time t + Q(t)/R + E, where
   Q(t) is the EF queue size at time t (including the packet under
   discussion)[4].

2.3. The need for dual characterization of EF PHB

   In a more general case, where either the output scheduler does not
   serve the EF packets in a FIFO order, or the variable internal delay
   in the device reorders packets while delivering them to the output
   (or both), the i-th packet destined to a given output interface to
   arrive to the device may no longer be the i-th packet to depart from
   that interface.  In that case the packet-identity-aware and the
   aggregate definitions are no longer identical.

   The aggregate behavior definition can be viewed as a truly aggregate
   characteristic of the service provided to EF packets.  For an
   analogy, consider a dark reservoir to which all arriving packets are
   placed.  A scheduler is allowed to pick a packet from the reservoir
   in a random order, without any knowledge of the order of packet



Charny, et. al.              Informational                      [Page 7]

RFC 3247                Supplemental Information              March 2002


   arrivals.  The aggregate part of the definition measures the accuracy
   of the output rate provided to the EF aggregate as a whole.  The
   smaller E_a, the more accurate is the assurance that the reservoir is
   drained at least at the configured rate.

   Note that in this reservoir analogy packets of EF aggregate may be
   arbitrarily reordered.  However, the definition of EF PHB given in
   [6] explicitly requires that no packet reordering occur within a
   microflow.  This requirement restricts the scheduling
   implementations, or, in the reservoir analogy, the order of pulling
   packets out of the reservoir to make sure that packets within a
   microflow are not reordered, but it still allows reordering at the
   aggregate level.

   Note that reordering within the aggregate, as long as there is no
   flow-level reordering, does not necessarily reflect a "bad" service.
   Consider for example a scheduler that arbitrates among 10 different
   EF "flows" with diverse rates.  A scheduler that is aware of the rate
   requirements may choose to send a packet of the faster flow before a
   packet of the slower flow to maintain lower jitter at the flow level.
   In particular, an ideal "flow"-aware WFQ scheduler will cause
   reordering within the aggregate, while maintaining packet ordering
   and small jitter at the flow level.

   It is intuitively clear that for such a scheduler, as well as for a
   simpler FIFO scheduler, the "accuracy" of the service rate is crucial
   for minimizing "flow"-level jitter.  The packet-identity-aware
   definition quantifies this accuracy of the service rate.

   However, the small value of E_a does not give any assurances about
   the absolute value of per-packet delay.  In fact, if the input rate
   exceeds the configured rate, the aggregate behavior definition may
   result in arbitrarily large delay of a subset of packets.  This is
   the primary motivation for the packet-identity-aware definition.

   The primary goal of the packet-aware characterization of the EF
   implementation is that, unlike the aggregate behavior
   characterization, it provides a way to find a per-packet delay bound
   as a function of input traffic parameters.

   While the aggregate behavior definition characterizes the accuracy of
   the service rate of the entire EF aggregate, the packet-identity-
   aware part of the definition characterizes the deviation of the
   device from an ideal server that serves the EF aggregate in FIFO
   order at least at the configured rate.

   The value of E_p in the packet-identity-aware definition is therefore
   affected by two factors: the accuracy of the aggregate rate service



Charny, et. al.              Informational                      [Page 8]

RFC 3247                Supplemental Information              March 2002


   and the degree of packet reordering within the EF aggregate (under
   the constraint that packets within the same microflow are not
   reordered).  Therefore, a sub-aggregate aware device that provides an
   ideal service rate to the aggregate, and also provides an ideal rate
   service for each of the sub-aggregates, may nevertheless have a very
   large value of E_p (in this case E_p must be at least equal to the
   ratio of the maximum packet size divided by the smallest rate of any
   sub aggregate).  As a result, a large value of E_p does not
   necessarily mean that the service provided to EF aggregate is bad -
   rather it may be an indication that the service is good, but non-
   FIFO.  On the other hand, a large value of E_p may also mean that the
   aggregate service is very inaccurate (bursty), and hence in this case
   the large value of E_p reflects a poor quality of implementation.

   As a result, a large number of E_p does not necessarily provide any
   guidance on the quality of the EF implementation.  However, a small
   value of E_p does indicate a high quality FIFO implementation.

   Since E_p and E_a relate to different aspects of the EF
   implementation, they should be considered together to determine the
   quality of the implementation.

3. Per Packet delay

   The primary motivation for the packet-identity-aware definition is
   that it allows quantification of the per-packet delay bound.  This
   section discusses the issues with computing per-packet delay.

3.1. Single hop delay bound

   If the total traffic arriving to an output port I from all inputs is
   constrained by a leaky bucket with parameters (R, B), where R is the
   configured rate at I, and B is the bucket depth (burst), then the
   delay of any packet departing from I is bounded by D_p, given by

      D_p = B/R + E_p                                             (eq_7)

   (see appendix B).

   Because the delay bound depends on the configured rate R and the
   input burstiness B, it is desirable for both of these parameters to
   be visible to a user of the device.  A PDB desiring a particular
   delay bound may need to limit the range of configured rates and
   allowed burstiness that it can support in order to deliver such
   bound.  Equation (eq_7) provides a means for determining an
   acceptable operating region for the device with a given E_p.  It may
   also be useful to limit the total offered load to a given output to
   some rate R_1 < R (e.g. to obtain end-to-end delay bounds [5]).  It



Charny, et. al.              Informational                      [Page 9]

RFC 3247                Supplemental Information              March 2002


   is important to realize that, while R_1 may also be a configurable
   parameter of the device, the delay bound in (eq_7) does not depend on
   it.  It may be possible to get better bounds explicitly using the
   bound on the input rate, but the bound (eq_7) does not take advantage
   of this information.

3.2. Multi-hop worst case delay

   Although the PHB defines inherently local behavior, in this section
   we briefly discuss the issue of per-packet delay as the packet
   traverses several hops implementing EF PHB.  Given a delay bound
   (eq_7) at a single hop, it is tempting to conclude that per-packet
   bound across h hops is simply h times the bound (eq_7).  However,
   this is not necessarily the case, unless B represents the worst case
   input burstiness across all nodes in the network.

   Unfortunately, obtaining such a worst case value of B is not trivial.
   If EF PHB is implemented using aggregate class-based scheduling where
   all EF packets share a single FIFO, the effect of jitter accumulation
   may result in an increase in burstiness from hop to hop.  In
   particular, it can be shown that unless severe restrictions on EF
   utilization are imposed, even if all EF flows are ideally shaped at
   the ingress, then for any value of delay D it is possible to
   construct a network where EF utilization on any link is bounded not
   to exceed a given factor, no flow traverses more than a specified
   number of hops, but there exists a packet that experiences a delay
   more than D [5].  This result implies that the ability to limit the
   worst case burstiness and the resulting end-to-end delay across
   several hops may require not only limiting EF utilization on all
   links, but also constraining the global network topology.  Such
   topology constraints would need to be specified in the definition of
   any PDB built on top of EF PHB, if such PDB requires a strict worst
   case delay bound.

4. Packet loss

   Any device with finite buffering may need to drop packets if the
   input burstiness becomes sufficiently high.  To meet the low loss
   objective of EF, a node may be characterized by the operating region
   in which loss of EF due to  congestion will not occur.  This may be
   specified as a token bucket of  rate r <= R and burst size B that can
   be offered from all inputs to a  given output interface without loss.

   However, as discussed in the previous section, the phenomenon of
   jitter accumulation makes it generally difficult to guarantee that
   the input burstiness never exceeds the specified operating region for
   nodes internal to the DiffServ domain.  A no-loss guarantee across
   multiple hops may require specification of constraints on network



Charny, et. al.              Informational                     [Page 10]

RFC 3247                Supplemental Information              March 2002


   topology which are outside the scope of inherently local definition
   of a PHB.  Thus, it must be possible to establish whether a device
   conforms to the EF definition even when some packets are lost.

   This can be done by performing an "off-line" test of conformance to
   equations (eq_1)- (eq_4).  After observing a sequence of packets
   entering and leaving the node, the packets which did not leave are
   assumed lost and are notionally removed from the input stream.  The
   remaining packets now constitute the arrival stream and the packets
   which left the node constitute the departure stream.  Conformance to
   the equations can thus be verified by considering only those packets
   that successfully passed through the node.

   Note that specification of which packets are lost in the case when
   loss does occur is beyond the scope of the definition of EF PHB.
   However, those packets that were not lost must conform to the
   equations definition of EF PHB in section 2.1.

5. Implementation considerations

   A packet passing through a router will experience delay for a number
   of reasons.  Two familiar components of this delay are the time the
   packet spends in a buffer at an outgoing link waiting for the
   scheduler to select it and the time it takes to actually transmit the
   packet on the outgoing line.

   There may be other components of a packet's delay through a router,
   however.  A router might have to do some amount of header processing
   before the packet can be given to the correct output scheduler, for
   example.  In another case a router may have a FIFO buffer (called a
   transmission queue in [7]) where the packet sits after being selected
   by the output scheduler but before it is transmitted.  In cases such
   as these, the extra delay a packet may experience can be accounted
   for by absorbing it into the latency terms E_a and E_p.

   Implementing EF on a router with a multi-stage switch fabric requires
   special attention.  A packet may experience additional delays due to
   the fact that it must compete with other traffic for forwarding
   resources at multiple contention points in the switch core.  The
   delay an EF packet may experience before it even reaches the output-
   link scheduler should be included in the latency term.  Input-
   buffered and input/output-buffered routers based on crossbar design
   may also require modification of their latency terms.  The factors
   such as the speedup factor and the choice of crossbar arbitration
   algorithms may affect the latency terms substantially.






Charny, et. al.              Informational                     [Page 11]

RFC 3247                Supplemental Information              March 2002


   Delay in the switch core comes from two sources, both of which must
   be considered.  The first part of this delay is the fixed delay a
   packet experiences regardless of the other traffic.  This component
   of the delay includes the time it takes for things such as packet
   segmentation and reassembly in cell based cores, enqueueing and
   dequeuing at each stage, and transmission between stages.  The second
   part of the switch core delay is variable and depends on the type and
   amount of other traffic traversing the core.  This delay comes about
   if the stages in the core mix traffic flowing between different
   input/output port pairs.  Thus, EF packets must compete against other
   traffic for forwarding resources in the core.  Some of this
   competing traffic may even be traffic from other, non-EF aggregates.
   This introduces extra delay, that can also be absorbed by the latency
   term in the definition.

   To capture these considerations, in this section we will consider two
   simplified implementation examples.  The first is an ideal output
   buffered node where packets entering the device from an input
   interface are immediately delivered to the output scheduler.  In this
   model the properties of the output scheduler fully define the values
   of the parameters E_a and E_p.  We will consider the case where the
   output scheduler implements aggregate class-based queuing, so that
   all EF packets share a single queue.  We will discuss the values of
   E_a and E_p for a variety of class-based schedulers widely
   considered.

   The second example will consider a router modeled as a black box with
   a known bound on the variable delay a packet can experience from the
   time it arrives to an input to the time it is delivered to its
   destination output.  The output scheduler in isolation is assumed to
   be an aggregate scheduler where all EF packets share a single FIFO
   queue, with a known value of E_a(S)=E_p(S)=E(S).  This model provides
   a reasonable abstraction to a large class of router implementations.

5.1. The output buffered model with EF FIFO at the output.

   As has been mentioned earlier, in this model E_a = E_p, so we shall
   omit the subscript and refer to both terms as latency E.  The
   remainder of this subsection discusses E for a number of scheduling
   implementations.

5.1.1. Strict Non-preemptive Priority Queue

   A Strict Priority scheduler in which all EF packets share a single
   FIFO queue which is served at strict non-preemptive priority over
   other queues satisfies the EF definition with the latency term E =
   MTU/C where MTU is the maximum packet size and C is the speed of the
   output link.



Charny, et. al.              Informational                     [Page 12]