| 一种基于CHT的可扩展非对称二分查找平衡算法 |
| |
| 引用本文： | 何统洲,王卫东,李芝棠.一种基于CHT的可扩展非对称二分查找平衡算法[J].华中科技大学学报(自然科学版),2007,35(2):54-56. |
| |
| 作者姓名： | 何统洲 王卫东 李芝棠 |
| |
| 作者单位： | 1. 湖北郧阳师范高等专科学校,物理与电子工程系,湖北,丹江口,442700;华中科技大学,计算机科学与技术学院,湖北,武汉,430074
2. 华中科技大学,计算机科学与技术学院,湖北,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金
,
郧阳师范高等专科学校校科研和教改项目 |
| |
| 摘 要： | 从讨论非对称二分查找树的平衡问题出发,给出了一种通用的平衡权函数构造方法,解决了Waldvogel等在算法优化过程中提出的启发式平衡权函数构造问题,优化了非对称二分查找树平衡算法,使得CHT(collection of hash tables)算法很容易扩展到128 bit的IPv6地址.实验表明,该算法与Waldvogel等在特殊情况下给出的推测结果基本符合,能很好地适应IP前缀分布的变化,具有很好的适应性和可扩展性.
|
| 关 键 词： | IP路由查找 对分搜索 CHT算法 平衡权函数 可扩展性 非对称 二分查找 平衡算法 balancing algorithm search binary asymmetric 适应性 变化 分布 前缀 结果 情况 实验 易扩展 collection hash tables 优化过程 |
| 文章编号： | 1671-4512（2007）02-0054-03 |
| 收稿时间： | 2005-11-04 |
| 修稿时间： | 2005年11月4日 |
CHT-based scalable asymmetric binary search balancing algorithm |
| |
| He Tongzhou,Wang Weidong,Li zhitang.CHT-based scalable asymmetric binary search balancing algorithm[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2007,35(2):54-56. |
| |
| Authors: | He Tongzhou Wang Weidong Li zhitang |
| |
| Abstract: | Collection of Hash Tables(CHT) organization proposed by Waldvogel et al,uses binary search to look up the Best Matching Prefix.However,because of the heuristic weighting functions of the scheme,it is difficult to migrate it to 128bit IPv6 addresses.Through researching the balancing problem of the asymmetric bi-search tree,this paper proposes an improved algorithm to resolve the problem by providing a universal balancing weighting function.The testing results show that this algorithm is consistent with the presumption of Waldvogel et al,and is able to adapt to the change of prefix distribution.This new algorithm is high adaptive and scalable. |
| |
| Keywords: | IP routing lookup bi-search CHT algorithm balancing weighting function |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
