Ramin Khalili

Nicolas Gast

Miroslav Popovic

Jean-Yves Le Boudec

MPTCP is not Pareto-Optimal: Performance Issues and a Possible Solution

MPTCP has been proposed recently as a mechanism for transparently supporting multiple connections to the application layer. It is under discussion at the IETF. We nevertheless demonstrate that the current MPTCP suffers from two problems: (P1) Upgrading some TCP users to MPTCP can reduce the throughput of others without any benefit to the upgraded users, which is a symptom of not being Pareto-optimal; and (P2) MPTCP users could be excessively aggressive towards TCP users. We attribute these problems to the linked-increases algorithm (LIA) of MPTCP and, more specifically, to an excessive amount of traffic transmitted over congested paths.

The design of LIA forces a tradeoff between optimal resource pooling and responsiveness. We revisit the problem and show that it is possible to provide these two properties simultaneously. We implement the resulting algorithm, called the opportunistic linked-increases algorithm (OLIA), in the Linux kernel, and we study its performance over our testbed, by simulations and by theoretical analysis. We prove that OLIA is Pareto-optimal and satisfies the design goals of MPTCP. Hence it can avoid the problems P1 and P2. Our measurements and simulations indicate that MPTCP with OLIA is as responsive and non-flappy as MPTCP with LIA and that it solves problems P1 and P2.

. This term is essential to provide Pareto-optimality.

• The second term guarantees responsiveness and nonflappiness of OLIA. By measuring the number of transmitted bits since the last loss, it reacts to events within the current window and adapts to changes faster than the first term.

I. INTRODUCTION

The regular TCP uses a window-based congestion-control mechanism to adjust the transmission rate of users [START_REF] Allman | Tcp congestion control[END_REF]. It always provides a Pareto-optimal allocation of resources: it is impossible to increase the throughput of one user without decreasing the throughput of another or without increasing the congestion cost [START_REF] Frank | Mathematical modelling of the internet[END_REF]. It also guarantees a fair allocation of bandwidth among the users, but favors the connections with lower RTT [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF].

Various mechanisms were used to build a multipath transport protocol compatible with the regular TCP. Authors of [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]- [START_REF] Wang | Optimal flow control and routing in multi-path networks[END_REF] propose a family of algorithms inspired by utility maximization frameworks. These algorithms tend to use only the best paths available to users and are optimal in static settings where paths have similar RTTs. In practice, however, they suffer from several problems [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF]- [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF]. First, they sometimes fail to quickly detect free capacity, because they do not probe paths with high loss probabilities sufficiently. Second, they exhibit flappiness: When there are multiple good paths available to a user, the user will randomly flip its traffic between these paths. This is not desirable, specifically, when the achieved rate depends on RTTs, as with TCP.

This research has received funding from the EU 7th Framework Programme (FP7/2007-2013) under grant agreement n. 257740 (Network of Excellence "TREND").

Ramin Khalili is with T-Labs/TU-Berlin e-mail: ramin@net.t-labs.tuberlin. de Nicolas Gast, Miroslav Popovic and Jean-Yves Le Boudec are with EPFL, IC-LCA2, Switzerland. e-mail: firstname.lastname@epfl.ch MultiPath TCP (MPTCP) is a concrete proposal for multipath transport; it is under discussion at the IETF [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF]. Because of the issues aforementioned, its congestion control part does not follow the algorithms in [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]- [START_REF] Wang | Optimal flow control and routing in multi-path networks[END_REF]. Instead, it follows an adhoc design based on three goals [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF]: [START_REF] Allman | Tcp congestion control[END_REF] Improve throughput: a multipath TCP user should perform at least as well as a TCP user that uses the best path available to it. (2) Do no harm: a multipath TCP user should never take up more capacity from any of its paths than a TCP user. And (3) balance congestion: a multipath TCP algorithm should balance congestion in the network, subject to meeting the first two goals.

MPTCP compensates for different RTTs and solves many problems of multipath transport [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF], [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF]: It can effectively use the available bandwidth; compared to independent TCP flows, it improves throughput and fairness in many scenarios; and it solves the flappiness problem. Through analysis and by using measurements over a testbed, we nevertheless demonstrate that MPTCP still suffers from the following problems: (P1) Upgrading some regular TCP users to MPTCP can reduce the throughput of other users without any benefit to the upgraded users. Hence, MPTCP is not Pareto-optimal. (P2) MPTCP users could be excessively aggressive towards TCP users.

We attribute these problems to the "linked increases" algorithm (LIA) of MPTCP [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF] and specifically to an excessive amount of traffic transmitted over congested paths. These problems indicate that MPTCP fails to fully satisfy its design goals, especially goal 3. The design of LIA forces a tradeoff between optimal resource pooling and responsiveness, it cannot provide both at the same time. Hence, to provide good responsiveness, LIA's current implementation must depart from Pareto-optimality, which leads to problems P1 and P2. We revisit the design and show that it is possible to simultaneously provide both properties. We introduce OLIA, the "opportunistic linkedincreases algorithm", as an alternative to LIA. Based on utility maximization frameworks, we prove that OLIA is Pareto-optimal. Hence it can avoid the problems P1 and P2. Furthermore, its construction makes it as responsive and nonflappy as LIA.

OLIA is a window-based congestion-control mechanism. Similarly to LIA, it couples the additive increases and uses unmodified TCP behavior in the case of a loss. OLIA's increase part, Equation [START_REF] Han | Multipath tcp: a joint congestion control and routing scheme to exploit path diversity in the internet[END_REF], has two terms: By adapting the window increases as a function of RTTs, OLIA also compensates for different RTTs.

We implement OLIA in the Linux kernel and study its performance over our testbed, by simulations and by theoretical analysis. Using a fluid model of OLIA based on differential inclusion, we prove that OLIA is Pareto-optimal (Theorem 3) and that it satisfies the design goals of MPTCP (Corollary 2). Our measurements and simulations indicate that MPTCP with OLIA is as responsive and non-flappy as MPTCP with LIA and it solves problems P1 and P2. Note that OLIA is now part of the Louvain MPTCP implementation [11].

A recent study by Chen et al. [START_REF] Chen | A measurement-based study of multipath tcp performance over wireless networks[END_REF] shows that MPTCP with OLIA always outperforms MPTCP with LIA in wireless networks and is very responsive to the changes in the environment. These results confirm our findings in this paper. Hence, we believe that MPTCP working group in IETF [13] should revisit the congestion control part of MPTCP and that an alternative algorithm, such as OLIA, should be considered.

In the next section, we briefly introduce MPTCP and LIA and discuss related work. In Section III, we provide a number of examples and scenarios where MPTCP with LIA exhibits problems P1 and P2. In Section IV, we introduce OLIA and detail its Linux implementation. In Section V, we prove that OLIA is Pareto-optimal and satisfies MPTCP's design goals. In Section VI, we study the performance of OLIA through measurements and by simulations.

II. MPTCP AND RELATED WORK

Multipath TCP (MPTCP) is a set of extensions to the regular TCP, which allows users to spread their traffic across potentially disjoint paths [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF]. MPTCP discovers the number of paths available to a user, establishes the paths, and distributes traffic across these paths through creation of separate subflows [START_REF] Ford | Architectural guidelines for multipath tcp development[END_REF], [START_REF] Ford | Tcp extensions for multipath operation with multiple addresses[END_REF]. The congestion control algorithm of MPTCP is inspired by the utility frameworks of [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF], [START_REF] Han | Multipath tcp: a joint congestion control and routing scheme to exploit path diversity in the internet[END_REF] which provide optimal resources pooling. However, it departs from the optimal resource pooling principle [START_REF] Wischik | The resource pooling principle[END_REF] to avoid flappiness and to improve response time [START_REF] Wischik | Control of multipath tcp and optimization of multipath routing in the internet[END_REF], [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF], [START_REF] Raiciu | Practical congestion control for multipath transport protocols[END_REF].

Congestion control algorithm of MPTCP forces a tradeoff between optimal resource pooling and responsiveness [START_REF] Wischik | Control of multipath tcp and optimization of multipath routing in the internet[END_REF]. The idea behind the algorithm is to transmit over a path r at a rate proportional to p -1/ε r , where p r is the loss probability over this link and ε ∈ [0, 2] is a design parameter. The choice ε = 0 corresponds to the fully coupled algorithm of [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]- [START_REF] Wang | Optimal flow control and routing in multi-path networks[END_REF]: the traffic is sent only over the best paths, it is Pareto-optimal but is flappy. The choice ε = 2 corresponds to using uncoupled TCP flows on each path: it is very responsive and non-flappy, but does not balance congestion. MPTCP's implementation uses ε = 1 to provide a compromise between optimal resource pooling and responsiveness. This algorithm is called "linked increases" algorithm (LIA) [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF].

Let w r and rtt r be the window size and the estimated roundtrip time on path r ∈ R u . R u is the set of all paths available to user u. LIA works as follows:

