基于哈希表與多比特樹的路由查找算法

范富明，李念軍，雷升平，吉 萌

(1．光纖通信技術和網絡國家重點實驗室，武漢430074;2．武漢烽火網絡有限責任公司，武漢430074)

1 概述

當前路由查找主要有Trie樹和哈希表等方法［1-3］。基于Trie樹路由算法在路由表項增多情況下，樹的深度變大，路由查找過程中平均匹配次數變多，算法效率較低。為了提高算法的查找效率，路由查找過程中采用步長為8的查找方式，在一定程度上提高了查找的效率。基于哈希表的路由算法，依據前綴長度路由表劃分為多張路由子表，在路由條目較少的情況下，取得了較好的性能，但在路由條目較多的情況下，哈希沖突迅速上升，查找效率下降明顯［4-5］。當前高端路由設備中大多采用基于Trie樹的方式存儲路由表項，路由查找過程依據表項的數目采用變步長的查找方式。在算法實際設計的過程中，為了權衡查找速率與消耗存儲空間之間的矛盾，對插入的表項要進行再平衡，使得樹的高度不至于太高和太低。

傳統基于哈希表或Trie樹的算法在表項較少的情況下能夠取得滿意的查找效率，但是在表項達到百萬以上時，查找效率迅速下降，難以滿足高端路由設備的需求［6-9］。TCAM(Ternary Content Addressable Memory)專用芯片憑借其出色的硬件查找性能，能顯著提高路由查找性能，可應用與高端路由設備，但是TCAM價格昂貴，在一定程度上限制了其應用的廣泛性［10］。當前隨著存儲設備容量的快速翻倍，內存價格進一步下降，高端路由設備迫于對性能的強烈要求，在算法中適當地采用內存空間置換時間也是可行的。

本文借鑒上述路由查找算法的特點，綜合考慮內存消耗和查找效率的因素，提出一種基于哈希表和多比特樹的路由最長前綴匹配查找算法。路由表項根據前綴長度采用分段儲的方式，表項查找和放置過程均從頂層開始。從數據結構上來看，每一級都是相當一個完全多比特樹。本文根據表項結構的存儲特點，在算法的內存消耗方面采取了進一步優化，同時為解決因表項重復而導致的遍歷困難問題，引入哈希表用于優化。

2 路由算法原理

當前處理芯片大多具有用于動態隨機存取存儲器(Dynamic Random Access Memory，DRAM)管理的專用接口，為數據在內存中的讀寫效率提供了較好的硬件條件，也為基于DRAM的大表項路由查找算法的設計與實現提供了可能性。高效的路由查找方法的設計在依賴硬件基礎的同時，良好的算法數據結構的設計顯得更加關鍵。

2．1 路由查找機制

16-8-8路由查找機制如圖1所示。在路由條目存儲是根據前綴長度分為第1部分1 bit～16 bit，第2部分17 bit～24 bit，第3 部分 25 bit～32 bit。

圖1 16-8-8查找機制

查找是采用最長前綴匹配(LPM)查找機制，首先取地址前16 bit的數值，在第1部分數組定位表項位置，并對表項的有效性進行測試。Valib為表項有效性的標志位，如果Valib=1，表明當前表項是有效的，如果Valib=0，則表明表項為空;Cont表示是否有更長路由可供查找的標志位，表明可以進行下一部分的查找，如果Valib=1，Cont=0，表明當前找的路由是唯一最長的匹配的路由，則可以在表項結構Info指針的地址中直接獲取下一跳的輸出信息，表項數據結構如圖2所示。

圖2 路由表項數據結構

如果Valib=1，Cont=1，表明有比當前長度為16 bit的表項更長的路由表項存在下一部分中，并需要抽取目的IP地址的17 bit～24 bit的數值作為偏移量，在第2級的對應數組中查詢表項。在第2級的表項判別過程同上一部分完全相同，主要對2個標志位進行判別。區分是查找成功、失敗或還是需要進入下一步中繼續查找，如圖3所示。

