基于前綴區間集合的IPv6路由查找算法

崔宇，田志宏，張宏莉，方濱興

(哈爾濱工業大學 網絡與信息安全技術研究中心，黑龍江 哈爾濱 150001)

1 引言

近年來，IPv4地址日漸枯竭，IPv6普及過程逐步加快，IPv6相關技術和服務支持得到了快速的發展，導致 IPv6分配的地址范圍和網絡流量迅猛增加，因此需要更加高效的IPv6路由算法為數據分組的快速轉發提供支撐。

與IPv4相同，IPv6路由方式也為最長前綴匹配，因此可繼承IPv4的部分路由算法，但在算法性能方面，兩者有以下區別：1) IPv6地址長度128 bit，IPv4為32 bit，使得按位比較的相關算法（如Binary Trie、Multi-bit）的查找樹深度增大，造成最壞時間、空間復雜度大量增加；2) IPv4路由規模基本穩定而IPv6處于發展階段，路由條數始終保持增長趨勢，根據文獻[1]對BGP路由表的統計，路由條數從2004年的500條增加到當前約8 000條，規模和分布存在較大不確定性，這對以前綴分布特點為基礎的相關算法影響較大，同時，由于更新相對頻繁，以前綴值為基礎的相關算法形成的查找樹中不平衡現象會加強，影響查找和更新效率；3) IPv4和 IPv6前綴長度體現了一定的集中性，目前，IPv6前綴絕大部分為32和48，而文獻[2]也預測未來前綴長度集中在32、47、48和64，這與IPv4分布相異，導致長度分布敏感的算法性能下降；4) IPv6前綴分布較為集中，從文獻[1]的數據可知，高16 bit為0x2001的前綴占30.5%，分布極大不平衡，這對前綴位敏感的算法不利，比如若干集中分布的前綴會出現在Patricia[3]樹的同一子樹下，增加局部查找深度，這主要是前期地址分配不平衡和地域發展不均勻所致，而隨著IPv6的普及，不平衡現象將會減少。

上述分析表明，目前，IPv6前綴存在分布集中和更新頻繁2個主要特點，因此良好的IPv6路由算法不僅在理論上應具有較好的平均時間和空間復雜度，還應在集中或稀疏區域具有較好的局部性能，同時也適應路由前綴更新頻繁的特點。目前，IPv6使用的軟路由算法可分為2類：其一是以IPv4為基礎的通用型算法；其二是針對IPv6特點實現的特定型路由算法。

以 IPv4為基礎的通用型算法主要分為基于前綴位、前綴長度和前綴值3種。

基于前綴位的路由查找算法主要以二進制樹（binary trie）為基礎，具有O(W)相關的查找與更新復雜度（W為地址長度）。該方法存在3個問題，其一是樹中存在大量不包含前綴的空節點，浪費大量內存；其二是空節點的存在增加了大量無用的比較次數；其三是可能導致已經找到最長匹配前綴卻繼續向葉子節點查找的情況，增加無效比較的次數。為了去除樹中空節點，Patricia方法對二進制樹中的連續空節點進行了壓縮，解決了前2個問題。文獻[4]中的多分枝Trie樹(multibits trie)通過將kbit整合到一個節點中，實現了O(W/k)的查找復雜度，降低了查找樹的深度。文獻[5]提出的優先樹(priority trie)對二進制樹結構進行了翻轉，可優先處理長度較長的前綴，同時去掉了樹中的空節點，部分解決了二進制樹的 3個問題，查找和更新時間復雜度介于[O(logN),O(W)]之間（N為路由數目），是近些年出現的較新穎的算法。

Waldvogel在文獻[6]中提出了基于前綴長度的二分查找方法。該方法具有O(logW)的查找復雜度，但需要大量的初始化計算和復雜的更新過程，同時也會產生大量的Marker，增加計算復雜度和內存空間。文獻[7]通過復雜算法降低了Marker數量，進而降低整個算法的內存占用。該類方法以散列為基礎，必然會產生散列沖突，影響算法效率和實際效果。

