文献

J-GLOBAL ID：201102282254768761   整理番号：11A1354064

高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価

Entwork Reliability Evaluation Using Efficient Path Enumeration ALgorithms

クリップ

著者 (6件)： 斎藤寿樹 (JST-ERATO) ,  川原純 (JST-ERATO) ,  吉仲亮 (JST-ERATO) ,  井上武 (JST-ERATO) ,  湊真一 (北大 大学院情報科学研究科) ,  湊真一 (JST-ERATO)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 111  号： 146(IN2011 45-63)  ページ： 57-62  発行年： 2011年07月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,ZDD(Zero-suppressed Binary Decision Diagram)を用いたグラフ上のパス列挙アルゴリズムが提案された。ZDDとは,組合せ集合を圧縮して表現できるデータ構造である。グラフ上のパスを辺の組合せと同一視すると,ZDDを用いてパスの集合を表現できる。また,ZDDには多様な演算が定義されており,これらを利用すると効率的にパス集合を操作できる。我々は通信ネットワークでの利用を想定し,ZDDを利用したパス管理ソフトウェアを開発した。このソフトウェアは与えられた条件でパス集合を絞り込み,その中から最小故障率のパスを抽出する。ZDDによるパス列挙は厳密であり,リンク故障率に依存関係があるような複雑な状況でも,正確なパス故障率を算出できる。また,これらの操作は効率的に行われ,たとえば81ノードの格子ネットワークにある1126509504221649本のパスを1.85秒で列挙し,0.1秒未満で絞り込みや最小故障率パスの抽出を行う。(著者抄録)

シソーラス用語： *パケット交換 ,  *ネットワーク管理 ,  *プロトコル ,  二分決定グラフ ,  一覧表 ,  故障率 ,  評価 ,  ソフトウェア開発 ,  信頼性評価 ,  *マルチプロトコルラベルスイッチング ,  *ルーティングプロトコル
準シソーラス用語： *MPLS【通信交換】 ,  *経路制御プロトコル ,  パス列挙 ,  最小故障率

分類 (3件)： 光通信方式・機器  (ND10000B) ,  計算機網  (JC03000K) ,  通信理論一般  (ND02010V)

引用文献 (11件)：

• BAX, E. T. Algorithms to count paths and cycles. Information Processing Letters. 1994, 52, 5, 249-252
• HARDY, G. K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability. 2007, 56, 3, 506-515
• 川原純. ZDDのリンクパズルへの応用. 組合せゲーム・パズルのミニ研究集会, 2011. 2011
• KNUTH, D. The Art of Computer Programming. 2005
• MCKEOWN, N. Open-flow : enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev. 2008, 38, 69-74

タイトルに関連する用語 (3件)： パス ,  アルゴリズム ,  信頼性評価