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

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

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

1 概述

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

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

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

2 路由算法原理

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

2．1 路由查找機制

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

圖1 16-8-8查找機制

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

圖2 路由表項數(shù)據(jù)結(jié)構(gòu)

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

圖3 表項存儲實例

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

2．2 路由存儲機制

如圖2所示，當路由前綴長度小于16 bit時，將路由添加到路由表的第1級表Tbl_L1_Entry中。當路由前綴長度介于17 bit～24 bit之間時，將路由添加到路由表的第2級表Tbl_L2_Entry中。但需要根據(jù)路由前16位前綴在第一級表中找到對應(yīng)的表項位置，并將Valid和Cont位置為有效。當路由前綴長度介于25 bit～32 bit之間時，將路由添加到路由表的第3級表Tbl_L3_Entry中。但需要根據(jù)路由前16位前綴在第一級表中找到對應(yīng)的表項位置，并將Valid和Cont位置為有效;并且根據(jù)17 bit～24 bit為前綴在第2級表中找到對應(yīng)的表項位置，同樣將該表項的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部分，則根據(jù)表項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部分表項插入過程中，需要進行判別已經(jīng)存在表項的前綴長度Len是否小于當前需要插入的表項前綴18，如果小于，則需要對已存在表項進行替換。由于第2條表項插入的前綴Len為17，小于當前的前綴長度18，因此如圖3表項下一跳指向C的所示，其對原有的部分下一跳指向B的表項進行了替換。

3 算法優(yōu)化

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

3．1 內(nèi)存空間的優(yōu)化

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

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

3．2 哈希表的引入

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

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

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

4 算法實現(xiàn)

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

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

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

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

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

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

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

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

步驟8沒有匹配到路由，取默認路由或?qū)⒃摂?shù)據(jù)包丟棄，退出。

5 測試結(jié)果與分析

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

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

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

表1 平均查找次數(shù)

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

圖4 64 Byte數(shù)據(jù)不同路由條目下性能測試結(jié)果

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

圖5 5×106條路由條目下算法測試結(jié)果

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

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

圖6 內(nèi)存優(yōu)化前后數(shù)據(jù)對比

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

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

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

6 結(jié)束語

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

當前基于哈希表和多比特樹相結(jié)合的路由查找機制已經(jīng)在高端路由設(shè)備的IPv4路由轉(zhuǎn)發(fā)中得到實際應(yīng)用，后期將推廣到IPv6的路由查找中，但由于IPv6地址長度有128 bit，其路由前綴長度分布有別于IPv4的情況，因此需要根據(jù)實際情況對地址的分段情況做出調(diào)整，以獲得較高的查找效率和較優(yōu)的內(nèi)存消耗。

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

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

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

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

［5］ 杜 飛，董治國，苗 琳，等．基于無沖突哈希表和多比特樹的兩級IPv6路由查找算法［J］．計算機應(yīng)用，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］ 陸笑天，李 曦，周學海．基于前驅(qū)查找的快速IP路由查找和更新方案［J］．計算機工程，2007，33(13):127-129．

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

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

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