Routing lookup algorithm with variable-length address based on AVL tree and Bloom filter

doi:10.11772/j.issn.1001-9081.2022121915

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (12): 3882-3889.DOI: 10.11772/j.issn.1001-9081.2022121915

Special Issue: 网络与通信

• Network and communications • Previous Articles Next Articles

Routing lookup algorithm with variable-length address based on AVL tree and Bloom filter

Yongjin HUANG¹^,², Yifang QIN¹(), Xu ZHOU¹, Xinqing ZHANG¹^,²

^1.Computer Network Information Center，Chinese Academy of Sciences，Beijing 100083，China
^2.University of Chinese Academy of Sciences，Beijing 100049，China

Received:2023-01-04 Revised:2023-03-08 Accepted:2023-03-09 Online:2023-03-30 Published:2023-12-10
Contact: Yifang QIN
About author:HUANG Yongjin， born in 1996， M. S. candidate. His research interests include future network system.
ZHOU Xu， born in 1976， Ph. D.， research fellow. His research interests include future network architecture， new generation wireless network.
ZHANG Xinqing， born in 1999， M. S. candidate. Her research interests include future network system.
Supported by:
Project of Beijing Municipal Science and Technology Plan(Z191100007519007);Fund of Youth Innovation Promotion Association of Chinese Academy of Sciences(2020175)

基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法

黄永锦¹^,², 覃毅芳¹(), 周旭¹, 张心晴¹^,²

^1.中国科学院计算机网络信息中心，北京 100083
^2.中国科学院大学，北京 100049

通讯作者: 覃毅芳
作者简介:黄永锦（1996—），男，广西南宁人，硕士研究生，主要研究方向：未来网络系统
覃毅芳（1984—），男，广西河池人，高级工程师，博士，主要研究方向：未来网络架构、5G移动通信；Email：qinyifang@cnic.cn
周旭（1976—），男，四川成都人，研究员，博士生导师，博士，CCF会员，主要研究方向：未来网络架构、新一代无线网络
张心晴（1999—），女，山西阳泉人，硕士研究生，主要研究方向：未来网络系统。
基金资助:
北京市科技计划项目(Z191100007519007);中国科学院青年创新促进会基金资助项目(2020175)

Abstract

Abstract:

The variable-length address is one of the important research content in the field of future network. Aiming at the low efficiency of traditional routing lookup algorithms for variable-length address， an efficient routing lookup algorithm suitable for variable-length addresses based on balanced binary tree — AVL （Adelson-Velskii and Landis） tree and Bloom filter， namely AVL-Bloom algorithm， was proposed. Firstly， multiple off-chip hash tables were used to separately store route entries with the same number of prefix bits and their next-hop information in view of the flexible and unbounded characteristics of the variable-length address. Meanwhile， the on-chip Bloom filter was utilized for speeding up the search for route prefixes that were likely to match. Secondly， in order to solve the problem that the routing lookup algorithms based on hash technology need multiple hash comparisons when searching for the route with the longest prefix， the AVL tree technology was introduced， that was， the Bloom filter and hash table of each group of route prefix set were organized through AVL tree， so as to optimize the query order of route prefix length and reduce the number of hash calculations and then decrease the search time. Finally， comparative experiments of the proposed algorithm with the traditional routing lookup algorithms such as METrie （Multi-Entrance-Trie） and COBF （Controlled prefix and One-hashing Bloom Filter） were conducted on three different variable-length address datasets. Experimental results show that the search speed of AVL-Bloom algorithm is significantly faster than those of METrie and COBF algorithms， and the query time is reduced by nearly 83% and 64% respectively. At the same time， AVL-Bloom algorithm can maintain stable search performance under the condition of large change in routing table entries， and is suitable for routing lookup and forwarding with variable-length addresses.

Key words: variable-length address, routing lookup, Adelson-Velskii and Landis (AVL) tree, Bloom filter, hash algorithm

摘要：

可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题，提出一种基于平衡二叉树AVL（Adelson-Velskii and Landis）树和Bloom过滤器的适用于可变长地址的高效路由查找算法，简称为AVL-Bloom算法。首先，针对可变长地址灵活可变且无界的特点，利用多个片外哈希表分别存储前缀比特位数相同的路由条目及其下一跳信息，同时应用片上Bloom过滤器加速搜索可能匹配的路由前缀；其次，为了解决基于哈希技术的路由查找算法在查找最长前缀路由时需多次哈希对比的问题，引入AVL树技术，即通过AVL树组织每组路由前缀集合的Bloom过滤器及其哈希表，优化路由前缀长度的查询顺序，并减少哈希计算次数进而降低查询时间；最后，在3种不同的可变长地址数据集上将所提算法与METrie（Multi-Entrance-Trie）和COBF（Controlled prefix and One-hashing Bloom Filter）这两种传统路由查找算法进行对比实验。实验结果表明，AVL-Bloom算法的查询时间明显少于METrie和COBF算法，分别减少了将近83%和64%；同时，AVL-Bloom算法在路由表项数变化较大的情况下也能维持稳定的查找性能，适用于可变长地址的路由查找转发。

