リンク故障時においてもサーバへの可到達性を保証し距離増大を抑制するサーバ配置法における多項式時間アルゴリズム

摘要

近年の大容量コンテンツの利用増加やクラウドサービスの商用化にともなって，ネットワークトラフィック，コンテンツ配信サーバ、データセンタへの負荷が増大している．これに対処する手段の一つとして，同一コンテンツを保持する複数のミラーサーバをネットワーク上に分散配置し，ユーザからのアクセスを適切なサーバに誘導することにより，サーバの負荷分散を図るというものがある．そこでは，幅榛抑制と遅延抑制の観点から，リンク故障時に代替経路長が増大することも避けなければならないため，性能を左右するサーバ配置設計が重要である．インターネットにおける通信経路は，ルーティングプロトコルによって一般に最短経路が選ばれるため，本稿では，最も近いサーバまで最短経路でルーティングされる制御が行われている状況の下で，リンク故障時にも，すべてのユーザが複数個のサーバに到達可能であり，かつ代替経路の延長ホップ数が一定以下となるようなサーバ配置を決定する問題を扱う．一般にNP困難であるこの問題において，単一リンク故障かつ延長可能ホップ数をノード数に限定した場合に対する多項式時間アルゴリズムを設計し，現実ネットワークにおける配置サーバ数を求めた．