節(jié)點效用最大化的服務(wù)功能鏈構(gòu)建方法

張傳浩，周　橋

(1.鐵道警察學(xué)院 公安技術(shù)系，鄭州 450053；　2.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)(*通信作者電子郵箱zhangchuanhao@rpc.edu.cn)

0　引言

隨著網(wǎng)絡(luò)流量的急劇膨脹和網(wǎng)絡(luò)業(yè)務(wù)的不斷更新，當(dāng)今的計算機網(wǎng)絡(luò)越來越依賴于中間件盒子(middlebox)所提供的功能。文獻(xiàn)[1]定義中間件盒子是工作在計算機網(wǎng)絡(luò)4～7層的一種網(wǎng)絡(luò)設(shè)備，用來對經(jīng)過它的流量進(jìn)行檢測和修改。中間件盒子在網(wǎng)絡(luò)中發(fā)揮著越來越重要的作用，如改善安全、提高性能、減小帶寬以及提供其他新穎功能[2]等。但如何在網(wǎng)絡(luò)中引導(dǎo)流量通過一定順序的中間件盒子構(gòu)成服務(wù)功能鏈來提供豐富的功能卻是一個非常復(fù)雜的過程：首先需要在網(wǎng)絡(luò)中的合適位置部署中間件盒子，然后需要手工配置轉(zhuǎn)發(fā)規(guī)則來引導(dǎo)流量通過一定順序的盒子。隨著軟件定義網(wǎng)絡(luò)(Software Defined Networ, SDN)[3]和網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization, NFV)[4]技術(shù)的興起，如何靈活高效地解決這些問題再次成為研究的熱點。

SDN技術(shù)提供了邏輯集中式的管理控制，解耦了數(shù)據(jù)平面和轉(zhuǎn)發(fā)平面，給中間件盒子提供了可編程的轉(zhuǎn)發(fā)規(guī)則配置方式。StEERING方法[5]通過對OpenFlow多級流表進(jìn)行改進(jìn)來實現(xiàn)流量引導(dǎo)；SIMPLE方法[6]構(gòu)建了基于SDN的策略執(zhí)行層，能夠使中間件的深度策略轉(zhuǎn)化更加有效，并解決了流量引導(dǎo)中的環(huán)路問題；FlowTags方法[7]則通過對中間件以及交換機的改進(jìn)，使之能夠?qū)M(jìn)出的流進(jìn)行標(biāo)記來實現(xiàn)流量引導(dǎo)。但是基于SDN技術(shù)實現(xiàn)的服務(wù)功能鏈存在著一些共性的問題：首先，無法根據(jù)業(yè)務(wù)需求來實現(xiàn)中間件的動態(tài)部署；其次，當(dāng)網(wǎng)絡(luò)中部署著大量中間件盒子時，硬件成本及管理開銷太大；最后，中間件盒子出現(xiàn)故障以及過載時，恢復(fù)速度過慢難以滿足用戶需求。

NFV技術(shù)克服了傳統(tǒng)中間件盒子種類繁多、價格昂貴、結(jié)構(gòu)封閉且十分不利于統(tǒng)一集中管理配置等缺點，由基于軟件實現(xiàn)的虛擬功能代替基于硬件實現(xiàn)的硬件盒子，并部署于廉價的商用設(shè)備(例如x86服務(wù)器)上。Sekar等[8]提出了一種集成統(tǒng)一的中間件盒子結(jié)構(gòu)CoMB(Consolidated MiddleBox)來解決傳統(tǒng)中間件盒子所帶來的弊端，每個CoMB運行多個基于軟件的中間件，根據(jù)不同的業(yè)務(wù)啟動相應(yīng)的中間件。ClickOS[9]是基于Xen實現(xiàn)的軟件平臺，通過優(yōu)化中間盒子處理能夠創(chuàng)建快速啟動的、低延遲的小型虛擬機。這些基于NFV的虛擬化中間件盒子主要側(cè)重于提升數(shù)據(jù)平面以及軟件上的實現(xiàn)，沒有涉及虛擬功能實例的最優(yōu)控制?；赟DN+NFV的方法能夠很好地解決上面出現(xiàn)的問題：首先能實現(xiàn)虛擬中間件盒子間的流量引導(dǎo)；其次能根據(jù)業(yè)務(wù)需求動態(tài)部署虛擬的中間件盒子；最后還能對故障或者過載的中間件盒子實現(xiàn)遷移，從而實現(xiàn)虛擬功能實例的最優(yōu)控制。OpenNF[10]和Slick[11-12]都是國外最新提出的基于SDN+NFV的服務(wù)功能部署架構(gòu)。OpenNF利用SDN控制器設(shè)計了一個服務(wù)功能控制平面、一系列的API接口以及服務(wù)功能組合與轉(zhuǎn)發(fā)機制；Slick設(shè)計了一個允許用戶對某些指定流的服務(wù)功能進(jìn)行編程處理的架構(gòu)，通過用戶自定義編程來完成虛擬中間件盒子的部署和流量引導(dǎo)。OpenNF和Slick的研究重點偏向于控制平面設(shè)計和控制軟件的實現(xiàn)，且其服務(wù)功能鏈構(gòu)建算法往往將流量引導(dǎo)和中間件盒子部署問題分開考慮，達(dá)不到節(jié)點資源效用最大化。

