SDN中一種基于多級流表的功能組合方法

段 通，蘭巨龍，胡宇翔，劉釋然

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州 450002)

?

SDN中一種基于多級流表的功能組合方法

段 通，蘭巨龍，胡宇翔，劉釋然

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州 450002)

軟件定義網(wǎng)絡(luò)(Software-Defined Network,SDN)中的網(wǎng)絡(luò)應用往往需要實現(xiàn)多種功能以滿足上層業(yè)務(wù)需求，而如何對運行在控制器上的功能模塊進行編排以完成數(shù)據(jù)包的多功能組合處理是一個仍待解決的問題.針對該問題，本文提出基于多級流表的功能并行和串行組合方案；其次，提出與任意多級流表交換機相適配的功能組合算法；最后，在Ryu控制器中添加功能組合模塊并基于NetFPGA-10G節(jié)點完成了功能組合的原型實現(xiàn).仿真實驗與結(jié)果表明，與現(xiàn)有功能組合方案相比，所提功能組合方法降低了流處理時延及表項存儲開銷.

軟件定義網(wǎng)絡(luò);多級流表;功能組合;Ryu控制器

1 引言

軟件定義網(wǎng)絡(luò)[1](Software-Defined Network,SDN)將控制功能轉(zhuǎn)移到控制平面并為應用層提供可編程接口，從而實現(xiàn)了靈活的網(wǎng)絡(luò)功能定制.現(xiàn)有網(wǎng)絡(luò)業(yè)務(wù)往往需要對數(shù)據(jù)包進行多重功能處理(比如路由、監(jiān)控、接入控制和負載均衡等)，如果在單個網(wǎng)絡(luò)應用內(nèi)涵蓋這些功能，會導致應用開發(fā)復雜度高、難以適應多種多樣的業(yè)務(wù)需求[2].對此，C Monsanto等人[2,3]提出將SDN應用轉(zhuǎn)化為多個可獨立處理數(shù)據(jù)流的功能模塊的組合，該方法在降低應用開發(fā)復雜度的同時也提高了應用的靈活性.其中如何對運行在控制器之上的功能模塊進行組合，以使得多個功能模塊生成的表項同時對數(shù)據(jù)包產(chǎn)生作用，是業(yè)界研究的重點.

為實現(xiàn)SDN中的功能模塊組合，文獻[3]中提出并行的模塊化編程語言Frenetic，將功能模塊生成的流表項進行組合以完成對數(shù)據(jù)包的多功能并行處理.作者隨后又提出Pyretic[2]編程語言，Pyretic支持串行功能模塊的組合，應用通過下發(fā)組合策略的方式將功能模塊生成的表項組合起來，實現(xiàn)功能模塊對數(shù)據(jù)流的多功能串行處理.以上研究基于OpenFlow單級流表[4]實現(xiàn)，面臨組合表項數(shù)量較大、功能組合復雜度較高等問題.Hesham Mekky等人[5]基于網(wǎng)絡(luò)應用感知[6]在SIGCOMM’14上提出在交換機軟件部分添加存放功能組合策略的應用表，通過數(shù)據(jù)流與應用表的匹配依次調(diào)用策略指示的上層應用，最終形成功能組合表項，達到功能組合的效果.該功能組合方法不僅要修改數(shù)據(jù)平面和控制平面之間的部分交互協(xié)議，還要不停調(diào)用上層應用，復雜度較高.此外，文獻[7]將功能組合分散到多個交換機內(nèi)進行，其方法系統(tǒng)復雜度高、且未規(guī)范使用多級流表，并不符合SDN控制器發(fā)展的趨勢.文獻[8～10]利用SDN的集中式控制將數(shù)據(jù)流導向網(wǎng)絡(luò)功能部署的節(jié)點，實現(xiàn)對數(shù)據(jù)流的功能組合操作，但其功能部署于中間件內(nèi)，并未考慮在控制器之上的功能應用.Heng Pan等人提出FlowAdapter[11]的交換機實現(xiàn)架構(gòu)，旨在利用多級流表進行規(guī)則的合并和拆分，從而將控制器下發(fā)的多級流表轉(zhuǎn)化為與底層適配的多級流表.其方法雖然不是針對功能組合，但其表項合并和拆分的方法為多個功能的表項組合提供了參考.

