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. In this paper, 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 queueing delay, which in turn depends on the available bandwidth. Based on this observation we propose an optimal multicast routing algorithm, which maximizes the reserved bandwidth while satisfying both delay and bandwidth constraints. Its correctness and time-complexity of O(n/sup 2/log n) are formally verified, where n is the number of nodes in the network. We also extend the algorithm to be dynamic, such that nodes are allowed to join or leave the network, with the multicast route updated dynamically. We carefully evaluate both the static and the dynamic algorithms via simulation. We found that the new algorithm significantly reduces the end-to-end delay experienced by network packets; its dynamic version is able to rapidly update the multicast route using little computation time. We believe that both versions of the new algorithm are important to the area of QoS-based multicast routing; their design and analysis may give new insights to network researchers in their future design of routing protocols.
展开▼
