BSD radix樹路由表的設(shè)計(jì)原理

1、寫這篇文章的時(shí)候使用的是FreeBSD5.1的代碼，舉例用的是IPv6地址。BSD路由表使用的是radix樹，這種樹的設(shè)計(jì)思想來自Donald R.Morrison于1968年提出的 Patricia 樹（Practical Algorithm To Retrieve Information Coded In Alphanumeric。這是一 種基于以二進(jìn)制表示的鍵值的查找樹，尤其適合于處理非常長的、可變長度的鍵值Partricia的基 本思想是構(gòu)建一個(gè)二叉樹，在每個(gè)節(jié)點(diǎn)中都存儲有進(jìn)行下一次的it測試之前需要跳過的bit數(shù)目， 以此來避免單路分支（即避免二叉樹的某一段呈現(xiàn)只往左或者只往右生長的

2、趨勢）。因此，一般意義 上的Patricia樹由內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)組成，內(nèi)部節(jié)點(diǎn)用于指示需要進(jìn)行5it測試的位置，并依據(jù) bit測試結(jié)果決定查找操作的前進(jìn)方向而外部節(jié)點(diǎn)則用于存儲鍵值查找操作將于外部節(jié)點(diǎn)處終止。BSD正是借用了Partricia樹的思想來組織路由表，但考慮到路由表的特殊性，即需要存儲掩碼 并實(shí)現(xiàn)最長匹配路由查找，于是對Partricia樹進(jìn)行了改造，形成了 BSD的radix樹。在BSD的radix 樹中的路由查找操作將分為三個(gè)步驟，第一個(gè)步驟即partricia查找，終結(jié)于某個(gè)葉子節(jié)點(diǎn)，判斷 該葉子節(jié)點(diǎn)是否與查找鍵相同。第二個(gè)步驟，如果找到的葉子節(jié)點(diǎn)與查找鍵無法匹配，則在這個(gè)

3、葉子 節(jié)點(diǎn)的重復(fù)鍵鏈表中尋找網(wǎng)絡(luò)匹配的可能。第三個(gè)步驟，如果找到的葉子節(jié)點(diǎn)及其重復(fù)鍵與查找鍵不 滿足網(wǎng)絡(luò)匹配條件，則向樹頂回溯，繼續(xù)尋找網(wǎng)絡(luò)匹配的可能。BSD路由表的表頭BSD路由表的頭指針存放在rt_tables數(shù)組中，這是一個(gè)radix_node_head結(jié)構(gòu)體類型的指針 數(shù)組。在BSD的協(xié)議棧中，所有協(xié)議的路由表都是用radix樹進(jìn)行組織的，而這些radix樹的頭指針 就都存放在rt_tables數(shù)組中，IPv6路由表的頭指針只是其中之一，即下標(biāo)為AF_INET6的數(shù)組元 素。radix_node_head結(jié)構(gòu)體的內(nèi)存布局如圖1所示。rnh_treetop是指向路由表頂部節(jié)點(diǎn)的指針。 在

