PaperlayerView exact revision on arXiv

Source-linked AI summary

Multipath TCP: Analysis, Design and Implementation

Qiuyu Peng, Anwar Walid, Jaehyun Hwang, Steven H. Low

arXiv:1308.3119v3cs.NI

TL;DR

MP-TCP seeks to use multiple network paths transparently, but existing designs lack a general structural account of equilibrium and competing performance properties. This paper develops a fluid model and design criteria, showing an inevitable tradeoff among TCP-friendliness, responsiveness, and window oscillation, then proposes Balia as a balanced design.

  • Problem

    Existing MP-TCP proposals lack a general structural framework for analyzing equilibrium and systematically trading off TCP-friendliness, responsiveness, and window oscillation.

  • Method

    The paper develops a fluid model for a broad class of MP-TCP algorithms and derives parameter-based criteria for equilibrium and performance properties.

  • Results

    The criteria guarantee equilibrium existence, uniqueness, and asymptotic stability, while analysis shows that greater responsiveness necessarily reduces TCP-friendliness.

  • Takeaways & Limitations

    Balia generalizes existing algorithms and provides a practical balance among TCP-friendliness, responsiveness, and window oscillation.

Abstract

from arXiv · show

Multi-path TCP (MP-TCP) has the potential to greatly improve application performance by using multiple paths transparently. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP-friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algorithms and motivate a new design that generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscillation. We have implemented our algorithm in the Linux kernel. We use our prototype to compare the new algorithm with existing MP-TCP algorithms.

I. INTRODUCTION … B. Existing MP-TCP algorithms

The paper develops a structural and fluid-model framework for MP-TCP, covering existing algorithms and examining equilibrium, friendliness, responsiveness, and window oscillation. It uses this framework to motivate systematic algorithm design and model literature proposals.

  • I. INTRODUCTION: MP-TCP can transparently use multiple available paths to improve application performance, unlike traditional single-path TCP.Examples include smartphones with cellular and WiFi access and data-center servers connected to multiple routers.
  • I. INTRODUCTION: Existing algorithms trade off fairness, responsiveness, and stability: per-path NewReno can be unfriendly, while Coupled is fair but responds slowly.OLIA is described as a Coupled variant that remains friendly while improving responsiveness.
  • I. INTRODUCTION: The paper seeks structural criteria for trading TCP-friendliness, responsiveness, and window oscillation, including the effect of an underlying utility function.Steady throughput matters for applications that are harmed by window oscillation.
  • I. INTRODUCTION: The proposed fluid model covers a broad class of MP-TCP algorithms and establishes conditions for utility representation, equilibrium existence and uniqueness, and asymptotic stability.The Max algorithm is given as an example without an associated utility function.
  • A. Fluid model: The model represents each route with sending rate xr(t), congestion window wr(t), and route loss or price measure qr(t), while links maintain capacities and congestion prices.Sending rate is defined by xr(t) := wr(t)/τr, and route aggregate price is derived from link prices.
  • A. Fluid model: The distributed MP-TCP fluid dynamics adapt sending rates and congestion prices in a closed loop, with algorithm behavior specified by source gains Ks(xs) and functions Φs(xs).The model is motivated by TCP NewReno’s additive-increase, multiplicative-decrease behavior.
  • B. Existing MP-TCP algorithms: Existing loss-based MP-TCP algorithms increase each route’s window upon ACKs and decrease it upon packet losses, with increments and decrements depending on the source’s route-window vector.The paper maps these window updates to fluid-model parameters kr(xs) and φr(xs).

Single-path TCP (TCP-NewReno): · III. STRUCTURAL PROPERTIES

