一種支持TCAM規則更新與壓縮方法

蔡立軍+李杜+池鵬+李睿

收稿日期：20140113

基金項目：國家科技支撐計劃資助項目（2012BAH09B02）；長沙市重點科技計劃資助項目（K1204006111）

作者簡介：蔡立軍（1964-），男，湖南常德人，湖南大學教授，博士

通訊聯系人，Email：chipeng@189.cn

摘要：提出了一種TCAM空間劃分和規則壓縮相結合的方法，使得OpenFlow網絡在支持實時更新的同時能采用小容量的TCAM芯片來存儲網絡中的規則.所提方法將TCAM芯片空間劃分為實時更新區和壓縮存儲區，實時更新區處在TCAM芯片的前部，用于存放中央控制器發送過來的實時更新規則.后臺服務器以一定的時間周期將TCAM芯片中的實時更新區的規則以及壓縮存儲區中的規則進行壓縮，并將壓縮后的規則存入TCAM的壓縮區，保持實時更新區具有空間接收實時更新規則.分析了區間劃分的比率問題，并利用ClassBench工具產生原始規則集進行了仿真實驗，實驗結果驗證了本文方法的有效性.

關鍵詞：網絡協議；OpenFlow；TCAM；規則壓縮；實時更新；空間劃分

中圖分類號：TP393.2 文獻標識碼：A

A New Method for Rule Realtime

Updates and Compression in TCAM

CAI Lijun1，2，LI Du2，CHI Peng1，LI Rui2

（1.National Supercomputing Center in Changsha， Changsha，Hunan410082， China；

2.College of Computer Science and Electronic Engineering，Hunan Univ，Changsha，Hunan410082， China）

Abstract：This paper presented an approach which combines space division and rules compression in an effort to allow the realtime updates and TCAM chips storage happening at the same time. In the approach， the TCAM chip was divided into two partitions， a realtime update area and a compression storage area. The former was assigned in the front of the chip for storing realtime updating rules sent by the controller， and the latter had the function of compressing and storing rules generated by the server within certain time period. We made a comprehensive analysis of the space division ratio and conducted simulation experiments on the rules generated by the ClassBench tool. The experiment results have demonstrated the effectiveness of the approach.

Key words：network protocols； OpenFlow；ternary content addressable memory（TCAM）； rules compression；realtime update；space division

OpenFlow[1]是一種新型網絡交換模型，主要由OpenFlow交換機、FlowVisor和Controller三部分組成.OpenFlow交換機進行數據層的轉發，FlowVisor對網絡進行虛擬化，Controller對網絡進行集中控制，實現控制層的功能.OpenFlow技術采用集中式的控制方法，由一個或多個包含整個網絡拓撲的中心控制器通過一個開放的協議對不同交換機和路由器中的流表直接進行編程，從而實現對網絡中數據流的控制.

為了實現數據包的高速轉發，采用TCAM[2]芯片來存儲與匹配路由規則已經成為OpenFlow網絡中事實上的工業標準.TCAM是一種三態內容尋址存儲器，查詢時采用全并行的方式對所有單元的數據進行搜索，因此可以在一個時鐘周期內完成數據的匹配.TCAM芯片在具有快速查詢處理優點的同時，也存在如下不足[3]：1）存儲空間小.TCAM存儲空間相當有限，目前比較流行的TCAM芯片的內存為2 Mb或1 Mb，最大的也只有18 Mb.2）能耗高、散熱大.在進行數據查詢時，由于TCAM采用全并行方式對整個存儲空間進行搜索，因此消耗的電能大，同時散發的熱量也多.一個1 Mb的TCAM芯片的功率可以達到15～30 W，大功率消耗對于核心路由以及其他網絡設備來說是一個非常嚴重的問題，因為在機箱內需要占用更大的面積.3）價格昂貴.TCAM芯片價格相當昂貴，特別是隨著容量的增加，價格增加迅速.因此，采用小容量的TCAM芯片是解決TCAM芯片面臨問題的有效途徑.針對小容量的存儲空間，國內外研究者在規則壓縮方面開展了大量的研究工作[4-5]，但這些研究工作都是針對TCAM中規則相對穩定或者更新速度慢的情況.在OpenFlow網絡中，規則更新頻繁[6].就我們所知，目前還沒有研究工作研究如何在小容量的TCAM芯片中實現規則的實時更新.

