基于VNF間性能干擾的服務請求調度策略

郭 勝，史久根，孫 立，謝熠君

(合肥工業大學 計算機與信息學院，安徽 合肥 230601)

0 引 言

網絡功能虛擬化(network function virtual，NFV)技術的特點在于實現硬件與軟件的分離，通過網絡功能的虛擬化，將虛擬網絡功能(virtual network function，VNF)運行在通用硬件之上，不需要專用硬件，減少成本支出[1]。虛擬網絡功能可以放置在虛擬機(virtual machine，VM)節點提供特定的網絡功能[2]。通過VM遷移，VNF可以部署在網絡中任意一個商用服務器中，同時這種新的模式也帶來了一些挑戰。首先，數據包需要經過一組VNF，即服務功能鏈[3](service function chain，SFC)，網絡運營商會考慮如何將VNF部署在候選服務器中以減少端到端延時。例如，Zhang等人[4]以最大化平均資源利用率和最小化請求平均響應延時為目標，提出了綜合考慮VNF服務鏈放置及服務請求調度的問題。其次，要提高資源利用率，VNF布局根據流量變化動態調整VNF實例的數量。例如，Eramo等人[5]提出VNF遷移策略，使得網絡運營商得知VNF最佳的遷移的時間和地點，以節約資源。最后，現有的VNF實例可能需要合并到另一臺服務器以釋放和關閉一些服務器來節省資源。現有研究致力于研究應對上述挑戰并提供高效的VNF放置方法。例如，Li等人[6]考慮不同VNF，在同一時隙對硬件計算量的需求不同，故將時變負載相關度最小的VNF放置在同一節點，達到計算資源互補，并采用多租戶策略共享VNF，從而減少物理機的使用量來減少資源消耗。

然而現有的VNF放置方法大都沒有將VNF同位間的性能干擾問題考慮在內。雖然虛擬化技術在VM之間提供了一定程度的性能隔離[7]，但VNF在一個共享的硬件基礎設施上運行時仍存在明顯的性能干擾[8]。當流量監視器與入侵檢測系統同時運行時，流量監控器的吞吐量下降了38.47%[9]。但是，為了最大化資源利用率和降低功耗，網絡運營商傾向于將VNF實例放在同一物理上的服務器盡可能多，導致資源匱乏競爭和嚴重的性能干擾。同時，在數據流增大的時候干擾也隨之增強。由于數據流的增大，VNF處理任務增加，所需的資源也隨之增加，導致基本硬件資源的競爭更加激烈。

針對上述問題，該文根據不同類型的虛擬網絡功能的工作特性，通過在虛擬機中運行工作特性相似的應用以及文獻[9]的分析，得出不同的虛擬網絡功能對CPU、Memory、Cache等資源的依賴程度，設計一個CAPA算法解出VNF之間的最佳組合，使得整體干擾度最小，并進行放置。其次，根據不同VNF對數據流量的處理特性，使用TAA算法進行服務請求的調度，從而進一步減小虛擬網絡功能的干擾程度。仿真結果表明，該方案緩解了VNF間的干擾，提升了網絡吞吐量。

1 問題描述

該模型需要解決的問題是，根據不同虛擬網絡功能間干擾程度不同，對每個VNF進行組合，要設法使其雙方的干擾度都盡可能小，并對服務鏈請求進行合理的調度，使得整體網絡中的虛擬網絡功能受到的干擾最小。

1.1 同位間虛擬網絡功能干擾

同位間虛擬網絡功能干擾是指，同一個物理中VNF會產生一定的性能干擾，使得彼此間性能下降。由于VNF對各種硬件資源的需求不盡相同，若多個同種資源需求密集型VNF放置在同一服務節點，會引起服務節點底層的某一資源過度占用，從而使得服務節點整體處理性能下降。在圖1中(a)表示當VNF1與VNF2獨立運行在服務器時的處理能力，(b)表示新增的VNF3分別放置在先前的服務器中，使得三個VNF處理能力都有不同程度的下降。由于各VNF，對不同的資源需求的比重不盡相同，可以通過資源互補的形式進行合理組合。如圖2所示，左邊部分表示三種VNF對不同資源的需求(每個顏色的柱型代表一種資源)，右上側VNF1+VNF2表示VNF1與VNF2進行組合，右下側VNF1+VNF3表示VNF1與VNF3匹配，故合理的組合可以達到較優的效果。

圖1 VNF間性能干擾示例

圖2 VNF匹配方案示例

1.2 修改數據流的大小

VNF會對數據包進行分析，根據特殊的業務需求對數據包添加包頭，或者對數據包進行優化壓縮，使得數據包的字節數及數據流的大小都被改變[10]。目前VNF的總數很多，與路由器的數量相當[11]，其中很大一部分的VNF有改變數據流大小的性質。如圖3所示，網絡功能F1可將數據流修改為原來的兩倍，F2則將數據流修改為原來的一半，所以數據流先經過F2時，可減緩F1的處理負擔，而VNF的流經順序是部分可調的[12-13]。

圖3 VNF修改數據流示例

數據流的減小和增大直接影響VNF工作時對資源的競爭程度。因此合理的調度方案可以進一步減小干擾。

2 系統模型

圖G(E,V)表示交換機網絡模型，節點v∈V都有一個物理機，設定網絡中的物理機是統一的，每個物理機有資源R(u)(r1,r2,…,rn)，ri表示各項分資源。(u,v)∈E表示連接節點u與v的鏈路傳播時延為De(u,v)。網絡為具有全局拓撲視圖的SDN網絡[14]，設定網絡中的交換機，連接高容量光鏈路，因此每條鏈路的帶寬容量不做約束[15]。

定義(干擾度)：假設兩個向量a(x1,x2,…,xn)和b(y1,y2,…,yn)之間的夾角為θ，a、b向量的長度分別是‖a‖和‖b‖，θ所對的邊的邊長為‖a-b‖。根據余弦定理：

‖a-b‖2=‖a‖2+‖b‖2-

(1)

a·b=‖a‖·‖b‖cosθ

(2)

根據上述公式可以得到：

(3)

cosθ就是余弦相似度，兩個向量之間的夾角越小，其夾角余弦越大(越相似)。因此可用余弦相似度來度量兩個VNF對資源的需求相似度。向量a(x1,x2,…,xn)對應VNF對各種資源的占有率X(X1,X2,…,Xn)，由于不同VNF對每種資源的依賴程度不一，故定義λ(λ1,λ2,…,λn)，λi表示VNF對某一種資源依賴程度的權值。VNF間的干擾度定義如下：

(4)

其物理概念為同一服務節點中的一個VNF的資源的占有率與另一個VNF對資源的實際需求率的一個契合程度。網絡吞吐量與網絡中VNF間的干擾程度呈反比例關系，定義反比例系數β，吞吐量P(m)與干擾度存在下述關系：

P(m)=βcosXY

(5)

決策變量的定義：用F表示所有流的集合，用Z表示網絡中VNF個數。任意一條流f∈F由三元組(srcf,dstf,Mf)表示其屬性，其中srcf表示流f的源節點，dstf表示流f的目的主機，Mf表示流f需要經過的VNF集合。ratio(m)表示VNFm的流改變因子。用符號→來定義VNF的依賴關系，若m→n則n依賴于m，即業務流需先經過m再經過n。

首先定義VNF處理順序的傳遞性，例如m→n，n→k，那么m→k。用二進制變量d(m,n)來描述這種關系：

(6)

(7)

(8)

流f在網絡中經過的是一條多跳路徑，用i表示跳數，若共有N跳，那么1≤i≤N。用f(u,i)表示第i跳所在的位置：

(9)

