星上路由查找設(shè)計(jì)與算法實(shí)現(xiàn)

田 園,張曙光,喬廬峰,邵世雷

(解放軍理工大學(xué)通信工程學(xué)院,江蘇 南京 210007)

隨著寬帶業(yè)務(wù)需求的不斷增長,地面 Internet、4G移動(dòng)通信系統(tǒng)及衛(wèi)星網(wǎng)絡(luò)互相結(jié)合、互為補(bǔ)充的模式逐漸成為全球互聯(lián)網(wǎng)的基本結(jié)構(gòu)。衛(wèi)星網(wǎng)絡(luò)將成為下一代全球信息網(wǎng)絡(luò)的重要組成部分。衛(wèi)星通信從非再生中繼式的載波彎管,再生式的比特彎管,逐步發(fā)展到更加復(fù)雜高效的星上處理和星上交換?；贗P技術(shù)的星上路由器,相較于星上ATM交換技術(shù)在提高業(yè)務(wù)性能、接納控制能力、資源利用率和全網(wǎng)的協(xié)議一致性等方面都有很大的優(yōu)勢,已成為研究的一個(gè)熱點(diǎn)。但由于衛(wèi)星空間環(huán)境的特殊要求,使得星載路由交換系統(tǒng)在設(shè)計(jì)上受到體積、功耗、可靠性等諸多因素的限制。路由查找是路由器實(shí)現(xiàn)路由轉(zhuǎn)發(fā)功能的關(guān)鍵技術(shù)之一,設(shè)計(jì)一個(gè)適合星上的路由查找算法就顯得的格外重要。也即面臨著如何采用簡捷高效的設(shè)計(jì)、在有限平臺(tái)資源條件下達(dá)到更高性能的問題。

1 算法分析

目前的路由查找都是基于最長地址前綴匹配方式的,即從所有和目的 IP地址匹配的路由表項(xiàng)中找出前綴最長的作為最終的路由查找結(jié)果。該方法在查找過程中,不僅需要與地址前綴的比特值進(jìn)行匹配查找,而且還需要考慮地址前綴的長度,因此各種路由查找算法都可以歸結(jié)為兩個(gè)方面的匹配查找過程:基于地址前綴值的路由查找算法和基于地址前綴長度的路由查找算法。在路由查找算法中,最為極端的是線性查找和采用內(nèi)容匹配(CAM:Content Addressable Memory)的路由查找。采用線性查找時(shí),輸入的IP地址和路由表中的每個(gè)表項(xiàng)進(jìn)行逐一比較,如果表項(xiàng)長度為 N,那么就需要比較 N次,從中找出最長匹配的前綴。這種方式下需要至少N個(gè)時(shí)鐘周期才能完成匹配操作,所以不實(shí)用。采用CAM結(jié)構(gòu)時(shí),輸入IP地址同時(shí)跟N個(gè)表項(xiàng)中的內(nèi)容進(jìn)行匹配比較,同時(shí)給出匹配結(jié)果,然后根據(jù)匹配結(jié)果的優(yōu)先級(jí)給出最長前綴匹配結(jié)果。采用CAM結(jié)構(gòu)時(shí),其匹配時(shí)間只需要1個(gè)時(shí)鐘周期,但其資源消耗和功耗都比較大。

除了上述兩種極端的情況之外,采用各種算法來實(shí)現(xiàn)路由查找功能是研究的熱點(diǎn),主要包括二進(jìn)制Trie樹算法、路徑壓縮Trie樹算法、多分支Trie樹算法、前綴長度的二分查找法以及地址區(qū)間的二分查找法等。在關(guān)鍵字長度為 W,前綴數(shù)目為 N,步長為k的情況下,不同算法的復(fù)雜度如表1所示。

從上分析可知基于硬件和軟件的查找算法各有利弊,硬件查找(如 TCAM 算法)的速度快,但內(nèi)存利用率低、資源消耗大,不能直接用于星上處理;而軟件算法(如Trie樹等)具有較好的數(shù)據(jù)組織結(jié)構(gòu),對資源消耗小,但性能有限。FPGA芯片是目前實(shí)現(xiàn)復(fù)雜數(shù)字系統(tǒng)時(shí)常用的可編程邏輯器件,可以更加靈活高效地實(shí)現(xiàn)查找功能。因此,本文利用軟硬件協(xié)同設(shè)計(jì)的思想,主要是通過軟件算法來實(shí)現(xiàn)路由表在節(jié)點(diǎn)存儲(chǔ)區(qū)的組織結(jié)構(gòu),而具體的查找過程交由硬件來完成,這樣既可以克服存儲(chǔ)資源有限的限制,又可以滿足較快的查找速度。

表 1 不同算法復(fù)雜度比較

2 路由查找設(shè)計(jì)

