IPv4/IPv6双栈兼容路由查找模块设计

摘要

随着计算机网络的迅猛发展，需要网络协议(Internet Protocol，IP)地址的主机越来越多。到2011年，第四代网络协议（IP version4,IPv4）地址已经耗尽。为解决IPv4地址耗尽问题，第六代互联网协议（IP version6，IPv6）被提出，然而更换一个协议十分复杂，因此IPv4和IPv6将会长时间共存。这要求路由器能够兼容IPv4和IPv6双栈协议。双栈路由器的性能很大程度上取决于数据包的分组转发速率，分组转发重要的是查找路由表，因此快速的路由查找显得尤为重要。
　　本文研究了国内外已有的路由查找算法，分析了各种算法的优缺点和硬件实现的可行性。在分析了IPv4/IPv6前缀的分布特点后，提出了一种一级缓存和一级索引相结合的分组分块硬件路由查找方案。根据提出的方案，本文设计并划分了模块，其中主要包括缓存模块、布隆滤波器模块、前缀处理模块和仲裁模块。为了提高索引效率，本文提出了加权值的相关性检测机制，减少了布隆滤波器(Bloom Filter,BF)的假阳性错误概率。为了提高路由查找的可扩展性，本设计选取了哈希链表(Hash Chain Tables，HCT)存储方案并定义了其数据结构。本文对设计模块进行了实现，建立了对应的C语言模型，通过与C语言模型对比完成了设计模块功能验证和可编程门阵列(Field Programmable Gate Array,FPGA)设计。
　　本设计通过Xilinx ML605开发平台完成FPGA实现，模块的工作频率可达244069MHz，平均每秒查找次数可达到2260万次，达到IPv4/IPv6双栈路由器OC-192(Optical Carrier192，10Gb/s)端口的链路速率。结果表明，相对使用三态内容寻址存储器(Ternary Content Addressable Memory，TCAM)实现的双栈路由查找方案，该查找方案成本低廉，支持动态无阻塞更新，其结构灵活，可扩展性强。本设计适用于链路速率不大于10Gb/s的IPv4/IPv6双栈路由器中，具有重要的工程应用意义。

目录

声明

摘要

第一章 绪论

1．1 课题背景与意义

1．2 国内外研究现状

1．3 研究内容与设计指标

1．3．2 设计要求与性能指标

1．4 本文组织结构

第二章 路由查找算法分析

2．1 基于前缀树的查找算法

2．2 基于硬件的查找算法

2．3 基于哈希的查找算法

2．4 基于布隆滤波器的查找算法

2．5 各算法优缺点比较

2．6 本章小结

第三章 双栈路由查找方案分析与设计

3．1 IPv4／IPv6前缀分布特点分析

3．2 双栈路由查找整体方案和模块划分

3．3 双栈路由查找各模块分析与设计

3．3．1 指令控制模块

3．3．2 缓存处理模块

3．3．3 布隆滤波器模块

3．3．4 前缀长度为8~16的前缀处理模块

3．3．5 其他前缀长度的前缀处理模块

3．3．6 仲裁模块

3．4 本章小结

第四章 双栈路由查找方案的RTL实现

4．1 双栈路由查找顶层模块接口定义

4．2 指令控制模块实现

4．3 缓存处理模块实现

4．4 布隆滤波器模块实现

4．5 前缀处理模块实现

4．5．1 前缀长度为8~16的前缀处理模块实现

4．5．2 其他前缀长度的前缀处理模块实现

4．6 仲裁模块实现

4．7 本章小结

第五章 验证与结果分析

5．1 功能仿真与验证

5．1．1 模块级仿真与验证

5．1．2 系统级仿真与验证

5．2．FPGA实现

5．2．1 ISE综合

5．2．3 上板验证

5．3 结果与性能分析

5．3．2 更新速度分析

5．3．4 验证结果对比

5．4 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读硕士学位期间的成果