一种基于流的局部特性和多级查找的高效包分类算法

An Efficient Packet Classification Based on the Local Properties and Multi-level Lookup

包分类技术是路由器和防火墙等网络设备的关键技术.在高速网络环境中,快速、准确地将数据包进行分类对于网络发展具有重要意义.提出一种基于流的局部特性和多级查找的高效包分类算法,同时可以支持规则库动态更新,实现快速包分类.该算法分为三级结构,第一级缓存用于存放最近10秒内到达的流,第二级计数布鲁姆过滤器存放最近10秒至60秒内到达的流,第三级计数布鲁姆过滤器存放剩余的流.实验表明:该算法比传统的包分类算法,在消耗内存接近的情况下具有更好的时间性能.

Packet classification is one of key technologies, which is frequently utilized in those network devices, such as routes, fire-walls, and so on. In such high-speed network environment, the efficiency and accuracy of packet classification plays a significant role in the development of network. In this paper, we propose an efficient packet classification algorithm based on the flow local properties and multi-level lookup { PCFM ）, which can support dynamic update of rule base, achieve high-speed packet classification. The struc- ture of this classification is divided into three levels： The first level is used to store the flow which arrived within 10 seconds, while the second for that arriving between 10 seconds to 60 seconds and the third level for the rest. Experiment results show that PCFM al- gorithm has better time performance while taking the same memory space with comparison to the traditional algorithm.