高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
近年,ZDD(Zero-suppressed Binary Decision Diagram)を用いたグラフ上のパス列挙アルゴリズムが提案された.ZDDとは,組合せ集合を圧縮して表現できるデータ構造である.グラフ上のパスを辺の組合せと同一視すると,ZDDを用いてパスの集合を表現できる.また,ZDDには多様な演算が定義されており,これらを利用すると効率的にパス集合を操作できる.我々は通信ネットワークでの利用を想定し,ZDDを利用したパス管理ソフトウェアを開発した.このソフトウェアは与えられた条件でパス集合を絞り込み,その中から最小故障率のパスを抽出する.ZDDによるパス列挙は厳密であり,リンク故障率に依存関係があるような複雑な状況でも,正確なパス故障率を算出できる.また,これらの操作は効率的に行われ,たとえば81ノードの格子ネットワークにある1126509504221649本のパスを1.85秒で列挙し,0.1秒未満で絞り込みや最小故障率パスの抽出を行う.
- 2011-07-14
著者
-
斎藤 寿樹
北陸先端科学技術大学院大学情報科学研究科
-
井上 武
日本電信電話株式会社NTT未来ねっと研究所
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
函館五稜郭病院
-
湊 真一
Ntt光ネットワークシステム研究所
-
斎藤 寿樹
科学技術振興機構ERATO湊離散構造処理系プロジェクト
-
湊 真一
Ntt 未来ねっと研
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
斎藤 寿樹
科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
川原 純
科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
吉仲 亮
JST・Hokkaido U.
-
吉仲 亮
科学技術振興機構ERATO湊離散構造処理系プロジェクト|北海道大学大学院情報科学研究科
-
Minato Shin-ichi
Graduate School Of Information Science And Technology Hokkaido University
-
川原 純
科学技術振興機構
-
井上 武
Ntt未来ねっと研究所メディアイノベーション研究部
-
井上 武
科学技術振興機構erato湊離散構造処理プロジェクト
-
吉仲 亮
科学技術振興機構erato湊離散構造処理プロジェクト
-
吉仲 亮
京都大学
-
井上 武
科学技術振興機構erato
-
湊 真一
Ntt光ネットワーク研究所
-
川原 純
奈良先端科学技術大学院大学情報科学研究科
-
湊 真一
北海道大学 大学院情報科学研究科
-
斎藤 寿樹
科学技術振興機構ERATO湊離散構造処理プロジェクト
-
湊 真一
京都大学大学院情報学研究科:科学技術振興機構ERATO湊離散構造処理プロジェクト
-
湊 真一
北海道大学 大学院 情報科学研究科
関連論文
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- BDD上の命題化計算に基づくEMアルゴリズム
- Network Mobilityに基づく公共交通機関を想定した位置管理方式(ネットワークソフトウェア論文)
- Bipartite Permutation Graphのランダム生成と列挙
- RESTアーキテクチャスタイルへのセッションの導入(ミドルウェア技術,セキュアでサステイナブルなインターネットアーキテクチャ論文)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (VLSI設計技術)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装(ネットワーク・並列分散システムソフトウェア, システム開発論文)
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- JGNを介した大規模映像配信プラットフォーム(新しいトラヒックモデルと性能評価及び一般)
- B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察
- B-7-47 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験
- B-7-46 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング
- B-7-45 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式
- BS-5-5 漏洩者の特定と配信停止が可能なマルチキャスト配信方式(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- B-7-4 ネットワークによるフロー切り替えを行うマルチキャスト電子透かし方式の検討(B-7.情報ネットワーク,一般講演)
- B-7-31 トラヒックの平滑化とFECによる講義ノート映像品質の改善(B-7.情報ネットワーク, 通信2)
- Flexcastを用いた講義ノート多地点同報配信システムの検討(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- FlexcastとJavaAppletに基づくプログラマブルな多地点同報配信アプリケーションの実装法(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- B-7-73 MulticastVNCを用いた講義ノート配信システムのトラヒック特性評価(B-7. 情報ネットワーク, 通信2)
- ベイジアンネットワークと離散構造処理系 (特集 ベイジアンネットワークの最先端)
- B-20-8 順序逆転のある時系列センサデータに対するオフセットビットマップを用いた効率的な索引付方法(B-20.ユビキタス・センサネットワーク,一般セッション)
- ネットワーク層マルチキャストにおける転送方法の分類について : ステートレスマルチキャストの優位性(マルチキャスト・一般)
- B-6-82 HTMLフォームと統合されたHTTPアクセス認証フレームワーク(B-6.ネットワークシステム,一般セッション)
- B-7-82 Stateless Multicastにおける配信木サイズ拡大のための仮想ポート構成法(B-7.情報ネットワーク,一般セッション)
- 仮想ポートを用いたステートレスマルチキャストにおける配信木サイズの解析について(マルチキャスト・一般)
- B-20-7 センサデータマイニングのための分散サンプリングストレージの提案(B-20.ユビキタス・センサネットワーク,一般セッション)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- iAuth : HTMLフォームと統合されたHTTPアクセス認証フレームワーク(匿名化・認証,インターネットセキュリティ,一般)
- 5.メディア系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- グラフクラスと部分グラフ同型性
- BDD/ZDDを用いたペントミノパズルの解の列挙
- 非巡回正規表現に対する効率的なパターン照合
- B-20-13 位置情報適応型サービスのための拡張現実型コンテキスト共有モデルの提案(B-20.ユビキタス・センサネットワーク,一般セッション)
- B-6-53 Web APIを備えたデータベースシステムの設計と再利用性に関する一検討(B-6.ネットワークシステム,一般セッション)
- B-7-11 移動体通信における接続性履歴にもとづく階層的位置管理方式
- 移動体通信における接続性履歴を用いた階層的位置管理方式の提案
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 迅速なアプリケーション開発のためのWeb APIデータべースシステム(一般,NGN,VoIP,FMC,自律分散ネットワーク,ソフトウェアエージェント,Webサービス,Web2.0及び一般)
- iAuth:HTMLフォームと統合されたHTTPアクセス認証フレームワーク(匿名化・認証,インターネットセキュリティ,一般)
- 順序逆転のある時系列センサデータのための効率的な索引付方法の提案と性能評価(センサーネットワーク)
- センサデータマイニングのための分散サンプリングストレージの提案 : 統計量の基本的な挙動解析を中心に(センサーネットワーク)
- パス上のボロノイゲーム
- 命題論理に基づく確率モデルのための二部決定グラフと順序符号化を用いた効率的なEMアルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- D-022 センサデータのための分散サンプリングストレージとそのサンプルサイズ制御手法(D分野:データベース,一般論文)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- 分散サンプリングストレージを用いた電波利用状況可視化 (情報ネットワーク)
- 移動体通信における接続性履歴を用いた階層的位置管理方式の提案
- B-7-21 移動体通信における接続性履歴を用いた位置登録集約方式の提案
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察 (テーマ:特集「ウェブデータの知的処理」および一般)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- B-20-25 分散サンプリングストレージを用いた電波利用状況可視化の初期的検討(B-20.ユビキタス・センサネットワーク,一般セッション)
- B-20-24 ランダムサンプリングを用いた空き周波数帯域検索手法(B-20.ユビキタス・センサネットワーク,一般セッション)
- B-7-32 ソースルーティングマルチキャストのトラフィック量と最大収容グループ数の評価(B-7.情報ネットワーク,一般セッション)
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- ZDDを用いたパスの列挙とその性能評価
- センサデータマイニングのための分散サンプリングストレージの提案 : 統計量の基本的な挙動解析を中心に
- 分散サンプリングストレージを用いた電波利用状況可視化(NW制御(3))
- B-7-37 ルータコストを考慮したソースルーティングマルチキャストとIPマルチキャストの最大収容グループ数の比較(B-7. 情報ネットワーク,一般セッション)
- Flexcast型ストリーム配信における経路設定法およびレイヤ3トポロジ考慮法の検討(一般,高度プロトコル・ネットワーキング技術(IP及び高位レイヤルーチング・フィルタリング,マルチキャスト,品質・経路制御,IPNWの利用技術(P2P,P4P,オーバレイ,SIP,NGN),ネットワークシステム関連技術(システム構成法,インタフェース,アーキテクチャ,ハードウェア・ソフトウェア・ミドルウェア),一般)
- 東日本大震災での短縮URLによるサーバ負荷分散とアクセス分析(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- マルチフローを考慮したFlexcast型ストリーム配信における経路設定法の検討(ポストIPネットワーキング,新世代ネットワーク,ネットワークモデル,インターネットトラヒック,TCP/IP,マルチメディア通信,ネットワーク管理,リソース管理,プライベートネットワーク,NW安全性及び一般)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- フロンティア法による電力網構成制御 (特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- フロンティア法による電力網構成制御(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- PS-154-1 自己弁温存大動脈基部置換術前後の弁形状の変化が遠隔期AR再発に及ぼす影響(心臓弁膜症,ポスターセッション,第112回日本外科学会定期学術集会)
- PS-153-6 ステントレス生体弁を用いた成人期右室流出路再建後の遠隔成績 : Ross手術を含めて(心臓小児・弁膜症,ポスターセッション,第112回日本外科学会定期学術集会)
- PS-105-8 脳内酸素モニタリングは大動脈弓部全置換術後の覚醒遅延を予測しうるか?(PS-105 大血管 胸部,ポスターセッション,第112回日本外科学会定期学術集会)
- SF-041-1 高齢者における大動脈弓部全置換術(SF-041 サージカルフォーラム(41)大血管 胸部,第112回日本外科学会定期学術集会)
- SF-040-3 アスコルビン酸徐放ハイドロゲルシートを用いた大動脈瘤の抑制(続報)(SF-040 サージカルフォーラム(40)大血管 基礎,第112回日本外科学会定期学術集会)
- VSY-6-5 当科における大動脈弁温存手術(VSY-6 ビデオシンポジウム(6)大動脈弁形成術および大動脈弁温存手術-適応と術式-,第112回日本外科学会定期学術集会)
- SF-107-3 胸部大動脈感染病変に対する治療経験(SF-107 サージカルフォーラム(107)大血管 胸腹部,第112回日本外科学会定期学術集会)
- VWS-1-5 機能的重症憎帽弁逆流に対する自己弁温存憎帽弁置換術の治療成績(VWS-1 ビデオワークショップ(1)機能的僧帽弁逆流に対する術式の工夫,第112回日本外科学会定期学術集会)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- フロンティア法を用いた電力網解析手法(新世代・次世代ネットワーク,ネットワークとシステムの仮想化,仮想化環境の管理・監視,オーバーレイ,IPv6ネットワーク,フォトニックネットワーク及び一般)