Strategy of Constructing Minimum Cost Multicast Routing Tree with Delay and Delay Variation Bounds
Ming Wang · Chinese Journal of Computers · 2002
This paper studies the problem of constructing multicast routing tree with delay and delay variation bounds. This problem can be formulated as that of finding a minimum cost Steiner Tree, which satisfies the constraints above mentioned and is known to be computationally intractable, being NP complete. While researching into the problem of constructing multicast routing tree with delay and delay variation bounds, we find that two best edge selection functions,which are betaken abroad to constructing multicast routing tree in many algorithms have some limitations. And just because of their limitations, on a certain occasion, the final tree constructed through them can not span all the destinations. At the same time they can not represent the dynamic characteristics of the routing process completely. Therefore, we propose a destination reachable qualification and a new edge selection function. In addition to the problem of delay and delay variation bounded multicast routing, based on our edge selection function, we put forward a heuristic algorithm called Delay and Delay Variation Bounded Multicast Routing Algorithm (DDVBMRA) by which a minimum cost multicast tree can be constructed. Besides, a method of adjusting to the dynamic change of multicast membership is introduced. It is shown that, in terms of delay variation and cost, the heuristic algorithm demonstrates good average case behavior through simulations on a large number of graphs.