• For each ACK on subflow r, increase w r by

min max i∈Ru w i /rtt 2 i ( i∈Ru w i /rtt i ) 2 , 1 w r . (1)
• For each loss on subflow r, decrease w r by w r /2. LIA increases by at most 1/w r to be at most as aggressive as regular TCP on any of its paths. When the RTTs are similar, this minimum can be neglected as the first term (max i w i /rtt 2 i )/( i w i /rtt i ) 2 will always be less than 1/w r . In this case, a fixed point analysis provides a simple lossthroughput formula for LIA [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF]: LIA allocates to a path r a window w r proportional to the inverse of the loss probability 1/p r and such that the total rate p∈Ru w p /rtt p equals the rate that a regular TCP user would get on the best path, i.e. max p∈Ru 2/p p /rtt p . Thus, the window size for the flow on a path r is given by

w r = 1 p r • max p∈Ru 2/p p /rtt p p∈Ru 1/(rtt p p p ) . (2)
Hence, two paths with similar qualities get equal windows, removing flappiness. When the path qualities differ, a larger window is allocated to the path with higher rate, providing some load balancing.

Besides MPTCP and algorithms in [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]- [START_REF] Wang | Optimal flow control and routing in multi-path networks[END_REF], a few other algorithms have been proposed to implement multipath protocols. In [START_REF] Cetinkaya | Opportunistic traffic scheduling over multiple network paths[END_REF], an opportunistic multipath scheduler measures the path conditions on time scales up to several seconds. [START_REF] Zhang | A transport layer approach for improving end-to-end performance and robustness using redundant paths[END_REF] uses a mechanism to detect shared bottlenecks and to avoid the use of multiple subflows on the same bottleneck. [START_REF] Honda | Multipath congestion control for shared bottleneck[END_REF] proposes to use uncoupled TCP flows with a weight depending on the congestion level. These mechanisms are complex, their robustness is not clear, and they need explicit information about congestion in the network. Our proposed algorithm, OLIA, differs from these works as it is implemented, proven to be Pareto optimal, and relies only on information that is available to regular TCP. It also differs from [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF]- [START_REF] Wang | Optimal flow control and routing in multi-path networks[END_REF] as it is not flappy and has a better responsiveness.

III. PERFORMANCE PROBLEMS OF MPTCP

In this section, we investigate the behavior of MPTCP with LIA in three different scenarios: A, B, and C. Using scenarios A and B, we show that upgrading some regular TCP users to MPTCP could reduce the throughput of other users in the network without any benefit to the upgraded users (problem P1). In Scenario C, we discuss the aggressiveness of MPTCP users that compete with regular TCP users (problem P2). Our conclusions are based on analytical results and measurements.

Testbed Setup

To investigate the behavior of the algorithms, we create three testbed topologies that represent our scenarios. Serverclient PCs run MPTCP (with LIA or OLIA) enabled Linux kernels. In all scenarios laptop PCs are used as routers. We install "Click Modular Router" software [START_REF] Kohler | The click modular router[END_REF] to emulate topologies with different characteristics. This is possible as Click allows custom manipulation of packets from the moment they arrive at one of the interfaces until the moment they leave the router. Figure 2 represents the testbed configuration of the scenario described in Figure 1(a).

We emulate links with configurable bandwidth and delay with RED queuing (drop-tail queuing is also studied in the simulations that use htsim, see Section VI-B). We set the propagation delay, the round-trip time between a sender and a receiver over an uncongested path, to 80 ms. For a 10 Mbps link, we set the dropping probability equal to 0 up to a queue size of min th = 25. Then it grows linearly to the value 0.1 at max th = 50. It again increases linearly up to 1 at 2max th . The queue size is set to 300 packets. The parameters are proportionally adapted when the link capacity changes. This results to an average queuing delay of 70 ms in the queues, as observed by measurements. We use Iperf to generate the traffic which emulates bulk transfers of large sizes. Each Iperf session runs for 120 second to allow the flows to reach equilibrium. The flows are initiated in the random order, adding some more randomness to our experiment.

A. Scenario A: MPTCP is not Pareto-Optimal and penalizes regular TCP users Consider a network with two types of users as shown in Figure 1(a). There are N 1 users of type1, each with a high-speed private connection, accessing different files on a media streaming server. The server has a network connection with capacity limit of N 1 C 1 Mbps. These users can activate a second connection through a shared access point (AP) by using MPTCP. There are also N 2 type2 users that have connections only through the shared AP, downloading their contents from the Internet. The shared AP has a capacity of N 2 C 2 Mbps.

Let x 1 be the rate that a type1 user receives over its private connection. By symmetry, every user of type1 will receive the same rate x 1 . Similarly, let x 2 (resp. y) be the rate that a type1 (resp. type2) user receives over the shared connection. We denote by p 1 and p 2 the loss probability at the link connected to the streaming server and the shared AP, respectively. The loss probabilities at the Internet backbone and the private APs are assumed negligible.

When type1 users use only their own private AP, we have x 1 =C 1 , x 2 =0, and y=C 2 . In this case the normalized throughput for both type1 and type2 users is 1. In the other case, assuming that all paths have RTT rtt, when all type1 users activate their public connections and use MPTCP with LIA to balance load between their connections, we have

(a) N 1 (x 1 +x 2 ) = N 1 C 1 N 1 x 2 + N 2 y = N 2 C 2 (b) x 1 + x 2 = 1 rtt 2 p1 x 2 = 1 2+p2/p1 1 rtt 2 p1 (c) y = 1 rtt 2/p 2
where (a) are the capacity constraints at the two bottlenecks, (b) comes from the loss-throughput formula for LIA (Eq. ( 2)), and (c) follows the TCP loss-throughput formula [START_REF] Misra | Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED[END_REF]. This system has a unique solution (see Appendix A). Figure 1(b) depicts the normalized throughput of type1 and type2 users, i.e. (x 1 + x 2 )/C 1 and y/C 2 . As shown in Appendix A, these values depend only on the ratios C 1 /C 2 and N 1 /N 2 .

A theoretically optimal algorithm (as discussed in [START_REF] Kelly | Stability of end-to-end algorithms for joint routing and rate control[END_REF], [START_REF] Han | Multipath tcp: a joint congestion control and routing scheme to exploit path diversity in the internet[END_REF]) will allocate a normalized throughput of 1 to both type1 and type2 users. In practice, however, the value of the congestion windows are bounded below by 1 MSS. Hence, with a window-based congestion-control algorithm, a minimum probing traffic of 1 MSS per RTT will be sent over an established path. In this paper, we introduce a theoretical baseline for window-based congestion-control algorithms, called theoretical optimum with probing cost; it provides optimal resource pooling in the network, given that a minimum probing traffic of 1 MSS per RTT is sent over each path. It serves as a reference to see how far from the optimum LIA is.

We measure the performance of LIA in Scenario A, by using the testbed, as shown in Figure 2. PC1 and PC2 run MPTCP enabled Linux kernel implementation and have two Ethernet interfaces. PC3 and PC4 use regular TCP. Within router PCs R1 and R2, we emulate links with capacities N 1 C 1 and N 2 C 2 modeling respectively the bottleneck at the server side and the shared AP. With Iperf we generate independent MPTCP connections between PC1 and PC2 and regular TCP connections between PC3 and PC4.

The measurements are taken for N 2 = 10 and three values of N 1 = 10, 20, 30. The capacities of R1 and R2 are N 1 C 1 and N 2 C 2 Mbps, where we set C 2 = 1Mbps and C 1 = 0.75, 1, 1.5 Mbps. All paths have similar RTTs (link delay plus queuing delay is around 150 ms over all paths). For each case, we took 5 measurements. The results are reported in Figure 1(b). Note that in all cases we present 95% confidence intervals, but in many cases they are too small to be visible. We also show our analytical analysis of LIA, as well as the theoretical optimum with probing cost as defined above. Note that the network setting is very static and the randomness of our results mainly comes from the congestion losses at the queues and the fact that the flows are initiated in the random order. Moreover, the queuing delay in a queue depends on its queue size and is therefore random.

These figures have multiple implications. First, they show that MPTCP with LIA exhibits problem (P1) from the introduction: upgrading type1 users to MPTCP penalizes type2 users without any gain for type1 users. As the number of type1 users increases, the throughput of type2 users decreases, but the throughput of type1 users does not change as it is limited by the capacity C 1 of the streaming server. For N 1 =N 2 , type2 users see a decrease of about 30% in their throughput. When N 1 =3N 2 , this decrease is between 50% to 60%. This is explained by the fact that LIA does not fully balance congestion, as shown in Figure 1(c). It excessively increases congestion on the shared AP (not in compliance with goal 3). Note that p 1 depends only on C 1 . Our measurements show that in average p 1 = 0.02, 0.009, 0.004 for C 1 = 0.75, 1, 1.5 Mbps, respectively. Hence, we observe that LIA performs far from how an optimal algorithm with probing cost would perform. Furthermore, these figures show that the fixed point analysis predicts accurately the behavior of the algorithm: the theoretical and experimental curves exhibit the same trend.

