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

劉陽

濱州學院信息工程系,山東濱州256603

?

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

劉陽

濱州學院信息工程系,山東濱州256603

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

關鍵詞:索引表;多比特Trie;路由查找; IPv6

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

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

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

1.1二進制Trie樹

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

根據表1的路由前綴信息，可以構造一棵二進制Trie樹。其結構見圖1。

表1　路由表Table1 Routing table

圖1　二進制TrieFig.1Binary Trie tree

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

1.2多比特Trie樹

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

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

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

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

2　算法設計

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

128位的IPv6地址空間被劃分為兩大部分[13]。其中，高64 bits表示網絡前綴，低64 bits表示后綴，即主機。根據RFC3587中規(guī)定的全球單播地址的標識長度為高64 bits，不用于子網間的路由。因此，IPv6單播地址的地址前綴長度不會小于64 bits，而是介于65~128 bits之間，并且只可能有長度為128 bits的前綴。而按照IPv6單播地址的分配策略，不存在長度小于16 bits的網絡前綴。就單播IPv6而言，以6 Bone，6 Net等幾個IPv6骨干實驗網絡的數據來看，其前綴長度主要介于19~64 bits，核心路由器關心的是目標地址的高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算法的數據結構

依據IPv6路由前綴分布規(guī)律，本算法采用三張索引表和三棵多比特Trie樹來實現。算法將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é)約存儲空間，三張索引表采用不同的數據結構。

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

圖3　H_Tab1和H_Tab2的數據結構Fig.3 Data structure of H_Tab1 and H_Tab2

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

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

②MP_1=1，MP_2=1，Fill_Len=000時，說明存在比32 bits更長的前綴，NHP_Add用來表示H_Tab2索引表的地址；

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

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

⑤其他情況為無效情況。

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

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

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

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

圖5　多比特Trie樹數據結構Fig.5 Data structure of multi-bit Trie tree

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

圖6　算法整體數據架構Fig.6 Data workup of the algorithm

3　算法流程與性能分析

3.1算法流程

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

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

3.2算法的性能分析

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

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

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

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

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

4　結論

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

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

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

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

參考文獻

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

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

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

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

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

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

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

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

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

[10]崔尚森,馮博琴.最長前綴匹配查找的索引分離Trie樹結構及其算法[J].計算機工程與應用,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樹相結合的IPv6路由查找算法研究[D].鄭州:鄭州大學,2010:9-20

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

[14]崔尚森,馮博琴,張白一.一種前綴長度二分查找的改進算法[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].南京:南京郵電大學,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-),女,碩士,主要從事計算機網絡相關工作. E-mail:bzjsjly@126.com

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

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

中圖法分類號:TP393文獻標示碼: A

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