一種高效的OpenFlow流表拆分壓縮算法

姜臘林，張亞南，熊 兵

1(長沙理工大學 計算機與通信工程學院，長沙 410114) 2(長沙理工大學 綜合交通運輸大數據智能處理湖南省重點實驗室，長沙 410114)

1 引 言

在軟件定義網絡(Software Defined Networking，SDN)中，南向接口協議完成控制平面與數據平面交互，實現網絡的數控分離，使得SDN具有強大的可編程性.OpenFlow協議是當前SDN中最為成熟的南向接口協議之一，它使得控制平面可以完全控制數據平面的轉發行為，開放了基于流表的交換機以及集中式的控制器，使得網絡的編程和控制變得十分靈活，大大降低了網絡創新的難度.然而OpenFlow協議還面臨很多未解決的問題，流表的存儲問題就是其中之一.OpenFlow將網絡協議棧扁平化，各個網絡字段都可以作為流表的匹配域，并通過通配符掩碼支持任意字段的組合.在OpenFlow規范1.0版中定義了12元組匹配字段，OpenFlow1.4版本中則定義了41項可匹配字段.豐富的流表匹配字段實現了網絡流的細粒度管理，大大提高了網絡的靈活性，但也帶來了流表規模龐大的問題.OpenFlow交換機通常采用三態內容尋址存儲器(ternary content addressable memory，TCAM)裝載流表，以支持靈活高效的查找.但其價格昂貴，能耗高，導致容量有限(4K-32K)，一般為8K左右.這就導致OpenFlow流表存儲成為一個嚴峻的挑戰.因此，如何有效減少OpenFlow流表存儲空間，是SDN走向實際應用部署亟待解決的問題.

針對OpenFlow交換機中TCAM資源緊缺的問題，目前有很多學者展開研究工作.Kannan[1]等人提出緊湊TCAM方案，引入流標識符來替代流表項的概念，減少在TCAM中標識流所需比特，從而減少OpenFlow流表項大小，同時降低TCAM能耗.Banerjee[2]等人利用SDN數據交換TCAM訪問速率和操作特性，提出一種標簽嵌套方法Tag-in-Tag，將流表項替換成兩層簡短標簽(用于數據包路由的路徑標簽和將數據包關聯到流的流標簽)，從而使TCAM容納更多的流表項，同時降低每條流的能耗.以上兩項工作可有效減小流表存儲空間，但是并沒有考慮到重復的流表項，優化效果還可以進一步提升.Bedhiaf[3]等人提出一種OpenFlow v1.1虛擬交換機的TCAM資源分配機制，應用遺傳算法和禁忌搜索算法解決多目標問題，從而可根據最小化分配能耗和最大化切片公平性之間的用戶偏好，在TCAM資源上進行靈活分配切片表來降低能耗.Veeramani[4]等人結合前綴重疊、前綴最小化和零壓縮三種方法，對OpenFlow交換機中TCAM存儲的轉發表進行虛擬壓縮，減少前綴值的長度可達50至60%.以上這些工作均是面向OpenFlow交換機TCAM提出虛擬壓縮方案，來節省流表存儲空間.

郭澤華[5]等人提出一個轉發方案JumpFlow，使用包首部中的VLAN標識符(VID)攜帶路由信息，反應式地在交換機中放置流表項，從而實現SDN中低的平衡的流表使用率.冷冰[6]等人提出一個流表簡化方案FTRS，根據所有流表項生成一個二叉樹，進一步移除空節點，從而消除冗余流表項，但沒有考慮到在SDN中，多播樹的節點和鏈接會受到容量的約束.羅壽西[7，8]等人提出一個對非前綴規則進行快照聚合的離線方案FFTA，以聚合感知的方式將非前綴規則劃分成前綴可置換的分區，進而應用最優的前綴聚合技術.在此基礎上，設計增量式的流表快速聚合方案iFFTA，在原始規則更新時，利用規則的順序無關性和結構信息，立即合并更新.該方案切實可行，極大簡化了聚合規則的更新，且壓縮率的損失在可接受的范圍內.然而，當出現新的版本號時，所有的規則都需要復制，將會造成大量的規則空間開銷.

