一種改進的TCAM路由表項管理算法及實現

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

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

0 引言

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

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

1 TCAM原理及特性分析

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

圖1 TCAM最長匹配規則

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

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

2 TCAM表項管理算法介紹

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

2.1 順序移動法

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

圖2 順序移動法

2.2 帶預留表項的順序移動法

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

圖3 帶預留表項的順序移動法

2.3 選擇移動法

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

圖4 選擇移動法

2.4 帶預留表項的選擇移動法

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

圖5 帶預留表項的選擇移動法

3 一種改進的帶預留表項的選擇移動法及實現

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

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

（2）當出現特定長度前綴塊預留空間滿時，盡最大可能減少現存表項的移動次數；

（3）系統趨穩后，特定長度前綴塊內部表項新增和刪除的次數會趨于相同，可以充分利用動態平衡的特性進行緩存優化。

3.1 選擇最符合的預留模型

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

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

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

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

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

圖8 route_queue結構

3.2 減少現存表項移動次數

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

圖9 route_node結構

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

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

（1）對于掩碼長度為i的新增路由，首先通過route_queue的total和length比較，判斷相對應前綴塊是否占滿。如果未占滿，按照鏈表順序搜索空閑表項，即首先通過route_queue[i]的empty_head指針搜索。如果能尋找到，那么直接添加表項，同時將該節點use_flag標示為已占用，并將該節點移出空閑鏈表。

（2）如果在空閑表內未找到可使用節點但預留還未填滿，則在當前掩碼長度塊的預留范圍內，創建新的route_node。將該節點關聯的TCAM地址置為tail節點的index+1，并加入已分配鏈表表尾，形成新的tail。

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

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

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

通過分析可以得到以下幾點結論。

（1）前綴塊內部空閑鏈表有已分配的空閑節點可以使用時，不需要系統分配新的route_node，更不需要挪動現有表項，可以直接添加表項，能加快表項更新速度。

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

（3）當長度i前綴塊預留空間占滿時，可以優先向i+1長度前綴塊預留空間擴充（向上擴展）。由于前綴塊內部優先從地址小的空間分配route_node，所以向i+1前綴塊空間擴展大概率僅需調整相鄰前綴塊的預留參數，然后分配、添加新route_node表項即可，也不需要挪動現有表項。

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

4 結語

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