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

• FUJII M.

  Kyushu Matsushita Electric Co., Ltd.

• FUNABIKI Nobuo

  Department of Communication Network Engineering, Faculty of Engineering, Okayama University

• YOKOHIRA Tokumi

  Department of Communication Network Engineering, Faculty of Engineering, Okayama University

• TAJIMA Shigeto

  Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

• TSUNEMURA Kazufumi

  Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

• HIGASHINO Teruo

  Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

抄録

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.

収録刊行物

• IEICE Journal

  IEICE Journal 85 (3), 730-, 2002

  一般社団法人電子情報通信学会

キーワード

• multicast routing
• mobile multicast
• communication network
• NP-complete
• approximate algorithm

詳細情報

• CRID: 1574231877208261248
• NII論文ID: 110003216809
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles