路由查找算法研究綜述

《路由查找算法研究綜述》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1000-9825/2002/13(01)0042-09?2002JournalofSoftware軟件學(xué)報(bào)Vol.13,No.1路由查找算法研究綜述?徐恪,徐明偉,吳建平,吳劍(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系網(wǎng)絡(luò)研究所,北京100084)E-mail:xuke@tsinghua.edu.cn;xmw@csnet1.cs.tsinghua.edu.cnhttp://netlab.cs.tsinghua.edu.cn摘要:隨著Internet的迅猛發(fā)展,用于主干網(wǎng)絡(luò)互聯(lián)的核心路由器的接口速率已經(jīng)達(dá)到了2.5Gbps~10Gbps.這一速率要求核心

2、路由器每秒能夠轉(zhuǎn)發(fā)幾百萬(wàn)乃至上千萬(wàn)個(gè)以上的分組.分組轉(zhuǎn)發(fā)的重要一步就是查找路由表,因此快速的路由查找算法是實(shí)現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵.路由查找需要實(shí)現(xiàn)最長(zhǎng)前綴匹配.近年來(lái),研究人員提出了多種路由查找算法,以提高查找性能.分析了路由查找問(wèn)題及其難點(diǎn),全面綜述了各種查找算法,并對(duì)它們進(jìn)行了詳細(xì)的分析和比較,最后指出了進(jìn)一步的研究方向.關(guān)鍵詞:路由查找;最長(zhǎng)前綴匹配;Trie樹(shù);哈希;CAM中圖法分類(lèi)號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A路由器的主要功能是按照IP分組中的目的地址轉(zhuǎn)發(fā)分組.查找路由表決定將分組發(fā)往哪個(gè)端口,這是轉(zhuǎn)發(fā)分組過(guò)程中的重要一步.因此,快

3、速的IP地址查找算法是實(shí)現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵.傳統(tǒng)的查找方法(如順序查找法、二分查找法)只能完成關(guān)鍵字的精確查找,而路由查找需要完成最長(zhǎng)匹配地址前綴的查找.為了提高路由查找的性能,研究人員提出了多種路由查找算法.本文首先分析了路由查找問(wèn)題和實(shí)現(xiàn)難點(diǎn),然后全面綜述了各種查找算法,并對(duì)它們進(jìn)行了詳細(xì)的分析和比較.1Internet地址結(jié)構(gòu)的發(fā)展在Internet的發(fā)展初期,IPv4地址采用的是基于類(lèi)的地址結(jié)構(gòu).整個(gè)IP地址空間一共分為5類(lèi):為單播地址設(shè)計(jì)的A,B,C類(lèi);為組播地址設(shè)計(jì)的D類(lèi);為今后使用而保留的E類(lèi)地址.各個(gè)類(lèi)之間由地址的前幾個(gè)比

4、特位來(lái)區(qū)分.在Internet發(fā)展的初期,基于類(lèi)的地址結(jié)構(gòu)由于其簡(jiǎn)單性而得到了廣泛的應(yīng)用.但是,隨著網(wǎng)絡(luò)的不斷發(fā)展,使用這種地址結(jié)構(gòu)產(chǎn)生了兩個(gè)問(wèn)題.一個(gè)問(wèn)題是地址分配的不靈活導(dǎo)致了地址空間的大量消耗以及路由表規(guī)模的不斷增大.基于類(lèi)的地址結(jié)構(gòu)將整個(gè)地址空間簡(jiǎn)單地分成了5個(gè)類(lèi)別,這就導(dǎo)致了地址的分配非常不靈活.另一個(gè)問(wèn)題是,由于路由器需要記錄所有已經(jīng)分配的網(wǎng)絡(luò)地址,特別是對(duì)于C類(lèi)地址來(lái)說(shuō),由于它的地址前綴特別多,如果記錄所有的C類(lèi)地址,那么路由表的規(guī)模將變得非常大.為了降低路由表規(guī)模的增長(zhǎng)速度以及提高地址空間的利用率,IETF提出了一種稱(chēng)為無(wú)類(lèi)

5、域間路由[1~2](classlessinter-domainrouting,簡(jiǎn)稱(chēng)CIDR)的地址結(jié)構(gòu).CIDR摒棄了傳統(tǒng)上基于類(lèi)的地址分配方式,規(guī)定可以使用任意長(zhǎng)度的網(wǎng)絡(luò)地址部分,因此產(chǎn)生了路由地址前綴的概念.使用CIDR的好處是明顯的,它提高了地址空間的利用率,例如為300臺(tái)主機(jī)分配網(wǎng)絡(luò)地址只需使用一個(gè)23位網(wǎng)絡(luò)地址前綴長(zhǎng)度的網(wǎng)絡(luò)地址(可以支持?收稿日期:2001-05-30;修改日期:2001-09-14基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(90104002);國(guó)家863高科技發(fā)展計(jì)劃資助項(xiàng)目(863-306-ZD-07-01)作者簡(jiǎn)介

6、:徐恪(1974－),男,江蘇洪澤人,博士,講師,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu),分布式路由器操作系統(tǒng),高性能路由器體系結(jié)構(gòu);徐明偉(1971－),男,遼寧朝陽(yáng)人,博士,副教授,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)體系體系結(jié)構(gòu),高性能路由器體系結(jié)構(gòu),網(wǎng)絡(luò)性能測(cè)試;吳建平(1953－),男,山西太原人,博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議測(cè)試,形式化技術(shù);吳劍(1977－),男,浙江杭州人,碩士,主要研究領(lǐng)域是高速路由查找算法,分布式路由協(xié)議.徐恪等:路由查找算法研究綜述43512臺(tái)主機(jī))就可以滿(mǎn)足要求.為了滿(mǎn)足網(wǎng)絡(luò)

7、規(guī)模不斷增長(zhǎng)的需要,IETF設(shè)計(jì)了新一代的網(wǎng)絡(luò)協(xié)議IPv6,也被稱(chēng)為IPng.IPv6與IPv4相比,在地址格式上發(fā)生了巨大的改變,地址長(zhǎng)度由原來(lái)的32位變成了128位,相應(yīng)地,IPv6在整個(gè)地址分配上也進(jìn)行[3]了一定的改進(jìn).盡管IPv6的地址結(jié)構(gòu)與IPv4相比有很多的不同之處,但是從根本上來(lái)說(shuō),整個(gè)地址空間仍然是層次性結(jié)構(gòu),仍然支持類(lèi)似于IPv4CIDR地址結(jié)構(gòu)下的路由合并,因此新一代的網(wǎng)絡(luò)協(xié)議并沒(méi)有改變路由查找的本質(zhì)特點(diǎn).2路由查找算法分析2.1路由查找算法的分類(lèi)最長(zhǎng)地址前綴匹配查找的難點(diǎn)在于,在查找過(guò)程中不僅需要與地址前綴的比特值進(jìn)

8、行匹配查找,而且還需要考慮地址前綴的長(zhǎng)度,因此各種路由查找算法都可以歸結(jié)為這兩個(gè)方面的匹配查找過(guò)程.2.1.1基于地址前綴值的路由查找算法基于地址前綴值路由查找算法的特點(diǎn)是通過(guò)對(duì)