基于值的路由策略主要有二分查找樹(BST)和按前綴范圍進行二分查找(BSR)2種。在BST中，前綴按值順序排列，遞歸選取子序列的中間位置進行比較，直到子序列前綴數為1停止，查找的時間復雜度為O(logN)。BST方法不存在空節點，因此最大程度地節省了空間，具有O(N)的空間復雜度。但BST方法因前綴層次問題，在構建時會出現不平衡現象，增加了查找深度。文獻[8]提出的 DPT算法通過對前綴進行 leaf-pushing擴展形成了平衡二叉樹，從而避免不平衡現象。文獻[9]以最內層節點為樹節點，同時用數組維護前綴的包含關系，提出了只使用不相交前綴進行二分查找的方法，避免初始條件下不平衡的發生。

BSR[10]方式用[s,f]表示一個前綴，其中，s表示前綴起始值，補0擴展，f表示結束值，補1擴展，兩者差值表示前綴的范圍。BSR將點集進行排序，形成有序點集{s1,f1,s2,s3,f3,f2,…}并對其進行初始化計算以存儲每個節點對應的最優前綴(BMP,best match prefix)，對其進行二分查找，時間復雜度為O(log2N)。BSR算法由于用2個點表示前綴，因此最多需要前綴數量二倍的節點。同時，由于需要序列進行重新計算，因此更新的時間復雜度最壞為O(2N)。為了提高該方法的更新復雜度，文獻[11]提出了Multi-Range-Tree方法將查找和更新的時間復雜度提高到O(logk2N)，但存在頻繁更新導致不平衡的可能，同時空間復雜度增加到了O(kNlogk2N)。文獻[12]也提出了查找和更新復雜度為O(logN)的算法，通過維護N+1棵樹來維護前綴間、前綴與前綴間隔的包含關系，實現快速地更新，但實現難度較大。與文獻[11]類似，兩者的核心均是保存前綴的包含關系。文獻[13]提出的RBMRTs方法將前綴進行分層，不被其他前綴包含的前綴是第一層前綴，只包含于某個第一層前綴A的前綴形成A的第二層前綴，以此類推。同層前綴之間不存在包含關系，因此可以減少更新時的計算量，實現了約為O(log2N)的查找和更新復雜度。

針對 IPv6特點實現的特定路由算法通過對路由表分布特性的分析，利用各種通用算法的特點，將多種通用算法組合成新算法。如文獻[14]提出的TSB方法就是將二叉樹、段表和路由桶技術結合的IPv6路由算法。其利用IPv6前綴分布特點形成的第一層二叉樹結構，只需要較少節點，同時結合段表和桶路由技術，可較好地提高算法性能并降低內存占用。該算法第二層路由桶和段表結構切換時需要進行數據結構的整體切換，會產生一定延時。TSB是多種算法組合，會在特定局部含有某算法的缺陷，但整體上，TSB組合各算法的優點降低單一算法在特定條件下的缺點。隨著 IPv6發展，TSB第一層二叉樹節點數目會不斷增加，降低查找性能，但這種增加不會在短時間內頻繁進行。

由于IPv6地址長度較大，且分布集中，因此理論上基于前綴值的具有O(logN)時間復雜度的相關路由算法比O(W)相關的前綴位算法有更好的性能。所以，本文對BSR相關路由算法進行了研究，分析其查找和更新過程中存在的問題，結合IPv6前綴特點，提出了結合段表和 BSR 2種通用算法并以RBMRTs為基礎的基于前綴區間集合的IPv6路由算法BSRPS (binary search on range of prefix set)。

2 前綴值相關算法中查詢與更新的不平衡性

BSR相關路由算法在IPv4中具有較好的性能，但在IPv6環境中存在的前綴分布與更新不平衡性會嚴重影響該類方法的性能。本節對該類算法存在的2種不平衡性進行舉例和理論分析，指出其在IPv6環境中存在的嚴重問題，提出了解決該問題的基本思路。

2.1 查詢不平衡性

BSR中，前綴按值排序形成{s1,f1,s2,f2,…,sm,fm}前綴值序列（假設不存在包含關系），查找時通過二分查找確定位置，進而與某一路由條目進行對應。表1為一前綴實例，地址長度為5(W=5)，前綴P1～P7集中分布于地址空間[2, 15]上，P8相對孤立。以這種前綴集合形成的BSR和Patricia的基本形式如圖1和圖2所示。

