IPv6融合樹結(jié)構(gòu)存儲及快速查找

張 沛，陳文龍，唐曉嵐

(首都師范大學(xué) 信息工程學(xué)院，北京 100048)

1 引 言

IPv4協(xié)議中每一個網(wǎng)絡(luò)接口由長度為32位IPv4地址表示，其地址空間為43億個.這一地址空間難以滿足未來移動設(shè)備和消費(fèi)電子設(shè)備對IP地址的巨大需求.截至目前，IPv4地址已全部分配完畢.

IPv6是下一代互聯(lián)網(wǎng)NGI(Next Generation Internet)的核心協(xié)議，和當(dāng)前計算機(jī)網(wǎng)絡(luò)使用的IPv4協(xié)議相比.IPv6的地址空間長度由IPv4的32位擴(kuò)展到128位，其中前64位為網(wǎng)絡(luò)前綴，后64位為主機(jī)地址.這樣龐大的地址空間可以滿足互聯(lián)網(wǎng)的指數(shù)型增長.隨著互聯(lián)網(wǎng)的進(jìn)一步發(fā)展，IPv4地址短缺問題變得越來越緊迫，IPv6也因此得到了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注和認(rèn)可.由此，產(chǎn)生了許多由IPv4到IPv6的相關(guān)技術(shù)[1-3].然而，IPv6仍采取最長前綴匹配查找，而現(xiàn)有的大多數(shù)IPv4查找算法不能直接適用到IPv6.因此，設(shè)計高效可行的IPv6查找算法是當(dāng)前面臨的難題.

路由表查找算法大致分為硬件算法和軟件算法.硬件算法：硬件三態(tài)內(nèi)容尋址存儲器(Ternary Content Addressable Memory，TCAM)算法[4]，IPv6查找的時間復(fù)雜度為0(1).但TCAM功耗大、價格昂貴且路由更新比較復(fù)雜.軟件算法：1)基于前綴長度的二分查找算法[5]，查找時間復(fù)雜度為0(W/M*logW)，其中M是機(jī)器的字寬，W是IP地址的長度.對于IPv4，W=32；對于IPv6，W=64(只考慮網(wǎng)絡(luò)前綴).在32位機(jī)上，使用基于前綴長度的二分查找算法來完成IPv6的最長前綴匹配，則最多需要64/32*(log64)=12次哈希.由于在查找中需要添加mark標(biāo)記位來確定其查找路線，在終點(diǎn)未查到匹配項時需要進(jìn)行回溯處理，其最壞情況下的性能難以預(yù)測.2)基于前綴區(qū)間的二分查找[6]，算法時間復(fù)雜度為0(log2N).最壞情況下，更新一個關(guān)鍵字會影響0(N)個地址空間.由此，二分查找算法的更新性能較差，且存儲空間過大.3)基于Hash表的路由查找算法[7-11].算法[7]提出的算法采用哈希和樹位圖技術(shù)進(jìn)行查找，采用硬件并行流水技術(shù)實現(xiàn)該算法時，能夠很好地平衡IPv6路由查找空間和速度，但更新較復(fù)雜.4)多比特查找樹算法[12，13]，有時也被稱為分段算法，查找性能和分段的層數(shù)成反比，內(nèi)存消耗和分段的層數(shù)成正比.近期研究的查找算法[14-18]的主要適用路由前16位取值不多，且路由項較少的情況.如TSB[18]將所有的前16位取值按數(shù)量進(jìn)行二叉樹存儲，對于前16位數(shù)量較多的路由項，添加段表以加快查找速率，對于前16位較少的路由項，則直接利用路由桶技術(shù)進(jìn)行查找.

