可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题,提出一种基于平衡二叉树AVL(Adelson-Velskii and Landis)树和Bloom过滤器的适用于可变长地址的高效路由查找算法,简称为AVL-Bl...可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题,提出一种基于平衡二叉树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(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念。统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋...针对传统AVL(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念。统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋转操作。广义AVL树放松了AVL树的平衡约束,允许左右子树树高相差不超过N(N≥1),当更新操作(插入/删除)执行后,广义AVL树只在平衡约束条件不满足时采用统一重平衡算法进行调整。理论分析与实验结果表明,广义AVL树的调整率随着N的增大而显著降低:N为5时,调整率低于4%;N为13时调整率低于千分之一。广义AVL树的调整率远低于红黑树等经典数据结构,适合并发应用。展开更多
文摘可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题,提出一种基于平衡二叉树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(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念。统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋转操作。广义AVL树放松了AVL树的平衡约束,允许左右子树树高相差不超过N(N≥1),当更新操作(插入/删除)执行后,广义AVL树只在平衡约束条件不满足时采用统一重平衡算法进行调整。理论分析与实验结果表明,广义AVL树的调整率随着N的增大而显著降低:N为5时,调整率低于4%;N为13时调整率低于千分之一。广义AVL树的调整率远低于红黑树等经典数据结构,适合并发应用。