為此，本文針對OpenFlow中規則更新頻繁的特點，提出了一種支持規則實時更新和壓縮的方法，在保證規則快速更新的同時，能夠采用小容量的TCAM芯片來存儲規則.為了同時支持快速更新以及規則壓縮，本文提出了一種對TCAM芯片存儲空間進行劃分的方法，將TCAM芯片空間劃分為實時更新規則區和壓縮規則存儲區，如圖1所示.實時更新規則區處在TCAM芯片的前部，用于存儲由中央控制器發來的最新更新規則集，壓縮規則存儲區存儲壓縮后的規則集.中央控制器持續向交換機下發規則，每隔一定的時間片段，將交換機中的規則集復制到規則處理服務器，由規則處理服務器負責對規則集采用規則壓縮算法對其進行壓縮處理，壓縮算法處理結束后服務器向TCAM芯片發出規則更新來替換TCAM更新區和壓縮區的規則.該結構一方面能夠滿足OpenFlow中的實時更新要求，另外一方面又防止控制器不斷產生的更新規則導致規則集過大而無法用容量較小的TCAM芯片來存儲的問題.

1相關工作

與本文工作最為相關的研究工作是數據包的分類以及防火墻領域的規則壓縮.文獻[5]提出了一種對一維包分類器的動態規劃算法，其一維前綴壓縮實驗數據顯示41 455條前綴的壓縮比為58%，運行時間為2.73 s.文獻[6]提出的壓縮算法總壓縮比為54%，較以往的壓縮算法在壓縮效果上已經有了部分改進，但在該文中未公布其算法運行時間.在此基礎上，文獻[3]提出了一種多維規則的壓縮算法，總的壓縮比為3.9%，壓縮效果有了大幅度的提高，但是缺點在于算法運行速度比較慢，661條規則壓縮運行時間為31.9 s.這些研究工作都是針對靜態規則集的壓縮，沒有考慮規則的實時更新問題.

OpenFlow網絡具有規則更新快的特點，僅僅考慮規則的壓縮而忽略規則的更新是沒有意義的，而目前規則壓縮的研究還未延伸到OpenFlow領域，因此本文的主要難點在于如何科學分配TCAM芯片中的實時更新區和壓縮存儲區，使得TCAM芯片既能持續不斷地接收中央控制器發出的最新規則，又能將已有規則集進行有效壓縮.

2基本概念

本節給出相關概念的定義.一個域Fi的一個區間變量，記作D（Fi），是一個非負整數的有限區間，比如[0，100].TCAM規則形式為〈predicate〉→〈decision〉，其中predicate的形式為F1∈S1∧…∧Fd∈Sd，其中每一個Si都是D（Fi）的非空子集當且僅當p1∈S1∧…pd∈Sd，一個數據包（p1，…，pd）和一條predicate匹配[7].decision指滿足匹配之后執行的指令，典型的decision包括accept，disgard，accept with logging，disgard with logging.

用f表示d個域F1，F2，…，Fd上的一個規則序列，序列個數用f表示.

當且僅當對于任意的數據包都在f中至少存在一條規則與之匹配，那么，一個規則序列f是一個完全規則序列.為了保證一個規則序列f是一個完全規則序列，f的最后一條規則通常是如下形式：F1∈D（F1）∧…∧Fd∈D（Fd）.如下所示為兩個域F1，F2上的兩條規則，其中D（F1）=D（F2）=[0，20].

