rfc2859.txt

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

Network Working Group                                             W. Fang
Request for Comments: 2859                           Princeton University
Category: Experimental                                         N. Seddigh
                                                                 B. Nandy
                                                          Nortel Networks
                                                                June 2000


           A Time Sliding Window Three Colour Marker (TSWTCM)

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2000).  All Rights Reserved.

Abstract

   This memo defines a Time Sliding Window Three Colour Marker (TSWTCM),
   which can be used as a component in a Diff-Serv traffic conditioner
   [RFC2475, RFC2474].  The marker is intended to mark packets that will
   be treated by the Assured Forwarding (AF) Per Hop Behaviour (PHB)
   [AFPHB] in downstream routers. The TSWTCM meters a traffic stream and
   marks packets to be either green, yellow or red based on the measured
   throughput relative to two specified rates: Committed Target Rate
   (CTR) and Peak Target Rate (PTR).

1.0 Introduction

   The Time Sliding Window Three Colour Marker (TSWTCM) is designed to
   mark packets of an IP traffic stream with colour of red, yellow or
   green. The marking is performed based on the measured throughput of
   the traffic stream as compared against the Committed Target Rate
   (CTR) and the Peak Target Rate (PTR). The TSWTCM is designed to mark
   packets contributing to sending rate below or equal to the CTR with
   green colour.  Packets contributing to the portion of the rate
   between the CTR and PTR are marked yellow. Packets causing the rate
   to exceed PTR are marked with red colour.

   The TSWTCM has been primarily designed for traffic streams that will
   be forwarded based on the AF PHB in core routers.





Fang, et al.                  Experimental                      [Page 1]

RFC 2859                         TSWTCM                        June 2000


   The TSWTCM operates based on simple control theory principles of
   proportionally regulated feedback control.

2.0 Overview of TSWTCM

   The TSWTCM consists of two independent components: a rate estimator,
   and a marker to associate a colour (drop precedence) with each
   packet.  The marker uses the algorithm specified in section 4. If the
   marker is used with the AF PHB, each colour would correspond to a
   level of drop precedence.

   The rate estimator provides an estimate of the running average
   bandwidth.  It takes into account burstiness and smoothes out its
   estimate to approximate the longer-term measured sending rate of the
   traffic stream.

   The marker uses the estimated rate to probabilistically associate
   packets with one of the three colours. Using a probabilistic function
   in the marker is beneficial to TCP flows as it reduces the likelihood
   of dropping multiple packets within a TCP window.  The marker also
   works correctly with UDP traffic, i.e., it associates the appropriate
   portion of the UDP packets with yellow or red colour marking if such
   flows transmit at a sustained level above the contracted rate.

                +---------+
                | Rate    | Rate
                |estimator| ==========
                |         |          |
                +---------+          |
                   ^                 V
                   |             +---------+
                   |             |         |
     Packet ====================>| Marker  |====> Marked packet stream
     Stream                      |         |    (Green, Yellow and Red)
                                 +---------+

                   Figure 1.  Block diagram for the TSWTCM

   The colour of the packet is translated into a DS field packet
   marking.  The colours red, yellow and green translate into DS
   codepoints representing drop precedence 2, 1 and 0 of a single AF
   class respectively.

   Based on feedback from four different implementations, the TSWTCM is
   simple and straightforward to implement.  The TSWTCM can be
   implemented in either software or hardware depending on the nature of
   the forwarding engine.




Fang, et al.                  Experimental                      [Page 2]

RFC 2859                         TSWTCM                        June 2000


