Multicast routing with end-to-end delay and delay variation constraints

We study the problem of constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: 1) bounded delay along the paths from the source to each destination and 2) bounded variation among the delays along these paths, We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation, The heuristic achieves its best performance under conditions typical of multicast scenarios in high-speed networks, We also show that it is possible to dynamically reorganize the initial tree in response to changes In the destination set, in a way that is minimally disruptive to the multicast session.