リンクデイスジョイント経路計算の高速解法の一検討DAPDNA-2による並列マルチレイヤ経路計算

摘要

K Disjoint-Paths　Pairs（KDPPs）は，耐障害性を確保するためのリンクデイスジョイント経路を求めるアルゴリズムとして広く使用されているが，最適解（合計コストが最小となるリンクデイスジョイント経路の組）が得られない場合が存在することが知られている．しかし，最通解が得られない状況について，詳しく言及している過去の研究はほとんど存在しない．そこで，本稿では，計算機シミュレーションを用いて様々なトポロジにおけるKDPPsの解の精度を定量化する．さらに，並列リコンフィギャラブルプロセッサに適したマルチレイヤを考慮するリンクデイスジョイント経路探索アルゴリズムも提案し，提案アルゴリズムがKDPPsと比較して計算クロック数を最大で約99.6%減少させることを示す．%K Disjoint-Paths Pairs (KDPPs) is widely used as a link-disjoint path search algorithm to keep sur-vivability. It is known that KDPPs often fails to obtain optimal solution. However, there is few resarches which discuss that issue. Therefore, the accuracy of KDPPs on various topology is investigated in this paper. We propose a parallel link-disjoint path search algorithm for multi-layer networks. Simulation results show that the calculation time of the proposed algorithm decreases by 99. 6% compared to KDPPs.