idnits 2.17.1 draft-khalili-mptcp-congestion-control-05.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 : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([4], [9,11], 8], 7,, [5,6,), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 284 has weird spacing: '...optimal resou...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 4, 2014) is 3578 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: '1' is mentioned on line 138, but not defined -- Looks like a reference, but probably isn't: 'Online' on line 430 ** Downref: Normative reference to an Informational RFC: RFC 6182 (ref. '3') Summary: 4 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Multipath TCP Ramin Khalili 3 INTERNET-DRAFT T-Labs/TU-Berlin 4 Intended Status: Standard Track Nicolas Gast 5 Expires: January 5, 2015 Miroslav Popovic 6 Jean-Yves Le Boudec 7 EPFL-LCA2 8 July 4, 2014 10 Opportunistic Linked-Increases Congestion Control Algorithm for MPTCP 11 draft-khalili-mptcp-congestion-control-05 13 Abstract 15 This document describes the mechanism of OLIA, the "Opportunistic 16 Linked Increases Algorithm". OLIA is a congestion control algorithm 17 for MPTCP. The current congestion control algorithm of MPTCP, LIA 18 [4], forces a tradeoff between optimal congestion balancing and 19 responsiveness. OLIA's design departs from this tradeoff and provide 20 these properties simultaneously. Hence, it solves the identified 21 performance problems with LIA while retaining non-flappiness and 22 responsiveness behavior of LIA, as shown by different studies [5, 6, 23 7, 8]. OLIA is now part of the UCLouvain's MPTCP implementation [9, 24 11]. 26 Status of this Memo 28 This Internet-Draft is submitted to IETF in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF), its areas, and its working groups. Note that 33 other groups may also distribute working documents as 34 Internet-Drafts. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on January 5, 2015. 43 The list of current Internet-Drafts can be accessed at 44 http://www.ietf.org/1id-abstracts.html 46 The list of Internet-Draft Shadow Directories can be accessed at 47 http://www.ietf.org/shadow.html 49 Copyright and License Notice 51 Copyright (c) 2014 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 67 1.1 Requirements Language . . . . . . . . . . . . . . . . . . . 4 68 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 69 2 The set of best paths, paths with maximum windows, and 70 collected paths . . . . . . . . . . . . . . . . . . . . . . . . 5 71 3 Opportunistic Linked-Increases Algorithm . . . . . . . . . . . . 6 72 4 Practical considerations . . . . . . . . . . . . . . . . . . . . 8 73 5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 74 6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 75 6.1 Normative References . . . . . . . . . . . . . . . . . . . . 9 76 6.2 Informative References . . . . . . . . . . . . . . . . . . . 9 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 79 1 Introduction 81 The current MPTCP implementation uses a congestion control algorithm 82 called LIA, the "Linked-Increases" algorithm [4]. The design of LIA 83 forces a tradeoff between optimal congestion balancing and 84 responsiveness. Hence, to provide good responsiveness, LIA's current 85 implementation must depart from optimal congestion balancing. This 86 leads to important performance issues (refer to [5] and [6]): (i) in 87 some scenarios upgrading TCP users to MPTCP results in a significant 88 drop in the aggregate throughput in the network without any benefit 89 for anybody; and (ii) MPTCP users can be excessively aggressive 90 toward TCP users. 92 In this draft, we introduce OLIA, the "opportunistic linked increases 93 algorithm", as an alternative to LIA. Contrary to LIA, OLIA's design 94 is not based on a trade-off between responsiveness and optimal 95 congestion balancing; it can provide both simultaneously [5]. 97 Similarly to LIA, OLIA couples the additive increases and uses 98 unmodified TCP behavior in the case of a loss. The difference between 99 LIA and OLIA is in the increase part. OLIA is an adaptation of TCP 100 New Reno to support multiple paths. OLIA's increase part, Equation 101 (1), has two terms: 103 - The first term is an adaptation of the increase term of Kelly and 104 Voice's algorithm [10]. This term is essential to provide optimal 105 resource pooling. 107 - The second term guarantees responsiveness and non-flappiness of 108 OLIA. By measuring the number of transmitted bytes since the last 109 loss, it reacts to events within the current window and adapts to 110 changes faster than the first term. 112 By adapting the window increases as a function of RTTs, OLIA also 113 compensates for different RTTs. As OLIA is rooted on the optimal 114 algorithm of [10], it provides fairness and optimal congestion 115 balancing. Because of the second term, it is responsive and non- 116 flappy. 118 OLIA is implemented in the Linux kernel and is now a part of 119 UCLouvain's MPTCP implementation [9, 11]. In [5], we study the 120 performance of MPTCP with OLIA over a testbed, by simulations and by 121 theoretical analysis. We prove theoretically that OLIA is Pareto- 122 optimal and that it satisfies the design goals of MPTCP described in 123 [4]. Hence, it can provide optimal congestion balancing and fairness 124 in the network. Our measurements and simulations indicate that MPTCP 125 with OLIA is as responsive and non-flappy as MPTCP with LIA and that 126 it solves the identified problems with LIA. Recent studies show that 127 MPTCP with OLIA always outperforms MPTCP with LIA and is very 128 responsive to the changes in the environment [7, 8]. 130 The rest of the document provides a description of OLIA. For an 131 analysis of its performance, we refer to [5, 7, 8]. 133 1.1 Requirements Language 135 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 136 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 137 document are to be interpreted as described in RFC 2119 [1]. 139 1.2 Terminology 141 Regular TCP: The standard version of TCP that operates between a 142 single pair of IP addresses and ports [2]. 144 Multipath TCP: A modified version of the regular TCP that allows a 145 user to spread its traffic across multiple paths. 147 MPTCP: The proposal for multipath TCP specified in [3]. 149 LIA: The Linked-Increases Algorithm of MPTCP (the congestion control 150 of MPTCP) [4]. 152 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP proposed 153 in [5]. 155 all_paths: The set of all the paths established by the MPTCP 156 connection. 158 best_paths: The set of paths in all_paths that are presumably the 159 best paths for the MPTCP connection. 161 max_w_paths: The set of paths in all_paths with largest congestion 162 windows. 164 collected_paths: The set of paths in all_paths that are presumably 165 the best paths but do not have largest congestion window (i.e. the 166 paths of best_paths that are not in max_w_paths). 168 w_r: The congestion windows on a path r. 170 rtt_r: The Round-Trip Time on a path r. 172 MSS_r: The Maximum Segment Size that specifies the largest amount of 173 data can be transmitted by a TCP packet on the path r. 175 2 The set of best paths, paths with maximum windows, and collected paths 177 A MPTCP connection has access to one or more paths. Let all_paths be 178 the set of all the paths established by the MPTCP connection and r be 179 one of these paths. 181 We denote by l_{1r} the number of bytes that were successfully 182 transmitted over path r between the last two losses seen on r, and by 183 l_{2r} the number of bytes that are successfully transmitted over r 184 after the last loss. We denote by l_r=max{l_{1r},l_{2r}} the smoothed 185 estimation of number of bytes transmitted on path r between last two 186 losses. 188 l_{1r} and l_{2r} can be measured by using information that is 189 already available to a regular TCP user: 191 - For each ACK on r: l_{2r} <- l_{2r} + (number of bytes that are 192 acknowledged by ACK), 194 - For each loss on r: l_{1r} <- l_{2r} and l_{2r} <- 0. 196 l_{1r} and l_{2r} are initially set to zero when the connection is 197 established. If no losses have been observed on r until now, then 198 l_{1r}=0 and l_{2r} is the total number of bytes transmitted on r. 200 Let rtt_r be the round-trip time observed on path r (e.g. the 201 smoothed round-trip time used by regular TCP) and w_r be the 202 congestion windows on path r. We denote by best_paths the set of 203 paths r in all_paths that have the maximum value of l_r*l_r/rtt_r, by 204 max_w_paths the set of paths r in all_paths with largest w_r, and by 205 collected_paths the set of best paths that do not have maximum window 206 size, i.e.: 208 - best_paths = { r | r = arg max_{p in all_paths} (l_p*l_p/rtt_p) } 210 - max_w_paths = { r | r = arg max_{p in all_paths} (w_p) } 212 - collected_paths = { r | r in best_paths and not in max_w_paths }. 214 where arg max is the argument of maximum, the set of points of the 215 given argument for which the given function is maximum. arg max is 216 applied over all paths p in all_paths. 218 best_paths represents the set of paths that are presumably the best 219 paths (in term of transmission rate) for the user: 1/l_r can be 220 considered as an estimate of byte loss probability on path r, and 221 hence the rate that path r can provide to a TCP user can be estimated 222 by (2*l_r)^{1/2}/rtt_r. A collected path is a path that is presumably 223 good but is not fully used. The set collected_paths can be empty. 225 Note that l_{1r}, l_{2r}, l_r, rtt_r, w_r, best_paths, max_w_paths 226 and collected_paths are all functions of time. 228 3 Opportunistic Linked-Increases Algorithm 230 In this section, we introduce OLIA. OLIA is a window-based 231 congestion-control algorithm. It couples the increase of congestion 232 windows and uses unmodified TCP behavior in the case of a loss. OLIA 233 is an alternative for LIA, the current congestion control of MPTCP. 235 The algorithm only applies to the increase part of the congestion 236 avoidance phase. The fast retransmit and fast recovery algorithms, as 237 well as the multiplicative decrease of the congestion avoidance 238 phase, are the same as in TCP [2]. We also use a similar slow start 239 algorithm as in TCP, with the modification that we set the ssthresh 240 (slow start threshold) to be 1 MSS if multiple paths are established. 241 In the case of a single path flow, we use the same minimum ssthresh 242 as in TCP (i.e. 2 MSS). The purpose of this modification is to avoid 243 transmitting unnecessary traffic over congested paths when multiple 244 paths are available to a user. 246 For a path r, we denote by w_r the congestion windows on this path 247 (also called subflow). We denote by MSS_r be the maximum segment size 248 on the path r. We assume that w_r is maintained in bytes. 250 Our proposed "Opportunistic Linked-Increases Algorithm" (OLIA) must: 252 - For each ACK on path r, increase w_r by 254 w_r/rtt_r^2 alpha_r 255 ( -------------------------- + --------- ) (1) 256 (SUM_{p in all_paths} (w_p/rtt_p))^2 w_r 258 multiplied by MSS_r * bytes_acked. 260 The summation in the denominator of the first term is over all the 261 paths p in all_paths. Recall that w_p and rtt_p denote the window 262 size and the round trip time of a path p. 264 alpha_r is calculated as follows: 266 - If r is in collected_paths, then 267 1/number_of_paths 268 alpha_r = -------------------- 269 |collected_paths| 271 - If r is in max_w_paths and if collected_paths is not empty, then 273 1/number_of_paths 274 alpha_r = - ----------------- 275 |max_w_paths| 277 - Otherwise, alpha_r=0. 279 |collected_paths| and |max_w_paths| are the number of paths in 280 collected_paths and in max_w_paths. Note that the sum of all alpha_r 281 is equal to 0. 283 The first term in (1) is an adaptation of Kelly and Voice's increase 284 term [10] and provides the optimal resource pooling (Kelly and 285 Voice's algorithm is based on scalable TCP; the first term in (1) is 286 a TCP compatible version of their algorithm that compensates also for 287 different RTTs). The second term, with alpha_r, guarantees 288 responsiveness and non-flappiness of our algorithm. 290 By definition of alpha_r, if all the best paths have the largest 291 window size, then alpha_r=0 for any r. This is because we already use 292 the capacity available to the user by using all the best path. 294 If there is any best path with a small window size, i.e. if 295 collected_paths is not empty, then alpha_r is positive for all r in 296 collected_paths and negative for all r in max_w_paths. Hence, our 297 algorithm increases windows faster on the paths that are presumably 298 best but that have small windows. The increase will be slower on the 299 paths with maximum windows. In this case, OLIA re-forwards traffic 300 from fully used paths (i.e. paths in max_w_paths) to paths that have 301 free capacity available to the users (i.e. paths in collected_paths). 303 In [4], three goals have been proposed for the design of a practical 304 multipath congestion control algorithm : (1) Improve throughput: a 305 multipath TCP user should perform at least as well as a TCP user that 306 uses the best path available to it. (2) Do no harm: a multipath TCP 307 user should never take up more capacity from any of its paths than a 308 TCP user. And (3) balance congestion: a multipath TCP algorithm 309 should balance congestion in the network, subject to meeting the 310 first two goals. 312 Our theoretical results in [5] show that OLIA fully satisfies these 313 three goals. LIA, however, fails to fully satisfy the goal (3) as 314 discussed in [5] and [6]. Moreover, in [5], we show through 315 measurements and by simulation that our algorithm is as responsive 316 and non-flappy as LIA and that it can solve the identified problems 317 with LIA. In [7], Chen et al. study how MPTCP with LIA and OLIA 318 performs in the wild with a common wireless environment, namely using 319 both WiFi and Cellular simultaneously. Their results show that MPTCP 320 with OLIA is very responsive to the changes in the environment and 321 always outperforms MPTCP with LIA. Furthermore, using Experimental 322 Design, Paasch et al. [8] show that MPTCP with OLIA satisfy the 323 design goal of MPTCP in a very wide range of scenarios and always 324 outperform MPTCP with LIA. 326 4 Practical considerations 328 Calculation of alpha requires performing costly floating point 329 operation whenever an ACK received over path r. In practice, however, 330 we can integrate calculation of alpha and Equation (1) together. Our 331 algorithm can be therefore simplified as the following. 333 For each ACK on the path r: 335 - If r is in collected_paths, increase w_r by 337 w_r/rtt_r^2 1 338 ----------------- + ------------------------------------ (2) 339 (SUM_p (w_p/rtt_p))^2 w_r * number_of_paths * |collected_paths| 341 multiplied by MSS_r * bytes_acked. 343 - If r is in max_w_paths and if collected_paths is not empty, 344 increase w_r by 346 w_r/rtt_r^2 1 347 ---------------- - ------------------------------- (3) 348 (SUM_p (w_p/rtt_p))^2 w_r * number_of_paths * |max_w_paths| 350 multiplied by MSS_r * bytes_acked. 352 - Otherwise, increase w_r by 354 (w_r/rtt_r^2) 355 -------------------------- (4) 356 (SUM_p (w_p/rtt_p))^2 358 multiplied by MSS_r * bytes_acked. 360 The summation in the dominator of the first term of equations (2), 361 (3), and (4) is over the path p in all_paths. To compute the 362 increase, we only need to determine the sets collected_paths and 363 max_w_paths when an ACK is received on the path r. We can further 364 simplify the algorithm by updating the sets collected_paths and 365 max_w_paths only once per round-trip time or whenever there is a drop 366 on the path. 368 We can see from above that in some cases (i.e. when r is max_w_paths 369 and collected_paths is not empty) the increase could be negative. 370 This is a property of our algorithm as in this case OLIA re-forwards 371 traffic from paths in max_w_paths to paths in collected_paths. It is 372 easy to show that using our algorithm, w_r >= 1 for any path r. 374 5 Discussion 376 Our results in [5] show that the identified problems with current 377 MPTCP implementation are not due to the nature of a window-based 378 multipath protocol, but rather to the design of LIA. OLIA shows that 379 it is possible to build an alternative to LIA that mitigates these 380 problems and that is as responsive and non-flappy as LIA. 382 Our proposed algorithm can provide similar resource pooling as Kelly 383 and Voice's algorithm [10] and fully satisfies the design goals of 384 MPTCP described in [4]. Hence, it can provide optimal congestion 385 balancing and fairness in the network [5]. Moreover, it is as 386 responsive and non-flappy as LIA and outperforms LIA in realistic 387 scenarios such as wireless networks (refer to [5, 7, 8]). 389 We therefore believe that mptcp working group should revisit the 390 congestion control part of MPTCP and that an alternative algorithm, 391 such as OLIA, should be considered. 393 6 References 395 6.1 Normative References 397 [2] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 398 Control", RFC 5681, September 2009. 400 [3] Ford, A., Raiciu, C., Greenhalgh, A., and M. Handley, 401 "Architectural Guidelines for Multipath TCP Development", 402 RFC 6182, March 2011. 404 6.2 Informative References 406 [4] Raiciu, C., Handley, M., and D. Wischik, "Coupled 407 Congestion Control for Multipath Transport Protocols", 408 RFC 6356, October 2011. 410 [5] R. Khalili, N. Gast, M. Popovic, U. Upadhyay, and J.-Y. Le 411 Boudec. "MPTCP is not Pareto-optimality: Performance 412 issues and a possible solution", ACM CoNEXT 2012 (The 413 extended version is published at IEEE/ACM Transaction of 414 Networking, volume 5, issue 25, October 2013). 416 [6] R. Khalili, N. Gast, M. Popovic, and J.-Y. Le Boudec. 417 "Performance Issues with MPTCP", draft-khalili-mptcp- 418 performance-issues-06. 420 [7] Chen Y.-C, Y.-S. Lim, R. J. Gibbens, E. M. Nahum, R. 421 Khalili, and D. Towsley, "A Measurement-based Study of 422 Multipath TCP Performance over Wireless Networks." ACM IMC 423 2013. 425 [8] C. Paasch, R. Khalili, and O. Bonaventure, "On the 426 Benefits of Applying Experimental Design to Improve 427 Multipath TCP." ACM CoNEXT 2013. 429 [9] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux 430 kernel implementation," 2013 [Online]. Available: 431 http://mptcp.info.ucl.ac.be/. 433 [10] F. Kelly, and T. Voice, "Stability of end-to-end 434 algorithms for joint routing and rate control", ACM 435 SIGCOMM CCR vol. 35 num. 2, pp. 5-12, 2005. 437 [11] O. Bonaventure, and C. Paasch, "Experience with Multipath 438 TCP", draft-bonaventure-mptcp-experience-00 440 Authors' Addresses 442 Ramin Khalili 443 T-Labs/TU-Berlin 444 TEL 18, Ernst-Reuter-Platz 7 445 10587 Berlin 446 Germany 448 Phone: +49 16 0972 28074 449 EMail: ramin@net.t-labs.tu-berlin.de 451 Nicolas Gast 452 EPFL IC ISC LCA2 453 Station 14 454 CH-1015 Lausanne 455 Switzerland 457 Phone: +41 21 693 1254 458 EMail: nicolas.gast@epfl.ch 460 Miroslav Popovic 461 EPFL IC ISC LCA2 462 Station 14 463 CH-1015 Lausanne 464 Switzerland 466 Phone: +41 21 693 6466 467 EMail: miroslav.popovic@epfl.ch 469 Jean-Yves Le Boudec 470 EPFL IC ISC LCA2 471 Station 14 472 CH-1015 Lausanne 473 Switzerland 475 Phone: +41 21 693 6631 476 EMail: jean-yves.leboudec@epfl.ch