陽(yáng) 勇, 孟相如, 康巧燕, 趙文文

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,傳統(tǒng)網(wǎng)絡(luò)僵化的弊端逐漸凸顯,其軟件與硬件緊耦合的架構(gòu)越來越難以滿足用戶的需求[1-2]。在傳統(tǒng)網(wǎng)絡(luò)中,基于專有硬件的網(wǎng)絡(luò)功能導(dǎo)致諸多問題,比如網(wǎng)絡(luò)升級(jí)換代需要巨大開銷、可管理性差、可擴(kuò)展性差等[3-5]。網(wǎng)絡(luò)功能虛擬化(network function virtuali-zation,NFV)是解決上述問題的下一代網(wǎng)絡(luò)重要技術(shù)之一,其通過解耦硬件物理設(shè)備與運(yùn)行于其上的網(wǎng)絡(luò)功能,實(shí)現(xiàn)網(wǎng)絡(luò)功能的靈活部署、軟硬件的發(fā)展周期分離以及網(wǎng)絡(luò)功能的動(dòng)態(tài)擴(kuò)展[6-8]。利用NFV技術(shù),網(wǎng)絡(luò)功能可以當(dāng)成一個(gè)普通軟件的實(shí)例,根據(jù)需求動(dòng)態(tài)部署在網(wǎng)絡(luò)中不同位置而無需重新安裝新的硬件,在增加靈活性的同時(shí)極大地降低了運(yùn)營(yíng)商的成本[9-11]。

在NFV環(huán)境的網(wǎng)絡(luò)中,服務(wù)功能鏈(service function chain,SFC)部署是實(shí)現(xiàn)網(wǎng)絡(luò)業(yè)務(wù)的基礎(chǔ),部署過程中的資源開銷很大程度上決定了運(yùn)營(yíng)商的成本,部署后的可靠性嚴(yán)重影響網(wǎng)絡(luò)功能的穩(wěn)定性,進(jìn)而影響對(duì)用戶的服務(wù)質(zhì)量(quality of service,QoS),因此SFC部署問題得到了許多學(xué)者的關(guān)注[12-29]。文獻(xiàn)[12]在虛擬網(wǎng)絡(luò)功能(virtual network function,VNF)部署階段,利用PageRank算法進(jìn)行節(jié)點(diǎn)排序,在保證端到端時(shí)延的同時(shí)提高了SFC的可靠性,但未考慮資源開銷的優(yōu)化。文獻(xiàn)[13-16]通過備份的方式提高SFC的可靠性,其中文獻(xiàn)[13]對(duì)VNF進(jìn)行聯(lián)合備份,將SFC部署問題構(gòu)建成整數(shù)線性規(guī)劃模型,在優(yōu)先滿足SFC可靠性的同時(shí)優(yōu)化了資源配置;文獻(xiàn)[14]對(duì)鏈路進(jìn)行備份,基于路徑分割對(duì)虛擬鏈路進(jìn)行多路徑映射,以保證鏈路的可靠性。但此類方法因?yàn)槿哂鄠浞菰黾恿诉\(yùn)營(yíng)商的成本。文獻(xiàn)[17-21]提出迭代算法進(jìn)行VNF部署,其中文獻(xiàn)[17]采用基于改進(jìn)遺傳模擬退火算法的VNF部署策略優(yōu)化了端到端時(shí)延;文獻(xiàn)[18]在對(duì)SFC構(gòu)建與部署進(jìn)行雙層編碼的基礎(chǔ)上,利用改進(jìn)遺傳粒子群算法優(yōu)化了請(qǐng)求接受率與資源開銷;文獻(xiàn)[19]提出改進(jìn)遺傳算法進(jìn)行VNF部署,并結(jié)合物理節(jié)點(diǎn)保護(hù)機(jī)制,提高了底層網(wǎng)絡(luò)資源利用率和SFC的生存性。但這此類方法都需通過反復(fù)迭代才能求解,難以實(shí)現(xiàn)VNF的快速部署。文獻(xiàn)[22]采用三階段遞進(jìn)的方式部署VNF,首先將VNF部署到可靠性最高的節(jié)點(diǎn)上,然后調(diào)整部署方案實(shí)現(xiàn)對(duì)負(fù)載的優(yōu)化,最后調(diào)整部署方案縮短大帶寬虛擬鏈路部署到底層網(wǎng)絡(luò)后的物理長(zhǎng)度,該方法提高了SFC的可靠性,但未考慮端到端時(shí)延。文獻(xiàn)[23-27]采用機(jī)器學(xué)習(xí)算法進(jìn)行VNF部署,對(duì)SFC的性能有較大優(yōu)化,但依賴足夠多的準(zhǔn)確數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練。文獻(xiàn)[28]提出可以采用聚合的方式部署VNF,但未進(jìn)一步研究具體的聚合方法。文獻(xiàn)[29]根據(jù)功能約束與資源約束聚合VNF,未考慮VNF對(duì)鏈路流量的影響。

