On Finding Feasible Solutions for the Group Multicast Routing Problem

Chor Ping LOW  Ning WANG  

IEICE TRANSACTIONS on Communications   Vol.E85-B   No.1   pp.268-277
Publication Date: 2002/01/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
group multicast routing,  heuristic algorithms,  bandwidth constraint,  NP-complete,  

Full Text: PDF(1.3MB)>>
Buy this Article

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.