基于动态规划和B+树的IP路由查找技术研究

摘要

随着Internet技术的迅猛发展，路由表，网络速度，网络流量都在持续增长，IP路由查找困难度也随之增加。无类别域间路由选择(CIDR,Classless InterDomain Routing)的使用，使得路由器必须在路由表中找到与IP地址最长匹配的前缀进行路由转发。IP地址查找是路由器转发性能的瓶颈，因此本文对IP路由查找技术进行了深入研究，并分别对两篇文献中提出的算法进行了改进。
　　本文首先对路由系统和IP路由查找技术进行了相关研究，对当前IP路由查找技术的难点进行了分析；然后对当前已有的典型IP路由查找算法进行了分类研究，重点对基于Trie树的算法、基于哈希技术的算法和基于硬件TCAM的算法进行了研究和分析，总结了各种算法的优点和缺点，对本文提出改进算法起到了较大的启发。
　　本文针提出了一种基于Trie树的动态规划算法。该算法可以确定一个最优的前缀划分方式，以使在所有不同的划分方案中，该划分方案可以达到空间最优，哈希结构使用的空间达到最小。实验结果表明，不同划分方式使用的空间差距较大，而本文提出的动态规划算法可使空间达到最优。
　　本文还提出了一种可升级的、支持快速动态更新的基于B+树的IP路由查找算法。该数据结构用最特殊前缀作为关键字来构造B+树，用一个无符号整数来压缩存储包含一个最特殊前缀的所有前缀。和其他可升级的动态算法相比，该算法对路由表中的每一个前缀只存储一次，且查找到叶节点就能找到匹配的最长前缀，而不会往回查找。对于一个有n个前缀的路由表，使用m阶的B+树，该查找结构空间复杂度为O(n)，查找时间复杂度为O(logmn)，且前缀插入和删除效率的效率为O(mlogmn)。实验结果表明，本文提出的基于B+树的IP路由查找算法能有效提升IP查找的速度，且支持IP前缀的动态更新和IPv6地址。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1研究背景及意义

1.2 国内外研究现状

1.3路由系统概述

1.4 IP查找及最长前缀匹配问题

1.5本文研究内容

1.6本文组织结构

第2章 相关研究技术综述

2.1 基于哈希的IP查找算法

2.3 内存效率高的IP查找算法

2.4 使用PIHT的IP查找结构

2.5 小结

第3章 基于Trie的动态规划前缀最优划分算法

3.1 基于Trie的数据结构

3.2 动态规划前缀最优划分算法

3.3 测试结果

3.4 小结

第4章 基于B+树的IP查找算法

4.1 相关工作

4.2 预定义

4.3 基于B-树的MMSPT算法

4.4 基于B+树的IP查找算法

4.5 实验结果

4.6 小结

总结与展望

1 本文工作总结

2 未来工作展望

参考文献

致谢