席孝強(qiáng)，蘭巨龍，段通，江逸茗

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

研究與開(kāi)發(fā)

SDN中一種基于拓?fù)渥儞Q的功能組合方法

席孝強(qiáng)，蘭巨龍，段通，江逸茗

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

現(xiàn)有軟件定義網(wǎng)絡(luò)（SDN）中的功能組合方法大多都在單節(jié)點(diǎn)內(nèi)進(jìn)行，均未考慮單節(jié)點(diǎn)交換機(jī)的功能承載力。為此，首先提出一種基于拓?fù)渥儞Q的功能組合方法，通過(guò)拓?fù)渥儞Q將功能組合分散到多個(gè)節(jié)點(diǎn)中進(jìn)行處理。其次，將拓?fù)渥儞Q建模成0-1線性規(guī)劃問(wèn)題并提出了綜合搜索算法進(jìn)行求解。最后，基于NetFPGA-10G和Ryu控制器完成了所提功能組合方法的原型系統(tǒng)實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有方法相比，所提出的功能組合方法在降低流處理時(shí)延和存儲(chǔ)開(kāi)銷的同時(shí)提高了組合效率。

軟件定義網(wǎng)絡(luò)；拓?fù)渥儞Q；功能組合；NetFPGA-10G

1 引言

軟件定義網(wǎng)絡(luò)[1]（software defined networking，SDN）將控制功能從底層網(wǎng)絡(luò)設(shè)備中剝離出來(lái)，實(shí)現(xiàn)了控制平面與數(shù)據(jù)平面相分離。其中，控制平面通過(guò)北向接口與應(yīng)用層交互以實(shí)現(xiàn)多樣的網(wǎng)絡(luò)業(yè)務(wù)功能，通過(guò)南向接口（OpenFlow[2]等）實(shí)現(xiàn)控制器與交換機(jī)的交互，使網(wǎng)絡(luò)功能以表項(xiàng)的形態(tài)存在于數(shù)據(jù)平面。SDN支持大數(shù)據(jù)、云計(jì)算等多樣化新興網(wǎng)絡(luò)業(yè)務(wù)，這些業(yè)務(wù)往往需要多個(gè)功能（如監(jiān)控、路由、負(fù)載均衡、NAT、接入控制等）共同作用于數(shù)據(jù)分組，然而，如果將各種不同的功能都包含于單個(gè)應(yīng)用內(nèi)，會(huì)導(dǎo)致不同功能生成的表項(xiàng)相互覆蓋，也會(huì)使網(wǎng)絡(luò)應(yīng)用中的功能邏輯變得錯(cuò)綜復(fù)雜，進(jìn)而增加應(yīng)用開(kāi)發(fā)難度。Monsanto C等人[3]指出模塊化可以降低SDN軟件系統(tǒng)開(kāi)發(fā)的復(fù)雜度，并提出將SDN中應(yīng)用轉(zhuǎn)為多個(gè)可以同時(shí)協(xié)作處理網(wǎng)絡(luò)數(shù)據(jù)分組的功能模塊組合，從而降低SDN應(yīng)用的邏輯復(fù)雜性并提高可擴(kuò)展性。產(chǎn)業(yè)界中，在城域網(wǎng)中SDN技術(shù)可以實(shí)現(xiàn)業(yè)務(wù)的智能控制與多樣化，通過(guò)利用策略和業(yè)務(wù)鏈中的功能組合，可以為不同用戶靈活定制差異化的業(yè)務(wù)服務(wù)。尤其是近年來(lái)在SDN中引入NFV技術(shù)，改變了設(shè)備狀態(tài)，簡(jiǎn)化和開(kāi)放了網(wǎng)絡(luò)能力，并逐漸凸顯出網(wǎng)絡(luò)功能在新型網(wǎng)絡(luò)體系結(jié)構(gòu)中的重要性，這就使得網(wǎng)絡(luò)功能編排成為產(chǎn)業(yè)界的一個(gè)研究熱點(diǎn)。

每個(gè)功能都會(huì)生成相應(yīng)的功能表項(xiàng)并下發(fā)至數(shù)據(jù)平面，因此，功能模塊組合問(wèn)題可以轉(zhuǎn)化為表項(xiàng)組合問(wèn)題。參考文獻(xiàn)[4,5]中提出了網(wǎng)絡(luò)編程語(yǔ)言Frenetic，將功能生成表項(xiàng)進(jìn)行并行組合，實(shí)現(xiàn)了多個(gè)功能（如路由、監(jiān)控、計(jì)數(shù)）同時(shí)作用于數(shù)據(jù)分組。隨后，又提出了優(yōu)化的模塊化編程語(yǔ)言Pyretic[3]，并增加了功能表項(xiàng)的串行組合方案，從而實(shí)現(xiàn)了不同的功能先后作用于數(shù)據(jù)分組（如一個(gè)被接入控制功能處理后的數(shù)據(jù)分組再經(jīng)過(guò)路由功能處理）的效果。以上工作基于OpenFlow單級(jí)流表[6]實(shí)現(xiàn)，面臨表項(xiàng)存儲(chǔ)開(kāi)銷大等問(wèn)題。為此，參考文獻(xiàn)[7]基于OpenFlow多級(jí)流表[8]實(shí)現(xiàn)了SDN功能模塊的串行和并行組合，并針對(duì)任意多級(jí)流表結(jié)構(gòu)提出了相應(yīng)組合算法，降低了表項(xiàng)開(kāi)銷和應(yīng)用開(kāi)發(fā)復(fù)雜度。