Single-path TCP is modeled as the one-route special case of MP-TCP, while existing multipath algorithms are described through route-level window adjustments and reduce to TCP-NewReno on one route. The structural analysis characterizes designs with finite equilibria and identifies criteria governing equilibrium behavior, TCP-friendliness, responsiveness, and window oscillation, including an inevitable tradeoff among the latter properties.

  • Single-path TCP (TCP-NewReno):: Single-path TCP is the |s| = 1 special case of MP-TCP, so each source has one route and a scalar window.TCP-NewReno increases its window by 1/w_r per ACK and halves it after each loss.
  • Single-path TCP (TCP-NewReno):: EWTCP applies TCP-NewReno-like control independently on each route, using a/w_r increase per ACK and halving after each loss.Here a > 0 is a constant in the corresponding fluid-model expression.
  • Single-path TCP (TCP-NewReno):: Coupled, Semi-coupled, and Max MPTCP adjust windows across multiple routes through coordinated ACK rules while halving each route’s window after loss.All existing MP-TCP algorithms summarized here degenerate to TCP-NewReno when each source has only one route.
  • III. STRUCTURAL PROPERTIES: The structural analysis assumes k_r(x_s) > 0 and restricts attention to finite equilibria, which require q_r > 0 for every route.At equilibrium, route and link conditions are given by φ_r(x_s) ≤ q_r with equality for positive x_r, and y_l ≤ c_l with equality for positive p_l.
  • III. STRUCTURAL PROPERTIES: An equilibrium depends on Φ_s but not K_s, whereas K_s affects dynamic properties such as stability and responsiveness.This separates equilibrium determination from the design parameters governing dynamics.
  • III. STRUCTURAL PROPERTIES: The paper characterizes MP-TCP designs that guarantee existence, uniqueness, and stability of system equilibrium.The designs are represented as (K, Φ) := (K_s, Φ_s, s ∈ S).
  • III. STRUCTURAL PROPERTIES: The analysis identifies criteria for TCP-friendliness, responsiveness, and window oscillation and proves an inevitable tradeoff among these properties.It then examines the implications of these structural properties for existing algorithms in the next section.

A. Summary · B. Utility maximization · C. Existence, uniqueness and stability of equilibrium

The paper characterizes when MP-TCP algorithms admit utility-maximization interpretations and when their equilibria exist uniquely and converge globally. These conditions also establish formal comparisons of TCP-friendliness and responsiveness, including an unavoidable tradeoff between them.

  • A. Summary: C0 guarantees utility functions whose maximization characterizes MP-TCP equilibria, but unlike single-path TCP, it is not automatic for multipath designs.C0 always holds when every source has one path, but not generally when sources use multiple paths.
  • A. Summary: C1–C3 guarantee existence, uniqueness, and global asymptotic stability of equilibrium, with C1 requiring aggregate link traffic to decrease toward zero as congestion price rises.C2 also implies opposing steady-state perturbations, (δx_s)^Tδq_s < 0.
  • A. Summary: Under C1–C4, an MP-TCP algorithm is more TCP-friendly when its route sending rate φ_r(x_s) is smaller.C4 is satisfied by all algorithms considered and supports this formal comparison.
  • A. Summary: Under C1–C3, more negative-definite Jacobians make MP-TCP more responsive, while C5 implies that greater responsiveness necessarily reduces TCP-friendliness.C5 states that route sending rates grow unbounded when congestion price is zero.
  • B. Utility maximization: Theorem 3.1 establishes a twice continuously differentiable concave utility function for an MP-TCP equilibrium if and only if C0 holds.Thus utility maximization depends on the design of Φ_s rather than following automatically from multipath operation.
  • B. Utility maximization: Only EWTCP and Coupled satisfy C0 among the modeled multipath algorithms; EWTCP has a unique stable equilibrium, whereas Coupled may have multiple equilibria.The Coupled utility function is not strictly concave, while the other MP-TCP algorithms have asymmetric Jacobians and fail C0.
  • C. Existence, uniqueness and stability of equilibrium: Theorem 3.2 shows that C1–C3 yield a unique equilibrium, and Theorem 3.3 shows global asymptotic stability when k_r(x_s) ≡ k_r(x_r).This gain condition holds for all existing algorithms presented in the paper, and trajectories converge from any initial point.
  • C. Existence, uniqueness and stability of equilibrium: When k_r depends on the full vector x_s, the sufficient global-stability condition fails, but the equilibrium can still be locally asymptotically stable.The paper notes this for its proposed algorithm and gives an alternative local-stability proof.

D. TCP friendliness · E. Responsiveness around equilibrium · F. Window oscillation

The paper characterizes TCP friendliness, local responsiveness, and window oscillation through design functions and establishes tradeoffs among these properties. In particular, greater responsiveness is associated with reduced friendliness and more severe oscillations under stated conditions.

  • D. TCP friendliness: An MP-TCP flow is TCP friendly when it does not dominate available bandwidth while sharing a network with a single-path TCP flow.Friendliness is evaluated using a test network in which both flows share a bottleneck link.
  • D. TCP friendliness: Under C1–C4, algorithm ˆ M is friendlier than ˜ M when ˆΦs(xs) ≤ ˜Φs(xs) for every route s.The comparison concerns two MP-TCP algorithms evaluated under the same stated conditions.
  • E. Responsiveness around equilibrium: Under C1–C3, the linearized system around a unique equilibrium is stable, and responsiveness is determined by the real parts of the Jacobian eigenvalues.More negative real parts imply faster local convergence to equilibrium.
  • E. Responsiveness around equilibrium: An MP-TCP algorithm with larger Ks(x∗) is more responsive because it has a smaller, more negative upper bound on the Jacobian eigenvalue real parts.The comparison defines greater responsiveness through λ(ˆJ∗) ≤ λ(˜J∗).
  • E. Responsiveness around equilibrium: With the same gain K and under C1–C3 and C5, a more responsive MP-TCP design is inevitably less friendly.This follows from the paper’s friendliness and responsiveness comparisons.
  • F. Window oscillation: Loss-based AIMD inherently produces window oscillations, and larger Ks(xs) generally makes those oscillations more severe.For TCP-NewReno, each packet loss halves the window, giving Ds(xs) = 1/2.
  • F. Window oscillation: With constant route delays, steady-state throughput fluctuation Ds(xs) is determined by kr(xs), while larger Ks(xs) tends to increase Ds(xs).The gain functions do not affect equilibrium rates xs under the stated first-order analysis.

IV. IMPLICATIONS AND A NEW ALGORITHM … B. A generalized algorithm

The paper evaluates existing MP-TCP algorithms through equilibrium properties, friendliness, responsiveness, and window oscillation, then introduces a generalized algorithmic design space. Its parameterization captures tradeoffs among these goals and includes several existing algorithms as special cases.

  • A. Implications on existing algorithms: Only EWTCP and Coupled satisfy C0, while Semicoupled and Max satisfy C1–C3 when they enable no more than 8 routes.Utility-maximization analysis applies to EWTCP and Coupled but not to Semicoupled and Max.
  • φewtcp: Existing MP-TCP algorithms have friendliness throughputs ordered as stated for the Fig. 1 test network, consistent with Linux-based experiments.The ordering follows from equal-RTT conditions and the algorithms’ shared C4 property.
  • φewtcp: Existing algorithms have the same gain function, so their responsiveness is predicted and experimentally confirmed to have the same order.The cited passages specify kr(xs) = 0.5x2 and invoke Theorem 3.5 for the ordering.
  • φewtcp: MP-TCP always tends to reduce window oscillation relative to TCP NewReno because existing algorithms satisfy kr(xs) = 0.5x2r ≤ 0.5xr∥xs∥1.The reduction is strict when |s| > 1 and xr > 0 for at least two routes.
  • B. A generalized algorithm: The generalized class includes Max, Coupled, and Semicoupled as special cases under equal RTTs across routes.Their parameter choices are Max (β = 1, η = 0, n = ∞), Coupled (β = 0, η = 0), and Semicoupled (β = 1, η = 0, n = 1).
  • B. A generalized algorithm: Theorem 4.1 characterizes a subclass with a unique and locally stable equilibrium: C1 holds for β ≥0, while C2–C3 hold for 0 < β ≤1, |s| ≤8, and equal route RTTs.The C2–C3 result assumes H has full row rank; the paper notes that enabling no more than 3 paths is typical in practice.
  • B. A generalized algorithm: The design space uses β ∈(0, 1], η ≥0, and n ∈N+, with β and n trading friendliness against responsiveness and η trading responsiveness against window oscillation.The paper describes these as inevitable tradeoffs in MP-TCP design.
  • B. A generalized algorithm: Experiments found that Max overtakes competing single-path TCP flows too much, motivating smaller β and larger η; Balia corresponds to (β, η, n) = (0.2, 0.5, ∞).Reducing β improves friendliness, while increasing η compensates responsiveness at the expense of window-oscillation performance.

