摘要
从讨论非对称二分查找树的平衡问题出发,给出了一种通用的平衡权函数构造方法,解决了Waldvogel等在算法优化过程中提出的启发式平衡权函数构造问题,优化了非对称二分查找树平衡算法,使得CHT(col-lection of hash tables)算法很容易扩展到128 bit的IPv6地址.实验表明,该算法与Waldvogel等在特殊情况下给出的推测结果基本符合,能很好地适应IP前缀分布的变化,具有很好的适应性和可扩展性.
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 128 bit 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.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2007年第2期54-56,共3页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(605731120)
郧阳师范高等专科学校科研基金资助项目(2003C12)
