基于路由查找算法的研究与硬件实现

《基于路由查找算法的研究与硬件实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东南大学硕士学位论文基于路由查找算法的研究与硬件实现姓名：林彦竹申请学位级别：硕士专业：通信与信息系统指导教师：衡伟20080101摘要近年来，随着Intcrnct的迅猛发展和人们对网络应用的各种需求，现有网络带宽的容量逐渐受到日益严重的挑战。由于用于主干网络互联的核心路由器的接口速率已经达到了几十个Gbps，这一速率要求核心路由器每秒能够转发几百万乃至上千万个数据包文。随着光通信技术的发展，现有的物理介质能够保证有足够的传输速度和传输质量满足网络流量的要求，但另一方面，网络结点的包处理转发能力却没有跟上物理层传输速度的步伐。因此，网络结点的较低的数据包处理转发能

2、力成为了一个很重要的需要克服的瓶颈。在网络结点对数据包的处理过程中，最主要的制约整个处理转发速度的步骤就是路由查找。因为基于软件实现的路由查找算法无法满足更快的网络要求，所以本论文的重点就是对路由查找算法进行研究、完成基于硬件实现的查找结构并进行实现。本文对现有的软件路由查找算法进行了归纳和总结，重点分析了各种算法查找速度，存储空间，更新复杂度等方面的优缺点。并介绍了CAM和TCAM器件在路由查找方面的应用．精确匹配是路由查找中的重要内容，其查找速度的快慢，关系到网络结点对数据链路层报文查找的速度。对于精确匹配，本文对基于Hash的路由查找的性能进行了分析，实现了

3、采用多重Hash进行查找的硬件结构，并对双重Hash的路由查找算法进行了硬件实现，所实现的硬件结构具有自学习功能，最后对所实现的硬件程序进了仿真。最大长度匹配是路由查找中的另一个重要内容。也是制约网络层数据包转发速度的主要因素。对于最大长度匹配，本文采取了并行结构和变步长多分支压缩树相结合的算法，对算法性能进行了分析，井对所设计的硬件结构进行了硬件实现和仿真。最后将程序下载到Xinlinx公司的V／rtex-Ⅱ系列FPGA器件中，搭建相应的测试平台，对查找性能进行了验证。，关键词：路由查找、精确匹配、最大长度匹配、Hash算法、并行结构、变长多分支压缩树东南大学硕

4、士论文AbstractNowdays．withtherapiddevelopmentofImemetandpeople’Sallkindsofrequirementfornetwork,theexistingnetworkbandwidthisbeingchallenged，ForcorerouterswhichareusedinbackbonenetworkalreadyhaveaboutseveralGbpsinterfacevelocity,theyshouldhavethecapacityofdealingwithmillionsofdatapacket．

5、Withtheimprovementoffibertechnology,theexistingphysicalmediumhasenoughtransmitingspePxIandtransmitingqualitytOkeepupwiththenetworkbandwidth’Srequirement．Ontheotherhand，theabilityofnetworknodedealingwiththedatapacketisbehind．So，itbecomesthebottleneckofenhancingthenetworkbandwidth．Whent

6、henetworknodedealswithdatapackeb，themainreasonofrestrictingthespeedistheroutelookup．Becausethesoftware-basedroutingalgorithmcan’tmcetlargernetworkbandwidth，thisthesiswillfocusonhardware-basedroutingalgorithmanditsrealization．Thisthesiswillconcludtheexistingsoftware-basedroutingalgorit

7、hms，analyzethealgorithms’searchingspeed，storagerequirementandcomplicationofupaate．AlsothisthesiswillintroducetheCAMandTCAM’sapplicationinroutelookup．Theexact-prefixmatchingisanimportantcontentofroutelookup，foritssearchingspeedisrelatedwiththenetworknode’Sdealingwithdatapacketoflayer2．

8、Thist