針對(duì)上述問題,本文提出基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署(reliable service function chain deployment based on traffic optimization,TO-RSFCD)方法。首先根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合處理,使聚合的VNF部署到底層網(wǎng)絡(luò)后大帶寬虛擬鏈路上的流量成為服務(wù)器的內(nèi)部流量,達(dá)到降低鏈路開銷的目的。然后綜合考慮物理節(jié)點(diǎn)的可靠性、綜合時(shí)延以及拓?fù)鋵傩?利用離差最大化的多指標(biāo)決策算法對(duì)滿足資源需求的物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)并排序,評(píng)價(jià)過程中賦予對(duì)排序作用大的評(píng)價(jià)指標(biāo)更高權(quán)重。同時(shí)通過鏈路約束降低流量乒乓效應(yīng),依次將聚合后的VNF部署在排序最靠前的節(jié)點(diǎn)上。最后采用k-最短路徑算法完成虛擬鏈路的部署。實(shí)驗(yàn)表明,TO-RSFCD方法在保證SFC可靠性的基礎(chǔ)上,對(duì)映射成功率、平均收益開銷比、端到端時(shí)延以及帶寬開銷進(jìn)行了較大優(yōu)化。本文的主要貢獻(xiàn)有:

(1) 根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合,使聚合的VNF部署到底層網(wǎng)絡(luò)后大帶寬需求鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,優(yōu)化了資源開銷；

(2) 提出節(jié)點(diǎn)綜合時(shí)延和拓?fù)渚徒戎笜?biāo),前者量化節(jié)點(diǎn)及其相鄰鏈路所產(chǎn)生的時(shí)延,后者量化節(jié)點(diǎn)與源、目的端點(diǎn)之間最短路徑的拓?fù)鋵傩?實(shí)現(xiàn)了算法對(duì)底層網(wǎng)絡(luò)的拓?fù)渑c時(shí)延感知；

(3) 采用離差最大化多指標(biāo)決策算法對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià),對(duì)排序作用大的評(píng)價(jià)指標(biāo)賦予更高權(quán)重,實(shí)現(xiàn)了權(quán)重的自適應(yīng)設(shè)定;

(4) VNF部署過程中設(shè)置鏈路約束條件,降低了流量的乒乓效應(yīng)。

1 網(wǎng)絡(luò)模型及問題描述

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

物理網(wǎng)絡(luò)用一個(gè)加權(quán)無向圖G=(N,E)表示,其中N為物理節(jié)點(diǎn)的集合,E為物理鏈路的集合。每個(gè)物理節(jié)點(diǎn)上附著一至多個(gè)服務(wù)器,能夠用來實(shí)例化VNF。節(jié)點(diǎn)ns∈N的剩余可用計(jì)算資源為Cal(ns),可用存儲(chǔ)資源為Mem(ns),可用轉(zhuǎn)發(fā)資源為For(ns),實(shí)例化VNF后產(chǎn)生的時(shí)延為d(ns),可靠性為r(ns)。鏈路es∈E的剩余可用帶寬為b(ns),時(shí)延為d(es)。

SFC請(qǐng)求用一個(gè)七元組(I,O,D,T,R,V,L)表示,其中I為源端點(diǎn),O為目的端點(diǎn),D為SFC的最大允許時(shí)延,T為SFC的生存時(shí)間,R為SFC的可靠性要求下限,V為組成SFC的VNF集合,L為組成SFC的虛擬鏈路集合。集合V={v1,v2,…,vn}中的元素vi表示SFC的第i個(gè)VNF,其計(jì)算資源需求為Cal(vi),存儲(chǔ)資源需求為Mem(vi),轉(zhuǎn)發(fā)資源需求為For(vi),帶寬改變因子為η(vi),其中帶寬改變因子定義為VNF流量的流出帶寬與流入帶寬之比。集合L={l0,l1,…,ln}中的元素li為vi到vi+1之間的虛擬鏈路。當(dāng)i=0時(shí),li為源端點(diǎn)I到v1之間的虛擬鏈路,當(dāng)i=n時(shí),li為vn到目的端點(diǎn)O之間的虛擬鏈路。用b(li)表示li的帶寬需求,則b(li)的計(jì)算公式為

(1)

1.2 優(yōu)化目標(biāo)

用xi, j表示vi是否部署到物理節(jié)點(diǎn)nj上,yi, j表示li部署到底層網(wǎng)絡(luò)后是否經(jīng)過物理鏈路ej。令集合φ=(Cal, Mem, For),k∈φ表示計(jì)算、存儲(chǔ)、轉(zhuǎn)發(fā)資源中任意一種資源。則SFC部署到底層網(wǎng)絡(luò)后,資源開銷的計(jì)算公式為

(2)

式(2)的第一部分表示節(jié)點(diǎn)的計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源開銷,第二部分表示鏈路的帶寬開銷。本文旨在保證SFC可靠性和時(shí)延要求的基礎(chǔ)上,對(duì)資源開銷進(jìn)行優(yōu)化,優(yōu)化目標(biāo)為

Goal=min(Cost)

(3)

SFC的部署過程中約束條件如下:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(4)表示每一個(gè)VNF都能在底層網(wǎng)絡(luò)部署,但只能部署到一個(gè)物理節(jié)點(diǎn)上。式(5)表示每一條虛擬鏈路都能在底層網(wǎng)絡(luò)部署,且能部署在一條或多條物理鏈路上。式(6)表示每一條物理鏈路被同一條SFC的虛擬鏈路最多部署一次,這是為了防止乒乓效應(yīng),其中乒乓效應(yīng)指流量在兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間來回傳輸。式(7)表示VNF的任意一種資源需求都不能超過所部署節(jié)點(diǎn)的剩余可用資源。式(8)表示虛擬鏈路的帶寬需求不能超過所部署鏈路的剩余可用帶寬。式(9)表示SFC的時(shí)延不能超過所允許的最大時(shí)延,不等式的左邊第一部分表示節(jié)點(diǎn)產(chǎn)生的時(shí)延,第二部分表示鏈路時(shí)延。式(10)表示SFC必須滿足可靠性要求,不等式的左邊表示SFC的可靠性。本文只考慮服務(wù)器的可靠性,當(dāng)節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí),由于其上附著的服務(wù)器沒有被SFC使用,所以其可靠性不計(jì)入SFC的可靠性中。

1.3 問題描述

從資源開銷的組成部分分析,由于每個(gè)VNF只能部署在一個(gè)物理節(jié)點(diǎn)上,所以計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源的開銷與需求相等,無法對(duì)其進(jìn)行優(yōu)化。而每一條虛擬鏈路能夠部署在一條或多條物理鏈路上,所以帶寬開銷必定大于或等于帶寬需求,能夠?qū)ζ溥M(jìn)行優(yōu)化。圖1是同一SFC在相同物理網(wǎng)絡(luò)拓?fù)湎碌?種不同部署方法,箭頭處數(shù)字代表初始帶寬,VNF處數(shù)字代表帶寬改變因子。

圖1 不同VNF部署方法對(duì)比Fig.1 Comparison of different VNF deployment methods

與方法1相比,方法2通過鏈路約束避免了流量在節(jié)點(diǎn)B與節(jié)點(diǎn)H之間來回傳輸(即乒乓效應(yīng)),方法3在避免乒乓效應(yīng)的基礎(chǔ)上,將某些VNF進(jìn)行了聚合部署。經(jīng)計(jì)算,方法1的帶寬開銷為583.84 M/s,方法2的帶寬開銷為497.44 M/s,方法3的帶寬開銷為367.84 M/s,方法2和方法3相較于方法1對(duì)帶寬開銷進(jìn)行了較大優(yōu)化。

假設(shè)每個(gè)物理節(jié)點(diǎn)的可靠性為0.95,由于方法3中只在兩個(gè)節(jié)點(diǎn)上部署VNF,SFC的可靠性為0.952=0.902 5。而另外兩種方法在4個(gè)節(jié)點(diǎn)上部署VNF,SFC的可靠性為0.954=0.814 5。對(duì)比可見,方法3的SFC可靠性也得到了提高。因此,在部署SFC時(shí),以一定規(guī)則對(duì)VNF進(jìn)行聚合處理,并盡可能減少流量的乒乓效應(yīng),則能在提高SFC可靠性的同時(shí)達(dá)到優(yōu)化帶寬開銷的目的。

2 基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署方法設(shè)計(jì)

