基于VNF組合的服務(wù)功能鏈設(shè)計及映射算法

朱國暉,劉 璐,雷蘭潔

(西安郵電大學(xué) 通信與信息工程學(xué)院,西安 710061)

0 概述

軟件定義網(wǎng)絡(luò)(Software Define Network,SDN)[1]和網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization,NFV)[2-3]技術(shù)的產(chǎn)生使得現(xiàn)有網(wǎng)絡(luò)模型變得更加開放和靈活[4]。NFV可以在傳統(tǒng)的專用硬件設(shè)備上實現(xiàn)虛擬網(wǎng)絡(luò)功能(Virtualized Network Function,VNF)[5],并將其在通用設(shè)備上運行,提高網(wǎng)絡(luò)的高效性、靈活性和擴展性,降低運營商對專用設(shè)備的依賴[6]。服務(wù)功能鏈(Service Function Chain,SFC)[7-8]通過NFV提供各種網(wǎng)絡(luò)服務(wù),即SFC由虛擬網(wǎng)絡(luò)功能根據(jù)需求按一定的邏輯順序組合而成[9]。傳統(tǒng)虛擬網(wǎng)絡(luò)(Virtualized Network,VN)映射[10-12]必須確保不同虛擬節(jié)點網(wǎng)絡(luò)請求被映射到不同的物理節(jié)點上,并且節(jié)點擁有足夠的計算資源,同時,在虛擬鏈路映射到底層網(wǎng)絡(luò)路徑上時滿足其帶寬要求。與傳統(tǒng)的虛擬網(wǎng)絡(luò)映射相比,每個SFC可看作由許多連接的VNF組成的線性鏈。由于多個VNF可共享同一個物理設(shè)備以提高物理資源利用率[13],因此可以指定2個(或2個以上)VNF進(jìn)行組合,且各VNF的功能和資源需求不同。

目前,已有相關(guān)文獻(xiàn)考慮對虛擬網(wǎng)絡(luò)功能進(jìn)行聚合或拆分處理。文獻(xiàn)[14]對租戶資源需求進(jìn)行主動拆分,利用更小的資源粒度提高物理資源利用率,但是增加了算法的復(fù)雜度。文獻(xiàn)[15]提出功能聚合的概念,將相同端節(jié)點的服務(wù)鏈組成一個簇,簇中功能相同的2個(或2個以上)節(jié)點聚合為一個資源相加的大節(jié)點,達(dá)到降低虛擬網(wǎng)絡(luò)功能實例化成本的目的,但是算法未考慮功能聚合后資源需求的增大,在映射時導(dǎo)致請求接受率降低和物理資源碎片化。文獻(xiàn)[16]針對所有網(wǎng)絡(luò)服務(wù)的差異性,提出剩余鏈路帶寬資源分配的優(yōu)化算法,通過給虛擬節(jié)點和鏈路添加權(quán)重,設(shè)計總資源消耗較低的SFC拓?fù)洹?/p>

本文以降低總帶寬消耗為優(yōu)化目標(biāo),組合映射VNF節(jié)點,提出基于虛擬網(wǎng)絡(luò)功能組合的服務(wù)功能鏈設(shè)計及映射算法A-VNFC。利用整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)模型在小規(guī)模物理網(wǎng)絡(luò)中對總帶寬消耗(Total Bandwidth Consumption,TBC)目標(biāo)函數(shù)求最優(yōu)解,尋找可組合的VNF并利用VNF決策樹檢查全部組合策略,直至迭代出最小的TBC。在此基礎(chǔ)上,通過優(yōu)化調(diào)整SFC拓?fù)?達(dá)到降低TBC的目的。

1 問題描述和模型建立

1.1 問題描述

由于物理服務(wù)器支持不同的網(wǎng)絡(luò)功能,同時服務(wù)功能鏈也允許VNF的多對一映射,因此可將VNF進(jìn)行組合。然而,在實際情況下,一些VNF由于功能約束或沖突不能進(jìn)行組合和映射到相同服務(wù)器中。另外,在決定是否對不同功能進(jìn)行組合時,需要權(quán)衡以下2個方面:

1)執(zhí)行VNF組合后可節(jié)省的帶寬消耗以及其他潛在益處。

2)組合的VNF可能會映射到一個距離其他VNF較遠(yuǎn)的多功能服務(wù)器中,從而導(dǎo)致消耗更多的帶寬。

例如,在圖1(a)中沒有組合v1和v2(功能需求分別為f1和f2),將其分別映射至節(jié)點B和節(jié)點D中,總帶寬需求為:80+60+60+50+50=300 Gb/s。如圖1(b)所示,v1和v2組合映射至一個物理節(jié)點A上(即僅有節(jié)點A可以同時支持f1和f2),但是在物理鏈路中從節(jié)點A到節(jié)點C再到節(jié)點E需要配置110 Gb/s的帶寬來支持從v1和v2到v3之間的流量,導(dǎo)致總帶寬消耗450 Gb/s。在執(zhí)行VNF組合后,總帶寬消耗反而大于不執(zhí)行組合時,由此可見,在設(shè)計SFC拓?fù)涞倪^程中需要判斷VNF組合的必要性。

圖1 SFC映射過程Fig.1 Mapping process of SFC

1.2 物理網(wǎng)絡(luò)模型

物理網(wǎng)絡(luò)模型采用帶權(quán)重的無向圖Gs=(Ns,Ls)表示物理網(wǎng)絡(luò)。其中,Ns為物理節(jié)點集合,Ls為物理鏈路集合。每個物理節(jié)點ns∈Ns的計算能力為R(ns),每個節(jié)點支持的功能集合為F(ns)∈Ω,Ω表示所有通用網(wǎng)絡(luò)功能的集合。一個物理節(jié)點可作為單功能服務(wù)器提供一個功能,也可作為多功能服務(wù)器提供多種網(wǎng)絡(luò)功能,物理鏈路ls∈Ls的可用帶寬資源表示為bw(ls)。

1.3 網(wǎng)絡(luò)服務(wù)功能鏈請求

1.4 基于功能組合的SFC設(shè)計及映射模型

1.4.1 VNF組合處理

(1)

(2)

1.4.2 SFC映射過程

SFC映射包含節(jié)點映射和鏈路映射2個過程。在節(jié)點映射時,SFC中的VNF(或組合后的VNF)映射到相同的物理節(jié)點上,其映射過程的數(shù)學(xué)表達(dá)式為MN:Nv→Ns,具體過程如下:

(3)

式(3)需要滿足的資源約束條件如下:

(4)

(5)

其中,式(4)代表物理節(jié)點可以提供的SFC網(wǎng)絡(luò)功能需求,式(5)為計算資源能力約束,表示虛擬鏈路必須映射至可滿足其帶寬需求的物理節(jié)點中。

(6)

2 算法設(shè)計

本文在整數(shù)線性規(guī)劃數(shù)學(xué)模型下,求解SFC拓?fù)湓O(shè)計與映射問題的最優(yōu)解,在約束條件中規(guī)定組合的節(jié)點對可以映射至一個物理節(jié)點中,但不允許節(jié)點拆分。由于整數(shù)線性規(guī)劃模型適用于小型網(wǎng)絡(luò),因此另提出適用于大規(guī)模網(wǎng)絡(luò)的基于節(jié)點組合的啟發(fā)式算法。然后,以降低總帶寬消耗為目標(biāo),判斷節(jié)點對組合的必要性,直至所有的節(jié)點對檢查完成并迭代出目標(biāo)最小值,最后通過四邊形調(diào)整算法進(jìn)一步優(yōu)化迭代后的SFC拓?fù)?減少帶寬消耗。

2.1 整數(shù)線性規(guī)劃模型

本文使用整數(shù)線性規(guī)劃模型對SFC拓?fù)湓O(shè)計及映射問題進(jìn)行精確定義,提出約束條件及優(yōu)化目標(biāo)并求得目標(biāo)函數(shù)最優(yōu)解。ILP模型所用參數(shù)及參數(shù)釋義如表1所示。

表1 ILP模型參數(shù)釋義Table 1 Parameter interpretation of ILP model

設(shè)定目標(biāo)函數(shù)為最小總帶寬消耗,公式如下:

(7)

目標(biāo)函數(shù)的約束條件包含3個部分,具體如下:

1)VNF組合約束

(8)

2)VNF映射約束

(9)

(10)

(11)

3)虛擬鏈路映射約束

(12)

式(8)約束表示如果2個VNF可以組合,則它們可以映射到同一個物理節(jié)點,式(9)確保一個虛擬節(jié)點至多映射到一個底層節(jié)點,不允許VNF分割,式(10)和式(11)分別為計算能力約束和功能約束,式(12)確保虛擬鏈路可以映射到物理路徑中。

2.2 虛擬網(wǎng)絡(luò)功能組合策略

由問題描述可知,部分VNF組合后并未達(dá)到降低帶寬的目的。因此,確定VNF組合方式并生成新的SFC拓?fù)涫潜疚乃惴ǖ闹匾襟E。VNF組合的必要條件為滿足式(8)所示的組合約束條件,即組合后存在可以承載其映射資源需求的物理節(jié)點。圖2給出SFC請求和VNF的組合決策樹。圖2(a)表示SFC拓?fù)浣Y(jié)構(gòu),其中,虛線圈出的虛擬節(jié)點表示2個節(jié)點滿足約束條件,可以進(jìn)行組合并映射至同一物理節(jié)點中,每一對可組合的VNF代表一種組合策略。圖2(b)表示VNF組合策略決策樹,其從端節(jié)點開始檢查圖2(a)中每一種組合策略執(zhí)行后是否能達(dá)到TBC降低的目的,從而構(gòu)成新的SFC拓?fù)洹Ｆ渲?& 表示節(jié)點組合,| 表示節(jié)點不組合,即1& 2表示節(jié)點1和節(jié)點2組合,1|2表示節(jié)點1和節(jié)點2不組合。具體算法流程如圖3所示。

圖2 VNF組合策略Fig.2 Combination strategy of VNF

圖3 VNF組合策略流程Fig.3 Procedure of VNF combination strategy

2.3 基于虛擬網(wǎng)絡(luò)功能組合的SFC映射算法

本文提出基于虛擬網(wǎng)絡(luò)功能組合的SFC映射算法A-VNFC,在設(shè)計VNF組合時,考慮映射在物理網(wǎng)絡(luò)中的所有VNF和虛擬鏈路的反饋情況。A-VNFC算法主要分為以下4個步驟:

1)不考慮VNF組合執(zhí)行映射算法,對SFC請求進(jìn)行映射,計算TBC并將其作為總帶寬消耗的初始最值。

2)對VNF進(jìn)行組合處理,計算映射組合后SFC拓?fù)涞腡BC數(shù)值,若總帶寬消耗小于初始值,則更新數(shù)據(jù),將組合后的TBC作為初始值。

3)重復(fù)步驟2)直至所有組合策略檢查完畢,迭代出最終TBC。

4)在迭代完成后,對SFC拓?fù)渲械墓?jié)點執(zhí)行四邊形調(diào)整優(yōu)化算法,進(jìn)一步降低TBC。

節(jié)點組合方法如2.2節(jié)所述,在SFC拓?fù)溆成潆A段使用文獻(xiàn)[17]的NS-NFV算法,該算法在選擇物理候選節(jié)點時引入節(jié)點親密度[18]屬性,親密度越高,節(jié)點之間經(jīng)過的鏈路跳數(shù)越少,需求帶寬也越少。本文在此算法的基礎(chǔ)上,使用四邊形調(diào)整策略優(yōu)化帶寬資源配置,主要優(yōu)化在一條服務(wù)鏈中的3個連續(xù)VNF節(jié)點。例如,將任意連續(xù)的3個虛擬節(jié)點vi-1→vi→vi+1分別映射至物理節(jié)點si-1、si和si+1中,若存在物理節(jié)點ti對應(yīng)于VNF節(jié)點vi,則滿足如下公式:

dis(si-1,ti)+dis(ti,si+1)

dis(si,si+1)

(13)

