QoS-guaranteed one-to-many and many-to-many multicast routing

Quality-of-service (QoS) multicast routing with more than one metric has always been technically challenging, since many of them are NP-hard. Most existing QoS multicast routing algorithms are heuristic. Furthermore, many of them considered only the unicast shortest paths, either based on propagation delay or the number of hops. The first part of this paper deals with one-to-many multicast routing. We observed that the end-to-end delay experienced by network packets is determined not only by the propagation distance, but also (and in many cases largely) by the hop-by-hop transmission and queuing delay, which in turn depends on the available bandwidth. Based on this observation, we propose an optimal multicast routing algorithm (the MBDC algorithm), which maximizes the reserved bandwidth while satisfying both delay and bandwidth constraints. Its correctness and time complexity of O(n(2) log n) are formally verified, where n is the number of nodes in the network. We also extend the algorithm to support dynamic membership, allowing nodes to join or leave the network, with the cast route updated dynamically. We carefully evaluate both the static and the dynamic algorithms via simulation. The second part of the paper focuses on minimizing the number of centers of multiple-shared multicast trees (MSMT) in many-to-many multicast routing. We propose three heuristic algorithms to this NP-complete problem and compare them with an existing one. We prove, theoretically and through simulation, that our algorithms give the same good results with a significantly shorter running time. We also apply the MBDC extension to the MSMT algorithms, so that the resulting solution not only reduces the number of centers, but also optimizes (maximizes) the bottleneck bandwidth. Proof of correctness, analysis of run-time, and simulation results of these extensions are also provided. We believe that the results report here are significant to the area of QoS-aware multicast routing; the algorithms may be applied to the Internet intra- and inter-domain multicast routing with minimal changes. (C) 2002 Elsevier Science B.V. All rights reserved.