張曉紅，黃繼海

(中州大學 信息工程學院，鄭州 450005)

1 引言

對于運營商而言，提供網(wǎng)絡(luò)服務(wù)的成本越來越高?？紤]到當前網(wǎng)絡(luò)的復(fù)雜性，即使是針對突發(fā)需求而實施的簡單升級，也可能需要數(shù)月甚至數(shù)年的時間才能完成。然而，在計算技術(shù)的進步和IT 環(huán)境中虛擬技術(shù)成功的鼓舞下，網(wǎng)絡(luò)運營商正努力推動類似的技術(shù)，希望以此作為解決擴展性問題的一種辦法。網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization，NFV)［1］便是此類選擇中的一種。它利用標準的IT 虛擬化技術(shù)，將多種類型的網(wǎng)絡(luò)設(shè)備合并到業(yè)界標準的高容量服務(wù)器、交換機和存儲設(shè)備中，并將其置于數(shù)據(jù)中心、網(wǎng)絡(luò)節(jié)點等地。

NFV 的重要技術(shù)支撐是服務(wù)功能鏈(Service Function Chain，SFC)的構(gòu)建。通過將特定的網(wǎng)絡(luò)服務(wù)抽象為一系列有序的報文處理功能實體，可以實現(xiàn)新網(wǎng)絡(luò)服務(wù)的靈活部署與服務(wù)隔離。然而，現(xiàn)有研究對NFV 中的SFC 構(gòu)建技術(shù)依然停留在資源分配［2－3］和標準建立［4－5］階段，無法實現(xiàn)SFC 的服務(wù)最優(yōu)組合。

在計算機網(wǎng)絡(luò)中，針對服務(wù)組合優(yōu)化問題的研究主要集中在基于構(gòu)件的軟件工程(Component－Based Software Engineering，CBSE)和面向服務(wù)體系結(jié)構(gòu)(Service－Oriented Architecture，SOA)等領(lǐng)域。雖然一個抽象的服務(wù)功能對應(yīng)的所有具體服務(wù)實體在功能上是等價的，但在其他屬性上是存在差異的，所以可以根據(jù)非功能屬性進行服務(wù)實體選擇和組合優(yōu)化。在不同領(lǐng)域，非功能屬性具有不同含義，基于這些屬性約束建立服務(wù)組合優(yōu)化模型并求解，已成為CBSE 和SOA 中的熱點問題。比如QoS 感知［6］的Web Services 組合問題的研究，文獻［7－8］針對順序、并發(fā)、分支、循環(huán)等4 種控制結(jié)構(gòu)的Web Services 組合模型，建立了包括費用、響應(yīng)時間、信譽、可用性等參數(shù)的評價體系來評價組合的效果，并利用整數(shù)規(guī)劃方法從全局角度進行最優(yōu)化求解。文獻［9－10］的研究思路與文獻［7－8］類似，提出了遺傳算法來解決QoS 感知的Web Services 組合問題。此外，文獻［11－13］以云計算系統(tǒng)為背景，建立基于QoS 的服務(wù)組合模型，并提出各種啟發(fā)算法。文獻［14］將信任概念和信任度引入到Web Services 組合中，分別基于信任感知和信任增強建立數(shù)學模型，并采用蟻群算法求解之。

上述研究主要針對Web Services 的組合優(yōu)化問題，其考慮的QoS 屬性并不適用于NFV 體系，且忽略了屬性的匹配約束。為此，本文提出一種適合于NFV 架構(gòu)的服務(wù)實體性能模型，并根據(jù)服務(wù)實體間的性能匹配和資源總量約束，形式化分析服務(wù)組合優(yōu)化問題;在求解過程中，為減輕大量無效解的干擾，提出了改進的模擬退火算法SCM－SA，該算法包含基于層次屬性的產(chǎn)生函數(shù)和基于偏離度的目標函數(shù)。

本文的后續(xù)部分組織如下:第2 節(jié)提出一種針對服務(wù)實體的性能模型，并在此基礎(chǔ)上分析基于性能的服務(wù)組合優(yōu)化問題;第3 節(jié)提出改進的模擬退火算法SCM－SA 及其相關(guān)函數(shù)設(shè)定;第4 節(jié)對提出的SCM－SA 算法進行實驗評估;第5 節(jié)為結(jié)束語。