其中,dis(s,t)表示物理節(jié)點s和t之間的帶寬資源消耗。若類似的節(jié)點ti可以被找到,則將VNF節(jié)點vi重新映射至節(jié)點ti上,以求得映射的最小帶寬消耗。

A-VNFC算法的具體步驟如算法2所示,其輸入為一條SFC,最終輸出迭代后的總帶寬消耗。首先對未進(jìn)行節(jié)點組合處理的SFC請求通過NS算法進(jìn)行映射處理,并將計算得到的TBC數(shù)值作為TBCmin。然后尋找滿足約束條件下的n種組合策略,若無則跳轉(zhuǎn)至第9行以降低TBC,若有則跳轉(zhuǎn)至第3行逐一檢查n種組合策略是否可以降低TBC,并且重復(fù)執(zhí)行第3行直至檢查完所有的組合策略,求出TBCmin值之后跳轉(zhuǎn)至第9行以優(yōu)化TBC。

算法2A-VNFC算法

輸入一條SFC請求r

輸出TBCmin

1.使用NS-NFV算法,映射SFC并計算TBCmin數(shù)值

2.為SFC請求r尋找n種滿足約束的虛擬節(jié)點組合策略,若存在跳轉(zhuǎn)至第3步,若無VNF可組合跳轉(zhuǎn)至第9步

3.對組合策略i,即組合后的SFC子拓?fù)溥M(jìn)行拓?fù)溆成洳⒂嬎鉚BC(i)

4.If TBC(i)

5.Else TBC(i)>TBC,則組合策略i失敗;

6.i++;

7.If i<=n;跳轉(zhuǎn)至第3步

8.Else映射結(jié)束

9.將虛擬節(jié)點存入集合V={v1,v2…,vm},物理節(jié)點存入集合S={s1,s2,…,sm}

10.令x=m-1

11.while x>1時執(zhí)行

12.for vi的任意底層節(jié)點tido

13.if dis(si-1,ti)+dis(ti,si+1)

14.映射vi至底層節(jié)點ti,更新集合V和集合S

15.end if;end for

16.令x=x-1;end while

17.根據(jù)式(7)計算其TBCmin值

18.輸出TBCmin

3 仿真結(jié)果與分析

仿真部分主要選擇TBC性能與本文相似的2種算法[19]進(jìn)行對比,即關(guān)鍵子拓?fù)溆成浞答?Close-loop with Critical Mapping Feedback,CCMF)算法和最大組合開環(huán)(Open-loop with Maximum Combination,OMC)算法,這2種算法均使用VNF組合策略,卻并未判斷組合必要性。本文以總帶寬消耗TBC作為算法性能評價指標(biāo),驗證A-VNFC算法的優(yōu)越性。

3.1 仿真環(huán)境

本文的仿真環(huán)境與比較算法的仿真環(huán)境基本一致。實驗使用JAVA語言通過eclipse工具在64位的Windows7操作系統(tǒng)平臺下進(jìn)行仿真評估。首先用小型網(wǎng)絡(luò)實現(xiàn)ILP模型和啟發(fā)式算法的仿真,然后在大型網(wǎng)絡(luò)中評估本文算法性能。

本文采用GT-ITM[20]工具生成底層物理網(wǎng)絡(luò)和SFC拓?fù)洹Ｐ⌒臀锢砭W(wǎng)絡(luò)由6個服務(wù)器通過8條物理鏈路相互連接,其中3個服務(wù)器被隨機分配為多功能服務(wù)器,剩余的則為單功能服務(wù)器。每個單功能服務(wù)器提供一種網(wǎng)絡(luò)功能,多功能服務(wù)器提供3種網(wǎng)絡(luò)功能,其功能從6種網(wǎng)絡(luò)功能中隨機分配。大型物理網(wǎng)絡(luò)由24個服務(wù)器通過43條物理鏈路相互連接，其中10個服務(wù)器被隨機分配為多功能服務(wù)器，其功能從8種網(wǎng)絡(luò)功能種隨機分配。每個服務(wù)器隨機分配1 500 unit的計算資源并且每條物理鏈路分配足夠的帶寬資源。另外,隨機生成30條SFC請求,每條請求由2個～6個VNF組成,每個VNF請求計算需求小于50 unit并且每條虛擬鏈路帶寬需求小于30 Gb/s。VNF組合率設(shè)置為0.3,表示所有VNF的30%可以被隨機選擇與另一個VNF組合。為保證仿真的可靠性,對于以上參數(shù)設(shè)置進(jìn)行5次實驗取平均值。