4、這個(gè)結(jié)構(gòu)體中還定義了8個(gè)函數(shù)指針，分別指向路由表提供的8個(gè)操作函數(shù)。在這個(gè)結(jié)構(gòu)體的尾部 還有三個(gè)radix_node結(jié)構(gòu)體，這就是radix樹的初始三節(jié)點(diǎn)，它們的rn_flags字段將被設(shè)置成RNF_ROOT，表示這是radix樹的根節(jié)點(diǎn)。這三個(gè)節(jié)點(diǎn)是在路由表跏薊時(shí)生成的e tzri-ict I adix_node * zroli_-fcxee-topriili_=Ldiitrsz exiihL_pktsize(炬 nh_addaddxj )C+i nh_de 1 addr) j J(:+mh_d.eC+t nh_mat chaiirio oltup) X)ch.pk t)(*inh_ia.l

5、kties)e true tx=&dz_XLod.eb true ti adl2_ii o des true txadi3E_no deEtruc-t iadi3E_iio de_h.e路由表初始化完成后，這三個(gè)根節(jié)點(diǎn)的鏈接關(guān)系如圖所示。從這個(gè)圖中我們可以看出，在三個(gè) 根節(jié)點(diǎn)組成的數(shù)組rnh_nodes3中，第二個(gè)根節(jié)點(diǎn)作為路由表的頂部節(jié)點(diǎn)，由rnh_treetop指針指 向，它將是對路由表的所有操作的開始處。此外，第一個(gè)根節(jié)點(diǎn)被初始化為頂部節(jié)點(diǎn)的左孩子，三個(gè)根節(jié)點(diǎn)被初始化為頂部節(jié)點(diǎn)的右孩子，而這三個(gè)初始根節(jié)點(diǎn)的父指針都指向了中間的那個(gè)頂部節(jié)點(diǎn)。這實(shí)際上已經(jīng)搭起了一個(gè)radix樹的基本框架。如

6、圖2所示。在圖2中，我們將中間的作為路由樹頂?shù)母?jié)點(diǎn)用圓圈表示，因?yàn)樗鼘儆趦?nèi)部節(jié)點(diǎn)而另外的兩 個(gè)根節(jié)點(diǎn)我們用方框表示，它們屬于葉子節(jié)點(diǎn)。在本文檔中將始終按照這一約定來圖示內(nèi)部節(jié)點(diǎn)和葉 子節(jié)點(diǎn)。BSD路由表的節(jié)點(diǎn)BSD路由表的radix樹實(shí)際上就是由一系列的內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)組成的。內(nèi)部節(jié)點(diǎn)位于樹的中 間位置，每個(gè)內(nèi)部節(jié)點(diǎn)都會指定一個(gè)bit測試位置，即當(dāng)從樹的頂端開始向下查找，遇到這個(gè)內(nèi)部節(jié) 點(diǎn)時(shí)需要判斷是0還是1的bit位置，接下來的查找將根據(jù)bit測試的結(jié)果來決定是向左走還是向右 走。葉子節(jié)點(diǎn)位于樹的邊緣，用于存儲路由表鍵值，即IP地址。2.1內(nèi)部節(jié)點(diǎn)前已述及，內(nèi)部節(jié)點(diǎn)在radix樹中用于表

7、示一個(gè)bit測試位置。內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)使用的都是radix_node結(jié)構(gòu)體，只是少數(shù)字段的定義有所不同。我們首先 通過內(nèi)部節(jié)點(diǎn)來查看一下radix_node結(jié)構(gòu)體中的各個(gè)字段。在radix樹中的3個(gè)根節(jié)點(diǎn)中，位于中 間的那個(gè)頂端節(jié)點(diǎn)就是內(nèi)部節(jié)點(diǎn)，因此我們的描述就以圈為例。rn_mklist:這個(gè)指針指向的是一個(gè)radix_mask結(jié)構(gòu)體鏈表。對于內(nèi)部節(jié)點(diǎn)來說這個(gè)鏈表上的掩 碼都取自它的子樹中的葉子節(jié)點(diǎn)所對應(yīng)的掩碼，但只有那些在做邏輯AND運(yùn)算時(shí)能夠把這個(gè)內(nèi)部節(jié)點(diǎn) 的測試bit變成0的掩碼才能夠加入到這個(gè)鏈表中，這類掩碼的作用將在路由查找時(shí)的回溯過程中體 現(xiàn)出來。對于葉子節(jié)點(diǎn)，如果它的掩碼滿足

