基于FPGA的高速流分类算法研究

论文摘要

随着Internet的不断发展,英特网提供商(ISP)希望网络能提供更多、更好的服务,如Qos保障、防火墙、虚拟专用网络(VPN)等。虽然这些服务的种类繁多,但所有这些服务都要求路由器能够对包头进行分类处理,而相关的规则查找技术即为流分类算法。本文首先简单介绍了国内外现有的部分研究成果,并在剖析Hicuts算法的基础上,结合RFC算法提出了一种适合FPGA实现的实用高速流分类算法。算法根据规则集的特征,在可用空间资源受限的前提下,给出了一种优化的建树方法。提出了流水线方式和主从并行方式的查找策略,提高了查找效率。测试结果表明,在同等规模的规则集下,相比HiCuts算法在空间上具有显著优势,而且算法达到3Mpps的分类速度。在文章末,利用自顶向下的设计方法完成了各模块的划分以及功能定义,并给出了算法实现的FPGA设计结构。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 背景介绍
• 1.2 研究现状
• 1.3 问题描述
• 第二章 相关算法研究及性能分析
• 2.1 基本数据结构算法
• 2.1.1 线性查找（Linear Search）
• 2.1.2 一维树结构（Radix trie）
• 2.1.3 分层树结构（Hierarchical Tries）
• 2.1.4 集合剪枝树（Set-Pruning Tries）
• 2.1.5 格栅树结构（Grid-of-tries）
• 2.2 基于计算几何算法
• 2.2.1 交叉乘积（Crossproducting）
• 2.2.2 AQT（Area-based quadtree）
• 2.2.3 FIS-树（Fat Inverted Segment Tree）
• 2.3 启发式算法
• 2.3.1 TSS（Tuple space search）
• 2.3.2 Tuple Pruning Algorithm
• 2.3.3 RFC（Recursive Flow Classification）
• 2.3.4 HiCuts（Hierarchical Intelligent Cuttings）
• 2.4 硬件算法
• 2.4.1 TCAM
• 2.4.2 位图交集（Bitmap-intersection）
• 2.5 各种算法性能分析比较
• 2.6 本章小结
• 第三章 改进的HICUTS算法
• 3.1 算法描述
• 3.2 数据结构的设计
• 3.2.1 决策树
• 3.2.2 树结点结构
• 3.2.3 叶结点规则集
• 3.3 算法优化
• 3.3.1 删除冗余的结点
• 3.3.2 叶结点规则集排序
• 3.3.3 规则的存储形式
• 3.4 处理通配规则
• 3.5 查找
• 3.5.1 流水线方式
• 3.5.2 主从并行方式
• 3.5.3 查找性能分析
• 3.6 性能评估
• 3.7 算法仿真及数据分析
• 3.7.1 测试环境
• 3.7.2 测试规则
• 3.7.3 测试结果
• 3.8 本章小结
• 第四章 算法的FPGA实现
• 4.1 FPGA简介
• 4.2 FPGA开发流程
• 4.3 FPGA系统设计
• 4.4 算法实现的模块划分
• 4.4.1 顶层模块定义
• 4.4.2 建树模块
• 4.4.3 通配规则处理模块
• 4.4.4 更新模块
• 4.4.5 查找模块
• 4.5 存储映射
• 4.5.1 片外RAM
• 4.5.2 片内RAM
• 4.6 FPGA的实现结构
• 4.7 本章小结
• 第五章 总结与展望
• 致谢
• 参考文献
• 研究成果