與當(dāng)前主流方法不同，本文將虛擬化的中間件盒子部署問題和流量引導(dǎo)問題聯(lián)合考慮，提出了一種節(jié)點效用最大化的服務(wù)功能鏈構(gòu)建方法NUM(Node Utility Maximization)。實驗結(jié)果表明，與主流方法相比，NUM在構(gòu)建時間、構(gòu)建成功率、網(wǎng)絡(luò)擁塞率以及節(jié)點效用上均具有優(yōu)越性。

1　服務(wù)功能鏈構(gòu)建問題

SDN技術(shù)使得中間件盒子的流量引導(dǎo)更加靈活便利，NFV技術(shù)則可虛擬化中間件盒子且使其易于動態(tài)部署。在SDN+NFV環(huán)境下，為了實現(xiàn)用戶訂制的服務(wù)功能，需要利用NFV技術(shù)動態(tài)部署虛擬化的中間件盒子，再利用SDN技術(shù)從源節(jié)點引導(dǎo)流量通過特定順序的中間件盒子到達(dá)目的節(jié)點構(gòu)成服務(wù)功能鏈。本文將中間件盒子部署問題和流量引導(dǎo)問題聯(lián)合起來，定義為服務(wù)功能鏈構(gòu)建問題(Service Function Chain Construction Problem, SFCCP)。

如圖1所示，本文所用的中間件盒子是建立在商用服務(wù)器中ClickOS平臺上虛擬化的中間件盒子，控制器控制交換機根據(jù)業(yè)務(wù)需求動態(tài)地進(jìn)行虛擬中間件盒子的實例化，在沒有業(yè)務(wù)需求時關(guān)閉來節(jié)省資源。以圖1為例簡單說明服務(wù)功能鏈構(gòu)建問題：根據(jù)業(yè)務(wù)需求，流量1需分別經(jīng)過防火墻、入侵檢測系統(tǒng)以及一個內(nèi)容過濾器，流量2僅需經(jīng)過防火墻和入侵檢測系統(tǒng)，流量3則僅需經(jīng)過防火墻和內(nèi)容過濾器。為了滿足用戶的服務(wù)功能需求，首先需要選擇出最優(yōu)節(jié)點并求解出一條最優(yōu)路徑和資源分配，然后以業(yè)務(wù)需求和路徑上的資源分配為條件來實現(xiàn)虛擬化中間件盒子的實例化，最后控制器引導(dǎo)流量在確定的路徑上通過實例化的中間件盒子完成服務(wù)功能鏈構(gòu)建。

圖1　服務(wù)功能鏈構(gòu)建示例Fig. 1　Example of service function chain construction

在SDN+NFV的網(wǎng)絡(luò)環(huán)境中，主要有以下因素影響著SFCCP：

1)用戶策略：用戶制定策略的數(shù)量和復(fù)雜度直接決定了SFCCP的求解難度。本文對用戶策略進(jìn)行劃分，每條策略劃分成多個經(jīng)過單一中間件盒子的流，以此來降低求解難度。

2)網(wǎng)絡(luò)拓?fù)湎拗疲褐饕蔷W(wǎng)絡(luò)節(jié)點數(shù)量和網(wǎng)絡(luò)節(jié)點的鏈接情況，以及鏈路帶寬限制。

