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

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

收稿日期：20140113

基金項(xiàng)目：國家科技支撐計(jì)劃資助項(xiàng)目（2012BAH09B02）；長沙市重點(diǎn)科技計(jì)劃資助項(xiàng)目（K1204006111）

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

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

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

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

中圖分類號(hào)：TP393.2 文獻(xiàn)標(biāo)識(shí)碼：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)絡(luò)交換模型，主要由OpenFlow交換機(jī)、FlowVisor和Controller三部分組成.OpenFlow交換機(jī)進(jìn)行數(shù)據(jù)層的轉(zhuǎn)發(fā)，F(xiàn)lowVisor對(duì)網(wǎng)絡(luò)進(jìn)行虛擬化，Controller對(duì)網(wǎng)絡(luò)進(jìn)行集中控制，實(shí)現(xiàn)控制層的功能.OpenFlow技術(shù)采用集中式的控制方法，由一個(gè)或多個(gè)包含整個(gè)網(wǎng)絡(luò)拓?fù)涞闹行目刂破魍ㄟ^一個(gè)開放的協(xié)議對(duì)不同交換機(jī)和路由器中的流表直接進(jìn)行編程，從而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中數(shù)據(jù)流的控制.

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

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

1相關(guān)工作

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

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

2基本概念

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

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

當(dāng)且僅當(dāng)對(duì)于任意的數(shù)據(jù)包都在f中至少存在一條規(guī)則與之匹配，那么，一個(gè)規(guī)則序列f是一個(gè)完全規(guī)則序列.為了保證一個(gè)規(guī)則序列f是一個(gè)完全規(guī)則序列，f的最后一條規(guī)則通常是如下形式：F1∈D（F1）∧…∧Fd∈D（Fd）.如下所示為兩個(gè)域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

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

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

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

3空間劃分

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

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

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

α+β=S. （1）

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

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

t≤S/v. （2）

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

t≤T≤S/v. （3）

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

證畢.

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

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

α≥vT.

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

vT≤β-rβ.

此時(shí)β的取值要求為：

β≥v T1-r.

因此有：

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

證畢.

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

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

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

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

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

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

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

證因?yàn)镾≥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ī)則壓縮算法

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

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

1）存在一個(gè)decision集合DS；

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

3）每一個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)decision，記為D（v）；

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

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

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

算法1BDDCompress（node）.

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

步驟：

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

2）BDDCompress （node）

{

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

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

Setnode（node=node->pre）；

BDDCompress （node）；

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

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

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

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

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

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

算法2BDDInsert（f，g）.

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

輸出：縮減后的BDDg1；

步驟：

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

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

{

移除g1中包含于f1中的路徑所對(duì)應(yīng)的葉子節(jié)點(diǎn)，并將f1中對(duì)應(yīng)的路徑添加到g1；

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

否則將該路徑添加到g1；

}

每隔一個(gè)時(shí)間周期T后臺(tái)服務(wù)器調(diào)用算法2對(duì)更新的規(guī)則集進(jìn)行壓縮處理.假設(shè)網(wǎng)絡(luò)中更新了如下2條規(guī)則：

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

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

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

BDD中的每一個(gè)decision都對(duì)應(yīng)一條規(guī)則，該規(guī)則由一條或多條路徑合并而成.從decision開始尋找其父節(jié)點(diǎn)直到根節(jié)點(diǎn)，若某個(gè)decision所對(duì)應(yīng)的葉子節(jié)點(diǎn)只存在一個(gè)父節(jié)點(diǎn)，那么從其到根節(jié)點(diǎn)的路徑唯一，且對(duì)應(yīng)一條或多條壓縮后的規(guī)則；若某個(gè)decision存在多個(gè)父節(jié)點(diǎn)，那么從其到跟節(jié)點(diǎn)的路徑中必然存在可以合并的兩條或多條路徑，此時(shí)對(duì)其各路徑進(jìn)行判斷并對(duì)滿足條件的邊進(jìn)行合并.圖4所示BDD中dicesion1只有一個(gè)父節(jié)點(diǎn)，因此從其到根節(jié)點(diǎn)的路徑唯一，對(duì)應(yīng)的規(guī)則為：r1：F1∈[0，7]∧F2∈[8，15]→disgard.dicesion2存在2個(gè)父節(jié)點(diǎn)node2，node3，將node1至node2的邊和node1至node3的邊所對(duì)應(yīng)的區(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

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

5實(shí)驗(yàn)

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

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

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

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

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

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

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

6結(jié)束語

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

參考文獻(xiàn)

[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]. 通信學(xué)報(bào)，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.

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

6結(jié)束語

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

參考文獻(xiàn)

[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]. 通信學(xué)報(bào)，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.

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

6結(jié)束語

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

參考文獻(xiàn)

[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]. 通信學(xué)報(bào)，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.