云邊協(xié)同下的虛擬網(wǎng)絡功能部署和流量調(diào)度方法

楊培星,湯紅波,游 偉,邱 航

1(鄭州大學 網(wǎng)絡空間安全學院,鄭州 450002)

2(中國人民解放軍戰(zhàn)略支援部隊信息工程大學 信息技術研究所,鄭州 450002)

1 引 言

為了滿足多樣化的業(yè)務需求,5G網(wǎng)絡的主要目標之一是支持各個垂直行業(yè)的技術和業(yè)務需求,這些垂直行業(yè)希望為其客戶提供具有不同性能要求的多樣化服務,而NFV已成為提供網(wǎng)絡服務的關鍵支持技術[1].特別是近年來,隨著用戶數(shù)據(jù)流量的空前增長,用戶訪問的網(wǎng)絡服務變得更加多樣化和動態(tài)化,運營商利用網(wǎng)絡服務技術通過部署多個專用的、定制化的、相互隔離的端到端邏輯網(wǎng)絡為垂直行業(yè)提供多樣化服務[2].

傳統(tǒng)的關于網(wǎng)絡服務的資源分配研究大都集中在云數(shù)據(jù)中心中,但大量物聯(lián)網(wǎng)、智能駕駛、工業(yè)物聯(lián)網(wǎng)等業(yè)務的引入,導致對帶寬、時延、安全性等業(yè)務需求越來越嚴苛,傳統(tǒng)云計算的集中部署方式已無法滿足這些業(yè)務需求.因此需要將云中心的高性能計算能力及大規(guī)模存儲能力拓展到網(wǎng)絡邊緣,用來提升網(wǎng)絡質(zhì)量,解決網(wǎng)絡中的時延、安全和擁塞等問題.基于此,MEC[3]應運而生.然而,與核心云相比,邊緣云的資源容量和計算能力有限,因此,在部署網(wǎng)絡服務時要考慮云邊協(xié)同下的資源分配問題.這種場景的一個例子是物聯(lián)網(wǎng)企業(yè)中基于云的托管服務,在物聯(lián)網(wǎng)企業(yè)中,物聯(lián)網(wǎng)設備會產(chǎn)生大量流量,這些流量可以通過位于網(wǎng)絡邊緣的物聯(lián)網(wǎng)網(wǎng)關路由到由多個數(shù)據(jù)中心或互連服務器組成的云環(huán)境.其中,一部分數(shù)據(jù)需要在用戶側(cè)處理來保證低時延、高并發(fā)、大流量等需求,同時,還有一些數(shù)據(jù)需要云端的強大計算能力支持數(shù)據(jù)存儲、模型訓練、大數(shù)據(jù)挖掘等操作[4].因此,根據(jù)物聯(lián)網(wǎng)設備生成的數(shù)據(jù)量和正在交付的網(wǎng)絡服務類型,網(wǎng)絡服務可能跨越云端和邊緣端,云邊協(xié)同[5]下的網(wǎng)絡服務部署模型如圖1所示.

目前關于云邊協(xié)同下的VNF部署研究已經(jīng)成為學術界的熱點問題,并被歸類為NFV中的資源分配問題.如文獻[6]研究如何在云邊協(xié)同下部署VNF并在相鄰VNF對之間進行流量路由,從而使在滿足每個用戶的時延約束下最小化最大鏈路負載率,減小網(wǎng)絡阻塞.其中,服務功能鏈分為完全有序和部分有序兩種,部分有序型服務功能鏈中相互獨立的VNF可以并行處理流量數(shù)據(jù)包以減少傳輸時延.文獻[7]提出根據(jù)不同的業(yè)務目標采取不同的策略來協(xié)調(diào)分配云邊協(xié)同中的虛擬資源(網(wǎng)絡、計算和存儲資源),以滿足垂直行業(yè)的網(wǎng)絡切片要求.文獻[8]提出一種針對邊緣云資源有限問題的VNF動態(tài)資源分配方法.首先將時延敏感型流量請求轉(zhuǎn)發(fā)到邊緣節(jié)點中的原始 VNF,以最大限度地發(fā)揮邊緣計算的優(yōu)勢,達到邊緣節(jié)點的容量限制后,在核心云中部署一個新的VNF實例來分擔流量負載,然后根據(jù)時延約束將時延敏感的流量轉(zhuǎn)發(fā)到邊緣云中,將時延不太敏感的流量轉(zhuǎn)移到核心云.本文基于時延對流量進行分類并將其轉(zhuǎn)發(fā)到不同的云數(shù)據(jù)中心以解決邊緣云資源有限問題,但面對時延敏感型流量實際上僅能保證部分流量的時延約束.

