Two algorithms for multi-constrained optimal multicast routing

摘要

Multimedia applications, such as video-conferencing and video-on-demand, often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. However, most previous efforts have focused on special situations where a single or a pair of constraints is considered. In general, routing under multiple constraints, even in the unicast case is an NP-complete problem. We present in this paper two practical and efficient algorithms, called multi-constrained QoS dependent multicast routing (M_QDMR) and (multicasting routing with multi-constrained optimal path selection (M_MCOP)), for QoS-based multicast routing under multiple constraints with cost optimization. We provide proof in the paper that our algorithms are correct. Furthermore, through extensive simulations, we illustrate the effectiveness and efficiency of our proposals and demonstrate their significant performance improvement in creating multicast trees with lower cost and higher success probability.