学位论文简介

目前，对于互联网用户和应用而言，对于数据内容的关注程度已经远胜于数据位置，因此涌现出诸多基于数据内容的网络应用和架构设计。在这样一种以数据内容为核心的新型互联网设计理念下，基于数据内容的路由查找和模式匹配是影响网络性能的两大重要关键技术，而如今这两项关键技术难以平衡匹配速度、存储开销和更新性能。为此，本文从算法设计和异构协同加速设计两个角度，展开如下几点工作：

（1）在数据名查找中的二分搜索结合Bloom过滤器方案的基础之上，分析了Bloom过滤器查询时过多的哈希计算带来的时间开销较大的缺点，提出了一种利用多核加速的查找方法。基于二分搜索的数据名查找算法会将前缀分长度保存于不同的哈希表中，并而构建成基于前缀长度的二分搜索树的结构，每个树节点都对应着一组特定长度的前缀规则集。每个树节点上的处理过程都分为Bloom过滤器查询和哈希表查找两个阶段，对于Bloom过滤器查询阶段采用多核任务并行的方式加速，对于哈希表查找则采用多核数据并行的方式加速，在不增加额外存储开销的情况下，实现算法加速的效果。

（2）从数据结构和算法设计的角度进行提出了一种数据名查找算法。本文分析了Bloom过滤器固有的假阳性问题对查找性能的不利影响，提出了一种混合计数Bloom过滤器数据结构，并基于此结构对二分搜索过程进行了优化设计。此外，还针对二分搜索的规则特点提出了一种快速更新算法。本文还将算法集成到了开源数据包处理平台上，实现了算法的系统部署。

（3）针对的问题是多数据名模式匹配（MNPM）问题，在分析了传统多模式匹配存在的不足，针对数据名组件化的结构特点，基于后缀筛选的思想，以哈希表为基础数据结构设计出一套高效的多数据名模式匹配算法。该算法支持动态更新和快速构建，具有快速匹配和低存储开销的特点。

（4）在分析了数据名查找过程中对组件编码和组件过滤的依赖性的基础上，结合可编程交换机和通用服务器，利用可编程ASIC和通用处理器构建异构协同加速系统，针对数据名查找算法进行功能拆解，有选择性地将其中重要功能卸载到可编程交换机中，进而实现了数据名查找的加速。

主要学术成果

学术论文：

[1] 许可, 李彦彪, 谢高岗, 张大方. 基于混合计数布隆过滤器的高效数据名查找方法[J]. 计算机研究与发展, 2023, 60(5):1136-1150. (CCF-A类中文期刊，第一作者，已发表)

[2] Ke Xu, Dafang Zhang, Yanbiao Li. Longest name prefix match on multi-core processor[C]. International Conference on High Performance Computing and Communications, Zhangjiajie, China, 2019:1035-1042. (CCF-C类会议，第一作者，已发表)

[3] Ke Xu, Donghong Jiang, Yanbiao Li, et al. MaP: Increasing Node Capacity of Programmable Cloud Gateways. Computer Networks. (CCF-B类期刊，第一作者，Major revision)

[4] Zhuoran Ma, Yanbiao Li, Xinyi Zhang, Ke Xu, Dafang Zhang. MLH-NRF: Enhancing 5G Core Network Scalability and Efficiency through a Multi-Layer Hash NRF. Asia-Pacific Workshop on Networking, Sydney, Australia, 2024.（CCF-C类会议，第四作者，投稿中）

发明专利：

[1] 李彦彪, 谢高岗, 许可. 一种针对GPU加速多步长前缀树的更新序列维护方法：中国，ZL2020111595353.2[P]. 2020-12-29. (已授权)

[2] 许可, 李彦彪, 谢高岗，张大方. 一种用于数据名匹配的多模式匹配方法：中国，202311109724.5. 2023-12-5. (实审)