requirement for three subsequent packets is the same as with TCP, and
it is to make TFMCC more robust in the presence of reordering. In
contrast to TCP, if a packet arrives late (after 3 subsequent packets
arrived) at a receiver, the late packet can fill the hole in the
reception record, and the receiver can recalculate the loss event
rate. Future versions of TFMCC might make the requirement for three
subsequent packets adaptive based on experienced packet reordering,
but we do not specify such a mechanism here.
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 arrival of subsequent packets.
5.2. Translation from Loss History to Loss Events
TFMCC requires that the loss event rate be robust to several
consecutive 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 congestion window during any single RTT. Thus the
receivers need to map the packet loss history into a loss event
record, where a loss event is one or more packets lost in an RTT.
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
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 can be noted directly. For a lost packet, we can
interpolate to infer the nominal "arrival time". Assume:
S_loss is the sequence number of a lost packet.
S_before is the sequence number of the last packet to arrive with
sequence number before S_loss.
S_after is the sequence number of the first packet to arrive with
sequence number after S_loss.
T_before is the reception time of S_before.
T_after is the reception time of S_after.
Note that T_before can be either before or after T_after due to
reordering.
For a lost packet S_loss, we can interpolate its nominal "arrival
time" at the receiver from the arrival times of S_before and S_after.
Thus
T_loss = T_before + ( (T_after - T_before)
* (S_loss - S_before)/(S_after - S_before) );
Note that if the sequence space wrapped between S_before and S_after,
the sequence numbers must be modified to take this into account
before the calculation is performed. If the largest possible
sequence number is S_max, and S_before > S_after, then modifying each
sequence number S by S’ = (S + (S_max + 1)/2) mod (S_max + 1) would
normally be sufficient.
If the lost packet S_old was determined to have started the previous
loss event, and if we have just determined that S_new has been lost,
then we interpolate the nominal arrival times of S_old and S_new,
called T_old and T_new, respectively.
If T_old + R >= T_new, then S_new is part of the existing loss event.
Otherwise, S_new is the first packet of a new loss event.
5.3. Inter-Loss Event Interval
If a loss interval, A, is determined to have started with packet
sequence number S_A and the next loss interval, B, started with
packet sequence number S_B, then the number of packets in loss
interval A is given by (S_B - S_A).
5.4. Average Loss Interval
To calculate the loss event rate p, we first calculate the average
loss interval. This is done using a filter that weights the n most
recent loss event intervals in such a way that the measured loss
event rate changes smoothly.
Weights w_0 to w_(n-1) are calculated as:
If (i < n/2)
w_i = 1;
Else
w_i = 1 - (i - (n/2 - 1))/(n/2 + 1);
Thus if n=8, the values of w_0 to w_7 are:
1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2
The value n for the number of loss intervals used in calculating the
loss event rate determines TFMCC’s speed in responding to changes in
the level of congestion. As currently specified, TFMCC should not be
used for values of n significantly greater than 8, for traffic that
might 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 to TFMCC’s mechanisms to include a more severe response to two
or more round-trip times with heavy packet loss.
When calculating the average loss interval, we need to decide whether
to include the interval since the most recent packet loss event. We
only do this if it is sufficiently large to increase the average loss
interval.
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 average loss interval I_mean as:
I_tot0 = 0;
I_tot1 = 0;
W_tot = 0;
for (i = 0 to n-1) {
I_tot0 = I_tot0 + (I_i * w_i);
W_tot = W_tot + w_i;
}
for (i = 1 to n) {
I_tot1 = I_tot1 + (I_i * w_(i-1));
}
I_tot = max(I_tot0, I_tot1);
I_mean = I_tot/W_tot;
The loss event rate, p is simply:
p = 1 / I_mean;
5.5. History Discounting
As described in Section 5.4, the most recent loss interval is only
assigned 4/(3*n) of the total weight in calculating the average loss
interval, regardless of the size of the most recent loss interval.
This section describes an optional history discounting mechanism that
allows the TFMCC receivers to adjust the weights, concentrating more
of the relative weight on the most recent loss interval, when the
most recent loss interval is more than twice as large as the computed
average loss interval.
To carry out history discounting, we associate a discount factor DF_i
with each loss interval L_i, where each discount factor is a floating
point number. The discount array maintains the cumulative history of
discounting for each loss interval. At the beginning, the values of
DF_i in the discount array are initialized to 1:
for (i = 0 to n) {
DF_i = 1;
}
History discounting also uses a general discount factor DF, also a
floating point number, that is also initialized to 1. First, we show
how the discount factors are used in calculating the average loss
interval, and then we describe later in this section how the discount
factors are modified over time.
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 that represents the number of packets received since the last
loss event. The computation of the average loss interval using the
discount factors is a simple modification of the procedure in Section
5.4, as follows:
I_tot0 = I_0 * w_0
I_tot1 = 0;
W_tot0 = w_0
W_tot1 = 0;
for (i = 1 to n-1) {
I_tot0 = I_tot0 + (I_i * w_i * DF_i * DF);
W_tot0 = W_tot0 + w_i * DF_i * DF;
}
for (i = 1 to n) {
I_tot1 = I_tot1 + (I_i * w_(i-1) * DF_i);
W_tot1 = W_tot1 + w_(i-1) * DF_i;
}
p = min(W_tot0/I_tot0, W_tot1/I_tot1);
The general discounting factor DF is updated on every packet arrival
as follows. First, a receiver computes the weighted average I_mean
of the loss intervals I_1, ..., I_n:
I_tot = 0;
W_tot = 0;
for (i = 1 to n) {
W_tot = 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_mean is compared to I_0, the number of
packets received since the last loss event. If I_0 is greater than
twice I_mean, then the new loss interval is considerably larger than
the old ones, and the general discount factor DF is updated to
decrease the relative weight on the older intervals, as follows:
if (I_0 > 2 * I_mean) {
DF = 2 * I_mean/I_0;
if (DF < THRESHOLD)
DF = THRESHOLD;
} else
DF = 1;
A nonzero value for THRESHOLD ensures that older loss intervals from
an earlier time of high congestion are not discounted entirely. We
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.
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_n is forgotten. The previous discount factor DF has to be
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 shifted as well. This is done as follows:
for (i = 1 to n) {
DF_i = DF * DF_i;
}
for (i = n-1 to 0 step -1) {
DF_(i+1) = DF_i;
}
I_0 = 1;
DF_0 = 1;
DF = 1;
This completes the description of the optional history discounting
mechanism. We emphasize that this is an optional mechanism whose
sole purpose is to allow TFMCC to respond more quickly to the sudden
absence of congestion, as represented by a long current loss
interval.
5.6. Initializing the Loss History after the First Loss Event
The number of packets received before the first loss event usually
does not reflect the current loss event rate. When the first loss
event occurs, a TFMCC receiver assumes that the correct data rate is
the rate at which data was received during the last RTT when the loss
occurred. Instead of initializing the first loss interval to the
number of packets sent until the first loss event, the TFMCC receiver
calculates the loss interval that would be required to produce the
receive rate X_recv, and it uses this synthetic loss interval l_0 to
seed the loss history mechanism.
The initial loss interval is calculated by inverting a simplified
version of the TCP Equation (1).
8s
X_recv = sqrt(3/2) * -----------------
R * sqrt(1/l_0)
X_recv * R
==> l_0 = (----------------)^2
sqrt(3/2) * 8s
The resulting initial loss interval is too small at higher loss rates
compared to using the more accurate Equation (1), which leads to a
more conservative initial loss event rate.
If a receiver still uses the initial RTT R_max instead of its real
RTT, the initial loss interval is too large in case the initial RTT
is higher than the actual RTT. As a consequence, the receiver will
calculate too high a desired rate when the first RTT measurement R is
made and the initial loss interval is still in the loss history. The
receiver has to adjust l_0 as follows:
l_0 = l_0 * (R/R_max)^2
No action needs to be taken when the first RTT measurement is made
after the initial loss interval left the loss history.
6. Security Considerations
TFMCC is not a transport protocol in its own right, but a congestion
control mechanism that is intended to be used in conjunction with a
transport protocol. Therefore, security primarily needs to be
considered in the context of a specific transport protocol and its
authentication mechanisms.
Congestion control mechanisms can potentially be exploited to create
denial of service. This may occur through spoofed feedback. Thus,
any transport protocol that uses TFMCC should take care to ensure
that feedback is only accepted from valid receivers of the data.
However, the precise mechanism to achieve this will depend on the
transport protocol itself.
Congestion control mechanisms may potentially be manipulated by a
greedy receiver that wishes to receive more than its fair share of
network bandwidth. However, in TFMCC a receiver can only influence
the sending rate if it is the CLR and thus has the lowest calculated
rate of all receivers. If the calculated rate is then manipulated
such that it exceeds the calculated rate of the second to lowest
receiver, it will cease to be CLR. A greedy receiver can only
significantly increase the transmission rate if it is the only
participant in the session. If such scenarios are of concern,
possible defenses against such a receiver would normally include some
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
transport protocol and, in particular, on whether the transport
protocol is reliable or unreliable.
It is possible that a receiver sends feedback claiming that it has a
very low calculated rate. This will reduce the rate of the multicast
session and might render it useless but obviously cannot hurt the
network itself.
We expect that protocols incorporating ECN with TFMCC will also want
to incorporate feedback from the receiver to the sender using the ECN
nonce [12]. 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.
7. Acknowledgments
We would like to acknowledge feedback and discussions on equation-
based congestion control with a wide range of people, including
members of the Reliable Multicast Research Group, the Reliable
Multicast Transport Working Group, and the End-to-End Research Group.
We would particularly like to thank Brian Adamson, Mark Pullen, Fei
Zhao, and Magnus Westerlund for feedback on earlier versions of this
document.
8. References
8.1. Normative References
[1] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S.,
and M. Luby, "Reliable Multicast Transport Building Blocks for
One-to-Many Bulk-Data Transfer", RFC 3048, January 2001.
[2] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable
Multicast Transport (RMT) Building Blocks and Protocol
Instantiation documents", RFC 3269, April 2002.
8.2. Informative References
[3] J. Widmer and M. Handley, "Extending Equation-Based Congestion
Control to Multicast Applications", Proc ACM Sigcomm 2001, San
Diego, August 2001.
[4] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based
Congestion Control for Unicast Applications", Proc ACM SIGCOMM
2000, Stockholm, August 2000.
[5] Adamson, B., Bormann, C., Handley, M., and J. Macker,
"Negative-Acknowledgment (NACK)-Oriented Reliable Multicast
(NORM) Building Blocks", RFC 3941, November 2004.
[6] Deering, S., "Host extensions for IP multicasting", STD 5, RFC
1112, August 1989.
[7] H. W. Holbrook, "A Channel Model for Multicast," Ph.D.
Dissertation, Stanford University, Department of Computer
Science, Stanford, California, August 2001.
[8] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, "Modeling TCP
Throughput: A Simple Model and its Empirical Validation", Proc
ACM SIGCOMM 1998.
[9] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition of
Explicit Congestion Notification (ECN) to IP", RFC 3168,
September 2001.
[10] L. Rizzo, "pgmcc: a TCP-friendly single-rate multicast
congestion control scheme", Proc ACM Sigcomm 2000, Stockholm,
August 2000.
[11] Schulzrinne, H., Casner, S., Frederick, R., and V. Jacobson,
"RTP: A Transport Protocol for Real-Time Applications", STD 64,
RFC 3550, July 2003.
[12] Spring, N., Wetherall, D., and D. Ely, "Robust Explicit
Congestion Notification (ECN) Signaling with Nonces", RFC 3540,
June 2003.
[13] J. Widmer and T. Fuhrmann, "Extremum Feedback for Very Large
Multicast Groups", Proc NGC 2001, London, November 2001.
Authors’ Addresses
Joerg Widmer
DoCoMo Euro-Labs
Landsberger Str. 312, Munich, Germany
EMail: widmer@acm.org
Mark Handley
UCL (University College London)
Gower Street, London WC1E 6BT, UK
EMail: m.handley@cs.ucl.ac.uk
Full Copyright Statement
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM 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.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).