| 講演名 | 2014-03-07 リンク故障時においてもサーバへの可到達性を保障し距離増大を抑制するサーバ配置法(リソース配置) 前田 奈緒, 巳波 弘佳, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年,大容量コンテンツの利用増加,クラウドサービスの商用化に伴い,ネットワークトラフィックやコンテンツ配信サーバ、データセンタへの負荷が増大している.これに対処するための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 fixed, 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 |
| 資料番号 | NS2013-243 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2014/2/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | リンク故障時においてもサーバへの可到達性を保障し距離増大を抑制するサーバ配置法(リソース配置) |
| サブタイトル（和） | |
| タイトル（英） | Server Location Method for Keeping Shorter Distance from Clients to Servers during Failures |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ネットワーク / Network |
| キーワード(2)（和/英） | グラフ理論 / Graph theory |
| キーワード(3)（和/英） | 計算時間量 / Computational complexity |
| キーワード(4)（和/英） | リンク故障 / Link failures |
| キーワード(5)（和/英） | サーバ配置 / Server allocation |
| キーワード(6)（和/英） | NP困難 / NP-hard |
| キーワード(7)（和/英） | 多項式時間アルゴリズム / Polynomial-time algorithm |
| キーワード(8)（和/英） | 近似アルゴリズム / Approximate algorithm |
| 第 1 著者 氏名（和/英） | 前田 奈緒 / Nao MAEDA |
| 第 1 著者 所属（和/英） | 関西学院大学大学院理工学研究科 Graduate School of Science and Technology, Kwansei Gakuin University |
| 第 2 著者 氏名（和/英） | 巳波 弘佳 / Hiroyoshi MIWA |
| 第 2 著者 所属（和/英） | 関西学院大学大学院理工学研究科 Graduate School of Science and Technology, Kwansei Gakuin University |
| 発表年月日 | 2014-03-07 |
| 資料番号 | NS2013-243 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 472 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |