電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-03-09 14:10
リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム
今川廣二藤村武史巳波弘佳関西学院大
技報オンラインサービス実施中
抄録 (和) インターネットが重要な社会基盤となるにともない,その信頼性,品質への要求は高くなっている.ネットワーク遅延はそのようなネットワーク品質のひとつであり,2 ノード間の遅延はそれらの距離と相関があるため,ネットワークの直径,つまり全ての2 ノード間の距離の最大値は小さいことが望ましい.さらに,ネットワークの故障に対して遅延を小さく保つ必要がある.そのため,故障によって著しい品質劣化を引き起こすような致命的なリンクは,IP 層以上のネットワークで故障を感知できないように,迅速に修復を行うことで保護しなければならない.そのような保護されるリンクの数は設備と運用にかかるコストを抑えるためにできる限り少ないことが望ましい.そのため,保護されていないリンクの故障に対してネットワークの直径が一定の数値より大きくならないような最小数の保護すべきリンクを求めることが重要である.
本稿では,この問題におけるこれらの未解決であった問題を解決した.まず,この問題はk = 2 に限定してもNP 困難であることを証明した.さらに,k が2 以上の定数である場合において,定数の近似度をもつ多項式時間近似アルゴリズムを与えた.これらの結果はこの問題の計算複雑性を理論的に明
らかにし,実用的なネットワーク設計アルゴリズムを与えた. 
(英) The high reliability and performance are needed as the Internet becomes an important social infrastructure. Network delay is one of measure of the performance of network. As the delay between two nodes correlates roughly with the distance between them, the diameter of the network which is the maximum distance of all two nodes must be small. In addition, it is necessary to keep the small network delay against network failures. Therefore, the critical links whose failures significantly degrade the performance must be protected by rapid recovery so that the failures cannot be detected over the IP layer. The number of these protected links must be small to restrict the investment cost of facilities and the operational cost for Internet service providers. Consequently, it is important to find the smallest number of the links to be protected so that the diameter of the network which non-protected links are failured is not more than a given integer.
In this paper, we solve these unsolved issues of this problem. First, we prove that the problem is NP-hard even if k=2. Second, we present approximation algorithms with the approximation ratio of a fixed constant for the NP-hard cases. These results make clear the computational complexity of this problem theoretically and gives an useful network design algorithm also from the practical viewpoints.
キーワード (和) リンク保護 / ネットワーク設計 / 直径 / 最適化 / / / /  
(英) link protection / network design / diameter / optimization / / / /  
文献情報 信学技報, vol. 111, no. 468, NS2011-251, pp. 403-408, 2012年3月.
資料番号 NS2011-251 
発行日 2012-03-01 (NS) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 NS IN  
開催期間 2012-03-08 - 2012-03-09 
開催地(和) 宮崎シーガイア 
開催地(英) Miyazaki Seagia 
テーマ(和) 一般 
テーマ(英) General 
講演論文情報の詳細
申込み研究会 NS 
会議コード 2012-03-NS-IN 
本文の言語 日本語 
タイトル(和) リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム 
サブタイトル(和)  
タイトル(英) Approximation Algorithms for Finding Protected Links to Keep Small Diameter during Link Failures 
サブタイトル(英)  
キーワード(1)(和/英) リンク保護 / link protection  
キーワード(2)(和/英) ネットワーク設計 / network design  
キーワード(3)(和/英) 直径 / diameter  
キーワード(4)(和/英) 最適化 / optimization  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 今川 廣二 / Koji Imagawa / イマガワ コウジ
第1著者 所属(和/英) 関西学院大学大学院 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第2著者 氏名(和/英/ヨミ) 藤村 武史 / Takeshi Fujimura / フジムラ タケシ
第2著者 所属(和/英) 関西学院大学大学院 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第3著者 氏名(和/英/ヨミ) 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ
第3著者 所属(和/英) 関西学院大学大学院 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-03-09 14:10:00 
発表時間 20 
申込先研究会 NS 
資料番号 IEICE-NS2011-251 
巻番号(vol) IEICE-111 
号番号(no) no.468 
ページ範囲 pp.403-408 
ページ数 IEICE-6 
発行日 IEICE-NS-2012-03-01 


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

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


IEICE / 電子情報通信学会