Efficient Name Lookup Method Based on Hybrid Counting Bloom Filters

Xu Ke; Li Yanbiao; Xie Gaogang; Zhang Dafang

doi:10.7544/issn1000-1239.202111242

Journal of Computer Research and Development > 2023 > 60(5): 1136-1150. > DOI: 10.7544/issn1000-1239.202111242

Xu Ke, Li Yanbiao, Xie Gaogang, Zhang Dafang. Efficient Name Lookup Method Based on Hybrid Counting Bloom Filters[J]. Journal of Computer Research and Development, 2023, 60(5): 1136-1150. DOI: 10.7544/issn1000-1239.202111242

Citation:

PDF (1948 KB)

Efficient Name Lookup Method Based on Hybrid Counting Bloom Filters

Xu Ke^{1, 2,},
Li Yanbiao^{2, 3,},
Xie Gaogang^{2, 3},
Zhang Dafang^1, ,

1.
College of Information Science and Engineering, Hunan University, Changsha 410082
2.
Computer Network Information Center, Chinese Academy of Sciences, Beijing 100083
3.
University of Chinese Academy of Sciences, Beijing 100089

Funds: This work was supported by the National Natural Science Foundation of China (62072430, 61976087).

More Information

Author Bio:
Xu Ke: born in 1992. Master. His main research interests include network system, in-network computation, and data packet computation

Li Yanbiao: born in 1986. PhD. His main research interests include network system, data packet processing algorithms, and routing security

Xie Gaogang: born in 1974. PhD, professor. His main research interests include Internet architecture, data packet processing and forwarding, and Internet measurement

Zhang Dafang: born in 1959. PhD, professor. His main research interests include reliable network and system, information security of networking, and next generation of Internet
Received Date: December 14, 2021
Revised Date: July 06, 2022
Available Online: February 26, 2023

Graphical Abstract

Abstract

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.
- name lookup,
- feature bitmap,
- counting Bloom filter,
- binary search,
- vector packet processing (VPP)

FullText(HTML)

References (44)

References

