
For FullText 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
Publication
IEICE TRANSACTIONS on Communications
Vol.E87B
No.1
pp.124131 Publication Date: 2004/01/01
Online ISSN:
DOI:
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Network Keyword: multicast routing, heuristic algorithm, lower bound techniques, NPcompleteness,
Full Text: PDF(946.2KB)>>
Summary:
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 NPcomplete 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 closetooptimal solutions.

