--- 1/draft-ietf-tsvwg-tfrc-04.txt 2006-02-05 01:46:47.000000000 +0100 +++ 2/draft-ietf-tsvwg-tfrc-05.txt 2006-02-05 01:46:47.000000000 +0100 @@ -1,26 +1,25 @@ Internet Engineering Task Force TSV WG INTERNET-DRAFT Mark Handley/ICIR -draft-ietf-tsvwg-tfrc-04.txt Jitendra Padhye/ICIR +draft-ietf-tsvwg-tfrc-05.txt Jitendra Padhye/Microsoft Sally Floyd/ICIR - Joerg Widmer/Univ. Mannheim - 27 April 2002 - Expires: October 2002 + 22 October 2002 + Expires: April 2003 TCP Friendly Rate Control (TFRC): Protocol Specification Status of this Document -This document is an Internet-Draft and is in full conformance with all -provisions of Section 10 of RFC2026. +This document is an Internet-Draft and is subject to all provisions of +Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." @@ -41,53 +40,85 @@ reasonably fair when competing for bandwidth with TCP flows, but has a much lower variation of throughput over time compared with TCP, making it more suitable for applications such as telephony or streaming media where a relatively smooth sending rate is of importance. Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 5 - 3. Protocol Mechanism. . . . . . . . . . . . . . . . . . . 5 + 3. Protocol Mechanism. . . . . . . . . . . . . . . . . . . 6 3.1. TCP Throughput Equation. . . . . . . . . . . . . . . 6 - 3.2. Packet Contents. . . . . . . . . . . . . . . . . . . 7 - 3.2.1. Data Packets. . . . . . . . . . . . . . . . . . . 7 - 3.2.2. Feedback Packets. . . . . . . . . . . . . . . . . 8 - 4. Data Sender Protocol. . . . . . . . . . . . . . . . . . 8 - 4.1. Measuring the Packet Size. . . . . . . . . . . . . . 9 - 4.2. Sender Initialization. . . . . . . . . . . . . . . . 9 + 3.2. Packet Contents. . . . . . . . . . . . . . . . . . . 8 + 3.2.1. Data Packets. . . . . . . . . . . . . . . . . . . 8 + 3.2.2. Feedback Packets. . . . . . . . . . . . . . . . . 9 + 4. Data Sender Protocol. . . . . . . . . . . . . . . . . . 9 + 4.1. Measuring the Packet Size. . . . . . . . . . . . . . 10 + 4.2. Sender Initialization. . . . . . . . . . . . . . . . 10 4.3. Sender behavior when a feedback packet is received. . . . . . . . . . . . . . . . . . . . . . . . . 10 4.4. Expiration of nofeedback timer . . . . . . . . . . . 11 - 4.5. Preventing Oscillations. . . . . . . . . . . . . . . 11 - 4.6. Scheduling of Packet Transmissions . . . . . . . . . 12 - 5. Calculation of the Loss Event Rate (p). . . . . . . . . 13 - 5.1. Detection of Lost or Marked Packets. . . . . . . . . 13 - 5.2. Translation from Loss History to Loss Events . . . . 14 - 5.3. Inter-loss Event Interval. . . . . . . . . . . . . . 15 - 5.4. Average Loss Interval. . . . . . . . . . . . . . . . 15 + 4.5. Preventing Oscillations. . . . . . . . . . . . . . . 12 + 4.6. Scheduling of Packet Transmissions . . . . . . . . . 13 + 5. Calculation of the Loss Event Rate (p). . . . . . . . . 14 + 5.1. Detection of Lost or Marked Packets. . . . . . . . . 14 + 5.2. Translation from Loss History to Loss Events . . . . 15 + 5.3. Inter-loss Event Interval. . . . . . . . . . . . . . 16 + 5.4. Average Loss Interval. . . . . . . . . . . . . . . . 16 5.5. History Discounting. . . . . . . . . . . . . . . . . 17 - 6. Data Receiver Protocol. . . . . . . . . . . . . . . . . 19 + 6. Data Receiver Protocol. . . . . . . . . . . . . . . . . 20 6.1. Receiver behavior when a data packet is - received. . . . . . . . . . . . . . . . . . . . . . . . . 19 + received. . . . . . . . . . . . . . . . . . . . . . . . . 20 6.2. Expiration of feedback timer . . . . . . . . . . . . 20 - 6.3. Receiver initialization. . . . . . . . . . . . . . . 20 + 6.3. Receiver initialization. . . . . . . . . . . . . . . 21 6.3.1. Initializing the Loss History after the First Loss Event . . . . . . . . . . . . . . . . . . . . 21 - 7. Security Considerations . . . . . . . . . . . . . . . . 21 - 8. IANA Considerations . . . . . . . . . . . . . . . . . . 22 - 9. Authors' Addresses. . . . . . . . . . . . . . . . . . . 22 - 10. Acknowledgments. . . . . . . . . . . . . . . . . . . . 22 - 11. References . . . . . . . . . . . . . . . . . . . . . . 22 + 7. Sender-based Variants . . . . . . . . . . . . . . . . . 22 + 8. Implementation Issues . . . . . . . . . . . . . . . . . 22 + 9. Security Considerations . . . . . . . . . . . . . . . . 23 + 10. IANA Considerations. . . . . . . . . . . . . . . . . . 24 + 11. Authors' Addresses . . . . . . . . . . . . . . . . . . 24 + 12. Acknowledgments. . . . . . . . . . . . . . . . . . . . 25 + 13. Normative References . . . . . . . . . . . . . . . . . 25 + 14. Non-normative References . . . . . . . . . . . . . . . 25 NOTE TO RFC EDITOR: PLEASE DELETE THIS NOTE UPON PUBLICATION. +Changes from draft-ietf-tsvwg-tfrc-04.txt: +* In Section 4.3, changed a variable name from RTT to R, for +consistency. + +* In Section 4.4, made one change for clarity: Changed: +"Cut the sending rate in half. This is done by..." +to: + +"Cut the sending rate in half. If the sender has received feedback from +the receiver, this is done by..." + +* In Section 4.4, made one change for correctness: +Changed: +"when the sender ... has not yet received any feedback from the sender," +to: +"when the sender ... has not yet received any feedback from the +receiver," +Thanks to Mike Luby for these reports. + +* Added a section about implementation-related issues. + +* Made the following changes in response to feedback from the IESG: + +* Changed the 64-seconds term in equations to "t_mbi", which is +explained as representing 64 seconds. This is to make it clear that +this term is in units of seconds. + +* Added a section about a sender-based variant of TFRC. + Changes from draft-ietf-tsvwg-tfrc-03.txt: * Changed one line in the computation of the weighted average I_mean of the loss intervals from: W_tot = w_(i-1) * DF_i; to: W_tot = W_tot + w_(i-1) * DF_i; Bug report from Wendy Lee. * Removed the specification that the sender sends its current transmit rate. This was only used to initialize X_recv, and is not needed. @@ -98,24 +129,26 @@ send the timestamp back to the sender. END OF NOTE TO RFC EDITOR. 1. Introduction This document specifies TCP-Friendly Rate Control (TFRC). TFRC is a congestion control mechanism designed for unicast flows operating in a Internet environment and competing with TCP traffic [2]. Instead of specifying a complete protocol, this document simply specifies a congestion control mechanism that could be used in a transport protocol -such as RTP [6], in an application incorporating end-to-end congestion +such as RTP [7], in an application incorporating end-to-end congestion control at the application level, or in the context of endpoint -congestion management [BRS99]. This document does not discuss packet -formats, reliability, or implementation-related issues. +congestion management [1]. This document does not discuss packet formats + +or reliability. Implementation-related issues are discussed only +briefly, in Section 8. TFRC is designed to be reasonably fair when competing for bandwidth with TCP flows, where a flow is ``reasonably fair'' if its sending rate is generally within a factor of two of the sending rate of a TCP flow under the same conditions. However TFRC has a much lower variation of throughput over time compared with TCP, which makes it more suitable for applications such as telephony or streaming media where a relatively smooth sending rate is of importance. The penalty of having smoother throughput than TCP while competing @@ -156,21 +188,21 @@ 3. Protocol Mechanism For its congestion control mechanism, TFRC directly uses a throughput 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 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 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 congestion -indication from Explicit Congestion Notification (ECN) [7]. +indication from Explicit Congestion Notification (ECN) [6]. Generally speaking, TFRC's congestion control mechanism works as follows: o The receiver measures the loss event rate and feeds this information back to the sender. o The sender also uses these feedback messages to measure the round- trip time (RTT). @@ -224,24 +257,23 @@ events as a fraction of the number of packets transmitted. t_RTO is the TCP retransmission timeout value in seconds. b is the number of packets acknowledged by a single TCP acknowledgement. We further simplify this by setting t_RTO = 4*R. A more accurate calculation of t_RTO is possible, but experiments with the current setting have resulted in reasonable fairness with existing TCP - -implementations [5]. Another possibility would be to set t_RTO = max(4R, +implementations [9]. Another possibility would be to set t_RTO = max(4R, one second), to match the recommended minimum of one second on the RTO -[8]. +[5]. Many current TCP connections use delayed acknowledgements, sending an 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 acknowledgement for every data packet, and this would be modeled by b = 1. Because many TCP implementations do not use delayed acknowledgements, we recommend b = 1. In future, different TCP equations may be substituted for this equation. The requirement is that the throughput equation be a reasonable @@ -393,63 +424,67 @@ q, but we recommend a default value of 0.9. 3) Update the timeout interval: t_RTO = 4*R. 4) Update the sending rate as follows: If (p > 0) Calculate X_calc using the TCP throughput equation. - X = max(min(X_calc, 2*X_recv), s/64); + X = max(min(X_calc, 2*X_recv), s/t_mbi); Else - If (t_now - tld >= RTT) - X = max(min(2*X, 2*X_recv), s/RTT); + If (t_now - tld >= R) + X = max(min(2*X, 2*X_recv), s/R); tld = t_now; Note that if p == 0, then the sender is in slow-start phase, where it approximately doubles the sending rate each round- - trip time until a loss occurs. The s/RTT term gives a minimum - sending rate during slow-start of one packet per RTT. When p - > 0, the sender sends at least one packet every 64 seconds. + trip time until a loss occurs. The s/R term gives a minimum + sending rate during slow-start of one packet per RTT. The + parameter t_mbi is 64 seconds, and represents the maximum + inter-packet backoff interval in the persistent absense of + feedback. Thus, when p > 0 the sender sends at least one + packet every 64 seconds. 5) Reset the nofeedback timer to expire after max(4*R, 2*s/X) seconds. 4.4. Expiration of nofeedback timer If the nofeedback timer expires, the sender should perform the following actions: -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 - sending rate is limited to at most twice X_recv, modifying X_recv - limits the current sending rate, but allows the sender to slow- - start, doubling its sending rate each RTT, if feedback messages - resume reporting no losses. +1) Cut the sending rate in half. If the sender has received feedback + from the receiver, this is done by modifying 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 limits the + current sending rate, but allows the sender to slow-start, doubling + its sending rate each RTT, if feedback messages resume reporting no + losses. If (X_calc > 2*X_recv) - X_recv = max(X_recv/2, s/128); + X_recv = max(X_recv/2, s/(2*t_mbi)); Else X_recv = X_calc/4; - The s/128 term limits the backoff to one packet every 64 seconds in - the case of persistent absence of feedback. + The term s/(2*t_mbi) limits the backoff to one packet every 64 + seconds in the case of persistent absence of feedback. 2) The value of X must then be recalculated as described under point (4) above. If the nofeedback timer expires when the sender does not yet have 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 + receiver, then step (1) can be skipped, and the sending rate cut in half directly: - X = max(X/2, s/64) + X = max(X/2, s/t_mbi) 3) Restart the nofeedback timer to expire after max(4*R, 2*s/X) seconds. Note that when the sender stops sending, the receiver will stop sending feedback. This will cause the nofeedback timer to start to expire and decrease X_recv. If the sender subsequently starts to send again, X_recv will limit the transmit rate, and a normal slowstart phase will occur until the transmit rate reaches X_calc. @@ -690,21 +723,21 @@ 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 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 section describes an optional history discounting mechanism, discussed -further in [3] and [5], that allows the TFRC receiver to adjust the +further in [3] and [9], that allows the TFRC receiver 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, for i > 0, 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: @@ -884,21 +920,92 @@ 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. Sender-based Variants + +It would be possible to implement a sender-based variant of TFRC, where +the receiver uses reliable delivery to send information about packet +losses to the sender, and the sender computes the packet loss rate and +the acceptable transmit rate. However, we do not specify the details of +a sender-based variant in this document. + +The main advantages of a sender-based variant of TFRC would be that the +sender would not have to trust the receiver's calculation of the packet +loss rate. However, with the requirement of reliable delivery of loss +information from the receiver to the sender, a sender-based TFRC would +have much tighter constraints on the transport protocol in which it is +embedded. + +In contrast, the receiver-based variant of TFRC specified in this +document is robust to the loss of feedback packets, and therefore does +not require the reliable delivery of feedback packets. It is also +better suited for applications such as streaming media from web servers, +where it is typically desirable to offload work from the server to the +client as much as possible. + +The sender-based and receiver-based variants also have different +properties in terms of upgrades. For example, for changes in the +procedure for calculating the packet loss rate, the sender would have to +be upgraded in the sender-based variant, and the receiver would have to +be upgraded in the receiver-based variant. + +8. Implementation Issues + +This document has specified the TFRC congestion control mechanism, for +use by applications and transport protocols. This section mentions +briefly some of the few implementation issues. + +For t_RTO = 4*R and b = 1, the throughput equation in Section 3.1 can be +expressed as follows: + + s + X = -------- + R * f(p) + + for + + f(p) = sqrt(2*p/3) + (12*sqrt(3*p/8) * p * (1+32*p^2)). + + A table lookup could be used for the function f(p). + +Many of the multiplications (e.g., q and 1-q for the round-trip time +average, a factor of 4 for the timeout interval) are or could be by +powers of two, and therefore could be implemented as simple shift +operations. + +We note that the optional sender mechanism for preventing oscillations +described in Section 4.5 uses a square-root computation. + +The calculation of the average loss interval in Section 5.4 involves +multiplications by the weights w_0 to w_(n-1), which for n=8 are: + + 1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2. + +With a minor loss of smoothness, it would be possible to use weights +that were powers of two or sums of powers of two, e.g., + + 1.0, 1.0, 1.0, 1.0, 0.75, 0.5, 0.25, 0.25. + +The optional history discounting mechanism described in Section 5.5 is +used in the calculation of the average loss rate. The history +discounting mechanism is invoked only when there has been an unusually +long interval with no packet losses. For a more efficient operation, +the discount factor DF_i could be restricted to be a power of two. + +9. Security Considerations 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 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 TFRC should take care to ensure that @@ -911,82 +1018,87 @@ fair share of network bandwidth. A receiver might do this by claiming to have received packets that in fact were lost due to congestion. 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. 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 +[WES02]. 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. IANA Considerations +10. IANA Considerations There are no IANA actions required for this document. -9. Authors' Addresses - - Mark Handley, Jitendra Padhye, Sally Floyd +11. Authors' Addresses + Mark Handley, Sally Floyd ICIR/ICSI 1947 Center St, Suite 600 Berkeley, CA 94708 - mjh@icir.org, padhye@icir.org, floyd@icir.org + mjh@icir.org, floyd@icir.org + + Jitendra Padhye + Microsoft Research + padhye@microsoft.com Joerg Widmer Lehrstuhl Praktische Informatik IV Universitat Mannheim L 15, 16 - Room 415 D-68131 Mannheim Germany widmer@informatik.uni-mannheim.de -10. Acknowledgments +12. 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 like to -thank Ken Lofgren, Eduardo Urzaiz, Vladica Stanisic, Shushan Wen, and -Wendy Lee (lhh@zsu.edu.cn) for feedback on earlier versions of this -document, and to thank Mark Allman for his extensive feedback from using -the draft to produce a working implementation. +thank Ken Lofgren, Mike Luby, Eduardo Urzaiz, Vladica Stanisic, Randall +Stewart, Shushan Wen, and Wendy Lee (lhh@zsu.edu.cn) for feedback on +earlier versions of this document, and to thank Mark Allman for his +extensive feedback from using the draft to produce a working +implementation. -11. References +13. Normative References + +14. Non-normative References [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 SIGCOMM 2000. [3] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based Congestion Control for Unicast Applications: the Extended Version", ICSI tech report TR-00-03, March 2000. [4] Padhye, J. and Firoiu, V. and Towsley, D. and Kurose, J., "Modeling TCP Throughput: A Simple Model and its Empirical Validation", Proc ACM SIGCOMM 1998. -[5] Widmer, J., "Equation-Based Congestion Control", Diploma Thesis, - University of Mannheim, February 2000. URL - "http://www.icir.org/tfrc/". +[5] V. Paxson and M. Allman, "Computing TCP's Retransmission Timer", RFC + 2988, November 2000. -[6] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: A +[6] K. Ramakrishnan and S. Floyd, "The Addition of Explicit Congestion + Notification (ECN) to IP", RFC 3168, September 2001. + +[7] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: A Transport Protocol for Real-Time Applications", RFC 1889, January 1996. -[7] K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit Congestion - Notification (ECN) to IP", RFC 2481, January 1999. - -[8] V. Paxson and M. Allman, "Computing TCP's Retransmission Timer", RFC - 2988, November 2000. +[8] Wetherall, D., Ely, D., and Spring, N., "Robust ECN Signaling with + Nonces", draft-ietf-tsvwg-tcp-nonce-03.txt, internet draft, work in + progress, April 2002. -[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. +[9] Widmer, J., "Equation-Based Congestion Control", Diploma Thesis, + University of Mannheim, February 2000. URL + "http://www.icir.org/tfrc/".