路由查找算法研究與分析

郭潤偉

摘要：隨著互聯網絡鏈路速率的不斷提高，路由查找已成為路由器報文轉發的瓶頸。本文首先介紹和分析了路由器中廣泛使用的各種典型IP 路由算法方法，并提出一種基于多分枝 trie樹的改進路由查找算法。該算法保留了多分支trie樹訪存次數少，查詢速度快的特點，并具有占用存儲空間少，更新開銷小等特點，對IPv4和IPv6地址都可以適用。

關鍵詞：因特網；路由查找；最長前綴匹配；trie樹

1引言

當前，因特網的規模、鏈路速度、帶寬、流量等都呈指數級增長，這對路由器中IP 路由查找算法對大容量路由表處理的適應性以及報文轉發查表的能力提出了更高要求。路由器是構成因特網的中間結點，其轉發性能決定了因特網的整體性能。路由器的發展面臨三個難題：交換結構、緩沖調度、報文處理。隨著半導體技術和光交換技術的發展，分組交換可以在很高的速率下得到實現。因此，IP路由查找是實現高速分組轉發的關鍵，其優劣直接影響了當前和未來因特網網絡的整體性能[1]。本文首先對現有的典型IP 路由算法進行介紹，總結其優缺點，并基于此提出一種基于多分枝 trie樹的路由查找算法。

2常用的路由查找算法分析

2.1 硬件算法

目前使用最多的硬件實現方法是使用CAM (Content AddressableMemory)內容可尋址存儲器[2]，它是一種特殊的存儲器件，用來實現路由表查找的一種硬件方法。CAM的最大特點是能夠在一個硬件時鐘周期內完成關鍵字的精確匹配查找。為了能夠實現最長前綴匹配，一個CAM表存放一類定長的前綴集。IPV4下需要32個CAM。這種方法有一個明顯的缺點，在對地址前綴長度具體分配沒有準確的了解之前，為了能夠保證存儲N個前綴表項目，每個CAM都要有N個表項的空間，因此，CAM存儲空間的利用率大大降低了。

另一種基于硬件的改進CAM算法是基于TCAM(三值CAM)的算法[3]。在進行搜索的時候，所有的TCAM 項都需要同時進行匹配，在有多個匹配項時，TCAM 規定在所有匹配的表項中選取地址最低的表項作為最后的結果。因此，為了能夠進行最長前綴路由的查找，就需要保證在TCAM的低地址區域存儲前綴路由項，而在高地址區域存儲短前綴路由項。TCAM 具有速度快、實現簡單的優點，但它也具有幾個不足之處：(1)單位比特昂貴；(2)容量小；(3)并行匹配導致功耗很大；(4)更新復雜。

2.2 軟件算法

2.2.1二進制trie樹[4]

IP路由要求查找最長匹配的前綴地址，因此樹形結構的路由查找算法將最長前綴匹配查找模型話為一棵二進制樹的過程。用Trie 表示前綴并不存儲在Trie 的結點中，而是用結點間的路徑表示前綴，一般規定一個結點到其左子結點的路徑表示前綴中的對應比特為0，結點到其右子結點的路徑代表前綴中的對應比特為1。如圖1所示就是二進制trie樹結構來表示的地址前綴結構。

IPv4中地址長度為32，所以二進制trie樹的深度為32層，前綴長度即子網掩碼長度為L的網絡路由會被存放在第L層的結點中。二進制trie樹算法一次更新操作只需要首先查詢定位并修改一個結點，開銷較小，它的最大不足在于查找過程中要進行大量的存儲訪問，對于IPv4地址查找最多需要32次，IPv6地址為128次。

2.2.2 多分支trie樹

直接用二進制trie樹的方式來實現路由查找，查找一個比特即對二叉樹向下遍歷一個深度，這樣會導致查找速度太慢。如果一次從目的IP中取出多個比特，就可以開有效的減少查找過程中的存儲訪問次數。多分支trie樹的查找過程與二進制trie樹的查找過程類似，在每次結點訪問過程時，記錄下到目前為止匹配上的最長地址前綴，直到到達葉子結點搜索過程結束。例如，如果每次檢查地址的4個比特，那么IPv4地址查找最多只需要8次存儲訪問就可以了。圖2是和前面圖1中采用同樣IP前綴表生成的多分支trie樹結構圖。

每次從目的IP中取出的比特長度K稱為查找步長。由于存儲樹中的前綴長度各不相同，如果每次檢查步長為K的比特數，則小于K或者不是K整數倍的前綴將無法與多分支trie樹的某個結點匹配。解決的方法是將無法匹配的前綴擴展為同K相同或者和K的整數倍。例如，K=3時，可以將1*擴展為100*、101*、110*、和111*。這種采用擴展前綴進行查找多分支trie樹的算法稱為可控前綴擴展算法。