同一節點允許部署一條流的多個VNF實體，對于流f來說有以下情況：

?u,i≠j:f(u,i)=1&f(u,j)=1

(10)

約束條件：tin(f,u)和tout(f,u)分別表示流f進入節點u和流出節點u的流量數據率。對于流f來說，如果它在節點u經過了VNF的處理，那么tin(f,u)和tout(f,u)滿足如下關系：

(11)

對于網絡中的物理節點來說，所有服務請求的VNF集合實例化到該點上所需的資源總和必須不超過該物理節點u所能提供的節點容量，R(u)與式(4)中的Xi以(Yi)對應，約束如下：

(12)

構成一條路徑的所有中間鏈路De(u,v)之和要小于所設定的時延容限MDe。約束如下：

(13)

如果VNFn依賴于VNFm，那么流f將先經過VNFm，即有以下約束：

f(v,k)×i]×d(m,n)>0

(14)

用下式表示鏈路中的流守恒：

tout(f,u)=tin(f,u+1)

(15)

最后文中目標是最大化網絡吞吐量，T表示參數因子，T與tin(f,u)呈反比。

(16)

3 算法分析

該文所要完成的目標，在式(11)～式(15)的約束下求解是一個NP-難問題。因為在所給定的節點容量約束下，不考慮資源種類和各VNF對不同資源的需求權重時，問題將轉換成裝箱問題，裝箱問題是常見的NP-難問題[16]。完成該目標需要兩個算法實現，首先通過自主設計的基于貪心的CAPA算法得到VNF間的最佳組合，并進行放置。然后通過TAA算法進行流服務請求調度，使得數據流經過各個節點的累加值最小，進一步減小VNF間性能干擾。所以通過該文提出的兩步調整策略可完成目標。

3.1 算法描述

算法1：MIMP算法。

輸入：虛擬網絡功能集合L，網絡拓撲G(E,V)，拓撲中心節點c；

輸出：組合放置集合L'。

1.構建優先矩陣ψ

2.鏡像復制

3.延時接受算法匹配

4.重復項刪除

5.干擾度求和排序

6.if原∑P(m)>重組∑P(m) do

7.拆分重組Return to step 5

8.else 構建組合集ξ

9.Dijkstra算法選點

10.組合集映射到節點集

11.得到組合放置集合L'

12.結束

算法1：

(1)輸入數據處理：首先輸入所有VNF資源需求集合L，網絡拓撲G(E,V)和給定的拓撲中心節點c，通過式(4)進行干擾度計算，生成VNF間的干擾度矩陣W。然后將矩陣的每一行元素按照干擾程度大小進行升序排列得到優先列表矩陣ψ，越靠前則最優。復制列表矩陣，一份做原優先列表矩陣，另一份為鏡像ψ'。鏡像處理使得原先無法進行匹配的單列元素可以進行匹配處理。

(3)節點映射：由于模型的設定，物理機類型統一，故將VNF組合向網絡拓撲中心靠攏，方便后續的服務請求調度，故以延時De為權值，使用Dijkstra算法計算給定節點c到網絡拓撲中其他節點延時的大小，得到權值集合τ。將得到的組合集合ξ中的元素映射到權值較小的集合τ中的節點元素，最終輸出最佳組合放置集合L'。

算法2：TAA算法。

輸入：服務請求的虛擬網絡功能集合Ω,網絡拓撲G(E,V)，組合放置集合L'

輸出：服務請求調度集合S

1.while Ω≠? do

2.讀取所需VNF信息構建初步順序

3.if 無依賴關系的VNF個數≠0 do

4.if NVF ratio(m)<1 do

5. 序列頭部升序排列 end if

6.if NVFratio(m)>1 do

7. 序列尾部升序排列 end if

8. end if return VNF order

9.得到必經點及順序約束

10.Dijkstra算法

11.if ∑De(u,v)

12.else丟棄此請求

13.輸出最終服務請求調度集合S

14.結束

算法2：

(1)順序建立：請求集合Ω不為空，對每條服務請求中的VNF的流修改因子ratio(m)進行讀取，判斷服務請求中的VNF是否存在依賴關系的VNF，確立具有依賴關系的VNF的流經順序。然后判斷服務請求中的VNF是否存在沒有依賴關系的VNF，若有，且VNF的流修改因子小于1，則將其在調度列表中頭部進行升序排列，若VNF的流修改因子大于1，則將其在調度列表中尾部進行升序排列，從而確立了此條服務請求中VNF的所有流經順序。

(2)路徑選擇：對于每條服務請求讀取其源節點以及目的節點，并將其值分別賦予k1，k2根據服務請求所需的VNF所在的物理節點，建立必經點的路徑約束，再根據上述處理提供的VNF流經順序，建立順序約束。最后通過雙約束的Dijkstra算法以鏈路延時為權值，進行路徑選擇，若總傳播時延超過給定的時延閾值則丟棄此條服務請求，若滿足約束則加入到最優路徑集，最終為請求集合中的每條服務規劃出一條路徑，得到服務請求調度集合S。

3.2 算法復雜度分析

用ω表示VNF的個數，在算法1中構建干擾度矩陣所需循環次數為O(ω2)，構建優先列表矩陣所需循環次數為O(ω2)，匹配過程中最大循環次數為O(ω2)，重組調整過程中的最大循環次數O(ω2-2ω)。Dijkstra算法時間復雜度為O(v2)，v表示物理節點個數，故算法1的整體復雜度為O(v2+ω2)。

在算法2中VNF的順序處理的復雜度取決于服務鏈的長度，以及無順序約束的VNF個數，定義平均服務鏈長度為ε最終順序建立的平均復雜度為O((ε/2)2)。Dijkstra算法的時間復雜度為O(n2)，其中n表示節點跳數，由于約束條件的存在，算法中使用的Dijkstra算法的復雜度為O(ε2)，故其整體復雜度為O(ε2+n2)。

3.3 算法近似比分析

CAPA算法所要解決的是一個NP-難問題，故對此進行近似比分析。將物理機假設為單位容量為C的箱子，VNF假設為大小為s的物品，設si<1,i=1,2,…,n。設OPT(I)為最優解所用箱子數目的一個上界，CAPA(I)為CAPA算法的解。由算法描述中CAPA算法的拆分重組規則可知，所有箱子中至多有一個非空箱子，所裝的物體體積小于1/2。

現在設εi為第i個箱子中的空余容量，δi為物品占用第i個箱子的容量εi+δi=C。那么有：

對于第k個箱子有兩種情況：

(1)εk<δk；

(2)εk>δk。

對于情況2，有：εk-1<δk，εk<δk-1，所以：

εk-1+εk<δk-1+δk。

最優解的一個上界為所有箱子恰好裝入全部物體，即：

故CAPA算法近似比為：

4 仿真實驗結果及分析

4.1 仿真實驗環境參數

硬件環境為Inter Core i5-7200U CPU 2.71 GHz RAM 4 GB的Windos10家庭版操作系統；該文選擇的仿真平臺是matlab2017a。實驗采用的網絡拓撲為真實的網絡拓撲Internet2(Internet OS3E)[17]。實驗設定VNF個數Z=32，實驗考慮多種不同資源R(u)(r1,r2,…,rn)，每個VNF對多種不同資源都有不同的權λ(λ1,λ2,…,λn)，每個VNF都有一個固有的流修改因子ratio(m)。

4.2 性能分析

4.2.1 CAPA算法的性能分析

