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

1、第33卷第6期電子科技大學(xué)學(xué)報(bào)V ol.33 No.62004年12月Journal of UEST of China Dec. 2004 快速路由器的路由查找和流分類算法研究姚興苗,李樂民,胡光岷(電子科技大學(xué)寬帶光纖傳輸與通信網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室成都 610054【摘要】分析了路由器的體系結(jié)構(gòu)發(fā)展,研究了路由查找算法和流分類算法在快速路由器中的應(yīng)用。研究表明,基于分段壓縮的路由查找算法支持IPv6路由查找,具有合理的存儲(chǔ)容量和快速的查找時(shí)間;采用按值分支樹的多維綜合流分類算法支持前綴和范圍匹配,可擴(kuò)展性強(qiáng),適合大容量規(guī)則數(shù)據(jù)庫。兩種算法適合在快速路由器中應(yīng)用。關(guān)鍵詞體系結(jié)構(gòu); 路由查找;

2、 流分類; 快速路由器中圖分類號(hào)TP393 文獻(xiàn)標(biāo)識(shí)碼 AResearch on IP Route Lookup and Packet ClassificationAlgorithms for High Speed RouterYao Xingmiao,Li Lemin,Hu Guangming(Key Laboratory of Brodband Optical Fiber Transmission and Communication Networks UEST of China, Ministry of Education Chengdu 610054 Abstract The devel

3、opment of router architecture is analyzed, and the fast route lookup and packet classification algorithms for high speed router are researched. The research shows the lookup algorithm for IPv6 route lookup with compression trie has reasonable memory space and fast lookup time. The compositive multi-

4、dimensional packet classification algorithm based on tree divided by value is scalable.It can deal with prefixes match and range match for large rule sets. Two algorithms are suitable for high speed router.Key words router architecture; route lookup; packet classification; high speed router隨著Interne

5、t的快速發(fā)展和各種寬帶技術(shù)的不斷出現(xiàn),以及多種Internet業(yè)務(wù)的增長(zhǎng),路由器的體系結(jié)構(gòu)不斷發(fā)展,第一代路由器主要采用單處理器共享總線式結(jié)構(gòu),中央處理器通過通用的總線與多個(gè)接口卡互連。中央處理器負(fù)責(zé)包括路由收集,報(bào)文轉(zhuǎn)發(fā)處理等所有的事務(wù)處理。這種體系結(jié)構(gòu)的性能主要取決于中央處理器的速度和共享總線的帶寬,路由器擴(kuò)展性比較差。第二代路由器在網(wǎng)絡(luò)接口卡上采用了一些智能處理,如業(yè)務(wù)接口卡的cache技術(shù)來增加轉(zhuǎn)發(fā)速率。第三代路由器采用路由與轉(zhuǎn)發(fā)相分離的技術(shù),從而有效地解決了路由計(jì)算能力的問題,并且總線技術(shù)也得到了較大的發(fā)展。第四代路由器采用硬件ASIC轉(zhuǎn)發(fā)模式和交換結(jié)構(gòu),解決了帶寬容量和性能不足的問

6、題。第五代路由器繼承了第四代路由器的優(yōu)點(diǎn),增加了更為靈活的網(wǎng)絡(luò)處理器。對(duì)于一些復(fù)雜的標(biāo)準(zhǔn)操作,如路由查找算法等,采用硬件協(xié)處理器方式提高處理性能,實(shí)現(xiàn)軟件業(yè)務(wù)靈活性和高性能硬件轉(zhuǎn)發(fā)的有機(jī)結(jié)合。路由器技術(shù)不斷向前發(fā)展的同時(shí),也對(duì)路由器中的兩項(xiàng)關(guān)鍵技術(shù)快速路由查找和流分類技術(shù)提出新的要求,并且由于傳統(tǒng)的IPv4網(wǎng)絡(luò)需要逐步升級(jí)到下一代以IPv6協(xié)議為基礎(chǔ)的網(wǎng)絡(luò),還需要路由查找和流分類對(duì)IPv6協(xié)議支持,因此研究快速的路由查找和流分類算法在路由器中的應(yīng)用十分必要。本文從路由器的體系收稿日期:2004 07 15作者簡(jiǎn)介:姚興苗(1976 ,男,博士生,主要從事流分類和路由查找算法方面的研究.電子科技

7、大學(xué)學(xué)報(bào)第33卷664結(jié)構(gòu)發(fā)展入手,對(duì)快速的IPv4/IPv6路由查找算法和流分類算法進(jìn)行了研究和討論,得出了適合在快速路由器采用的快速路由查找和流分類算法。1 快速路由查找算法當(dāng)一個(gè)分組到達(dá)路由器時(shí),路由器必須根據(jù)其目的地址在路由轉(zhuǎn)發(fā)表中查找下一跳信息。轉(zhuǎn)發(fā)表一般按照如下的形式保存路由項(xiàng):<目的網(wǎng)絡(luò)地址/掩碼,邏輯端口號(hào)>,分組可能匹配多個(gè)端口,但分組最終選擇所有候選端口中相應(yīng)掩碼最長(zhǎng)的端口,這被稱為最長(zhǎng)前綴匹配(能夠有效的降低路由表的大小,并且在一定程度上緩和IPv4地址的枯竭問題。尋找高效的路由表查找算法是相當(dāng)困難,查找算法的性能不僅要考慮到快速查找時(shí)間,還要求低存儲(chǔ)空間和快

8、速路由表更新。路由查找算法大致分為3類:1 基于三態(tài)內(nèi)容可尋址存儲(chǔ)器(Ternary Content Addressable Memory, TCAM的算法:用TCAM來實(shí)現(xiàn)路由查找非常簡(jiǎn)單,只需要一次查找。如果存在多個(gè)匹配表項(xiàng),在經(jīng)過優(yōu)先級(jí)比較之后,就可確定下一跳信息。目前的TCAM存儲(chǔ)器容量較小,而且價(jià)格昂貴,另外,TCAM部件的功耗很大,不利于硬件集成。在克服TCAM的缺陷后,采用TCAM實(shí)現(xiàn)路由查找是一個(gè)不錯(cuò)的方案。文獻(xiàn)1,2提出了幾種不同的基于TCAM的查找算法。2 基于Hash的算法:文獻(xiàn)3提出了基于地址長(zhǎng)度的二分Hash查找算法,針對(duì)地址最大長(zhǎng)度為W比特的路由查找,需要O(lb

9、W次哈希表查找,需要的最大存儲(chǔ)空間為O(NW,其中N為路由表中的表項(xiàng)數(shù)目。但是算法不易硬件實(shí)現(xiàn),并且如何尋找高效的哈希函數(shù)還需進(jìn)行研究。3 基于Trie的算法4:Trie又稱為數(shù)字查找樹(DST。最簡(jiǎn)單的Trie就是二叉查找樹。查找樹算法通?？梢岳密浖?shí)現(xiàn)。但它的查找速度慢,最壞情況下,所需要的查找次數(shù)是O(W次,二叉樹的數(shù)據(jù)結(jié)構(gòu)需要的存儲(chǔ)空間在最壞情況下為O(NW。路徑壓縮樹和級(jí)壓縮樹對(duì)二叉查找樹作了改進(jìn),但是其動(dòng)態(tài)性能較差?；诙啾忍夭檎覙?Multibit Tries的算法一次查找多個(gè)比特5,6,與基本的二叉樹相比大大降低了查找時(shí)間復(fù)雜度。多比特查找樹的分段式硬件查找算法將多比特查找樹

10、中的節(jié)點(diǎn)通過簡(jiǎn)單的地址映射與路由表項(xiàng)的硬件存儲(chǔ)地址關(guān)聯(lián),從而達(dá)到高速的查找速率。典型的查找算法是文獻(xiàn)7提出的DIR 24-8方案。分段式硬件查找算法具有查表速率快,結(jié)構(gòu)簡(jiǎn)單,易于實(shí)現(xiàn),對(duì)硬件要求不高等優(yōu)點(diǎn),適合在快速路由器上實(shí)現(xiàn)。但多數(shù)算法專門針對(duì)IPv4路由查找,不易擴(kuò)展到IPv6查找。文獻(xiàn)8提出的算法是一種基于分段路由查找方法,可擴(kuò)展到IPv6查找。但是它針對(duì)IPv6查找所需存儲(chǔ)空間是令人難以接受的。文獻(xiàn)9提出了一種基于分段壓縮的方案,與文獻(xiàn)8提出的算法相比,該算法能進(jìn)行空間壓縮,算法需要存儲(chǔ)空間小,并且算法的平均查找時(shí)間少。因此,算法能夠在需要對(duì)IPv6路由查找支持的快速路由器上實(shí)現(xiàn)。表

11、1所示列出了幾種路由查找算法的性能。表1 幾種路由查找算法比較算法查找復(fù)雜度更新復(fù)雜度存儲(chǔ)空間備注TCAM方案O(1 O(N O(N二分Hash查找O(W O(lb W O(W lb N二叉Tire樹O(W O(W O(NW多比特Tire樹O(W O(W/K +2K O(2K NW/KMBDIR 24-8方案O(2 O(216 33LLCAT方案O(W/K O(W/K +2(K1 O(2K NW/K 支持IPv6分段壓縮方案O(W/K O(W/K +2K+M O(2K NW/KM 支持IPv62 快速流分類查找算法隨著路由器的發(fā)展和多種業(yè)務(wù)的需求,如不同的用戶需要不同的Qos要求,一些如接納控

12、制,資源預(yù)留,公平調(diào)度等新技術(shù)需要在路由器上實(shí)現(xiàn)。而實(shí)現(xiàn)這些技術(shù)的前提條件是需要對(duì)分組進(jìn)行分類。分類主要依第6期姚興苗等: 快速路由器的路由查找和流分類算法研究665據(jù)分組中第三層分組頭中的第四層協(xié)議類型、源地址和目的地址,第四層報(bào)文頭中的源端口和目的端口號(hào)等信息,有時(shí)候還包括第二層的MAC地址和更上層的頭信息乃至分組的內(nèi)容。流分類算法大致可以分為以下3類:1 基于硬件的查找算法:基于硬件TCAM的流分類算法10, 11,算法性能要受到TCAM缺陷的制約。重復(fù)流分類算法是一種多維的流分類算法12,其優(yōu)點(diǎn)是查找時(shí)間快并能同時(shí)支持前綴和范圍匹配,但是需要的存儲(chǔ)空間太大,算法不易擴(kuò)展。位向量算法便于

13、硬件實(shí)現(xiàn)13,在小規(guī)則數(shù)量時(shí)具有快速的查找速度,但查找時(shí)間隨著規(guī)則數(shù)量的增加線性增加。聚合位向量算法使用聚合位向量的方法改進(jìn)了BV算法的查找時(shí)間14,但是所需要的存儲(chǔ)容量增大。2 基于查找數(shù)的算法:這一類流分類算法的主要特征是:在預(yù)處理時(shí)建立以查找樹為中心的數(shù)據(jù)結(jié)構(gòu),流分類時(shí)通過一次或多次訪問查找樹得到分類結(jié)果。這類方法如查找樹網(wǎng)格等15。該類算法的空間復(fù)雜性相對(duì)較小,但算法數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜,不易硬件實(shí)現(xiàn)。3 基于Hash的算法:流分類的Hash表方法有2種實(shí)現(xiàn)途徑,(1是直接使用Hash函數(shù)實(shí)現(xiàn)流分類。(2是預(yù)先對(duì)流分類規(guī)則作某些處理,以達(dá)到降低沖突率的目的,如文獻(xiàn)16提出的元組空間搜索算法

14、。但還需研究針對(duì)流分類有效的Hash函數(shù)。由于流分類規(guī)則數(shù)量和規(guī)則維數(shù)不斷擴(kuò)展,上述的流分類算法不能完全滿足路由器要求。為此流分類算法應(yīng)該綜合使用多種方法,按流分類過程本身的特點(diǎn),將其劃分為多個(gè)階段,根據(jù)每個(gè)階段特點(diǎn)和流分類總體目標(biāo)進(jìn)行不同處理。Modular算法實(shí)際上就是這樣的一種算法17,它將查找分為三個(gè)階段,對(duì)每一階段使用不同的優(yōu)化算法。Modular算法將每一維規(guī)則看作前綴的形式,使它能夠適應(yīng)規(guī)則的擴(kuò)展。然而它只支持前綴匹配,不能夠直接支持范圍匹配。在多維的規(guī)則匹配中,有些維是需要范圍匹配的。同時(shí)由于Modular方法使用索引跳轉(zhuǎn)表,某些規(guī)則可能在子樹和葉子規(guī)則束中重復(fù)多次,可能會(huì)引起

15、存儲(chǔ)空間的爆炸。針對(duì)Modular算法存在的問題,文獻(xiàn)18提出了一種適用于多維、大容量、可擴(kuò)展的按值分支樹高效流分類查找算法,算法同時(shí)支持前綴匹配和范圍匹配,能處理大型的流分類數(shù)據(jù)庫。由于對(duì)于規(guī)則每維的匹配類型沒有嚴(yán)格的要求,規(guī)則的維數(shù)也容易擴(kuò)展。算法不僅可以軟件實(shí)現(xiàn),還可實(shí)現(xiàn)硬件的查找,是一種能在快速路由器上應(yīng)用的流分類算法。表2所示為幾種流分類算法比較。表2 幾種流分類算法比較算法支持的規(guī)則類型支持的元組數(shù)算法類型備注TCAM方案前綴匹配多元組硬件算法硬件CAM 重復(fù)流分類算法前綴、范圍匹配多元組可硬件實(shí)現(xiàn)位向量前綴匹配多元組硬件算法查找樹網(wǎng)格前綴匹配二元組軟件算法元組空間搜索前綴匹配多元

16、組可硬件實(shí)現(xiàn)Modular算法前綴匹配多元組可硬件實(shí)現(xiàn)按值分支樹算法前綴、范圍匹配多元組可硬件實(shí)現(xiàn)3 結(jié)束語本文對(duì)快速路由查找和流分類算法進(jìn)行了討論,并指出了快速路由器對(duì)路由查找和流分類算法的要求。隨著路由表數(shù)量和流分類規(guī)則數(shù)量的增多,基于分段壓縮的快速路由查找算法和綜合的流分類算法更適合在快速路由器中應(yīng)用。另外,考慮要支持IPv6協(xié)議,路由查找算法和流分類算法還需具有對(duì)協(xié)議的擴(kuò)展性要求。參考文獻(xiàn)1 Ravikumar V C, Mahapatra R N. TCAM architecture for IP lookup using prefix propertiesJ. IEEE Micro

17、, 2004, 24(2: 60-69電子科技大學(xué)學(xué)報(bào)第33卷6662 Liang Zhiyong, Wu Jianping, Xu Ke. A TCAM-based IP lookup scheme for multi-nexthop routingC. InternationalConference on Computer Networks and Mobile Computing, Shanghai, China, 2003. 128-1353 Waldvogel M, Varghese G, Turner J, et al. Scalable high speed IP routing

18、 lookupsC. Proceedings of ACMSIGCOMM 97, French Riviera, 1997. 25-364 Tzeng HH-Y, Przygienda T. On fast address-lookup algorithmsJ. IEEE Journal of Select Areas in Communication,1999, 17(6: 1 067-1 0825 Sahni S, Kun Suk Kim. Efficient construction of multibit tries for IP lookupJ. IEEE/ACM Transacti

19、ons onNetworking, 2003, 11(4: 650-6626 Jia Jinpeng, Lin Chuang, Liu Weidong. A fast two-way IP lookup algorithm based multibit-trieC. InternationalConference on Computer Networks and Mobile Computing, Shanghai, China, 2003. 136-1427 Gupta P, Lin S, McKeown N. Routing lookups in hardware at memory ac

20、cess speedsC. Proceedings. IEEEINFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco 1998. 1 240-1 2478 Yilmaz P, Belekiy A, Uzun N, et al. A Trie-based algorithm for IP lookup problemC. IEEE GLOBECOM2000, SanFrancisco, 2000. 593-5989 Y

21、ao Xingmiao, Li Lemin, Hu Guangming. A fast IPv6 route lookup algorithm with hash compressionC. 2004International Conference on Communications, Circuits and Systems, Chengdu, China, 2004. 674-67710 Van L J, Engbersen T. Fast and scalable packet classificationJ. IEEE J. on SAC, 2003, 21(4: 560-57111

22、Liu Huan. Efficient mapping of range classifier into ternary-CAMC. Proceedings of 10th symposium on HighPerformance Interconnects, California, 2002. 95-10012 Pankaj P, McKeown N. Packet classification on multiple fieldsC. Proceedings of ACM Sigcomm, Cambridge,1999. 147-16013 Lakshman T V, Stiliadis D. High-speed policy-based packet forwarding using efficient multi-dimensional rangematchingC. Proceedings of ACM Sigcomm, Vancouver, Ca