B. Scenario B: MPTCP is not Pareto-optimal and can penalize other MPTCP users.

Consider the multi-homing scenario depicted in Figure 3. We have four Internet Service Providers, ISPs, X, Y , Z, and T . Y is a local ISP in a small city, which connects to the Internet through Z. X, Z, and T are nation-wide service providers and are connected to each other through high speed Z and T host different video streaming servers. There are two types of users: N B Blue users download contents from a server in Z, and N R Red users download from a server in ISP T . Blue users use multi-homing and are connected to both ISPs X and Y to increase their reliability. Red users can connect either only to Y or to both X and Y . We assume that only ISPs X and T are bottlenecks and denote by p X and p T the loss probabilities. All paths have similar RTTs.

We first present a theoretical analysis of the rate that each user would achieve using MPTCP. To simplify the analysis, we assume similar numbers of Blue and Red users. There are two possible cases. When Red users connect only to Y , the analysis is the same as the one of scenario C, given in Section III-C. Here, we analyze the case when Red users upgrade to MPTCP. The loss throughput formula (Eq. ( 2)) shows that the throughput of the different connections are:

       y 1 = 1/rtt 2 + p X p T 2 p T y 2 = p X + p T p T y 1 ,        x 1 = 1/rtt 1 + p X /p T max 2 p X , 2 p T x 2 = 1/rtt 1 + p T /p X max 2 p X , 2 p T
As shown in Appendix B, this set of equations has a unique positive solution. A numerical evaluation of these formulas is depicted in Figure 4(a). This decrease is about 3% when we use an optimal algorithm with probing cost (Figure 4(b)).

We emulate this scenario in our testbed in a similar manner as for Scenario A. The measurement results are reported in Table I for a similar setting with C X = 27 Mbps. We observe that when Red users only connect to ISP Y, the aggregate throughput of users is close to the cut-set bound, 63 Mbps. However, Blue users get a higher share of the network bandwidth. Now consider that Red users upgrade to MPTCP by establishing a second connection through X (shown by dashed line in Figure 3). Our results in Table I show that Red users do not receive any higher throughput. However, the average rate of Blue users drops by 20%, which results in a drop of 13% in aggregate throughput.

C. Scenario C: MPTCP users could be excessively aggressive towards TCP users.

We consider a scenario with N 1 multipath users, N 2 singlepath users, and two APs with capacities N 1 C 1 and N 2 C 2 Mbps (see Figure 5). Multipath users connect to both APs and they share AP2 with single-path users.

If the allocation of rates is proportionally fair, multipath users will use AP2 only if C 1 <C 2 and all users will receive

(N 1 C 1 +N 2 C 2 )/(N 1 + N 2 ). When C 1 > C 2 ,
a fair multipath user will not transmit over AP2. This fair allocation is represented by dashed lines in Figure 5(b) when we take into account the minimum probing cost (the analysis is similar to what we proposed in Appendix B, Case1). However, using MPTCP with LIA, multipath users get a larger share of bandwidth as soon as

C 1 ≥ C 2 /(2+N 1 /N 2 ).
Let p 1 and p 2 be the loss probabilities at APs, x 1 and x 2 be rates that a multipath user receives over its paths, and y be the rate of a single-path user. Assume all RTTs are the same. When C 1 /C 2 < 1/(2+N 1 /N 2 ), we have p 1 > p 2 and all users receive the same rate:

x 1 +x 2 = y = (C 1 +C 2 )/2. When C 1 /C 2 > 1/(2+N 1 /N 2 )
, we have p 1 < p 2 and the fixed point formula of LIA gives:

x 1 = p 2 p 1 + p 2 1 rtt 2 p 1 and x 2 = p 1 p 1 + p 2 1 rtt 2 p 1 .
Moreover, both the APs are bottlenecks and we have

x 1 = C 1 and x 2 + y = C 2 . Let z := p 1 /p 2 .
Using that the TCP loss throughput formula, y = 2/p 2 , the quantity z is the unique positive root of:

z 3 + N 1 N 2 z 2 + z - C 2 C 1 .
The normalized throughputs of multipath users are

(x 1 + x 2 )/C 1 = (1 + p 1 /p 2 )/C 1 = 1 + z 2 .
The single path users receive a rate of y/C 2 = 1 -N1C1 N2C2 z 2 . Again, this quantity only depends on the ratio N 1 /N 2 and C 1 /C 2 .

Figure 5(b) reports a numerical evaluation of these fixed point equations for the case N 1 = N 2 . We show the normalized throughputs ((x 1 +x 2 )/C 1 and y/C 2 ) received by the users, as well as p 2 . We observe that LIA is fair with regular TCP users, as long as C 1 < C 2 /3. However, as C 1 exceeds C 2 /3, it takes most of the capacity of AP2 for itself.

We emulate the scenario in our testbed and measure the performance of MPTCP with LIA. The results are reported in Figures 5(c) and 5(d) for C 2 =1 Mbps and C 1 =1, 2Mbps, with N 2 =10 and N 1 =5, 10, 20, 30. As in scenario A, we also present the theoretical optimum with probing cost in Figure 5(c). When C 1 /C 2 ≥ 1, multipath users should not use AP2 at all. However, our results show that, MPTCP users are disproportionately aggressive and exhibit problem (P2). Figure 5(d) shows the loss probability at AP2. We observe that LIA excessively increases congestion on AP2 and is unable to fully balance congestion in the network. Also, we have p 1 =0.01 and 0.003 for C 1 =1 and 2Mbps, respectively.

IV. OLIA: THE OPPORTUNISTIC LINKED INCREASES ALGORITHM In this section, we introduce OLIA as an alternative for MPTCP's LIA. OLIA is a window-based congestion-control algorithm that couples the increase of congestion windows and uses unmodified TCP behavior in the case of a loss. The increase part of OLIA has two terms. The first term is an adaptation of Kelly and Voice's increase term and provides the Pareto-Optimality. Kelly and Voice's algorithm is based on scalable TCP; the first term is a TCP compatible version of their algorithm that compensates also for different RTTs. The second term, with α, guarantees responsiveness and non-flappiness. We first present the algorithm and its Linux implementation. Then, we illustrate with an example its operation and its difference with LIA.

A. Detailed Description of OLIA

Let R u be the set of paths available to user u and let r ∈ R u be a path. We denote by 1r (t) the number of bits that were successfully transmitted by u over path r between the last two losses seen on r, and by 2r (t) the number of bits that are successfully transmitted over r after the last loss. If no losses have been observed on r up to time t, then 1r (t) = 0 and 2r (t) is the total number of bits transmitted on r. Also, let r (t) = max{ 1r (t), 2r (t)} and let rtt r (t) and w r (t) be respectively RTT and the window on r at time t. We define

M(t) = i(t) | i(t) = arg max p∈Ru w p (t) (3)
B(t) = j(t) | j(t) = arg max p∈Ru p (t) rtt p (t) 2 (4)
M(t) is the set of the paths of u with the largest window sizes at time t. B(t) is the set of the paths at time t that are presumably the best paths for u: 1/ r (t) can be considered as an estimate of packet loss probability on path r at time t, and hence the rate that path r can provide to a TCP user can be estimated by 2 r (t)/rtt r [START_REF] Misra | Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED[END_REF].

Our algorithm is as follows (to simplify notation, we drop the time argument t; however, note that w r , rtt r , r , M, and B are all functions of time):

• For each ACK on path r, increase w r by:

w r /rtt 2 r ( p∈Ru w p /rtt p ) 2 + α r w r , (5)
where α r is calculated as follows:

α r =            1/|R u | |B \ M| if r ∈ B \ M = ∅ - 1/|R u | |M| if r ∈ M and B \ M = ∅ 0 otherwise. ( 6
)
B\M is the set of elements in B but not in M, ∅ is the empty set, and |R u | is the number of paths available to u at the time. Note that r∈Ru α r =0. • For each loss on path r, decrease w r by w r 2 .

By definition of α r , if all the best paths have the largest window size, i.e. if B \ M = ∅, then α r = 0 for any r ∈ R u . This is because we already use the capacity available to the user by using all the best paths.

If there is any best path with a small window size, i.e. if B \ M = ∅, then α r is positive for all r in B\M and negative for all r in M. Hence, our algorithm increases windows faster on the paths that are presumably best but that have small windows. The increase will be slower on the paths with maximum windows. In this case, OLIA re-forwards traffic from fully used paths (i.e. paths in M) to paths that have free capacity available to the users (i.e. paths in B\M).

B. Linux Implementation of OLIA