基于以上分析，本文提出基于OpenFlow多級流表[12]的SDN功能模塊組合方法(Network Function Composition,NFC)及其具體組合算法，并且在Ryu控制器中添加功能組合模塊實現(xiàn)了所提功能組合方法的原型系統(tǒng).本文主要創(chuàng)新點有：(1)利用多級流表進行SDN功能組合；(2)提出了與任意多級流表交換機適配的功能組合算法；(3)在SDN控制器內(nèi)實現(xiàn)了功能組合模塊.

2 概念描述

作為SDN最成熟的交換機-控制器交互協(xié)議，OpenFlow1.0協(xié)議采用十二元組構(gòu)成的單級流表結(jié)構(gòu)，支持對數(shù)據(jù)流操作的功能定制.單級流表的匹配字段長度長達252位，鑒于一般網(wǎng)絡(luò)功能所需的匹配字段長度不足100位，因此其在實際部署和應用中面臨的主要問題之一就是表項存儲資源開銷問題.對此，標準化組織提出基于多級流表的交換機結(jié)構(gòu)[12]，它將流表進行特征提取，進而將匹配過程分解成多個步驟，形成流水線的處理形式，不僅減小了表項的存儲開銷，也增加了上層配置的靈活性.本文采用多級流表實現(xiàn)SDN中的網(wǎng)絡(luò)功能組合.

2.1 功能組合概念描述

首先，描述本文所使用的基本概念，作為后續(xù)功能組合方案及算法設(shè)計的基礎(chǔ).

定義1 功能，指在SDN控制器上運行的程序模塊(或應用)，可通過控制器提供的北向接口向控制器下發(fā)功能表項，以完成對數(shù)據(jù)流的相應處理.不同網(wǎng)絡(luò)功能的包處理過程所涉及到的匹配域種類和動作類型不同，如常用安全功能的ACL表需要以IPv4協(xié)議的源/目的IP地址作為匹配域，動作類型為轉(zhuǎn)發(fā)或丟棄；NAT功能則以IP地址作為匹配域，動作類型為修改IP字段.

定義2 功能并行組合，指通過將功能生成的表項進行合并，達到多個功能同時作用于數(shù)據(jù)包的效果.例如對于功能A和功能B，用A|B表示A和B的并行組合：若數(shù)據(jù)包能夠匹配功能A生成的表項，則執(zhí)行功能A的動作；若能夠匹配功能B生成的表項，則執(zhí)行功能B的動作；若同時兩者同時滿足，則A和B的動作均需執(zhí)行.

定義3 功能串行組合，指將功能生成的表項進行合并，達到多個功能相繼作用于數(shù)據(jù)包的效果.例如對于功能A和功能B，用A>>B表示A和B的串行組合：若數(shù)據(jù)包能夠匹配功能A生成的表項，則執(zhí)行功能A的動作；經(jīng)過功能A處理后的數(shù)據(jù)包繼續(xù)匹配功能B的表項，若匹配成功則執(zhí)行功能B的動作.

定義4 組合策略，指定需要對相應數(shù)據(jù)包進行的功能組合處理.組合策略由目標集和功能集組成，其中目標集指定所需處理的數(shù)據(jù)流，功能集指定數(shù)據(jù)流處理所需的功能及其組合方式.例如組合策略P=match(srcip=p)[A|B]表示對源IP為p的數(shù)據(jù)流執(zhí)行A|B的功能操作.

2.2 功能組合方案

多級流表以其靈活的流表跳轉(zhuǎn)和連接特性為功能組合提供了更加靈活的方案，通過示例對基于多級流表的功能組合方法NFC進行說明.為方便與Frenetic、Pyretic等經(jīng)典方法進行對比，本文采用文獻[2]中提供的3種功能的示例表項(見圖1(a)、(b)、(c))，利用多級流表分別進行并行和串行功能組合，組合結(jié)果見圖1(d)、(e).

