提高軟件定義網(wǎng)絡(luò)交換機(jī)存儲(chǔ)能力的流表壓縮算法

沈劍良,王崇越,湯先拓,張霞

(1.中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué),450003,鄭州;2.國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,450002,鄭州)

隨著互聯(lián)網(wǎng)技術(shù)與信息技術(shù)革命的不斷深入,舊有的網(wǎng)絡(luò)結(jié)構(gòu)無(wú)法滿足靈活多變的用戶需求,以軟件定義網(wǎng)絡(luò)(software defined networking,SDN)為首的新型網(wǎng)絡(luò)體系具備良好的前景,受到了廣泛關(guān)注。SDN將控制平面和數(shù)據(jù)平面解耦分離,控制平面生成流表,數(shù)據(jù)平面根據(jù)流表對(duì)數(shù)據(jù)進(jìn)行分類、轉(zhuǎn)發(fā)等操作[1-3],實(shí)現(xiàn)了網(wǎng)絡(luò)的統(tǒng)一管理。利用流表的數(shù)據(jù)包分類已經(jīng)被廣泛應(yīng)用在防火墻過(guò)濾、入侵檢測(cè)、流量計(jì)費(fèi)等領(lǐng)域[4-5],在網(wǎng)絡(luò)數(shù)據(jù)安全方面發(fā)揮著重要作用。

隨著SDN及其南向協(xié)議OpenFlow的不斷發(fā)展,流表內(nèi)容愈發(fā)復(fù)雜,流表數(shù)不斷增加。為了滿足低時(shí)延的流式處理,三態(tài)內(nèi)容尋址存儲(chǔ)器(TCAM)被用于交換機(jī)中進(jìn)行流表存儲(chǔ)與匹配,但是TCAM存儲(chǔ)空間較小,價(jià)格昂貴[6],且無(wú)法直接存儲(chǔ)具有范圍值的流表項(xiàng),需編碼后進(jìn)行存儲(chǔ),編碼后流表項(xiàng)用0,1,*(通配符)表示,給存儲(chǔ)空間帶來(lái)了巨大壓力。

針對(duì)流表內(nèi)容耗費(fèi)存儲(chǔ)空間的問(wèn)題,學(xué)術(shù)界和工業(yè)界已經(jīng)提出了許多方法來(lái)優(yōu)化存儲(chǔ)空間,這些研究主要集中在優(yōu)化TCAM編碼算法[7-18]、修改TCAM硬件結(jié)構(gòu)[19-21]、流表優(yōu)化[22-25]3個(gè)方面。

TCAM的范圍編碼算法是利用編碼過(guò)程中流表特性來(lái)進(jìn)行優(yōu)化,減少編碼后流表項(xiàng)數(shù)。最直接的前綴編碼[7](prefix encoding,PE)算法將每個(gè)范圍值轉(zhuǎn)化為前綴表示,并獨(dú)立存儲(chǔ)在TCAM表項(xiàng)中,當(dāng)一條規(guī)則同時(shí)具有多個(gè)范圍值時(shí),會(huì)導(dǎo)致多組前綴相乘,占用大量空間,最壞情況下一條規(guī)則需要900個(gè)TCAM表項(xiàng)進(jìn)行表示,導(dǎo)致范圍擴(kuò)展問(wèn)題。通常,一個(gè)W位的范圍最多需要2(W-1)條前綴來(lái)表示[7],占用大量存儲(chǔ)空間,不滿足網(wǎng)絡(luò)的發(fā)展。為了減少編碼后表項(xiàng)數(shù),文獻(xiàn)[8-13,16]利用額外比特位來(lái)提高編碼效率。文獻(xiàn)[14-15,17]利用規(guī)則集本身特性來(lái)提高編碼效率,修改TCAM硬件結(jié)構(gòu)則是通過(guò)修改硬件電路來(lái)提高存儲(chǔ)空間。Yu等[20]提出了利用靜態(tài)隨機(jī)存取存儲(chǔ)器(SRAM)來(lái)模擬TCAM,可以在保留高效處理速度的前提下降低成本,提高存儲(chǔ)空間。Gangadhar等[21]提出了修改TCAM的晶體管結(jié)構(gòu)來(lái)優(yōu)化TCAM構(gòu)造,實(shí)現(xiàn)了容量增加以及功耗降低,但是修改硬件電路的方法都具有較大局限性。

