お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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

研究会情報
研究会 NS IN  
開催期間 2014-03-06 - 2014-03-07 
開催地(和) 宮崎シーガイア 
開催地(英) Miyazaki Seagia 
テーマ(和) 一般 
テーマ(英) General 
講演論文情報の詳細
申込み研究会 NS 
会議コード 2014-03-NS-IN 
本文の言語 日本語 
タイトル(和) リンク故障時においてもサーバへの可到達性を保障し距離増大を抑制するサーバ配置法 
サブタイトル(和)  
タイトル(英) Sever 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著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第2著者 氏名(和/英/ヨミ) 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ
第2著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2014-03-07 08:50:00 
発表時間 20 
申込先研究会 NS 
資料番号 IEICE-NS2013-243 
巻番号(vol) IEICE-113 
号番号(no) no.472 
ページ範囲 pp.385-390 
ページ数 IEICE-6 
発行日 IEICE-NS-2014-02-27 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会