r1：F1∈[0，8]∧F2∈[0，15]→accept

r2：F1∈[0，20]∧F2∈[0，20]→disgard

在一個規則序列f中可能存在這種情況，其中的兩條或者多條規則的區間部分重疊或其中一個區間包含于另一個區間，甚至兩條規則不但重疊而且具有不同的decision.為了解決這個矛盾，TCAM采用首匹配原則，也就是說一個包p的decision是p在f中匹配到的第一個規則的decision，數據包p在f中匹配的decision用f（p）表示[8].兩個規則序列f1，f2等價，當且僅當對于任意包p都有f1（p）=f2（p），記作f1≡f2.對于任意規則序列f，我們用f表示所有與f等價的規則集合.

規則的壓縮：對于一個規定的規則序列f，找到另一個語義與f等價的規則序列g， 其中g擁有盡可能少的規則數量.

壓縮比：壓縮比=壓縮后規則數/原始規則數.

3空間劃分

為了實現壓縮與更新的平衡，將TCAM芯片的存儲空間分為兩個區域：實時更新區和壓縮規則存儲區.實時更新區中存儲了由中央控制器發來的最新更新規則.TCAM芯片采用的是首匹配方式進行規則匹配，因此，實時更新區處在TCAM的前部.壓縮規則區存儲壓縮后的規則.引入規則處理服務器負責對TCAM中的規則進行處理規則集的壓縮.規則處理服務器定期向TCAM芯片發出規則更新來替換TCAM壓縮區的規則.采用該結構，一方面能滿足OpenFlow中的實時更新要求，另外一方面又防止控制器不斷產生的更新規則導致規則集過大而無法用容量較小的TCAM芯片來存儲的問題.

中央控制器持續向TCAM芯片傳輸最新的規則集，每隔一定的時間周期，將其中的規則集復制到規則壓縮處理器中進行壓縮算法處理，在算法處理過程中由中央控制器傳輸的最新規則保存在實時規則更新區，壓縮算法處理結束之后，將壓縮后的規則集替換壓縮規則存儲區中的規則集，然后將實時規則更新區中的規則集轉移至壓縮規則存儲區，如此循環進行算法處理，以達到規則實時更新以及壓縮的目的.

TCAM中規則的實時更新以及壓縮過程如圖2所示.假設TCAM芯片容量總共可以存儲S條規則，進行空間劃分之后實時更新區可以存儲α條規則，壓縮存儲區可以存儲β條規則，其中有：

α+β=S. （1）

假設后臺服務器對規則進行壓縮的時間周期為T，網絡中規則的更新速度為v 條/s，算法運行時間為t，規則壓縮算法的壓縮比為r，r<1.因此每一個時間周期內在實時更新區內更新的規則數為vT.上文已經提到，TCAM芯片采用的是首匹配原則，因此新的規則總是存放在規則集的頂端.在狀態1，實時更新區處于相對空白狀態，此時將TCAM中的規則復制到壓縮服務器，在服務器中進行壓縮算法處理.在狀態2，算法結束經過一個時間周期之后將已壓縮的規則集存放在TCAM的底部，此時實時更新區內已積累v T條規則.在狀態3，將壓縮之后的規則集與最新的更新規則組成新的規則集存放在TCAM中，重新返回狀態1，進入下一個循環.

定理1 規則的更新與壓縮機制中所運用的規則壓縮算法運行時間t須滿足：

t≤S/v. （2）

定理2更新與壓縮過程中一個時間周期T的取值范圍為：

t≤T≤S/v. （3）

證因為規則壓縮算法運行時間為t，所以必須等待t時間之后才能將壓縮后的規則集導入TCAM芯片.因為規則持續更新的速度為v，在S/v的時間段內TCAM芯片內存將占用完畢而導致沒有更多的空間存放即將接受的新規則.

證畢.

定理3當時間周期一定時，同時實現規則的更新與壓縮的必要條件為TCAM芯片的空間不小于v T （2-r）/（1-r）.