在研究中我們先設(shè)計(jì)出了一個(gè) 8端口星上路由器的系統(tǒng)硬件結(jié)構(gòu)圖,如圖 1所示。該體系采用了基于FPGA的設(shè)計(jì)架構(gòu),將功能分為三個(gè)模塊:查找引擎、隊(duì)列管理器與交換結(jié)構(gòu)。查找引擎負(fù)責(zé)數(shù)據(jù)鏈路層協(xié)議的處理(如封裝改變)、IP包的提取和依據(jù)路由表對目的地址進(jìn)行匹配查找;隊(duì)列管理器按照一定的調(diào)度策略對目標(biāo)是同一輸出隊(duì)列的分組進(jìn)行排隊(duì)和調(diào)度管理;交換結(jié)構(gòu)實(shí)現(xiàn)高性能的數(shù)據(jù)交換?？梢娫O(shè)計(jì)星上路由器的一個(gè)瓶頸是如何在有效的資源條件下實(shí)現(xiàn)快速有效的路由查找機(jī)制。

圖1 8端口路由器硬件平臺(tái)結(jié)構(gòu)

圖2是IP路由查找電路的基本結(jié)構(gòu)示意圖。圖中的IP報(bào)文輸入緩沖區(qū)用于暫存來自同一端口或不同端口的 IP報(bào)文,其應(yīng)具有一定深度。IP路由查找引擎負(fù)責(zé)提取輸入 IP報(bào)文頭部的目的地址區(qū)域,并以目的地址為索引在節(jié)點(diǎn)存儲(chǔ)區(qū)內(nèi)進(jìn)行最長匹配查找。最長匹配查找到的結(jié)果是路由表索引,根據(jù)該索引,IP路由查找引擎從路由表中讀出該報(bào)文的轉(zhuǎn)發(fā)端口。在路由表中,除了常規(guī)的轉(zhuǎn)發(fā)表項(xiàng)外,還包括一些特殊的轉(zhuǎn)發(fā)表項(xiàng),如缺省轉(zhuǎn)發(fā)、多投、轉(zhuǎn)交給星載處理器等控制信息。IP路由查找引擎內(nèi)部有路由表管理寄存器,該寄存器可以被星載處理器所訪問,星載處理器可以通過路由表管理寄存器對節(jié)點(diǎn)存儲(chǔ)區(qū)和路由表進(jìn)行維護(hù)和更新。需要說明的是,路由表的建立和更新是由星載處理器依靠路由協(xié)議來完成的,但不在本文的研究范圍之內(nèi)。本設(shè)計(jì)假設(shè)路由表項(xiàng)數(shù)量較大,存儲(chǔ)資源有限的情況,采用路徑壓縮Trie樹算法;當(dāng)然表項(xiàng)數(shù)量少,可用存儲(chǔ)資源較充裕的情況下,可以采用傳統(tǒng)的 Trie樹算法或是多分支Trie樹算法,本文并未考慮。

圖2 IP路由查找電路示意圖

3 算法實(shí)現(xiàn)

從表 1中我們知道,路徑壓縮算法的查找復(fù)雜度為 O(W),算法的時(shí)間復(fù)雜度與表項(xiàng)的數(shù)目沒有關(guān)系,只與關(guān)鍵字 W的長度有關(guān),對于硬件實(shí)現(xiàn)來說則取決于處理器訪問內(nèi)存的頻率。采用路徑壓縮算法不僅可以減少節(jié)點(diǎn)存儲(chǔ)區(qū)內(nèi)存消耗,還可以縮短平均搜索的深度。但由于傳統(tǒng)的Trie樹算法使用的樹的節(jié)點(diǎn)靈活度非常高,所以直接用于硬件實(shí)現(xiàn)不太可取,需要改進(jìn)。本算法的思想是利用硬件的并行技術(shù)的優(yōu)勢,通過一次查找多個(gè)比特,來減少內(nèi)存訪問的次數(shù),提高查找的速度。算法中定義一次最多能查找4個(gè)比特,以降低FPGA實(shí)現(xiàn)的難度。同時(shí)利用多進(jìn)制壓縮算法良好的數(shù)據(jù)組織結(jié)構(gòu)來減少存儲(chǔ)空間的消耗,從而在速度和資源上取得了很好的平衡。程序用C語言編寫,測試環(huán)境為Visual C++ 6.0,路由表的IP地址和Mask地址均由隨機(jī)函數(shù)rand()生成。

算法數(shù)據(jù)結(jié)構(gòu)及初始化:

1)每個(gè)結(jié)點(diǎn)有如下字段:左兒子下標(biāo) LSON、右兒子RSON、是否擴(kuò)展SF、路由索引RINDEX;

2)樹結(jié)點(diǎn)用結(jié)構(gòu)數(shù)組存儲(chǔ),數(shù)組名是Tree[];

3)第 0個(gè)元素是總樹根,Root=0,開始時(shí),Tree[0]所有字段為0;

4)其它樹結(jié)點(diǎn)從1號(hào)元素開始分配;每分配一個(gè)結(jié)點(diǎn),把該結(jié)點(diǎn)清零;

