MULTICAST ROUTING WITH END-TO-END DELAY AND DELAY VARIATION CONSTRAINTS

We study the problem of constructing multicast trees to meet the quali ty of service requirements of real-time interactive applications opera ting in high-speed packet-switched environments. In particular, we ass ume that multicast communication depends on: 1) bounded delay along th e paths from the source to each destination and 2) bounded variation a mong the delays along these paths, We first establish that the problem of determining such a constrained tree is NP-complete. We then presen t 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 i n 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.