基于GPU的高性能数据名查找算法的研究与实现

摘要

命名数据网络（Named Data Networking, NDN）是一种面向未来互联网的新型网络架构，旨在颠覆传统TCP/IP网络以地址为核心的通信模型，代之以命名数据作为网络核心，从而在根本上解决传统网络架构在可扩展性、动态性和安全性等方面的问题。在NDN的路由转发过程中，数据名查找是一项核心操作，也是影响NDN数据包转发性能的关键所在。然而，由于NDN数据名结构复杂、长度不定且无理论上限，这使得存储压缩和查找加速成为解决数据名查找问题的关键技术挑战。
　　目前大多数现有数据名查找解决方案都是只针对存储压缩或者查找加速的某一方面进行优化，难以兼顾综合性能。而多对齐迁移数组（Multi-Aligned Transition Array, MATA）另辟蹊径，借助经典的稀疏表压缩策略和图形处理单元（Graphic Processing Unit, GPU）的强大并行计算能力，在实现存储压缩的同时还能保证线速查找。但该方案的存储利用率依然较低。鉴于此，本文在充分了解NDN数据名查找需求以及GPU平台特性的基础上，设计了一种新型数据结构——候选对齐迁移数组（Candidate-Aligned Transition Array, CATA），引入多候选机制配合多个哈希函数来提升存储利用率，从而实现存储的进一步压缩，同时本文也借助了GPU这一并行平台来实现查找加速。对比实验的结果表明，本文的CATA在保证与MATA相同查找速度的同时，存储利用率能提升到90％左右，总存储开销不到其五分之一。
　　此外，考虑到目前对数据名查找算法的验证评估方案都以模拟为主，本文还针对NDN数据包的特殊结构以及CPU-GPU协同加速的一般处理流程，实现了一个高效的数据名查找引擎，并在此基础上进一步实现数据名查找算法的系统级测试。最后，为了验证本文的数据名查找引擎的实际性能，本文还部署了该框架与另一有数据名查找系统实现的G-opt框架的对比实验，实验结果表明本文的数据名查找引擎的整体性能要优于G-opt，在吞吐率上与之相比提高了40%，而延时则下降了15%。

目录

声明

第1章 绪 论

1.1 研究背景及动机

1.2 国内外研究现状

1.3 本文主要工作

1.4 本文组织结构

第2章 数据名查找技术的相关理论概述

2.1 数据名查找技术的主要挑战

2.2 基于前缀树的数据名查找解决方案的介绍

2.3 数据包处理框架的介绍

2.4 本章小结

第3章 一种基于GPU 的高性能数据名查找算法

3.1 引言

3.2 问题分析

3.3 基于GPU的候选对齐迁移数组及其算法

3.4 实验评估

3.5 本章小结

第4章 一种基于CPU-GPU协同处理的数据名查找引擎

4.1 引言

4.2 NDN数据包处理的主要模块

4.3 基于CPU-GPU协同处理的数据名查找引擎

4.4 实验评估

4.5 本章小结

结论

参考文献

附录A 攻读硕士学位期间发表的学术论文

致谢