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

摘要：

对IPv6相关的通用型与特定型路由算法进行了分析，重点研究了以BSR为基础的IPv6路由算法在查找和更新时的不平衡问题，提出了基于前缀区间集合的IPv6路由算法。通过对路由前缀（N）进行范围（K）、集合（M）划分以及更新节点自修复提高查询速度、降低不平衡性的影响，具有O(log2N/K)和O(log2N/K+2M)的查询与更新时间复杂度，空间复杂度为O(K+2N)。实验表明，该算法具有良好的查询性能，降低了更新不平衡性的影响。

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

分类号：TP393.08(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划“973”计划基金资助项目2011CB302605；国家高技术研究发展计划“863”计划基金资助项目2011AA010705,2012AA012506,2012AA012502；国家自然科学基金资助项目61202457；国家科技支撑计划基金资助项目2012BAH37B01FoundationItems:TheNationalBasicResearchProgramofChina973Program2011CB302605;TheNationalHighTechnologyResearchandDevelopmentProgramofChina863Program2011AA010705,2012AA012506,2012AA012502;TheNationalNaturalScienceFoundationofChina61202457;TheNationalKeyTechnologyR&DProgramofChina2012BAH37B01

在线出版日期：2013-07-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：29-37,48