We implemented OLIA in the MPTCP release supported on the Linux kernel 3.0.0 [11]. Similarly to LIA, our algorithm only applies to the increase part of the congestion avoidance phase. The fast retransmit and fast recovery algorithms, as well as the multiplicative decrease of the congestion avoidance phase, are the same as in TCP [START_REF] Allman | Tcp congestion control[END_REF]. We also use a similar slow start algorithm as in TCP, with the modification that we set the ssthresh (slow start threshold) to be 1 MSS if multiple paths are established. In the case of a single path flow, we use similar minimum ssthresh as in TCP (2 MSS). The purpose of this modification is to avoid transmitting unnecessary traffic over congested paths when multiple paths are available to a user. The minimum congestion windows size is 1 MSS as in TCP. Our implementation is now part of the Louvain MPTCP implementation [11].

One important part of our implementation is the measurement of r on a path r. This can be done easily by using information that is already available to a regular TCP user. Our algorithm for computing r is as follows:

• For each ACK on r: 2,r ← 2,r + (number of bits that are acknowledged by ACK) • For each loss on r: 1,r ← 2,r and 2r ← 0 where r = max{ 1,r , 2,r }. 1,r and 2,r are initially set to zero when the connection is established. To compute a smoothed estimate of rtt r , we use the algorithm, proposed in [START_REF] Jacobson | Congestion avoidance and control[END_REF] and implemented in the Linux kernel. To give more insight into how OLIA performs, we show the evolution of window sizes and α values for a two-path flow in Figure 6. The measurement results on our testbed are reported in Figures 7 and8.

We first consider a symmetric case, depicted in Figure 6(a). As both of the paths are equally good, a multipath user will benefit from using both of them. Figure 7(a) shows the evolution of w r and α r as a function of time. We observe that OLIA simultaneously uses both of the paths, similarly to LIA (Figure 7(b)), which is the desired behavior. There is no sign of flappiness as α 1 and α 2 react quickly to changes and adjust w 1 and w 2 accordingly.

We now study the asymmetric scenario of Figure 6(b). In this case, the second path is shared with 10 TCP flows and multipath users should use only the first path. This is what we observe in Figure 8(a). The window on the congested path is 1, most of the time (because of the first increase term). However, due to α, the window increases from time to time over the congested path whenever the path has the largest interloss distance r . This increase is brief as losses occur more frequently on this path. LIA, however, transmits significant traffic over the congested paths and lower traffic, compared to OLIA, over the good path as depicted in Figure 8(b).

V. PARETO-OPTIMALITY OF OLIA

In this section, we build a fluid model of OLIA by using differential inclusions. We show that this model provides a Pareto-optimal allocation (Theorem 3) that satisfies the three design goals of MPTCP [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF] (Corollary 2). Also, we prove that MPTCP with OLIA is fair with TCP: If all routes of a user have the same RTT, then OLIA maximizes the same fairness criteria as the regular TCP (Theorem 4). LIA transmits significant traffic over the congested path and less than OLIA over the good path.

A. Fluid Model of OLIA

We consider a network model similar to [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF]. The network is static and composed of a set L of links (or resources). We denote by R u the set of paths available to a user u, each path being a set of links. If the route r is available to user u, we write r ∈ R u . If a route r uses a resource , we write ∈ r. Similarly, we refer to all routes that cross as r . Let x r (t) ≥ 0 be the rate of traffic transmitted by the user u on a path r ∈ R u . We assume that the RTT of a route r is fixed in time and we denote it by rtt r . In the fluid model, the rate x r is an approximation of the window size divided by the RTT, i.e. x r = w r /rtt r .

Let p ( ∈r x r ) be the loss rate at link . p depends on the capacity of the link, C , and the total amount of traffic sent through the link, ∈r x r . We assume that p is an increasing function of ∈r x r . To simplify the notation, we omit the dependence on x and write only p . But note that if x varies with time, p will also vary. We assume that the loss probabilities of links are independent and small; hence, the loss probability on a route r is p r =1-∈r (1-p ) ≈ ∈r p . When p r is small, a user u receives acknowledgments on a route r ∈ R u at rate x r and increases the window w r as Eq. [START_REF] Han | Multipath tcp: a joint congestion control and routing scheme to exploit path diversity in the internet[END_REF]. Losses occur at rate p r x r on r, and the user decreases w r by half whenever it detects a loss. We consider a fluid approximation of OLIA in which we replace the stochastic variations of rates by their expectation. This leads to the differential equation:

dx r dt = x 2 r 1/rtt 2 r ( p∈Ru x p ) 2 - p r 2 + α r rtt 2 r , (7)
α r depends on the values p p and w p for all paths p ∈ R u of users u. It is defined by Eq. ( 6). To compute α r , we approximate r by its average: l r = 1/p r .

For a user u, the set of best paths B u and the set of paths with maximum window size M u depend non-continuously on the probability of loss on each route, as well as on the various window sizes of the routes of this user. This implies that the right-hand side of Eq. ( 7) is not a continuous function of x r . Therefore, this differential equation is not well defined and can have no solutions. A natural way to deal with a differential equation with a discontinuous right-hand size is to replace the differential equation ( 7) by a differential inclusion dx/dt ∈ F (x) where the discontinuous α r of ( 7) is replaced by the convex closure of the possible values of α r in a small neighborhood of x [START_REF] Gast | Mean field limit of non-smooth systems and differential inclusions[END_REF], [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF].

We show in Appendix C, that the differential inclusion corresponding to Eq. ( 7) is

dx r dt = x 2 r 1/rtt 2 r ( p∈Ru x p ) 2 - p r 2 + ᾱr rtt 2 r , (8)
where ᾱ = (ᾱ 1 . . . ᾱ|Ru| ) is such that Note that there are multiple ᾱ that correspond to definition [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF]. The differential inclusion might have multiple solutions, but this does not affect our analysis [START_REF] Khalili | Non pareto-optimality of mptcp: Performance issues and a possible solution[END_REF].

(ᾱ r • |R u |) ∈        [1 |Bu|=1 , 1] if r ∈ B u \ M u [-1, -1 |Mu|=1 ] if r ∈ M u \ B u [-1 |Bu|≥2 , 1 |Mu|≥2 ] if r ∈ M u ∩ B u {0} if r ∈ M u ∪ B u (9)

B. Pareto Optimality of OLIA

A fixed point of the congestion control algorithm (8) is a vector of rates x = (x 1 . . . x |R| ) such that there exists ᾱ satisfying [START_REF] Wischik | Design, implementation and evaluation of congestion control for multipath tcp[END_REF] and such that, Equation ( 8) is equal to zero for any route r. We say that x is a non-degenerate allocation of rates if each user transmits with a non-zero rate on at least one of its paths. In practice, due to re-establishment routines in traditional TCP, the allocation of rates will not be degenerate. Hence, in our analysis, we consider only the non-degenerate fixed points and analyze their properties.

Theorem 1. Any non-degenerate fixed point x of OLIA congestion control algorithm, given by Equation (8), has the following properties:

(i) Only the best paths will be used, i.e. paths r with maximum 2/p r /rtt r . (ii) The total rate obtained by a user u is equal to the rate that a regular TCP user would receive on the best path available to u:

r∈Ru x r = max r∈Ru 1 rtt r 2 p r .
Proof. The proof is given in Appendix D.

This theorem implies the following corollary:

Corollary 2. OLIA satisfies the three design goals suggested by the RFC [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF].

Proof. The proof is given in Appendix E.

The following theorem gives a global optimality property of OLIA. For a rate allocation x, we define the total congestion cost by C(x) = r xr 0 p (y)dy.

Theorem 3. Any non-degenerate fixed point x of our congestion control algorithm (8) is Pareto optimal, i.e.:

• It is impossible to increase the quantity r∈Ru x r /rtt 2 r for some users without decreasing it for others or increasing the congestion cost C(x).

Proof. The proof is given in Appendix F.

Remark 1. If the probability p is sharp around C , i.e. if p (y) ≈ 0 when y < C and p grows rapidly when y exceeds C , then the cost C is a binary function: it is very small if the capacity constraints r∈ x r ≤ C are respected and grows rapidly otherwise. In this case, Theorem 3 shows that if x is a fixed point of our algorithm, it is impossible to increase the quantity r∈Ru x r /rtt 2 r for some users without decreasing it for others while respecting the capacity constraints.

Remark 2. As pointed out by Kelly [START_REF] Frank | Mathematical modelling of the internet[END_REF], as C(x) is an increasing function of rates, single-path congestion control mechanisms are always Pareto optimal and the choice of an allocation of rates is only a matter of fairness. However, if we have multiple paths, it is likely that an algorithm will lead to a non-Pareto optimal allocation [START_REF] Frank | Mathematical modelling of the internet[END_REF]. Theorem 3 guarantees that this cannot happen with OLIA. As a consequence, our algorithm will not exhibit either problem P1 nor P2.

