著者

細谷 好志 若林 真一 小出 哲士 吉田 典可

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.89-90, 1993-09-27

---

ネットワーク管理における重要な問題の1つに最短経路木更新問題がある.特に各通信リンクの負荷晴報をコストと考えた場合に最短経路木更新問題を解くことは,メッセージを送る経路を決定する際に混雑した経路を避けるという意味で有用である.オンラインシステムではネットワークのトポロジが頻繁に変化するため,その都度最短経跨を更新する必要がある.動的ネットワークにおける最短経路木更新問題はこれまでにも多くの研究がなされてきた.特に,アルゴリズムの実行中でもトポロジの変化を許す場合,いつかはネットワークのトポロジ変化が安定するという仮定のもとでいくつかのアルゴリズムが提案されている.一般にメッセージ複雑度と空間計算量はトレードオフの関係にあり,さらにメッセージに持たせる情報を少なくすれば,一時的に経路木中にサイクルが生じるなどして各プロセスが正しい情報を保持するまでに時間がかかったり,ネットワークが非連結になった場合に正しい更新が保証されない.文献では,静的ネットワークのアルゴリズムを動的ネットワークに適用する手法として,トポロジの変化ごとにアルゴリズムをリセットして再起動させているが,その手法だとそれまでに集められた情報が無駄になってしまう.本稿では,少ない局所情報及びメッセージ情報によって,分散最短経路木更新問題を効率良く解くイベントドリプンアルゴリズムを提案する.