JISE


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


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


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

  Retrieve PDF document (JISE_200503_02.pdf)