idnits 2.17.1 draft-walid-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: ---------------------------------------------------------------------------- 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.) 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 21, 2014) is 3567 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) ** Downref: Normative reference to an Experimental RFC: RFC 6356 Summary: 3 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Multipath TCP A. Walid 3 Internet-Draft Bell Labs 4 Intended status: Standards Track Q. Peng 5 Expires: January 22, 2015 Caltech 6 J. Hwang 7 Bell Labs 8 S. Low 9 Caltech 10 July 21, 2014 12 Balanced Linked Adaptation Congestion Control Algorithm for MPTCP 13 draft-walid-mptcp-congestion-control-00 15 Abstract 17 This document describes the mechanism of Balia, the "Balanced linked 18 adaptation", which is a congestion control algorithm for Multipath 19 TCP (MPTCP). The recent proposals, LIA and OLIA, suffer from either 20 unfriendliness to Single Path TCP (SPTCP) or unresponsiveness to 21 network changes under certain conditions. The tradeoff between 22 friendliness and responsiveness is inevitable, but Balia judiciously 23 balances this tradeoff based on a new design framework that allows 24 one to systematically explore the design space. Balia has been 25 implemented in the Linux kernel and there are plans to make it 26 available for experimentation. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on January 22, 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 63 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 64 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Balanced Linked Adaptation Algorithm . . . . . . . . . . . . 4 66 3. Theoretical justification . . . . . . . . . . . . . . . . . . 4 67 4. Experimental results . . . . . . . . . . . . . . . . . . . . 5 68 4.1. Khalili's scenario . . . . . . . . . . . . . . . . . . . 5 69 4.2. Responsiveness . . . . . . . . . . . . . . . . . . . . . 7 70 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 8 71 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 72 6.1. Normative References . . . . . . . . . . . . . . . . . . 8 73 6.2. Informative References . . . . . . . . . . . . . . . . . 8 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 76 1. Introduction 78 Various congestion control algorithms have been proposed as 79 extensions of TCP NewReno to MPTCP. A straightforward extension is 80 to run TCP NewReno on each subpath, e.g., [HONDA09]. This algorithm, 81 however, can be highly unfriendly when it shares a path with a SPTCP 82 user. This motivates the Coupled algorithm which is fair because it 83 has the same underlying utility function as TCP NewReno, e.g., 84 [KELLY05], [HAN04]. It is found in [RFC6356], however, that the 85 Coupled algorithm responds slowly in a dynamic network environment. 87 The current default congestion control algorithm for MPTCP, called 88 LIA (Linked-Increases Algorithm), is more responsive than the Coupled 89 algorithm. However, it has been reported that LIA can sometimes be 90 excessively aggressive toward SPTCP users without any benefit to 91 multipath users [KHALILI12]. Recently, OLIA (Opportunistic Linked- 92 Increases Algorithm) [KHALILI12] was proposed as a variant of Coupled 93 algorithm [KELLY05] which is as friendly as the Coupled algorithm. 94 We have found, however, that OLIA can be unresponsive to changes in 95 network conditions in some scenarios (e.g., when the paths used by a 96 user have similar round trip times (RRTs)) [PENG14]. 98 In this draft, we introduce Balia, the "Balanced linked adaptation", 99 which is a window-based congestion control algorithm for MPTCP. The 100 main design goal of Balia is to systematically tradeoff different 101 properties such as TCP friendliness and responsiveness by developing 102 structural understanding of MPTCP algorithms in a new design 103 framework. For instance, it is widely suspected that there is a 104 tradeoff between friendliness and responsiveness and it is proved in 105 this framework that this tradeoff is indeed inevitable. By 106 parameterizing different structural properties, Balia generalizes 107 existing algorithms and explicitly balances the tradeoff. We also 108 prove mathematically that Balia has a unique equilibrium point, and 109 that it is asymptotically stable. Therefore, Balia can provide 110 balanced performance in terms of friendliness and responsiveness. 112 In [PENG14], we compare the performance of several MPTCP algorithms 113 over a testbed, including Balia, OLIA and LIA. Our experimental 114 results show that Balia is friendlier than LIA and more responsive 115 than OLIA. It also solves LIA's problem identified by [KHALILI12]. 116 Balia has been implemented in the Linux kernel and there are plans to 117 make it available for experimentation. 119 1.1. Requirements Language 121 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 122 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 123 document are to be interpreted as described in [RFC2119]. 125 1.2. Terminology 127 Regular/Singlepath TCP (SPTCP): The standard version of TCP [RFC5681] 128 that uses a single pair of IP address and ports per connection. 130 Multipath TCP (MPTCP): A modified version of the regular TCP that 131 simultaneously uses multiple paths between hosts. 133 LIA: The Linked-Increases Algorithm for MPTCP [RFC6356]. 135 OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP 136 [KHALILI12]. 138 Balia: The Balanced linked adaptation algorithm for MPTCP [PENG14]. 140 AIMD: The Additive Increase Multiplicative Decrease algorithm used in 141 TCP congestion avoidance. 143 w_r: The congestion window on a path r. 145 rtt_r: The Round-Trip Time (RTT) on a path r. 147 2. Balanced Linked Adaptation Algorithm 149 Balia is a generalized MPTCP algorithm that strikes a good balance 150 between friendliness and responsiveness. The algorithm only applies 151 to the AIMD part of the congestion avoidance phase. The other parts 152 such as slow start, fast retransmit/recovery algorithms are the same 153 as in TCP [RFC5681]. The minimum ssthresh is set to 1 MSS instead of 154 2 when more than 1 path is available. 156 Each source s has a set of paths r. As a special case, the set can 157 be a singleton in which case Balia reduces to TCP Reno (see below). 158 Each path r maintains a congestion window w_r and measures its round- 159 trip time rtt_r. The window adaptation of Balia is as follows: 161 - For each ACK on path r, increase w_r by: 163 x_r 1 + alpha_r 4 + alpha_r 164 -------------------- * ( ----------- ) * ( ----------- ) 165 rtt_r * (SUM(x_k))^2 2 5 167 - For each packet loss on path r, decrease w_r as: 169 w_r 170 ----- * min { alpha_r, 1.5 } 171 2 173 where x_r = w_r / rtt_r and alpha_r = max { x_r } / x_r. 175 Note that Balia's decrement algorithm multiplies the MD algorithm of 176 TCP Reno by a factor in the range of [1, 1.5]. 178 If a Balia user uses only a single path, then alpha_r = 1, in which 179 [case] both the increment and the decrement algorithms of Balia 180 reduces to those of TCP Reno. Hence Balia reduces to TCP Reno on 181 single paths. 183 3. Theoretical justification 185 In [PENG14], we have developed a unified model of MPTCP algorithms 186 and characterized the design space. This provides a framework to 187 systematically design MPTCP algorithms and analyze their behavior in 188 a large network at design time. For instance, it has allowed us to 189 identify designs that guarantee the existence, uniqueness and 190 stability of network equilibrium. Balia is designed using this 191 framework to achieve specific design goals. In this section, we will 192 focus on how Balia balances three often conflicting design goals, TCP 193 friendliness, responsiveness and window oscillation. 195 TCP friendliness characterizes how much more throughput a MPTCP flow 196 will get when it competes with an SPTCP flow. A MPTCP flow is said 197 to be "TCP friendly" if it does not dominate the available bandwidth 198 when it shares the same network with a SPTCP flow. 200 Responsiveness characterizes how fast the MPTCP algorithm reacts to 201 changes in network conditions. 203 The window oscillation property characterizes how severely the window 204 size fluctuates around the equilibrium point. It is an inherent 205 property of AIMD-like algorithms. 207 In [PENG14], it is proved mathematically that there is an inevitable 208 tradeoff between TCP friendliness and responsiveness, and between 209 responsiveness and window oscillation. Thus, it is theoretically 210 impossible to maximize the performance in all three metrics 211 simultaneously. 213 Our design philosophy is to allow window oscillation up to an 214 acceptable level in order to improve both friendliness and 215 responsiveness. This is achieved by explicitly parameterizing these 216 properties and systematically choosing these parameters. 218 4. Experimental results 220 In this section, we summarize our experimental results that 221 illustrate the weaknesses of the current algorithms (LIA and OLIA). 222 We evaluate the MPTCP algorithms using a reference Linux 223 implementation of MPTCP, Multipath TCP v0.88 [MPLKI], based on the 224 Linux kernel 3.11.8. The network parameters such as network 225 bandwidth and delay are implemented by Dummynet [DUMMYNET]. Iperf is 226 used to generate traffic and measure the throughput. 228 4.1. Khalili's scenario 230 In [KHALILI12], it has been revealed that LIA can be unfriendly to 231 SPTCP users even when its own MPTCP throughput is saturated. That 232 is, the throughputs of SPTCP flows are significantly degraded without 233 any benefit to MPTCP flows. To reproduce this scenario, we create a 234 testbed as shown in Figure 1. In this scenario, N1 type1 users can 235 be either single path or multipath while N2 type2 users are always 236 single path. 238 +----+ 239 N1 | | Server 240 Type1 ---------------------------------| C1 |-- for type1 241 flows --\ /--| | flows 242 \ / +----+ 243 \ / Router1 244 \ +----+ +----+ / 245 \--| | | |--/ 246 N2 | C2 |---| | Server 247 Type2 ---------| | | |------------------ for type2 248 flows +----+ +----+ flows 249 Router2 Router3 251 Figure 1: Testbed topology for Khalili's scenario. The Router1 252 emulates the server-side bottleneck for type1 users and the Router2 253 emulates the shared bottleneck. 255 The aggregate throughputs of these users are shown in Table 1 for the 256 case when all users are SPTCP and the case when all type1 users are 257 upgraded to MPTCP users using different algorithms. We observe that 258 upgrading type1 users to MPTCP decreases type2 users' throughput 259 without any benefit to type1 users if LIA is used; the type2 users 260 are worse off by 19% when N1=N2=5 and by 25% when N1=15 and N2=5. 261 Both OLIA and Balia are more friendly than LIA to SPTCP (type2) 262 users. 264 C1=C2=10Mbps 265 +-------------+----------------------------------+ 266 | Type1 users | Type1 users are multipath | 267 | are +-----------+----------+-----------+ 268 | single path | LIA | OLIA | Balia | 269 +------+-------------+-----------+----------+-----------+ 270 N1=5 |type1 | 9.47 | 9.26 | 9.25 | 9.25 | 271 +------+-------------+-----------+----------+-----------+ 272 N2=5 |type2 | 9.29 | 7.55 | 8.13 | 8.32 | 273 ------+------+-------------+-----------+----------+-----------+ 274 N1=15 |type1 | 9.39 | 8.96 | 8.93 | 9.02 | 275 +------+-------------+-----------+----------+-----------+ 276 N2=5 |type2 | 9.29 | 6.94 | 7.41 | 7.98 | 277 +------+-------------+-----------+----------+-----------+ 278 Values are in Mbps. 280 Table 1: Throughput obtained by type1 and type2 users: Upgrading 281 type1 users to MPTCP decreases type2 users' throughput without any 282 benefit to type1 users. 284 4.2. Responsiveness 286 To demonstrate the dynamic performance of MPTCP algorithms, we 287 implement a testbed topology as shown in Figure 2. In this scenario, 288 a MPTCP flow is long lived while 5 SPTCP flows start at 40s and end 289 at 80s. Table 2 shows the convergence time, which is defined as the 290 first time the congestion window on the second path via Router2 291 reaches the average congestion window after the SPTCP users have 292 left. 294 Router1 Router3 295 +--------+ +--------+ 296 1 MPTCP ----------| 20Mbps |----------| 40Mbps |-- Server 297 flow --\ | 10ms | /--| | 298 (0-200s) \ +--------+ / +--------+ 299 \ / 300 \ / 301 \ +--------+ / 302 \--| 20Mbps |--/ 303 5 SPTCP ----------| 10ms | 304 flows +--------+ 305 (40-80s) Router2 307 Figure 2: Testbed topology for the responsiveness scenario. 309 +------------------+-----------+----------+-----------+-----------+ 310 | | Coupled | OLIA | LIA | Balia | 311 +------------------+-----------+----------+-----------+-----------+ 312 | Convergence time | 94.36 | 58.5 | 17.75 | 14.73 | 313 +------------------+-----------+----------+-----------+-----------+ 314 Values are in seconds. 316 Table 2: Responsiveness: Convergence time of MPTCP user after SPTCP 317 users have left the network. 319 We observe that in this scenario Balia and LIA are quite responsive 320 while both Coupled and OLIA algorithms take an excessively long time 321 to recover. Note that in this scenario, the increment/decrement 322 algorithms of Coupled and those of OLIA are similar, and therefore 323 they behave in a similar way. For both algorithms, the excessively 324 slow recovery of the congestion window on the second path is due to 325 the design that increases the window roughly by w_r / (SUM(w_k))^2 on 326 each ACK assuming the RTTs are similar. After the SPTCP users have 327 left, w_2 is small while w_1 is large, so that w_2 / (w_1 + w_2)^2 is 328 very small. It therefore takes a long time for w_2 to increase to 329 its steady state value. In general, under the Coupled algorithm, a 330 route with a large throughput can greatly suppress the throughput on 331 another route even though the other route is underutilized. 333 5. Conclusion 335 In [PENG14], we have developed a model for MPTCP and identified 336 designs that guarantee the existence, uniqueness and stability of the 337 network equilibrium. We also characterize the design space and study 338 the tradeoff among TCP friendliness, responsiveness, and window 339 oscillation. Base on better understanding of the design space, our 340 new congestion control algorithm for MPTCP, Balia, generalizes prior 341 algorithms and strikes a good balance between friendliness and 342 responsiveness. Balia has been implemented in the Linux kernel and 343 tested in various scenarios. 345 6. References 347 6.1. Normative References 349 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 350 Requirement Levels", BCP 14, RFC 2119, March 1997. 352 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 353 Control", RFC 5681, September 2009. 355 [RFC6356] Raiciu, C., Handley, M., and D. Wischik, "Coupled 356 Congestion Control for Multipath Transport Protocols", RFC 357 6356, October 2011. 359 6.2. Informative References 361 [HONDA09] Honda, M., Nishida, Y., Eggert, L., Sarolahti, P., and H. 362 Tokuda, "Multipath congestion control for shared 363 bottleneck", PFLDNeT Workshop, 2009. 365 [KELLY05] Kelly, F. and T. Voice, "Stability of end-to-end 366 algorithms for joint routing and rate control", ACM 367 SIGCOMM Computer Communication Review, vol. 35, no. 2, pp. 368 5-12, 2005. 370 [HAN04] Han, H., Shakkottai, S., Hollot, C., Srikant, R., and D. 371 Towsley, "Overlay tcp for multi-path routing and 372 congestion control", IMA Workshop on Measurements and 373 Modeling of the Internet, 2004. 375 [KHALILI12] 376 Khalili, R., Gast, N., Popovic, M., Upadhyay, U., and J. 377 Le Boudec, "MPTCP is not Pareto-optimality: Performance 378 issues and a possible solution", ACM CoNext, 2012. 380 [MPLKI] UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux 381 kernel implementation", 2014, . 383 [PENG14] Peng, Q., Walid, A., Hwang, J., and S. Low, "Multipath 384 TCP: Analysis, Design and Implementation", 2014, 385 . 387 [DUMMYNET] 388 Carbone, M. and L. Rizzo, "Dummynet revisited", ACM 389 SIGCOMM Computer Communication Review, vol. 40, no. 2, pp. 390 12-20, 2010. 392 Authors' Addresses 394 Anwar Walid 395 Bell Labs 396 600 Mountain Ave 397 New Providence, NJ, USA 399 Email: anwar@research.bell-labs.com 401 Qiuyu Peng 402 Caltech 403 Department of Electrical Engineering 404 Pasadena, CA, USA 406 Email: qpeng@caltech.edu 408 Jaehyun Hwang 409 Bell Labs 410 Seoul, Republic of Korea 412 Email: jh.hwang@alcatel-lucent.com 414 Steven H. Low 415 Caltech 416 Department of Computing + Mathematical Sciences 417 Department of Electrical Engineering 418 Pasadena, CA, USA 420 Email: slow@caltech.edu