張宏亮，陳 明，賈永興，陳沛然

（中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引言

近年來(lái)移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、大數(shù)據(jù)等技術(shù)日新月異，深刻地影響著人們的生產(chǎn)和生活。網(wǎng)絡(luò)中高帶寬、低延遲的數(shù)據(jù)業(yè)務(wù)對(duì)路由器轉(zhuǎn)發(fā)速率的要求也越來(lái)越高，然而使用軟件通過(guò)如Patricia樹(shù)[1]、路徑壓縮樹(shù)[1]（Path compressed tree）等結(jié)構(gòu)來(lái)組織路由表數(shù)據(jù)，并配合相應(yīng)的算法來(lái)實(shí)現(xiàn)路由查表的方案，已無(wú)法滿足高速轉(zhuǎn)發(fā)的要求。正是在這種背景下，業(yè)界提出了基于硬件三態(tài)內(nèi)容尋址存儲(chǔ)器（Ternary Content-Addressable Memory，TCAM）的路由查表方案。該方案解決了（Classless Inter-Domain Routing，CIDR）[2,3]最長(zhǎng)前綴匹配問(wèn)題，因此在行業(yè)內(nèi)得到大規(guī)模應(yīng)用。TCAM硬件查表的時(shí)長(zhǎng)恒定為一個(gè)時(shí)鐘周期，時(shí)間復(fù)雜度僅為O(1)，但由于TCAM對(duì)路由表項(xiàng)存放有嚴(yán)格的順序要求，使得表項(xiàng)管理趨于復(fù)雜，例如，當(dāng)表項(xiàng)更新時(shí)，無(wú)法進(jìn)行查表，此時(shí)數(shù)據(jù)包需要先緩存，等表項(xiàng)更新完畢后才能查表。此外，若表項(xiàng)更新時(shí)間過(guò)長(zhǎng)，會(huì)引起緩存溢出，進(jìn)而產(chǎn)生嚴(yán)重丟包，影響路由器的正常轉(zhuǎn)發(fā)性能。因此，表項(xiàng)管理算法的性能是影響TCAM路由查表性能的關(guān)鍵因素之一。

本文首先分析現(xiàn)有表項(xiàng)管理算法的優(yōu)缺點(diǎn)；其次利用前綴塊概率分布、動(dòng)態(tài)平衡的特點(diǎn)，對(duì)表項(xiàng)預(yù)留模型進(jìn)行了優(yōu)化，合理利用回收緩存；最后提出并實(shí)現(xiàn)一種改進(jìn)的基于緩存的雙鏈表管理算法。

1 TCAM原理及特性分析

TCAM每個(gè)存儲(chǔ)比特可以有3種狀態(tài)：0,1,X。X態(tài)表示“Don’t care”，正是這第三態(tài)的特征使得其能進(jìn)行模糊匹配查表。在模糊匹配查表時(shí)，可能存在多個(gè)表項(xiàng)都匹配的情況，此時(shí)TCAM會(huì)在匹配表項(xiàng)中選擇地址最低的表項(xiàng)作為最終匹配項(xiàng)，如圖1所示。

圖1 TCAM最長(zhǎng)匹配規(guī)則

TCAM存放路由表時(shí)，需要按地址由低到高，依次存放前綴長(zhǎng)度由長(zhǎng)到短的表項(xiàng)[4]，才能實(shí)現(xiàn)最長(zhǎng)前綴匹配。這種硬性規(guī)定，讓表項(xiàng)管理變得復(fù)雜，有時(shí)會(huì)附帶無(wú)法避免的現(xiàn)有表項(xiàng)的挪動(dòng)。

假設(shè)TCAM的容量為M，現(xiàn)存表項(xiàng)總數(shù)為N。用原始的方法添加一條表項(xiàng)，且要保證順序要求，就要在TCAM的特定位置增加才行，不然表項(xiàng)的前綴長(zhǎng)度會(huì)亂序。最糟糕的情況下，需要挪動(dòng)N次為其挪出空間，時(shí)間復(fù)雜度為O(N)。因此，實(shí)現(xiàn)表項(xiàng)高效管理、減少挪動(dòng)次數(shù)、節(jié)省更新時(shí)間，是提高查表速度的幾個(gè)關(guān)鍵因素。

