一種支持TCAM規(guī)則更新與壓縮方法＊

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

（1.國家超級計算長沙中心，湖南 長沙 410082；2.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082）

一種支持TCAM規(guī)則更新與壓縮方法＊

蔡立軍1，2，李 杜2，池 鵬1?，李 睿2

（1.國家超級計算長沙中心，湖南 長沙 410082；2.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082）

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

網(wǎng)絡(luò)協(xié)議；OpenFlow；TCAM；規(guī)則壓縮；實時更新；空間劃分

OpenFlow［1］是一種新型網(wǎng)絡(luò)交換模型，主要由OpenFlow交換機(jī)、FlowVisor和Controller三部分組成.OpenFlow交換機(jī)進(jìn)行數(shù)據(jù)層的轉(zhuǎn)發(fā)，F(xiàn)lowVisor對網(wǎng)絡(luò)進(jìn)行虛擬化，Controller對網(wǎng)絡(luò)進(jìn)行集中控制，實現(xiàn)控制層的功能.OpenFlow技術(shù)采用集中式的控制方法，由一個或多個包含整個網(wǎng)絡(luò)拓?fù)涞闹行目刂破魍ㄟ^一個開放的協(xié)議對不同交換機(jī)和路由器中的流表直接進(jìn)行編程，從而實現(xiàn)對網(wǎng)絡(luò)中數(shù)據(jù)流的控制.

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

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

圖1 實時更新與壓縮Fig.1 Real-time updates and compression

1 相關(guān)工作

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

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

2 基本概念

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

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

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

壓縮比：壓縮比＝壓縮后規(guī)則數(shù)／原始規(guī)則數(shù).

3 空間劃分

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

中央控制器持續(xù)向TCAM芯片傳輸最新的規(guī)則集，每隔一定的時間周期，將其中的規(guī)則集復(fù)制到規(guī)則壓縮處理器中進(jìn)行壓縮算法處理，在算法處理過程中由中央控制器傳輸?shù)淖钚乱?guī)則保存在實時規(guī)則更新區(qū)，壓縮算法處理結(jié)束之后，將壓縮后的規(guī)則集替換壓縮規(guī)則存儲區(qū)中的規(guī)則集，然后將實時規(guī)則更新區(qū)中的規(guī)則集轉(zhuǎn)移至壓縮規(guī)則存儲區(qū)，如此循環(huán)進(jìn)行算法處理，以達(dá)到規(guī)則實時更新以及壓縮的目的.

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

圖2 TCAM芯片狀態(tài)Fig.2 TCAM chip status

假設(shè)后臺服務(wù)器對規(guī)則進(jìn)行壓縮的時間周期為T，網(wǎng)絡(luò)中規(guī)則的更新速度為v條／s，算法運行時間為t，規(guī)則壓縮算法的壓縮比為r，r＜1.因此每一個時間周期內(nèi)在實時更新區(qū)內(nèi)更新的規(guī)則數(shù)為vT.上文已經(jīng)提到，TCAM芯片采用的是首匹配原則，因此新的規(guī)則總是存放在規(guī)則集的頂端.在狀態(tài)1，實時更新區(qū)處于相對空白狀態(tài)，此時將TCAM中的規(guī)則復(fù)制到壓縮服務(wù)器，在服務(wù)器中進(jìn)行壓縮算法處理.在狀態(tài)2，算法結(jié)束經(jīng)過一個時間周期之后將已壓縮的規(guī)則集存放在TCAM的底部，此時實時更新區(qū)內(nèi)已積累v T條規(guī)則.在狀態(tài)3，將壓縮之后的規(guī)則集與最新的更新規(guī)則組成新的規(guī)則集存放在TCAM中，重新返回狀態(tài)1，進(jìn)入下一個循環(huán).

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

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

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

證畢.

定理3 當(dāng)時間周期一定時，同時實現(xiàn)規(guī)則的更新與壓縮的必要條件為TCAM芯片的空間不小于v T （2－r）／（1－r）.

證 如圖2所示，規(guī)則的更新與壓縮是一個動態(tài)的循環(huán)過程，在每一次循環(huán)中都要對β條規(guī)則進(jìn)行一次壓縮處理，為了保證壓縮過程中實時更新區(qū)的規(guī)則不溢出，實時更新區(qū)所分配的空間必須滿足：

α≥vT.

壓縮算法結(jié)束之后，將已壓縮的規(guī)則集替換壓縮存儲區(qū)內(nèi)的舊規(guī)則集，壓縮之后的規(guī)則集存放在壓縮存儲區(qū)的底部，同時壓縮存儲區(qū)騰出的空間為β－rβ.此時將實時更新區(qū)內(nèi)的最新規(guī)則轉(zhuǎn)移至壓縮存儲區(qū)的頂部，為了保證壓縮之后的規(guī)則集不占用實時更新區(qū)的空間而導(dǎo)致規(guī)則溢出，那么壓縮存儲區(qū)所占空間必須滿足：

證畢.

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

性質(zhì)1 當(dāng)其他參數(shù)一定時，實時更新區(qū)在TCAM芯片中所需空間隨規(guī)則更新速度的增大而增大.

性質(zhì)2 當(dāng)其他參數(shù)一定時，壓縮存儲區(qū)在TCAM芯片中所需空間隨規(guī)則壓縮比的增大而增大.

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

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

