面向SDN的流規(guī)則拆分分配算法

閆祎程，易 波，王興偉，黃 敏

1(東北大學(xué) 軟件學(xué)院，沈陽 110169)

2(東北大學(xué) 計算機科學(xué)與工程學(xué)院，沈陽 110169)

3(東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819)E-mail:wangxw@mail.neu.edu.cn

1 引 言

隨著互聯(lián)網(wǎng)的發(fā)展，傳統(tǒng)網(wǎng)絡(luò)這種全分布式的結(jié)構(gòu)開始展露出許多弊端.為了表達所需的高級網(wǎng)絡(luò)策略，網(wǎng)絡(luò)運營商通常需要使用低級別且特定的命令來配置每個單獨的網(wǎng)絡(luò)設(shè)備[1].為解決傳統(tǒng)網(wǎng)絡(luò)中管理復(fù)雜、強耦合等弊端，國內(nèi)外學(xué)者提出了軟件定義網(wǎng)絡(luò)(Software Defined Networking，SDN)，并對SDN進行了廣泛的研究[2,3].SDN不僅使網(wǎng)絡(luò)在靈活性和可控性上得到了很大的提升，而且已經(jīng)成為信息中心網(wǎng)絡(luò)等新型網(wǎng)絡(luò)架構(gòu)的基石[4].OpenFlow作為目前SDN中被最廣泛應(yīng)用的協(xié)議，為操作員提供了簡單接口，簡化了網(wǎng)絡(luò)管理并提高了魯棒性[5].OpenFlow協(xié)議需要在有限容量的三態(tài)內(nèi)容尋址寄存器(Ternary Content Addressable Memory，TCAM)中安裝流規(guī)則，但TCAM容量有限的問題，限制了大規(guī)模流規(guī)則的存儲[6].

在網(wǎng)絡(luò)中實現(xiàn)高級策略(如防火墻策略等)所產(chǎn)生的流規(guī)則數(shù)量對于TCAM空間來說往往是巨大的.因流規(guī)則放置不當(dāng)而沒有完全實現(xiàn)高級策略，導(dǎo)致本該被拒絕的數(shù)據(jù)包進入網(wǎng)絡(luò)，有可能造成網(wǎng)絡(luò)安全問題.因此，如何在SDN交換機上合理利用流規(guī)則空間實現(xiàn)高級策略至關(guān)重要.

本文在給定的拓?fù)渖戏胖迷L問控制列表(Access Control List，ACL)規(guī)則以實現(xiàn)防火墻策略，并針對ACL規(guī)則拆分分配問題，設(shè)計了兩種不同的拆分分配算法.流規(guī)則拆分分配的關(guān)鍵挑戰(zhàn)在于如何將原始規(guī)則集拆分為多個語義上等效的子集，以及如何將這些子集分配給TCAM空間有限的SDN交換機[7].本文的主要貢獻如下：

1)設(shè)計了基于矩形拆分分配算法，在路徑上僅放置與之相關(guān)的高級策略規(guī)則集.

2)設(shè)計了基于平均拆分分配算法，在路徑上放置全部高級策略規(guī)則集.

3)仿真結(jié)果表明，與基準(zhǔn)機制相比，本文所提出的算法可以明顯降低拆分后流規(guī)則的數(shù)量.

2 相關(guān)工作

由于單個交換機沒有足夠的TCAM空間來存儲所有規(guī)則，因此，針對如何高效地利用TCAM空間來放置流規(guī)則的解決方案主要分為兩種[8].一種是流表壓縮機制.文獻[9]提出了使用通配符規(guī)則的流表壓縮機制，對流規(guī)則按照源地址、目的地址和默認(rèn)流規(guī)則進行壓縮.文獻[10]中對流條目進行周期性的壓縮，并基于匹配頻率和匹配概率的隱馬爾可夫模型決定保留在流表中的流條目.文獻[11]首先根據(jù)流表匹配域之間的關(guān)系將流表分割為流表子集，然后對每個流表子集進行壓縮，從而實現(xiàn)流表的高效存儲.雖然流表壓縮機制可以提高TCAM的利用率，但流表壓縮降低了流規(guī)則的可見性.

