View Full Document

A Unified Framework for Multipath Routing for Unicast and Multicast Traffic



View the full content.
View Full Document
View Full Document

9 views

Unformatted text preview:

1 A Unified Framework for Multipath Routing for Unicast and Multicast Traffic Tuna Gu ven Richard J La Mark A Shayman and Bobby Bhattacharjee Abstract We study the problem of load balancing the traffic from a set of unicast and multicast sessions The problem is formulated as an optimization problem However we assume that the gradient of the network cost function is not available and needs to be estimated Multiple paths are provided between a source and a destination using application layer overlay We propose a novel algorithm that is based on what is known as simultaneous perturbation stochastic approximation and utilizes only noisy measurements collected and reported to the sources using an overlay architecture We consider three network models that reflect different sets of assumptions regarding multicast capabilities of the network Using an analytical model we first prove the almost sure convergence of the algorithm to a corresponding optimal solution under each network model considered in this paper with decreasing step sizes Then we establish the weak convergence or convergence in distribution with a fixed step size In addition we investigate the benefits acquired from implementing additional multicast capabilities by studying the relative performance of our algorithm under the three network models I I NTRODUCTION Multicast traffic over the Internet is growing steadily with increasing number of demanding applications including Internet broadcasting video conferencing data stream applications distributions and exchange of large data sets by geographically distributed scientists working in collaboration Ideally many of these applications require certain rate guarantees and providing such guarantees demands that the network be utilized more efficiently than with current approaches to satisfy the rate requirements Traffic mapping or load balancing is one particular method to carry out traffic engineering which deals with the problem of assigning traffic load onto pre established paths to meet certain requirements 1 Many major Internet Service Providers ISPs are in various stages of increasing their network capacity and node connectivity 22 A higher level of network connectivity typically provides multiple paths between source destination pairs and offers an opportunity to better utilize network resources through load balancing The focus of this paper is to investigate the potential benefits of load balancing both unicast and multicast traffic within a single domain and to propose a practical routing algorithm for carrying out such load balancing using only noisy network measurements Although the issue of distributed routing using multiple paths is an old problem with extensive literature on it e g 5 Department of Electrical and Computer Engineering University of Maryland College Park MD 20742 tguven hyongla shayman eng umd edu Department of Computer Science University of Maryland College Park MD 20742 bobby cs umd edu 9 there is a limited amount of existing work on multipath multicast routing Park and Shin 18 propose a scheme that creates multiple trees between a source and a set of destinations and splits the traffic optimally among the trees However the proposed solution covers only a single source case In addition it assumes the existence of the gradient of an analytical cost function and that the cost function is strictly convex and continuously differentiable As discussed in 7 in practice it may be difficult if not impossible to precisely define accurate analytical cost functions due to the dynamic nature of networks Further even when an analytical cost function exists it may not be differentiable everywhere As we will show in this paper these assumptions can be relaxed considerably In another set of work 17 24 solutions based on network coding are proposed Even though they approach the problem under a more general architecture these solutions suffer from the limitations inherited from network coding Network coding relies on an unrealistic assumption that the network is lossless as long as the average link rates do not exceed the link capacities Furthermore a packet loss can be much more costly when network coding is employed because it can potentially affect the decoding of a large number of other packets In addition any event that changes the min cut max flow value between a source and a receiver requires the code to be updated at every node simultaneously This brings about considerable complexity and demands a high level of coordination and synchronism among the nodes Besides similar to earlier efforts these solutions also assume that there is only one multicast session in the network In this paper we propose a distributed optimal routing algorithm that balances the load along multiple paths for multiple unicast and multicast sessions Our measurement based algorithm does not assume the existence of the gradient of an analytical cost function and is a natural generalization of the unicast routing algorithms proposed in 7 11 To the best of our knowledge this is the first attempt to address the issue of optimal multi path routing with multiple multicast sessions in a distributed manner while relying only on local network measurements In order to study the performance of the proposed algorithm and to understand and quantify the benefits of implementing additional multicast capabilities in the underlying IP network we consider three different network models with gradually increasing network capabilities first we look at the problem under the traditional network model without any IP multicast functionality In this model multiple paths are provided using a limited number of application layer overlay nodes that are used as relay nodes In the second model we allow IP multicast and load balancing of multicast traffic is carried out utilizing 2 multiple multicast trees available for each source These trees are rooted either at the source or at the overlay nodes that act as surrogate sources for traffic forwarded by the source The routers are assumed to be capable of copying and forwarding multicast packets onto downstream branches Finally in the third model we replace the routers in the second model with smart routers capable of forwarding multicast packets onto each downstream branch at a different rate This model enables our algorithm to exercise finer control over rate allocation than in the second model These models together provide us with a general framework that helps us


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view A Unified Framework for Multipath Routing for Unicast and Multicast Traffic and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Unified Framework for Multipath Routing for Unicast and Multicast Traffic and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?