お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2011-07-21 17:10
高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価
斎藤寿樹川原 純吉仲 亮井上 武JST)・湊 真一北大/JSTIN2011-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

研究会情報
研究会 IN NV  
開催期間 2011-07-21 - 2011-07-22 
開催地(和) 北海道大学 
開催地(英) Hokkaido University 
テーマ(和) IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワークおよび一般 
テーマ(英) IPv6, Photonic network system, New/Next Generation Network, etc 
講演論文情報の詳細
申込み研究会 IN 
会議コード 2011-07-IN 
本文の言語 日本語 
タイトル(和) 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価 
サブタイトル(和)  
タイトル(英) Entwork Reliability Evaluation Using Efficient Path Enumeration ALgorithms 
サブタイトル(英)  
キーワード(1)(和/英) ZDD / ZDD  
キーワード(2)(和/英) パス列挙 / path enumeration  
キーワード(3)(和/英) ネットワーク管理 / network management  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 斎藤 寿樹 / Toshiki Saitoh / サイトウ トシキ
第1著者 所属(和/英) 科学技術振興機構 (略称: JST)
Japan Science and Technology Agency (略称: JST)
第2著者 氏名(和/英/ヨミ) 川原 純 / Jun Kawahara / カワハラ ジュン
第2著者 所属(和/英) 科学技術振興機構 (略称: JST)
Japan Science and Technology Agency (略称: JST)
第3著者 氏名(和/英/ヨミ) 吉仲 亮 / Ryo Yoshinaka / ヨシナカ リョウ
第3著者 所属(和/英) 科学技術振興機構 (略称: JST)
Japan Science and Technology Agency (略称: JST)
第4著者 氏名(和/英/ヨミ) 井上 武 / Takeru Inoue / イノウエ タケル
第4著者 所属(和/英) 科学技術振興機構 (略称: JST)
Japan Science and Technology Agency (略称: JST)
第5著者 氏名(和/英/ヨミ) 湊 真一 / Shin-ichi Minato / ミナト シンイチ
第5著者 所属(和/英) 北海道大学 (略称: 北大/JST)
Hokkaido University (略称: Hokkaido Univ.)
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2011-07-21 17:10:00 
発表時間 25 
申込先研究会 IN 
資料番号 IEICE-IN2011-55 
巻番号(vol) IEICE-111 
号番号(no) no.146 
ページ範囲 pp.57-62 
ページ数 IEICE-6 
発行日 IEICE-IN-2011-07-14 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会