基于GPU动态IP查找架构的分析与研究

论文摘要

随着社会信息化步伐的加快,信息通讯的重要性正在逐步突显。作为信息通讯形式之一的网络通讯扮演着重要角色。当前,光纤技术的出现,使得点对点的信息传输速度达到了几百Gbps,这信息传输带宽已经能够满足现在的信息传输量。然而,作为网络中转站的路由器限制了网络的整体速度。目前,实际路由速度才几十个Gbps,远远无法满足信息通讯的带宽要求。因此,研究快速、高效的路由架构及相应的更新算法在路由表的查找、删除、插入/更新等技术中具有重要的意义。本文着力于研究快速、有效的路由架构及对应的算法,主要工作有:1)针对软件路由速度慢和硬件路由扩展性弱、内存小、价格昂贵等缺点,提出一种基于GPU并行多Hash动态IP查找架构。该架构包含两部分,第一部分是Host端与Device端的数据传输,其中包括将CPU预处理的IP数据包头部信息传给GPU和返回处理完后的结果给CPU两部分;第二部分是GPU对IP数据包头部信息的处理。首先,CUDA提供了 Host端与Device端的数据传输模块;另外,我们依据IP地址前缀长度的分布特性对相同长度的IP地址Hash索引后,存储于相应的数组。同时,我们用另外一个表顺序存储冲突的IP地址。在采用Adaptive Optimal XOR Hash函数后,保证冲突率低于1%。这也意味着,该架构结合GPU硬件强大的并行处理能力能够保证99%以上的查找访存度为O(1),从而使得该架构获得十倍于软件路由的查找速度,以及百倍于现有基于GPU路由的更新速度。2)针对上述架构,我们在已有Hash理论的基础上,提出了构造Adaptive Optimal XORHash的理论。该理论基于比特之间的异或操作,统计样本数据比特之间0和1的差值,依据差值进行比特的异或操作达到压缩位数的效果。虽然该算法的时间复杂度是O(n3),但由于规则的更新是线下处理,所以这个时间复杂度可以被接受。实验结果表明,该方法使得IP地址的冲突率低于1%,能够大幅度提高架构的查找速度。3)针对企业的实际工程需求,设计和实现了一个基于GPU并行多Hash路由系统。该系统在转发路由数据包过程中,首先通过CPU预处理IP数据的头部信息,并打包传给GPU,上述架构依据最长前缀匹配算法,找到IP地址所对应的下一跳地址并将结果打包返回给CPU。系统根据结果转发具体的IP数据包。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状及发展趋势
• 1.2.1 研究现状
• 1.2.2 发展趋势
• 1.3 存在的问题与难点
• 1.4 本文研究内容
• 1.5 本文组织结构
• 第2章 路由架构研究综述
• 2.1 路由转发技术
• 2.2 硬件路由转发技术
• 2.2.1 路由器硬件组成部分
• 2.2.2 硬件路由器工作原理
• 2.3 软件路由转发技术
• 2.3.1 路由器算法介绍
• 2.3.2 路由器算法的分析与研究
• 2.4 基于NP的路由转发架构技术
• 2.4.1 硬件NP的介绍
• 2.4.2 基于NP的路由技术的分析与研究
• 2.5 基于GPU技术的路由转发架构技术
• 2.5.1 图形处理器介绍
• 2.5.2 基于GPU路由架构的研究发展情况
• 2.6 本章小结
• 第3章 基于GPU动态IP快速查找算法
• 3.1 网络IP相关术语的介绍
• 3.2 GPU和CUDA简要介绍
• 3.2.1 图形处理器GPU（Graphic Processing Unit）
• 3.2.2 统一计算设备架构CUDA（Compute Unified Device Architecture）
• 3.3 基于GPU动态IP快速查找架构
• 3.3.1 介绍新的基于GPU路由架构
• 3.3.2 适应上述架构的IP查找及更新算法
• 3.4 算法复杂度分析
• 3.5 实验结果
• 3.6 本章小结
• 第4章 基于XOR哈希最优算法
• 4.1 哈希算法
• 4.1.1 XOR哈希算法原理
• 4.1.2 XOR哈希算法分析
• 4.2 基于XOR哈希最优算法
• 4.2.1 基于XOR哈希最优算法原理
• 4.2.2 基于XOR哈希最优算法复杂度分析
• 4.4 实验结果
• 4.5 本章小结
• 第5章 基于GPU动态路由系统的设计与实现
• 5.1 系统概述
• 5.2 系统工作环境
• 5.2.1 系统硬件环境
• 5.2.2 系统软件环境
• 5.3 系统组成及工作流程
• 5.4 系统模块实现
• 5.4.1 获取IP数据包包头部分
• 5.4.2 Device端处理
• 5.4.3 Host端与Device端的传输处理
• 5.4.4 Host端处理
• 5.6 本章小结
• 总结
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文