3)節(jié)點資源限制：交換機節(jié)點的轉(zhuǎn)發(fā)處理能力主要被單個物理設(shè)備的三態(tài)內(nèi)容尋址存儲器(Ternary Content Addressable Memory, TCAM)資源所限制，屬于底層轉(zhuǎn)發(fā)能力。

4)服務(wù)器資源限制：在服務(wù)器上的ClickOS平臺上虛擬出中間件盒子需要耗費計算資源與存儲和帶寬資源，屬于配置層計算能力。

5)虛擬網(wǎng)絡(luò)功能相關(guān)性問題：本文討論的虛擬網(wǎng)絡(luò)功能模塊均具備獨立性特點，即均以用戶需求為驅(qū)動進(jìn)行部署，模塊間交互接口網(wǎng)絡(luò)數(shù)據(jù)流量；同時本文考慮的重點也是以模塊為基本單元的服務(wù)鏈部署策略，所以模塊之間的層級相同，可以不考慮其相關(guān)性。

2　服務(wù)功能鏈構(gòu)建方法

2.1　服務(wù)功能鏈構(gòu)建機制

各種因素互相影響、相互制約，使得虛擬中間件盒子的部署以及部署完成后的流量引導(dǎo)變成一個極為復(fù)雜的過程。為了解決SFCCP，本文設(shè)計如圖2所示的服務(wù)功能鏈構(gòu)建機制，通過擴展現(xiàn)有SDN控制器的南向接口實現(xiàn)對服務(wù)器上虛擬中間件的部署與管理。該機制核心的控制器主要由三部分組成：資源處理器、轉(zhuǎn)發(fā)規(guī)則產(chǎn)生器以及服務(wù)器管理器。

1)資源處理器以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、用戶制定的服務(wù)功能需求以及交換機和服務(wù)器等的資源限制為輸入，通過一定的算法實現(xiàn)對服務(wù)器的資源分配和網(wǎng)絡(luò)節(jié)點及路徑的選擇；資源處理器計算的結(jié)果直接輸出到轉(zhuǎn)發(fā)規(guī)則產(chǎn)生器和服務(wù)器管理器。

2)服務(wù)器管理器根據(jù)資源處理器所計算的資源分配在對應(yīng)的服務(wù)器上進(jìn)行中間件盒子的實例化，并根據(jù)網(wǎng)絡(luò)流量動態(tài)地進(jìn)行開啟和關(guān)閉處理。

3)轉(zhuǎn)發(fā)規(guī)則產(chǎn)生器根據(jù)資源處理器所計算出的網(wǎng)絡(luò)節(jié)點和路徑下發(fā)轉(zhuǎn)發(fā)規(guī)則。

在服務(wù)功能鏈構(gòu)建機制中，規(guī)則產(chǎn)生器和服務(wù)器管理器是重要的組成部分，根據(jù)資源處理器所處理的結(jié)果，服務(wù)器管理器先進(jìn)行虛擬中間件盒子的實例化，規(guī)則產(chǎn)生器再引導(dǎo)流量通過實例化的虛擬中間件盒子；而資源處理器是整個機制的核心，它負(fù)責(zé)對各種輸入進(jìn)行建模并計算，下一節(jié)將描述資源處理器建模的主要內(nèi)容。

圖2　服務(wù)功能鏈構(gòu)建機制Fig. 2　Mechanism of service function chain construction

2.2　服務(wù)功能鏈構(gòu)建模型

在SDN+NFV的環(huán)境下，虛擬中間件在網(wǎng)絡(luò)節(jié)點的部署問題等同于節(jié)點資源對虛擬中間件的分配問題，而流量引導(dǎo)問題等同于對網(wǎng)絡(luò)中最優(yōu)節(jié)點的選擇問題。因此服務(wù)功能鏈構(gòu)建問題可簡化成一種考慮鏈路帶寬分配、節(jié)點資源分配以及服務(wù)器資源分配的新型路由問題。

模型描述如下：流量根據(jù)其不同的業(yè)務(wù)需求，可被劃分成若干個從si到ti的流comi(si,ti,di)，di表示總的業(yè)務(wù)需求量；給定網(wǎng)絡(luò)拓?fù)銰=(V,E)，鏈路E的鏈路容量為B(E)，節(jié)點V的容量為C(V)，分配給V節(jié)點的服務(wù)器資源為S(V)，以及一系列的服務(wù)功能業(yè)務(wù)流量D={com1,com2，…,comk}。

