黃永錦，覃毅芳*，周旭，張心晴

基于平衡二叉樹和Bloom過濾器的可變長地址路由查找算法

黃永錦1，2，覃毅芳1*，周旭1，張心晴1，2

（1.中國科學院 計算機網(wǎng)絡信息中心，北京 100083； 2.中國科學院大學，北京 100049）（?通信作者電子郵箱qinyifang@cnic.cn）

可變長地址是未來網(wǎng)絡領域的重要研究內(nèi)容之一。針對傳統(tǒng)路由查找算法在面向可變長地址時查找效率低的問題，提出一種基于平衡二叉樹AVL（Adelson-Velskii and Landis）樹和Bloom過濾器的適用于可變長地址的高效路由查找算法，簡稱為AVL-Bloom算法。首先，針對可變長地址靈活可變且無界的特點，利用多個片外哈希表分別存儲前綴比特位數(shù)相同的路由條目及其下一跳信息，同時應用片上Bloom過濾器加速搜索可能匹配的路由前綴；其次，為了解決基于哈希技術的路由查找算法在查找最長前綴路由時需多次哈希對比的問題，引入AVL樹技術，即通過AVL樹組織每組路由前綴集合的Bloom過濾器及其哈希表，優(yōu)化路由前綴長度的查詢順序，并減少哈希計算次數(shù)進而降低查詢時間；最后，在3種不同的可變長地址數(shù)據(jù)集上將所提算法與METrie（Multi-Entrance-Trie）和COBF（Controlled prefix and One-hashing Bloom Filter）這兩種傳統(tǒng)路由查找算法進行對比實驗。實驗結(jié)果表明，AVL-Bloom算法的查詢時間明顯少于METrie和COBF算法，分別減少了將近83%和64%；同時，AVL-Bloom算法在路由表項數(shù)變化較大的情況下也能維持穩(wěn)定的查找性能，適用于可變長地址的路由查找轉(zhuǎn)發(fā)。

可變長地址；路由查找；AVL樹；Bloom過濾器；哈希算法

0 引言

隨著移動互聯(lián)網(wǎng)的廣泛普及，互聯(lián)網(wǎng)承載的業(yè)務種類不斷豐富，網(wǎng)絡新應用也層出不窮；然而，隨著互聯(lián)網(wǎng)與各行各業(yè)不斷深入融合，以及以增強現(xiàn)實（Augmented Reality， AR）、虛擬現(xiàn)實（Virtual Reality， VR）和全息通信等為代表的全新業(yè)務、全新場景的涌現(xiàn)，傳統(tǒng)互聯(lián)網(wǎng)基于固定有界的網(wǎng)際互聯(lián)協(xié)議（Internet Protocol， IP）地址實現(xiàn)互聯(lián)互通的缺陷逐漸暴露，且缺乏靈活、有效的擴展方式適應未來多樣化、專業(yè)化業(yè)務的發(fā)展需求。可變長地址技術是解決上述問題的一種有效方案，它能夠根據(jù)網(wǎng)絡規(guī)模和應用場景需求的不同提供適應長度的地址結(jié)構(gòu)。由于滿足各種異構(gòu)網(wǎng)絡、異構(gòu)終端實現(xiàn)萬物互聯(lián)的需求，支持可變長地址結(jié)構(gòu)的未來網(wǎng)絡體系也相繼被提出并成為研究的熱點，如泛在IP（Ubiquitous IP， UIP）協(xié)議體系［1］、FlexIP（Flexible IP）協(xié)議體系［2］、NewIP（Network 2030 and the future of IP）協(xié)議體系［3-4］等。

然而，雖然可變長地址具有靈活可變長的優(yōu)點，能夠依據(jù)實際需求定制地址長度，但是也給路由查找?guī)砹艘欢ǖ睦щy。如果仍然以最長前綴的地址長度統(tǒng)一存儲所有路由條目并基于此進行路由查找，將對路由查找算法的存儲空間和查找性能帶來巨大挑戰(zhàn)。

通常，傳統(tǒng)路由查找算法基于Trie［5-6］，或者基于硬件三態(tài)內(nèi)容尋址存儲器（Ternary Content Addressable Memory， TCAM）［7-9］實現(xiàn)路由查找?；赥rie的路由查找算法結(jié)構(gòu)簡單、易于實現(xiàn)，但是每次路由查詢時都需要大量的內(nèi)存訪問。由于可變長地址長度靈活，所以它的長度遠大于傳統(tǒng)IP的地址長度，若直接將基于Trie算法的路由查找技術應用于可變長地址路由查詢，它的查詢性能將受到極大的限制，因此基于Trie算法的路由查找技術不適合可變長地址的路由查找。基于硬件的路由查找算法由于受到高成本和高功耗的限制，而且難以靈活擴展，因此也不適用于面向靈活可變長地址的路由查找。可變長地址給路由查找及其數(shù)據(jù)結(jié)構(gòu)設計帶來了新的挑戰(zhàn)，傳統(tǒng)的路由查找算法難以直接應用，所以針對可變長地址的特點展開路由查找算法的研究成為當前的熱點。

