In this paper, we present a heuristic algorithm called OPSAM (Optimal Path Selection Algorithm for Multicast) for the static multicast rooting problem. Given a directed connected graph with two weights associated to each edge, representing the cost and the delay, a source sending out data, and a set of destinations receiving data, this problem requires to provide a multicast tree such that the total cost of edges in the tree is not only minimized, but also every path delay from the source to a destination is less than its upper limit. OPSAM first extracts plural path candidates to each destination that satisfy the delay constraint. Then, it iteratively selects better paths among them so that it can find a low-cost tree within short time. The performance of OPSAM is verified through simulations in two types of network models, where especially, OPSAM shows the high performance for Tiers model instances, which are close to real networks.
展开▼