上述工作都在研究云邊協(xié)同下的VNF部署和流量調(diào)度問題,但是由于邊緣云資源容量有限,不僅要考慮將不同類型的VNF類型部署在不同的資源域中,還要考慮多邊緣云間的資源協(xié)調(diào)以及底層網(wǎng)絡中的負載均衡,提高邊緣云的資源利用率.鑒于此,在網(wǎng)絡服務支持流量拆分的場景下,本文提出了一種基于流量拆分的VNF部署和流量調(diào)度方法.流量拆分是指將流量拆分為多條子流并通過多條鏈路傳輸至多個VNF實例中進行處理,每個VNF實例處理每條流量的一部分子流[9-11].通過將流量請求分配到多條路徑和多個節(jié)點可以使全局流量分布的更加均衡,進而減少發(fā)生網(wǎng)絡擁塞和流量請求超時的概率.其中,每條流量請求的拆分條數(shù)以及每條子流的拆分比例是根據(jù)底層網(wǎng)絡的資源狀態(tài)和流量的特性確定的.因此,整個過程包括有效的流量拆分策略、VNF部署策略和流量調(diào)度策略.將網(wǎng)絡服務部署方法分為兩個階段,首先根據(jù)網(wǎng)絡服務中包含的VNF的類型及其位置約束確定VNF在云邊協(xié)同環(huán)境中的部署位置,然后在流量調(diào)度階段引入動態(tài)的流量拆分思想,根據(jù)流量的時延等特性將其拆分成多條子流,并根據(jù)物理節(jié)點間的最短路徑確定虛擬鏈路到物理鏈路的最佳映射.仿真結(jié)果顯示,本文提出的云邊協(xié)同下的VNF部署和流量調(diào)度方法既充分利用MEC減少傳輸時延的優(yōu)勢,提高網(wǎng)絡中的流量請求接受率,又能保證網(wǎng)絡中節(jié)點和鏈路的負載均衡,提高邊緣云中的資源利用率.

2 問題描述和模型建立

2.1 問題描述

本文旨在云邊協(xié)同環(huán)境中部署多個網(wǎng)絡服務,其中每個網(wǎng)絡服務由多個按照一定順序連接的VNF組成,其中每個VNF的實例個數(shù)由最大流量拆分數(shù)I確定.對于底層網(wǎng)絡,無論是核心云還是邊緣云,都由物理節(jié)點和物理鏈路組成,因此,不同的資源域都可以描述為網(wǎng)絡拓撲圖.本文將網(wǎng)絡服務和底層網(wǎng)絡描述為VNF轉(zhuǎn)發(fā)圖和底層網(wǎng)絡圖.因為涉及到云邊協(xié)同,本文的資源分配問題比單一資源域要復雜的多,約束條件主要包括VNF的位置約束、資源約束和流量拆分約束.本文將云邊協(xié)同下的虛擬網(wǎng)絡功能部署問題表述為MILP問題,由于流量拆分策略增加了VNF實例的部署成本,且不同的流量調(diào)度策略會因鏈路成本的不同而產(chǎn)生不同的帶寬成本,因此,本文的最優(yōu)化目標是總資源開銷.

其中需要注意的是,雖然流量拆分方法能夠有效的提高的網(wǎng)絡整體性能解決網(wǎng)絡中的負載均衡問題,但是由于數(shù)據(jù)包遵循不同的路徑,其到達的順序可能有誤,因此需要節(jié)點重新排序數(shù)據(jù)包.本文中,假設利用多路徑傳輸技術Multipath QUIC[12]來處理流量拆分后的數(shù)據(jù)包,該傳輸協(xié)議可以確保來自多個路徑的數(shù)據(jù)包被重新排序,以便按照它們發(fā)送的順序到達應用層,從而保障網(wǎng)絡通信的可靠性和穩(wěn)定速率.

此外,不同類型的VNF在流量處理過程中可能改變用戶的流量大小,例如,添加、刪除和修改數(shù)據(jù)包頭;屏蔽惡意流量;防火墻可以丟棄違反安全策略的傳入數(shù)據(jù)包,從而導致更低的數(shù)據(jù)速率;視頻渲染可以改變流量的編碼,從而導致更高的數(shù)據(jù)速率[13]等操作.因此,在考慮流量調(diào)度的問題時,流量改變率也是應該考慮的因素.

