重要ノードとの連結性を維持するためのサーバ配置と保護リンク決定法

摘要

通信ネットワークにおいて通信が断絶する原因のーつとして，リンク故障が挙げられる．リンク故障が発生した場合，一般に複数の連結成分に分断されうるが，インターネットへのゲートウェイやコンテンツを配信するサーバなどの重要なノードを含まない連結成分が生じる．この場合，コンテンツ配信サービスやネットワークを利用できなくなる危険性がある．これを回避するために，2つの方法を考える．1つ目はサーバ配置問題に基づく方法である．ミラーサーバの配置はコンテンツ配信サービスの性能に影響を与えるため，適切な配置が求められる．2つ目はリンク保護に基づく方法である．下位レイヤにおいて高速なバックアップ機構を整備してリンクを頑健化することが有効であるが，すべてのリンクの保護には膨大なコストを要する．したがって，これらを組み合わせ，コスト制約のもとで，いかなる非保護のリンクが故障しネットワークが分断されても，すべての連結成分がサーバとの連結性を保つ，サーバ配置と最小数の保護リンクの決定が必要である．本稿では，このネットワーク設計を決定問題として定式化し，そのNP困難性を証明し，同時故障辺数を1に制限した時の多項式時間アルゴリズムを提案する．さらに，現実のネットワークトポロジを用いて，サーバ数と最小の保護リンク数の関係性を評価することで，アルゴリズムの有用性を示す．