鑒于此，本文基于平衡二叉樹AVL（Adelson-Velskii and Landis）樹和Bloom過濾器提出了一種適用于可變長地址的高效路由查找算法——AVL-Bloom算法。該算法對每一組長度相同的路由前綴都利用一個Bloom過濾器和相應的存儲哈希表構(gòu)建，哈希表存儲路由前綴及其下一跳信息；同時，該算法依據(jù)地址前綴長度構(gòu)建平衡二叉樹，每一個樹節(jié)點包含一組前綴長度相同的Bloom過濾器及其哈希表，用于檢驗任意可變長地址的路由前綴是否存在于該節(jié)點。AVL-Bloom算法不但解決了由于地址長度過長導致分支樹前綴擴展帶來的內(nèi)存資源浪費問題，而且可以有效地緩解基于哈希進行路由查找時需要從地址最大比特長度位數(shù)依次遞減進行多次哈希比較，直到獲得最長前綴的缺陷。

1 相關工作

路由查找是分組交換網(wǎng)絡中通過查詢路由前綴集合以獲取下一跳轉(zhuǎn)發(fā)信息的過程，它的結(jié)果用于指導路由器進行數(shù)據(jù)包的轉(zhuǎn)發(fā)。路由查找的效率很大程度上決定了路由器的性能，因此，各種基于軟硬件的路由查找算法也相繼被提出，如基于Trie樹和基于TCAM等一系列路由查找算法。

在未來網(wǎng)絡研究領域，可變長地址結(jié)構(gòu)的相關設計與研究也逐漸成為熱點，可變長地址背景下的路由查找相關解決方案也成為領域內(nèi)亟須解決的難題。

METrie（Multi-Entrance-Trie）［10］是首先被提出用于可變長地址的路由查找算法。METrie使用了多分類路由表的存儲方法，并通過地址長度擴展的方式將非對齊的可變長地址分類為固定長度的地址，使可變長地址能夠使用傳統(tǒng)的Trie樹算法查找；然而，METrie的結(jié)構(gòu)復雜，特別是動態(tài)更新操作時需要進行大量的修剪和擴展，導致了頻繁的內(nèi)存訪問，難以滿足海量數(shù)據(jù)通信下未來網(wǎng)絡業(yè)務的高效路由需求。

COBF（Controlled prefix and One-hashing Bloom Filter）［11-12］是一種基于Bloom過濾器的路由查找算法，該算法通過可控前綴擴展限制可變長地址的前綴長度，減少了所需Bloom過濾器數(shù)，并通過優(yōu)化Bloom過濾器的哈希函數(shù)，減小了誤報對算法的影響；然而，COBF算法由于哈希技術的局限性，查找最佳路由前綴時需要多次哈希運算操作，哈希運算次數(shù)的增加會顯著影響算法的查找效率，特別是在可變長地址的情況下，多次哈希運算導致的影響更加嚴重。

命名數(shù)據(jù)網(wǎng)絡采用可變長地址結(jié)構(gòu)的內(nèi)容名稱作為網(wǎng)絡標識符，并基于此提出了面向可變長內(nèi)容地址的路由查找算法。文獻［13］中針對命名數(shù)據(jù)網(wǎng)絡可變長字符標識符的特點，提出了一個基于哈希的命名數(shù)據(jù)網(wǎng)絡路由查找算法。該算法通過比較不同類型的函數(shù)選取最優(yōu)哈希函數(shù)，并結(jié)合Bloom過濾器預查詢?nèi)〉昧溯^好的路由查找性能；然而該算法并沒能降低查詢過程的哈希次數(shù)，不能從根本上解決基于哈希算法的弊端。

傳統(tǒng)基于哈希的路由查找算法中，各個路由條目數(shù)據(jù)沒有相關性，每個哈希表只能存儲同一長度的路由前綴，進行路由查詢時也只能對每個前綴進行哈希匹配實現(xiàn)精確查找。當查找最長路由前綴時，只能從地址的最大比特位長度開始依次遞減進行多次哈希，直到找到匹配的前綴為止，因此算法中的哈希次數(shù)成為影響路由查找算法查找效率的關鍵因素。針對此問題，文獻［14］中首先提出通過降低哈希次數(shù)提升路由查找效率的算法。該算法將路由條目存儲于哈希表，并使用平衡二叉樹二分查找所有的哈希表，提高了路由查找效率；然而該算法直接將路由條目存儲于哈希表，在每次路由比對時都需要進行內(nèi)存訪問，對路由查找效率造成了較大的影響。

綜上所述，現(xiàn)有的可變長地址路由查找算法尚存在以下幾點不足：1）由于可變長地址長度可變，路由條目基數(shù)較大，存儲開銷的問題亟須解決；2）由于可變長地址的長度較長，在查找最優(yōu)最長路由前綴時，需要頻繁地訪問內(nèi)存，極大影響算法的整體性能；3）基于哈希的算法雖然能夠在一定程度上緩解存儲空間占用的問題，但是在最長前綴的前提下進行查找需要多次哈希計算，加重了網(wǎng)元設備的處理負擔。

針對上述路由查找算法存在的缺點，本文結(jié)合可變長地址的特點，設計了一個基于平衡二叉樹和Bloom過濾器的可變長地址路由查找算法。該算法利用Bloom過濾器有效解決了可變長地址由于數(shù)量多所帶來的內(nèi)存開銷過大及訪存頻繁的問題，同時通過AVL樹推進最長前綴的查找順序，有效地解決了基于哈希進行路由查找時哈希次數(shù)過多的問題。

2 AVL?Bloom算法

