故障時においても直径が抑制されたリンク数の少ないネットワーク設計法

摘要

インターネットをはじめ，通信ネットワークが社会において必要不可欠なインフラとなった現在，ネットワークには高い信頼性が求められている．しかし，ネットワークにおいてリンク故障による経路切断が発生した際，代替経路の経路長が大幅に増加し，通信品質の大幅な劣化を引き起こす可能性がある．本稿では，直径·次数の制約を満たしつつ，コストに対応するリンク数を抑えた新規ネットワークの設計問題を扱う．まず，この問題が一般にNP困難であることと，同時に故障するリンクは一つだけとする単一リンク故障（SLF）に限定してもNP完全であることを証明し，SLFに対するヒューリスティックなアルゴリズムを設計した．さらに，ネットワーク生成モデルを用いて生成したネットワークヘアルゴリズムを適用し，有効性を評価した．