面向SDN的流規則拆分分配算法

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

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

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

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

1 引 言

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

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

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

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

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

3)仿真結果表明，與基準機制相比，本文所提出的算法可以明顯降低拆分后流規則的數量.

2 相關工作

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

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

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

3 網絡模型

3.1 網絡拓撲模型

網絡拓撲可以抽象為一個有向連接圖G=(V,E)，由基礎設備和鏈路組成，頂點集合V=(H,S)由主機集合H和交換機集合S組成.邊集合E由Esh和Ess組成，其中Ess表示交換機之間的通信鏈路，Esh表示交換機與主機之間的通信鏈路.

3.2 節點模型

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

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

Pcapi=Tcapi×THRTCAM×portion

(1)

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

3.3 數據流模型

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

3.4 流規則模型

本文的流規則模型表示為ri={pre,act,tim,pri}，其中pre為流規則的匹配域，act為流規則的動作域，本文ACL的動作域為act={Permit,Drop}，其中Permit表示允許轉發數據分組，Drop表示丟棄數據分組.tim為流規則的超時值，對于所有的ACL規則設置統一的固定超時值.pri為流規則的優先級.

4 算法設計

4.1 設計目標

(2)

(3)

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

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

4.2.1 交換機空間資源分配

(4)

(5)

(6)

(7)

(8)

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

算法1.交換機流規則空間分配算法

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

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

BEGIN:

1.FORi∈S

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

4.ENDFOR

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

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

7.ENDFOR

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

11.IF估計值>分配值

12. 重新執行交換機規則空間分配模塊；

13.ELSEIF估計值≤分配值

14. 執行規則集拆分分配模塊；

15.ENDIF

16.ENDFOR

17.END

4.2.2 矩形拆分分配算法

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

圖1 ACL規則集的幾何表示

(9)

(10)

(11)

(12)

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

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

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

輸出：在交換機上放置的規則.

BEGIN:

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

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

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

4.FORsi∈pi

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

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

8. 選擇矩形q′

9.ENDIF

10. 在當前交換機上安裝與矩形切塊q包含的規則集

11. 更新路徑相關策略規則；

14.ENDWHILE

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

16. 重新執行拆分模塊；

17.ENDIF

18.ENDFOR

19.ENDFOR

20.END

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

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

4.3.1 計算最值

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

4.3.2 平均拆分分配算法

(13)

NAVS

(14)

(15)

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

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

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

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

輸出：在交換機上放置的規則.

BEGIN:

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

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

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

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

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

7.WHEN安裝低優先級規則時

8.IF數據分組同時匹配高優先級規則

9. 在安裝了低優先級規則的交換機上安裝相應的高優先級

規則；

10.ENDIF

11.ENDWHEN

12.ENDFOR

13.END

5 性能評價

本節對設計的SDN流規則拆分分配算法進行仿真實現與性能評價.基于Mininet網絡仿真器和Floodlight控制器構建仿真實驗平臺，以此為基礎，分別從拆分后規則總數、運行時間和額外開銷三個方面對比設計的PNS、AVS流規則放置機制與基準機制.仿真環境詳細信息如表1所示.

表1 仿真環境

5.1 拓撲用例

本文從拓撲園中選擇了Darkstrand拓撲和ATT North America拓撲作為實驗拓撲.Darkstrand拓撲結構如圖2(a)所示，具有28個節點，31條邊，最大節點度Maxndeg為3，平均節點度Avgndeg為2.2，其中節點的度為連接該節點的邊數.ATT North America拓撲結構如圖2(b)所示，具有25個節點，57條邊，其中最大節點度Maxndeg為10，平均節點度Avgndeg為4.2.

圖2 網絡拓撲結構

5.2 對比機制

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

5.3 性能評價

本文使用ClassBench[16]生成10000條高級策略規則集，分別在實驗拓撲上將本文提出的PNS和AVS機制與對比機制APS在拆分后生成的流規則總數、運行時間這兩個方面進行對比實驗，以及對本文提出的機制所產生的額外開銷進行實驗.

5.3.1 拆分后生成的流規則總數

流規則總數為將ACL規則進行拆分分配后，網絡中的流規則數量.流規則增加率為拆分分配后的流規則總數與ACL原規則數相比增加的比例.規定每個交換機的TCAM可存儲2000條規則，當網絡中的總規則數超過總容量時，將無法放置規則.

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

圖3 不同拓撲上拆分后流規則總數對比

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

5.3.2 運行時間

將三種算法分別在路徑為16的Darkstrand拓撲和路徑數為28的ATT North America拓撲下運行，比較其運行時間.如圖4所示，隨著路徑的增加，時間也不斷增加.三種機制都以路徑為基本計算單位.AVS使用線性時間拆分，所以運行時間最短，APS需要遞歸尋找樞軸位，運行時間次之.PNS機制雖然在兩種拓撲上產生的規則總數最低，但是由于其需要為每條路徑上的每個交換機都遞歸的尋找拆分切塊，因此運行時間也最長.

圖4 不同拓撲上算法運行時間對比

5.3.3 額外開銷

額外開銷指的是流規則放置機制使用拆分分配算法生成的額外規則與原高級策略規則總數的比值，可以體現流規則放置機制的性能.在對額外開銷進行測試時，需要測試算法在不同跳數路徑下的額外開銷，由于Darkstrand拓撲結構相對簡單，因此在ATT North America拓撲下，對算法進行測試.

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

圖5 不同跳數的路徑上產生的額外開銷

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

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

6 結束語

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

本文設計的流規則放置算法，取得了一定的研究成果.但在流規則拆分過程中，可能會導致網絡狀態不穩定，因此如何評估和降低拆分對網絡狀態的影響將作為下一步工作.當拓撲或者高級策略發生變化時，如何提高魯棒性和容錯能力同樣是下一步工作的重點.