Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 21 No. 3, pp. 495-527 (May 2005)

Algorithms for Static and Dynamic Group Multicast
Routing Under Bandwidth Constraints

Kun-Cheng Tsai and Chyouhwa Chen
Department of Electronic Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

Multicast routing allows network sources to use network resources efficiently by sending only a single copy of data to all group members. In the group multicast routing problem (GMRP), every member of a group is also a source node. The routing algorithm must construct a source-based routing tree for each member of the group which spans all other member nodes without exceeding the capacities of the traversed links. Previous work adopted the direct, intuitive approach by first creating an independent source- based multicast tree for each member node, and then iteratively locating network links whose capacity constraints are violated and eliminating the violation by rerouting the trees. In this paper, we propose a more systematic approach to solve the static GMRP based on the idea of critical pairs. For the dynamic GMRP, we propose the DGMCP algorithm. Through extensive experiments, our proposals are shown to outperform previous algorithms in constructing group multicast trees with low costs and high success ratios.

Keywords: group multicast routing, Steiner tree, dynamic group multicast routing, QoS routing, constrained Steiner tree

Full Text () Retrieve PDF document (200505_02.pdf)

Received June 3, 2003; revised February 24 & June 23, 2004; accepted August 23, 2004.
Communicated by Chu-Sing Yang.