劉陽

濱州學(xué)院信息工程系,山東濱州256603

?

基于三級索引和Trie的IPv6路由查找算法研究

劉陽

濱州學(xué)院信息工程系,山東濱州256603

摘要:Internet的迅速發(fā)展使得骨干網(wǎng)核心路由器轉(zhuǎn)發(fā)分組的數(shù)量呈指數(shù)級增長，快速的IP路由查找算法是實現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵。IPv6的應(yīng)用，使得路由查找算法要適應(yīng)IPv6地址的特點。本文分析了典型的基于Trie的路由查找算法，總結(jié)各種算法的優(yōu)缺點。結(jié)合IPv6地址特征和骨干路由器路由表地址前綴的分布規(guī)律，提出了一種基于三級索引表和多比特Trie的快速IPv6路由查找算法。與其他同類算法相比較，該算法易于實現(xiàn)，并且具有較快的查找和更新速度，較低的存儲空間。

關(guān)鍵詞:索引表;多比特Trie;路由查找; IPv6

Internet的迅猛發(fā)展，使其鏈路速度、帶寬、流量等呈指數(shù)級增長[1]，骨干網(wǎng)絡(luò)核心路由器的接口速率也隨之迅速提高。快速的IP地址路由查找算法是實現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵[2]，IP路由查找操作已經(jīng)成為當(dāng)前路由器轉(zhuǎn)發(fā)性能的瓶頸之一[3]?；ヂ?lián)網(wǎng)下一代IP協(xié)議使用地址長度為128位的IPv6地址，隨著無分類域間路由(Classless Inter Domain Routing，CIDR)的引入，IP地址查找采用最長前綴匹配(Longest Prefix Match，LPM)算法，更加增加了IPv6路由查找的復(fù)雜性[4-6]。如果簡單的套用原有的用于IPv4路由查找算法，將會導(dǎo)致讀取存儲器的次數(shù)和占用的存儲空間急劇增加，性能急劇下降[7]，因此，要得到較好的路由必須使算法更適用于IPv6的結(jié)構(gòu)[8]，尋找一種適用于IPv6的路由查找方法顯得十分重要。

為了提高路由查找和更新的速度，路由表一般采用一定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲，查找和更新算法不僅要有較快的速度，同時在所需存儲空間方面有比較好的性能。基于Trie的算法是常用的路由查找算法，它不僅結(jié)構(gòu)簡單，而且在時間復(fù)雜度和空間復(fù)雜度等方面均能滿足不斷提高的路由器性能要求。因此，很多現(xiàn)代的路由算法都是在此基礎(chǔ)上進(jìn)行優(yōu)化和改進(jìn)。本文分析基于Trie的路由查找算法的優(yōu)缺點，根據(jù)骨干網(wǎng)絡(luò)核心路由表中地址前綴的分布規(guī)律，提出一種快速IPv6路由查找算法，該算法采用索引表和多比特Trie兩種數(shù)據(jù)結(jié)構(gòu)。從性能上來看，該算法易于實現(xiàn)，并且具有較快的查找和更新速度，較低的存儲空間。

1　典型的Trie樹路由查找算法

1.1二進(jìn)制Trie樹

Trie樹是表示地址前綴的常用方法，是一種被廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)[7]。二進(jìn)制Trie樹是一棵二叉樹，樹中每個節(jié)點（除葉子節(jié)點以外）只有兩個分支，每個節(jié)點代表一個地址前綴，而Trie樹中的部分節(jié)點保存著地址前綴信息。例如，某路由器的部分路由表如表1所示。表中*是通配符，下一跳地址為a、b、c、d、e的表項的地址前綴分別為00，0001，010111，01，1000。

根據(jù)表1的路由前綴信息，可以構(gòu)造一棵二進(jìn)制Trie樹。其結(jié)構(gòu)見圖1。

表1　路由表Table1 Routing table

圖1　二進(jìn)制TrieFig.1Binary Trie tree

從圖1可以看出，處于第L層的節(jié)點代表一類地址前綴L比特均相同的地址空間。例如，c節(jié)點代表地址前綴前4比特為1000的一類地址空間。在查找的過程中，有可能出現(xiàn)多個前綴同時匹配的情況。例如，若到來的分組的地址前綴為0001，根據(jù)圖1，可以看出(a,b)均能夠匹配，這時按照最長前綴匹配原則，b節(jié)點為最后查找結(jié)果。在查找過程中要記錄當(dāng)前最匹配的路由前綴，一直到葉子節(jié)點或者節(jié)點沒有合適的分支為止。用二叉Trie樹組織路由轉(zhuǎn)發(fā)表，結(jié)構(gòu)比較簡單，易于實現(xiàn)[9]。但訪存次數(shù)與地址前綴長度相同，若地址前綴長度為w，則此算法的時間復(fù)雜度為O(w)[10]。對于圖1的二進(jìn)制Trie樹，此算法的時間復(fù)雜度為O(6)。若用于IPV6路由查找，在最壞的情況下，樹的深度為128，需要訪問128次存儲器，時間復(fù)雜度為O(128)。

1.2多比特Trie樹

在基本的二進(jìn)制Trie樹中，每次讀取一個比特信息，步長為1。多比特Trie樹選擇一次讀取多個比特，若樹的深度為L，則多比特Trie樹的時間復(fù)雜度為O(L)。因此，路由查找的時間復(fù)雜度大大降低。根據(jù)表1的前綴信息，可以構(gòu)造一棵步長為2的多比特Trie樹（見圖2），此時，算法的時間復(fù)雜度為O(3)。IPv6路由查找時，在最壞的情況下，步長可以設(shè)置為128，只需要一次訪問存儲器的操作，其時間復(fù)雜度為O(1)，但它卻是以犧牲存儲器空間為代價的，需要2128個表項的存儲空間。步長選擇是多比特Trie樹進(jìn)行路由查找必須解決的問題之一[10]。

圖2　多比特Trie樹Fig.2 Multi-bit Trie tree

1.3其他基于Trie樹的路由算法

文獻(xiàn)[11]提出了層次壓縮樹(Level Compressed Trie，簡稱LC-trie)的概念，該算法首先對二進(jìn)制Trie樹的稀疏部分進(jìn)行路徑壓縮，然后將壓縮后Trie樹的稠密部分轉(zhuǎn)換為多比特Trie樹。以此達(dá)到減少訪存次數(shù)和節(jié)約存儲空間的效果，但是對前綴的更新支持不是很好。文獻(xiàn)[12]提出了以32 bits為查找路由前綴起點的分段哈希表和多比特Trie樹相結(jié)合的IPv6路由查找算法，該算法與單純多比特樹查找算法相比，在一定程度上提高了查找效率，但需要構(gòu)造一個完備哈希函數(shù)來解決沖突問題。本算法采用三級索引表和多比特Trie樹，無論在查找效率和消耗存儲空間上，都具有很好的性能。

2　算法設(shè)計

2.1IPv6路由前綴分布規(guī)律

128位的IPv6地址空間被劃分為兩大部分[13]。其中，高64 bits表示網(wǎng)絡(luò)前綴，低64 bits表示后綴，即主機(jī)。根據(jù)RFC3587中規(guī)定的全球單播地址的標(biāo)識長度為高64 bits，不用于子網(wǎng)間的路由。因此，IPv6單播地址的地址前綴長度不會小于64 bits，而是介于65~128 bits之間，并且只可能有長度為128 bits的前綴。而按照IPv6單播地址的分配策略，不存在長度小于16 bits的網(wǎng)絡(luò)前綴。就單播IPv6而言，以6 Bone，6 Net等幾個IPv6骨干實驗網(wǎng)絡(luò)的數(shù)據(jù)來看，其前綴長度主要介于19~64 bits，核心路由器關(guān)心的是目標(biāo)地址的高64 bits[14]。從骨干自治域AS2、AS1221、AS6447等的路由表來看，路由前綴分布存在一定規(guī)律，不存在長度小于16 bits的前綴[12]，而前綴長度為32 bits的最多，前綴長度為48 bits的位居其次，這兩部分占全部路由表的4/5以上[15]，不存在前綴長度介于64~128 bits之間的前綴，而長度為128 bits的前綴僅有幾個，這也符合IPv6的地址分配策略。

2.2算法的數(shù)據(jù)結(jié)構(gòu)

依據(jù)IPv6路由前綴分布規(guī)律，本算法采用三張索引表和三棵多比特Trie樹來實現(xiàn)。算法將128 bits的IPv6地址空間劃分成五段，分別為16 bits，32 bits、48 bits，64 bits和128 bits，地址前綴長度為16 bits和32 bits、48 bits和64 bits、128 bits信息分別存放在三張索引表中：H_Tab1、H_Tab2、H_Tab3；而前綴長度介于16~32 bits、32~48 bits、48~64 bits的信息存放在3棵多比特Trie樹Trie_1、Trie_2、Trie_3中。為了有效利用和節(jié)約存儲空間，三張索引表采用不同的數(shù)據(jù)結(jié)構(gòu)。

2.2.1索引表的數(shù)據(jù)結(jié)構(gòu)索引表H_Tab1與H_Tab2采用相同的數(shù)據(jù)結(jié)構(gòu)，包含五個字段：IP_Pre字段、2個標(biāo)志位MP_1和MP_2字段，F(xiàn)ill_Len字段和NHP_Add字段。IP_Pre字段用于存放0~31 bits 或32~63 bits地址前綴，當(dāng)路由表中前綴長度不足32 bits時，需要用連續(xù)的1進(jìn)行填充，使其填充后滿足32 bits；MP_1用來標(biāo)志是否存在比32 bits或64 bits更長的前綴，占1 bit，當(dāng)MP_1=1時，表示存在比32 bits或64 bits更長的前綴，反之則表示沒有；MP_2用來標(biāo)志是否存在比16 bits或48 bits更長前綴，占1 bit，當(dāng)MP_2=1時，表示存在比16 bits或48 bits更長的前綴，反之則表示沒有；Fill_Len表示當(dāng)前綴長度大于16 bits但小于32 bits或者當(dāng)前綴長度大于32 bits但小于48 bits時，需要進(jìn)行填充的比特數(shù)，占3個比特，取值范圍為000-111；NHP_Add存放轉(zhuǎn)發(fā)接口或下一跳地址、Trie樹或者下一級索引表的地址。索引表H_Tab1和H_Tab2的數(shù)據(jù)結(jié)構(gòu)見圖3。

圖3　H_Tab1和H_Tab2的數(shù)據(jù)結(jié)構(gòu)Fig.3 Data structure of H_Tab1 and H_Tab2

H_Tab1和H_Tab2中MP_1、MP_2標(biāo)志位和Fill_Len有幾種有效的組合，每種不同的組合，NHP_Add的表示含義也有所不同。在數(shù)據(jù)存儲完畢之后，需要對該表按照Fill_Len進(jìn)行升序排序，以提高查找效率。以索引表H_Tab1為例說明幾種組合的含義。其中：

①MP_1=0，MP_2=1，F(xiàn)ill_Len=000時，說明不存在比32 bits更長的前綴，前綴長度正好是32 bits，NHP_Add用來表示轉(zhuǎn)發(fā)接口地址或者下一跳地址；

②MP_1=1，MP_2=1，F(xiàn)ill_Len=000時，說明存在比32 bits更長的前綴，NHP_Add用來表示H_Tab2索引表的地址；

③MP_1=0，MP_2=0，F(xiàn)ill_Len=000時，說明前綴長度正好為16 bits，NHP_Add用來表示轉(zhuǎn)發(fā)接口地址或者下一跳地址；

④MP_1=0，MP_2=1，F(xiàn)ill_Len=m（8>m>0）時，說明在原有前綴后填充了mbits，即前綴長度介于16~32 bits之間，NHP_Add用來表示多比特樹Trie 1的地址；

⑤其他情況為無效情況。

因為不存在長度介于64~128 bits之間的前綴，只存在長度為128 bits的前綴，為了節(jié)約存儲空間，H_Tab3表的結(jié)構(gòu)與H_Tab1相比減少了三個字段，只有IP_Pre和NHP_Add兩個字段，其含義與H_Tab1表相同。

