仮想包囲方形に基づくパラメータフィルタの設計と実装

摘要

本論文では，仮想的な包囲方形を導入した多次元空間検索手法によるパラメータフィルタの高速化を提案する．我々はルータにおける複雑なポリシを反映するパケット分類の問題に対し，KUPFアーキテクチャを提案し，実装してきた．パラメータフィルタは一般に複数のパラメータからなるフィルタをもつため，KUPFに対して従来の高速化手法を適用できない．多次元空間における検索手法として，最小包囲方形を用いて探索木を構築し，検索を高速化させるR-tree, R*-treeが知られている．これに対し，本提案では仮想的な包囲方形を導入することで，フィルタルールを多次元空間上で表現するとともに，パラメータごとの特性の違いを正規化してR*-treeを適用した．本提案を実装したKUPF-VRは，従来のKUPFの検索速度を向上させ，IPパケット処理に特化した手法と比べても，フィルタルールが多い場合に優位性があることが明らかになった．