武靜雯，江凌云

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

在傳統(tǒng)網(wǎng)絡(luò)中，各種網(wǎng)絡(luò)服務(wù)都是基于硬件的中間件來實(shí)現(xiàn)的，它們通常部署在特定的硬件設(shè)備上[1]。但是，隨著互聯(lián)網(wǎng)的飛快發(fā)展，傳統(tǒng)網(wǎng)絡(luò)的僵化結(jié)構(gòu)和中間件對(duì)特定硬件設(shè)備的嚴(yán)重依賴已無法滿足用戶的靈活定制需求[2]。應(yīng)對(duì)這一挑戰(zhàn)，網(wǎng)絡(luò)功能虛擬化(network function virtualization，NFV)的出現(xiàn)帶來了新的機(jī)遇[3]。NFV中的一個(gè)網(wǎng)絡(luò)服務(wù)可以表示為一個(gè)服務(wù)功能鏈(service function chain，SFC)，它由一系列按給定順序的虛擬網(wǎng)絡(luò)功能(virtual network function，VNF)組成，為了提供高效的服務(wù)，SFC部署在多個(gè)不同的服務(wù)器中，并引導(dǎo)流量以特定順序通過一組VNF。

SFC部署問題是NP-hard，現(xiàn)有大部分研究都集中于SFC在單域網(wǎng)絡(luò)的部署問題，但是由于地理位置的限制，SFC部署必須跨域進(jìn)行，因此SFC跨域部署問題的研究是至關(guān)重要的。現(xiàn)有文獻(xiàn)主要提出兩種方法來解決跨域SFC部署問題，即集中式和分布式，其中分布式方法是更貼合實(shí)際的[4]，這是目前研究的重點(diǎn)和難點(diǎn)。

文獻(xiàn)[4]提出了切鏈再部署的SFC跨域部署方案，其采用全網(wǎng)聚合技術(shù)將物理網(wǎng)絡(luò)抽象，基于各個(gè)域網(wǎng)絡(luò)的剩余資源完成SFC切鏈。但是該方案并未考慮到不同類型的VNF資源需求是不同的，對(duì)此，本文基于先前的研究成果[5]，提出了SFC切鏈改進(jìn)算法。

針對(duì)SFC切鏈后再部署的問題，目前已有大量文獻(xiàn)進(jìn)行了研究。但是，現(xiàn)有文獻(xiàn)中將節(jié)能作為優(yōu)化目標(biāo)的研究很少，同時(shí)，節(jié)能和負(fù)載均衡是兩個(gè)相互沖突的優(yōu)化目標(biāo)[6]，如何在負(fù)載均衡和節(jié)能之間做出合適的權(quán)衡是一個(gè)具有挑戰(zhàn)性的問題。對(duì)此，本文提出了共同優(yōu)化能耗和負(fù)載均衡的SFC部署方案。

1 相關(guān)工作

為了提高網(wǎng)絡(luò)資源利用率和網(wǎng)絡(luò)運(yùn)營(yíng)商的效率，單域網(wǎng)絡(luò)的SFC部署問題得到了廣泛的研究。文獻(xiàn)[7]設(shè)計(jì)了一種基于采樣的馬爾可夫方法，用于部署SFC的VNF，以最小化能耗和流量感知成本。文獻(xiàn)[8]提出了整數(shù)線性規(guī)劃模型來降低SFC的部署成本，并提出了一種啟發(fā)式算法來提供近似模型的解決方案。

據(jù)調(diào)研，只有少數(shù)研究涉及SFC的跨域部署問題。文獻(xiàn)[9]從理論上分析了跨不同管理域的NFV問題，并討論了解決問題的挑戰(zhàn)和方向，但是并未提出用于VNF部署或SFC映射的具體算法。文獻(xiàn)[10]研究了在多域彈性光網(wǎng)絡(luò)中經(jīng)濟(jì)高效地配置VNF圖的問題，此外，他們基于最小 k-cut問題設(shè)計(jì)了兩種啟發(fā)式算法。但是，文獻(xiàn)[10]中的工作是假設(shè)VNF應(yīng)該組裝成圖而不是服務(wù)鏈，并且只考慮了具有兩個(gè)域的理想網(wǎng)絡(luò)。文獻(xiàn)[11]制定了一個(gè)整數(shù)線性優(yōu)化模型，以在多云網(wǎng)絡(luò)中優(yōu)化SFC，作者還提出了幾種啟發(fā)式算法來解決該問題。文獻(xiàn)[12]提出了一種在線拍賣機(jī)制，用于在多云網(wǎng)絡(luò)中配置動(dòng)態(tài)虛擬集群。文獻(xiàn)[4]提出了基于切鏈的SFC跨域部署方案，其根據(jù)各個(gè)域網(wǎng)絡(luò)的剩余資源來完成SFC切鏈，但并未考慮不同類型VNF的資源需求是不同的，對(duì)此，本文提出了SFC切鏈改進(jìn)算法。

