ネットワーク負荷を最小とする情報配信サーバ配置問題の考察： サーバ分割法SPTとサ一バ統合法MRG

摘要

ブロードバンド化により音楽，動画等のコンテンツ配信サービスが盛んとなり，情報配信ネットワークCDN（Contents Delivery Network）が重要となって来た，そこでは，配信サーバをどこに配置すればCDN全体の効率が向上するかというサーバ最適配置問題が課題である．本報告では情報配信サーバに情報配信が要求されたとき，ネットワーク負荷最小とする配信サーバ最適配置問題を考察し，二種類の配置アルゴリズム，サーバ分割法SPTおよびサーバ統合法MRGを提案したサーバ分割法SPTはネットワーク上に存在する全てのユーザをサーバ配置数に等しい数の集合に直和分解することにより，近似的にサーバ配置を求める手法である．サーバ統合法MRGでは，まず全てのユーザ上にサーバを配置し，次にサーバ個数を効率的に減少させる．このとき互いに近傍にある複数のサーバをネットワーク負荷の増加が最小になるように1つのサーバにまとめることによって，近似的にサーバ配置を求める手法である．解の精度や計算量などを各手法で求め，ア／レゴリズムの性能を比較，評価した．