Keywords

Traffic Management, convergence, Multipath Routing, Utilization 
INTRODUCTION

THE Internet has evolved into an ultra large and complex system interconnecting diverse endhosts and transmission links, with numerous applications running over it. Traffic management thus becomes a critical challenge to the healthy operation of the Internet. To this end, various traffic management tools have been developed, including TCP congestion control at endhosts, traffic engineering by network operators, and adaptive routing algorithms performed by routers, as shown in Fig. 1. They all target efficient utilization of network resources and quality service to end users. Unfortunately, the collaboration among them is far from being perfect. 
The logarithmic barrier method is a powerful optimization method for constrained optimization, in which logarithmic terms are introduced to prevent feasible iterates from moving too close to the boundary of the feasible region [2]. In this paper, we address the above issues through a novel logarithmbarrierbased approach. Our approach jointly considers user utility and routing/congestion control. It translates the multipath utility maximization into a sequence of unconstrained optimization problems, with infinite logarithm barriers being deployed at the constraint boundary. We demonstrate that setting up barriers is much simpler than choosing cost functions and, more importantly, it makes optimal solution achievable. It can be shown that the sequence of the unconstrained optimization approaches to the optimal solution of one of the original problems . We further demonstrate a distributed implementation, together with the design of a practical LogarithmBarrierbased Multipath Protocol (LBMP). Our LBMP also allows every link to be configured with different control parameters, providing flexibility in dealing with traffic bursts. We evaluate the performance of LBMP through both numerical analysis and packetlevel simulations. The results show that LBMP achieves high throughput and fast convergence over diverse representative network topologies. Such performance is comparable to TRUMP and is often better. In addition, LBMP is flexible in differentiating the control at different links and its optimality and convergence are theoretically guaranteed. 
MULTIPATH UTILITY MAXIMIZATION

Multipath utility maximization appears naturally in many resource allocation problems in communication networks, such as the multipath flow control, the optimal quality of service (QoS) routing and the optimal network. It is shown in that even the singlepath utility maximization is NPhard and generally has a duality gap. An equilibrium of TCP/IP exists if and only if the single path utility maximization has no duality gap. In this case, TCP/IP incurs no penalty in not splitting traffic across multiple paths. Such equilibrium gives a solution to the singlepath utility maximization and its Lagrangian dual, but can be quite unstable. 
We focus on a network of directed links, l belongs to L, and origin destination pairs, s belongs to S. Each origin destination pair represents a source of traffic (or source in short) in the network. Associated with a source is a set of routes, each being a set of links. We represent the routing by matrix Rls that captures the fraction of source s’s flow traversing the links, and we let cl denote the capacity of link l. As shown in the network utilization maximization problem can be formulated as 

Where both R and x are variables. The utility functions Us are increasing, strictly concave, and twice continuously differentiable. For singlepath routing that is widely used in the current Internet, R is a 01 matrix. Set Rls = 1; if link l is in a path of source s; and set Rls = 0 otherwise. It is known that single path routing limits the achievable throughput. If a flow can be flexibly divided and delivered over multiple paths, higher efficiency and robustness can be expected. 
Dualbased Utility Maximizing Protocol (DUMP) is constructed from a distributed solution of using decomposition. DUMP is similar to the TCP dual algorithm in , except that the local maximization is conducted over a vector zs, as opposed to a scalar xs only. DUMP, however, has poor convergence behavior with greedy flows, because the sources can only reduce their sending rates after packet losses. In addition, its utility is based on throughput only. As such, some links will be operating at closetofull capacity, resulting in long delays, particularly with traffic bursts. 
MULTIPATH UTILITY MAXIMIZATION

Our LBMP is derived using a Barrier function technique ,which translates a constrained optimization problem into a sequence of simpler unconstrained optimization problems; it then constructs infinite barriers at the constraint bounds, and ensures every optimization iteration strictly meet the respective constraints. We will demonstrate three noticeable benefits of applying this barrier function method in the multipath traffic management context. First, setting up barriers is much simpler than choosing cost functions; second, with commonly used logarithm barriers, it enables exact solution to the multipath utility maximization; and finally, every link can be allocated with different control parameters, providing flexibility in dealing with traffic bursts. 
Multipath streaming: Optimization of load distribution

