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

《基于trie软转发路由查找模块设计实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京邮电大学硕士学位论文基于TRIE的软转发路由查找模块的设计实现姓名：郭文文申请学位级别：硕士专业：信号与信息处理指导教师：曹雪虹2011-03学科门类：工学分类号：TN911单位代码：10293密级：硕士学位论文论文题目：基于TRIE的软转发路由查找模块的设计实现学生姓名郭文文学号硕080717指导教师曹雪虹教授学科专业信号与信息处理研究方向现代通信中的智能信号处理技术论文提交日期二〇一一年三月南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表

2、或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：_____________日期：____________南京邮电大学学位论文使用授权声明南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。论文的公布（包括刊登）授权南京邮电大学研究生

3、院（筹）办理。研究生签名：____________导师签名：____________日期：_____________南京邮电大学硕士学位论文摘要学科、专业：工学信号与信息处理研究方向：现代通信中的智能信号处理技术作者：郭文文指导教师：曹雪虹题目：基于TRIE的软转发路由查找模块的设计实现英文题目：DesignonTRIE-BasedSoft-forwordRoutelookupmodule主题词：路由查找，TRIE树，软转发，最长前缀匹配Keywords:Routelookup,Trie-tree,Soft-forword,LongestPrefixMatching南京邮电

4、大学硕士研究生学位论文摘要摘要随着Internet的迅猛发展，其规模、链路速度、带宽、流量等都呈指数级增长，这对路由器的转发性能提出了更高的要求，而转发的重要一步就是查找路由表，故快速的路由查找算法是实现高速数据转发的关键。在常用的路由查找算法中，基于Trie树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度，而且能适应不断提高的路由器性能要求，新颖的现代快速路由查找算法均是在Trie树的基础上通过优化算法实现的。Trie树是实现高速路由查找的关键，是实现各种路由查找优化策略的基础，故基于Trie树的路由查找算法的实现成为软转发路由表查找的一种趋势。本文将围绕如何设计实

5、现高效实用的基于Trie的软转发路由表查找算法这一核心，结合实际路由器的自身配置，在已有算法的基础上提出综合改进的方案，提高路由查找速度，实现对报文高速转发。本文的主要内容如下：1）研究了路由器的基本功能和IP路由选择的流程，分析了Trie结构在IP路由查找算法中的应用，介绍了路由与转发的相关概念，路由表的生成与路由选择的基本原理。2）详细分析了转发模块的框架与流程，研究了转发查询表项的基本结构，详细介绍了转发模块中上下行子模块的设计方案原理和具体流程。3）研究了软转发路由表查找模块对数据转发的重要性，分析了路由表查找算法的研究现状，结合新颖的算法思想设计高效实用的基于TR

6、IE的路由表查找算法。4）根据设计的路由查找算法的实现方法，整合源码实现符合规范要求的路由表查找算法。确定整个路由器软转发模块的解决方案，优化整个模块，最后编译版本上机调试。5）在路由器上实现基于TRIE的软转发路由表查找算法，用测试仪配合路由器来验证软转发功能的实现。根据实验测试结果来分析是否满足用户需求，总结现有方案的利弊，提出改进的方法和后期的展望。关键词：路由查找，TRIE树，软转发，最长前缀匹配I南京邮电大学硕士研究生学位论文ABSTRACTABSTRACTWiththerapiddevelopmentofInternet,itssize,linkspeed,ba

7、ndwidth,traffic,etc.showexponentialgrowth,whichneedahigherrouteforwardingperformance,andanimportantstepofforwardingistolooktheroutingtableup,sofastroutelookupalgorithmisthekeytohigh-speeddataforwarding.Amongthecommonlyusedroutelookupalgorithms,Trie-basedalgori