圖4表示不同算法情況下，網絡中分別部署4,8,16,32個VNF時，網絡的整體標準化吞吐量變化情況(利用式(5)計算，并做標準化處理，標準化處理最終為兩個結果的比值)。從實驗結果圖中發現，在VNF數量較少的情況下，CAPA算法與First-fit算法[18]差異不是特別明顯。這是因為當VNF數量較少時，組合的方式很少，當VNF數量增加使差異不斷增加是因為First-fit算法在尋找組合對象時只考慮選擇對象對自己的干擾程度，沒有考慮自身對選擇對象的干擾程度，使得單方面最優，達不到雙方最優。圖中random表示不考慮干擾因素以隨機的方式組合，其代表的柱型起伏不定的原因是由于VNF數量少時偶然性因素較大。

圖4 不同VNF個數下的網絡標準化吞吐量情況

4.2.2 TAA算法的性能分析

圖5表示在Internet OS3E網絡中，設定服務鏈總長度為10，當平均無依賴關系的VNF占服務請求鏈的百分比增加時，兩種算法情況的對比。縱坐標的標準化處網絡吞吐量，可由式(16)經過標準化處理得到。從圖中可以看出，當服務鏈請求中的無依賴關系的VNF占總體服務鏈請求所需的VNF比重越小，TAA算法性能會越接近于Dijkstra算法[19]，這是因為當具有先后依賴關系的VNF占服務鏈請求所需的VNF比重越大，TAA算法所能調整的范圍就會越小，在服務鏈請求中的VNF全部相互依賴的情況下，TAA接近普通算法。在實際情況中服務鏈請求中的VNF是有相當一部分可以調整的。

圖5 無依賴關系的VNF比例與性能間關系

4.2.3 標準化傳播時延分析

圖6表示在不同的無依賴關系的VNF比例下，兩種VNF放置方法與網絡標準化傳播時延的關系，其中服務鏈總長度設定為10，用TAA算法進行調度。圖中可以看到隨著流經順序可調的VNF比例的增加，兩種放置方法對應的網絡中標準化傳播延時都在減小，這是因為服務請求調度的順序約束減少了。而中心化放置方式對應的網絡標準化傳播時延，始終較小的原因是由于隨機放置，會使得某些VNF被放置在網絡邊緣，流服務請求必須達到網絡邊緣獲取相應的處理，仿真結果中隨機放置情況下TAA算法所得平均端到端延時為0.55 ms。而中心化放置使得VNF集中于網絡拓撲中心附近，服務請求在網絡拓撲中心附近便可獲取所需的處理，實驗分析表明CAPA算法中將VNF放置在網絡拓撲中心附近，能夠在一定程度上減小服務請求調度過程中的網絡傳播時延。

圖6 標準化傳輸時延無依賴關系VNF比例間關系

4.2.4 算法整體性能分析

圖7中，考慮干擾方案表示在Internet2(Internet OS3E)網絡中，將VNF通過算法1進行組合放置在網絡拓撲中，設定服務鏈總長度為10，服務鏈請求中具有依賴關系VNF的比例為60%，并使用TAA算法進行服務請求調度。未考慮干擾方案表示在Internet2(Internet OS3E)網絡中，通過First-fit算法進行組合放置，并使用Dijkstra算法進行請求調度。從實驗生成圖中可以看出，當數據流不斷增加時，兩種方案下的標準化網絡吞吐量都有所下降，但是考慮干擾方案下的網絡吞吐量始終比未考慮干擾方案下的標準化網絡吞吐量優。

圖7 標準化處理能力隨數據流大小變化示意圖

5 結束語

提出了一種考慮VNF間性能干擾的組合放置問題，并根據VNF的修改數據流大小的特性設計了服務鏈請求調度算法，從而減小了VNF間性能干擾，提高了網絡吞吐量。理論分析以及仿真結果表明，該策略較忽視干擾因素的一般策略可將網絡吞吐量提升1.3倍。今后將研究在干擾情況下的動態部署VNF以及如何權衡成本開銷與網絡性能間的關系問題，并將在真實環境中進行實驗以提高結果的準確性。