其中Route功能根據(jù)目的IP匹配進行端口轉(zhuǎn)發(fā)，如圖1(a)；Monitor功能根據(jù)源/目的IP進行計數(shù)，如圖1(b)；Load-Balance功能將來自不同主機的數(shù)據(jù)流分別重新分配路由，如圖1(c).假設(shè)交換機多級流表中源IP和目的IP的匹配域分別位于表1和表2中，則對于Route和Monitor的并行組合，首先匹配源IP，若匹配成功則跳轉(zhuǎn)至表2；若未匹配到源IP，則通過Table-miss項跳轉(zhuǎn)至表2，以實現(xiàn)路由的同時完成對數(shù)據(jù)流的監(jiān)控，如圖1(d).對于Load-Balance和Route的串行組合，考慮到Load-Balance功能會修改數(shù)據(jù)包的目的IP，導致對Route的匹配產(chǎn)生影響，因此在表2的表項中將Route目的IP的匹配置換成Load-Balance的目的IP匹配，以達到負載均衡和路由的串行處理效果，如圖1(e).

3 功能組合算法

基于以上標準化概念描述，本文提出基于多級流表的SDN功能組合問題.

定義5 功能組合問題.給定交換機多級流表結(jié)構(gòu)、組合策略和功能表項，在數(shù)據(jù)包滿足策略目標集的前提下，根據(jù)各級流表的匹配域?qū)δ鼙眄椷M行合并，并下發(fā)到交換機中，以實現(xiàn)對數(shù)據(jù)包的并行或串行處理.

為形式化地描述功能組合問題，本文將使用下列符號：

表1 主要的符號定義及其意義

假設(shè)1 各級流表內(nèi)的匹配域無重疊.多級流表將各個匹配域分散到多個流表中，從而減小了表項空間耗費.若各級流表之間包含相同的匹配域，將會增加控制器下發(fā)表項時的難度，同時也違背了多級流表設(shè)計的初衷.因此除非特殊廠商的要求，各級流表包含的匹配域不同.

令功能P的一條表項FP={p1,p2,…,pk1;ap}，功能Q的一條表項FQ={q1,q2,…,qk2;aq}，則P|Q和P>>Q的表項組合算法分別描述如下.

3.1 并行組合算法

由于功能并行組合不用考慮功能P處理對功能Q匹配產(chǎn)生的影響，因此并行組合的關(guān)鍵在于匹配字段放置和動作字段放置.對于匹配字段的放置，需要判斷匹配字段所屬的流表，并使用Goto指令對各匹配域所在的流表進行連接；對于動作字段的放置，需要判斷所屬流表編號最大的匹配域，并將動作字段放置在該匹配域所屬的流表內(nèi).

考慮功能表項最多包含K個匹配域，因此并行組合算法的復雜度為O(NK)，也即復雜度與多級流表級數(shù)和匹配域個數(shù)成線性關(guān)系.

3.2 串行組合算法

由于功能P的數(shù)據(jù)包處理可能影響到功能Q的數(shù)據(jù)包匹配，因此需要首先判斷功能P的動作會不會影響功能Q的匹配：若產(chǎn)生影響則先對受到影響的匹配字段進行操作，然后進行表項放置；否則對P和Q的表項依次放置，同時考慮功能Q的流表在前的情況.

對于串行組合算法，要考慮功能P對功能Q可能產(chǎn)生的影響，若P對Q的匹配域產(chǎn)生影響，則算法復雜度為O(2NK)，否則算法復雜度為O(NK).因此串行組合算法的復雜度也為O(NK).

3.3 多個功能的組合方法

以上算法針對兩個功能的組合，其方法對于三種或三種以上的功能表項組合同樣適用.如對于三個網(wǎng)絡(luò)功能的表項FP、FQ、FR，并行組合算法在算法1的末行加入Map(FR)即可；串行組合算法則先將算法2中得到的FP>>Q看做一個功能的表項，再按照算法2進行FP>>Q與FR的合并.三個以上功能組合方法以此類推.超過兩個功能組合時，由于組合后的功能表項可能繼續(xù)與其他表項再次組合，因此組合算法的復雜度最壞可達O(N^2).考慮到OpenFlow多級流表級數(shù)一般在10級以內(nèi)，因此即使O(N^2)的復雜度也對控制器的計算能力也構(gòu)不成主要影響因素.