針對可變長地址的特點，本文基于平衡二叉樹和Bloom過濾器提出了AVL-Bloom算法。該算法利用片外哈希表存儲長度相同的路由前綴及其下一跳信息，同時為了減少片外哈希表的訪存次數(shù)，對每個片外哈希表都建立一個Bloom過濾器進行預篩選。雖然Bloom過濾器引入的哈希計算開銷和天然存在的假陽性影響了查找性能，但是與訪存帶來的時間開銷相比，它的總體查找性能仍然可以獲得較大的提升，且內(nèi)存訪問次數(shù)更少。此外，針對查找時哈希次數(shù)過多的問題，AVL-Bloom算法使用一棵平衡二叉樹組織不同長度前綴的哈希表和它的Bloom過濾器。在路由查找時，可以利用平衡二叉樹快速查詢的特性，將哈希計算次數(shù)從地址長度的比特位數(shù)級別降低到二叉樹的高度級別，以大幅提升算法的查找性能。

2.1　AVL-Bloom算法的結(jié)構(gòu)

AVL-Bloom算法的結(jié)構(gòu)主要由AVL樹結(jié)構(gòu)、Bloom過濾器和存儲路由條目的哈希表組成，具體結(jié)構(gòu)如圖1所示。雖然哈希表與Bloom過濾器技術在路由查找領域應用較廣泛，然而基于樸素哈希表查找路由需要多次訪問內(nèi)存，傳統(tǒng)Bloom過濾器天然存在假陽性和需要額外哈希計算的特點，直接應用這些技術查找路由的算法在整體性能上并不理想，特別是可變長地址。一些路由查找算法［15-16］通過改進哈希函數(shù)、減少沖突次數(shù)達到提升查找性能的目的。然而優(yōu)化哈希函數(shù)并不能解決在最長前綴查找前提下需要多次哈希計算的問題，AVL-Bloom算法通過引入路由前綴控制技術和單哈希多次取余的方法優(yōu)化路由查找的性能，同時依據(jù)長度分類路由條目并構(gòu)建AVL樹結(jié)構(gòu)，使整個算法構(gòu)建的查找樹的高度維持在一個平衡狀態(tài)，有效地控制了算法在查找最長路由前綴時所需的哈希計算次數(shù)，最大限度地提升整個路由查找算法的查找效率。

圖1　AVL-Bloom算法的結(jié)構(gòu)

2.1.1AVL-Bloom的AVL樹結(jié)構(gòu)

AVL-Bloom 算法的整體結(jié)構(gòu)為一棵平衡二叉樹，每一個樹節(jié)點代表具有相同路由前綴長度的處理集合。以最大長度為7 b的可變長地址為例，根據(jù)AVL-Bloom算法構(gòu)建的AVL樹結(jié)構(gòu)如圖1左下部分所示。圖1中每個樹節(jié)點的數(shù)字代表當前樹節(jié)點所存儲路由前綴的比特位數(shù)，如根節(jié)點的值為4，即代表可變長地址所有路由前綴比特位數(shù)為4的路由條目都存儲于該節(jié)點的哈希表中。由于基于哈希的路由查找算法在查找最佳路由前綴時，只能從目標地址的最大比特位數(shù)依次減少哈希位數(shù)尋找最長路由前綴，而AVL-Bloom樹結(jié)構(gòu)則采用折半查找的方式，極大地減少了哈希計算次數(shù)；因此AVL-Bloom算法通過AVL樹優(yōu)化查找推進順序，有效提高路由查找效率。

2.1.2AVL-Bloom 樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)

AVL-Bloom的每個樹節(jié)點用于處理具有相同長度的路由前綴，由一個Bloom過濾器及其對應的哈希表組成?？勺冮L地址的路由前綴可通過哈希表將不規(guī)則的路由前綴存儲在有規(guī)律的哈希表中，并通過Bloom過濾器進行預篩選，可以有效地減少哈希表訪問次數(shù)，提高路由查找的效率。在進行路由查找時，首先將待查詢的地址輸入Bloom過濾器進行比較，由于Bloom過濾器存在一定的假陽性概率，為了驗證查找結(jié)果是否真實匹配，需再次檢查片外哈希表。如果片外哈希表中存在相應的路由信息，則結(jié)束當前路由查找并根據(jù)相應信息轉(zhuǎn)發(fā)；否則，繼續(xù)根據(jù)AVL樹的特點查詢下一樹節(jié)點，直至匹配成功或獲取默認轉(zhuǎn)發(fā)為止。

2.1.3AVL-Bloom 樹節(jié)點哈希表結(jié)構(gòu)

AVL-Bloom每個樹節(jié)點哈希表所存儲的路由條目由路由前綴Prefix、路由前綴計數(shù)器Count和下一跳信息Nexthop組成，Nexthop的最高位為最佳路由前綴標志位Mark。AVL-Bloom算法為了提高查詢速度，避免算法在樹的左右子樹之間振蕩，將路由前綴的子前綴插入遍歷路徑上的所有樹節(jié)點。前綴計數(shù)器Count統(tǒng)計當前路由前綴是否為其他更長路由前綴的子前綴，便于路由條目刪除時能夠正確刪除它相應的子前綴。Mark位標記當前路由條目是否為最佳路由前綴。當前綴計數(shù)器Count值為1時，說明該前綴只為一條路由的子前綴，它的結(jié)果和最長前綴一致，并將Mark位置為1標為最佳路由前綴。在進行路由查找時，當樹節(jié)點中的Bloom過濾器預判該前綴存在于此節(jié)點并在哈希表中找到相應的路由條目時，首先判斷該路由條目的Mark位是否為1，如果為1則結(jié)束查詢并返回該前綴的下一跳信息；否則，說明該前綴不是最優(yōu)前綴，繼續(xù)往AVL樹的右子樹方向進行查找，直到找到最佳路由前綴。