另一種是流規(guī)則拆分分配機制.文獻[12]中將規(guī)則轉(zhuǎn)化為有向依賴圖，將規(guī)則拆分后緩存在存儲桶中.雖然將規(guī)則存儲在額外存儲設(shè)備上可以緩解TCAM空間緊缺的問題，但是額外存儲設(shè)備使得網(wǎng)絡(luò)的管理變得復(fù)雜.文獻[13]提出了一種線性規(guī)則拆分方法和兩種基于啟發(fā)式的規(guī)則分配方法.但該方法會導(dǎo)致計算成本較高.文獻[14]將流條目劃分為通用規(guī)則和本地規(guī)則，并且針對不同類型的流條目執(zhí)行不同的拆分和分配算法.這意味著拆分分配可能導(dǎo)致拆分后流規(guī)則數(shù)目較多.

考慮到流規(guī)則壓縮存在一定的弊端，并且流規(guī)則拆分分配機制還有很大的改進空間.因此本文根據(jù)按需安裝的原則，對高級策略(即ACL)提出了基于拆分分配的流規(guī)則放置算法.

3 網(wǎng)絡(luò)模型

3.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

網(wǎng)絡(luò)拓?fù)淇梢猿橄鬄橐粋€有向連接圖G=(V,E)，由基礎(chǔ)設(shè)備和鏈路組成，頂點集合V=(H,S)由主機集合H和交換機集合S組成.邊集合E由Esh和Ess組成，其中Ess表示交換機之間的通信鏈路，Esh表示交換機與主機之間的通信鏈路.

3.2 節(jié)點模型

交換機節(jié)點模型為S={id,Tcapi,Ptabi,Ftabi,linkset}.其中id表示交換機的唯一標(biāo)識，Tcapi表示為交換機Si上TCAM的存儲空間.每個流表由策略規(guī)則表Ptabi={rp1,rp2,…,rpn}和轉(zhuǎn)發(fā)規(guī)則表Ftabi={rf1,rf2,…,rfn}組成，linkset表示該節(jié)點到下個節(jié)點的集合.

為了防止交換機中的規(guī)則空間被全部占用，基于式(1)對策略規(guī)則表進行空間分配.

Pcapi=Tcapi×THRTCAM×portion

(1)

式(1)中Pcapi表示為策略規(guī)則表的大小，Tcapi為TCAM存儲空間，THRTCAM為交換機規(guī)則空間的最大利用率，portion表示交換機流規(guī)則空間可以分配給高級策略規(guī)則的比例.

3.3 數(shù)據(jù)流模型

本文將數(shù)據(jù)流描述為Flow={cookie,ips,ipd,ports,portd,rate,time,path,edgeset}.其中，cookie用以標(biāo)識一個數(shù)據(jù)流，ips和ipd分別代表數(shù)據(jù)流的源IP和目的IP地址，ports和portd分別代表數(shù)據(jù)流的源和目的端口地址，rate為數(shù)據(jù)流的速率，time為當(dāng)前時間戳，path為數(shù)據(jù)流經(jīng)過的一系列交換機節(jié)點的有序序列，edgeset為數(shù)據(jù)流經(jīng)過的有向邊的集合.

3.4 流規(guī)則模型

本文的流規(guī)則模型表示為ri={pre,act,tim,pri}，其中pre為流規(guī)則的匹配域，act為流規(guī)則的動作域，本文ACL的動作域為act={Permit,Drop}，其中Permit表示允許轉(zhuǎn)發(fā)數(shù)據(jù)分組，Drop表示丟棄數(shù)據(jù)分組.tim為流規(guī)則的超時值，對于所有的ACL規(guī)則設(shè)置統(tǒng)一的固定超時值.pri為流規(guī)則的優(yōu)先級.

