idnits 2.17.1 draft-khalili-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 : ---------------------------------------------------------------------------- ** 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], 8], [9], 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 282 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 (February 14, 2014) is 3722 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 136, but not defined -- Looks like a reference, but probably isn't: 'Online' on line 429 ** Downref: Normative reference to an Informational RFC: RFC 6182 (ref. '3') == Outdated reference: A later version (-06) exists of draft-khalili-mptcp-performance-issues-05 Summary: 4 errors (**), 0 flaws (~~), 5 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: August 18, 2014 Miroslav Popovic 6 Jean-Yves Le Boudec 7 EPFL-LCA2 8 February 14, 2014 10 Opportunistic Linked-Increases Congestion Control Algorithm for MPTCP 11 draft-khalili-mptcp-congestion-control-03 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]. 25 Status of this Memo 27 This Internet-Draft is submitted to IETF 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 This Internet-Draft will expire on August 18, 2014. 42 The list of current Internet-Drafts can be accessed at 43 http://www.ietf.org/1id-abstracts.html 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html 48 Copyright and License Notice 50 Copyright (c) 2014 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1 Requirements Language . . . . . . . . . . . . . . . . . . . 4 67 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 68 2 The set of best paths, paths with maximum windows, and 69 collected paths . . . . . . . . . . . . . . . . . . . . . . . . 5 70 3 Opportunistic Linked-Increases Algorithm . . . . . . . . . . . . 7 71 4 Practical considerations . . . . . . . . . . . . . . . . . . . . 9 72 5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 6.1 Normative References . . . . . . . . . . . . . . . . . . . . 11 75 6.2 Informative References . . . . . . . . . . . . . . . . . . . 11 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 78 1 Introduction 80 The current MPTCP implementation uses a congestion control algorithm 81 called LIA, the "Linked-Increases" algorithm [4]. The design of LIA 82 forces a tradeoff between optimal congestion balancing and 83 responsiveness. Hence, to provide good responsiveness, LIA's current 84 implementation must depart from optimal congestion balancing. This 85 leads to important performance issues (refer to [5] and [6]): (i) in 86 some scenarios upgrading TCP users to MPTCP results in a significant 87 drop in the aggregate throughput in the network without any benefit 88 for anybody; and (ii) MPTCP users can be excessively aggressive 89 toward TCP users. 91 In this draft, we introduce OLIA, the "opportunistic linked increases 92 algorithm", as an alternative to LIA. Contrary to LIA, OLIA's design 93 is not based on a trade-off between responsiveness and optimal 94 congestion balancing; it can provide both simultaneously [5]. 96 Similarly to LIA, OLIA couples the additive increases and uses 97 unmodified TCP behavior in the case of a loss. The difference between 98 LIA and OLIA is in the increase part. OLIA's increase part, Equation 99 (1), has two terms: 101 - The first term is an adaptation of the increase term of Kelly and 102 Voice's algorithm [10]. This term is essential to provide optimal 103 resource pooling. 105 - The second term guarantees responsiveness and non-flappiness of 106 OLIA. By measuring the number of transmitted bytes since the last 107 loss, it reacts to events within the current window and adapts to 108 changes faster than the first term. 110 By adapting the window increases as a function of RTTs, OLIA also 111 compensates for different RTTs. As OLIA is rooted on the optimal 112 algorithm of [10], it provides fairness and optimal congestion 113 balancing. Because of the second term, it is responsive and non- 114 flappy. 116 OLIA is implemented in the Linux kernel and is now a part of 117 UCLouvain's MPTCP implementation. In [5], we study the performance of 118 MPTCP with OLIA over a testbed, by simulations and by theoretical 119 analysis. We prove theoretically that OLIA is Pareto-optimal and that 120 it satisfies the design goals of MPTCP described in [4]. Hence, it 121 can provide optimal congestion balancing and fairness in the network. 122 Our measurements and simulations indicate that MPTCP with OLIA is as 123 responsive and non-flappy as MPTCP with LIA and that it solves the 124 identified problems with LIA. Recent studies show that MPTCP with 125 OLIA always outperforms MPTCP with LIA and is very responsive to the 126 changes in the environment [7, 8]. 128 The rest of the document provides a description of OLIA. For an 129 analysis of its performance, we refer to [5, 7, 8]. 131 1.1 Requirements Language 133 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 134 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 135 document are to be interpreted as described in RFC 2119 [1]. 137 1.2 Terminology 139 Regular TCP: The standard version of TCP that operates between a 140 single pair of IP addresses and ports [2]. 142 Multipath TCP: A modified version of the regular TCP that allows a 143 user to spread its traffic across multiple paths. 145 MPTCP: The proposal for multipath TCP specified in [3]. 147 LIA: The Linked-Increases Algorithm of MPTCP (the congestion control 148 of MPTCP) [4]. 150 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP proposed 151 in [5]. 153 all_paths: The set of all the paths established by the MPTCP 154 connection. 156 best_paths: The set of paths in all_paths that are presumably the 157 best paths for the MPTCP connection. 159 max_w_paths: The set of paths in all_paths with largest congestion 160 windows. 162 collected_paths: The set of paths in all_paths that are presumably 163 the best paths but do not have largest congestion window (i.e. the 164 paths of best_paths that are not in max_w_paths). 166 w_r: The congestion windows on a path r. 168 rtt_r: The Round-Trip Time on a path r. 170 MSS_r: The Maximum Segment Size that specifies the largest amount of 171 data can be transmitted by a TCP packet on the path r. 173 2 The set of best paths, paths with maximum windows, and collected paths 175 A MPTCP connection has access to one or more paths. Let all_paths be 176 the set of all the paths established by the MPTCP connection and r be 177 one of these paths. 179 We denote by l_{1r} the number of bytes that were successfully 180 transmitted over path r between the last two losses seen on r, and by 181 l_{2r} the number of bytes that are successfully transmitted over r 182 after the last loss. We denote by l_r=max{l_{1r},l_{2r}} the smoothed 183 estimation of number of bytes transmitted on path r between last two 184 losses. 186 l_{1r} and l_{2r} can be measured by using information that is 187 already available to a regular TCP user: 189 - For each ACK on r: l_{2r} <- l_{2r} + (number of bytes that are 190 acknowledged by ACK), 192 - For each loss on r: l_{1r} <- l_{2r} and l_{2r} <- 0. 194 l_{1r} and l_{2r} are initially set to zero when the connection is 195 established. If no losses have been observed on r until now, then 196 l_{1r}=0 and l_{2r} is the total number of bytes transmitted on r. 198 Let rtt_r be the round-trip time observed on path r (e.g. the 199 smoothed round-trip time used by regular TCP) and w_r be the 200 congestion windows on path r. We denote by best_paths the set of 201 paths r in all_paths that have the maximum value of l_r*l_r/rtt_r, by 202 max_w_paths the set of paths r in all_paths with largest w_r, and by 203 collected_paths the set of best paths that do not have maximum window 204 size, i.e.: 206 - best_paths = { r | r = arg max_{p in all_paths} (l_p*l_p/rtt_p) } 208 - max_w_paths = { r | r = arg max_{p in all_paths} (w_p) } 210 - collected_paths = { r | r in best_paths and not in max_w_paths }. 212 where arg max is the argument of maximum, the set of points of the 213 given argument for which the given function is maximum. arg max is 214 applied over all paths p in all_paths. 216 best_paths represents the set of paths that are presumably the best 217 paths (in term of transmission rate) for the user: 1/l_r can be 218 considered as an estimate of byte loss probability on path r, and 219 hence the rate that path r can provide to a TCP user can be estimated 220 by (2*l_r)^{1/2}/rtt_r. A collected path is a path that is presumably 221 good but is not fully used. The set collected_paths can be empty. 223 Note that l_{1r}, l_{2r}, l_r, rtt_r, w_r, best_paths, max_w_paths 224 and collected_paths are all functions of time. 226 3 Opportunistic Linked-Increases Algorithm 228 In this section, we introduce OLIA. OLIA is a window-based 229 congestion-control algorithm. It couples the increase of congestion 230 windows and uses unmodified TCP behavior in the case of a loss. OLIA 231 is an alternative for LIA, the current congestion control of MPTCP. 233 The algorithm only applies to the increase part of the congestion 234 avoidance phase. The fast retransmit and fast recovery algorithms, as 235 well as the multiplicative decrease of the congestion avoidance 236 phase, are the same as in TCP [2]. We also use a similar slow start 237 algorithm as in TCP, with the modification that we set the ssthresh 238 (slow start threshold) to be 1 MSS if multiple paths are established. 239 In the case of a single path flow, we use the same minimum ssthresh 240 as in TCP (i.e. 2 MSS). The purpose of this modification is to avoid 241 transmitting unnecessary traffic over congested paths when multiple 242 paths are available to a user. 244 For a path r, we denote by w_r the congestion windows on this path 245 (also called subflow). We denote by MSS_r be the maximum segment size 246 on the path r. We assume that w_r is maintained in bytes. 248 Our proposed "Opportunistic Linked-Increases Algorithm" (OLIA) must: 250 - For each ACK on path r, increase w_r by 252 w_r/rtt_r^2 alpha_r 253 ( -------------------------- + --------- ) (1) 254 (SUM_{p in all_paths} (w_p/rtt_p))^2 w_r 256 multiplied by MSS_r * bytes_acked. 258 The summation in the denominator of the first term is over all the 259 paths p in all_paths. Recall that w_p and rtt_p denote the window 260 size and the round trip time of a path p. 262 alpha_r is calculated as follows: 264 - If r is in collected_paths, then 265 1/number_of_paths 266 alpha_r = -------------------- 267 |collected_paths| 269 - If r is in max_w_paths and if collected_paths is not empty, then 271 1/number_of_paths 272 alpha_r = - ----------------- 273 |max_w_paths| 275 - Otherwise, alpha_r=0. 277 |collected_paths| and |max_w_paths| are the number of paths in 278 collected_paths and in max_w_paths. Note that the sum of all alpha_r 279 is equal to 0. 281 The first term in (1) is an adaptation of Kelly and Voice's increase 282 term [10] and provides the optimal resource pooling (Kelly and 283 Voice's algorithm is based on scalable TCP; the first term in (1) is 284 a TCP compatible version of their algorithm that compensates also for 285 different RTTs). The second term, with alpha_r, guarantees 286 responsiveness and non-flappiness of our algorithm. 288 By definition of alpha_r, if all the best paths have the largest 289 window size, then alpha_r=0 for any r. This is because we already use 290 the capacity available to the user by using all the best path. 292 If there is any best path with a small window size, i.e. if 293 collected_paths is not empty, then alpha_r is positive for all r in 294 collected_paths and negative for all r in max_w_paths. Hence, our 295 algorithm increases windows faster on the paths that are presumably 296 best but that have small windows. The increase will be slower on the 297 paths with maximum windows. In this case, OLIA re-forwards traffic 298 from fully used paths (i.e. paths in max_w_paths) to paths that have 299 free capacity available to the users (i.e. paths in collected_paths). 301 In [4], three goals have been proposed for the design of a practical 302 multipath congestion control algorithm : (1) Improve throughput: a 303 multipath TCP user should perform at least as well as a TCP user that 304 uses the best path available to it. (2) Do no harm: a multipath TCP 305 user should never take up more capacity from any of its paths than a 306 TCP user. And (3) balance congestion: a multipath TCP algorithm 307 should balance congestion in the network, subject to meeting the 308 first two goals. 310 Our theoretical results in [5] show that OLIA fully satisfies these 311 three goals. LIA, however, fails to fully satisfy the goal (3) as 312 discussed in [5] and [6]. Moreover, in [5], we show through 313 measurements and by simulation that our algorithm is as responsive 314 and non-flappy as LIA and that it can solve the identified problems 315 with LIA. In [7], Chen et al. study how MPTCP with LIA and OLIA 316 performs in the wild with a common wireless environment, namely using 317 both WiFi and Cellular simultaneously. Their results show that MPTCP 318 with OLIA is very responsive to the changes in the environment and 319 always outperforms MPTCP with LIA. Furthermore, using Experimental 320 Design, Paasch et al. [8] show that MPTCP with OLIA satisfy the 321 design goal of MPTCP in a very wide range of scenarios and always 322 outperform MPTCP with LIA. 324 4 Practical considerations 326 Calculation of alpha requires performing costly floating point 327 operation whenever an ACK received over path r. In practice, however, 328 we can integrate calculation of alpha and Equation (1) together. Our 329 algorithm can be therefore simplified as the following. 331 For each ACK on the path r: 333 - If r is in collected_paths, increase w_r by 335 w_r/rtt_r^2 1 336 ----------------- + ------------------------------------ (2) 337 (SUM_p (w_p/rtt_p))^2 w_r * number_of_paths * |collected_paths| 339 multiplied by MSS_r * bytes_acked. 341 - If r is in max_w_paths and if collected_paths is not empty, 342 increase w_r by 344 w_r/rtt_r^2 1 345 ---------------- - ------------------------------- (3) 346 (SUM_p (w_p/rtt_p))^2 w_r * number_of_paths * |max_w_paths| 348 multiplied by MSS_r * bytes_acked. 350 - Otherwise, increase w_r by 352 (w_r/rtt_r^2) 353 -------------------------- (4) 354 (SUM_p (w_p/rtt_p))^2 356 multiplied by MSS_r * bytes_acked. 358 The summation in the dominator of the first term of equations (2), 359 (3), and (4) is over the path p in all_paths. To compute the 360 increase, we only need to determine the sets collected_paths and 361 max_w_paths when an ACK is received on the path r. We can further 362 simplify the algorithm by updating the sets collected_paths and 363 max_w_paths only once per round-trip time or whenever there is a drop 364 on the path. 366 We can see from above that in some cases (i.e. when r is max_w_paths 367 and collected_paths is not empty) the increase could be negative. 368 This is a property of our algorithm as in this case OLIA re-forwards 369 traffic from paths in max_w_paths to paths in collected_paths. It is 370 easy to show that using our algorithm, w_r >= 1 for any path r. 372 5 Discussion 374 Our results in [5] show that the identified problems with current 375 MPTCP implementation are not due to the nature of a window-based 376 multipath protocol, but rather to the design of LIA. OLIA shows that 377 it is possible to build an alternative to LIA that mitigates these 378 problems and that is as responsive and non-flappy as LIA. 380 Our proposed algorithm can provide similar resource pooling as Kelly 381 and Voice's algorithm [10] and fully satisfies the design goals of 382 MPTCP described in [4]. Hence, it can provide optimal congestion 383 balancing and fairness in the network [5]. Moreover, it is as 384 responsive and non-flappy as LIA and outperforms LIA in realistic 385 scenarios such as wireless networks (refer to [5, 7, 8]). 387 We therefore believe that mptcp working group should revisit the 388 congestion control part of MPTCP and that an alternative algorithm, 389 such as OLIA, should be considered. 391 6 References 393 6.1 Normative References 395 [2] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 396 Control", RFC 5681, September 2009. 398 [3] Ford, A., Raiciu, C., Greenhalgh, A., and M. Handley, 399 "Architectural Guidelines for Multipath TCP Development", 400 RFC 6182, March 2011. 402 6.2 Informative References 404 [4] Raiciu, C., Handley, M., and D. Wischik, "Coupled 405 Congestion Control for Multipath Transport Protocols", 406 RFC 6356, October 2011. 408 [5] R. Khalili, N. Gast, M. Popovic, U. Upadhyay, and J.-Y. Le 409 Boudec. "MPTCP is not Pareto-optimality: Performance 410 issues and a possible solution", ACM CoNEXT 2012 (The 411 extended version of this paper is published at IEEE/ACM 412 Transaction of Networking, volume 5, issue 25, October 413 2013). 415 [6] R. Khalili, N. Gast, M. Popovic, and J.-Y. Le Boudec. 416 "Performance Issues with MPTCP", draft-khalili-mptcp- 417 performance-issues-05. 419 [7] Chen Y.-C, Y.-S. Lim, R. J. Gibbens, E. M. Nahum, R. 420 Khalili, and D. Towsley, "A Measurement-based Study of 421 Multipath TCP Performance over Wireless Networks." ACM IMC 422 2013. 424 [8] C. Paasch, R. Khalili, and O. Bonaventure, "On the 425 Benefits of Applying Experimental Design to Improve 426 Multipath TCP." ACM CoNEXT 2013. 428 [9] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux 429 kernel implementation," 2013 [Online]. Available: 430 http://mptcp.info.ucl.ac.be/. 432 [10] Kelly, F. and T. Voice, "Stability of end-to-end 433 algorithms for joint routing and rate control", ACM 434 SIGCOMM CCR vol. 35 num. 2, pp. 5-12, 2005. 436 Authors' Addresses 438 Ramin Khalili 439 T-Labs/TU-Berlin 440 TEL 18, Ernst-Reuter-Platz 7 441 10587 Berlin 442 Germany 444 Phone: +49 30 8353 58276 445 EMail: ramin@net.t-labs.tu-berlin.de 447 Nicolas Gast 448 EPFL IC ISC LCA2 449 Station 14 450 CH-1015 Lausanne 451 Switzerland 453 Phone: +41 21 693 1254 454 EMail: nicolas.gast@epfl.ch 456 Miroslav Popovic 457 EPFL IC ISC LCA2 458 Station 14 459 CH-1015 Lausanne 460 Switzerland 462 Phone: +41 21 693 6466 463 EMail: miroslav.popovic@epfl.ch 465 Jean-Yves Le Boudec 466 EPFL IC ISC LCA2 467 Station 14 468 CH-1015 Lausanne 469 Switzerland 471 Phone: +41 21 693 6631 472 EMail: jean-yves.leboudec@epfl.ch