idnits 2.17.1 draft-ietf-rmt-bb-tfmcc-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3667, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1361. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (14 October 2004) is 7106 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'WES01' on line 1272 == Unused Reference: '5' is defined on line 1323, but no explicit reference was found in the text == Unused Reference: '9' is defined on line 1338, but no explicit reference was found in the text -- No information found for draft-ietf-rmt-norm-bb - is the name correct? -- Possible downref: Normative reference to a draft: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Obsolete normative reference: RFC 2988 (ref. '5') (Obsoleted by RFC 6298) ** Obsolete normative reference: RFC 2481 (ref. '6') (Obsoleted by RFC 3168) -- Possible downref: Non-RFC (?) normative reference: ref. '7' ** Obsolete normative reference: RFC 1889 (ref. '8') (Obsoleted by RFC 3550) ** Downref: Normative reference to an Historic draft: draft-ietf-tsvwg-tcp-nonce (ref. '9') -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' Summary: 15 errors (**), 0 flaws (~~), 4 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force RMT WG 2 INTERNET-DRAFT Joerg Widmer/EPFL 3 draft-ietf-rmt-bb-tfmcc-04.txt Mark Handley/ICIR 5 14 October 2004 6 Expires: April 2005 8 TCP-Friendly Multicast Congestion Control (TFMCC): 9 Protocol Specification 11 Status of this Document 13 By submitting this Internet-Draft, I certify that any applicable patent 14 or other IPR claims of which I am aware have been disclosed, or will be 15 disclosed, and any of which I become aware will be disclosed, in 16 accordance with RFC 3668. 18 Internet-Drafts are working documents of the Internet Engineering Task 19 Force (IETF), its areas, and its working groups. Note that other groups 20 may also distribute working documents as Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet- Drafts as reference material 25 or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This document is a product of the IETF RMT WG. Comments should be 34 addressed to the authors, or the WG's mailing list at rmt@lbl.gov. 36 Abstract 38 This document specifies TCP-Friendly Multicast Congestion 39 Control (TFMCC). TFMCC is a congestion control mechanism for 40 multicast transmissions in a best-effort Internet environment. 42 Expires: April 2005 October 2004 44 It is a single-rate congestion control scheme, where the 45 sending rate is adapted to the receiver experiencing the worst 46 network conditions. TFMCC is reasonably fair when competing 47 for bandwidth with TCP flows and has a relatively low 48 variation of throughput over time, making it suitable for 49 applications such as streaming media where a relatively smooth 50 sending rate is of importance. 52 Expires: April 2005 October 2004 54 Table of Contents 56 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 4 57 1.1. Terminology. . . . . . . . . . . . . . . . . . . . . 5 58 1.2. Related Documents. . . . . . . . . . . . . . . . . . 5 59 1.3. Environmental Requirements and Considerations. . . . 5 60 2. Protocol Overview . . . . . . . . . . . . . . . . . . . 6 61 2.1. TCP Throughput Equation. . . . . . . . . . . . . . . 7 62 2.2. Packet Contents. . . . . . . . . . . . . . . . . . . 8 63 2.2.1. Sender Packets. . . . . . . . . . . . . . . . . . 8 64 2.2.2. Feedback Packets. . . . . . . . . . . . . . . . . 9 65 3. Data Sender Protocol. . . . . . . . . . . . . . . . . . 10 66 3.1. Sender Initialization. . . . . . . . . . . . . . . . 10 67 3.2. Determining the Maximum RTT. . . . . . . . . . . . . 11 68 3.3. Adjusting the Sending Rate . . . . . . . . . . . . . 11 69 3.4. Controlling Receiver Feedback. . . . . . . . . . . . 13 70 3.5. Assisting Receiver-Side RTT Measurements . . . . . . 14 71 3.6. Slowstart. . . . . . . . . . . . . . . . . . . . . . 15 72 3.7. Scheduling of Packet Transmissions . . . . . . . . . 15 73 4. Data Receiver Protocol. . . . . . . . . . . . . . . . . 16 74 4.1. Receiver Initialization. . . . . . . . . . . . . . . 16 75 4.2. Receiver Leave . . . . . . . . . . . . . . . . . . . 16 76 4.3. Measurement of the Network Conditions. . . . . . . . 17 77 4.3.1. Updating the Loss Event Rate. . . . . . . . . . . 17 78 4.3.2. Basic Round-Trip Time Measurement . . . . . . . . 17 79 4.3.3. One-Way Delay Adjustments . . . . . . . . . . . . 18 80 4.3.4. Receive Rate Measurements . . . . . . . . . . . . 18 81 4.4. Setting the Desired Rate . . . . . . . . . . . . . . 19 82 4.5. Feedback and Feedback Suppression. . . . . . . . . . 19 83 5. Calculation of the Loss Event Rate. . . . . . . . . . . 21 84 5.1. Detection of Lost or Marked Packets. . . . . . . . . 21 85 5.2. Translation from Loss History to Loss Events . . . . 22 86 5.3. Inter-Loss Event Interval. . . . . . . . . . . . . . 23 87 5.4. Average Loss Interval. . . . . . . . . . . . . . . . 23 88 5.5. History Discounting. . . . . . . . . . . . . . . . . 24 89 5.6. Initializing the Loss History after the First 90 Loss Event. . . . . . . . . . . . . . . . . . . . . . . . 27 91 6. Security Considerations . . . . . . . . . . . . . . . . 28 92 7. IANA Considerations . . . . . . . . . . . . . . . . . . 28 93 8. Authors' Addresses. . . . . . . . . . . . . . . . . . . 29 94 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . 29 95 10. References . . . . . . . . . . . . . . . . . . . . . . 29 96 11. Copyright Notice . . . . . . . . . . . . . . . . . . . 30 97 Expires: April 2005 October 2004 99 1. Introduction 101 This document specifies TCP-Friendly Multicast Congestion Control 102 (TFMCC) [11]. TFMCC is a source-based, single-rate congestion control 103 scheme that builds upon the unicast TCP-Friendly Rate Control mechanism 104 (TFRC) [2]. TFMCC is stable and responsive under a wide range of network 105 conditions and scales to receiver sets on the order of several thousand 106 receivers. To support scalability, as much congestion control 107 functionality as possible is located at the receivers. Each receiver 108 continuously determines a desired receive rate that is TCP-friendly for 109 the path from the sender to this receiver. Selected receivers then 110 report the rate to the sender in feedback packets. 112 TFMCC is a building block as defined in RFC 3048. Instead of specifying 113 a complete protocol, this document simply specifies a congestion control 114 mechanism that could be used in a transport protocol such as RTP [8], in 115 an application incorporating end-to-end congestion control at the 116 application level. This document does not discuss packet formats, 117 reliability, or implementation-related issues. 119 TFMCC is designed to be reasonably fair when competing for bandwidth 120 with TCP flows. A multicast flow is ``reasonably fair'' if its sending 121 rate is generally within a factor of two of the sending rate of a TCP 122 flow from the sender to the slowest receiver of the multicast group 123 under the same network conditions. 125 In general, TFMCC has a low variation of throughput, which makes it 126 suitable for applications such as streaming media where a relatively 127 smooth sending rate is of importance. The penalty of having smooth 128 throughput while competing fairly for bandwidth is a reduced 129 responsiveness to changes in available bandwidth. Thus TFMCC should be 130 used when the application has a requirement for smooth throughput, in 131 particular, avoiding halving of the sending rate in response to a single 132 packet drop. For applications that simply need to multicast as much 133 data as possible in as short a time as possible, PGMCC [7] may be more 134 suitable. 136 TFMCC is designed for applications that use a fixed packet size, and 137 vary their sending rate in packets per second in response to congestion. 138 Some audio applications require a fixed interval of time between packets 139 and vary their packet size instead of their packet rate in response to 140 congestion. The congestion control mechanism in this document cannot be 141 used by those applications. 143 Expires: April 2005 October 2004 145 1.1. Terminology 147 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 148 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 149 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 150 requirement levels for compliant TFMCC implementations. 152 1.2. Related Documents 154 As described in RFC 3048, TFMCC is a building block that is intended to 155 be used, in conjunction with other building blocks, to help specify a 156 protocol instantiation. In particular, TFMCC is a suitable congestion 157 control building block for NACK-Oriented Reliable Multicast (NORM) [1]. 159 1.3. Environmental Requirements and Considerations 161 TFMCC is intended to be a congestion control scheme that can be used in 162 a complete protocol instantiation that delivers objects and streams 163 (both reliable content delivery and streaming of multimedia 164 information). 166 TFMCC is most applicable for sessions that deliver a substantial amount 167 of data, i.e., in length from hundreds of kilobytes to many gigabytes, 168 and whose duration is in the order of tens of seconds or more. 170 TFMCC is intended for multicast delivery. There are currently two 171 models of multicast delivery, the Any-Source Multicast (ASM) model as 172 defined in RFC 1112 and the Source-Specific Multicast (SSM) model as 173 defined in [3]. TFMCC works with both multicast models, but in a 174 slightly different way. When using ASM, feedback from the receivers is 175 multicast to the sender as well as to all other receivers. Feedback can 176 be either multicast on the same group address used for sending data or 177 on a separate multicast feedback group address. For SSM, the receivers 178 must unicast the feedback directly to the sender. Hence, feedback from 179 a receiver will not be received by other receivers. 181 TFMCC inherently works with all types of networks, including LANs, WANs, 182 Intranets, the Internet, asymmetric networks, wireless networks, and 183 satellite networks. However, in some network environments varying the 184 sending rate to the receivers may not be advantageous (e.g., for a 185 satellite or wireless network, there may be no mechanism for receivers 186 to effectively reduce their reception rate since there may be a fixed 187 transmission rate allocated to the session). 189 Expires: April 2005 October 2004 191 2. Protocol Overview 193 TFMCC extends the basic mechanisms of TFRC into the multicast domain. 194 In order to compete fairly with TCP, TFMCC receivers individually 195 measure the prevalent network conditions and calculate a rate that is 196 TCP-friendly on the path from the sender to themselves. The rate is 197 determined using an equation for TCP throughput, which roughly describes 198 TCP's sending rate as a function of the loss event rate, round-trip time 199 (RTT), and packet size. We define a loss event as one or more lost or 200 marked packets from the packets received during one RTT, where a marked 201 packet refers to a congestion indication from Explicit Congestion 202 Notification (ECN) [6]. The sending rate of the multicast transmission 203 is adapted to the receiver experiencing the worst network conditions. 205 Basically, TFMCC's congestion control mechanism works as follows: 207 o Each receiver measures the loss event rate and its RTT to the sender. 209 o Each receiver then uses this information, together with an equation 210 for TCP throughput, to derive a TCP-friendly sending rate. 212 o Through a distributed feedback suppression mechanism, only a subset of 213 the receivers are allowed to give feedback to prevent a feedback 214 implosion at the sender. The feedback mechanism ensures that 215 receivers reporting a low desired transmission rate have a high 216 probability of sending feedback. 218 o Receivers whose feedback is not suppressed report the calculated 219 transmission rate back to the sender in so-called receiver reports. 220 The receiver reports serve two purposes: they inform the sender about 221 the appropriate transmit rate, and they allow the receivers to measure 222 their RTT. 224 o The sender selects the receiver that reports the lowest rate as 225 current limiting receiver (CLR). Whenever feedback with an even lower 226 rate reaches the sender, the corresponding receiver becomes CLR and 227 the sending rate is reduced to match that receiver's calculated rate. 228 The sending rate increases when the CLR reports a calculated rate 229 higher than the current sending rate. 231 The dynamics of TFMCC are sensitive to how the measurements are 232 performed and applied and what feedback suppression mechanism is chosen. 233 We recommend specific mechanisms below to perform and apply these 234 measurements. Other mechanisms are possible, but it is important to 235 understand how the interactions between mechanisms affect the dynamics 236 of TFMCC. 238 Expires: April 2005 October 2004 240 2.1. TCP Throughput Equation 242 Any realistic equation giving TCP throughput as a function of loss event 243 rate and RTT should be suitable for use in TFMCC. However, we note that 244 the TCP throughput equation used must reflect TCP's retransmit timeout 245 behavior, as this dominates TCP throughput at higher loss rates. We 246 also note that the assumptions implicit in the throughput equation about 247 the loss event rate parameter have to be a reasonable match to how the 248 loss rate or loss event rate is actually measured. While this match is 249 not perfect for the throughput equation and loss rate measurement 250 mechanisms given below, in practice the assumptions turn out to be close 251 enough. 253 The throughput equation we currently recommend for TFMCC is a slightly 254 simplified version of the throughput equation for Reno TCP from [4]: 256 8 s 257 X = --------------------------------------------------------- (1) 258 R * (sqrt(2*p/3) + (12*sqrt(3*p/8) * p * (1+32*p^2))) 260 where 262 X is the transmit rate in bits/second. 264 s is the packet size in bytes. 266 R is the round-trip time in seconds. 268 p is the loss event rate, between 0.0 and 1.0, of the number of 269 loss events as a fraction of the number of packets transmitted. 271 In future, different TCP equations may be substituted for this equation. 272 The requirement is that the throughput equation be a reasonable 273 approximation of the sending rate of TCP for conformant TCP congestion 274 control. 276 The parameters s (packet size), p (loss event rate) and R (RTT) need to 277 be measured or calculated by a TFMCC implementation. The measurement of 278 R is specified in Section 4.3.2, and the measurement of p is specified 279 in Section 5. The parameter s (packet size) is normally known to an 280 application. This may not be so in two cases: 282 o The packet size naturally varies depending on the data. In this case, 283 although the packet size varies, that variation is not coupled to the 284 Expires: April 2005 October 2004 286 transmit rate. It should normally be safe to use an estimate of the 287 mean packet size for s. 289 o The application needs to change the packet size rather than the number 290 of packets per second to perform congestion control. This would 291 normally be the case with packet audio applications where a fixed 292 interval of time needs to be represented by each packet. Such 293 applications need to have a different way of measuring parameters. 295 Currently, TFMCC cannot be used for the second class of applications. 297 2.2. Packet Contents 299 Before specifying the sender and receiver functionality, we describe the 300 congestion control information contained in packets sent by the sender 301 and feedback packets from the receivers. Information from the sender 302 can either be sent in separate congestion control messages or 303 piggybacked onto data packets. If separate congestion control messages 304 are sent at time intervals larger than the time interval between data 305 packets (e.g., once per feedback round), it is necessary to be able to 306 include timestamp information destined for more than one receiver to 307 allow a sufficient number of receivers to measure their RTT. 309 As TFMCC will be used along with a transport protocol, we do not specify 310 packet formats, since these depend on the details of the transport 311 protocol used. The recommended representation of the header fields is 312 given below. Alternatively, if the computational overhead of a floating 313 point representation is prohibitive, fixed point arithmetic can be used 314 at the expense of larger packet headers. 316 2.2.1. Sender Packets 318 Each packet sent by the data sender contains the following information: 320 o A sequence number i. This number is incremented by one for each data 321 packet transmitted. The field must be sufficiently large that it does 322 not wrap causing two different packets with the same sequence number 323 to be in the receiver's recent packet history at the same time. In 324 most cases the sequence number will be supplied by the transport 325 protocol used along with TFMCC. 327 o A suppression rate X_supp in bits/s. Only receivers with a calculated 328 rate lower than the suppression rate are eligible to give feedback, 329 unless their RTT is higher than the maximum RTT described below in 330 which case they are also eligible to give feedback. The suppression 331 rate should be represented as a 12 bit floating point value with 5 332 Expires: April 2005 October 2004 334 bits for the unsigned exponent and 7 bits for the unsigned mantissa 335 (to represent rates from 100 bit/s to 400 Gbit/s with an error of less 336 than 1%). 338 o A timestamp ts_i indicating when the packet is sent. The resolution 339 of the timestamp should typically be milliseconds and the timestamp 340 should be an unsigned integer value no less than 16 bits wide. 342 o A receiver ID r and a copy of the timestamp ts_r of that receiver's 343 last report, which allows the receiver to measure its RTT. The 344 receiver ID is described in the next section. The resolution of the 345 timestamp echo should be milliseconds and the timestamp should be an 346 unsigned integer value no less than 16 bits wide. If separate instead 347 of piggybacked congestion control messages are used, the packet needs 348 to contain a list of receiver IDs with corresponding timestamps to 349 allow a sufficient number of receivers to simultaneously measure their 350 RTT. For the default values used for the feedback process this 351 corresponds to a list size on the order of 10 to 20 entries. 353 o A flag is_CLR indicating whether the receiver with ID r is the CLR. 355 o A feedback round counter fb_nr. This counter is incremented by the 356 sender at the beginning of a new feedback round to notify the 357 receivers than all feedback for older rounds should be suppressed. 358 The feedback round counter should be at least 4 bits wide. 360 o A maximum RTT value R_max, representing the maximum of the RTTs of all 361 receivers. The RTT should be measured in milliseconds. An 8 bit 362 floating point value with 4 bits for the unsigned exponent and 4 bits 363 for the unsigned mantissa (to represent RTTs from 1 millisecond to 64 364 seconds with an error of ca. 6%) should be used for the 365 representation. 367 2.2.2. Feedback Packets 369 Each feedback packet sent by a data receiver contains the following 370 information: 372 o A unique receiver ID r. In most cases the receiver ID will be 373 supplied by the transport protocol, but it may simply be the IP 374 address of the receiver. 376 o A flag have_RTT indicating whether the receiver has made at least one 377 RTT measurement since it joined the session. 379 o A flag have_loss indicating whether the receiver experienced at least 380 one loss event since it joined the session. 382 Expires: April 2005 October 2004 384 o A flag receiver_leave indicating that the receiver will leave the 385 session (and should therefore not be CLR). 387 o A timestamp ts_r indicating when the feedback packet is sent. The 388 representation of the timestamp should be the same as that of the 389 timestamp echo in the data packets. 391 o An echo of the timestamp of the last data packet received. If the 392 last packet received at the receiver has sequence number i, then ts_i 393 is included in the feedback. If there is a delay t_d between 394 receiving that last data packet and sending feedback, then ts_i' = 395 ts_i + t_d is included in the feedback instead of ts_i. The 396 representation of the timestamp echo should be the same as that of the 397 timestamp in the data packets. 399 o A feedback round echo fb_nr, reflecting the highest feedback round 400 counter value received so far. The representation of the feedback 401 round echo should be the same as the one used for the feedback round 402 counter in the data packets. 404 o The desired sending rate X_r. This is the rate calculated by the 405 receiver to be TCP-friendly on the path from the sender to this 406 receiver. The representation of the desired sending rate should be 407 the same as that of the suppression rate in the data packets. 409 3. Data Sender Protocol 411 The data sender multicasts a stream of data packets to the data 412 receivers at a controlled rate. Whenever feedback is received, the 413 sender checks if it is necessary to switch CLRs and to readjust the 414 sending rate. 416 The main tasks that have to be provided by a TFMCC sender are: 418 o adjusting the sending rate, 420 o controlling receiver feedback, and 422 o assisting receiver-side RTT measurements. 424 3.1. Sender Initialization 426 At initialization of the sender, the maximum RTT is set to a value that 427 should be larger than the highest RTT to any of the receivers. It 428 should not be smaller than 500 milliseconds for operation in the public 429 Internet. The sending rate X is initialized to 1 packet per maximum 430 Expires: April 2005 October 2004 432 RTT. 434 3.2. Determining the Maximum RTT 436 For each feedback packet that arrives at the sender, the sender computes 437 the instantaneous RTT to the receiver as 439 R_r = t_now - ts_i 441 where t_now is the time the feedback packet arrived. Receivers will 442 have adjusted ts_i for the time interval between receiving the last data 443 packet and sending the corresponding report so that this interval will 444 not be included in R_r. If the actual RTT is smaller than the 445 resolution of the timestamps and t_now equals ts_i, then R_r is set to 446 the smallest positive RTT value larger than 0 (i.e., 1 millisecond in 447 our case). If the instantaneous RTT is larger than the current maximum 448 RTT, the maximum RTT is increased to that value 450 R_max = R_r 452 Otherwise, if no feedback with a higher instantaneous RTT than the 453 maximum RTT is received during a feedback round (see Section 3.4), the 454 maximum RTT is reduced to 456 R_max = MAX(R_max * 0.9, R_peak) 458 where R_peak is the peak receiver RTT measured during the feedback 459 round. 461 The maximum RTT is mainly used for feedback suppression among receivers 462 with heterogeneous RTTs. Feedback suppression is closely coupled to the 463 sending of data packets and for this reason, the maximum RTT must not 464 decrease below the maximum time interval between consecutive data 465 packets: 467 R_max = max(R_max, s/X + t_gran) 469 where t_gran is the granularity of the sender's system clock (see 470 Section 3.7). 472 3.3. Adjusting the Sending Rate 474 When a feedback packet from receiver r arrives at the sender, the sender 475 has to check whether it is necessary to adjust the transmission rate and 476 to switch to a new CLR. 478 Expires: April 2005 October 2004 480 How the rate is adjusted depends on the desired rate X_r of the receiver 481 report. We distinguish four cases: 483 1 If no CLR is present, receiver r becomes the current limiting 484 receiver. The sending rate X is directly set to X_r, so long as 485 this would result in a rate increase of less than 8s/R_max bits/s 486 (i.e., 1 packet per R_max). Otherwise X is gradually increased to 487 X_r at an increase rate of no more than 8s/R_max bits/s every R_max 488 seconds. 490 2 If receiver r is not the CLR but a CLR is present, then receiver r 491 becomes the current limiting receiver if X_r is less than the 492 current sending rate X and the receiver_leave flag of that 493 receiver's report is not set. Furthermore, the sending rate is 494 reduced to X_r. 496 3 If receiver r is not the CLR but a CLR is present and the 497 receiver_leave flag of the CLR's last report was set, then receiver 498 r becomes the current limiting receiver. However, if X_r > X, the 499 sending rate is not increased to X_r for the duration of a feedback 500 round to allow other (lower rate) receivers to give feedback and be 501 selected as CLR. 503 4 If receiver r is the CLR, the sending rate is set to the minimum of 504 X_r and X + 8s/R_max bits/s. 506 If the receiver has not yet measured its RTT but already experienced 507 packet loss (indicated by the corresponding flags in the receiver 508 report), the receiver report will include a desired rate that is based 509 on the maximum RTT rather than the actual RTT to that receiver. In this 510 case, the sender adjusts the desired rate using its measurement of the 511 instantaneous RTT R_r to that receiver: 513 X_r' = X_r * R_max / R_r 515 X_r' is then used instead of X_r to detect whether to switch to a new 516 CLR. 518 If the TFMCC sender receives no reports from the CLR for 4 RTTs, the 519 sending rate is cut in half unless the CLR was selected less than 10 520 RTTs ago. In addition, if the sender receives no reports from the CLR 521 for at least 10 RTTs, it assumes that the CLR crashed or left the group. 522 A new CLR is selected from the feedback that subsequently arrives at the 523 sender, and we increase as in case 3 above. 525 If no new CLR can be selected (i.e., in the absence of any feedback from 526 any of the receivers) it is necessary to further reduce the sending 527 rate. For every 10 consecutive RTTs without feedback, the sending rate 528 Expires: April 2005 October 2004 530 is cut in half. The rate is at most reduced to one packet every 8 531 seconds. 533 Note that when receivers stop receiving data packets, they will stop 534 sending feedback. This eventually causes the sending rate to be reduced 535 in the case of network failure. If the network subsequently recovers, a 536 linear increase to the calculated rate of the CLR will occur at 8s/R_max 537 bits/s every R_max. 539 3.4. Controlling Receiver Feedback 541 The receivers allowed to send a receiver report are determined in so- 542 called feedback rounds. Feedback rounds have a duration T of six times 543 the maximum RTT. In case the multicast model is ASM, i.e., receiver 544 feedback is multicast to the whole group, the duration of a feedback 545 round may be reduced to four times the maximum RTT. 547 Only receivers wishing to report a rate that is lower than the 548 suppression rate X_supp, or those with a higher RTT than R_max may send 549 feedback. At the beginning of each feedback round, X_supp is set to the 550 highest possible value that can be represented. When feedback arrives 551 at the sender over the course of a feedback round, X_supp is decreased 552 such that more and more feedback is suppressed towards the end of the 553 round. How receiver feedback is spread out over the feedback round is 554 discussed in Section 4.5. 556 Whenever non-CLR feedback for the current round arrives at the sender, 557 X_supp is reduced to 559 X_supp = (1-g) * X_r 561 if X_supp > X_r. Feedback that causes the corresponding receiver to be 562 selected as CLR, but was from a non-CLR receiver at the time of sending 563 also contributes to the feedback suppression. Note that X_r must not be 564 adjusted by the sender to reflect the receiver's real RTT in case X_r 565 was calculated using the maximum RTT, as is done for setting the sending 566 rate (Section 3.3), otherwise a feedback implosion is possible. The 567 parameter g determines to what extent higher rate feedback can suppress 568 lower rate feedback. This mechanism guarantees, that the lowest 569 calculated rate reported lies within a factor of g of the actual lowest 570 calculated rate of the receiver set (see [10]). A value of g of 0.1 is 571 recommended. 573 To allow receivers to suppress their feedback, the sender's suppression 574 rate needs to be updated whenever feedback is received. This 575 suppression rate has to be communicated to the receivers in a timely 576 manner, either by including it in the data packet header or, if separate 577 Expires: April 2005 October 2004 579 congestion control messages are used, by sending a message with the 580 suppression rate whenever the rate changes significantly (i.e., when it 581 is reduced to less than (1-g) times the previously advertised 582 suppression rate). 584 After a time span of T, the feedback round ends if non-CLR feedback was 585 received during that time. Otherwise, the feedback round ends as soon 586 as the first non-CLR feedback message arrives at the sender but at most 587 after 2T. The feedback round counter is incremented by one and the 588 suppression rate X_supp is reset to the highest representable value. 589 The feedback round counter restarts with round 0 after a wrap-around. 591 3.5. Assisting Receiver-Side RTT Measurements 593 Receivers measure their RTT by sending a timestamp with a receiver 594 report, which is echoed by the sender. If congestion control 595 information is piggybacked onto data packets, usually only one receiver 596 ID and timestamp can be included. If multiple feedback messages from 597 different receivers arrive at the sender during the time interval 598 between two data packets, the sender has to decide which receiver to 599 allow to measure RTT. The same applies if separate congestion control 600 messages allow to echo multiple receiver timestamps simultaneously but 601 the number of receivers that gave feedback since the last congestion 602 control message exceeds the list size. 604 The sender's timestamp echoes are prioritized in the following order: 606 1. a new CLR (after a change of CLR's) or a CLR without any previous 607 RTT measurements 609 2. receivers without any previous RTT measurements in the order of the 610 feedback round echo of the corresponding receiver report (i.e., 611 older feedback first) 613 3. non-CLR receivers with previous RTT measurements, again in 614 ascending order of the feedback round echo of the report 616 4. the CLR 618 Ties are broken in favor of the receiver with the lowest reported rate. 620 It is necessary to account for the time that elapses between receiving a 621 report and sending the next data packet. This time needs to be deducted 622 from the RTT and thus has to be added to the receiver's timestamp value. 624 Whenever no feedback packets arrive in the interval between two data 625 packets, the CLR's last timestamp, adjusted by the appropriate offset, 626 Expires: April 2005 October 2004 628 is echoed. When the number of packets per RTT is so low that all 629 packets carry a non-CLR receiver's timestamp, the CLR's timestamp and ID 630 are included in a data packet at least once per feedback round. 632 3.6. Slowstart 634 TFMCC uses a slowstart mechanism to quickly approach its fair bandwidth 635 share at the start of a session. During slowstart, the sending rate 636 increases exponentially. The rate increase is limited to the minimum of 637 the rates included in the receiver reports and receivers report twice 638 the rate at which they currently receive data. As in normal congestion 639 control mode, the receiver with the smallest reported rate becomes CLR. 640 Since a receiver can never receive data at a rate higher than its link 641 bandwidth, this effectively limits the overshoot to twice this 642 bandwidth. In case the resulting increase over R_max is less than 643 8s/R_max bits/s, the sender may choose to increase the rate by up to 644 8s/R_max bits/s every R_max. The current sending rate is gradually 645 adjusted to the target rate reported in the receiver reports over the 646 course of a RTT. Slowstart is terminated as soon as any one of the 647 receivers experiences its first packet loss. Since that receiver's 648 calculated rate will be lower than the current sending rate, the 649 receiver will be selected as CLR. 651 During slowstart, the upper bound on the rate increase of 8s/R_max 652 bits/s every RTT does not apply. Only after the TFMCC sender receives 653 the first report with the have_loss flag set is the rate increase 654 limited in this way. 656 3.7. Scheduling of Packet Transmissions 658 As TFMCC is rate-based, and as operating systems typically cannot 659 schedule events precisely, it is necessary to be opportunistic about 660 sending data packets so that the correct average rate is maintained 661 despite the coarse-grain or irregular scheduling of the operating 662 system. Thus a typical sending loop will calculate the correct inter- 663 packet interval, t_ipi, as follows: 665 t_ipi = s/X 667 When a sender first starts sending at time t_0, it calculates t_ipi, and 668 calculates a nominal send time t_1 = t_0 + t_ipi for packet 1. When the 669 application becomes idle, it checks the current time, t_now, and then 670 requests re-scheduling after (t_ipi - (t_now - t_0)) seconds. When the 671 application is re-scheduled, it checks the current time, t_now, again. 672 If (t_now > t_1 - delta) then packet 1 is sent (see below for delta). 674 Expires: April 2005 October 2004 676 Now a new t_ipi may be calculated, and used to calculate a nominal send 677 time t_2 for packet 2: t2 = t_1 + t_ipi. The process then repeats, with 678 each successive packet's send time being calculated from the nominal 679 send time of the previous packet. 681 In some cases, when the nominal send time, t_i, of the next packet is 682 calculated, it may already be the case that t_now > t_i - delta. In 683 such a case the packet should be sent immediately. Thus if the 684 operating system has coarse timer granularity and the transmit rate is 685 high, then TFMCC may send short bursts of several packets separated by 686 intervals of the OS timer granularity. 688 The parameter delta is to allow a degree of flexibility in the send time 689 of a packet. If the operating system has a scheduling timer granularity 690 of t_gran seconds, then delta would typically be set to: 692 delta = min(t_ipi/2, t_gran/2) 694 t_gran is 10 milliseconds on many Unix systems. If t_gran is not known, 695 a value of 10 milliseconds can be safely assumed. 697 4. Data Receiver Protocol 699 Receivers measure the current network conditions, namely RTT and loss 700 event rate, and use this information to calculate a rate that is fair to 701 competing traffic. The rate is then communicated to the sender in 702 receiver reports. Due to the potentially large number of receivers, it 703 is undesirable that all receivers send reports, especially not at the 704 same time. 706 In the description of the receiver functionality, we will first address 707 how the receivers measure the network parameters and then discuss the 708 feedback process. 710 4.1. Receiver Initialization 712 The receiver is initialized when it receives the first data packet. The 713 RTT is set to the maximum RTT value contained in the data packet. This 714 initial value is used as the receiver's RTT until the first real RTT 715 measurement is made. The loss event rate is initialized to 0. 717 4.2. Receiver Leave 719 A receiver that sends feedback but wishes to leave the TFMCC session 720 within the next feedback round may indicate the pending leave by setting 721 Expires: April 2005 October 2004 723 the receiver_leave flag in its report. If the leaving receiver is the 724 CLR, the receiver_leave flag should be set for all the reports within 725 the feedback round before the leave takes effect. 727 4.3. Measurement of the Network Conditions 729 Receivers have to update their estimate of the network parameters with 730 each new data packet they receive. 732 4.3.1. Updating the Loss Event Rate 734 When a data packet is received, the receiver adds the packet to the 735 packet history. It then recalculates the new value of the loss event 736 rate p. The loss event rate measurement mechanism is described 737 separately in Section 5. 739 4.3.2. Basic Round-Trip Time Measurement 741 When a receiver gets a data packet that carries the receiver's own ID in 742 the r field, the receiver updates its RTT estimate. 744 1. The current RTT is calculated as: 746 R_sample = t_now - ts_r 748 where t_now is the time the data packet arrives at the receiver and 749 ts_r is the receiver report timestamp echoed in the data packet. If 750 the actual RTT is smaller than the resolution of the timestamps and 751 t_now equals ts_r, then R_sample is set to the smallest positive 752 RTT value larger than 0 (i.e., 1 millisecond in our case). 754 2. The smoothed RTT estimate R is updated: 756 If no feedback has been received before 757 R = R_sample 758 Else 759 R = q*R + (1-q)*R_sample 761 A filter parameter q of 0.5 is recommended for non-CLR receivers. 762 The CLR performs RTT measurements much more frequently and hence 763 should use a higher filter value. We recommend using q=0.9. Note 764 that TFMCC is not sensitive to the precise value for the filter 765 constant. 767 Expires: April 2005 October 2004 769 Optionally, sender-based instead of receiver-based RTT measurements may 770 be used. The sender already determines the RTT to a receiver from the 771 receiver's echo of the sender's own timestamp for the calculation of the 772 maximum RTT. For sender-based RTT measurements, this RTT measurement 773 needs to be communicated to the receiver. Instead of including an echo 774 of the receiver's timestamp, the sender includes the receiver's RTT in 775 the next data packet, using the prioritization rules described in 776 Section 3.5. 778 To simplify sender operation, smoothing of RTT samples as described 779 above should still be done at the receiver. 781 4.3.3. One-Way Delay Adjustments 783 When a RTT measurement is performed, the receiver also determines the 784 one-way delay D_r from itself to the sender: 786 D_r = ts_r - ts_i 788 where ts_i and ts_r are the timestamp and timestamp echo contained in 789 the data packet. With each new data packet i', the receiver can now 790 calculate an updated RTT estimate as: 792 R' = max(D_r + t_now - ts_i', 1 millisecond) 794 In between RTT measurements, the updated R' is used instead of the 795 smoothed RTT R. Like the RTT samples, R' must be strictly positive. When 796 a new measurement is made, all interim one-way delay measurements are 797 discarded (i.e., the smoothed RTT is updated according to Section 4.3.2 798 without taking one-way delay adjustments into account). 800 For the one-way delay measurements, the clocks of sender and receivers 801 need not be synchronized. Clock skew will cancel itself out when both 802 one-way measurements are added to form a RTT estimate, as long as clock 803 drift between real RTT measurements is negligible. 805 The same one-way delay adjustments should be applied to the RTT supplied 806 by the sender when using sender-based RTT measurements. 808 4.3.4. Receive Rate Measurements 810 When a receiver has not experienced any loss events, it cannot calculate 811 a TCP-friendly rate to include in the receiver reports. Instead, the 812 receiver measures the current receive rate and sets the desired rate X_r 813 to twice the receive rate. 815 Expires: April 2005 October 2004 817 The receive rate in bits/s is measured as the number of bits received 818 over the last k RTTs, taking into account the IP and transport packet 819 headers, but excluding the link-layer packet headers. A value for k 820 between 2 and 4 is recommended. 822 4.4. Setting the Desired Rate 824 When a receiver measures a non-zero loss event rate, it calculates the 825 desired rate using Equation (1). In case no RTT measurement is 826 available yet, the maximum RTT is used instead of the receiver's RTT. 827 The desired rate X_r is updated whenever the loss event rate or the RTT 828 changes. 830 A receiver may decide to not report desired rates that are below 1 831 packet per 8 seconds, since a sender is very slow to recover from such 832 low sending rates. In this case, the receiver reports a desired rate of 833 1 packet per 8 seconds. However, it must leave the multicast group if 834 for more than 120 seconds the calculated rate falls below the reported 835 rate and the current sending rate is higher than the receiver's 836 calculated rate. 838 As mentioned above, calculation of the desired rate is not possible 839 before the receiver experiences the first loss event and in that case 840 twice the rate at which data is received is included in the receiver 841 reports as X_r. This mechanism allows the sender to slowstart as 842 described in Section 3.6. 844 4.5. Feedback and Feedback Suppression 846 Let fb_nr be the highest feedback round counter value received by a 847 receiver. When a new data packet arrives with a higher feedback round 848 counter than fb_nr, a new feedback round begins and fb_nr is updated. 849 Outstanding feedback for the old round is canceled. In case a feedback 850 number with a value that is more than half the feedback number space 851 lower than fb_nr is received, the receiver assumes that the feedback 852 round counter wrapped and also cancels the feedback timer and updates 853 fb_nr. 855 The CLR sends its feedback independently from all the other receivers 856 once per RTT. Its feedback does not suppress other feedback and cannot 857 be suppressed by other receiver's feedback. 859 Non-CLR receivers set a feedback timer at the beginning of a feedback 860 round. Using an exponentially weighted random timer mechanism, the 861 feedback timer is set to expire after 862 Expires: April 2005 October 2004 864 t = max(T * (1 + log(x)/log(N)), 0) 866 where 868 x is a random variable uniformly distributed in (0,1], 870 T is the duration of a feedback round (i.e., 6 * R_max), 872 N is an estimated upper bound on the number of receivers. 874 N is a constant specific to the TFMCC protocol. Since TFMCC scales to 875 up to thousands of receivers, setting N to 10,000 for all receivers (and 876 limiting the TFMCC session to at most 10,000 receivers) is recommended. 878 A feedback packet is sent when the feedback timer expires, unless the 879 timer is canceled beforehand. When the multicast model is ASM, feedback 880 is multicast to the whole group, otherwise the feedback is unicast to 881 the sender. The feedback packet includes the calculated rate valid at 882 the time the feedback packet is sent (not the rate at the point of time 883 when the feedback timer is set). The copy of the timestamp ts_i of the 884 last data packet received, which is included in the feedback packet, 885 needs to be adjusted by the time interval between receiving the data 886 packet and sending the report to allow the sender to correctly infer the 887 instantaneous RTT (i.e., that time interval has to be added to the 888 timestamp value). 890 The timer is canceled if a data packet with a lower suppression rate 891 than the receiver's calculated rate and a higher or equal maximum RTT 892 than the receiver's RTT is received. Likewise, a data packet indicating 893 the beginning of a new feedback round cancels all feedback for older 894 rounds. In case of ASM, the timer is also canceled if a feedback packet 895 from another non-CLR receiver reporting a lower rate is received. 897 The feedback suppression process is complicated by the fact that the 898 calculated rates of the receivers will change during a feedback round. 899 If the calculated rates decrease rapidly for all receivers, feedback 900 suppression can no longer prevent a feedback implosion since earlier 901 feedback will always report a higher rate than current feedback. To make 902 the feedback suppression mechanism robust in the face of changing rates, 903 it is necessary to introduce X_fbr, the calculated rate of a receiver at 904 the beginning of a feedback round. A receiver needs to suppress its 905 feedback not only when the suppression rate is less than the receiver's 906 current calculated rate but also in the case that the suppression rate 907 falls below X_fbr. 909 When the maximum RTT changes significantly during one feedback round, it 910 is necessary to reschedule the feedback timer in proportion to the 911 change. 913 Expires: April 2005 October 2004 915 t = t * R_max / R_max' 917 where R_max is the new maximum RTT and R_max' is the previous maximum 918 RTT. The same considerations hold, when the last data packets were 919 received more than a time interval of R_max ago. In this case, it is 920 necessary to add the difference of the inter-packet gap and the maximum 921 RTT to the feedback time to prevent a feedback implosion (e.g., in case 922 the sender crashed). 924 t = t + max(t_now - tr_i - R_max, 0) 926 where tr_i is the time when the last data packet arrived at the 927 receiver. 929 More details on the characteristics of the feedback suppression 930 mechanism can be found in [10] and [11]. 932 5. Calculation of the Loss Event Rate 934 Obtaining an accurate and stable measurement of the loss event rate is 935 of primary importance for TFMCC. Loss rate measurement is performed at 936 the receiver, based on the detection of lost or marked packets from the 937 sequence numbers of arriving packets. 939 5.1. Detection of Lost or Marked Packets 941 TFMCC assumes that all packets contain a sequence number that is 942 incremented by one for each packet that is sent. For the purposes of 943 this specification, we require that if a lost packet is retransmitted, 944 the retransmission is given a new sequence number that is the latest in 945 the transmission sequence, and not the same sequence number as the 946 packet that was lost. If a transport protocol has the requirement that 947 it must retransmit with the original sequence number, then the transport 948 protocol designer must figure out how to distinguish delayed from 949 retransmitted packets and how to detect lost retransmissions. 951 The receivers each maintain a data structure that keeps track of which 952 packets have arrived and which are missing. For the purposes of 953 specification, we assume that the data structure consists of a list of 954 packets that have arrived along with the timestamp when each packet was 955 received. In practice this data structure will normally be stored in a 956 more compact representation, but this is implementation-specific. 958 The loss of a packet is detected by the arrival of at least three 959 packets with a higher sequence number than the lost packet. The 960 requirement for three subsequent packets is the same as with TCP, and is 961 Expires: April 2005 October 2004 963 to make TFMCC more robust in the presence of reordering. In contrast to 964 TCP, if a packet arrives late (after 3 subsequent packets arrived) at a 965 receiver, the late packet can fill the hole in the reception record, and 966 the receiver can recalculate the loss event rate. Future versions of 967 TFMCC might make the requirement for three subsequent packets adaptive 968 based on experienced packet reordering, but we do not specify such a 969 mechanism here. 971 For an ECN-capable connection, a marked packet is detected as a 972 congestion event as soon as it arrives, without having to wait for the 973 arrival of subsequent packets. 975 5.2. Translation from Loss History to Loss Events 977 TFMCC requires that the loss event rate be robust to several consecutive 978 packets lost where those packets are part of the same loss event. This 979 is similar to TCP, which (typically) only performs one halving of the 980 congestion window during any single RTT. Thus the receivers needs to 981 map the packet loss history into a loss event record, where a loss event 982 is one or more packets lost in a RTT. 984 To determine whether a lost or marked packet should start a new loss 985 event, or be counted as part of an existing loss event, we need to 986 compare the sequence numbers and timestamps of the packets that arrived 987 at the receiver. For a marked packet S_new, its reception time T_new 988 can be noted directly. For a lost packet, we can interpolate to infer 989 the nominal "arrival time". Assume: 991 S_loss is the sequence number of a lost packet. 993 S_before is the sequence number of the last packet to arrive with 994 sequence number before S_loss. 996 S_after is the sequence number of the first packet to arrive with 997 sequence number after S_loss. 999 T_before is the reception time of S_before. 1001 T_after is the reception time of S_after. 1003 Note that T_before can either be before or after T_after due to 1004 reordering. 1006 For a lost packet S_loss, we can interpolate its nominal "arrival time" 1007 at the receiver from the arrival times of S_before and S_after. Thus 1008 Expires: April 2005 October 2004 1010 T_loss = T_before + ( (T_after - T_before) 1011 * (S_loss - S_before)/(S_after - S_before) ); 1013 Note that if the sequence space wrapped between S_before and S_after, 1014 then the sequence numbers must be modified to take this into account 1015 before performing the calculation. If the largest possible sequence 1016 number is S_max, and S_before > S_after, then modifying each sequence 1017 number S by S' = (S + (S_max + 1)/2) mod (S_max + 1) would normally be 1018 sufficient. 1020 If the lost packet S_old was determined to have started the previous 1021 loss event, and we have just determined that S_new has been lost, then 1022 we interpolate the nominal arrival times of S_old and S_new, called 1023 T_old and T_new respectively. 1025 If T_old + R >= T_new, then S_new is part of the existing loss event. 1026 Otherwise S_new is the first packet of a new loss event. 1028 5.3. Inter-Loss Event Interval 1030 If a loss interval, A, is determined to have started with packet 1031 sequence number S_A and the next loss interval, B, started with packet 1032 sequence number S_B, then the number of packets in loss interval A is 1033 given by (S_B - S_A). 1035 5.4. Average Loss Interval 1037 To calculate the loss event rate p, we first calculate the average loss 1038 interval. This is done using a filter that weights the n most recent 1039 loss event intervals in such a way that the measured loss event rate 1040 changes smoothly. 1042 Weights w_0 to w_(n-1) are calculated as: 1044 If (i < n/2) 1045 w_i = 1; 1046 Else 1047 w_i = 1 - (i - (n/2 - 1))/(n/2 + 1); 1049 Thus if n=8, the values of w_0 to w_7 are: 1051 1.0, 1.0, 1.0, 1.0, 0.8, 0.6, 0.4, 0.2 1052 Expires: April 2005 October 2004 1054 The value n for the number of loss intervals used in calculating the 1055 loss event rate determines TFMCC's speed in responding to changes in the 1056 level of congestion. As currently specified, TFMCC should not be used 1057 for values of n significantly greater than 8, for traffic that might 1058 compete in the global Internet with TCP. At the very least, safe 1059 operation with values of n greater than 8 would require a slight change 1060 to TFMCC's mechanisms to include a more severe response to two or more 1061 round-trip times with heavy packet loss. 1063 When calculating the average loss interval we need to decide whether to 1064 include the interval since the most recent packet loss event. We only 1065 do this if it is sufficiently large to increase the average loss 1066 interval. 1068 Thus if the most recent loss intervals are I_0 to I_n, with I_0 being 1069 the interval since the most recent loss event, then we calculate the 1070 average loss interval I_mean as: 1072 I_tot0 = 0; 1073 I_tot1 = 0; 1074 W_tot = 0; 1075 for (i = 0 to n-1) { 1076 I_tot0 = I_tot0 + (I_i * w_i); 1077 W_tot = W_tot + w_i; 1078 } 1079 for (i = 1 to n) { 1080 I_tot1 = I_tot1 + (I_i * w_(i-1)); 1081 } 1082 I_tot = max(I_tot0, I_tot1); 1083 I_mean = I_tot/W_tot; 1085 The loss event rate, p is simply: 1087 p = 1 / I_mean; 1089 5.5. History Discounting 1091 As described in Section 5.4, the most recent loss interval is only 1092 assigned 4/(3*n) of the total weight in calculating the average loss 1093 interval, regardless of the size of the most recent loss interval. This 1094 section describes an optional history discounting mechanism that allows 1095 the TFMCC receivers to adjust the weights, concentrating more of the 1096 relative weight on the most recent loss interval, when the most recent 1097 loss interval is more than twice as large as the computed average loss 1098 interval. 1100 Expires: April 2005 October 2004 1102 To carry out history discounting, we associate a discount factor DF_i 1103 with each loss interval L_i, where each discount factor is a floating 1104 point number. The discount array maintains the cumulative history of 1105 discounting for each loss interval. At the beginning, the values of 1106 DF_i in the discount array are initialized to 1: 1108 for (i = 0 to n) { 1109 DF_i = 1; 1110 } 1112 History discounting also uses a general discount factor DF, also a 1113 floating point number, that is also initialized to 1. First we show how 1114 the discount factors are used in calculating the average loss interval, 1115 and then we describe later in this section how the discount factors are 1116 modified over time. 1118 As described in Section 5.4 the average loss interval is calculated 1119 using the n previous loss intervals I_1, ..., I_n, and the interval I_0 1120 that represents the number of packets received since the last loss 1121 event. The computation of the average loss interval using the discount 1122 factors is a simple modification of the procedure in Section 5.4, as 1123 follows: 1125 I_tot0 = I_0 * w_0 1126 I_tot1 = 0; 1127 W_tot0 = w_0 1128 W_tot1 = 0; 1129 for (i = 1 to n-1) { 1130 I_tot0 = I_tot0 + (I_i * w_i * DF_i * DF); 1131 W_tot0 = W_tot0 + w_i * DF_i * DF; 1132 } 1133 for (i = 1 to n) { 1134 I_tot1 = I_tot1 + (I_i * w_(i-1) * DF_i); 1135 W_tot1 = W_tot1 + w_(i-1) * DF_i; 1136 } 1137 p = min(W_tot0/I_tot0, W_tot1/I_tot1); 1139 The general discounting factor, DF is updated on every packet arrival as 1140 follows. First, a receiver computes the weighted average I_mean of the 1141 loss intervals I_1, ..., I_n: 1143 Expires: April 2005 October 2004 1145 I_tot = 0; 1146 W_tot = 0; 1147 for (i = 1 to n) { 1148 W_tot = w_(i-1) * DF_i; 1149 I_tot = I_tot + (I_i * w_(i-1) * DF_i); 1150 } 1151 I_mean = I_tot / W_tot; 1153 This weighted average I_mean is compared to I_0, the number of packets 1154 received since the last loss event. If I_0 is greater than twice 1155 I_mean, then the new loss interval is considerably larger than the old 1156 ones, and the general discount factor DF is updated to decrease the 1157 relative weight on the older intervals, as follows: 1159 if (I_0 > 2 * I_mean) { 1160 DF = 2 * I_mean/I_0; 1161 if (DF < THRESHOLD) 1162 DF = THRESHOLD; 1163 } else 1164 DF = 1; 1166 A nonzero value for THRESHOLD ensures that older loss intervals from an 1167 earlier time of high congestion are not discounted entirely. We 1168 recommend a THRESHOLD of 0.5. Note that with each new packet arrival, 1169 I_0 will increase further, and the discount factor DF will be updated. 1171 When a new loss event occurs, the current interval shifts from I_0 to 1172 I_1, loss interval I_i shifts to interval I_(i+1), and the loss interval 1173 I_n is forgotten. The previous discount factor DF has to be 1174 incorporated into the discount array. Because DF_i carries the discount 1175 factor associated with loss interval I_i, the DF_i array has to be 1176 shifted as well. This is done as follows: 1178 for (i = 1 to n) { 1179 DF_i = DF * DF_i; 1180 } 1181 for (i = n-1 to 0 step -1) { 1182 DF_(i+1) = DF_i; 1183 } 1184 I_0 = 1; 1185 DF_0 = 1; 1186 DF = 1; 1188 This completes the description of the optional history discounting 1189 mechanism. We emphasize that this is an optional mechanism whose sole 1190 purpose is to allow TFMCC to response somewhat more quickly to the 1191 sudden absence of congestion, as represented by a long current loss 1192 Expires: April 2005 October 2004 1194 interval. 1196 5.6. Initializing the Loss History after the First Loss Event 1198 The number of packets received before the first loss event usually does 1199 not reflect the current loss event rate. When the first loss event 1200 occurs, a TFMCC receiver assumes that the correct data rate is the rate 1201 at which data was received during the last RTT when the loss occurred. 1202 Instead of initializing the first loss interval to the number of packets 1203 sent until the first loss event, the TFMCC receiver calculates the loss 1204 interval that would be required to produce the receive rate X_recv, and 1205 uses this synthetic loss interval l_0 to seed the loss history 1206 mechanism. 1208 The initial loss interval is calculated by inverting a simplified 1209 version of the TCP Equation (1). 1211 s 1212 X_recv = sqrt(3/2) * ----------------- 1213 R * sqrt(1/l_0) 1215 X_recv * R 1216 ==> l_0 = (---------------)^2 1217 sqrt(3/2) * s 1219 The resulting initial loss interval is too small at higher loss rates 1220 compared to using the more accurate Equation (1), which leads to a more 1221 conservative initial loss event rate. 1223 If a receiver still uses the initial RTT R_max instead of its real RTT, 1224 the initial loss interval is too large in case the initial RTT is higher 1225 than the actual RTT. As a consequence, the receiver will calculate a 1226 too high desired rate when the first RTT measurement R is made and the 1227 initial loss interval is still in the loss history. The receiver has to 1228 adjust l_0 as follows: 1230 l_0 = l_0 * (R/R_max)^2 1232 No action needs to be taken when the first RTT measurement is made after 1233 the initial loss interval left the loss history. 1235 Expires: April 2005 October 2004 1237 6. Security Considerations 1239 TFMCC is not a transport protocol in its own right, but a congestion 1240 control mechanism that is intended to be used in conjunction with a 1241 transport protocol. Therefore security primarily needs to be considered 1242 in the context of a specific transport protocol and its authentication 1243 mechanisms. 1245 Congestion control mechanisms can potentially be exploited to create 1246 denial of service. This may occur through spoofed feedback. Thus any 1247 transport protocol that uses TFMCC should take care to ensure that 1248 feedback is only accepted from valid receivers of the data. The precise 1249 mechanism to achieve this will however depend on the transport protocol 1250 itself. 1252 Congestion control mechanisms may potentially be manipulated by a greedy 1253 receiver that wishes to receive more than its fair share of network 1254 bandwidth. However, in TFMCC a receiver can only influence the sending 1255 rate if it is the CLR and thus has the lowest calculated rate of all 1256 receivers. If the calculated rate is then manipulated such that it 1257 exceeds the calculated rate of the second to lowest receiver, it will 1258 cease to be CLR. A greedy receiver can only significantly increase then 1259 transmission rate if it is the only participant in the session. If such 1260 scenarios are of concern, possible defenses against such a receiver 1261 would normally include some form of nonce that the receiver must feed 1262 back to the sender to prove receipt. However, the details of such a 1263 nonce would depend on the transport protocol, and in particular on 1264 whether the transport protocol is reliable or unreliable. 1266 It is possible that a receiver sends feedback claiming it has a very low 1267 calculated rate. This will reduce the rate of the multicast session and 1268 might render it useless but obviously cannot hurt the network itself. 1270 We expect that protocols incorporating ECN with TFMCC will also want to 1271 incorporate feedback from the receiver to the sender using the ECN nonce 1272 [WES01]. The ECN nonce is a modification to ECN that protects the 1273 sender from the accidental or malicious concealment of marked packets. 1274 Again, the details of such a nonce would depend on the transport 1275 protocol, and are not addressed in this document. 1277 7. IANA Considerations 1279 There are no IANA actions required for this document. 1281 Expires: April 2005 October 2004 1283 8. Authors' Addresses 1285 Joerg Widmer 1286 EPFL (Swiss Federal Institute of Technology - Lausanne) 1287 CH-1015 Lausanne, Switzerland 1288 joerg.widmer@epfl.ch 1290 Mark Handley 1291 UCL (University College London) 1292 Gower Street, London WC1E 6BT, UK 1293 m.handley@cs.ucl.ac.uk 1295 9. Acknowledgments 1297 We would like to acknowledge feedback and discussions on equation-based 1298 congestion control with a wide range of people, including members of the 1299 Reliable Multicast Research Group, the Reliable Multicast Transport 1300 Working Group, and the End-to-End Research Group. We would particularly 1301 like to thank Brian Adamson, Mark Pullen, and Fei Zhao for feedback on 1302 earlier versions of this document. 1304 10. References 1306 [1] B. Adamson, C. Bormann, M. Handley, and J. Macker, "NACK-Oriented 1307 Reliable Multicast (NORM) Protocol Building Blocks", Internet Draft 1308 draft-ietf-rmt-norm-bb-09.txt, July 2004, work in progress. 1309 Citation for informational purposes only. 1311 [2] S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-Based 1312 Congestion Control for Unicast Applications", Proc ACM SIGCOMM 1313 2000, Stockholm, August 2000 1315 [3] H. W. Holbrook, "A Channel Model for Multicast," Ph.D. 1316 Dissertation, Stanford University, Department of Computer Science, 1317 Stanford, California, August 2001. 1319 [4] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, "Modeling TCP 1320 Throughput: A Simple Model and its Empirical Validation", Proc ACM 1321 SIGCOMM 1998. 1323 [5] V. Paxson and M. Allman, "Computing TCP's Retransmission Timer", RFC 1324 2988, November 2000. 1326 Expires: April 2005 October 2004 1328 [6] K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit Congestion 1329 Notification (ECN) to IP", RFC 2481, January 1999. 1331 [7] L. Rizzo, "pgmcc: a TCP-friendly single-rate multicast congestion 1332 control scheme", Proc ACM SIGCOMM 2000, Stockholm, August 2000 1334 [8] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: A 1335 Transport Protocol for Real-Time Applications", RFC 1889, January 1336 1996. 1338 [9] D. Wetherall, D. Ely, and N. Spring, "Robust ECN Signaling with 1339 Nonces", Internet Draft draft-ietf-tsvwg-tcp-nonce-04.txt, October 1340 2002, work in progress. Citation for informational purposes only. 1342 [10] J. Widmer and T. Fuhrmann, "Extremum Feedback for Very Large 1343 Multicast Groups", Proc NGC 2001, London, November 2001. 1345 [11] J. Widmer and M. Handley, "Extending Equation-Based Congestion 1346 Control to Multicast Applications", Proc ACM SIGCOMM 2001, San 1347 Diego, August 2001 1349 11. Copyright Notice 1351 Copyright (C) The Internet Society (2004). This document is subject to 1352 the rights, licenses and restrictions contained in BCP 78, and except as 1353 set forth therein, the authors retain all their rights. 1355 This document and the information contained herein are provided on an 1356 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR 1357 IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1358 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1359 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1360 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1361 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.