以上研究中提出的功能組合方案均基于單個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，當(dāng)應(yīng)用下發(fā)所需的功能數(shù)量超過(guò)單個(gè)交換節(jié)點(diǎn)的承載能力時(shí)，以上方法均難以處理。而考慮到單個(gè)交換機(jī)的功能承載力十分有限（承載功能的個(gè)數(shù)約等于流表級(jí)數(shù)），因此以上方法在實(shí)際應(yīng)用中存在較大局限性。為此，參考文獻(xiàn)[9]從可重構(gòu)網(wǎng)絡(luò)[10]中引入元能力概念，提出一種基于元能力的SDN功能組合機(jī)制，通過(guò)多個(gè)交換節(jié)點(diǎn)協(xié)作的方式將功能組合分散到多個(gè)交換機(jī)內(nèi)進(jìn)行，從而減小單個(gè)交換機(jī)的開(kāi)銷，但在該方法所預(yù)設(shè)的應(yīng)用場(chǎng)景中，功能表項(xiàng)是提前下發(fā)到交換機(jī)中的，并不符合SDN實(shí)時(shí)下發(fā)流表項(xiàng)的特性。

綜上所述，如何基于多交換節(jié)點(diǎn)進(jìn)行SDN中的功能組合是一個(gè)有待解決的問(wèn)題。為此，本文提出了一種基于拓?fù)渥儞Q的SDN功能組合方法，該方法在控制器中完成組合策略的分析，當(dāng)所需功能數(shù)量大于單個(gè)節(jié)點(diǎn)的承載力時(shí)，對(duì)發(fā)送給各個(gè)功能模塊的網(wǎng)絡(luò)拓?fù)溥M(jìn)行虛擬變換，然后將各個(gè)功能生成的表項(xiàng)分散到虛擬變換的幾個(gè)節(jié)點(diǎn)中，從而在不影響上層功能處理邏輯的同時(shí)實(shí)現(xiàn)了多功能組合處理。最后，在Ryu[11]控制器內(nèi)實(shí)現(xiàn)了該功能組合模塊的原型系統(tǒng)。

2 功能組合整體架構(gòu)

本文所提的功能組合方法在控制器中實(shí)現(xiàn)，其整體架構(gòu)如圖1所示，由功能組合模塊、功能庫(kù)以及組合策略等部分組成，其中，功能組合模塊完成策略分析、拓?fù)錁?gòu)建、表項(xiàng)下發(fā)等任務(wù)。根據(jù)網(wǎng)絡(luò)業(yè)務(wù)功能需要，上層應(yīng)用下發(fā)組合策略。組合策略中包含多種有序編排的網(wǎng)絡(luò)功能，功能對(duì)應(yīng)生成相應(yīng)的表項(xiàng)并下發(fā)到OpenFlow交換機(jī)中完成對(duì)數(shù)據(jù)分組的處理。策略分析模塊用來(lái)接收組合策略并進(jìn)行分析，判斷組合策略中的功能數(shù)是否超過(guò)單個(gè)交換機(jī)功能承載力，如果超過(guò)，則拓?fù)錁?gòu)建模塊將獲取的底層抽象拓?fù)溥M(jìn)行虛擬變換。拓?fù)錁?gòu)建模塊用來(lái)生成虛擬網(wǎng)絡(luò)拓?fù)湟怨┥蠈庸δ苣K使用，其首先根據(jù)底層實(shí)際物理網(wǎng)絡(luò)拓?fù)渖沙橄笸負(fù)?，然后根?jù)策略分析模塊的處理結(jié)果決定是否對(duì)抽象拓?fù)溥M(jìn)行拓?fù)渥儞Q?？刂破鞲鶕?jù)組合策略從功能庫(kù)中調(diào)用處理數(shù)據(jù)分組所需的功能，并將功能生成表項(xiàng)下發(fā)到表項(xiàng)下發(fā)模塊。表項(xiàng)下發(fā)模塊根據(jù)拓?fù)錁?gòu)建模塊傳來(lái)的網(wǎng)絡(luò)拓?fù)?，決定將功能表項(xiàng)下發(fā)到單個(gè)或者多個(gè)OpenFlow交換機(jī)中。

2.1 功能庫(kù)

功能庫(kù)，是指在SDN控制器上運(yùn)行的各種不重疊的網(wǎng)絡(luò)功能模塊的集合，其中包含常見(jiàn)的網(wǎng)絡(luò)功能，如監(jiān)控、接入控制、路由、轉(zhuǎn)發(fā)等。功能庫(kù)的存在使得在設(shè)計(jì)不同的SDN應(yīng)用時(shí)不用再重新開(kāi)發(fā)功能的實(shí)現(xiàn)模塊，而僅需通過(guò)下發(fā)組合策略的方式，并用功能組合模塊從功能庫(kù)中獲取相應(yīng)的功能?？刂破鲗⒐δ芟鄳?yīng)表項(xiàng)下發(fā)到交換機(jī)中，從而實(shí)現(xiàn)業(yè)務(wù)所需的多功能處理，避免了不同應(yīng)用中相同功能模塊的重復(fù)開(kāi)發(fā)。

2.2 組合策略描述

面對(duì)網(wǎng)絡(luò)業(yè)務(wù)的多樣化需求，上層應(yīng)用通過(guò)下發(fā)組合策略的方式實(shí)現(xiàn)業(yè)務(wù)對(duì)數(shù)據(jù)分組的多功能處理。組合策略由目標(biāo)集和功能集組成。目標(biāo)集是指被處理的數(shù)據(jù)流集合，如在異常檢測(cè)過(guò)程中處理{SrcIP=192.168.2.1/16;DstIp=192.168.3.3/16}的數(shù)據(jù)流；功能集是指處理目標(biāo)集中數(shù)據(jù)流所需功能的有序集合，即功能組合鏈，對(duì)目標(biāo)數(shù)據(jù)流的操作必須包含功能組合鏈中的所有功能。功能組合鏈和組合策略的形式化描述如下。

圖1 功能組合整體系統(tǒng)結(jié)構(gòu)

定義1 （功能組合鏈）網(wǎng)絡(luò)業(yè)務(wù)所需各種功能有序排列的集合，在應(yīng)用層表現(xiàn)為功能的排列，即邏輯功能組合鏈；控制層根據(jù)底層網(wǎng)絡(luò)拓?fù)鋵⒐δ芙M合鏈向下映射到數(shù)據(jù)層，得到功能組合實(shí)例鏈，并以下發(fā)流表項(xiàng)的方式實(shí)現(xiàn)上層的組合鏈。F是功能集合，且F≠。功能序列Fp就是一個(gè)功能組合鏈。