流表優(yōu)化方法則是根據(jù)流表項(xiàng)之間的關(guān)系以及流表內(nèi)部的信息冗余來(lái)對(duì)流表項(xiàng)進(jìn)行壓縮優(yōu)化。唐亞哲等[24]結(jié)合TCAM和布隆過(guò)濾器設(shè)計(jì)了混合多級(jí)流表,有效提高了存儲(chǔ)容量。Zhong等[25]在幾何空間上對(duì)規(guī)則集進(jìn)行分析,將具有重疊特征的不同規(guī)則集進(jìn)行合并轉(zhuǎn)化,實(shí)現(xiàn)了規(guī)則集的優(yōu)化,增加了存儲(chǔ)空間利用率。

這些技術(shù)都是為了提高TCAM存儲(chǔ)空間利用率,而范圍編碼是其中無(wú)法繞開(kāi)的關(guān)鍵環(huán)節(jié)。針對(duì)現(xiàn)有范圍編碼算法占用額外比特位過(guò)多[8,11-13]或支持場(chǎng)景局限性過(guò)大[9-10,14-17]的問(wèn)題,本文提出了一種不占用額外比特位的高效混合編碼算法。該算法將任意W位范圍[2p,2q-1](其中p≥0,w≥q>p)稱為無(wú)范圍擴(kuò)展前綴編碼(none range expansion prefix encoding,NREPE)范圍,對(duì)其編碼可以實(shí)現(xiàn)無(wú)范圍擴(kuò)展。對(duì)于非NREPE范圍采用其他編碼方案,由于精力限制,本文對(duì)其他范圍仍采用了PE算法進(jìn)行編碼,但是在后續(xù)工作中,可以采用更高效的編碼方案進(jìn)行混合編碼。

本文從TCAM的缺點(diǎn)著手,通過(guò)分析對(duì)比已有的優(yōu)化算法,查漏補(bǔ)缺,首先對(duì)此前辦法進(jìn)行改進(jìn),設(shè)計(jì)新型編碼算法,其次設(shè)計(jì)對(duì)應(yīng)的架構(gòu),最后通過(guò)實(shí)驗(yàn)證明方法有效性。綜上所述,本文提出了一種無(wú)需修改TCAM結(jié)構(gòu)的混合編碼方案,可以靈活有效地對(duì)不同類型流表進(jìn)行優(yōu)化;提出了一種不占用額外比特位的無(wú)范圍擴(kuò)展的編碼算法,有效地節(jié)省了TCAM存儲(chǔ)資源;從更細(xì)粒度的層次對(duì)算法編碼效果進(jìn)行了分析,證明了本算法高效的編碼效率。

1 混合編碼策略與算法實(shí)現(xiàn)

在本節(jié)中,對(duì)目前已有的關(guān)于TCAM范圍編碼的算法進(jìn)行介紹,根據(jù)這些編碼算法的獨(dú)立性將其分為兩類:規(guī)則集無(wú)關(guān)的范圍編碼和規(guī)則集相關(guān)的范圍編碼。

1.1 規(guī)則集無(wú)關(guān)的范圍編碼

最直接的獨(dú)立于規(guī)則集的范圍編碼方式是前綴編碼算法PE[7],該算法直接將十進(jìn)制數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制的前綴表示形式,將所有的范圍端口轉(zhuǎn)化為前綴表示。算法簡(jiǎn)單易于部署,但是直接轉(zhuǎn)化的范圍值通常需要多條流表項(xiàng)表示,在最初流量規(guī)模較小時(shí)應(yīng)用較多。隨著網(wǎng)絡(luò)流量不斷增加,流表規(guī)模不斷膨脹,PE算法已無(wú)法滿足當(dāng)下網(wǎng)絡(luò)流表存儲(chǔ)需求。