葛敬國和陳智等人提出了一種啟發式的 OpenFlow 流表存儲空間優化算法H-SOFT[9]，通過分析OpenFlow 流表結構中各個字段之間的共存和互斥關系，將一個 OpenFlow 流表劃分成多個規模較小的子流表，進而根據字段匹配類型將子流表切分成多個字段[10]，并采用合適的算法和硬件進行存儲和查找，得到字段匹配結果后再結合匯總表查找得到子流表的匹配結果，從而有效減小流表規模，降低SDN交換機的TCAM資源需求與能耗.然而，這兩個工作都是對于取值重復不多的字段，其存儲開銷可能反而會增加，優化效果有待改進.劉中金等人[11]等提出一種 OpenFlow 多級流表結構及其映射算法，將單一流表映射到多級流表中進行高效存儲和查找，可節省17%以上TCAM 資源.然而，該算法在進行流表分級時，匹配集合的表項寬度會因為個別字段值的重復次數多而變大，使得總體壓縮效果顯著下降.針對上述問題，本文利用匹配域間共存互斥關系，將流表劃分出多個規模較小的子流表，進而針對每個字段建立判定條件進行壓縮，以實現OpenFlow流表的高效存儲.

2 OpenFlow流表拆分壓縮算法

2.1 匹配字段關系