模型整體目標(biāo)是在盡可能多業(yè)務(wù)的同時，耗費最少的節(jié)點資源滿足所有流量的業(yè)務(wù)功能需求，從而達(dá)到節(jié)點最優(yōu)和效能最大化的目的。服務(wù)功能鏈構(gòu)建問題核心在于選擇最優(yōu)的節(jié)點構(gòu)建服務(wù)功能鏈來滿足服務(wù)需求，根據(jù)模型整體目標(biāo)，將該問題分為兩部分：第一部分是最小化問題，即選擇最小的節(jié)點集合來滿足所有的服務(wù)需求；第二部分是最大化問題，即在已選節(jié)點的基礎(chǔ)上滿足最大的業(yè)務(wù)流量，從而達(dá)到節(jié)點資源和服務(wù)器資源最大效用。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?i∈[1,m],j∈{1,2},v∈V,?u∈Vcomi

(8)

(9)

(10)

(11)

其中:式(1)是整體優(yōu)化目標(biāo)，選擇最小的節(jié)點集合來滿足業(yè)務(wù)需求；式(2)～(6)表示鏈路帶寬限制、節(jié)點資源限制、服務(wù)器資源限制以及滿足服務(wù)需求的約束；式(7)則要求節(jié)點資源處理能力大于業(yè)務(wù)需求，從而滿足處理條件；式(8)～(11)表示在節(jié)點和鏈路上的流量守恒約束。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

其中：式(15)、(16)表示節(jié)點v的總流量守恒，式(17)、(18)分別是鏈路和節(jié)點資源限制；式(19)則是流量非負(fù)約束。

2.3　求解算法

該服務(wù)功能鏈部署問題是一個組合優(yōu)化問題，同時也是NP難問題，此類問題求解方法通常采用模擬退火等啟發(fā)式算法來尋找最優(yōu)解。模擬退火(Simulated Annealing，SA)算法[13]能夠有限度地接受劣解，可以跳出局部最優(yōu)解，并且具有原理簡單、使用方便、所求解全局最優(yōu)或近似全局最優(yōu)等特點，但是其求解時間過長，步長和溫度T的初值較難設(shè)置，而且搜索過程中有概率遺失當(dāng)前的最優(yōu)解。而禁忌搜索算法(Tabu Search, TS)[14]模仿人類的記憶能力，在搜索過程采用設(shè)置禁忌表的方式來避免陷入局部最優(yōu)以及迂回搜索，很好地克服了模擬退火算法的缺點。本文參考目前解決網(wǎng)絡(luò)路徑選擇與節(jié)點資源分配問題常用的組合算法思路[15-16]，使用基于TS改進(jìn)的組合模擬退火算法TS-CSA來解決服務(wù)功能鏈部署問題。

以下簡單說明基于TS改進(jìn)的組合模擬退火算法的主要步驟。TS-CSA算法共分為兩層：其中內(nèi)層算法是對節(jié)點選擇決策進(jìn)行優(yōu)化，即對問題第一部分進(jìn)行優(yōu)化；外層算法則是在節(jié)點選擇決策的基礎(chǔ)上進(jìn)行效用最大化，即對問題第二部分進(jìn)行優(yōu)化。設(shè)g為該問題的一個解，該解在SA算法中稱為一個配置或狀態(tài)。設(shè)Ω為狀態(tài)空間，定義E(g)為狀態(tài)g的能量。Metropolis策略[17]用于計算在溫度t時從狀態(tài)g到狀態(tài)g′的轉(zhuǎn)移概率，即：

(20)

其中溫度T控制著SA算法的速度。

在外層優(yōu)化算法中，利用禁忌搜索算法中的禁忌表思想對組合模擬退火算法進(jìn)行改進(jìn)，同時增加了升溫操作，提高算法搜索效率。外層優(yōu)化算法的具體步驟如下:

1)置空禁忌表H，設(shè)置模擬退火計劃表，令初始溫度為t，升溫系數(shù)τ=1，降溫系數(shù)ξ=0．9，隨機生成問題的初始解X0，同時令當(dāng)前記憶最優(yōu)解Xbest=X0，Ω←Ω∪X0，且令禁忌長度λ(X0)=n，K=1。

2)執(zhí)行外層鄰域函數(shù)，同時更新禁忌表中各對象的禁忌長度。

3)執(zhí)行內(nèi)層優(yōu)化算法。

