idnits 2.17.1 draft-alvestrand-rtcweb-congestion-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (September 5, 2011) is 4610 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'I-D.gharai-avtcore-rtp-tfrc' is defined on line 593, but no explicit reference was found in the text ** Obsolete normative reference: RFC 3448 (Obsoleted by RFC 5348) == Outdated reference: A later version (-01) exists of draft-gharai-avtcore-rtp-tfrc-00 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Lundin 3 Internet-Draft S. Holmer 4 Intended status: Informational H. Alvestrand, Ed. 5 Expires: March 8, 2012 Google 6 September 5, 2011 8 A Google Congestion Control for Real-Time Communication on the World 9 Wide Web 10 draft-alvestrand-rtcweb-congestion-00 12 Abstract 14 This document describes two methods of congestion control when using 15 real-time communications on the World Wide Web (RTCWEB); one sender- 16 based and one receiver-based. 18 It is published to aid the discussion on mandatory-to-implement flow 19 control for RTCWEB applications; initial discussion is expected in 20 the RTCWEB WG's mailing list. 22 Requirements Language 24 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 25 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 26 document are to be interpreted as described in RFC 2119 [RFC2119]. 28 Status of this Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on March 8, 2012. 45 Copyright Notice 47 Copyright (c) 2011 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 1.1. Mathemathical notation conventions . . . . . . . . . . . . 3 64 2. System model . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 3. Receiver side control . . . . . . . . . . . . . . . . . . . . 4 66 3.1. Arrival-time filter . . . . . . . . . . . . . . . . . . . 5 67 3.2. Over-use detector . . . . . . . . . . . . . . . . . . . . 8 68 3.3. Rate control . . . . . . . . . . . . . . . . . . . . . . . 8 69 4. Sender side control . . . . . . . . . . . . . . . . . . . . . 10 70 5. Interoperability Considerations . . . . . . . . . . . . . . . 11 71 6. Implementation Experience . . . . . . . . . . . . . . . . . . 12 72 7. Further Work . . . . . . . . . . . . . . . . . . . . . . . . . 12 73 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 74 9. Security Considerations . . . . . . . . . . . . . . . . . . . 13 75 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 13 76 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 77 11.1. Normative References . . . . . . . . . . . . . . . . . . . 13 78 11.2. Informative References . . . . . . . . . . . . . . . . . . 14 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 81 1. Introduction 83 Congestion control is a requirement for all applications that wish to 84 share the Internet [RFC2914]. 86 The problem of doing congestion control for real-time media is made 87 difficult for a number of reasons: 89 o The media is usually encoded in forms that cannot be quickly 90 changed to accomodate varying bandwidth, and bandwidth 91 requirements can often be changed only in discrete, rather large 92 steps 94 o The participants may have certain specific wishes on how to 95 respond - which may not be reducing the bandwidth required by the 96 flow on which congestion is discovered 98 o The encodings are usually sensitive to packet loss, while the real 99 time requirement precludes the repair of packet loss by 100 retransmission 102 This memo describes two congestion control algorithms that together 103 are seen to give reasonable performance and reasonable (not perfect) 104 bandwidth sharing with other conferences and with TCP-using 105 applications that share the same links. 107 The signalling used consists of standard RTP timestamps [RFC3550], 108 standard RTCP feedback reports and Temporary Maximum Media Stream Bit 109 Rate Requests (TMMBR) as defined in [RFC5104] section 3.5.4. 111 1.1. Mathemathical notation conventions 113 The mathematics of this document have been transcribed from a more 114 formula-friendly format. 116 The following notational conventions are used: 118 X_bar The variable X, where X is a vector - conventionally marked by 119 a bar on top of the variable name. 121 X_hat An estimate of the true value of variable X - conventionally 122 marked by a circumflex accent on top of the variable name. 124 X(i) The "i"th value of X - conventionally marked by a subscript i. 126 [x y z] A row vector consisting of elements x, y and z. 128 X_bar^T The transpose of vector X_bar. 130 2. System model 132 The following elements are in the system: 134 o Incoming media stream 136 o Media codec - has a bandwidth control, and encodes the incoming 137 media stream into an RTP stream. 139 o RTP sender - sends the RTP stream over the network to the RTP 140 receiver. Generates the RTP timestamp. 142 o RTP receiver - receives the RTP stream, notes the time of arrival. 143 Regenerates the media stream for the recipient. 145 o RTCP sender at RTP sender - sends sender reports. 147 o RTCP sender at RTP receiver - sends receiver reports and TMMBR 148 messages. 150 o RTCP receiver at RTP sender - receives receiver reports and TMMBR 151 messages, reports these to sender side control. 153 o RTCP receiver at RTP receiver. 155 o Sender side control - takes loss rate info, round trip time info, 156 and TMMBR messages and computes a sending bitrate. 158 o Receiver side control - takes the packet arrival info at the RTP 159 receiver and decides when to send TMMBR messages. 161 Together, sender side control and receiver side control implement the 162 congestion control algorithm. 164 3. Receiver side control 166 The receive-side algorithm can be further decomposed into three 167 parts: an arrival-time filter, an over-use detector, and a remote 168 rate-control. 170 3.1. Arrival-time filter 172 This section describes an adaptive filter that continuously updates 173 estimates of network parameters based on the timing of the received 174 frames. 176 At the receiving side we are observing groups of incoming video 177 packets, where each group of packets corresponding to the same frame 178 having timestamp T(i). 180 Each frame is assigned a receive time t(i), which corresponds to the 181 time at which the whole frame has been received (ignoring any packet 182 losses). A frame is delayed relative to its predecessor if t(i)-t(i- 183 1)>T(i)-T(i-1), i.e., if the arrival time difference is larger than 184 the timestamp difference. 186 We define the (relative) inter-arrival time, d(i) as 188 d(i) = t(i)-t(i-1)-(T(i)-T(i-1)) 190 Since the time ts to send a frame of size L over a path with a 191 capacity of C is 193 ts = L/C 195 we can model the inter-arrival time as 197 L(i)-L(i-1) 198 d(i) = -------------- + w(i) =~ dL(i)/C+w(i) 199 C 201 Here, w(i) is a sample from a stochastic process W, which is a 202 function of the capacity C, the current cross traffic X(i), and the 203 current send bit rate R(i). We model W as a white Gaussian process. 204 If we are over-using the channel we expect w(i) to increase, and if a 205 queue on the network path is being emptied, w(i) will decrease; 206 otherwise the mean of w(i) will be zero. 208 Breaking out the mean of w(i) to make it zero mean, we get 210 Equation 5 212 d(i) = dL(i)/C + m(i) + v(i) 214 This is our fundamental model, where we take into account that a 215 large frame needs more time to traverse the link than a small frame, 216 thus arriving with higher relative delay. The noise term represents 217 network jitter and other delay effects not captured by the model. 219 When graphing the values for d(i) versus dL(i) on a scatterplot, we 220 find that most samples cluster around the center, and the outliers 221 are clustered along a line with average slope 1/C and zero offset. 223 When using a regular video codec, most frames are roughly the same 224 size after encoding (the central "cloud"); the exceptions are 225 I-frames (or key frames) which are typically much larger than the 226 average causing positive outliers (the I-frame itself) and negative 227 outliers (the frame after an I-frame). 229 The parameters d(i) and dL(i) are readily available for each frame i, 230 and we want to estimate C and m(i) and use those estimates to detect 231 whether or not we are over-using the bandwidth currently available. 232 These parameters are easily estimated by any adaptive filter - we are 233 using the Kalman filter. 235 Let 237 theta_bar(i) = [1/C(i) m(i)]^T 239 and call it the state of time i. We model the state evolution from 240 time i to time i+1 as 242 theta_bar(i+1) = theta_bar(i) + u_bar(i) 244 where u_bar(i) is the zero mean white Gaussian process noise with 245 covariance 247 Equation 7 249 Q(i) = E{u_bar(i) u_bar(i)^T} 251 Given equation 5 we get 253 Equation 8 255 d(i) = h_bar(i)^T theta_bar(i) + v(i) 257 h_bar(i) = [ dL(i) 1 ]^T 259 where v(i) is zero mean white Gaussian measurement noise with 260 variance var_v = sigma(v,i)^2 262 The Kalman filter recursively updates our estimate 264 theta_hat(i) = [1/C_hat(i) m_hat(i)]^T 266 as 268 z(i) = d(i) - h_bar(i)^T * theta_hat(i-1) 270 theta_hat(i) = theta_hat(i-1) + z(i) * k_bar(i) 272 E(i-1) * h_bar(i) 273 k_bar(i) = ------------------------------ 274 var_v_hat + h_bar(i)^T E(i-1)h_bar(i) 276 E(i)=(I - K_bar(i) h_bar(i)^T) * E(i-1) + Q(i) 278 I is the 2-by-2 identity matrix. 280 The variance var_v = sigma(v,i)^2 is estimated using an exponential 281 averaging filter, modified for variable sampling rate 283 var_v_hat = beta*sigma(v,i-1)^2 + (1-beta)*z(i)^2 285 beta = (1-alpha)30/(1000 * f_max) 287 where f_max = max {1/(T(j) - T(j-1))} for j in i-K+1...i is the 288 highest rate at which frames have been captured by the camera the 289 last K frames and alpha is a filter coefficient typically chosen as a 290 number in the interval [0.1, 0.001]. Since our assumption that v(i) 291 should be zero mean WGN is less accurate in some cases, we have 292 introduced an additional outlier filter around the updates of 293 var_v_hat. If z(i) > 3 var_v_hat the filter is updated with 3 294 sqrt(var_v_hat) rather than z(i). In a similar way, Q(i) is chosen 295 as a diagonal matrix with main diagonal elements given by 297 diag(Q(i)) = 30/(1000 * f_max)[10^-10 10^-2]^T 299 It is necessary to scale these filter parameters with the frame rate 300 to make the detector respond as quickly at low frame rates as at high 301 frame rates. 303 3.2. Over-use detector 305 The offset estimate m(i) is compared with a threshold gamma_1. An 306 estimate above the threshold is considered as an indication of over- 307 use. Such an indication is not enough for the detector to signal 308 over-use to the rate control subsystem. Not until over-use has been 309 detected for at least gamma_2 milliseconds and at least gamma_3 310 frames, a definitive over-use will be signaled. However, if the 311 offset estimate m(i) was decreased in the last update, over-use will 312 not be signaled even if all the above conditions are met. Similarly, 313 the opposite state, under-use, is detected when m(i) < -gamma_1. If 314 neither over-use nor under-use is detected, the detector will be in 315 the normal state. 317 3.3. Rate control 319 The rate control at the receiving side is designed to increase the 320 available bandwidth estimate A_hat as long as the detected state is 321 normal. Doing that assures that we, sooner or later, will reach the 322 available bandwidth of the channel and detect an over-use. 324 As soon as over-use has been detected the available bandwidth 325 estimate is decreased. In this way we get a recursive and adaptive 326 estimate of the available bandwidth. 328 In this design description we make the assumption that the rate 329 control subsystem is executed periodically and that this period is 330 constant. 332 The rate control subsystem has 3 states: Increase, Decrease and Hold. 333 "Increase" is the state when no congestion is detected; "Decrease" is 334 the state where congestion is detected, and "Hold" is a state that 335 waits until built-up queues have drained before going to "increase" 336 state. 338 The state transitions (with blank fields meaning "remain in state") 339 are: 341 State ----> | Hold |Increase |Decrease 342 Signal----------------------------------------- 343 v | | | 344 Over-use | Decrease |Decrease | 345 ----------------------------------------------- 346 Normal | Increase | |Hold 347 ----------------------------------------------- 348 Under-use | |Hold |Hold 349 ----------------------------------------------- 350 The subsystem starts in the increase state, where it will stay until 351 over-use or under-use has been detected by the detector subsystem. 352 On every update the available bandwidth is increased with a factor 353 which is a function of the global system response time and the 354 estimated measurement noise variance var_v_hat. The global system 355 response time is the time from an increase that causes over-use until 356 that over-use can be detected by the over-use detector. The variance 357 var_v_hat affects how responsive the Kalman filter is, and is thus 358 used as an indicator of the delay inflicted by the Kalman filter. 360 A(i) = eta*A(i-1) 361 1.001+B 362 eta(RTT, var_v_hat) = ------------------------------------------ 363 1+e^(b(d*RTT - (c1 * var_v_hat + c2))) 365 Here, B, b, d, c1 and c2 are design parameters. 367 Since the system depends on over-using the channel to verify the 368 current available bandwidth estimate, we must make sure that our 369 estimate doesn't diverge from the rate at which the sender is 370 actually sending. Thus, if the sender is unable to produce a bit 371 stream with the bit rate the receiver is asking for, the available 372 bandwidth estimate must stay within a given bound. Therefore we 373 introduce a threshold 375 A_hat(i) < 1.5 * R_hat(i) 377 where R_hat(i) is the incoming bit rate measured over a T seconds 378 window: 380 R_hat(i) = 1/T * sum(L(j)) for j from 1 to N(i) 382 N(i) is the number of frames received the past T seconds and L(j) is 383 the payload size of frame j. 385 When an over-use is detected the system transitions to the decrease 386 state, where the available bandwidth estimate is decreased to a 387 factor times the currently incoming bit rate. 389 A_hat(i) = alpha*R_hat(i) 391 alpha is typically chosen to be in the interval [0.8, 0.95]. 393 When the detector signals under-use to the rate control subsystem, we 394 know that queues in the network path are being emptied, indicating 395 that our available bandwidth estimate is lower than the actual 396 available bandwidth. Upon that signal the rate control subsystem 397 will enter the hold state, where the available bandwidth estimate 398 will be held constant while waiting for the queues to stabilize at a 399 lower level - a way of keeping the delay as low as possible. This 400 decrease of delay is wanted, and expected, immediately after the 401 estimate has been reduced due to over-use, but can also happen if the 402 cross traffic over some links is reduced. In either case we want to 403 measure the highest incoming rate during the under-use interval: 405 R_max = max{R_hat(i)} for i in 1..K 407 where K is the number of frames of under-use before returning to the 408 normal state. R_max is a measure of the actual bandwidth available 409 and is a good guess of what bit rate we should be able to transmit 410 at. Therefore the available bandwidth will be set to Rmax when we 411 transition from the hold state to the increase state. 413 4. Sender side control 415 An additional congestion controller resides at the sending side. It 416 bases its decisions on the round-trip time, packet loss and available 417 bandwidth estimates transmitted from the receiving side. 419 The available bandwidth estimates produced by the receiving side are 420 only reliable when the size of the queues along the channel are large 421 enough. If the queues are very short, over-use will only be visible 422 through packet losses, which aren't used by the receiving side 423 algorithm. 425 This algorithm is run every time a receive report arrives at the 426 sender, which will happen [[how often do we expect? and why?]]. If 427 no receive report is recieved within [[what timeout?]], the algorithm 428 will take action as if all packets in the interval have been lost. 429 [[does that make sense?]] 431 o If 2-10% of the packets have been lost since the previous report 432 from the receiver, the sender available bandwidth estimate As(i) 433 (As denotes 'sender available bandwidth') will be kept unchanged. 435 o If more than 10% of the packets have been lost a new estimate is 436 calculated as As(i)=As(i-1)(1-0.5p), where p is the loss ratio. 438 o As long as less than 2% of the packets have been lost As(i) will 439 be increased as As(i)=1.05(As(i-1)+1000) 441 The new send-side estimate is limited by the TCP Friendly Rate 442 Control formula [RFC3448] and the receive-side estimate of the 443 available bandwidth A(i): 445 8 s 446 As(i) >= ---------------------------------------------------------- 447 R*sqrt(2*b*p/3) + (t_RTO*(3*sqrt(3*b*p/8) * p * (1+32*p^2))) 449 As(i) <= A(i) 451 where b is the number of packets acknowledged by a single TCP 452 acknowledgement (set to 1 per TFRC recommendations), t_RTO is the TCP 453 retransmission timeout value in seconds (set to 4*R) and s is the 454 average packet size in bytes. 456 (The multiplication by 8 comes because TFRC is computing bandwidth in 457 bytes, while this document computes bandwidth in bits.) 459 In words: The sender-side estimate will never be larger than the 460 receiver-side estimate, and will never be lower than the estimate 461 from the TFRC formula. 463 We motivate the packet loss thresholds by noting that if we have 464 small amount of packet losses due to over-use, that amount will soon 465 increase if we don't adjust our bit rate. Therefore we will soon 466 enough reach above the 10 % threshold and adjust As(i). However if 467 the packet loss rate does not increase, the losses are probably not 468 related to self-induced channel over-use and therefore we should not 469 react on them. 471 5. Interoperability Considerations 473 There are three scenarios of interest, and one included for reference 475 o Both parties implement the algorithms described here 477 o Sender implements the algorithm described in section Section 4, 478 recipient does not implement Section 3 480 o Recipient implements the algorithm in section Section 3, sender 481 does not implement Section 4. 483 In the case where both parties implement the algorithms, we expect to 484 see most of the congestion control response to slowly varying 485 conditions happen by TMMBR messages from recipient to sender. At 486 most times, the sender will send less than the congestion-inducing 487 bandwidth limit C, and when he sends more, congestion will be 488 detected before packets are lost. 490 If sudden changes happen, packets will be lost, and the sender side 491 control will trigger, limiting traffic until the congestion becomes 492 low enough that the system switches back to the receiver-controlled 493 state. 495 In the case where sender only implements, we expect to see somewhat 496 higher loss rates and delays, but the system will still be overall 497 TCP friendly and self-adjusting; the governing term in the 498 calculation will be the TFRC formula. 500 In the case where recipient implements this algorithm and sender does 501 not, congestion will be avoided for slow changes as long as the 502 sender understands and obeys TMMBR; there will be no backoff for 503 packet-loss-inducing changes in capacity. Given that some kind of 504 congestion control is mandatory for the sender according to the TMMBR 505 spec, this case has to be reevaluated against the specific congestion 506 control implemented by the sender. 508 6. Implementation Experience 510 This algorithm has been implemented in the open-source WebRTC 511 project. 513 7. Further Work 515 This draft is offered as input to the congestion control discussion. 517 Work that can be done on this basis includes: 519 o Consideration of timing info: It may be sensible to use the 520 proposed TFRC RTP header extensions 521 [I-D.gharai-avtcore-rtp-tfrc]to carry per-packet timing 522 information, which would both give more data points and a 523 timestamp applied closer to the network interface. 525 o Considerations of cross-channel calculation: If all packets in 526 multiple streams follow the same path over the network, congestion 527 or queueing information should be considered across all packets 528 between two parties, not just per media stream. 530 o Considerations of cross-channel balancing: The decision to slow 531 down sending in a situation with multiple media streams should be 532 taken across all media streams, not per stream. 534 o Considerations of additional input: How and where packet loss 535 detected at the recipient can be added to the algorithm. 537 o Considerations of locus of control: Whether the sender or the 538 recipient is in the best position to figure out which media 539 streams it makes sense to slow down, and therefore whether one 540 should use TMMBR to slow down one channel, signal an overall 541 bandwidth change and let the sender make the decision, or signal 542 the (possibly processed) delay info and let the sender run the 543 algorithm. 545 These are matters for further work; since some of them involve 546 extensions that have not yet been standardized, this could take some 547 time, and it's important to consider when this work can be completed. 549 8. IANA Considerations 551 This document makes no request of IANA. 553 Note to RFC Editor: this section may be removed on publication as an 554 RFC. 556 9. Security Considerations 558 An attacker with the ability to insert or remove messages on the 559 connection will, of course, have the ability to mess up rate control, 560 causing people to send either too fast or too slow, and causing 561 congestion. 563 In this case, the control information is carried inside RTP, and can 564 be protected against modification or message insertion using SRTP, 565 just as for the media. Given that timestamps are carried in the RTP 566 header, which is not encrypted, this is not protected against 567 disclosure, but it seems hard to mount an attack based on timing 568 information only. 570 10. Acknowledgements 572 11. References 574 11.1. Normative References 576 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 577 Requirement Levels", BCP 14, RFC 2119, March 1997. 579 [RFC3448] Handley, M., Floyd, S., Padhye, J., and J. Widmer, "TCP 580 Friendly Rate Control (TFRC): Protocol Specification", 581 RFC 3448, January 2003. 583 [RFC3550] Schulzrinne, H., Casner, S., Frederick, R., and V. 584 Jacobson, "RTP: A Transport Protocol for Real-Time 585 Applications", STD 64, RFC 3550, July 2003. 587 [RFC5104] Wenger, S., Chandra, U., Westerlund, M., and B. Burman, 588 "Codec Control Messages in the RTP Audio-Visual Profile 589 with Feedback (AVPF)", RFC 5104, February 2008. 591 11.2. Informative References 593 [I-D.gharai-avtcore-rtp-tfrc] 594 Gharai, L. and C. Perkins, "RTP with TCP Friendly Rate 595 Control", draft-gharai-avtcore-rtp-tfrc-00 (work in 596 progress), March 2011. 598 [RFC2914] Floyd, S., "Congestion Control Principles", BCP 41, 599 RFC 2914, September 2000. 601 Authors' Addresses 603 Henrik Lundin 604 Google 605 Kungsbron 2 606 Stockholm 11122 607 Sweden 609 Stefan Holmer 610 Google 611 Kungsbron 2 612 Stockholm 11122 613 Sweden 615 Email: holmer@google.com 617 Harald Alvestrand (editor) 618 Google 619 Kungsbron 2 620 Stockholm 11122 621 Sweden 623 Email: harald@alvestrand.no