用Trie樹結(jié)構(gòu)來表示地址前綴是一種常用的方法，Trie樹采用一種基于樹的數(shù)據(jù)結(jié)構(gòu)，它通過前綴中每一位比特值來決定樹的分支.而多比特Trie樹則是一種提高Trie樹查找效率的方法，即查找每一步檢查地址中的多個比特，而不僅僅是一個.多分支Trie樹的查找過程與一般的二分支Trie樹的查找過程類似，在每次節(jié)點(diǎn)訪問過程中，記錄下到目前為止已經(jīng)匹配上的最長地址前綴，直到到達(dá)葉子節(jié)點(diǎn)，搜索過程結(jié)束.由于多分支Trie樹采用的步寬大于1，所以它的搜索效率會有明顯的提升.

本文設(shè)計了一種融合樹結(jié)構(gòu)的IPv6查找算法，將所有路由存放在節(jié)點(diǎn)中，查找時直接定位樹節(jié)點(diǎn)，并通過回溯指針確?？焖偻瓿勺铋L前綴匹配.該方案支持快速IP查找，并能有效的對路由前綴進(jìn)行插入和刪除操作.提出方案以多分支Trie樹(Multibit Trie)為基礎(chǔ)，以融合存儲(Fusion Storage)與回溯指針(Backtracking Pointer)為核心，因此我們稱該算法為MFB算法.

2 IPv6路由分布特點(diǎn)

IPv6的地址分配采用分級結(jié)構(gòu)，因特網(wǎng)分配地址權(quán)威機(jī)構(gòu)IANA(Internet Assigned Number-Authority)負(fù)責(zé)IPv6地址空間的分配，目前IANA從可聚合全球單播地址空間(格式前綴001)中將高位地址分配給RIR(Regional Internet Registries).RIR則將已獲得的高位地址再次分配給下級地址機(jī)構(gòu)：本地因特網(wǎng)服務(wù)提供商(Internet Service Provider)、本地因特網(wǎng)注冊機(jī)構(gòu)(Local Internet Registries).最終用戶(End Users)再根據(jù)自身規(guī)模的需要向ISP/LIR申請所需的IPv6地址.IPv6的128位超大空間和靈活的地址結(jié)構(gòu)也為IPv6制定更好的地址分配策略提供了前提.為了更好保證IPv6地址分配的可聚合性和節(jié)約性，IPv6明確規(guī)定了各級地址分配機(jī)構(gòu)可以分配的前綴長度，這使得IPv6路由表呈現(xiàn)出更好的層次性.

以主干網(wǎng)1為對象，分析該路由表中的前綴長度規(guī)律，從圖1和圖2中可以看出：

1) 所有路由的前綴長度都在16～64之間；

2) 前綴長度為32和48路由占到整體數(shù)量的70.61%；

3) 路由表中路由前綴的前16位取值類型很少，“取值”是把前綴的1-16位作為整體轉(zhuǎn)換成10進(jìn)制后得到的一個值.對于該AS的主干網(wǎng)路由表，前綴1-16位取值僅有52個.

圖1 IPv6前綴長度分布Fig.1 IPv6 prefix length distribution

將IP前綴的前16位取值相同的路由集合定義為一個路由域(rooting region)，簡稱RR.例如：前16位是0x2001的路由集合稱為RR(2001).

圖2 Rooting region數(shù)量分布Fig.2 Rooting region number distribution

3 MFB算法

3.1 整體結(jié)構(gòu)

基于前文所述的IPv6地址結(jié)構(gòu)、IPv6地址分配策略和IPv6骨干網(wǎng)路由表特點(diǎn)，對于數(shù)量級為1-10(如圖2)的rooting region域，直接使用二分查找，最大查找次數(shù)為4.對于數(shù)量級大于10的，本文設(shè)計了一種基于融合樹結(jié)構(gòu)的多分支Trie樹模型.以節(jié)點(diǎn)為整體單位，將所有路由歸屬到某一節(jié)點(diǎn)，利用Trie樹的三層節(jié)點(diǎn)實施路由查找.