現(xiàn)有大多數(shù)研究中，提出的SFC部署方案大部分是基于不同的優(yōu)化目標(biāo)。文獻(xiàn)[13]將SFC映射問題抽象為多目標(biāo)線性優(yōu)化問題，其目標(biāo)是最大化資源利用率，并提出了啟發(fā)式算法來解決該問題。文獻(xiàn)[14]提出了一個(gè)有效的框架，該框架將隨機(jī)云選擇的概念與基于支持向量回歸的預(yù)測(cè)模型相結(jié)合，提出了成本優(yōu)化、延遲感知的SFC部署算法。文獻(xiàn)[15]通過資源整合來最小化物理網(wǎng)絡(luò)中的能耗。文獻(xiàn)[16]提出了一種旨在同時(shí)平衡網(wǎng)絡(luò)和服務(wù)器負(fù)載的聯(lián)合優(yōu)化算法。雖然先前的研究已取得了顯著的成果，但由于大部分研究?jī)H考慮了單一優(yōu)化目標(biāo)，忽略了其它優(yōu)化目標(biāo)，這樣，整體來看并不是最優(yōu)的解決方案。鑒于現(xiàn)存文獻(xiàn)中對(duì)節(jié)能和負(fù)載均衡多目標(biāo)優(yōu)化的SFC部署方案甚少，對(duì)此，本文提出了共同優(yōu)化節(jié)能和負(fù)載均衡的SFC部署算法。

2 問題描述

2.1 系統(tǒng)模型

2.1.1 網(wǎng)絡(luò)模型

將多域物理網(wǎng)絡(luò)建模為無向圖G=(S，R)， 其中S是各個(gè)域網(wǎng)絡(luò)服務(wù)器節(jié)點(diǎn)的集合，而R是各個(gè)域網(wǎng)絡(luò)總資源容量的集合。其中，Gi=(Si，Ri) 表示第i個(gè)域網(wǎng)絡(luò)，Si和Ri分別表示第i個(gè)域網(wǎng)絡(luò)中的服務(wù)器節(jié)點(diǎn)集合和資源容量集合。G=∪NGiGi， 其中NG表示域網(wǎng)絡(luò)數(shù)。域網(wǎng)絡(luò)Gi中的服務(wù)器節(jié)點(diǎn)集定義為SiNG， 域網(wǎng)絡(luò)Gi中的第j個(gè)服務(wù)器節(jié)點(diǎn)定義為si，jNG∈SiNG?SNG。 不同域網(wǎng)絡(luò)中的服務(wù)器具有不同的資源容量，包括計(jì)算、存儲(chǔ)和內(nèi)存容量，本文僅考慮更易成為性能瓶頸的計(jì)算資源，每個(gè)服務(wù)器si，jSN都關(guān)聯(lián)了計(jì)算資源容量，即rpi，jcpu。

2.1.2 SFC請(qǐng)求

如圖1所示為SFC的轉(zhuǎn)發(fā)映射示意圖，圖中有兩個(gè)不同的SFC，但它們具有完全相同的宿源地址，分別經(jīng)過不同的中間件以完成不同的服務(wù)功能。其中實(shí)線表示的第一個(gè)SFC依次經(jīng)過防火墻、負(fù)載均衡器，虛線表示的第二個(gè)SFC依次經(jīng)過防火墻、入侵檢測(cè)系統(tǒng)(intrusion detection system，IDS)以及視頻優(yōu)化器。

圖1 SFC轉(zhuǎn)發(fā)映射

圖中的流分類器負(fù)責(zé)識(shí)別網(wǎng)絡(luò)流量，并分發(fā)至不同的SFC，轉(zhuǎn)發(fā)器負(fù)責(zé)將網(wǎng)絡(luò)流量轉(zhuǎn)發(fā)至不同的中間件(即VNF)。SFC作為網(wǎng)絡(luò)服務(wù)的一種實(shí)現(xiàn)方式，基于網(wǎng)絡(luò)連通性，為用戶提供了多樣的L4-L7層的增值服務(wù)，它由一系列不同類型的VNF按序組成[17]，本文重點(diǎn)研究如何為不同類型的VNF選擇合適的部署域，并選擇合適的服務(wù)器進(jìn)行實(shí)例化部署。

本文定義f={f1，f2，f3，…，fNf} 為不同類型VNF的集合，其中fi表示第i類型的VNF，Nf表示VNF類型的總數(shù)，不同類型的VNF具有不同的資源需求，本文僅考慮更易成為網(wǎng)絡(luò)性能瓶頸的計(jì)算資源，將VNFfi的計(jì)算資源需求表示為rdicpu。 同時(shí)定義F={F1，F(xiàn)2，F(xiàn)3，…，F(xiàn)NF} 為SFC服務(wù)請(qǐng)求的集合，其中Fi，j∈Fi∈F表示第i個(gè)SFCFi上的第j個(gè)VNF，NF表示SFC服務(wù)請(qǐng)求的總數(shù)。

2.2 系統(tǒng)框架

圖2為本文所提出的跨域SFC部署系統(tǒng)框架，具體介紹說明如下。

圖2 跨域SFC部署系統(tǒng)框架

2.2.1 模塊功能

(1)NFV編排器

NFV編排器是ETSI定義的NFV架構(gòu)框架中的NFVO組件，管理VNF生命周期。它負(fù)責(zé)接收來自SDN控制器組件的服務(wù)請(qǐng)求，并通過與SFC切鏈組件通信獲取SFC切鏈方案，最后再將SFC切鏈方案發(fā)送給SDN控制器組件以提供服務(wù)。

(2)SDN控制器

