故障時のネットワーク負荷集中を回避する高信頼リンク決定法

摘要

インターネットが普及して重要な社会基盤となるにともない，故障の影響を最小限に抑えた信頼性の高いネットワークの構築·運用が，サービス提供者にとって重要な課題となっている．インターネットにおける経路としては通常最短経路が選ばれるが，リンクに割り当てられたメトリックにより自動的に経路が決定されるため，リンク故障によって経路が変更された際，特定のリンクに経路が集中して輻輳が発生する可能性がある．すべてのネットワーク構成要素の信頼性を十分高いものにするためには膨大な設備コストがかかるため，信頼性が十分高いリンクの数を最小限に抑えることにより，それら以外のリンクがたとえ故障して経路が変更されたとしても，各リンクに経路が集中することを回避できることが望ましい．本稿では，この問題を離散最適化問題として定式化し，NP困難性を証明した．さらに，単一リンク故障を想定した場合に対して，多項式時間アルゴリズムを設計した．