路由表的整體結(jié)構(gòu)如圖3所示.根據(jù)主干網(wǎng)中IPv6的分布特點(diǎn)，IPv6主干網(wǎng)路由表中前16位取值較少，在查找時先對前16位進(jìn)行第一次查找定位到具體的某一棵Trie樹中.

3.2 自定義型Trie樹結(jié)構(gòu)

根據(jù)主干網(wǎng)中的分布特點(diǎn)，前綴長度為32、48的路由數(shù)量較大，占比70%以上.所以，本文針對同一region域，設(shè)計了16位步長的多比特Trie樹進(jìn)行路由存儲.前綴長度為16、32、48的路由為節(jié)點(diǎn)(Backbone Node)，分別存儲在Trie樹結(jié)構(gòu)的第1-3層.每個節(jié)點(diǎn)包含3部分：主干路由(Backbone Routing Entry)，附加路由(Addition Routing Entry)，回溯指針

1http：//bgp.potaroo.net/v6/as2.0/bgptable.txt.

(Backtracking Routing Pointer).

主干路由：前綴長度為16、32、48的路由.主干路由為節(jié)點(diǎn)的核心，每個節(jié)點(diǎn)有且僅有一個主干路由，但其可能為真實節(jié)點(diǎn)(如圖4中B、C節(jié)點(diǎn)，圖中所有灰色區(qū)域為真實路由，下同)，可能為空節(jié)點(diǎn)(如圖4中A、D節(jié)點(diǎn)).

圖3 MFB整體結(jié)構(gòu)Fig.3 MFB whole frame

附加路由：所有前綴長度不為32、48的路由.我們首先給出如下定義.

定義1.對于兩個給定的IP前綴IP1：address1/masklen1，IP2：address2/masklen2不妨設(shè)masklen2>masklen1.我們稱IP1歸屬于IP2，當(dāng)且僅當(dāng)IP1的前綴地址address1補(bǔ)0至前綴長度masklen2后得到新前綴address1′與address2完全一致.

附加路由與主干路由的關(guān)系為上面描述的歸屬關(guān)系，若附加路由的前綴長度在17～31之間，則歸屬在前綴長度為32的路由上.(圖4中A節(jié)點(diǎn)的附加路由2001:1200::/23將其補(bǔ)0至32位后存放在對應(yīng)節(jié)點(diǎn)2001:1200::/32上).若附加路由的前綴長度在33～47之間，則歸屬在前綴長度為48的路由上.對于附加路由前綴長度在49～64之間的，路由表中極少.路由表[17]只有19個.具體操作時，我們將其鏈接在第三層節(jié)點(diǎn)下，使用鏈表查詢，本文中不做重點(diǎn).每個節(jié)點(diǎn)可能有一個或多個附加路由(圖4中A、C、D節(jié)點(diǎn))，也可能沒有附加路由(圖4中B節(jié)點(diǎn)).在查找路由時，不直接查找附加路由，而是通過回溯指針間接查找到附加路由.

3.3 回溯指針

定義2.路由集合S中各路由項的目的IP前綴描述為IPi：addressi/maskleni，i=1，2，…，n.對于給定前綴IPx：addressx/masklenx，令集合S的子集S′，且IPx歸屬于S′中每條路由項的目的IP前綴，則S′中masklen最大的路由項被稱為IPx的最近上游路由.

例如：路由表中有如下前綴2001:2300::/24、2001:2330::/28、2001:2333::/32、2001:2355::/32.則根據(jù)以上定義，2001:2333::/32的最近上游路由為2001:2330::/28.2001:2355::/32的最近上游路由為2001:2300::/24.

