idnits 2.17.1 draft-xu-mptcp-congestion-control-03.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 4, 2016) is 3034 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 365, but not defined == Outdated reference: A later version (-04) exists of draft-walid-mptcp-congestion-control-03 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 2016 NDSC, China 5 Enhuan Dong 6 Tsinghua University 7 January 4, 2016 9 Delay-based Congestion Control for MPTCP 10 draft-xu-mptcp-congestion-control-03.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 the changes of 21 network congestion and thus achieves more timely traffic shifting and 22 quicker convergence. WVegas has been implemented in the Linux Kernel 23 and is 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 4, 2016. 47 Copyright Notice 49 Copyright (c) 2016 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. Terminology ............................................ 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, which is more sensitive to the changes of network 96 congestion, thus achieving fine-grained load balancing. [WVEGAS] 98 WVegas is developed using the network utility maximization model 99 [ADMTQM]. By solving the maximization problem, we get a general 100 framework for designing an algorithm of multipath congestion control, 101 which constitutes the Congestion Equality Principle and an 102 approximate iterative algorithm [WVEGAS]. The Congestion Equality 103 Principle illustrates that a fair and efficient traffic shifting 104 implies every flow strives to equalize the extent of congestion that 105 it perceives on all its available paths. And the approximate 106 iterative algorithm makes the solution practical in real networks. 107 The wVegas is precisely derived from the framework. 109 As the name shows, wVegas is originated from TCP-vegas [VEGAS] that 110 measures packet queuing delay to estimate the extent of network 111 congestion. TCP-vegas has two configurable parameters alpha and beta, 112 for adjusting the congestion window during the congestion avoidance 113 phase. Since the two parameters are commonly very close to each 114 other, wVegas uses only one parameter for brevity. The design 115 philosophy of wVegas is depicted as follows. First, WVegas performs 116 in the same way as TCP-vegas on each path. Second, each flow has a 117 fixed sum of parameters alpha, in spite of the number of subflows the 118 flow has. Third, wVegas adaptively adjusts the parameter alpha 119 resulting in the change of the transmission rate of the related 120 subflows so as to equalize the extent of congestion on the path. 122 WVegas has been implemented in the Linux Kernel and is part of 123 UCLouvain's MPTCP implementation now [MPLKI]. In [VEGAS], we study 124 the traffic shifting ability of wVegas, reveal that it can guarantee 125 the intra-protocol fairness and show the domino effect which is an 126 indication of good performance. 128 1.1. Requirements Language 130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 132 document are to be interpreted as described in [RFC2119]. 134 1.2. Terminology 136 Regular TCP: The standard version of TCP, which is currently 137 restricted to a single path per connection. 139 Multipath TCP (MPTCP): A modified version of the regular TCP that 140 provides the ability to simultaneously use multiple paths between 141 peers. 143 LIA: The Linked-Increases Algorithm of MPTCP. [RFC6356] 145 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP. [OLIA] 147 Balia: Balanced Linked Adaptation Congestion Control Algorithm for 148 MPTCP [BALIA] 150 WVegas: Weighted Vegas, which is a delay-based multipath congestion 151 control algorithm for MPTCP. [WVEGAS] 153 Subflow (path): A single path TCP connection always belonging to a 154 MPTCP connection. 156 Expected sending rate: The best rate that a single path flow can get 157 under the current congestion window condition. 159 Actual sending rate: The actual rate that a single path flow can get 160 under the current congestion window condition. 162 Diff_r: For subflow r, the difference between Expected sending rate 163 and Actual sending rate. 165 Cwnd_r: The congestion window on a subflow r (maintained in packets). 167 Ssthresh_r: The slow start threshold of a subflow r. 169 Rtt_r: The average RTT in the last round on a subflow r. 171 Rate_r: The rate of subflow r, which is used to estimate the 172 equilibrium rate of subflow r. 174 Base_rtt_r: The RTT of a subflow r when the sub-connection is not 175 congested. 177 Alpha_r: TCP-vegas tries to keep the extra bytes between two 178 configurable parameters in a single path flow. For subflow r, we use 179 only one parameter, alpha, for brevity. 181 Total_alpha: The total bytes backlogged in the network for all 182 subflows belonging to one MPTCP flow. 184 Weight_r: The rate of subflow r divided by the total rate among all 185 subflows belonging to one MPTCP flow. 187 Gamma: When the Actual sending rate falls below the Expected sending 188 rate by the gamma threshold, TCP-vegas changes from slow start to 189 congestion avoidance phase. 191 Queue_delay_r: For subflow r, queue_delay_r records the minimal 192 queuing delay measured after the last backoff. 194 2. Weighted Vegas Algorithm 196 In this section, we introduce wVegas. WVegas is a delay-based 197 congestion control algorithm and also uses the unmodified TCP 198 behavior in the case of loss event. WVegas is an alternative for LIA, 199 the current congestion control of MPTCP. 201 The algorithm mainly applies to the congestion avoidance phase and, 202 in slow start phase, it also add a chance to enter the congestion 203 avoidance phase earlier, which is similar with the implementation of 204 the TCP-vegas [VEGAS]. The decrease of the congestion avoidance 205 phase, the fast retransmit and fast recovery algorithms are the same 206 as TCP [RFC5681]. 208 The following operations of wVegas must be performed on the end of 209 each transmission round. 211 For a subflow r, the difference between the Expected sending rate and 212 Actual sending rate is calculated as follows: 214 diff_r = (cwnd_r / base_rtt_r - cwnd_r / rtt_r) * base_rtt_r 216 If the subflow is in the slow start phase and the diff_r is larger 217 than gamma, it must enter the congestion avoidance phase. This 218 operation is inherited from TCP-vegas [VEGAS] and can be achieved by 219 setting the ssthresh_r to (cwnd_r - 1). On the other hand, if the 220 diff_r is no more than gamma in slow start phase, wVegas must act the 221 same way as TCP [RFC5681]. 223 In the congestion avoidance phase, if the diff_r is no less than 224 alpha_r, the rate_r must be updated. The weight_r and the alpha_r 225 must be tweaked before the window adjustment and the improvement of 226 the base_rtt_r accuracy. The rate_r , the weight_r and the alpha_r 227 must be calculated as follows: 229 rate_r = cwnd_r / rtt_r (1) 231 weight_r = rate_r / SUM(rate_r) (2) 233 alpha_r = weight_r * total_alpha 235 SUM(rate_r) is the total rate of all subflows belonging to one MPTCP 236 flow. After the tweak of the alpha_r, if the tweak is needed, the 237 cwnd_r must be adjusted as follows: 239 - If diff_r is larger than alpha_r, then 240 cwnd_r = cwnd_r - 1 242 - If diff_r is less than alpha_r, then 244 cwnd_r = cwnd_r + 1 246 The last task wVegas has to do is to try to drain link queues. This 247 operation is to improve the accuracy of base_rtt_r. And the specific 248 method is described in [DRLK]. The idea is to make congestion window 249 back off once detecting the queuing delay is larger than some 250 threshold, so that the bottleneck link can drain off the backlogged 251 packets. And thus all the flows involved have a chance to obtain the 252 more accurate propagation delay. 254 First, wVegas has to calculate the current queuing delay as follows: 256 queue_delay_r = rtt_r - base_rtt_r 258 If the current queuing delay is less than the saved queue_delay_r, 259 the queue_delay_r must be replaced by the current one. And if the 260 current queuing delay is two times larger than queue_delay_r, the 261 following operations must be performed: 263 cwnd_r = cwnd_r * 0.5 * base_rtt_r / rtt (3) 265 3. Practical considerations 267 In practice, it is difficult to get the RTT of a subflow r when the 268 sub-connection is not congested. WVegas should set the base_rtt_r to 269 the minimum of all the measured round trip times. The total_alpha 270 should be implemented as a configurable parameter. 272 Equation (1) and (2) imply that the rate and the weight are floating 273 point values. However, in many kernels, floating point operations are 274 disabled. There is an easy way to approximate the above calculations 275 using integer arithmetic. 277 Let rate_scale be an integer. When computing the rate, use cwnd_r * 278 rate_scale instead of cwnd_r and the related operations can be done 279 in integer arithmetic. The rate_r should be calculated as follows: 281 rate_r = cwnd_r * rate_scale / rtt_r 283 The rate_scale implies the precision we need for computing the rate. 284 With this change, the rate can be stored as an integer variable. 285 Besides, when we need to calculate the sum rate of all subflows 286 belonging to one flow, the operations can be done in integer 287 arithmetic. 289 When updating the weight_r, we also need a weight_scale to avoid 290 floating point operations. So the weight_r should be computed as 291 follows: 293 weight_r = rate_r * weight_scale / SUM(rate_r) 295 The weight_scale supplies a similar function with rate_scale. With 296 the weight_scale, alpha_r can be much more accurate. But it also need 297 scale down as follows: 299 alpha_r = weight_r * total_alpha / weight_scale 301 For the sake of brevity, we combine the rate_scale and weight_scale 302 to one scale parameter. We name it wvegas_scale. It would be better 303 to set the wvegas_scale as a power of two, which allows faster shift 304 operations rather than multiplication and division. 306 In equation (3), the multiplication by 0.5 can be implemented by 307 shift operation. 309 4. Discussion 311 Congestion Equality Principle shows that a fair and efficient traffic 312 shifting implies that every flow strives to equalize the extent of 313 congestion that it perceives on all its available paths. This 314 principle has been proved in [WVEGAS]. By instantiating the 315 approximate iterative algorithm, weighted Vegas (wVegas), a delay- 316 based algorithm for multipath congestion control, was developed, 317 which uses packet queuing delay as congestion signals, thus achieving 318 fine-grained load balancing. Our simulations show that, compared with 319 loss-based algorithms, wVegas is more sensitive to the changes of 320 network congestion and achieves more timely traffic shifting and 321 quicker convergence. Additionally, as it occupies fewer link buffers, 322 wVegas rarely causes packet losses and shows better intra-protocol 323 fairness. 325 5. Security Considerations 327 Security considerations discussed in [RFC6181] and [RFC6356] are to 328 be taken into account. 330 6. IANA Considerations 332 This document has no actions for IANA. 334 7. References 336 7.1. Normative References 338 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 339 Requirement Levels", BCP 14, RFC 2119, March 1997. 341 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 342 Control", RFC 5681, September 2009. 344 7.2. Informative References 346 [DRLK] D. Leith, R. Shorten, G. McCullagh, L. Dunn, and F. Baker, 347 "Making Available Base-RTT for Use in Congestion Control 348 Applications", IEEE Communications Letters, vol. 12, no. 6, 349 pp. 429-431, Jun. 2008. 351 [RFC6356] Raiciu, C., Handley, M., and D. Wischik, "Coupled 352 Congestion Control for Multipath Transport Protocols", RFC 353 6356, October 2011. 355 [OLIA] R. Khalili, N. Gast, M. Popovic, J.-Y. Le Boudec, 356 "Opportunistic Linked-Increases Congestion Control 357 Algorithm for MPTCP", draft-khalili-mptcp-congestion- 358 control-05. 360 [BALIA] A. Walid, Q. Peng, J. Hwang, S. Low, "Balanced Linked 361 Adaptation Congestion Control Algorithm for MPTCP", draft- 362 walid-mptcp-congestion-control-03. 364 [MPLKI] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux kernel 365 implementation," 2013 [Online]. Available: 366 http://mptcp.info.ucl.ac.be/. 368 [WVEGAS] Y. Cao, M. Xu, X. Fu, "Delay-based congestion control for 369 multipath TCP", ICNP 2012. 371 [ADMTQM] S. H. Low, "A Duality Model of TCP and Queue Management 372 Algorithms", IEEE/ACM Transactions on Networking, 373 11(4):525-536, Aug. 2003. 375 [VEGAS] L. S. Brakmo, S. W. O'Malley, and L. L. Peterson, "TCP 376 Vegas: new techniques for congestion detection and 377 avoidance, " in Proc. of ACM SIGCOMM, 1994, pp. 24-35. 379 [RFC6181] Bagnulo, M., "Threat Analysis for TCP Extensions for 380 Multipath Operation with Multiple Addresses", RFC 6181, 381 March 2011. 383 Authors' Addresses 385 Mingwei Xu 386 Tsinghua University 387 Department of Computer Science, Tsinghua University 388 Beijing 100084 389 P.R.China 391 Phone: +86-10-6278-5822 392 EMail: xmw@cernet.edu.cn 394 Yu Cao 395 NDSC 396 National Digital Switching System Engineering and Technological 397 Research Center 398 Zhengzhou 450002 399 P.R.China 401 Email: caoyu08@tsinghua.org.cn 403 Enhuan Dong 404 Tsinghua University 405 Department of Computer Science, Tsinghua University 406 Beijing 100084 407 P.R.China 409 Email: deh13@mails.tsinghua.edu.cn