故障時のネットワーク負荷集中を回避する高信頼リ ンク決定法に関する研究
著者 野口 烈
URL http://hdl.handle.net/10236/9714
2011
年度 修士論文要旨
故障時のネットワーク負荷集中を回避する 高信頼リンク決定法に関する研究
関西学院大学大学院理工学研究科 情報科学専攻 巳波研究室 野口 烈
インターネットが普及して重要な社会基盤となるにともない，故障の影響を最小限に抑え た信頼性の高いネットワークの構築・運用が，サービス提供者にとって重要な課題となって いる．インターネットにおける経路としては通常最短経路が選ばれるが，リンクに割り当て られたメトリックにより自動的に経路が決定されるため，リンク故障によって経路が変更さ れた際，特定のリンクに経路が集中して輻輳が発生する可能性がある．すべてのネットワー ク構成要素の信頼性を十分高いものにするためには膨大な設備コストがかかるため，信頼性 が十分高いリンクの数を最小限に抑えることにより，それら以外のリンクがたとえ故障して 経路が変更されたとしても，各リンクに経路が集中することを回避できることが望ましい．
本研究では，この問題を離散最適化問題として定式化し，
NP
困難性を証明した．さらに，単一リンク故障を想定した場合に対して，多項式時間アルゴリズムを設計した．
