Abstract: Most of the existing routing lookup algorithms usually use a variety of optimization methods to improve search performance; however they need to reconstruct the entire routing table to update routing information. Concerning this, a multi-layer hybrid structure algorithm for IPv6 routing table lookup was proposed. The first layer used the advantage of the optimal search tree for reference. The different values of prefix 1-16 bit were ordered by their probability of occurrence in the routing table, and were stored in the linear list. The 17-32 bit and 33-48 bit of prefix were organized respectively with the balanced binary tree. The 49~64 bit of prefix was organized with the linear list. The evaluation results show that the proposed scheme performs faster, occupies less memory, and supports incremental update.

Key words: routing lookup, IPv6, balanced binary tree, optimal search tree, linear list

摘要： 针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能，却使得路由更新需要重构整个路由表的问题，提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点，把前缀1~16位的不同取值按其在路由表中出现的概率降序存储在线性表中，在第二、三层把前缀的17~32位和33~48位分别用二叉平衡树组织，在第四层把49~64位使用线性表组织。实验结果表明，该算法查找速度快，占用内存少，动态增量更新速度快。

关键词: 路由查找, IPv6, 二叉平衡树, 最优查找树, 线性表