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 Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation
Chor Ping LOW Ning WANG
IEICE TRANSACTIONS on Communications
Publication Date: 2004/01/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
multicast routing, heuristic algorithm, lower bound techniques, NP-completeness,
Full Text: PDF>>
Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belongs to the same group. The group multicast routing problem (GMRP) is that of finding a set of multicast trees with bandwidth requirements, each rooted at a member of the group, for multicasting messages to other members of the group. An optimal solution to GMRP is a set of trees, one for each member of the group, that incurs the least overall cost. This problem is known to be NP-complete and hence heuristic algorithms are likely to be the only viable approach for computing near optimal solutions in practice. In this paper, we derive a lower bound on the cost of an optimal solution to GMRP by using Lagrangean Relaxation and Subgradient Optimization. This lower bound is used to evaluate the two existing heuristic algorithms in terms of their ability to find close-to-optimal solutions.