关键词: 可变长地址, 路由查找, AVL树, Bloom过滤器, 哈希算法

CLC Number:

TP393.05

Yongjin HUANG, Yifang QIN, Xu ZHOU, Xinqing ZHANG. Routing lookup algorithm with variable-length address based on AVL tree and Bloom filter[J]. Journal of Computer Applications, 2023, 43(12): 3882-3889.

黄永锦, 覃毅芳, 周旭, 张心晴. 基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3882-3889.

Figures/Tables 7

Fig.1 Structure of AVL-Bloom algorithm

Fig.2 Lookup process of AVL-Bloom

Fig.3 Inserting process of AVL-Bloom

Fig.4 Deleting process of AVL-Bloom

Fig. 5 Comparison of query time among different algorithms

Fig. 6 Comparison of memory overhead among different algorithms

Fig.7 Comparison of hash time between COBF and AVL-Bloom

References 17

1	周旭，蒋胜，张杰，等. 泛在IP协议体系［J］. 电信科学， 2021， 37（10）：47-54. 10.11959/j.issn.1000-0801.2021237
	ZHOU X， JIANG S， ZHANG J， et al. Ubiquitous IP protocol system［J］. Telecommunications Science，2021，37（10）：47-54. 10.11959/j.issn.1000-0801.2021237
2	TANG J， ZHANG W， GONG X， et al. A flexible hierarchical network architecture with variable-length IP address［C］// Proceedings of the IEEE INFOCOM 2020 — IEEE Conference on Computer Communications Workshops. Piscataway： IEEE， 2020：267-272. 10.1109/infocomwkshps50562.2020.9162703
3	郑秀丽，蒋胜，王闯. NewIP：开拓未来数据网络的新连接和新能力［J］.电信科学，2019，35（9）：2-11.
	ZHENG X L， JIANG S， WANG C. NewIP： new connectivity and capabilities of upgrading future data network［J］. Telecommunications Science， 2019，35（9）： 2-11.
4	CHEN Z， WANG C， LI G， et al. New IP framework and protocol for future applications ［C］// Proceedings of the NOMS 2020-2020 IEEE/IFIP Network Operations and Management Symposium. Piscataway： IEEE， 2020： 1-5. 10.1109/noms47738.2020.9110352
5	ASAI H， OHARA Y. Poptrie： a compressed trie with population count for fast and scalable software IP routing table lookup ［C］// Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York： ACM， 2015：57-70. 10.1145/2785956.2787474
6	YANG T， XIE G， LI Y， et al. Guarantee IP lookup performance with FIB explosion ［C］// Proceedings of the 2014 ACM Conference on SIGCOMM. New York： ACM， 2014：39-50. 10.1145/2619239.2626297
7	HUANG J-Y， WANG P-C. TCAM-based IP address lookup using longest suffix split［J］. IEEE/ACM Transactions on Networking， 2018， 26（2）： 976-989. 10.1109/tnet.2018.2815999
8	SUN Y， LIU H， KIM M S. Using TCAM efficiently for IP route lookup［C］// Proceedings of the 2011 IEEE Consumer Communications and Networking Conference. Piscataway： IEEE， 2011： 816-817. 10.1109/ccnc.2011.5766609
9	LE H， PRASANNA V K. Scalable high throughput and power efficient IP lookup on FPGA［C］// Proceedings of the 2009 17th IEEE Symposium on Field Programmable Custom Computing Machines. Piscataway： IEEE， 2009：167-174. 10.1109/fccm.2009.42
10	REN S， YU D， LI G， et al. Routing and addressing with length variable IP address ［C］// Proceedings of the ACM SIGCOMM 2019 Workshop on Networking for Emerging Applications and Technologies. New York： ACM， 2019：43-48. 10.1145/3341558.3342204
11	LIU S， LUO W， ZHOU X， et al. OBF： a guaranteed IP lookup performance scheme for flexible IP using one bloom filter ［C］// Proceedings of 2021 IEEE 29th International Conference on Network Protocols. Piscataway： IEEE， 2021：1-6. 10.1109/icnp52444.2021.9651925
12	LIU S， LUO W， ZHOU X， et al. An efficient addressing scheme for flexible IP address［C］// Proceedings of the 2021 2nd International Conference on Control， Robotics and Intelligent System. New York： ACM， 2021：111-116. 10.1145/3483845.3483865
13	SO W， NARAYANAN A， ORAN D， et al. Toward fast NDN software forwarding lookup engine based on hash tables［C］// Proceedings of 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. New York： ACM， 2012：85-86. 10.1145/2396556.2396575
14	WALDVOGEL M， VARGHESE G， TURNER J， et al. Scalable high speed IP routing lookups［C］// Proceedings of the ACM SIGCOMM’97 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 1997：25-36. 10.1145/263105.263136
15	ZHANG C， XIE G. Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network［J］. Computer Communications， 2022， 181： 438-445. 10.1016/j.comcom.2021.10.027
16	SHI S， QIAN C. Ludo hashing： compact， fast， and dynamic key-value lookups for practical network systems［J］. ACM SIGMETRICS Performance Evaluation Review， 2020， 48（1）：57-58. 10.1145/3410048.3410081
17	SRINIVASAN V， VARGHESE G. Faster IP lookups using controlled prefix expansion ［J］. ACM SIGMETRICS Performance Evaluation Review， 1998， 26（1）：1-10. 10.1145/277858.277863