針對(duì)PE算法編碼效率較低的問(wèn)題,文獻(xiàn)[8]提出了柵欄編碼算法,可以將任意的范圍轉(zhuǎn)化為一條前綴表示,但是該算法需要2W-1個(gè)額外比特位來(lái)表示,在實(shí)際的部署中無(wú)法提供足夠的額外比特位。進(jìn)而提出的獨(dú)立于數(shù)據(jù)庫(kù)的范圍前綴編碼(database independent range preencoding,DIRPE)算法針對(duì)柵欄算法需要額外比特位過(guò)多的問(wèn)題,對(duì)柵欄算法進(jìn)行了改進(jìn),將范圍值占用的比特位拆分成為多個(gè)塊,拆分后得到的各個(gè)塊利用柵欄編碼表示,拆分后得到的塊越多,每個(gè)塊包含的比特位越少,需要的額外比特位也越少,但是相應(yīng)會(huì)增加得到的TCAM表項(xiàng)數(shù)。

針對(duì)DIRPE需要額外比特位的情況,Bremler-barr等[9]提出了短范圍格雷碼編碼(short range gray encoding,SRGE)方案。SRGE利用了二進(jìn)制反射格雷碼的特性來(lái)進(jìn)行編碼,借助二叉樹(shù)的反射特性和格雷碼的鄰接特性,確保二叉反射樹(shù)的任意范圍都可以通過(guò)一個(gè)或多個(gè)折疊節(jié)點(diǎn)進(jìn)行壓縮。該算法不需要額外的比特位,可以編碼不超過(guò)1 024位的范圍,但是對(duì)于更大的范圍值,則需要采用混合編碼的方式處理。

Bremler-barr等[10]提出無(wú)擴(kuò)展范圍編碼(range encoding with no expansion,RENE)算法,從全局出發(fā),根據(jù)規(guī)則集中最大范圍值長(zhǎng)度對(duì)所有范圍進(jìn)行編碼,對(duì)于較小的范圍值,可以實(shí)現(xiàn)不需要行擴(kuò)展的范圍編碼。該編碼算法主要針對(duì)于較短的范圍字段,范圍字段較長(zhǎng)時(shí)編碼效率有所下降。

Demianiuk等[11]提出的范圍減少(range reduction,RR)算法,通過(guò)將原始規(guī)則集分組后得到相互獨(dú)立的不相交范圍,再利用PE算法或SRGE方案進(jìn)行編碼后存儲(chǔ),在范圍字段較短時(shí)編碼效果較好。

文獻(xiàn)[12]提出的分割編碼結(jié)構(gòu)(divide-and-conquer scheme,DCS),首次提出了分而治之的編碼架構(gòu)。通過(guò)對(duì)范圍值進(jìn)行分析,將含有范圍值的規(guī)則分割為多條表項(xiàng),對(duì)不同的表項(xiàng)采用不同的編碼算法,可以有效地減少范圍擴(kuò)展,但是該算法需要W位額外比特位,在減少范圍擴(kuò)展的同時(shí)也占用一部分TCAM存儲(chǔ)空間,在IPV6環(huán)境下,存儲(chǔ)空間優(yōu)化效果并不好,仍具有較大的改進(jìn)空間。

1.2 規(guī)則集相關(guān)的范圍編碼

規(guī)則集相關(guān)的范圍編碼核心在于利用規(guī)則集內(nèi)部的特征來(lái)進(jìn)行編碼,編碼效率較高,但是當(dāng)規(guī)則集發(fā)生改變時(shí),需要重新計(jì)算,代價(jià)較大,不能實(shí)現(xiàn)規(guī)則集的快速更新。

最基本的規(guī)則集相關(guān)的范圍編碼算法是比特映射算法(Bit-Map)[16],該算法統(tǒng)計(jì)規(guī)則集中的所有范圍規(guī)則,將不同范圍用一個(gè)比特位表示,利用不同比特位對(duì)范圍規(guī)則進(jìn)行劃分。若存在N個(gè)范圍規(guī)則,則需要N個(gè)比特位來(lái)進(jìn)行范圍編碼。該編碼規(guī)則較為簡(jiǎn)單,不產(chǎn)生行擴(kuò)展,但是缺陷較為明顯,無(wú)法應(yīng)用于大規(guī)模規(guī)則集。

文獻(xiàn)[17]給出了動(dòng)態(tài)范圍編碼算法(dynamic range encoding scheme,DRES),該算法首先對(duì)規(guī)則集中范圍規(guī)則進(jìn)行統(tǒng)計(jì),得到每條規(guī)則的編碼增益(該規(guī)則編碼后可以消除的表項(xiàng)數(shù))。進(jìn)而按照編碼增益排序,依次選擇編碼增益最大的規(guī)則進(jìn)行編碼,編碼方式可以任意選擇。文獻(xiàn)[17]提供了一個(gè)系統(tǒng)的解決方案,雖然給出了規(guī)則集更新的方法,但是過(guò)于繁瑣,更新困難。

