哈希表和多比特Trie相結(jié)合的IPv6分階段路由查找算法

秦 怡，楊 云，閔玉涓，姚 明，趙晶晶

(揚(yáng)州大學(xué) 信息工程學(xué)院計(jì)算機(jī)系，江蘇 揚(yáng)州 225127)

1 引 言

隨著近幾年物聯(lián)網(wǎng)以及車聯(lián)網(wǎng)等概念的大熱，目前互聯(lián)網(wǎng)上廣泛使用的IPv4(Internet Protocol Version 4)技術(shù)已經(jīng)很難支撐起網(wǎng)絡(luò)的持續(xù)發(fā)展[1].IPv6作為IPv4的換代技術(shù)，能夠很好的解決目前IPv4網(wǎng)絡(luò)中存在的諸如：IPv4資源耗盡、路由表規(guī)模龐大、安全性和服務(wù)質(zhì)量不高等問題，但是至今仍然在科研等領(lǐng)域內(nèi)小范圍使用[2].雖然為了緩解IPv4地址即將耗盡的問題，提出了在IPv4技術(shù)的基礎(chǔ)上引入CIDR(無類型域間路由選擇)技術(shù)[3]使其地址前綴分配更加靈活[4]，但是由于IPv4本身設(shè)計(jì)的缺陷，已經(jīng)無法支撐起互聯(lián)網(wǎng)的進(jìn)一步發(fā)展，而IPv6是由IETF設(shè)計(jì)的用來取代IPv4的下一代IP協(xié)議，無論是在安全性方面還是服務(wù)質(zhì)量方面都有很明顯的改進(jìn).根據(jù)IETF發(fā)布的RFC2460可知，IPv6與IPv4最大的變化在于IPv6地址長(zhǎng)度達(dá)到了128比特，這個(gè)改變一勞永逸的解決了IPv4地址空間耗盡的問題.但是IPv6較長(zhǎng)的地址長(zhǎng)度，增加了最長(zhǎng)前綴匹配的難度和復(fù)雜度，雖然現(xiàn)有許多基于IPv4的快速路由查找算法，但是這些路由查找算法很難移植到IPv6中去，或者移植之后性能低下，實(shí)用性較低.因此需要設(shè)計(jì)一種適用于IPv6的路由查找算法，推動(dòng)IPv6的普及.本文的主要內(nèi)容是提出一種適合在IPv6網(wǎng)絡(luò)中的高速路由查找算法.

2 相關(guān)算法及研究

最長(zhǎng)地址前綴匹配問題，是路由查找算法中最需要解決的問題，也是目前研究最多的部分.最長(zhǎng)地址前綴匹配算法研究方向大致分為基于Trie、基于哈希表、以及基于硬件這三種[5].其中基于Trie樹的算法中，最經(jīng)典的是二進(jìn)制Trie樹.在這種數(shù)據(jù)結(jié)構(gòu)中，下一跳路由信息被保存在葉子節(jié)點(diǎn)或分支節(jié)點(diǎn)中，在進(jìn)行路由查找過程中，根據(jù)前綴的每一比特是0還是1來決定左右分支.通過這種數(shù)據(jù)結(jié)構(gòu)，進(jìn)行IPv6的路由查找最壞情況下需要進(jìn)行128次存儲(chǔ)器訪問，性能較低.隨后又有學(xué)者在二進(jìn)制Trie樹上進(jìn)行改進(jìn)，提出壓縮、多bit等改進(jìn)算法[6-9].

在早期的Linux系統(tǒng)中，路由查找算法采用的是哈希表結(jié)構(gòu)，Linux為每個(gè)地址前綴長(zhǎng)度都維護(hù)了一張哈希表，在路由查找時(shí)，將目的IP地址從最長(zhǎng)的前綴長(zhǎng)度開始哈希，根據(jù)哈希結(jié)果選擇下一跳路由信息.哈希表具有查詢速度快的特點(diǎn)，在理想狀況下只需要一次存儲(chǔ)器訪問，然而基于哈希的算法大多數(shù)擴(kuò)展性較差，隨著路由表表項(xiàng)的增加，哈希表的沖突問題會(huì)越來越嚴(yán)重，這將導(dǎo)致路由查找時(shí)間不可控的問題[10-12].