SDN控制器共分為兩類，一個(gè)是集中控制器(如圖2中的C0)，另一個(gè)是域控制器(如圖2中的C1、C2和C3)。整個(gè)網(wǎng)絡(luò)由多個(gè)域網(wǎng)絡(luò)組成，例如圖2中有3個(gè)域網(wǎng)絡(luò)，所有域控制器都由集中控制器控制和管理。域控制器負(fù)責(zé)控制和管理每個(gè)域中的所有底層網(wǎng)絡(luò)設(shè)備，包括轉(zhuǎn)發(fā)設(shè)備和物理服務(wù)器。前者負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)流，后者用于實(shí)例化VNF。

為實(shí)現(xiàn)共同優(yōu)化節(jié)能和負(fù)載均衡的跨域SFC部署，本文在SDN控制器組件中添加了4個(gè)功能模塊，分別是需求預(yù)測(cè)模塊、能量檢測(cè)模塊、網(wǎng)絡(luò)監(jiān)控模塊和信息收集模塊，它們的主要功能描述如下：

1)需求預(yù)測(cè)模塊

該模塊負(fù)責(zé)預(yù)測(cè)不同類型VNF的資源需求，這是基于先前文獻(xiàn)[4]的研究成果。將訓(xùn)練好的預(yù)測(cè)模型集成至該系統(tǒng)，這樣可以實(shí)時(shí)獲得各類型VNF的資源需求信息，從而做出合適的部署決策。

2)能量檢測(cè)模塊

該模塊負(fù)責(zé)檢測(cè)各個(gè)域網(wǎng)絡(luò)中服務(wù)器的平均能耗，將各個(gè)域網(wǎng)絡(luò)的平均能耗信息記錄在數(shù)據(jù)庫(kù)中，實(shí)現(xiàn)在最小化能耗的情況下，完成SFC跨域部署。

3)網(wǎng)絡(luò)監(jiān)控模塊

該模塊負(fù)責(zé)監(jiān)控每臺(tái)服務(wù)器的網(wǎng)絡(luò)狀態(tài)和工作負(fù)載的變化。一旦網(wǎng)絡(luò)狀態(tài)或服務(wù)器工作負(fù)載發(fā)生變化，會(huì)更新存儲(chǔ)在數(shù)據(jù)庫(kù)中的相應(yīng)信息，從而為每個(gè)服務(wù)請(qǐng)求計(jì)算最佳部署方案。

4)信息收集模塊

該模塊負(fù)責(zé)收集各個(gè)域的總剩余資源，此處并未涉及到各個(gè)域網(wǎng)絡(luò)的具體拓?fù)湫畔⒑唾Y源信息，符合實(shí)際中各個(gè)域網(wǎng)絡(luò)信息隔離的情況。

(3)SFC切鏈組件

該組件通過與集中控制器C0通信，獲取該SFC中各類型VNF的資源需求情況以及每個(gè)域網(wǎng)絡(luò)的剩余資源情況，基于這些信息生成合適的SFC切鏈方案。

(4)SFC子鏈部署組件

該組件通過與各個(gè)域控制器通信，獲取該SFC子鏈中各類型VNF的資源需求情況以及當(dāng)前域網(wǎng)絡(luò)的剩余資源情況，基于這些信息生成合適的SFC子鏈部署方案。

2.2.2 工作流程

(1)當(dāng)終端用戶進(jìn)入多域網(wǎng)絡(luò)時(shí)，向SDN控制器C0發(fā)送服務(wù)請(qǐng)求；

(2)SDN控制器C0將服務(wù)請(qǐng)求轉(zhuǎn)發(fā)給NFV編排器，NFV編排器將此服務(wù)請(qǐng)求轉(zhuǎn)化為SFC；

(3)NFV編排器將SFC發(fā)送給SFC切鏈組件；

(4)SFC切鏈組件通過與SDN控制器C0通信獲取各個(gè)域網(wǎng)絡(luò)的總剩余資源量及SFC中不同類型VNF所需的資源量；

(5)SFC切鏈組件調(diào)用算法1完成SFC的切鏈，以實(shí)現(xiàn)多個(gè)域網(wǎng)絡(luò)的負(fù)載均衡；

(6)SFC切鏈組件將SFC切鏈方案發(fā)送給NFV編排器，NFV編排器轉(zhuǎn)發(fā)給SDN控制器C0；

(7)SDN控制器C0與各個(gè)域控制器進(jìn)行通信，并將步驟(5)獲得的SFC子鏈分別分配給每個(gè)域網(wǎng)絡(luò)以完成進(jìn)一步的部署；

(8)SFC子鏈部署組件通過與域控制器通信獲取當(dāng)前域網(wǎng)絡(luò)的服務(wù)器資源使用情況及SFC子鏈中不同類型VNF所需的資源情況；

(9)SFC子鏈部署組件調(diào)用算法2完成SFC子鏈部署，實(shí)現(xiàn)單域網(wǎng)絡(luò)節(jié)能和負(fù)載均衡的合適權(quán)衡；

(10)SFC子鏈部署組件將計(jì)算所得的SFC子鏈部署方案發(fā)送給各個(gè)域控制器，由域控制器負(fù)責(zé)完成SFC子鏈的部署；

(11)當(dāng)網(wǎng)絡(luò)狀態(tài)或服務(wù)器負(fù)載發(fā)生變化時(shí)，更新存儲(chǔ)在數(shù)據(jù)庫(kù)中相應(yīng)信息。

3 算法設(shè)計(jì)

3.1 SFC切鏈