4 算法設(shè)計

4.1 設(shè)計目標(biāo)

(2)

(3)

4.2 基于矩形拆分分配的PNS算法

設(shè)計了基于矩形拆分(Rectangle Based Split，RBS)算法在路徑上放置與之相關(guān)的高級策略規(guī)則子集(Partial Related Policy and Not Share Rule Mechanism，PNS)，路徑之間不共享流規(guī)則.網(wǎng)絡(luò)中的數(shù)據(jù)分組可能僅與高級策略規(guī)則集中的部分規(guī)則相匹配，所以只需在數(shù)據(jù)分組的轉(zhuǎn)發(fā)路徑上放置與之匹配的高級策略規(guī)則集即可.因此PNS算法可以保證規(guī)則拆分分配前后網(wǎng)絡(luò)操作的一致性.下面分別從交換機空間資源分配和基于矩形拆分分配算法進行介紹.

4.2.1 交換機空間資源分配

(4)

(5)

(6)

(7)

(8)

交換機資源分配算法如算法1所示，其中1-7行是交換機為每條路徑分配相應(yīng)的空間，其中8-16行是為每條路徑篩選與路徑相關(guān)的策略規(guī)則.

算法1.交換機流規(guī)則空間分配算法

輸入：路徑匹配結(jié)果{p1,{IPh1,IPh2,…,IPhm}},…,{pn,{IPhl,IPhl+1,…,IPhn}}，高級策略規(guī)則Rpol.

輸出：交換機為不同路徑分配的空間.

BEGIN:

1.FORi∈S

3. 按式(5)為每個路徑平均分配交換機空間；

4.ENDFOR

5.FORpi∈{p1,p2,…,pn}

6. 根據(jù)式(7)確保路徑pi所分配到足夠的規(guī)則空間；

7.ENDFOR

8.FORpi∈{p1,p2,…,pn}

11.IF估計值>分配值

12. 重新執(zhí)行交換機規(guī)則空間分配模塊；

13.ELSEIF估計值≤分配值

14. 執(zhí)行規(guī)則集拆分分配模塊；

15.ENDIF

16.ENDFOR

17.END

4.2.2 矩形拆分分配算法

本文使用幾何方法來表示規(guī)則，提出基于矩形的拆分算法RBS，假設(shè)由源地址和目的地址生成一條規(guī)則，可以用一個矩形網(wǎng)絡(luò)來表示規(guī)則，如圖1所示，橫坐標(biāo)F1表示源地址的范圍，縱坐標(biāo)F2表示目的地址的范圍.將按優(yōu)先級排列的ACL映射到矩陣中.由于規(guī)則中使用通配符，所以規(guī)則之間有重疊部分，其中高優(yōu)先級的規(guī)則矩形位于低優(yōu)先級矩形的上部.

圖1 ACL規(guī)則集的幾何表示

(9)

(10)

(11)

(12)

基于矩形的切塊算法如算法2所示.3-9行是選擇合適的矩形切塊q，并根據(jù)矩形切塊對規(guī)則進行拆分.10-17行是將規(guī)則安裝在相應(yīng)交換機上.

算法2.基于矩形拆分分配算法

輸入：路徑匹配結(jié)果{p1,{IPh1,IPh2,…,IPhm}},…,{pn,{IPhl,IPhl+1,…,IPhn}}，高級策略規(guī)則Rpol.

輸出：在交換機上放置的規(guī)則.

BEGIN:

1.初始化參數(shù)di←Pcapi，xj,i←交換機si為路徑pj分配的交換機空間；

2.q←滿足條件最大的矩形切塊，需要滿足q≤di；

3.FORpi∈{p1,p2,…,pn}

4.FORsi∈pi

5.WHILE交換機si有可用的流規(guī)則空間

6. 根據(jù)式(10)選擇矩形q；