通過(guò)一個(gè)例子簡(jiǎn)要說(shuō)明。管理員希望用戶在訪問(wèn)IP地址為10.10.21.1/24的服務(wù)器之前，要經(jīng)過(guò)負(fù)載均衡、監(jiān)控、計(jì)數(shù)功能處理，所以該組合策略可以表述為＜{SrcIP=192.168.2.1/24,DstIP=10.10.21.1/24},{load-balance,monitor,count}＞。

2.3 拓?fù)渥儞Q

拓?fù)渥儞Q是指控制器從底層網(wǎng)絡(luò)獲得抽象拓?fù)浜?，根?jù)策略需求將源節(jié)點(diǎn)附近若干能與其形成到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)流通路的節(jié)點(diǎn)看成一個(gè)虛擬節(jié)點(diǎn)而完成的虛擬變換。經(jīng)過(guò)拓?fù)渥儞Q，控制器可以將下發(fā)到源節(jié)點(diǎn)交換機(jī)的功能表項(xiàng)改為下發(fā)到一個(gè)虛擬節(jié)點(diǎn)中，然后再將功能表項(xiàng)分散到虛擬節(jié)點(diǎn)內(nèi)的多個(gè)物理節(jié)點(diǎn)中，從而解決單點(diǎn)交換機(jī)承載能力有限的問(wèn)題。為方便后文敘述，定義單個(gè)節(jié)點(diǎn)的功能承載力。

定義3 （功能承載力）OpenFlow交換機(jī)同時(shí)執(zhí)行功能表項(xiàng)對(duì)應(yīng)動(dòng)作的能力，以能夠同時(shí)執(zhí)行的動(dòng)作指令的數(shù)量定義功能承載力。當(dāng)處理數(shù)據(jù)分組所需功能較多時(shí)，對(duì)應(yīng)下發(fā)到交換機(jī)中功能表項(xiàng)也較多，而交換機(jī)的表項(xiàng)容量以及動(dòng)作執(zhí)行數(shù)量均有限，就可能導(dǎo)致單個(gè)節(jié)點(diǎn)無(wú)法承載多個(gè)功能處理。假設(shè)單點(diǎn)交換機(jī)的功能承載力為N（約為流表級(jí)數(shù)）。

根據(jù)網(wǎng)絡(luò)業(yè)務(wù)功能需要，上層應(yīng)用下發(fā)組合策略，控制器分析組合策略，根據(jù)網(wǎng)絡(luò)拓?fù)鋸墓δ軒?kù)中獲取相應(yīng)功能并生成表項(xiàng)下發(fā)到源節(jié)點(diǎn)交換機(jī)中，即在單節(jié)點(diǎn)內(nèi)完成功能組合。當(dāng)功能需求超過(guò)單個(gè)節(jié)點(diǎn)的功能承載力時(shí)，控制器會(huì)根據(jù)變換后的拓?fù)鋵⒐δ鼙眄?xiàng)下發(fā)到多個(gè)交換節(jié)點(diǎn)中，假設(shè)需要M個(gè)功能，單節(jié)點(diǎn)功能承載力為N，則需要將功能表項(xiàng)下發(fā)到[M/N]+1個(gè)交換機(jī)中，功能表項(xiàng)與交換機(jī)的對(duì)應(yīng)關(guān)系由拓?fù)渥儞Q方法得出（見(jiàn)第4節(jié)）。

單節(jié)點(diǎn)內(nèi)的功能表項(xiàng)組合，就是將不同功能表項(xiàng)匹配域與動(dòng)作集進(jìn)行拆分合并，然后用多級(jí)流表進(jìn)行連接，route（路由）和 load-balance（負(fù)載均衡）的示例如圖 2所示，具體組合方法見(jiàn)參考文獻(xiàn)[7]。由于并行組合方法是串行組合方法的一種特殊情況，所以將參考文獻(xiàn)[7]中串行和并行組合方法進(jìn)行合并，并統(tǒng)一用&表示；對(duì)于多節(jié)點(diǎn)內(nèi)功能表項(xiàng)組合，就是將相應(yīng)功能表項(xiàng)放在不同交換機(jī)上進(jìn)行連接，monitor（監(jiān)控）、route、load-balance、count（計(jì)數(shù)）與NAT的示例如圖3所示。

圖2 單節(jié)點(diǎn)內(nèi)功能組合示例

通過(guò)一個(gè)簡(jiǎn)單例子具體說(shuō)明拓?fù)渥儞Q的過(guò)程，如圖4所示。假設(shè)組合策略的功能集為{monitor，count、load-balance，NAT}，單點(diǎn)交換機(jī)的功能承載力N=2。當(dāng)數(shù)據(jù)流到達(dá)源點(diǎn)交換機(jī)E6時(shí)，通過(guò)分析組合策略判定需要進(jìn)行拓?fù)渥儞Q，通過(guò)拓?fù)渥兓椒ǖ玫叫枰儞Q的節(jié)點(diǎn)以及執(zhí)行路徑{E6-E4-E5-E3}，即將節(jié)點(diǎn)E6、E4看成一個(gè)虛擬節(jié)點(diǎn)E0完成變換，如圖4所示。最后下發(fā)功能表項(xiàng)時(shí)，將monitor與 count組合表項(xiàng)下發(fā)到 E6，將 load-balance與NAT組合表項(xiàng)下發(fā)到E4。

3 功能組合問(wèn)題建模

3.1 問(wèn)題描述

將單節(jié)點(diǎn)功能承載力作為功能組合的影響因素，是本文的一個(gè)創(chuàng)新點(diǎn)。因此，本文提出SDN中基于全局網(wǎng)絡(luò)拓?fù)涞墓δ芙M合問(wèn)題并對(duì)其進(jìn)行建模。

