文献

J-GLOBAL ID：201502281139966935   整理番号：15A0745214

任意ビットマスク規則の構造を含むランベーストライ

Run-Based Trie Involving the Structure of Arbitrary Bitmask Rules

著者 (2件)： MIKAWA Kenji (Center for Academic Information Serv., Niigata Univ.) ,  TANAKA Ken (Fac. of Sci., Kanagawa Univ.)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 6  ページ： 1206-1212 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： パケット分類はネットワークトラヒック制御,サイバー脅威からの保護における基本タスクである。殆どのレイヤ3および高次ネットワーク機器はパケット分類能力を持ち,一連の規則を用いてヘッダを比較することにより着信パケットの許認可または廃棄を決定する。線形探索はパケット分類の直観的実行であるが,大変非効率である。Srinivasan他は線形探索の代りに階層トライを用いる革新的ルックアップスキームを提案し,規則数よりむしろ規則長に比例した時間複雑性を有するより高速なパケット分類を実現した。しかし,階層トライとその多様な改良アルゴリズムは単一プレフィックス規則の処理だけを許容する。レイヤ4および高次パケット分類は階層トライの任意ビットマスク規則を処理する必要があるため,但し任意ビットマスク規則を処理すべく拡張された,階層トライに基づくランベーストライを提案した。提案アルゴリズムは長さdWのN規則においてO((dW)²)クエリー時間とO(N^dW)空間複雑性を達成した。革新的アルゴリズムのクエリー時間は規則数に依存しない。ファイアウォールの規則増加に起因する滞在時間問題を解決する。(翻訳著者抄録)

シソーラス用語： 分類 ,  *パケット ,  *ディシジョンツリー ,  二値論理 ,  階層構造 ,  ツリー構造 ,  実証実験 ,  木探索 ,  許認可 ,  *インターネット ,  *コンピュータセキュリティ ,  経路選定 ,  ファイアウォール ,  通信操作 ,  サイバー攻撃
準シソーラス用語： パケット分類 ,  ビットマスク

分類 (3件)： 計算機網  (JC03000K) ,  データ保護  (JD01020V) ,  通信網  (ND07030A)

引用文献 (12件)：

• [1] H.J. Chen, “Next generation routers,” Proc. IEEE, vol.90, no.9, pp.1518-1558, Sept. 2002.
• [2] V. Grout, J. McGinn, and J. Davies, “Real-time optimisation of access control lists for efficient Internet packet filtering,” J. Heuristics, vol.13, no.5, pp.435-454, Oct. 2007.
• [3] P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol.20, no.1, pp.34-41, Jan./Feb. 2000.
• [4] P. Gupta and N. McKeown, “Packet classification on multiple fields,” Proc. ACM SIGCOMM, pp.147-160, 1999.
• [5] H. Hamed and E. Al-Shaer, “Dynamic rule-ordering optimization for high-speed firewall filtering,” Proc. ACM Symposium on Information, Computer and Communications Security, pp.332-342, 2006.

タイトルに関連する用語 (3件)： ビット ,  マスク ,  規則