回溯指針為指向本節(jié)點(diǎn)下主干路由最近上游路由的指針.記為Rcon.添加回溯指針的主要意義在于使所有查找進(jìn)程都在節(jié)點(diǎn)中進(jìn)行.若沒有回溯指針，則在查找節(jié)點(diǎn)且無匹配項后，則需要進(jìn)一步在臨近的節(jié)點(diǎn)中進(jìn)行回溯查找，時間消耗過大.在添加回溯指針后，對于同一層中，若不匹配，則直接匹配到回溯指針上，并進(jìn)行下一層查找，極大的提升時間效率.(圖4中節(jié)點(diǎn)A的主干路由為2001:1200::/32，附加路由2001:1200::/23，2001:1200::/24都為其父節(jié)點(diǎn)，但路由2001:1200::/24的前綴長度最大，所以節(jié)點(diǎn)A的回溯指針為(2001:1200::/24).由于回溯指針指向的是其最近上游路由，而該節(jié)點(diǎn)下主干路由的最近上游路由不一定在本節(jié)點(diǎn)中，這是因為該路由與其最近上游路由只是前綴相匹配.例如路由2001:1200::/24與2001:1234::/32他們的前24位相匹配，2001:1200::/24是2001:1234::/32的最近上游路由，但是他們存儲在兩個不同的節(jié)點(diǎn)中.所以回溯指針指向的路由可能在本節(jié)點(diǎn)中(圖4中節(jié)點(diǎn)A)，也可能在其他節(jié)點(diǎn)中(圖4中節(jié)點(diǎn)B).

3.4 Trie結(jié)構(gòu)融合

在Trie樹每一層節(jié)點(diǎn)查找過程中，采用直接尋址表，即建立一個216的段表(每一次查找16位)，一次定位到對應(yīng)樹節(jié)點(diǎn).在第一層根節(jié)點(diǎn)查找第二層節(jié)點(diǎn)時，構(gòu)建一個段表.不過，在第二層節(jié)點(diǎn)查找第三層節(jié)點(diǎn)時，由于 每一個第二層節(jié)點(diǎn)都需一個段表，且所建段表極為稀疏，空間利用率極低.為提升存儲效率，我們將第三層節(jié)點(diǎn)融合，具體融合方法是將所有主干節(jié)點(diǎn)中主干路由的33-48位一致的路由進(jìn)行融合存儲.如圖5中的D、E、F節(jié)點(diǎn)，它們的主干路由第33-48位都為0x2200，記為Area(2200).

對于某一個Area來說，由于存儲節(jié)點(diǎn)的主干路由的1-16位與33-48位完全一致，而17到32位不等，這就導(dǎo)致可能會發(fā)生沖突，如圖5中Area(2200)與Area(2234).若所有1-16位與33-48位一致的主干路由少于或等于1個，就不會發(fā)生沖突，如Area(2256)與Area(3456).

在進(jìn)行融合查找時，需將目的地址的17-32位與主干路由中的17-32位作比較，匹配后記錄下匹配項.例如，收到目的地址為2001:1200:2200:f000::1的報文.根據(jù)目的地址的33-48位0x2200找到Area(2200)，并順序分析各所屬節(jié)點(diǎn).第一個節(jié)點(diǎn)D，其主干路由的17-32位0x1000與目的地址不匹配；繼續(xù)向下查找節(jié)點(diǎn)E，主干路由17-32位與目的地址0x1200匹配，查找成功并記錄下匹配項.

在同一Area中，若節(jié)點(diǎn)沖突較少(本文定為節(jié)點(diǎn)數(shù)量不超過3)，則可用鏈表查詢.在AS2.0路由表中，最大的沖突個數(shù)為region(0x2620)中的Area(0x4000)有98個節(jié)點(diǎn)(僅包括節(jié)點(diǎn)的主干路由為真實節(jié)點(diǎn)的情況)，對于這種數(shù)量級，如果使用直接尋址表，則由于數(shù)據(jù)較少且數(shù)據(jù)跨度過大，造成空間利用率低.本文使用除法散列的方法來解決這一問題.

在用來設(shè)計散列函數(shù)的除法散列法[19]中，通過取x除以m的余數(shù)，將關(guān)鍵字x映射到m個槽中的某一個上，即散列函數(shù)為：

hab(x)=((ax+b)modn)modm

(1)

其中a，b為自定義參數(shù).n為原數(shù)據(jù)的跨度，在這里都為216，(ax+b)的作用有兩點(diǎn)：

1) 原數(shù)據(jù)先進(jìn)行一次線性變換，再進(jìn)行模n的歸約，使原數(shù)據(jù)均勻散列，降低下一次模m歸約時發(fā)生沖突的概率.

