快速路由器的路由查找和流分类算法研究new

《快速路由器的路由查找和流分类算法研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第33卷第6期电子科技大学学报Vol.33No.62004年12月JournalofUESTofChinaDec.2004快速路由器的路由查找和流分类算法研究姚兴苗，李乐民，胡光岷(电子科技大学宽带光纤传输与通信网技术教育部重点实验室成都610054)【摘要】分析了路由器的体系结构发展，研究了路由查找算法和流分类算法在快速路由器中的应用。研究表明，基于分段压缩的路由查找算法支持IPv6路由查找，具有合理的存储容量和快速的查找时间；采用按值分支树的多维综合流分类算法支持前缀和范围匹配，可扩展性强，适合大容量规则数据库。两种算法适合在快速路由器中应用。关键词体系结构;路由查找;流分类;快速路由器

2、中图分类号TP393文献标识码AResearchonIPRouteLookupandPacketClassificationAlgorithmsforHighSpeedRouterYaoXingmiao，LiLemin，HuGuangming(KeyLaboratoryofBrodbandOpticalFiberTransmissionandCommunicationNetworksUESTofChina,MinistryofEducationChengdu610054)AbstractThedevelopmentofrouterarchitectureisanalyzed,andthefa

3、stroutelookupandpacketclassificationalgorithmsforhighspeedrouterareresearched.TheresearchshowsthelookupalgorithmforIPv6routelookupwithcompressiontriehasreasonablememoryspaceandfastlookuptime.Thecompositivemulti-dimensionalpacketclassificationalgorithmbasedontreedividedbyvalueisscalable.Itcandealwit

4、hprefixesmatchandrangematchforlargerulesets.Twoalgorithmsaresuitableforhighspeedrouter.Keywordsrouterarchitecture;routelookup;packetclassification;highspeedrouter随着Internet的快速发展和各种宽带技术的不断出现，以及多种Internet业务的增长，路由器的体系结构不断发展，第一代路由器主要采用单处理器共享总线式结构，中央处理器通过通用的总线与多个接口卡互连。中央处理器负责包括路由收集，报文转发处理等所有的事务处理。这种体系结构

5、的性能主要取决于中央处理器的速度和共享总线的带宽，路由器扩展性比较差。第二代路由器在网络接口卡上采用了一些智能处理，如业务接口卡的cache技术来增加转发速率。第三代路由器采用路由与转发相分离的技术，从而有效地解决了路由计算能力的问题，并且总线技术也得到了较大的发展。第四代路由器采用硬件ASIC转发模式和交换结构，解决了带宽容量和性能不足的问题。第五代路由器继承了第四代路由器的优点，增加了更为灵活的网络处理器。对于一些复杂的标准操作，如路由查找算法等，采用硬件协处理器方式提高处理性能，实现软件业务灵活性和高性能硬件转发的有机结合。路由器技术不断向前发展的同时，也对路由器中的两项关键技术快速路

6、由查找和流分类技术提出新的要求，并且由于传统的IPv4网络需要逐步升级到下一代以IPv6协议为基础的网络，还需要路由查找和流分类对IPv6协议支持，因此研究快速的路由查找和流分类算法在路由器中的应用十分必要。本文从路由器的体系收稿日期：2004−07−15作者简介：姚兴苗(1976−)，男，博士生，主要从事流分类和路由查找算法方面的研究.664电子科技大学学报第33卷结构发展入手，对快速的IPv4/IPv6路由查找算法和流分类算法进行了研究和讨论，得出了适合在快速路由器采用的快速路由查找和流分类算法。1快速路由查找算法当一个分组到达路由器时，路由器必须根据其目的地址在路由转发表中查找下一跳信

7、息。转发表一般按照如下的形式保存路由项：<目的网络地址/掩码，逻辑端口号>，分组可能匹配多个端口，但分组最终选择所有候选端口中相应掩码最长的端口，这被称为最长前缀匹配(能够有效的降低路由表的大小，并且在一定程度上缓和IPv4地址的枯竭问题)。寻找高效的路由表查找算法是相当困难，查找算法的性能不仅要考虑到快速查找时间，还要求低存储空间和快速路由表更新。路由查找算法大致分为3类：1)基于三态内容可寻址存储器(Te