パスサーチ時間短縮を考慮したマルチポイントパスサーチアルゴリズムの検討

概要

論文の詳細を見る
音声、画像、データを統合的に扱えるATM通信システムでは、電話等の1対1(SP:Single Point)通信だけでなく、VOD(Video On Demand)に代表される1対多(MP:Multi Point)通信が重要である。MP通信においては効率的なMPパスのサーチが課題である。MPパスサーチはNP完全問題であり、従来、最小コストスパニングツリーを使用するアルゴリズム(MST)等が考えられているが、これらの計算時間はネットワークのノード数に大きく依存するため、ネットワークが大規模になると計算時間が増加する問題がある。ところが、実際は、ユーザからパス設定要求を受信してからMPパスサーチ結果を出力するまでの応答時間が呼制御では重要であるため、この応答時間がネットワーク規模非依存であるか、小さいことが必要となる。本報告では、応答時間短縮に着目したアルゴリズムの評価法(NRC-RC評価法)について述べる。さらに、NRC-RC評価法により応答時間が短縮可能なアルゴリズムを例として示すとともにその効果を示す。
1995-03-27