Fallback+:複数のQoS要求を満たす経路選択アルゴリズム

概要

論文の詳細を見る
マルチサービスネットワークにおいて、帯域や遅延など複数のQoS要求を満たす経路選択アルゴリズムが必要となる。これは複数制約下での最短路問題として定式化できるが、NP完全であることが知られている。それゆえ多くの発見的アルゴリズムが提案されたが、その中で代表的なものにFallbackアルゴリズムがある。これは、個々のQoSを目的関数とする最短路問題を遂次的に解き、解が全てのQoS要求を満たせば、経路として採用するというものである。本稿では、このFallbackアルゴリズムを拡張し、QoS要求を満たしつつ、ネットワーク側の視点から最も低コストな経路を選択する発見的アルゴリズムFallback+を提案する。これは、コストあるいは個々のQoSに対する最短経路を得る過程で、暫定解として生成される経路を廃棄せず、Fallbackする前に別候補として検討するものである。Fallback+の最大計算量はFallbackと等しいが、Fallback+はより高い確率でQoS要求を満たす経路を選択可能である。更に、シミュレーションの結果から、Fallback+の実行速度は平均的には単純なFallbackより10%以上高速であり、また、最適な経路を選択する確率も高いことを示した。
社団法人電子情報通信学会の論文
1998-05-28