張傳浩，周　橋

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

模型整體目標(biāo)是在盡可能多業(yè)務(wù)的同時(shí)，耗費(fèi)最少的節(jié)點(diǎn)資源滿足所有流量的業(yè)務(wù)功能需求，從而達(dá)到節(jié)點(diǎn)最優(yōu)和效能最大化的目的。服務(wù)功能鏈構(gòu)建問(wèn)題核心在于選擇最優(yōu)的節(jié)點(diǎn)構(gòu)建服務(wù)功能鏈來(lái)滿足服務(wù)需求，根據(jù)模型整體目標(biāo)，將該問(wèn)題分為兩部分：第一部分是最小化問(wèn)題，即選擇最小的節(jié)點(diǎn)集合來(lái)滿足所有的服務(wù)需求；第二部分是最大化問(wèn)題，即在已選節(jié)點(diǎn)的基礎(chǔ)上滿足最大的業(yè)務(wù)流量，從而達(dá)到節(jié)點(diǎn)資源和服務(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é)點(diǎn)集合來(lái)滿足業(yè)務(wù)需求；式(2)～(6)表示鏈路帶寬限制、節(jié)點(diǎn)資源限制、服務(wù)器資源限制以及滿足服務(wù)需求的約束；式(7)則要求節(jié)點(diǎn)資源處理能力大于業(yè)務(wù)需求，從而滿足處理?xiàng)l件；式(8)～(11)表示在節(jié)點(diǎn)和鏈路上的流量守恒約束。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

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

2.3　求解算法

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

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

(20)

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

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

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

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

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

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

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

6)檢驗(yàn)收斂性。

算法偽代碼如下所示：

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　實(shí)驗(yàn)仿真與性能評(píng)估

3.1　實(shí)驗(yàn)平臺(tái)

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

3.2　實(shí)驗(yàn)仿真

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

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

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

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

圖5　服務(wù)功能鏈構(gòu)建時(shí)間隨服務(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為實(shí)際成功構(gòu)建的服務(wù)功能鏈數(shù)量。按照3.2.1節(jié)的數(shù)據(jù)設(shè)定通過(guò)Matlab仿真以下情況：隨著拓?fù)涔?jié)點(diǎn)數(shù)增多不同算法的構(gòu)建成功率，結(jié)果如圖6所示；隨著服務(wù)功能鏈增多不同算法的構(gòu)建成功率，結(jié)果如圖7所示。成功率越高說(shuō)明算法越有效。

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

圖6　服務(wù)功能鏈構(gòu)建成功率隨節(jié)點(diǎn)數(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é)點(diǎn)平均效用

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

3.3　性能分析

圖4和圖5反映了隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)增多時(shí)不同算法的服務(wù)功能鏈構(gòu)建時(shí)間變化情況，可以看到，NUM在構(gòu)建時(shí)間上明顯少于其他兩種方法，其算法采用分層式的結(jié)構(gòu)降低了模型求解的復(fù)雜度，更利于最優(yōu)解的尋找；圖6和圖7反映了網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)與服務(wù)功能鏈構(gòu)建成功率之間的關(guān)系，可以看到，隨著節(jié)點(diǎn)數(shù)和服務(wù)功能鏈數(shù)的增多，構(gòu)建成功率呈下降趨勢(shì)，但是NUM方法構(gòu)建成功率仍高于其他兩種算法，這是因?yàn)闃?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)于其他兩種方法，因?yàn)樵摲椒ㄔ诰W(wǎng)絡(luò)中所選的節(jié)點(diǎn)優(yōu)于其他方法，能夠避免節(jié)點(diǎn)擁塞；而圖9反映了網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)與節(jié)點(diǎn)平均效用之間的關(guān)系，可以看出本文方法明顯提升了節(jié)點(diǎn)的效用(約20%)，因?yàn)樵摲椒梢栽谌W(wǎng)范圍內(nèi)找到最優(yōu)節(jié)點(diǎn)并進(jìn)行資源最大化利用，能達(dá)到節(jié)點(diǎn)效用最優(yōu)。

4　結(jié)語(yǔ)

本文主要解決了SDN+NFV環(huán)境下的服務(wù)功能鏈構(gòu)建問(wèn)題。首先，對(duì)SDN+NFV環(huán)境下的服務(wù)功能鏈構(gòu)建問(wèn)題進(jìn)行詳細(xì)描述，分析了影響SFCCP的主要因素；然后介紹了本文所設(shè)計(jì)的服務(wù)功能鏈構(gòu)建機(jī)制，分別建立了最優(yōu)化節(jié)點(diǎn)選擇模型和最大效能模型，并利用禁忌搜索改進(jìn)模擬退火算法對(duì)模型進(jìn)行求解；最后，對(duì)比測(cè)試了在網(wǎng)絡(luò)節(jié)點(diǎn)和服務(wù)功能鏈數(shù)增多的情況下，不同算法的服務(wù)功能鏈構(gòu)建時(shí)間、構(gòu)建成功率和網(wǎng)絡(luò)擁塞率的變化以及采用本文方法在節(jié)點(diǎn)效用上的提升，結(jié)果表明本文方法具有明顯優(yōu)勢(shì)。下一步的研究主要集中在節(jié)點(diǎn)數(shù)及服務(wù)功能鏈數(shù)增多時(shí)如何進(jìn)一步提高構(gòu)建服務(wù)功能鏈的成功率，以及如何對(duì)過(guò)載的服務(wù)器虛擬機(jī)進(jìn)行遷移來(lái)達(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),倪玲霖,繆立新.多級(jí)多商品流物流網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化模型與組合模擬退火算法[J].計(jì)算機(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.