A Proposal of Optimal Path Selection Algorithm for Static and Mobile Multicast Routing Problems

概要

論文の詳細を見る
In this paper, we present an approximation algorithm called OPSAM (Optimal Path Selection Algorithm for Multicast) for the static multicast routing problem and the newly defined mobile multicast routing problem. Given a graph with the cost and the delay associated to each edge, a data source, a destination set, and the delay time limit, the first problem requires finding a multicast tree such that the total edge cost is not only minimized, but also the delay of any path from source to a destination does not surpass its limit. OPSAM first extracts plural path candidates for each destination to satisfy the delay constraint. Then, it repeatedly selects better paths among candidates so as to find a lowcost tree within a short computation time. The performance of OPSAM is verified through simulations in the random graph model and the Tiers model, where OPSAM is better than the best existing algorithm BSMA, especially for Tiers model instances. The second problem requires finding a sequence of multicast trees which should be modified to follow changes of mobile user locations, such that the sum of the total edge costs and the difference between two consecutive trees is minimized. The simulation results show the performance of OPSAM is better than BSMA.
社団法人電子情報通信学会の論文
2002-03-01