定義4 （功能組合問(wèn)題）對(duì)于給定的組合策略、底層網(wǎng)絡(luò)拓?fù)洌刂破鳛椴呗砸?guī)定的功能組合鏈尋找一條最優(yōu)執(zhí)行路徑并將相應(yīng)的功能表項(xiàng)下發(fā)到底層OpenFlow交換機(jī)中。是功能集中相應(yīng)功能映射到底層拓?fù)涞囊粭l執(zhí)行路徑。定義SF={s1,s2,…,sm,…,si,…,sn}是功能集F的一條執(zhí)行路徑，且需要滿足下列條件:

· 節(jié)點(diǎn) si與 si+1是相互連通的，1≤i≤n-1；

·{s1,s2,…,sm}是功能集映射到底層拓?fù)涞墓?jié)點(diǎn)集；

·s1是源節(jié)點(diǎn)，sn是目的節(jié)點(diǎn)。

多節(jié)點(diǎn)內(nèi)的功能組合過(guò)程可建模為“組合策略—執(zhí)行路徑—交換機(jī)表項(xiàng)”的兩級(jí)映射過(guò)程，即“組合策略—執(zhí)行路徑”的映射和“執(zhí)行路徑—交換機(jī)表項(xiàng)”的映射，定義如下。

定義6 （“組合策略—執(zhí)行路徑”映射）將組合策略P中的功能集作為功能組合鏈，以業(yè)務(wù)需求為約束條件，為每個(gè)功能組合鏈選取最優(yōu)的執(zhí)行路徑，即將功能組合鏈中功能映射到底層拓?fù)浣粨Q機(jī)中，形成從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的數(shù)據(jù)流通路。映射過(guò)程可以表示為h:P→SF，其中，P={＜Op,Fp＞|Op?O,Fp?F}，SF是功能組合鏈 F 的執(zhí)行路徑。

定義7 （“執(zhí)行路徑—交換機(jī)表項(xiàng)”映射）根據(jù)功能組合鏈與底層網(wǎng)絡(luò)拓?fù)涞挠成潢P(guān)系，將功能相應(yīng)表項(xiàng)按次序下發(fā)到底層OpenFlow交換機(jī)中。映射過(guò)程可以表示為g:SF→EF，EF表示執(zhí)行路徑中交換機(jī)的表項(xiàng)，其包含功能表項(xiàng)和普通表項(xiàng)。

圖3 多節(jié)點(diǎn)內(nèi)功能組合示例

圖4 拓?fù)渥儞Q示例

一個(gè)“組合策略—執(zhí)行路徑—交換機(jī)表項(xiàng)”的映射過(guò)程示例如圖5所示。該組合策略的目標(biāo)集為 (src=W1,dst=

執(zhí)行路徑的形式化描述見(jiàn)定義5，其中，符號(hào)“?”表示功能所在節(jié)點(diǎn)交換機(jī)。

定義5 （執(zhí)行路徑）F是功能集合W6),首先將邏輯功能組合鏈映射到底層拓?fù)浣粨Q機(jī)上，得到從W1到W6的執(zhí)行路徑，圖5中陰影的節(jié)點(diǎn)是功能組合鏈映射到底層拓?fù)涞墓?jié)點(diǎn)。然后根據(jù)“組合策略—執(zhí)行路徑”的映射關(guān)系，控制器將表項(xiàng)下發(fā)到交換機(jī)中，得到E1到E6的表項(xiàng)，圖5陰影的表項(xiàng)是功能組合鏈對(duì)應(yīng)生成的功能表項(xiàng)；非陰影的表項(xiàng)是普通表項(xiàng)，僅起到連接的作用。

圖5 “組合策略—執(zhí)行路徑—交換機(jī)表項(xiàng)”映射過(guò)程

3.2 “組合策略—執(zhí)行路徑”映射

底層網(wǎng)絡(luò)拓?fù)溆肎(V,L)表示，其中，V表示交換機(jī)節(jié)點(diǎn)集，L表示執(zhí)行路徑的鏈路集合?！敖M合策略—執(zhí)行路徑”映射，即把組合策略中的邏輯功能組合鏈映射到底層網(wǎng)絡(luò)拓?fù)?，得到?zhí)行路徑。假設(shè)應(yīng)用下發(fā)組合策略P，通過(guò)形式化的描述對(duì)該映射過(guò)程進(jìn)行建模，稱其為功能組合模型。從源節(jié)點(diǎn)到目的節(jié)點(diǎn)有多條執(zhí)行路徑，通過(guò)選取最優(yōu)執(zhí)行路徑，最小化鏈路代價(jià)。本文計(jì)算鏈路代價(jià)，考慮執(zhí)行路徑距離代價(jià)、流表空間耗費(fèi)參數(shù)與最小節(jié)點(diǎn)數(shù)目對(duì)鏈路代價(jià)的影響。

由于現(xiàn)有網(wǎng)絡(luò)路由算法均以最小化路徑距離代價(jià)為設(shè)計(jì)目標(biāo)，低的路徑距離代價(jià)可以降低系統(tǒng)能耗。因此，執(zhí)行路徑的距離代價(jià)依然是本文優(yōu)先考慮的因素。對(duì)于流表空間耗費(fèi)而言，由于功能表項(xiàng)不止一條，而交換機(jī)流表存儲(chǔ)空間有限，如果流表存儲(chǔ)空間占用過(guò)大，會(huì)降低交換機(jī)處理性能，導(dǎo)致分組丟失率和處理時(shí)延增大。因此，流表空間耗費(fèi)是選擇執(zhí)行路徑時(shí)需要考慮的關(guān)鍵因素之一。最小化節(jié)點(diǎn)數(shù)目可以降低交換機(jī)總體存儲(chǔ)開(kāi)銷，減少系統(tǒng)資源占用。

模型用式（1）～式（6）進(jìn)行表示，表1中給出主要符號(hào)的含義。

表1 描述中主要符號(hào)的含義

優(yōu)化目標(biāo)：