2 問題描述

2.1 服務(wù)功能鏈模型

定義1 服務(wù)拓撲。在NFV 體系中，服務(wù)功能鏈可以抽象為服務(wù)拓撲Gc=(V，E，s，t)。其中，V 為服務(wù)功能集合，E 為服務(wù)間的連接關(guān)系，s 為該服務(wù)功能鏈的源節(jié)點，t 為該服務(wù)功能鏈末節(jié)點。

服務(wù)功能鏈的構(gòu)建過程分為兩步:服務(wù)拓撲映射和服務(wù)組合優(yōu)化。對于第一步，我們通過虛擬網(wǎng)映射技術(shù)［2－3］，將服務(wù)拓撲嵌入到底層網(wǎng)絡(luò)中，并為其分配節(jié)點資源和帶寬資源。對于第二步，我們需要描述服務(wù)組合的實體和約束條件。

定義2 服務(wù)實體。提供具體服務(wù)的功能實體稱之為服務(wù)實體。每個服務(wù)對應(yīng)大量的服務(wù)實體，雖然它們的服務(wù)屬性相同，但是具有多樣化的性能參數(shù)，所以我們將服務(wù)i 的第j個服務(wù)實體抽象為

式中，Configin為服務(wù)實體的輸入性能矢量，Configout為服務(wù)實體的輸出性能矢量，Res 為服務(wù)實體運行時所占用的系統(tǒng)資源矢量，k 為所考慮的資源類型數(shù)，分別為第i個輸入性能屬性和輸出性能屬性，m 為所考慮的性能屬性個數(shù)。特別地，若為，則說明服務(wù)實體不受該性能屬性的約束;若為，則說明服務(wù)實體不對外提供該性能屬性的信息。

性能屬性是指服務(wù)實體在運行時所需要的或表現(xiàn)出的某一性能方面的特性。例如某一報文分類實體在運行時輸入報文的到達速率需小于10 Gb/s，而輸出的分類結(jié)果速率為125 Mb/s。

兩個同種類型的性能屬性c1和c2進行疊加，記為c1c2。根據(jù)性能屬性類型不同，疊加符號對應(yīng)的數(shù)學運算可以是交集運算、并集運算、求和運算或最小(大)值運算等。例如，當性能屬性為傳輸速率時，c1c2=c1+c2;當性能屬性為最大時延時，c1c2=max(c1，c2);當性能屬性為執(zhí)行時間時，c1和c2均為取值區(qū)間，c1c2=c1∪c2。特別地，若c2=，則c1c2=c1;若c1=，則c1c2=c2。

定義3 性能矢量疊加。兩個性能矢量Config1和Config2進行疊加，記為Config1Config2=［c11，c12，…，c1m］［c21，c22，…，c2m］。具體表達式為

2.2 服務(wù)組合優(yōu)化

服務(wù)組合優(yōu)化問題就是從每個服務(wù)i 對應(yīng)的候選服務(wù)實體集合Si中挑選出合適的實體eij，從而得到成本最優(yōu)的服務(wù)組合模式SCMbest，且滿足性能約束和資源約束。圖1 中的SCM1={e11，e21，e31，e41，e51}和SCM2={e13，e22，e32，e42，e52}即為兩種可能的服務(wù)組合模式。

圖1 服務(wù)組合優(yōu)化問題Fig.1 Service composition optimization problem

服務(wù)組合優(yōu)化問題的關(guān)鍵在于使所有服務(wù)實體的性能需求得到滿足。

定義4 性能滿足。若服務(wù)實體eij的輸入性能矢量Configin被所依賴的服務(wù)實體{e1，e2，…，el}所滿足，則下式成立:

此外，在虛擬網(wǎng)構(gòu)建過程中，Resource=［R1，R2，…，Rk］是服務(wù)組合的資源約束條件;服務(wù)組合后的服務(wù)功能鏈也需要滿足虛擬網(wǎng)的整體性能需求Configreq=［c1，c2，…，cm］，所以末節(jié)點候選服務(wù)實體的輸出性能矢量需要與Configreq相匹配。

綜合上述設(shè)定，服務(wù)組合優(yōu)化問題可以描述為:尋找一個服務(wù)組合模式SCMbest=，n 表示候選實體集合個數(shù)，ai表示第i個候選服務(wù)實體集合中選擇的實體序號，1≤i≤n，1≤ai≤M，使其滿足

