[本文摘要]

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