2.2.2多比特Trie樹的數(shù)據(jù)結(jié)構(gòu)多比特樹用來查找長度介于16~32 bits之間、32~48 bits之間和48~64 bits之間的地址前綴。為了降低算法的復(fù)雜性，本算法采用步長為3的固定步長多比特多比特樹，由于基于Trie樹的查找最多只涉及15 bits，因此，最多就只需要5次訪問內(nèi)存。例如，若a、b、c代表三個地址前綴，長度在32~48 bits之間，其地址前綴的前32 bits已經(jīng)存儲在H_Tab1表中，而其后的比特串分別為100*，101001*，10100101*，由它們構(gòu)成的多比特Trie樹見圖4，其數(shù)據(jù)結(jié)構(gòu)見圖5。

其中，Next_Node指針指向該節(jié)點的下一層節(jié)點，當(dāng)w=3時，下一層節(jié)點總數(shù)為23個，共需要23個指針；Next_Add指針指向轉(zhuǎn)發(fā)接口或者下一跳地址。存儲多比特樹需要占用較多的存儲空間，但由于本算法采用固定步長的比特樹，因此結(jié)構(gòu)相對簡單，易于實現(xiàn)。目前存儲器價格低廉，所消耗的存儲空間也是可以接受的。

圖4　多比特Trie樹Fig.4 Multi-bit Trie tree

圖5　多比特Trie樹數(shù)據(jù)結(jié)構(gòu)Fig.5 Data structure of multi-bit Trie tree

2.2.3整體數(shù)據(jù)架構(gòu)在三張索引表中，IP_Pre用來記錄地址前綴信息，NHP_Add用來存儲下一跳或轉(zhuǎn)發(fā)接口的地址。當(dāng)目標(biāo)IP地址的前綴為16 bits或32 bits時，只需要查找H_Tab1表；當(dāng)前綴為48 bits或64 bits時，在查找H_Tab1表之后，按照NHP_Add中指向的地址繼續(xù)查找H_Tab2表；如果前綴為128 bits時，在查找H_Tab1、H_Tab2后，要繼續(xù)查找H_Tab3。而當(dāng)前綴長度介于16~32 bits之間時，在查找H_Tab1表之后，要按照NHP_Add中指向的地址繼續(xù)查找Trie_1；當(dāng)前綴長度介于32~48 bits之間時，在查找H_Tab2表之后，要按照NHP_Add中指向的地址繼續(xù)查找Trie_2；當(dāng)前綴長度介于48~64 bits之間時，在查找H_Tab2表之后，要按照NHP_Add中指向的地址繼續(xù)查找Trie_3。根據(jù)如上描述，算法的整體的數(shù)據(jù)架構(gòu)見圖6。

圖6　算法整體數(shù)據(jù)架構(gòu)Fig.6 Data workup of the algorithm

3　算法流程與性能分析

3.1算法流程

H_Tab1和H_Tab2表在存儲時，以Fill_Len字段為主關(guān)鍵字、MP_1字段為次關(guān)鍵字進(jìn)行升序排序。這樣排序后，可以保證表中的表項是按照地址前綴長度為32 bits或64 bits、大于32 bits或64bits、等于16 bits或48 bits、介于16~32 bits或者介于48 bits和64 bits的順序進(jìn)行排序。以表H_Tab1為例來說明這樣做的目的：前面分析過，IPv6路由表中，前綴長度為32 bits和48 bits的表項占總路由表的4/5，因此，這樣做可以保證絕大多數(shù)的地址前綴長度為32 bits的IP地址可以一次命中，從而盡最大可能減少訪存次數(shù)。以查找H_Tab1為例，說明路由查找的過程，其查找詳細(xì)流程見圖7。

圖7　查找H_Tab1流程圖Fig.7 Flow chart of looking for H_Tab1

3.2算法的性能分析

從時間復(fù)雜度和所用的存儲空間兩個方面來分析算法的性能。3.2.1時間復(fù)雜度當(dāng)一個IP數(shù)據(jù)包到來時，提取目的IP地址，然后查找路由表來轉(zhuǎn)發(fā)分組。如果的路由前綴長度為16 bits、32 bits、48 bits、64 bits和128 bits，只需查找各級索引表，則分別需要1次、1次、2次、2次、3次訪問存儲器。除了以上幾種情況，每次查找除了要訪問索引表之外，還需要加上訪問多比特樹的訪存次數(shù)?？紤]最壞的情況，各種情況的訪存次數(shù)如表2所示。

表2　路由查找訪存次數(shù)Table 2 Times of memory access of routing lookup

從表2可以看出，最壞情況下，當(dāng)前綴長度介于48~64 bits之間時，在查找H_Tab1、H_Tab2兩張索引表后，還要訪問一棵多比特樹，訪存次數(shù)共計7次，總的時間復(fù)雜度為O(7)。由于IPv6路由表中32 bits和48 bits的前綴占總路由表的4/5以上，如果分組按照這個比例到達(dá)路由器，那么大多數(shù)情況下的查找復(fù)雜度為O(1)或O(2)，即只需一次或兩次內(nèi)存訪問就可查到路由信息。路由更新過程類似于路由查找過程，算法復(fù)雜度也為O(7)。

3.2.2所需存儲空間算法所需要的存儲空間主要用來存放索引表、多比特Trie樹。三張索引表所需的存儲空間分別為：H_Tab1表有5個字段，長度共53 bits；H_Tab2表有5個字段，長度共53 bits；H_Tab3表有2個字段，長度共80 bits。最壞情況下，一個地址前綴長度為128的路由表項，則需要186bits的存儲空間，而相同情況下，文獻(xiàn)[12]算法則需要270 bits的存儲空間。多比特樹步長為3，深度為5，每個多比特分支共有23個指針，，一顆滿8分支樹最多存在86-2個節(jié)點，每個節(jié)點需要存儲24個指針和其他字段信息，多比特樹所需要的存儲空間約4 MB，與文獻(xiàn)[12]算法相當(dāng)。而實際上，由于多比特樹存儲的路由屬于稀疏分布，多比特樹可以采用可變步長，也可以采用層次壓縮技術(shù)，也可以采用文獻(xiàn)[16]所提到的多比特樹優(yōu)化算法，以節(jié)約存儲空間。

表3　不同算法時間復(fù)雜度的比較Table 3 Comparison of time complexity of the different algorithms

4　結(jié)論

（1）采用三級索引表，將128 bits的IPv6地址空間分成了3部分。當(dāng)路由前綴長度為16 bits、32 bits、48 bits、64 bits和128 bits時，通過查找各級索引表，分別需要1次、1次、2次、2次、3次訪問存儲器。前綴長度為32 bits和48 bits的路由表項占路由表的4/5，因此，絕大多數(shù)情況下，只需要1次或2次即可完成查找。

（2）采用固定步長為3 bits的多比特Trie樹，用來查找長度介于16~32 bits之間、32~48 bits之間和48~64 bits之間的地址前綴。多比特Trie樹最多只涉及15 bits，樹的深度為5，時間復(fù)雜度為O(5)。而更新過程與查找過程相同，因此，更新速度與查找速度相同。

（3）從路由查找速度和更新速度來看，該算法訪問存儲器的次數(shù)遠(yuǎn)低于二進(jìn)制Trie樹和單純采用多比特Trie樹的路由查找算法，優(yōu)于文獻(xiàn)12中所提到的基于哈希表和多比特Trie的算法；從算法所使用的存儲空間來看，該算法所使用的存儲空間也低于文獻(xiàn)12算法所需的存儲空間。

（4）提出的基于三級索引表和Trie的IPv6查找算法在保持低存儲空間的基礎(chǔ)上，提高了查找和更新路由表的效率，但由于路由表存儲時要對路由表進(jìn)行排序處理，在一定程度上增加了算法的時間復(fù)雜度。今后的研究將開展為該算法選擇或設(shè)計一個適合的排序算法，與本研究的查找算法相結(jié)合，提供更完善的IPv6路由查找方案。

