The Research On Heuristic Multi-constrained QoS Multicast Routing Algorithm

The recent proliferation of QoS-aware group applications over the Internet, such as video conferencing, news distributions, distance learning, software upgrading etc, has accelerated the need for scalable and efficient multicast support. Multicast is a more efficient transport mechanism than unicast on point-to-multipoint data transmitting. In the traditional unicast the source need to send an individual copy of the same data to each receiver, so a single stream may unnecessarily require a large portion of the available network bandwidth, if there are thousands of receivers, it maybe give rise to network congestion. While in the multicast there is only one copy of the same data on the main path links and the routers make copies only on the branches, so it uses the least network bandwidth.The multicast data transporting topology is a multicast tree and nowadays more and more multimedia applications require QoS guarantees, so how to build a multicast tree that meet the corresponding QoS constraints has emerged as one of the biggest challenges in the field of multicast research. Many researchers have been heavily involved in studying and designing QoS multicast routing algorithms and protocols. QoS multicast routing has been a topic of intense research and development efforts over the past couple of years.To find a feasible path that meet multi-constraints is a NP-complete problem. We propose an algorithm Opposed to the situation that the constrained minimum Steiner tree (CMST) problem has been attracting much attention in quality of service (QoS) routing area, little work has been done on multicast routing subject to multiple additive constraints even though this is required by many emerging applications. In this paper, we propose a heuristic HMCMC to find feasible solutions to this problem. HMCMC has a provably low time complexity, and its basic idea is to construct a multicast tree step-by-step, which is done essentially based on the latest research results on multi-constrained multicast routing. Computer simulations demonstrate that HMCMC can achieve a high success ratio of finding feasible solutions.