On QoS multicast routing algorithms using k-minimum Steiner trees

Moonseong Kim, Hyunseung Choo, Matt W. Mutka, Hyung-Jin Lim, and Kwangjin Park

Information Sciences, vol.238, pp. 190-204, Jul. 2013 (SCI, IF: 3.893)


In this paper, we study how to obtain Steiner trees appropriately for efficient multicast routing. We first introduce a scheme for generating a new weighted multicast parameter by efficiently combining two independent measures: cost and delay. We call our proposal the Weighted Parameter for Multicast Trees (WPMT) algorithm. The WPMT can be adjusted by the weight ω ∈ [0, 1]. For instance, if ω approaches 0, then the delay of the multicast tree may be relatively lower than the delay of other trees that are obtained asω approaches 1. Otherwise, as the weight approaches 1 then the cost of the obtained tree may be relatively lower compared with other trees. A case study shows how to find an appropriate Steiner tree for each ω. The simulation results show that the use of the proposed WPMT produces results similar to the k-minimum Steiner tree algorithm. The WPMT can be applied to several existing multicast problems as we describe. We also propose several multicast algorithms using the WPMT in order to solve well-known multicast problems, and compare the proposed algorithms-based the WPMT with representative algorithms for the well-known problems.



Multicast routing, Quality of Service (QoS), Steiner tree, Minimum Steine, tree algorithm, Delay constraint problem, Delay variation constraint problem


View Full Text