ポインタ付与によるRun-Based Trie探索の高速化

摘要

Run-Based Trieは，アルファベット（0，1，＊）上の長さwの系列のリストによって定義された函数f：｛0，1｝~w→Nを計算することができるデータ構造である．パケット分類問題は，ネットワーク機器を通過するパケットと与えられているフィルタリングルールリストの各ルールとを照合して，パケットに合致する優先度の最も高いルールを求める問題である．この問題は，Run-Based Trieを上手く用いることができる問題の一つである．本稿では，Run-Based Trieの全てのノードにポインタを付与することにより，Run-Based Trie探索の時間計算量をルールリストのルール数nに関してO（nw＋w~2）からO（nw）へと減らす手法を提案する．また，計算機実験により提案手法の有効性を検証する．