| 基于混合计数布隆过滤器的高效数据名查找方法 |
| |
| 作者姓名： | 许可 李彦彪 谢高岗 张大方 |
| |
| 作者单位： | 1. 湖南大学信息科学与工程学院;2. 中国科学院计算机网络信息中心;3. 中国科学院大学 |
| |
| 基金项目： | 国家自然科学基金项目（62072430,61976087）~~； |
| |
| 摘 要： | 数据名查找是信息中心网络、内容分发网络、5G核心网中基础功能组件的关键操作，需要面向大规模规则表进行最长前缀匹配，在查找速度、更新开销和存储开销等方面面临严峻挑战.首先设计了混合计数布隆过滤器（HyCBF），将数据名前缀和前缀标记维护在同一个计数布隆过滤器中同时保持二者的逻辑独立性.这样可在不增加额外存储开销和时间开销的情况下提供更丰富的指示信息.基于此，提出HyCBF辅助的二分数据名查找（HyBS）方法以实现高效查找.进一步，为缓解二分查找过程中因回溯导致的性能损失，为HyCBF中每个条目关联一个特征比特位图以降低其假阳性率.实验表明，HyBS相比现有方法在查找性能和更新速度方面具有明显优势，存储效率也有一定提升.此外，将HyBS集成到向量化数据包处理（VPP）框架中进行系统性能评估，结果表明HyBS可用于构建高通量可扩展的数据名查找引擎.
|
| 关 键 词： | 数据名查找 特征比特位图 计数布隆过滤器 二分搜索 向量化数据包处理 |
|
