高速缓存感知的包分类算法

提出了一种高速缓存感知的数据结构CATree，对聚合位向量包分类算法进行改进，可提高算法的区间查找速度．CATree是一个基于B-树的数据结构，它使用数组存储数据，由于没有指针，所以Cache利用率更高，使用CATree可以降低查找算法的DRAM访问次数，改进后的算法整体性能有很大提高，即在600条规则的性能评价实验中，改进算法比聚合位向量算法快30%，比位向量算法快94％。

Cache-Aware Algorithm for Packet Classification

The packet classification is important for routers and firewalls. The aggregation bit vector (ABV) can be considered as a scalable algorithm for packet classification, but the performance of range lookup offered by ABV is poor. Based on B-Tree, a cache-aware data structure called CATree with data stored in an array is proposed, which takes advantage of cache line size to speedup the range lookup in ABV. Since there is no pointer, the cache line utilization becomes more efficient. CATree's search will take less memory accesses than a binary search. The performance of CABV, i.e. an ABV with CATree, is evaluated by experiments on a rule base with 600 rules, which that CABV performs faster than ABV by 30% and BV by 94%.