[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04

Multipath TCP                                                   A. Walid
Internet-Draft                                                 Bell Labs
Intended status: Standards Track                                 Q. Peng
Expires: January 22, 2015                                        Caltech
                                                                J. Hwang
                                                               Bell Labs
                                                                  S. Low
                                                                 Caltech
                                                           July 21, 2014


   Balanced Linked Adaptation Congestion Control Algorithm for MPTCP
                draft-walid-mptcp-congestion-control-00

Abstract

   This document describes the mechanism of Balia, the "Balanced linked
   adaptation", which is a congestion control algorithm for Multipath
   TCP (MPTCP).  The recent proposals, LIA and OLIA, suffer from either
   unfriendliness to Single Path TCP (SPTCP) or unresponsiveness to
   network changes under certain conditions.  The tradeoff between
   friendliness and responsiveness is inevitable, but Balia judiciously
   balances this tradeoff based on a new design framework that allows
   one to systematically explore the design space.  Balia has been
   implemented in the Linux kernel and there are plans to make it
   available for experimentation.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 22, 2015.








Walid, et al.           Expires January 22, 2015                [Page 1]


Internet-Draft          MPTCP Congestion Control               July 2014


Copyright Notice

   Copyright (c) 2014 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
     1.2.  Terminology . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Balanced Linked Adaptation Algorithm  . . . . . . . . . . . .   4
   3.  Theoretical justification . . . . . . . . . . . . . . . . . .   4
   4.  Experimental results  . . . . . . . . . . . . . . . . . . . .   5
     4.1.  Khalili's scenario  . . . . . . . . . . . . . . . . . . .   5
     4.2.  Responsiveness  . . . . . . . . . . . . . . . . . . . . .   7
   5.  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . .   8
   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     6.1.  Normative References  . . . . . . . . . . . . . . . . . .   8
     6.2.  Informative References  . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   Various congestion control algorithms have been proposed as
   extensions of TCP NewReno to MPTCP.  A straightforward extension is
   to run TCP NewReno on each subpath, e.g., [HONDA09].  This algorithm,
   however, can be highly unfriendly when it shares a path with a SPTCP
   user.  This motivates the Coupled algorithm which is fair because it
   has the same underlying utility function as TCP NewReno, e.g.,
   [KELLY05], [HAN04].  It is found in [RFC6356], however, that the
   Coupled algorithm responds slowly in a dynamic network environment.

   The current default congestion control algorithm for MPTCP, called
   LIA (Linked-Increases Algorithm), is more responsive than the Coupled
   algorithm.  However, it has been reported that LIA can sometimes be
   excessively aggressive toward SPTCP users without any benefit to
   multipath users [KHALILI12].  Recently, OLIA (Opportunistic Linked-
   Increases Algorithm) [KHALILI12] was proposed as a variant of Coupled



Walid, et al.           Expires January 22, 2015                [Page 2]


Internet-Draft          MPTCP Congestion Control               July 2014


   algorithm [KELLY05] which is as friendly as the Coupled algorithm.
   We have found, however, that OLIA can be unresponsive to changes in
   network conditions in some scenarios (e.g., when the paths used by a
   user have similar round trip times (RRTs)) [PENG14].

   In this draft, we introduce Balia, the "Balanced linked adaptation",
   which is a window-based congestion control algorithm for MPTCP.  The
   main design goal of Balia is to systematically tradeoff different
   properties such as TCP friendliness and responsiveness by developing
   structural understanding of MPTCP algorithms in a new design
   framework.  For instance, it is widely suspected that there is a
   tradeoff between friendliness and responsiveness and it is proved in
   this framework that this tradeoff is indeed inevitable.  By
   parameterizing different structural properties, Balia generalizes
   existing algorithms and explicitly balances the tradeoff.  We also
   prove mathematically that Balia has a unique equilibrium point, and
   that it is asymptotically stable.  Therefore, Balia can provide
   balanced performance in terms of friendliness and responsiveness.

   In [PENG14], we compare the performance of several MPTCP algorithms
   over a testbed, including Balia, OLIA and LIA.  Our experimental
   results show that Balia is friendlier than LIA and more responsive
   than OLIA.  It also solves LIA's problem identified by [KHALILI12].
   Balia has been implemented in the Linux kernel and there are plans to
   make it available for experimentation.

1.1.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

1.2.  Terminology

   Regular/Singlepath TCP (SPTCP): The standard version of TCP [RFC5681]
   that uses a single pair of IP address and ports per connection.

   Multipath TCP (MPTCP): A modified version of the regular TCP that
   simultaneously uses multiple paths between hosts.

   LIA: The Linked-Increases Algorithm for MPTCP [RFC6356].

   OLIA: The Opportunistic Linked-Increases Algorithm for MPTCP
   [KHALILI12].

   Balia: The Balanced linked adaptation algorithm for MPTCP [PENG14].





Walid, et al.           Expires January 22, 2015                [Page 3]


Internet-Draft          MPTCP Congestion Control               July 2014


   AIMD: The Additive Increase Multiplicative Decrease algorithm used in
   TCP congestion avoidance.

   w_r: The congestion window on a path r.

   rtt_r: The Round-Trip Time (RTT) on a path r.

2.  Balanced Linked Adaptation Algorithm

   Balia is a generalized MPTCP algorithm that strikes a good balance
   between friendliness and responsiveness.  The algorithm only applies
   to the AIMD part of the congestion avoidance phase.  The other parts
   such as slow start, fast retransmit/recovery algorithms are the same
   as in TCP [RFC5681].  The minimum ssthresh is set to 1 MSS instead of
   2 when more than 1 path is available.

   Each source s has a set of paths r.  As a special case, the set can
   be a singleton in which case Balia reduces to TCP Reno (see below).
   Each path r maintains a congestion window w_r and measures its round-
   trip time rtt_r.  The window adaptation of Balia is as follows:

   - For each ACK on path r, increase w_r by:

                x_r             1 + alpha_r       4 + alpha_r
       -------------------- * ( ----------- ) * ( ----------- )
       rtt_r * (SUM(x_k))^2          2                 5

   - For each packet loss on path r, decrease w_r as:

        w_r
       -----  *  min { alpha_r,  1.5 }
         2

   where x_r = w_r / rtt_r and alpha_r = max { x_r } / x_r.

   Note that Balia's decrement algorithm multiplies the MD algorithm of
   TCP Reno by a factor in the range of [1, 1.5].

   If a Balia user uses only a single path, then alpha_r = 1, in which
   [case] both the increment and the decrement algorithms of Balia
   reduces to those of TCP Reno.  Hence Balia reduces to TCP Reno on
   single paths.

3.  Theoretical justification

   In [PENG14], we have developed a unified model of MPTCP algorithms
   and characterized the design space.  This provides a framework to
   systematically design MPTCP algorithms and analyze their behavior in



Walid, et al.           Expires January 22, 2015                [Page 4]


Internet-Draft          MPTCP Congestion Control               July 2014


   a large network at design time.  For instance, it has allowed us to
   identify designs that guarantee the existence, uniqueness and
   stability of network equilibrium.  Balia is designed using this
   framework to achieve specific design goals.  In this section, we will
   focus on how Balia balances three often conflicting design goals, TCP
   friendliness, responsiveness and window oscillation.

   TCP friendliness characterizes how much more throughput a MPTCP flow
   will get when it competes with an SPTCP flow.  A MPTCP flow is said
   to be "TCP friendly" if it does not dominate the available bandwidth
   when it shares the same network with a SPTCP flow.

   Responsiveness characterizes how fast the MPTCP algorithm reacts to
   changes in network conditions.

   The window oscillation property characterizes how severely the window
   size fluctuates around the equilibrium point.  It is an inherent
   property of AIMD-like algorithms.

   In [PENG14], it is proved mathematically that there is an inevitable
   tradeoff between TCP friendliness and responsiveness, and between
   responsiveness and window oscillation.  Thus, it is theoretically
   impossible to maximize the performance in all three metrics
   simultaneously.

   Our design philosophy is to allow window oscillation up to an
   acceptable level in order to improve both friendliness and
   responsiveness.  This is achieved by explicitly parameterizing these
   properties and systematically choosing these parameters.

4.  Experimental results

   In this section, we summarize our experimental results that
   illustrate the weaknesses of the current algorithms (LIA and OLIA).
   We evaluate the MPTCP algorithms using a reference Linux
   implementation of MPTCP, Multipath TCP v0.88 [MPLKI], based on the
   Linux kernel 3.11.8.  The network parameters such as network
   bandwidth and delay are implemented by Dummynet [DUMMYNET].  Iperf is
   used to generate traffic and measure the throughput.

4.1.  Khalili's scenario

   In [KHALILI12], it has been revealed that LIA can be unfriendly to
   SPTCP users even when its own MPTCP throughput is saturated.  That
   is, the throughputs of SPTCP flows are significantly degraded without
   any benefit to MPTCP flows.  To reproduce this scenario, we create a
   testbed as shown in Figure 1.  In this scenario, N1 type1 users can




Walid, et al.           Expires January 22, 2015                [Page 5]


Internet-Draft          MPTCP Congestion Control               July 2014


   be either single path or multipath while N2 type2 users are always
   single path.

                                               +----+
         N1                                    |    |   Server
        Type1 ---------------------------------| C1 |-- for type1
        flows --\                           /--|    |   flows
                 \                         /   +----+
                  \                       /    Router1
                   \   +----+   +----+   /
                    \--|    |   |    |--/
         N2            | C2 |---|    |                   Server
        Type2 ---------|    |   |    |------------------ for type2
        flows          +----+   +----+                   flows
                       Router2  Router3

   Figure 1: Testbed topology for Khalili's scenario.  The Router1
   emulates the server-side bottleneck for type1 users and the Router2
   emulates the shared bottleneck.

   The aggregate throughputs of these users are shown in Table 1 for the
   case when all users are SPTCP and the case when all type1 users are
   upgraded to MPTCP users using different algorithms.  We observe that
   upgrading type1 users to MPTCP decreases type2 users' throughput
   without any benefit to type1 users if LIA is used; the type2 users
   are worse off by 19% when N1=N2=5 and by 25% when N1=15 and N2=5.
   Both OLIA and Balia are more friendly than LIA to SPTCP (type2)
   users.

     C1=C2=10Mbps
                  +-------------+----------------------------------+
                  | Type1 users |     Type1 users are multipath    |
                  |     are     +-----------+----------+-----------+
                  | single path |    LIA    |   OLIA   |   Balia   |
           +------+-------------+-----------+----------+-----------+
     N1=5  |type1 |    9.47     |    9.26   |   9.25   |   9.25    |
           +------+-------------+-----------+----------+-----------+
     N2=5  |type2 |    9.29     |    7.55   |   8.13   |   8.32    |
     ------+------+-------------+-----------+----------+-----------+
     N1=15 |type1 |    9.39     |    8.96   |   8.93   |   9.02    |
           +------+-------------+-----------+----------+-----------+
     N2=5  |type2 |    9.29     |    6.94   |   7.41   |   7.98    |
           +------+-------------+-----------+----------+-----------+
     Values are in Mbps.

   Table 1: Throughput obtained by type1 and type2 users: Upgrading
   type1 users to MPTCP decreases type2 users' throughput without any
   benefit to type1 users.



Walid, et al.           Expires January 22, 2015                [Page 6]


Internet-Draft          MPTCP Congestion Control               July 2014


4.2.  Responsiveness

   To demonstrate the dynamic performance of MPTCP algorithms, we
   implement a testbed topology as shown in Figure 2.  In this scenario,
   a MPTCP flow is long lived while 5 SPTCP flows start at 40s and end
   at 80s.  Table 2 shows the convergence time, which is defined as the
   first time the congestion window on the second path via Router2
   reaches the average congestion window after the SPTCP users have
   left.

                            Router1             Router3
                          +--------+          +--------+
        1 MPTCP ----------| 20Mbps |----------| 40Mbps |-- Server
          flow  --\       |  10ms  |       /--|        |
        (0-200s)   \      +--------+      /   +--------+
                    \                    /
                     \                  /
                      \   +--------+   /
                       \--| 20Mbps |--/
        5 SPTCP ----------|  10ms  |
          flows           +--------+
        (40-80s)            Router2

   Figure 2: Testbed topology for the responsiveness scenario.

   +------------------+-----------+----------+-----------+-----------+
   |                  |  Coupled  |   OLIA   |    LIA    |   Balia   |
   +------------------+-----------+----------+-----------+-----------+
   | Convergence time |   94.36   |   58.5   |   17.75   |   14.73   |
   +------------------+-----------+----------+-----------+-----------+
   Values are in seconds.

   Table 2: Responsiveness: Convergence time of MPTCP user after SPTCP
   users have left the network.

   We observe that in this scenario Balia and LIA are quite responsive
   while both Coupled and OLIA algorithms take an excessively long time
   to recover.  Note that in this scenario, the increment/decrement
   algorithms of Coupled and those of OLIA are similar, and therefore
   they behave in a similar way.  For both algorithms, the excessively
   slow recovery of the congestion window on the second path is due to
   the design that increases the window roughly by w_r / (SUM(w_k))^2 on
   each ACK assuming the RTTs are similar.  After the SPTCP users have
   left, w_2 is small while w_1 is large, so that w_2 / (w_1 + w_2)^2 is
   very small.  It therefore takes a long time for w_2 to increase to
   its steady state value.  In general, under the Coupled algorithm, a
   route with a large throughput can greatly suppress the throughput on
   another route even though the other route is underutilized.



Walid, et al.           Expires January 22, 2015                [Page 7]


Internet-Draft          MPTCP Congestion Control               July 2014


5.  Conclusion

   In [PENG14], we have developed a model for MPTCP and identified
   designs that guarantee the existence, uniqueness and stability of the
   network equilibrium.  We also characterize the design space and study
   the tradeoff among TCP friendliness, responsiveness, and window
   oscillation.  Base on better understanding of the design space, our
   new congestion control algorithm for MPTCP, Balia, generalizes prior
   algorithms and strikes a good balance between friendliness and
   responsiveness.  Balia has been implemented in the Linux kernel and
   tested in various scenarios.

6.  References

6.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC5681]  Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
              Control", RFC 5681, September 2009.

   [RFC6356]  Raiciu, C., Handley, M., and D. Wischik, "Coupled
              Congestion Control for Multipath Transport Protocols", RFC
              6356, October 2011.

