A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees

With the proliferation of multimedia group applications, the construction o f multicast trees satisfying quality of service (QoS) requirements is becom ing a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support d ynamic multicast sessions wherein the membership of the multicast group cha nges with time. In this paper, we propose and evaluate an algorithm called CRCDM (controlled rearrangement for constrained dynamic multicasting) for o n-line update of multicast trees to adjust to changes in group membership, The CRCDM algorithm is based on a concept called quality factor (QF) that r epresents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree d rops below a threshold, a rearrangement technique is used to suitably modif y the tree. Our algorithm aims to satisfy the delay constraints of all curr ent group members, at the same time minimizing the cost of the constructed tree, We compare the performance of our algorithm, by simulation, with that of an off-line Steiner heuristic; with ARIES [2], a recently published alg orithm for on-line update of unconstrained trees; and with the algorithm pr oposed in [10] for on-line update of delay-constrained trees. The simulatio n results indicate that our algorithm provides excellent cost-competitivene ss that is better than that provided by the algorithm described in [10], mi nimizes changes in the multicast tree after each update, and performs favor ably even when compared with the unconstrained ARIES heuristic.