| 講演名 | 2009-03-03 故障時における性能劣化を抑制するネットワーク設計法(ルーティング,ネットワーク設計) 片山 希, 藤村 武史, 巳波 弘佳, 上山 憲昭, 長谷川 治久, 吉野 秀明, |
|---|---|
| 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. Such a network must be constructed by adding some links to a network, because it is impossible to reconstruct a network which is in operation. In this paper, we formalize this network design problem as the optimization problem that determines the edges added to a graph 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 / backbone network / optimization problem / NP-complete / approximation algorithm |
| 資料番号 | NS2008-164 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2009/2/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 故障時における性能劣化を抑制するネットワーク設計法(ルーティング,ネットワーク設計) |
| サブタイトル（和） | |
| タイトル（英） | A Design Method of Robust Networks against Performance Deterioration in Failures |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 通信品質 / quality of service |
| キーワード(2)（和/英） | バックボーンネットワーク / backbone network |
| キーワード(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 |
| 発表年月日 | 2009-03-03 |
| 資料番号 | NS2008-164 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 457 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |