基于流量優化的可靠服務功能鏈部署方法

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

(空軍工程大學信息與導航學院, 陜西 西安 710077)

0 引 言

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

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

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

(1) 根據虛擬鏈路的帶寬需求變化對VNF進行聚合,使聚合的VNF部署到底層網絡后大帶寬需求鏈路上的流量變為服務器的內部流量,優化了資源開銷；

(2) 提出節點綜合時延和拓撲就近度指標,前者量化節點及其相鄰鏈路所產生的時延,后者量化節點與源、目的端點之間最短路徑的拓撲屬性,實現了算法對底層網絡的拓撲與時延感知；

(3) 采用離差最大化多指標決策算法對物理節點進行評價,對排序作用大的評價指標賦予更高權重,實現了權重的自適應設定;

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

1 網絡模型及問題描述

1.1 網絡模型

物理網絡用一個加權無向圖G=(N,E)表示,其中N為物理節點的集合,E為物理鏈路的集合。每個物理節點上附著一至多個服務器,能夠用來實例化VNF。節點ns∈N的剩余可用計算資源為Cal(ns),可用存儲資源為Mem(ns),可用轉發資源為For(ns),實例化VNF后產生的時延為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),轉發資源需求為For(vi),帶寬改變因子為η(vi),其中帶寬改變因子定義為VNF流量的流出帶寬與流入帶寬之比。集合L={l0,l1,…,ln}中的元素li為vi到vi+1之間的虛擬鏈路。當i=0時,li為源端點I到v1之間的虛擬鏈路,當i=n時,li為vn到目的端點O之間的虛擬鏈路。用b(li)表示li的帶寬需求,則b(li)的計算公式為

(1)

1.2 優化目標

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

(2)

式(2)的第一部分表示節點的計算、存儲與轉發資源開銷,第二部分表示鏈路的帶寬開銷。本文旨在保證SFC可靠性和時延要求的基礎上,對資源開銷進行優化,優化目標為

Goal=min(Cost)

(3)

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

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

1.3 問題描述

從資源開銷的組成部分分析,由于每個VNF只能部署在一個物理節點上,所以計算、存儲與轉發資源的開銷與需求相等,無法對其進行優化。而每一條虛擬鏈路能夠部署在一條或多條物理鏈路上,所以帶寬開銷必定大于或等于帶寬需求,能夠對其進行優化。圖1是同一SFC在相同物理網絡拓撲下的3種不同部署方法,箭頭處數字代表初始帶寬,VNF處數字代表帶寬改變因子。

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

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

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

2 基于流量優化的可靠服務功能鏈部署方法設計

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

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

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

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

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

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

對SFC中VNF進行聚合處理后,再對聚合的VNF進行部署。本算法的中心思想是在對底層網路進行拓撲與時延感知的基礎上,利用離差最大化的多目標決策算法對物理節點進行評價并排序,每次按照編排順序部署聚合后的VNF時,依據資源約束與鏈路約束篩選物理節點,再從篩選出的物理節點中選擇排序靠前的部署VNF。對物理節點進行評價的指標有節點可靠性、節點綜合時延、節點拓撲就近度和節點源端距。

節點可靠性采用固有可用度[30]進行表示,其定義為

(11)

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

定義 1節點綜合時延是對節點及其相關聯鏈路所產生時延的綜合度量,能反映選取該節點部署VNF后對SFC時延的影響,是算法實現對底層網絡時延感知的關鍵指標,其計算公式為

(12)

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

定義 2節點拓撲就近度表示節點與源目端點之間最短路徑的拓撲緊密程度,能反映選取該節點部署VNF后對SFC物理長度的影響,是算法實現對底層網絡拓撲感知的關鍵指標,其計算公式為

(13)

式中:TD(ns)表示ns的度數,數值上等于|E(ns)|；hop(ns,I)表示ns與源端點之間的最短跳數；hop(ns,O)表示ns與目的端點之間的最短跳數。采用節點拓撲就近度作為評價指標能縮短SFC的物理長度,節點的拓撲就近度越大,越有利于靠前排序。

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

采用離差最大化的多指標決策算法計算每個物理節點ns的評價度S(ns),并利用S(ns)對各物理節點進行排序,然后依據VNF編排順序對各VNF進行部署。離差最大化的多指標決策算法步驟如下。

步驟 1根據評價指標類型構造規范化決策矩陣(Zij)m×n。假設有m個評價對象,表示不同的物理節點,每個物理節點有n個評價指標,記第i個物理節點的第j個評價指標值為aij。值越大越有利于節點靠前排序的評價指標為效益型評價指標,如節點可靠性與拓撲就近度;值越小越有利于節點靠前排序的評價指標為成本型評價指標,如節點綜合時延與源端距。效益型評價指標在決策矩陣中的值為

(14)

成本型評價指標在決策矩陣中的值為

(15)

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

步驟 2根據離差最大化方法計算各評價指標的最優加權向量W*。設評價指標的加權向量為W=[w1,w2,…,wn],則在W作用下規范化決策矩陣為

(16)

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

(17)

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

(18)

據前面分析,加權向量W的選擇應使所有評價指標的總離差最大,因此構造目標函數為

(19)

其中,約束條件為

(20)

(21)

步驟 3根據最優加權向量作用下的決策矩陣計算各物理節點的綜合評價度S(ns)。最優加權向量作用下的決策矩陣為

(22)

第i個物理節點的綜合評價度為

(23)

算法 2 基于離差最大化的VNF部署算法輸入: 經VNF聚合處理后的SFC=(I,O,D,T,R,V′,L′),物理網絡G=(N,E)輸出: VNF_Embedding_List1 for N中每一個物理節點ns2 利用離差最大化多指標決策算法計算綜合評價度S(ns);3 end for4 利用S(ns)對N中物理節點進行排序;5 for V′中每一個v′i6 從N中篩選出滿足其計算、存儲與轉發資源需求的節點集合Ф(v′i);7 if Ф(v′i)為空8 return VNF_EMBEDDING_FAILED9 else10 從Ф(v′i)刪除滿足hop(ns, O)>hop(ns(vi-1′), O)的物理節點;11 if Ф(v′i)為空12 return VNF_EMBEDDING_FAILED13 else14 將v′i部署到Ф(v′i)中排序最靠前的物理節點上,并將映射關系存入VNF_Embedding_List中;15 更新各物理節點剩余資源;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部署完畢后,首先在物理拓撲中刪除不滿足帶寬需求的物理鏈路,然后利用k-最短路徑算法在剩余拓撲中部署虛擬鏈路,最后根據VNF所部署物理節點產生的時延與虛擬鏈路所部署物理鏈路的時延計算出SFC的端到端時延,若該時延小于最大允許時延D,則SFC部署成功,否則部署失敗。

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

3 算法性能評估與分析

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

3.1 方法評價指標

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

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

(24)

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

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

(25)

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

(3) SFCg的可靠性為

(26)

則SFC的平均可靠性定義為

(27)

(4) SFCg的端到端時延為

(28)

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

(29)

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

(30)

物理網絡的資源開銷為

(31)

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

(32)

3.2 仿真環境設置

仿真環境中物理網絡是由100個節點和525條鏈路組成的連通圖,相當于一個中型網絡拓撲,SFC請求服從到達率λ=0.05的泊松分布,生存時間服從μ=1 000的指數分布,仿真時間為50 000個單位。其余各項參數如表1所示。

表1 仿真參數Table 1 Simulation parameters

3.3 實驗結果分析

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

圖3 重復映射鏈路條數Fig.3 Number of links that are mapped repeatedly

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

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

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

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

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

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

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

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

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

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

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

4 結 論

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