3.2 仿真結(jié)果

由于ILP模型的計算復(fù)雜度較高,因此先在6節(jié)點的網(wǎng)絡(luò)中進(jìn)行仿真,結(jié)果如圖4所示。在不同數(shù)量的SFC請求下評估ILP算法、A-VNFC算法、OMC算法和CCMF算法的TBC性能。從圖4可以看出,本文算法可根據(jù)SFC映射反饋來決定VNF是否組合構(gòu)成新的的拓?fù)?并在映射算法中對節(jié)點和鏈路進(jìn)行調(diào)整以達(dá)到最小帶寬,因此,其TBC低于OMC算法和CCMF算法,并且非常接近ILP算法的最優(yōu)結(jié)果。

圖4 6節(jié)點網(wǎng)絡(luò)中的TBC性能Fig.4 TBC performance in a 6-node network

根據(jù)SFC請求數(shù)量的增加觀察3種算法的TBC變化,結(jié)果如圖5(a)所示?？梢钥闯?3種算法的TBC均隨SFC請求數(shù)量的增加而增加,但A-VNFC算法的增幅明顯低于OMC算法和CCMF算法。這是因為A-VNFC算法考慮映射在底層網(wǎng)絡(luò)的節(jié)點及鏈路反饋情況進(jìn)行VNF組合,減少了帶寬消耗。圖5(b)給出SFC請求的大小對TBC的影響?？梢钥闯?隨著SFC請求變大,TBC也明顯增加,但是TBC的增加速度在SFC請求達(dá)到6以后變緩慢。這是因為隨著SFC大小的增加,會有更多的VNF可進(jìn)行組合,因此節(jié)省了帶寬消耗。

圖5 SFC請求對TBC性能的影響Fig.5 Impact of SFC request on TBC performance

圖6給出VNF組合概率對TBC性能的影響。從圖6可以看出,隨著組合概率的增加,TBC的數(shù)值降低,且A-VNFC算法的降幅較其他2種算法更大,說明A-VNFC算法可以根據(jù)映射反饋為VNF組合做出最合適的選擇。

圖6 VNF組合概率對TBC性能的影響Fig.6 Influence of VNF combination probability on TBCperformance

圖7給出多功能服務(wù)器數(shù)量和服務(wù)器上可提供功能數(shù)量對TBC的影響。從圖7(a)可以看出,TBC隨多功能服務(wù)器數(shù)量的增加而呈下降趨勢,這是因為多功能服務(wù)器越多,供給VNF組合的概率就越大。在圖7(b)中,TBC隨服務(wù)器提供的功能數(shù)量的增加而增加,原理同上,都是因為服務(wù)器提供給VNF組合的概率增加。

圖7 物理服務(wù)器對TBC性能的影響Fig.7 Impact of physical servers on TBC performance

4 結(jié)束語

本文從網(wǎng)絡(luò)功能組合的角度研究NFV中的服務(wù)功能鏈拓?fù)湓O(shè)計及映射,提出基于VNF組合的服務(wù)功能鏈設(shè)計及映射算法。利用物理網(wǎng)絡(luò)中多功能物理服務(wù)器可承載多個不同類型VNF的特性,將服務(wù)鏈中的兩個VNF映射到同一個物理節(jié)點,以減少實例化成本和總帶寬消耗。仿真結(jié)果表明,該算法可有效降低不同場景下的物理網(wǎng)絡(luò)總帶寬消耗。下一步將研究多條服務(wù)功能鏈請求到達(dá)時的最優(yōu)拓?fù)湓O(shè)計和映射,并在NFV仿真環(huán)境下進(jìn)行更大規(guī)模的應(yīng)用與驗證。