V. EXPERIMENT … VI. CONCLUSION

Experiments validate the analysis by comparing MP-TCP algorithms on TCP friendliness, responsiveness, and window oscillation. The proposed Balia algorithm achieves a favorable balance across these properties and is implemented and evaluated in Linux.

  • V. EXPERIMENT: Experiments compare Balia with prior MP-TCP algorithms on TCP friendliness, responsiveness, and window oscillation.The evaluation uses a reference Linux implementation and includes Max, OLIA, EWTCP, Semicoupled, Coupled, and Balia.
  • A. TCP friendliness: The Coupled algorithm is friendliest under equal RTTs, while Balia is closer to Coupled than the other algorithms.The equal-RTT experiments use T1 = T2 = 5ms, c1 = c2 = 60Mbps, and N1 = N2 = 30.
  • A. TCP friendliness: Under heterogeneous WiFi/3G RTTs, Coupled remains friendliest and Balia remains closer than the other algorithms when single-path TCP flows exist.The experiment sets T1 = 10ms, c1 = 8Mbps for WiFi and T2 = 100ms, c2 = 2Mbps for 3G.
  • B. Responsiveness: EWTCP is most responsive, while Balia is as responsive as Max and significantly friendlier than EWTCP.Coupled and OLIA take excessively long to recover the congestion window on the second path.
  • B. Responsiveness: Coupled and OLIA recover slowly because a high-throughput route can suppress growth on another underutilized route.For Coupled, the per-ACK increase is roughly wr/(P_k∈s w_k)^2 when RTTs are similar; after competing flows leave, a small w2 and large w1 make recovery slow.
  • C. Window oscillation: A single-link experiment compares window sizes of two MP-TCP subpaths and their aggregate with a TCP-Reno flow, using Balia as the representative MP-TCP algorithm.The reported results are shown in Fig. 3, and other MP-TCP algorithms are described as having similar behavior.
  • VI. CONCLUSION: The paper presents equilibrium guarantees, characterizes the tradeoff among friendliness, responsiveness, and window oscillation, and proposes and evaluates Balia as a balanced Linux implementation.Balia generalizes existing algorithms and is implemented in the Linux kernel for performance evaluation.

APPENDIX A PROOF OF THEOREM 3.1 (UTILITY MAXIMIZATION) … B. Proof of part 2