證如圖2所示，規則的更新與壓縮是一個動態的循環過程，在每一次循環中都要對β條規則進行一次壓縮處理，為了保證壓縮過程中實時更新區的規則不溢出，實時更新區所分配的空間必須滿足：

α≥vT.

壓縮算法結束之后，將已壓縮的規則集替換壓縮存儲區內的舊規則集，壓縮之后的規則集存放在壓縮存儲區的底部，同時壓縮存儲區騰出的空間為β-r β.此時將實時更新區內的最新規則轉移至壓縮存儲區的頂部，為了保證壓縮之后的規則集不占用實時更新區的空間而導致規則溢出，那么壓縮存儲區所占空間必須滿足：

vT≤β-rβ.

此時β的取值要求為：

β≥v T1-r.

因此有：

S=α+β≥vT+vT1-r=vT2-r1-r.

證畢.

在壓縮算法、時間周期以及TCAM芯片空間容量等條件得到滿足的前提下，對TCAM區間進行劃分，分析一定容量TCAM芯片內實時更新區以及壓縮存儲區所占空間的比例.

性質1當其他參數一定時，實時更新區在TCAM芯片中所需空間隨規則更新速度的增大而增大.

性質2當其他參數一定時，壓縮存儲區在TCAM芯片中所需空間隨規則壓縮比的增大而增大.

例如，當時間周期T以及規則更新速度v一定時，選擇不同的規則壓縮算法，則壓縮存儲區所占空間也會有差別.當r=0.5時，β的最小取值為2vT，當r=0.9時，β的最小取值為10 vT.

當實時更新區所占空間取最小值v T時，壓縮存儲區分配的空間為S-v T，當壓縮存儲區所占空間取最小值v T/（1-r）時，實時更新區的空間為S-v T/（1-r），由此可得TCAM芯片中實時更新區和壓縮存儲區所占空間比例的取值范圍.

引理1TCAM芯片中實時更新區和壓縮存儲區所占空間比例取值范圍為：

vTS-vT≤αβ≤S（1-r）-vTvT. （4）

證因為S≥v T （2-r）/（1-r），所以S>vT.

又由于r<1，所以有：

S（1-r）-vT（2-r）≥0

S（S-Sr+vTr-2vT）≥0.

因此有：

S2（1-r）-SvT（1-r）-SvT+（vT）2-（vT）2vT（S-vT）≥0

[S（1-r）-v] （S-vT）-（vT）2vT（S-vT）≥0

S（1-r）-vTvT-vTS-vT≥0.

證畢.

4規則壓縮算法

本文設計一種適用于快速更新的動態規則壓縮算法，主要思想為在不改變規則集語義的前提下將規則集轉換為一個等價的BDD[9]，再將實時更新的規則集嵌入改變縮減之后的BDD，最后將BDD轉換為等價的規則集以減少規則集中的規則數量從而達到壓縮規則的目的.將更新與壓縮兩種操作結合在一起，不僅能夠滿足網絡中快速更新規則的需要，而且可以提高規則集的壓縮效率.

一個二叉決策圖Binary Dicesion Diagram（BDD）是有限個節點的有向無環圖G=（V，E），其中，V是G中所有節點的集合，E是G中所有邊的集合.其中一個BDD滿足如下4個條件：

1）存在一個decision集合DS；

2）存在一個根節點，其不存在父節點，存在若干葉子節點，其不存在子節點；

3）每一個葉子節點對應一個decision，記為D（v）；

4）一條從根節點到decision的路徑對應規則集中的一條或多條規則.

如圖3所示為規則集轉換為BDD的示意圖.其中D（F1）=D（F2）=[0，15]，并用a表示accept，用d表示disgard.根據規則集的特點在每一個節點處每一個域進行二分，直到所有的規則都包含于BDD中.

r1：F1∈[0，7]∧F2∈[0，7]→accept