式（1）是該模型的優(yōu)化目標(biāo)，最小化執(zhí)行路徑的代價(jià)，其中，N表示拓?fù)渲泄?jié)點(diǎn)數(shù)目，M表示功能集中的功能數(shù)。式（2）中R表示承載功能所需最小節(jié)點(diǎn)數(shù)目，T表示交換機(jī)流表級(jí)數(shù)。式（3）表示歸一化后的執(zhí)行路徑距離代價(jià)。式（4）表示歸一化后的流表空間耗費(fèi)，在選取執(zhí)行路徑的前R個(gè)節(jié)點(diǎn)時(shí)需要考慮，因?yàn)楣δ苌杀眄?xiàng)條目較多，而普通表項(xiàng)只有一條，起到連接轉(zhuǎn)發(fā)的作用，所以普通表項(xiàng)空間耗費(fèi)可以忽略不計(jì)。式（5）表示兩個(gè)放縮系數(shù)應(yīng)滿足的條件，可以用來(lái)調(diào)節(jié)執(zhí)行路徑距離代價(jià)和流表空間耗費(fèi)這兩個(gè)因素的重要程度比例。式（6）表明該問(wèn)題的解空間取值為0或1，即該問(wèn)題為0-1線性規(guī)劃問(wèn)題。式（7）保證所選執(zhí)行路徑從源地址s到目的地址t的可達(dá)性。

3.3 “執(zhí)行路徑—交換機(jī)表項(xiàng)”映射

“執(zhí)行路徑—交換機(jī)表項(xiàng)”映射是一個(gè)表項(xiàng)下發(fā)的過(guò)程，控制器根據(jù)“組合策略—執(zhí)行路徑”映射中所選的執(zhí)行路徑 SF={s1,s2,…,sm,…,sn}，將功能表項(xiàng)下發(fā)到進(jìn)行拓?fù)渥儞Q的交換機(jī)上，將其他普通表項(xiàng)下發(fā)到執(zhí)行路徑的其余交換機(jī)上，這些流表項(xiàng)僅起到連接的作用。該過(guò)程可以表示為 SF?EF，EF={siei,1≤i≤n|e1,e2,…,em,…,en}，其中，{e1,e2,…,em}是功能表項(xiàng)，其余的為普通表項(xiàng)。

4 拓?fù)渥儞Q方法

拓?fù)渥儞Q方法其實(shí)就是在源節(jié)點(diǎn)附近尋找R-1個(gè)節(jié)點(diǎn)（R同式（2）），確保這R-1個(gè)節(jié)點(diǎn)在從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的可達(dá)執(zhí)行路徑上，并滿足所需的約束條件。其實(shí)就是從源地址到目的地址間找到一條鏈路代價(jià)最小的執(zhí)行路徑，執(zhí)行路徑中的前R個(gè)點(diǎn)（包含源節(jié)點(diǎn)在內(nèi)）就是需要進(jìn)行拓?fù)渥儞Q的節(jié)點(diǎn)。由第2.2節(jié)中得到執(zhí)行路徑的選取是0-1線性規(guī)劃問(wèn)題，即拓?fù)渥儞Q方法也是0-1線性規(guī)劃問(wèn)題。為求解該問(wèn)題，本文基于鏈路代價(jià)提出一種節(jié)點(diǎn)搜索算法——綜合搜索算法。

4.1 綜合搜索算法

綜合搜索算法可以減小搜索范圍，在保證所選執(zhí)行路徑滿足所需約束條件的前提下，最小化鏈路代價(jià)。該算法的過(guò)程是：在滿足約束條件的前提下，從源節(jié)點(diǎn)出發(fā)搜索其鄰接點(diǎn)中路徑代價(jià)最小的點(diǎn)（路徑代價(jià)包括兩點(diǎn)之間的距離代價(jià)與節(jié)點(diǎn)的流表空間耗費(fèi)之和），并將其記錄；然后從該節(jié)點(diǎn)出發(fā)，搜索其鄰接點(diǎn)中路徑代價(jià)最小的點(diǎn)，參照上述過(guò)程，直到搜索到第R個(gè)（含源節(jié)點(diǎn)）滿足條件的節(jié)點(diǎn)；繼續(xù)搜索節(jié)點(diǎn)時(shí)，只考慮路徑距離代價(jià)，直到搜索到目的地址為止，最終得到鏈路代價(jià)最小的執(zhí)行路徑，即最優(yōu)執(zhí)行路徑。

算法1 綜合搜索算法

輸入 網(wǎng)絡(luò)拓?fù)銰(V,L)及其鄰接矩陣W、組合策略P及其目標(biāo)集{src=vi,dst=vt}。

輸出 最優(yōu)執(zhí)行路徑SFP及拓?fù)渥儞Q的節(jié)點(diǎn)集。

Src=vi,SF-Set=[vi] //源節(jié)點(diǎn)vi是執(zhí)行路徑的第一個(gè)

節(jié)點(diǎn)，SF-Set表示執(zhí)行路徑節(jié)點(diǎn)集；

for j=1:N

while(len.SF-Set＜R&&w(i,j)=1)do//從源節(jié)點(diǎn)出發(fā)，搜索其鄰接點(diǎn)，w(i,j)=1表示節(jié)點(diǎn)vi與vj相鄰；

if vj≠vi&&min f(y)then //搜索代價(jià)最小節(jié)點(diǎn)，并且節(jié)點(diǎn)集長(zhǎng)度小于R時(shí)，搜索的節(jié)點(diǎn)不能是目的節(jié)點(diǎn)；

SF-Set=[SF-Set,vj]，i=j//更新執(zhí)行路徑節(jié) 點(diǎn)集 ，更新搜索起點(diǎn)；

end if

end while

while(len.SF-Set≥R&&w(i,j)=1)do

if min h(y,n)then//當(dāng)執(zhí)行路徑節(jié)點(diǎn)集大于或等于R時(shí)，以最小距離代價(jià)為條件進(jìn)行搜索，當(dāng)vj=vi時(shí)停止搜索；

SF-Set=[SF-Set,vj]，i=j//更新執(zhí)行路徑節(jié)點(diǎn)集，更新搜索起點(diǎn)；

end if

end while

end for

4.2 算法分析

在節(jié)點(diǎn)尋找問(wèn)題上，一般使用窮舉算法，從源節(jié)點(diǎn)出發(fā)，搜索整個(gè)拓?fù)渲袧M足約束條件的節(jié)點(diǎn)，假設(shè)網(wǎng)絡(luò)拓?fù)渲杏蠳個(gè)節(jié)點(diǎn)，窮舉算法的時(shí)間復(fù)雜度為O((N-1)!)。而本文所提綜合搜索算法綜合考慮鏈路代價(jià)與計(jì)算復(fù)雜度，并在它們之間尋求平衡，搜索空間較小，其算法時(shí)間復(fù)雜度為O((N-1)2)。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)較多時(shí)，綜合搜索算法搜索空間較小，時(shí)間復(fù)雜度較低，明顯優(yōu)于窮舉算法。

5 實(shí)驗(yàn)分析

5.1 基于Ryu的原型系統(tǒng)實(shí)現(xiàn)

[12]中提出的Application-aware是在交換節(jié)點(diǎn)內(nèi)加入功能組合模塊（App和App table），數(shù)據(jù)平面通過(guò)在控制平面調(diào)用所需功能完成功能組合。然而，該方法需要修改控制平面與數(shù)據(jù)平面之間交互的OpenFlow協(xié)議，這會(huì)導(dǎo)致開(kāi)發(fā)難度大，交換機(jī)復(fù)雜度高。參考文獻(xiàn)[7]將功能組合模塊放在控制器中，針對(duì)單節(jié)點(diǎn)交換機(jī)完成功能組合并下發(fā)表項(xiàng)，并未考慮單節(jié)點(diǎn)交換機(jī)功能承載力有限的問(wèn)題。因此，在上述基礎(chǔ)上將功能組合模塊放置在Ryu控制器中，并且考慮到單節(jié)點(diǎn)功能承載力有限的問(wèn)題，在模塊中加入策略分析、拓?fù)錁?gòu)建、表項(xiàng)下發(fā)等模塊，通過(guò)分析策略所需功能，完成在單節(jié)點(diǎn)或者多節(jié)點(diǎn)下發(fā)功能表項(xiàng)。

控制平面中引入功能組合模塊改變了傳統(tǒng)SDN處理數(shù)據(jù)流的過(guò)程。當(dāng)數(shù)據(jù)流到達(dá)OpenFlow交換機(jī)時(shí)，如果數(shù)據(jù)流匹配到交換機(jī)中的流表項(xiàng)，則執(zhí)行對(duì)該數(shù)據(jù)流的相關(guān)處理；如果未匹配成功，則將數(shù)據(jù)流頭部封裝分組的packet in消息上傳至控制器，交由功能組合模塊進(jìn)行處理；數(shù)據(jù)流頭部信息匹配組合策略，從而得到處理數(shù)據(jù)流所需功能，如果未匹配到相應(yīng)組合策略，則交由控制器其他組件進(jìn)行處理；匹配后判斷是否超過(guò)單節(jié)點(diǎn)功能承載力，并決定將功能表項(xiàng)下發(fā)到單節(jié)點(diǎn)還是多節(jié)點(diǎn)交換機(jī)中，以完成對(duì)數(shù)據(jù)流的多功能處理。

為了實(shí)現(xiàn)文中所述功能組合方法 （control plane function composition，CPFC），基 于 NetFPGA-10G[13]平 臺(tái) 和Ryu控制器設(shè)計(jì)并實(shí)現(xiàn)了CPFC的原型系統(tǒng)，如圖6所示。在數(shù)據(jù)平面，采用NetFPGA-10G實(shí)驗(yàn)平臺(tái)，現(xiàn)已實(shí)現(xiàn)最大支持OpenFlow 1.3[8]協(xié)議的4級(jí)流表串聯(lián)的流水線處理機(jī)制，可實(shí)現(xiàn)路由、轉(zhuǎn)發(fā)、計(jì)數(shù)、負(fù)載均衡等功能，為了更好地進(jìn)行對(duì)照實(shí)驗(yàn)，實(shí)驗(yàn)時(shí)限制節(jié)點(diǎn)流表級(jí)數(shù)為兩級(jí)。NetFPGA-10G板卡通過(guò)PCIe插槽插在工控機(jī)中，工控機(jī)中運(yùn)行OpenFlow agent軟件包，以實(shí)現(xiàn)與控制器的互聯(lián)?？刂破矫娌捎肦yu控制器，Python語(yǔ)言編寫的Ryu提供強(qiáng)大的API，有利于網(wǎng)絡(luò)應(yīng)用的開(kāi)發(fā)，而且Ryu自帶一些功能模塊，如防火墻、路由、交換等。

5.2 功能組合性能分析

采用第5.1節(jié)提到的CPFC原型系統(tǒng)對(duì)CPFC的性能進(jìn)行仿真分析，實(shí)驗(yàn)仿真拓?fù)淙鐖D7所示。本文采用參考文獻(xiàn)[14]中提到的仿真驗(yàn)證方法，基于NetFPGA-10G構(gòu)造6個(gè)交換節(jié)點(diǎn)，各節(jié)點(diǎn)由Ryu控制器控制并下發(fā)流表。該實(shí)驗(yàn)拓?fù)溆脕?lái)實(shí)現(xiàn)用戶向視頻服務(wù)器請(qǐng)求視頻服務(wù)，實(shí)驗(yàn)時(shí)上層組合策略為＜{SrcIP=192.168.2.146,DstIP=192.168.3.3},{monitor,route,load-balance}＞，各功能表項(xiàng)具體如圖8所示。實(shí)驗(yàn)時(shí)各NetFPGA-10G節(jié)點(diǎn)均限制為兩級(jí)流表，每級(jí)流表由64條表項(xiàng)組成，每條表項(xiàng)寬度是 64 bit的匹配域（存于 TCAM中）和 380 bit的動(dòng)作域（存于SRAM中）。采用綜合搜索算法得到的最優(yōu)路徑為 E1-E3-E4-E6，因此在 E1上下發(fā) monitor和route對(duì)應(yīng)功能表項(xiàng)，在E3上下發(fā) load-balance對(duì)應(yīng)功能表項(xiàng)。

圖6 CPFC原型系統(tǒng)