2) 若原數(shù)據(jù)通過除法散列法后發(fā)生沖突，則可通過對參數(shù)a，b的修改使其不發(fā)生沖突.

m為最后進(jìn)行歸約的空間大小，它與Area中的數(shù)量t相關(guān)，顯然m>t.且對于數(shù)量t越大的數(shù)據(jù)，往往需要更大的空間來減小最后歸約時的沖突概率，這里對于數(shù)量t小的數(shù)據(jù)不妨設(shè)m=2p+1-1，2p為大于t的最小的以2為底的冪.以圖5中Area(2200)發(fā)生的沖突為例，這里沖突的數(shù)量t為3，p=2，設(shè)n=216，m=7，a=2，b=50.首先將發(fā)生沖突的16位二進(jìn)制數(shù)轉(zhuǎn)化為10進(jìn)制，再進(jìn)行除法歸約，得到除法散列表(如圖6所示).再根據(jù)得到的散列表找到對應(yīng)的節(jié)點(diǎn).需要注意的是，當(dāng)查找到節(jié)點(diǎn)后仍需對17-32位進(jìn)行一次比較(歸約到最后出發(fā)散列表的地址會有多項，如0x1001經(jīng)過散列公式(1)后關(guān)鍵字也為5)，匹配后方可記錄匹配項.

圖5 融合Trie樹示例圖Fig.5 Fusion Trie tree sample graph

圖6 除法散列算法示例Fig.6 Example of division hash algorithm

在查找節(jié)點(diǎn)時，可通過添加虛擬節(jié)點(diǎn)提升后續(xù)相同目的IP的匹配速度.如圖5中的H節(jié)點(diǎn)，雖然它的主干路由不為真實路由，也無附加路由，但當(dāng)接收到目的地址2001:1000:2234::1的時候，需要借助節(jié)點(diǎn)H中的回溯指針找到其匹配的路由2001:1000:2200::/40.對于2001:1000:2200::/40這一條附加路由而言，需要添加主干路由為2001:1000:2200::/48-2001:1000:22ff::/48的共計256個節(jié)點(diǎn).顯然，實際流量進(jìn)行路由匹配時，由于實際流量遵循28原則，其中大部分節(jié)點(diǎn)我們不會用到，造成較大浪費(fèi).本文利用?；顧C(jī)制優(yōu)化存儲效率，所謂保活機(jī)制即在初始化路由表時，不添加任何空節(jié)點(diǎn)(空節(jié)點(diǎn)即該節(jié)點(diǎn)下無任何真實的主干路由與附加路由)，當(dāng)接收到目的地址時，才建立對應(yīng)的空節(jié)點(diǎn).以圖5中的H節(jié)點(diǎn)為例，當(dāng)接收到目的地址為2001:1000:2234::1的報文時，才會生成H節(jié)點(diǎn)，并添加2001:1000:2234::/48的回溯指針.回溯指針指向其最近上游路由，即2001:1000:2200::/40.此后，所有以2001:1000:2234::/48為前綴的目的地址都將通過H節(jié)點(diǎn)及回溯指針完成快速路由匹配.

虛擬節(jié)點(diǎn)的回溯指針生成方法是根據(jù)前綴長度從大到小查找與之匹配的上游路由.但在實際查找時，由于附加路由的特定查找形式，無需按位依次進(jìn)行查找，只需根據(jù)查找數(shù)據(jù)中1的數(shù)量進(jìn)行分組，同一組的附加路由存放在同一節(jié)點(diǎn)中，依次在組中進(jìn)行查找即可.

