著者
川原 洋人
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)
巻号頁・発行日
vol.78, no.7, pp.573-587, 1995-07-25
被引用文献数
2

コンピュータネットワークのルーティング方式の研究においては適応型ルーティングに比べ,固定ルーティング方式の研究は少ないが,実際のネットワークではその方法の簡易性から,固定ルーティングを用いているものが少なくない.固定ルーティングは,ノードやリンクの障害により,ルートが不通となったとき,他のルートに切り換える方法に問題がある.すなわち,多くの場合,固定ルーティングにおいては,パケットを送出するリンク(出方路と呼ぶ)が障害であることを検出したノードが,あらかじめ定められた優先順に従って,予備の出方路に切り換えることにより,ルートの切換えを行うが,ピンポン現象や,ループ現象などの誤ルーティングを起こすことがあり,完全ではない.本論文では,この問題を解決するために,ノード同士が情報を交換し,そのような現象の起こらないルート切換えを実現する分散アルゴリズムを与える.次に,障害が回復したときに,元のルートへ復元するアルゴリズムを与える.最後に,それらのアルゴリズムに基づく一連の操作が,複数同時に進行しても,誤ルーティングが起こらないことの証明を与える.