8. 選擇矩形q′

9.ENDIF

10. 在當(dāng)前交換機上安裝與矩形切塊q包含的規(guī)則集

11. 更新路徑相關(guān)策略規(guī)則；

14.ENDWHILE

15.IF到路徑pi的最后一個交換機，仍有規(guī)則未安裝

16. 重新執(zhí)行拆分模塊；

17.ENDIF

18.ENDFOR

19.ENDFOR

20.END

4.3 基于平均拆分分配的AVS算法

當(dāng)網(wǎng)絡(luò)拓?fù)渲泄?jié)點度較大時，每個節(jié)點均被多條路徑所共用.為了更高效的利用流表空間，可以使路徑之間共享交換機空間，因此本文提出了基于平均拆分(Average Based Split，ABS)算法在路徑上放置全部規(guī)則集機制(All Policy Split Average and Share Rule Mechanism，AVS).

4.3.1 計算最值

AVS機制是將高級策略規(guī)則集均勻拆分后放置到路徑上.在網(wǎng)絡(luò)中不同數(shù)據(jù)分組的轉(zhuǎn)發(fā)路徑長度有可能不同，若最短路徑pshort上可以放置全部高級策略規(guī)則子集，那么其他路徑也都可以成功放置拆分后的規(guī)則塊.因此均勻拆分的份數(shù)取決于最短路徑的長度lshort.

4.3.2 平均拆分分配算法

(13)

NAVS

(14)

(15)

AVS算法對流規(guī)則進行拆分放置時，不一定按順序放到路徑上的交換機中，可能存在優(yōu)先級高的規(guī)則被放置到路徑的下游.因此為了保證網(wǎng)絡(luò)全局操作的一致性，需要在放置了低優(yōu)先級策略的交換機上放置與之相同匹配域的高優(yōu)先級策略.

基于平均拆分分配的算法如算法3所示.首先計算最短路徑，并將規(guī)則等分.然后在最短路徑上安裝相應(yīng)的規(guī)則，在其他路徑上安裝未安裝的規(guī)則.

算法3.基于平均拆分分配算法.

輸入：路徑匹配結(jié)果{p1,{IPh1,IPh2,…,IPhm}},…,{pn,{IPhl,IPhl+1,…,IPhn}}，高級策略規(guī)則Rpol.

輸出：在交換機上放置的規(guī)則.

BEGIN:

1.將路徑p1,p2,…,pn按長度從小到大排序；

2.記最短路徑為pshort，最短路徑長度為lshort；

3.按照式(13)計算每份規(guī)則塊包含的規(guī)則數(shù)NAVS；

5.FORpi∈{p1,p2,…,pn}

6. 在其他路徑上安裝剩余規(guī)則，如式(15)；

7.WHEN安裝低優(yōu)先級規(guī)則時

8.IF數(shù)據(jù)分組同時匹配高優(yōu)先級規(guī)則

9. 在安裝了低優(yōu)先級規(guī)則的交換機上安裝相應(yīng)的高優(yōu)先級

規(guī)則；

10.ENDIF

11.ENDWHEN

12.ENDFOR

13.END

5 性能評價

本節(jié)對設(shè)計的SDN流規(guī)則拆分分配算法進行仿真實現(xiàn)與性能評價.基于Mininet網(wǎng)絡(luò)仿真器和Floodlight控制器構(gòu)建仿真實驗平臺，以此為基礎(chǔ)，分別從拆分后規(guī)則總數(shù)、運行時間和額外開銷三個方面對比設(shè)計的PNS、AVS流規(guī)則放置機制與基準(zhǔn)機制.仿真環(huán)境詳細信息如表1所示.

表1 仿真環(huán)境

5.1 拓?fù)溆美?/h3>