表1 前綴實例

可以看到，BSR方法中，集中區域的前綴具有較淺的深度，而 Patricia相反，集中區域的前綴深度較大。如前綴P5，在前者中深度為3，后者為5。反之，對于處于稀疏區域的前綴，如P8，BSR中深度為4，而Patricia中為2，差別較大。

圖1 BSR查找樹

圖2 Patricia查找樹

理論上，考慮一種極限情況，假設在某一集中區域中存在擁有共同前綴a的2m-1個連續等長前綴，其范圍為{[a×2m +0,a×2m +1], [a×2m +2,a×2m +3],…, [a×2m+2m-2,a×2m +2m-1]}，以及1個前綴為b(b!=a且與a等長)的前綴Px。則在 BSR中，Px必然處于查找樹的最左端或最右端，因此其查找深度為log(1+2m-1)，約為m-1；而在Patricia中由于b!=a，Px的查找深度為2。對于連續的2m-1個前綴，查找深度分別為m-1和1+m，差別較小。可見，基于前綴區間的相關查找算法對集中區域的前綴有較好的查找性能，而基于前綴位的相關算法(如 Patricia、Multi-bit)對稀疏區域前綴的查找性能較好。

不同于IPv4，IPv6前綴分布的不均勻會嚴重增加 BSR算法的不平衡性。首先，目前的 IPv6中含有大量0x2001起始的前綴，分布集中，這對稀疏區域前綴的查找影響較大；其次，稀疏區域中存在的一些特殊前綴，如2002：：/16（6to4隧道）約占整體流量40%，會嚴重影響路由的整體性能。因此，為了避免這種情況，本文通過結合前綴位路由算法的思想，對前綴進行一次范圍劃分以減輕稀疏區域前綴查詢的不平衡性，將在第3節中詳細介紹。

2.2 更新不平衡性

BSR相關路由算法在不斷更新后可能會產生極端不平衡情況，比如圖1中刪除前綴P8[24, 31]并逐次插入P8[16, 17]、P9[18, 19]、…、P15[30, 31]后形成的查找樹如圖3所示。

圖3 更新不平衡性舉例

從圖3可見，按照BSR基本更新方法插入前綴P8～P15會產生眾多單分支節點。若不進行平衡旋轉，則必然會增加查找深度。在最壞情況下，整個查找樹會出現每個節點均為單分支的情況，查詢時間復雜度降為O(N)。

由于IPv6前綴更新較為頻繁，因此查找樹的形態會對BSR的查詢效率產生極大影響，必須有效控制最壞情況的出現，降低其對查詢效率產生的影響。為此，本文借鑒了Muliti-bit方法中對若干前綴位進行合并的思想，將前綴區間進行第二次劃分，形成前綴區間集合，達到有效地降低查找樹深度的目的。并且，在更新后配合節點自修復算法以避免大量空置集合的出現，降低內存占用量。

3 基于前綴區間集合的IPv6路由查找算法

BSRPS算法以RBMRTs為基礎，針對IPv6前綴長度、分布范圍等特點，通過地址范圍劃分和前綴集合劃分對 RBMRTs基礎結構進行改造，構造BSRPS樹，進行查找與更新。更新時，對更新過程中涉及到的節點使用自修復算法以避免前綴集合劃分引入的空位，降低不斷更新對查找樹平衡性的影響。本節首先介紹 BSRPS算法經二次劃分后形成的多棵多層查找樹的結構，其次分別介紹查找和更新算法。

3.1 BSRPS算法劃分方法與框架

BSRPS以RBMRTs為基礎，后者將前綴進行分層，形成單棵、多層二分查找樹。圖4顯示了表1和表2所示前綴形成的查找樹。

表2 前綴補充實例

圖4 RBMRTs算法框架