文獻(xiàn)[18]提出了范圍特征碼編碼算法(RFC),該算法首先將規(guī)則集中所有范圍分為多組,其次將每組范圍劃分為多個(gè)正交范圍,最后對(duì)各組中的正交范圍進(jìn)行編碼,通過(guò)利用額外比特位對(duì)不同范圍值進(jìn)行區(qū)分,從而減少了范圍擴(kuò)展的問(wèn)題。

2 無(wú)范圍擴(kuò)展前綴編碼

目前大多數(shù)編碼算法存在占用額外比特位、編碼后流表項(xiàng)過(guò)多等情況,針對(duì)這個(gè)問(wèn)題,本文在PE算法和DCS算法的基礎(chǔ)上提出了無(wú)范圍擴(kuò)展前綴編碼算法,不需要占用額外比特位,對(duì)于本文提出的NREPE范圍,可以實(shí)現(xiàn)無(wú)范圍擴(kuò)展。

2.1 無(wú)范圍擴(kuò)展前綴編碼的基本思想

TCAM的范圍編碼算法一直是研究熱點(diǎn),目前許多算法利用TCAM中的額外比特位來(lái)對(duì)范圍值進(jìn)行編碼,但是由于空間制約,無(wú)法適應(yīng)新型網(wǎng)絡(luò)體系結(jié)構(gòu)的發(fā)展。經(jīng)典的PE算法在不需要額外比特位的基礎(chǔ)上則會(huì)帶來(lái)范圍擴(kuò)展問(wèn)題。

本文針對(duì)PE算法帶來(lái)的范圍擴(kuò)展問(wèn)題,結(jié)合PE算法以及DCS算法的優(yōu)點(diǎn),提出了無(wú)范圍擴(kuò)展前綴編碼,通過(guò)設(shè)計(jì)獨(dú)特的編碼方式可以對(duì)范圍值實(shí)現(xiàn)不占用額外比特位的單條編碼,解決了PE算法和DCS算法的缺點(diǎn)。通過(guò)表1簡(jiǎn)要描述無(wú)范圍擴(kuò)展編碼的思想。

表1 范圍[2,64]的PE編碼結(jié)果

由表1知,對(duì)范圍[2,64]使用前綴編碼后,自上而下每條表項(xiàng)的最高有效位依次遞進(jìn),且最高位后的比特位均使用*(通配符)代替。針對(duì)規(guī)則集編碼的特性,給出了定理1如下。

定理1對(duì)于任意的W位范圍[2p,2q-1],其中p≥0,W≥q>p,可以使用最高有效位遞進(jìn)的q-p個(gè)向量將該W位范圍表示。為便于表示,本文將該類型范圍稱為NREPE范圍。

證明對(duì)于任意的W位范圍[2p,2q-1],由于q>p,因此該W位范圍必定存在區(qū)間[2p,2p+1-1],可以用一條前綴表示為0W-p-11*p,此時(shí)剩余區(qū)間為[2p+1,2q-1](q>p+1),仍可重復(fù)分割后編碼過(guò)程,最終可使用最高有效位遞進(jìn)的q-p個(gè)前綴向量將該W位范圍表示。證明完畢。

根據(jù)定理1知,任意NREPE范圍的前綴表示是有規(guī)律的,僅利用一條表項(xiàng)將其編碼,即可解決PE算法范圍擴(kuò)展的問(wèn)題,節(jié)省存儲(chǔ)資源。

2.2 無(wú)范圍擴(kuò)展前綴編碼流程

本文已經(jīng)在2.1節(jié)中提出了NREPE范圍的概念,通過(guò)分析可知,若僅利用一條表項(xiàng)表示NREPE范圍,即可實(shí)現(xiàn)無(wú)范圍擴(kuò)展范圍編碼。規(guī)則集中的范圍值,并不都是NREPE范圍,針對(duì)該問(wèn)題,本文提出一種編碼架構(gòu),首先將范圍值進(jìn)行分割,得到NREPE范圍和其他范圍字段,對(duì)于NREPE范圍采用無(wú)范圍擴(kuò)展編碼,而其他類型的范圍值采用前綴編碼。通過(guò)混合編碼技術(shù),即可最高效率地進(jìn)行編碼,通過(guò)這種編碼架構(gòu),可以靈活有效地支持不同的應(yīng)用場(chǎng)景,具備良好的發(fā)展前景。

