On finding feasible solutions for the delay constrained group multicast routing problem

Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. In this paper, we study the problem of finding feasible solutions for the delay constrained group multicast routing problem (DCGMRP)...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2002-05, Vol.51 (5), p.581-588
Main Authors: Low, Chor Ping, Song, Xueyan
Format: Article
Language:English
Subjects:
Algorithms
Computer simulation
Constraints
Delay
Mathematical models
Messages
Multicast
Multicasting
Routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. In this paper, we study the problem of finding feasible solutions for the delay constrained group multicast routing problem (DCGMRP). The routing problem in this case involves the construction of a set of delay bounded multicast trees with bandwidth requirements, one for each member of the group, for multicasting messages to other members of the group. We first show that the problem is NP-complete. Next, we propose a heuristic algorithm to find feasible solutions for this problem. Simulation results show that our proposed algorithm is able to achieve a high probability of finding feasible solutions for DCGMRP, whenever one exists.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2002.1004596