idnits 2.17.1 draft-xu-mptcp-congestion-control-01.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 (January 5, 2015) is 3392 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) == Missing Reference: 'Online' is mentioned on line 363, but not defined == Outdated reference: A later version (-04) exists of draft-walid-mptcp-congestion-control-01 Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Multipath TCP Mingwei Xu 2 Internet Draft Tsinghua University 3 Intended status: Standard Track Yu Cao 4 Expires: July 2015 NDSC, China 5 Enhuan Dong 6 Tsinghua University 7 January 5, 2015 9 Delay-based Congestion Control for MPTCP 10 draft-xu-mptcp-congestion-control-01.txt 12 Abstract 14 This document describes the mechanism of wVegas (weighted Vegas), 15 which is a delay-based congestion control for MPTCP. The current 16 congestion control algorithm of MPTCP, LIA, achieves only course- 17 grained load balancing, since it is based on packet loss event. On 18 the contrary, wVegas adopts packet queuing delay as congestion 19 signals, thus achieving fine-grained load balancing. Compared with 20 loss-based algorithms, wVegas is more sensitive to changes of network 21 congestion and thus achieves more timely traffic shifting and quicker 22 convergence. WVegas has been implemented in the Linux Kernel and is 23 part of the UCLouvain's MPTCP implementation now. 25 Status of this Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as 33 Internet-Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/ietf/1id-abstracts.txt 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html 45 This Internet-Draft will expire on July 5, 2015. 47 Copyright Notice 49 Copyright (c) 2015 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction ................................................ 3 65 1.1. Requirements Language................................... 4 66 1.2. Requirements Language................................... 4 67 2. Weighted Vegas Algorithm..................................... 6 68 3. Practical considerations..................................... 8 69 4. Discussion .................................................. 9 70 5. Security Considerations..................................... 10 71 6. IANA Considerations ........................................ 10 72 7. References ................................................. 10 73 7.1. Normative References................................... 10 74 7.2. Informative References................................. 10 76 1. Introduction 78 Performing congestion control independently on each path cannot 79 guarantee the fairness for multipath transportation. So the major 80 goal of multipath congestion control is to couple all the subflows 81 belonging to a flow in order to achieve both fairness and efficiency. 82 The current MPTCP adopts a congestion control algorithm called Linked 83 Increases algorithm [RFC6356]. It provides the ability to shift 84 traffic from more congested paths to less ones. However, it achieves 85 only course-grained load balancing, since it uses the packet losses 86 as the signal of network congestion and will shift traffic only after 87 the loss event. Other alternative congestion control algorithms, such 88 as OLIA [OLIA] or Balia [BALIA], have the same way to judge the 89 congestion. These proposals lack the finer-grained information 90 related to the degree of congestion. 92 In this draft, we introduce weighted Vegas (wVegas), which is a 93 delay-based multipath congestion control algorithm. Comparing to LIA, 94 OLIA and Balia wVegas adopts packet queuing delay as congestion 95 signals, thus achieving fine-grained load balancing. [WVEGAS] 97 WVegas is developed using the network utility maximization model 98 [ADMTQM]. By solving the maximization problem, we get a general 99 framework for designing an algorithm of multipath congestion control, 100 which constitutes the Congestion Equality Principle and an 101 approximate iterative algorithm [WVEGAS]. The Congestion Equality 102 Principle illustrates that a fair and efficient traffic shifting 103 implies every flow strives to equalize the extent of congestion that 104 it perceives on all its available paths. And the approximate 105 iterative algorithm makes the solution practical in real networks. 106 The wVegas is precisely derived from the framework. 108 As the name shows, wVegas is originated from TCP-vegas [VEGAS] that 109 measures packet queuing delay to estimate the extent of network 110 congestion. TCP-vegas has two configurable parameters alpha and beta, 111 for adjusting the congestion window during the congestion avoidance 112 phase. Since the two parameters are commonly very close to each 113 other, wVegas uses only one parameter for brevity. The design 114 philosophy of wVegas is depicted as follows. First, WVegas performs 115 in the same way as TCP-vegas on each path. Second, each flow has a 116 fixed sum of parameters alpha, in spite of the number of subflows the 117 flow has. Third, wVegas adaptively adjusts the parameter alpha 118 resulting in the change of the transmission rate of the related 119 subflows so as to equalize the extent of congestion on the path. 121 WVegas has been implemented in the Linux Kernel and is part of 122 UCLouvain's MPTCP implementation now [MPLKI]. In [VEGAS], we study 123 the traffic shifting ability of wVegas, reveal that it can guarantee 124 the intra-protocol fairness and show the domino effect which is an 125 indication of good performance. 127 1.1. Requirements Language 129 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 130 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 131 document are to be interpreted as described in [RFC2119]. 133 1.2. Requirements Language 135 Regular TCP: The standard version of TCP, which is currently 136 restricted to a single path per connection. 138 Multipath TCP (MPTCP): A modified version of the regular TCP that 139 provides the ability to simultaneously use multiple paths between 140 peers. 142 LIA: The Linked-Increases Algorithm of MPTCP. [RFC6356] 144 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP. [OLIA] 146 Balia: Balanced Linked Adaptation Congestion Control Algorithm for 147 MPTCP [BALIA] 149 WVegas: Weighted Vegas, which is a delay-based multipath congestion 150 control algorithm for MPTCP. [WVEGAS] 152 Subflow (path): A single path TCP connection always belonging to a 153 MPTCP connection. 155 Expected sending rate: The best rate that a single path flow can get 156 under the current congestion window condition. 158 Actual sending rate: The actual rate that a single path flow can get 159 under the current congestion window condition. 161 Diff_r: For subflow r, the difference between Expected sending rate 162 and Actual sending rate. 164 Cwnd_r: The congestion window on a subflow r (maintained in packets). 166 Ssthresh_r: The slow start threshold of a subflow r. 168 Rtt_r: The average RTT in the last round on a subflow r. 170 Rate_r: The rate of subflow r, which is used to estimate the 171 equilibrium rate of subflow r. 173 Base_rtt_r: The RTT of a subflow r when the sub-connection is not 174 congested. 176 Alpha_r: TCP-vegas tries to keep the extra bytes between two 177 configurable parameters in a single path flow. For subflow r, we use 178 only one parameter, alpha, for brevity. 180 Total_alpha: The total bytes backlogged in the network for all 181 subflows belonging to one MPTCP flow. 183 Weight_r: The rate of subflow r divided by the total rate among all 184 subflows belonging to one MPTCP flow. 186 Gamma: When the Actual sending rate falls below the Expected sending 187 rate by the gamma threshold, TCP-vegas changes from slow start to 188 congestion avoidance phase. 190 Queue_delay_r: For subflow r, queue_delay_r records the minimal 191 queuing delay measured after the last backoff. 193 2. Weighted Vegas Algorithm 195 In this section, we introduce wVegas. WVegas is a delay-based 196 congestion control algorithm and also uses the unmodified TCP 197 behavior in the case of loss event. WVegas is an alternative for LIA, 198 the current congestion control of MPTCP. 200 The algorithm mainly applies to the congestion avoidance phase and, 201 in slow start phase, it also add a chance to enter the congestion 202 avoidance phase earlier, which is similar with the implementation of 203 the TCP-vegas [VEGAS]. The decrease of the congestion avoidance 204 phase, the fast retransmit and fast recovery algorithms are the same 205 as TCP [RFC5681]. 207 The following operations of wVegas must be performed on the end of 208 each transmission round. 210 For a subflow r, the difference between the Expected sending rate and 211 Actual sending rate is calculated as follows: 213 diff_r = (cwnd_r / base_rtt_r - cwnd_r / rtt_r) * base_rtt_r 215 If the subflow is in the slow start phase and the diff_r is larger 216 than gamma, it must enter the congestion avoidance phase. This 217 operation is inherited from TCP-vegas [VEGAS] and can be achieved by 218 setting the ssthresh_r to (cwnd_r - 1). On the other hand, if the 219 diff_r is no more than gamma in slow start phase, wVegas must act the 220 same way as TCP [RFC5681]. 222 In the congestion avoidance phase, if the diff_r is no less than 223 alpha_r, the rate_r must be updated. The weight_r and the alpha_r 224 must be tweaked before the window adjustment and the improvement of 225 the base_rtt_r accuracy. The rate_r , the weight_r and the alpha_r 226 must be calculated as follows: 228 rate_r = cwnd_r / rtt_r (1) 230 weight_r = rate_r / SUM(rate_r) (2) 232 alpha_r = weight_r * total_alpha 234 SUM(rate_r) is the total rate of all subflows belonging to one MPTCP 235 flow. After the tweak of the alpha_r, if the tweak is needed, the 236 cwnd_r must be adjusted as follows: 238 - If diff_r is larger than alpha_r, then 239 cwnd_r = cwnd_r - 1 241 - If diff_r is less than alpha_r, then 243 cwnd_r = cwnd_r + 1 245 The last task wVegas has to do is to try to drain link queues. This 246 operation is to improve the accuracy of base_rtt_r. And the specific 247 method is described in [DRLK]. The idea is to make congestion window 248 back off once detecting the queuing delay is larger than some 249 threshold, so that the bottleneck link can drain off the backlogged 250 packets. And thus all the flows involved have a chance to obtain the 251 more accurate propagation delay. 253 First, wVegas has to calculate the current queuing delay as follows: 255 queue_delay_r = rtt_r - base_rtt_r 257 If the current queuing delay is less than the saved queue_delay_r, 258 the queue_delay_r must be replaced by the current one. And if the 259 current queuing delay is two times larger than queue_delay_r, the 260 following operations must be performed: 262 cwnd_r = cwnd_r * 0.5 * base_rtt_r / rtt (3) 264 3. Practical considerations 266 In practice, it is difficult to get the RTT of a subflow r when the 267 sub-connection is not congested. WVegas should set the base_rtt_r to 268 the minimum of all the measured round trip times. The total_alpha 269 should be implemented as a configurable parameter. 271 Equation (1) and (2) imply that the rate and the weight are floating 272 point values. However, in many kernels, floating point operations are 273 disabled. There is an easy way to approximate the above calculations 274 using integer arithmetic. 276 Let rate_scale be an integer. When computing the rate, use cwnd_r * 277 rate_scale instead of cwnd_r and the related operations can be done 278 in integer arithmetic. The rate_r should be calculated as follows: 280 rate_r = cwnd_r * rate_scale / rtt_r 282 The rate_scale implies the precision we need for computing the rate. 283 With this change, the rate can be stored as an integer variable. 284 Besides, when we need to calculate the sum rate of all subflows 285 belonging to one flow, the operations can be done in integer 286 arithmetic. 288 When updating the weight_r, we also need a weight_scale to avoid 289 floating point operations. So the weight_r should be computed as 290 follows: 292 weight_r = rate_r * weight_scale / SUM(rate_r) 294 The weight_scale supplies a similar function with rate_scale. With 295 the weight_scale, alpha_r can be much more accurate. But it also need 296 scale down as follows: 298 alpha_r = weight_r * total_alpha / weight_scale 300 For the sake of brevity, we combine the rate_scale and weight_scale 301 to one scale parameter. We name it wvegas_scale. It would be better 302 to set the wvegas_scale as a power of two, which allows faster shift 303 operations rather than multiplication and division. 305 In equation (3), the multiplication by 0.5 can be implemented by 306 shift operation. 308 4. Discussion 310 Congestion Equality Principle shows that a fair and efficient traffic 311 shifting implies that every flow strives to equalize the extent of 312 congestion that it perceives on all its available paths. This 313 principle has been proved in [WVEGAS]. By instantiating the 314 approximate iterative algorithm, weighted Vegas (wVegas), a delay- 315 based algorithm for multipath congestion control, was developed, 316 which uses packet queuing delay as congestion signals, thus achieving 317 fine-grained load balancing. Our simulations show that, compared with 318 loss-based algorithms, wVegas is more sensitive to changes of network 319 congestion and thus achieves more timely traffic shifting and quicker 320 convergence. Additionally, as it occupies fewer link buffers, wVegas 321 rarely causes packet losses and shows better intra-protocol fairness. 323 5. Security Considerations 325 Security considerations discussed in [RFC6181] and [RFC6356] are to 326 be taken into account. 328 6. IANA Considerations 330 This document has no actions for IANA. 332 7. References 334 7.1. Normative References 336 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 337 Requirement Levels", BCP 14, RFC 2119, March 1997. 339 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 340 Control", RFC 5681, September 2009. 342 7.2. Informative References 344 [DRLK] D. Leith, R. Shorten, G. McCullagh, L. Dunn, and F. Baker, 345 "Making Available Base-RTT for Use in Congestion Control 346 Applications", IEEE Communications Letters, vol. 12, no. 6, 347 pp. 429-431, Jun. 2008. 349 [RFC6356] Raiciu, C., Handley, M., and D. Wischik, "Coupled 350 Congestion Control for Multipath Transport Protocols", RFC 351 6356, October 2011. 353 [OLIA] R. Khalili, N. Gast, M. Popovic, J.-Y. Le Boudec, 354 "Opportunistic Linked-Increases Congestion Control 355 Algorithm for MPTCP", draft-khalili-mptcp-congestion- 356 control-05. 358 [BALIA] A. Walid, Q. Peng, J. Hwang, S. Low, "Balanced Linked 359 Adaptation Congestion Control Algorithm for MPTCP", draft- 360 walid-mptcp-congestion-control-01. 362 [MPLKI] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux kernel 363 implementation," 2013 [Online]. Available: 364 http://mptcp.info.ucl.ac.be/. 366 [WVEGAS] Y. Cao, M. Xu, X. Fu, "Delay-based congestion control for 367 multipath TCP", ICNP 2012. 369 [ADMTQM] S. H. Low, "A Duality Model of TCP and Queue Management 370 Algorithms", IEEE/ACM Transactions on Networking, 371 11(4):525-536, Aug. 2003. 373 [VEGAS] L. S. Brakmo, S. W. O'Malley, and L. L. Peterson, "TCP 374 Vegas: new techniques for congestion detection and 375 avoidance, " in Proc. of ACM SIGCOMM, 1994, pp. 24-35. 377 [RFC6181] Bagnulo, M., "Threat Analysis for TCP Extensions for 378 Multipath Operation with Multiple Addresses", RFC 6181, 379 March 2011. 381 Authors' Addresses 383 Mingwei Xu 384 Tsinghua University 385 Department of Computer Science, Tsinghua University 386 Beijing 100084 387 P.R.China 389 Phone: +86-10-6278-5822 390 EMail: xmw@cernet.edu.cn 392 Yu Cao 393 NDSC 394 National Digital Switching System Engineering and Technological 395 Research Center 396 Zhengzhou 450002 397 P.R.China 399 Email: caoyu08@tsinghua.org.cn 401 Enhuan Dong 402 Tsinghua University 403 Department of Computer Science, Tsinghua University 404 Beijing 100084 405 P.R.China 407 Email: deh13@mails.tsinghua.edu.cn