2.2.1 范圍值的分割

目前網(wǎng)絡(luò)應(yīng)用向智能化、精細(xì)化發(fā)展,對(duì)數(shù)據(jù)處理有更高的要求,因此在數(shù)據(jù)包分類中端口號(hào)等范圍字段也發(fā)揮著越來(lái)越重要的作用。目前數(shù)據(jù)包包頭中含有的端口范圍種類繁多,并不完全滿足編碼要求,因此對(duì)于這些范圍字段,首先需要對(duì)其進(jìn)行加工處理,使其滿足編碼算法的要求。本文所提算法是在PE算法和DCS算法的基礎(chǔ)上進(jìn)行改進(jìn),借鑒了DCS算法對(duì)范圍值分割的方法。即對(duì)于任意給定的范圍[l,h](0≤l

(1)不需要進(jìn)行分割。該范圍被某個(gè)NREPE范圍覆蓋(2p

(2)分割為兩段范圍。分割后均為非NREPE范圍[l,2p-1],[2p,h](2p-1≤l

(3)分割為3段范圍。[l,2p-1],[2p,2q-1],[2q,h](2p-1

通過(guò)對(duì)原始范圍值的分割處理,可以得到NREPE范圍和其他范圍字段,為后續(xù)打下基礎(chǔ)。

2.2.2 規(guī)則集編碼算法

對(duì)范圍值進(jìn)行分割后可以得到不同的范圍字段,對(duì)不同的范圍采用針對(duì)性編碼算法,可以提高編碼效率。對(duì)于NREPE范圍,本文給出了算法1來(lái)進(jìn)行編碼,而對(duì)于其他范圍字段,本文采用前綴編碼來(lái)進(jìn)行表示。

算法1NREPE范圍編碼算法

輸入 范圍值的最高位與最低位p、q以及位寬W(p+1

輸出 字符串向量s

1.初始化一個(gè)空的W位字符串向量s

2.利用q設(shè)置字符串向量的最高位

3.從字符串最高位W-1到q-1進(jìn)行遍歷填充,對(duì)第q-1位填充為*,其余高位填充為0

4.for allifromW-1 toq-1 do

5.ifi=q-1 then

6.s.append(‘*’) {‘*’為通配符}

7.else

8.s.append(‘0’);

9.i--;

10.利用p設(shè)置字符串向量的最低位

11.從字符串q-2位到0進(jìn)行遍歷填充,對(duì)第p位填充為1,其余位填充為*

12.for allifromq-2 to 0 do

13.ifi=pthen

14.s.append(‘1’)

15.else

16.s.append(‘*’);

17.i--;

18.returns;

通過(guò)對(duì)規(guī)則集中的范圍值進(jìn)行分割編碼后,可以實(shí)現(xiàn)不占用額外比特位的目的。由于對(duì)范圍值采用了獨(dú)特的編碼方式,為了實(shí)現(xiàn)流表項(xiàng)的匹配,同樣需要對(duì)包頭向量進(jìn)行對(duì)應(yīng)的搜索秘鑰編碼,下面給出搜索秘鑰算法的偽代碼。

算法2NREPE搜索秘鑰編碼算法

輸入 端口值v以及位寬W

輸出 字符串向量k

1.初始化一個(gè)空的W位字符串向量k

2.將端口值使用二進(jìn)制表示,最高有效位設(shè)為y

3.從k的最高位開(kāi)始遍歷填充,y左側(cè)填充為0,y位填充為1,其余填充為*

4.for allifromW-1 to 0 do

5.ifi=ythen

6.k.append(‘1’)

7.for alljfromy-1 to 0 do

8.k.append(‘*’)

9.j--

10.break

11.else

12.k.append(‘0’)

13.i--

14.returnk;

通過(guò)設(shè)計(jì)范圍編碼算法以及秘鑰算法,可以有效地減少范圍擴(kuò)展問(wèn)題。本文所提出算法的核心在于利用p和q對(duì)范圍規(guī)則進(jìn)行表示,使用p表示范圍下限,q表示范圍上限。在搜索秘鑰編碼算法中,則利用端口值的最高有效位進(jìn)行編碼,可以實(shí)現(xiàn)精確匹配,本文在圖1中使用了范圍值[5,71]作為例子,完整地展示了如何進(jìn)行范圍分割,范圍編碼以及搜索秘鑰編碼。

在圖1(a)中,對(duì)范圍值進(jìn)行了分割,將其分為3個(gè)范圍字段,其中[8,63]是NREPE范圍。在圖1(b)中,針對(duì)其中的NREPE范圍進(jìn)行了編碼,在圖1(c)中,分別使用15和7進(jìn)行了測(cè)試,結(jié)果顯示15被編碼后符合規(guī)則,7因最高有效位不匹配而不符合規(guī)則。

2.3 NREPE的結(jié)構(gòu)體系

在2.2節(jié)中已經(jīng)介紹了NREPE編碼的基本流程,即通過(guò)對(duì)范圍值分割后進(jìn)行針對(duì)性編碼來(lái)減少范圍擴(kuò)展,不同的類型范圍值采用不同的編碼方式。為了更好地部署本文提出的算法并保留未來(lái)支持新型算法的能力,本文提出了一個(gè)開(kāi)放和靈活的架構(gòu),可以使TCAM獲得更高效的存儲(chǔ)效率。該框架無(wú)需對(duì)交換機(jī)硬件進(jìn)行改造,通過(guò)軟件方法對(duì)規(guī)則進(jìn)行壓縮。

圖2展示了NREPE編碼在數(shù)據(jù)平面的結(jié)構(gòu),當(dāng)數(shù)據(jù)包進(jìn)入后,首先被數(shù)據(jù)包處理器所解析,提取特定字段組合后形成包頭字段;其次將包頭字段輸入編碼模塊,通過(guò)搜索關(guān)鍵字編碼算法進(jìn)行編碼,進(jìn)而將編碼結(jié)果傳輸至匹配模塊(TCAM塊)匹配,最終輸出匹配結(jié)果。當(dāng)規(guī)則集或編碼方式改變時(shí),可以通過(guò)控制平面下達(dá)修改指令,并對(duì)TCAM塊中的流表項(xiàng)進(jìn)行重配置,實(shí)現(xiàn)動(dòng)態(tài)更新。由于本算法僅針對(duì)范圍值本身,對(duì)于未來(lái)可能出現(xiàn)的其他字段的范圍值,該編碼算法仍然有效,因此所提出的結(jié)構(gòu)仍保留廣闊的發(fā)展空間,適應(yīng)未來(lái)網(wǎng)絡(luò)發(fā)展。

由于TCAM匹配的目的是對(duì)輸入的數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)、丟棄、分類等處理。與TCAM進(jìn)行匹配的是從數(shù)據(jù)包中提取的多元組,編碼算法也是僅針對(duì)多元組,并不影響數(shù)據(jù)包本身結(jié)構(gòu),因此并不存在解碼這一環(huán)節(jié)。

由于本文將范圍值分割為NREPE范圍和非NREPE范圍,二者編碼方式不同,因此存儲(chǔ)后的TCAM分為兩種類型,分別存儲(chǔ)NREPE和PE編碼的范圍值,兩兩組合后共存在4種不同類型的TCAM塊。

3 實(shí)驗(yàn)評(píng)價(jià)

在本節(jié)中測(cè)試了本文提出算法的性能,由于真實(shí)的分類數(shù)據(jù)集數(shù)據(jù)難以得到,本文數(shù)據(jù)是通過(guò)ClassBench[26]生成的模擬真實(shí)分類數(shù)據(jù)集。ClassBench是由華盛頓大學(xué)開(kāi)發(fā)的實(shí)驗(yàn)平臺(tái),它是一套對(duì)數(shù)據(jù)包分類算法和設(shè)備進(jìn)行測(cè)試的工具,可以生成精確模擬真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)規(guī)則庫(kù),主要有ACL(訪問(wèn)控制列表)、FW(防火墻規(guī)則)、IPC(IP鏈)3種規(guī)則。本文通過(guò)ClassBench生成了10組300 000規(guī)模的規(guī)則集,并在個(gè)人PC上利用Matlab對(duì)數(shù)據(jù)進(jìn)行了模擬仿真,由于生成的規(guī)則集存在冗余情況,因此消除冗余后部分規(guī)則集數(shù)小于300 000,但是并不影響后續(xù)的測(cè)試。對(duì)生成的數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)后,結(jié)果如表2所示。

表2 ClassBench產(chǎn)生的規(guī)則集

對(duì)規(guī)則集統(tǒng)計(jì)后得到,FW類型的規(guī)則集在源和目的端口中均含有范圍類型,然而其范圍種類較少。ACL類型的規(guī)則集僅在目的端口具有范圍,這些范圍字段種類相較于FW和IPC更多。IPC類型的規(guī)則集雖然在源和目的端口都具有范圍字段,但源和目的端口并不同時(shí)具備。

3.1 拓展比性能比較

為了更好地展示本文提出方法的優(yōu)勢(shì),本文選擇了PE算法、DIRPE算法和DCS進(jìn)行比較。比較時(shí)使用占用額外比特位數(shù)、更新速度、最壞情況擴(kuò)展比ER(expansion ratio)作為依據(jù),擴(kuò)展比ER定義為具有范圍的規(guī)則經(jīng)過(guò)范圍編碼后所得的規(guī)則數(shù)ne比編碼前的規(guī)則數(shù)nd。

由于本算法不改變TCAM結(jié)構(gòu)以及芯片設(shè)計(jì),僅利用軟件對(duì)規(guī)則集以及提取的包頭向量進(jìn)行編碼,因此所造成的額外功耗相比于TCAM本身功耗幾乎可以忽略,而算法在對(duì)原始規(guī)則集進(jìn)行編碼并存儲(chǔ)后重點(diǎn)在于規(guī)則集發(fā)生改變時(shí)的更新速度,對(duì)于更新速度以及其他指標(biāo)在表3中進(jìn)行了對(duì)比。

為了能夠清楚地表示本文所提出方法針對(duì)不同規(guī)則集源和目的端口范圍的編碼能力,在本節(jié)中分別針對(duì)源端口和目的端口進(jìn)行了編碼。圖3展示了僅在源端口進(jìn)行編碼的結(jié)果,從圖3中可以看出,當(dāng)僅對(duì)源端口的范圍進(jìn)行編碼的時(shí)候,所提出的NREPE算法相較于PE、DIRPE以及RENE算法可以有效地降低擴(kuò)展比,在FW和IPC類型的規(guī)則集中擴(kuò)展比基本都為1,這是因?yàn)樵贔W和IPC規(guī)則集中包含了大量[1 024,65 535]范圍值,而NREPE對(duì)此種類型的數(shù)據(jù)可以進(jìn)行無(wú)范圍擴(kuò)展編碼。ACL規(guī)則集中并不包含源端口具有范圍的規(guī)則,因此并未在圖3中出現(xiàn)。

表3 各編碼算法比較

圖4展示了僅在目的端口進(jìn)行范圍編碼的結(jié)果?？梢钥闯?NREPE算法在各種規(guī)則集下都優(yōu)于傳統(tǒng)的PE算法,并且都有較大幅度的領(lǐng)先,但在ACL2數(shù)據(jù)集下優(yōu)化效果并不十分突出,這是因?yàn)樵谠撘?guī)則集中包含大量[1 025,65 535]范圍值,對(duì)于[1 025,65 535]范圍值,需要將其分割為[1 025,2 047]、[2 048,65 535]兩種情況,其中[2 048,65 535]僅需要一條表項(xiàng)表示,而[1 025,2 047]需要多條表項(xiàng)表示,因此最終仍需要多條表項(xiàng),但相較于PE算法依然提升了40%的空間利用率。RENE算法則表現(xiàn)不佳,因?yàn)槠溥m用于較短范圍的范圍編碼,當(dāng)存在大量較長(zhǎng)范圍時(shí)表現(xiàn)較差。