基于文獻(xiàn)[4]，本文提出了一種SFC切鏈改進(jìn)算法，具體偽代碼如算法1所示。綜合每個(gè)域網(wǎng)絡(luò)的剩余資源量及不同類型VNF的資源需求量，“量力而為”地切分子鏈。

由于不同類型VNF的資源需求是不同的，先前的研究并沒有考慮到這個(gè)因素，本文基于先前文獻(xiàn)[5]的研究成果“基于特征選擇的VNF資源需求預(yù)測(cè)”完成SFC切鏈，將需求預(yù)測(cè)模塊集成到本文的控制器模塊中，有利于生成更合適的SFC切鏈方案。

具體根據(jù)式(1)進(jìn)行切鏈這里假設(shè)共有k個(gè)域網(wǎng)絡(luò)，它們是有序的，其中wgti表示第i個(gè)域可以提供的資源量，該值的大小也代表了該域網(wǎng)絡(luò)部署VNF的能力，Riprocess表示為實(shí)現(xiàn)多域網(wǎng)絡(luò)的負(fù)載均衡，該域網(wǎng)絡(luò)應(yīng)提供的資源量，Rdemand表示該SFC請(qǐng)求所需的總資源量。

Riprocess=wgti∑ki=1wgti×Rdemand

(1)

由于一個(gè)VNF僅能部署在一臺(tái)服務(wù)器上，且VNF是不可分的，因此是很難做到理想的多域網(wǎng)絡(luò)負(fù)載均衡，本文的目標(biāo)是實(shí)現(xiàn)多域網(wǎng)絡(luò)負(fù)載均衡的最大化。

基于VNF資源需求預(yù)測(cè)模塊，本文假設(shè)某個(gè)到達(dá)的長(zhǎng)度為n的SFC請(qǐng)求中各個(gè)VNF的資源需求可以表示為Rdemand={r1，r2，r3，…rn}， 為減少域間鏈路帶寬資源及時(shí)延，本文提出的切鏈算法綜合考慮各個(gè)域網(wǎng)絡(luò)的剩余資源及各個(gè)VNF的資源需求，將SFC切分為與域網(wǎng)絡(luò)數(shù)量相同的多個(gè)子鏈，從而確定分配到每個(gè)域網(wǎng)絡(luò)的SFC子鏈。首先對(duì)所有VNF的資源需求量進(jìn)行排序，接著遍歷每個(gè)VNF的資源需求量，若∑mj=1rjR1process， 則可以確定分配給第一個(gè)域網(wǎng)絡(luò)的子鏈為從第一個(gè)VNF到第m個(gè)VNF，以次類推，若最后存在VNF未被部署的情況，則將這些VNF分配給當(dāng)前負(fù)載率最小的域網(wǎng)絡(luò)，從而實(shí)現(xiàn)多域網(wǎng)絡(luò)負(fù)載均衡的最大化及SFC的合理切分。

算法1：改進(jìn)權(quán)重切鏈

輸入：域網(wǎng)絡(luò)數(shù)量NG， 各個(gè)域網(wǎng)絡(luò)服務(wù)器總數(shù)及總資源量G=(S，R)； SFC請(qǐng)求隊(duì)列及對(duì)應(yīng)的VNF數(shù)量和類型F=(f，num，type)； VNF類型數(shù)VNFType及不同類型VNF對(duì)應(yīng)的資源需求量rdcpu；

輸出：各個(gè)域網(wǎng)絡(luò)所需部署的SFC子鏈集合M；

(1)針對(duì)每一個(gè)到達(dá)的SFC請(qǐng)求執(zhí)行以下循環(huán)調(diào)度算法；

(2)對(duì)該SFC請(qǐng)求中的所有的VNF按資源需求進(jìn)行由小到大的排序，獲得集合VNFsSorted1；

(3)利用式(1)計(jì)算每個(gè)域網(wǎng)絡(luò)應(yīng)承擔(dān)的資源供給量；

(4)遍歷每個(gè)域網(wǎng)絡(luò)，并針對(duì)該域網(wǎng)絡(luò)是否有能力提供上述資源供給量進(jìn)行分類討論；

(5)若能的話，則遍歷VNFsSorted計(jì)算該域網(wǎng)絡(luò)應(yīng)承擔(dān)的VNF部署集合VNFDeploy；

(6)若不能的話，則根據(jù)每個(gè)域網(wǎng)絡(luò)的資源容量，盡最大努力承擔(dān)部署任務(wù)，獲得該域網(wǎng)絡(luò)的VNF部署集合VNFDeploy；

(7)針對(duì)(5)、(6)中的切鏈結(jié)果進(jìn)行反饋，若最后仍有VNF未被劃分，則將其劃分至剩余資源最多的域網(wǎng)絡(luò)，并更新切鏈結(jié)果M；

(8)返回最后結(jié)果，即各個(gè)域網(wǎng)絡(luò)所需部署的SFC子鏈集合M。

3.2 SFC子鏈部署

