故障時における性能劣化を抑制するネットワーク設計法

摘要

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完全であることを証明し，近似アルゴリズムを設計した．さらに，現実の様々なネットワークへ適用してアルゴリズムの有効性を評価した．