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

摘要

In next generation network, a high level reliabilty is strong required. In a protection, which is the one of network survivable technology, it is important to use a link-disjoint paths pair of lowest total cost in a view of network resource efficiency. However, the link-disjoint paths pair calculation is NP Complete and it takes great investment of time. In order to solve this problem, we propose a high-speed method of link-disjoint paths pair calculation based on parallel reconfigurable processor. Our proposed method calculates and finds all paths in network from all network link patterns, and then calculates all link-disjoint paths pairs and selects optimal solution. A parallel execution and data flow execution enable our propose to high-speed calculations. A two performance evaluation results show that our proposed method improves calculation time more than 20 times compared to conventional optimal link-disjoint paths pair calculation algorithm.%次世代のネットワークには高い水準の信頼性が求められている．高い信頼性を実現するための技術の1つであるプロテクションでは、リンクディスジョイントな2つの経路の合計コストをできるだけ低くすることが，リソースの効率的な利用の点で重要な課題となっている．しかしながら、経路の合計コストが最も低い最適解を求めるための計算はNP困難であり，膨大な時間がかかってしまう．そこで、本稿では並列プロセッサDAPDNA-2を用いて、リンクディスジョイント経路計算における最適解を高速に算出する方法を提案する．提案方式では、全リンクパターンの中から制約条件を基にネットワーク中の全経路を抽出し、並列組合せ計算を行うことにより、最適解を高速に算出する.特性評価では、従来の最適解を求めるための高速化アプローチと比較して、提案方式が20倍以上高速化できることを示す．