draft-ietf-tsvwg-tfrc-01.txt   draft-ietf-tsvwg-tfrc-02.txt 
Internet Engineering Task Force TSV WG Internet Engineering Task Force TSV WG
INTERNET-DRAFT Mark Handley/ACIRI INTERNET-DRAFT Mark Handley/ACIRI
draft-ietf-tsvwg-tfrc-01.txt Jitendra Padhye/ACIRI draft-ietf-tsvwg-tfrc-02.txt Jitendra Padhye/ACIRI
Sally Floyd/ACIRI Sally Floyd/ACIRI
Joerg Widmer/Univ. Mannheim Joerg Widmer/Univ. Mannheim
2 March 2001 18 May 2001
Expires: September 2001 Expires: November 2001
TCP Friendly Rate Control (TFRC): TCP Friendly Rate Control (TFRC):
Protocol Specification Protocol Specification
Status of this Document Status of this Document
This document is an Internet-Draft and is in full conformance with all This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Task Internet-Drafts are working documents of the Internet Engineering Task
skipping to change at page 3, line 16 skipping to change at page 3, line 16
1. Introduction. . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 5
3. Protocol Mechanism. . . . . . . . . . . . . . . . . . . 5 3. Protocol Mechanism. . . . . . . . . . . . . . . . . . . 5
3.1. TCP Throughput Equation. . . . . . . . . . . . . . . 5 3.1. TCP Throughput Equation. . . . . . . . . . . . . . . 5
3.2. Packet Contents. . . . . . . . . . . . . . . . . . . 7 3.2. Packet Contents. . . . . . . . . . . . . . . . . . . 7
3.2.1. Data Packets. . . . . . . . . . . . . . . . . . . 7 3.2.1. Data Packets. . . . . . . . . . . . . . . . . . . 7
3.2.2. Feedback Packets. . . . . . . . . . . . . . . . . 8 3.2.2. Feedback Packets. . . . . . . . . . . . . . . . . 8
4. Data Sender Protocol. . . . . . . . . . . . . . . . . . 8 4. Data Sender Protocol. . . . . . . . . . . . . . . . . . 8
4.1. Measuring the Packet Size. . . . . . . . . . . . . . 8 4.1. Measuring the Packet Size. . . . . . . . . . . . . . 8
4.2. Sender behavior when a feedback packet is 4.2. Sender Initialization. . . . . . . . . . . . . . . . 9
4.3. Sender behavior when a feedback packet is
received. . . . . . . . . . . . . . . . . . . . . . . . . 9 received. . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Expiration of nofeedback timer . . . . . . . . . . . 10 4.4. Expiration of nofeedback timer . . . . . . . . . . . 10
4.4. Sender Initialization. . . . . . . . . . . . . . . . 11
4.5. Preventing Oscillations. . . . . . . . . . . . . . . 11 4.5. Preventing Oscillations. . . . . . . . . . . . . . . 11
4.6. Scheduling of Packet Transmissions . . . . . . . . . 12 4.6. Scheduling of Packet Transmissions . . . . . . . . . 12
5. Calculation of the loss event rate (p). . . . . . . . . 13 5. Calculation of the Loss Event Rate (p). . . . . . . . . 13
5.1. Detection of Lost or Marked Packets. . . . . . . . . 13 5.1. Detection of Lost or Marked Packets. . . . . . . . . 13
5.2. Translation from Loss History to Loss Events . . . . 14 5.2. Translation from Loss History to Loss Events . . . . 13
5.3. Inter-loss Event Interval. . . . . . . . . . . . . . 15 5.3. Inter-loss Event Interval. . . . . . . . . . . . . . 15
5.4. Average Loss Interval. . . . . . . . . . . . . . . . 15 5.4. Average Loss Interval. . . . . . . . . . . . . . . . 15
5.5. History Discounting. . . . . . . . . . . . . . . . . 16 5.5. History Discounting. . . . . . . . . . . . . . . . . 16
6. Data Receiver Protocol. . . . . . . . . . . . . . . . . 18 6. Data Receiver Protocol. . . . . . . . . . . . . . . . . 18
6.1. Receiver behavior when a data packet is 6.1. Receiver behavior when a data packet is
received. . . . . . . . . . . . . . . . . . . . . . . . . 18 received. . . . . . . . . . . . . . . . . . . . . . . . . 19
6.2. Expiration of feedback timer . . . . . . . . . . . . 19 6.2. Expiration of feedback timer . . . . . . . . . . . . 19
6.3. Receiver initialization. . . . . . . . . . . . . . . 20 6.3. Receiver initialization. . . . . . . . . . . . . . . 20
6.3.1. Initializing the Loss History after the
First Loss Event . . . . . . . . . . . . . . . . . . . . 20
7. Security Considerations . . . . . . . . . . . . . . . . 20 7. Security Considerations . . . . . . . . . . . . . . . . 20
8. Authors' Addresses. . . . . . . . . . . . . . . . . . . 20 8. Authors' Addresses. . . . . . . . . . . . . . . . . . . 21
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . 21 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . 21
10. References . . . . . . . . . . . . . . . . . . . . . . 21 10. References . . . . . . . . . . . . . . . . . . . . . . 22
1. Introduction 1. Introduction
This document specifies TCP-Friendly Rate Control (TFRC). TFRC is a This document specifies TCP-Friendly Rate Control (TFRC). TFRC is a
congestion control mechanism designed for unicast flows operating in a congestion control mechanism designed for unicast flows operating in a
Internet environment and competing with TCP traffic. Instead of Internet environment and competing with TCP traffic. Instead of
specifying a complete protocol, this document simply specifies a specifying a complete protocol, this document simply specifies a
congestion control mechanism that could be used in a transport protocol congestion control mechanism that could be used in a transport protocol
such as RTP [5], in an application incorporating end-to-end congestion such as RTP [6], in an application incorporating end-to-end congestion
control at the application level, or in the context of endpoint control at the application level, or in the context of endpoint
congestion management. This document does not discuss packet formats, congestion management [BRS99]. This document does not discuss packet
reliability, or implementation-related issues. formats, reliability, or implementation-related issues.
TFRC is designed to be reasonably fair when competing for bandwidth with TFRC is designed to be reasonably fair when competing for bandwidth with
TCP flows [1]. However it has a much lower variation of throughput over TCP flows [2]. However it has a much lower variation of throughput over
time compared with TCP, which makes it more suitable for applications time compared with TCP, which makes it more suitable for applications
such as telephony or streaming media where a relatively smooth sending such as telephony or streaming media where a relatively smooth sending
rate is of importance. rate is of importance.
The penalty of having smoother throughput than TCP whilst competing The penalty of having smoother throughput than TCP while competing
fairly for bandwidth is that TFRC responds slower than TCP to changes in fairly for bandwidth is that TFRC responds slower than TCP to changes in
available bandwidth. Thus TFRC should only be used when the application available bandwidth. Thus TFRC should only be used when the application
has a requirement for smooth throughput, in particular, avoiding TCP's has a requirement for smooth throughput, in particular, avoiding TCP's
halving of the sending rate in response to a single packet drop. For halving of the sending rate in response to a single packet drop. For
applications that simply require to transfer as much data as possible in applications that simply need to transfer as much data as possible in as
as short a time as possible we recommend using TCP, or if reliability is short a time as possible we recommend using TCP, or if reliability is
not required, using an Additive-Increase, Multiplicative-Decrease (AIMD) not required, using an Additive-Increase, Multiplicative-Decrease (AIMD)
congestion control scheme with similar parameters to those used by TCP. congestion control scheme with similar parameters to those used by TCP.
TFRC is designed for applications that use a fixed packet size, and vary TFRC is designed for applications that use a fixed packet size, and vary
their sending rate in packets per second in response to congestion. their sending rate in packets per second in response to congestion.
Some audio applications require a fixed interval of time between packets Some audio applications require a fixed interval of time between packets
and vary their packet size instead of their packet rate in response to and vary their packet size instead of their packet rate in response to
congestion. The congestion control mechanism in this document cannot be congestion. The congestion control mechanism in this document cannot be
used by those applications; variants of TFRC for applications that have used by those applications; variants of TFRC for applications that have
a fixed sending rate but vary their packet size in response to a fixed sending rate but vary their packet size in response to
congestion will be addressed in a separate document. congestion will be addressed in a separate document.
TFRC is a receiver-based mechanism, with the calculation of the TFRC is a receiver-based mechanism, with the calculation of the
congestion control information (i.e., the loss event rate) in the data congestion control information (i.e., the loss event rate) in the data
receiver rather in the data sender. This is well-suited to an receiver rather in the data sender. This is well-suited to an
application where the sender is a large web server handling many application where the sender is a large server handling many concurrent
concurrent connections, and the receiver has more memory and CPU cycles connections, and the receiver has more memory and CPU cycles available
available for computation. In addition, a receiver-based mechanism is for computation. In addition, a receiver-based mechanism is more
more suitable as a building block for multicast congestion control. suitable as a building block for multicast congestion control.
2. Terminology 2. Terminology
In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" are to be interpreted as described in RFC 2119 and indicate "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate
requirement levels for compliant TFRC implementations. requirement levels for compliant TFRC implementations.
3. Protocol Mechanism 3. Protocol Mechanism
For its congestion control mechanism, TFRC directly uses a throughput For its congestion control mechanism, TFRC directly uses a throughput
equation for the allowed sending rate as a function of the loss event equation for the allowed sending rate as a function of the loss event
rate and round-trip time. In order to compete fairly with TCP, TFRC rate and round-trip time. In order to compete fairly with TCP, TFRC
uses the TCP throughput equation, which roughly describes TCP's sending uses the TCP throughput equation, which roughly describes TCP's sending
rate as a function of the loss event rate, round-trip time, and packet rate as a function of the loss event rate, round-trip time, and packet
size. We define a loss event as one or more lost or marked packets from size. We define a loss event as one or more lost or marked packets from
a window of data, where a marked packet refers to a mark from Explicit a window of data, where a marked packet refers to a congestion
Congestion Notification (ECN). indication from Explicit Congestion Notification (ECN) [7].
Generally speaking, TFRC's congestion control mechanism works as Generally speaking, TFRC's congestion control mechanism works as
follows: follows:
o The receiver measures the loss event rate and feeds this o The receiver measures the loss event rate and feeds this
information back to the sender. information back to the sender.
o The sender also uses these feedback messages to measure the round- o The sender also uses these feedback messages to measure the round-
trip time (RTT). trip time (RTT).
skipping to change at page 5, line 46 skipping to change at page 5, line 46
rate. rate.
The dynamics of TFRC are sensitive to how the measurements are performed The dynamics of TFRC are sensitive to how the measurements are performed
and applied. We recommend specific mechanisms below to perform and and applied. We recommend specific mechanisms below to perform and
apply these measurements. Other mechanisms are possible, but it is apply these measurements. Other mechanisms are possible, but it is
important to understand how the interactions between mechanisms affect important to understand how the interactions between mechanisms affect
the dynamics of TFRC. the dynamics of TFRC.
3.1. TCP Throughput Equation 3.1. TCP Throughput Equation
Any realistic equation of TCP throughput as a function of loss event Any realistic equation giving TCP throughput as a function of loss event
rate and RTT should be suitable for use in TFRC. However, we note that rate and RTT should be suitable for use in TFRC. However, we note that
the TCP throughput equation used must reflect TCP's retransmit timeout the TCP throughput equation used must reflect TCP's retransmit timeout
behavior, as this dominates TCP throughput at higher loss rates. We behavior, as this dominates TCP throughput at higher loss rates. We
also note that the assumptions implicit in the throughput equation about also note that the assumptions implicit in the throughput equation about
the loss event rate parameter have to be a reasonable match to how the the loss event rate parameter have to be a reasonable match to how the
loss rate or loss event rate is actually measured. Whilst this match is loss rate or loss event rate is actually measured. While this match is
not perfect for the throughput equation and loss rate measurement not perfect for the throughput equation and loss rate measurement
mechanisms given below, in practice the assumptions turn out to be close mechanisms given below, in practice the assumptions turn out to be close
enough. enough.
The throughput equation we currently recommend for TFRC is a slightly The throughput equation we currently recommend for TFRC is a slightly
simplified version of the throughput equation for Reno TCP from [3]. simplified version of the throughput equation for Reno TCP from [4].
Ideally we'd prefer a throughput equation based on SACK TCP, but no one Ideally we'd prefer a throughput equation based on SACK TCP, but no one
has yet derived the throughput equation for SACK TCP, and from both has yet derived the throughput equation for SACK TCP, and from both
simulations and experiments, the differences between the two equations simulations and experiments, the differences between the two equations
are relatively minor. are relatively minor.
The throughput equation is: The throughput equation is:
s s
X = ---------------------------------------------------------- X = ----------------------------------------------------------
R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2))) R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
skipping to change at page 6, line 42 skipping to change at page 6, line 42
events as a fraction of the number of packets transmitted. events as a fraction of the number of packets transmitted.
t_RTO is the TCP retransmission timeout value in seconds. t_RTO is the TCP retransmission timeout value in seconds.
b is the number of packets acknowledged by a single TCP b is the number of packets acknowledged by a single TCP
acknowledgement. acknowledgement.
We further simplify this by setting t_RTO = 4*R. A more accurate We further simplify this by setting t_RTO = 4*R. A more accurate
calculation of t_RTO is possible, but experiments with the current calculation of t_RTO is possible, but experiments with the current
setting have resulted in reasonable fairness with existing TCP setting have resulted in reasonable fairness with existing TCP
implementations [4]. Another possibility would be to set t_RTO = max(4R, implementations [5]. Another possibility would be to set t_RTO = max(4R,
one second), to match the recommended minimum of one second on the RTO one second), to match the recommended minimum of one second on the RTO
[7]. [8].
Many current TCP connections use delayed acknowledgements, sending an Many current TCP connections use delayed acknowledgements, sending an
acknowledgement for every two data packets received, and thus have a acknowledgement for every two data packets received, and thus have a
sending rate modeled by b = 2. However, TCP is also allowed to send an sending rate modeled by b = 2. However, TCP is also allowed to send an
acknowledgement for every data packet, and this would be modeled by b = acknowledgement for every data packet, and this would be modeled by b =
1. Because many TCP implementations do not use delayed 1. Because many TCP implementations do not use delayed
acknowledgements, we recommend b = 1. acknowledgements, we recommend b = 1.
In future, different TCP equations may be substituted for this equation. In future, different TCP equations may be substituted for this equation.
The requirement is that the throughput equation be a reasonable The requirement is that the throughput equation be a reasonable
approximation of the sending rate of TCP for conformant TCP congestion approximation of the sending rate of TCP for conformant TCP congestion
control. control.
The parameters s (packet size), p (loss event rate) and R (RTT) need to The parameters s (packet size), p (loss event rate) and R (RTT) need to
be measured or calculated by a TFRC implementation. The measurement of be measured or calculated by a TFRC implementation. The measurement of
s is specified in Section 4.1, measurement of R is specified in Section s is specified in Section 4.1, measurement of R is specified in Section
4.2, and measurement of p is specified in Section 4.2. In the rest of 4.3, and measurement of p is specified in Section 5. In the rest of this
this document, all data rates are measured in bytes/second. document all data rates are measured in bytes/second.
3.2. Packet Contents 3.2. Packet Contents
Before specifying the sender and receiver functionality, we describe the Before specifying the sender and receiver functionality, we describe the
contents of the data packets sent by the sender and feedback packets contents of the data packets sent by the sender and feedback packets
sent by the receiver. As TFRC will be used along with a transport sent by the receiver. As TFRC will be used along with a transport
protocol, we do not specify packet formats, as these depend on the protocol, we do not specify packet formats, as these depend on the
details of the transport protocol used. details of the transport protocol used.
3.2.1. Data Packets 3.2.1. Data Packets
skipping to change at page 8, line 48 skipping to change at page 8, line 48
o The sender behavior when the nofeedback timer expires. o The sender behavior when the nofeedback timer expires.
o Oscillation prevention (optional) o Oscillation prevention (optional)
o Scheduling of transmission on non-realtime operating systems. o Scheduling of transmission on non-realtime operating systems.
4.1. Measuring the Packet Size 4.1. Measuring the Packet Size
The parameter s (packet size) is normally known to an application. This The parameter s (packet size) is normally known to an application. This
may not be the case in two cases: may not be so in two cases:
o The packet size naturally varies depending on the data. In this o The packet size naturally varies depending on the data. In this
case, although the packet size varies, that variation is not case, although the packet size varies, that variation is not
coupled to the transmit rate. It should normally be safe to use an coupled to the transmit rate. It should normally be safe to use an
estimate of the mean packet size for s. estimate of the mean packet size for s.
o The application needs to change the packet size rather than the o The application needs to change the packet size rather than the
number of packets per second to perform congestion control. This number of packets per second to perform congestion control. This
would normally be the case with packet audio applications where a would normally be the case with packet audio applications where a
fixed interval of time needs to be represented by each packet. fixed interval of time needs to be represented by each packet.
Such applications need to have a completely different way of Such applications need to have a completely different way of
measuring parameters. measuring parameters.
The second class of applications are discussed separately in a separate The second class of applications are discussed separately in a separate
document. For the remainder of this section we assume the sender can document. For the remainder of this section we assume the sender can
estimate the packet size, and that congestion control is performed by estimate the packet size, and that congestion control is performed by
adjusting the number of packets sent per second. adjusting the number of packets sent per second.
4.2. Sender behavior when a feedback packet is received 4.2. Sender Initialization
To initialize the sender, the value of X is set to 1 packet/second and
the nofeedback timer is set to expire after 2 seconds. The initial
values for R (RTT) and t_RTO are undefined until they are set as
described above. The intial value of tld, for the Time Last Doubled
during slow-start, is set to -1.
4.3. Sender behavior when a feedback packet is received
The sender knows its current sending rate, X, and maintains an estimate The sender knows its current sending rate, X, and maintains an estimate
of the current round trip time, R, and an estimate of the timeout of the current round trip time, R, and an estimate of the timeout
interval, t_RTO. interval, t_RTO.
When a feedback packet is received by the sender at time t_now, the When a feedback packet is received by the sender at time t_now, the
following actions should be performed: following actions should be performed:
1) Calculate a new round trip sample. 1) Calculate a new round trip sample.
R_sample = (t_now - t_recvdata) - t_delay. R_sample = (t_now - t_recvdata) - t_delay.
skipping to change at page 9, line 48 skipping to change at page 10, line 9
Else Else
R = q*R + (1-q)*R_sample; R = q*R + (1-q)*R_sample;
TFRC is not sensitive to the precise value for the filter constant TFRC is not sensitive to the precise value for the filter constant
q, but we recommend a default value of 0.9. q, but we recommend a default value of 0.9.
3) Update the timeout interval: 3) Update the timeout interval:
t_RTO = 4*R. t_RTO = 4*R.
4) Update the sending rate: 4) Update the sending rate as follows:
First, calculate the allowed transmit rate, X_calc, using the TCP
equation from Section 3.1.
Then:
If (p > 0) If (p > 0)
X = min(X_calc, 2*X_recv, s/64); Calculate X_calc using the TCP throughput equation.
X = max(min(X_calc, 2*X_recv), s/64);
Else Else
If (t_now - tld >= RTT)
X = max(min(2*X, 2*X_recv), s/RTT); X = max(min(2*X, 2*X_recv), s/RTT);
tld = t_now;
Note that if p == 0, then the sender is in slow-start phase, where Note that if p == 0, then the sender is in slow-start phase,
it approximately doubles the sending rate each round-trip time where it approximately doubles the sending rate each round-
until a loss occurs. The s/RTT term gives a minimum sending rate trip time until a loss occurs. The s/RTT term gives a minimum
during slow-start of one packet per RTT. When p > 0, the sender sending rate during slow-start of one packet per RTT. When p
sends at least one packet every 64 seconds. > 0, the sender sends at least one packet every 64 seconds.
5) Reset the nofeedback timer to expire after max(2*R, 2*s/X) seconds. 5) Reset the nofeedback timer to expire after max(4*R, 2*s/X) seconds.
4.3. Expiration of nofeedback timer 4.4. Expiration of nofeedback timer
If the nofeedback timer expires, the sender should perform the following If the nofeedback timer expires, the sender should perform the following
actions: actions:
1) Cut the sending rate in half. This is done by modifying the 1) Cut the sending rate in half. This is done by modifying the
sender's cached copy of X_recv (the receive rate). Because the sender's cached copy of X_recv (the receive rate). Because the
sending rate is limited to at most twice X_recv, modifying X_recv sending rate is limited to at most twice X_recv, modifying X_recv
limits the current sending rate, but allows the sender to slow- limits the current sending rate, but allows the sender to slow-
start, doubling its sending rate each RTT, if feedback messages start, doubling its sending rate each RTT, if feedback messages
resume reporting no losses. resume reporting no losses.
skipping to change at page 11, line 5 skipping to change at page 11, line 10
the case of persistent absence of feedback. the case of persistent absence of feedback.
2) The value of X must then be recalculated as described under point 2) The value of X must then be recalculated as described under point
(4) above. (4) above.
If the nofeedback timer expires when the sender does not yet have If the nofeedback timer expires when the sender does not yet have
an RTT sample, and has not yet received any feedback from the an RTT sample, and has not yet received any feedback from the
sender, then step (1) can be skipped, and the sending rate cut in sender, then step (1) can be skipped, and the sending rate cut in
half directly: half directly:
X = X_calc. X = max(X/2, s/64)
3) Restart the nofeedback timer to expire after max(4*R, 2*s/X) 3) Restart the nofeedback timer to expire after max(4*R, 2*s/X)
seconds. seconds.
Note that when the sender stops sending, the receiver will stop sending Note that when the sender stops sending, the receiver will stop sending
feedback. This will cause the nofeedback timer to start to expire and feedback. This will cause the nofeedback timer to start to expire and
decrease X_recv. If the sender subsequently starts to send again, decrease X_recv. If the sender subsequently starts to send again,
X_recv will limit the transmit rate, and a normal slowstart phase will X_recv will limit the transmit rate, and a normal slowstart phase will
occur until the transmit rate reached X_calc. occur until the transmit rate reaches X_calc.
4.4. Sender Initialization
To initialize the sender, the value of X is set to 1 packet/second and
the nofeedback timer is set to expire after 2 seconds. The initial
values for R (RTT) and t_RTO are undefined until they are set as
described above.
4.5. Preventing Oscillations 4.5. Preventing Oscillations
To prevent oscillatory behavior in environments with a low degree of To prevent oscillatory behavior in environments with a low degree of
statistical multiplexing it is useful to modify sender's transmit rate statistical multiplexing it is useful to modify sender's transmit rate
to provide congestion avoidance behavior by reducing the transmit rate to provide congestion avoidance behavior by reducing the transmit rate
as the queuing delay (and hence RTT) increases. To do this the sender as the queuing delay (and hence RTT) increases. To do this the sender
maintains an estimate of the long-term RTT and modifies its sending rate maintains an estimate of the long-term RTT and modifies its sending rate
depending on how the most recent sample of the RTT differs from this depending on how the most recent sample of the RTT differs from this
value. The long-term sample is R_sqmean, and is set as follows: value. The long-term sample is R_sqmean, and is set as follows:
skipping to change at page 13, line 4 skipping to change at page 12, line 49
high, then TFRC may send short bursts of several packets separated by high, then TFRC may send short bursts of several packets separated by
intervals of the OS timer granularity. intervals of the OS timer granularity.
The parameter delta is to allow a degree of flexibility in the send time The parameter delta is to allow a degree of flexibility in the send time
of a packet. If the operating system has a scheduling timer granularity of a packet. If the operating system has a scheduling timer granularity
of t_gran seconds, then delta would typically be set to: of t_gran seconds, then delta would typically be set to:
delta = min(t_ipi/2, t_gran/2); delta = min(t_ipi/2, t_gran/2);
t_gran is 10ms on many Unix systems. If t_gran is not known, a value of t_gran is 10ms on many Unix systems. If t_gran is not known, a value of
10ms can be safely assumed. 10ms can be safely assumed.
5. Calculation of the loss event rate (p) 5. Calculation of the Loss Event Rate (p)
Obtaining a accurate and stable measurement of the loss event rate is of Obtaining a accurate and stable measurement of the loss event rate is of
primary importance for TFRC. Loss rate measurement is performed at the primary importance for TFRC. Loss rate measurement is performed at the
receiver, based on the detection of lost or marked packets from the receiver, based on the detection of lost or marked packets from the
sequence numbers of arriving packets. We describe this process before sequence numbers of arriving packets. We describe this process before
describing the rest of the receiver protocol. describing the rest of the receiver protocol.
5.1. Detection of Lost or Marked Packets 5.1. Detection of Lost or Marked Packets
TFRC assumes that all packets contain a sequence number that is TFRC assumes that all packets contain a sequence number that is
skipping to change at page 14, line 9 skipping to change at page 14, line 4
mechanism here. mechanism here.
For an ECN-capable connection, a marked packet is detected as a For an ECN-capable connection, a marked packet is detected as a
congestion event as soon as it arrives, without having to wait for the congestion event as soon as it arrives, without having to wait for the
arrival of subsequent packets. arrival of subsequent packets.
5.2. Translation from Loss History to Loss Events 5.2. Translation from Loss History to Loss Events
TFRC requires that the loss fraction be robust to several consecutive TFRC requires that the loss fraction be robust to several consecutive
packets lost where those packets are part of the same loss event. This packets lost where those packets are part of the same loss event. This
is similar to TCP, which (typically) only performs one halving of the is similar to TCP, which (typically) only performs one halving of the
congestion window during any single RTT. Thus the receiver needs to map congestion window during any single RTT. Thus the receiver needs to map
the packet loss history into a loss event record, where a loss event is the packet loss history into a loss event record, where a loss event is
one or more packets lost in an RTT. To perform this mapping, the one or more packets lost in an RTT. To perform this mapping, the
receiver needs to know the RTT to use, and this is supplied periodically receiver needs to know the RTT to use, and this is supplied periodically
by the sender, typically as control information piggy-backed onto a data by the sender, typically as control information piggy-backed onto a data
packet. TFRC is not sensitive to how the RTT measurement sent to the packet. TFRC is not sensitive to how the RTT measurement sent to the
receiver is made, but we recommend using the sender's calculated RTT, R, receiver is made, but we recommend using the sender's calculated RTT, R,
(see Section 4.2) for this purpose. (see Section 4.3) for this purpose.
To determine whether a lost or marked packet should start a new loss To determine whether a lost or marked packet should start a new loss
event, or be counted as part of an existing loss event, we need to event, or be counted as part of an existing loss event, we need to
compare the sequence numbers and timestamps of the packets that arrived compare the sequence numbers and timestamps of the packets that arrived
at the receiver. For a marked packet S_new, its reception time T_new at the receiver. For a marked packet S_new, its reception time T_new
can be noted directly. For a lost packet, we can interpolate to infer can be noted directly. For a lost packet, we can interpolate to infer
the nominal "arrival time". Assume: the nominal "arrival time". Assume:
S_loss is the sequence number of a lost packet. S_loss is the sequence number of a lost packet.
skipping to change at page 15, line 49 skipping to change at page 15, line 45
The value n for the number of loss intervals used in calculating the The value n for the number of loss intervals used in calculating the
loss event rate determines TRFC's speed in responding to changes in the loss event rate determines TRFC's speed in responding to changes in the
level of congestion. As currently specified, TFRC should not be used level of congestion. As currently specified, TFRC should not be used
for values of n significantly greater than 8, for traffic that might for values of n significantly greater than 8, for traffic that might
compete in the global Internet with TCP. At the very least, safe compete in the global Internet with TCP. At the very least, safe
operation with values of n greater than 8 would require a slight change operation with values of n greater than 8 would require a slight change
to TFRC's mechanisms to include a more severe response to two or more to TFRC's mechanisms to include a more severe response to two or more
round-trip times with heavy packet loss. round-trip times with heavy packet loss.
To calculate the average loss interval we need to decide whether to When calculating the average loss interval we need to decide whether to
include the interval since the most recent packet loss event. We only include the interval since the most recent packet loss event. We only
do this if it is sufficiently large to increase the average loss do this if it is sufficiently large to increase the average loss
interval. interval.
Thus if the most recent loss intervals are I_0 to I_n, with I_0 being Thus if the most recent loss intervals are I_0 to I_n, with I_0 being
the interval since the most recent loss event, then we calculate the the interval since the most recent loss event, then we calculate the
average loss interval I_mean as: average loss interval I_mean as:
I_tot0 = 0; I_tot0 = 0;
I_tot1 = 0; I_tot1 = 0;
W_tot = 0; W_tot = 0;
for (i = 0 to n-1) { for (i = 0 to n-1) {
skipping to change at page 16, line 31 skipping to change at page 16, line 29
I_tot = max(I_tot0, I_tot1); I_tot = max(I_tot0, I_tot1);
I_mean = I_tot / W_tot; I_mean = I_tot / W_tot;
The loss event rate, p is simply: The loss event rate, p is simply:
p = 1 / I_mean; p = 1 / I_mean;
5.5. History Discounting 5.5. History Discounting
As described in Section 5.4, the most recent loss interval is only As described in Section 5.4, the most recent loss interval is only
assigned 1/(.75n) of the total weight in calculating the average loss assigned 1/(0.75*n) of the total weight in calculating the average loss
interval, regardless of the size of the most recent loss interval. This interval, regardless of the size of the most recent loss interval. This
section describes an optional history discounting mechanism, discussed section describes an optional history discounting mechanism, discussed
further in [2] and [4], that allows the TFRC receiver to adjust the further in [3] and [5], that allows the TFRC receiver to adjust the
weights, concentrating more of the relative weight on the most recent weights, concentrating more of the relative weight on the most recent
loss interval, when the most recent loss interval is more than twice as loss interval, when the most recent loss interval is more than twice as
large as the computed average loss interval. large as the computed average loss interval.
To carry out history discounting, we associate a discount factor DF_i To carry out history discounting, we associate a discount factor DF_i
with each loss interval L_i, for i > 0, where each discount factor is a with each loss interval L_i, for i > 0, where each discount factor is a
floating point number. The discount array maintains the cumulative floating point number. The discount array maintains the cumulative
history of discounting for each loss interval. At the beginning, the history of discounting for each loss interval. At the beginning, the
values of DF_i in the discount array are initialized to 1: values of DF_i in the discount array are initialized to 1:
skipping to change at page 17, line 4 skipping to change at page 16, line 50
history of discounting for each loss interval. At the beginning, the history of discounting for each loss interval. At the beginning, the
values of DF_i in the discount array are initialized to 1: values of DF_i in the discount array are initialized to 1:
for (i = 1 to n) { for (i = 1 to n) {
DF_i = 1; DF_i = 1;
} }
History discounting also uses a general discount factor DF, also a History discounting also uses a general discount factor DF, also a
floating point number, that is also initialized to 1. First we show how floating point number, that is also initialized to 1. First we show how
the discount factors are used in calculating the average loss interval, the discount factors are used in calculating the average loss interval,
and then we describe later in this section how the discount factors are and then we describe later in this section how the discount factors are
modified over time. modified over time.
As described in Section 5.4 the average loss interval is calculated As described in Section 5.4 the average loss interval is calculated
using the n previous loss intervals I_1, ..., I_n, and the interval I_0 using the n previous loss intervals I_1, ..., I_n, and the interval I_0
that represents the number of packets received since last loss event. that represents the number of packets received since the last loss
The computation of the average loss interval using the discount factors event. The computation of the average loss interval using the discount
is a simple modification of the procedure in Section 5.4, as follows: factors is a simple modification of the procedure in Section 5.4, as
follows:
I_tot0 = 0; I_tot0 = I_0 * w_0
I_tot1 = 0; I_tot1 = 0;
W_tot = 0; W_tot0 = w_0
for (i = 0 to n-1) { W_tot1 = 0;
for (i = 1 to n-1) {
I_tot0 = I_tot0 + (I_i * w_i * DF_i * DF); I_tot0 = I_tot0 + (I_i * w_i * DF_i * DF);
W_tot = W_tot + w_i * DF_i * DF; W_tot0 = W_tot0 + w_i * DF_i * DF;
} }
for (i = 1 to n) { for (i = 1 to n) {
I_tot1 = I_tot1 + (I_i * w_(i-1) * DF_i * DF); I_tot1 = I_tot1 + (I_i * w_(i-1) * DF_i);
W_tot1 = W_tot1 + w_(i-1) * DF_i;
} }
p = W_tot / max(I_tot0, I_tot1); p = min(W_tot0/I_tot0, W_tot1/I_tot1);
The general discounting factor, DF is updated on every packet arrival as The general discounting factor, DF is updated on every packet arrival as
follows. First, the receiver computes the weighted average I_tot of the follows. First, the receiver computes the weighted average I_mean of the
loss intervals I_1, ..., I_n: loss intervals I_1, ..., I_n:
I_tot = 0; I_tot = 0;
W_tot = 0;
for (i = 1 to n) { for (i = 1 to n) {
W_tot = w_(i-1) * DF_i;
I_tot = I_tot + (I_i * w_(i-1) * DF_i); I_tot = I_tot + (I_i * w_(i-1) * DF_i);
} }
I_mean = I_tot / W_tot;
This weighted average I_tot is compared against I_0, the number of This weighted average I_mean is compared to I_0, the number of packets
packets received since the last loss event. If I_0 is greater than received since the last loss event. If I_0 is greater than twice
twice I_tot, then the new loss interval is considerably larger than the I_mean, then the new loss interval is considerably larger than the old
old ones, and the general discount factor DF is updated to decrease the ones, and the general discount factor DF is updated to decrease the
relative weight on the older intervals, as follows: relative weight on the older intervals, as follows:
if (I_0 > 2 * I_tot) { if (I_0 > 2 * I_mean) {
DF = 2 * I_tot / I_0; DF = 2 * I_mean/I_0;
if (DF < THRESHOLD) if (DF < THRESHOLD)
DF = THRESHOLD; DF = THRESHOLD;
} else } else
DF = 1; DF = 1;
A nonzero value for THRESHOLD ensures that older loss intervals from an A nonzero value for THRESHOLD ensures that older loss intervals from an
earlier time of high congestion are not discounted entirely. We earlier time of high congestion are not discounted entirely. We
recommend a THRESHOLD of 0.5. Note that with each new packet arrival, recommend a THRESHOLD of 0.5. Note that with each new packet arrival,
I_0 will increase further, and the discount factor DF will be updated. I_0 will increase further, and the discount factor DF will be updated.
When a new loss event occurs, the current interval shifts from I_0 to When a new loss event occurs, the current interval shifts from I_0 to
I_1, loss interval I_i shifts to interval I_(i+1), and the loss interval I_1, loss interval I_i shifts to interval I_(i+1), and the loss interval
I_n is forgotten. The previous discount factor DF has to be I_n is forgotten. The previous discount factor DF has to be
incorporated into the discount array. Because DF_i carries the discount incorporated into the discount array. Because DF_i carries the discount
factor associated with loss interval I_i, the DF_i array has to be factor associated with loss interval I_i, the DF_i array has to be
shifted as well. This is done as follows: shifted as well. This is done as follows:
skipping to change at page 18, line 15 skipping to change at page 18, line 19
When a new loss event occurs, the current interval shifts from I_0 to When a new loss event occurs, the current interval shifts from I_0 to
I_1, loss interval I_i shifts to interval I_(i+1), and the loss interval I_1, loss interval I_i shifts to interval I_(i+1), and the loss interval
I_n is forgotten. The previous discount factor DF has to be I_n is forgotten. The previous discount factor DF has to be
incorporated into the discount array. Because DF_i carries the discount incorporated into the discount array. Because DF_i carries the discount
factor associated with loss interval I_i, the DF_i array has to be factor associated with loss interval I_i, the DF_i array has to be
shifted as well. This is done as follows: shifted as well. This is done as follows:
for (i = 1 to n) { for (i = 1 to n) {
DF_i = DF * DF_i; DF_i = DF * DF_i;
} }
for (i = n-1 to 0) { for (i = n-1 to 0 step -1) {
DF_(i+1) = DF_i; DF_(i+1) = DF_i;
} }
I_0 = 1; I_0 = 1;
DF_0 = 1; DF_0 = 1;
DF = 1; DF = 1;
This completes the description of the optional history discounting This completes the description of the optional history discounting
mechanism. We emphasize that this is an optional mechanism whose sole mechanism. We emphasize that this is an optional mechanism whose sole
purpose is to allow TFRC to response somewhat more quickly to the sudden purpose is to allow TFRC to response somewhat more quickly to the sudden
absence of congestion, as represented by a long current loss interval. absence of congestion, as represented by a long current loss interval.
skipping to change at page 19, line 33 skipping to change at page 19, line 40
feedback was sent. feedback was sent.
Let the maximum sequence number of a packet at the receiver so far be Let the maximum sequence number of a packet at the receiver so far be
S_m, and the value of the RTT measurement included in packet S_m be R_m. S_m, and the value of the RTT measurement included in packet S_m be R_m.
If data packets have been received since the pervious feedback was sent, If data packets have been received since the pervious feedback was sent,
the receiver performs the following steps: the receiver performs the following steps:
1) Calculate the average loss event rate using the algorithm described 1) Calculate the average loss event rate using the algorithm described
above. above.
2) Calculate the measured receive rate, X_sample, based on the packets 2) Calculate the measured receive rate, X_recv, based on the packets
received within the previous R_m seconds. received within the previous R_m seconds.
3) Calculate X_recv as follows: 3) Prepare and send a feedback packet containing the information
X_recv = q3*X_sample + (1-q3)*X_recv;
Where q3 is a constant with recommended value 0.5.
4) Prepare and send a feedback packet containing the information
described in Section 3.2.2 described in Section 3.2.2
5) Restart the feedback timer to expire after R_m seconds. 4) Restart the feedback timer to expire after R_m seconds.
If no data packets have been received since the last feedback was sent, If no data packets have been received since the last feedback was sent,
no feedback packet is sent, and the feedback timer is restarted to no feedback packet is sent, and the feedback timer is restarted to
expire after R_m seconds. expire after R_m seconds.
6.3. Receiver initialization 6.3. Receiver initialization
The receiver is initialized by the first packet that arrives at the The receiver is initialized by the first packet that arrives at the
receiver. Let the sequence number of this packet be i. receiver. Let the sequence number of this packet be i.
skipping to change at page 20, line 21 skipping to change at page 20, line 21
o Set p=0 o Set p=0
o Set X_recv = X_send, where X_send is the sending rate the sender o Set X_recv = X_send, where X_send is the sending rate the sender
reports in the first data packet. reports in the first data packet.
o Prepare and send a feedback packet. o Prepare and send a feedback packet.
o Set the feedback timer to expire after R_i seconds. o Set the feedback timer to expire after R_i seconds.
6.3.1. Initializing the Loss History after the First Loss Event
The number of packets until the first loss can not be used to compute
the sending rate directly, as the sending rate changes rapidly during
this time. TFRC assumes that the correct data rate after the first loss
is half of the sending rate when the loss occurred. TFRC approximates
this target rate by X_recv, the receive rate over the most recent round-
trip time. After the first loss, instead of initializing the first loss
interval to the number of packets sent until the first loss, the TFRC
receiver calculates the loss interval that would be required to produce
the data rate X_recv, and uses this synthetic loss interval to seed the
loss history mechanism.
TFRC does this by finding some value p for which the throughput equation
in Section 3.1 gives a sending rate within 5% of X_recv, given the
current packet size s and round-trip time R. The first loss interval is
then set to 1/p. (The 5% tolerance is introduced simply because the
throughput equation is difficult to invert, and we want to reduce the
costs of calculating p numerically.)
7. Security Considerations 7. Security Considerations
TFRC is not a transport protocol in its own right, but a congestion TFRC is not a transport protocol in its own right, but a congestion
control mechanism that is intended to be used in conjunction with a control mechanism that is intended to be used in conjunction with a
transport protocol. Therefore security primarily needs to be considered transport protocol. Therefore security primarily needs to be considered
in the context of a specific transport protocol and its authentication in the context of a specific transport protocol and its authentication
mechanisms. mechanisms.
Congestion control mechanisms can potentially be exploited to create Congestion control mechanisms can potentially be exploited to create
denial of service. This may occur through spoofed feedback. Thus any denial of service. This may occur through spoofed feedback. Thus any
skipping to change at page 20, line 46 skipping to change at page 21, line 22
In addition, congestion control mechanisms may potentially be In addition, congestion control mechanisms may potentially be
manipulated by a greedy receiver that wishes to receive more than its manipulated by a greedy receiver that wishes to receive more than its
fair share of network bandwidth. A receiver might do this by claiming fair share of network bandwidth. A receiver might do this by claiming
to have received packets that in fact were lost due to congestion. to have received packets that in fact were lost due to congestion.
Possible defenses against such a receiver would normally include some Possible defenses against such a receiver would normally include some
form of nonce that the receiver must feed back to the sender to prove form of nonce that the receiver must feed back to the sender to prove
receipt. However, the details of such a nonce would depend on the receipt. However, the details of such a nonce would depend on the
transport protocol, and in particular on whether the transport protocol transport protocol, and in particular on whether the transport protocol
is reliable or unreliable. is reliable or unreliable.
We expect that protocols incorporating ECN with TFRC will also want to
incorporate feedback from the receiver to the sender using the ECN nonce
[WES01]. The ECN nonce is a modification to ECN that protects the
sender from the accidental or malicious concealment of marked packets.
Again, the details of such a nonce would depend on the transport
protocol, and are not addressed in this document.
8. Authors' Addresses 8. Authors' Addresses
Mark Handley, Jitendra Padhye, Sally Floyd Mark Handley, Jitendra Padhye, Sally Floyd
ACIRI/ICSI ACIRI/ICSI
1947 Center St, Suite 600 1947 Center St, Suite 600
Berkeley, CA 94708 Berkeley, CA 94708
mjh@aciri.org, padhye@aciri.org, floyd@aciri.org mjh@aciri.org, padhye@aciri.org, floyd@aciri.org
Joerg Widmer Joerg Widmer
Lehrstuhl Praktische Informatik IV Lehrstuhl Praktische Informatik IV
Universitat Mannheim Universitat Mannheim
L 15, 16 - Room 415 L 15, 16 - Room 415
skipping to change at page 21, line 23 skipping to change at page 22, line 4
L 15, 16 - Room 415 L 15, 16 - Room 415
D-68131 Mannheim D-68131 Mannheim
Germany Germany
widmer@informatik.uni-mannheim.de widmer@informatik.uni-mannheim.de
9. Acknowledgments 9. Acknowledgments
We would like to acknowledge feedback and discussions on equation-based We would like to acknowledge feedback and discussions on equation-based
congestion control with a wide range of people, including members of the congestion control with a wide range of people, including members of the
Reliable Multicast Research Group, the Reliable Multicast Transport Reliable Multicast Research Group, the Reliable Multicast Transport
Working Group, and the End-to-End Research Group. We would like to Working Group, and the End-to-End Research Group. We would like to
thank Eduardo Urzaiz and Shushan Wen for feedback on earlier versions of thank Eduardo Urzaiz, Vladica Stanisic, and Shushan Wen for feedback on
this document, and to thank Mark Allman for his extensive feedback from earlier versions of this document, and to thank Mark Allman for his
using the draft to produce a working implementation. extensive feedback from using the draft to produce a working
implementation.
10. References 10. References
[1] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based [1] Balakrishnan, H., Rahul, H., and Seshan, S., "An Integrated
Congestion Management Architecture for Internet Hosts," Proc. ACM
SIGCOMM, Cambridge, MA, September 1999.
[2] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based
Congestion Control for Unicast Applications", August 2000, Proc Congestion Control for Unicast Applications", August 2000, Proc
SIGCOMM 2000. SIGCOMM 2000.
[2] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based [3] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based
Congestion Control for Unicast Applications: the Extended Version", Congestion Control for Unicast Applications: the Extended Version",
ICSI tech report TR-00-03, March 2000. ICSI tech report TR-00-03, March 2000.
[3] Padhye, J. and Firoiu, V. and Towsley, D. and Kurose, J., "Modeling [4] Padhye, J. and Firoiu, V. and Towsley, D. and Kurose, J., "Modeling
TCP Throughput: A Simple Model and its Empirical Validation", Proc TCP Throughput: A Simple Model and its Empirical Validation", Proc
ACM SIGCOMM 1998. ACM SIGCOMM 1998.
[4] Widmer, J., Equation-Based Congestion Control, Diploma Thesis, [5] Widmer, J., "Equation-Based Congestion Control", Diploma Thesis,
University of Mannheim, February 2000. URL University of Mannheim, February 2000. URL
"http://www.aciri.org/tfrc/". "http://www.aciri.org/tfrc/".
[5] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, RTP: A [6] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: A
Transport Protocol for Real-Time Applications, RFC 1889, January Transport Protocol for Real-Time Applications", RFC 1889, January
1996. 1996.
[6] K. Ramakrishnan and S. Floyd, A Proposal to add Explicit Congestion [7] K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit Congestion
Notification (ECN) to IP, RFC 2481, January 1999. Notification (ECN) to IP", RFC 2481, January 1999.
[7] V. Paxson and M. Allman, Computing TCP's Retransmission Timer, RFC [8] V. Paxson and M. Allman, "Computing TCP's Retransmission Timer", RFC
2988, November 2000. 2988, November 2000.
[9] Wetherall, D., Ely, D., and Spring, N., "Robust ECN Signaling with
Nonces", draft-ietf-tsvwg-tcp-nonce-00.txt, internet draft, work in
progress, January 2001. Citation for informational purposes only.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/