Compact RFC:一种内存优化的RFC包分类算法  

Compact RFC: a Memory-optimized RFC Packet Classification Algorithm

作　　者：刘铎[1] 华蓓[1] 唐锡南 胡向辉[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系 [2]英特尔编译器实验室

出　　处：《小型微型计算机系统》2007年第3期482-487,共6页Journal of Chinese Computer Systems

基　　金：IntelIXA大学计划项目资助.

摘　　要：RFC(Recursive Flow Classification)算法是目前速度较快的基于软件实现的多维包分类算法,但是随着规则集规模的增大,其消耗的内存空间迅速增大.针对这一问题,本文提出了一种基于内存优化的RFC算法-Compact RFC,该算法根据RFC算法构建的交叉乘积表中元素的分布特点设计出了一种压缩的数据结构及压缩方法,能够消除RFC交叉乘积表中60%以上的冗余空间,并且仍然保持与RFC算法相同的时间复杂度.本文在Intel IXP2800网络处理器上实现了RFC和Compact RFC,验证了Compact RFC的优越性能,实验同时表明Compact RFC在Intel IXP2800上消耗较少的资源就能够达到OC-192(10Gbps)的分类速度,具有较高的应用价值.Among software-based multi-dimensional packet classification algorithms, RFC （Recursive Flow Classification） has the reputation of high efficiency, but it also has the shortcoming of incurring excessive memory consumption with the expansion of filter sets. Therefore, Compact RFC, a memory optimized RFC is proposed in this paper. Designing a compact data structure and compression method according to the distribution characteristics of the data in the cross-producting tables RFC constructs, it can reduce the memory redundancy up to 60 % while retaining the same time complexity with RFC. The implementation of both algorithms on Intel IXP2800 has demonstrated the outstanding performance of compact RFC as well as its resource efficiency when achieving OC-192 （10Gbps） classification speed, thus ensures its applicability.

关 键 词：包分类 RFC算法 网络处理器 

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