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

(哈爾濱工業(yè)大學(xué) 網(wǎng)絡(luò)與信息安全技術(shù)研究中心，黑龍江 哈爾濱 150001)

1 引言

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

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

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

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

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

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

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

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

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

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

2 前綴值相關(guān)算法中查詢與更新的不平衡性

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

2.1 查詢不平衡性

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

表1 前綴實(shí)例

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

圖1 BSR查找樹

圖2 Patricia查找樹

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

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

2.2 更新不平衡性

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

圖3 更新不平衡性舉例

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

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

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

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

3.1 BSRPS算法劃分方法與框架

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

表2 前綴補(bǔ)充實(shí)例

圖4 RBMRTs算法框架

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

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

3.1.1 地址范圍劃分

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

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

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

表3 前綴分布關(guān)系

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

3.1.2 前綴集合劃分

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

圖5 集合劃分框架

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

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

3.2 BSRPS查找

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

算法1BSRPS主查找算法

算法2子樹內(nèi)遞歸查找算法

3.3 更新與自修復(fù)

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

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

圖6 BSRPS更新情況（Preset表示眾節(jié)點(diǎn)）

當(dāng)Pnew涉及多個(gè)眾節(jié)點(diǎn)時(shí)，更新操作相對復(fù)雜，如圖6(f)顯示了向左子樹擴(kuò)展多個(gè)眾節(jié)點(diǎn)的情況?？梢钥吹絇new覆蓋了PresetA的前面部分、PresetB的后面部分，且對于所有大于PresetB.P1小于PresetA.P3的前綴（斜杠條紋顯示），這些需要被替換的眾節(jié)點(diǎn)組成Pnew的包含子樹（與RBMRTs相同，需要對包含子樹進(jìn)行平衡旋轉(zhuǎn)，防止出現(xiàn)大量單分支眾節(jié)點(diǎn)）。而Pnew則被加入PresetA或PresetB，更新原有眾節(jié)點(diǎn)。

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

節(jié)點(diǎn)自修復(fù)算法的核心思想是當(dāng)眾節(jié)點(diǎn)自身在更新后不滿時(shí)，不斷從小于或大于該眾節(jié)點(diǎn)的區(qū)域中取最接近前綴以填補(bǔ)該眾節(jié)點(diǎn)的空白，直到該眾節(jié)點(diǎn)滿。該算法主要包括4個(gè)操作：重排序、定位、移動(dòng)和旋轉(zhuǎn)。下面以圖7為例說明這一過程。

圖7 自修復(fù)算法舉例

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

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

4 性能分析與實(shí)驗(yàn)

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

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

為了測試算法實(shí)際性能，筆者在一臺(tái)2.6 GHz主頻、16 GB內(nèi)存的服務(wù)器上對該算法進(jìn)行了對比測試。對比算法采用 Patricia、BSR和 RBMRTs 3種，實(shí)驗(yàn)數(shù)據(jù)采用了文獻(xiàn)[1,15]提供的 Potaroo、Tokyo和Atlanta路由表。表4列出了3個(gè)BGP路由表的相關(guān)參數(shù)。

表4 3種路由表及內(nèi)存占用

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

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

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

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

表6 Potaroo更新性能/μs

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

為了驗(yàn)證 BSRPS在極端情況下的性能，本文針對集中區(qū)（Du）與稀疏區(qū)（Fu）子樹第一層進(jìn)行了連續(xù)插入 64個(gè)遞增前綴的極端環(huán)境測試，并獲得了這種情況對于查找速度的影響（Du-L，F(xiàn)u-L），測試結(jié)果如表7所示?？梢钥吹?，BSRPS算法更新時(shí)間較長，但不超過RBMRTs的115%。在經(jīng)過極端插入后，BSRPS算法在集中區(qū)和稀疏區(qū)均具有較好的查詢速度，查詢時(shí)間僅為 RBMRTs的 30%左右，Patricia的 40%左右。主要原因是連續(xù)插入的64個(gè)遞增前綴會(huì)在RBMRTs查找樹下形成深度為64的局部單鏈子樹，BSRPS形成深度為64/M的局部單鏈子樹，查找性能有線性級的提高。理論上，Patricia深度增加最少，為對數(shù)級。

表7 Potaroo極限情況/μs

5 結(jié)束語

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

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

[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] 李振強(qiáng), 鄭東去, 馬嚴(yán).TSB：一種多階段 IPv6 路由表查找算法[J].電子學(xué)報(bào), 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.