講演抄録/キーワード |
講演名 |
2009-03-03 11:50
故障時における性能劣化を抑制するネットワーク設計法 ○片山 希・藤村武史・巳波弘佳(関西学院大)・上山憲昭・長谷川治久・吉野秀明(NTT) NS2008-164 |
抄録 |
(和) |
インターネットをはじめ,通信ネットワークが社会において必要不可欠なインフラとなった現在,ネットワークには高い信頼性が求められている.しかし,ネットワークにおいて単一リンク故障による経路切断が発生した際,もとの経路に比べて代替経路の経路長が大幅に増加し,通信品質の大幅な劣化を引き起こす可能性がある.通常,ネットワークは既に構築・運用されており,初期段階の想定から大幅に変化していることが多い.このような既設ネットワーク全体を再構築しなおすことは非現実的であるため,既存のネットワークに最小限の増設を行うことで性能を向上させること,つまり経路長増加率を小さくすることが必要となる.本稿では,これを経路長増加率を抑制する最小リンク付加問題として定式化した.そして,この問題が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 / / / |
文献情報 |
信学技報, vol. 108, no. 457, NS2008-164, pp. 117-122, 2009年3月. |
資料番号 |
NS2008-164 |
発行日 |
2009-02-24 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2008-164 |