基于硬件的查找算法具有查找速度快、實(shí)現(xiàn)簡(jiǎn)單和可并行訪問的特點(diǎn)[13]，但是基于硬件成本高昂，單位比特的TCAM比較昂貴，存儲(chǔ)容量有限[14].同時(shí)，由于是基于硬件的算法，因此可擴(kuò)展性較差[15].

3 算法設(shè)計(jì)

本節(jié)將從算法思想與依據(jù)、相關(guān)數(shù)據(jù)結(jié)構(gòu)、哈希函數(shù)設(shè)計(jì)與沖突處理和算法的實(shí)現(xiàn)四個(gè)方面，對(duì)算法進(jìn)行詳細(xì)的解釋分析.

3.1 算法思想與依據(jù)

在研究了IPv6地址前綴分布規(guī)律和當(dāng)前主流算法的基礎(chǔ)上，對(duì)LFT進(jìn)行改進(jìn)[16].如圖1所示，根據(jù)potaroo提供的核心路由器路由表數(shù)據(jù)可以得出，IPv6的地址前綴長(zhǎng)度主要集中在[32，48]區(qū)間中，其中以前綴長(zhǎng)度為48的表項(xiàng)最多，占全部表項(xiàng)的4成以上.其次為前綴長(zhǎng)度為32的表項(xiàng)，占全部表項(xiàng)五分之一，其余前綴長(zhǎng)度的路由表項(xiàng)數(shù)量較少，不存在前綴長(zhǎng)度小于16的表項(xiàng).同時(shí)根據(jù)RFC3587規(guī)定，128比特的IPv6地址中，只有前64位參與路由尋址，后64比特為接口地址，因此路由表中不存在前綴長(zhǎng)度大于64的表項(xiàng).

圖1 核心路由器路由表IPv6地址前綴長(zhǎng)度分布圖Fig.1 IPv6 address prefix length distribution in core router

圖2 前綴值所占百分比Fig.2 Percentage of prefix value

如圖2所示，根據(jù)IPv6 網(wǎng)絡(luò)的AS6939的核心路由器數(shù)據(jù)統(tǒng)計(jì)分析，核心路由器中路由表的表項(xiàng)大多以20、24、26、28和2a開頭，以其他數(shù)值開頭的表項(xiàng)很少或沒有，且常用表項(xiàng)中，以2001開頭的表項(xiàng)最多.

此外，IPv6經(jīng)過十幾年的發(fā)展逐漸走向成熟，其地址前綴長(zhǎng)度的分布已趨向于穩(wěn)定.如圖3所示，根據(jù)potaroo對(duì)IPv6網(wǎng)絡(luò)建網(wǎng)以來的統(tǒng)計(jì)，以地址前綴長(zhǎng)度32和48為例，在IPv6網(wǎng)絡(luò)成立初期，地址前綴長(zhǎng)度為32的表項(xiàng)占路由表所有表項(xiàng)的65%，并且其數(shù)量一度領(lǐng)先于地址前綴長(zhǎng)度為48的表項(xiàng).從2009年開始，地址前綴長(zhǎng)度為32的表項(xiàng)逐年下降，并慢慢穩(wěn)定在了24%左右，而地址前綴長(zhǎng)度為48的表項(xiàng)呈現(xiàn)平穩(wěn)上升態(tài)勢(shì)，并逐漸穩(wěn)定在了45%左右.從2013年起，地址前綴長(zhǎng)度為48的表項(xiàng)的數(shù)量，超越了地址前綴長(zhǎng)度為32的表項(xiàng)，一直占據(jù)了大部分的路由表.

圖3 32、48前綴長(zhǎng)度表項(xiàng)數(shù)量歷年趨勢(shì)Fig.3 Trend of items in router table by prefix length (32 and 48)