3.0 Rate Estimator

   The Rate Estimator provides an estimate of the traffic stream's
   arrival rate.  This rate should approximate the running average
   bandwidth of the traffic stream over a specific period of time
   (AVG_INTERVAL).

   This memo does not specify a particular algorithm for the Rate
   Estimator.  However, different Rate Estimators should yield similar
   results in terms of bandwidth estimation over the same fixed window
   (AVG_INTERVAL) of time.  Examples of Rate Estimation schemes include:
   exponential weighted moving average (EWMA) and the time-based rate
   estimation algorithm provided in [TON98].

   Preferably, the Rate Estimator SHOULD maintain time-based history for
   its bandwidth estimation.  However, the Rate Estimator MAY utilize
   weight-based history.  In this case, the Estimator used should
   discuss how the weight translates into a time-window such as
   AVG_INTERVAL.

   Since weight-based Estimators track bandwidth based on packet
   arrivals, a high-sending traffic stream will decay its past history
   faster than a low-sending traffic stream. The time-based Estimator is
   intended to address this problem. The latter Rate Estimator utilizes
   a low-pass filter decaying function. [FANG99] shows that this Rate
   Estimator decays past history independently of the traffic stream's
   packet arrival rate.  The algorithm for the Rate Estimator from
   [TON98] is shown in Figure 2 below.























Fang, et al.                  Experimental                      [Page 3]

RFC 2859                         TSWTCM                        June 2000


========================================================================
|Initially:                                                            |
|                                                                      |
|      AVG_INTERVAL = a constant;                                      |
|      avg-rate     = CTR;                                             |
|      t-front      = 0;                                               |
|                                                                      |
|Upon each packet's arrival, the rate estimator updates its variables: |
|                                                                      |
|      Bytes_in_win = avg-rate * AVG_INTERVAL;                         |
|      New_bytes    = Bytes_in_win + pkt_size;                         |
|      avg-rate     = New_bytes/( now - t-front + AVG_INTERVAL);       |
|      t-front      = now;                                             |
|                                                                      |
|Where:                                                                |
|      now          = The time of the current packet arrival           |
|      pkt_size     = The packet size in bytes of the arriving packet  |
|      avg-rate     = Measured Arrival Rate of traffic stream          |
|      AVG_INTERVAL = Time window over which history is kept           |
|                                                                      |
|                                                                      |
|              Figure 2. Example Rate Estimator Algorithm              |
|                                                                      |
========================================================================

   The Rate Estimator MAY operate in the Router Forwarding Path or as a
   background function.  In the latter case, the implementation MUST
   ensure that the Estimator provides a reasonably accurate estimation
   of the sending rate over a window of time.  The Rate Estimator MAY
   sample only certain packets to determine the rate.

4.0 Marker

   The Marker determines the colour of a packet based on the algorithm
   presented in Figure 3.  The overall effect of the marker on the
   packets of a traffic stream is to ensure that:

   - If the estimated average rate is less than or equal to the CTR,
     packets of the stream are designated green.

   - If the estimated average rate is greater than the CTR but less
     than or equal to the PTR, packets are designated yellow with
     probability P0 and designated green with probability (1-P0).
     P0 is the fraction of packets contributing to the measured
     rate beyond the CTR.






Fang, et al.                  Experimental                      [Page 4]

RFC 2859                         TSWTCM                        June 2000


   ===================================================================
   |       avg-rate = Estimated Avg Sending Rate of Traffic Stream   |
   |                                                                 |
   |       if (avg-rate <= CTR)                                      |
   |               the packet is green;                              |
   |       else if (avg-rate <= PTR) AND (avg-rate > CTR)            |
   |                                 (avg-rate - CTR)                |
   |               calculate P0  =   ----------------                |
   |                                       avg-rate                  |
   |               with probability P0 the packet is yellow;         |
   |               with probability (1-P0) the packet is green;      |
   |       else                                                      |
   |                                 (avg-rate - PTR)                |
   |               calculate P1  =   ----------------                |
   |                                      avg-rate                   |
   |                                 (PTR - CTR)                     |
   |               calculate P2  =   -----------                     |
   |                                  avg-rate                       |
   |               with probability P1 the packet is red;            |
   |               with probability P2 the packet is yellow;         |
   |               with probability (1-(P1+P2)) the packet is green; |
   |                                                                 |
   |                 Figure 3. TSWTCM Marking Algorithm              |
   ===================================================================