Under the current Internet infrastructure, quality of service (QoS) in the delivery of continuous media (CM) is still relatively poor and inconsistent. In this paper we consider providing QoS through the exploitation of multiple paths existing in the network. Previous work has illustrated the advantages of this approach. Here we extend this work by considering a more expressive model for characterizing the network path losses. In particular, we pr oppose a variation on the Gilbert model wherein the loss characteristics of a path depend on an application’s transmission bandwidth. Using this model, we show the benefits of multipath streaming over best singlepath streaming, under optimal load distribution among the multiple paths. We use extensive simulation and measurements from a system prototype to quantify the performance benefits of our techniques. 
Optimal traffic splitting

we present a framework for determining appropriate traffic splitting between the multiple paths used for CM streaming. We use the achieved loss rate and lag1 autocorrelation as our objective functions. 
Optimization based on achieved loss rate

We first consider the minimization of the loss rate, PM, achieved at the receiver as our objective. For path j, let Fj (b) denote the functional transition rate from state 0 to 1 when the streaming traffic on path j is b pkts/s. Similarly, Bj (b) denotes the functional transition rate from state 1 to 0 when the streaming traffic on path j is b pkts/s. Let us first consider a simple case wherein there are two paths available for CM streaming. We define Fj(αjλ) = Fj(αjλ)/(Fj(αjλ) + Bj(αjλ)), for j = 1, 2 and express the achieved loss rate as P2 = α1F1(α1λ) + (1 − α1)F2((1 − α1)λ). 
CONCLUSION

We consider the problem of congestionaware multipath routing in the Internet. Currently, Internet routing protocols select only a single path between a source and a destination. However, due to many policy routing decisions, singlepath routing may limit the achievable throughput. In this paper, we envision a scenario where multipath routing is enabled in the Internet to take advantage of path diversity. Using minimal congestion feedback signals from the routers, we present a class of algorithms that can be implemented at the sources to stably and optimally split the flow between each sourcedestination pair. We then show that the connectionlevel throughput region of such multipath routing/congestion control algorithms can be larger than that of a singlepath congestion control scheme. 

References

 D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiaro. A framework for internet traffic engineering.Network Working Group, Internet Draft (work in progress), http://search.ietf.org/internetdrafts/draftietftewgframework02.txt, 2000.
 W. BenAmeur, N. Michel, E. Gourdin, and B. Liau. Routing strategies for IP networks. Telektronikk, 2/3:145–158, 2001.
 A. Bley, M. Gr¨otchel, and R. Wess¨aly. Design of broadband virtual private networks: Model and heuristics for the BWiN. In Proc. DIMACS Workshop on Robust Communication Networks and Survivability, AMSDIMACS Series 53, pages 1–16,1998.
 R. Callon. Use of OSI ISIS for routing in TCP/IP and dual environments. NetworkWorking Group, Request for Comments:1195, http://search.ietf.org/rfc/rfc1195.txt, December 1990.
 Cisco. Configuring OSPF, 1997. Documentation at http://www.cisco.com/univercd/cc/td/doc/product/software/ios113ed/113ed cr/np1 c/1cospf.htm.
 M. Ericsson, M.G.C Resende, and P.M. Pardalos. A genetic algorithm for the weightsetting problem in OSPF routing, 2001. To appear in J. Combinatorial Optimization in 2002.
 B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Communications Magazine, 40(10):118–124, 2002.
 B. Fortz and M. Thorup. Increasing internet capacity using local search. Technical Report ISMG 2000/21, Universit´e Libre de Bruxelles, 2000. http://smg.ulb.ac.be/Preprints/Fortz00 21.html.
 B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proc. 19th IEEE Conf. on Computer Communications (INFOCOM), pages 519–528, 2000.
 B. Fortz and M. Thorup. Optimizing OSPF/ISIS weights in a changing world. IEEE Journal on Selected Areas in Communications, 20(4):756–767, 2002.
