基于多分支trie的快速路由查找算法

摘要

随着Internet的不断发展,路由查找速度已经成为制约核心路由器性能的主要瓶颈。减少访问存储器的次数是提高路由查找速度的有效途径之一。由于片外存储器价格较片内存储器低很多,本文利用多片片外存储器,采用基于并行流水线的查找方式对IP地址进行最长前缀匹配,以达到访问一次存储器的时间完成一次路由查找。
　　 本文首先介绍了国内外现有的部分研究成果,并在剖析多分支trie算法的基础上,采用分段查找及前缀扩展技术,给出了一种适合FPGA实现的路由查找算法。算法采用多表结构,将查找过程分为了四级,然后根据四块存储器独立工作的特性,采用流水线的方式进行了并行化设计,从而可以保证访问一次存储器完成一次数据包的查找。设计表的结构时,为了保证占用的空间小,本文给出了一个动态规划算法用于求解四个目标层的值。
　　 本文提出的设计结构支持动态更新,并且更新单元数少。测试结果表明,在同等规模的前缀集下,相比DIR-24-8-BASIC方法在空间上具有显著优势。最后,给出了算法实现的FPGA设计结构,实验结果显示算法可以达到15Mpps的查找速度。

目录

文摘

英文文摘

第一章 绪论

1.1 背景介绍

1.2 研究现状

1.3 本文工作

第二章 相关算法研究及性能分析

2.1 二分查找算法

2.1.1 线性查找hash表算法

2.1.2 二分法hash表查找算法

2.1.3 基于前缀区间的二分查找算法

2.2 基于trie的数据结构算法

2.2.1 二进制trie

2.2.2 Leaf-Push

2.2.3 路径压缩trie

2.2.4 多路分支trie

2.2.5 LC-trie

2.3 基于Cache的算法

2.4 硬件算法

2.4.1 CAM

2.4.2 基于DIR-24-8-BASIC结构的实现方法

2.5 算法性能分析比较

2.6 本章小结

第三章 改进的DIR-24-8-BASIC算法

3.1 算法描述

3.2 确定四个目标层

3.2.1 前缀扩展

3.2.2 如何选择四个目标层

3.3 建表

3.4 查找

3.5 实验结果与分析

3.5.1 测试结果

3.5.2 性能分析

3.6 本章小结

第四章 算法的FPGA实现

4.1 FPGA简介

4.2 FPGA开发流程

4.3 FPGA系统设计

4.4 算法的实现

4.5 查找模块

4.6 实验结果

4.7 本章小结

第五章 总结与展望

致谢

参考文献

研究成果