圖7 實(shí)驗(yàn)拓?fù)?/p>

圖8 具體功能表項(xiàng)

實(shí)驗(yàn)與參考文獻(xiàn)[12]的數(shù)據(jù)平面組合方法（data plane function composition，DPFC） 和 NFC （network function composition）[7]進(jìn)行對(duì)比。實(shí)驗(yàn)時(shí)，CPFC的功能組合均在多節(jié)點(diǎn)中進(jìn)行，單節(jié)點(diǎn)內(nèi)功能組合的思想來(lái)源于NFC，后續(xù)仿真分析不再討論。本文采用與參考文獻(xiàn)[7]中相同的實(shí)驗(yàn)方法，利用數(shù)據(jù)分組測(cè)試工具packet sender從網(wǎng)口發(fā)送10 Gbit/s數(shù)據(jù)分組，分別記錄 DPFC、NFC、CPFC 3種方法的單節(jié)點(diǎn)流處理時(shí)延情況，如圖9所示。從圖9中可以看出，NFC和CPFC的流處理時(shí)延明顯低于DPFC，這是由于在控制平面調(diào)用功能模塊比在數(shù)據(jù)平面調(diào)用控制平面內(nèi)功能模塊的時(shí)延小。隨著數(shù)據(jù)分組流量的增大，3種方法的時(shí)延均變大，當(dāng)數(shù)據(jù)分組流量超過(guò)單個(gè)節(jié)點(diǎn)的處理能力（約350 Mbit/s）時(shí)，CPFC較NFC的時(shí)延增速顯著下降，這是由于CPFC將功能組合分散到多個(gè)交換機(jī)中，會(huì)減少單個(gè)交換機(jī)的負(fù)載。從圖9中還可以得出，對(duì)于源地址重寫所帶來(lái)的時(shí)延，DPFC低于NFC和CPFC，因?yàn)閷?duì)于簡(jiǎn)單的轉(zhuǎn)發(fā)功能來(lái)說(shuō)，DPFC可以直接在交換機(jī)中處理，而NFC和CPFC還要調(diào)用控制平面中的功能組合模塊進(jìn)行判斷。

5.3 組合效率分析

在功能組合效率方面，F(xiàn)renetic、Pyretic利用OpenFlow單級(jí)流表結(jié)構(gòu)將不同功能生成表項(xiàng)進(jìn)行合并，完成功能組合，NFC則利用OpenFlow多級(jí)流表結(jié)構(gòu)，對(duì)不同功能生成表項(xiàng)的匹配域進(jìn)行判斷后，進(jìn)行拆分與合并，并用多級(jí)流表進(jìn)行連接；以上功能組合方法均是在單節(jié)點(diǎn)交換機(jī)中完成的。為與以上功能組合方法進(jìn)行對(duì)比，本文采用參考文獻(xiàn)[3，4，7]中提到的 3 類功能表項(xiàng) monitor、route、load-balance進(jìn)行驗(yàn)證，隨機(jī)生成1 000～7 000次組合策略，得到不同功能組合方法生成表項(xiàng)的時(shí)間，如圖10所示。Frenetic和Pyretic分別是在單級(jí)流表上引入功能并行組合與串行組合方法，這兩種方法需要判斷表項(xiàng)匹配域的可合并性以及對(duì)表項(xiàng)進(jìn)行合并，所以時(shí)間復(fù)雜度較高，表項(xiàng)生成時(shí)間較長(zhǎng)。NFC利用多級(jí)流表結(jié)構(gòu)分別實(shí)現(xiàn)功能串行和并行組合，由于多級(jí)流表表項(xiàng)合并流程復(fù)雜度比單級(jí)流表高，所以NFC時(shí)間復(fù)雜度最高。而所提功能組合方法直接對(duì)各個(gè)功能表項(xiàng)進(jìn)行下發(fā)和連接，省去了表項(xiàng)合并的時(shí)間，因此表項(xiàng)生成時(shí)間最短，即功能組合效率最高。

圖9 流處理時(shí)延對(duì)比

5.4 表項(xiàng)存儲(chǔ)開(kāi)銷分析

對(duì)于兩個(gè)功能產(chǎn)生的表項(xiàng)，A有M條，B有N條，則Pyretic的存儲(chǔ)開(kāi)銷為M×N，因?yàn)锳和B的每一條表項(xiàng)均需要進(jìn)行合并；NFC的存儲(chǔ)開(kāi)銷則與多級(jí)流表結(jié)構(gòu)有關(guān)，若交換機(jī)有K級(jí)流表，則其存儲(chǔ)開(kāi)銷近似為(M×N)/K；CPFC則直接將不同功能的表項(xiàng)下發(fā)至不同交換機(jī)的流表，因此其存儲(chǔ)開(kāi)銷為M+N；當(dāng)M和N較大時(shí)，CPFC的存儲(chǔ)開(kāi)銷更低?？紤]到匹配域字段放在TCAM中，動(dòng)作字段放在SRAM中。采用第5.3節(jié)中提到的3種功能表項(xiàng)，圖11給出了4種功能組合方法對(duì)應(yīng)表項(xiàng)存儲(chǔ)開(kāi)銷對(duì)比。NFC由于使用多級(jí)流表結(jié)構(gòu)對(duì)匹配域進(jìn)行判斷合并，所以該方法較Frenetic與Pyretic節(jié)省了寶貴的TCAM資源。CPFC方法也使用多級(jí)流表并將不同功能表項(xiàng)下發(fā)到不同交換機(jī)的流表，在SRAM資源占用比NFC高約6%的情況下，能夠節(jié)省約25%的TCAM資源。由于TCAM的成本遠(yuǎn)高于SRAM，因此CPFC能夠節(jié)省一定的交換機(jī)存儲(chǔ)開(kāi)銷。

圖10 表項(xiàng)生成時(shí)間對(duì)比

圖11 表項(xiàng)存儲(chǔ)開(kāi)銷對(duì)比

6 結(jié)束語(yǔ)