2.1 基于帶寬需求變化的VNF聚合算法

NFV環(huán)境中存在3類VNF,第1類是帶寬改變因子大于1的VNF,比如數(shù)據(jù)加密、編碼等,經(jīng)此類VNF處理后,SFC的帶寬會(huì)增大。第2類是帶寬改變因子等于1的VNF,比如QoS監(jiān)視、入侵檢測(cè)等,經(jīng)此類VNF處理后,SFC的帶寬不會(huì)發(fā)生變化。第3類是帶寬改變因子小于1的VNF,比如防火墻、數(shù)據(jù)解密等,經(jīng)此類VNF處理后,SFC的帶寬會(huì)減小。為達(dá)到優(yōu)化帶寬開銷的目的,就必須在保證VNF編排順序不變的前提下,將帶寬改變因子小于1的VNF在物理網(wǎng)絡(luò)中靠前部署,帶寬改變因子大于1的VNF靠后部署。

本算法的中心思想是針對(duì)所有帶寬改變因子大于1的VNF,將編排在其后但在下一個(gè)帶寬改變因子大于1的VNF之前的所有VNF與其進(jìn)行聚合,聚合的VNF將部署到同一個(gè)物理節(jié)點(diǎn)上,達(dá)到將帶寬改變因子小于1的VNF靠前部署的目的,并使大帶寬需求鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,如圖2所示。

圖2 基于帶寬需求變化的VNF聚合算法案例Fig.2 A case study of VNF polymerization algorithm based on bandwidth demand changes

以SFC1為例,v1和v4是帶寬改變因子大于1的VNF,v2和v3編排在v1之后,v4之前,所以將v2和v3與v1進(jìn)行聚合。聚合的VNF將部署到同一個(gè)物理節(jié)點(diǎn)上,其中流入該物理節(jié)點(diǎn)流量的帶寬為SFC1的初始帶寬,流出該物理節(jié)點(diǎn)流量的帶寬為經(jīng)v1、v2和v3依次處理過的帶寬,是一個(gè)較小的值。而僅經(jīng)v1處理過的大帶寬流量成為了該物理節(jié)點(diǎn)上所附著服務(wù)器的內(nèi)部流量。SFC2和SFC3的聚合規(guī)則同理。算法的具體步驟如下所示。

算法 1 基于帶寬需求變化的VNF聚合算法輸入: VNF集合V,V中元素所對(duì)應(yīng)的帶寬改變因子集合η輸出: 聚合后的VNF集合V′1 for V中每一個(gè)元素vi 2 if η(vi)>13 將vi的編排位置放入集合Temp中;4 end if5 end for6 if η(vi)≤17 將V中前Temp-1個(gè)VNF進(jìn)行聚合,并賦值給v′1; 8 for i=2: |Temp|9 將V中第Temp(i-1)到Temp(i)-1個(gè)VNF進(jìn)行聚合,并賦值給v′i;10 end for11 將V中第Temp(i)及之后的所有VNF進(jìn)行聚合,并賦值給v′ i+1;12 else13 for i=|Temp|-114 將V中第Temp(i)到Temp(i+1)-1個(gè)VNF進(jìn)行聚合,并賦值給v′i;15 end for16 將V中第Temp(i+1)及之后的所有VNF進(jìn)行聚合,并賦值給v′ i+1;17 end if18 return V′

聚合后VNF的計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源需求等于聚合前各VNF的同類資源需求之和,帶寬改變因子等于聚合前各VNF的帶寬改變因子之積。

2.2 基于離差最大化的VNF部署算法

對(duì)SFC中VNF進(jìn)行聚合處理后,再對(duì)聚合的VNF進(jìn)行部署。本算法的中心思想是在對(duì)底層網(wǎng)路進(jìn)行拓?fù)渑c時(shí)延感知的基礎(chǔ)上,利用離差最大化的多目標(biāo)決策算法對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)并排序,每次按照編排順序部署聚合后的VNF時(shí),依據(jù)資源約束與鏈路約束篩選物理節(jié)點(diǎn),再?gòu)暮Y選出的物理節(jié)點(diǎn)中選擇排序靠前的部署VNF。對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)的指標(biāo)有節(jié)點(diǎn)可靠性、節(jié)點(diǎn)綜合時(shí)延、節(jié)點(diǎn)拓?fù)渚徒群凸?jié)點(diǎn)源端距。

節(jié)點(diǎn)可靠性采用固有可用度[30]進(jìn)行表示,其定義為

(11)