4 基于Ryu控制器的原型實現(xiàn)

文獻[5]將功能組合模塊放置在交換機軟件內(nèi)，并修改OpenFlow數(shù)據(jù)流消息，從而使得交換機軟件可以向控制器調(diào)用所需組合的功能.該種在數(shù)據(jù)平面調(diào)用控制平面功能的方法的困難之處在于需要修改數(shù)據(jù)平面和控制平面的標準交互協(xié)議，導致復雜度較高且難以推廣.本文提出在控制平面增加功能組合模塊，通過直接調(diào)用控制器內(nèi)的功能應用實現(xiàn)組合.

4.1 方案設(shè)計

本文所提功能組合方法NFC的系統(tǒng)整體方案設(shè)計如圖2所示，該架構(gòu)分為數(shù)據(jù)平面和控制平面，其中數(shù)據(jù)平面由多級流表交換機組成，完成對數(shù)據(jù)流的處理；控制平面內(nèi)部增加功能組合模塊，根據(jù)接收到的組合策略調(diào)用上層應用，完成組合表項的下發(fā).

功能組合模塊的引入改變了SDN控制器處理數(shù)據(jù)流的方式，具體處理步驟如圖2所示.首先管理員或應用向功能組合模塊下發(fā)組合策略，用于選定組合所需功能及組合類型，見步驟0.數(shù)據(jù)流到達交換機后，與交換機中流表進行匹配，若匹配成功則執(zhí)行相應數(shù)據(jù)包處理；若無匹配則上傳至控制器，見步驟1.數(shù)據(jù)包上傳至控制器后交由功能組合模塊處理，見步驟2.功能組合模塊接收到數(shù)據(jù)包后根據(jù)組合策略將數(shù)據(jù)包發(fā)送至相應功能應用，見步驟3.若數(shù)據(jù)包不是組合策略需要處理的數(shù)據(jù)包，則將數(shù)據(jù)包交給控制器其他模塊進行處理.功能應用接收到數(shù)據(jù)包后通過功能計算得到相應表項，下發(fā)至控制器，見步驟4.功能組合模塊接收到應用下發(fā)的功能表項計算功能組合表項并下發(fā)至交換機，見步驟5.數(shù)據(jù)流后續(xù)數(shù)據(jù)包直接在交換機內(nèi)根據(jù)下發(fā)的流表項進行處理并轉(zhuǎn)發(fā)，見步驟6.

4.2 原型系統(tǒng)實現(xiàn)

目前，本文的多級流表節(jié)點采用項目組已有的在NetFPGA-10G[13]平臺上的開發(fā)成果，支持四級流表的流水線處理.原型系統(tǒng)實現(xiàn)框架如圖3所示，底層多級流表各匹配域分布如圖4所示.每級流表的動作模塊可完成協(xié)議規(guī)定的動作，如轉(zhuǎn)發(fā)、丟棄、修改字段、添加VLAN標簽等，可實現(xiàn)如路由、轉(zhuǎn)發(fā)、安全、接入控制、負載均衡、NAT等功能.與NetFPGA相連的主機作為交換節(jié)點的軟件部分，負責對硬件的流表下發(fā)和與控制器的交互.

控制平面采用支持多級流表的Ryu[14]控制器，該控制器自帶一些編寫好的應用模塊，并且為應用組件開發(fā)定義了良好的API，使得開發(fā)者可以簡單地創(chuàng)建新的網(wǎng)絡(luò)管理與控制應用.本文利用Ryu已有的功能模塊(Firewall,Router,Switching hub)以及新開發(fā)的功能組合模塊完成功能組合的原型驗證，見圖3.

5 組合性能仿真與分析

本節(jié)從兩方面對本文所提功能組合方法進行驗證.首先，與文獻[6]中基于數(shù)據(jù)平面的功能組合模塊做性能對比測試，驗證基于控制平面的功能組合的性能優(yōu)勢；然后，通過與其他編程語言[2,3]的功能組合機制做對比實驗，驗證NFC在資源占用和計算復雜度方面的優(yōu)勢.

5.1 性能分析

