PNNI階層型ネットワークにおけるルート選択アルゴリズムの効率化

概要

論文の詳細を見る
インターネットやATMの私設ネットワークのように分散管理されたネットワークにおいては, 動的なルーティング方式が用いられる. ネットワークの状態は時事刻々と変化するため, 障害ルートの回避やQoSの補償のためには, ルート選択が行われる頻度は短いほうが有利である. しかし一方で, ルート選択の計算はスイッチやルータの処理に負荷を与えるため, できるだけ効率良く実行できることが望ましい. 従来, ルート選択のアルゴリズムには, 一般に, DikstraのSPFが用いられてきた. SPFの計算効率はその実装に依存し, 例えばグラフを連結行列で表現した場合はO (n^2) (nはノード数) であることが知られている. しかし, PNNI等の階層型ネットワークのトポロジでは, 階層内と階層間でその密度に濃淡ができることが予想される. これは, 従来のSPFの実装で想定されていた一様な密度のグラフトポロジとは異なる. 本稿では, このような観点から, 階層型のネットワークトポロジに摘要可能な新たなSPFの実装について考察した.
社団法人電子情報通信学会の論文
1998-01-23