參考文獻(xiàn)

[1] Roberts LG. Beyond Moore’s Law: Internet growth trends[J]. IEEE Computer-Internet Watch, 2000,33(1):1172-119

[2]郭文文.基于Trie的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)[D].南京:南京郵電學(xué)院,2011:1-2

[3]譚明鋒,高蕾,龔正虎.IP路由查找算法研究概述[J].計算機(jī)工程與科學(xué),2006,28(6):87-91

[4]楊玉梅,黎仁國.基于二分查找和Trie的IPv6路由查找算法[J].蘭州理工大學(xué)學(xué)報,2012,38(4):98-102

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

[6]王亞剛,杜慧敏,楊康平.使用Hash表和樹位圖的兩級IPv6地址查找算法[J].計算機(jī)科學(xué),2010,37(9):36-37

[7]白曉慶.基于分層分段和索引表的前綴區(qū)間IPv6路由查找算法[D].沈陽:東北大學(xué),2010:9-10

[8]劉偉,劉偉科,閆春.IPV6下的路由技術(shù)[J].電腦知識與技術(shù),2006,28(20):74-75

[9]王東菊.基于Bloom濾波器的快速路由查找算法研究[D].大連:大連理工大學(xué),2013:10-13

[10]崔尚森,馮博琴.最長前綴匹配查找的索引分離Trie樹結(jié)構(gòu)及其算法[J].計算機(jī)工程與應(yīng)用,2005,41(20):131-135

[11] Nilsson S, Karlsson G. IP address lookup using LC-Tries[J]. IEEE Journal on Selected Areasin Communications, 1999,17(6):1083-1092

[12]高瑩.哈希表和多比特Trie樹相結(jié)合的IPv6路由查找算法研究[D].鄭州:鄭州大學(xué),2010:9-20

[13]謝希仁.計算機(jī)網(wǎng)絡(luò).第六版.[M].北京:電子工業(yè)出版社,2013:189

[14]崔尚森,馮博琴,張白一.一種前綴長度二分查找的改進(jìn)算法[J].計算機(jī)工程,2007,33(15):71-74

[15] Li Z, Deng X, Ma H, et al. Divide-and-Conquer: A scheme for IPv6 Address longest prefixmatching[C]//Proceedings of IEEE Workshop on High Performance Switching and Routing. Poznan, Poland: IEEE Press, 2006:37-42

[16]秦曉分.IPv6路由查找算法研究[D].南京:南京郵電大學(xué),2009:37-40

The Study on IPv6 Routing Lookup Algorithm Based on Three-level Index and Multi-bit Trie

LIU Yang

Department of Information Engineering/Binzhou University, Binzhou 256603, China

Abstract:The rapid development of Internet facilitates the exponential growth in the number of forwarded packets of core router for backbone network and the rapid IP routing lookup algorithm is a key for achieving the high-speed packet forwarding. The application of IPv6 requires the routing lookup algorithm to adapt to the characteristics of IPv6 address. This paper analyzed the typical routing lookup algorithm based on Trie and summarized the advantages and disadvantages of various algorithms. Combining the characteristics of IPv6 address and the distribution laws of address prefixes in the routing table of backbone router, this paper proposed a rapid IPv6 routing lookup algorithm based on the three-level index table and the multi-bit Trie. It was easier to be achieved a faster speed in lookup and updating and required a smaller storage space comparing with other similar algorithms.

Keywords:Index table; multi-bit Trie; routing lookup; IPv6

作者簡介:劉陽(1979-),女,碩士,主要從事計算機(jī)網(wǎng)絡(luò)相關(guān)工作. E-mail:bzjsjly@126.com

基金項目:濱州學(xué)院“青年人才創(chuàng)新工程”科研基金(BZXYQNLG200903)；濱州市軟科學(xué)研究計劃項目(2014RKX18)

收稿日期:2015-01-04修回日期: 2015-05-08

中圖法分類號:TP393文獻(xiàn)標(biāo)示碼: A

文章編號:1000-2324(2015)04-0607-06