As per Relevance of the word probability, we have this rfc below:
Network Working Group W.
Request for Comments: 2859 Princeton
Category: Experimental N.
B.
Nortel
June 2000
A Time Sliding Window Three Colour Marker (TSWTCM
Status of this
This memo defines an Experimental Protocol for the
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
Copyright (C) The Internet Society (2000). All Rights Reserved
This memo defines a Time Sliding Window Three Colour Marker (TSWTCM),
which can be used as a component in a Diff-Serv traffic
[RFC2475, RFC2474]. The marker is intended to mark packets that
be treated by the Assured Forwarding (AF) Per Hop Behaviour (PHB
[AFPHB] in downstream routers. The TSWTCM meters a traffic stream
marks packets to be either green, yellow or red based on the
throughput relative to two specified rates: Committed Target
(CTR) and Peak Target Rate (PTR).
1.0
The Time Sliding Window Three Colour Marker (TSWTCM) is designed
mark packets of an IP traffic stream with colour of red, yellow
green. The marking is performed based on the measured throughput
the traffic stream as compared against the Committed Target
(CTR) and the Peak Target Rate (PTR). The TSWTCM is designed to
packets contributing to sending rate below or equal to the CTR
green colour. Packets contributing to the portion of the
between the CTR and PTR are marked yellow. Packets causing the
to exceed PTR are marked with red colour
The TSWTCM has been primarily designed for traffic streams that
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
proportionally regulated feedback control
2.0 Overview of
The TSWTCM consists of two independent components: a rate estimator
and a marker to associate a colour (drop precedence) with
packet. The marker uses the algorithm specified in section 4. If
marker is used with the AF PHB, each colour would correspond to
level of drop precedence
The rate estimator provides an estimate of the running
bandwidth. It takes into account burstiness and smoothes out
estimate to approximate the longer-term measured sending rate of
traffic stream
The marker uses the estimated rate to probabilistically
packets with one of the three colours. Using a probabilistic
in the marker is beneficial to TCP flows as it reduces the
of dropping multiple packets within a TCP window. The marker
works correctly with UDP traffic, i.e., it associates the
portion of the UDP packets with yellow or red colour marking if
flows transmit at a sustained level above the contracted rate
+---------+
| Rate |
|estimator| ==========
| | |
+---------+ |
^
| +---------+
| | |
Packet ====================>| Marker |====> Marked packet
Stream | | (Green, Yellow and Red
+---------+
Figure 1. Block diagram for the
The colour of the packet is translated into a DS field
marking. The colours red, yellow and green translate into
codepoints representing drop precedence 2, 1 and 0 of a single
class respectively
Based on feedback from four different implementations, the TSWTCM
simple and straightforward to implement. The TSWTCM can
implemented in either software or hardware depending on the nature
the forwarding engine
Fang, et al. Experimental [Page 2]
RFC 2859 TSWTCM June 2000
3.0 Rate
The Rate Estimator provides an estimate of the traffic stream'
arrival rate. This rate should approximate the running
bandwidth of the traffic stream over a specific period of
(AVG_INTERVAL).
This memo does not specify a particular algorithm for the
Estimator. However, different Rate Estimators should yield
results in terms of bandwidth estimation over the same fixed
(AVG_INTERVAL) of time. Examples of Rate Estimation schemes include
exponential weighted moving average (EWMA) and the time-based
estimation algorithm provided in [TON98].
Preferably, the Rate Estimator SHOULD maintain time-based history
its bandwidth estimation. However, the Rate Estimator MAY
weight-based history. In this case, the Estimator used
discuss how the weight translates into a time-window such
AVG_INTERVAL
Since weight-based Estimators track bandwidth based on
arrivals, a high-sending traffic stream will decay its past
faster than a low-sending traffic stream. The time-based Estimator
intended to address this problem. The latter Rate Estimator
a low-pass filter decaying function. [FANG99] shows that this
Estimator decays past history independently of the traffic stream'
packet arrival rate. The algorithm for the Rate Estimator
[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
background function. In the latter case, the implementation
ensure that the Estimator provides a reasonably accurate
of the sending rate over a window of time. The Rate Estimator
sample only certain packets to determine the rate
4.0
The Marker determines the colour of a packet based on the
presented in Figure 3. The overall effect of the marker on
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
than or equal to the PTR, packets are designated yellow
probability P0 and designated green with probability (1-P0).
P0 is the fraction of packets contributing to the
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 |
===================================================================
- If the estimated average rate is greater than the PTR
packets are designated red with probability P1,
yellow with probability P2 and designated green with
(1-(P1+P2)). P1 is the fraction of packets
to the measured rate beyond the PTR. P2 is the fraction
packets contributing to that part of the measured
between CTR and PTR
The marker MUST operate in the forwarding path of all packets
5.0
5.1 Rate
If the Rate Estimator is time-based, it should base its
estimate on the last AVG_INTERVAL of time. AVG_INTERVAL is
amount of history (recent time) that should be used by the
in estimating the rate. Essentially it represents the window of
included in the Rate Estimator's most recent result
The value of AVG_INTERVAL SHOULD be configurable, and MAY
specified in either milliseconds or seconds
Fang, et al. Experimental [Page 5]
RFC 2859 TSWTCM June 2000
[TON98] recommends that for the case where a single TCP
constitutes the contracted traffic, AVG_INTERVAL be configured
approximately the same value as the RTT of the TCP flow.
experimental studies in [GLOBE99] utilized an AVG_INTERVAL value of 1
second for scenarios where the contracted traffic consisted
multiple TCP flows, some with different RTT values. The latter
showed that AVG_INTERVAL values larger than the largest RTT for a
flow in an aggregate can be used as long as the long-term
assurance for TCP aggregates is measured at a granularity of seconds
The AVG_INTERVAL value of 1 second was also used successfully
aggregates with UDP flows
If the Rate Estimator is weight-based, the factor used in
history - WEIGHT - SHOULD be a configurable parameter
The Rate Estimator measures the average sending rate of the
stream based on the bytes in the IP header and IP payload. It
not include link-specific headers in its estimation of the
rate
5.2
The TSWTCM marker is configured by assigning values to its
traffic parameters: Committed Target Rate (CTR) and Peak Target
(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
second
The TSWTCM can be configured so that it essentially operates with
single rate. If the PTR is set to the same value as the CTR then
packets will be coloured either green or red. There will be no
packets
If the PTR is set to link speed and the CTR is set below the PTR
all packets will be coloured either green or yellow. There will be
red packets
6.0 Scaling
The TSWTCM can work with both sender-based service level
and receiver-based service level agreements
Fang, et al. Experimental [Page 6]
RFC 2859 TSWTCM June 2000
7.0
There are no restrictions on the type of traffic stream for which
TSWTCM can be utilized. It can be used to meter and mark
TCP flows, aggregated TCP flows, aggregates with both TCP and
flows [UDPTCP] etc
The TSWTCM can be used in conjunction with the AF PHB to create
service where a service provider can provide decreasing levels
bandwidth assurance for packets originating from customer sites
With sufficient over-provisioning, customers are assured of
achieving their CTR. Sending rates beyond the CTR will have
assurance of being achieved. Sending rates beyond the PTR have
least chance of being achieved due to high drop probability of
packets
Based on the above, the Service Provider can charge a tiered level
service based on the final achieved rate
8.0 Security
TSWTCM has no known security concerns
9.0
The authors would like to thank Juha Heinanen, Kenjiro Cho,
Yeom and Jamal Hadi Salim for their comments on earlier versions
this document. Their suggestions are incorporated in this memo
10.0
[TON98] D.D. Clark, W. Fang, "Explicit Allocation of Best
Packet Delivery Service", IEEE/ACM Transactions
Networking, August 1998, Vol 6. No. 4, pp. 362-373.
[RFC2474] Nichols, K., Blake, S., Baker, F. and D. Black, "
of the Differentiated Services Field (DS Field) in
IPv4 and IPv6 Headers", RFC 2474, December 1998.
[RFC2475] Black, D., Blake, S., Carlson, M., Davies, E., Wang, Z.
W. Weiss, "An Architecture for Differentiated Services",
RFC 2475, December 1998.
[FANG99] Fang, W. "The 'Expected Capacity' Framework:
Results", Princeton University Technical Report, TR-601-99,
March, 1999.
Fang, et al. Experimental [Page 7]
RFC 2859 TSWTCM June 2000
[YEOM99] I. Yeom, N. Reddy, "Impact of Marking Strategy
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
UDP Interaction in IP-QoS Differentiated Service Networks",
Proceedings of the 3rd Canadian Conference on
Research (CCBR), Ottawa, November 1999
[GLOBE99] N. Seddigh, B. Nandy, P. Pieda, "Bandwidth Assurance
for TCP flows in a Differentiated Services Network",
Proceedings of Global Internet Symposium, Globecom 99,
De Janeiro, December 1999.
11.0 Authors'
Wenjia
Computer Science Dept
35 Olden Street
Princeton, NJ08540
EMail: wfang@cs.princeton.
Nabil
Nortel Networks
3500 Carling
Ottawa, ON, K2H 8E
EMail: nseddigh@nortelnetworks.
Biswajit
Nortel Networks
3500 Carling
Ottawa, ON, K2H 8E
EMail: bnandy@nortelnetworks.
Fang, et al. Experimental [Page 8]
RFC 2859 TSWTCM June 2000
12. Full Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English
The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns
This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE
Funding for the RFC Editor function is currently provided by
Internet Society
Fang, et al. Experimental [Page 9]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