8、上述條件而被選入它的某一級父節(jié)點(diǎn)的掩碼鏈表的話，那 么它的rn_mklist指針就會指向這個(gè)掩碼鏈表中對應(yīng)于它自己的掩碼的那個(gè)節(jié)點(diǎn)。rn_parent:這是節(jié)點(diǎn)的父指針，從葉子節(jié)點(diǎn)一直向上指到樹的頂端節(jié)點(diǎn)，而樹的頂端節(jié)點(diǎn)的父指針是 指向它自己的。路由查找時(shí)的回溯過程將沿父指針進(jìn)行。rn_bit:對于內(nèi)部節(jié)點(diǎn)，這個(gè)值大于等于0，用于指示在這個(gè)內(nèi)部節(jié)點(diǎn)處需要進(jìn)行測試的bit位 置。這個(gè)位置是從用于存儲IP地址的socket地址結(jié)構(gòu)體的起始位置開始計(jì)算的。對于葉子節(jié)點(diǎn)，這 個(gè)值是一個(gè)負(fù)數(shù)，具體數(shù)值就是1減去這個(gè)葉子節(jié)點(diǎn)所對應(yīng)的掩碼的索引值。而所謂掩碼的索引值 就是指這個(gè)掩碼中第一次出現(xiàn)0的bit位置

9、，這個(gè)位置也是從socket地址結(jié)構(gòu)體的起始位置開始計(jì) 算的。etmct radix node headEtructr!idix_nL!=LEkEtruclradix_iiode:+：Tn_pi!jr e?itrn._bi+I IX_tiITL：=LE；kI !_ 1 ag 5rn_Keyhi_Pk1 eiiE-tr uctr ailixiiode：+：m_DuLp e di eystrnjc-t17:id ix_nLask*xn_irik liststructr=idix_tlwdt:*in_p：=ix entrn_t +x iiiriaEkxn_t lagsrn_Qffrn_Lrn_REt

10、lTLCtr：=Ldix_ni：=LEkJtfrn_mkliEtEtruclradix_iiode=+：Tn_pi!jr e?itrn_bitlags37ti_PKl tille -tr u c tr ：=nlix_iiq de如n_Dnp e 丑 eyNULL-S5K1IF_ROOT | RMF_ACTIVEA m_z ex 三NULL1000 0000KMF_ROQT | RNF_ACTIVENULL-65RWF._ROOT | RNF_ACTIVEA rn_ont!Ern_bmask:這是一個(gè)1字節(jié)的掩碼，其中只有一個(gè)bit為1。在實(shí)際的路由查找中，為了加快查 找速度，就是使用這個(gè)字段直

11、接對指定的字節(jié)進(jìn)行）it測試，而不是指定bit進(jìn)行測試。對于葉子節(jié) 點(diǎn)，這個(gè)字段為0。rn_flags:這個(gè)字段的可能取值一共有3個(gè)，RNF_NORMAL，表示這是一個(gè)含有常規(guī)路由的葉子節(jié) 點(diǎn)；RNF_ROOT，表示這是一個(gè)位于radix_node_head結(jié)構(gòu)體中的節(jié)點(diǎn)，即路由表中的三個(gè)根節(jié)點(diǎn)； RNF_ACTIVE，表示這條路由的狀態(tài)是好的。rn_Off:這是內(nèi)部節(jié)點(diǎn)獨(dú)有的字段，表示一個(gè)從socket地址結(jié)構(gòu)體的起始位置開始計(jì)算的字節(jié)偏 移量，用于指定在這個(gè)內(nèi)部節(jié)點(diǎn)處需用rn_bmask進(jìn)行單字節(jié)比較的字節(jié)偏移量。rn_L :這是內(nèi)部節(jié)點(diǎn)獨(dú)有的字段，指向這個(gè)內(nèi)部節(jié)點(diǎn)的左孩子。rn_R :這

12、是內(nèi)部節(jié)點(diǎn)獨(dú)有的字段，指向這個(gè)內(nèi)部節(jié)點(diǎn)的右孩子。2.2葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)的大部分字段都是一樣的，只是最后三個(gè)字段的定義不一樣。相同字段的定 義已在前面的內(nèi)部節(jié)點(diǎn)部分進(jìn)行了描述，最后三個(gè)字段的定義如下。rn_Key:這個(gè)字段就內(nèi)存位置而言相當(dāng)于內(nèi)部節(jié)點(diǎn)中的rn_Off字段。這個(gè)字段用于指向存儲著葉 子節(jié)點(diǎn)鍵值（即IP地址）的socket地址結(jié)構(gòu)體。rn_Pfxlen:這個(gè)字段就內(nèi)存位置而言相當(dāng)于內(nèi)部節(jié)點(diǎn)中的m_L字段。這個(gè)字段用于存儲前綴長 度。rn_Dupedkey:這個(gè)字段就內(nèi)存位置而言相當(dāng)于內(nèi)部節(jié)點(diǎn)中的rn_R字段。當(dāng)路由表中有重復(fù)鍵情 況出現(xiàn)的時(shí)候，即有多個(gè)葉子節(jié)點(diǎn)的鍵值IP地址

13、）相同，這些葉子節(jié)點(diǎn)是以鏈表的形式掛接在樹 中的某個(gè)葉子節(jié)點(diǎn)下的，rn_Dupedkey即指向重復(fù)鍵鏈表中的下一個(gè)葉子節(jié)點(diǎn)。在radix樹中，左右兩個(gè)根節(jié)點(diǎn)即屬于葉子節(jié)點(diǎn)。2.3根節(jié)點(diǎn)radix樹中的根節(jié)點(diǎn)即是在圖2和圖3中給出的3個(gè)節(jié)點(diǎn)。這三個(gè)節(jié)點(diǎn)都被設(shè)置了RNF_ROOT標(biāo) 志，以表示它們是根節(jié)點(diǎn)。中間的那個(gè)根節(jié)點(diǎn)是radix樹的頂部節(jié)點(diǎn)，所有的路由查找操作都是從它開始的我們可以看到， 這個(gè)根節(jié)點(diǎn)的bit測試位置是64,也就是說，對于存儲在socket地址結(jié)構(gòu)體中的BSD地址而言，實(shí) 際的BSD地址開始的第一個(gè)bit在結(jié)構(gòu)體中的偏移量是64,整個(gè)radix樹的bit比較算法就是從這 第64

14、 bit開始。前已述及，為了加快查找速度，實(shí)際的查找操作中使用的是字節(jié)偏移和字節(jié)掩碼。 因此，第64 bit對應(yīng)的字節(jié)偏移就是8,而字節(jié)掩碼就是二進(jìn)制的1000 0000。另外的兩個(gè)根節(jié)點(diǎn)分列于樹的最左端和最右端。我們可以看到，它們的n_bit字段都小于0， 表明這兩個(gè)根節(jié)點(diǎn)屬于葉子節(jié)點(diǎn)。事實(shí)上，它們一個(gè)對應(yīng)的是全鍵值，一個(gè)對應(yīng)的是全1鍵值。在路由查找操作中，任何時(shí)刻都不能返回根節(jié)點(diǎn)本身。如果查找操作定位到了根節(jié)點(diǎn)，將代之以 返回空指針。2.4重復(fù)鍵節(jié)點(diǎn)BSD路由表中的重復(fù)鍵節(jié)點(diǎn)是指路由樹中鍵值IP地址）完全相同的葉子節(jié)點(diǎn)。這些重復(fù)鍵節(jié)點(diǎn)由各自的rn_Dupedkey指針串成一個(gè)鏈表，通過位于

15、鏈表頭部的葉子節(jié)點(diǎn)掛在路 由樹中。位于鏈表中的重復(fù)鍵節(jié)點(diǎn)是按照掩碼的精確程度從高到低排列的即位于鏈表頭部的葉子節(jié) 點(diǎn)的掩碼最精確，對于掩碼連續(xù)的情況而言也就是它的掩碼最長。這樣在路由查找的時(shí)候如果找到了 這串重復(fù)鍵節(jié)點(diǎn)，就可以保證掩碼最長的路由最先匹配。BSD路由表的路由條目如前所述，BSD路由表是由一系列的內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)組織起來的，這是BSD路由表的邏輯結(jié) 構(gòu)。如果從內(nèi)存布局來講，BSD路由表中的路由條目則是通rtentry結(jié)構(gòu)體來存放的，我們前面提 到的內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)實(shí)際上都是存放在這個(gè)結(jié)構(gòu)體中的rtentry結(jié)構(gòu)體的組成如圖4所示。我們可以看到，在rtentry結(jié)構(gòu)體的頭部就是由

16、兩個(gè)radix_node結(jié)構(gòu)體組成的數(shù)組rt_nodes2。在這個(gè)數(shù)組中，第一個(gè)元素是葉子節(jié)點(diǎn)，負(fù)責(zé)存儲路由表鍵值，即IP地址，第二個(gè)元素是內(nèi)部節(jié)點(diǎn)， 負(fù)責(zé)完成樹的連接。因此，就一般情況而言，每當(dāng)往路由樹中添加一條路由的時(shí)候，我們實(shí)際上添加 的是兩個(gè)節(jié)點(diǎn)，一個(gè)葉子節(jié)點(diǎn)和一個(gè)內(nèi)部節(jié)點(diǎn)，只不過這兩個(gè)節(jié)點(diǎn)的存儲空間是我們事先gentry 結(jié)構(gòu)體分配好了的。雖然這兩個(gè)節(jié)點(diǎn)在物理上是緊挨著的，但是由于后續(xù)路由條目的加入，它們之間 就可能會插入一系列的內(nèi)部節(jié)點(diǎn)，而這些內(nèi)部節(jié)點(diǎn)又分別屬于各自的rtentry結(jié)構(gòu)體，并對應(yīng)著各自 的葉子節(jié)點(diǎn)。日 + T1J.C+rde r +_tiQdes 2e t rue

17、tEcick adiztr +：r t_g at ewayefentLagsEtmct ifnetpet i ididir ：+=ra3rt_llinfnEtruct T+_TTie + r icer + _i3TixE+171-1-3 +:*Vfc_gWTDTltUiii-teeii-tzry牛!:r * ipazrmn七void. :+：zr+_f iller 2e +xijc+ i-+ eii-txy +:iex ieti+r-y在rtentry結(jié)構(gòu)體的剩余部分中存儲的是這條路由的接口、接口地址以及網(wǎng)關(guān)路由等關(guān)鍵信息。BSD路由表的路由查找前已述及，BSD路由表使用的是經(jīng)BSD修改之后的

18、Patricia樹，也就是BSD radix樹。在這種 樹中，內(nèi)部節(jié)點(diǎn)用于指定需要對查找鍵進(jìn)行測試的一系列bit位置，而外部節(jié)點(diǎn)則用于存儲鍵值。為 了適合路由表的需求，每個(gè)葉子節(jié)點(diǎn)都會有一個(gè)與之對應(yīng)的掩碼。內(nèi)部節(jié)點(diǎn)可能有也可能沒有對應(yīng)的 掩碼，這取決于在它的子樹中是否存在能夠?qū)⑺臏y試bit邏輯AND成0的掩碼。于是，根據(jù)這些特 性，BSD路由表中的路由查找就分成了三個(gè)步驟，即找到葉子節(jié)點(diǎn)進(jìn)行精確匹配、在重復(fù)鍵鏈表中進(jìn) 行網(wǎng)絡(luò)匹配和通過回溯過程進(jìn)行網(wǎng)絡(luò)匹配。4.1第一步：尋葉這一步實(shí)際上就是Patricia查找，即從路由表的頂部節(jié)點(diǎn)開始，根據(jù)所遇內(nèi)部節(jié)點(diǎn)中指示的bit 測試位置進(jìn)行測試，根據(jù)該