Remark 3. Although the utility function of each user r∈Ru x r /rtt 2 r could appear to be an ad-hoc utility function, it reflects the fact that like TCP, OLIA favors paths with low rtt. When all paths belonging to a user have the same RTT, this theorem implies that the rate allocation of OLIA is such that one user cannot increase its rate without decreasing the rate of some other users. Hence, OLIA can successfully avoid problems P1 and P2. When RTTs over paths available to a user are different, satisfying goals 1 and 2 of the RFC [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF] can lead to sending traffic on paths that are not the least congested but have a small round trip times. Therefore, using a TCPcompatible algorithm, it is not possible to avoid problems P1 and P2 in all possible settings. However, we can see from Theorem 1 that by using OLIA, only the best paths available to a user would be used. This indicates that OLIA provides an allocation as close as or closer to the optimal than any TCPcompatible algorithm. To completely avoid problems P1 and P2, it is necessary to depart from the compatibility with regular TCP by using congestion mechanisms that are less sensitive to round trip times, such as CUBIC [START_REF] Ha | Cubic: A new tcp-friendly high-speed tcp variant[END_REF] or STCP [START_REF] Kelly | Scalable tcp: Improving performance in highspeed wide area networks[END_REF].

C. TCP Compatibility

As we show in Appendix F, OLIA maximizes the utility function V * (x) given by Equation [START_REF] Raiciu | Practical congestion control for multipath transport protocols[END_REF]. We now show that our algorithm is fair with the regular TCP under the assumption (A): all the paths belonging to a user u have the same RTT rtt u . Under this assumption, V * (x) simplifies as follows:

V (x) = u∈U - 1 rtt 2 u r∈Ru x r - 1 2 l∈L r l xr 0 p (x)dx,
where x is the set of all the rates of the users.

Theorem 4. Under the assumption (A), the congestion control algorithm defined by Equation (8) converges to a maximum of the utility function V :

lim t→∞ V (x(t)) = max x≥0 V (x).
Proof. The proof is given in Appendix G.

This implies that OLIA maximizes the same utility function as the regular TCP of [START_REF] Kunniyur | End-to-end congestion control schemes: Utility functions, random losses and ecn marks[END_REF] where we replace the rate of a connection by the total rate that a user achieves on all its paths. If the probabilities of loss p are sharp around C , then our algorithm converges to an optimum of the following global maximization problem:

max u∈U - 1 rtt 2 u r∈Ru x r subject to r x r ≤ C x r ≥ 0.
This is analog to the TCP maximization problem.

VI. OLIA EVALUATION: MEASUREMENTS AND

SIMULATIONS

In this section, we study the performance of MPTCP with OLIA, through measurements and by simulations. We first perform measurements on our testbed to show that OLIA outperforms LIA in all the scenarios from Section III, as evidence that OLIA solves problems P1 and P2. Results from this section are in line with our theoretical analysis from Section V. We then study the performance of OLIA in a data center by using htsim simulator [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF].

A. Performance of OLIA in Scenarios A, B and C

In this section, we study the performance of MPTCP with OLIA, in the scenarios A,B and C described in Sections III-A to III-C. We show that in practice, OLIA is very close to the theoretical optimum with probing cost. These results are obtained through measurements over our testbed, by using our Linux implementation of OLIA.

1) Scenario A: We have shown in Section III-A that when the addition of an extra link does not help (like in Scenario A), using MPTCP with LIA can reduce the throughput of competing TCP users. Here, we show by measurements that MPTCP with OLIA significantly outperforms MPTCP with LIA and comes close to the theoretical optimum with probing cost. Figures 9 and 10 report measurements obtained on the testbed shown in Figure 2. Figure 9 depicts the normalized throughput of type1 and type2 users that use LIA or OLIA. The results show that OLIA performs close to an optimal multipath algorithm that transmits the minimum traffic over congested paths (theoretical optimum with probing cost). OLIA significantly outperforms LIA: by using OLIA, type2 Fig. 9. Scenario A -Normalized throughput of type1 and type2 users: we compare performance of LIA and OLIA. By using OLIA, type2 users achieve up to 2 times higher rates. OLIA performs close to the theoretical optimum with probing cost. users achieve rates up to two times higher than with LIA, with no reduction for type1 users.

Figure 10 depicts the measured loss probability p 2 on the shared access point. We observe that OLIA balances congestion much better than LIA. When we use OLIA, p 2 increases only by a factor of 1.3 in the worst case, whereas with LIA, p 2 increases by a factor of 5. p 1 is almost the same when using LIA or OLIA.

2) Scenario B: We now show the performance of OLIA in the scenario B described in Section III-B. As we have shown, OLIA is Pareto optimal. Hence, taking into account the minimum probing cost, we expect only 3% reduction in the Blue users' rates and in the aggregate throughput when we upgrade Red users to OLIA (see Figure 4(b)).

Table II presents the measurements for the scenario described in Section III-B using OLIA. We set C X =27, C T =36, C Z =100, all in Mbps. We have 15 Red and 15 Blue users. We set RTTs to 150 ms over all paths. Our results show that there is a 3.5% decrement in aggregate throughput when we update Red users to OLIA, which is much smaller than the 13% reduction we observed when we used LIA (see Table I). This 3.5% reduction in the aggregate throughput is due to the minimum traffic transmitted by users over congested paths and cannot be reduced as it is bounded below by 1/rtt packets/sec.

3) Scenario C: Finally, we study the performance of MPTCP with OLIA in scenario C described in Section III-C. Theorems 1 and 4 imply that by using our algorithm, multipath users do not send any traffic on their path crossing AP2. Next, we show by measurements that OLIA provides a fair allocation among users and performs close to an optimal algorithm with probing cost (Figure 5(b), dashed lines).

Figure 11 depicts the normalized throughput of singlepath and multipath users, as a function of N 1 /N 2 and for C 1 /C 2 =1, 2. We show the results for LIA and OLIA, as well as for an optimal algorithm with minimum probing cost. This figure shows that with OLIA multipath users transmit only one packet per RTT over AP2. Compared to LIA, type2 users receive up to 2 times higher throughput. Hence, OLIA is less aggressive than LIA towards regular TCP users.

Figure 12, shows the measured loss probability p 2 . The results show again that OLIA balances congestion in the network and reduces the loss probability in bottlenecks much better than LIA. In particular, we observe that by increasing N 1 from 0 to 3N 2 , p 2 increases by a factor of 2 using OLIA, we compare the performance of LIA and OLIA. We observe that by using OLIA, type2 users achieve up to 2 times higher rates. OLIA close to the theoretical optimum with probing cost. whereas the increase is in the order of 4 to 6 times when using LIA. p 1 is almost the same when using OLIA or LIA.

B. Performance of OLIA in Data Center and Dynamic Scenarios

The three preceding examples show that by providing a better congestion balance, MPTCP with OLIA outperforms MPTCP with LIA in Scenarios A, B, and C. In this section, we show that, by being non-flappy and as responsive as LIA, OLIA can fully use the multiple paths available in a data center. Our study is based on a series of scenarios in which MPTCP with LIA is studied in [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF]. Because of space constraints, we present the results for only two of the cases where LIA was shown to be very efficient. We observe that OLIA performs as well or better than LIA in these two scenarios. This indicates that it is not flappy and has a very good responsiveness. These results are obtained using htsim simulator used in [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF], provided by Raiciu et al. We implemented OLIA in the simulator and use the same scenarios as [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF].

1) Static FatTree Topology: We first study exactly the same scenario as in [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF], Section 4.2-Throughput: the network is a FatTree with 128 hosts, 80 eight-port switches, 100Mb/s links. Each host sends a long-lived flow to another host chosen at random. Figure 13(a) shows the aggregate throughput achieved by long-lived TCP and MPTCP (LIA and OLIA) flows. We show the results for different numbers of subflows used. Our results show that OLIA can successfully exploit the multiple paths that exist in the network and can use the available capacity. This is a sign that it is not flappy. Regular TCP shows a poor performance. Figure 13(b) shows the throughput of individual users ranked in order of achieved throughputs, for LIA and OLIA with 8 subflows per user and with TCP; LIA and OLIA provide similar fairness among users and are more fair than TCP. We observe that, in this scenario, LIA performs close to an optimal algorithm and exhibits a similar performance to OLIA. The reason is that the users have multiple equally good paths. Hence, LIA also successfully balances the congestions in the network, similarly to OLIA, Fig. 13. Performance of OLIA in a FatTree with many possible parallel paths between users. OLIA successfully explores the path diversity and uses the available capacity (a sign of non-flappiness). LIA performs similarly as, in this scenario, it can successfully balance the congestion. and performs optimally. During the experiments, we measured the loss probabilities of links available to users. The results confirm our reasoning: for this scenario, the obeserved loss probabilities are similar on all paths.

