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

doi:10.11772/j.issn.1001-9081.2022121915

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (12): 3882-3889.DOI: 10.11772/j.issn.1001-9081.2022121915

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

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

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

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

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)

摘要/Abstract

摘要：

可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题，提出一种基于平衡二叉树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过滤器, 哈希算法

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

中图分类号:

TP393.05

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

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.

图/表 7

图1 AVL-Bloom算法的结构

Fig.1 Structure of AVL-Bloom algorithm

图2 AVL-Bloom 的查找过程

Fig.2 Lookup process of AVL-Bloom

图3 AVL-Bloom 的添加过程

Fig.3 Inserting process of AVL-Bloom

图4 AVL-Bloom 的删除过程

Fig.4 Deleting process of AVL-Bloom

图5 不同算法的查询时间比较

Fig. 5 Comparison of query time among different algorithms

图6 不同算法的内存开销比较

Fig. 6 Comparison of memory overhead among different algorithms

图7 COBF算法和AVL-Bloom算法的哈希计算次数比较

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

参考文献 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]	韩亚茹, 闫连山, 姚涛. 基于元学习的深度哈希检索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2015-2021.
[2]	杨粟, 欧阳智, 杜逆索. 基于相关度距离的无监督并行哈希图像检索[J]. 计算机应用, 2021, 41(7): 1902-1907.
[3]	王亚芳, 刘东升, 侯敏. 基于图像相似度检测代码克隆[J]. 计算机应用, 2019, 39(7): 2074-2080.
[4]	杨萍, 赵冰, 舒辉. 基于图标相似性分析的恶意代码检测方法[J]. 计算机应用, 2019, 39(6): 1728-1734.
[5]	刘竹松, 杨张杰. 基于布隆过滤器所有权证明的高效安全可去重云存储方案[J]. 计算机应用, 2017, 37(3): 766-770.
[6]	江顺亮, 胡世鸿, 唐祎玲, 葛芸, 叶发茂, 徐少平. 低调整率的广义AVL树及其统一重平衡方法[J]. 计算机应用, 2015, 35(3): 654-658.
[7]	陆婷, 房俊, 乔彦克. 基于HBase的交通流数据实时存储系统[J]. 计算机应用, 2015, 35(1): 103-107.
[8]	黄胜张卫吴川川陈胜蓝. 基于多分支优先级树的IP路由查找算法[J]. 计算机应用, 2014, 34(3): 615-618.
[9]	丁俊张曦煌. 实现欧洲/电气安装总线协议数据加密和设备认证的方法[J]. 计算机应用, 2014, 34(3): 728-732.
[10]	邓亚平周美红. 基于多层混合结构的IPv6路由表查找算法[J]. 计算机应用, 2013, 33(02): 385-389.
[11]	胡国良林亚平王刚. 基于并行Bloom过滤器组的深度数据包检测算法[J]. 计算机应用, 2012, 32(11): 3132-3135.
[12]	董继光陈卫卫田浪军吴海佳. 大规模云存储系统副本布局研究[J]. 计算机应用, 2012, 32(03): 620-624.
[13]	吴武飞王奕李仁发. Keccak算法\|海绵结构\|哈希算法\|可重构\|现场可编程门阵列[J]. 计算机应用, 2012, 32(03): 864-866.
[14]	王景中杜飞. 矩阵型布鲁姆过滤器在病毒过滤防火墙中的研究[J]. 计算机应用, 2009, 29(11): 2939-2941.
[15]	罗绪成 . RAP2P：一种基于资源广告的非结构化P2P系统[J]. 计算机应用, 2006, 26(11): 2578-2582.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 17

相关文章 15

编辑推荐

Metrics