r2：F1∈[0，7]∧F2∈[11，15]→disgard

r3：F1∈[8，15]∧F2∈[0，7]→accept

r4：F1∈[8，15]∧F2∈[10，12]→disgard

r5：F1∈[8，15]∧F2∈[13，15]→disgard

對于一個已轉換的BDD進行改編縮減.在這里提出BDD規則壓縮算法.

算法1BDDCompress（node）.

輸入：原始BDDg1； 輸出：縮減后的BDDg.

步驟：

1）當node為葉子節點且node的父節點不為空那么Setnode（node=node->pre）；

2）BDDCompress （node）

{

以node為根節點到葉子節點的任意兩條路徑R1，R2，若R2包含于R1，且其葉子節點在樹中的位置相對R1的葉子節點位置靠右，則移除R2所對應的葉子節點；

以node為根節點的樹中任意兩條從根節點到葉子節點的路徑有且僅有一條邊相連或相交且葉子節點所對應的decision相同，則將該兩條路徑的葉子節點合并；

Setnode（node=node->pre）；

BDDCompress （node）；

本文的壓縮策略是在規則快速更新的OpenFlow網絡中，將實時的更新規則嵌入已有的壓縮BDD，嵌入的過程完成冗余規則的去除以及特定規則的合并，最后將BDD轉換為等價的規則集.

對于一個網絡中實時更新的規則集f，本文的動態規則壓縮算法分為如下3個步驟：

1）將規則集f轉換成一個等價的BDDf1；

2）將f1嵌入已有的壓縮BDD；

3）將合并后的BDD轉換為等價的規則集.

在這里提出BDD動態規則壓縮算法.

算法2BDDInsert（f，g）.

輸入：原始BDDg；更新規則集f；

輸出：縮減后的BDDg1；

步驟：

1）將f轉換為等價的BDDf1；

2）對f1中的每一條從葉子節點到根節點的路徑與g1中從葉子節點到根節點的路徑匹配

{

移除g1中包含于f1中的路徑所對應的葉子節點，并將f1中對應的路徑添加到g1；

若兩條路徑有且僅有一條邊相連或相交且葉子節點所對應的decision相同，則將該兩條路徑的葉子節點合并；

否則將該路徑添加到g1；

}

每隔一個時間周期T后臺服務器調用算法2對更新的規則集進行壓縮處理.假設網絡中更新了如下2條規則：

r1：F1∈[0，7]∧F2∈[9，15]→disgard

r2：F1∈[8，15]∧F2∈[8，13]→accept

轉換后的BDD如圖5所示.

BDD中的每一個decision都對應一條規則，該規則由一條或多條路徑合并而成.從decision開始尋找其父節點直到根節點，若某個decision所對應的葉子節點只存在一個父節點，那么從其到根節點的路徑唯一，且對應一條或多條壓縮后的規則；若某個decision存在多個父節點，那么從其到跟節點的路徑中必然存在可以合并的兩條或多條路徑，此時對其各路徑進行判斷并對滿足條件的邊進行合并.圖4所示BDD中dicesion1只有一個父節點，因此從其到根節點的路徑唯一，對應的規則為：r1：F1∈[0，7]∧F2∈[8，15]→disgard.dicesion2存在2個父節點node2，node3，將node1至node2的邊和node1至node3的邊所對應的區間合并得到規則：r2：F1∈[0，15]∧F2∈[0，7]→accept.圖4所示BDD轉換為規則集如下：

r1：F1∈[0，7]∧F2∈[8，15]→disgard

r2：F1∈[0，15]∧F2∈[0，7]→accept

r3：F1∈[8，15]∧F2∈[10，15]→disgard

假設壓縮服務器中規則集的規則數目為n，實時更新的規則數目為k，由于算法需要先將規則集轉換為等價的BDD，且BDD中的每一個葉子節點對應一條規則，而調用BDD動態規則壓縮算法時需要將更新BDD中的每一條從根節點到葉子節點的路徑與壓縮BDD中的每一條從根節點到葉子節點的路徑匹配，因此BDD動態規則壓縮算法的時間復雜度為O（kn）.這種動態更新與壓縮的算法避免了每一次規則更新之后都將壓縮服務器中的規則集與更新的規則集重新進行一次壓縮算法處理，節約了運行時間，提高了規則壓縮的效率.

5實驗

網絡中的實際規則集由于安全保密等原因很難獲得，因此本文中實驗用的規則集利用華盛頓大學圣路易斯分校Taylor和Turner開發的工具ClassBench產生.ClassBench產生的規則集中的每條規則包含了6個域：源IP地址、目的IP地址、源端口、目的端口、協議類型和標志域.其中源IP地址和目的IP地址以前綴表示，源端口和目的端口以范圍表示，協議類型和標志域以某種精確數據類型表示.實驗過程首先利用ClassBench生成若干條規則，然后利用正則表達式從規則集中截取源端口和目的端口作為實驗源數據生成二維規則集，最后對二維規則集進行仿真實驗，其中每條規則域的區間為[0，65 535].因為ClassBench工具產生的規則不包含decision項，所以在仿真實驗時每一條規則都隨機產生一個decision，其中設置decision僅包含accept和disgard.圖7為ClassBench生成的5條規則組成的規則集.

圖8為算法1對20組從50～1 000條不同數量的規則所組成的規則集進行壓縮處理的實驗數據圖，從圖8可以看出，壓縮算法具有較高的壓縮比，1 000條規則的壓縮比接近30%.

實驗過程中利用ClassBench工具產生100 000條規則作為原始規則集，以不同的更新速度向仿真TCAM容器內傳輸規則集，利用上述規則壓縮算法對規則進行周期性壓縮，對規則更新速度v、仿真容器容量S、時間周期T等參數進行設置，并以上文的理論為依據對仿真TCAM容器進行區間劃分，采用BDD動態規則壓縮算法對壓縮處理器中的實時更新規則進行壓縮并實時記錄容器規則數量的變化.實驗采用java在PC機上（Inter Core2 雙核CPU，2.53 GHz，2 GB內存）實現.

圖9和圖10分別為仿真容器容量S取值800和1 500時對于不同的規則更新速度選取不同的壓縮周期并對其進行區間劃分后仿真容器內規則數目變化的情況展示.以圖9為例，當S=800，v=10時，規則平均壓縮比約為r=0.5，壓縮算法運行時間t<5，根據不等式（3）可得時間周期T的取值范圍為 5≤T≤80，因此可取時間周期T為20，又因為.

因此仿真容器容量的大小滿足所需條件，根據不等式（4）可得仿真TCAM芯片中實時更新區和壓縮存儲區所占空間比例取值范圍為：

1∶3≤α∶β≤1∶1.

在實驗中取α∶β=3∶5，從實驗結果可以看出，在一個時間周期內，仿真容器中的規則呈線性增長，而每隔一個時間周期，仿真容器中的規則就會被壓縮一次，最終容器內的規則在一定范圍內波動.

6結束語

本文針對OpenFlow網絡中規則需要進行實時更新以及TCAM芯片容量受限等問題，提出了一種對TCAM區間進行劃分和規則壓縮的方法.為了驗證規則壓縮算法的效果和效率，采用ClassBench工具產生原始規則集，并對不同的規則更新速度根據論文的理論基礎對仿真TCAM容器進行區間劃分，實驗采用java在PC機上實現.實驗結果證明本文提出的壓縮與更新的平衡機制能夠很好的對快速更新的規則進行實時動態壓縮.

參考文獻

[1]KEMPF J， BELLAGAMBA E， JOCHA D. Scalable fault management for OpenFlow [C]//Communications （ICC）， 2012 IEEE International Conference on. Ottawa， ON： IEEE， 2012：6606-6610.

[2]BREMLERBARR A， HENDLER D. Spaceefficient TCAMbased classification using gray coding[J]. Computers， IEEE Transactions on， 2012：18-30.

[3]CHAD R M，ALEX X L， ERIC T. TCAM razor：a systematic approach towards minimizing packet classifiers in TCAMS [C]//Network Protocols，ICNP 2007，IEEE International Conference on.Beijing： IEEE， 2007：266-275.

[4]TAYLOR D E，TURNER J S.Class bench：a packet classification benchmark[C]//Association for Computing Machinery， Networking， IEEE/ACM Transactions on. Miami： IEEE， 2005：2068-2079.

[5]DONG Qunfeng，BANERJEE S，WANG Jia.Packet classifiers in ternary CAMs can be smaller [C]// SIGMETRICS '06/Performance '06 Proceedings of the Joint International Conference on. New York： ACM， 2006：311-322.

[6]DELY P，KASSLER A，BAYER N.OpenFlow for wireless mesh networks [C]// Computer Communications and Networks （ICCCN）， 2011 Proceedings of 20th International Conference on. Maui： IEEE， 2011：1-6.

[7]朱國勝，余少華. 基于TCAM的范圍匹配方法——CTCAM [J]. 通信學報，2012，33（1）：31-37.

ZHU Guosheng， YU Shaohua. Range matching method based on TCAM：CTCAM[J].Journal on Communications， 2012， 33（1）： 31-37. （In Chinese）

[8]YAN S， KIM M S. Treebased minimization of TCAM entries for packet classificaion[C]//Consumer Communications and Networking Conference（CCNC）， 2010 7th IEEE. Las Vegas： IEEE， 2010：1-5.

[9]CHAD R M， LIU A X， TORNG E.Topological transformation approaches to optimizing TCAM-based classification systems[C]// SIGMETRICS '09 Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2009：73-84.

1∶3≤α∶β≤1∶1.

在實驗中取α∶β=3∶5，從實驗結果可以看出，在一個時間周期內，仿真容器中的規則呈線性增長，而每隔一個時間周期，仿真容器中的規則就會被壓縮一次，最終容器內的規則在一定范圍內波動.

6結束語

本文針對OpenFlow網絡中規則需要進行實時更新以及TCAM芯片容量受限等問題，提出了一種對TCAM區間進行劃分和規則壓縮的方法.為了驗證規則壓縮算法的效果和效率，采用ClassBench工具產生原始規則集，并對不同的規則更新速度根據論文的理論基礎對仿真TCAM容器進行區間劃分，實驗采用java在PC機上實現.實驗結果證明本文提出的壓縮與更新的平衡機制能夠很好的對快速更新的規則進行實時動態壓縮.

參考文獻

[1]KEMPF J， BELLAGAMBA E， JOCHA D. Scalable fault management for OpenFlow [C]//Communications （ICC）， 2012 IEEE International Conference on. Ottawa， ON： IEEE， 2012：6606-6610.

[2]BREMLERBARR A， HENDLER D. Spaceefficient TCAMbased classification using gray coding[J]. Computers， IEEE Transactions on， 2012：18-30.

[3]CHAD R M，ALEX X L， ERIC T. TCAM razor：a systematic approach towards minimizing packet classifiers in TCAMS [C]//Network Protocols，ICNP 2007，IEEE International Conference on.Beijing： IEEE， 2007：266-275.

[4]TAYLOR D E，TURNER J S.Class bench：a packet classification benchmark[C]//Association for Computing Machinery， Networking， IEEE/ACM Transactions on. Miami： IEEE， 2005：2068-2079.

[5]DONG Qunfeng，BANERJEE S，WANG Jia.Packet classifiers in ternary CAMs can be smaller [C]// SIGMETRICS '06/Performance '06 Proceedings of the Joint International Conference on. New York： ACM， 2006：311-322.

[6]DELY P，KASSLER A，BAYER N.OpenFlow for wireless mesh networks [C]// Computer Communications and Networks （ICCCN）， 2011 Proceedings of 20th International Conference on. Maui： IEEE， 2011：1-6.

[7]朱國勝，余少華. 基于TCAM的范圍匹配方法——CTCAM [J]. 通信學報，2012，33（1）：31-37.

ZHU Guosheng， YU Shaohua. Range matching method based on TCAM：CTCAM[J].Journal on Communications， 2012， 33（1）： 31-37. （In Chinese）

[8]YAN S， KIM M S. Treebased minimization of TCAM entries for packet classificaion[C]//Consumer Communications and Networking Conference（CCNC）， 2010 7th IEEE. Las Vegas： IEEE， 2010：1-5.

[9]CHAD R M， LIU A X， TORNG E.Topological transformation approaches to optimizing TCAM-based classification systems[C]// SIGMETRICS '09 Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2009：73-84.

1∶3≤α∶β≤1∶1.

在實驗中取α∶β=3∶5，從實驗結果可以看出，在一個時間周期內，仿真容器中的規則呈線性增長，而每隔一個時間周期，仿真容器中的規則就會被壓縮一次，最終容器內的規則在一定范圍內波動.

6結束語

本文針對OpenFlow網絡中規則需要進行實時更新以及TCAM芯片容量受限等問題，提出了一種對TCAM區間進行劃分和規則壓縮的方法.為了驗證規則壓縮算法的效果和效率，采用ClassBench工具產生原始規則集，并對不同的規則更新速度根據論文的理論基礎對仿真TCAM容器進行區間劃分，實驗采用java在PC機上實現.實驗結果證明本文提出的壓縮與更新的平衡機制能夠很好的對快速更新的規則進行實時動態壓縮.

參考文獻

[1]KEMPF J， BELLAGAMBA E， JOCHA D. Scalable fault management for OpenFlow [C]//Communications （ICC）， 2012 IEEE International Conference on. Ottawa， ON： IEEE， 2012：6606-6610.

[2]BREMLERBARR A， HENDLER D. Spaceefficient TCAMbased classification using gray coding[J]. Computers， IEEE Transactions on， 2012：18-30.

[3]CHAD R M，ALEX X L， ERIC T. TCAM razor：a systematic approach towards minimizing packet classifiers in TCAMS [C]//Network Protocols，ICNP 2007，IEEE International Conference on.Beijing： IEEE， 2007：266-275.

[4]TAYLOR D E，TURNER J S.Class bench：a packet classification benchmark[C]//Association for Computing Machinery， Networking， IEEE/ACM Transactions on. Miami： IEEE， 2005：2068-2079.

[5]DONG Qunfeng，BANERJEE S，WANG Jia.Packet classifiers in ternary CAMs can be smaller [C]// SIGMETRICS '06/Performance '06 Proceedings of the Joint International Conference on. New York： ACM， 2006：311-322.

[6]DELY P，KASSLER A，BAYER N.OpenFlow for wireless mesh networks [C]// Computer Communications and Networks （ICCCN）， 2011 Proceedings of 20th International Conference on. Maui： IEEE， 2011：1-6.

[7]朱國勝，余少華. 基于TCAM的范圍匹配方法——CTCAM [J]. 通信學報，2012，33（1）：31-37.

ZHU Guosheng， YU Shaohua. Range matching method based on TCAM：CTCAM[J].Journal on Communications， 2012， 33（1）： 31-37. （In Chinese）

[8]YAN S， KIM M S. Treebased minimization of TCAM entries for packet classificaion[C]//Consumer Communications and Networking Conference（CCNC）， 2010 7th IEEE. Las Vegas： IEEE， 2010：1-5.

[9]CHAD R M， LIU A X， TORNG E.Topological transformation approaches to optimizing TCAM-based classification systems[C]// SIGMETRICS '09 Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2009：73-84.