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

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