4)若未滿足同溫度下的抽樣穩(wěn)定準(zhǔn)則，返回步驟2)繼續(xù)尋找新解，否則執(zhí)行降溫操作。

5)若未滿足升溫條件，則返回步驟2)繼續(xù)尋找新解，否則執(zhí)行升溫操作。

6)檢驗收斂性。

算法偽代碼如下所示：

1)

while not stop

2)

Xbest=X0;tk=t;

3)

fori=1 toL

4)

ifλ(X0)>0

5)

getXnew,calculateE(Xnew)

6)

λ(X0)=λ(X0)-1;

7)

ifλ(X0)=0;

8)

goto procedure TS-CSA partⅡ

9)

end if

10)

Update the tabu listH;

11)

end if

12)

ifE(Xnew′)

13)

Xbest=Xnew′;

14)

ifE(Xnew)

15)

X0=Xnew;

16)

else CalculateP(tk)=

exp[-(E(Xnew)-E(Xk))/τt];

17)

end if

18)

if random(0,1)

19)

X0=Xnew;

20)

end if

21)

end if

22)

end for

23)

K=K+1;t=ζt;

24)

end while

25)

printXbest

內(nèi)層優(yōu)化算法的步驟為:

1)以Xnew為當(dāng)前初始解和最優(yōu)解，構(gòu)造內(nèi)層鄰域解，得到新解Xnew′。

2)判斷新解的優(yōu)劣性。

3)若未達(dá)到同溫度下的抽樣穩(wěn)定準(zhǔn)則，則返回步驟2);否則算法終止，返回外層優(yōu)化算法。

內(nèi)層算法(TS-CSA partⅡ)偽代碼如下所示：

1)

while not stop

2)

ifE(Xnew′)

3)

Xnew=Xnew′;

4)

else CalculateP(t)=exp[-(E(Xnew′)-E(Xnew))/τt];

5)

if random(0,1)

6)

Xnew=Xnew′;

7)

end if

8)

end while

3　實驗仿真與性能評估

3.1　實驗平臺

為了驗證模型與算法的可靠性與有效性，本實驗算法仿真部分在配置Intel Core i7 CPU 3.40 GHz、4 GB內(nèi)存的計算機上運行。實驗網(wǎng)絡(luò)模型如圖3所示，底層網(wǎng)絡(luò)拓?fù)浜头?wù)功能請求的拓?fù)溆蒅T-ITM[18]工具生成，通過仿真來驗證算法的性能。本文設(shè)計的服務(wù)功能鏈構(gòu)建原型模型采用ClickOS模擬網(wǎng)絡(luò)中的大量元服務(wù)實例，ClickOS是一款高性能的虛擬化平臺，當(dāng)單個物理CPU核運行100個實例時，ClickOS虛擬機(Virtual Machine, VM)能實現(xiàn)整體10 Gb/s的速率。實驗平臺由NetFPGA 10G實現(xiàn)的OpenFlow交換機的全連接網(wǎng)絡(luò)組成：每臺交換機連接一臺服務(wù)器，運行ClickOS平臺；每臺服務(wù)器配置3.4 GHz Intel Core i7處理器、4 GB內(nèi)存和1 Gb/s網(wǎng)絡(luò)接口。

3.2　實驗仿真

3.2.1服務(wù)功能鏈構(gòu)建時間

分別用GT-ITM模擬節(jié)點數(shù)k=5，連接度d=2，以及按照網(wǎng)絡(luò)復(fù)雜度越來越高的原則分別設(shè)計：k=15,d=4;k=25,d=6;k=50,d=8;k=100,d=8等網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，服務(wù)功能鏈數(shù)M=10保持不變。通過Matlab實驗分別仿真StEERING、SIMPLE和本文NUM方法的服務(wù)功能鏈的構(gòu)建時間隨節(jié)點數(shù)的變化，結(jié)果如圖4所示；再用GT-ITM模擬節(jié)點數(shù)k=10，連接度d=3的網(wǎng)絡(luò)拓?fù)?，使服?wù)功能鏈數(shù)逐漸增加，分別為M=5,10,20,50,100，通過Matlab實驗分別仿真模擬退火算法、禁忌搜索算法和改進(jìn)的組合模擬退火算法計算服務(wù)功能鏈的構(gòu)建時間隨服務(wù)功能鏈數(shù)的變化，結(jié)果如圖5所示。構(gòu)建時間越短，說明算法效率越高。

