| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-03-09 14:10 リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム ○今川廣二・藤村武史・巳波弘佳（関西学院大）  NS2011-251 |
|
| 抄録 | （和） | インターネットが重要な社会基盤となるにともない，その信頼性，品質への要求は高くなっている．ネットワーク遅延はそのようなネットワーク品質のひとつであり，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 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2011-251 |
|
| 研究会情報 | |
| 研究会 | 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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-03-09 14:10:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NS |
| 資料番号 | NS2011-251 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.468 |
| ページ範囲 | pp.403-408 |
| ページ数 | 6 |
| 発行日 | 2012-03-01 (NS) |
[研究会発表申込システムのトップページに戻る]