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

摘要

インターネットをはじめ，通信ネットワークが社会において必要不可欠なインフラとなった現在，ネットワークには高い信頼性が求められている．しかし，ネットワークにおいて単一リンク故障による経路切断が発生した際，もとの経路に比べて代替経路の経路長が大幅に増加し，通信品質の大幅な劣化を引き起こす可能性がある．通常，ネットワークは既に構築·運用されており，初期段階の想定から大幅に変化していることが多い．このような既設ネットワーク全体を再構築しなおすことは非現実的であるため，既存のネットワークに最小限の増設を行うことで性能を向上させること，つまり経路長増加率を小さくすることが必要となる．本稿では，これを経路長増加率を抑制する最小リンク付加問題として定式化した．そして，この問題がNP完全であることを証明し，近似アルゴリズムを設計した．さらに，現実の様々なネットワークへ適用してアルゴリズムの有効性を評価した．