圖3 表項存儲實例

第2級表的起始位置Min和結束位置Max，Max－Min+1表示第2級表中可供查找的表項數，Max和Min的取值都不超過第2級表的最大有效表項數。Info路由信息指針，指向路由的下一跳信息。L1_Entry指向第2級表中相應表項的起始位置。

2．2 路由存儲機制

如圖2所示，當路由前綴長度小于16 bit時，將路由添加到路由表的第1級表Tbl_L1_Entry中。當路由前綴長度介于17 bit～24 bit之間時，將路由添加到路由表的第2級表Tbl_L2_Entry中。但需要根據路由前16位前綴在第一級表中找到對應的表項位置，并將Valid和Cont位置為有效。當路由前綴長度介于25 bit～32 bit之間時，將路由添加到路由表的第3級表Tbl_L3_Entry中。但需要根據路由前16位前綴在第一級表中找到對應的表項位置，并將Valid和Cont位置為有效;并且根據17 bit～24 bit為前綴在第2級表中找到對應的表項位置，同樣將該表項的Valid和Cont位置為有效。

例如有3個路由表項先后需要插入到路由表中:

A=10．0．0．0/8，B=10．34．128．0/17

C=10．34．192．0/18

首先 A=10．0．0．0/8，前綴長度小于 16 故而直接存儲到表的第1部分，則根據表項IP的前16位，找到table1［2560］的表項作為地址，前綴長度為8的表項 A=10．0．0．0/8，在第一級表項中作用域10．0．X．X ～10．255．X．X，第一級的下一跳指向 A 的表項都是其作用域。

第2 條表項 B=10．34．128．0/17，其前綴長度大于16，因此需要動用第1級和第2級進行表項的存儲，首先在第一部分的Tbl_L1_Entry［2594］的表項中將Cont標志位置為1，表明有比10．34給長的表項供匹配。在第2部分中的Tbl_L2_Entry［128］個表項起始，開始插入表項，其作用域是從10．34．128．X到10．34．255．X，第2級的下一跳指向B的表項都是其作用域。

第3 條表項 C=10．34．192．0/18，同樣長度大于16，并且同樣在第1部分的 Tbl_L1_Entry［2594］表項中，指向第二部分的列表，由于其前綴長度為18，故而其作用域為 10．34．192．X ～ 10．34．255．X，在第2部分表項插入過程中，需要進行判別已經存在表項的前綴長度Len是否小于當前需要插入的表項前綴18，如果小于，則需要對已存在表項進行替換。由于第2條表項插入的前綴Len為17，小于當前的前綴長度18，因此如圖3表項下一跳指向C的所示，其對原有的部分下一跳指向B的表項進行了替換。

3 算法優化

由上述算法的原理可知，在設計上采用三級的表項設計，前綴1到16的第一級完全采用連續的內存空間存儲表項，二三級以近似256個表項為單位的連續內存存儲方式。這些連續的內存存儲組織方式，使得路由在查找或存儲的過程中，根據目的IP或路由可以很簡便的計算出地址偏移量，從而快速定位到表項的位置，相對于傳統的動態樹形結構的路由組織方式在路由查找和路由添加效率上確實高很多。但算法是這種設計方式耗用了大量內存，并且有相當一部分的路由表項是空的，同時由于作用域的存在造成很多表項的鍵值是重復的，這些重復鍵值的存在導致路由遍歷操作的困難，難以完成用戶的Show或Dump路由條目的操作，因此需要對算法進行進一步的優化。

3．1 內存空間的優化

根據網絡研究機構的有效數據統計IPV4的路由前綴99．93%是小于等于24的［3］，也就是說大部分表項在樹形結構中分布于第一級和第二級中。第一層的長度16的前綴路由表項的存儲空間是在初始化的時候一次分配完成，大約為Tbl_L1_Entry［52000］(除去多播地址區間)，但是對于第2級和第3級的空間是根據添加路由的前綴長度動態分配。