在單域網(wǎng)絡(luò)部署SFC子鏈時(shí)，本文提出了共同優(yōu)化節(jié)能和服務(wù)器負(fù)載均衡的部署策略，具體偽代碼如算法2所示，用戶可以在不同場(chǎng)景下根據(jù)需求進(jìn)行適當(dāng)?shù)恼{(diào)整。

當(dāng)SFC子鏈在第i個(gè)域中成功部署時(shí)定義兩個(gè)決策變量如下

xjn={1VNFFj成功部署在服務(wù)器vnSN0otherwise

(2)

ykj={1VNFFj屬于SFCfk0otherwise

(3)

如前所述，在網(wǎng)絡(luò)優(yōu)化中，節(jié)能和負(fù)載均衡是矛盾的，無法同時(shí)實(shí)現(xiàn)針對(duì)它們的最佳解決方案。因此，為了在兩者間實(shí)現(xiàn)理想的權(quán)衡，本文將能耗作為約束，將單域網(wǎng)絡(luò)負(fù)載均衡度作為目標(biāo)函數(shù)，假設(shè)某個(gè)SFC子鏈成功部署在域網(wǎng)絡(luò)Gi上，式(4)表示第n個(gè)服務(wù)器vnSN的能耗，式(5)表示激活服務(wù)器的額外能耗，式(6)表示單個(gè)服務(wù)器的CPU利用率，式(7)表示單個(gè)服務(wù)器消耗的CPU資源量，式(8)表示單域網(wǎng)絡(luò)的總能耗

en={enidlein idle modeenidle+enactivein active mode0in off mode

(4)

enactive=dln·enactivemax

(5)

dln=cpncpnmax

(6)

cpn=∑Fj∈F∑fk∈fxjn·ykj·rdkcpu

(7)

EC=∑nen

(8)

所以，優(yōu)化問題可表示為式(9)。其中，約束條件C1確保每個(gè)VNF僅部署在一個(gè)服務(wù)器節(jié)點(diǎn)上；約束條件C2確保服務(wù)器的CPU資源容量應(yīng)滿足待部署VNF的CPU需求；約束條件C3和C4是負(fù)載均衡度定義，用服務(wù)器CPU利用率標(biāo)準(zhǔn)差來量化負(fù)載均衡度(load balance degree，LBD)；約束條件C5是能耗約束，確?？偰芎男∮陂撝礒max， 此外，兩個(gè)決策變量應(yīng)滿足約束條件C6和C7中的完整性約束

minLBD

(9)

算法2：CCBP-adv算法

輸入：域網(wǎng)絡(luò)服務(wù)器數(shù)量及激活狀態(tài)Gi=(N，A)， 服務(wù)器最大容量Repo及最大能耗Emax， 各個(gè)服務(wù)器當(dāng)前資源利用率Ri， SFC子鏈中VNF數(shù)量totalVNF及各VNF的資源需求量SFCi， 總能耗閾值totalEmax；

輸出：SFC子鏈中各VNF的部署結(jié)果N；

(1)對(duì)該SFC子鏈中的所有VNF的按資源需求進(jìn)行由大到小的排序，獲得集合VNFsSorted2；

(2)針對(duì)VNFsSorted2執(zhí)行以下循環(huán)調(diào)度算法；

(3)過濾域網(wǎng)絡(luò)中可以滿足該VNF資源需求的服務(wù)器集合，獲得候選服務(wù)器集合CandidateServer；

(4)篩選候選服務(wù)器集合CandidateServer中資源容量最大的服務(wù)器作為當(dāng)前VNF的部署節(jié)點(diǎn)，更新部署結(jié)果N，并將該服務(wù)器從Gi中暫時(shí)刪除；

(5)獲得初次部署結(jié)果N1；

(6)計(jì)算此時(shí)各個(gè)服務(wù)器的資源利用率CpuRadio1， 負(fù)載均衡度Variance1及總能耗energyCom1；

(7)進(jìn)行第一次反饋部署，篩選部署失敗的VNF，重新部署到其它服務(wù)器上，獲得部署結(jié)果N2；

(8)計(jì)算此時(shí)各個(gè)服務(wù)器的資源利用率CpuRadio2， 負(fù)載均衡度Variance2及總能耗energyCom2；

(9)當(dāng)energyCom2>totalEmax時(shí)，進(jìn)行第二次反饋部署；

(10)定義最大反饋次數(shù)feedBackNum=round(totalVNF/2)；

(11)初始化反饋次數(shù)num；

(12)whileenergyCom2>totalEmax

(13) whilenum

(14) 獲取所有激活的服務(wù)器集合activatedServer

(15) 在activatedServer中尋找資源利用率最低的服務(wù)器節(jié)點(diǎn)server1；

(16) 在activatedServer中尋找資源利用率次低的服務(wù)器節(jié)點(diǎn)server2；

(17) 更新總能耗energyCom2；

(18) end

(19)end

(20)獲得最后部署結(jié)果N，并關(guān)閉所有空閑的服務(wù)器以降低能耗；

(21)計(jì)算此時(shí)各個(gè)服務(wù)器的資源利用率CpuRadio3， 負(fù)載均衡度Variance3及總能耗energyCom3；

(22)返回SFC子鏈中各VNF的部署結(jié)果N；

4 仿 真

4.1 仿真設(shè)計(jì)

仿真所用計(jì)算機(jī)配置為Intel Core i5 7300HQ (2.5 GHz)，8 GB內(nèi)存，所運(yùn)行的軟件環(huán)境為安裝在Windows 10上的MATLAB2015。仿真中設(shè)置的主要參數(shù)總結(jié)在表1中。為了使我們的模擬場(chǎng)景更通用，類似于文獻(xiàn)[17]，本文采用“單元”來量化資源消耗及能耗。

表1 仿真參數(shù)

針對(duì)表1中的仿真參數(shù)設(shè)置詳細(xì)說明如下。其中，NG表示多域網(wǎng)絡(luò)數(shù)為4，NSFC表示SFC的總數(shù)為50，Nvnf_type表示VNF類型數(shù)為6，分別是網(wǎng)絡(luò)地址轉(zhuǎn)化、防火墻、IDS、負(fù)載均衡器、廣域網(wǎng)優(yōu)化和流量監(jiān)控器，NS表示域網(wǎng)絡(luò)中的服務(wù)器數(shù)服從(5，10)的均勻分布，Nvnf表示SFC中的VNF數(shù)服從(3，7)的均勻分布，stati，j表示第i個(gè)域網(wǎng)絡(luò)中的第j個(gè)服務(wù)器的激活狀態(tài)，隨機(jī)生成0或1，rpi，jcpu表示第i個(gè)域網(wǎng)絡(luò)中的第j個(gè)服務(wù)器的CPU容量，其服從(3，5)的均勻分布，rdicpu表示第i種VNF類型的CPU資源需求量，其服從(0，0.4)的均勻分布，Eidle表示未激活服務(wù)器的能耗，Emax表示服務(wù)器的最大能耗，Emaxtotal表示整個(gè)網(wǎng)絡(luò)的能耗閾值。

4.2 評(píng)價(jià)指標(biāo)

本文選擇能耗、負(fù)載均衡度和時(shí)間開銷3個(gè)指標(biāo)來評(píng)估所提出的分布式跨域部署算法的性能。

(1)能耗：指所有服務(wù)器的總能耗，由式(8)計(jì)算；

(2)負(fù)載均衡度：指多域網(wǎng)絡(luò)的負(fù)載均衡度，由式(9)中的C3和C4計(jì)算，其值越小，表示負(fù)載均衡效果越好；

(3)時(shí)間開銷：指SFC跨域部署算法在多域網(wǎng)絡(luò)中部署一組SFC所消耗的時(shí)間。

4.3 仿真結(jié)果分析

4.3.1 SFC切鏈

圖3是不同切鏈算法在不同SFC數(shù)量下多域網(wǎng)絡(luò)負(fù)載均衡度的比較，其中，平均切鏈算法和權(quán)重切鏈算法是文獻(xiàn)[4]所提出的。由圖3可知，本文所提出的改進(jìn)權(quán)重切鏈算法可以產(chǎn)生更小的負(fù)載均衡度。如前所述，負(fù)載均衡度越小，則可以達(dá)到更好的負(fù)載均衡效果。這是因?yàn)楸疚乃岢龅母倪M(jìn)權(quán)重切鏈算法考慮到了不用類型VNF的資源需求是不同的，在切鏈過程中綜合考慮了每個(gè)域網(wǎng)絡(luò)的剩余資源量及不同類型VNF的資源需求量，基于先前文獻(xiàn)[5]的研究成果完成SFC切鏈，將需求預(yù)測(cè)模塊集成到本文的控制器模塊中，這樣有利于生成更合適的SFC切鏈方案。

圖3 多域網(wǎng)絡(luò)負(fù)載均衡度隨SFC數(shù)量變化對(duì)比

此外，不同切鏈算法在不同SFC數(shù)量下的多域網(wǎng)絡(luò)負(fù)載均衡度也是不同的。這是因?yàn)椴煌腟FC數(shù)量對(duì)應(yīng)了不同的VNF數(shù)量，這些VNF所對(duì)應(yīng)的資源需求也是不一樣的，而對(duì)于不同的SFC數(shù)量，各個(gè)域網(wǎng)絡(luò)的起始資源容量是一致的，這樣就會(huì)造成不同SFC數(shù)量部署后多域負(fù)載均衡度的起伏變化，但總體來看，本文所提出的改進(jìn)權(quán)重切鏈算法總是可以達(dá)到更好的負(fù)載均衡效果。

圖4是不同切鏈算法在不同VNF數(shù)量下多域網(wǎng)絡(luò)負(fù)載均衡度的比較。由圖4可知，本文所提出的改進(jìn)權(quán)重切鏈算法可以產(chǎn)生更小的負(fù)載均衡度，即本文所提出的改進(jìn)權(quán)重切鏈算法比其它兩種比較算法能夠達(dá)到更好的負(fù)載均衡效果。這同樣是因?yàn)楸疚乃岢龅母倪M(jìn)權(quán)重切鏈算法考慮到了不用類型VNF的資源需求是不同的。此外，不同切鏈算法在不同VNF數(shù)量下的多域網(wǎng)絡(luò)負(fù)載均衡度也是不同的。這是因?yàn)椴煌琕NF所對(duì)應(yīng)的資源需求是不同的，而對(duì)于不同數(shù)量的VNF，各個(gè)域網(wǎng)絡(luò)的起始資源容量是一致的，這樣就會(huì)造成不同數(shù)量VNF部署后多域負(fù)載均衡度的起伏變化，但總體來看，本文所提出的改進(jìn)權(quán)重切鏈算法總是可以達(dá)到更好的負(fù)載均衡效果。