本文從拓?fù)鋱@中選擇了Darkstrand拓?fù)浜虯TT North America拓?fù)渥鳛閷嶒炌負(fù)?Darkstrand拓?fù)浣Y(jié)構(gòu)如圖2(a)所示，具有28個節(jié)點，31條邊，最大節(jié)點度Maxndeg為3，平均節(jié)點度Avgndeg為2.2，其中節(jié)點的度為連接該節(jié)點的邊數(shù).ATT North America拓?fù)浣Y(jié)構(gòu)如圖2(b)所示，具有25個節(jié)點，57條邊，其中最大節(jié)點度Maxndeg為10，平均節(jié)點度Avgndeg為4.2.

圖2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

5.2 對比機制

采用基于樞軸位拆分(Pivot Bit Decomposition，PBD)算法[15]作為對比機制，該算法在路徑上放置全部高級策略規(guī)則集(All Policy Split Based on Pivot Bit and Share Rule Mechanism，APS).基于樞軸位拆分算法是目前比較具有代表性的算法之一，因此采用該算法作為對比機制.樞軸位指的是規(guī)則位上是通配符的位點，如果一個規(guī)則具有P個軸點，則可以分解成為2p個新規(guī)則.

5.3 性能評價

本文使用ClassBench[16]生成10000條高級策略規(guī)則集，分別在實驗拓?fù)渖蠈⒈疚奶岢龅腜NS和AVS機制與對比機制APS在拆分后生成的流規(guī)則總數(shù)、運行時間這兩個方面進行對比實驗，以及對本文提出的機制所產(chǎn)生的額外開銷進行實驗.

5.3.1 拆分后生成的流規(guī)則總數(shù)

流規(guī)則總數(shù)為將ACL規(guī)則進行拆分分配后，網(wǎng)絡(luò)中的流規(guī)則數(shù)量.流規(guī)則增加率為拆分分配后的流規(guī)則總數(shù)與ACL原規(guī)則數(shù)相比增加的比例.規(guī)定每個交換機的TCAM可存儲2000條規(guī)則，當(dāng)網(wǎng)絡(luò)中的總規(guī)則數(shù)超過總?cè)萘繒r，將無法放置規(guī)則.

在節(jié)點度較小的Darkstrand拓?fù)渲?，對三種算法拆分后產(chǎn)生的總規(guī)則數(shù)進行比較.如圖3(a)所示.從圖中可以看出，隨著ACL原規(guī)則數(shù)的不斷增大，流規(guī)則總數(shù)也不斷增大.由于AVS和APS兩個算法拆分和分配的情況比較接近，因此這兩種算法所呈現(xiàn)出的增長趨勢比較相似.PNS機制明顯優(yōu)于AVS和APS.這是因為AVS和APS算法在路徑上放置全部高級策略規(guī)則，而PNS機制只拆分與路徑相關(guān)的規(guī)則集，因此PNS機制中每條路徑拆分基數(shù)小，總規(guī)則數(shù)也相應(yīng)的少.在Darkstrand拓?fù)渲?，最短路徑長度為9跳，最短路徑上可存儲的流規(guī)則數(shù)為路徑長度與該路徑上交換機存儲空間的乘積，即18000條.所以當(dāng)ACL原規(guī)則數(shù)超過18000時，則不能使用AVS和APS機制.在相同ACL原規(guī)則數(shù)下，PNS機制算法流規(guī)則平均增加率約為34.1%，AVS和APS的流規(guī)則平均增加率分別為113.27%和144.85%.

圖3 不同拓?fù)渖喜鸱趾罅饕?guī)則總數(shù)對比

在節(jié)點度較大的ATT North America拓?fù)渲?，比較三種算法拆分后產(chǎn)生的總規(guī)則數(shù)，如圖3(b)所示，APS機制的增長速度明顯大于其他機制.從圖3(b)中可以看出，PNS機制產(chǎn)生的規(guī)則數(shù)與AVS機制產(chǎn)生的規(guī)則數(shù)相差不多.結(jié)合圖3(a)中PNS的表現(xiàn)，說明PNS機制具有較好的適用性.同樣，在該拓?fù)湎?，最短路徑跳?shù)為6，AVS和APS可以放置的最大規(guī)則數(shù)為12000條.所以當(dāng)規(guī)則總數(shù)大于12000時，將不能使用這兩個機制.在相同ACL原規(guī)則數(shù)下，AVS和PNS機制的流規(guī)則平均增加率約為55.5%和67.06%，APS的流規(guī)則平均增加率為186.96%.

