基于前缀区间集合的IPv6路由查找算法  

Binary search on range of IPv6 prefix sets

作　　者：崔宇[1] 田志宏[1] 张宏莉[1] 方滨兴[1] 

机构地区：[1]哈尔滨工业大学网络与信息安全技术研究中心,黑龙江哈尔滨150001

出　　处：《通信学报》2013年第6期29-37,48,共10页Journal on Communications

基　　金：国家重点基础研究发展计划("973"计划)基金资助项目(2011CB302605);国家高技术研究发展计划("863"计划)基金资助项目(2011AA010705;2012AA012506;2012AA012502);国家自然科学基金资助项目(61202457);国家科技支撑计划基金资助项目(2012BAH37B01)~~

摘　　要：对IPv6相关的通用型与特定型路由算法进行了分析,重点研究了以BSR为基础的IPv6路由算法在查找和更新时的不平衡问题,提出了基于前缀区间集合的IPv6路由算法。通过对路由前缀(N)进行范围(K)、集合(M)划分以及更新节点自修复提高查询速度、降低不平衡性的影响,具有O(log2N/K)和O(log2N/K+2M)的查询与更新时间复杂度,空间复杂度为O(K+2N)。实验表明,该算法具有良好的查询性能,降低了更新不平衡性的影响。The general and special types of IPv6 routing algorithms were studied. Focusing on the imbalance problems in lookup and update process in routing algorithm, a novel method called BSRPS （binary search on range of prefix sets） was presented. By range-partition （K） and set-partition （M） on routing table （N）, and self-recovery after updating, this method enhanced the lookup speed and reduced the impact of imbalance in updating. Time complexity in tookup and update process is O（log2N/K） and O（log2N/K＋2M）, and space complexity is O（K＋2N） where N is the size of routing table. Experiment re- sults show that this method is efficient in lookup and reduces the impact of imbalance after updating effectively.

关 键 词：路由 IPV6 前缀区间集合 自修复 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]