On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation

Chor Ping LOW; Ning WANG

On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation

Chor Ping LOW, Ning WANG

Full Text Views

0

Share
Cite this

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 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.

Publication: IEICE TRANSACTIONS on Communications Vol.E87-B No.1 pp.124-131

Publication Date: 2004/01/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Network

Cite this

Copy

Chor Ping LOW, Ning WANG, "On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation" in IEICE TRANSACTIONS on Communications, vol. E87-B, no. 1, pp. 124-131, January 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/communications/10.1587/e87-b_1_124/_p

Copy

@ARTICLE{e87-b_1_124,
author={Chor Ping LOW, Ning WANG, },
journal={IEICE TRANSACTIONS on Communications},
title={On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation},
year={2004},
volume={E87-B},
number={1},
pages={124-131},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation
T2 - IEICE TRANSACTIONS on Communications
SP - 124
EP - 131
AU - Chor Ping LOW
AU - Ning WANG
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E87-B
IS - 1
JA - IEICE TRANSACTIONS on Communications
Y1 - January 2004
AB - 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.
ER -