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

With the proliferation of multimedia group applications, the construction of multicast trees satisfying quality of service (QoS) requirements is becoming a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support dynamic multicast sessions wherein the membership of the multicast group changes with time. In this paper, we propose and evaluate an algorithm called CRCDM (controlled rearrangement for constrained dynamic multicasting) for on-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 represents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree drops below a threshold, a rearrangement technique is used to suitably modify the tree. Our algorithm aims to satisfy the delay constraints of all current 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, a previously published algorithm for on-line update of unconstrained trees; and with the algorithm proposed by Hong, Lee and Park (see Proc. IEEE INFOCOM, p.1433-40, 1998) for on-line update of delay-constrained trees. The simulation results indicate that our algorithm provides excellent cost-competitiveness that is better than that provided by the algorithm described by Hong et al., minimizes changes in the multicast tree after each update, and performs favorably even when compared with the unconstrained ARIES heuristic