式中:MTBF表示節(jié)點(diǎn)的平均故障間隔；MTTR表示平均修復(fù)時(shí)間。節(jié)點(diǎn)可靠性越高,越有利于靠前排序。

定義 1節(jié)點(diǎn)綜合時(shí)延是對(duì)節(jié)點(diǎn)及其相關(guān)聯(lián)鏈路所產(chǎn)生時(shí)延的綜合度量,能反映選取該節(jié)點(diǎn)部署VNF后對(duì)SFC時(shí)延的影響,是算法實(shí)現(xiàn)對(duì)底層網(wǎng)絡(luò)時(shí)延感知的關(guān)鍵指標(biāo),其計(jì)算公式為

(12)

式中:d(ns)表示節(jié)點(diǎn)ns所產(chǎn)生的時(shí)延,包括排隊(duì)時(shí)延、處理時(shí)延與發(fā)送時(shí)延；E(ns)表示與ns相關(guān)聯(lián)的物理鏈路集合,|E(ns)|表示集合E(ns)中元素的個(gè)數(shù)；d(es)表示鏈路es所產(chǎn)生的時(shí)延,包括傳播時(shí)延；α與β為權(quán)重因子,本文中均設(shè)為1。節(jié)點(diǎn)的綜合時(shí)延越小,越有利于靠前排序。

定義 2節(jié)點(diǎn)拓?fù)渚徒缺硎竟?jié)點(diǎn)與源目端點(diǎn)之間最短路徑的拓?fù)渚o密程度,能反映選取該節(jié)點(diǎn)部署VNF后對(duì)SFC物理長(zhǎng)度的影響,是算法實(shí)現(xiàn)對(duì)底層網(wǎng)絡(luò)拓?fù)涓兄年P(guān)鍵指標(biāo),其計(jì)算公式為

(13)

式中:TD(ns)表示ns的度數(shù),數(shù)值上等于|E(ns)|；hop(ns,I)表示ns與源端點(diǎn)之間的最短跳數(shù)；hop(ns,O)表示ns與目的端點(diǎn)之間的最短跳數(shù)。采用節(jié)點(diǎn)拓?fù)渚徒茸鳛樵u(píng)價(jià)指標(biāo)能縮短SFC的物理長(zhǎng)度,節(jié)點(diǎn)的拓?fù)渚徒仍酱?越有利于靠前排序。

節(jié)點(diǎn)源端距表示節(jié)點(diǎn)與源端點(diǎn)之間的最短跳數(shù),即hop(ns,I)。采用節(jié)點(diǎn)源端距作為評(píng)價(jià)指標(biāo)能實(shí)現(xiàn)帶寬改變因子小于1的VNF盡可能靠前部署,節(jié)點(diǎn)源端距越小,越有利于靠前排序。

采用離差最大化的多指標(biāo)決策算法計(jì)算每個(gè)物理節(jié)點(diǎn)ns的評(píng)價(jià)度S(ns),并利用S(ns)對(duì)各物理節(jié)點(diǎn)進(jìn)行排序,然后依據(jù)VNF編排順序?qū)Ω鱒NF進(jìn)行部署。離差最大化的多指標(biāo)決策算法步驟如下。

步驟 1根據(jù)評(píng)價(jià)指標(biāo)類型構(gòu)造規(guī)范化決策矩陣(Zij)m×n。假設(shè)有m個(gè)評(píng)價(jià)對(duì)象,表示不同的物理節(jié)點(diǎn),每個(gè)物理節(jié)點(diǎn)有n個(gè)評(píng)價(jià)指標(biāo),記第i個(gè)物理節(jié)點(diǎn)的第j個(gè)評(píng)價(jià)指標(biāo)值為aij。值越大越有利于節(jié)點(diǎn)靠前排序的評(píng)價(jià)指標(biāo)為效益型評(píng)價(jià)指標(biāo),如節(jié)點(diǎn)可靠性與拓?fù)渚徒?值越小越有利于節(jié)點(diǎn)靠前排序的評(píng)價(jià)指標(biāo)為成本型評(píng)價(jià)指標(biāo),如節(jié)點(diǎn)綜合時(shí)延與源端距。效益型評(píng)價(jià)指標(biāo)在決策矩陣中的值為

(14)

成本型評(píng)價(jià)指標(biāo)在決策矩陣中的值為

(15)

式中:max(a*j)表示第j個(gè)評(píng)價(jià)指標(biāo)的最大值；min(a*j)表示第j個(gè)評(píng)價(jià)指標(biāo)的最小值。