當然，這種地址前綴擴展的多分支trie樹在減少訪存次數的同時也帶來了消耗存儲空間增大以及更新復雜的問題。假設步長K=5，那么就有4/5的IP前綴需要擴展（假設IP前綴長度均勻分布），最大的擴展長度前綴都要進行擴展到24個，這樣就消耗了大量的存儲空間。此時要更新某個IP前綴，最多需要更新24個結點。

文獻[5]中列舉了多分支trie樹算法取不同步長時的實際運行性能比較。當步長K較大時，多分支trie樹的深度相對較小，因此查找性能較好，但是需要耗費較多的存儲空間。當步長K較小時，多分支trie樹的深度相對較大，查找性能較差，但是存儲空間需求較小。可見，對于多分支trie樹來說，查找速度和存儲容量是一對互相矛盾的性能指標。

3路由查找算法的衡量標準及性能提高方法

在評價一種地址查找算法的優劣時，必須綜合考慮以下性能[6]：

3.1查找速度。一般所使用的指標是每秒查找分組數。考慮到各種方案在測試時所使用硬件不同、測試條件的不同會對測試結果產生很大影響，所以使用一次查找、特別是最差情況下一次查找需要進行的存儲器訪問次數作為衡量速度的標準更為合理。

3.2所需存儲器的大小。實施方案所需的存儲器應盡可能的小，在一定的空間中存儲盡可能多的路由前綴，以便于硬件實現和滿足不斷增長的前綴數目的需要。

3.3路由表更新的開銷。包括路由表周期更新開銷和表項插入、刪除操作開銷兩部分。路由信息的變化所引起的查找性能的下降應盡可能的小。

提高路由查找速度的主要途徑有3個[7]：（1）減少存儲器訪問次數；（2）減小轉發表的存儲空間；（3）采用硬件流水并行處理。只采用一種方法或者算法所得到的查找性能受到一定的限制，既使能夠取得很快的查找速度，往往也存在轉發表更新困難或者擴展性差等問題。所以很多算法都是把這3個方向上的改進結合起來的結果。

4一種改進的多分支trie樹算法

我們提出一種多分支trie樹改進算法。在多分支trie樹結構基礎上，不需要進行前綴擴展。假設檢查步長為K的比特數，為解決小于K或者不是K整數倍的前綴將無法與多分支trie樹的某個結點匹配問題，把小于K或者不是K整數倍的前綴掛載到K的整數倍結點上，以整數倍結點為根結點，組成一個大的中間結點。即，中間結點之間采用多分支步長查詢，中間結點的內部使用二進制trie樹來表示。

圖3列舉了步長K=3時，某個中間結點的表示方法。前綴100110是K的整數倍結點，即中間結點。1001100，1001101，

10011010都不是K的整數倍結點，把他們掛載在100110的中間結點上。圖4是使用前面的IP前綴表生成的結構圖。

在路由查詢時，使用步長為K訪問中間結點，找到中間結點后，以步長為1訪問中間結點內部。一個長度為N的前綴，所需要的訪存次數為N/K的結果加上N/K的余數。以步長K為3為例，假設前綴長度N為11，那么訪存次數為3+2=5次。最壞情況下，IPv4地址前綴最長為32，訪存次數為10+2=12次，僅比原來的多分支trie樹的10次訪存多2次，而又遠少于二進制trie樹的32次訪存，這就保留了原來多分支trie樹查詢速度快的優點。

同時，普通的多分支trie樹，對于前綴長不是整數倍的結點，要進行前綴擴充，最多擴充為2K-1個，占用了大量的存儲空間，而本算法于沒有對前綴進行擴展，占用空間小；而且更新結點不需要涉及到其他結點，和二進制trie樹路由表更新的開銷其實是一樣小的。

5結束語

本文在分析傳統路由算法的基礎上，提出了一種基于多分支trie樹的路由查找算法。該保留了多分支trie樹訪存次數少，查詢速度快的特性，并具有占用存儲空間不大，更新開銷小的特點，對IPv4和IPv6地址都可以使用。由于使用硬件實現往往能使得路由查找算法性能得到數量級的提升，接下來的工作可以在硬件實現技術上進行研究。

參考文獻:

[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]劉永鋒,楊宗凱.高速路由器中基于樹型結構路由查找算法的研究與實現[J].計算機工程與科學.vol.26,No1,2004:77-80.

[5]徐格,吳建平,徐明偉等.高等計算機網絡-體系結構、協議機制、算法設計與路由器技術[M],機械工業出版社,北京,2006:522-544.

[6]譚明鋒,高蕾,龔正虎,IP路由查找算法研究概述[J].計算機工程與科學.vol,28,No6,2006:87-91.

[7]徐宇鋒,李樂民.快速路由查找算法及其實現,通信技術[J],No7,2001:48-52.