以構(gòu)建虛擬節(jié)點(diǎn)2001:1000:2208::/48的回溯指針為例.根據(jù)路由33-48位中1的數(shù)量對附加路由進(jìn)行分組(0010 0010 0000 1000).附加路由2001:1000:2208::/45-2001:1000:2208::/47都存放在以2001:1000:2208::/48為主干路由的節(jié)點(diǎn)下；同理附加路由2001:1000:2200::/39-2001:1000:2200::/44存放在以2001:1000:2200::/48為主干路由的節(jié)點(diǎn)下；附加路由2001:1000:2000::/35-2001:1000:2000::/38都存放在以2001:1000:2000::/48為主干路由的節(jié)點(diǎn)下；附加路由2001:1000:0000::/33-2001:1000:0000::/34存放在以2001:1000:0000::/48為主干路由的節(jié)點(diǎn)下.依次查找以2001:1000:2208::/48，2001:1000:2200::/48，2001:1000:2200::/48，2001:1000:2200::/48為主干路由的節(jié)點(diǎn).找到匹配項，建立虛擬節(jié)點(diǎn)，添加Rcon回溯指針信息.若無匹配項，則Rcon指向null.

該機(jī)制對于重合度不高的流量，該算法的查找時間會有所增加.但真實流量遵循28原則，該機(jī)制不僅能減少冗余空間的產(chǎn)生，并且極大的減少查找時間.

3.5 路由查找

查找路由時，根據(jù)該融合Trie樹的特性，采用分層查找的方法進(jìn)行查找.首先，通過目的地址的前16位定位到具體某一rooting region域中，后續(xù)操作在同一Trie樹中完成.由于遵循最長前綴匹配原則，為了提高查找效率，先查找第三層節(jié)點(diǎn).若找到匹配項，則無需查找第二層節(jié)點(diǎn)(第二層匹配項的前綴長度一定小于第三層匹配項的前綴長度)，直接從匹配路由的對應(yīng)出口轉(zhuǎn)發(fā)即可.若第三層節(jié)點(diǎn)無匹配項，則需查找第二層節(jié)點(diǎn).若第二層節(jié)點(diǎn)無匹配項，則利用默認(rèn)路由出接口轉(zhuǎn)發(fā).在查找到的節(jié)點(diǎn)中，若主干路由為真實路由，無需查找回溯指針，因為回溯指針的前綴長度一定小于主干路由的前綴長度.故有如下結(jié)論：查找某一節(jié)點(diǎn)時，主干路由匹配，無需查找回溯指針.

具體路由查找算法如下，其中desIP為接收到的目的地址.NP為最長前綴匹配路由的下一跳地址.

1 search MFB(desIP){

2 NP=nexthop of default route;

3 num1=the 1-16 bits of desIP after decimal;

4 node=searchTreeNode(num1);

5 if(node==null) returnNP;

6 NP=node.nexthop;

7 num2=the 33-48 of desIP after decimal;

8 node1=searchArea(num2);

9 if(node1!=null){

10 if(node1.backbone_routing!=null)

11 NP=node1.backbode_routing.nexthop;

12 else NP=node1.rcon.nexthop;

13 return NP;

14 }

15 else{

16 num3=the 17-31 of desIP after decimal;

17 node2=searchArea(num3);

18 if(node2!=null){

19 if(node2.backbone_routing!=null)

20 NP=node2.backbode_routing.nexthop;

21 else NP=node2.rcon.nexthop;

22 return NP;

23 }

24 }

25 }

以圖5為例.若查找目的地址2001:1000:2200:1234::1.首先查找目的地址的33-48位0x2200，找到Area(2200)中的D節(jié)點(diǎn)，D節(jié)點(diǎn)中的主干路由2001:1000:2200::/48為真實路由，記錄下匹配項，結(jié)束查找.