2.2 系統(tǒng)模型

底層網(wǎng)絡模型:底層基礎設施用無向帶權圖Gp=(Cp,Lp)表示,其中Cp表示云節(jié)點集,Lp表示云鏈路集.其中,根據(jù)云節(jié)點所在的位置分為邊緣云Ep?Cp和核心云Op?Cp,且Ep∪Op=Cp.每個云節(jié)點A,B∈Cp上包含多臺服務器,每臺服務器上可以部署多個虛擬機,每個虛擬機僅且運行一個VNF實例.對于任意物理節(jié)點i,ci表示服務器i的計算資源容量,物理節(jié)點之間的物理鏈路(i,j)∈Φ表示為物理節(jié)點i,j所屬的云節(jié)點之間的物理鏈路.每個云節(jié)點包含一個路由器用于流量轉(zhuǎn)發(fā),云節(jié)點之間的物理鏈路表示為兩個云上的路由器之間的物理鏈路.對于任意兩個云節(jié)點之間的物理鏈路(A,B)∈Lp,b(A,B)表示云節(jié)點之間的物理鏈路帶寬,d(A,B) 表示云節(jié)點之間物理鏈路的平均時延,c(A,B)表示云節(jié)點之間物理鏈路的部署成本.本文只考慮云間流量,因為云間鏈路比云內(nèi)鏈路更容易擁塞且成本更高.

流量請求模型:每個流量請求t∈T可以由一個五元組表示,其中i(t)和o(t)分別為服務請求數(shù)據(jù)流量的源節(jié)點和目的節(jié)點,svn(t)為所需的網(wǎng)絡服務類型,w(t)為初始流量速率,d(t)為流量請求的時延約束.此外,流量是可拆分的.

2.3 優(yōu)化目標和約束條件

根據(jù)文獻[14]提出的VNF映射資源開銷計算方法,推導出網(wǎng)絡服務映射的計算資源開銷.在VNF映射過程中,若網(wǎng)絡服務中的VNFμ有a=1,…,m個VNF實例并行處理,則其占用的物理資源開銷如公式(1)所示.其中δμ表示VNFμ部署產(chǎn)生的總物理資源開銷,δμo表示管理和維護VNFμ所需的物理資源開銷,只要服務器節(jié)點部署了VNFμ就會生成該部分開銷,與流經(jīng)該服務器的流量大小無關.δμa表示每個VNF實例μa處理流量請求所需的物理資源開銷.

(1)

(2)

(3)

(4)

約束條件:

資源容量約束:公式(5)和公式(6)表示請求資源與底層物理網(wǎng)絡之間的資源約束關系.其中,公式(5)表示虛擬鏈路和物理鏈路之間的帶寬約束,即對于任何一條云間鏈路,其傳輸?shù)牧髁空埱笏加玫膸捹Y源之和不能超過該云間鏈路的帶寬容量.公式(6)表示VNF和物理節(jié)點之間的資源約束,對于任何一個物理節(jié)點,其承載的VNF所占用的總計算資源不能超過該節(jié)點的計算資源容量.其中公式右側(cè)第1項表示在物理節(jié)點上部署VNF實例所需的計算資源,第2項表示所有VNF實例處理流量請求所需的計算資源開銷.

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

3 算法設計

根據(jù)上述的網(wǎng)絡服務部署模型,云邊協(xié)同環(huán)境下的網(wǎng)絡服務部署可以被認為是一種特殊類型的虛擬網(wǎng)絡映射(VNE)問題,該問題是NP難問題[16],引入流量拆分后,進一步增加了其復雜性.因此,本文設計了一種基于禁忌搜索算法(TS)和遺傳算法(GA)相結(jié)合的聯(lián)合優(yōu)化(TSGA)算法,通過利用禁忌搜索的局部搜索能力和遺傳算法的全局搜索能,得到網(wǎng)絡服務的部署方案.

禁忌搜索算法和遺傳算法各有優(yōu)缺點,雖然兩種算法都可以解決本文研究的在云邊協(xié)同環(huán)境下的網(wǎng)絡服務部署問題,但是僅某一種算法存在依賴于初始解[17]或陷入早熟收斂的問題,因此,兩種算法相結(jié)合可以獲得更好的優(yōu)化效果和更優(yōu)的部署方案.