2 TCAM表項(xiàng)管理算法介紹

本文以IPv4路由表為例進(jìn)行說(shuō)明，其中的方法也可以擴(kuò)展到IPv6上，同時(shí)假定其前綴塊長(zhǎng)度范圍在3～32之間。

2.1 順序移動(dòng)法

順序移動(dòng)法如圖2所示，圖中相同長(zhǎng)度表項(xiàng)組成前綴塊。從TCAM低地址空間開(kāi)始，按前綴塊由長(zhǎng)到短的順序存放表項(xiàng)，高地址處存放空閑表。當(dāng)新增加一個(gè)表項(xiàng)時(shí)，假設(shè)其前綴長(zhǎng)度為i(3≤i≤32)，表項(xiàng)中長(zhǎng)度小于i的表項(xiàng)都需要挪動(dòng)位置，然后插入新表項(xiàng)。顯然，這種管理方式造成現(xiàn)有表項(xiàng)關(guān)聯(lián)移動(dòng)次數(shù)過(guò)多，效率極低。最糟糕的情況下，時(shí)間復(fù)雜度為O(N)，其中N是TCAM中現(xiàn)存的表項(xiàng)條數(shù)。

圖2 順序移動(dòng)法

2.2 帶預(yù)留表項(xiàng)的順序移動(dòng)法

與順序移動(dòng)法相比，帶預(yù)留表項(xiàng)的順序移動(dòng)算法[5]的改進(jìn)之處在于，把空閑表分散到各個(gè)前綴塊內(nèi)部。如圖3所示，帶預(yù)留表項(xiàng)的順序移動(dòng)算法中3～32前綴長(zhǎng)度預(yù)留相同大小的存儲(chǔ)空間。當(dāng)添加表項(xiàng)時(shí)，假設(shè)其前綴長(zhǎng)度為i(3≤i≤32)，如果i對(duì)應(yīng)的前綴塊內(nèi)部未占滿，則直接寫(xiě)入，現(xiàn)存表項(xiàng)不需要挪動(dòng)；若i前綴塊內(nèi)部占滿，則借占i+1前綴塊的預(yù)留空間尾部位置添加表項(xiàng)。當(dāng)刪除表項(xiàng)時(shí)，為保證空閑表的連續(xù)性，i前綴塊內(nèi)部在其后面的表項(xiàng)都往上挪動(dòng)一位。該算法僅減少了表項(xiàng)移動(dòng)的平均次數(shù)，但若是前綴塊及相鄰前綴塊預(yù)留空間均占滿的情況下，時(shí)間復(fù)雜度仍然是O(N)。

圖3 帶預(yù)留表項(xiàng)的順序移動(dòng)法

2.3 選擇移動(dòng)法

