疎なルールのもとでのRBTからの決定木構築法

摘要

パケット分類問題は，分類ポリシーを実装したルールリストの各ルールとネットワーク機器を通過するパケットとを照合して，パケットに合致する優先度の最も高いルールを求める問題である．一般にルールリストのルール数nは増える一方なめで，分類時間がルール数nに依存しないアルゴリズムが求められる．そこで我々は，任意のビットマスクルールに対応するRun-Based Trie（RBT）というデータ構造とRBTから構成される決定木を用いた探索時間がルール数nに依らない探索アルゴリズムを提案した1，2．けれども，提案手法に用いる決定木の領域計算量はビット長wとルール数nに関して0（n~w）と指数オーダであり，w≧118のルールリストやパケット分類のベンチマークであるClassBench［3］のルールリストのような疎なルールリストに対しても決定木を構築できなかった．本稿では，節点vの子を生成する際に根から節点vまでのパスで得られる連を参照することによって不要な節点を生成しない決定木構築法を提案する．提案手法はn＝1000のClassBenchから生成される疎なルールリストに対して決定木を構築できる．