[1]	Yang Tong, Xie Gaogang, Li Yanbiao, et al. Guarantee IP lookup performance with FIB explosion[C]//Proc of the 38th ACM Conf on SIGCOMM. New York: ACM, 2014: 39−50
[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, 2015, 45(4): 57−70 doi: 10.1145/2829988.2787474
[3]	Huang Jhihyu, Wang Pichung. TCAM-based IP address lookup using longest suffix split[J]. IEEE/ACM Transactions on Networking, 2018, 26(2): 976−989 doi: 10.1109/TNET.2018.2815999
[4]	Zec M, Rizzo L, Mikuc M. DXR: Towards a billion routing lookups per second in software[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(5): 29−36 doi: 10.1145/2378956.2378961
[5]	Eatherton W, Varghese G, Dittia Z. Tree bitmap: Hardware/software IP lookups with incremental updates[J]. ACM SIGCOMM Computer Communication Review, 2004, 34(2): 97−122 doi: 10.1145/997150.997160
[6]	Degermark M, Brodnik A, Carlsson S, et al. Small forwarding tables for fast routing lookups[J]. ACM SIGCOMM Computer Communication Review, 1997, 27(4): 3−14 doi: 10.1145/263109.263133
[7]	Waldvogel M, Varghese G, Turner J, et al. Scalable high speed IP routing lookups[C]//Proc of the 21st ACM Conf on SIGCOMM. New York: ACM, 1997: 25−36
[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, 2020, 8(6): 4081−4104
[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. Piscataway, NJ: IEEE, 2018: 386−392
[10]	Guan Yu, Huang Lemei, Zhang Xinggong, et al. Name-based routing with on-path name lookup in information-centric network[C]//Proc of the 24th IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2018: 1495−1500
[11]	Dilley J, Maggs B, Parikh J, et al. Globally distributed content delivery[J]. IEEE Internet Computing, 2002, 6(5): 50−58 doi: 10.1109/MIC.2002.1036038
[12]	Harahap E, Wijekoon J, Tennekoon R, et al. Router-based request redirection management for a next-generation content distribution network[C/OL]//Proc of the 3rd IEEE Globecom Workshops. Piscataway, NJ: IEEE, 2013[2021-11-10]. https://ieeexplore.ieee.org/abstract/document/6825123
[13]	Dong Lijun, Zhang Dan, Zhang Yanyong, et al. Performance evaluation of content based routing with in-network caching[C]//Proc of the 20th Annual Wireless and Optical Communications Conf. Piscataway, NJ: IEEE, 2011: 43−48
[14]	Abdallah H B H, Louati W. Ftree-CDN: Hybrid CDN and P2P architecture for efficient content distribution[C]//Proc of the 27th Euromicro Int Conf on Parallel, Distributed and Network-Based Processing. Piscataway, NJ: IEEE, 2019: 438−445
[15]	Wang Yi, Zu Yuan, Zhang Ting, et al. Wire speed name lookup: A GPU-based approach[C]//Proc of the 10th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2013: 199−212
[16]	Li Dagang, Li Junmao, Zheng Du. An improved trie-based name lookup scheme for named data networking[C]//Proc of the 21st IEEE Symp on Computers and Communication. Piscataway, NJ: IEEE, 2016: 1294−1296
[17]	Wang Yi, Dai Huichen, Zhang Ting, et al. GPU-accelerated name lookup with component encoding[J]. Computer Networks, 2013, 57(16): 3165−3177 doi: 10.1016/j.comnet.2013.07.006
[18]	Song Tian, Yuan Haowei, Crowley P, et al. Scalable name-based packet forwarding: From millions to billions[C]//Proc of the 2nd ACM Conf on Information-Centric Networking. New York: ACM, 2015: 19−28
[19]	Ghasemi C, Yousefi H, Shin K G, et al. A fast and memory-efficient trie structure for name-based packet forwarding[C]//Proc of the 26th IEEE Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2018: 302−312
[20]	Ghasemi C, Yousefi H, Shin K G, et al. On the granularity of TRIE-based data structures for name lookups and updates[J]. IEEE/ACM Transactions on Networking, 2019, 27(2): 777−789 doi: 10.1109/TNET.2019.2901487
[21]	Byun S H, Lee J, Sul D M, et al. Multi-worker NFD: An NFD-compatible high-speed NDN forwarder[C]//Proc of the 7th ACM Conf on Information-Centric Networking. New York: ACM, 2020: 166−168
[22]	Yuan Haowei, Crowley P. Reliably scalable name prefix lookup [C]//Proc of the 11th ACM/IEEE Symp on Architectures for Networking and Communications Systems. Piscataway, NJ: IEEE, 2015: 111−121
[23]	Wang Yi, Xu Boyang, Tai Dongzhe, et al. Fast name lookup for named data networking[C]//Proc of the 22nd IEEE Int Symp of Quality of Service. Piscataway, NJ: IEEE, 2014: 198−207
[24]	Yuan Haowei, Crowley P. Scalable pending interest table design: From principles to practice[C]//Proc of the 33rd IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 2049−2057
[25]	Dai Huichen, Lu Jianyuan, Wang Yi, et al. BFAST: High-speed and memory-efficient approach for NDN forwarding engine[J]. IEEE/ACM Transactions on Networking, 2016, 25(2): 1235−1248
[26]	Perino D, Varvello M, Linguaglossa L, et al. Caesar: A content router for high-speed forwarding on content names[C]//Proc of the 10th ACM/IEEE Symp on Architectures for Networking and Communications Systems. New York: ACM, 2014: 137−148
[27]	Wang Yi, Pan Tian, Mi Zhian, et al. Namefilter: Achieving fast name lookup with low memory cost via applying two-stage Bloom filters[C]//Proc of the 32nd IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2013: 95−99
[28]	Quan Wei, Xu Changqiao, Vasilakos A V, et al. TB2F: Tree-bitmap and Bloom-filter for a scalable and efficient name lookup in content-centric networking[C]//Proc of the 14th IFIP Networking Conf. Piscataway, NJ: IEEE, 2014: 395−403
[29]	Huang Kun, Wang Zhaohua, Xie Gaogang. Scalable high-speed NDN name lookup[C]//Proc of the 14th Symp on Architectures for Networking and Communications Systems. New York: ACM, 2018: 55−65
[30]	He Dacheng, Zhang Dafang, Xu Ke, et al. A fast and memory-efficient approach to NDN name lookup[J]. China Communications, 2017, 14(10): 61−69 doi: 10.1109/CC.2017.8107632
[31]	Xu Ke, Zhang Dafang, Li Yanbiao. Longest name prefix match on multi-core processor[C]//Proc of the 21st IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2019: 1035−1042
[32]	Kirsch A, Mitzenmacher M. Less hashing, same performance: Building a better Bloom filter[C]//Proc of the 14th European Symp on Algorithms. Berlin: Springer, 2006: 456−467
[33]	Lu Jianyuan, Yang Tong, Wang Yi, et al. One-hashing Bloom filter[C]//Proc of the 23rd IEEE Int Symp on Quality of Service. Piscataway, NJ: IEEE, 2015: 289−298
[34]	Lu Jianyuan, Wan Ying, Li Yang, et al. Ultra-fast Bloom filters using SIMD techniques[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(4): 953−964
[35]	Bender M A, Farach-Colton M, Johnson R, et al. Don't thrash: How to cache your Hash on flash[J]. arXiv preprint, arXiv: 1208.0290, 2012
[36]	Dai Haipeng, Zhong Yuankun, Alex L, et al. Noisy Bloom filters for multi-set membership testing[C]//Proc of the 39th ACM Int Conf on Measurement and Modeling of Computer Science. New York: ACM, 2016: 139−151
[37]	Yang Tong, Alex L, Shahzad M, et al. A shifting framework for set queries[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 3116−3131 doi: 10.1109/TNET.2017.2730227
[38]	Pfaff B, Pettit J, Koponen T, et al. The design and implementation of open vSwitch[C]//Proc of the 12th Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2015: 117−130
[39]	Barach D, Linguaglossa L, Marion D, et al. High-speed software data plane via vectorized packet processing[J]. IEEE Communications Magazine, 2018, 56(12): 97−103 doi: 10.1109/MCOM.2018.1800069
[40]	马潇潇,杨帆,王展,等. 智能网卡综述[J]. 计算机研究与发展,2022,59(1):1−21 doi: 10.7544/issn1000-1239.20200629 Ma Xiaoxiao, Yang Fan, Wang Zhan, et al. Survey on smart network interface card[J]. Journal of Computer Research and Development, 2022, 59(1): 1−21 (in Chinese) doi: 10.7544/issn1000-1239.20200629
[41]	Zhu Wenjun, Li Peng, Luo Baozhou, et al. Research and implementation of high performance traffic processing based on Intel DPDK[C]//Proc of the 9th Int Symp on Parallel Architectures, Algorithms and Programming. Piscataway, NJ: IEEE, 2018: 62−68
[42]	Reddit. Dataset of reddit posts and comments[EB/OL]. (2021-09-08)[2021-11-10]. https://www.reddit.com/r/datasets/comments/la0w4n/dataset_of_reddit_posts_and_comments/
[43]	Appleby A. MurmurHash[CP/OL]. (2011-03-01)[2021-11-10]. https://sites.google.com/site/murmurhash/
[44]	Lameter C. NUMA (non-uniform memory access) an overview: NUMA becomes more common because memory controllers get close to execution units on microprocessors[J]. Queue, 2013, 11(7): 40−51 doi: 10.1145/2508834.2513149

Cited By

Cited by

Periodical cited type(10)

1.	陶蔚，陇盛，刘鑫，胡亚豪，黄金才. 深度学习步长自适应动量优化方法研究综述. 小型微型计算机系统. 2025(02): 257-265 .
2.	张泽东，陇盛，鲍蕾，陶卿. 基于AdaBelief的Heavy-Ball动量方法. 模式识别与人工智能. 2022(02): 106-115 .
3.	陇盛，陶蔚，张泽东，陶卿. 基于AdaGrad的自适应NAG方法及其最优个体收敛性. 软件学报. 2022(04): 1231-1243 .
4.	曲军谊. 基于对偶平均的动量方法研究综述. 计算机与数字工程. 2022(11): 2443-2448 .
5.	曲军谊，鲍蕾，陶卿. 非光滑凸问题投影型对偶平均优化方法的个体收敛性. 模式识别与人工智能. 2021(01): 25-32 .
6.	黄鉴之，陇盛，陶卿. 自适应策略下Heavy-Ball型动量法的最优个体收敛速率. 模式识别与人工智能. 2021(02): 137-145 .
7.	李兴怡，岳洋. 梯度下降算法研究综述. 软件工程. 2020(02): 1-4 .
8.	丁成诚，陶蔚，陶卿. 一种三参数统一化动量方法及其最优收敛速率. 计算机研究与发展. 2020(08): 1571-1580 . 本站查看
9.	鲁淑霞，蔡莲香，张罗幻. 基于动量加速零阶减小方差的鲁棒支持向量机. 计算机工程. 2020(12): 88-95+104 .
10.	黄鉴之，丁成诚，陶蔚，陶卿. 非光滑凸情形Adam型算法的最优个体收敛速率. 智能系统学报. 2020(06): 1140-1146 .