算法 1 中概述了TSGA算法的偽代碼.引入雙層編碼方法同時實現(xiàn)網(wǎng)絡服務的構建與部署,從初始解nss0開始,將初始解設置為最佳部署方案和當前部署方案nowns.然后通過VNF個體變異和調(diào)整流量拆分比例生成鄰域結(jié)構,再通過迭代來探索鄰域空間.并根據(jù)適應度函數(shù)公式計算出所有鄰域結(jié)構的適應度函數(shù)值生成點序列,然后將最小適應度值所對應的部署方案設為最佳候選集nextns.若最佳候選解nextns的適應度值小于全局最優(yōu)解bestns的適應度值,則將nowns和bestns全部替換為nextns,并將其對應的部署方案nextns作為禁忌對象替換最早進入禁忌表的禁忌對象.否則,判斷候選解中各部署方案的禁忌屬性,即是否在禁忌表中.將候選解集中非禁忌對象對應的最佳候選解設為新的nowns,并用nowns替換最早進入禁忌表的禁忌對象元素,以幫助局部搜索過程擺脫局部最優(yōu).但是最佳部署方案bestns保持不變.為了避免陷入局部最優(yōu)并再次循環(huán)到之前已經(jīng)選擇過的部署方案,將已經(jīng)選擇過的部署方案儲存在禁忌列表中,阻止在一定的迭代次數(shù)內(nèi)移動到之前已經(jīng)選擇過的部署方案.但是,如果這些移動產(chǎn)生的部署方案得到的適應度值比迄今為止所有的適應度值都要小,那么仍然可以選擇此適應度值所對應的部署方案,這種情況稱為特赦準則.重復以上過程,直到滿足迭代次數(shù)時終止算法循環(huán).接下來將詳細介紹TSGA算法的組成部分.

算法1.基于禁忌搜索算法和遺傳算法的網(wǎng)絡服務部署算法

輸入：底層網(wǎng)絡參數(shù):底層網(wǎng)絡拓撲圖Gp=(Cp,Lp);網(wǎng)絡服務參數(shù):網(wǎng)絡服務拓撲圖Sv=(Nv,Ev);流量請求參數(shù):五元組.

輸出：最優(yōu)部署方案bestns,適應度函數(shù)值fitnessvalue

1. 設置禁忌列表tabu,迭代次數(shù)num,鄰域結(jié)構長度length,適應度函數(shù)fitness;

2. 初始解:根據(jù)輸入?yún)?shù)隨機生成網(wǎng)絡服務初始部署方案nss0;

3. 將nss0設置為當前部署方案nowns和最佳部署方案bestns;

4. for q=1:sq_num //計算適應度函數(shù)值fitnessvalue

5. 根據(jù)流量的服務類型計相對應網(wǎng)絡服務的部署位置確定流量所經(jīng)過的節(jié)點順序,并計算每條子流的總時延delayns1,delayns2

6. if delayns1<=delayns2

7. delayns=delayns2;

8. else

9. delayns=delayns1;

10. end //計算流量總時延delayns

11. if delayns>latency(q) OR 節(jié)點資源容量和鏈路帶寬容量不能滿足所需資源

12. 流量請求處理失敗;

13. else

14. 計算次流量請求所需總資源開銷,更新節(jié)點和鏈路的剩余資源;

15. end

16. 計算所有流量請求所需的總資源開銷與適應度函數(shù)值;

17. end

18. fork=1:num//迭代尋優(yōu)

19. 根據(jù)nowns利用遺傳算法的交叉和變異操作生成鄰域結(jié)構linyu;

20. 根據(jù)鄰域結(jié)構linyu和禁忌列表tabu生成當前鄰域linyu的點序列函數(shù)select;

21. 計算當前點序列select的適應度函數(shù)值,得到適應度序列;

22. 找出適應度最小值以及其所對應的部署方案nextns;

23. if fitness(nextns)≤fitness(bestns) //滿足特赦準則

24. 將nextns設置為nowns和bestns,并更新禁忌列表tabu;

25. else

26. 從鄰域的非禁忌對象中找出適應度最小值以及其所對應的部署方案nextns;

27. 將nextns設置為nowns,并更新禁忌列表tabu;

28. end;

29.k=k+1;

30.end

31.獲得最優(yōu)部署方案bestns及其適應度函數(shù)值;

3.1 初始解

本文根據(jù)每條流量中可以拆分的最大子流數(shù)來生成初始解,且將該初始解設置為TSGS算法的起點.下面只介紹無流量拆分時的初始解nss1,nss1可以很容易的擴展到最大子流數(shù)為2或3時的初始解nss2和nss3.

首先采用十進制整數(shù)編碼方式同時對網(wǎng)絡服務的構建與部署進行雙層編碼,長度為網(wǎng)絡服務中所包含VNF類型的兩倍.如圖2所示的一個網(wǎng)絡服務編碼,前5位為網(wǎng)絡服務的構建編碼,不同的數(shù)字代表不同的VNF類型,從左至右的順序代表VNF之間流量轉(zhuǎn)發(fā)的方向;后5位為網(wǎng)絡服務的部署編碼,分別對應前5位VNF類型部署的節(jié)點位置,VNF的部署位置需要滿足VNF類型的位置約束和所部屬節(jié)點的資源約束,例如本網(wǎng)絡服務中VNF類型1部署于底層物理網(wǎng)絡中7號物理節(jié)點.解碼時,首先根據(jù)網(wǎng)絡服務的構建編碼計算每個VNF實例所需的部署資源開銷和VNF之間所需的帶寬資源開銷,然后根據(jù)部署編碼在底層基礎設施中的最短路徑集合Link查找物理節(jié)點之間的流量轉(zhuǎn)發(fā)路徑,并判斷物理鏈路上的剩余帶寬是否滿足帶寬資源需求,如果不能滿足,則刪除該物理鏈路,接著在最短路徑集合Link中重新計算這兩個物理節(jié)點之間的物理鏈路.這種計算物理鏈路的方式能夠減少部署節(jié)點之間轉(zhuǎn)發(fā)路徑的計算次數(shù),提高解碼效率.然后將此初始解nss1設置為最佳部署方案bestns和當前部署方案nowns.

3.2 鄰域結(jié)構

TSGA算法基于遺傳算法中的交叉和變異操作用兩種種方法生成鄰域結(jié)構:第1個是VNF個體變異,旨在擴大算法的搜索范圍,避免陷入局部最優(yōu)解;第2個是流量拆分比例調(diào)整,旨在重新調(diào)整流量請求中每條子流的拆分比例.

VNF個體變異:由于網(wǎng)絡服務中流量轉(zhuǎn)發(fā)路徑是定向的,因此網(wǎng)絡服務的構建編碼部分是固定的,因此VNF個體變異指的是網(wǎng)絡服務的部署編碼部分的變異策略.且變異策略只考慮節(jié)點,不考慮鏈路,在網(wǎng)絡服務中隨機選擇一個VNF,然后根據(jù)其資源約束和位置約束隨機分配給另一個候選物理節(jié)點,然后在最短路徑集合Link查找滿足帶寬約束的流量轉(zhuǎn)發(fā)路徑.

動態(tài)流量拆分:動態(tài)流量拆分指各個子流的拆分比例是根據(jù)可用資源和時延約束動態(tài)調(diào)整的,而不是固定值.從需要流量拆分的流量請求中隨機選擇一條流量請求t∈T,然后從該流量請求的多個子流中隨機選擇其中兩條子流,然后調(diào)整這兩條子流之間的流量拆分比例,使這兩條子流的流量總和保持不變.為了處理分流比變量的連續(xù)性,假設流量被拆分為m個離散單元.例如,假設選擇了第I條子流,并且其最大子流數(shù)為3,每條子流I1、I2、I3處理的流量單元分別為m1、m2和m3,其中m1+m2+m3=m.首先隨機從3條子流中選擇2個,假設是I1和I3.然后選擇一個介于 1 和(m2+m3)之間的隨機數(shù),假設是n.最后,將I1和I3處理的流量分別調(diào)整為n和(m1+m3-n).

3.3 禁忌列表

為避免重復選擇同一種部署方案以及避免局部最優(yōu)解,TSGA算法將接受的候選解的移動聲明為“禁忌”并在一定次數(shù)的迭代內(nèi)將其存儲在禁忌列表中.此外,該算法禁止選擇存在于禁忌列表中的部署方案,除非該移動產(chǎn)生的部署方案的適應度函數(shù)值優(yōu)于最優(yōu)部署方案(bestns)的適應度函數(shù)值.

3.4 鄰域評估和特赦準則

在每次迭代中,TSGA算法評估整組鄰域結(jié)構的部署方案,然后選擇其中一個設置為當前部署方案.TSGA算法使用公式(17)中的適應度函數(shù),在評估鄰域結(jié)構中的候選部署方案時,適應度函數(shù)是部署成本和流量請求接收數(shù)的加權和,適應度函數(shù)值越小越好.其中,cost(ε)是網(wǎng)絡服務的總資源開銷,包括網(wǎng)絡服務部署所需的資源開銷以及用于流量處理所需的資源開銷;amod是流量請求未接受數(shù)量n(t)的權重,n(t)定義為有多少流量請求未被成功處理,本部分是為了獎勵滿足所有流量請求的鄰域選擇,尤其是時延約束.

