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]