若查找目的地址2001:1234:2200:ffff::1，查找目的地址的33-48位0x2200，找到Area(2200)中的F節(jié)點(diǎn)，F(xiàn)節(jié)點(diǎn)中的主干路由2001:1234:2200::/48不為真實路由，繼續(xù)查找節(jié)點(diǎn)中的回溯指針2001:1234:2200::/39，記錄下匹配項，結(jié)束查找.

若查找目的地址是2001:1234:ffff::1.查找目的地址的33-48位0xffff，沒有找到Area(ffff).因此第三層節(jié)點(diǎn)無匹配項.繼續(xù)在地址中查找17-32位0x1234.找到節(jié)點(diǎn)C，節(jié)點(diǎn)C的主干路由不為真實路由，繼續(xù)查找節(jié)點(diǎn)中的回溯指針，找到匹配項2001:1200::/24.

3.6 路由維護(hù)

主干路由是節(jié)點(diǎn)的核心，主干路由的增加與刪除并不意味著節(jié)點(diǎn)的增加或刪除.仍以圖5為例進(jìn)行說明.

當(dāng)增加主干路由2001:ffff::/32時，我們需要添加一個新的節(jié)點(diǎn).若增加的主干路由為2001:1234:2200::/48時，我們只需將節(jié)點(diǎn)F的主干路由標(biāo)記為真實路由即可.若刪除路由2001:1000:2200::/48時，由于D節(jié)點(diǎn)中仍有附加路由2001:1000:2200::/40，所以不能刪除整個D節(jié)點(diǎn)，只需將D節(jié)點(diǎn)中的主干路由標(biāo)記為非真實路由即可.若刪除路由2001:1234:3456::/48，由于節(jié)點(diǎn)J除主干路由外無其他路由信息，因此將J視為無用節(jié)點(diǎn)，刪除整個J節(jié)點(diǎn).

附加路由的維護(hù)與主干路由類似，若添加附加路由時，我們只需將附加路由補(bǔ)0添加到相應(yīng)的位置上，在沒有節(jié)點(diǎn)時添加節(jié)點(diǎn).刪除附加路由時，在對應(yīng)的節(jié)點(diǎn)處刪除路由，若在刪除過后無任何路由項信息，則刪除整個節(jié)點(diǎn).

對于附加路由我們?nèi)孕杼砑忧昂罄^關(guān)系.優(yōu)點(diǎn)在于當(dāng)刪除的路由為Rcon指針指向的路由時，需更新Rcon指針信息，此時無需再從附加路由里一一進(jìn)行查找，而是查找刪除路由的前繼路由即可.在圖7中，若刪除的節(jié)點(diǎn)為2001:1200::/24，節(jié)點(diǎn)的Rcon路由直接指向2001:1200::/24的前繼節(jié)點(diǎn)2001:1000::/20，極大減少路由更新時間.

圖7 前后繼關(guān)系維護(hù)示例圖Fig.7 Example of relationship maintenance

在刪除附加路由時，只需將該附加路由的后繼路由的前繼改為自身的前繼即可，例如圖7中刪除2001:1200::/24.則直接將2001:12f0::/28的前繼改為自身的前繼2001:1000::/20即可.

在添加路由時首先需要找到自身的前繼節(jié)點(diǎn)，這里采用移位法.例如若添加路由0x1C60/12 (0001 1100 0110 0000)則依次看向左移1，2，…，k位，查看路由0x1C60/12 (0001 1100 0110 0000)，依次查看節(jié)點(diǎn):0x1C40 (0001 1100 0100 0000)，0x1C00 (0001 1100 0000 0000)，0x1800(0001 1000 0000 0000)，0x1000(0001 0000 0000 0000).