根據(jù)上述IPv6地址前綴分布特點(diǎn)可知，在IPv6網(wǎng)絡(luò)中，路由表中目前前綴長(zhǎng)度為16倍數(shù)的路由表項(xiàng)最多，在這些表項(xiàng)中，前綴長(zhǎng)度為48的表項(xiàng)最多，其次是前綴長(zhǎng)度為32的表項(xiàng).因此，如果算法在設(shè)計(jì)時(shí)考慮從48比特切入，優(yōu)先查找48比特的表項(xiàng)，使路由查找操作在大部分情況下只需要訪問一次存儲(chǔ)器.同時(shí)與IPv4不同的是，IPv6的前綴值分布具有很明顯的特點(diǎn)，即以20、24、26、28和2a開頭的地址前綴占絕大部分.算法根據(jù)這個(gè)特性，將地址前綴值不以上述值開頭的地址前綴直接用哈希表存儲(chǔ)，由于這類地址很少，因此這類地址產(chǎn)生哈希沖突的概率較低.直接用哈希表存儲(chǔ)，可以減少不必要的存儲(chǔ)器訪問次數(shù)，提升查找效率.算法將通過綜合運(yùn)用上述策略，提高IPv6網(wǎng)絡(luò)中路由查找的效率.

3.2 相關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

算法設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)包括哈希表和多比特樹.

3.2.1 哈希表

算法共管理5種功能不同的哈希表，分別為HT、LFT0、LFT1、LFT2以及LFT3.其中HT用來存儲(chǔ)地址前綴不以20、24、26、28和2a開頭的地址前綴信息，而LFT0、LFT1、LFT2和LFT3用來存儲(chǔ)以20、24、26、28和2a開頭的地址前綴信息.

圖4 HT結(jié)構(gòu)Fig.4 Structure of HT

HT含有的表項(xiàng)數(shù)量有限，目前即使在核心路由器中也僅有數(shù)十項(xiàng)，因此HT的結(jié)構(gòu)比較簡(jiǎn)單，其結(jié)構(gòu)如圖4所示.Prefix用來存儲(chǔ)前綴信息，共64比特，NP為指針，占用16比特.考慮到HT表存儲(chǔ)的信息比較少，發(fā)生哈希沖突的概率較低，因此當(dāng)HT發(fā)生哈希沖突時(shí)，采用開放定址法來處理沖突.

LFT0存儲(chǔ)前綴長(zhǎng)度為48比特的前綴信息，并且存儲(chǔ)前綴長(zhǎng)度大于48且小于64的標(biāo)志位信息.LFT1存儲(chǔ)前綴長(zhǎng)度為32比特的前綴信息，同時(shí)存儲(chǔ)前綴長(zhǎng)度大于32并小于48的標(biāo)志位信息.LFT2存儲(chǔ)前綴長(zhǎng)度為16比特的前綴信息和前綴長(zhǎng)度大于16且小于32的標(biāo)志位信息，LFT3存儲(chǔ)前綴長(zhǎng)度為64比特的前綴信息，結(jié)構(gòu)如圖5所示.

圖5 LFTx結(jié)構(gòu)Fig.5 Structure of LFTx

LFT結(jié)構(gòu)由5部分組成，分別為Prefix、cFlag、nFlag、NP和CP，其中Prefix用來存儲(chǔ)地址前綴信息，在LFT0中占用48比特，在LFT1中占用32比特，在LFT2中占用16比特，LFT3中占用64比特，cFlag占用1比特為沖突標(biāo)志位，nFlag占用1比特為是否有更長(zhǎng)匹配項(xiàng)標(biāo)志位，NP和CP為地址指針，各占16比特.根據(jù)標(biāo)志位的不同，NP和CP的意義和指向也有所不同，如表1所示.

表1 標(biāo)志位與指針關(guān)系Table 1 Relationship between flag and pointer

3.2.2 多比特樹

除了哈希表外，算法還包括3棵6-5-4Trie.

6-5-4Trie屬于多比特樹，但與固定步寬的多比特樹不同的是，6-5-4Trie的步寬不是不變的，因此相對(duì)于固定步寬的多比特樹，6-5-4Trie能夠更有效的利用存儲(chǔ)空間.同時(shí)與可變步寬的多比特樹不同的是，6-5-4Trie在每一層上是固定步寬的，因此在算法的實(shí)現(xiàn)上較為簡(jiǎn)單.

同時(shí)，6-5-4Trie是一顆最高高度為4的多比特樹，其中第一層到第二層的步寬為6，第二層到第三層的步寬為5，第三層到第四層的步寬為4.根據(jù)IPv6地址前綴長(zhǎng)度分布的特點(diǎn)可以知道，地址前綴長(zhǎng)度主要集中在[32，48]的區(qū)間內(nèi)，而在這個(gè)區(qū)間內(nèi)，[33，38]、[39，43]和[43，47]這三個(gè)區(qū)間所包含的地址前綴項(xiàng)在數(shù)量上差不多，因此將步寬設(shè)為6、5和4能夠使多比特樹更加平衡易于優(yōu)化.由于多比特樹的特性，6-5-4Trie同樣需要進(jìn)行前綴擴(kuò)展，分別需要將前綴長(zhǎng)度不足6比特、大于6比特且小于12比特、大于12比特且小于16比特的前綴分別擴(kuò)展至6比特、5比特和4比特.由于6-5-4Trie的高度最多只有4，因此在最壞的情況下，完成查找操作也只需要訪問3次存儲(chǔ)器，極大的提升了查找性能.

3.2.3 哈希函數(shù)設(shè)計(jì)與沖突處理

基于哈希表的路由查找算法的性能，主要由哈希函數(shù)的好壞決定.哈希函數(shù)的沖突是無法避免的，每一個(gè)性能優(yōu)異的路由查找算法，離不開一個(gè)好的哈希函數(shù)，同時(shí)也離不開處理哈希沖突的策略.

根據(jù)IPv6地址前綴分析結(jié)果可知，LFT0與LFT1產(chǎn)生沖突的概率較高，LFT2和LFT3產(chǎn)生沖突的概率較低，因此針對(duì)不同的LFT，算法將采用不同的哈希函數(shù)和處理沖突的策略，如表2所示.

表2 哈希函數(shù)及沖突處理策略Table 2 Hash functions and conflict handling strategy

針對(duì)LFT0、LFT1、LFT2、LFT3、LFT0c和LFT1c，算法設(shè)計(jì)了H48、H32、H16、H64、H48c和H32c五個(gè)哈希函數(shù).其中除了HT的哈希函數(shù)采用MD5以外，其余都采用XOR-Folding的方式來進(jìn)行計(jì)算，各個(gè)哈希函數(shù)的具體設(shè)計(jì)如圖6所示.

3.3 算法實(shí)現(xiàn)

算法流程如圖7所示，查找過程分為哈希表查找階段和6-5-4Trie查找階段.由圖可知，當(dāng)nFlag=0，即存在更長(zhǎng)匹配項(xiàng)時(shí)，需要進(jìn)行6-5-4Trie查找.

3.3.1 哈希表查找

1)當(dāng)IPv6數(shù)據(jù)包到達(dá)后，判斷目的IP地址的前綴是否以20、24、26、28和2a開頭，如果不是則經(jīng)過Hash后與HT進(jìn)行比對(duì)，匹配成功則按照NP指向的下一跳路由信息轉(zhuǎn)發(fā)，若匹配失敗則按照默認(rèn)路由轉(zhuǎn)發(fā).

2)若目的IP地址以20、24、26、28和2a開頭，則根據(jù)數(shù)據(jù)包中目的IP地址的前48比特進(jìn)行哈希計(jì)算后與LFT0表進(jìn)行比對(duì)，若匹配成功，且不存在沖突(cFlag=0)、不存在更長(zhǎng)的匹配項(xiàng)(nFlag=0)，此時(shí)數(shù)據(jù)包通過NP指向的下一跳路由信息進(jìn)行轉(zhuǎn)發(fā)，算法結(jié)束.若匹配成功且不存在沖突、但是存在更長(zhǎng)的匹配項(xiàng)，此時(shí)NP指向T0進(jìn)入下一階段的查找.

3)當(dāng)?shù)诙街邪l(fā)現(xiàn)存在沖突(cFlag=1)，匹配prefix與當(dāng)前的地址前綴信息，若prefix和當(dāng)前的地址前綴信息匹配成功，則此時(shí)仍然按照第二步中流程進(jìn)行處理.如果prefix與當(dāng)前的地址前綴信息不匹配，則進(jìn)入LFT0c表查詢，經(jīng)過哈希后匹配，若匹配成功則轉(zhuǎn)發(fā)，若匹配失敗則進(jìn)入LFT1.

圖7 算法流程圖Fig.7 Flow chart of the algorithm

4)如果第二步中與LFT0匹配失敗，則進(jìn)入LFT1.根據(jù)數(shù)據(jù)包中目的IP地址的前32比特進(jìn)行匹配后與LFT1進(jìn)行比對(duì)，流程和第二步相似.

5)如果匹配到LFT3仍然失敗，則按照默認(rèn)路由轉(zhuǎn)發(fā)數(shù)據(jù)包.

3.3.2 6-5-4Trie的查找

哈希表查找階段中遇到有更長(zhǎng)的匹配項(xiàng)時(shí)，則進(jìn)入第二階段：6-5-4Trie的查找階段.

1)以T0為例，截取目的IP地址的第49到54比特與T0的第一層進(jìn)行匹配，若匹配成功，且該葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)，則根據(jù)葉子節(jié)點(diǎn)中的下一跳路由信息進(jìn)行轉(zhuǎn)發(fā).

2)如果該葉子節(jié)點(diǎn)有葉子節(jié)點(diǎn)，則記錄此時(shí)的下一跳路由信息NHP，將目的IP地址的第55到59比特進(jìn)行匹配，若匹配成功則更新下一跳路由信息NHP，若匹配失敗，則按照NHP轉(zhuǎn)發(fā).

3)如果第二步中匹配成功的節(jié)點(diǎn)仍然有葉子節(jié)點(diǎn)，則記錄該葉子節(jié)點(diǎn)的下一跳路由信息NHP，將目的地址的第60到64比特進(jìn)行匹配，若匹配成功則按照該節(jié)點(diǎn)的下一跳路由信息進(jìn)行轉(zhuǎn)發(fā)，若匹配失敗，則按照NHP轉(zhuǎn)發(fā).

對(duì)于T1、T2,查找方法類似.

4 性能分析

從算法查找速度、路由表更新、轉(zhuǎn)發(fā)表所需存儲(chǔ)空間和哈希沖突解決等方面，對(duì)算法性能進(jìn)行分析.

4.1 查找速度

算法將地址前綴長(zhǎng)度為48比特、32比特、16比特和64比特的路由信息分別存儲(chǔ)在LFT0、LFT1、LFT2和LFT3中，在哈希階段查找過程中，分別需要訪問存儲(chǔ)器1次、2次、3次和4次.在最壞情況下，地址前綴信息在LFT2中未能匹配成功，此時(shí)算法需要進(jìn)入6-5-4Trie進(jìn)行第二階段的查找，共需要訪問存儲(chǔ)器6次，因此算法查找的時(shí)間復(fù)雜度為O(6).如表3所示.根據(jù)IPv6地址前綴分布規(guī)律可知，針對(duì)當(dāng)前的IPv6網(wǎng)絡(luò)，70%的地址可以在算法的第一階段內(nèi)完成查找，其中45%的地址只需要訪問1次存儲(chǔ)器.

表3 前綴長(zhǎng)度與訪問存儲(chǔ)器次數(shù)關(guān)系Table 3 Relationship between prefix length and number of memory access

4.2 路由表更新

IPv6正處于發(fā)展上升階段，其路由表的更新頻率較大，因此路由表的更新對(duì)路由查找算法性能的影響不可忽略.路由更新操作和查找過程類似，對(duì)于當(dāng)前IPv6網(wǎng)絡(luò)，大多數(shù)的更新操作只需要更新相應(yīng)的LFT，對(duì)于地址前綴長(zhǎng)度不是16倍數(shù)的地址前綴，除了需要更新對(duì)應(yīng)的LFT，還需要更新對(duì)應(yīng)的6-5-4Trie，最壞情況下需要訪問存儲(chǔ)器6次，因此路由更新復(fù)雜度為O(6).

4.3 轉(zhuǎn)發(fā)表存儲(chǔ)空間

算法的結(jié)構(gòu)決定了算法所消耗的存儲(chǔ)空間，算法包含哈希表和6-5-4Trie兩種數(shù)據(jù)結(jié)構(gòu)，對(duì)于哈希表結(jié)構(gòu)中每一個(gè)表項(xiàng)所需要的存儲(chǔ)空間如下：

LFT0：包含48比特 Prefix、1比特 cFlag、1比特 nFlag、16比特 NP和16比特 CP，共計(jì)82比特.