流表是一些針對特定“流”的策略表項集合，用于數據分組的查詢和轉發[[12].流表往往包含大量流表項，每個流表項表征一個“流”及其對應的處理方法.匹配域作為交換機匹配數據包的依據，是流表項的關鍵組成部分.匹配域的字段主要來源于各層網絡協議首部，提供了一層到四層的網絡控制信息.以OpenFlow1.0 的12元組為例，如圖1所示.交換機入口(Ingress Port)屬于物理層；源MAC地址(Ether_src)、目的MAC地址(Ether_dst)、以太網類型(Ether_type)、VLAN標簽(VLAN_id)、VALN優先級(VLAN_priority)屬于數據鏈路層；源IP(IP_src)、目的IP(IP_dst)、IP協議(IP_proto)、IP服務類型(IP_ToS bits)屬于網絡層；TCP/UDP源端口(TCP/UDP_src port)、TCP/UDP目的端口(TCP/UDP_dst port)屬于傳輸層.

由于各個匹配字段分布的協議層次不同、隸屬的協議類型也不同，因而存在共存互斥關系.在同一層中屬于同一節點的匹配字段存在共存關系，在同一層分布不同節點的匹配字段則存在互斥關系.對于兩個匹配字段fi、fj，如果fi、fj同時存在或者同時不存在則為共存關系，如果字段fi存在則字段fj就不存在，反之亦然，則為互斥關系.例如，、、< ETH_SCR，ETH_DST >存在共存關系，而，、、 存在互斥關系.

圖1 OpenFlow1.0包頭域分布協議樹Fig. 1 OpenFlow1.0 protocol tree distribution of header fields

匹配字段之間的共存互斥關系可以用0-1矩陣描述.以8個典型字段(IPV4_SRC、IPV4_DST、IPV6_SRC、IPV6_DST、TCP_SRC、TCP_DST、UDP_SRC、UDP_DST)為例，其共存和互斥關系的二維矩陣分別如式(1)和式(2)所示.其中Cij=1代表任意兩個匹配字段fi、fj存在共存關系，Mij=1則表示任意兩個匹配字段fi、fj存在互斥關系.

(1)

(2)

2.2 算法思想

根據上述匹配字段之間的共存和互斥關系，將流表中的所有匹配字段劃分成多個字段集合，組成多個規模較小的子流表.字段劃分規則如下：對于存在共存關系的匹配字段，則將其劃分到相同子流表的字段集合中；對于存在互斥關系的匹配字段，則將其劃分到不同子流表的字段集合中.依據這一規則，可將規模龐大的原始流表劃分為多個規模較小的子流表.在此基礎上，將子流表中取值重復較多的字段劃分出來單獨存儲，以進一步減少存儲空間.為便于理解，在表1給出了下列公式中各個變量及其含義.

表1 變量及其含義Table 1 Variables and their meanings

假設現有一個流表，包含N條流表項，每條流項包含M個匹配字段，流表字段集合記為F={fi|1≤i≤M}.根據所有匹配字段之間的共存和互斥關系，將流表拆分成k(k≤M)個子流表，其中，第i個子流表的匹配字段集合Fi={fij|1≤j≤Mi}，且Fij?F.Fi滿足如下關系：

(3)

對于單個子流表，某些字段的取值可能重復次數較多，如：IP協議字段的取值主要是7(UDP)和16(TCP)，因而可能存在進一步壓縮的空間.下面嘗試劃分子流表，以進一步減少存儲空間.首先，統計子流表中各個字段取值互不重復的數量，并按照從小到大排序.然后，從子流表中依次選取一個字段，將其單獨存放或者和已取出的字段集合一起存放，作為二級子流表.最后，計算與原始子流表相比，各種情況下存儲空間的變化量，從而找出最優的子流表存儲方案.

(4)

(5)

(6)

(7)

(8)

(9)

綜合式(6)和式(9)可得，第k個子流表中的第i個字段取出后與第j個二級子流表組合或單獨存放的存儲空間變化量為：

(10)

根據式(10)，可計算某個字段從子流表中取出后，不同存儲方式的存儲空間變化量.然后，找出所有變化量中的最小值.若該值小于零，則相應的方案即為該字段當前最優的存儲方案；否則，該字段存儲在原子流表中.依據上述方法，依次處理子流表中的每個字段，最終確定任意子流表的最佳存儲方案.

3 算法實現

3.1 算法流程

述算法思想，本文所提的流表拆分壓縮算法如表2所示.該算法分為兩大步驟：(1)對于一個給定的流表，基于上述共存矩陣和互斥矩陣，將流表的所有字段劃分為多個字段集合，形成多個子流表；(2)對于劃分后的每個子流表，根據存儲空間變化量依次考察其各個字段的存儲方式，確定該子流表的最優存儲方案.

對于流表ft，首先將其第一個匹配字段f1單獨作為一個子流表.然后，從流表ft依次取出字段fi，判定該字段和現有子流表的字段集合是否存在共生關系或互斥關系.對于某個子流表字段集合Fj，若字段fi和字段集合Fj中的字段具有共生關系，則將該字段加入到子流表字段集合Fj中；否則，將字段fi單獨作為一個子流表存放，并放入到相應新增的字段集合Fn+1中.所有字段劃分完畢后，原始流表中的字段取值改為相應子流表中表項取值的存儲地址，成為匯總表.

表2 OpenFlow流表拆分壓縮算法.Table 2 Flow Table split and compress algorithm.

在上述算法中，流表拆分為一級子流表過程的時間復雜度為O(n)，一級子流表拆分為二級子流表過程的時間復雜度為O(n*m).因此，本文所提的算法的時間復雜度為O(n*m).

3.2 流表劃分過程

為簡化起見，以圖2所示的流表為例，描述本文所提算法的工作過程.在圖2中，每條流表項包含7個匹配字段：協議類型IP_PROTO(8bit)、源IP地址IP_SRC(32bit)、目的IP地址IP_DST(32bit)、TCP源(16bit)端口TCP_SRC(16bit)、TCP目的端口TCP_DST(16bit)、UDP源端口UDP_SRC(16bit)、UDP目的端口UDP_DST(16bit).

第一步，根據式(1)和式(2)所示的字段共存和互斥關系矩陣，流表所有字段劃分為三個字段集合：字段集合1(含3個字段IP_PROTO、IP_SRC、IP_DST)，字段集合2(含2個字段TCP_SRC、TCP_DST)，字段集合3(含2個字段UDP_SRC、UDP_DST)，進而存為3個子流表.同時，原始流表中的相應字段取值改為相應子流表中對應取值的存儲地址(寬度為3bit)，成為匯總表1，具體劃分過程如圖3所示.

圖2 流表Fig. 2 Flow table

圖3 流表劃分結果Fig. 3 Result of flow Table splitting

第二步，對上述三個子流表依次尋求更優的存儲方案.對于子流表1，其字段按互不重復取值數從小到大排序為IP_PROTO、IP_SRC、IP_DST.首先假設將字段IP_PROTO單獨存放，按式(10)計算得到空間變化量為小于零，表明該劃分方案可有效減少存儲空間.然后繼續考察字段IP_DST，計算其單獨存放以及與字段IP_PROTO組合存放之后的子流表的空間變化量，可知字段IP_DST單獨存放占用空間更少.最后考察字段IP_SRC，計算其單獨存儲以及分別與字段IP_PROTO、IP_DST組合存儲的空間變化量，可知該字段與IP_DST組合存放占用空間最少.因此，子流表1的最佳存儲方案是：字段IP_PROTO單獨存放為一個二級子流表，IP_SRC和IP_DST組合存放為另一個二級子流表，原子流表中的字段取值改為相應二級子流表的表項取值的存儲地址，成為二級匯總表2，具體劃分過程如圖4所示.同理可知，子流表2和子流表3的原始存儲方案占用空間最少.

圖4 子流表1劃分結果Fig. 4 Result of sub-flow Table 1 splitting

4 實 驗

實驗借助實際網絡樣本，將本文所提算法的流表壓縮性能分別與H-SOFT算法和多級流表映射算法進行比較.實驗選取江蘇省計算機網絡技術中心發布的兩個網絡流量樣本(TRACE20130418、TRACE20120922)作為測試數據集.這兩個數據集是按照1：4的比例從速率為10Gbps的高速網絡鏈路上采集而得，持續時間分別約為107秒和86秒.為了簡化起見，實驗選取網絡層和傳輸層的7個字段(IP_PROTO、IP_SRC、IP_DST、TCP_SRC、TCP_DST、UDP_SRC、UDP_DST)作為匹配域.實驗每10秒輸出一次流表，其流表項數量如圖5所示.從圖5可以看出：實驗選取的兩個數據集輸出流表的流表項個數分別為60K和80K條左右.

圖5 流表項數量Fig. 5 Number of flow entries

用本文所提算法、H-SOFT算法和多級流表映射算法，分別對上述流表進行壓縮，得到相應的流表壓縮率如圖6所示.H-SOFT算法主要通過壓縮流表項中的通配符，從而節省存儲空間.由于該算法未考慮流表項還存在重復取值這一情況，所以拆分后的流表還存在較大的可壓縮存儲空間.多級流表映射算法在進行流表分級時，匹配集合的表項寬度會因為個別字段值的重復次數多而變大，使得總體壓縮效果顯著下降.而本文所提算法，則進一步考慮到字段的不同存儲方案，確定子流表最優的存儲方案，從而實現更好流表壓縮的性能.從圖6中可以看出，本文所提算法的流表壓縮率要高于多級流表映射算法和H-SOFT算法.本文所提算法的流表壓縮率穩定在50%左右，H-SOFT算法的流表壓縮率在30%—40%左右，而多級流表映射算法的壓縮率只有25%左右.

圖6 流表壓縮率對比Fig. 6 Flow Table storage compression rate

5 總 結

本文提出了一種高效壓縮OpenFlow流表存儲空間的算法，首先基于匹配字段的共存互斥關系將流表拆分成多個規模更小、匹配字段更少的子流表，進而考慮字段的不同劃分情況，根據判定條件對子流表進行優化，從而達到存儲空間壓縮的目的，避免引入存儲地址變量會增大存儲開銷的問題，進而達到存儲空間壓縮的目的.實驗結果表明本文所提算法得出的流表存儲壓縮率穩定在50%—60%，高于H-SOFT算法和多級流表映射算法，可有效的提高流表空間的存儲效率.

由于流表存儲空間優化理論和應用研究還處于初期階段，許多問題還需要人們不斷探索和解決，本文所提算法還是局限在對靜態流表存儲空間的壓縮，如何實現動態流表的存儲壓縮就是進一步要做的研究工作.

[1] Kannan K，Banerjee S.Compact TCAM：flow entry compaction in TCAM for power aware SDN[C].In：Proceedings of the Distributed Computing and Networking,Springer Berlin Heidelberg，2013：439-444.

[2] Banerjee S，Kannan K.Tag-In-Tag：efficient flow
Table management in SDN switches[C].In：Proceedings of IEEE International Conference on Network and Service Management(CNSM)，Rio de Janeiro，Brazil，2014：109- 117.

[3] Bedhiaf I L，Burguin R，Cherkaoui O，et al.TCAM
Table resource allocation for virtual openflow switch[C].In：Proceedings of the Annual Mediterranean on Ad Hoc Networking Workshop(MedHoc)，Ajaccio，2013：128-132.

[4] Veeramani S，Kumar M，Mahammad S N.Minimization of flow
Table for TCAM based openflow switches by virtual compression approach[C].In Proceedings of Advanced Networks and Telecommuncations Systems(ANTS)，Kattankulathur，2013：1-4.

[5] Guo Z，Xu Y，Cello M，et al.JumpFlow：reducing flow
Table usage in software-defined networks[J].Computer Networks，2015，92(2)：300-315.

[6] Leng B，Huang L，Wang X，et al.A mechanism for reducing flow tables in software defined network[C].In：Proceedings of the 2015 IEEE International Conference on Communications(ICC)，London，2015：5302-5307.

[7] Luo S，Yu H，Li L M.Fast incremental flow
Table aggregation in SDN[C].In：Proceedings of the International Conference on Computer Communication and Networks，Shanghai，2014：1-8.

[8] Luo S，Yu H，Li L.Practical flow
Table aggregation in SDN[J].Computer Networks the International Journal of Computer & Telecommunications Networking，2015，92(P1)：72-88.

[9] Ge J，Chen Z，Wu Y，et al.H-SOFT：a heuristic storage space optimisation algorithm for flow
Table of OpenFlow[J].Concurrency & Computation Practice & Experience，2015，27(13)：3497-3509.

[10] E Yue-peng，Chen Zhi，Ge Jing-guo.An efficient implementation of storage and lookup for flow tables in OpenFlow [J].Science China：Information Science，2015，45(10)：1280-1288.

[11] Liu Zhong-jin，Li Yong，Su Li，et al.TCAM-efficient flow
Table mapping scheme for OpenFlow multiple-
Table pipelines[J].Tsinghua Univ( Sci & Technol)，2014，54：437-442.

[12] Zuo Qing-yun，Chen Ming，Zhao Guang-song，et al.Research on OpenFlow-based SDN technologies[J].Journal of Software，2013，24(5)：1078-1097.

附中文參考文獻：

[10] 鄂躍鵬，陳 智，葛敬國，等.一種高效的OpenFlow流表存儲與查找實現方法[J].中國科學:信息科學，2015，45(10)：1280-1288.

[11] 劉中金，李 勇，蘇 厲，等.TCAM存儲高效的OpenFlow多級流表映射機制[J].清華大學學報(自然科學版)，2014，54(4)：437-442.

[12] 左青云，陳 鳴，趙廣松，等.基于OpenFlow的SDN技術研究[J].軟件學報，2013，24(5):1078-109.