二三級前綴范圍分別從17～24和25～32，前綴跨度為8，一般二三級存儲的時標號是0～255，需要的存儲塊大小統一都是256個表項空間，這中內存分配方式在一定程度上造成空間的浪費。算法在設計的過程中，在第一級和第二級的表項中設置了2個參數:Min和Max域，其分別用來標示下一級中表項的起始和結束段地址，其值是0～255范圍內的一個子區間，這個區間的大小取決與路由前綴的長度，該區間總是0～255范圍的一個子區間，消耗的內存空間塊大小總是不超過256個表項空間。

3．2 哈希表的引入

為了解決表項遍歷的問題，算法在設計上增加了一張用于存儲下一跳的信息的Hash表。Hash表根據前綴的長度建立32張子表，相同前綴的路由表項下一跳信息存儲在同一張子表中。每次在樹形結構中添加表項的時候，先把下一跳的信息結構Info添加到Hash表中，并把該地址指針傳給樹形表項的Info指針。

雖然樹形結構中有多個重復的表項，但是每個重復的表項的Info域指向哈希表中的地址是相同的Htbl_Entry，如圖3所示。添加的路由表項根據前綴長度在Hash表中的信息是唯一的，因此，在進路由Dump或Show進行路由遍歷的時候，從在Hash表中32張子表中依次遍歷出路由信息。

哈希表在沖突域中采用單鏈表的組織方式，雖然由于表項條目巨大，路由信息的添加和刪除的過程中，碰撞比較多。但是哈希表管理與維護是由控制平面來完成的，不會給數據平面的轉發效率帶來影響。

4 算法實現

為了實現最長匹配，依次從頂層開始向下查找。如果在第一層沒有匹配到路由前綴項，則表明路由不存在，則對數據包進行丟棄或送默認路由。如果在盡可能深的層次中匹配到表項，表明是最長的路由匹配，并通過表項中Info指針在哈希表中獲取下一跳的信息，并找到相應的出接口。

步驟1根據目的IP地址計算出高16位數值L1_Base_Idx，在第一級路由表結構中找到對于的表項Tbl_L1_Entry［L1_Base_Idx］。判別表項中的Valid標志位，如果 Valid=0進入步驟 8;如果Valid=1，進一步判別Cont標志位，如果Cont=1，進入步驟3，否則進入步驟2。

步驟2根據Tbl_L1_Entry［L1_Base_Idx］表項中的Info指針，找到路由信息Htbl_Entry，即可獲得出接口Index和下一跳網關等信息，進入步驟7。

步驟3表明第二級中可能存在更長的路由表項，其中L2_Entry指向下一級結構內存的起始地址Table2［0］，根據目的IP地址的17～24位獲得數值L2_Base_Idx，將L2_Base_Idx值與上級Tbl_L1_Entry［L1_Base_Idx］中的Min和Max值進行比較，如果L2_Base_Idx不在Min和Max組成的閉區間內，返回步驟2;如果L2_Base_Idx在Min和Max組成的閉區間中，表明第二級空間中存在該路由。進一步檢查Tbl_L2_Entry［L2_Base_Idx］表項中 Valid的有效性，如果Valid=0，表明該表項無效，返回步驟2;如果Valid=1，進一步判別Cont標志位，如果Cont=1，進入步驟5，否則進入步驟4。

步驟4根據Tbl_L2_Entry［L2_Base_Idx］表項的Info指針，找到路由信息Htbl_Entry，即可獲得出接口Index和下一跳網關等信息，進入步驟7。