圖4中，RBMRTs將前綴集合分成若干層，同層前綴不存在包含關系，層間前綴為包含關系，稱包含于某一前綴的若干前綴形成的樹為該前綴的包含子樹，如P10、P11形成了P1的包含子樹。該結構有以下2點優勢：1) 同層無包含關系可省去BSR中一部分預計算和更新時間；2) 查詢和更新算法也相對簡單。查詢時，首先在Level1中進行查詢，如果不存在則返回空，若前綴節點存在包含子樹則進入下一層查詢，否則返回該前綴。更新過程與查詢類似，但增加了層間移動、替換等操作。

BSRPS設計中，首先用地址范圍劃分將Level1進行分割，形成多棵第一層樹，如圖4中若按地址范圍四等分可形成{P9,P1,P2,P3}、{P4,P5,P6,P7}和{P8} 3棵第一層查找樹。之后將每棵查找樹的若干節點組合為一個眾節點，形成BSRPS查找樹。

3.1.1 地址范圍劃分

RBMRTs算法基于BSR，因此對集中區域前綴的查詢能力較好。為了提高稀疏區域前綴性能，需通過地址范圍劃分分離稀疏區的IPv6前綴，避免其查詢時間被平均化，提高對稀疏區前綴的查詢效率。為此，本文采用對地址空間進行分段的方法，將地址空間分成K段，占用地址的高logKbit，形成多棵第一層樹。

對于K的選擇有以下考慮：1) 空置率，在前綴覆蓋范圍一定的情況下，K增大，每段范圍縮小，空置率可能會增加，內存浪費增大；2) 分散率，K越大，第一層樹越多，分散越廣，查找性能越高；3) 被覆蓋率，若K很大，logK也會增大，假設存在某個前綴Px，其長度Lx小于LogK，那么則要進行位擴展到logKbit，從而增加2Lx-logK個前綴，內存占用增加，也增加了更新的復雜度。良好的路由算法應具有低空置率、高分散率和零被覆蓋率。對于 IPv6，目前最短前綴長度為 16，除去最高 3 bit的全局地址標識，可以用高13位分段，K=213，既可以避免被覆蓋現象，又可以最大程度上劃分子樹，分散率最高。

根據這種劃分，Potaroo路由表最終形成了如表3所示的前綴分布情況。其中，Num表示經劃分后，查找樹中節點數目為[1, 10]、[11,100]、[101, 1 000]或[1 001, ∞]的查找樹類型；Count.表示該類型查找樹的數目，比如節點個數在[101, 1 000]范圍內的查找樹有17棵；Percent表示該類查找樹包含的前綴占前綴總數的百分比，可以看出100+類型包含了最多的前綴；Acc-Rate表示極限情況下各個段中查找深度在劃分前后的理論比值，體現了極限情況下查找的加速情況。

表3 前綴分布關系

可以看到，100+類型的前綴占整體數目的63.02%，且理論上可加速到 1.48倍，因此這種分段方法可有效提升整體的性能。同時，根據筆者對IPv6網絡中骨干路由器統計，稀疏區域 1+類型包含的以“2002：：”開頭的前綴(6to4隧道)占有了約 40%的流量，經過地址范圍劃分，該類流量理論上可提升到9.87倍，提升效果明顯。可見，對地址范圍的有效分段可以較大提高 IPv6路由轉發的性能，是十分必要和有效的。

3.1.2 前綴集合劃分

前綴集合劃分借鑒了 Multi-bits前綴位集合方法，在前綴按值升序排序基礎上，將M個連續前綴劃分為一個前綴集合，稱為眾節點，并用[Ss,Se]表示該眾節點的范圍。假設圖4所示前綴經地址劃分后屬于同一查找樹，圖5則表示經過集合劃分（假設M=3）后的情況。

圖5 集合劃分框架

前綴集合劃分直觀上反映出3個特點：1) 每個眾節點含有多個前綴；2) 查找樹深度降低；3) 眾節點存在空閑位置。查找樹深度降低是前綴合并的必然結果。原始情況下查找樹深度為logN，集合劃分后，查找樹深度變為 log(N/M)，總層數減少了logM。這對于查找失敗選擇默認路由的情況是有利的，可減少logM次比較。

