一種改進(jìn)的TCAM路由表項管理算法及實現(xiàn)

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

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

0 引言

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

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

1 TCAM原理及特性分析

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

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

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

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

2 TCAM表項管理算法介紹

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

2.1 順序移動法

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

圖2 順序移動法

2.2 帶預(yù)留表項的順序移動法

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

圖3 帶預(yù)留表項的順序移動法

2.3 選擇移動法

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

圖4 選擇移動法

2.4 帶預(yù)留表項的選擇移動法

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

圖5 帶預(yù)留表項的選擇移動法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖10 基于前綴塊長度的TCAM管理雙鏈表

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

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

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

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

（4）如果無法向上擴(kuò)展，則開始嘗試向下擴(kuò)展。這個時候使用帶預(yù)留表項的選擇移動法挪動表項，直到存在可用空閑表為止。

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

通過分析可以得到以下幾點結(jié)論。

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

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

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

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

4 結(jié)語

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