2.1.4AVL-Bloom 樹結(jié)構(gòu)的建立

AVL-Bloom算法的建立過程主要是對核心數(shù)據(jù)結(jié)構(gòu)進行實現(xiàn)并將路由前綴條目依次插入。具體描述如下所示：

步驟1 數(shù)據(jù)預處理。根據(jù)路由前綴集合的分布情況進行預處理，如果不同長度路由前綴的條目數(shù)差距較大，將導致樹節(jié)點存儲分布不均勻，查找遞進比特位數(shù)較少，進而影響算法的查找效率。為此，可通過控制路由前綴方法［17］，即采用“葉推法”將路由前綴長度的比特位數(shù)推到特定長度，從而減少樹節(jié)點的數(shù)量和控制樹的高度。

步驟2 建立AVL樹。根據(jù)路由前綴集合中路由條目不同長度類型的數(shù)量建立AVL樹，同時初始化各個樹節(jié)點的哈希表及其對應的Bloom過濾器。

步驟3 添加數(shù)據(jù)。將集合中的路由條目依次遍歷AVL樹，查找合適的樹節(jié)點并將該路由條目存儲在節(jié)點的哈希表中，同時更新Bloom過濾器。

至此完成了AVL-Bloom算法的樹結(jié)構(gòu)的建立。

2.2　AVL-Bloom查找

路由查找算法的核心是查找效率，AVL-Bloom 算法的路由查找本質(zhì)是一個二叉樹遍歷的過程，即通過依次比較樹節(jié)點是否存在相應的路由條目實現(xiàn)路由查找的過程。假設可變長地址存在一條路由前綴為F506112233440000/48，根據(jù)AVL-Bloom的添加規(guī)則，當該路由條目添加到AVL樹中時，將會在遍歷路徑上比它小的兩個樹節(jié)點（如圖2中44和36節(jié)點），也分別存儲該路由條目的子路由，并設置相應的Mark位。如圖2所示，44節(jié)點存儲了該路由條目的子路由，且沒有其他路由的子路由與它相同，此時將Mark位置為1，標記為最佳路由；同時，由于36節(jié)點也存儲了其他路由條目的子路由，則它的Mark位置為0。當進行路由查找時，可以根據(jù)Mark位標記當前路由是否為最佳路由，以便提前結(jié)束路由查詢，提升算法查詢效率。

圖2　AVL-Bloom 的查找過程

AVL-Bloom算法的路由查找流程如算法1所示，主要是在樹結(jié)構(gòu)中驗證是否存在待查找路由前綴并返回相應的下一跳信息。具體描述如下所示：

步驟1 初始化查詢棧。AVL-Bloom算法在AVL樹中找到第一個路由前綴長度不大于待查詢可變長地址長度的樹節(jié)點，并將它記錄（入棧）。

步驟2 遍歷查詢棧。當查詢棧不為空時，將棧中的樹節(jié)點依次出棧，并利用樹節(jié)點Bloom過濾器驗證待查詢的可變長地址，判斷是否存在相應的路由前綴。如果經(jīng)Bloom過濾器驗證存在相應的路由前綴，則訪問相應的片外哈希表，再次檢查前綴是否存在，避免由于過濾器的假陽性對查詢造成影響，如果片外哈希表存在相應路由條目，則獲取相應的下一跳信息；如果Bloom過濾器驗證不存在，則說明最佳前綴長度小于當前節(jié)點，將左子節(jié)點入棧，繼續(xù)查找。

步驟3 獲取最優(yōu)前綴。在獲取下一跳信息后對其中的Mark位進行驗證，查看該路由條目是否為最佳前綴，即路由前綴長度最長的條目。如果是，則返回該前綴值，結(jié)束查詢；如果否，則將當前節(jié)點的右子節(jié)點入棧（Mark=0，說明存在更長的最優(yōu)前綴），繼續(xù)遍歷查詢棧查找最優(yōu)路由前綴條目。

至此獲取最優(yōu)的下一跳轉(zhuǎn)發(fā)信息。

算法1 AVL-Bloom路由查詢。

輸入 目標地址， AVL樹的根節(jié)點；

輸出 目標地址的下一跳。

1） 初始化查詢棧，獲取的長度

2） while！= null do

3）←.pop（）

4） if.>then

5） while..>do

6）←.

7） end while

8） if.！= null then

9）←.push（.）

10） end if

11） continue

12） end if

13）← get.bits of

14）← Hash（）

15） if.BF（） and.HashFind（） then

16）←.HashGet（）

17）←.

18） if.== 1 then

19） return

20） else

21）←.push（.）

22） end if

23） else

24）←.push（.）

25） end if

26） end while

27） return

2.3　AVL-Bloom更新

AVL-Bloom算法的更新包含路由條目的添加和刪除，根據(jù)路由生成算法得到的結(jié)果或者用戶配置策略依次對AVL樹進行動態(tài)更新，使得路由能夠適應網(wǎng)絡的拓撲變化。

2.3.1添加

AVL-Bloom算法的添加過程是通過在平衡二叉樹上找到相應的樹節(jié)點，并將路由條目添加到哈希表中和更新Bloom過濾器，同時將路由條目的子路由添加到查詢路徑上存儲路由前綴長度小于該路由長度的所有樹節(jié)點上。以在AVL中添加一條F506112233445566/64的路由前綴為例，它的過程如圖3所示。

