文献

J-GLOBAL ID：201702216860979783   整理番号：17A0540540

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

Method for Finding Server Placement and Protected Links to Keep Connectivity to Servers

著者 (2件)： 入江大史 (関西学院大 大学院理工学研究科) ,  巳波弘佳 (関西学院大 大学院理工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 484(NS2016 157-253)  ページ： 145-150  発行年： 2017年02月23日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *ネットワークアーキテクチャ ,  *通信網 ,  *連結性 ,  *計算機システム ,  *配置 ,  *保護 ,  *リンク ,  *決定 ,  通信故障 ,  インターネット ,  ゲートウェイ ,  情報配布 ,  コンピュータ ,  設計 ,  NP困難 ,  アルゴリズム ,  ネットワーク構造
準シソーラス用語： *ノード【通信】 ,  *サーバ【計算機】 ,  *通信リンク ,  リンク故障 ,  コンテンツ配信 ,  ミラーサーバ ,  ネットワーク設計 ,  多項式時間アルゴリズム ,  ネットワークトポロジー

分類 (2件)： 通信網  (ND07030A) ,  その他の情報処理  (JE15050M)

引用文献 (18件)：

• Akamai Technologies, http://www.akamai.com
• Edge Cast Networks, httmp://www.edgecast.com/
• S. L. Hamiki, ′′Optimum distribution of switching centers in a communication network and some related graph teoretic problems,′′ Operations Research, Vol. 13, pp. 268-475, 1965.
• M S Daskin, ′′A new approach to solving the vertex p-center problem to optimality: Algorithm and computational results,′′ Communications of the Operations Research Society of Japan, 45:428-436, 2000.
• M. Charikar, S. Guha, ′′Improved Combinational Algorithms for Facility Location Problems,′′ SIAM J. Comput., Vol. 34, pp. 803-824, 2004.

タイトルに関連する用語 (4件)： ノード ,  連結性 ,  サーバ ,  リンク