Internet DRAFT - draft-fang-diffserv-tc-tswtcm

draft-fang-diffserv-tc-tswtcm



HTTP/1.1 200 OK
Date: Mon, 08 Apr 2002 23:51:17 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Fri, 22 Oct 1999 13:23:00 GMT
ETag: "2e9934-3a9c-38106534"
Accept-Ranges: bytes
Content-Length: 15004
Connection: close
Content-Type: text/plain

INTERNET DRAFT                                                Wenjia Fang
Internet Engineering Task Force                      Princeton University
Differentiated Services Working Group                       Nabil Seddigh
Expires March, 2000                                        Biswajit Nandy
                                                          Nortel Networks
                                                            October, 1999


           A Time Sliding Window Three Colour Marker (TSWTCM)
                 <draft-fang-diffserv-tc-tswtcm-00.txt>


Status of this Memo

   This document is an Internet-Draft and is in  full  conformance  with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents  of  the  Internet  Engineering
   Task  Force  (IETF),  its  areas,  and its working groups.  Note that
   other groups may  also  distribute  working  documents  as  Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and  may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate  to  use  Internet-  Drafts  as  reference
   material or to cite them other than as "work in progress."

   The  list   of   current   Internet-Drafts   can   be   accessed   at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow  Directories  can  be  accessed  at
   http://www.ietf.org/shadow.html.

   Distribution of this memo is unlimited.

Abstract

   This  draft  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



Fang, Seddigh, Nandy                                            [Page 1]





INTERNET DRAFT  draft-fang-diffserv-tc-tswtcm-00.txt          March 2000


   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.

   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 scheme to associate a colour (drop precedence) with each packet
   (marker). The marker uses the algorithm specified  in  section  4  to
   associate packets with a particular colour.

   The rate estimator  provides  an  estimate  of  the  running  average
   bandwidth.  It  takes  into  account  burstiness  and smooths 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 probablistic function
   in the marker is beneficial to TCP flows as it reduces the likelihood
   of  dropping  multiple packets within a window. It is also beneficial
   for certain low bandwidth voice UDP flows.  Such  flows  can  benefit
   from  Forward Error Correction methods to reconstruct lost packets if
   the number of consecutively lost packets is kept low.


                +---------+
                | 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.






Fang, Seddigh, Nandy                                            [Page 2]





INTERNET DRAFT  draft-fang-diffserv-tc-tswtcm-00.txt          March 2000


3.0 Rate Estimator

   The Rate Estimator provides  an  estimate  of  the  traffic  stream's
   arrival rate. This rate is a running average bandwidth of the traffic
   stream over  a  window  of  time.  This  draft  does  not  dictate  a
   particular algorithm for the Rate Estimator.

   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
   use all packets or may sample only certain packets to  determine  the
   rate.

   Examples of Rate Estimation algorithms include: exponential  weighted
   moving  average  (EWMA) and the rate estimation algorithm provided in
   [TON98]. The following [TON98] is one possible example of  a  rate  
   estimator that is designed for TCP rate estimation.

   =========================================================================
   | Initially:                                                            |
   |                                                                       |
   |       Win-Length = a constant;                                        |
   |       avg-rate   = CTR;                                               |
   |       t-front    = 0;                                                 |
   |                                                                       |
   | Upon each packet's arrival, the rate estimator updates its variables: |
   |                                                                       |
   |       Bytes_in_win = avg-rate * Win-Length;                           |
   |       New_bytes    = Bytes_in_win + pkt_size;                         |
   |       avg-rate     = New_bytes/( now - t-front + Win-Length);         |
   |       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          |
   |                                                                       |
   |                                                                       |
   |               Figure 2. Example Rate Estimator Algorithm              |
   |                                                                       |
   =========================================================================

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 green.




Fang, Seddigh, Nandy                                            [Page 3]





INTERNET DRAFT  draft-fang-diffserv-tc-tswtcm-00.txt          March 2000


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

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

   - If the estimated average rate is greater than the PTR,
     packets are designated red with probability P1, designated
     yellow with probability P2 and designated green with probability
     (1-(P1+P2)). P1 is the fraction of packets contributing
     to the measured rate beyond the PTR. P2 is the fraction of
     packets contributing to that part of the measured rate
     between CTR and PTR.

   The marker MUST operate in the forwarding path of all packets.

5.0 Configuration

5.1 Rate estimator

   The  TSWTCM  Rate  Estimator  is  configured  with  one  parameter  -
   AVG_INTERVAL.  AVG_INTERVAL  is  the  amount of history (recent time)
   that should be used by the algorithm in estimating the rate.

   The AVG_INTERVAL parameter MUST be configurable and MAY be  specified
   in either milliseconds or seconds.

   Research into appropriate AVG_INTERVAL values  for  TSWTCM  with  TCP
   flows can be found in [TON98].



Fang, Seddigh, Nandy                                            [Page 4]





INTERNET DRAFT  draft-fang-diffserv-tc-tswtcm-00.txt          March 2000


   The Rate Estimator measures the average sending rate of  the  traffic
   stream  based  on  the bytes in the IP header and IP payload. It does
   not include link-specific headers in its estimation  of  the  sending
   rate.

5.2 Marker

   The TSWTCM marker is  configured  by  assigning  values  to  its  two
   traffic  parameters: Committed Target Rate (CTR) and Peak Target Rate
   (PTR).

   The PTR MUST be equal to or greater than the CTR.

   The CTR and PTR MAY be specifiable in bits per second  or  bytes  per
   second.

   The TSWTCM can be configured so that it essentially operates  with  a
   single  rate. If the PTR is set to the same value as the CTR then all
   packets will be coloured either green or red. There will be no yellow
   packets.

   If the PTR is set to link speed and the CTR is set below the PTR then
   all packets will be coloured either green or yellow. There will be no
   red packets.

6.0 Scaling properties

   The TSWTCM can work with both sender-based service  level  agreements
   and receiver-based service level agreements.



7.0 Services

   There are no restrictions on the type of traffic stream for which the
   TSWTCM  can  be utilized. It can be used to meter and mark individual
   TCP flows, aggregated TCP flows, aggregates with  both  TCP  and  UDP
   flows [UDPTCP] etc.

   The TSWTCM can be used in conjunction with the AF  PHB  to  create  a
   service  where  a  service  provider can provide decreasing levels of
   bandwidth assurance for packets originating from customer sites.

   With sufficient over-provisioning, customers are  assured  of  mostly
   achieving  their  CTR.  Sending rates beyond the CTR will have lesser
   assurance of being achieved. Sending rates beyond the  PTR  have  the
   least  chance  of  being achieved due to high drop probability of red
   packets.

   Based on the above, the Service Provider can charge a tiered level of
   service based on the final achieved rate.

8.0 Security Considerations




Fang, Seddigh, Nandy                                            [Page 5]





INTERNET DRAFT  draft-fang-diffserv-tc-tswtcm-00.txt          March 2000


   TSWTCM has no known security concerns.


9.0 References:

   [RFC2474] K. Nichols, S. Blake, F. Baker, and D. Black, "Definition of
             the Differentiated  Services Field (DS Field) in the IPv4 and IPv6
             Headers", Internet RFC 2474, December 1998.

   [RFC2475] D. Black, S. Blake, M. Carlson, E. Davies, Z. Wang, and
             W. Weiss, "An Architecture  for Differentiated Services", Internet
             RFC 2475, December 1998.

   [TON98]   D.D. Clark, W. Fang, "Explicit Allocation of Best Effort
             Packet Delivery Service", IEEE/ACM Transactions on Networking, August,
             1998, Vol 6. No. 4, pp. 362-373.

   [AFPHB]   J. Heinanen, F. Baker, W. Weiss, J. Wroclawski,
             "Assured Forwarding PHB Group", RFC 2597, June 1999

   [UDPTCP]  N. Seddigh, B. Nandy, P. Pieda, "Study of TCP and UDP
             Interaction for the AF PHB," Internet Draft,
             <draft-nsbnpp-diffserv-tcpudpaf-01.pdf>, September 1999.



10.0 Author Addresses

   Wenjia Fang
   Computer Science Dept.
   35 Olden Street,
   Princeton, NJ08540
   Email: wfang@cs.princeton.edu

   Nabil Seddigh
   Nortel Networks,
   3500 Carling Ave
   Ottawa, ON, K2H 8E9
   Canada
   Email: nseddigh@nortelnetworks.com

   Biswajit Nandy
   Nortel Networks,
   3500 Carling Ave
   Ottawa, ON, K2H 8E9
   Canada
   Email: bnandy@nortelnetworks.com










Fang, Seddigh, Nandy                                            [Page 6]