(1)除源節(jié)點外，其他服務(wù)實體的性能需求均得到滿足;

(3)組合模式中所有實體占用的資源不超過虛擬網(wǎng)限定的資源閾值Resource;

(4)在滿足上述3個條件下，選取成本最低的服務(wù)組合模式。

形式化描述如下:

式(2)表示組合模式中所有服務(wù)實體的總成本，而每個服務(wù)實體的成本=所占各種資源的成本+實體的固有成本，其中wj為資源屬性rj的單位成本;pi為候選服務(wù)實體的固有成本，為了便于描述，式(3)中將作為源節(jié)點、作為末節(jié)點，分別描述了上文中(1)、(2)和(3)三種約束條件;M為候選服務(wù)實體集合大小的上界。

服務(wù)組合優(yōu)化問題是一個具有復(fù)雜約束的整數(shù)規(guī)劃問題，其復(fù)雜性為NP－h(huán)ard。如果采用遍歷方式，則最壞情況下搜索的模式數(shù)為O(Mn)，模式的有效性判別時間復(fù)雜度為O(n2)，所以總的時間復(fù)雜度為O(Mnn2)，僅適用于小規(guī)模服務(wù)組合。為適應(yīng)不同規(guī)模的服務(wù)組合，需要采用啟發(fā)算法。

現(xiàn)有啟發(fā)式算法如模擬退火算法、遺傳算法、粒子群算法等主要采用罰函數(shù)方法或者松弛方法消除約束條件，但考慮到本文提出的服務(wù)組合優(yōu)化問題的約束條件屬于整數(shù)約束而且較為復(fù)雜，上述方法均難以保證能以較大概率收斂到有效解。因此，本文提出一種改進的啟發(fā)式算法，能夠有目的性地產(chǎn)生新解，從而提高算法收斂到有效解的概率。然而，遺傳算法和粒子群算法的新解產(chǎn)生過程相對受限，因此后文對模擬退火算法進行改進，利用解的性能需求約束的分層特性，設(shè)計適合服務(wù)組合優(yōu)化問題的新解產(chǎn)生函數(shù)和目標函數(shù)。

3 服務(wù)組合優(yōu)化算法

模擬退火算法是一種適合解決NP－h(huán)ard 問題的通用有效的全局優(yōu)化算法，其基本思想是從任意解出發(fā)，每次產(chǎn)生一個鄰居解，直接接受使目標函數(shù)更優(yōu)的鄰居解，或以一定概率接受使目標函數(shù)變差的鄰居解，不斷迭代上述過程，最終得到使目標函數(shù)全局最優(yōu)的近似解。采用改進的模擬退火算法解決服務(wù)組合優(yōu)化問題，關(guān)鍵在于確定新解的產(chǎn)生函數(shù)(Generation Function)和目標函數(shù)(Cost Function)的計算公式，以便克服無效解的干擾。

3.1 基于層次屬性的產(chǎn)生函數(shù)

首先，需要對問題的解進行編碼。服務(wù)組合優(yōu)化問題的解(即服務(wù)組合模式)使用了一個整數(shù)數(shù)組來表示，數(shù)組的長度為組成服務(wù)功能鏈的服務(wù)實體數(shù)n，數(shù)組中的每個元素為該服務(wù)實體所對應(yīng)的索引號，比如服務(wù)組合模式SCMi={e13，e21，e32，e42，e54}可以被編碼為［3，1，2，2，4］的數(shù)組。然后，算法的初始化過程就是對數(shù)組中的元素賦予隨機的正整數(shù)值，并且取值范圍不超過相應(yīng)候選服務(wù)實體集合的大小。

成立金融改革工作領(lǐng)導(dǎo)小組，政府主要領(lǐng)導(dǎo)任組長，駐地金融監(jiān)管部門和相關(guān)部門為成員單位，建立健全跨行業(yè)、跨部門的工作聯(lián)動機制，加強統(tǒng)籌協(xié)調(diào)，整體推進和監(jiān)督落實，協(xié)調(diào)重大金融項目和金融改革政策落地實施；領(lǐng)導(dǎo)小組下設(shè)辦公室在政府金融辦，政府金融辦主任兼任辦公室主任負責領(lǐng)導(dǎo)小組日常工作；領(lǐng)導(dǎo)小組及其辦公室不刻制印章，如因工作需要由市政府金融辦代章；各地也要建立相應(yīng)的工作推進機制，形成上下齊抓共管的金融改革工作新格局。

