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

石川 裕樹  原田 崇司  田中 賢  三河 賢治  

誌名
電子情報通信学会論文誌 B   Vol.J103-B   No.2   pp.48-56
発行日: 2020/02/01
Online ISSN: 1881-0209
DOI: 10.14923/transcomj.2019GTP0013
論文種別: 特集論文 (通信の未来を拓く学生論文特集)
専門分野: 基礎理論
キーワード: 
ネットワーク,  セキュリティ,  パケット分類,  決定木,  多値決定グラフ,  

本文: PDF(804.8KB)>>
論文を購入




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