故障時においてもサーバへの可到達性と距離を保障する高信頼リンク決定法

摘要

インターネットが普及して重要な社会基盤となるにともない，故障の影響を最小限に抑えた信頼性の高いネットワークの構築·運用が，サービス提供者にとって重要な課題となっている．特にコンテンツ配信サービスにおいては，サービスを受けるノードと通信していたサーバとの通信経路の切断によってサービスが途絶することを回避しなければならない．コンテンツ配信には，同一コンテンツを持つ複数のミラーサーバが用いられることが多いが，故障時においても少なくとも一つのサーバへ通信経路が存在するような信頼性がネットワークには必要である．さらに，故障時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまうことも，通信品質劣化と輻輳可能性の抑制の観点から避けなければならない．しかし，このような高い信頼性を持つネットワークの構築には膨大なコストがかかるため，信頼性が十分に高いリンク（保護リンク）の数を最小限に抑えることにより，保護リンク以外のリンクがたとえ故障したとしても一定距離以内にあるサーバの数を維持して通信の継続を図るネットワーク設計が有効であると考えられる．本稿では，このネットワーク設計問題を定式化し，まずNP困難性を証明した．さらに，単一リンク故障を想定した場合に対して，多項式時間アルゴリズムを設計した．