為了更好地逼近有效解，模擬退火算法設(shè)計了具有記憶性的新解產(chǎn)生函數(shù)。所謂有記憶性是指新解產(chǎn)生函數(shù)能夠記錄當前解的層次屬性(見定義5)，并且根據(jù)具體情況產(chǎn)生三種類型的新解:具有相同層次屬性的新解;具有更高層次屬性的新解;具有更低層次屬性的新解。下面給出解的層次屬性定義。

定義5 解的層次屬性。根據(jù)圖論中的反向拓撲排序算法，解數(shù)組中的每個元素所代表的候選服務(wù)實體都存在唯一的層次編號。新解是通過隨機改變舊解數(shù)組中的若干元素得到的，并且這些元素所代表的候選服務(wù)實體具有相同的層次編號，所以每個解的產(chǎn)生都與一個層次編號相關(guān)聯(lián)，該編號稱為解的層次屬性。

在對候選服務(wù)實體的層次編號進行預(yù)計算后，新解產(chǎn)生函數(shù)的處理流程如下所示:

GenFunc 函數(shù)每次只針對首先出現(xiàn)性能約束不匹配的一層進行隨機改變生成新解;如遇有效解，則隨機從某一層開始新解的生成。經(jīng)過逐層推進，解的性能約束條件逐漸得到滿足，從而趨近有效解。這種方式有利于避免普通隨機生成方式的盲目性，提高有效解的搜索效率。

3.2 基于偏離度的目標函數(shù)

對于當前解Mold和新產(chǎn)生的解Mnew，若目標函數(shù)值f(Mnew)＜f(Mold)，則直接接受Mnew為當前解;若f(Mnew)≥f(Mold)，則依接受概率接受Mnew。接受概率P(Mold，Mnew，t)的計算公式如下:

根據(jù)公式(4)，定義如下的目標函數(shù)計算公式:

式(5)中的Cost 函數(shù)用來計算當前解(服務(wù)組合模式)所消耗的成本值，具體見公式(2);Conflict.size()表示當前層次的服務(wù)實體集合中違反與上層服務(wù)實體性能依賴關(guān)系的個數(shù)，1 +Conflict.size()即為解的偏離度。

3.3 基于模擬退火的服務(wù)組合模式搜索

基于上述函數(shù)設(shè)計，可以得到基于模擬退火的服務(wù)組合模式搜索算法(Service Composition Mode search algorithm based on Simulated Annealing，SCM－SA)的完整處理流程如下:

3.4 復(fù)雜度分析

由于SCM－SA 算法是基于模擬退火算法，因此新解的迭代產(chǎn)生次數(shù)是受參數(shù)影響的，如果將算法參數(shù)視作常數(shù)，則迭代次數(shù)的復(fù)雜度是O(1)。對于新解產(chǎn)生函數(shù)GenFunc，其計算復(fù)雜性主要體現(xiàn)在第8步“while j ＜L do”中，其復(fù)雜度為O(n2)，而該步的執(zhí)行次數(shù)由服務(wù)拓撲的最大節(jié)點度D 和最大層次數(shù)H決定，最壞情況下次數(shù)為O(D +H)，因此函數(shù)Gen-Func 的最壞情況復(fù)雜度為O(n2(D+H))。

4 實驗評估

4.1 實驗設(shè)置

通過C++編程模擬服務(wù)組合優(yōu)化問題并實現(xiàn)模擬退火算法。實驗方案主要為了評估SCM－SA算法相比于其他啟發(fā)式算法在服務(wù)組合成功率和組合代價上的優(yōu)勢。服務(wù)組合成功率CSR 是指所有服務(wù)組合請求中成功的比例。

