高端路由器路由查找算法分析与实现

摘要

互连网络的迅猛发展，对网络通信设备提出了更高的要求，特别是核心的路由器设备。中低端的路由设备往往只需要应对10M或100M的数据流量，而高端的路由器则需要应对Gbit/秒级别甚至Tbit/秒级别的流量。这对路由器厂商提出了强有力的挑战，他们需要挖掘路由器更大的潜力来满足日益增长的互联网流量需求。　　作为互连网核心设备的路由器其最重要的核心部件之一是路由的最长匹配查找算法，算法的好坏直接影响了路由器的数据转发性能，特别是在核心路由器上，这将影响整个路由器的吞吐量。另外由于路由器是嵌入式系统，所以在考虑算法效率的同时，还要综合考虑内存的使用，也就是要设计好的数据结构来组织路由项以减少内存的消耗。　　文章在对IPv4地址的特点、最长匹配的含义进行详细阐述基础上，分析了当前普遍使用的AVL查找算法的不足，提出将新的查找算法MBit-Trie应用于高端路由器设计的构想。在设计并实现了MBit-Trie算法的基础上，通过多种平台进行仿真测试，验证了MBit-Trie在路由查找性能上的优越性，以及在高端路由器设计中应用的可行性。

目录

文摘

英文文摘

论文说明：图形列表、表格列表

第一章绪论

1.1背景和现状

1.2本文的工作和意义

1.3本文研究的主要内容和成果

第二章路由查找技术的介绍

2.1 IP地址的结构

2.1.1子网的出现

2.1.2可变长子网掩码(VLSM)

2.1.3无类域间路由(CIDR)

2.2最长匹配的含义

2.3传统的路由查找算法

2.3.1线性查找算法

2.3.2缓存策略

2.3.3 Binary Trie

2.4新的路由查找算法

2.4.1 Multi Bit Trie

2.4.2前缀长度二分法查找

2.4.3路由硬件查找

2.5现行情况的分析

2.5.1 Internet上实际路由条目的掩码长度分析

2.6小结

第三章AVL与MBit Trie算法设计与实现

3.1算法概述

3.1.1 AVL二叉树概述

3.1.2 MBit Trie概述：

3.2算法逻辑结构的实现

3.2.1主程序的实现

3.2.2 AVL二叉树的实现

3.2.3 MBit Trie的实现

3.3测试方案的设计

3.3.1测试环境

3.3.2内存统计：

3.3.3插入时间统计

3.3.4查询时间统计

3.3.5更新时间统计

3.3.6遍历时间统计

3.3.7动态编程策略

3.3.8内存分配策略

3.3.9试验对比方案

3.3.10测试程序参数

3.4小结

第四章AVL与MBit Trie算法分析与评价

4.1环境一上AVL和MBit Trie比较

4.1.1测试结果数据

4.1.2内存使用比较

4.1.3构建时间比较

4.1.4查找时间比较

4.1.5环境一结果分析：

4.2环境二上AVL和MBit Trie比较

4.2.1测试结果数据

4.2.2内存使用比较

4.2.3构建时间比较

4.2.4查找时间比较

4.2.5环境二结果分析

4.3环境三上AVL和MBit Trie比较

4.3.1测试结果数据

4.3.2内存使用比较

4.3.3构建时间比较

4.3.4查找时间比较

4.3.5环境三结果分析

4.4总体结果评价

第五章总结与展望

5.1文章总结

5.2创新与突破

5.3未来展望

附录一测试程序介绍

参考文献：

致谢

缩略语英汉对照

论文独创性声明及论文使用授权声明