若添加路由時，若找不到前繼路由，則其前繼路由為根節(jié)點(diǎn)，但根節(jié)點(diǎn)不能作為Rcon指向的目標(biāo)，若某一路由的前繼路由為根節(jié)點(diǎn)，則Rcon指向null.在找到前繼路由后，向下找后繼路由，其方法是通過前繼路由查找后繼路由，因為添加路由的后繼路由一定在前繼路由的后繼中.圖7中，我們實施添加路由操作，目的前綴為2001:3400::/24.首先找到其前繼路由2001::/16，進(jìn)一步在2001::/16的后繼路由中查找后繼路由，并改變前后繼關(guān)系.通過建立附加路由之間的前后繼關(guān)系，在更新Rcon指向的路由時，極大的提高了更新速度，完善了數(shù)據(jù)結(jié)構(gòu)的整體性.

4 實驗分析

為了驗證本算法的性能，在Windows操作系統(tǒng)下模擬算法的軟件原型系統(tǒng)，測試用PC機(jī)安裝win7操作系統(tǒng)，硬件配置為2G DDR內(nèi)存，Intel Core i7-4790CPU @3.6Hz.本文以AS2.0 IPv6 BGP Table為基本路由表，本文以TSB[16]為對比實驗對查找時間以及存儲空間進(jìn)行分析.隨機(jī)抽取1k、2k、5k、10k、20k、50k條真實流量數(shù)據(jù)，其函數(shù)圖在區(qū)間上為增函數(shù)，且逐漸收斂于某一數(shù)據(jù)，其平均查找時間結(jié)果如圖8、圖9所示.

3.53.02.52.01.51.00.50012查找路由條數(shù)×104MFBTSB平均查找時間(μ)s34543210查找路由條數(shù)×104MFBTSB平均查找時間(μs)012345圖8 第一次平均查找時間圖9 第二次平均查找時間Fig.8 First time to find Fig.9 Second average the averagesearch time

圖10 第一次平均以及最大查找次數(shù)Fig.10 First average and maximum number of lookups

查找真實流量，對于第一次查找時，MFB的平均查找時間較小于TSB，但MFB的第二次平均查找時間明顯優(yōu)于TSB，而且隨著查找條數(shù)的增多，MFB的第二次平均查找時間沒有明顯變化.這是由于保活機(jī)制的存在，極大地減少了內(nèi)存訪問次數(shù).此方法適用于流量較為集中的情況，由于真實流量符合二八定律，所以MFB在查找真實流量情況時，在查找速度方面有優(yōu)勢.

查找路由條數(shù)×104第二次平均查找次數(shù)第二次最大查找次數(shù)012345543210查找次數(shù)403020100占用內(nèi)存大小)(MB005.10.15.20.25.30.查找路由條數(shù)×104MFBTSB圖11 第二次平均以圖12 占用內(nèi)存空及最大查找次數(shù)間大小Fig.11 Second average andFig.12 Occupied memorymaximum lookups space size

第一次的平均查找次數(shù)與最大查找次數(shù)都較大，如圖10所示.且最大查找次數(shù)不穩(wěn)定.由于兩次查找的是相同的流量，第二次查找時會直接根據(jù)第一次查找時建立的回溯指針直接定位到符合最長前綴匹配的路由.極大的減少了查找次數(shù),如圖11所示.

本算法由于多分支Trie樹的建立，造成了一定空間的冗余.雖然進(jìn)行了融合，但大部分段表上數(shù)據(jù)分布仍十分稀疏，空間略大于其他算法，整體呈線性增長，如圖12所示.

5 結(jié)束語

充分分析了IPv6地址結(jié)構(gòu)和IPv6地址分配策略和IPv6骨干網(wǎng)路由表的特點(diǎn)，設(shè)計一種自定義型Trie樹結(jié)構(gòu)，相比以往算法，具有查找速度快，擴(kuò)展性好的特點(diǎn).實驗結(jié)果表明，算法在首次接收到流量時，內(nèi)存訪問次數(shù)以及查找時間可能較長，但由于?；顧C(jī)制與回溯指針機(jī)制的存在，后續(xù)查找時間大大降低.在查找大量流量時，大流量平均查找時間為：1.88μs/條.