[發明專利]TCAM表項的壓縮方法

有效

• 申請號: 201010252194.6
• 申請日: 2010-08-12
• 公開（公告）號: CN102375820A
• 公開（公告）日: 2012-03-14
• 發明（設計）人: 陳玉強
• 申請（專利權）人: 盛科網絡(蘇州)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L12/46
• 代理公司: 蘇州威世朋知識產權代理事務所(普通合伙) 32235
• 代理人: 楊林潔

【技術領域】

本發明涉及一種TCAM(Ternary?Content?Addressable?Memory，三態內容尋址寄存器)表項的壓縮方法，屬于互聯網數據通信內容壓縮領域。

【背景技術】

隨著互聯網的高速發展，網絡中節點數目大幅度增長，對路由器接口速率的要求也越來越高，例如支持10G速率的路由器，單包轉發處理時間已經要求小于50納秒，軟件路由查找機制顯然已不能滿足線速轉發要求。由于三態內容可尋址寄存器(TCAM)查表速度快，且解決了CIDR最長前綴匹配的問題，已成為業界目前常用的硬件解決方案。

TCAM的每個單元位可以賦予3個邏輯態：0、1或者x，其中x代表一個不確定位，可以起到掩碼的作用，這個掩碼使得TCAM可以存儲那些包含有通配符的規則。TCAM另外一個優點是它所保存的表項可以實現長度靈活配置，結合掩碼的應用可以在同一個TCAM芯片中保存任意長度的關鍵字表項，因此，TCAM非常適用于最長前綴路由的查找。

但是，由于TCAM對路由表項存放的有序性要求，使其表項管理較為復雜。若表項更新時間過長，必然影響查表速度，非常容易引起處理隊列阻塞甚至丟包，嚴重影響路由器的性能，也提高了路由器設計的難度，如對緩存容量提出更高的要求等。

與本發明相關的現有技術請參閱2005年3月2日公告的中國發明專利第CN1191520C號，該專利揭示了一種把都基于樹結構的路由壓縮以及建立在把TCAM芯片內的空間劃分為N個子空間的前綴鏈約束基礎上的前綴更新這兩個步驟前后合在一起的TCAM高速更新方法，其中，判斷前綴是否需要更新的原則是該節點是否冗余，冗余則不更新，反之，則更新。

然而，現有技術所揭示的方案適用于具有前綴的路由表項的壓縮，卻不適合于不具有前綴的非路由的普通TCAM表項的壓縮。例如，在虛擬私有局域網服務(VPLS)和虛擬專線服務(VPWS)應用中，一個端口可以支持多個虛擬局域網(VLAN)的綁定。這種綁定方式稱為捆綁(bundle)，它是MEF(Metro?Ethernet?Forum)城域以太網論壇定義的一種綁定方式。在此種應用下，系統中存在大量的不具有前綴的表項，它們的源端口相同，VLAN不同，而處理相同?，F有技術并不適合于此類表項的壓縮。

【發明內容】

本發明所要解決的技術問題在于提供一種能夠處理沒有前綴且只有一個變值元素的TCAM(Ternary?Content?Addressable?Memory，三態內容尋址寄存器)表項的壓縮方法。

為解決上述技術問題，本發明采用如下技術方案：一種TCAM表項的壓縮方法，其特征在于包括如下步驟：

(1).首先把一組沒有前綴且只有一個變值元素的TCAM表項，劃分為變值元素數值連續的段；

(2).對于數值連續的段，系統先找出段內可以馬上進行掩碼壓縮的規則子段進行直接壓縮；而對段內不能立即壓縮的非規則子段，系統首先找出此類段公共數值，然后再進行壓縮。

作為本發明的進一步改進，在添加新表項的步驟中，包括如下過程：(a).確定元素值；(b).判斷該元素值是否不屬于任何段，如果屬于，結束；如果不屬于，進行下一步；(c).判斷元素值是否在某段的邊緣，如果不在，就創建新段，其start和end分別為元素值；如果在，進行下一步；(d).判斷元素值是否在某兩段的邊緣，如果不在，把元素值合并入步驟(c)中的該某段，如果在，把該兩段合并成一段；(e).結束。

作為本發明的進一步改進，在刪除表項的步驟中，包括如下過程：(a).確定刪除表項的元素值；(b).判斷元素值是否屬于某段，如果不屬于，結束；如果屬于，進行下一步；(c).判斷元素值是否在某段的邊緣，如果不在，就創建兩個新段，范圍分別為start～元素值-1，元素值+1～end；如果在，進行下一步；(d).更新步驟(c)中的該某段；(e).結束。

作為本發明的進一步改進，規則子段的壓縮包括如下過程：(a).壓縮規則子段段(start～end)；(b).保存公共數值；(c).得到規則子段壓縮后的數據和掩碼；(d).對新段(start～end)繼續壓縮。

作為本發明的進一步改進，非規則子段的壓縮包括如下過程：(a).壓縮非規則子段段(start～end)；(b).保存公共數值；(c).得到規則子段壓縮后的數據和掩碼；(d).對新段(start～end)繼續壓縮；(e).提取段公共數值，繼續壓縮，直至非規則子段不能壓縮為止。

作為本發明的進一步改進，所述步驟(1)與步驟(2)之間還包括一個通過采用添加新表項或者刪除表項的方式對段進行維護的步驟。