For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Finding Feasible Solutions for the Group Multicast Routing Problem
Chor Ping LOW Ning WANG
IEICE TRANSACTIONS on Communications
Publication Date: 2002/01/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
group multicast routing, heuristic algorithms, bandwidth constraint, NP-complete,
Full Text: PDF>>
In this paper we addresses the problem of finding feasible solutions for the Group Multicast Routing Problem (GMRP). This problem is a generalization of the multicast routing problem whereby every member of the group is allowed to multicast messages to other members from the same group. The routing problem involves the construction of a set of low cost multicast trees with bandwidth requirements for all the group members in the network. We first prove that the problem of finding feasible solutions to GMRP is NP-complete. Following that we propose a new heuristic algorithm for constructing feasible solutions for GMRP. Simulation results show that our proposed algorithm is able to achieve good performance in terms of its ability of finding feasible solutions whenever one exist.