文献

J-GLOBAL ID：202002299101953445   整理番号：20A0658282

ポインタ付連分割トライに基づく決定木構築法

著者 (4件)： 石川裕樹 (スズキ) ,  原田崇司 (高知工科大 情報学群) ,  田中賢 (神奈川大 理) ,  三河賢治 (新潟大 情報基盤セ)
資料名： 電子情報通信学会論文誌 B(Web)
巻： J103-B  号： 2  ページ： 48-56 (WEB ONLY)  発行年： 2020年02月01日 
JST資料番号： U0471A  ISSN： 1881-0209  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,不正アクセスやサービス不能攻撃によるサイバー被害の増加にともない,不正な通信を遮断するファイアウォールなどの基礎技術であるパケット分類が注目されている.連想メモリなどの特殊なハードウェアを実装していないネットワーク機器では,分類の指標となるルールリストとパケットを線型探索により照合する.ほとんどのパケットがルールリストの全てのルールと照合されるため,ルール数が数千行に及ぶ実際の運用において分類処理の遅延は重大な問題となっている.このため,ルール数に依存しない探索法が求められる.本論文では,連分割トライを応用した新しい決定木探索法を提案する.提案手法の探索時間計算量は,ルール数に依存せず,ルール長wに対してO(w)時間である.同様な探索時間計算量を実現するデータ構造として多値決定グラフが知られるが,現実的な時間で多値決定グラフを構成できないルールリストに対しても,探索可能な決定木を構成できる場合があることを示す.(著者抄録)

シソーラス用語： *分類 ,  *コンピュータセキュリティ ,  通信装置 ,  規則 ,  *ディシジョンツリー ,  方式 ,  時間 ,  計算量 ,  データ構造
準シソーラス用語： *サイバーセキュリティ ,  ネットワーク機器 ,  *パケット分類 ,  ルール ,  *決定木 ,  探索時間 ,  探索法

分類 (3件)： データ保護  (JD01020V) ,  電話・データ通信・交換一般  (ND11010T) ,  計算理論  (JB02000A)

引用文献 (6件)：

• V. Srinivasan, G. Varghee, S. Suri, and M. Waldvogel, “Fast and scalable layer four switching,” SIGCOMM Comput. Commun. Rev., vol.28, no.4, pp.191-202, Oct. 1998.
• K. Mikawa and K. Tanaka, “Run-based trie involving the structure of arbitrary bitmask rules,” IEICE Trans. Inf. & Syst., vol.E98-D, no.6, pp.1206-1212, June 2015.
• A. Srinivasan, T. Ham, S. Malik, and R.K. Brayton, “Algorithms for discrete function manipulation,”1990 IEEE International Conference on ComputerAided Design. Digest of Technical Papers, pp.92-95, Nov. 1990.
• 原田崇司,田中 賢,三河賢治,“ポインタ付与によるRun-Based Trie探索の高速化,” 信学技報,CAS2016-60, Nov. 2016.
• D.E. Taylor and J.S. Turner, “Classbench: A packet classification benchmark,” IEEE/ACM Trans. Netw., vol.15, no.3, pp.499-511, June 2007. http://dx.doi.org/10.1109/TNET.2007.893156

タイトルに関連する用語 (3件)： ポインタ ,  決定木 ,  構築