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

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

隨著寬帶業(yè)務(wù)需求的不斷增長(zhǎng),地面 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ù)雜高效的星上處理和星上交換。基于IP技術(shù)的星上路由器,相較于星上ATM交換技術(shù)在提高業(yè)務(wù)性能、接納控制能力、資源利用率和全網(wǎng)的協(xié)議一致性等方面都有很大的優(yōu)勢(shì),已成為研究的一個(gè)熱點(diǎn)。但由于衛(wèi)星空間環(huán)境的特殊要求,使得星載路由交換系統(tǒng)在設(shè)計(jì)上受到體積、功耗、可靠性等諸多因素的限制。路由查找是路由器實(shí)現(xiàn)路由轉(zhuǎn)發(fā)功能的關(guān)鍵技術(shù)之一,設(shè)計(jì)一個(gè)適合星上的路由查找算法就顯得的格外重要。也即面臨著如何采用簡(jiǎn)捷高效的設(shè)計(jì)、在有限平臺(tái)資源條件下達(dá)到更高性能的問題。

1 算法分析

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

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

從上分析可知基于硬件和軟件的查找算法各有利弊,硬件查找(如 TCAM 算法)的速度快,但內(nèi)存利用率低、資源消耗大,不能直接用于星上處理;而軟件算法(如Trie樹等)具有較好的數(shù)據(jù)組織結(jié)構(gòu),對(duì)資源消耗小,但性能有限。FPGA芯片是目前實(shí)現(xiàn)復(fù)雜數(shù)字系統(tǒng)時(shí)常用的可編程邏輯器件,可以更加靈活高效地實(shí)現(xiàn)查找功能。因此,本文利用軟硬件協(xié)同設(shè)計(jì)的思想,主要是通過軟件算法來(lái)實(shí)現(xiàn)路由表在節(jié)點(diǎn)存儲(chǔ)區(qū)的組織結(jié)構(gòu),而具體的查找過程交由硬件來(lái)完成,這樣既可以克服存儲(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ù)路由表對(duì)目的地址進(jìn)行匹配查找;隊(duì)列管理器按照一定的調(diào)度策略對(duì)目標(biāo)是同一輸出隊(duì)列的分組進(jìn)行排隊(duì)和調(diào)度管理;交換結(jié)構(gòu)實(shí)現(xiàn)高性能的數(shù)據(jù)交換。可見設(shè)計(jì)星上路由器的一個(gè)瓶頸是如何在有效的資源條件下實(shí)現(xiàn)快速有效的路由查找機(jī)制。

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

圖2是IP路由查找電路的基本結(jié)構(gòu)示意圖。圖中的IP報(bào)文輸入緩沖區(qū)用于暫存來(lái)自同一端口或不同端口的 IP報(bào)文,其應(yīng)具有一定深度。IP路由查找引擎負(fù)責(zé)提取輸入 IP報(bào)文頭部的目的地址區(qū)域,并以目的地址為索引在節(jié)點(diǎn)存儲(chǔ)區(qū)內(nèi)進(jìn)行最長(zhǎng)匹配查找。最長(zhǎng)匹配查找到的結(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)部有路由表管理寄存器,該寄存器可以被星載處理器所訪問,星載處理器可以通過路由表管理寄存器對(duì)節(jié)點(diǎn)存儲(chǔ)區(qū)和路由表進(jìn)行維護(hù)和更新。需要說(shuō)明的是,路由表的建立和更新是由星載處理器依靠路由協(xié)議來(lái)完成的,但不在本文的研究范圍之內(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的長(zhǎng)度有關(guān),對(duì)于硬件實(shí)現(xiàn)來(lái)說(shuō)則取決于處理器訪問內(nèi)存的頻率。采用路徑壓縮算法不僅可以減少節(jié)點(diǎn)存儲(chǔ)區(qū)內(nèi)存消耗,還可以縮短平均搜索的深度。但由于傳統(tǒng)的Trie樹算法使用的樹的節(jié)點(diǎn)靈活度非常高,所以直接用于硬件實(shí)現(xiàn)不太可取,需要改進(jìn)。本算法的思想是利用硬件的并行技術(shù)的優(yōu)勢(shì),通過一次查找多個(gè)比特,來(lái)減少內(nèi)存訪問的次數(shù),提高查找的速度。算法中定義一次最多能查找4個(gè)比特,以降低FPGA實(shí)現(xiàn)的難度。同時(shí)利用多進(jìn)制壓縮算法良好的數(shù)據(jù)組織結(jié)構(gòu)來(lái)減少存儲(chǔ)空間的消耗,從而在速度和資源上取得了很好的平衡。程序用C語(yǔ)言編寫,測(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)是無(wú)需對(duì)路由表進(jìn)行排序,并且在構(gòu)造過程中沒有回溯,提高了樹構(gòu)造的效率。為了便于說(shuō)明我們隨機(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)對(duì)應(yīng)于節(jié)點(diǎn)在內(nèi)存的存儲(chǔ)地址,并采用了十六進(jìn)位制,便于直觀顯示。其 Trie樹結(jié)構(gòu)如圖4所示,灰色的節(jié)點(diǎn)表示對(duì)應(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為算法的測(cè)試程序界面,其中“葉子個(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)過多次測(cè)試表明,算法的平均壓縮比為 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萬(wàn)次。Gupta等人在文獻(xiàn)中通過統(tǒng)計(jì)Internet網(wǎng)絡(luò)中前綴長(zhǎng)度的分布,發(fā)現(xiàn) 99.93%的前綴長(zhǎng)度都分布在24或小于 24的范圍內(nèi)。因此實(shí)際速度每秒可以達(dá)到200萬(wàn)次,假設(shè)數(shù)據(jù)報(bào)的長(zhǎng)度是40bye(IP報(bào)的最短長(zhǎng)度),則轉(zhuǎn)發(fā)速度為 200*40*8*106=640Mbit/s ,可以滿足寬帶衛(wèi)星通信系統(tǒng)業(yè)務(wù)的需求。

圖5 算法測(cè)試程序

4 結(jié)束語(yǔ)

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

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

[2]肖鵬,張濤,劉鋒. 基于無(wú)線接入的一體化星載路由交換系統(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.