圖4 多域網(wǎng)絡(luò)負(fù)載均衡度隨VNF數(shù)量變化對(duì)比

圖5是不同切鏈算法在不同VNF資源需求下多域網(wǎng)絡(luò)負(fù)載均衡度的比較，其中橫坐標(biāo)數(shù)字a表示VNF資源需求服從均勻分布(a，a+0.1)。由圖5可知，本文所提出的改進(jìn)權(quán)重切鏈算法可以產(chǎn)生更小的負(fù)載均衡度，即本文所提出的改進(jìn)權(quán)重切鏈算法比其它兩種比較算法能夠達(dá)到更好的負(fù)載均衡效果。這同樣是因?yàn)楸疚乃岢龅母倪M(jìn)權(quán)重切鏈算法考慮到了不用類型VNF的資源需求是不同的。此外，不同切鏈算法在不同VNF資源需求下的多域網(wǎng)絡(luò)負(fù)載均衡度是不同的，整體上呈現(xiàn)正相關(guān)趨勢(shì)。這是因?yàn)槊總€(gè)服務(wù)器節(jié)點(diǎn)具有不同的資源容量，并且每個(gè)VNF都部署在可以滿足不斷變化的資源需求的服務(wù)器節(jié)點(diǎn)上，而不是固定的服務(wù)器節(jié)點(diǎn)上。針對(duì)不斷增長(zhǎng)的VNF資源需求，滿足其資源需求的服務(wù)器節(jié)點(diǎn)越來越少，即可供選擇的部署位置越來越少，這樣很容易造成多域網(wǎng)絡(luò)負(fù)載均衡度的不斷增長(zhǎng)，但總體來看，本文所提出的改進(jìn)權(quán)重切鏈算法總是可以達(dá)到更好的負(fù)載均衡效果。