fitness=cost(ε)+amodn(t)

(17)

在每次迭代中,在計算完生成的鄰域結(jié)構中的所有部署方案的適應度函數(shù)值后,對所有的鄰域評估結(jié)果進行序列排序.如果其最小適應度值優(yōu)于當前部署方案的適應度值且沒有存儲于禁忌列表中,則將此部署方案替換為當前部署方案;如果此部署方案存儲于禁忌列表中,但是其適應度值小于最小適應度值,則依然將此部署方案替換為當前部署方案,因為滿足了特赦準則.

3.5 停止準則

TSGA算法在達到最大迭代次數(shù)后終止.在仿真實驗過程中,不斷調(diào)整迭代次數(shù),以便在部署方案質(zhì)量和代碼執(zhí)行時間之間找到一個平衡.

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

本節(jié)通過仿真實驗驗證了本文所提出的聯(lián)合算法的有效性,并將本文提出的TSGA算法與文獻[4]中采用的TS算法和文獻[18]中采用的輪詢算法(Round Robin,RB)進行對比,驗證多個流量請求到達情況下算法求解出的網(wǎng)絡服務部署方案的有效性.每種對比算法運行10次,實驗結(jié)果取平均值.文獻[4]的最優(yōu)化目標是部署成本與總時延的加權之和,并用TS算法解決網(wǎng)絡服務的部署問題.選擇這個算法的原因是因為它的物理場景與本文相似,都是在云邊環(huán)境中部署多種類型的網(wǎng)絡服務.文獻[18]利用RB算法和最短路徑算法聯(lián)合實現(xiàn)VNF的部署,通過在互相靠近的物理節(jié)點上部署VNF從而最小化端到端時延.選擇這個算法的原因是因為它的目標函數(shù)是最小化整體時延,與本文降低通信時延的目標相似.

4.1 實驗環(huán)境與參數(shù)設置

為了驗證TSGA算法的性能,本文在配置為Intel Core i7-6700 CPU、16GB內(nèi)存、1T硬盤的臺式機算上使用MATLAB R2021A進行仿真試驗.仿真環(huán)境中使用的云邊協(xié)同的網(wǎng)絡拓撲由GT-ITM工具生成,底層物理基礎設施由3個核心云與17個邊緣云組成,其中每個核心云的計算容量為8Gbps,每個邊緣云的計算容量為2Gbps,且每個云都有一個路由器僅用于本云內(nèi)所有流量的轉(zhuǎn)發(fā).邊緣云之間兩個方向的鏈路帶寬設置為2Gbps,邊緣云與核心云之間的鏈路帶寬設置為8Gbps,每條鏈路的單位流量成本在0.1～0.4/Mbps之間.關于鏈路傳輸時延,本文采用與文獻[18]類似的方法,根據(jù)VNF的部署約束選擇部署位置,假設邊緣云之間的傳輸時延為1ms,邊緣云和核心云之間的傳輸時延為3ms,兩個核心云之間的傳輸時延為5ms.

參考文獻[4]中的仿真參數(shù),設定底層物理網(wǎng)絡可接受的最大流量請求數(shù)為100,平臺中可實例化的VNF類型數(shù)量為10(其中4種VNF必須部署于邊緣云中,2種必須部署于核心云中,剩余4種可以根據(jù)部署于任何一類云中),每個網(wǎng)絡服務包含的VNF數(shù)量不超過5.實驗中所需的VNF類型及其相關參數(shù)如表1所示,其中規(guī)定了不同類型VNF的流量改變率raf,每Mbps帶寬所需的計算資源uf和位置約束(p(μ)=1表示該VNF必須部署在核心云中;p(μ)=-1表示該 VNF必須部署在邊緣云上;p(μ)=0表示“不關心”情況,可以部署在任何一個云中).

表1 VNF類型及參數(shù)Table 1 VNF types and parameters

本實驗中共部署6種類型的網(wǎng)絡服務,每個網(wǎng)絡服務的網(wǎng)絡拓撲已提前確定,包括所需的VNF類型以及它們之間的順序,且每個網(wǎng)絡服務根據(jù)其服務類型處理一定數(shù)量的流量請求.假設每條流量請求根據(jù)其所需服務類型選擇接入特定的網(wǎng)絡服務,每條流量請求是一組數(shù)據(jù)包,每個流量請求的源節(jié)點和目的節(jié)點在邊緣云節(jié)點上的路由器之中隨機選擇.實驗結(jié)果的每個數(shù)據(jù)為運行10次取平均值,接下來討論仿真結(jié)果并進行分析.

