講演抄録/キーワード |
講演名 |
2009-01-30 17:00
並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法 ○木原 拓・清水 翔・高 山・荒川 豊・山中直明(慶大)・渡辺昭文(アイピーフレックス) VLD2008-125 CPSY2008-87 RECONF2008-89 |
抄録 |
(和) |
次世代のネットワークには高い水準の信頼性が求められている.高い信頼性を実現するための技術の1つであるプロテクションでは、リンクディスジョイントな2つの経路の合計コストをできるだけ低くすることが,リソースの効率的な利用の点で重要な課題となっている.しかしながら、経路の合計コストが最も低い最適解を求めるための計算はNP困難であり,膨大な時間がかかってしまう.そこで、本稿では並列プロセッサDAPDNA-2を用いて、リンクディスジョイント経路計算における最適解を高速に算出する方法を提案する.提案方式では、全リンクパターンの中から制約条件を基にネットワーク中の全経路を抽出し、並列組合せ計算を行うことにより、最適解を高速に算出する.特性評価では、従来の最適解を求めるための高速化アプローチと比較して、提案方式が20倍以上高速化できることを示す. |
(英) |
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. |
キーワード |
(和) |
プロテクション / リンクディスジョイント経路計算 / 並列リコンフィギュラブルプロセッサ / DAPDNA-2 / / / / |
(英) |
Protection / Link-disjoint paths calculation / Parallel Reconfigurable Processor / DAPDNA-2 / / / / |
文献情報 |
信学技報, vol. 108, no. 414, RECONF2008-89, pp. 201-206, 2009年1月. |
資料番号 |
RECONF2008-89 |
発行日 |
2009-01-22 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2008-125 CPSY2008-87 RECONF2008-89 |