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

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

作　　者：陈胜[1] 张大方[1] 毕夏安[2] 

机构地区：[1]湖南大学信息与科学工程学院,长沙410082 [2]湖南师范大学数学与计算机科学学院,长沙410081

出　　处：《小型微型计算机系统》2013年第11期2499-2503,共5页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2012CB315801)资助;国家自然科学基金项目(61173167)资助

摘　　要：包分类技术是路由器和防火墙等网络设备的关键技术.在高速网络环境中,快速、准确地将数据包进行分类对于网络发展具有重要意义.提出一种基于流的局部特性和多级查找的高效包分类算法,同时可以支持规则库动态更新,实现快速包分类.该算法分为三级结构,第一级缓存用于存放最近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.

关 键 词：包分类 多级查找 布鲁姆过滤器 流局部特性 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]