眾節點會存在空閑位置，如Level3中P15所在眾節點，其根本原因是原始情況下查找樹包含的前綴數不能被M整除，因此必然在查找樹最右眾節點出現空閑現象。由于空閑情況只在最右出現，且目前路由表不會形成大量的包含子樹，因此不會產生浪費大量內存的情況。而在更新過程中，插入和刪除可能會形成空閑位置，需要對更新節點進行自修復以避免不斷更新產生大量的空閑眾節點，將在3.3節詳細說明。

3.2 BSRPS查找

從圖5可知，BSRPS雖然形成了眾節點，但查找樹基本框架未變，因此可根據每個眾節點的范圍進行二分查找。算法首先需要定位到某一眾節點，假設Ni表示某棵查找樹，則定位某一眾節點的時間復雜度為 log(2Ni/M)。之后仍用二分查找定位該眾節點中的前綴，時間復雜度為logM。單棵查找樹總時間復雜度為log(2Ni/M)+ logM=log2Ni，與原始算法一致。因此，對于單棵查找樹，BSRPS并沒有提升理論上的查詢復雜度，主要是降低更新不平衡對查找性能的影響，但對于查找失敗進行默認路由的情況，查詢復雜度降為 log(2Ni/M)，性能有一定提升。在加入地址范圍劃分后，平均時間復雜度有所降低，為 log(2Ni/K)。下面給出查找算法，其中，bs-set(pt,address)對一個眾節點中的M個前綴進行二分查找，Prefix-set表示第一層查找樹。

算法1BSRPS主查找算法

算法2子樹內遞歸查找算法

3.3 更新與自修復

BSRPS的更新過程與RBMRTs類似，包括同層內添加刪除前綴和層間前綴子樹的替換與擴展。但是，由于 BSRPS采用了眾節點模式，在比較和移動時略有不同，如圖6顯示了添加前綴Pnew時的3類情況（刪除過程類似）：1) 添加的前綴只與一個眾節點相關，如圖 6(a)～圖 6(d)所示；2) 與任何眾節點均無關，如圖6(e)所示；3) 與多個眾節點相關，如圖6(f)所示。

圖 6(a)中，Pnew覆蓋了整個眾節點，用只包含Pnew的新眾節點進行替換，同時將包含P1～Pm的原始眾節點擴展為Pnew包含子樹；圖6(b)表示Pnew包含了原始眾節點的部分前綴，此時將P2、P3形成新的眾節點并擴展為Pnew的包含子樹，并用Pnew替換兩者原始位置；圖6(c)中，Pnew屬于P3的子前綴，進入P3的包含子樹更新；圖6(d)表示Pnew位于該眾節點中兩個連續前綴中間，此時需要挪動眾節點中的其他前綴以重新形成有序數列。若該眾節點是滿節點，則在插入Pnew時必須要移出P1或Pm，此時P1或Pm需以該眾節為根節點進行如圖6(e)的插入過程，否則挪動單側前綴即可形成新有序數列；圖6(e)表示Pnew不包含于任何眾節點，若PresetB未滿，則填入PresetB末尾，否則新建一眾節點并鏈到PresetB的右孩子處。反之亦然。

圖6 BSRPS更新情況（Preset表示眾節點）

當Pnew涉及多個眾節點時，更新操作相對復雜，如圖6(f)顯示了向左子樹擴展多個眾節點的情況。可以看到Pnew覆蓋了PresetA的前面部分、PresetB的后面部分，且對于所有大于PresetB.P1小于PresetA.P3的前綴（斜杠條紋顯示），這些需要被替換的眾節點組成Pnew的包含子樹（與RBMRTs相同，需要對包含子樹進行平衡旋轉，防止出現大量單分支眾節點）。而Pnew則被加入PresetA或PresetB，更新原有眾節點。

上述方法可正確更新，但存在以下2個問題：1) 缺少機制保證被更新的眾節點是滿的，這會導致該眾節點可能只剩下極少的有效前綴，如圖6(a)、圖6(f)分別會使一個和2個眾節點包含的前綴數目大量減少，眾節點的空置率偏高，浪費大量內存；2) 當出現大量不滿眾節點時，必然會增加查找樹的深度，影響查詢和更新效率。為此，本文提出了更新節點的自修復算法以避免出現上述情況，保證最壞的查詢復雜度為log(2N/KM)。