由第1節(jié)可知：路由最長(zhǎng)前綴匹配只要求不同長(zhǎng)度表項(xiàng)的存放有順序關(guān)系，相同長(zhǎng)度的表項(xiàng)不要求順序。選擇移動(dòng)法則充分利用此特性，其表項(xiàng)存放結(jié)構(gòu)與順序移動(dòng)法相同。如圖4所示，假設(shè)新添加的表項(xiàng)前綴長(zhǎng)度為i(3≤i≤32)，那么需要按前綴塊長(zhǎng)度由短到長(zhǎng)的順序，依次將前綴長(zhǎng)度為3,4,…,i-1的前綴塊的第一條表項(xiàng)挪至該前綴塊尾部。其時(shí)間復(fù)雜度為O(P)(0

圖4 選擇移動(dòng)法

2.4 帶預(yù)留表項(xiàng)的選擇移動(dòng)法

通過(guò)將預(yù)留空間、選擇移動(dòng)兩種方法結(jié)合起來(lái)，減少關(guān)聯(lián)移動(dòng)次數(shù)，這就是帶預(yù)留表項(xiàng)的選擇移動(dòng)法的思路。如圖5所示，3～32前綴長(zhǎng)度預(yù)留相同大小的存儲(chǔ)空間。當(dāng)新增加一個(gè)表項(xiàng)時(shí)，假設(shè)其前綴長(zhǎng)度為i(3≤i≤32)，若i對(duì)應(yīng)前綴塊有空閑，則直接寫(xiě)入。若i預(yù)留空間占滿，則考慮i+1前綴塊是否未滿。如果未滿，則借i+1預(yù)留空間尾部地址寫(xiě)入表項(xiàng)；否則，按選擇移動(dòng)法的方式處理，直到為i前綴塊挪出空間寫(xiě)入新表項(xiàng)。刪除表項(xiàng)時(shí)，也要求在挪動(dòng)i前綴塊內(nèi)部被刪除表項(xiàng)以后的表項(xiàng)，以保持空閑表連續(xù)，并且僅在i前綴塊及相鄰i+1前綴塊均占滿的情況下，才挪動(dòng)表項(xiàng)，關(guān)聯(lián)移動(dòng)概率大幅降低，算法時(shí)間復(fù)雜度比選擇移動(dòng)法更小。

圖5 帶預(yù)留表項(xiàng)的選擇移動(dòng)法

3 一種改進(jìn)的帶預(yù)留表項(xiàng)的選擇移動(dòng)法及實(shí)現(xiàn)

綜合分析順序移動(dòng)法、帶預(yù)留表項(xiàng)的順序移動(dòng)法、選擇移動(dòng)法、帶預(yù)留表項(xiàng)的選擇移動(dòng)法[6,7]這幾種現(xiàn)存的TCAM管理算法，可以看出TCAM表項(xiàng)管理算法優(yōu)化主要有以下幾個(gè)方向：

（1）選擇與實(shí)際路由前綴分布最符合的預(yù)留模型；

（2）當(dāng)出現(xiàn)特定長(zhǎng)度前綴塊預(yù)留空間滿時(shí)，盡最大可能減少現(xiàn)存表項(xiàng)的移動(dòng)次數(shù)；

（3）系統(tǒng)趨穩(wěn)后，特定長(zhǎng)度前綴塊內(nèi)部表項(xiàng)新增和刪除的次數(shù)會(huì)趨于相同，可以充分利用動(dòng)態(tài)平衡的特性進(jìn)行緩存優(yōu)化。

3.1 選擇最符合的預(yù)留模型

現(xiàn)實(shí)中各種網(wǎng)絡(luò)設(shè)備側(cè)重不一樣，IP前綴長(zhǎng)度為3～32的路由表項(xiàng)分布也不一樣，比如，核心骨干網(wǎng)與邊緣接入網(wǎng)對(duì)IP地址段的使用側(cè)重就不一樣。核心骨干網(wǎng)和邊緣接入網(wǎng)節(jié)點(diǎn)IP前綴按長(zhǎng)度分布情況分別如圖6、圖7所示。邊緣接入網(wǎng)一般24～32之間網(wǎng)段需求最多，核心骨干網(wǎng)則對(duì)長(zhǎng)度8～24之間的IP前綴需求最多[8]，尤其是8，16，24位長(zhǎng)度的IP前綴需求較多。如圖6所示，在設(shè)備規(guī)劃設(shè)計(jì)階段，通過(guò)對(duì)核心骨干網(wǎng)節(jié)點(diǎn)的統(tǒng)計(jì)分析發(fā)現(xiàn)，8～24位長(zhǎng)度掩碼的占了98%，其他長(zhǎng)度掩碼的IP路由地址，總共才占2%。如圖7所示，在邊緣接入網(wǎng)節(jié)點(diǎn)對(duì)24～32位IP前綴需求最多，總計(jì)占了約80%的比例，其他長(zhǎng)度IP前綴僅占20%左右。

圖6 核心骨干節(jié)點(diǎn)IP前綴按長(zhǎng)度分布的情況

圖7 邊緣接入節(jié)點(diǎn)IP前綴按長(zhǎng)度分布的情況

結(jié)合設(shè)計(jì)，本文可以得出按掩碼長(zhǎng)度i(3≤i≤32)統(tǒng)計(jì)分布概率的模型a[i]，其中。假設(shè)TCAM容量為N，根據(jù)概率統(tǒng)計(jì)分布，可以得出掩碼長(zhǎng)度為i的預(yù)留表項(xiàng)大小為r[i]=N×a[i]。如果網(wǎng)絡(luò)無(wú)法通過(guò)設(shè)計(jì)方案得出概率分布，則可以根據(jù)分類原則，首先確定路由節(jié)點(diǎn)在網(wǎng)絡(luò)中承擔(dān)的是核心骨干、邊緣接入或者混合接入的角色，其次對(duì)相應(yīng)范圍的前綴增大權(quán)重比。此外，也可以通過(guò)抽樣分析的方法，確定最終合適的統(tǒng)計(jì)分布模型。

根據(jù)以上分析，本文可以定義出如下的數(shù)據(jù)結(jié)構(gòu)：struct route_queue[32]數(shù)組。對(duì)于任一掩碼長(zhǎng)度i對(duì)應(yīng)的預(yù)留描述結(jié)構(gòu)route_queue[i]，如圖8所示，其中total字段表示為該前綴塊預(yù)留表項(xiàng)總條數(shù)，length為當(dāng)前該前綴塊已經(jīng)使用的表項(xiàng)大小。head、tail、empty_head、empty_tail為前綴塊內(nèi)部TCAM分配管理使用的字段（下一小節(jié)予以說(shuō)明），這樣即可生成與實(shí)際情況相匹配的前綴塊預(yù)留模型。

圖8 route_queue結(jié)構(gòu)

3.2 減少現(xiàn)存表項(xiàng)移動(dòng)次數(shù)

帶預(yù)留表項(xiàng)的選擇移動(dòng)法保證IP前綴塊之間相對(duì)順序一致，但其實(shí)前綴塊內(nèi)部不需要絕對(duì)的先后存放順序。該方法還要求前綴塊內(nèi)部已使用表項(xiàng)和空閑表之間保持連續(xù)，這就會(huì)增加額外的前綴塊內(nèi)部路由集合的移動(dòng)次數(shù)。在相同長(zhǎng)度前綴塊內(nèi)部，也并非一定要讓已使用表項(xiàng)和空閑表嚴(yán)格分開(kāi)，可以通過(guò)在前綴塊內(nèi)部，增加已分配鏈表（已占用表和空閑鏈表）和空閑鏈表這兩個(gè)鏈表，將它們分別組織起來(lái)。需要說(shuō)明的是，空閑鏈表是已分配鏈表的子集。如圖9所示，index為分配的TCAM地址，use_flag表示是否占用，next、prev指針用于構(gòu)建已分配鏈表，empty_next、empty_prev用于構(gòu)建空閑鏈表，entry則是對(duì)應(yīng)具體的路由信息。按照掩碼長(zhǎng)度形成的已分配鏈表、空閑鏈表如圖10 所示。

圖9 route_node結(jié)構(gòu)

圖10 基于前綴塊長(zhǎng)度的TCAM管理雙鏈表

該管理算法添加路由表項(xiàng)的步驟如下文所述。

（1）對(duì)于掩碼長(zhǎng)度為i的新增路由，首先通過(guò)route_queue的total和length比較，判斷相對(duì)應(yīng)前綴塊是否占滿。如果未占滿，按照鏈表順序搜索空閑表項(xiàng)，即首先通過(guò)route_queue[i]的empty_head指針?biāo)阉鳌Ｈ绻軐ふ业?，那么直接添加表?xiàng)，同時(shí)將該節(jié)點(diǎn)use_flag標(biāo)示為已占用，并將該節(jié)點(diǎn)移出空閑鏈表。

