论文部分内容阅读
随着网络技术的飞速发展以及网络应用的层出不穷,互联网用户对网络服务的可靠性、安全性、多样性都提出了更深层次的要求。路由器需要提供有差别的网络服务才能满足不同用户的需求,如包过滤防火墙、流量计费、流量控制、区分服务、QoS等。为了支撑这些新型的网络服务,传统的单独依据目标地址进行匹配的单维包分类算法已经不能满足多样化的网络新需求,路由器需要根据数据包头的多个域对数据进行分类处理,例如数据报文的5元组(源IP地址、目的IP地址、源端口、目的端口、协议)。研究表明,Internet持续迅猛的发展对多维包分类算法提出越来越高的性能要求,不仅要求匹配速度快、空间占用少,且对算法动态更新及扩展性能也有高的要求。研究高性能的多维包分类算法是大规模高速网络发展的必然要求。本文提出两种高性能的多维包分类算法,一种属于软件范畴,一种属于硬件范畴,如下所述:软件算法方面,提出一种基于元组空间的高性能二维包分类算法TB(Joint Tuple Space and Bitmap),该算法从维度分解思想出发,联合元组空间和位图设计并实现。TB算法首先分别对源IP和目的IP进行单维匹配后,运用交叉组合思想形成访问元组空间的路线,并通过位图过滤技术进一步减少访问元组空间的个数。相比传统的元组空间算法,TB算法结构清晰简洁易于实现,时间和空间性能较为优越,规则库更新较易,且算法扩展性能较好。实验证明,TB算法平均访问内存次数低于元组空间代表算法RSFR约26.6%,空间性能平均低于RSFR算法35.1%。硬件算法方面,提出一种基于计数布鲁姆过滤器的快速多维包分类算法CBHT(Counting Bloom filter and Hash Table),该算法从数据包匹配规则的聚集特性出发,结合计数布鲁姆过滤器和哈希表设计并实现。基于聚集特性,对于五维包分类问题,CBHT算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集,而后在此有限规则集中对后三维进行匹配。CBHT运用数据包匹配的聚集特性对传统的硬件算法结构进行改进,同时通过计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新。在斯坦福大学的PALAC实验平台中对CBHT算法进行仿真实验,实验结果表明CBHT算法较其它算法匹配速度快,占用硬件资源少,并有效的支持了规则库动态更新。