在實驗數(shù)據(jù)上，利用TGFF［15］工具隨機生成具有指定節(jié)點數(shù)的服務(wù)拓撲，且只考慮有向無環(huán)圖(DAG)。利用C++語言生成候選服務(wù)實體集合，其中每個候選服務(wù)實體集合大小在［3，10］內(nèi)均勻分布。每個候選服務(wù)實體的性能矢量長度為3，且性能屬性的取值為0 或1，疊加符號對應(yīng)最小值運算，其中1 的概率為90%。候選服務(wù)實體的資源屬性個數(shù)為3，且取值在［10，100］內(nèi)均勻分布，各資源屬性的單位成本w1、w2和w3分別設(shè)為1.0、1.0 和1.0，總量均設(shè)為4000。此外，候選服務(wù)實體的固有成本取值在［10，15］內(nèi)均勻分布。

4.2 性能評估

實驗中，SCM－SA 算法的主要參數(shù)取值如下:初始溫度Ts=1000，終止溫度Te=10，降溫比例a=0.9，每個溫度下迭代的次數(shù)L=5 ×n(n 為服務(wù)拓撲節(jié)點數(shù))，收斂條件R=50。在不同服務(wù)組合規(guī)模下(n=10，15，20，25，30，35，40)，分別進行60 次服務(wù)組合問題求解，計算不同算法的服務(wù)組合成功率CSR，結(jié)果如圖2 所示?？梢钥闯?，隨著服務(wù)組合規(guī)模的擴大，服務(wù)間的性能依賴關(guān)系更加復(fù)雜化，從而使各種算法的CSR 值逐漸降低。其中，SCM－ SA算法的CSR 值保持在46.7%以上，高于其他算法;單純考慮有效解的模擬退火算法Feasible－ SA 的CSR 值始終低于SCM－SA 算法，且隨組合規(guī)模n 的擴大而下降至16.7%;不考慮解有效性的基本遺傳算法GA 的CSR 值最低，不超過10%。上述結(jié)果表明，單純考慮有效解方式會使部分搜索陷入僵局，降低CSR 值，基本啟發(fā)式算法(GA)則很難在復(fù)雜約束條件下收斂到有效解，所以CSR 值最低。

圖2 不同算法的服務(wù)組合成功率(CSR)比較Fig.2 CSR comparison among different algorithms

相同實驗環(huán)境下，比較不同算法的最優(yōu)服務(wù)組合模式成本值，如圖3 所示。從實驗結(jié)果可以看出，不同算法的服務(wù)組合模式成本值的大小關(guān)系為CSCM－SA＜ CFeasible－SA＜ CGA，其中Feasible－ SA 和GA 算法的成本值比較接近。隨著服務(wù)組合規(guī)模n的擴大，不同算法的成本值差距逐漸增大。上述結(jié)果表明，單純考慮有效解方式會使結(jié)果陷入局部最優(yōu)，而基本啟發(fā)式算法又易受無效解的干擾，從而使算法得到的成本值偏大。

圖3 不同算法得到的最優(yōu)組合代價Fig.3 Composition cost comparison among different algorithms

比較不同算法的時間消耗，如圖4 所示。從實驗結(jié)果可以看出，基本遺傳算法GA 的時間消耗最小且波動不明顯，單純考慮有效解的模擬退火算法Feasible－SA 的時間消耗最大，且隨問題規(guī)模呈非線性增長，而SCM－SA 算法的時間消耗低于Feasible－SA，原因在于，GA 的新解產(chǎn)生函數(shù)跟問題規(guī)模無關(guān)，而Feasible－SA 和SCM－SA 的新解產(chǎn)生函數(shù)跟問題規(guī)模有關(guān)，并且Feasible－SA 只考慮有效解，導(dǎo)致調(diào)用新解產(chǎn)生函數(shù)的次數(shù)多于SCM－SA，因此時間消耗大于SCM－SA。

圖4 不同算法的時間消耗Fig.4 Time cost comparison among different algorithms

上述實驗在不同組合規(guī)模和仿真數(shù)據(jù)下重復(fù)進行，結(jié)果表明SCM－SA 算法在服務(wù)組合成功率和服務(wù)組合成本上優(yōu)于其他算法。

5 結(jié)束語