（2）如果在空閑表內(nèi)未找到可使用節(jié)點(diǎn)但預(yù)留還未填滿，則在當(dāng)前掩碼長(zhǎng)度塊的預(yù)留范圍內(nèi)，創(chuàng)建新的route_node。將該節(jié)點(diǎn)關(guān)聯(lián)的TCAM地址置為tail節(jié)點(diǎn)的index+1，并加入已分配鏈表表尾，形成新的tail。

（3）如果當(dāng)前掩碼長(zhǎng)度預(yù)留范圍已占滿，則優(yōu)先向掩碼長(zhǎng)度i+1的預(yù)留地址范圍，檢查其是否存在未分配地址空間（向上擴(kuò)展）。如果存在，則直接添加表項(xiàng)，不用挪動(dòng)現(xiàn)有表項(xiàng)，僅需修正相鄰前綴塊的預(yù)留范圍和大小。

（4）如果無(wú)法向上擴(kuò)展，則開(kāi)始嘗試向下擴(kuò)展。這個(gè)時(shí)候使用帶預(yù)留表項(xiàng)的選擇移動(dòng)法挪動(dòng)表項(xiàng)，直到存在可用空閑表為止。

刪除路由時(shí)，首先直接刪除TCAM表內(nèi)容或置該項(xiàng)無(wú)效，其次通過(guò)軟件將需要?jiǎng)h除的路由節(jié)點(diǎn)use_flag置為空閑，同時(shí)將該路由節(jié)點(diǎn)加入空閑鏈表尾部，以備添加路由時(shí)使用。