5)令路由表R={r1,r2,…,rn},其中每個(gè)ri=,最高位定義為第1位,最低位定義為第32位;

6)調(diào)用下面算法構(gòu)造Trie樹:

ErrFlag=BuildTrieTree(R,Root,1);

算法如下:

算法的優(yōu)點(diǎn)是無需對路由表進(jìn)行排序,并且在構(gòu)造過程中沒有回溯,提高了樹構(gòu)造的效率。為了便于說明我們隨機(jī)生成了表項(xiàng)數(shù)為7的路由表,如圖3所示。實(shí)際中路由表由路由協(xié)議生成或是人工配置。算法運(yùn)行后,路由表表項(xiàng)在節(jié)點(diǎn)存儲(chǔ)區(qū)的數(shù)據(jù)結(jié)構(gòu)見表 2,表中的節(jié)點(diǎn)序號(hào)對應(yīng)于節(jié)點(diǎn)在內(nèi)存的存儲(chǔ)地址,并采用了十六進(jìn)位制,便于直觀顯示。其 Trie樹結(jié)構(gòu)如圖4所示,灰色的節(jié)點(diǎn)表示對應(yīng)著路由表索引,節(jié)點(diǎn)內(nèi)的數(shù)字為節(jié)點(diǎn)序號(hào),同樣為十六進(jìn)位制。

圖3 隨機(jī)生成的路由表表項(xiàng)

圖4 節(jié)點(diǎn)存儲(chǔ)區(qū)的樹結(jié)構(gòu)

表2 節(jié)點(diǎn)存儲(chǔ)區(qū)數(shù)據(jù)結(jié)構(gòu)

圖5為算法的測試程序界面,其中“葉子個(gè)數(shù)”為圖 4中灰色節(jié)點(diǎn),表示路由表中表項(xiàng)的數(shù)目,“樹的大小”為形成樹的總的節(jié)點(diǎn)數(shù)等于節(jié)點(diǎn)存儲(chǔ)區(qū)中占用的地址數(shù),“時(shí)鐘”為構(gòu)造樹消耗的硬件時(shí)鐘周期,單節(jié)點(diǎn)耗費(fèi)為＝“時(shí)鐘/樹的大小”。經(jīng)過多次測試表明,算法的平均壓縮比為 1:4,平均單節(jié)點(diǎn)消耗為 400個(gè)時(shí)鐘周期。在星上路由器的設(shè)計(jì)中,若采用的處理器的時(shí)鐘頻率為 50MHz,SRAM 容量為64*40 K /8 = 320KB 。采用的路由表的表項(xiàng)數(shù)目為1K 項(xiàng),算法數(shù)據(jù)結(jié)構(gòu)占用的存儲(chǔ)空間為1K *4*64/8 = 32KB ,僅占SRAM容量的10%。算法在最差的情況下需要查找 32次,查找一次所需的時(shí)間為 32/50*10-6=640ns ,查找速度可以達(dá)到每秒 150萬次。Gupta等人在文獻(xiàn)中通過統(tǒng)計(jì)Internet網(wǎng)絡(luò)中前綴長度的分布,發(fā)現(xiàn) 99.93%的前綴長度都分布在24或小于 24的范圍內(nèi)。因此實(shí)際速度每秒可以達(dá)到200萬次,假設(shè)數(shù)據(jù)報(bào)的長度是40bye(IP報(bào)的最短長度),則轉(zhuǎn)發(fā)速度為 200*40*8*106=640Mbit/s ,可以滿足寬帶衛(wèi)星通信系統(tǒng)業(yè)務(wù)的需求。

圖5 算法測試程序

4 結(jié)束語

本文從硬件的角度對星上IP路由查找算法實(shí)現(xiàn)做了一系列的分析,并提出了改進(jìn)的 Trie樹算法,給出了相應(yīng)的便于用硬件實(shí)現(xiàn)的 IP路由表的數(shù)據(jù)結(jié)構(gòu)。由于VHDL/Verilog HDL語言固有的靈活性和可編程性,可以更為靈活和高效的實(shí)現(xiàn)路由查找。所以,使用FPGA芯片來實(shí)現(xiàn)路由查找,是未來的趨勢。

[1]Del R E, Pierucci L. Next-generation Satellite Networks[J].IEEE Communication Magazine,2002,40(9):50-159.

[2]肖鵬,張濤,劉鋒. 基于無線接入的一體化星載路由交換系統(tǒng)[J].計(jì)算工程,2008,34(12):277-279.

[3]徐恪,吳建平,徐明偉.高等計(jì)算機(jī)網(wǎng)絡(luò)[M].北京:機(jī)械工業(yè)出版社,2003.

[4]M.Sanchez, E.W.Biersack, W.Dabbous, Surey and taxonomy of IP address lookup algorithms[J], IEEE Network,2001,15(2):18-23.

[5]Pankaj Gupta, Steven Lin, and Nick Mckeown. Routing Lookups in Hardware at Memory Acess Speeds[C]//Proceeding of the IEEE INFOCOM,1998.