5.3.2 運行時間

將三種算法分別在路徑為16的Darkstrand拓?fù)浜吐窂綌?shù)為28的ATT North America拓?fù)湎逻\行，比較其運行時間.如圖4所示，隨著路徑的增加，時間也不斷增加.三種機制都以路徑為基本計算單位.AVS使用線性時間拆分，所以運行時間最短，APS需要遞歸尋找樞軸位，運行時間次之.PNS機制雖然在兩種拓?fù)渖袭a(chǎn)生的規(guī)則總數(shù)最低，但是由于其需要為每條路徑上的每個交換機都遞歸的尋找拆分切塊，因此運行時間也最長.

圖4 不同拓?fù)渖纤惴ㄟ\行時間對比

5.3.3 額外開銷

額外開銷指的是流規(guī)則放置機制使用拆分分配算法生成的額外規(guī)則與原高級策略規(guī)則總數(shù)的比值，可以體現(xiàn)流規(guī)則放置機制的性能.在對額外開銷進行測試時，需要測試算法在不同跳數(shù)路徑下的額外開銷，由于Darkstrand拓?fù)浣Y(jié)構(gòu)相對簡單，因此在ATT North America拓?fù)湎?，對算法進行測試.

在交換機TCAM大小為750，ACL規(guī)則總數(shù)為3000的情況下，對PNS機制在不同跳數(shù)路徑下產(chǎn)生的額外開銷進行測試.如圖5所示，隨著路徑跳數(shù)的增加，PNS算法的額外開銷也不斷增加.這是因為當(dāng)路徑的跳數(shù)增加，交換機可能被更多條路徑共用，因此交換機為每條路徑分配的流規(guī)則空間也隨之降低.PNS算法需要尋找更小的切塊來拆分原規(guī)則集，從而使不同交換機中安裝重復(fù)規(guī)則，因此導(dǎo)致了額外開銷的增加.

圖5 不同跳數(shù)的路徑上產(chǎn)生的額外開銷

在路徑跳數(shù)為10，ACL規(guī)則數(shù)為5000條的情況下，測試PNS機制在不同TCAM大小下產(chǎn)生的額外開銷.如圖6所示，交換機TCAM大小從500增加至2000.隨著TCAM大小的增加，額外開銷逐漸降低.這是由于TCAM的存儲空間變大，PNS中切塊的選擇也可以相應(yīng)的增大，因此與切塊相交的規(guī)則按一定比例減少，額外開銷也隨之降低.

圖6 不同TCAM大小的額外開銷

6 結(jié)束語

本文在現(xiàn)有的TCAM大小下，思考如何將流規(guī)則更高效的放置在交換機上.本文提出了面向SDN的流規(guī)則拆分分配算法，選擇ACL作為高級策略，分別設(shè)計了基于矩形切塊拆分算法在路徑上放置與之相關(guān)的高級策略規(guī)則子集的PNS算法和基于平均拆分算法在路徑上放置全部規(guī)則集策略的AVS算法.

本文設(shè)計的流規(guī)則放置算法，取得了一定的研究成果.但在流規(guī)則拆分過程中，可能會導(dǎo)致網(wǎng)絡(luò)狀態(tài)不穩(wěn)定，因此如何評估和降低拆分對網(wǎng)絡(luò)狀態(tài)的影響將作為下一步工作.當(dāng)拓?fù)浠蛘吒呒壊呗园l(fā)生變化時，如何提高魯棒性和容錯能力同樣是下一步工作的重點.