步驟5表明第3級中可能存在更長的路由表項，其中表項中L2_Entry域指向下一級結構內存的起始地址Tbl_L3_Entry［0］，根據目的IP地址的25～32為獲得數值L3_Base_Idx，將L3_Base_Idx值與上一級Tbl_L2_Entry［L2_Base_Idx］中的Min和Max值進行比較，如果L3_Base_Idx不在Min和Max組成的閉區間內，返回步驟4;如L3_Base_Idx在Min和Max組成的閉區間內，進一步檢查Tbl_L3_Entry［L3_Base_Idx］表項中 Valid的有效性，如果Valid=0，表明該表項無效，返回步驟4;如果Valid=1，進入步驟6。

步驟6根據Tbl_L2_Entry［L2_Base_Idx］表項的Info指針，找到路由信息Htbl_Entry，即可獲得出接口Index和下一跳網關等信息，進入步驟7。

步驟7匹配到路由，退出。

步驟8沒有匹配到路由，取默認路由或將該數據包丟棄，退出。

5 測試結果與分析

在多核平臺中對該算法進行了測試。該CPU擁有10個核，核0運行Linux系統作為控制平面;其他9個核運行在數據平面，實現算法環境下數據實際轉發功能的實現。平臺外部配備2條8 GB的DDR3的內存，端口上外接2個萬兆口(XG)。

實驗中采用的路由表信息來自網絡Protocol上的統計信息，其中長度為1 bit～16 bit，17 bit～24 bit，25 bit～32 bit，各占一定比例的實際前綴總數為1 ×103，1 ×104，1 ×105，1 ×106，5 ×106不同數量的路由，并從轉發的數據的吞吐量、數據包平均延時、丟包率3個方面對算法進行測試。

為了評估本文IP地址查找算法的效率，本文使用隨機和非隨機兩種策略產生IPv4測試地址。表1中列出了采用4種IP測試數據所得到的地址在5×106條路由條目下查找次數和平均查找次數。從測試結果可以看出，算法的平均查找次數介于1～2次之間。

表1 平均查找次數

在1 ×103，1 ×104，1 ×105，1 ×106，5 ×106條路由測試，在64 Btye長度 IP數據包下達到了雙向10 GB/s的吞吐量，其測試特性如圖4所示，儀表記錄了數據包進入被測試設備最大、最小和平均延時時間，從圖中的數據變化來看，路由條目雖然成級數增加，但是數據轉發延時則變化并不明顯，這是因為算法在路由查找的過程中平均查找次數控制在1～2次之間，克服了傳統算法隨著路由條目數增加，平均查找的次數隨之增加而導致算法性能降低的問題。

圖4 64 Byte數據不同路由條目下性能測試結果

在5×106條路由的情況下，進行了64 Btye，128 Btye，256 Btye，512 Btye，1 024 Btye 不同數據包長度的性能測試，測試結果如圖5所示。latancy記錄測試進端口到出端口的延時。

圖5 5×106條路由條目下算法測試結果

在64 Btye長度的數據包測試中，在路由表中裝載不同條目的路由表項，其測試結果顯示算法在表項數目達到5×106條的情況下，達到雙向10 GB/s的線速，并且維持較低的丟包率，包延時相對于其他情況下有所增加，但變化比較平穩，在容忍的范圍內。同時5×106條路線下，算法在64 Btye長度的短包下達到線速。

測試分別對 1 ×103，1 ×104，1 ×105，1 ×106，5×106路由條目情況下內存使用情況進行統計，如圖6所示。算法內存空間的優化前后的數據進行對比，優化后的算法在內存的消耗量上明顯比沒有進行優化時要少很多，相對于普通的分段路由查找機制，算法一定程度上節約了內存的開銷。優化后的算法，在5×106大表項的情況下算法占用8．9 GB的內存空間，這是一般高端路由設備的硬件能夠承受的。

圖6 內存優化前后數據對比

為了測試算法與其他算法查找速度的對比，本文選擇了常用的二進制Trie樹、多比特Trie樹［11］和二分哈希法［12］路由查找算法，64 Btye長度IP數據包在多核平臺上進行 1 ×103，1×104，1×105，1×106，5×106條路由查找平均延時時間測試，測試結果如表2所示。