2) Dynamic Setting with Short Flows: We study the same scenario as the one described in Section 4.3.4-ShowFlows of [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF]. The scenario is a 4:1 oversubscribed FatTree where each host sends to one other host. One-third of the hosts send a continuous flow by using either TCP, MPTCP with LIA (8 subflows) or with OLIA (8 subflows). The remaining hosts send short flows of size 70Kbyte every 200ms on average (they generate these flows according to a Poisson process). They use regular TCP. This is a highly dynamic setting in which changes occur in the order of milliseconds. Table III shows the average completion time for short flows and the network core usage. Figure 14 shows the distribution of completion times of short flows. Our results show that although OLIA uses the available capacity as efficiently as LIA, the average completion time of short flows decreases by 10% using OLIA. Moreover, we observe in Figure 14 that OLIA decreases the completion time of both fast and slow short flows. For slow flows, the decrease is more than 25%. This shows that OLIA has a better responsiveness than LIA, is more fair to TCP users, and uses capacity quickly when it is available. With TCP, we have a lower average completion time for short flows, but very low network utilization.

VII. CONCLUSION

We have shown that MPTCP with LIA suffers from important performance issues. Moreover, it is possible to build an alternative to LIA, which performs close to an optimal algorithm with probing cost while being as responsive and non-flappy as LIA. Our theoretical results show that our proposed algorithm, OLIA, is Pareto-optimal and satisfies the three design goals of MPTCP [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF]. Moreover, we have shown through measurements and by simulation that OLIA is as responsive and non-flappy as LIA, and that it solves identified problems with LIA.

Multiple directions could be explored to go further. The first one comes from the fixed point analysis of Theorem 3. The stability and convergence of OLIA is another important question that will be studied in future work. Another one would be to vary the minimum probing traffic rate by an adjustment of the retransmit timer or by discarding bad paths from the set of available paths. Also, we plan to perform more detailed experiments to include other factors such as background traffic, flow durations, and receive window limitations.

APPENDIX

These appendix are divided in two parts. The first part (Appendix A and B) focuses on the proofs of the analytical results for LIA. It contains the fixed point analysis and the computation of the optimal allocation with probing cost for scenarios A, B and C. The second part (Appendix C to G) contains the proofs related to the Pareto optimality of OLIA.

A. Fixed point analysis for scenario A

In this appendix, we present a fixed point analysis of the scenarios A of Section III. For more clarity, we represent the scenario A in Figure 15. Recall that p 1 and p 2 are the loss probabilities at the link connected to the streaming server and at the shared AP. Also, we assume that the private APs are not the bottlenecks, hence, the loss probabilities at the private APs are negligible. We provide the analysis for the case where RTTs are the same over all connections and equal to rtt. x 1 is the rate of a type1 user over the path that crosses its private AP and x 2 is its rate over the shared AP. y is the rate of a type2 user.

1) MPTCP with LIA: The type1 users use MPTCP with LIA on two paths with loss probabilities p 1 and p 1 +p 2 . Thus, the fixed point formula (Eq.( 2)) of LIA gives:

x 1 + x 2 = C 1 = 1 rtt 2 p 1 and x 2 = 1 2 + p 2 /p 1 1 rtt 2 p 1
Users of type 2 are using the regular TCP over a link with probability of loss p 2 , they get a throughput

y = 1 rtt 2/p 2 .
This comes from the loss-throughput formula for TCP.

As the link connected to the streaming server and shared AP are the bottlenecks, the capacity constraints give:

N 1 (x 1 + x 2 ) = N 1 C 1 and N 1 x 2 + N 2 y = N 2 C 2 Let z := p 1 /p 2 . A direct computation shows that z is a root of z + z 2 1 + 2z 2 N 1 N 2 = C 2 C 1 (10)
As z 2 /(1 + 2Z 2 ) is an increasing function of z, this equation has a unique positive solution. Although this solution has no simple closed-form solution (it is the root of a third-order polynomial), it can be easily computed numerically. Hence, It provides a numerical scheme for computing x 1 , x 2 and y.

Type1 users always receives a rate of C 1 ; hence, their normalized throughput, (x 1 + x 2 )/C 1 , is always 1. The normalized throughput of type2 users, y/C 2 , is equal to p 1 /p 2 2/p 1 = zC 1 , where z is the unique positive solution of Equation [START_REF] Raiciu | Coupled congestion control for multipath transport protocols[END_REF]. In particular, this shows that y/C 2 only depends on the ratios C 1 /C 2 and N 1 /N 2 .

2) Optimal with probing cost: In scenario A, the throughput of type1 users is bounded by the streaming server. Using the shared AP can reduce the throughput of type2 users but cannot bring any gain to type1 users. Thus, an optimal algorithm should put as low traffic as possible on the second path. Assuming that the minimum traffic sent over a link is one packet of size MSS per round trip time, this leads to the following allocation of rate:

x 1 + x 2 = C 1 and x 2 = MSS rtt y = C 2 - N 1 N 2 MSS rtt .
This allocation is represented by the solid lines on Figure 1(b).

B. Fixed point analysis for scenario B

We present a theoretical analysis of the troughput acheived by blue and red users when multipath users use MPTCP with LIA and when users use optimal algorithm with probing cost.

We represent scenario B in Figure 16. We assume that the capacity of link Y and link Z are greater than C X + C T . This ensures that only links X and T are bottlenecks and we denote by p X and p T the probabilities of loss over them. Y , the theoretical analysis is the same as the one of scenario C, and we refer to Section III-C for more details. In the case where all paths are activated, i.e. when Red users upgrade to MPTCP users, the loss throughput formula (Eq.( 2)) for LIA shows that the throughput of the different connections are:

       y 1 = 1/rtt 2 + p X p T 2 p T y 2 = p X + p T p T y 1 ,        x 1 = 1/rtt 1 + p X /p T max 2 p X , 2 p T x 2 = 1/rtt 1 + p T /p X max 2 p X , 2 p T
Moreover, as ISP X and Y are bottlenecks, we have:

C X = N (x 1 + y 1 ) and C T = N (x 2 + y 1 + y 2 )
and y 1 + y 2 = 2/p T /rtt. Let's first assume that p X >p T . In that case, we have x 1 + x 2 = 2/p T . Let z=p X /p T . The capacity constraints impliy

C X = 1/rtt 1 + z 2 p T + 1/rtt 2 + z 2 p T C T = z/rtt 1 + z 2 p T + 1 rtt 2 p T .
This implies that

2z 2 + z(5 -2 C T C X ) + 2 -3 C T C X .
This equation has only one positive root. This root is greater than one only when C X /C T < 5/9. Thus, p X /p T is the root of this second order polynomial in this case. When C X /C T > 5/9, we must have p T > p X . A similar computation as above shows that in this case z is the unique positive root of the fifth order polynomial:

z 5 + z 4 + z 3 (3 - C T C X ) + z 2 (2 - C T C X ) + z(2 - C T C X ) -2 C T C X
These equation provide an efficient numerical method to evaluate the rate sent over the various links and therefore evaluate the performance of LIA. Note that he solutions of these equation only depend on C T /C X .

2) Optimal with probing cost: To simplify the notations, we present the analysis for N B = N R = N , which is the case in the scenarios studied in Section III-B. The analysis is similar when N B = N R . We distinguish two cases: first when red users use the regular TCP, then when red users uses an optimal multipath algorithm and activate the dashed connection.

Case 1. Red users are only connected to ISP Y : As ISP Y and Z are not bottlenecks, we have x 1 = C X /N . Moreover, the capacity constraint for ISP T implies that N (x 2 + y 2 ) = C T . Assuming that x 2 ≥ MSS/rtt, there are two scenarios:

• When C X ≤ C T -N MSS/rtt, a fair allocation will allocate the same rate, i.e. (C X +C T )/(2N ), to all users . • When C X > C T -N MSS/rtt, blue users will get more than red users. Thus, blue users should only transmit the minimal traffic x 2 = MSS/rtt over the second link. This shows that using an optimal algorithm with probing, each blue user will get a rate x 1 + x 2 and each red user will get a rate y 2 , where:

x 1 + x 2 = max C X N + MSS rtt , C T + C X 2N (11)
y 2 = min C T N - MSS rtt , C X + C T 2N . (12)
Case 2. Red users activate the dashed connection: As y 1 and y 2 share the same bottleneck, ISP T , the Red users should only transmit the minimum traffic over the dashed path, i.e. y 1 = MSS/rtt. If the Red users transmit over the dashed path they will penalize the other users without any benefit for themselves. This implies that x 1 = C X /N -MSS/rtt. Also, the capacity constraints for ISP T gives N (x 2 + y 1 + y 2 ) = C T . Therefore, we have: N (x 1 + x 2 + y 1 + y 2 ) = C T + C X -N MSS/rtt. As x 2 ≥ MSS/rtt, a fair allocation should allocate x 2 such that:

• if C X ≤ C T -N MSS/rtt, we should have x 1 + x 2 = y 1 + y 2 = (C T + C X -N MSS/rtt)/(2N ) • if C X ≥ C T -N MSS/
rtt, Blue users should transmit the minimal traffic x 2 = MSS/rtt over their second link. Thus, using this optimal algorithm with probing cost, each Blue user will get a rate x 1 + y 2 and each Red user will get a rate y 1 + y 2 where

