Zheng Weibin£¬Zhang Deyun£¬An Zhiping£¬Liu Weina
(School of Electronics and Information Engineering,Xi'an Jiaotong University,Xi'an ¡¡710049,China)
Abstract: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¡MTree, 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%.
Keywords:packet classification;cacheª²aware data structure;Bª²tree;range lookup