為驗證NFC的性能優(yōu)勢，通過實驗與文獻[6]中基于數(shù)據(jù)平面實現(xiàn)的功能組合模塊(Application-aware)進行對比分析.使用網(wǎng)口帶寬為10Gbps的數(shù)據(jù)包測試儀發(fā)送數(shù)據(jù)流，圖5對比了兩種方案的平均數(shù)據(jù)包處理時延，圖中[1]代表Application-aware，[2]代表NFC.

實驗結(jié)果表明，相比于Application-aware在數(shù)據(jù)平面內(nèi)添加功能組合模塊，NFC在處理數(shù)據(jù)流時的時延明顯較小，這是由于在控制器內(nèi)調(diào)用功能模塊比在數(shù)據(jù)平面內(nèi)調(diào)用控制器內(nèi)的功能模塊所需的時間少.此外，從實驗結(jié)果可知，NFC的源地址改寫所帶來的額外時延要比Application-aware大，這是由于對于單純的轉(zhuǎn)發(fā)功能，NFC依然要經(jīng)過控制器內(nèi)的功能組合模塊進行判斷；而在無功能組合時，Application-aware不需調(diào)用應用表，也不需控制器的參與，因此在低流速率情況下，Application-aware有無功能組合的處理時延相差較小.

5.2 組合效率分析

多級流表相比單級流表的處理流程更為復雜，因此其組合表項的計算復雜度有所提高；但同時多級流表分散了各個匹配域，使得表項存儲開銷有大幅下降.實驗選取文獻[2]中提供的三種功能實例表項(Monitor、Route、Load Balancer)，分別隨機生成1000～7000次組合策略，仿真平臺同5.1節(jié).圖6對比了NFC與Frenetic、Pyretic組合表項生成時間.

仿真結(jié)果表明，相比于Frenetic和Pyretic，NFC生成組合表項的時間復雜度較高.這是由于相比于單級流表的表項組合，多級流表的表項組合需要針對各級流表的匹配域進行判斷及表項拆分，這增加了額外的計算復雜度.

圖7對比了針對上述三種功能表項，NFC與Frenetic、Pyretic方法生成組合表項的流表存儲空間占用(按照一般的交換機設(shè)計，流表項中的匹配字段放置在TCAM中，動作字段放置在SRAM中).在給定的三種功能的示例表項情況下，串行功能組合和并行功能組合所占用存儲空間相同，因此僅列出一項.實驗結(jié)果表明，由于多級流表對單級流表的各個匹配域進行了拆分，因此其匹配域所占用的存儲空間明顯比單級流表表項?。坏捎诙嗉壛鞅砑墧?shù)增多，因此動作字段所占存儲空間相對較大.NFC在SRAM資源使用與Frenetic相當?shù)那闆r下TCAM資源節(jié)省了90%，在SRAM資源使用比Pyretic高的情況下TCAM資源節(jié)省了75%.而由于TCAM的存儲成本要比SRAM高出很多，因此NFC有效節(jié)省了交換機的存儲資源開銷.

考慮到相比于計算復雜度方面高出的20%的開銷，NFC在交換機流表存儲資源方面節(jié)省的75%的開銷更為寶貴[15]，因此NFC在實用性上優(yōu)于現(xiàn)有的基于單級流表的功能組合方法.

6 結(jié)論

本文提出基于多級流表的SDN功能組合方案并設(shè)計了并行和串行組合算法，且在Ryu控制器中添加功能組合模塊并基于NetFPGA-10G節(jié)點實現(xiàn)了功能組合的原型系統(tǒng).實驗結(jié)果表明，所提功能組合方法有效降低了流處理時延及流表存儲空間耗費.本文所提功能組合方法對SDN中的功能模塊組合具有一定實用價值.

[1]McKeown N.Keynote talk:software-defined networking[A].Proceedings of the IEEE INFOCOM[C].Rio de Janeiro,Brazil:IEEE,2009.1-11.

[2]Monsanto C,Reich J,Foster N,et al.Composing software-defined networks[A].Proceedings of NSDI’13[C].LOMBARD,IL:USENIX,2013.1-14.

[3]Foster N,Harrison R,Freedman M J,et al.Frenetic:a network programming language[A].Proceedings of ICFP[C].Tokyo,Japan:ACM,2011.279-291.

