| 講演名 | 2008-08-08 リンクディスジョイント経路計算の高速解法の一検討 : DAPDNA-2による並列マルチレイヤ経路計算 木原 拓, 清水 翔, 高 山, 荒川 豊, 山中 直明, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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 survivability. 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. |
| キーワード(和) | リンクディスジョイント経路 / 並列リコンフィギュラブルプロセッサ / DAPDNA-2 / K Disjoint-Paths Pairs |
| キーワード(英) | Link-disjoint paths / Parallel Reconfigurable Processor / DAPDNA-2 / K Disjoint-Paths Pairs |
| 資料番号 | PN2008-17 |
| 発行日 |
| 研究会情報 | |
| 研究会 | PN |
|---|---|
| 開催期間 | 2008/8/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Photonic Network (PN) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | リンクディスジョイント経路計算の高速解法の一検討 : DAPDNA-2による並列マルチレイヤ経路計算 |
| サブタイトル（和） | |
| タイトル（英） | A Study on High Speed Method of Link-Disjoint Path Calculation : A Parallel Multi-layer Path Calculation on DAPDNA-2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | リンクディスジョイント経路 / Link-disjoint paths |
| キーワード(2)（和/英） | 並列リコンフィギュラブルプロセッサ / Parallel Reconfigurable Processor |
| キーワード(3)（和/英） | DAPDNA-2 / DAPDNA-2 |
| キーワード(4)（和/英） | K Disjoint-Paths Pairs / K Disjoint-Paths Pairs |
| 第 1 著者 氏名（和/英） | 木原 拓 / Taku KIHARA |
| 第 1 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 2 著者 氏名（和/英） | 清水 翔 / Sho SHIMIZU |
| 第 2 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 3 著者 氏名（和/英） | 高 山 / SHAN Gao |
| 第 3 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 4 著者 氏名（和/英） | 荒川 豊 / Yutaka ARAKAWA |
| 第 4 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 5 著者 氏名（和/英） | 山中 直明 / Naoaki YAMANAKA |
| 第 5 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 発表年月日 | 2008-08-08 |
| 資料番号 | PN2008-17 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 183 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |