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

(揚(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地址長度達(dá)到了128比特，這個改變一勞永逸的解決了IPv4地址空間耗盡的問題.但是IPv6較長的地址長度，增加了最長前綴匹配的難度和復(fù)雜度，雖然現(xiàn)有許多基于IPv4的快速路由查找算法，但是這些路由查找算法很難移植到IPv6中去，或者移植之后性能低下，實(shí)用性較低.因此需要設(shè)計(jì)一種適用于IPv6的路由查找算法，推動IPv6的普及.本文的主要內(nèi)容是提出一種適合在IPv6網(wǎng)絡(luò)中的高速路由查找算法.

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

最長地址前綴匹配問題，是路由查找算法中最需要解決的問題，也是目前研究最多的部分.最長地址前綴匹配算法研究方向大致分為基于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次存儲器訪問，性能較低.隨后又有學(xué)者在二進(jìn)制Trie樹上進(jìn)行改進(jìn)，提出壓縮、多bit等改進(jìn)算法[6-9].

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

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

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

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

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

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

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

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

根據(jù)上述IPv6地址前綴分布特點(diǎn)可知，在IPv6網(wǎng)絡(luò)中，路由表中目前前綴長度為16倍數(shù)的路由表項(xiàng)最多，在這些表項(xiàng)中，前綴長度為48的表項(xiàng)最多，其次是前綴長度為32的表項(xiàng).因此，如果算法在設(shè)計(jì)時考慮從48比特切入，優(yōu)先查找48比特的表項(xiàng)，使路由查找操作在大部分情況下只需要訪問一次存儲器.同時與IPv4不同的是，IPv6的前綴值分布具有很明顯的特點(diǎn)，即以20、24、26、28和2a開頭的地址前綴占絕大部分.算法根據(jù)這個特性，將地址前綴值不以上述值開頭的地址前綴直接用哈希表存儲，由于這類地址很少，因此這類地址產(chǎn)生哈希沖突的概率較低.直接用哈希表存儲，可以減少不必要的存儲器訪問次數(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用來存儲地址前綴不以20、24、26、28和2a開頭的地址前綴信息，而LFT0、LFT1、LFT2和LFT3用來存儲以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é)構(gòu)如圖4所示.Prefix用來存儲前綴信息，共64比特，NP為指針，占用16比特.考慮到HT表存儲的信息比較少，發(fā)生哈希沖突的概率較低，因此當(dāng)HT發(fā)生哈希沖突時，采用開放定址法來處理沖突.

LFT0存儲前綴長度為48比特的前綴信息，并且存儲前綴長度大于48且小于64的標(biāo)志位信息.LFT1存儲前綴長度為32比特的前綴信息，同時存儲前綴長度大于32并小于48的標(biāo)志位信息.LFT2存儲前綴長度為16比特的前綴信息和前綴長度大于16且小于32的標(biāo)志位信息，LFT3存儲前綴長度為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用來存儲地址前綴信息，在LFT0中占用48比特，在LFT1中占用32比特，在LFT2中占用16比特，LFT3中占用64比特，cFlag占用1比特為沖突標(biāo)志位，nFlag占用1比特為是否有更長匹配項(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的步寬不是不變的，因此相對于固定步寬的多比特樹，6-5-4Trie能夠更有效的利用存儲空間.同時與可變步寬的多比特樹不同的是，6-5-4Trie在每一層上是固定步寬的，因此在算法的實(shí)現(xiàn)上較為簡單.

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

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

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

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

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

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

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

算法流程如圖7所示，查找過程分為哈希表查找階段和6-5-4Trie查找階段.由圖可知，當(dāng)nFlag=0，即存在更長匹配項(xiàng)時，需要進(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)行比對，匹配成功則按照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)行比對，若匹配成功，且不存在沖突(cFlag=0)、不存在更長的匹配項(xiàng)(nFlag=0)，此時數(shù)據(jù)包通過NP指向的下一跳路由信息進(jìn)行轉(zhuǎn)發(fā)，算法結(jié)束.若匹配成功且不存在沖突、但是存在更長的匹配項(xiàng)，此時NP指向T0進(jìn)入下一階段的查找.

3)當(dāng)?shù)诙街邪l(fā)現(xiàn)存在沖突(cFlag=1)，匹配prefix與當(dāng)前的地址前綴信息，若prefix和當(dāng)前的地址前綴信息匹配成功，則此時仍然按照第二步中流程進(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)行比對，流程和第二步相似.

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

3.3.2 6-5-4Trie的查找

哈希表查找階段中遇到有更長的匹配項(xiàng)時，則進(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)，則記錄此時的下一跳路由信息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ā).

對于T1、T2,查找方法類似.

4 性能分析

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

4.1 查找速度

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

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

4.2 路由表更新

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

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

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

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中地址前綴長度為16的倍數(shù)的路由前綴信息加入哈希表，則共需要：

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

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

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

4.4 哈希沖突

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

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

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

表4 地址前綴長度分布Table 4 Prefix length distribution

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

5.1 哈希函數(shù)性能

首先是對提出的哈希函數(shù)進(jìn)行測試，將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能夠有效的存儲地址前綴信息.

5.2 查找性能

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

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

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

5.3 存儲空間

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

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

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

此外，算法使用多比特樹降低樹的高度，同時由于地址前綴長度擴(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)，此時算法對存儲空間的消耗是幾乎不變的.因此，由圖9可知，隨著路由表項(xiàng)的增大，本算法在存儲空間上的優(yōu)勢越來越明顯.此外，由于6-5-4Trie比較稀疏，因此在存儲空間的消耗上仍有優(yōu)化空間.

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

6 結(jié) 論

算法將哈希表與多比特樹，分階段進(jìn)行結(jié)合，并在設(shè)計(jì)時充分將IPv6地址前綴長度的分布特點(diǎn)考慮在內(nèi)，首先將極少使用的地址前綴和常用的地址前綴分開存儲，其次針對常用的地址前綴，算法將前綴長度為48的表項(xiàng)優(yōu)先匹配.算法在大多數(shù)情況下，只需要進(jìn)行一次存儲器訪問，就可以查找到下一跳路由信息，即使在最壞情況下也只需要訪問6次存儲器.同時算法的更新復(fù)雜度與查找復(fù)雜度同為O(6)，能夠適應(yīng)當(dāng)前IPv6路由更新頻繁的情況.算法消耗的存儲空間較少，結(jié)合算法結(jié)構(gòu)簡單的特點(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].中國科學(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] 唐明董，張國清，楊 景，等.互聯(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)先級樹的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.