文献

J-GLOBAL ID：201602206108132650   整理番号：16A0000741

MDDを用いたハイパーキューブ探索によるネットワーク検証の高速化

Efficient Network Policy Checking with Multi-dimensional Graph Traversal Algorithm

著者 (7件)： CHEN R. (NTT 未来ねっと研) ,  CHEN R. (ウォータールー大) ,  井上武 (NTT 未来ねっと研) ,  間野暢 (NTT 未来ねっと研) ,  水谷后宏 (NTT 未来ねっと研) ,  永田尚志 (NTT 未来ねっと研) ,  明石修 (NTT 未来ねっと研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 256(IA2015 30-36)  ページ： 25-30  発行年： 2015年10月12日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 現在のネットワークは高度な機能を提供するために複雑に設定されており,それが障害の原因となっている。設定ミスを検出するネットワーク検証技術は,SDNの重要なアプリケーションとして注目を集めている。本稿では,パケット分類アルゴリズムを拡張し,ネットワーク検証の大幅な高速化を可能にする探索アルゴリズムを提案する。パケット分類が一つのパケットに対するアクションを決定するのに対し,提案アルゴリズムは「ハイパーキューブ探索(範囲検索の多次元拡張)」により,パケットの集合に対応する全アクションを一度に取得し,ネットワーク検証を実現する。この探索処理はMDDという圧縮データ構造上で動的計画法により効率的に実行される。実データを用いた実験により,提案手法が既存の最速手法APVより桁違いに高速であることを示す。たとえば,大規模更新を想定したシナリオでは,3時間が2分間に短縮される。(著者抄録)

シソーラス用語： 探索問題 ,  *ハイパーキューブ方式 ,  動的計画法 ,  *部分グラフ ,  *ネットワーク構造 ,  *データ構造 ,  *検証 ,  *高速アルゴリズム ,  *探索アルゴリズム
準シソーラス用語： *多値決定グラフ

分類 (2件)： ネットワーク法  (KA03040X) ,  人工知能  (JE08000Z)

引用文献 (19件)：

• T. Benson, A. Akella, and D. A. Maltz, "Mining policies from enterprise network configuration," in ACM IMC, pp. 136-142, 2009.
• X. Sun and G. G. Xie, "Minimizing network complexity through integrated top-down design," in ACM CoNEXT, pp. 259-270, 2013.
• D. Oppenheimer, A. Ganapathi, and D. A. Patterson, "Why do internet services fail, and what can be done about it?," in USENIX USITS, pp. 1-16, 2003.
• H. Zeng, P. Kazemian, G. Varghese, and N. McKeown, "A survey on network troubleshooting," tech. rep., Technical Report Stanford/TR12-HPNG-061012, Stanford University, 2012.
• E. Al-Shaer, W. Marrero, A. El-Atawy, and K. ElBadawi, "Network configuration in a box: towards end-to-end verification of network reachability and security," in IEEE ICNP, pp. 123-132, 2009.

タイトルに関連する用語 (4件)： ハイパーキューブ ,  探索 ,  検証 ,  高速化