1A Unified Framework for Multipath Routing forUnicast and Multicast TrafficTuna G¨uven†, Richard J. La†, Mark A. Shayman,†and Bobby Bhattacharjee‡Abstract—We study the problem of load balancing the trafficfrom a set of unicast and multicast sessions. The problem isformulated as an optimization problem. However, we assumethat the gradient of the network cost function is not availableand needs to be estimated. Multiple paths are provided betweena source and a destination using application-layer overlay. Wepropose a novel algorithm that is based on what is known assimultaneous perturbation stochastic approximation and utilizesonly noisy measurements collected and reported to the sources,using an overlay architecture.We consider three network models that reflect different sets ofassumptions regarding multicast capabilities of the network. Usingan analytical model we first prove the almost sure convergence ofthe algorithm to a corresponding optimal solution under eachnetwork model considered in this paper with decreasing stepsizes. Then, we establish the weak convergence (or convergence indistribution) with a fixed step size. In addition, we investigatethe benefits acquired from implementing additional multicastcapabilities by studying the relative performance of our algorithmunder the three network models.I. INTRODUCTIONMulticast traffic over the Internet is growing steadily withincreasing number of demanding applications including Internetbroadcasting, video conferencing, data stream applications,distributions, and exchange of large data sets by geographicallydistributed scientists working in collaboration. Ideally manyof these applications require certain rate guarantees, and pro-viding such guarantees demands that the network be utilizedmore efficiently than with current approaches to satisfy therate requirements. Traffic mapping (or load balancing) is oneparticular method to carry out traffic engineering, which dealswith the problem of assigning traffic load onto pre-establishedpaths to meet certain requirements [1].Many major Internet Service Providers (ISPs) are in variousstages of increasing their network capacity and node connec-tivity [22]. A higher level of network connectivity typicallyprovides multiple paths between source-destination pairs, andoffers an opportunity to better utilize network resources throughload balancing. The focus of this paper is to investigate thepotential benefits of load balancing both unicast and multicasttraffic within a single domain and to propose a practical routingalgorithm for carrying out such load balancing, using only noisynetwork measurements.Although the issue of distributed routing using multiple pathsis an old problem with extensive literature on it (e.g., [5],†– Department of Electrical and Computer Engineering, University ofMaryland, College Park, MD 20742, {tguven,hyongla,shayman}@eng.umd.edu‡– Department of Computer Science, University of Maryland, College Park,MD 20742, [email protected][9]), there is a limited amount of existing work on multi-path multicast routing. Park and Shin [18] propose a schemethat creates multiple trees between a source and a set ofdestinations and splits the traffic optimally among the trees.However, the proposed solution covers only a single sourcecase. In addition, it assumes the existence of the gradient ofan analytical cost function and that the cost function is strictlyconvex and continuously differentiable. As discussed in [7], inpractice it may be difficult, if not impossible, to precisely defineaccurate analytical cost functions due to the dynamic nature ofnetworks. Further, even when an analytical cost function exists,it may not be differentiable everywhere. As we will show inthis paper, these assumptions can be relaxed considerably.In another set of work [17], [24] solutions based on networkcoding are proposed. Even though they approach the problemunder a more general architecture, these solutions suffer fromthe limitations inherited from network coding. Network codingrelies on an unrealistic assumption that the network is losslessas long as the average link rates do not exceed the link capaci-ties. Furthermore, a packet loss can be much more costly whennetwork coding is employed because it can potentially affect thedecoding of a large number of other packets. In addition, anyevent that changes the min-cut max-flow value between a sourceand a receiver requires the code to be updated at every nodesimultaneously. This brings about considerable complexity anddemands a high level of coordination and synchronism amongthe nodes. Besides, similar to earlier efforts, these solutions alsoassume that there is only one multicast session in the network.In this paper we propose a distributed optimal routingalgorithm that balances the load along multiple paths for mul-tiple unicast and multicast sessions. Our measurement-basedalgorithm does not assume the existence of the gradient of ananalytical cost function and is a natural generalization of theunicast routing algorithms proposed in [7], [11]. To the bestof our knowledge this is the first attempt to address the issueof (optimal) multi-path routing with multiple multicast sessionsin a distributed manner, while relying only on (local) networkmeasurements.In order to study the performance of the proposed algorithmand to understand and quantify the benefits of implementingadditional multicast capabilities in the underlying IP network,we consider three different network models with graduallyincreasing network capabilities; first, we look at the problemunder the traditional network model without any IP multicastfunctionality. In this model multiple paths are provided usinga limited number of (application-layer) overlay nodes that areused as relay nodes. In the second model, we allow IP multicastand load balancing of multicast traffic is carried out utilizing2multiple multicast trees available for each source. These treesare rooted either at the source or at the overlay nodes that actas surrogate sources for traffic forwarded by the source. Therouters are assumed to be capable of copying and forwardingmulticast packets onto downstream branches. Finally, in thethird model we replace the routers in the second model with“smart” routers capable of forwarding multicast packets ontoeach downstream branch at a different rate. This model enablesour algorithm to exercise finer control over rate allocation thanin the second model. These models