並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法

摘要

次世代のネットワークには高い水準の信頼性が求められている．高い信頼性を実現するための技術の1つであるプロテクションでは、リンクディスジョイントな2つの経路の合計コストをできるだけ低くすることが，リソースの効率的な利用の点で重要な課題となっている．しかしながら、経路の合計コストが最も低い最適解を求めるための計算はNP困難であり，膨大な時間がかかってしまう．そこで、本稿では並列プロセッサDAPDNA-2を用いて、リンクディスジョイント経路計算における最適解を高速に算出する方法を提案する．提案方式では、全リンクパターンの中から制約条件を基にネットワーク中の全経路を抽出し、並列組合せ計算を行うことにより、最適解を高速に算出する．特性評価では、従来の最適解を求めるための高速化アプローチと比較して、提案方式が20倍以上高速化できることを示す．