LFT1：包含32比特 Prefix、1比特 cFlag、1比特 nFlag、16比特 NP和16比特 CP，共計(jì)66比特.

LFT2：包含16比特 Prefix、1比特 cFlag、1比特 nFlag和16比特 NP，共計(jì)34比特.

LFT3：包含64比特 Prefix、1比特 cFlag、16比特 NP，共計(jì)81比特.

HT：包含64比特 Prefix和16比特 NP，共計(jì)80比特.

LFT0c：包含48比特 Prefix、1比特 nFlag和16比特 NP，共計(jì)65比特.

LFT1c：包含32比特 Prefix、1比特 nFlag和16比特 NP，共計(jì)49比特.

假如將AS6939中地址前綴長(zhǎng)度為16的倍數(shù)的路由前綴信息加入哈希表，則共需要：

1*34bits+8349*66bits+29*49bits+15764*82bits+14*65bits+149*81bits=227KB.

對(duì)于6-5-4Trie結(jié)構(gòu)來說，每個(gè)節(jié)點(diǎn)都包含指針和NHP，因此一顆滿6-5-4Trie共需要：

(26*6bits)+(25*5bits+16bits)*26+(24*4bits+16bits)*25*26+16bits*24*25*26=854KB存儲(chǔ)空間.在實(shí)際使用中，6-5-4Trie的節(jié)點(diǎn)都比較稀疏，因此可以采用壓縮等手段來進(jìn)一步降低存儲(chǔ)空間的消耗.

4.4 哈希沖突

由圖6可知，當(dāng)LFT0和LFT1發(fā)生沖突時(shí)，LFT0c和LFT1c才會(huì)存在.AS6939是當(dāng)前互聯(lián)網(wǎng)中包含IPv6路由信息最多的自治系統(tǒng)，其包含前綴長(zhǎng)度為16、32、48和64的路由前綴共計(jì)24306個(gè).將這些地址前綴信息經(jīng)過哈希函數(shù)處理后，LFT0c和LFT1c共含有43個(gè)表項(xiàng)，即將24306個(gè)表項(xiàng)存入LFT時(shí)，共計(jì)發(fā)生沖突43次，針對(duì)這43個(gè)表項(xiàng)，除了在哈希查找階段需要訪問LFT表以外，還需要訪問一次相應(yīng)的用來解決沖突的表.發(fā)生沖突的概率為0.17%，所以哈希函數(shù)性能優(yōu)異.

5 實(shí)驗(yàn)仿真

本文收集了含有IPv6路由信息的AS174、AS3356和AS6939三個(gè)自治系統(tǒng)中路由表進(jìn)行了統(tǒng)計(jì)，表4給出了它們的前綴長(zhǎng)度分布情況.

表4 地址前綴長(zhǎng)度分布Table 4 Prefix length distribution

為了說明算法的效率，同時(shí)避免由于計(jì)算機(jī)性能差異、程序之間相互影響等因素而導(dǎo)致的誤差，依據(jù)表4 的數(shù)據(jù)，對(duì)算法的哈希函數(shù)、查找速度、存儲(chǔ)空間三個(gè)方面進(jìn)行實(shí)驗(yàn)仿真，算法均采用Python實(shí)現(xiàn).

5.1 哈希函數(shù)性能

首先是對(duì)提出的哈希函數(shù)進(jìn)行測(cè)試，將AS6939、AS174和A3356分別建立數(shù)據(jù)結(jié)構(gòu)，實(shí)驗(yàn)結(jié)果如表5所示.

表5 哈希沖突次數(shù)Table 5 Number of hash collisions

通過實(shí)驗(yàn)仿真結(jié)果可以知道，哈希沖突的概率都在0.2%以內(nèi)，結(jié)合提出的哈希沖突處理策略，LFT能夠有效的存儲(chǔ)地址前綴信息.

5.2 查找性能

在查找性能測(cè)試上，實(shí)驗(yàn)結(jié)果以算法對(duì)存儲(chǔ)器的讀取次數(shù)進(jìn)行統(tǒng)計(jì)，實(shí)驗(yàn)結(jié)果如圖8所示.

