A Time Sliding Window Three Colour Marker (TSWTCM)
A traffic marker that colors packets green, yellow or red to show sending rate relative to a contract.
Fang, W., Seddigh, N., and B. Nandy, "A Time Sliding Window Three Colour Marker (TSWTCM)", RFC 2859, DOI 10.17487/RFC2859, June 2000, <https://www.rfc-editor.org/info/rfc2859>.
@misc{rfc2859,
series = {Request for Comments},
number = 2859,
howpublished = {RFC 2859},
publisher = {RFC Editor},
doi = {10.17487/RFC2859},
url = {https://www.rfc-editor.org/info/rfc2859},
author = {W. Fang and N. Seddigh and B. Nandy},
title = {{A Time Sliding Window Three Colour Marker (TSWTCM)}},
pagetotal = 9,
year = 2000,
month = jun,
} RFC text
Contents
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.
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.
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.
========================================================================
|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.
===================================================================
| 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
If the Rate Estimator is time-based, it should base its bandwidth
estimate on the last AVG_INTERVAL of time. AVG_INTERVAL is the
amount of history (recent time) that should be used by the algorithm
in estimating the rate. Essentially it represents the window of time
included in the Rate Estimator's most recent result.
The value of AVG_INTERVAL SHOULD be configurable, and MAY be
specified in either milliseconds or seconds.
[TON98] recommends that for the case where a single TCP flow
constitutes the contracted traffic, AVG_INTERVAL be configured to
approximately the same value as the RTT of the TCP flow. Subsequent
experimental studies in [GLOBE99] utilized an AVG_INTERVAL value of 1
second for scenarios where the contracted traffic consisted of
multiple TCP flows, some with different RTT values. The latter work
showed that AVG_INTERVAL values larger than the largest RTT for a TCP
flow in an aggregate can be used as long as the long-term bandwidth
assurance for TCP aggregates is measured at a granularity of seconds.
The AVG_INTERVAL value of 1 second was also used successfully for
aggregates with UDP flows.
If the Rate Estimator is weight-based, the factor used in weighting
history - WEIGHT - SHOULD be a configurable parameter.
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
TSWTCM has no known security concerns.
9.0 Acknowledgements
The authors would like to thank Juha Heinanen, Kenjiro Cho, Ikjun
Yeom and Jamal Hadi Salim for their comments on earlier versions of
this document. Their suggestions are incorporated in this memo.
10.0 References
[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.
[RFC2474] Nichols, K., Blake, S., Baker, F. and D. Black, "Definition
of the Differentiated Services Field (DS Field) in the
IPv4 and IPv6 Headers", RFC 2474, December 1998.
[RFC2475] Black, D., Blake, S., Carlson, M., Davies, E., Wang, Z. and
W. Weiss, "An Architecture for Differentiated Services",
RFC 2475, December 1998.
[FANG99] Fang, W. "The 'Expected Capacity' Framework: Simulation
Results", Princeton University Technical Report, TR-601-99,
March, 1999.
[YEOM99] I. Yeom, N. Reddy, "Impact of Marking Strategy on
Aggregated Flows in a Differentiated Services Network",
Proceedings of IwQoS, May 1999.
[AFPHB] Heinanen, J., Baker, F., Weiss, W. and J. Wroclawski,
"Assured Forwarding PHB Group", RFC 2597, June 1999.
[UDPTCP] P. Pieda, N. Seddigh, B. Nandy, "The Dynamics of TCP and
UDP Interaction in IP-QoS Differentiated Service Networks",
Proceedings of the 3rd Canadian Conference on Broadband
Research (CCBR), Ottawa, November 1999
[GLOBE99] N. Seddigh, B. Nandy, P. Pieda, "Bandwidth Assurance Issues
for TCP flows in a Differentiated Services Network",
Proceedings of Global Internet Symposium, Globecom 99, Rio
De Janeiro, December 1999.
11.0 Authors' 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
12. Full Copyright Statement
Copyright (C) The Internet Society (2000). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
AI ELI5
On this page
§1.0Introduction
The Time Sliding Window Three Colour Marker (TSWTCM) marks individual packets with one of three colours based on how fast the traffic stream is sending compared to two rate limits. These limits are the Committed Target Rate (CTR), the rate the customer has paid for, and the Peak Target Rate (PTR), a burst rate above that.
Packets sending at or below the CTR get marked green. Packets in the part of the traffic between CTR and PTR get marked yellow. Packets causing the rate to exceed PTR get marked red. TSWTCM is designed for use with the Assured Forwarding Per Hop Behaviour (AF PHB) in DiffServ, where each colour maps to a drop precedence level in the router.
A key design choice is to mark using probability rather than deterministic rules. This protects TCP flows from losing multiple packets in the same window, which would reduce throughput.
TSWTCM watches the rate at which data arrives. If it is going slow, paint green. If it is between two limits, paint yellow with some chance. If it is over the top limit, paint red with some chance. This way, routers know what to drop first when busy.
§2.0How TSWTCM Works
TSWTCM has two independent parts. A rate estimator measures the running average bandwidth of the traffic stream, smoothing out burstiness to approximate the longer-term sending rate. A marker then assigns a colour to each packet using that estimate.
The rate estimator can use different algorithms (such as exponential weighted moving average or time-based filters) as long as they yield similar results over a time window called AVG_INTERVAL. Preferably, it tracks time-based history rather than weight-based history, so that fast flows do not decay their history faster than slow flows.
The marker uses a probabilistic function to decide the colour. When the rate is between CTR and PTR, the probability of yellow marking is the fraction of the traffic above CTR. When the rate exceeds PTR, probability of red is the fraction above PTR, probability of yellow is the fraction between CTR and PTR, and the remainder is green. This probabilistic approach reduces the chance that multiple packets from the same flow are marked red or yellow.
The estimator measures how much data arrived recently, smoothed out so bursts do not fool it. The marker then rolls dice to paint each packet, so the chance of painting it red or yellow matches how much the traffic is over its limit.
§5.0Configuration
| Field | Name | Size | Value | Description |
|---|---|---|---|---|
RATE-RANGE | Average Rate | 3 bytes | Measured sending rate against limits | |
BELOW-CTR | At or Below CTR | 3 bytes | All packets marked green | |
CTR-TO-PTR | CTR to PTR | 3 bytes | Mark yellow with probability (rate-CTR)/rate | |
ABOVE-PTR | Above PTR | 3 bytes | Mark red and yellow probabilistically |
TSWTCM configuration centers on two parameters: the CTR and PTR. The PTR MUST be equal to or greater than the CTR. Both MAY be expressed in bits per second or bytes per second.
For the rate estimator, the AVG_INTERVAL time window should be configurable. Recommendations from the RFC suggest using an interval roughly equal to the round-trip time for a single TCP flow, or 1 second for aggregates with multiple TCP flows or mixed TCP and UDP traffic. If weight-based estimation is used, the WEIGHT factor becomes configurable.
Special cases exist: if PTR equals CTR, TSWTCM operates with a single rate and packets are marked only green or red, never yellow. If PTR is set to link speed and CTR is below that, packets are marked only green or yellow, never red. The rate estimator measures IP header and payload but does not include link-layer headers.
You set two numbers: the promised rate and the burst limit. You can also pick how far back in time the meter looks to calculate the average. Different trade-offs let you tune for single TCP flows or large aggregates.
§4.0The Marking Algorithm
The marker operates in the router forwarding path and implements the following rules:
If the estimated average rate is less than or equal to CTR, all packets are marked green.
If the average rate is greater than CTR but at or below PTR, packets are marked yellow with probability P0 and green with probability (1-P0), where P0 is the fraction (avg-rate - CTR) / avg-rate.
If the average rate exceeds PTR, packets are marked red with probability P1, yellow with probability P2, and green with probability (1 - P1 - P2), where P1 is the fraction (avg-rate - PTR) / avg-rate and P2 is the fraction (PTR - CTR) / avg-rate.
This algorithm ensures that when the traffic is within contract, green packets dominate. When it is over contract, the excess traffic is distributed probabilistically among yellow and red, in proportions matching how much the rate has exceeded each threshold.
The algorithm uses simple math: divide the excess traffic by the total traffic to get the chance of painting the packet yellow or red. This way, if the flow sends 20% over limit, about 20% of its packets get painted yellow.
§7.0Use in Services
TSWTCM works with any type of traffic stream: single TCP flows, aggregates of TCP flows, and mixes of TCP and UDP. When used with Assured Forwarding, a service provider can offer tiered service based on drop probability. Packets marked green have the highest chance of delivery, yellow are intermediate, and red have the lowest.
With sufficient over-provisioning of the network, customers are mostly assured of achieving their CTR. Traffic between CTR and PTR has lesser assurance. Traffic above PTR has the least assurance due to high drop probability of red packets.
This allows the service provider to charge customers on a sliding scale: one price for CTR delivery, a lower price for PTR delivery, and rates in between for the intermediate tier.
Operators can promise to deliver all green packets and most yellow packets, but only some red ones. By offering different prices for each tier, they can give customers what they pay for.