x 1 +x 2 = max C X N , C T + C X 2N - MSS 2rtt (13)
y 1 +y 2 = min C T N - MSS rtt , C X +C T 2N - MSS 2rtt (14)
Compared to Equations (11) and [START_REF] Chen | A measurement-based study of multipath tcp performance over wireless networks[END_REF], the rates obtained by (13) and ( 14) are strictly smaller. The agregate throughput of all users decreases by N MSS/rtt.

3) Illustrations for two values of RTT: C. Construction of the differential inclusion 1) Brief introduction on differential inclusions: In this section, we briefly recall some definitions and results about differential inclusions and their relation to stochastic systems that have discontinuous drifts.

A set-valued function F : R d → S(R d ) is a function that associates to each vector x ∈ R d a set of vectors F (x) ⊂ R d . We say that a function

x : [0, T ] → R d is a solution of the differential inclusion dx/dt ∈ F (x) on the interval [0, T ] if there exists a function f : [0, T ] → R d such that ∀t ∈ [0, T ] : x(t) = x(0) + t 0 f (s)ds with f (t) ∈ F (t).
In particular, this implies that x is differentiable for almost every t and its derivative x satisfies x (t) ∈ F (x(t)).

Differential inclusion provide a natural way to represent differential equation with discontinuous right-hand side. Let f : R d → R d be a single-valued function. Following [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF], we define the set-valued function F corresponding to f :

F (x) = ε→0 convex closure {f (x) : x -w ≤ ε} .
This definition guarantees that the differential inclusion dx/dt ∈ F (x) has at least one solution. Moreover, it has been shown in [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF] that the solution of differential inclusions are a good approximation of the stochastic systems with discontinuous drift, such as Eq.( 7).

2) Computation of Equation (9): In this section, we show how to obtain the conditions on α r given by Eq.( 9) and how to compute the differential inclusion (8) from the differential equation [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF].

The only non-continuous part of the ODE ( 7) is due to α r . The set-valued function ᾱ corresponding to α is ᾱ(w) = ε→0 convex closure {α(x) : xw ≤ ε} .

The computation of ᾱ can be done by a careful inspection of Figure 18. For a route r, the set ᾱr corresponds to the convex closure of the values that α r can take when all the points (w r , p r /rtt r ) move in a small neighborhood. We detail the computation for a link r ∈ B u \M u . The other cases (r ∈ M u \B u and r ∈ M u ∩B u and r ∈ M u ∪B u ) are similar.

Let r be a route in B u \M u . Let first assume that there are two or more best paths (e.g. this is the case for the route r 4 r of a link (the inverse of its hypothetical rate for a single regular TCP flow) and its y-coordinate being its window size. The dotted circles around each node represent a small neighborhood of the points. In this example, the routes r 1 , r 2 , r 3 are routes with maximum window size: r 1 , r 2 , r 3 ∈ Mu. The routes r 1 , r 4 are best routes: r 1 , r 4 ∈ Bu. Finally, we have r 5 , r 6 ∈ Bu∪Mu.

of Figure 18), then if all points move in a small neighborhood (represented by the dotted circles around nodes on Figure 18), then there are some situations for which this route will be the only route in B u \M u = ∅ and α r will be 1/|R u | in that case. In other situations, the only best route can be route r 1 and in that case α r =0. Since this route cannot become a route with maximum window size, α r can take any value in [0, 1/|R u |].

On the other hand, if there is only one best paths and if r ∈ B u \M u , then r is the best path. (this would be the case for the route r 4 on Figure 18 if the node r 1 did not exist). In that case, r will always be in B u \M u and α r = 1/|R u |.