圖3　實驗網(wǎng)絡(luò)拓?fù)銯ig. 3　Experimental network topology

圖4　服務(wù)功能鏈構(gòu)建時間隨節(jié)點數(shù)變化情況Fig. 4　Service function chain construction time changes with the number of nodes

圖5　服務(wù)功能鏈構(gòu)建時間隨服務(wù)功能鏈數(shù)變化情況Fig. 5　Service function chain construction time changes with the number of service function chains

3.2.2服務(wù)功能鏈構(gòu)建成功率

定義服務(wù)功能鏈構(gòu)建成功率SR=m/M,其中:M為需求服務(wù)功能鏈數(shù)量，m為實際成功構(gòu)建的服務(wù)功能鏈數(shù)量。按照3.2.1節(jié)的數(shù)據(jù)設(shè)定通過Matlab仿真以下情況：隨著拓?fù)涔?jié)點數(shù)增多不同算法的構(gòu)建成功率，結(jié)果如圖6所示；隨著服務(wù)功能鏈增多不同算法的構(gòu)建成功率，結(jié)果如圖7所示。成功率越高說明算法越有效。

3.2.3網(wǎng)絡(luò)擁塞率

圖6　服務(wù)功能鏈構(gòu)建成功率隨節(jié)點數(shù)變化情況Fig. 6　Success rate of service function chain construction changes with the number of nodes

圖7　服務(wù)功能鏈構(gòu)建成功率隨服務(wù)功能鏈數(shù)變化情況Fig. 7　Success rate of service function chain construction changes with the number of service function chains

圖8　構(gòu)建擁塞率隨服務(wù)功能鏈數(shù)變化情況Fig. 8　Congestion rate of construction changes with the number of service function chains

3.2.4節(jié)點平均效用

圖9　節(jié)點平均效用隨服務(wù)功能鏈數(shù)變化情況Fig. 9　Mean utility of nodes changes with the number of service function chains

3.3　性能分析

圖4和圖5反映了隨著網(wǎng)絡(luò)節(jié)點數(shù)和網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)增多時不同算法的服務(wù)功能鏈構(gòu)建時間變化情況，可以看到，NUM在構(gòu)建時間上明顯少于其他兩種方法，其算法采用分層式的結(jié)構(gòu)降低了模型求解的復(fù)雜度，更利于最優(yōu)解的尋找；圖6和圖7反映了網(wǎng)絡(luò)節(jié)點數(shù)和網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)與服務(wù)功能鏈構(gòu)建成功率之間的關(guān)系，可以看到，隨著節(jié)點數(shù)和服務(wù)功能鏈數(shù)的增多，構(gòu)建成功率呈下降趨勢，但是NUM方法構(gòu)建成功率仍高于其他兩種算法，這是因為構(gòu)建成功率取決于解的優(yōu)異性，而本文TS-CSA算法尋找到的最優(yōu)解優(yōu)于其他方法；圖8反映了網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)與網(wǎng)絡(luò)擁塞率之間的關(guān)系，可以看出服務(wù)功能鏈數(shù)和擁塞率成正比，但采用NUM擁塞率較低，負(fù)載均衡性能優(yōu)于其他兩種方法，因為該方法在網(wǎng)絡(luò)中所選的節(jié)點優(yōu)于其他方法，能夠避免節(jié)點擁塞；而圖9反映了網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)與節(jié)點平均效用之間的關(guān)系，可以看出本文方法明顯提升了節(jié)點的效用(約20%)，因為該方法可以在全網(wǎng)范圍內(nèi)找到最優(yōu)節(jié)點并進(jìn)行資源最大化利用，能達(dá)到節(jié)點效用最優(yōu)。

4　結(jié)語