圖5 多域網(wǎng)絡(luò)負(fù)載均衡度隨VNF需求變化對(duì)比

4.3.2 SFC子鏈部署

圖6是不同部署算法在不同VNF數(shù)量下單域網(wǎng)絡(luò)能耗的比較，其中一個(gè)基準(zhǔn)算法是隨機(jī)部署算法(random deployment，RANP)，首次擬合部署(first-fit deployment，F(xiàn)FP)算法是文獻(xiàn)[18]提出的，基于改進(jìn)切鏈部署(chain-cut-based deployment advanced，CCBP-adv)算法是本文提出的SFC跨域部署算法。由圖6可知，本文所提出的CCBP-adv算法在大多數(shù)情況下均可以產(chǎn)生更少的能耗。這是因?yàn)楸疚乃岢龅腃CBP-adv算法設(shè)置了反饋部署，當(dāng)能耗超過閾值時(shí)，就會(huì)做出相應(yīng)地調(diào)整，旨在激活更小的服務(wù)器集合，在負(fù)載均衡度和能耗間做出合適的權(quán)衡。而對(duì)于FFP算法是將每個(gè)VNF部署在最先滿足其資源需求的服務(wù)器上。對(duì)于RANP算法，每個(gè)VNF都是隨機(jī)部署在一個(gè)服務(wù)器上的。與FFP算法相比，RANP算法可能占用更多的服務(wù)器來部署VNF，進(jìn)一步導(dǎo)致更多的能耗。

圖6 單域網(wǎng)絡(luò)能耗隨VNF數(shù)量變化對(duì)比

此外，隨著VNF數(shù)量的增加，本文所提出CCBP-adv算法所產(chǎn)生的單域網(wǎng)絡(luò)能耗整體上呈下降趨勢(shì)，這是因?yàn)楸疚乃O(shè)置的反饋部署次數(shù)與VNF數(shù)量正相關(guān)，隨著反饋次數(shù)的增加，會(huì)減少激活的服務(wù)器數(shù)量，從而降低總能耗；而對(duì)于FFP算法和RANP算法所產(chǎn)生的單域網(wǎng)絡(luò)能耗均呈上升趨勢(shì)，這是因?yàn)檫@兩種算法均未進(jìn)行反饋部署，隨著VNF數(shù)量的增加，必然會(huì)造成能耗的增加。

圖7是不同部署算法在不同VNF數(shù)量下單域網(wǎng)絡(luò)負(fù)載均衡度的比較。由圖7可知，本文所提出的CCBP-adv算法可以產(chǎn)生更小的負(fù)載均衡度，即CCBP-adv算法比其它兩個(gè)部署算法的負(fù)載均衡效果更好。這是因?yàn)楸疚乃岢龅腃CBP-adv算法是以單域網(wǎng)絡(luò)的負(fù)載均衡度為優(yōu)化目標(biāo)進(jìn)行部署，僅當(dāng)能耗超過閾值情況下，才會(huì)進(jìn)行相應(yīng)的部署調(diào)整。而對(duì)于FFP算法是將每個(gè)VNF部署在最先滿足其資源需求的服務(wù)器上，這樣會(huì)造成VNF集中部署，不利于負(fù)載均衡，大量的流量流向單一節(jié)點(diǎn)，極易造成網(wǎng)絡(luò)堵塞、數(shù)據(jù)包丟失，更有甚者造成網(wǎng)絡(luò)癱瘓的情況。對(duì)于RANP算法，每個(gè)VNF都是隨機(jī)部署在服務(wù)器上，同樣也不利于負(fù)載均衡。

圖7 單域網(wǎng)絡(luò)負(fù)載均衡度隨VNF數(shù)量變化對(duì)比

此外，隨著VNF資源需求的增加，3種部署算法產(chǎn)生的單域網(wǎng)絡(luò)負(fù)載均衡度起伏變化。這是因?yàn)殡S著VNF資源需求的不斷增加，滿足其資源需求的服務(wù)器節(jié)點(diǎn)數(shù)目不斷變化，這樣很容易造成單域網(wǎng)絡(luò)負(fù)載均衡度的起伏變化，但總體來看，本文所提出的CCBP-adv算法總是可以達(dá)到更好的負(fù)載均衡效果。