6.2.  Informative References

   [HONDA09]  Honda, M., Nishida, Y., Eggert, L., Sarolahti, P., and H.
              Tokuda, "Multipath congestion control for shared
              bottleneck", PFLDNeT Workshop, 2009.

   [KELLY05]  Kelly, F. and T. Voice, "Stability of end-to-end
              algorithms for joint routing and rate control", ACM
              SIGCOMM Computer Communication Review, vol. 35, no. 2, pp.
              5-12, 2005.

   [HAN04]    Han, H., Shakkottai, S., Hollot, C., Srikant, R., and D.
              Towsley, "Overlay tcp for multi-path routing and
              congestion control", IMA Workshop on Measurements and
              Modeling of the Internet, 2004.

   [KHALILI12]
              Khalili, R., Gast, N., Popovic, M., Upadhyay, U., and J.
              Le Boudec, "MPTCP is not Pareto-optimality: Performance
              issues and a possible solution", ACM CoNext, 2012.





Walid, et al.           Expires January 22, 2015                [Page 8]


Internet-Draft          MPTCP Congestion Control               July 2014


   [MPLKI]    UCL, Louvain-la-Neuve, Belgium, "MultiPath TCP-Linux
              kernel implementation", 2014, <http://multipath-tcp.org/>.

   [PENG14]   Peng, Q., Walid, A., Hwang, J., and S. Low, "Multipath
              TCP: Analysis, Design and Implementation", 2014,
              <http://arxiv.org/abs/1308.3119v2>.

   [DUMMYNET]
              Carbone, M. and L. Rizzo, "Dummynet revisited", ACM
              SIGCOMM Computer Communication Review, vol. 40, no. 2, pp.
              12-20, 2010.

Authors' Addresses

   Anwar Walid
   Bell Labs
   600 Mountain Ave
   New Providence, NJ, USA

   Email: anwar@research.bell-labs.com


   Qiuyu Peng
   Caltech
   Department of Electrical Engineering
   Pasadena, CA, USA

   Email: qpeng@caltech.edu


   Jaehyun Hwang
   Bell Labs
   Seoul, Republic of Korea

   Email: jh.hwang@alcatel-lucent.com


   Steven H. Low
   Caltech
   Department of Computing + Mathematical Sciences
   Department of Electrical Engineering
   Pasadena, CA, USA

   Email: slow@caltech.edu







Walid, et al.           Expires January 22, 2015                [Page 9]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/