郭潤偉
摘要:隨著互聯(lián)網(wǎng)絡鏈路速率的不斷提高,路由查找已成為路由器報文轉(zhuǎn)發(fā)的瓶頸。本文首先介紹和分析了路由器中廣泛使用的各種典型IP 路由算法方法,并提出一種基于多分枝 trie樹的改進路由查找算法。該算法保留了多分支trie樹訪存次數(shù)少,查詢速度快的特點,并具有占用存儲空間少,更新開銷小等特點,對IPv4和IPv6地址都可以適用。
關鍵詞:因特網(wǎng);路由查找;最長前綴匹配;trie樹
1引言
當前,因特網(wǎng)的規(guī)模、鏈路速度、帶寬、流量等都呈指數(shù)級增長,這對路由器中IP 路由查找算法對大容量路由表處理的適應性以及報文轉(zhuǎn)發(fā)查表的能力提出了更高要求。路由器是構(gòu)成因特網(wǎng)的中間結(jié)點,其轉(zhuǎn)發(fā)性能決定了因特網(wǎng)的整體性能。路由器的發(fā)展面臨三個難題:交換結(jié)構(gòu)、緩沖調(diào)度、報文處理。隨著半導體技術和光交換技術的發(fā)展,分組交換可以在很高的速率下得到實現(xiàn)。因此,IP路由查找是實現(xiàn)高速分組轉(zhuǎn)發(fā)的關鍵,其優(yōu)劣直接影響了當前和未來因特網(wǎng)網(wǎng)絡的整體性能[1]。本文首先對現(xiàn)有的典型IP 路由算法進行介紹,總結(jié)其優(yōu)缺點,并基于此提出一種基于多分枝 trie樹的路由查找算法。
2常用的路由查找算法分析
2.1 硬件算法
目前使用最多的硬件實現(xiàn)方法是使用CAM (Content AddressableMemory)內(nèi)容可尋址存儲器[2],它是一種特殊的存儲器件,用來實現(xiàn)路由表查找的一種硬件方法。CAM的最大特點是能夠在一個硬件時鐘周期內(nèi)完成關鍵字的精確匹配查找。為了能夠?qū)崿F(xiàn)最長前綴匹配,一個CAM表存放一類定長的前綴集。IPV4下需要32個CAM。這種方法有一個明顯的缺點,在對地址前綴長度具體分配沒有準確的了解之前,為了能夠保證存儲N個前綴表項目,每個CAM都要有N個表項的空間,因此,CAM存儲空間的利用率大大降低了。
另一種基于硬件的改進CAM算法是基于TCAM(三值CAM)的算法[3]。在進行搜索的時候,所有的TCAM 項都需要同時進行匹配,在有多個匹配項時,TCAM 規(guī)定在所有匹配的表項中選取地址最低的表項作為最后的結(jié)果。因此,為了能夠進行最長前綴路由的查找,就需要保證在TCAM的低地址區(qū)域存儲前綴路由項,而在高地址區(qū)域存儲短前綴路由項。TCAM 具有速度快、實現(xiàn)簡單的優(yōu)點,但它也具有幾個不足之處:(1)單位比特昂貴;(2)容量?。?3)并行匹配導致功耗很大;(4)更新復雜。
2.2 軟件算法
2.2.1二進制trie樹[4]
IP路由要求查找最長匹配的前綴地址,因此樹形結(jié)構(gòu)的路由查找算法將最長前綴匹配查找模型話為一棵二進制樹的過程。用Trie 表示前綴并不存儲在Trie 的結(jié)點中,而是用結(jié)點間的路徑表示前綴,一般規(guī)定一個結(jié)點到其左子結(jié)點的路徑表示前綴中的對應比特為0,結(jié)點到其右子結(jié)點的路徑代表前綴中的對應比特為1。如圖1所示就是二進制trie樹結(jié)構(gòu)來表示的地址前綴結(jié)構(gòu)。
IPv4中地址長度為32,所以二進制trie樹的深度為32層,前綴長度即子網(wǎng)掩碼長度為L的網(wǎng)絡路由會被存放在第L層的結(jié)點中。二進制trie樹算法一次更新操作只需要首先查詢定位并修改一個結(jié)點,開銷較小,它的最大不足在于查找過程中要進行大量的存儲訪問,對于IPv4地址查找最多需要32次,IPv6地址為128次。
2.2.2 多分支trie樹
直接用二進制trie樹的方式來實現(xiàn)路由查找,查找一個比特即對二叉樹向下遍歷一個深度,這樣會導致查找速度太慢。如果一次從目的IP中取出多個比特,就可以開有效的減少查找過程中的存儲訪問次數(shù)。多分支trie樹的查找過程與二進制trie樹的查找過程類似,在每次結(jié)點訪問過程時,記錄下到目前為止匹配上的最長地址前綴,直到到達葉子結(jié)點搜索過程結(jié)束。例如,如果每次檢查地址的4個比特,那么IPv4地址查找最多只需要8次存儲訪問就可以了。圖2是和前面圖1中采用同樣IP前綴表生成的多分支trie樹結(jié)構(gòu)圖。
每次從目的IP中取出的比特長度K稱為查找步長。由于存儲樹中的前綴長度各不相同,如果每次檢查步長為K的比特數(shù),則小于K或者不是K整數(shù)倍的前綴將無法與多分支trie樹的某個結(jié)點匹配。解決的方法是將無法匹配的前綴擴展為同K相同或者和K的整數(shù)倍。例如,K=3時,可以將1*擴展為100*、101*、110*、和111*。這種采用擴展前綴進行查找多分支trie樹的算法稱為可控前綴擴展算法。
當然,這種地址前綴擴展的多分支trie樹在減少訪存次數(shù)的同時也帶來了消耗存儲空間增大以及更新復雜的問題。假設步長K=5,那么就有4/5的IP前綴需要擴展(假設IP前綴長度均勻分布),最大的擴展長度前綴都要進行擴展到24個,這樣就消耗了大量的存儲空間。此時要更新某個IP前綴,最多需要更新24個結(jié)點。
文獻[5]中列舉了多分支trie樹算法取不同步長時的實際運行性能比較。當步長K較大時,多分支trie樹的深度相對較小,因此查找性能較好,但是需要耗費較多的存儲空間。當步長K較小時,多分支trie樹的深度相對較大,查找性能較差,但是存儲空間需求較小??梢?,對于多分支trie樹來說,查找速度和存儲容量是一對互相矛盾的性能指標。
3路由查找算法的衡量標準及性能提高方法
在評價一種地址查找算法的優(yōu)劣時,必須綜合考慮以下性能[6]:
3.1查找速度。一般所使用的指標是每秒查找分組數(shù)??紤]到各種方案在測試時所使用硬件不同、測試條件的不同會對測試結(jié)果產(chǎn)生很大影響,所以使用一次查找、特別是最差情況下一次查找需要進行的存儲器訪問次數(shù)作為衡量速度的標準更為合理。
3.2所需存儲器的大小。實施方案所需的存儲器應盡可能的小,在一定的空間中存儲盡可能多的路由前綴,以便于硬件實現(xiàn)和滿足不斷增長的前綴數(shù)目的需要。
3.3路由表更新的開銷。包括路由表周期更新開銷和表項插入、刪除操作開銷兩部分。路由信息的變化所引起的查找性能的下降應盡可能的小。
提高路由查找速度的主要途徑有3個[7]:(1)減少存儲器訪問次數(shù);(2)減小轉(zhuǎn)發(fā)表的存儲空間;(3)采用硬件流水并行處理。只采用一種方法或者算法所得到的查找性能受到一定的限制,既使能夠取得很快的查找速度,往往也存在轉(zhuǎn)發(fā)表更新困難或者擴展性差等問題。所以很多算法都是把這3個方向上的改進結(jié)合起來的結(jié)果。
4一種改進的多分支trie樹算法
我們提出一種多分支trie樹改進算法。在多分支trie樹結(jié)構(gòu)基礎上,不需要進行前綴擴展。假設檢查步長為K的比特數(shù),為解決小于K或者不是K整數(shù)倍的前綴將無法與多分支trie樹的某個結(jié)點匹配問題,把小于K或者不是K整數(shù)倍的前綴掛載到K的整數(shù)倍結(jié)點上,以整數(shù)倍結(jié)點為根結(jié)點,組成一個大的中間結(jié)點。即,中間結(jié)點之間采用多分支步長查詢,中間結(jié)點的內(nèi)部使用二進制trie樹來表示。
圖3列舉了步長K=3時,某個中間結(jié)點的表示方法。前綴100110是K的整數(shù)倍結(jié)點,即中間結(jié)點。1001100,1001101,
10011010都不是K的整數(shù)倍結(jié)點,把他們掛載在100110的中間結(jié)點上。圖4是使用前面的IP前綴表生成的結(jié)構(gòu)圖。
在路由查詢時,使用步長為K訪問中間結(jié)點,找到中間結(jié)點后,以步長為1訪問中間結(jié)點內(nèi)部。一個長度為N的前綴,所需要的訪存次數(shù)為N/K的結(jié)果加上N/K的余數(shù)。以步長K為3為例,假設前綴長度N為11,那么訪存次數(shù)為3+2=5次。最壞情況下,IPv4地址前綴最長為32,訪存次數(shù)為10+2=12次,僅比原來的多分支trie樹的10次訪存多2次,而又遠少于二進制trie樹的32次訪存,這就保留了原來多分支trie樹查詢速度快的優(yōu)點。
同時,普通的多分支trie樹,對于前綴長不是整數(shù)倍的結(jié)點,要進行前綴擴充,最多擴充為2K-1個,占用了大量的存儲空間,而本算法于沒有對前綴進行擴展,占用空間?。欢腋陆Y(jié)點不需要涉及到其他結(jié)點,和二進制trie樹路由表更新的開銷其實是一樣小的。
5結(jié)束語
本文在分析傳統(tǒng)路由算法的基礎上,提出了一種基于多分支trie樹的路由查找算法。該保留了多分支trie樹訪存次數(shù)少,查詢速度快的特性,并具有占用存儲空間不大,更新開銷小的特點,對IPv4和IPv6地址都可以使用。由于使用硬件實現(xiàn)往往能使得路由查找算法性能得到數(shù)量級的提升,接下來的工作可以在硬件實現(xiàn)技術上進行研究。
參考文獻:
[1]Marc Friedman,AlonLevy,Todd Millstein. NavigationalPlans for Data Integration[C].Proc of t he 16t h National Confon Artificial Intelligence (AAAI'99)[C].1999.6:72-73.
[2]A MCAULEY,P FRANCIS.Fast Routing Table Lookup using CAMs[J].Proc.IEEE INFOCOM 1993,Vol3,pp1382 - 1391,San Francisco,USA.
[3]吳彤,楊嗣超,諸鴻文.路由表快速查找算法[J],通信技術,No4,2000:52-59.
[4]劉永鋒,楊宗凱.高速路由器中基于樹型結(jié)構(gòu)路由查找算法的研究與實現(xiàn)[J].計算機工程與科學.vol.26,No1,2004:77-80.
[5]徐格,吳建平,徐明偉等.高等計算機網(wǎng)絡-體系結(jié)構(gòu)、協(xié)議機制、算法設計與路由器技術[M],機械工業(yè)出版社,北京,2006:522-544.
[6]譚明鋒,高蕾,龔正虎,IP路由查找算法研究概述[J].計算機工程與科學.vol,28,No6,2006:87-91.
[7]徐宇鋒,李樂民.快速路由查找算法及其實現(xiàn),通信技術[J],No7,2001:48-52.