本文對網(wǎng)絡(luò)功能虛擬化中的服務(wù)功能鏈構(gòu)建和服務(wù)組合優(yōu)化問題進行了論述。首先，針對服務(wù)實體的性能描述需求和匹配約束特性，給出了一種服務(wù)實體性能模型，并在此基礎(chǔ)上形式化分析服務(wù)組合優(yōu)化問題。然后，為減輕大量不滿足性能約束的無效解對搜索過程的干擾，提出了改進的模擬退火算法SCM－SA。最后，通過仿真實驗驗證了SCMSA 算法在服務(wù)組合成功率和組合成本上具有明確的優(yōu)勢。

本文對單一服務(wù)組合請求下的優(yōu)化問題進行了研究，而實際的服務(wù)組合請求可以是在線到達的，所以下一步需對在線模式下的服務(wù)組合優(yōu)化問題進行研究。

［1］Network Functions Virtualisation(NFV).Network Operator Perspectives on Industry Progress，ETSI ［EB/OL］.2014－04－ 01［2015－ 01－ 05］.http://portal.etsi.org/NFV/NFV_White_Paper2.pdf.

［2］Yu M，Yi Y，Rexford J，et al.Rethinking virtual network embedding:substrate support for path splitting and migration［J］.ACM SIGCOMM Computer Communication Review，2008，38(2):17－29.

［3］Chowdhury M，Rahman M R，Boutaba R.Vineyard:Virtual network embedding algorithms with coordinated node and link mapping［J］.IEEE/ACM Transactions on Networking，2012，20(1):206－219.

［4］Boucadair M，Jacquenet C，Parker R，et al.Service Function Chaining:Framework ＆ Architecture［EB/OL］.2014－08－16［2015－01－05］.http://tools.ietf.org/html/draft－boucadair－sfc－framework－02.

［5］Quinn P，Beliveau A.Service Function Chaining(SFC)Architecture［EB/OL］.2014－02－04［2015－01－05］.http://tools.ietf.org/html/draft－merged－sfc－architecture－01.

［6］Menasce D.QoS issues in Web service［J］.Internet Computing，2002，6(6):72－75.

［7］Zeng L，Benatallah B，Ngu A H H，et al.Qos－aware middleware for web services composition［J］.IEEE Transactions on Software Engineering，2004，30(5):311－327.

［8］Zeng L，Benatallah B，Dumas M，et al.Quality driven web services composition［C］//Proceedings of the 12th International Conference on World Wide Web.New York:ACM，2003:411－421.

［9］張成文，蘇森，陳俊亮.基于遺傳算法的QoS 感知的Web服務(wù)選擇［J］.計算機學報，2006，29(7):1029－1037.ZHANG Chengwen，SU Sen，CHEN Junliang.Genetic algorithm on web services selection supporting QoS［J］.Chinese Journal of Computers，2006，29(7):1029－1037.(in Chinese)

［10］蔣哲遠，韓江洪，王釗.動態(tài)的QoS 感知Web 服務(wù)選擇和組合優(yōu)化模型［J］.計算機學報，2009(5):1014－1025.JIANG Zheyuan，HAN Jianghong，WANG Zhao.An Optimization Model for Dynamic QoS－Aware Web Services Selection and Composition［J］.Chinese Journal of Computers，2009(5):1014－1025.(in Chinese)

［11］Ma H，Bastani F，Yen I L，et al.QoS－ driven service composition with reconfigurable services［J］.IEEE Transactions on Services Computing，2013，6(1):20－34.

［12］Xiang F，Hu Y，Yu Y，et al.QoS and energy consumption aware service composition and optimal－ selection based on Pareto group leader algorithm in cloud manufacturing system［J］.Central European Journal of Operations Research，2014，22(4):663－685.

［13］Tao F，LaiLi Y，Xu L，et al.FC－PACO－RM:a parallel method for service composition optimal－selection in cloud manufacturing system［J］.IEEE Transactions on Industrial Informatics，2013，9(4):2023－2033.

［14］王勇，代桂平，侯亞榮.信任感知的組合服務(wù)動態(tài)選擇方法［J］.計算機學報，2009，32(8):1668－1675.WANG Yong，DAI Guiping，HOU Yarong.Dynamic methods of trust－aware composite service selection［J］.Chinese Journal of Computers，2009，32(8):1668－1675.(in Chinese)

［15］Dick R P，Rhodes D L，Wolf W.TGFF:task graphs for free［C］//Proceedings of the 6th International Workshop on Hardware/Software Codesign.Seattle:IEEE，1998:97－101.