4.2 算法性能與評估

首先,驗證TSGA算法的收斂性和有效性,設置流量請求數(shù)為100,禁忌列表長度為200,迭代次數(shù)為200.

圖3為最大子流數(shù)對流量請求接受數(shù)量的影響.從圖中可以看出,當I=1,I=2,I=3時,最大流量請求接受數(shù)量分別為81.6,94.1和96.7.采用動態(tài)的流量拆分方法,流量請求完成率提高了12.5%.這是因為將流量請求拆分成多條獨立的子流,不僅可以解決底層網(wǎng)絡中鏈路的負載均衡問題減少網(wǎng)絡擁塞的概率,還可以利用VNF并行處理方法讓多個節(jié)點共同分擔流量數(shù)據(jù)包避免因物理節(jié)點過載而造成流量請求超時.通過流量拆分來降低節(jié)點的資源利用率來降低節(jié)點處理時延,從而滿足流量請求嚴格的時延約束.但是,對于I=2和I=3,流量拆分數(shù)增加,流量成功率提升了2.6%,即增大流量拆分數(shù)對流量請求接受數(shù)量的影響力有限.這是因為I的值并不意味著流量總是被分成I條獨立的子流,只要滿足流量請求的時延約束流量就不會被進一步拆分,因此一味的增大最大子流數(shù)不一定就會得到更好的部署效果.從圖中還可以看出,將流量拆分數(shù)設置為2就可以滿足場景中大多數(shù)流量請求的時延約束.

圖3 最大子流數(shù)對流量請求接受數(shù)量的影響Fig.3 Effect of the maximum number of substreams on the number of traffic requests accepted

圖4為最大子流數(shù)對流量請求平均資源開銷的影響.從圖中可以看出,I值越大,流量請求的平均資源開銷越高.主要原因為,為了滿足更多流量請求的時延要求,就要增加子流數(shù)以降低總通信時延,然而增加子流數(shù)也意味著增加VNF實例數(shù)以及不同的鏈路帶寬開銷.與圖3類似,I=1和I=2時最優(yōu)解的性能之間有比較大的差距,I=2和I=3時最優(yōu)解的性能近似相同.從圖3,圖4中可以看出I=2時即可接收場景中94%的流量請求,且繼續(xù)增加流量拆分數(shù)對流量請求接受率的提升空間較小,同時I值越大,算法的執(zhí)行時間越長,已接受的流量請求的平均資源開銷也越大.因此下文中將TSGA算法與TS算法和RB算法進行對比時,選取I=2.

接下來驗證同時處理多個流量請求時3種算法求解出的網(wǎng)絡部署方案的有效性,為了增強對比效果,設置流量請求數(shù)為200.圖5為不同流量請求數(shù)量下的適應度值對比,可以看出,TSGA算法的解決方案更好,RB算法的解決方案最差,TS算法居中,較接近于RB算法.主要原因為:RB算法沒有考慮到物理節(jié)點和物理鏈路的可用資源和性能的差異性,雖然更為簡潔,但是容易導致節(jié)點間的負載不平衡和網(wǎng)絡阻塞.與TS算法相比,在鄰域結(jié)構的構建上,TSGA算法在鄰域結(jié)構的構建上加入遺傳算法的交叉因子和變異因子,增加鄰域結(jié)構的隨機性和多樣性,且流量拆分策略克充分利用底層網(wǎng)絡中的碎片化資源處理和傳輸流量請求,因此在相同的場景中可以找到更優(yōu)的部署方案.

圖5 不同流量請求數(shù)量下的適應度值Fig.5 Fitness values under different traffic request numbers