表2 不同算法的延時比較 μs

在表項較小的情況下4種算法查找平均延時相差不大，但是隨著表項的增加二進制Trie樹和多比特Trie樹高度增加，以及二分哈希查找算法哈希沖突增加，算法平均匹配查找次數增加，延時也隨之增加，本算法則隨表項的增加查找延時變化不大，維持在 22 μs左右。

6 結束語

本文提出一種基于哈希表和多比特樹相結合的路由查找機制，充分考慮到網絡實際應用中路由前綴長度的分布情況、存儲空間和每次路由查找平均匹配次數等綜合因素，將IPv4地址分成3段:1 bit～16 bit，17 bit～24 bit，25 bit～32 bit，對于網絡中前綴長度大多數分布在24 bit的路由表來說擁有非常高的查找效率，平均查找次數介于1～2次就可以查找最長匹配的路由表項，從而取得較快的轉發速度。同時算法引入了哈希表用于解決算法在路由表項輸出表項詳細信息方面的不足，算法在內存空間上也進行了一定程度的優化，進一步壓縮了算法在內存空間消耗量。算法通過多核平臺進行驗證，取得百萬條路由環境下雙向10 GB/s的速度，平均延時小于30 μs的測試性能，平均查找次數1～2次。

當前基于哈希表和多比特樹相結合的路由查找機制已經在高端路由設備的IPv4路由轉發中得到實際應用，后期將推廣到IPv6的路由查找中，但由于IPv6地址長度有128 bit，其路由前綴長度分布有別于IPv4的情況，因此需要根據實際情況對地址的分段情況做出調整，以獲得較高的查找效率和較優的內存消耗。

［1］ 王亞剛，杜慧敏，楊康平．使用Hash表和樹位圖的兩級IPv6地址查找算法［J］．計算機科學，2010，39(9):36-39．

［2］ 汪志莉，沈富可．一種基于哈希表和Trie樹的快速內容路由查找算法［J］．計算機應用與軟件，2009，26(10):121-125．

［3］ 張 琦，金胤丞，李 苗，等．Trie樹路由查找算法在網絡處理器中的實現［J］．計算機工程，2014，40(1):98-102．

［4］ 華 澤，班建民，陸 悠．基于分段地址結構的快速路由查找算法［J］．計算機與數字工程，2007，37(10):8-11．

［5］ 杜 飛，董治國，苗 琳，等．基于無沖突哈希表和多比特樹的兩級IPv6路由查找算法［J］．計算機應用，2013，33(5):1194-1196．

［6］ Grama A，Atallah M J．Adaptive Data Structures for IP Lookups［J］．AIM Journal of Experimental Algorithms，2005，33(5):1194-1196．

［7］ Zheng K，Liu B．V6Gene:A ScalableIPv6 Prefix Generator for Route Look up Algorithm Benchmark［C］//Proceedings of AINA’06．Washington D．C．，USA:IEEE Press，2006:1254-1260．

［8］ Swartzlandere L Y．Priority Tries for IP Address Lookup［J］．IEEE Transactions on Computers，2010，59(6):784-794．

［9］ 陸笑天，李 曦，周學海．基于前驅查找的快速IP路由查找和更新方案［J］．計算機工程，2007，33(13):127-129．

［10］ 殷 科，鄧亞平．基于RAM和TCAM存儲結構的高速路由查找算法［J］．計算機工程與應用，2005，41(20):159-161．

［11］ 崔 宇，田志宏，張宏莉，等．基于前綴區間集合的IPv6路由查找算法［J］．通信學報，2013，34(6):29-37．

［12］ 楊玉梅，黎仁國．基于二分查找和Trie的IPv6路由查找算法［J］．蘭州理工大學學報，2012，38(4):98-102．