[1]	Li LI, Chunyan YANG, Jiangwen ZHU, Ronglei HU. User plagiarism identification scheme in social network under blockchain [J]. Journal of Computer Applications, 2024, 44(1): 242-251.
[2]	Jing ZHANG, He TIAN, Kun XIONG, Yongli TANG, Li YANG. Fair multi-party private set intersection protocol based on cloud server [J]. Journal of Computer Applications, 2023, 43(9): 2806-2811.
[3]	Wendi HUA, Yuan GAO, Meng LYU, Ping XIE. Research on Bloom filter： a survey [J]. Journal of Computer Applications, 2022, 42(6): 1729-1747.
[4]	YANG Su, OUYANG Zhi, DU Nisuo. Unsupervised parallel hash image retrieval based on correlation distance [J]. Journal of Computer Applications, 2021, 41(7): 1902-1907.
[5]	Ruliang XIAO, Zhixia ZENG, Chenkai XIAO, Shi ZHANG. IIoT hidden anomaly detection based on locality sensitive Bloom filter [J]. Journal of Computer Applications, 2021, 41(12): 3620-3625.
[6]	WANG Yafang, LIU Dongsheng, HOU Min. Clone code detection based on image similarity [J]. Journal of Computer Applications, 2019, 39(7): 2074-2080.
[7]	YANG Ping, ZHAO Bing, SHU Hui. Malicious code detection method based on icon similarity analysis [J]. Journal of Computer Applications, 2019, 39(6): 1728-1734.
[8]	LI Yong, XIANG Zhongqi. Ciphertext retrieval ranking method based on counting Bloom filter [J]. Journal of Computer Applications, 2018, 38(9): 2554-2559.
[9]	ZHANG Zhen, FU Yinjin, HU Guyu. Bloom filter-based wear-leveling scheme for novel hybrid memory architecture [J]. Journal of Computer Applications, 2018, 38(8): 2230-2235.
[10]	ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.
[11]	LIU Xiaoqiang, WEI Yongzhuang, LIU Zhenghong. New design of linear structure for round-reduced Keccak [J]. Journal of Computer Applications, 2018, 38(10): 2934-2939.
[12]	LIU Zhusong, YANG Zhangjie. Efficient and secure deduplication cloud storage scheme based on proof of ownership by Bloom filter [J]. Journal of Computer Applications, 2017, 37(3): 766-770.
[13]	ZHOU Guoliang, SA Churila, ZHU Yongli. Star join algorithm based on multi-dimensional Bloom filter in Spark [J]. Journal of Computer Applications, 2016, 36(2): 353-357.
[14]	ZHANG En, LIU Yapeng. Cloud outsourcing private set intersection protocol based on garbled Bloom filter [J]. Journal of Computer Applications, 2016, 36(10): 2723-2727.
[15]	LIU Shubo, WANG Ying, LIU Mengjun, ZHU Guangjun. Privacy-preserving various data sharing protocol in participatory sensing [J]. Journal of Computer Applications, 2015, 35(7): 1865-1869.

Routing lookup algorithm with variable-length address based on AVL tree and Bloom filter

基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 17

Related Articles 15

Recommended Articles

Metrics