圖6為不同流量請求數(shù)量下的流量請求接受率,初始資源充足,流量請求接受率都為1,隨著流量請求接收數(shù)量的增大,曲線出現(xiàn)不同趨勢的下降.其中,TSGA算法在流量請求為60時開始出現(xiàn)接受率下降的情況,即此時出現(xiàn)流量請求拒絕的現(xiàn)象,比TS算法和RB算法開始下降分別多了20和40個流量請求數(shù).且TSGA算法的流量請求接受率一直高于其他兩種算法,當流量請求數(shù)量為200時,TSGA,TS和RB算法的流量請求接受率分別為42.6%,34.9%和29.7%,相比之下,TSGA算法的流量請求接受率高于TS算法7.7%左右,高于RB算法12.9%左右.主要原因為:TS算法和RB算法都是采用靜態(tài)的流量拆分策略和相對僵化的鄰域結(jié)構選擇方法,在大流量場景中,靜態(tài)的流量拆分策略降低了對底層網(wǎng)絡中資源分配的靈活性,同時僵化的鄰域結(jié)構方法容易使算法陷入局部最優(yōu)解.相比之下,TSGA算法在鄰域結(jié)構的構建上,加入遺傳算法的交叉因子和變異因子,增加鄰域結(jié)構的隨機性和多樣性,從而跳出局部最優(yōu)解找到更優(yōu)的部署方案.且動態(tài)的流量拆分策略保證了網(wǎng)絡中的負載均衡,通過均衡每個節(jié)點的資源利用率減小節(jié)點處理時延,從而滿足更多流量請求的時延約束,進而增加了流量請求接受率.

圖6 不同流量請求數(shù)量下的流量請求接受率Fig.6 Traffic request acceptance rate under different traffic request numbers

圖7為不同數(shù)量流量請求下處理完成的流量請求的平均資源開銷,從圖中可以看出,TS算法和RB算法的平均資源開銷分別收斂于2.14和2.19,而TSGA算法的平均資源開銷收斂于2.03,相比于TS算法和RB算法降低了近似5.4%和7.8%.其中,流量請求數(shù)量較小時,其平均資源開銷較大,隨著流量請求數(shù)量的增加,平均資源開銷逐漸降低,后期流量請求接受數(shù)量逐漸趨于飽和,平均資源開銷也無下降空間.主要原因為:初始無資源競爭,平均資源開銷對流量請求接受率影響有限,但是,流量請求較大時,要想在有限資源下接受盡可能多的流量請求,需要每條流量請求都以最小的資源開銷滿足流量請求的位置約束,資源約束和時延約束,因此需要尋找更優(yōu)的網(wǎng)絡服務部署和流量路由方法以減小平均資源開銷,從而接受更多的流量請求.

圖7 不同流量請求數(shù)量下的平均資源開銷Fig.7 Average resource overhead under different traffic request numbers

5 結(jié) 論

傳統(tǒng)的關于網(wǎng)絡服務的資源分配研究大都集中在云數(shù)據(jù)中心中,但物聯(lián)網(wǎng)、智能駕駛、工業(yè)物聯(lián)網(wǎng)等業(yè)務的大量引入,導致對帶寬、時延、安全性等業(yè)務需求越來越嚴苛.傳統(tǒng)云計算的集中部署方式已無法滿足這些業(yè)務需求,因此需要將部分VNF下沉至網(wǎng)絡邊緣以降低網(wǎng)絡時延,減少網(wǎng)絡阻塞的壓力.然而,與核心云相比,邊緣云的資源容量收到很大限制,因此,不僅要考慮將不同類型的VNF部署在不同的資源域中,還要考慮多邊緣云間的資源協(xié)調(diào)以及底層網(wǎng)絡中的負載均衡,避免邊緣云節(jié)點過載造成流量超時或鏈路過載出現(xiàn)網(wǎng)絡擁塞等問題.所以,在云邊協(xié)同場景下部署網(wǎng)絡服務,如何有效地利用核心云和邊緣云各自的優(yōu)勢實現(xiàn)VNF的部署和流量調(diào)度是本文要解決的問題.本文提出了一種動態(tài)的流量拆分策略進行靈活的流量調(diào)度,根據(jù)流量的時延約束將其拆分成多條子流,并利用網(wǎng)絡中的碎片化資源提高流量請求接受率.本文將云邊協(xié)同下的虛擬網(wǎng)絡功能部署和流量路由問題描述為混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)問題,并提出了一種基于禁忌搜索算法和遺傳算法的聯(lián)合優(yōu)化(TSGA)算法,仿真結(jié)果表明,動態(tài)的流量拆分策略可以靈活優(yōu)化全局網(wǎng)絡,利用網(wǎng)絡中的碎片化資源提高流量請求接受率,但當流量請求接受率達到一定值時,繼續(xù)增加流量拆分數(shù)對流量請求接受率的提升空間較小.而且,本文提出的TSGA算法與TS算法和RB算法相比可以分別提高7.7%和12.9%的流量請求接受率,并分別減少5.4%和7.8%的流量平均開銷.