資源描述：
《快速路由器的路由查找和流分類算法研究new》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第33卷第6期電子科技大學(xué)學(xué)報Vol.33No.62004年12月JournalofUESTofChinaDec.2004快速路由器的路由查找和流分類算法研究姚興苗，李樂民，胡光岷(電子科技大學(xué)寬帶光纖傳輸與通信網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗室成都610054)【摘要】分析了路由器的體系結(jié)構(gòu)發(fā)展，研究了路由查找算法和流分類算法在快速路由器中的應(yīng)用。研究表明，基于分段壓縮的路由查找算法支持IPv6路由查找，具有合理的存儲容量和快速的查找時間；采用按值分支樹的多維綜合流分類算法支持前綴和范圍匹配，可擴(kuò)展性強(qiáng)，適合大容量規(guī)則數(shù)據(jù)庫。兩種算法適合在快速路由器中應(yīng)用。關(guān)鍵詞體系結(jié)構(gòu);路由查找;流分類;快速路由器
2、中圖分類號TP393文獻(xiàn)標(biāo)識碼AResearchonIPRouteLookupandPacketClassificationAlgorithmsforHighSpeedRouterYaoXingmiao，LiLemin，HuGuangming(KeyLaboratoryofBrodbandOpticalFiberTransmissionandCommunicationNetworksUESTofChina,MinistryofEducationChengdu610054)AbstractThedevelopmentofrouterarchitectureisanalyzed,andthefa
3、stroutelookupandpacketclassificationalgorithmsforhighspeedrouterareresearched.TheresearchshowsthelookupalgorithmforIPv6routelookupwithcompressiontriehasreasonablememoryspaceandfastlookuptime.Thecompositivemulti-dimensionalpacketclassificationalgorithmbasedontreedividedbyvalueisscalable.Itcandealwit
4、hprefixesmatchandrangematchforlargerulesets.Twoalgorithmsaresuitableforhighspeedrouter.Keywordsrouterarchitecture;routelookup;packetclassification;highspeedrouter隨著Internet的快速發(fā)展和各種寬帶技術(shù)的不斷出現(xiàn)，以及多種Internet業(yè)務(wù)的增長，路由器的體系結(jié)構(gòu)不斷發(fā)展，第一代路由器主要采用單處理器共享總線式結(jié)構(gòu)，中央處理器通過通用的總線與多個接口卡互連。中央處理器負(fù)責(zé)包括路由收集，報文轉(zhuǎn)發(fā)處理等所有的事務(wù)處理。這種體系結(jié)構(gòu)
5、的性能主要取決于中央處理器的速度和共享總線的帶寬，路由器擴(kuò)展性比較差。第二代路由器在網(wǎng)絡(luò)接口卡上采用了一些智能處理，如業(yè)務(wù)接口卡的cache技術(shù)來增加轉(zhuǎn)發(fā)速率。第三代路由器采用路由與轉(zhuǎn)發(fā)相分離的技術(shù)，從而有效地解決了路由計算能力的問題，并且總線技術(shù)也得到了較大的發(fā)展。第四代路由器采用硬件ASIC轉(zhuǎn)發(fā)模式和交換結(jié)構(gòu)，解決了帶寬容量和性能不足的問題。第五代路由器繼承了第四代路由器的優(yōu)點(diǎn)，增加了更為靈活的網(wǎng)絡(luò)處理器。對于一些復(fù)雜的標(biāo)準(zhǔn)操作，如路由查找算法等，采用硬件協(xié)處理器方式提高處理性能，實(shí)現(xiàn)軟件業(yè)務(wù)靈活性和高性能硬件轉(zhuǎn)發(fā)的有機(jī)結(jié)合。路由器技術(shù)不斷向前發(fā)展的同時，也對路由器中的兩項關(guān)鍵技術(shù)快速路
6、由查找和流分類技術(shù)提出新的要求，并且由于傳統(tǒng)的IPv4網(wǎng)絡(luò)需要逐步升級到下一代以IPv6協(xié)議為基礎(chǔ)的網(wǎng)絡(luò)，還需要路由查找和流分類對IPv6協(xié)議支持，因此研究快速的路由查找和流分類算法在路由器中的應(yīng)用十分必要。本文從路由器的體系收稿日期：2004?07?15作者簡介：姚興苗(1976?)，男，博士生，主要從事流分類和路由查找算法方面的研究.664電子科技大學(xué)學(xué)報第33卷結(jié)構(gòu)發(fā)展入手，對快速的IPv4/IPv6路由查找算法和流分類算法進(jìn)行了研究和討論，得出了適合在快速路由器采用的快速路由查找和流分類算法。1快速路由查找算法當(dāng)一個分組到達(dá)路由器時，路由器必須根據(jù)其目的地址在路由轉(zhuǎn)發(fā)表中查找下一跳信
7、息。轉(zhuǎn)發(fā)表一般按照如下的形式保存路由項：<目的網(wǎng)絡(luò)地址/掩碼，邏輯端口號>，分組可能匹配多個端口，但分組最終選擇所有候選端口中相應(yīng)掩碼最長的端口，這被稱為最長前綴匹配(能夠有效的降低路由表的大小，并且在一定程度上緩和IPv4地址的枯竭問題)。尋找高效的路由表查找算法是相當(dāng)困難，查找算法的性能不僅要考慮到快速查找時間，還要求低存儲空間和快速路由表更新。路由查找算法大致分為3類：1)基于三態(tài)內(nèi)容可尋址存儲器(Te