通過(guò)分析可以得到以下幾點(diǎn)結(jié)論。

（1）前綴塊內(nèi)部空閑鏈表有已分配的空閑節(jié)點(diǎn)可以使用時(shí)，不需要系統(tǒng)分配新的route_node，更不需要挪動(dòng)現(xiàn)有表項(xiàng)，可以直接添加表項(xiàng)，能加快表項(xiàng)更新速度。

（2）當(dāng)空閑鏈表為空但前綴塊預(yù)留空間未滿時(shí)，僅需分配新的route_node即可添加表項(xiàng)，也不需要挪動(dòng)現(xiàn)有表項(xiàng)。

（3）當(dāng)長(zhǎng)度i前綴塊預(yù)留空間占滿時(shí)，可以優(yōu)先向i+1長(zhǎng)度前綴塊預(yù)留空間擴(kuò)充（向上擴(kuò)展）。由于前綴塊內(nèi)部?jī)?yōu)先從地址小的空間分配route_node，所以向i+1前綴塊空間擴(kuò)展大概率僅需調(diào)整相鄰前綴塊的預(yù)留參數(shù)，然后分配、添加新route_node表項(xiàng)即可，也不需要挪動(dòng)現(xiàn)有表項(xiàng)。

（4）當(dāng)i+1長(zhǎng)度的前綴塊已分配完畢（無(wú)論是否占用完），表明i+1長(zhǎng)度前綴塊存儲(chǔ)表項(xiàng)的突發(fā)峰值已經(jīng)達(dá)到預(yù)留空間大小，此時(shí)不應(yīng)當(dāng)向i+1長(zhǎng)度前綴塊借占空間。此時(shí)，考慮向i-1長(zhǎng)度前綴塊借占空間，有一定概率i-1長(zhǎng)度塊并未分配空間，此時(shí)也不用挪動(dòng)現(xiàn)有表項(xiàng)，可以直接添加route_node，并加入分配表的鏈表尾部。更多的情況是，i-1長(zhǎng)度前綴塊開(kāi)始處的空間已經(jīng)被分配，這個(gè)時(shí)候就需要考慮傳統(tǒng)的帶預(yù)留表項(xiàng)的選擇移動(dòng)法，挪動(dòng)未占用的TCAM空間，為i長(zhǎng)度前綴塊分配空間。此時(shí)，是向i長(zhǎng)度前綴塊的上方，還是下方尋找可以挪動(dòng)的空間，可以作為一個(gè)新的研究方向。

4 結(jié)語(yǔ)

本文根據(jù)具體實(shí)現(xiàn)，有針對(duì)性地優(yōu)化路由表項(xiàng)的預(yù)留模型，充分利用前綴塊內(nèi)部動(dòng)態(tài)平衡的特點(diǎn)，減少表項(xiàng)移動(dòng)的次數(shù)、降低表項(xiàng)移動(dòng)的復(fù)雜度，進(jìn)而提高表項(xiàng)更新的速度。本文研究是提高TCAM查表速度的一個(gè)研究方向。本文在分析現(xiàn)有方案的優(yōu)缺點(diǎn)之后，結(jié)合前綴塊靜態(tài)概率分布、動(dòng)態(tài)路由平衡等特點(diǎn)，提出并實(shí)現(xiàn)了基于緩存優(yōu)化的雙鏈表管理算法，對(duì)帶預(yù)留表項(xiàng)的選擇移動(dòng)法進(jìn)行了深入的優(yōu)化，并在實(shí)踐中取得了較好的效果。