信頼度の高いネットワークを実現する保護リンク決定法の高速化

摘要

通信ネットワークには高い信頼性が求められており，ネットワーク故障に耐性のある頑健なネットワークの構築と運用が重要である.そのため，バックアップ機構や高速復旧機構などによってリンク故障確率を大幅に下げること（リンク保護）が必要であるが，すべてのリンクを保護するには膨大なコストがかかる.そのため，一部の必要性の高いリンクのみを優先的に保護し，ネットワーク全体の信頼性を高めることが現実的である.本稿では，一部のリンクを保護することによって，ネットワーク信頼度（ネットワーク全体が連結している確率）を最大化する設計問題を扱う.まず，ネットワーク信頼度の下界を用いて，高速に保護リンク集合を決定するアルゴリズムを設計する.さらに，実際の通信ネットワークトポロジを用いて性能を評価し，既存アルゴリズムに比べて大幅な高速化が可能であることを示す.