圖5給出了同時(shí)對(duì)源和目的端口進(jìn)行范圍編碼的結(jié)果。在兩個(gè)端口均為范圍的情況下,需要根據(jù)范圍是否可以分割為NREPE范圍進(jìn)行分塊存儲(chǔ)。對(duì)于只有一個(gè)端口為范圍的規(guī)則集,編碼后所需的TCAM表項(xiàng)和針對(duì)該端口進(jìn)行范圍編碼所得到的結(jié)果一致。例如在ACL規(guī)則集中,源端口均不包含范圍,因此同時(shí)對(duì)源端口和目的端口編碼的結(jié)果與針對(duì)目的端口編碼得到的結(jié)果一致,但在FW規(guī)則集中,同時(shí)對(duì)源和目的端口編碼后結(jié)果會(huì)發(fā)生巨大變化。在FW類型的規(guī)則集中,使用NREPE算法進(jìn)行編碼所得到的擴(kuò)展比相較PE算法平均降低了86%,相較于DIRPE算法降低了83%,效果十分明顯。

這是由于FW中包含了大量的[1 024,65 535]范圍值,擴(kuò)展比近似為1,并且源和目的端口均包含范圍規(guī)則。如果采用其他方法,會(huì)導(dǎo)致大量的范圍擴(kuò)展,在ACL規(guī)則集中,NREPE編碼后所需的TCAM表項(xiàng)相較PE和DIRPE算法平均降低了37%和4%,這是因?yàn)樵贏CL1數(shù)據(jù)集中包含了大量的范圍長(zhǎng)度較小的規(guī)則,3種算法編碼效果較為相似,而在ACL2中3種算法效果都不十分理想。在IPC數(shù)據(jù)集中,NREPE算法相較于PE和DIRPE可以分別降低11%和71%的表項(xiàng)數(shù)。由于RENE算法在FW類型中表現(xiàn)不佳,通過(guò)實(shí)驗(yàn)知其在源和目的端口同時(shí)編碼時(shí)擴(kuò)展比遠(yuǎn)超其他類型算法,擴(kuò)展比基本均在100以上,因此并未在圖中展示。