[4]Mckeown N,Anderson T,Balakrishnan H N,et al.Openflow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Commnication Review,2008,38(2):69-74.

[5]Hesham M Fang H,Sarit M,et al.Application-aware data plane processing in SDN[A].Proceedings of SIGCOMM’14[C].Chicago,USA:ACM,2014.13-18.

[6]Koponen T,Amidon K,Balland P,et al.Network virtualization in multi-tenant datacenters[A].Proceedings of NSDI’14[C].Seattle USA:USENIX,2014.203-216.

[7]段通，蘭巨龍，程國振.基于元能力的SDN功能組合機制[J].通信學報,2015,36(5):2015178-1-2015178-11.

Duan Tong,Lan Ju-long,Cheng Guo-zhen.Functional composition in software-defined network based on atomic capacity[J].Journal on Communications.2015,36(5):2015178-1-2015178-11.(in Chinese)

[8]Fayazbakhsh S K,Chiang L,Sekar V,et al.Enforcing network-wide policies in the presence of dynamic middlebox actions using flowtags[A].Proceedings of NSDI’14[C].Seattle USA:USENIX,2014.533-546.

[9]Qazi Z A,Tu C C,Chiang L,et al.SIMPLE-fying middlebox policy enforcement using SDN[A].Proceedings of SIGCOMM’13[C].HongKong,China:ACM,2013.27-38.

[10]Zhang Y,Beheshti N,Beliveau L,et al.StEERING：a software-defined networking for inline service chaining[A].Proceedings of the 21st IEEE International Conference on Network Protocols[C].Gottingen,Germany:IEEE,2013.1-10.

[11]Heng Pan,Hongtao Guan,Junjie Liu,et al.The flowadapter:enable flexible multi-table processing on legacy hardware[A].Proceedings of the 2nd ACM SIGCOMM workshop on Hot topics in software defined networking[C].NewYork:ACM,2013.85-90.

[12]OpenFlow v1.1 project[EB/OL].http://archive.openflow.org/wk/index.php/OpenFlow-v1.1,2012.

[13]NetFPGA-10G project[EB/OL].https://github.com/NetFPGA/NetFPGA-public/wiki,2013.

[14]Ryu controller project[EB/OL].https://osrg.github.io/ryu,2014.

[15]Curtis A R,Mogul J C,Tourrilhes J,et al.DevoFlow:scaling flow management for high-performance networks[A].Proceedings of the ACM SIGCOMM 2011 conference[C].New York,USA:ACM,2011.254-265.

段 通 男，1992年生于河南駐馬店.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士研究生.主要研究方向為可編程網(wǎng)絡(luò)數(shù)據(jù)平面.

E-mail:duantong21@126.com

蘭巨龍 男，1962年生于河北張北.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心總工程師、教授、博士生導師.主要研究方向為新一代信息網(wǎng)絡(luò)關(guān)鍵理論與技術(shù).

E-mail:ndscljl@163.com

A Function Composition Method of Software-Defined Network Based on Multiple Tables

DUAN Tong,LAN Ju-long,HU Yu-xiang,LIU Shi-ran

(NationalDigitalSwitchingSystemEngineering&TechnologyResearchCenter,Zhengzhou,Henan450002,China)

Network applications in Software-Defined Network (SDN) are always required to implement several functions to meet the network service demands,but how to arrange the function modules running on SDN controller to achieve multiple function packet processing is a problem to be solved.To compose the network functions,we introduced parallel and sequential composition schemes based on multiple tables;secondly,we put forward functional composition algorithms that can adapt with any multiple-table openflow switches;finally,we devised and implemented a Ryu-based control module which is used to do the function composition.Experimental results show that the method can reduce the storage cost and processing delay effectively compared with the existing schemes.

software-defined network;multiple tables;function composition;Ryu controller

2015-05-22;

2015-10-13;責任編輯：馬蘭英

國家973重點基礎(chǔ)研究發(fā)展規(guī)劃計劃(No.2012CB315901，No.2013CB329104);國家自然科學基金(No.61372121);國家863高技術(shù)研究發(fā)展計劃(No.2013AA013505)

TP393

A

0372-2112 (2016)11-2682-06

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.017