新媒體信息傳播的量更大，在新聞中可以涵蓋圖片、音頻、視頻等多種信息資源。同時，新媒體時代相關(guān)的信息鏈接可以隨意打開，這是傳統(tǒng)的報紙行業(yè)無法做到的。最后，信息互動性更強(qiáng)。互動性是新媒體時代信息傳播的典型特點。在這種形勢下，信息傳播主體和客體之間的界限不再明顯，人們不僅是新聞內(nèi)容的傳播者，同時也是信息的發(fā)布和評論者，在互動交流的共同影響下形成了新的信息傳播模式。新媒體時代人們對新聞的閱讀興趣大大提高，可以根據(jù)自身需要選擇個性化的信息服務(wù)。不僅如此，新聞信息更加生活化和平民化，這勢必會對傳統(tǒng)報紙行業(yè)產(chǎn)生非常重大的影響。

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

4 規(guī)則壓縮算法

本文設(shè)計一種適用于快速更新的動態(tài)規(guī)則壓縮算法，主要思想為在不改變規(guī)則集語義的前提下將規(guī)則集轉(zhuǎn)換為一個等價的BDD［9］，再將實時更新的規(guī)則集嵌入改變縮減之后的BDD，最后將BDD轉(zhuǎn)換為等價的規(guī)則集以減少規(guī)則集中的規(guī)則數(shù)量從而達(dá)到壓縮規(guī)則的目的.將更新與壓縮兩種操作結(jié)合在一起，不僅能夠滿足網(wǎng)絡(luò)中快速更新規(guī)則的需要，而且可以提高規(guī)則集的壓縮效率.

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

1）存在一個decision集合DS；

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

3）每一個葉子節(jié)點對應(yīng)一個decision，記為D（v）；

4）一條從根節(jié)點到decision的路徑對應(yīng)規(guī)則集中的一條或多條規(guī)則.

圖3 BDD示意圖Fig.3 A binary decision digram

對于一個已轉(zhuǎn)換的BDD進(jìn)行改編縮減.在這里提出BDD規(guī)則壓縮算法.

算法1 BDDCompress（node）.

圖4為改編縮減后的BDD，其語義與圖3等價.

圖4 壓縮后的BDDFig.4 A reduced binary decision diagram

本文的壓縮策略是在規(guī)則快速更新的Open－Flow網(wǎng)絡(luò)中，將實時的更新規(guī)則嵌入已有的壓縮BDD，嵌入的過程完成冗余規(guī)則的去除以及特定規(guī)則的合并，最后將BDD轉(zhuǎn)換為等價的規(guī)則集.

對于一個網(wǎng)絡(luò)中實時更新的規(guī)則集f，本文的動態(tài)規(guī)則壓縮算法分為如下3個步驟：

轉(zhuǎn)換后的BDD如圖5所示.

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

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

圖5 轉(zhuǎn)換后的BDDFig.5 Converted BDD

將圖5中的BDD嵌入圖4的BDD中，得到新的BDD如圖6所示.

圖6 規(guī)則壓縮算法實驗結(jié)果Fig.6 Rules compression algorithm results

5 實 驗

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

圖7 ClassBench工具生成的規(guī)則Fig.7 Rules producesd by ClassBench

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

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

圖8 規(guī)則壓縮算法實驗結(jié)果Fig.8 Rules compression algorithm results

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

圖9 S＝800時規(guī)則數(shù)量變化Fig.9 Number of rules changes when S＝800

圖10 S＝1 500時規(guī)則數(shù)量變化Fig.10 Number of rules changes when S＝1 500

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

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

6 結(jié)束語

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

［1］ KEMPF J，BELLAGAMBA E，JOCHA D.Scalable fault management for OpenFlow［C］／／Communications（ICC），2012IEEE International Conference on.Ottawa，ON：IEEE，2012：6606－6610.

［2］ BREMLER-BARR A，HENDLER D.Space-efficient TCAM-based 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：apacket classification benchmark［C］／／Association for Computing Machinery，Networking，IEEE／ACM Transactions on.Miami：IEEE，2005：2068－2079.

［5］ DONG Qun-feng，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），2011Proceedings of 20th International Conference on.Maui：IEEE，2011：1－6.

［7］ 朱國勝，余少華.基于TCAM的范圍匹配方法——C-TCAM ［J］.通信學(xué)報，2012，33（1）：31－37.

ZHU Guo-sheng，YU Shao-hua.Range matching method based on TCAM：C-TCAM［J］.Journal on Communications，2012，33（1）：31－37.（In Chinese）

［8］ YAN S，KIM M S.Tree-based 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＇09Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems.New York：ACM，2009：73－84.

A New Method for Rule Real-time Updates and Compression in TCAM

CAI Li-jun1，2，LI Du2，CHI Peng1?，LI Rui2
（1.National Supercomputing Center in Changsha，Changsha，Hunan 410082，China；2.College of Computer Science and Electronic Engineering，Hunan Univ，Changsha，Hunan 410082，China）

This paper presented an approach which combines space division and rules compression in an effort to allow the real-time updates and TCAM chips storage happening at the same time.In the approach，the TCAM chip was divided into two partitions，a real-time update area and a compression storage area.The former was assigned in the front of the chip for storing real-time 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.

network protocols；OpenFlow；ternary content addressable memory（TCAM）；rules compression；real-time update；space division

TP393.2

A

1674-2974（2014）08-0094-07

2014-01-13

國家科技支撐計劃資助項目（2012BAH09B02）；長沙市重點科技計劃資助項目（K1204006-11-1）

蔡立軍（1964－），男，湖南常德人，湖南大學(xué)教授，博士

?通訊聯(lián)系人，E-mail：chipeng＠189.cn