The appendices establish utility-maximization conditions and prove equilibrium properties for the MP-TCP model. They show existence in part 1 and uniqueness in part 2 under the stated assumptions.

  • APPENDIX A PROOF OF THEOREM 3.1 (UTILITY MAXIMIZATION): The KKT conditions require y_l < c_l ⇒ p_l = 0 and p_l > 0 ⇒ y_l = c_l at optimality.These complementary-slackness conditions connect link capacity and price variables in the utility-maximization proof.
  • APPENDIX A PROOF OF THEOREM 3.1 (UTILITY MAXIMIZATION): A continuously differentiable utility solution exists exactly when the Jacobian of Φ_s(x_s) is symmetric.This condition is obtained by comparing the MP-TCP characterization with the KKT conditions.
  • A. Proof of part 1: For fixed p_−l, g_l(p) is nondecreasing in p_l and converges to c_l as p_l approaches infinity.The proof uses the nonincreasing behavior of y_l^s(p) and its limit as p_l grows.
  • A. Proof of part 1: The function h_l(p) is quasi-concave in p_l, whether g_l(0,p_−l) is nonnegative or negative.When g_l(0,p_−l) is negative, continuity yields a p_l* where g_l(p_l*,p_−l)=0, after which h_l is nondecreasing.
  • A. Proof of part 1: Nash’s theorem yields at least one p⋆, and therefore at least one solution (x,p) satisfying equations (6) and (7).The argument applies when h_l is quasi-concave for every l and p lies in a bounded set.
  • B. Proof of part 2: Under C3, every route has strictly positive equilibrium state x_r* > 0.This positivity is established in Lemma B.2 and is then used in the uniqueness proof.
  • B. Proof of part 2: Lemma B.1 and assumption C2 produce a strict inequality for two distinct equilibrium points, while the equilibrium conditions make its left-hand side nonnegative.The contradiction follows from p^T(c−y)=0 and p̂^T(c−ŷ)=0 together with nonnegative prices, proving uniqueness.
  • B. Proof of part 2: The contradiction establishes that the equilibrium is unique.The final step uses the nonnegativity of p and p̂ to contradict the strict inequality derived for distinct equilibria.

APPENDIX C PROOF OF THEOREM 3.3 (STABILITY)

The proof establishes global asymptotic stability of the unique equilibrium by constructing a radially unbounded Lyapunov function and applying LaSalle’s invariance principle. It shows that the only trajectory with zero Lyapunov derivative is the equilibrium itself.

  • Lyapunov construction: A candidate Lyapunov function is constructed for deviations δx := x−x⋆ and δp := p−p⋆ around the unique equilibrium.The proof explicitly invokes LaSalle’s invariance principle to establish global asymptotic stability.
  • Lyapunov construction: The function is positive away from equilibrium, zero at equilibrium, and radially unbounded as the state norm tends to infinity.These properties ensure it qualifies as a global stability candidate.
  • Derivative analysis: The derivative satisfies ˙V (x, p) < −δxT HT δp + δpT Hδx = 0 when δx ≠ 0, while ˙V (x, p) = 0 when δx = 0.Thus ˙V (x, p) ≤ 0 and V is a Lyapunov function.
  • Invariant set: LaSalle’s invariance principle reduces global asymptotic stability to showing that the only trajectory remaining in Z, where ˙V ≡ 0, is the equilibrium trajectory.The set is defined as Z := { (x(t), p(t)) | ˙V (x(t), p(t)) = 0 for all t ≥0 }.
  • Invariant set: Any trajectory in Z has x(t) = x∗, then q(t) = Φ(x(t)) and HT p(t) = Φ(x∗); full row rank of H forces p(t) = p∗.Therefore (x, p) ≡ (x∗, p∗) is the only trajectory in Z, completing the stability proof.

APPENDIX D PROOF OF THEOREM 3.4 (FRIENDLINESS) · APPENDIX E PROOF OF THEOREM 3.5 (RESPONSIVENESS) · A. Proof of part 1

The friendliness proof shows aggregate MP-TCP throughput increases with parameter µ, while the stability proof establishes that all linearized-system eigenvalues have nonpositive real parts under condition C2.

  • APPENDIX D PROOF OF THEOREM 3.4 (FRIENDLINESS): Algorithm ˆ M corresponds to µ = 0, whereas ˜ M corresponds to µ = 1 in the equilibrium formulation.The equilibrium uses x := (xs, xg), with xg and τg denoting TCP NewReno throughput and RTT.
  • APPENDIX D PROOF OF THEOREM 3.4 (FRIENDLINESS): Condition C2 guarantees the inverse of ∂Φs/∂xs(xs; µ), denoted D(µ), exists.The proof applies the implicit function theorem and uses C4 for an additional required property.
  • APPENDIX D PROOF OF THEOREM 3.4 (FRIENDLINESS): The proof derives 1T ∂xs/∂µ ≥ 0 for µ ∈ [0, 1], so aggregate MP-TCP throughput increases with µ.This follows from D(µ) being negative definite, Σi∈s Dir(µ) < 0, and ˜φr(xs) − ˆφr(xs) ≥ 0.
  • APPENDIX D PROOF OF THEOREM 3.4 (FRIENDLINESS): ˜ M, corresponding to µ = 1, attains higher throughput than ˆ M, corresponding to µ = 0, when separately sharing the test network with the same SP-TCP.The comparison concerns the test network in Fig. 1.
  • A. Proof of part 1: For any eigenvalue λ of J∗, the proof uses a unit-norm corresponding eigenvector z := (x, p) ∈ Z.The eigenvector satisfies ∥z∥2 = 1.
  • A. Proof of part 1: Because the denominator is positive and the numerator is imaginary, condition C2 implies Re(λ) ≤ λ(J∗) ≤ 0 for every eigenvalue.Therefore, the linearized system (10) is stable.