19、bit是0還是1來決定繼續(xù)往右走還是往左走，直至到達(dá)一個(gè)葉子節(jié)點(diǎn)為 止。當(dāng)radix_node結(jié)構(gòu)體作為內(nèi)部節(jié)點(diǎn)的時(shí)候，它的bit測試位置是由rn_bit字段來給出的。但是， 僅僅是這樣一個(gè)bit測試位置對于有多個(gè)字節(jié)的IP地址來說顯然是不合適的，在查找的時(shí)候再去定 位這個(gè)bit會影響查找效率，所以在添加這個(gè)內(nèi)部節(jié)點(diǎn)的時(shí)候就會根據(jù)3哉測試位置計(jì)算一個(gè)字節(jié)偏 移量和相應(yīng)的字節(jié)掩碼，即rn_Off和rn_bmask字段。字節(jié)偏移量用于指定bit測試位置所在字節(jié)相 對于socket地址結(jié)構(gòu)體起始處的偏移量，而字節(jié)掩碼則是一個(gè)8 bit的掩碼，其中只有一個(gè)bit為 1，在通過字節(jié)偏移量定位了字節(jié)之后，

20、即可由字節(jié)掩碼進(jìn)什it測試操作。舉例而言，BSD路由表的局部如圖5所示。圖中位于最上方的標(biāo)記有64的那個(gè)內(nèi)部節(jié)點(diǎn)就是radix 樹的頂端根節(jié)點(diǎn)，即在初始化路由表時(shí)生成的三個(gè)根節(jié)點(diǎn)中的中間一個(gè)64這個(gè)數(shù)字是IPv6地址的 第一個(gè)bit在socket地址結(jié)構(gòu)體中的偏移量。由于所有的路由查找操作都要從樹的頂端開始向下進(jìn) 行，所以不管查找哪條路由，都會從IPv6地址的第一個(gè)bit開始進(jìn)行比較。假設(shè)我們現(xiàn)在需要在這個(gè)radix樹中查找FE80:210:5CFF:FEC2:38E7這條路由。從樹的頂端開 始，根據(jù)沿途內(nèi)部節(jié)點(diǎn)指定的bit進(jìn)行測試。這條路由的第64 bit為1，向右。第65 bit為1，繼

21、續(xù)向右。第71 bit為0，向左。第128 bit為0，繼續(xù)向左。第160 bit為1，向右。這時(shí)，將會遇 到一個(gè)rn_bit字段為負(fù)值的節(jié)點(diǎn)，即葉子節(jié)點(diǎn)，于是查找操作將停止在此處。接下來的操作就是比較找到的這個(gè)葉子節(jié)點(diǎn)與我們的查找鍵是否匹配比較操作是以字節(jié)為單位 進(jìn)行的，參與比較的字節(jié)數(shù)將以葉子節(jié)點(diǎn)掩碼的最后一個(gè)司0字節(jié)為限，即若在此范圍內(nèi)葉子節(jié)點(diǎn)與 查找鍵相同則認(rèn)為匹配，查找操作成功結(jié)束，否則認(rèn)為不匹配，并記錄下查找鍵與葉子節(jié)點(diǎn)鍵值第一 次出現(xiàn)不同的字節(jié)位置。在返回查找結(jié)果時(shí)有一點(diǎn)需要注意，即在任何時(shí)候都不能返回根節(jié)點(diǎn)自身， 如果在這一步找到的葉子節(jié)點(diǎn)是一個(gè)根節(jié)點(diǎn)，那么就必須返回它的重復(fù)鍵

