| 講演名 | 2010-03-05 故障時性能劣化が小さいリンク数最小ネットワーク設計法(ネットワーク管理/制御/設計) 片山 希, 藤村 武史, 巳波 弘佳, 上山 憲昭, 長谷川 治久, 吉野 秀明, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | インターネットをはじめ,通信ネットワークが社会において必要不可欠なインフラとなった現在,ネットワークには高い信頼性が求められている.しかし,ネットワークにおいて単一リンク故障による経路切断が発生した際,もとの経路に比べて代替経路の経路長が大幅に増加し,通信品質の大幅な劣化を引き起こす可能性がある.これまで,既設ネットワークへの最小限のリンク増設によって,この経路長増加率を与えられた定数以下に抑えるネットワーク設計法を提案し,その有効性を示した.しかし,その設計法そのままでは新規ネットワークを構築する際には適用できない.本稿では,経路長増加率・直径・次数を制約として満たしつつ,コストに対応するリンク数が最小であるような新規ネットワークの設計問題を扱う.この問題がNP完全であることを証明し,近似アルゴリズムを設計した.さらに,現実の様々なネットワークへ適用してアルゴリズムの有効性を評価した. |
| 抄録(英) | A telecommunication network should be reliable, since it is important as social infrastructure. But it is known that, in many real networks, there exists the risk that the quality of service drastically deteriorates when the length of paths increases by a link failure. To get rid of this risk, it is necessary to design a network that the maximum increasing rate of the length of all paths in a link failure is small. We proposed an approximation algorithm for a network design problem that constructs such a network by adding some links to a network in our previous paper. On the other hand, when we construct a network from scratch, we must consider not only the quality of the failure time but also that of the normal time. In this paper, we formalize this network design problem as the optimization problem that determines a graph with a constrained degree and diameter so that the maximum increasing rate of the lengths of all paths in an edge deletion is not more than a threshold. First, we prove that this problem is NP-complete. Next, we propose an approximation algorithm for this problem and evaluate its performance by applying the algorithm to some real ISP networks. As a result, the proposed algorithm shows the good performance. |
| キーワード(和) | 通信品質 / 経路長増加率 / 最適化問題 / NP完全性 / 近似アルゴリズム |
| キーワード(英) | quality of service / path length / optimization problem / NP-complete / approximation algorithm |
| 資料番号 | NS2009-228 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2010/2/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 故障時性能劣化が小さいリンク数最小ネットワーク設計法(ネットワーク管理/制御/設計) |
| サブタイトル（和） | |
| タイトル（英） | Design Method of Smallest Robust Networks against Performance Deterioration during Failures |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 通信品質 / quality of service |
| キーワード(2)（和/英） | 経路長増加率 / path length |
| キーワード(3)（和/英） | 最適化問題 / optimization problem |
| キーワード(4)（和/英） | NP完全性 / NP-complete |
| キーワード(5)（和/英） | 近似アルゴリズム / approximation algorithm |
| 第 1 著者 氏名（和/英） | 片山 希 / Nozomu KATAYAMA |
| 第 1 著者 所属（和/英） | 関西学院大学理工学部 Kwansei Gakuin University |
| 第 2 著者 氏名（和/英） | 藤村 武史 / Takeshi FUJIMURA |
| 第 2 著者 所属（和/英） | 関西学院大学理工学部 Kwansei Gakuin University |
| 第 3 著者 氏名（和/英） | 巳波 弘佳 / Hiroyoshi MIWA |
| 第 3 著者 所属（和/英） | 関西学院大学理工学部 Kwansei Gakuin University |
| 第 4 著者 氏名（和/英） | 上山 憲昭 / Noriaki KAMIYAMA |
| 第 4 著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 NTT Service Integration Laboratories |
| 第 5 著者 氏名（和/英） | 長谷川 治久 / Haruhisa HASEGAWA |
| 第 5 著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 NTT Service Integration Laboratories |
| 第 6 著者 氏名（和/英） | 吉野 秀明 / Hideaki YOSHINO |
| 第 6 著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 NTT Service Integration Laboratories |
| 発表年月日 | 2010-03-05 |
| 資料番号 | NS2009-228 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 448 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |