Efficient Name Lookup Method Based on Hybrid Counting Bloom Filters

被引:0
作者
Xu K. [1 ,2 ]
Li Y. [2 ,3 ]
Xie G. [2 ,3 ]
Zhang D. [1 ]
机构
[1] College of Information Science and Engineering, Hunan University, Changsha
[2] Computer Network Information Center, Chinese Academy of Sciences, Beijing
[3] University of Chinese Academy of Sciences, Beijing
来源
Jisuanji Yanjiu yu Fazhan/Computer Research and Development | 2023年 / 60卷 / 05期
基金
中国国家自然科学基金;
关键词
binary search; counting Bloom filter; feature bitmap; name lookup; vector packet processing (VPP);
D O I
10.7544/issn1000-1239.202111242
中图分类号
学科分类号
摘要
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. © 2023 Science Press. All rights reserved.
引用
收藏
页码:1136 / 1150
页数:14
相关论文
共 43 条
[1]  
Yang Tong, Xie Gaogang, Li Yanbiao, Et al., Guarantee IP lookup performance with FIB explosion, Proc of the 38th ACM Conf on SIGCOMM, pp. 39-50, (2014)
[2]  
Asai H, Ohara Y., Poptrie: A compressed trie with population count for fast and scalable software IP routing table lookup[J], ACM SIGCOMM Computer Communication Review, 45, 4, pp. 57-70, (2015)
[3]  
Jhihyu Huang, Pichung Wang, TCAM-based IP address lookup using longest suffix split[J], IEEE/ACM Transactions on Networking, 26, 2, pp. 976-989, (2018)
[4]  
Zec M, Rizzo L, Mikuc M., DXR: Towards a billion routing lookups per second in software[J], ACM SIGCOMM Computer Communication Review, 42, 5, pp. 29-36, (2012)
[5]  
Eatherton W, Varghese G, Dittia Z., Tree bitmap: Hardware/software IP lookups with incremental updates[J], ACM SIGCOMM Computer Communication Review, 34, 2, pp. 97-122, (2004)
[6]  
Degermark M, Brodnik A, Carlsson S, Et al., Small forwarding tables for fast routing lookups[J], ACM SIGCOMM Computer Communication Review, 27, 4, pp. 3-14, (1997)
[7]  
Waldvogel M, Varghese G, Turner J, Et al., Scalable high speed IP routing lookups[C], Proc of the 21st ACM Conf on SIGCOMM, pp. 25-36, (1997)
[8]  
Serhane O, Yahyaoui K, Nour B, Et al., A survey of ICN content naming and in-network caching in 5G and beyond networks[J], IEEE Internet of Things Journal, 8, 6, pp. 4081-4104, (2020)
[9]  
Li Jiawei, Luo Hongbin, Jin Mingshuang, Et al., Solving selfish routing in route-by-name information-centric network architectures[C], Proc of the 19th IEEE Global Communications Conf, pp. 386-392, (2018)
[10]  
Guan Yu, Huang Lemei, Zhang Xinggong, Et al., Name-based routing with on-path name lookup in information-centric network, Proc of the 24th IEEE Int Conf on Communications, pp. 1495-1500, (2018)