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