B. Proof of part 2 … A. Proof of part 1

The appendices prove the tradeoff result and Theorem 4.1, while establishing existence, uniqueness, and monotonicity properties for the part-1 solution. The arguments cover both finite n and n = ∞ and distinguish the β = 0 and β > 0 cases.

  • B. Proof of part 2: The proof of part 2 considers two MP-TCP algorithms and establishes the claimed comparison through a contradiction argument.
  • APPENDIX F PROOF OF THEOREM 3.6 (TRADEOFF): The tradeoff proof concludes that ˆΦs(xs) ≥ ˜Φs(xs) under the stated derivative-order assumption.
  • APPENDIX G PROOF OF THEOREM 4.1: Theorem 4.1 is proved for every finite n ∈ N+, with the n = ∞ case following from limn→∞∥xs∥n = ∥xs∥∞.
  • APPENDIX G PROOF OF THEOREM 4.1: For β = 0, φr satisfies C1 and h is negative semidefinite under the theorem’s conditions, so the proof focuses on β > 0.
  • A. Proof of part 1: For finite p ≥ 0 with qr > 0 on every path, the part-1 proof shows that an xs > 0 satisfying φr(xs) = qr exists in two steps.
  • A. Proof of part 1: The scalar ˜C satisfying ψ(˜C) = 1 exists and is unique because ψ(C) is continuous and strictly decreasing.
  • A. Proof of part 1: As pl increases, ys_l(p) decreases, and limpl→∞ ys_l(p) follows because xr → 0 for paths traversing l.

B. Proof of part 2

The proof establishes that φr(xs) satisfies C2 and C3 for β > 0 under 0 < β ≤ 1, |s| ≤ 8, and equal round-trip times. It does so by proving the Jacobian is negative definite and showing C3 directly from (27).

  • Jacobian definiteness: For 0 < β ≤ 1, |s| ≤ 8, and equal τr, the Jacobian ∂Φs(xs)/∂xs is negative definite.The proof reduces negative definiteness to establishing positive definiteness of the associated expression, using Lemma G.2.
  • Condition C3: The proof of C3 follows from (27): xr = 0 implies φr(xs) = ∞, and the converse also holds.Thus, the zero-window condition is characterized exactly by an infinite φr(xs).
  • Positivity argument: For fixed sum M, Lagrange optimization yields a unique minimizer with µ = −3M/m and zi = M.This minimizer is used to establish positivity of f over the constraint set ZM.
  • Positivity argument: When M ≠ 0, minz∈ZM f(z) > 0 if n < 9; when z is nonzero and M = 0, f(z) > 0 follows from (35).These positivity results complete the definiteness argument needed for the theorem.

APPENDIX H PROOF OF LEMMA 3.1

The appendix proof of Lemma 3.1 begins from the definition of D_k(A_k) and uses independence to derive probability expressions and their small-q_k expansions.

  • The proof first invokes the definition of D_k(A_k) as its starting relation.
  • Independence of a_ij is used to justify the final equality in the displayed derivation.
  • The proof expands P(P_j a_kj ≥ 1) as 1 − (1 − q_k)^|A_k| = |A_k|q_k + o(q_k).
Loading 1308.3119v3…