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

收稿日期：20140113

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

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

通訊聯(lián)系人，Email：chipeng@189.cn

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

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

中圖分類號：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]是一種新型網(wǎng)絡交換模型，主要由OpenFlow交換機、FlowVisor和Controller三部分組成.OpenFlow交換機進行數(shù)據(jù)層的轉(zhuǎn)發(fā)，F(xiàn)lowVisor對網(wǎng)絡進行虛擬化，Controller對網(wǎng)絡進行集中控制，實現(xiàn)控制層的功能.OpenFlow技術采用集中式的控制方法，由一個或多個包含整個網(wǎng)絡拓撲的中心控制器通過一個開放的協(xié)議對不同交換機和路由器中的流表直接進行編程，從而實現(xiàn)對網(wǎng)絡中數(shù)據(jù)流的控制.

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

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

1相關工作

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

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

2基本概念

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

用f表示d個域F1，F(xiàn)2，…，F(xiàn)d上的一個規(guī)則序列，序列個數(shù)用f表示.

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

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

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

在一個規(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等價，當且僅當對于任意包p都有f1（p）=f2（p），記作f1≡f2.對于任意規(guī)則序列f，我們用f表示所有與f等價的規(guī)則集合.

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

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

3空間劃分

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

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

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

α+β=S. （1）

假設后臺服務器對規(guī)則進行壓縮的時間周期為T，網(wǎng)絡中規(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ī)則復制到壓縮服務器，在服務器中進行壓縮算法處理.在狀態(tài)2，算法結(jié)束經(jīng)過一個時間周期之后將已壓縮的規(guī)則集存放在TCAM的底部，此時實時更新區(qū)內(nèi)已積累v T條規(guī)則.在狀態(tài)3，將壓縮之后的規(guī)則集與最新的更新規(guī)則組成新的規(guī)則集存放在TCAM中，重新返回狀態(tài)1，進入下一個循環(huán).

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

t≤S/v. （2）

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

t≤T≤S/v. （3）

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

證畢.

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

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

α≥vT.

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

vT≤β-rβ.

此時β的取值要求為：

β≥v T1-r.

因此有：

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

證畢.

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

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

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

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

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

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

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規(guī)則壓縮算法

本文設計一種適用于快速更新的動態(tài)規(guī)則壓縮算法，主要思想為在不改變規(guī)則集語義的前提下將規(guī)則集轉(zhuǎn)換為一個等價的BDD[9]，再將實時更新的規(guī)則集嵌入改變縮減之后的BDD，最后將BDD轉(zhuǎn)換為等價的規(guī)則集以減少規(guī)則集中的規(guī)則數(shù)量從而達到壓縮規(guī)則的目的.將更新與壓縮兩種操作結(jié)合在一起，不僅能夠滿足網(wǎng)絡中快速更新規(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é)點對應一個decision，記為D（v）；

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

如圖3所示為規(guī)則集轉(zhuǎn)換為BDD的示意圖.其中D（F1）=D（F2）=[0，15]，并用a表示accept，用d表示disgard.根據(jù)規(guī)則集的特點在每一個節(jié)點處每一個域進行二分，直到所有的規(guī)則都包含于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

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

算法1BDDCompress（node）.

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

步驟：

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

2）BDDCompress （node）

{

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

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

Setnode（node=node->pre）；

BDDCompress （node）；

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

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

1）將規(guī)則集f轉(zhuǎn)換成一個等價的BDDf1；

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

3）將合并后的BDD轉(zhuǎn)換為等價的規(guī)則集.

在這里提出BDD動態(tài)規(guī)則壓縮算法.

算法2BDDInsert（f，g）.

輸入：原始BDDg；更新規(guī)則集f；

輸出：縮減后的BDDg1；

步驟：

1）將f轉(zhuǎn)換為等價的BDDf1；

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

{

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

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

否則將該路徑添加到g1；

}

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

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

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

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

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

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

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

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

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

5實驗

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

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

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

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

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

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

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

6結(jié)束語

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

參考文獻

[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，從實驗結(jié)果可以看出，在一個時間周期內(nèi)，仿真容器中的規(guī)則呈線性增長，而每隔一個時間周期，仿真容器中的規(guī)則就會被壓縮一次，最終容器內(nèi)的規(guī)則在一定范圍內(nèi)波動.

6結(jié)束語

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

參考文獻

[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，從實驗結(jié)果可以看出，在一個時間周期內(nèi)，仿真容器中的規(guī)則呈線性增長，而每隔一個時間周期，仿真容器中的規(guī)則就會被壓縮一次，最終容器內(nèi)的規(guī)則在一定范圍內(nèi)波動.

6結(jié)束語

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

參考文獻

[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.