AS174、AS3356和AS6939雖然來自不同的自治系統(tǒng)，但是它們有著相似的地址前綴分布規(guī)律.相比Compressed Trie，本算法具有較大的優(yōu)勢(shì).與同樣采用了哈希表和Trie結(jié)構(gòu)的文獻(xiàn)[16]中的算法相比[16]，本算法擁有更好的查找效率.

圖8 查找性能實(shí)驗(yàn)結(jié)果Fig.8 Results of lookup speed

5.3 存儲(chǔ)空間

在存儲(chǔ)空間上，實(shí)驗(yàn)結(jié)果如圖9所示.

圖9 存儲(chǔ)空間實(shí)驗(yàn)結(jié)果Fig.9 Results of storage space

文獻(xiàn)[16]中的算法為地址前綴長(zhǎng)度為32的表項(xiàng)進(jìn)行優(yōu)化，使其為前綴長(zhǎng)度為32的表項(xiàng)節(jié)省更多的存儲(chǔ)空間，而本算法根據(jù)地址前綴長(zhǎng)度為48的表項(xiàng)進(jìn)行優(yōu)化，使其為前綴長(zhǎng)度為48的表項(xiàng)節(jié)省更多的存儲(chǔ)空間.由IPv6地址前綴分布規(guī)律可知，隨著IPv6網(wǎng)絡(luò)逐漸成熟，地址前綴長(zhǎng)度為48的表項(xiàng)的數(shù)量，將在路由表中長(zhǎng)期處于領(lǐng)先地位，因此隨著路由表項(xiàng)的增多，本算法在存儲(chǔ)空間的消耗上將比文獻(xiàn)[16]中的算法更少.

此外，算法使用多比特樹降低樹的高度，同時(shí)由于地址前綴長(zhǎng)度擴(kuò)展機(jī)制的存在，從而產(chǎn)生了大量的節(jié)點(diǎn)，因此在表項(xiàng)較少的情況下，其消耗的空間要比文獻(xiàn)[16]中算法消耗的多，隨著路由表項(xiàng)的增多，本算法中產(chǎn)生的這些節(jié)點(diǎn)，逐漸變?yōu)榇嬗械刂非熬Y信息和下一跳路由信息的節(jié)點(diǎn)，此時(shí)算法對(duì)存儲(chǔ)空間的消耗是幾乎不變的.因此，由圖9可知，隨著路由表項(xiàng)的增大，本算法在存儲(chǔ)空間上的優(yōu)勢(shì)越來越明顯.此外，由于6-5-4Trie比較稀疏，因此在存儲(chǔ)空間的消耗上仍有優(yōu)化空間.

從上述實(shí)驗(yàn)仿真結(jié)果來看，算法在哈希函數(shù)沖突避免、查找性能上和存儲(chǔ)空間上都有優(yōu)勢(shì)，各項(xiàng)性能指標(biāo)良好.

6 結(jié) 論

算法將哈希表與多比特樹，分階段進(jìn)行結(jié)合，并在設(shè)計(jì)時(shí)充分將IPv6地址前綴長(zhǎng)度的分布特點(diǎn)考慮在內(nèi)，首先將極少使用的地址前綴和常用的地址前綴分開存儲(chǔ)，其次針對(duì)常用的地址前綴，算法將前綴長(zhǎng)度為48的表項(xiàng)優(yōu)先匹配.算法在大多數(shù)情況下，只需要進(jìn)行一次存儲(chǔ)器訪問，就可以查找到下一跳路由信息，即使在最壞情況下也只需要訪問6次存儲(chǔ)器.同時(shí)算法的更新復(fù)雜度與查找復(fù)雜度同為O(6)，能夠適應(yīng)當(dāng)前IPv6路由更新頻繁的情況.算法消耗的存儲(chǔ)空間較少，結(jié)合算法結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，易于用硬件實(shí)現(xiàn).

：

[1] Tang Hui，Lin Tao，F(xiàn)an Dian，et al.Conducting pst IP rsearch，dveloping iternet′s nxt gneration [J].Bulletin of Chinese Academy of Sciences，2010，25(1)：55-63.

[2] Zhang Ze-xin，Li Jun，Chang Xiang-qing.Longitudinal study on evolution of Internet traffic[J].Application Research of Computers，2015，32(11)：3215-3221.