3.2 比特位數(shù)性能比較

NREPE算法相較于其他算法可以有效地降低擴(kuò)展比ER,但相比于DCS算法,僅分析擴(kuò)展比并無(wú)明顯優(yōu)勢(shì)。本文所提出算法并不需要額外比特位,而規(guī)則集在TCAM中的存儲(chǔ)在更細(xì)粒度上是對(duì)比特位進(jìn)行存儲(chǔ),僅利用ER并不能突出本算法的優(yōu)勢(shì),因此本文提出了比特位數(shù)比(bit number ratio,BNR)作為補(bǔ)充比較指標(biāo),從更細(xì)粒度的層次評(píng)價(jià)算法的編碼效果。BNR定義為編碼后所需要的比特位數(shù)ne,b比編碼前占用的比特位數(shù)nd,b。由于篇幅限制,本文僅給出了對(duì)同時(shí)從源和目的端口進(jìn)行編碼后的比特位數(shù)分析,結(jié)果如圖6所示。

根據(jù)實(shí)驗(yàn)結(jié)果可知,本文所提出的NREPE編碼算法占用的比特位數(shù)遠(yuǎn)小于其他算法,即使相比效果最好的DCS算法,平均占據(jù)的比特位也減少了50%。通過(guò)綜合比較,本文所提出的算法對(duì)存儲(chǔ)空間優(yōu)化效果最好。

4 結(jié)束語(yǔ)

本文提出了一種提高軟件定義網(wǎng)絡(luò)交換機(jī)存儲(chǔ)能力的流表壓縮算法。該算法針對(duì)SDN交換機(jī)的流表存儲(chǔ)模塊,對(duì)流表項(xiàng)進(jìn)行分割后混合編碼,實(shí)現(xiàn)了不占用額外比特位的低開(kāi)銷無(wú)范圍擴(kuò)展編碼,有效提高了存儲(chǔ)能力,且是一種通用算法,可以針對(duì)任意類型范圍值,適用性廣。從更細(xì)粒度利用存儲(chǔ)資源,易于部署。實(shí)驗(yàn)結(jié)果表明,本文提出的流表壓縮算法在各種規(guī)則集下,均可有效地優(yōu)化存儲(chǔ)空間,具備良好的擴(kuò)展性,且是一種完整的編碼架構(gòu),能夠有效地適應(yīng)網(wǎng)絡(luò)流量的變化與發(fā)展。