AVL-Bloom算法的路由添加流程如算法2所示，主要是根據(jù)待插入路由條目前綴長度在樹結(jié)構(gòu)中找到合適的樹節(jié)點并添加至相應數(shù)據(jù)結(jié)構(gòu)。具體描述如下所示：

步驟1 初始化修改棧。通過遍歷平衡二叉樹查詢當前查找樹節(jié)點前綴長度等于待插入路由前綴長度的節(jié)點，并將在遍歷過程中樹節(jié)點前綴長度小于待插入路由前綴長度的節(jié)點記錄（入棧）。

步驟2 遍歷修改棧。將修改棧中的樹節(jié)點依次出棧，并將待插入路由前綴條目修剪至與當前節(jié)點前綴長度相同，再添加到當前節(jié)點的哈希表中，同時更新Bloom過濾器。

步驟3 修改下一跳信息。當路由前綴添加至哈希表時，如果檢測到該路由前綴已經(jīng)存在于哈希表中，則將最優(yōu)前綴的Mark置為0，否則置為1，同時修改Count計數(shù)字段，以便在刪除時用于判斷是否需要刪除該路由前綴。

至此完成路由前綴條目的更新插入。

算法2 AVL-Bloom路由添加。

輸入 待插入路由條目， AVL樹的根節(jié)點；

輸出 None。

1） 初始化修改棧

2） while.！=.do

3） if.≤.then

4）←.push（）

5） end if

6） if.>.then

7）←.

8） else

9）←.

10） end if

11） end while

12） while！= null do

13）← get.bits of

14）← Hash（）

15）←.pop（）

16）←.HashGet（）

17） if！= null then

18）.← 0

19） else

20）.← 1

21）.BloomFilterAdd（）

22） end if

23）.←.+ 1

24）.HashAdd（，）

25） end while

2.3.2刪除

AVL-Bloom算法的刪除與添加基本相同，主要差異是找到相應樹節(jié)點后從中刪除目標路由前綴條目，并更新相應的數(shù)據(jù)結(jié)構(gòu)。由于AVL-Bloom算法存在一個子路由條目被多個共用的問題，為了避免刪除對其他路由條目造成影響，在插入子條目時通過引入計數(shù)器Count統(tǒng)計當前子路由條目被共用的情況。刪除時，只有當Count值為0時再刪除該路由條目。如圖4所示，以在AVL樹中刪除路由前綴為F506112233445566/48的路由條目為例。

圖3　AVL-Bloom 的添加過程

圖4　AVL-Bloom 的刪除過程

AVL-Bloom算法的路由刪除流程如算法3所示，主要是從樹結(jié)構(gòu)中找到目標樹節(jié)點并刪除相應的路由前綴條目。具體描述如下所示：

步驟1 初始化刪除棧。在AVL樹中查找樹節(jié)點前綴長度等于目標路由前綴長度的節(jié)點，并記錄遍歷過程中樹節(jié)點前綴長度小于待刪除路由前綴長度的節(jié)點記錄（入棧）。

步驟2 遍歷刪除棧。將刪除棧中的樹節(jié)點依次出棧，同時將該前綴修剪至與當前節(jié)點前綴長度相同，并通過該樹節(jié)點的Bloom過濾器驗證。如果存在，則尋找哈希表中相應的路由條目，將它的計數(shù)器Count減1。當Count變?yōu)?時，則刪除該子路由條目，并完成Bloom過濾器的更新。

至此完成目標路由前綴條目的刪除。

算法3 AVL-Bloom路由刪除。

輸入 待刪除路由條目， AVL樹的根節(jié)點；

輸出 None。

1） 初始化修改棧

2） while.！=.do

3） if.≤.then

4）←.push（）

5） end if

6） if.>.then

7）←.

8） else

9）←.

10） end if

11） end while

12） while！= null do

13）←.pop（）

14）← get.bits of

15）← Hash（）

16） if.BF（） and.HashFind（） then

17）←.HashGet（）

18）.←.- 1

19） if.≤ 0 then

20）.BloomFilterDel（）

21）.HashDel（）

22） end if

23） end if

24） end while

2.4　AVL-Bloom 性能分析

AVL-Bloom算法的本質(zhì)是基于哈希的路由查找算法，因此減少哈希計算次數(shù)和片外哈希表訪問次數(shù)是提高此類算法查找效率的關鍵。AVL-Bloom算法通過對片外哈希表存儲的路由條目建立Bloom過濾器進行預篩選，由于Bloom過濾器體量較小，可以加載在片內(nèi)存儲器，因而能夠有效地減少哈希表的訪問次數(shù)，提高查找效率（關于引入Bloom過濾器后路由查找的性能分析可參考文獻［11-12］）。同時，AVL-Bloom算法通過構(gòu)建平衡二叉樹組織不同長度前綴的哈希表和它的Bloom過濾器。路由查找時，可利用平衡二叉樹的快速查詢特性將哈希計算次數(shù)從地址的比特位數(shù)級別降低到二叉樹的高度級別，從而大幅提升算法的查找性能。

AVL-Bloom樹的高度決定了算法的查找效率，假設可變長的地址長度為，在進行路由查找時AVL-Bloom算法通過構(gòu)建的平衡二叉樹優(yōu)化最長前綴的查詢進程，使哈希計算次數(shù)由傳統(tǒng)樸素哈希查找的減少為log，大幅提高了算法的查找效率。特別是對于可變長地址，地址長度越長，普通的路由查找算法越難適用，而AVL-Bloom路由查找算法則可以有效應對。