圖8是不同部署算法在不同VNF資源需求下單域網(wǎng)絡(luò)能耗的比較，其中橫坐標(biāo)數(shù)字a表示VNF資源需求服從均勻分布U(a，a+0.1)。由圖8可知，本文所提出的CCBP-adv算法可以產(chǎn)生更少的能耗。這是因?yàn)楸疚乃岢龅腃CBP-adv算法設(shè)置了反饋部署，當(dāng)能耗超過閾值情況下，會(huì)做出相應(yīng)的調(diào)整，旨在激活更小的服務(wù)器集合。而對(duì)于FFP算法是將每個(gè)VNF部署在最先滿足其資源需求的服務(wù)器上。對(duì)于RANP算法，每個(gè) VNF都是隨機(jī)部署在服務(wù)器上。與FFP算法相比，RANP算法可能占用更多的服務(wù)器來部署VNF，進(jìn)一步導(dǎo)致更多的能耗。

圖8 單域網(wǎng)絡(luò)能耗隨VNF需求變化對(duì)比

此外，隨著VNF資源需求的增加，3種部署算法產(chǎn)生的總能耗變大。這是因?yàn)殡S著VNF資源需求的增加，為了提供高效的服務(wù)，服務(wù)器需要更多的資源來實(shí)例化部署的VNF，進(jìn)一步導(dǎo)致更多的能耗。

圖9是不同部署算法在不同VNF資源需求下單域網(wǎng)絡(luò)負(fù)載均衡度的比較。由圖9可知，本文所提出的CCBP-adv算法可以產(chǎn)生更小的負(fù)載均衡度，即CCBP-adv算法比其它兩個(gè)部署算法的負(fù)載均衡效果更好。這是因?yàn)楸疚乃岢龅腃CBP-adv算法是以單域網(wǎng)絡(luò)的負(fù)載均衡度為優(yōu)化目標(biāo)進(jìn)行部署，僅當(dāng)能耗超過閾值時(shí)，才會(huì)進(jìn)行相應(yīng)的部署調(diào)整。而對(duì)于FFP算法是將每個(gè)VNF部署在最先滿足其資源需求的服務(wù)器上，這樣會(huì)造成VNF集中部署，不利于負(fù)載均衡，大量的流量流向單一節(jié)點(diǎn)，極易造成網(wǎng)絡(luò)堵塞，更有甚者造成網(wǎng)絡(luò)癱瘓的情況。對(duì)于RANP算法，每個(gè)VNF都是隨機(jī)部署在服務(wù)器上，同樣也不利于負(fù)載均衡。

圖9 單域網(wǎng)絡(luò)負(fù)載度隨VNF需求變化對(duì)比

此外，隨著VNF資源需求的增加，3種部署算法產(chǎn)生的單域網(wǎng)絡(luò)負(fù)載均衡度起伏變化。這是因?yàn)殡S著VNF資源需求的增加，滿足其資源需求的服務(wù)器節(jié)點(diǎn)數(shù)目不斷變化，這樣很容易造成單域網(wǎng)絡(luò)負(fù)載均衡度的起伏變化，但總體來看，本文所提出的CCBP-adv算法總是可以達(dá)到更好的負(fù)載均衡效果。

圖10是不同部署算法在不同VNF數(shù)量下時(shí)間成本的比較。由圖10可知，本文所提出的CCBP-adv算法可能需要更多的時(shí)間完成部署，但相較于FFP算法，時(shí)間成本平均僅增加了0.02 ms，這是可接受的。此外，隨著VNF數(shù)量的增加，3種部署算法產(chǎn)生的時(shí)間成本整體上呈上升趨勢(shì)。這是因?yàn)殡S著VNF數(shù)量的增加，需要執(zhí)行的循環(huán)調(diào)度算法次數(shù)也會(huì)相應(yīng)增加，即每個(gè)部署算法需要遍歷更多的服務(wù)器，搜索最優(yōu)部署服務(wù)器的時(shí)間會(huì)增加，由此造成了更多的部署時(shí)間。

圖10 時(shí)間成本隨VNF數(shù)量變化對(duì)比

綜上所述，從上述性能比較中可以得出結(jié)論，本文所提出的SFC跨域部署算法是有效的，并且在能耗和負(fù)載均衡度方面均優(yōu)于比較算法。

5 結(jié)束語

現(xiàn)有網(wǎng)絡(luò)虛擬化場(chǎng)景下的服務(wù)功能鏈部署算法的研究大部分集中在單域網(wǎng)絡(luò)，這些算法無法直接應(yīng)用于跨域部署場(chǎng)景下，同時(shí)現(xiàn)有的跨域部署算法都未考慮到不同類型的VNF資源需求是不同的，且優(yōu)化目標(biāo)單一。本文提出的SFC跨域部署算法很好地解決了多域網(wǎng)絡(luò)負(fù)載失衡及能耗過多的問題，基于先前的研究成果，將VNF資源需求預(yù)測(cè)模塊集成至該算法中，共同優(yōu)化負(fù)載均衡和能耗，靈活地在這兩者間進(jìn)行權(quán)衡，在最大化減少能耗的同時(shí)，獲得了更好的網(wǎng)絡(luò)負(fù)載均衡效果。