On Multicasting Steiner Trees for Delay and Delay Variation Constraints

Lecture Notes in Computer Science, vol. 4208, pp. 447-456, Sep. 2006

Moonseong Kim, Young-Cheol Bang, and Hyunseung Choo


The objective of multicasting is to find a tree that has a minimum total cost, which called theSteiner tree. Multicast routing algorithms should support the required QoS. There are two important Quality of Service (QoS) parameters that need to be guaranteed in order to support the real time and multimedia applications. Firstly, we consider the delay parameter where, the data sent from source need to reach destinations within a certain time limit (delay bound). Secondly, in addition to the delay constraint, we add the delay variation constraint. The delay variation constraint is a bound on the delay difference between any two destinations. Our research subject is Delay and delay Variation Bounded Steiner Tree (DVBST) problem. The problem has been proved to NP-complete. In this paper, we propose efficient algorithm for DVBST. Simulations demonstrate that our algorithm is better in terms of tree cost as compared to the existing algorithms.




View Full Text