idnits 2.17.1 draft-xu-mptcp-congestion-control-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: ---------------------------------------------------------------------------- == It seems as if not all pages are separated by form feeds - found 0 form feeds but 12 pages 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 (July 4, 2014) is 3577 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 354, but not defined == Outdated reference: A later version (-05) exists of draft-khalili-mptcp-congestion-control-04 Summary: 0 errors (**), 0 flaws (~~), 5 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 July 4, 2014 4 Expires: January 2015 6 Delay-based Congestion Control for MPTCP 7 draft-xu-mptcp-congestion-control-00.txt 9 Abstract 11 This document describes the mechanism of wVegas (weighted Vegas), 12 which is a delay-based congestion control for MPTCP. The current 13 congestion control algorithm of MPTCP, LIA, achieves only course- 14 grained load balancing, since it is based on packet loss event. On 15 the contrary, wVegas adopts packet queuing delay as congestion 16 signals, thus achieving fine-grained load balancing. Compared with 17 loss-based algorithms, wVegas is more sensitive to changes of network 18 congestion and thus achieves more timely traffic shifting and quicker 19 convergence. WVegas has been implemented in the Linux Kernel and will 20 be a part of UCLouvain's MPTCP implementation. 22 Status of this Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF), its areas, and its working groups. Note that 29 other groups may also distribute working documents as 30 Internet-Drafts. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 The list of current Internet-Drafts can be accessed at 38 http://www.ietf.org/ietf/1id-abstracts.txt 40 The list of Internet-Draft Shadow Directories can be accessed at 41 http://www.ietf.org/shadow.html 43 This Internet-Draft will expire on January 4, 2015. 45 Copyright Notice 47 Copyright (c) 2014 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. Requirements Language................................... 4 64 1.2. Requirements Language................................... 4 65 2. Weighted Vegas Algorithm..................................... 6 66 3. Practical considerations..................................... 8 67 4. Discussion .................................................. 9 68 5. Security Considerations..................................... 10 69 6. IANA Considerations ........................................ 10 70 7. References ................................................. 10 71 7.1. Normative References................................... 10 72 7.2. Informative References................................. 10 74 1. Introduction 76 Performing congestion control independently on each path cannot 77 guarantee the fairness for multipath transportation. So the major 78 goal of multipath congestion control is to couple all the subflows 79 belonging to a flow in order to achieve both fairness and efficiency. 80 The current MPTCP adopts a congestion control algorithm called Linked 81 Increases algorithm [RFC6356]. It provides the ability to shift 82 traffic from more congested paths to less ones. However, it achieves 83 only course-grained load balancing, because it uses the packet losses 84 as the signal of network congestion and will shift traffic only after 85 the loss event. Other alternative congestion control algorithms, such 86 as OLIA [OLIA], have the same way to judge the congestion. These 87 proposals lack the finer-grained information related to the degree of 88 congestion. 90 In this draft, we introduce weighted Vegas (wVegas), which is a 91 delay-based multipath congestion control algorithm. Comparing to LIA 92 and OLIA, wVegas adopts packet queuing delay as congestion signals, 93 thus achieving fine-grained load balancing. [WVEGAS] 95 WVegas is developed using the network utility maximization model 96 [ADMTQM]. By solving the maximization problem, we get a general 97 framework for designing an algorithm of multipath congestion control, 98 which constitutes the Congestion Equality Principle and an 99 approximate iterative algorithm [WVEGAS]. The Congestion Equality 100 Principle illustrates that a fair and efficient traffic shifting 101 implies every flow strives to equalize the extent of congestion that 102 it perceives on all its available paths. And the approximate 103 iterative algorithm makes the solution practical in real networks. 104 The wVegas is precisely derived from the framework. 106 As the name shows, wVegas is originated from TCP-vegas [VEGAS] that 107 measures packet queuing delay to estimate the extent of network 108 congestion. TCP-vegas has two configurable parameters alpha and beta, 109 for adjusting the congestion window during the congestion avoidance 110 phase. Since the two parameters are commonly very close to each 111 other, wVegas uses only one parameter for brevity. The design 112 philosophy of wVegas is depicted as follows. First, WVegas performs 113 in the same way as TCP-vegas on each path. Second, each flow has a 114 fixed sum of parameters alpha, in spite of the number of subflows the 115 flow has. Third, wVegas adaptively adjusts the parameter alpha 116 resulting in the change of the transmission rate of the related 117 subflows so as to equalize the extent of congestion on the path. 119 WVegas has been implemented in the Linux Kernel and will be a part of 120 UCLouvain's MPTCP implementation [MPLKI]. In [VEGAS], we study the 121 traffic shifting ability of wVegas, reveal that it can guarantee the 122 intra-protocol fairness and show the domino effect which is an 123 indication of good performance. 125 1.1. Requirements Language 127 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 128 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 129 document are to be interpreted as described in [RFC2119]. 131 1.2. Requirements Language 133 Regular TCP: The standard version of TCP, which is currently 134 restricted to a single path per connection. 136 Multipath TCP (MPTCP): A modified version of the regular TCP that 137 provides the ability to simultaneously use multiple paths between 138 peers. 140 LIA: The Linked-Increases Algorithm of MPTCP. [RFC6356] 142 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP. [OLIA] 144 WVegas: Weighted Vegas, which is a delay-based multipath congestion 145 control algorithm for MPTCP. [WVEGAS] 147 Subflow (path): A single path TCP connection always belonging to a 148 MPTCP connection. 150 Expected sending rate: The best rate that a single path flow can get 151 under the current congestion window condition. 153 Actual sending rate: The actual rate that a single path flow can get 154 under the current congestion window condition. 156 Diff_r: For subflow r, the difference between Expected sending rate 157 and Actual sending rate. 159 Cwnd_r: The congestion window on a subflow r (maintained in packets). 161 Ssthresh_r: The slow start threshold of a subflow r. 163 Rtt_r: The average RTT in the last round on a subflow r. 165 Rate_r: The rate of subflow r, which is used to estimate the 166 equilibrium rate of subflow r. 168 Base_rtt_r: The RTT of a subflow r when the sub-connection is not 169 congested. 171 Alpha_r: TCP-vegas tries to keep the extra bytes between two 172 configurable parameters in a single path flow. For subflow r, we use 173 only one parameter, alpha, for brevity. 175 Total_alpha: The total bytes backlogged in the network for all 176 subflows belonging to one MPTCP flow. 178 Weight_r: The rate of subflow r divided by the total rate among all 179 subflows belonging to one MPTCP flow. 181 Gamma: When the Actual sending rate falls below the Expected sending 182 rate by the gamma threshold, TCP-vegas changes from slow start to 183 congestion avoidance phase. 185 Queue_delay_r: For subflow r, queue_delay_r records the minimal 186 queuing delay measured after the last backoff. 188 2. Weighted Vegas Algorithm 190 In this section, we introduce wVegas. WVegas is a delay-based 191 congestion control algorithm and also uses the unmodified TCP 192 behavior in the case of loss event. WVegas is an alternative for LIA, 193 the current congestion control of MPTCP. 195 The algorithm mainly applies to the congestion avoidance phase and, 196 in slow start phase, it also add a chance to enter the congestion 197 avoidance phase earlier, which is similar with the implementation of 198 the TCP-vegas [VEGAS]. The decrease of the congestion avoidance 199 phase, the fast retransmit and fast recovery algorithms are the same 200 as TCP [RFC5681]. 202 The following operations of wVegas must be performed on the end of 203 each transmission round. 205 For a subflow r, the difference between the Expected sending rate and 206 Actual sending rate is calculated as follows: 208 diff_r = (cwnd_r / base_rtt_r - cwnd_r / rtt_r) * base_rtt_r 210 If the subflow is in the slow start phase and the diff_r is larger 211 than gamma, it must enter the congestion avoidance phase. This 212 operation is inherited from TCP-vegas [VEGAS] and can be achieved by 213 setting the ssthresh_r to (cwnd_r - 1). On the other hand, if the 214 diff_r is no more than gamma in slow start phase, wVegas must act the 215 same way as TCP [RFC5681]. 217 In the congestion avoidance phase, if the diff_r is no less than 218 alpha_r, the rate_r must be updated. The weight_r and the alpha_r 219 must be tweaked before the window adjustment and the improvement of 220 the base_rtt_r accuracy. The rate_r , the weight_r and the alpha_r 221 must be calculated as follows: 223 rate_r = cwnd_r / rtt_r (1) 225 weight_r = rate_r / SUM(rate_r) (2) 227 alpha_r = weight_r * total_alpha 229 SUM(rate_r) is the total rate of all subflows belonging to one MPTCP 230 flow. After the tweak of the alpha_r, if the tweak is needed, the 231 cwnd_r must be adjusted as follows: 233 - If diff_r is larger than alpha_r, then 234 cwnd_r = cwnd_r - 1 236 - If diff_r is less than alpha_r, then 238 cwnd_r = cwnd_r + 1 240 The last task wVegas has to do is to try to drain link queues. This 241 operation is to improve the accuracy of base_rtt_r. And the specific 242 method is described in [DRLK]. The idea is to make congestion window 243 back off once detecting the queuing delay is larger than some 244 threshold, so that the bottleneck link can drain off the backlogged 245 packets. And thus all the flows involved have a chance to obtain the 246 more accurate propagation delay. 248 First, wVegas has to calculate the current queuing delay as follows: 250 queue_delay_r = rtt_r - base_rtt_r 252 If the current queuing delay is less than the saved queue_delay_r, 253 the queue_delay_r must be replaced by the current one. And if the 254 current queuing delay is two times larger than queue_delay_r, the 255 following operations must be performed: 257 cwnd_r = cwnd_r * 0.5 * base_rtt_r / rtt (3) 259 3. Practical considerations 261 In practice, it is difficult to get the RTT of a subflow r when the 262 sub-connection is not congested. WVegas should set the base_rtt_r to 263 the minimum of all the measured round trip times. The total_alpha 264 should be implemented as a configurable parameter. 266 Equation (1) and (2) imply that the rate and the weight are floating 267 point values. However, in many kernels, floating point operations are 268 disabled. There is an easy way to approximate the above calculations 269 using integer arithmetic. 271 Let rate_scale be an integer. When computing the rate, use cwnd_r * 272 rate_scale instead of cwnd_r and the related operations can be done 273 in integer arithmetic. The rate_r should be calculated as follows: 275 rate_r = cwnd_r * rate_scale / rtt_r 277 The rate_scale implies the precision we need for computing the rate. 278 With this change, the rate can be stored as an integer variable. 279 Besides, when we need to calculate the sum rate of all subflows 280 belonging to one flow, the operations can be done in integer 281 arithmetic. 283 When updating the weight_r, we also need a weight_scale to avoid 284 floating point operations. So the weight_r should be computed as 285 follows: 287 weight_r = rate_r * weight_scale / SUM(rate_r) 289 The weight_scale supplies a similar function with rate_scale. With 290 the weight_scale, alpha_r can be much more accurate. But it also need 291 scale down as follows: 293 alpha_r = weight_r * total_alpha / weight_scale 295 For the sake of brevity, we combine the rate_scale and weight_scale 296 to one scale parameter. We name it wvegas_scale. It would be better 297 to set the wvegas_scale as a power of two, which allows faster shift 298 operations rather than multiplication and division. 300 In equation (3), the multiplication by 0.5 can be implemented by 301 shift operation. 303 4. Discussion 305 Congestion Equality Principle shows that a fair and efficient traffic 306 shifting implies that every flow strives to equalize the extent of 307 congestion that it perceives on all its available paths. This 308 principle has been proved in [WVEGAS]. By instantiating the 309 approximate iterative algorithm, weighted Vegas (wVegas), a delay- 310 based algorithm for multipath congestion control, was developed, 311 which uses packet queuing delay as congestion signals, thus achieving 312 fine-grained load balancing. Our simulations show that, compared with 313 loss-based algorithms, wVegas is more sensitive to changes of network 314 congestion and thus achieves more timely traffic shifting and quicker 315 convergence. Additionally, as it occupies fewer link buffers, wVegas 316 rarely causes packet losses and shows better intra-protocol fairness. 318 5. Security Considerations 320 Security considerations discussed in [RFC6181] and [RFC6356] are to 321 be taken into account. 323 6. IANA Considerations 325 This document has no actions for IANA. 327 7. References 329 7.1. Normative References 331 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 332 Requirement Levels", BCP 14, RFC 2119, March 1997. 334 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 335 Control", RFC 5681, September 2009. 337 7.2. Informative References 339 [DRLK] D. Leith, R. Shorten, G. McCullagh, L. Dunn, and F. Baker, 340 "Making Available Base-RTT for Use in Congestion Control 341 Applications", IEEE Communications Letters, vol. 12, no. 6, 342 pp. 429-431, Jun. 2008. 344 [RFC6356] Raiciu, C., Handley, M., and D. Wischik, "Coupled 345 Congestion Control for Multipath Transport Protocols", RFC 346 6356, October 2011. 348 [OLIA] R. Khalili, N. Gast, M. Popovic, J.-Y. Le Boudec, 349 "Opportunistic Linked-Increases Congestion Control 350 Algorithm for MPTCP", draft-khalili-mptcp-congestion- 351 control-04. 353 [MPLKI] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux kernel 354 implementation," 2013 [Online]. Available: 355 http://mptcp.info.ucl.ac.be/. 357 [WVEGAS] Y. Cao, M. Xu, X. Fu, "Delay-based congestion control for 358 multipath TCP", ICNP 2012. 360 [ADMTQM] S. H. Low, "A Duality Model of TCP and Queue Management 361 Algorithms", IEEE/ACM Transactions on Networking, 362 11(4):525-536, Aug. 2003. 364 [VEGAS] L. S. Brakmo, S. W. O'Malley, and L. L. Peterson, "TCP 365 Vegas: new techniques for congestion detection and 366 avoidance, " in Proc. of ACM SIGCOMM, 1994, pp. 24-35. 368 [RFC6181] Bagnulo, M., "Threat Analysis for TCP Extensions for 369 Multipath Operation with Multiple Addresses", RFC 6181, 370 March 2011. 372 Authors' Addresses 374 Mingwei Xu 375 Tsinghua University 376 Department of Computer Science, Tsinghua University 377 Beijing 100084 378 P.R.China 380 Phone: +86-10-6278-5822 381 EMail: xmw@cernet.edu.cn 383 Yu Cao 384 Tsinghua University 385 Department of Computer Science, Tsinghua University 386 Beijing 100084 387 P.R.China 389 Phone: +86-185-3927-5620 390 Email: caoyu08@csnet1.cs.tsinghua.edu.cn 392 Enhuan Dong 393 Tsinghua University 394 Department of Computer Science, Tsinghua University 395 Beijing 100084 396 P.R.China 398 Phone: +86-183-1105-7156 399 Email: deh13@mails.tsinghua.edu.cn