節點自修復算法的核心思想是當眾節點自身在更新后不滿時，不斷從小于或大于該眾節點的區域中取最接近前綴以填補該眾節點的空白，直到該眾節點滿。該算法主要包括4個操作：重排序、定位、移動和旋轉。下面以圖7為例說明這一過程。

圖7 自修復算法舉例

圖7(a)中假設PresetA中前綴P2被替代或被刪除后，PresetA進入自修復過程（更新過程涉及的所有眾節點均需進行自修復，以保證除葉子節點外的所有眾節點均為滿眾節點）。首先假設PresetA優先選擇從左子樹取最接近的前綴，則PresetA需要對自身進行重排序留前部的空位，如圖7(a)所示；之后查找左孩子的最右子樹以定位小于該眾節點的最近前綴，如圖7(b)所示，將P12挪動到PresetA的空閑處。此時，PresetD雖被更新但由于其為葉子節點因此不需要進行自修復。圖6(c)假設PresetB的右子樹PresetD中的前綴已經全被修復到PresetA的第一個位置上，因而必須從PresetB的末尾選擇前綴移動到PresetA的前部。由于PresetB不是葉子節點（含有左子樹），因此也要執行自修復。此時，PresetB有2個可用策略：1) 從其左子樹里不斷移動最接近的前綴補位；2) 若其左孩子非葉子節點，則可首先進行旋轉，再移動P6到PresetA中，如圖7(c)的右側部分，既可以降低更新的時間復雜度，還可平衡查找樹，降低查找深度。

前綴集合劃分和更新節點的自修復并不能避免不平衡性的出現，但可以減少最壞情況下查找和更新的復雜度。同時，在配合使用AVL算法時，查找樹節點總數從N降為N/M，可節省大量平衡開銷。

4 性能分析與實驗

本節通過理論分析和實際測試對 BSRPS算法的性能進行了評估。首先在內存使用上，該算法首先進行了區域劃分，將 Level1層查找樹分成了K份，因此需要O(K)的空間存儲樹根指針；同時，由于一般情況下只有最右眾節點可能存在不滿情況，因此空間復雜度為O(K+2N)。但在經過不斷更新后，由于葉子節點無法進行自我修復，會出現葉子眾節點中只含有極少前綴的情況，浪費存儲空間。在這種情況下，對于二叉樹而言，假設其含有的非葉子眾節點個數為x，那么葉子眾節點數目至多x+1，由于Mx+1×(x+1)=2N，可推導出x=(2N-1)/(M+1)，由此查找樹占用的內存為M×(2x+1)≈2M(2N-1)/(M+1)，因此算法最壞空間復雜度為O(K+4N)。

在時間復雜度上，對于每一層查找樹而言，該算法擁有log2Ni的查詢速度。但是，前綴中存在若干包含子樹，實際查詢效率必然會低于該值，且查詢效率隨層數增多而下降。目前前綴最多包含5層，且每層的個數不定，不利于理論分析，因此通過實驗進一步分析其對查找性能的影響。在更新方面，與查詢過程相同，首先定位新前綴位置，進而向下替換或者更新，其最多需要對2個眾節點進行自修復（如圖 6(f)所示情況），因此更新復雜度為O(log2Ni+2M)。

為了測試算法實際性能，筆者在一臺2.6 GHz主頻、16 GB內存的服務器上對該算法進行了對比測試。對比算法采用 Patricia、BSR和 RBMRTs 3種，實驗數據采用了文獻[1,15]提供的 Potaroo、Tokyo和Atlanta路由表。表4列出了3個BGP路由表的相關參數。

表4 3種路由表及內存占用

