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

姜臘林，張亞南，熊 兵

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

1 引 言

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

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

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

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

2 OpenFlow流表拆分壓縮算法

2.1 匹配字段關(guān)系

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

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

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

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

(1)

(2)

2.2 算法思想

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

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

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

(3)

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

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

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

3 算法實現(xiàn)

3.1 算法流程

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

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

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

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

3.2 流表劃分過程

為簡化起見，以圖2所示的流表為例，描述本文所提算法的工作過程.在圖2中，每條流表項包含7個匹配字段：協(xié)議類型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).

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

圖2 流表Fig. 2 Flow table

圖3 流表劃分結(jié)果Fig. 3 Result of flow Table splitting

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

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

4 實 驗

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

圖5 流表項數(shù)量Fig. 5 Number of flow entries

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

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

5 總 結(jié)

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

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

[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.

附中文參考文獻(xiàn)：

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

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

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