mReno: a practical multipath congestion control for communication networks

Abstract

In current networks, end-user devices are usually equipped with several network interfaces. The design of a multipath protocol that can cooperate with current single-path transport protocols is an interesting research field. Most previous works on multipath network utility maximization (NUM) lead to rate-based control protocols. Moreover, these studies do not model a case in which paths from a source may have different characteristics. Thus, these approaches are difficult to deploy to the Internet. In this paper, we introduce a multipath NUM model for a network with both multipath and single-path users. The proposed algorithm converges to a global solution to the multipath NUM. Based on the mathematical framework, we develop a multipath TCP called mReno. Analysis and simulations indicate that mReno is completely compatible with TCP Reno and achieves load-balance, fairness, and performance improvement targets.

Appendix

Proof of Proposition 1

The arguments are closely based on the convergence proof of the gradient decent algorithm [17, Prop.2.3.2].

The function $U_s$ is twice continuously differentiable for all $s \in \mathcal N$, thus, the function $\hat{V}$ is has a similar property. That is, there exists a constant $L$ such that $\Vert \nabla \hat{V}(\varvec{x}) - \nabla \hat{V}(\varvec{y})\Vert \le L \Vert \varvec{x}-\varvec{y}\Vert , \forall \varvec{x},\varvec{y}$ bounded. The gradient update (4) does not decrease the objective of Approximation problem in every inner-iteration [17, Prop.2.3.2] or [18, Prop.3.3].

$$\begin{aligned} \hat{V}(\varvec{x}^{(\tau )}(k);\varvec{\theta }^{(\tau )}) \le \hat{V}(\varvec{x}^{(\tau )}(k + 1);\varvec{\theta }^{(\tau )}) - \left( \frac{L}{2} - \frac{1}{\kappa }\right) \Vert \varvec{x}^{(\tau )}(k+1) - \varvec{x}^{(\tau )}(k)\Vert ^2.\qquad \end{aligned}$$

(12)

If the stepsize $0< \kappa < 2/L$, the following inequalities are obtained

$$\begin{aligned} V(\varvec{x}^{(\tau -1)}(K))&= \hat{V}(\varvec{x}^{(\tau )}(0);\varvec{\theta }^{(\tau )}) \end{aligned}$$

(13)

$$\begin{aligned}&\le \hat{V}(\varvec{x}^{(\tau )}(K);\varvec{\theta }^{(\tau )}) - \left( \frac{L}{2} - \frac{1}{\kappa }\right) \sum _{k=0}^{K-1} \Vert \varvec{x}^{(\tau )}(k+1) - \varvec{x}^{(\tau )}(k)\Vert ^2 \end{aligned}$$

(14)

$$\begin{aligned}&\le V(\varvec{x}^{(\tau )}(K)) - \left( \frac{L}{2} - \frac{1}{\kappa }\right) \sum _{k=0}^{K-1} \Vert \varvec{x}^{(\tau )}(k+1) - \varvec{x}^{(\tau )}(k)\Vert ^2 . \end{aligned}$$

(15)

Equation (13) is obtained by replacing $\theta _{s,i}^{(\tau )}$ with $\frac{x^{(\tau -1)}_{s,i}(K)}{\sum _{j \in s}x^{(\tau -1)}_{s,j}(K)}$ and $\varvec{x}^{(\tau )}(0)$ with $\varvec{x}^{(\tau - 1)}(K)$. Inequality (14) is obtained by summing $K$ inequalities (12) when $k = 0,..,K-1$. Inequality (15) is satisfied because of (1). $\square$

The sequence $V(\varvec{x}^{(\tau )}(K))$ is non-decreasing and bounded as $\varvec{x}$ is bounded. Therefore, the sequence $V(\varvec{x}^{(\tau )}(K))$ converges as $\tau \rightarrow \infty$. From (13)–(15), we also have $\Vert \varvec{x}^{(\tau )}(k+1) - \varvec{x}^{(\tau )}(k)\Vert ^2 \rightarrow 0$ as $\tau \rightarrow \infty$ for $k=0,\ldots ,K-1$.

Let $\varvec{x}^*$ be any limit point, i.e., there is a subsequence $\varvec{x}^{(\tau _n)}(K) \rightarrow \varvec{x}^*$ as $n \rightarrow \infty$. Since $\Vert \varvec{x}^{(\tau _n)}(k+1) - \varvec{x}^{(\tau _n)}(k)\Vert ^2 \rightarrow 0$ as $n \rightarrow \infty , k = 0,\ldots ,K-1$, the limit point $\varvec{x}^*$ is also a stationary point of the gradient update (4). We have

$$\begin{aligned} \nabla \hat{V}(\varvec{x}^*;\varvec{\theta }^*) = 0 \end{aligned}$$

where $\theta ^*_{s,i}$ is the limit point of $\frac{x_{s,i}^{(\tau _n)}(0)}{\sum _{j \in s}x_{s,j}^{(\tau _n)}(0)}$ according to Step 5 of Algorithm 1. Moreover, due to $\Vert \varvec{x}^{(\tau _n)}(k+1) - \varvec{x}^{(\tau _n)}(k)\Vert ^2 \rightarrow 0$ as $n \rightarrow \infty$ for $k=0,\ldots ,K-1$, the sequences $\varvec{x}^{(\tau _n)}(k), k=0,\ldots ,K$ converges to $\varvec{x}^*$ as $n \rightarrow \infty$. Therefore, we have $\theta ^*_{s,i} = \frac{x^*_{s,i}}{\sum _{k \in s}x^*_{s,k}}$.

Now, we can easily verify that

$$\begin{aligned} \frac{\partial V(\varvec{x})}{\partial x_{s,i}}\bigg |_{\varvec{x}=\varvec{x}^*} = \frac{\partial \hat{V}(\varvec{x};\varvec{\theta }^*)}{\partial x_{s,i}}\bigg |_{\varvec{x}=\varvec{x}^*} \end{aligned}$$

with $\theta ^*_{s,i} = \frac{x^*_{s,i}}{\sum _{k \in s}x^*_{s,k}}$ , for all $s \in \mathcal N$ and $i \in s$. Therefore,

$$\begin{aligned} \nabla {V}(\varvec{x}^*) = 0. \end{aligned}$$

In case $0<\epsilon <1, V(\varvec{x})$ is a strictly concave function w.r.t $\varvec{x}$. Therefore, $\varvec{x}^*$ is the unique global optimal solution to Main problem.