论文部分内容阅读
自因特网兴起以来,其迅猛增长的势头就从未停止,通信链路以吉比特乃至更高的速度进行数据传输己不成问题,而承担网络通讯任务的传统路由器,通常对数据包未加区分尽力而为地转发,这种方式已不能满足网络用户对不同服务的需求。因此路由器需要对数据包进行分类,以提供有差别的网络服务来满足不同的用户需求,包分类技术已成为实现防火墙包过滤、基于策略的路由、虚拟专用网和流量计费等差别服务的基础。由于对每个数据包都要进行分类处理,因此包分类也成为了高速路由器的一个性能瓶颈,如何在可接受的时间和空间复杂度下进行快速的包分类是目前需要解决的一个难题。
本文在研究了目前几种较为典型的基于软件实现的包分类算法基础上,发现RFC(RecursiveFlowClassification)算法是速度较快的包分类算法,但是随着规则集规模的增大,其构建的数据结构消耗的存储空间迅速增大。针对这一问题,本文提出了一种基于存储空间优化的RFC算法——BitmapRFC,以及该算法基于IntelIXP2800网络处理器的优化与实现。BitmapRFC算法根据RFC算法构建的交叉乘积表中元素的分布特征,采用了一种压缩的数据结构,以及能根据交叉乘积表中元素分布特征自动调整数据结构大小的压缩方法,能对RFC算法构建的交叉乘积表进行最大程度的压缩。
BitmapRFC算法的高效实现,离不开IntelIXP2800网络处理器多核多线程体系结构特征的支持。算法在设计思路与实现的过程中,都充分考虑了IntelIXP2800网络处理器诸如多层次存储结构、快速的位操作指令、多种任务划分模式以及访存延迟隐藏等体系结构特征,并基于这些体系结构特征进行了优化。
本文在IntelIXP2800网络处理器上结合种优化措施对BitmapRFC算法进行了仿真实验和分析,验证了BitmapRFC算法的优越性能。仿真结果表明BitmapRFC算法能够消除RFC算法交叉乘积表中60%以上的冗余空间,并且算法在IntelIXP2800网络处理器上消耗较少的资源就能够实现10Gbps的线速分类,同时保持与RFC算法相同的分类效率,具有较高的应用价值。