基于流量優(yōu)化的可靠服務(wù)功能鏈部署方法

陽 勇, 孟相如, 康巧燕, 趙文文

(空軍工程大學(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ò)升級換代需要巨大開銷、可管理性差、可擴(kuò)展性差等[3-5]。網(wǎng)絡(luò)功能虛擬化(network function virtuali-zation,NFV)是解決上述問題的下一代網(wǎng)絡(luò)重要技術(shù)之一,其通過解耦硬件物理設(shè)備與運(yùn)行于其上的網(wǎng)絡(luò)功能,實現(xiàn)網(wǎng)絡(luò)功能的靈活部署、軟硬件的發(fā)展周期分離以及網(wǎng)絡(luò)功能的動態(tài)擴(kuò)展[6-8]。利用NFV技術(shù),網(wǎng)絡(luò)功能可以當(dāng)成一個普通軟件的實例,根據(jù)需求動態(tài)部署在網(wǎng)絡(luò)中不同位置而無需重新安裝新的硬件,在增加靈活性的同時極大地降低了運(yùn)營商的成本[9-11]。

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

Goal=min(Cost)

(3)

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

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

1.3 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

(11)

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

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

(12)

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

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

(13)

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

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

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

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

(14)

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

(15)

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

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

(16)

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

(17)

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

(18)

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

(19)

其中,約束條件為

(20)

(21)

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

(22)

第i個物理節(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中每一個物理節(jié)點ns2 利用離差最大化多指標(biāo)決策算法計算綜合評價度S(ns);3 end for4 利用S(ns)對N中物理節(jié)點進(jìn)行排序;5 for V′中每一個v′i6 從N中篩選出滿足其計算、存儲與轉(zhuǎn)發(fā)資源需求的節(jié)點集合Ф(v′i);7 if Ф(v′i)為空8 return VNF_EMBEDDING_FAILED9 else10 從Ф(v′i)刪除滿足hop(ns, O)>hop(ns(vi-1′), O)的物理節(jié)點;11 if Ф(v′i)為空12 return VNF_EMBEDDING_FAILED13 else14 將v′i部署到Ф(v′i)中排序最靠前的物理節(jié)點上,并將映射關(guān)系存入VNF_Embedding_List中;15 更新各物理節(jié)點剩余資源;16 end if17 end if18 end for19 計算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é)點產(chǎn)生的時延與虛擬鏈路所部署物理鏈路的時延計算出SFC的端到端時延,若該時延小于最大允許時延D,則SFC部署成功,否則部署失敗。

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

3 算法性能評估與分析

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

3.1 方法評價指標(biāo)

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

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

(24)

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

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

(25)

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

(3) SFCg的可靠性為

(26)

則SFC的平均可靠性定義為

(27)

(4) SFCg的端到端時延為

(28)

則SFC平均端到端時延定義為

(29)

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

(30)

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

(31)

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

(32)

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

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

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

3.3 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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