Distributed delay constrained multicast path setup algorithm forhigh speed networks

摘要

The problem of finding an optimal multicast tree in a point topoint network translates to the Steiner problem in graphs. Since theSteiner problem is NP complete, heuristic approaches are required forpath setup. The problem takes a new dimension in wide area networks,where centralized algorithms are not feasible, and distributed schemesare needed. It is also desirable that node participation for path setupis limited to nodes directly involved in the multicast. An additionalrequirement that comes from the nature of the applications such as videoconferencing that use the multicast support from the network is that ofbounded end to end delays along any path from the source to eachdestination in the multicast tree. We present a heuristic algorithm thatensures delay bounds, is distributed and produces trees that are onlyslightly more expensive than those produced by centralized algorithms.Further we examine the degradation in performance in case of changingdelays along network links (where QoS guarantees on delay are notavailable), and propose ways of making the tree adaptive to thesechanges. This dynamic routing approach minimizes resource reservationdemands and also makes changing multicast groups permissible