二分決定グラフを用いたネットワーク信頼性評価

ネットワーク信頼性とは，ネットワークの指定された2点間で正しく通信が行える確率のことです．ネットワーク信頼性はネットワークのサービスの質を評価する重要な指標ですが，これを求める問題はNP困難であり，素朴な方法では数十リンク規模のネットワークでも計算することは難しいです．しかし実用上は，二分決定グラフ（ZDD）と呼ばれるデータ構造を用いて数百リンク規模のネットワークに対してもネットワーク信頼性を厳密に計算できることが知られています．ネットワーク信頼性は60年以上研究されている歴史あるテーマですが，遅延や時間変化などを考慮した信頼性の評価についてはまだあまり効率よい手法が知られていません．本テーマではそのような現実の様々な制約を考慮した信頼性評価も効率よく行う方法を研究しています．