本文主要解決了SDN+NFV環(huán)境下的服務(wù)功能鏈構(gòu)建問題。首先，對SDN+NFV環(huán)境下的服務(wù)功能鏈構(gòu)建問題進(jìn)行詳細(xì)描述，分析了影響SFCCP的主要因素；然后介紹了本文所設(shè)計的服務(wù)功能鏈構(gòu)建機制，分別建立了最優(yōu)化節(jié)點選擇模型和最大效能模型，并利用禁忌搜索改進(jìn)模擬退火算法對模型進(jìn)行求解；最后，對比測試了在網(wǎng)絡(luò)節(jié)點和服務(wù)功能鏈數(shù)增多的情況下，不同算法的服務(wù)功能鏈構(gòu)建時間、構(gòu)建成功率和網(wǎng)絡(luò)擁塞率的變化以及采用本文方法在節(jié)點效用上的提升，結(jié)果表明本文方法具有明顯優(yōu)勢。下一步的研究主要集中在節(jié)點數(shù)及服務(wù)功能鏈數(shù)增多時如何進(jìn)一步提高構(gòu)建服務(wù)功能鏈的成功率，以及如何對過載的服務(wù)器虛擬機進(jìn)行遷移來達(dá)到網(wǎng)絡(luò)中負(fù)載均衡的目的。

參考文獻(xiàn):

[1]GEMBER A, PRABHU P, GHADIYALI Z, et al. Toward software-defined middlebox networking [C]// HotNets-XI: Proceedings of the 2012 11th ACM Workshop on Hot Topics in Networks. New York: ACM, 2012: 7-12.

[2]SHERRY J, HASAN S, SCOTT C, et al. Making middleboxes someone else’s problem: network processing as a cloud service [J]. ACM SIGCOMM Computer Communication Review — Special October issue SIGCOMM ’12, 2012, 42(4): 13-24.

[3]McKEOWN N. Software-defined networking [J]. INFOCOM Keynote Talk, 2009, 17(2): 30-32.

[4]CARAPINHA J, JIMéNEZ J. Network virtualization: a view from the bottom [C]// VISA ’09: Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 73-80.

[5]ZHANG Y, BEHESHTI N, BELIVEAU L, et al. StEERING: a software-defined networking for inline service chaining [C]// ICNP 2013: Proceedings of the 2013 21st IEEE International Conference on Network Protocols. Piscataway, NJ: IEEE, 2013: 1-10.

[6]QAZI Z A, TU C-C, CHIANG L, et al. SIMPLE-fying middlebox policy enforcement using SDN [C]// SIGCOMM ’13: Proceedings of the ACM SIGCOMM 2013 Computer Communication. New York: ACM, 2013: 27-38.

[7]FAYAZBAKHSH S K, SEKAR V, YU M, et al. FlowTags: enforcing network-wide policies in the presence of dynamic middlebox actions [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 19-24.

[8]SEKAR V, EGI N, RATNASAMY S, et al. Design and implementation of a consolidated middlebox architecture [C]// NSDI’12: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 24.

[9]MARTINS J, AHMED M, RAICIU C, et al. ClickOS and the art of network function virtualization [C]// NSDI’14: Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 459-473.

[10]GEMBER-JACOBSON A, VISWANATHAN R, PRAKASH C, et al. OpenNF: Enabling innovation in network function control [C]// SIGCOMM ’14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM, 2014: 163-174.

[11]ANWER B, BENSON T, FEAMSTER N, et al. A slick control plane for network middleboxes [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 147-148.

[12]ANWER B, BENSON T, FEAMSTER N, et al. Programming slick network functions [C]// SOSR ’15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research. New York: ACM, 2015: Article No. 14.

[13]KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671-680.

[14]GLOVER F, LAGUNA M. Tabu search [M]// Metaheuristic Procedures for Training Neutral Networks. Boston: Springer, 1993: 53-69.

[15]秦進(jìn),倪玲霖,繆立新.多級多商品流物流網(wǎng)絡(luò)設(shè)計的優(yōu)化模型與組合模擬退火算法[J].計算機應(yīng)用研究,2010,27(9):3348-3351. (QIN J, NI L L, MIU L X. Optimization model and combined simulated annealing algorithm for multi-level multi-commodity logistics network design [J]. Application Research of Computers, 2010, 27(9): 3348-3351.)

[16]LIN Y, BIAN Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing Tabu search algorithm to solve the symmetrical traveling salesman problem [J]. Applied Soft Computing, 2016, 49(C): 937-952.

[17]METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines [J]. The Journal of Chemical Physics, 1953, 21(6): 1087-1092.

[18]ZEGURA E W, CALVERT K L, ACHARJEE S B. How to model an internetwork [C]// INFOCOM’96: Proceedings of the Fifteenth Annual Joint Conference of the IEEE Computer Societies on Networking the Next Generation. Washington, DC: IEEE Computer Society, 1996, 2: 594-602.