基于GPU的高性能包分类技术的研究与实现

摘要

随着网络规模不断扩大，网络业务也急剧增加。互联网的性能已经难以满足日益增长的需求。数据包分类作为路由器、交换机等网络设备的核心功能，需要解决五元组规则匹配的问题，在一定程度上决定了网络包处理的吞吐率，进而影响整体网络性能。另一方面，在未来互联网架构的典型代表软件定义网络(SDN)中，数据平面需解决的核心问题是OpenFlow流表查找。其本质依然是数据包分类，只是域更多，规则更多，更新更频繁而已。因此，实现高性能的、灵活可扩展的包分类技术已经成为一个具有实际意义并且非常具有挑战性的问题。
　　本文着眼于数据包分类这一网络包处理的核心问题，重点研究CPU/GPU协处理架构下的算法和结合优化，取得了一定的成果。
　　首先，从经典包分类算法HiCuts入手，探索GPU加速包分类算法需解决的一般性问题。同时，通过引入高性能的包输入输出框架Netmap，本文搭建了一个简易的CPU/GPU协同包处理框架，实现端到端性能实测。实验结果表明，GPU加速可显著提升HiCuts的性能，但离线速处理还有较大的差距。这是因为HiCuts算法并未能充分利用GPU的硬件特点。因此，本文进一步结合GPU的并行机理及访存特性设计了一种新型的基于比特位图合并的包分类算法，并在算法的实现过程中充分利用CUDA平台来实现细节优化。实测结果表明，该算法相比于HiCuts，在GPU平台上能实现2.3倍至9.5倍的加速。最后，本文结合OpenFlow流表查找的需求和GPU的硬件特点设计并实现了一种基于比特分割的树形结构及相应的分类算法。初步实验表明，该算法不仅适用于多维度、大规模规则集的场景，并且支持高频率的规则集更新操作。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及意义

1．2 数据包分类概述

1．2．1 传统数据包分类问题

1．2．2 OpenFlow流表查询问题

1．3 本文的组织结构

第2章 包分类技术国内外研究现状

2．1 基于通用CPU平台的解决方案

2．1．1 基于树形结构的多维规则匹配算法

2．1．2 RFC算法

2．1．3 基于布鲁姆过滤器的包分类算法

2．1．4 元组空间算法

2．2 基于硬件的解决方案

2．2．1 基于FPGA的解决方案

2．2．2 基于TCAM的解决方案

2．3 基于GPU的解决方案

2．4 OpenFlow中的包分类方案

2．4．1 多核CPU的解决方案

2．4．2 GFlow

2．4．3 Bloom Search

2．5 本章小结

第3章 GPU加速HiCuts算法

3．1 背景知识

3．1．1 HiCuts算法

3．1．2 Netmap

3．1．3 CUDA

3．1．4 ClassBench

3．2 在GPU上执行HiCuts

3．3 平台部署

3．4 实验评估

3．4．1 数据集

3．4．2 CPU和GPU执行HiCuts的性能对比

3．4．3 不同的CUDA配置下的吞吐率

3．4．4 存储空间的使用量

3．5 本章小结

第4章 比特位图合并算法

4．1 GPU的硬件特点及优化

4．1．1 全局存储器的合并访存

4．1．2 常量存储器

4．1．3 简化线程逻辑

4．1．4 多流优化

4．2 算法思想

4．2．1 CPU预处理操作

4．2．2 GPU执行包分类操作

4．2．3 GPU线程并行处理策略

4．3 实验验证

4．3．1 预处理时间

4．3．2 与HiCuts的性能对比

4．4 本章小结

第5章 基于比特划分树的包分类算法

5．1 比特划分树

5．2 流表查询操作

5．3 更新操作

5．3．1 插入规则

5．3．2 删除规则

5．4 在GPU上实现BSTree

5．5 实验验证

5．5．1 查询性能

5．5．2 更新性能

5．6 本章小结

结论

参考文献

致谢

附录A 发表论文和参加科研情况说明