表4第2列顯示了Potaroo、Tokyo和Atlanta 3個路由表中路由條數，均在8 000左右。第3～6列顯示了4種路由算法在不同路由表下的內存占用量，其中，BSR在理論上不存在內存的浪費因此在實際中的占用量也最少，而BSRPS方法理論上的空間復雜度大于 RBMRTs，但實際中卻相反，這主要是由于BSRPS方法中，眾節點對若干前綴進行了集合，因此對于一個M個前綴的眾節點只需2個指針指向左右子樹，而RBMRTs方法則需要2M個指針，增加了大量的內存。表4還顯示了各個路由表中最深層均為5層、且大部分前綴處于Level1層，因此不會對算法總體性能產生巨大影響。最后一列SEG表示（按照K=8 192計算）地址劃分將路由表分成了約28個段（即分成28棵第一層樹），分配較不平均，有效分段只占3.4%。隨著IPv6的發展，當高16 bit地址使用明顯增加時，有效分段比例也會有明顯提高。

為了測試算法的查詢和更新速度，本文選擇M=5，K=8 192。理論上，M大小不影響查找速度，但M較大時會影響算法的內存占用量。同時，M的大小也與算法的更新時間復雜度相關，在當前路由條數在 8 000左右的情況下，logN約為 13，選擇M=5可不過分突出眾節點重排序的時間開銷。在以上條件下，表5顯示了4種路由算法在查找Potaroo路由表時，不同分布前綴的查詢能力。其中，1 000+表示地址范圍劃分后前綴個數大于1 000的查找樹（與表 3相同），表中數值表示該算法對于該類查找樹各層部分前綴的平均查找時間。

表5中，Patricia對集中區和稀疏區前綴的查詢速度有較大差異，稀疏區的查詢速度明顯優于集中區，差距在4倍以上。BSR基本保持平均，對集中區的查詢速度優于Patricia，而稀疏區慢于前者。RBMRTs方法與BSR方法類似，性能相差不多。BSRPS算法由于進行了地址劃分，生成了多棵Level1層查找樹因此與Patricia具有相似的性能趨勢，均對稀疏區域的前綴有較好的查詢性能。而與BSR和RBMRTs相比，在集中區，BSRPS與前兩者性能相近，這是由于集中區形成的Level1層查找樹中節點總數并沒有成指數級的降低，查找樹深度降低不明顯，從而導致性能提升不高。在稀疏區，由于 BSRPS地址范圍劃分使得稀疏區前綴形成的獨立查找樹只具有少量的節點，查找深度大量減少，因此性能有很大提高。Tokyo和Atlanta路由表的測試結果與Potaroo類似。

在更新測試中，本文針對 Potaroo前綴集合首先對圖6所示的6種情況進行了更新測試。測試選取集中區域（1 000+，D）和稀疏區域（10+，F）的若干第一層子樹節點進行了插入測試。

表6 Potaroo更新性能/μs

表6中，BSRPS方法在稀疏區域（F）的更新性能與 Patricia相當，且由于查找性能提高和較少的自修復過程，整體更新性能優于RBMRTs算法。在集中區域（D），c/e 2種更新情況不需要復雜的更新流程，時間少于RBMRTs；在a/b/d/f 4種情況下，由于需要建立子樹或更新節點自修復等相對復雜的更新流程，BSRPS算法較RBMRTs增加了至多20%的更新時間。其中，a/b/f 3種情況表示Pnew前綴包含多個原有路由前綴的情況，d情況表示Pnew前綴處于原有2個前綴之間。通常路由更新時并不能進行查找操作，因此當上述4種情況頻率較高時，會增加分組丟失概率，降低用戶體驗。相反，若更新的情況主要是c/e 2種情況，如在新啟用的地址空間中分配 IPv6的前綴時，更新性能相比RBMRTs會有所提高。

為了驗證 BSRPS在極端情況下的性能，本文針對集中區（Du）與稀疏區（Fu）子樹第一層進行了連續插入 64個遞增前綴的極端環境測試，并獲得了這種情況對于查找速度的影響（Du-L，Fu-L），測試結果如表7所示。可以看到，BSRPS算法更新時間較長，但不超過RBMRTs的115%。在經過極端插入后，BSRPS算法在集中區和稀疏區均具有較好的查詢速度，查詢時間僅為 RBMRTs的 30%左右，Patricia的 40%左右。主要原因是連續插入的64個遞增前綴會在RBMRTs查找樹下形成深度為64的局部單鏈子樹，BSRPS形成深度為64/M的局部單鏈子樹，查找性能有線性級的提高。理論上，Patricia深度增加最少，為對數級。