步驟 2根據(jù)離差最大化方法計(jì)算各評(píng)價(jià)指標(biāo)的最優(yōu)加權(quán)向量W*。設(shè)評(píng)價(jià)指標(biāo)的加權(quán)向量為W=[w1,w2,…,wn],則在W作用下規(guī)范化決策矩陣為

(16)

如果某評(píng)價(jià)指標(biāo)的值對(duì)所有物理節(jié)點(diǎn)均無差異,則其對(duì)節(jié)點(diǎn)排序不起作用,應(yīng)將其權(quán)重設(shè)為0。反之若某評(píng)價(jià)指標(biāo)的值對(duì)所有物理節(jié)點(diǎn)有較大差異,則其對(duì)節(jié)點(diǎn)排序起重要作用,應(yīng)將其權(quán)重設(shè)為較大值。在當(dāng)前權(quán)重下,第i個(gè)物理節(jié)點(diǎn)的第j個(gè)評(píng)價(jià)指標(biāo)與其他物理節(jié)點(diǎn)的離差為dispij(w),計(jì)算方式為

(17)

第j個(gè)評(píng)價(jià)指標(biāo)的總離差為dispj(w),其表示就第j個(gè)評(píng)價(jià)指標(biāo)而言,所有物理節(jié)點(diǎn)與其他物理節(jié)點(diǎn)的總離差,計(jì)算方式為

(18)

據(jù)前面分析,加權(quán)向量W的選擇應(yīng)使所有評(píng)價(jià)指標(biāo)的總離差最大,因此構(gòu)造目標(biāo)函數(shù)為

(19)

其中,約束條件為

(20)

(21)

步驟 3根據(jù)最優(yōu)加權(quán)向量作用下的決策矩陣計(jì)算各物理節(jié)點(diǎn)的綜合評(píng)價(jià)度S(ns)。最優(yōu)加權(quán)向量作用下的決策矩陣為

(22)

第i個(gè)物理節(jié)點(diǎn)的綜合評(píng)價(jià)度為

(23)

算法 2 基于離差最大化的VNF部署算法輸入: 經(jīng)VNF聚合處理后的SFC=(I,O,D,T,R,V′,L′),物理網(wǎng)絡(luò)G=(N,E)輸出: VNF_Embedding_List1 for N中每一個(gè)物理節(jié)點(diǎn)ns2 利用離差最大化多指標(biāo)決策算法計(jì)算綜合評(píng)價(jià)度S(ns);3 end for4 利用S(ns)對(duì)N中物理節(jié)點(diǎn)進(jìn)行排序;5 for V′中每一個(gè)v′i6 從N中篩選出滿足其計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源需求的節(jié)點(diǎn)集合Ф(v′i);7 if Ф(v′i)為空8 return VNF_EMBEDDING_FAILED9 else10 從Ф(v′i)刪除滿足hop(ns, O)>hop(ns(vi-1′), O)的物理節(jié)點(diǎn);11 if Ф(v′i)為空12 return VNF_EMBEDDING_FAILED13 else14 將v′i部署到Ф(v′i)中排序最靠前的物理節(jié)點(diǎn)上,并將映射關(guān)系存入VNF_Embedding_List中;15 更新各物理節(jié)點(diǎn)剩余資源;16 end if17 end if18 end for19 計(jì)算SFC的可靠性;20 if SFC的可靠性不滿足可靠性要求下限R21 return VNF_EMBEDDING_FAILED22 else 23 return VNF_Embedding_List34 end if

2.3 虛擬鏈路部署

VNF部署完畢后,首先在物理拓?fù)渲袆h除不滿足帶寬需求的物理鏈路,然后利用k-最短路徑算法在剩余拓?fù)渲胁渴鹛摂M鏈路,最后根據(jù)VNF所部署物理節(jié)點(diǎn)產(chǎn)生的時(shí)延與虛擬鏈路所部署物理鏈路的時(shí)延計(jì)算出SFC的端到端時(shí)延,若該時(shí)延小于最大允許時(shí)延D,則SFC部署成功,否則部署失敗。

在VNF部署階段,TO-RSFCD對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)的時(shí)間復(fù)雜度為O(|N|);在鏈路部署階段,k-最短路徑算法的時(shí)間復(fù)雜度為O(k|N|(|E|+|N|lg|E|))。

3 算法性能評(píng)估與分析

