Abstract
Many real-time applications, such as video conferencing, require the transmission of messages from a sender to multiple receivers subject to Quality-of-Service (QoS) delivery constraints (e.g. bounded delay). This requires the underlying multicast protocol to find a QoS-constrained minimum-cost communication path (tree). However, finding such a tree is known to be computationally expensive. In this paper, we present a fast heuristic, called QDMR, for generating delay-constrained low-cost multicast routing trees. A salient feature of QDMR is that it dynamically adjusts its low-cost tree construction policy based on how far the current on-tree node is from violating the QoS delay bound. This QoS dependent (adaptive) tree construction, together with the capability to merge least-delay paths into the low-cost tree in case of stringent delay requirements, lead to the following properties: (1) QDMR guarantees to find a feasible multicast tree if such tree exists; (2) this delay-bounded multicast tree is very rapidly generated; and (3) the tree has low cost. Through analysis and extensive simulations, we confirm the premise of QDMR by comparing it to many existing multicast algorithms.