论文部分内容阅读
包分类技术作为互联网中支持多业务服务能力的关键技术一直是研究人员关注的研究课题.网络处理器由于结合了通用处理器的低成本、灵活性以及专用集成电路(ASIC)的高效率的特点使其成为目前构建网络设备的基本组件.因此,研究与网络处理器体系结构相适应的快速包分类算法具有很重要的意义.本文从网络处理器TinyNP系统的体系结构特点出发,对适用于对称多处理器体系结构的网络处理器的快速包分类技术进行了深入研究,从提高快速查找性能和降低成本的角度入手,提出了两种新的快速包分类算法,并研究了使用包分类技术加速路由查找的算法.本文的创新点如下:
1.提出了一种基于子元组划分的包分类算法-STS算法.该算法从元组空间入手,提出了新的元组划分准则.这种划分准则,能够有效的将原来不具备匹配规则定位性的元组空间转化为具有定位性的子元组空间.这种定位性能够有效地减少查找匹配规则所需要的哈希查找的次数,因此避免了同类(元组空间)算法因哈希查找次数的不确定性带来的性能不稳定现象.实验采用了根据真实规则集统计规律生成的二维规则集,实验结果显示,STS算法的关键操作(哈希查找)次数明显少于其它同类算法,平均查找性能可提高28﹪以上.
2.提出了一种基于最大前缀长度的位向量包分类算法-MPLBV算法.该算法的最大特点是算法的查找性能不受规则集规模大小的影响,只与所使用的规则集里的规则前缀的最大长度有关.这个特点使得算法能够根据需要达到的查找性能调整性能参数,具有一定程度的查找性能的可控性.实验采用了根据真实规则集统计规律生成的大规模规则集,实验表明所提出算法的查找性能比同类算法提高一倍以上.
3.提出了一种基于包分类算法的快速路由查找算法.对于采用前缀匹配的适用于大规模路由表的快速路由查找算法,其性能大多数与前缀长度有着紧密联系.本文给出了一种使用包分类技术来加速路由查找的新算法.在这个算法下,用于路由查找的路由表被转化为用于包分类的规则集,并使用快速包分类算法-MPLBV算法用于路由查找.该算法能够有效地提高路由查找的速度.仿真实验结果表明,这种策略能够将路由查找的速度提高至少23﹪.