為評(píng)估本文所提方法的性能,利用Matlab對(duì)其進(jìn)行仿真并與基于QoS保障的服務(wù)功能鏈動(dòng)態(tài)部署算法[12]、可靠感知與資源優(yōu)化的虛擬網(wǎng)絡(luò)功能部署方法[22]進(jìn)行對(duì)比。同時(shí),為驗(yàn)證VNF聚合部署的優(yōu)勢(shì),設(shè)置了一種本文所提方法的對(duì)照方法,該方法除不進(jìn)行VNF聚合外,所有過程皆與本文所提方法保持一致。

3.1 方法評(píng)價(jià)指標(biāo)

本文采用請(qǐng)求接受率、平均帶寬開銷、SFC平均可靠性、SFC平均端到端時(shí)延以及長(zhǎng)期平均收益開銷比來衡量算法的性能。

(1) 請(qǐng)求接受率ωaccept定義為

(24)

式中:NUMsuc(T)表示T時(shí)間內(nèi)成功部署的SFC數(shù)目;NUMv(T)表示T時(shí)間內(nèi)到達(dá)的SFC請(qǐng)求總數(shù)目。

(2) 平均帶寬開銷Bcost_ave定義為

(25)

式中:Bcostsg是成功部署的SFCg所消耗的帶寬。

(3) SFCg的可靠性為

(26)

則SFC的平均可靠性定義為

(27)

(4) SFCg的端到端時(shí)延為

(28)

則SFC平均端到端時(shí)延定義為

(29)

(5) 在t時(shí)刻,成功部署一個(gè)SFCg的收益為

(30)

物理網(wǎng)絡(luò)的資源開銷為

(31)

式中:α,β,γ,χ分別表示收益和開銷中計(jì)算、存儲(chǔ)、轉(zhuǎn)發(fā)與帶寬資源的比重,本文中均設(shè)為1。則長(zhǎng)期平均收益開銷比定義為

(32)

3.2 仿真環(huán)境設(shè)置

仿真環(huán)境中物理網(wǎng)絡(luò)是由100個(gè)節(jié)點(diǎn)和525條鏈路組成的連通圖,相當(dāng)于一個(gè)中型網(wǎng)絡(luò)拓?fù)?SFC請(qǐng)求服從到達(dá)率λ=0.05的泊松分布,生存時(shí)間服從μ=1 000的指數(shù)分布,仿真時(shí)間為50 000個(gè)單位。其余各項(xiàng)參數(shù)如表1所示。

表1 仿真參數(shù)Table 1 Simulation parameters

3.3 實(shí)驗(yàn)結(jié)果分析

為避免隨機(jī)因素影響,仿真實(shí)驗(yàn)共進(jìn)行10次,取每次結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果,如圖3～圖8所示。

圖3 重復(fù)映射鏈路條數(shù)Fig.3 Number of links that are mapped repeatedly

從圖3可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的鏈路重復(fù)映射條數(shù)小于另外兩種方法,即乒乓效應(yīng)低于另外兩種方法。這是因?yàn)樵诓渴疬^程中這兩種方法進(jìn)了鏈路約束,有效降低了同一條SFC上的不同虛擬鏈路映射到相同物理鏈路上。而另外兩種方法未考慮乒乓效應(yīng),所以鏈路重復(fù)映射條數(shù)較高。

從圖4可以發(fā)現(xiàn),本文所提方法的收益開銷比保持在0.75以上,明顯優(yōu)于其他3種方法。這是因?yàn)楸疚乃岱椒ǜ鶕?jù)帶寬需求變化對(duì)VNF進(jìn)行聚合處理,并且在部署時(shí)利用鏈路約束降低了乒乓效應(yīng),有效降低了帶寬開銷,從而提升了長(zhǎng)期平均收益開銷比。本文對(duì)照方法未進(jìn)行VNF聚合,但在部署時(shí)利用鏈路約束降低了乒乓效應(yīng),所以其長(zhǎng)期收益開銷比大于另外兩種方法。文獻(xiàn)[12]和文獻(xiàn)[22]所提方法未進(jìn)行VNF聚合,也未考慮乒乓效應(yīng),所以長(zhǎng)期收益開銷比較低。

圖4 長(zhǎng)期平均收益開銷比Fig.4 Long-term average revenue overhead ratio