This shows the first line of Equation ( 9 The proofs of the other cases of Eq.( 9) as they are very similar.

D. Proof of Theorem 1

Let x be a non-degenerate fixed point of our algorithm. Recall that a fixed point of the congestion control algorithm ( 8) is a rate allocation vector x such that there exists ᾱr satisfying Eq.( 9) such that the quantity dx r /dt defined by Eq. ( 8) is null.

Proof of (i). Let x be a non-degenerate fixed point of OLIA. For any path p ∈ R u , the equation dx p /dt contains two terms, denoted term A and term B in the next equation:

0 = dx p dt = x 2 p 1/rtt 2 p ( s∈Ru x s ) 2 - p p 2 term A + ᾱp term B . ( 15
)
Assume that there exists a non-best path r ∈ B u such that x r > 0. We show that this leads to a contradiction.

Equation [START_REF] Ford | Tcp extensions for multipath operation with multiple addresses[END_REF] shows that the term A is positive for r and hence is strictly positive for any best paths (by definition of best path). If B u ∩ M u = ∅, there exists a best path p with maximum window size. Thus, we have x p = 0, which implies that dx p /dt > 0 as ᾱp is non-negative. If B u ∩ M u = ∅, then there exists p ∈ B u such that ᾱp > 0, which implies that ᾱp > 0 and thus dx p /dt > 0. In both cases, we have dx p /dt > 0 which contradicts that dx p /dt = 0.

This shows that for any non-best path r ∈ B u , we must have x r = 0.

Proof of (ii). Because of (i), for all routes r ∈ B u , we have x r = 0. This means that for all routes r ∈ B u , we have r ∈ M u and ᾱr = 0. The best paths are the set of paths p with minimum p p rtt 2 p . Therefore, the term A of Eq. ( 15) is of the same sign for all best paths. This implies that the term ᾱp is of the same sign for all p. As p∈u ᾱp = p∈Bu ᾱp = 0, this implies that ᾱp = 0 for all paths p ∈ R u .

Therefore, the fixed point x satisfies

x r = 0 or

p∈Ru x p = 1 rtt r 2 p r . ( 16
)
By assumption, x is non-degenerate, which means that there exists a route r ∈ R u such that x r = 0. Because of (i), r is a necessarily a best path. Hence, we have This concludes the proof of (ii).

E. Proof of Corollary 2

Point (ii) of Theorem 1 implies that OLIA satisfies goal 1: the total rate that OLIA gets ( r∈Ru x r ) is the same as the rate that a regular TCP would get on its best link (max r∈Ru 2/p r /rtt r ).

Moreover, as OLIA uses only its best paths, it does not transmit more than a regular TCP does on any of its paths and satisfies goal 2. Finally, as OLIA uses only its best path, it perfectly balances congestion and satisfies goal 3. where τ u is defined by: τ u = ( r∈Ru x * r )/( r∈Ru x * r /rtt 2 r ). The function V * is a non-positive function. Moreover, using that p (x) is increasing, it goes to -∞ when x → ∞. Therefore, it has a maximum, attained for a finite x. By concavity of V * , a necessary and sufficient condition for a point x to be a maximizer of U is that for every route r: ∂V * ∂x r (x) ≤ 0 and ∂V * ∂x r (x) = 0 or x r = 0.

By definition of V * , this implies that for every r:

1 τ 2 u 1/rtt 2 r ( r∈Ru x r /rtt 2 r ) 2 - p r 2 ≤ 0, (18)
By definition of τ u and as x * satisfies point (i) of Theorem 1, Equation ( 18) holds. Moreover, ( 16) comes directly from [START_REF] Zhang | A transport layer approach for improving end-to-end performance and robustness using redundant paths[END_REF]. This shows that x * is a maximum of the function V * . Since V * (x) is an increasing function of r∈Ru x r /rtt 2 r and a decreasing function of the congestion cost C(x), it is impossible to increasing r∈Ru x r /rtt 2 r for some users without decreasing it for others or increasing the cost.

  Normalized throughput of users (x 1 +x 2 )/C 1 and y/C 2 . Loss prob. p 2 at the shared AP.

Fig. 1 .

 1 Fig. 1. Scenario A: type1 users are all downloading through the same streaming server and have access to both a private high speed access point and a shared access point. Type2 users have access only to the shared access point. The performance of MPTCP with LIA obtained by measurement (points) or numerical analysis (lines) is shown on figures (b) and (c). We observe that it is not Pareto-Optimal, penalizes type2 users, and its performance is far from the theoretical optimum with probing cost. It also fails to balance the congestion.

Fig. 2 .

 2 Fig. 2. Testbed implementation of scenario A: router R 1 emulates the bottleneck at the server side and router R 2 the shared AP bottleneck. Iperf is used to emulate multiple connections. The red PCs use MPTCP and the blue PCs use regular TCP.

2 Fig. 3 .

 23 Fig. 3. Scenario B. Thick lines represent peering agreements. Blue users are downloading from servers in ISP Z and Red users from servers in ISP T . Blue users use multi-homing and have access to ISPs X and Y . Initially, Red users have access only to ISP Y but upgrade to MPTCP and connect to both X and Y (by activating the dashed connection).

  users when Red use MPTCP Red users when Red use MPTCP Blue users Red users (a) Performance of LIA.

Fig. 4 .

 4 Fig. 4. Analytical results for Scenario B with 15 Blue and 15 Red users. We show the normalized throughput (15(x 1 + x 2 )/C T and 15(y 1 + y 2 )/C T ) as a function of C X /C T . Dashed curves: normalized throughput when Red users connect only to ISP Y . Solid curves: the case when Red users upgrade to multipath. For all values of C X /C T , the throughput of all users decreases when Red users upgrade to MPTCP.

Figure 4

 4 Scenario C: N 1 multipath users and N 2 single-path users are connected to two APs with capacities N 1 C 1 and N 2 -path users LIA: multipath users Optimum w. prob.: multipath users Optimum w. prob.: single-path users (b) Analytical results: normalized throughput of all users using LIA (solid) or optimum with probing cost (dashed) for N 1 = N 2 . Loss prob. p 2 at AP2: LIA fails to balance the congestion.

Fig. 5 .

 5 Fig. 5. Scenario C: MPTCP with LIA excessively penalizes TCP users (when C 1 /C 2 ≥1, for any fairness criterion, MPTCP users should not impact TCP users). We show the normalized throughputs ((x 1 +x 2 )/C 1 and y/C 2 ) received by the users, as well as p 2 . The performance of LIA is far from the theoretical optimum with probing cost.

  of a theoretical optimum with probing cost (see Appendix B). The results are presented for RTT=150 ms, C Y = C Z = 100 Mbps, and C T = 36 Mbps. We consider 15 Blue users and 15 Red users in the network. We depict the normalized throughput (15(x 1 + x 2 )/C T and 15(y 1 + y 2 )/C T ) as a function of C X /C T . The results show that upgrading Red users to MPTCP with LIA decreases the performance for everyone. As an example, when C X /C T ≈ 0.75, by upgrading the Red users we reduce the throughput of the Blue users by up to 21%.

C

  Fig. 6. A multipath user sharing two bottlenecks of the same capacity C with single-path users.

2 (

 2 a) MPTCP -OLIA: window size and αr as a function of time.

  MPTCP -LIA: window size.

Fig. 7 .

 7 Fig. 7. Evolution of w and α values for a two-path flow. Each path is shared with 5 regular TCP users. OLIA uses both of the paths, similarly to LIA, and there is no sign of flappiness.

2 (

 2 a) MPTCP -OLIA: window size and αr as a function of time.

  MPTCP -LIA: window size.

Fig. 8 .

 8 Fig.8. Evolution of w and α for a two paths flow. The first path is shared with 5 TCP flows and the second with 10. OLIA uses only the good path. LIA transmits significant traffic over the congested path and less than OLIA over the good path.

  with r∈Ru ᾱr = 0 and r∈Bu ᾱr = 1/|R u | if B u ∩ M u = ∅. The notation 1 |Bu|=1 means that this term is equal to 1 if |B u | = 1 and 0 otherwise. For example, when there is only one best path (i.e. |B| = 1), ᾱr = 1/|R u | for r ∈ B u \M u . If there are two or more best paths (i.e. |B| = 1), then ᾱr ∈ [0, 1/|R u |] for r ∈ B u \ M u .

Fig. 10 .

 10 Fig.10. Scenario A -Loss probability p 2 at shared AP: we observe that OLIA significantly reduces the congestion level at this bottleneck and improves the congestion balancing.

Fig. 11 .

 11 Fig. 11. Scenario C -Normalized throughput of single-path and multipath users: we compare the performance of LIA and OLIA. We observe that by using OLIA, type2 users achieve up to 2 times higher rates. OLIA close to the theoretical optimum with probing cost.

Fig. 12 .

 12 Fig.[START_REF] Chen | A measurement-based study of multipath tcp performance over wireless networks[END_REF]. Scenario C -Loss probability p 2 at shared AP: we observe that OLIA significantly reduces the congestion level at this bottleneck (4 to 6 times lower compared tp LIA).

Fig. 14 .

 14 Fig. 14. Completion time of short flows competing with long-lived TCP, MPTCP with LIA or OLIA flows in a highly dynamic setting. OLIA reacts faster to the changes in the network and is fairer toward short flows.

Fig. 15 .

 15 Fig. 15. The scenario A of Section III

2 Fig. 16 .

 216 Fig. 16. The scenario B of Section III

Figure 17

 17 depicts the throughput reduction when upgrading Red users to multipath for an optimal algorithm with probing cost. The values are shown for C X = 27 Mbps, C T = 36 Mbps and N B = N R = 15 users. The values of the MSS is 1500 Bytes. As the minimal probing traffic sent over a link is MSS/rtt, a lower value of the RTT means a higher reduction of throughput.

Fig. 17 .

 17 Fig. 17. Illustration of the optimal allocation with probing for scenario B for two values of the RTT. We set C T = 36 Mbps and N B =N R =15 users.

Fig. 18 .

 18 Fig.[START_REF] Cetinkaya | Opportunistic traffic scheduling over multiple network paths[END_REF]. State of the routes of a user that has 6 routes at a given time. Each route is represented by a point •, its x-coordinate being the ratio prrtt 2 r of a link (the inverse of its hypothetical rate for a single regular TCP flow) and its y-coordinate being its window size. The dotted circles around each node represent a small neighborhood of the points. In this example, the routes r 1 , r 2 , r 3 are routes with maximum window size: r 1 , r 2 , r 3 ∈ Mu. The routes r 1 , r 4 are best routes: r 1 , r 4 ∈ Bu. Finally, we have r 5 , r 6 ∈ Bu∪Mu.

  ): for r ∈ B u \M u : ᾱr ∈ [0, 1/|R u |] if |B u | = 1 and ᾱr = 1/|R u | otherwise.

F

  . Proof of Pareto-optimality (Theorem 3) Let x * be a fixed point of the algorithm and define the utility function V * (x) as u∈users

1 τ 2 u 1 /rtt 2 r( r∈Ru x r /rtt 2 r ) 2 - p r 2 =

 121222 0 or x r = 0.

TABLE I MEASUREMENT

 I RESULTS FOR SCENARIO B.

	Red users	Rate/user Blue users Red users	Aggregate
	Single-path	2.5	1.5	59.8
	Multipath	2.0	1.4	52.0

The number of Red and Blue users is 15 and all values are recorded in Mbps. By upgrading Red users to MPTCP, the throughput drops for all users and the aggregate throughput falls by 13%.

  Using OLIA, we observe a small drop of 3.5% in the aggregate throughput, which is due to the overhead of minimum traffic (1/rtt) over the congested path. Compared to LIA (see TableI), we see significant improvement.

		TABLE II
	MEASUREMENT RESULTS FOR SCENARIO B
	Red users	Rate/user Blue users Red users	Aggregate
	Single-path	2.2	1.8	59.3
	Multipath	2.2	1.7	57.8

TABLE III PERFORMANCE

 III OF OLIA IN A HIGHLY DYNAMIC SETTING.

	algorithm	Short flow finish time (mean/stdev)	Network core utilization
	MPTCP -LIA	98 ± 57 ms	63.2%
	MPTCP -OLIA	90 ± 42 ms	63%
	Regular TCP	73 ± 57 ms	39.3%
	OLIA uses the available capacity as efficient as LIA, but decreases the
	average completion time of short flows by 10%.

G. Proof of TCP-compatibility (Theorem 4) Theorem 4 assumes that all the paths belonging to user u have the same round trip time rtt u . Recall that V is:

By construction of F , there exists at least one solution of the differential inclusion given by Eq.( 8) (see C1). Let x be one of these solutions. There exists a function ᾱ(t) = (ᾱ 1 (t) . . . ᾱ|R| (t)) satisfying Eq.( 9) for all t and such that dx r /dt satisfies Eq.( 8):

When running the algorithm, the derivative of V (x(t)) w.r.t. time satisfies dV /dt = u,r (∂V /∂x r )(dx r /dt). Thus:

By definition of ᾱ, we have r∈Ru ᾱr = 0. Moreover, when all rtt are equal, the best paths are the paths with minimal probability loss and ᾱr ≤ 0 for such paths. Thus: These two properties together show that the term ( 21) is non-negative. Since ( 20) is also non-negative, this shows that dV (x(t))/dt ≥ 0 for all t. Thus, the function V is non decreasing. Since V is non-positive, this shows that lim t→∞ dV (x(t))/dt = 0. Let x * be a limit point of x(t), which exists since x(t) remains in a compact set. Since lim t→∞ dV (x(t))/dt = 0, this implies that ( 20) and ( 21) are equal to 0 for this x * . In particular, this implies that for all r ∈ R u :

p r 2 or (x r = 0 and ᾱr = 0).

This shows that x * is a fixed point of the algorithm. When the RTT of all paths of a user u are equal to rtt u , the quantity τ u defined in the proof of Theorem 3 is equal to rtt 2 u . Thus, the function V * of the proof of Theorem is equal to V . In particular, V * does not depend on x * . Since x * is a fixed point of the algorithm, x * is a maximizer of V .