席孝強，蘭巨龍，段通，江逸茗

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

研究與開發(fā)

SDN中一種基于拓撲變換的功能組合方法

席孝強，蘭巨龍，段通，江逸茗

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

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

軟件定義網(wǎng)絡(luò)；拓撲變換；功能組合；NetFPGA-10G

1 引言

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

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

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

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

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

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

2.1 功能庫

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

2.2 組合策略描述

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

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

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

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

2.3 拓撲變換

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

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

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

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

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

通過一個簡單例子具體說明拓撲變換的過程，如圖4所示。假設(shè)組合策略的功能集為{monitor，count、load-balance，NAT}，單點交換機的功能承載力N=2。當數(shù)據(jù)流到達源點交換機E6時，通過分析組合策略判定需要進行拓撲變換，通過拓撲變化方法得到需要變換的節(jié)點以及執(zhí)行路徑{E6-E4-E5-E3}，即將節(jié)點E6、E4看成一個虛擬節(jié)點E0完成變換，如圖4所示。最后下發(fā)功能表項時，將monitor與 count組合表項下發(fā)到 E6，將 load-balance與NAT組合表項下發(fā)到E4。

3 功能組合問題建模

3.1 問題描述

將單節(jié)點功能承載力作為功能組合的影響因素，是本文的一個創(chuàng)新點。因此，本文提出SDN中基于全局網(wǎng)絡(luò)拓撲的功能組合問題并對其進行建模。

定義4 （功能組合問題）對于給定的組合策略、底層網(wǎng)絡(luò)拓撲，控制器為策略規(guī)定的功能組合鏈尋找一條最優(yōu)執(zhí)行路徑并將相應(yīng)的功能表項下發(fā)到底層OpenFlow交換機中。是功能集中相應(yīng)功能映射到底層拓撲的一條執(zhí)行路徑。定義SF={s1,s2,…,sm,…,si,…,sn}是功能集F的一條執(zhí)行路徑，且需要滿足下列條件:

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

·{s1,s2,…,sm}是功能集映射到底層拓撲的節(jié)點集；

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

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

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

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

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

圖4 拓撲變換示例

一個“組合策略—執(zhí)行路徑—交換機表項”的映射過程示例如圖5所示。該組合策略的目標集為 (src=W1,dst=

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

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

圖5 “組合策略—執(zhí)行路徑—交換機表項”映射過程

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

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

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

模型用式（1）～式（6）進行表示，表1中給出主要符號的含義。

表1 描述中主要符號的含義

優(yōu)化目標：

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

3.3 “執(zhí)行路徑—交換機表項”映射

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

4 拓撲變換方法

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

4.1 綜合搜索算法

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

算法1 綜合搜索算法

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

輸出 最優(yōu)執(zhí)行路徑SFP及拓撲變換的節(jié)點集。

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

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

for j=1:N

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

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

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

end if

end while

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

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

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

end if

end while

end for

4.2 算法分析

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

5 實驗分析

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

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

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

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

5.2 功能組合性能分析

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

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

圖7 實驗拓撲

圖8 具體功能表項

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

5.3 組合效率分析

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

圖9 流處理時延對比

5.4 表項存儲開銷分析

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

圖10 表項生成時間對比

圖11 表項存儲開銷對比

6 結(jié)束語

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

參考文獻：

[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].電子學(xué)報,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]段通,蘭巨龍,程國振,等.基于元能力的 SDN功能組合機制[J].通信學(xué)報,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]蘭巨龍,程東年,胡宇翔.可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究[J].通信學(xué)報,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

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

席 孝 強(1989-)， 男 ， 國 家 數(shù) 字 交 換 系 統(tǒng) 工程技術(shù)研究中心碩士生，主要研究方向為新型網(wǎng)絡(luò)體系結(jié)構(gòu)。

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

段通(1992-)，男，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向為可編程網(wǎng)絡(luò)數(shù)據(jù)平面。

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