講演抄録/キーワード |
講演名 |
2011-07-21 17:10
高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価 ○斎藤寿樹・川原 純・吉仲 亮・井上 武(JST)・湊 真一(北大/JST) IN2011-55 |
抄録 |
(和) |
近年,ZDD (Zero-suppressed Binary Decision Diagram) を用いたグラフ上のパス列挙アルゴリズムが提案された.ZDD とは,組合せ集合を圧縮して表現できるデータ構造である.グラフ上のパスを辺の組合せと同一視すると,ZDD を用いてパスの集合を表現できる.また,ZDD には多様な演算が定義されており,これらを利用すると効率的にパス集合を操作できる.我々は通信ネットワークでの利用を想定し,ZDD を利用したパス管理ソフトウェアを開発した.このソフトウェアは与えられた条件でパス集合を絞り込み,その中から最小故障率のパスを抽出する.ZDD によるパス列挙は厳密であり,リンク故障率に依存関係があるような複雑な状況でも,正確なパス故障率を算出できる.また,これらの操作は効率的に行われ,たとえば81 ノードの格子ネットワークにある1126509504221649 本のパスを1.85 秒で列挙し,0.1 秒未満で絞り込みや最小故障率パスの抽出を行う. |
(英) |
Recently, novel algorithms that enumerate all possible paths on a graph have been proposed. They commonly take advantage of Zero-suppressed Binary Decision Diagram, or ZDD, which is an efficient data structure for representing family of sets. These algorithms treat a path as a set of edges, and so ZDD is allowed to handle paths in its own way. ZDD’s efficient algebra is also used in the algorithms to select required paths. We develop a path management system that relies on the ZDD path enumeration algorithm. Our management system accepts some filtering conditions to select paths, and finds the best one from them. The best path is correctly chosen without approximation even if there is a dependency among link failures. Despite of the correctness, our system is quite efficient; 1126509504221649 paths on a grid network of 81 nodes are enumerated in 1.85 seconds, and these paths are filtered and the best one is found in 0.1 seconds. |
キーワード |
(和) |
ZDD / パス列挙 / ネットワーク管理 / / / / / |
(英) |
ZDD / path enumeration / network management / / / / / |
文献情報 |
信学技報, vol. 111, no. 146, IN2011-55, pp. 57-62, 2011年7月. |
資料番号 |
IN2011-55 |
発行日 |
2011-07-14 (IN) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IN2011-55 |