同時通過Bloom過濾器進行預篩選，在片上存儲器提前判斷路由前綴是否存在，避免哈希表的無效訪問，減少存于片外存儲器中哈希表的訪問次數(shù)，有助于降低訪存開銷，進一步提升算法的查找性能。Bloom過濾器主要通過個哈希函數(shù)標記位數(shù)組中相應位置，然而Bloom過濾器存在假陽性，對于未標記在過濾器中的元素，它的哈希索引對應的位置上因其他元素的插入而被標記為存在時，就會發(fā)生假陽性的情況。假陽性發(fā)生的概率可近似認為：

在算法設計時，為了減少因Bloom過濾器誤報而造成的訪存開銷，需要盡可能地使假陽性發(fā)生的概率為極小值。一個bloom過濾器由一個長度為b的數(shù)組及個哈希函數(shù)組成，表示bloom過濾器存儲數(shù)組的比特位數(shù)（長度），為待存儲數(shù)據(jù)集的數(shù)據(jù)量（數(shù)據(jù)量的上限）。最優(yōu)值為：

從而取得了最小的假陽性率：

通過合理配置Bloom過濾器數(shù)組比特位數(shù)和哈希函數(shù)的數(shù)量，可降低訪存開銷，使整個查找算法獲得較高的查找效率。以一個長度為128 b的可變長地址在圖2所示的樹形結(jié)構(gòu)中查找路由為例，當前路由表中并不存在適合它的路由前綴。如果采用傳統(tǒng)的樸素哈希方法進行查找，則需要從最長的128 b依次遞減直到1 b，經(jīng)過128次哈希計算才能知道路由表中不存在適合該地址的路由前綴。如果采用AVL-Bloom算法，僅需5次哈希計算便可發(fā)現(xiàn)路由表中不存在合適的路由前綴。AVL-Bloom算法通過AVL樹及其相應的查詢標記，將查詢哈希計算次數(shù)從降至log，同時利用片上Bloom過濾器減少對片外存儲器上哈希表的訪問次數(shù)，大幅提高了路由算法的查找效率。

3 實驗與結(jié)果分析

為了驗證AVL-Bloom算法路由查找的有效性和正確性，在多組數(shù)據(jù)集下與METrie［10］和COBF［11-12］路由查找算法進行對比實驗。實驗在一臺配置Intel Core i7-11700 CPU@3.20 GHz、緩存為64 KB L1、256 KB L2、12 MB L3以及8 GB 運行內(nèi)存的計算機上開展，安裝的操作系統(tǒng)為Ubuntu 16.04 64 b。

本文實驗中，各種路由查找算法的性能對比通過比較平均查詢時間和內(nèi)存消耗情況展開。本文設置了3組不同的路由表作為仿真實驗的數(shù)據(jù)集，測試數(shù)據(jù)符合UIP協(xié)議［1］的可變長地址編碼規(guī)范。UIP協(xié)議的可變長地址主要分為四大類，地址長度由1 B跨越到255 B，且每類地址的長度都靈活可變，因此在進行路由查找性能測試時，數(shù)據(jù)集的路由條目分布情況需要考慮各類地址應用場景以及每類地址的數(shù)量比例。由于UIP協(xié)議仍然處于研究階段，目前還沒有真正的路由數(shù)據(jù)，因此每組數(shù)據(jù)分別符合UIP地址分布規(guī)律隨機生成，數(shù)據(jù)量從10 000到100 000條路由條目組成。為了進行比較分析，數(shù)據(jù)集1的路由條目在符合地址分布規(guī)律的基礎上主要偏向超長地址（最大長度為2 048 b）的路由條目；數(shù)據(jù)集2的路由條目主要側(cè)重于中長地址（最大長度為1 024 b）；同理，數(shù)據(jù)集3的路由條目主要集中于長地址（最大長度為512 b）。各個數(shù)據(jù)集路由前綴長度動態(tài)地變化更有利于檢驗算法是否適用于可變長地址的路由查找。

圖5顯示了METrie、COBF和AVL-Bloom這3種不同路由查找算法在3個不同數(shù)據(jù)集上路由查詢時間的變化情況。從圖5可見，AVL-Bloom算法具有較好的查詢效率，它的查詢時間顯著低于COBF和METrie。在綜合不同數(shù)據(jù)集的情況下，AVL-Bloom算法的路由查詢時間相較于METrie算法和COBF算法減少了近83%和64%。隨著每個數(shù)據(jù)集路由條目數(shù)的增加，3種路由查找算法的查詢時間也明顯增加。METrie和COBF的路由查詢時間幾乎呈線性增長趨勢，而AVL-Bloom算法的查詢時間受影響較小。這是由于AVL-Bloom算法采用了AVL樹推進路由查找時所需進行哈希計算地址位數(shù)，使得整個算法在進行路由查找時哈希計算次數(shù)穩(wěn)定在log級別。對比圖5（a）～（c）中每個算法的曲線變化情況可以發(fā)現(xiàn)，METrie在3個不同數(shù)據(jù)集上的曲線抖動較明顯，而COBF和AVL-Bloom算法的曲線則較平穩(wěn)。這是由于3種算法所采用核心數(shù)據(jù)結(jié)構(gòu)不同，METrie核心的Trie樹結(jié)構(gòu)不能很好地適應可變長地址靈活可變長、長短地址分布不均勻等特點；COBF和AVL-Bloom算法是基于哈希設計的路由查找算法，通過哈?？梢詫⒌刂烽L度分布不均勻、長度差距較大的地址分類存儲不同的哈希表中，極大縮短了路由查找所需的時間開銷，顯著提高了整個算法的查找效率。

更進一步，對比3個不同數(shù)據(jù)集下不同算法的內(nèi)存開銷情況，結(jié)果如圖6所示。從圖6可見，各種路由算法的內(nèi)存開銷情況隨著數(shù)據(jù)集路由條目數(shù)的增加而增加，且基于哈希技術實現(xiàn)的路由查找算法內(nèi)存開銷遠大于基于Trie樹的算法。由于METrie算法在實現(xiàn)時，每個子樹采用Radix Tree實現(xiàn)，通過壓縮路徑的方式節(jié)省了大量的節(jié)點開銷；但是，這也給路由查找效率帶來了一定的影響，需遍歷節(jié)點的所有元素，查詢效率不高。值得注意地，由于基于哈希的路由查找算法需要通過哈希表存儲每一條路由前綴，而基于Trie樹的算法則通過相同前綴合并路由條目，因此隨著數(shù)據(jù)集路由條目數(shù)的增加，基于哈希路由查找算法的內(nèi)存開銷幾乎是線性增長，而基于Trie的路由查找算法由于合并相同路由前綴，使得內(nèi)存開銷增長趨勢并不明顯。

圖5　不同算法的查詢時間比較

圖6　不同算法的內(nèi)存開銷比較

由于AVL-Bloom算法和COBF都基于哈希表技術實現(xiàn)，因此哈希計算次數(shù)成為了影響這兩個算法路由查找效率的關鍵因素。為了探究基于哈希路由查找性能差異產(chǎn)生的原因，本文繼續(xù)測試了COBF和AVL-Bloom算法在不同數(shù)據(jù)集下的哈希計算總次數(shù)。圖7顯示了這兩種算法的哈希計算總次數(shù)的實驗結(jié)果。從圖7可見，COBF在不同數(shù)據(jù)集下的哈希計算次數(shù)遠高于AVL-Bloom算法。由于AVL-Bloom算法引入了平衡二叉樹，使得它在進行最長路由前綴查找時不需要從地址最長前綴長度的比特位數(shù)依次減少進行哈希計算，從而減少了哈希計算次數(shù)，使算法總體查找效率提高較明顯。

圖7　COBF算法和AVL-Bloom算法的哈希計算次數(shù)比較

4 結(jié)語

可變長地址結(jié)構(gòu)是未來網(wǎng)絡發(fā)展的一種趨勢，是根據(jù)未來多態(tài)異構(gòu)網(wǎng)絡互聯(lián)場景需求而提出的新型網(wǎng)絡地址格式。本文針對這種可變長地址提出了一種路由查找算法AVL-Bloom算法，實現(xiàn)地址長度可變情況下的高效路由查找。實驗結(jié)果表明，相較于其他路由查找算法，AVL-Bloom算法可以實現(xiàn)更高的查詢效率，能夠滿足未來網(wǎng)絡海量數(shù)據(jù)通信下全新業(yè)務的高效路由需求。在接下來的工作中，將進一步研究未來網(wǎng)絡發(fā)展趨勢和需求，結(jié)合可變長地址結(jié)構(gòu)的特點，不斷地改進和創(chuàng)新AVL-Bloom路由查找算法，探索它在不同網(wǎng)絡環(huán)境下的適用性。

[1] 周旭，蔣勝，張杰，等. 泛在IP協(xié)議體系［J］. 電信科學， 2021， 37（10）：47-54.（ZHOU X， JIANG S， ZHANG J， et al. Ubiquitous IP protocol system［J］. Telecommunications Science，2021，37（10）：47-54.）

[2] TANG J， ZHANG W， GONG X， et al. A flexible hierarchical network architecture with variable-length IP address［C］// Proceedings of the IEEE INFOCOM 2020 — IEEE Conference on Computer Communications Workshops. Piscataway： IEEE， 2020：267-272.

[3] 鄭秀麗，蔣勝，王闖. NewIP：開拓未來數(shù)據(jù)網(wǎng)絡的新連接和新能力［J］.電信科學，2019，35（9）：2-11.（ZHENG X L， JIANG S， WANG C. NewIP： new connectivity and capabilities of upgrading future data network［J］. Telecommunications Science， 2019，35（9）： 2-11.）

[4] CHEN Z， WANG C， LI G， et al. New IP framework and protocol for future applications ［C］// Proceedings of the NOMS 2020-2020 IEEE/IFIP Network Operations and Management Symposium. Piscataway： IEEE， 2020： 1-5.

[5] ASAI H， OHARA Y. Poptrie： a compressed trie with population count for fast and scalable software IP routing table lookup ［C］// Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York： ACM， 2015：57-70.

[6] YANG T， XIE G， LI Y， et al. Guarantee IP lookup performance with FIB explosion ［C］// Proceedings of the 2014 ACM Conference on SIGCOMM. New York： ACM ， 2014：39-50.

[7] HUANG J-Y， WANG P-C. TCAM-based IP address lookup using longest suffix split［J］. IEEE/ACM Transactions on Networking， 2018， 26（2）： 976-989.

