一种用于大规模规则库的快速包分类算法  

A Scalable Fast Algorithm for Packet Classification

作　　者：余胜生[1] 张宁[1] 周敬利[1] 胡熠峰[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机工程》2004年第7期49-51,68,共4页Computer Engineering

摘　　要：网络应用的发展，要求路由器必须有能力支持防火墙、入侵检测、提供 QoS、流量计费等一系列功能，这些功能都要求路由器对IP包进行分类来完成对数据包的不同处理。目前的包分类算法不适用于大规模的规则数据库。该文在现有的一种基于位串的包分类算法上做了两个改进，位串的聚合和过滤规则的重排列。从而生成了一种新的包分类机制－ABV（Aggregated Bit Vector）。通过评测可看出这种新的算法可以很好地应用在大规模规则数据库上，性能比原先有很大提升。The development of Internet application necessitates routers ability to support those functions such as firewalls, intrusion detection, provision of QoS and traffic billing etc. All these functions need routers need classification of packets, according to which it is determined how different packets are processed subsequently. Existing algorithms for packet classification do not scale to large classifiers. This paper uses the bit vector (BV) scheme as a point of departure and adds two new ideas, aggregation of bit maps and filter rearrangement, to create aggregated bit vector (ABV). We show that ABV outperforms BV and scales well to large classifiers using the experimental results.

关 键 词：包分类 位串聚合 规则重排列 

分 类 号：TP393.04[自动化与计算机技术—计算机应用技术]