快速包分类算法研究

论文摘要

包分类是下一代路由器、防火墙等设备的关键技术。包分类算法研究具有十分重要的意义,是目前的热点之一。本文介绍了常用的包分类算法,分析了它们的优缺点。从算法和体系两条主线出发,对包分类问题进行研究。首先,针对多维包分类问题提出一种新的相联存储器结构——MDR-CAM,支持多维范围匹配,其维数的设定具有灵活性。理论分析表明,在该结构上实现包分类,算法时间复杂度为O（1）,空间复杂度为O（n）。然后,针对一个具体应用,提出一种动态多维硬件高速包分类算法。该算法采用决策树作为快速查找的数据结构,每个叶结点存储一组规则,根据叶结点所处决策树层次和最大查找时间要求来确定叶结点最大规则数,从而可界定最坏情况下的分类时间;支持快速更新,借用一个限定长度的双向链表来更新决策树,可减少临时空间;优化决策树并提出存储动态管理策略,适于在FPGA上实现。仿真结果表明,在50MHz的搜索频率下,该算法能够达到每秒处理2.5M个包头的速度,最坏情况下的分类时间Csum=34个时钟,空间复杂度为O（n）。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 包分类问题
• 1.3 包分类算法的评定标准
• 1.4 本文的主要工作
• 第二章 概述
• 2.1 规则集特征概述
• 2.2 算法分类法
• 2.3 穷尽查找
• 2.3.1 线性查找
• 2.3.2 TCAM
• 2.4 决策树
• 2.4.1 Grid-of-Tries
• 2.4.2 EGT
• 2.4.3 HiCuts
• 2.4.4 HyperCuts
• 2.4.5 E-TCAM
• 2.5 分解
• 2.5.1 Parallel BV
• 2.5.2 ABV算法
• 2.5.3 Crossproducting
• 2.5.4 RFC
• 2.6 元组空间
• 2.6.1 元组空间查找和元组剪枝树
• 2.7 高速缓冲技术
• 第三章 MDR-CAM
• 3.1 包分类与范围匹配
• 3.1.1 规则类型
• 3.1.2 范围匹配原理
• 3.2 MDR-CAM结构
• 3.3 性能分析
• 3.4 本章小结
• 第四章 一种动态硬件包分类算法
• 4.1 算法原理
• 4.1.1 决策树结构
• 4.1.2 时间约束
• 4.1.3 优化决策树
• 4.1.4 查找
• 4.2 算法实现
• 4.2.1 存储结构
• 4.2.2 建树与更新
• 4.2.3 存储管理
• 4.2.4 查找
• 4.3 仿真结果
• 4.3.1 算法的空间性能
• 4.3.2 算法的时间性能
• 4.4 本章小结
• 总结与展望
• 致谢
• 参考文献
• 研究成果