[8] SUN Y， LIU H， KIM M S. Using TCAM efficiently for IP route lookup［C］// Proceedings of the 2011 IEEE Consumer Communications and Networking Conference. Piscataway： IEEE， 2011： 816-817.

[9] LE H， PRASANNA V K. Scalable high throughput and power efficient IP lookup on FPGA［C］// Proceedings of the 2009 17th IEEE Symposium on Field Programmable Custom Computing Machines. Piscataway： IEEE， 2009：167-174.

[10] REN S， YU D， LI G， et al. Routing and addressing with length variable IP address ［C］// Proceedings of the ACM SIGCOMM 2019 Workshop on Networking for Emerging Applications and Technologies. New York： ACM， 2019：43-48.

[11] LIU S， LUO W， ZHOU X， et al. OBF： a guaranteed IP lookup performance scheme for flexible IP using one bloom filter ［C］// Proceedings of 2021 IEEE 29th International Conference on Network Protocols. Piscataway： IEEE， 2021：1-6.

[12] LIU S， LUO W， ZHOU X， et al. An efficient addressing scheme for flexible IP address［C］// Proceedings of the 2021 2nd International Conference on Control， Robotics and Intelligent System. New York： ACM， 2021：111-116.

[13] SO W， NARAYANAN A， ORAN D， et al. Toward fast NDN software forwarding lookup engine based on hash tables［C］// Proceedings of 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. New York： ACM， 2012：85-86.

[14] WALDVOGEL M， VARGHESE G， TURNER J， et al. Scalable high speed IP routing lookups［C］// Proceedings of the ACM SIGCOMM’97 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 1997：25-36.

[15] ZHANG C， XIE G. Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network［J］. Computer Communications， 2022， 181： 438-445.

[16] SHI S， QIAN C. Ludo hashing： compact， fast， and dynamic key-value lookups for practical network systems［J］. ACM SIGMETRICS Performance Evaluation Review， 2020， 48（1）：57-58.

[17] SRINIVASAN V， VARGHESE G. Faster IP lookups using controlled prefix expansion ［J］. ACM SIGMETRICS Performance Evaluation Review， 1998， 26（1）：1-10.

Routing lookup algorithm with variable-length address based on AVL tree and Bloom filter

HUANG Yongjin1，2， QIN Yifang1*， ZHOU Xu1， ZHANG Xinqing1，2

（1，，100083，；2，100049，）

The variable-length address is one of the important research content in the field of future network. Aiming at the low efficiency of traditional routing lookup algorithms for variable-length address， an efficient routing lookup algorithm suitable for variable-length addresses based on balanced binary tree — AVL （Adelson-Velskii and Landis） tree and Bloom filter， namely AVL-Bloom algorithm， was proposed. Firstly， multiple off-chip hash tables were used to separately store route entries with the same number of prefix bits and their next-hop information in view of the flexible and unbounded characteristics of the variable-length address. Meanwhile， the on-chip Bloom filter was utilized for speeding up the search for route prefixes that were likely to match. Secondly， in order to solve the problem that the routing lookup algorithms based on hash technology need multiple hash comparisons when searching for the route with the longest prefix， the AVL tree technology was introduced， that was， the Bloom filter and hash table of each group of route prefix set were organized through AVL tree， so as to optimize the query order of route prefix length and reduce the number of hash calculations and then decrease the search time. Finally， comparative experiments of the proposed algorithm with the traditional routing lookup algorithms such as METrie （Multi-Entrance-Trie） and COBF （Controlled prefix and One-hashing Bloom Filter） were conducted on three different variable-length address datasets. Experimental results show that the search speed of AVL-Bloom algorithm is significantly faster than those of METrie and COBF algorithms， and the query time is reduced by nearly 83% and 64% respectively. At the same time， AVL-Bloom algorithm can maintain stable search performance under the condition of large change in routing table entries， and is suitable for routing lookup and forwarding with variable-length addresses.

variable-length address; routing lookup; Adelson-Velskii and Landis (AVL) tree; Bloom filter; hash algorithm

This work is partially supported by Project of Beijing Municipal Science and Technology Plan （Z191100007519007）， Fund of Youth Innovation Promotion Association of Chinese Academy of Sciences （2020175）.

HUANG Yongjin， born in 1996， M. S. candidate. His research interests include future network system.

QIN Yifang， born in 1984， Ph. D.， senior engineer. His research interests include future network architecture， 5G mobile communication.

ZHOU Xu， born in 1976， Ph. D.， research fellow. His research interests include future network architecture， new generation wireless network.

ZHANG Xinqing， born in 1999， M. S. candidate. Her research interests include future network system.

TP393.05

A

1001-9081（2023）12-3882-08

10.11772/j.issn.1001-9081.2022121915

2023?01?04；

2023?03?08；

2023?03?09。

北京市科技計劃項目（Z191100007519007）；中國科學院青年創(chuàng)新促進會基金資助項目（2020175）。

黃永錦（1996—），男，廣西南寧人，碩士研究生，主要研究方向：未來網(wǎng)絡系統(tǒng)；覃毅芳（1984—），男，廣西河池人，高級工程師，博士，主要研究方向：未來網(wǎng)絡架構(gòu)、5G移動通信；周旭（1976—），男，四川成都人，研究員，博士生導師，博士，CCF會員，主要研究方向：未來網(wǎng)絡架構(gòu)、新一代無線網(wǎng)絡；張心晴（1999—），女，山西陽泉人，碩士研究生，主要研究方向：未來網(wǎng)絡系統(tǒng)。