從圖5可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的映射成功率都在0.95以上,優(yōu)于另外兩種方法,這是因?yàn)檫@兩種方法在進(jìn)行部署時(shí)考慮了物理節(jié)點(diǎn)的綜合時(shí)延、可靠性以及拓?fù)鋵傩?使得部署后的SFC能較好地滿足時(shí)延與可靠性約束,所以映射成功功率較高。而文獻(xiàn)[12]所提方法未考慮鏈路的時(shí)延,文獻(xiàn)[22]所提方法對(duì)節(jié)點(diǎn)和鏈路的時(shí)延均未作考慮,使得部署后的SFC未能很好滿足時(shí)延約束,所以映射成功率較低。

圖5 映射成功率Fig.5 Mapping success rate

從圖6可以發(fā)現(xiàn),本文所提方法的SFC平均可靠性最高,保持在0.91以上,這是因?yàn)檫M(jìn)行了VNF聚合后,多個(gè)VNF部署到同一個(gè)物理節(jié)點(diǎn)上,并采用離差最大化的多指標(biāo)決策方法賦予對(duì)排序作用大的評(píng)價(jià)指標(biāo)更高權(quán)重,有效地提高了SFC的可靠性。文獻(xiàn)[22]所提方法的SFC平均可靠性保持在0.9以上,僅次于本文所提方法,這是因?yàn)樵摲椒ㄔ诘谝浑A段將VNF都部署在可靠性最高的物理節(jié)點(diǎn)上,后兩個(gè)階段只是在此基礎(chǔ)上作調(diào)整,所以能保持較高的可靠性。本文對(duì)照方法在部署階段考慮了拓?fù)鋵傩?、?jié)點(diǎn)綜合時(shí)延與可靠性,文獻(xiàn)[12]所提方法考慮了拓?fù)鋵傩耘c節(jié)點(diǎn)可靠性,均未對(duì)VNF進(jìn)行聚合,所以其SFC可靠性較低,但由于本文對(duì)照方法采用離差最大化多指標(biāo)決策方法,所以在可靠性方面還有一定優(yōu)勢(shì)。

圖6 SFC平均可靠性Fig.6 Average reliability of SFC

從圖7可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的SFC平均端到端時(shí)延低于另外兩種方法,分別保持在45 ms和50 ms左右,這是因?yàn)檫@兩種方法在部署階段既把物理節(jié)點(diǎn)綜合時(shí)延作為評(píng)價(jià)指標(biāo),還利用鏈路約束降低了乒乓效應(yīng),所以能獲得更低的節(jié)點(diǎn)與鏈路時(shí)延。而文獻(xiàn)[12]所提方法未考慮鏈路時(shí)延,文獻(xiàn)[22]所提方法對(duì)節(jié)點(diǎn)時(shí)延與鏈路時(shí)延均未考慮,所以SFC平均端到端時(shí)延較高。

圖7 SFC平均端到端時(shí)延Fig.7 Average end to end delay of SFC

圖8 平均帶寬開銷Fig.8 Average bandwidth overhead

從圖8可以發(fā)現(xiàn),本文所提方法的帶寬開銷低于另外3種方法,保持在500 M/s左右,這是因?yàn)楸疚乃岱椒雀鶕?jù)帶寬需求對(duì)VNF進(jìn)行了聚合處理,在部署時(shí)還利用鏈路約束降低了乒乓效應(yīng),所以獲得了較低的帶寬開銷。而本文對(duì)照算法未進(jìn)行VNF聚合處理,但降低了乒乓效應(yīng),所以帶寬開銷僅高于本文所提方法。另外兩種方法未進(jìn)行VNF聚合,也未考慮乒乓效應(yīng),所以平均帶寬開銷較高。

4 結(jié) 論

針對(duì)NFV環(huán)境中服務(wù)功能鏈的部署問題,本文提出一種基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署方法。首先根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合處理,使大帶寬虛擬鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,有效降低了帶寬開銷,提升了收益開銷比。然后綜合考慮節(jié)點(diǎn)可靠性、綜合時(shí)延以及拓?fù)鋵傩?使用離差最大化的多指標(biāo)決策算法對(duì)滿足聚合后VNF資源需求的物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià),并利用鏈路約束降低乒乓效應(yīng),依次將VNF部署到評(píng)價(jià)度最高的節(jié)點(diǎn)上。最后采用k-最短路徑算法完成虛擬鏈路的部署。實(shí)驗(yàn)表明,該方法在保證SFC可靠性的基礎(chǔ)上,對(duì)長(zhǎng)期平均收益開銷比、映射成功率、端到端時(shí)延以及平均帶寬開銷有較大優(yōu)化。下一步將對(duì)流量預(yù)測(cè)進(jìn)行研究,進(jìn)一步提高NFV環(huán)境中網(wǎng)絡(luò)的性能。