高级检索

    基于混合计数布隆过滤器的高效数据名查找方法

    Efficient Name Lookup Method Based on Hybrid Counting Bloom Filters

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

       

      Abstract: Name lookup is a key operation in fundamental building blocks of information-centric networking, content delivery network, as well as the user plane function of 5G core network. It is required to deal with the longest prefix matching with a large-scale rule table, and thus confronts with serious challenges on lookup speed, update overhead and memory cost. In this paper, we design the hybrid counting Bloom filter (HyCBF) that maintains name prefixes and prefix markers within a single counting Bloom filter, while keeping them logically separated. This offers more guidance information without additional memory cost and time overhead. On this basis, we propose a HyCBF-assisted binary search (HyBS) scheme for efficient name lookup. Further, to mitigate the performance loss caused by backtracking operation during the binary search, we associate each unit of the HyCBF with a feature bitmap so as to reduce its false positive rate. Our extensive evaluations show that HyBS outperforms the state-of-the-art approaches in terms of lookup performance, update speed, as well as memory efficiency. In addition, we integrate HyBS into the vector packet processing (VPP) platform to evaluate its performance in terms of system implementation. The experimental results clearly demonstrate their potential to build a high throughput and scalable name lookup engine.

       

    /

    返回文章
    返回