Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. VI (2011), No. 4 (December), pp. 656-667 An Optimal Rate Control and Routing Scheme for Multipath Networks S. Li, W. Sun, Y. Zhang, H. Zhang Shiyong Li, Wei Sun, Yaming Zhang School of Economics and Management, Yanshan University, Qinhuangdao, 066004, P.R. China E-mail(s): shiyongli@ysu.edu.cn, wsun@ysu.edu.cn, yaming99@ysu.edu.cn Hongke Zhang School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, P.R. China E-mail: hkzhang@bjtu.edu.cn Abstract: This paper considers optimal rate control and routing schemes for multipath networks which can be formulated as multipath network utility max- imization problems. In these schemes, maximizing the aggregated user utility over the network with multipath routes under the link capacity constraints is the objective of utility maximization problems. By adopting the Lagrangian method, sub-problems for users and paths are deduced and interpreted from an economic point of view. In order to obtain the optimal rate allocation, a novel distributed primal-dual algorithm is proposed, and the performance is evaluated through simulations under two different fairness concepts. Moreover, window-based flow control scheme is also presented since it is more convenient to realize in practical end-to-end implementation than the rate control scheme. Keywords: multipath networks, rate control, routing, network utility maxi- mization, optimization. 1 Introduction Since the publication of the seminal paper [1], the single path rate control and routing schemes which can be formulated as network utility maximization problems have been extensively studied in the past years, mainly in the context of Internet congestion control and flow control (e.g., [2]- [5], and the reference therein). Recently, there has been much interest in multipath rate control and routing schemes [6]- [13]. In a multipath routing scheme, each source-destination pair can have several different paths along which data packet can be transmitted. In these schemes, maximizing aggregated user utility over the network with multipath routes under the link capacity constraints is the objective of the multipath network utility maximization problems. These problems are indeed a combination of multipath routing and rate control and can be viewed as an example of cross- layer optimization [5] for network architectures, where additional benefits are obtained by jointly optimizing at the routing (network layer) and rate control (transport layer). In order to solve the multipath network utility maximization problems, roughly speaking, multipath rate control and routing schemes can be classed into three categories: primal algo- rithms [6], [8], dual algorithms [7], [11], and primal-dual algorithms [9], [10], [12]. The primal algorithms have a dynamical law for adjusting user rate and a static law for generating link price, and conversely, the dual algorithms have a dynamical law for adjusting link price and a Copyright c⃝ 2006-2011 by CCC Publications An Optimal Rate Control and Routing Scheme for Multipath Networks 657 static law for generating user rate. Then, the primal-dual algorithms have dynamical laws for adjusting both user rate and link price. The primal algorithms are based on a penalty function approach, i.e., they replace the capacity constraints by a penalty function in the optimization objective [1], [6], [8]. They always tend to produce biased approximates of the optimal operating points, due to the fact that penalties are only incurred when the capacity constraints are vio- lated. (In contrast, the optimal operating point is defined to be one that satisfies the capacity constraints.) As for the dual algorithms, the advantage is that they are designed to compute the exact optimal operating points when the step sizes are driven to zero in an appropriate fashion [7], [11]. Then the primal-dual algorithms combine the advantages of both primal and dual algorithms, and possess a rapid convergence property to the optimums within reasonable convergence times [9], [10], [12]. In [1], after studying the single-path network utility maximization problem, the authors discuss the extension to the multipath case, where the flow between each source-destination pair can be globally split among multiple paths, and present a distributed rate-based congestion control algorithm. Then in [6] the utility maximization framework for multipath case is further studied, and a primal algorithm with round-trip delay is proposed and investigated. Meanwhile, a decentralized sufficient condition for local stability of the delayed algorithm is obtained. In [8], the sufficient condition for local stability of the primal algorithm with round-trip delay is improved, i.e., the gain parameter for each route is restricted by the round-trip delay of that route, but not by the round-trip delays of other routes, even those other routes serving the same users. Dual algorithms that can produce exact optimal operating points are developed in [2] for single- path networks. When extended to the multipath cases, the primal variables (i.e., the resource allocation) may not be unique although the dual variables (i.e., the price) in the dual algorithms converge. In order to obtain the unique optimum, some researchers relax the multipath network optimization problems and make them strictly concave. The authors in [9] address the problem by adding a quadratic term onto the objective problem and provide rigorous proof of convergence for the dual algorithm. Then in [11] the author proposes a novel relaxed network utility maximization problem and derives a new class of controlled splitting multipath dual algorithms. In [12], by combining the first order Lagrangian method and filtering mechanism, a new primal-dual algorithm is proposed to eliminate typical oscillation behavior in multipath networks. In this paper we investigate the optimal rate control and routing scheme formulated as multipath network utility maximization problem, decompose the optimization problem into two sub-problems for users and paths through Lagrangian method, and give the interpretations for the sub-problems and dual problem from an economic point of view. Furthermore, for each user and its available paths, we analyze the relationship between the prices charged by paths and that paid by the user, and on basis of the difference between them we propose a novel distributed primal- dual algorithm for the optimal rate control and routing, which can converge to the optimum of the utility maximization problem, and present the practical end-to-end implementation in the Internet. The rest of this paper is organized as follows: in Section 2, we analyze the model for jointly optimal rate control and routing scheme known as multipath network utility maximization; in Section 3, we present a novel distributed primal-dual algorithm for optimal rate control and routing; in Section 4, we give some simulation results to illustrate the convergence of the proposed algorithm; finally, we conclude the paper in Section 5. 658 S. Li, W. Sun, Y. Zhang, H. Zhang 2 Multipath Network Utility Maximization 2.1 Model Description Consider a network consisting of a set of links L, a set of paths P and a set of users S. Each link l ∈ L has capacity Cl. Each user identifies a unique source-destination pair. There are multiple paths between each source-destination pair. Associated with each user s ∈ S is a set of paths P(s) where each path p ∈ P(s) is a collection of links L(p). Obviously, associated with a path p ∈ P(s) is a set of paths P(s) which are all associated with the same user s, and with identical source and destination. In following analysis, if a user s transmits along a path p, then we write p ∈ P(s); if a path p uses a link l, then we write p ∈ P(l), where P(l) is the set of paths that use link l. In this paper we make no assumptions about whether the paths p ∈ P(s) are link-disjointed. Obviously the ability to generate link-disjointed paths can assist in the construction of highly robust end-to-end communication for the source-destination pair which is labeled by user s, but the model also covers the case where some or all of the paths p ∈ P(s) of user s share some common path segments. For user s, assume the transmission rate on path p is xsp(t), then the total flow rate of user s is ys(t) = ∑ p:p∈P(s) xsp(t). Meanwhile, the aggregated rate on link l is zl(t) = ∑ p:p∈P(l) xsp(t). User s attains a utility Us(ys(t)) when it transmits at rate ys(t). The multipath network utility maximization is modeled as the following nonlinear optimization problem max ∑ s:s∈S Us(ys(t)) subject to ∑ p:p∈P(s) xsp(t) = ys(t)∑ p:p∈P(l) xsp(t) ≤ Cl over xsp(t) ≥ 0. (1) Here, maximizing the aggregated utility of the user rate ys(t) over all users with the con- straints of link capacities is the objective of network. We are interested in the following class of utility functions proposed in [14] Us(ys(t)) =   ws log ys(t), if αs = 1, ws ys(t) 1−αs 1 − αs , if αs ̸= 1, (2) where ws is considered as the willingness to pay of user s, αs is the parameter of fairness concept. This family of utility functions are known to characterize a large class of fairness concepts and have been investigated extensively [13], [15], [12]. In particular, if we set αs = 0, the optimization problem reduces to throughput maximization. If αs = 1, proportional fairness among competing users is obtained; if αs = 2, then harmonic mean fairness; and if αs = ∞, then max-min fairness [14]. For example, these utility functions are considered in wireless networks and optimal network performance and energy efficiency is achieved by jointly optimizing congestion control and power control [13]. 2.2 Model Analysis The utility maximization problem (1) with utility functions (2) is regarded as the primal problem with primal variables x = (xsp(t), p ∈ P(s)) and y = (ys(t), s ∈ S). Then we can obtain the following theorem An Optimal Rate Control and Routing Scheme for Multipath Networks 659 Theorem 1. The rate allocation model (1) with utility functions (2) is a convex programming problem. The optimal total flow rate of each user, i.e. y∗s , exists and is unique. However, the optimal flow rate of each user on every path, i.e. xsp(t), may be not unique. Proof: From the nonlinear programming theory [13], the objective of (1) is concave with respect to primal variables. The constraints of (1) are linear, and thereby all of them are convex. So the feasible set is compact. We deduce that (1) is a convex programming problem. Furthermore, the optimization problem is strictly convex with respect to primal variable y = (ys(t), s ∈ S), then the optimal flow rate y = (y∗s, s ∈ S) exists and is unique as a consequence of strict convexity. However, the objective of (1) is not strictly concave with respect to primal variable x = (xsp(t), s ∈ S, p ∈ P), thus the optimal flow rate of each user on every path may be not unique. 2 In order to investigate the optimum of model (1), we firstly give the Lagrangian of this nonlinear optimization problem L(x, y; λ, µ) = ∑ s:s∈S  Us(ys(t)) + λs   ∑ p:p∈P(s) xsp(t) − ys(t)    +∑ l:l∈L µl  Cl − ∑ p:p∈P(l) xsp(t) − ε2l  , (3) where λ = (λs, s ∈ S) is the price vector with element λs ≥ 0, which is the Lagrange multiplier associated with the equality on user s, and can be considered as the price per unit bandwidth paid by user s; µ = (µl, l ∈ L) is the price vector with element µl ≥ 0, which is the Lagrange multiplier associated with the inequality constraint on link l, and can be considered as the price per unit bandwidth charged by link l; ε2l is the slack variable, which can be considered as the spare capacity of link l. Then the Lagrangian (3) can be rewritten as L(x, y; λ, µ) = ∑ s:s∈S (Us(ys(t)) − λsys(t))+ ∑ s:s∈S ∑ p:p∈P(s) xsp(t)  λs − ∑ l:l∈L(p) µl  +∑ l:l∈L µl ( Cl − ε2l ) . (4) Notice that the first term in (4) is separable in ys(t), and the second term is separable in xsp(t). Thus the objective function of the dual problem is D(λ, µ) = max x,y L(x, y; λ, µ) = ∑ s:s∈S As(λs) + ∑ s:s∈S ∑ p:p∈P(s) Bsp(λs, γsp) + ∑ l:l∈L µl ( Cl − ε2l ) , (5) where As(λs) = max ys(t) Us(ys(t)) − λsys(t), (6) Bsp(λs, γsp) = max xsp(t) xsp(t)(λs − γsp), γsp = ∑ l:l∈L(p) µl. (7) Then, the optimal flow rate can be denoted as y∗s(λs) = argmax Us(ys(t)) − λsys(t), x∗sp(γsp) = argmax xsp(λs)(λs − γsp), where ∑ p:p∈P(s) xsp(λs) = y ∗ s(λs), γsp = ∑ l:l∈L(p) µl. 660 S. Li, W. Sun, Y. Zhang, H. Zhang Hence, the dual problem is min D(λ, µ) over λs ≥ 0, µl ≥ 0, s ∈ S, l ∈ L. (8) We can interpret the sub-problems (6)(7) from an economic point of view as follows. The sub-problem (6) is regarded as the USER problem. In this problem, every user s tries to maximize its own utility which depends on the total flow rate ys(t). Meanwhile, the user has to pay a price for its using bandwidth. Since λs is the price per unit bandwidth paid by user s, then λsys(t) is the total cost that user is willing to pay. Thus, the USER problem (6) is a nonlinear optimization problem that every user is to maximize its own profit. The sub-problem (7) is regarded as the PATH problem. In this problem, µl is the price per unit bandwidth charged by link l, then γsp is the total price associated with the path p of user s. The product xsp(t)λs is the cost paid by user s for path p, and xsp(t)γsp is the total cost charged by path p. Hence, the PATH problem (7) is a linear optimization problem that every path is to maximize its own revenue. Meanwhile, the dual problem (8) can be considered as the NETWORK problem. The ob- jective is to minimize the total price charged by all links under the constraints that users are guaranteed with certain levels of satisfaction. Indeed, the price paid by a user and those charged by its paths is an equilibrium from the game theory point of view. For model (1) and its Lagrangian (4) we can obtain the following theorem. Theorem 2. At the positive optimum of model (1), the optimal total prices associated with paths for a user are all equal to the optimal price paid by the user. Proof: Indeed, at the optimum of model (1), from the Karush-Kuhn-Tucker condition for opti- mality of an optimization problem, we can obtain U′s(y∗s) − λ ∗ s ⇒ { = 0, if y∗s > 0, ≤ 0, if y∗s = 0, ∀s ∈ S, λ∗s − γ ∗ sp = λ ∗ s − ∑ l:l∈L(p) µ∗l ⇒ { = 0, if x∗sp > 0, ≤ 0, if x∗sp = 0, ∀s ∈ S, ∀p ∈ P(s). Thus, for the multiple paths that a user uses, e.g., p1, p2 ∈ P(s), the optimal total price associated with each path is∑ l:l∈L(p1) µ∗l = ∑ l:l∈L(p2) µ∗l = λ ∗ s = ws(∑ p:p∈P(s) x ∗ sp )αs . (9) 2 3 Distributed Algorithm 3.1 Rate Control Algorithm To obtain the optimal flow rate in a decentralized architecture, we present the following distributed primal-dual algorithm, which depends on locally available information. Each user s updates its flow rate xsp(t) on path p with the following primal algorithm dxsp(t) dt = (κxsp(t)(λs(t) − γsp(t)))+xsp(t) , (10) An Optimal Rate Control and Routing Scheme for Multipath Networks 661 λs(t) = ws(∑ p:p∈P(s) xsp(t) )αs , (11) γsp(t) = ∑ l:l∈L(p) µl(t), (12) where κ > 0 is the step size; a = (b)+c means a = b if c > 0 and a = max{0, b} if c = 0. Each link l updates its price µl(t) with the following dual algorithm dµl(t) dt = ( υ zl(t) − Cl Cl )+ µl(t) , (13) zl(t) = ∑ p:p∈P(l) xsp(t), (14) where υ > 0 is the step size. In the primal-dual algorithm, user s computes the price λs(t) paid for path p according to (11), obtains the total price γsp(t) charged by the path from (12), and updates its rate xsp(t) according to (10), which is a fluid model depending on the difference between the price paid by user s and the price charged by path p. Meanwhile, link l observes the aggregated rate zl(t) on it, and updates its price µl(t) according to (13), which is identical to the packet loss rate on the link. Obviously, the primal-dual algorithm is distributed, which only depends on locally available information. Obviously, the rule for rate update (10)(11)(12) is a scaled gradient algorithm for the PATH sub-problem, and can be reduced to the single-path rate control algorithm when only a single path is available for each user. Meanwhile, the rule for price update (13)(14) is also a gradient algorithm, and is similar to the single-path price algorithms designed for solving the dual problems. 3.2 End-to-End Implementation In practical end-to-end implementation, window-based flow control where the window size is increased or decreased upon receipt of acks (positive acknowledgments) or nacks (negative acknowledgments) is more convenient to implement than rate-based flow control mechanism since the former is inherently self-clocking. In order to obtain a window flow control scheme, we discretize the system (10)(11)(12) and obtain xsp(t + δ) − xsp(t) δ = κxsp(t)(∑ p:p∈P(s) xsp(t) )αs  wr −   ∑ p:p∈P(s) xsp(t)  αs ∑ l:l∈L(p) µl(t)   . (15) Here, we assume xsp(t) > 0. Let Wsp(t) be the window size of user s on its path p at time t. We follow the approximation relating data transmission rate and window size [14] xsp(t) ≈ Wsp(t) RTTp , where RTTp is the round trip time of path p. 662 S. Li, W. Sun, Y. Zhang, H. Zhang Let Ap(t, t + δ) and Np(t, t + δ) denote the numbers of acks and nacks received by user s on path p in the time interval [t, t + δ), respectively. Then Ap(t, t + δ) δ ≈ xsp(t) ≈ Wsp(t) RTTp , and Np(t, t + δ) δ ≈ xsp(t) ∑ l:l∈L(p) µl(t). Thus, xsp(t + δ) − xsp(t) δ = Wsp(t + δ) − Wsp(t) Ap(t, t + δ) Ap(t, t + δ) RTTpδ = Wsp(t + δ) − Wsp(t) Ap(t, t + δ) Wsp(t) RTT 2p . Using the approximations above, the window-based flow control mechanism becomes Wsp(t + δ) − Wsp(t) = κwsRTTp ( ∑ p:p∈P(s) Wsp(t)/RTTp) αs Ap(t, t + δ) − κRTTpNp(t, t + δ). (16) In order to damp the oscillation when window size is too small, we modify (16) into Wsp(t + δ) − Wsp(t) = κwsRTTpAp(t, t + δ) − κRTTp   ∑ p:p∈P(s) Wsp(t) RTTp  αs Np(t, t + δ). (17) The window-based flow control mechanism (17) can be interpreted as follows: when each ack is received, the window size is increased by a fixed amount which is in proportion to RTTp; when each nack is received, the window size is decreased by a fixed amount which is in proportion to RTTp( ∑ p:p∈P(s) Wsp(t)/RTTp) αs . Hence, the window flow control scheme realizes the adaptive increase/multiplicative decrease (AIMD) principle which is used in the original TCP version and other variants. For the total price associated with each path in practical end-to-end implementation, we present a way to communicate path prices to users implicitly, i.e., a user deduces the aggregated price on each path from observed round trip time. Notice that queuing length bl(t) evolves according to dbl(t) dt = (zl(t) − Cl)+. (18) Comparing (18) with (13), we can observe that the link price µl(t) at time t is proportional to the current queuing delay ql(t), i.e., µl(t) = υ bl(t) Cl = υql(t). Then the price on path p is proportional to the end-to-end queuing delay at time t γsp(t) = ∑ l:l∈L(p) µl(t) = υ ∑ l:l∈L(p) ql(t). Given the end-to-end propagation delay Dp, the price associated with path p can be deduced from the round trip time RTTp observed at the user s γsp(t) = υ ∑ l:l∈L(p) ql(t) = υ(RTTp − Dp). In practical implementation, Dp can be estimated by the minimum RTTp observed so far. An Optimal Rate Control and Routing Scheme for Multipath Networks 663 4 Simulation In this section, we investigate the performance of the proposed primal-dual algorithm and give simulation results to illustrate the convergence of our algorithm. We make no assumption that the paths for a user are link-disjointed and consider the general multipath communication where some of the paths for a user can share some path segments in common, just as shown in Figure 1. There are two users in this simple network. Two paths are available for each user, i.e., paths A→B→C and D→E→F→G for user 1 (pair of S1 and D1), and paths D→E→F→G and H→I→F→G for user 2 (pair of S2 and D2). Obviously, the two paths for user 2 share a common link which is labeled by L5. There are seven unidirectional links with capacities C = (C1, C2, C3, C4, C5, C6, C7) = (3, 2, 3, 4, 4, 2, 3)Mbps. In the proposed algorithm, we choose w = (w1, w2) = (2, 3), and κ = υ = 0.05. A D E I GS2 H BS1 D1 D2F L1 C L2 L3 L4 L5 L6 L7 Figure 1: Multipath network topology 4.1 Proportional Fairness We firstly consider the proportional fairness among competing users, thus the fairness pa- rameter is α1 = α2 = 1. Without loss of generality, assume the initial rate of each user on every available path is 1Mbps. The optimum obtained by the proposed algorithm is listed in Table 1. The optimal solution solved by nonlinear programming software LINGO is also presented in the table. variable x∗11 x ∗ 12 x ∗ 21 x ∗ 22 y ∗ 1 y ∗ 2 algorithm 2.0000 0.4000 1.6440 1.9560 2.4000 3.6000 LINGO 2.0000 0.4000 1.7360 1.8640 2.4000 3.6000 Table 1. The optimum under multipath network topology: proportional fairness Obviously, the algorithm is convergent and efficient to solve the optimum of multipath net- work utility maximization problem under the general multipath network topology. Also as shown in Table 1, the optimal rate of user 2 on its paths is not unique, which has been proved in The- orem 1. However, the total optimal rate for each user is unique since the optimization problem is strictly convex with respect to primal variable y = (ys(t), s ∈ S). The simulation results for proportional fairness in this general multipath network topology are shown in Figure 2, where (a) and (b) are the optimal prices for users 1 and 2, respectively, and (c) and (d) are the optimal rates of users 1 and 2, respectively. Obviously, both the prices for users and rates of users converge to the optimum. It can also be observed that at the optimum the optimal total price associated with each path that a user uses is equal to the optimal price paid by the user. 664 S. Li, W. Sun, Y. Zhang, H. Zhang 0 100 200 300 400 500 0 0.5 1 1.5 Iterations P ri ce s γ 11 γ 12 λ 1 (a)Prices for user 1 0 100 200 300 400 500 0 0.5 1 1.5 Iterations P ri ce s γ 21 γ 22 λ 2 (b)Prices for user 2 0 100 200 300 400 500 0 1 2 3 4 5 Iterations R at es x 11 x 12 y 1 (c)Rates of user 1 0 100 200 300 400 500 1 2 3 4 5 Iterations R at es x 21 x 22 y 2 (d)Rates of user 2 Figure 2: Performance of the algorithm: proportional fairness 4.2 Harmonic Mean Fairness Now we consider the harmonic mean fairness among competing users, thus the fairness pa- rameter is α1 = α2 = 2. The optimums obtained by the proposed algorithm and LINGO are both listed in Table 2. Obviously, the algorithm is convergent and efficient to solve the optimum of utility maximization problem. Also, the optimal rate of user 2 on its paths is not unique, however, the total optimal rate for each user is unique since the optimization problem is strictly convex with respect to y = (ys(t), s ∈ S). variable x∗11 x ∗ 12 x ∗ 21 x ∗ 22 y ∗ 1 y ∗ 2 algorithm 2.0000 0.6969 1.5748 1.7283 2.6969 3.3031 LINGO 2.0000 0.6969 1.6070 1.6961 2.6969 3.3031 Table 2. The optimum under multipath network topology: harmonic mean fairness The simulation results for harmonic mean fairness in this general multipath network topology are shown in Figure 3, where (a) and (b) are the optimal prices for users 1 and 2, respectively, and (c) and (d) are the optimal rates of users 1 and 2, respectively. Obviously, the algorithm is convergent to the optimum of multipath network utility maximization problem. Meanwhile, at the optimum the optimal total price associated with each path of a user is equal to the optimal price paid by the user. An Optimal Rate Control and Routing Scheme for Multipath Networks 665 0 200 400 600 800 0 0.1 0.2 0.3 0.4 0.5 Iterations P ri ce s γ 11 γ 12 λ 1 (a)Prices for user 1 0 200 400 600 800 0 0.1 0.2 0.3 0.4 0.5 Iterations P ri ce s γ 21 γ 22 λ 2 (b)Prices for user 2 0 200 400 600 800 0 0.5 1 1.5 2 2.5 3 3.5 Iterations R at es x 11 x 12 y 1 (c)Rates of user 1 0 200 400 600 800 1 1.5 2 2.5 3 3.5 Iterations R at es x 21 x 22 y 2 (d)Rates of user 2 Figure 3: Performance of the algorithm: harmonic mean fairness 5 Conclusions In this paper, we have studied the optimal rate control and routing schemes in communication networks with multipath routing, which are formulated as multipath network utility maximiza- tion problems. We decompose the utility optimization problem into two sub-problems, deduce the dual problem through the Lagrangian method, and give the interpretation for them from an economic point of view. In order to obtain the optimum, we propose a novel primal-dual algorithm for jointly optimizing rate control and routing, and give the window-based flow con- trol scheme in practical end-to-end implementation. We don’t assume that whether the paths of a user are node-disjoint, thus the algorithm also covers the case where the paths for a user are node-disjoint in parallel, which is regarded as concurrent multipath communication. Then, we evaluate the performance of the proposed algorithm through simulations under two different fairness concepts. Simulation results confirm that the algorithm can achieve the optimum within reasonable convergence times. Acknowledgements The authors would like to thank the support from the National Natural Science Foundation of China under Grants 71101124, 71171174 and 60974018, and the National Basic Research Program of China (973 Program) under Grant 2007CB307100. 666 S. Li, W. Sun, Y. Zhang, H. Zhang Bibliography [1] F. P. Kelly, A. Maulloo, D. Tan, Rate control in communication networks: Shadow prices, proportional fairness and stability, Journal of the Operational Research Society, 49(3): 237- 252, 1998. [2] S. H. Low, D. E. Lapsley, Optimization flow control, I: basic algorithm and convergence, IEEE/ACM Transactions on Networking, 7(6): 861-874, 1999. [3] F. P. Kelly, Fairness and stability of end-to-end congestion control, European Journal of Control, 9(2-3): 159-176, 2003. [4] S. H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Trans- actions on Networking, 11(4): 525-536, 2003. [5] M. Chiang, S. H. Low, A. R. Calderbank, J. C. Doyle, Layering as optimization decom- position: a mathematical theory of network architectures, Proceedings of the IEEE, 95(1): 255-312, 2007. [6] H. Han, S. Shakkottai, C. V. Hollot, R. Srikant, D. Towsley, Overlay TCP for multi-path routing and congestion control, presented at ENS-INRIA ARC-TCP Workshop, Paris, France, 2003. [7] W. H. Wang, M. Palaniswami, S. H. Low, Optimal flow control and routing in multi-path networks, Performance Evaluation, 52(2-3): 119-132, 2003. [8] F. P. Kelly, T. Voice, Stability of end-to-end algorithms for joint routing and rate control, ACM Computer Communication Review, 35(2): 5-12, 2005. [9] X. Lin, N. B. Shroff, Utility maximization for communication networks with multipath rout- ing, IEEE Transactions on Automatic Control, 51(5): 766-781, 2006. [10] H. Han, S. Shakkottai, C. V. Hollot, D. Towsley, Multi-path TCP: A joint congestion control and routing scheme to exploit path diversity in the Internet, IEEE/ACM Transactions on Networking, 14(6): 1260-1271, 2006. [11] T. Voice, Stability of multi-path dual congestion control algorithms, IEEE/ACM Transac- tions on Networking, 15(6): 1231-1239, 2007. [12] J. Jin, W. H. Wang, M. Palaniswami, Utility max-min fair resource allocation for commu- nication networks with multipath routing, Computer Communications, 32(17): 1802-1809, 2009. [13] J. Zhang, H. N. Lee, Energy-efficient utility maximization for wireless networks with/without multipath routing, AEU-International Journal of Electronics and Communications, 64(2): 99-111, 2010. [14] J. Mo, J. Walrand, Fair end-to-end windows-based congestion control, IEEE/ACM Trans- actions on Networking, 8(5): 556-567, 2000. [15] J. W. Lee, M. Chiang, R. A. Calderbank, Utility-optimal random access control, IEEE Transactions on Wireless Communications, 6(7): 2741-2751, 2007. An Optimal Rate Control and Routing Scheme for Multipath Networks 667 [16] C. Long, B. Li, Q. Zhang, B. Zhao, B. Yang, X. Guan, The end-to-end rate control in multiple-hop wireless networks: Cross-layer formulation and optimal allocation, IEEE Jour- nal on Selected Areas in Communications, 26(4): 719-731, 2008. [17] D. Bertsekas, Nonlinear Programming. 2nd ed., Athena Scientific, Nashua, USA, 1999. [18] T. V. Lakshman, U. Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking, 5(3): 336-350, 1997.