[3] Wang Rui-qing，Du Hui-min，Wang Ya-gang.IPv6 routing lookup algorithm based on hash and CAM[J].Computer Engineering，2012，38(8)：50-53.

[4] Tang Ming-dong，Zhang Guo-qing，Yang Jing，et al.Scalable routing for the Internet [J].Journal of Software，2010，21(10)：2524-2541.

[5] Xu Ke，Xu Ming-wei，Wu Jian-ping，et al.Survey on routing lookup algorithms[J].Journal of Software，2002，13(1)：42-50.

[6] Bando M，Lin Y L，Chao H J.Flash trie：beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie[J].IEEE/ACM Transactions on Networking，2012，20(4)：1262-1275.

[7] Lin C H，Hsu C Y，Hsieh S Y.A multi-index hybrid trie for lookup and updates[J].IEEE Transactions on Parallel & Distributed Systems，2014，25(10)：2486-2498.

[8] Pao D，Lu Z，Poon Y H.IP address lookup using bit-shuffled trie[J].Computer Communications，2014，47(2)：51-64.

[9] Huang Sheng，Zhang Wei，Wu Chuan-chuan，et al.IP address lookup algorithm based on multi-bit priority tries tree [J].Journal of Computer Applications，2014，34(3)：615-618.

[10] Hsiao Y M，Chu Y S，Lee J F，et al.A high-throughput and high-capacity IPv6 routing lookup system[J].Computer Networks，2013，57(3)：782-794.

[11] Xu Pan，Liu Sheng-li，Lan Jing-hong，et al.An improved segment hash algorithm[J].Computer Engineering，2015，41(1)：266-269.

[12] Li Yuan，Ruan Jun-zhou.Research on router lookup algorithm based on hash and radix tree [J].Computer & Network，2015，41(11)：42-44.

[13] Eatherton W，Varghese G，Dittia Z.Tree bitmap：hardware/software IP lookups with incremental updates[J].Acm Sigcomm Computer Communication Review，2015，34(2)：97-122.

[14] Sun Y，Egi N，Shi G，et al.Content-based route lookup using CAMs[C].Global Communications Conference，2012：2677-2682.

[15] Meiners C R，Patel J，Norige E，et al.Fast regular expression matching using small TCAM[J].IEEE/ACM Transactions on Networking，2014，22(1)：94-109.

[16] Gao Ying，Wang He-ming，Chen Qiang.IPv6 routing lookup algorithm based on hierarchical Hash[J].Computer Engineering and Design，2010，31(22)：4790-4793.

附中文參考文獻(xiàn)：

[1] 唐 暉，林 濤，范 典，等.開展后IP技術(shù)研究發(fā)展互聯(lián)網(wǎng)下一代[J].中國(guó)科學(xué)院院刊，2010，25(1)：55-63.

[2] 張澤鑫，李 俊，常向青.互聯(lián)網(wǎng)流量的演化研究[J].計(jì)算機(jī)應(yīng)用研究，2015，32(11)：3215-3221.

[3] 王瑞青，杜慧敏，王亞剛.基于Hash和CAM的IPv6路由查找算法[J].計(jì)算機(jī)工程，2012，38(8)：50-53.

[4] 唐明董，張國(guó)清，楊 景，等.互聯(lián)網(wǎng)可擴(kuò)展路由[J].軟件學(xué)報(bào)，2010，21(10)：2524-2541.

[5] 徐 恪，徐明偉，吳建平，等.路由查找算法研究綜述[J].軟件學(xué)報(bào)，2002，13(1)：42-50.

[9] 黃 勝，張 衛(wèi)，吳川川，等.基于多分支優(yōu)先級(jí)樹的IP路由查找算法[J].計(jì)算機(jī)應(yīng)用，2014，34(3)：615-618.

[11] 胥 攀，劉勝利，蘭景宏，等.一種改進(jìn)的分段哈希算法[J].計(jì)算機(jī)工程，2015，41(1)：266-269.

[12] 李 淵，阮軍洲.基于Hash和Radix樹的路由查找算法研究[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2015，41(11)：42-44.

[16] 高 瑩，王賀明，陳 強(qiáng).采用分段哈希方法的IPv6路由查找算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(22)：4790-4793.