22、指針n_dupedkey，而不是 它自己。第一步的查找路徑在圖5中用紅色曲線進(jìn)行了標(biāo)識。4.2第二步：辨重如果在第一步中找到的葉子節(jié)點(diǎn)與查找鍵不滿足匹配的條件則需要遍歷這個(gè)葉子節(jié)點(diǎn)的重復(fù)鍵 鏈表。由于重復(fù)鍵鏈表中的葉子節(jié)點(diǎn)與第一步中找到的葉子節(jié)點(diǎn)的鍵值（也就是P地址）是完全相 同的，只是掩碼呈逐漸縮短的趨勢，因此可能在重復(fù)鍵鏈表中存在網(wǎng)絡(luò)匹配的可能。重復(fù)鍵處理的過 程如圖6所示。646518ISO圖6是在圖5的基礎(chǔ)上繪制的。對于圖中所示的三個(gè)重復(fù)鍵節(jié)點(diǎn)，我們用綠色的長短表示了它們 各自掩碼的長短，可以看出，掩碼是呈逐漸變短趨勢的。由于在第一步中我們已經(jīng)確定了查找鍵和葉子節(jié)點(diǎn)鍵值第一次出現(xiàn)不同的

23、字節(jié)位置因此可以方 便地?fù)Q算出查找鍵和葉子節(jié)點(diǎn)鍵值第一次出現(xiàn)不同的3哉位置。前已述及，在葉子節(jié)點(diǎn)的radix_node 結(jié)構(gòu)體中，rn_bit字段就是由葉子節(jié)點(diǎn)的掩碼中第一次出現(xiàn)0的bit位置換算出來的。因此，在接 下來的重復(fù)鍵處理中，我們只需要把查找鍵和葉子鍵值第一次出現(xiàn)不同的it位置跟葉子節(jié)點(diǎn)的 rn_bit字段進(jìn)行比較就可以方便地確定某個(gè)重復(fù)鍵節(jié)點(diǎn)是否滿足網(wǎng)絡(luò)匹配的條件，而不需要進(jìn)行實(shí) 際的掩碼操作。如果在重復(fù)鍵鏈表中有某個(gè)葉子節(jié)點(diǎn)滿足網(wǎng)絡(luò)匹配條件，則向調(diào)用者返回這個(gè)葉子節(jié)點(diǎn)。否則查 找操作將回到最初找到的那個(gè)葉子節(jié)點(diǎn)（也就是重復(fù)鍵鏈表上的第一個(gè)節(jié)點(diǎn)），準(zhǔn)備開始向樹頂回溯 了。第二步的查

24、找路徑在圖6中依然用紅色曲線進(jìn)行標(biāo)識，實(shí)際上是將圖5中的紅色曲線延伸至重復(fù) 鍵鏈表中。4.3第三步：回溯到目前為止，我們只是使用作為查找鍵的地址在radix樹中根據(jù)內(nèi)部節(jié)點(diǎn)指示的bit測試位 置找到了某個(gè)葉子節(jié)點(diǎn)，并進(jìn)行了重復(fù)鍵處理，仍然沒有找到匹配的葉子節(jié)點(diǎn)這并不能排除在radix 樹中還存在有其它可能滿足網(wǎng)絡(luò)匹配條件的葉子節(jié)點(diǎn)因此就需要沿著來時(shí)的內(nèi)部節(jié)點(diǎn)路徑向樹頂回 溯，尋求網(wǎng)絡(luò)匹配的可能?；厮葸^程如圖7所示。回溯過程在圖7中用藍(lán)色曲線標(biāo)識，方向從下到上。我們可以看出，回溯過程是從第一步中找到 的那個(gè)葉子節(jié)點(diǎn)處開始，沿著每個(gè)節(jié)點(diǎn)的父指針rn_parent向樹頂前進(jìn)，這實(shí)際上就是我們在第一步 中從樹頂找到葉子節(jié)點(diǎn)所經(jīng)由的路徑，因此才把這一步稱為回溯?；厮萃局薪?jīng)過的是一系列的內(nèi)部節(jié)點(diǎn)，對于每一個(gè)內(nèi)部節(jié)點(diǎn)，將會判斷它是否掛的有掩碼鏈表， 即它的rn_mklist字段是否為空。掩碼鏈表在圖7中用粉紅色表示。沒有掩碼鏈表的內(nèi)部節(jié)點(diǎn)將不予 考慮，直接通過。如果某個(gè)內(nèi)部節(jié)點(diǎn)掛的