表7 Potaroo極限情況/μs

5 結束語

高效的 IPv6路由算法是提高網絡傳輸性能的重要因素。本文提出的BSRPS算法通過地址范圍劃分、連續前綴集合和更新節點自修復算法在犧牲一定更新時間的條件下有效地提升了平均和極端情況下的查詢速度，同時也降低了內存的占用量，具有較好的性能。測試結果表明，查找性能在平均情況下性能比RBMRTs提升1.5倍，極端情況下提升3倍以上。

本文的研究仍存在一定不足。首先，M取值沒有給出規范的公式，這需要與內存和更新時間聯合評估；其次，本算法未從根本上消除RBMRTs算法頻繁更新產生的不平衡性，只是降低不平衡性對查詢的影響。當使用AVL進行平衡時，由于降低了節點總數，因此可提高AVL的性能；再次，集中區域a/b/d/f 4種情況下更新時間有所降低，增加更新過程導致分組丟失的概率，需進一步研究；最后，地址劃分的有效性較低，有效值僅為 3%，對集中區域的性能提升效果不佳，可采用文獻[14]中將2001：：/16前綴進行單獨劃分等方式進一步優化。

[1] http：//bgp.potaroo.net[EB/OL].2010.

[2] SUN Q, HUANG X H, ZHOU X J.A dynamic binary hash scheme for IPv6 lookup[A].Proceedings of IEEE GLOBECOM[C].New Orleans,USA, 2008.1-5.

[3] RUIZ-SANCHEX M A, BIERSACK E W, DABBOUS W.Survey and taxonomy of IP address lookup algorithms[J].IEEE Network, 2001,15(2)：8-23.

[4] SAHNI S, KIM K S.Efficient construction of multibit tries for IP address lookup[J].IEEE/ACM Trans Networking, 2003, 11(4)： 650-662.

[5] LIM H, YIM C H.SWARTZLANDER E.Priority tries for IP address lookup[J].IEEE Transactions on Computers, 2010, 6(59)： 784-794.

[6] WALDVOGEL M, VARGHESE G, TURNER J.Scalable high speed IP routing lookups[A].Proceeding of ACM SIGCOMM[C].Cannes,France, 1997.25-36.

[7] Kim K S, SAHNI S.IP lookup by binary search on prefix length[A].ISCC '03 Proceedings, of the Eighth IEEE International Symposium on Computers and Communications[C].Antalya, Turkey, 2003.77-82.

[8] LIM H, KIM W, LEE B.Binary search in a balanced tree for IP address lookup[A].IEEE Workshop High Performance Switching and Routing[C].HongKong, China, 2005.490-494.

[9] LIM H, KIM H, YIM C.IP address lookup for internet routers using balanced binary search with prefix vector[J].IEEE Transactions on Communication, 2009, 57(3)：618-821.

[10] LAMPSON B, SRINIVASAN V, VARGHESE G.IP lookups using multiway and multicolumn search[J].IEEE/ACM Trans Networking,1999, 7(3)：324-334.

[11] WARKHEDE P, SURI S, VARGHESE G.Multiway range trees： scalable IP lookup with fast updates[J].Computer Networks, 2004, 44： 289-303.

[12] SAHNI S, KIM K S.AnO(logN) dynamic router-table design[J].IEEE Transactions on Computers, 2004, 53(3)：351-363.

[13] ZHONG P F.An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update[A].Computer Science and Service System (CSSS)[C].Paris, France, 2011.2059-2063.

[14] 李振強, 鄭東去, 馬嚴.TSB：一種多階段 IPv6 路由表查找算法[J].電子學報, 2007, 35(10)：1859-1864.LI Z Q, ZHENG D Q, MA Y.TSB：a multi-stage algorithm for IPv6 routing table lookup[J].Chinese Journal of Electronics, 2007, 35(10)：1859-1864.

[15] http：//www.routeviews.org[EB/OL].2012.