路由查找算法研究與分析

郭潤偉

摘要：隨著互聯(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.