講演抄録/キーワード |
講演名 |
2014-03-07 08:50
リンク故障時においてもサーバへの可到達性を保障し距離増大を抑制するサーバ配置法 ○前田奈緒・巳波弘佳(関西学院大) NS2013-243 |
抄録 |
(和) |
近年,大容量コンテンツの利用増加,クラウドサービスの商用化に伴い,ネットワークトラフィックやコンテンツ配信サーバ、データセンタへの負荷が増大している.これに対処するための1 つの手段として,同一コンテンツを保持する複数のミラーサーバをネットワーク上に分散配置し,ユーザからのアクセスを適切なサーバに誘導することにより,サーバの負荷分散を図るというものがある.また,輻輳抑制と遅延抑制の観点から,リンク故障時に代替経路長が増大することも避けなければならないため,性能を左右するサーバ配置設計が重要となる.インターネットにおける通信経路は,ルーティングプロトコルによって一般に最短経路が選ばれるため,本稿では,最も近いサーバまで最短経路でルーティングされる制御が行われている状況の下で,リンク故障時にも,すべてのユーザが複数個のサーバに到達可能であり,代替経路の延長ホップ数が一定以下となるようなサーバ配置を決定する問題を扱う.まず,このサーバ配置設計問題を定式化し,この問題のNP 困難性を証明した.さらに,単一リンク故障かつ延長可能ホップ数をノード数に限定した場合に対する多項式時間アルゴリズムを設計し,現実ネットワークにおける配置サー
バ数を求めた.また,リンク故障を定数,到達可能サーバ数を1 とした場合に対する近似アルゴリズムを設計し,実ネットワークにおいて近似比の評価を行った. |
(英) |
Recently, large contents in the Internet have increased loads of contents servers, networks and data centers which may degrade the quality of service. To overcome this problem, some mirror servers providing the same
contents are located on a network and a request is navigated to one of the mirror servers. Moreover, the network should have a communication to one of the servers and the hop length of a path from a user to a server should
be short even during link failure. As it affects the performance, the location of the mirror servers is important. In this paper, we address the server location problem, which determines the location of the servers satisfying the following the constraint: any users can access servers within a small hop count even if some links fails. First, we formulate this problem and prove that it is NP-hard. Second, we present a polynomial-time algorithm to solve this problem when the number of simultaneously failed links is restricted to one and evaluate the performance of actual ISP network topologies by the algorithm from the viewpoint of the number of servers. Furthermore, we also present an approximation algorithm to solve this problem when the number of servers to be accessed is restricted to one and the number of simultaneously failed links is xed, and evaluate the performance by using some actual network topologies. |
キーワード |
(和) |
ネットワーク / グラフ理論 / 計算時間量 / リンク故障 / サーバ配置 / NP 困難 / 多項式時間アルゴリズム / 近似アルゴリズム |
(英) |
Network / Graph theory / Computational complexity / Link failures / Server allocation / NP-hard / Polynomial-time algorithm / Approximate algorithm |
文献情報 |
信学技報, vol. 113, no. 472, NS2013-243, pp. 385-390, 2014年3月. |
資料番号 |
NS2013-243 |
発行日 |
2014-02-27 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2013-243 |