基于VNF組合的服務功能鏈設計及映射算法

朱國暉,劉 璐,雷蘭潔

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

0 概述

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

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

本文以降低總帶寬消耗為優化目標,組合映射VNF節點,提出基于虛擬網絡功能組合的服務功能鏈設計及映射算法A-VNFC。利用整數線性規劃(Integer Linear Programming,ILP)模型在小規模物理網絡中對總帶寬消耗(Total Bandwidth Consumption,TBC)目標函數求最優解,尋找可組合的VNF并利用VNF決策樹檢查全部組合策略,直至迭代出最小的TBC。在此基礎上,通過優化調整SFC拓撲,達到降低TBC的目的。

1 問題描述和模型建立

1.1 問題描述

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

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

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

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

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

1.2 物理網絡模型

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

1.3 網絡服務功能鏈請求

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

1.4.1 VNF組合處理

(1)

(2)

1.4.2 SFC映射過程

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

(3)

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

(4)

(5)

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

(6)

2 算法設計

本文在整數線性規劃數學模型下,求解SFC拓撲設計與映射問題的最優解,在約束條件中規定組合的節點對可以映射至一個物理節點中,但不允許節點拆分。由于整數線性規劃模型適用于小型網絡,因此另提出適用于大規模網絡的基于節點組合的啟發式算法。然后,以降低總帶寬消耗為目標,判斷節點對組合的必要性,直至所有的節點對檢查完成并迭代出目標最小值,最后通過四邊形調整算法進一步優化迭代后的SFC拓撲,減少帶寬消耗。

2.1 整數線性規劃模型

本文使用整數線性規劃模型對SFC拓撲設計及映射問題進行精確定義,提出約束條件及優化目標并求得目標函數最優解。ILP模型所用參數及參數釋義如表1所示。

表1 ILP模型參數釋義Table 1 Parameter interpretation of ILP model

設定目標函數為最小總帶寬消耗,公式如下:

(7)

目標函數的約束條件包含3個部分,具體如下:

1)VNF組合約束

(8)

2)VNF映射約束

(9)

(10)

(11)

3)虛擬鏈路映射約束

(12)

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

2.2 虛擬網絡功能組合策略

由問題描述可知,部分VNF組合后并未達到降低帶寬的目的。因此,確定VNF組合方式并生成新的SFC拓撲是本文算法的重要步驟。VNF組合的必要條件為滿足式(8)所示的組合約束條件,即組合后存在可以承載其映射資源需求的物理節點。圖2給出SFC請求和VNF的組合決策樹。圖2(a)表示SFC拓撲結構,其中,虛線圈出的虛擬節點表示2個節點滿足約束條件,可以進行組合并映射至同一物理節點中,每一對可組合的VNF代表一種組合策略。圖2(b)表示VNF組合策略決策樹,其從端節點開始檢查圖2(a)中每一種組合策略執行后是否能達到TBC降低的目的,從而構成新的SFC拓撲。其中,& 表示節點組合,| 表示節點不組合,即1& 2表示節點1和節點2組合,1|2表示節點1和節點2不組合。具體算法流程如圖3所示。

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

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

2.3 基于虛擬網絡功能組合的SFC映射算法

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

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

2)對VNF進行組合處理,計算映射組合后SFC拓撲的TBC數值,若總帶寬消耗小于初始值,則更新數據,將組合后的TBC作為初始值。

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

4)在迭代完成后,對SFC拓撲中的節點執行四邊形調整優化算法,進一步降低TBC。

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

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

dis(si,si+1)

(13)

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

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

算法2A-VNFC算法

輸入一條SFC請求r

輸出TBCmin

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

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

3.對組合策略i,即組合后的SFC子拓撲進行拓撲映射并計算TBC(i)

4.If TBC(i)

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

6.i++;

7.If i<=n;跳轉至第3步

8.Else映射結束

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

10.令x=m-1

11.while x>1時執行

12.for vi的任意底層節點tido

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

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

15.end if;end for

16.令x=x-1;end while

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

18.輸出TBCmin

3 仿真結果與分析

仿真部分主要選擇TBC性能與本文相似的2種算法[19]進行對比,即關鍵子拓撲映射反饋(Close-loop with Critical Mapping Feedback,CCMF)算法和最大組合開環(Open-loop with Maximum Combination,OMC)算法,這2種算法均使用VNF組合策略,卻并未判斷組合必要性。本文以總帶寬消耗TBC作為算法性能評價指標,驗證A-VNFC算法的優越性。

3.1 仿真環境

本文的仿真環境與比較算法的仿真環境基本一致。實驗使用JAVA語言通過eclipse工具在64位的Windows7操作系統平臺下進行仿真評估。首先用小型網絡實現ILP模型和啟發式算法的仿真,然后在大型網絡中評估本文算法性能。

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

3.2 仿真結果

由于ILP模型的計算復雜度較高,因此先在6節點的網絡中進行仿真,結果如圖4所示。在不同數量的SFC請求下評估ILP算法、A-VNFC算法、OMC算法和CCMF算法的TBC性能。從圖4可以看出,本文算法可根據SFC映射反饋來決定VNF是否組合構成新的的拓撲,并在映射算法中對節點和鏈路進行調整以達到最小帶寬,因此,其TBC低于OMC算法和CCMF算法,并且非常接近ILP算法的最優結果。

圖4 6節點網絡中的TBC性能Fig.4 TBC performance in a 6-node network

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

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

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

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

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

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

4 結束語

本文從網絡功能組合的角度研究NFV中的服務功能鏈拓撲設計及映射,提出基于VNF組合的服務功能鏈設計及映射算法。利用物理網絡中多功能物理服務器可承載多個不同類型VNF的特性,將服務鏈中的兩個VNF映射到同一個物理節點,以減少實例化成本和總帶寬消耗。仿真結果表明,該算法可有效降低不同場景下的物理網絡總帶寬消耗。下一步將研究多條服務功能鏈請求到達時的最優拓撲設計和映射,并在NFV仿真環境下進行更大規模的應用與驗證。