サーバへの可到達性を保障する高信頼リンク決定法(NWシステム(信頼性))

概要

論文の詳細を見る
インターネットが普及して重要な社会基盤となるにともない,故障の影響を最小限に抑えた信頼性の高いネットワークの構築・運用が,サービス提供者にとって重要な課題となっている.特にコンテンツ配信サービスにおいては,サーバと通信不可能となることを避けるために,サーバのみならずネットワークにも高い信頼性が必要である.しかし,すべてのネットワーク構成要素の信頼性を十分高いものにするためには膨大なコストがかかる.したがって,信頼性が十分高いリンク(保護リンク)の数を最小限に抑えることにより,他のリンクがたとえ故障したとしても通信が継続できるようにすることが望ましい.本稿では,この問題を離散最適化問題として定式化し,NP困難性を証明した.さらに,単一リンク故障を想定した場合に対して,多項式時間アルゴリズムを設計した.故障の約70%が単一リンク故障であることから,このアルゴリズムは理論的な結果としてだけでなく,実用性もあるアルゴリズムである.さらに,様々なネットワークトポロジに対して本アルゴリズムを適用して最適な保護リンク集合を決定した.
2011-02-24