基于TRIE的软转发路由查找模块的设计实现

摘要

随着Internet的迅猛发展，其规模、链路速度、带宽、流量等都呈指数级增长，这对路由器的转发性能提出了更高的要求，而转发的重要一步就是查找路由表，故快速的路由查找算法是实现高速数据转发的关键。在常用的路由查找算法中，基于Trie 树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度，而且能适应不断提高的路由器性能要求，新颖的现代快速路由查找算法均是在Trie 树的基础上通过优化算法实现的。Trie 树是实现高速路由查找的关键，是实现各种路由查找优化策略的基础，故基于Trie 树的路由查找算法的实现成为软转发路由表查找的一种趋势。
　　 本文将围绕如何设计实现高效实用的基于Trie的软转发路由表查找算法这一核心，结合实际路由器的自身配置，在已有算法的基础上提出综合改进的方案，提高路由查找速度，实现对报文高速转发。本文的主要内容如下：
　　 1）研究了路由器的基本功能和Ip路由选择的流程，分析了Trie 结构在Ip路由查找算法中的应用，介绍了路由与转发的相关概念，路由表的生成与路由选择的基本原理。
　　 2）详细分析了转发模块的框架与流程，研究了转发查询表项的基本结构，详细介绍了转发模块中上下行子模块的设计方案原理和具体流程。
　　 3）研究了软转发路由表查找模块对数据转发的重要性，分析了路由表查找算法的研究现状，结合新颖的算法思想设计高效实用的基于TRIE的路由表查找算法。
　　 4）根据设计的路由查找算法的实现方法，整合源码实现符合规范要求的路由表查找算法。确定整个路由器软转发模块的解决方案，优化整个模块，最后编译版本上机调试。
　　 5）在路由器上实现基于TRIE的软转发路由表查找算法，用测试仪配合路由器来验证软转发功能的实现。根据实验测试结果来分析是否满足用户需求，总结现有方案的利弊，提出改进的方法和后期的展望。

目录

基于TRIE的软转发路由查找模块的设计实现