摘要
可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题,提出一种基于平衡二叉树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算法在路由表项数变化较大的情况下也能维持稳定的查找性能,适用于可变长地址的路由查找转发。
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.
作者
黄永锦
覃毅芳
周旭
张心晴
HUANG Yongjin;QIN Yifang;ZHOU Xu;ZHANG Xinqing(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100083,China;University of Chinese Academy of Sciences,Beijing 100049,China)
出处
《计算机应用》
CSCD
北大核心
2023年第12期3882-3889,共8页
journal of Computer Applications
基金
北京市科技计划项目(Z191100007519007)
中国科学院青年创新促进会基金资助项目(2020175)。
关键词
可变长地址
路由查找
AVL树
BLOOM过滤器
哈希算法
variable-length address
routing lookup
Adelson-Velskii and Landis(AVL)tree
Bloom filter
hash algorithm