針對(duì)SDN中單節(jié)點(diǎn)功能組合無(wú)法滿足多功能組合需求的問(wèn)題，提出了一種基于拓?fù)渥儞Q的功能組合方法，并設(shè)計(jì)和實(shí)現(xiàn)了相應(yīng)的功能組合模塊。當(dāng)業(yè)務(wù)功能需求大于單節(jié)點(diǎn)交換機(jī)的功能承載力時(shí)，對(duì)底層抽象拓?fù)溥M(jìn)行虛擬變化，把原來(lái)在單節(jié)點(diǎn)內(nèi)進(jìn)行的功能組合分散到多節(jié)點(diǎn)中進(jìn)行。實(shí)驗(yàn)結(jié)果表明，該方法提高了組合效率并且降低了流處理時(shí)延，而且也節(jié)省了交換機(jī)存儲(chǔ)開(kāi)銷。

參考文獻(xiàn)：

[1]MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[2]SHIN M K,NAM K H,KIM H J.Software-defined networking(SDN): A reference architecture and open APIs[C]//International Conference on ICT Convergence,October 15-17,2012,Jeju Island,Korea.New Jersey:IEEE Press,2012:360-361.

[3]MONSANTO C,REICH J,FOSTER N,etal.Composing software defined networks[C]//NSDI,April 3-5,2013,Lombard,IL,USA.New York:ACM Press,2013:1-13.

[4]FOSTER N,HARRISON R,FREEDMAN M J,et al.Frenetic:a network programming language[C]//ACM SIGPLAN Notices,March 3-7,2011,Las vegas,USA.New York:ACM Press,2011,46(9):279-291.

[5]MONSANTO C,FOSTER N,HARRISON R,et al.A compiler and run-time system for network programming languages[J].ACM SIGPLAN Notices,2012,47(1):217-230.

[6]Open Networking Foudation. OpenFlow_v1.0 [EB/OL].(2016-01-03)[2016-04-10].https://archive.openflow.org/wk/index.php/OpenFlow_v1.0,2016.

[7]段通,蘭巨龍,胡宇翔,等.SDN中一種基于多級(jí)流表的功能組合方法[J].電子學(xué)報(bào),2015.DUAN T,LAN J L,HU Y X,et al.A function composition method of software-defined network based on multiple tables[J].Accepted by Chinese Journal of Electronics,2015.

[8]Open Networking Foudation. OpenFlow1.3,OpenFlowswitch specification 1.3.0[EB/OL].(2012-02-10)[2016-04-10].https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/OpenFlow/OpenFlow-spec-v1.3.0.pdf,2012.

[9]段通,蘭巨龍,程國(guó)振,等.基于元能力的 SDN功能組合機(jī)制[J].通信學(xué)報(bào),2015,36(5):19-2015178.DUAN T,LAN J L,CHENG G Z,et al.SDN function combination mechanism based on meta-ability[J].Journal of Communications,2015,36(5):19-2015178.

[10]蘭巨龍,程?hào)|年,胡宇翔.可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究[J].通信學(xué)報(bào),2014(1):128-139.LAN J L,CHENG D N,HU Y X.Reconfigurable network system based on information and communication research[J].Journal of Communications,2014(1):128-139.

[11]Ryu Framework Community.Ryu controller project[EB/OL].(2014-01-20)[2016-04-10].https://osrg.github.io/ryu,2014.

[12]HESHAM M,FANG H,SARIT M,et al.Application-aware data plane processing in SDN[M].New York:Acm Press,2014:13-18.[13]Github. NetFPGA-10G project [EB/OL]. (2014-01-10)[2016-04-10].https://github.com/NetFPGA-public/wiki,2014.

[14]GIBB G,ZENG H,MCKEOWN N.Outsourcingnetwork functionality[C]//The Workshop on Hot Topics in Software Defined Networks,March 5-10,2012,Las vegas,USA.New York:ACM Press,2012:73-78.

A function composition method of software defined networking based on topology transformation

XI Xiaoqiang,LAN Julong,DUAN Tong,JIANG Yiming
National Digital Switching System Engineering&Technology Research Center,Zhengzhou 450002,China

The existing function composition methods of software defined networking(SDN)are mostly carried out in the single node without considering the function bearing capacity of the single switch.To solve this problem,firstly a function composition method based on topology transformation was proposed to carry out function composition in multiple nodes by transforming abstract topology.Secondly,the topology transformation was modeled as the 0-1 linear programming problem and a comprehensive search algorithm was proposed to solve this problem.Finally,the function composition module and implemented the prototype system based on NetFPGA-10G and Ryu controller were devised to do the function composition.The experimental results show that the method can reduce processing delay and storage cost as well as improve the composition efficiency compared with the existing method.

software defined networking,topology transformation,function composition,NetFPGA-10G

s:The National Basic Research Program of China(973 Program)(No.2012CB315901,No.2013CB329104)，The National Natural Science Foundation of China（No.61372121,No.61309019,No.61502530），The National High Technology Research and Development Program of China(863 Program)(No.2013AA013505,No.2015AA016102)

TP393

A

10.11959/j.issn.1000-0801.2016175

2016-05-10；

2016-06-14

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(“973”計(jì)劃)基金資助項(xiàng)目(No.2012CB315901,No.2013CB329104)；國(guó)家自然科學(xué)基金資助項(xiàng)目(No.61372121,No.61309019,No.61502530)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目(No.2013AA013505,No.2015AA016102)

席 孝 強(qiáng)(1989-)， 男 ， 國(guó) 家 數(shù) 字 交 換 系 統(tǒng) 工程技術(shù)研究中心碩士生，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)。

蘭巨龍(1962-)，男，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心總工程師、教授、博士生導(dǎo)師，主要從事新一代信息網(wǎng)絡(luò)關(guān)鍵理論與技術(shù)的研究工作，目前作為首席科學(xué)家主持國(guó)家“973”計(jì)劃項(xiàng)目“可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究”。

段通(1992-)，男，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向?yàn)榭删幊叹W(wǎng)絡(luò)數(shù)據(jù)平面。

江逸茗(1984-)，男，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、可重構(gòu)網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化。