面向時延敏感業(yè)務的服務功能鏈部署

趙東成，謝景昭，孫 罡

（電子科技大學光纖傳感與通信教育部重點實驗室 成都 611731）

服務時延一直是服務部署中的一個重點研究問題，研究人員也對減小服務時延進行了大量的研究。目前，對于減小服務時延的研究主要分為兩個方面。1） 一方面的研究是考慮減少數(shù)據(jù)包的處理、排隊和轉發(fā)的時延，但由于受制于云網絡的容量和設備自身的處理能力和處理速度，這方面研究的提升空間有限。因此，文獻[1-5]指出除了減少數(shù)據(jù)包的處理、排隊和轉發(fā)時延外，通過將服務功能鏈（service function chain, SFC）部署在更合理的物理路徑上，從而減少對鏈路資源的消耗和部署路徑的傳播時延，也能有效地降低服務功能鏈的整體時延。2） 此外，服務卸載和霧計算為應對云網絡的資源消耗和時延問題提供了新的范例。然而，目前關于服務卸載的研究大多考慮將正在運行的計算服務從移動手機或云網絡卸載到霧網絡。目前，在云-霧網絡中，利用服務卸載來部署服務功能鏈的研究還不夠深入。

因此，本文考慮在部署服務功能鏈時，通過有效的在線博弈決策，將每個服務功能鏈的一部分虛擬網絡功能卸載和部署到霧網絡中，從而降低對云網絡的資源需求和縮短SFC 的部署路徑的長度，進而減小SFC 的路徑時延。本文提出了一種基于服務卸載和在線博弈的最小化時延的SFC 部署算法（elay-minimum service function chain deploying of services offloading and online game, DSFCD-SOOG），該算法結合有效的在線博弈和服務卸載決策，在云-霧網絡中部署SFC，以減少SFC 的端到端時延。最后，驗證了DSFCD-SOOG 算法在SFC 部署中的部署成本、SFC 的路徑時延和部署成功率方面的優(yōu)越性。

1 相關工作

隨著互聯(lián)網的發(fā)展，傳統(tǒng)網絡的僵化問題越來越嚴重，研究人員提出了網絡功能虛擬化技術[6-10]。隨著越來越多的網絡用戶接入，集中式的云網絡面臨著巨大的挑戰(zhàn)，這也給服務功能鏈的部署帶來了困難。為了解決這些挑戰(zhàn)，分布式的霧/邊緣計算應運而生[11-13]。該計算可以使接入網擁有少量的計算資源，利用這些資源可以為一些小型業(yè)務提供計算資源，從而降低對云網絡資源的需求。

為了更加靈活地利用接入網的霧計算資源，研究人員提出對接入網的霧計算資源進行切片和虛擬化。然后，將服務功能鏈中的一部分虛擬網絡功能卸載并部署到接入網中，使得虛擬網絡功能的部署更加靈活，同時也能有效地降低服務功能鏈的整體時延。計算卸載能夠靈活地利用霧計算資源，成為了一個新的研究熱點[14-15]，它們考慮將一些云計算服務卸載到邊緣網絡上，從而降低云計算的流量負載，滿足用戶相應的需求。

服務時延一直以來都是服務提供商和用戶所關心的一個重要問題。在數(shù)據(jù)包的處理、排隊和轉發(fā)時延難以改善時，通過將服務功能鏈部署在更加合理和更短的物理路徑上，減少對鏈路資源的消耗和部署路徑的傳播時延，進而降低服務功能鏈的整體時延也是研究人員關注的問題。因此，在面對時延敏感業(yè)務的服務功能鏈部署問題時，有效地減小部署路徑的傳播時延也是研究的重要方向。因此，本文研究了具有時延需求的用戶到用戶的服務功能鏈的部署問題，通過將服務卸載和云-霧網絡的資源調度相結合以降低服務功能鏈的時延。

2 問題定義和數(shù)學建模

本節(jié)給出了具有時延需求的用戶到用戶的SFC 請求，以及由霧接入網和云網絡組成的物理網絡，研究假設每條物理鏈路都有一個時延約束，每個用戶到用戶的SFC 請求都有一個整體時延需求。在知道各條物理鏈路時延約束的前提下，通過服務卸載和聯(lián)合調度云-霧計算的資源，解決用戶到用戶的服務功能鏈的最小化時延和資源效率的配置問題。

2.1 物理網絡

在本文中，物理網絡由多個分布式的霧無線接入網和集中式的云網絡組成。將物理網絡建模為無向加權圖GP= （NP,EP），其中NP={n1,n2, ···,n|NP|}定義為所有物理節(jié)點（如服務器和路由器）的集合，|NP|表示物理節(jié)點的數(shù)量。EP={l1,l2, ···,l|EP|}定義為所有物理鏈路的集合，|EP|表示物理鏈路的數(shù)量。本文定義RC=（CN,CE,LN）為物理網絡資源約束的集合，其中CN表示物理節(jié)點的屬性（如服務器資源的 容 量c（nk）和 服 務 器 資 源 的 單 位 成 本p（nk））。CE表示物理鏈路的屬性（如時延d（lj）、帶寬的容量b（lj）和 鏈 路 資 源 的 單 位 成 本p（lj））。LN={L（n1）,L（n2） ,···,L（n|NP|）}表示所有物理節(jié)點位置的集合。

2.2 用戶到用戶的SFC 請求

本文將具有時延需求的用戶到用戶的SFC 請求建模為無向加權圖GR= （NR,ER），其中，NR={f1,f2, ···,f|NR|}表示用戶到用戶的SFC 請求中所有虛擬網絡功能（virtual network function, VNF）的集合，|NR|表示SFC 請求中所有VNF 的數(shù)量。ER={e1,e2, ···,e|ER|}表示所有SFC 鏈路的集合，|ER|表示所有SFC 鏈路的數(shù)量。定義MC=（CN,CE,CD,LN,LU1,LU2）為部署約束，其中，CN={ε（f1）, ε（f2） ,···, ε（f|NR|）}表示SFC 請求中所有VNF 的計算資源需求的集合，CE={ε（e1）, ε（e2） ,···, ε（e|ER|）}表示所有SFC 鏈路的帶寬資源需求的集合，CD表示托管SFC 請求的物理路徑的可容忍的總體傳輸時延，LN={L（f1）L（f2） ,···,L（f|NR|）}描述了所有VNF 的位置約束的集合。由于接入網中的霧計算資源相對稀缺，本研究只允許每個SFC 請求使用自身用戶所在的接入網的霧計算資源。因此，每個SFC 請求的VNF 只能部署到用戶所在的云網絡或霧接入網中。LU1和LU2分別表示兩個用戶的位置。

2.3 部署SFC 的網絡模型

在用戶到用戶的服務功能鏈的部署過程中，本研究的重點是部署VNF 和SFC 的虛擬鏈路。首先，本文將VNF 的部署過程建模為：

本文在部署VNF 的同時部署SFC 鏈路，將SFC 鏈路的部署過程建模為：

2.4 基于性別大戰(zhàn)的在線博弈的SFC 部署模型

將上述博弈過程建模為BoS 模型，在這個模型中，有兩個參與者（包括接入網的總計算資源Rg與剩余計算資源rg的比例Rg/rg和云網絡的總計算資源Rc與剩余計算資源rc的比例Rc/rc）有一些共同的興趣，但是共同利益的結果不同，并且有相對沖突的偏好。該模型基于兩種策略：1）將虛擬網絡功能卸載并部署到接入網中；2）將虛擬網絡功能部署到云網絡中。這兩種策略是給定并為玩家預知的。

因此，將每個VNF 的部署過程看作是一個博弈過程，接入網的總計算資源Rg與剩余計算資源rg的比例Rg/rg和云網絡的總計算資源Rc與剩余計算資源rc的比例Rc/rc作為兩個參與者進行博弈，決定是否將VNF 卸載并部署到接入網中。將VNF卸載并部署到接入網作為第一策略（即S1），將VNF部署到云網絡中作為第二策略（即S2），Rg/rg作為第一玩家（即P1），Rc/rc作為第二個玩家（即P2），博弈策略如表1 所示。

表1 用于服務卸載的博弈策略

3 算法設計

由于具有時延需求的用戶到用戶的服務功能鏈的部署是一個NP 問題，整數(shù)線性規(guī)劃很難快速地得到解決方案。為解決這一難題，基于BoS 在線博弈的SFC 部署模型，本文設計了一個基于服務卸載和在線博弈的最小化時延的SFC 部署算法（DSFCD-SOOG），聯(lián)合調度云計算和霧計算的資源，解決用戶到用戶的SFC 的最小化時延和資源效率的部署問題。DSFCD-SOOG 算法如算法1 所示。

算法1：基于服務卸載和在線博弈的最小化時延的SFC 部署算法（DSFCD- SOOG）

輸入：物理網絡GP= （NP,EP）和資源約束RC =（CN,CE,LN）

SFC 請求隊列QueuedSFC

2） 如果QueuedSFC≠?，就執(zhí)行下一步；否則，轉到步驟9）；

3） 根據(jù)LeavedSFC，更新LeavedSFC 和物理網絡資源，讓LeavedSFC=?，執(zhí)行下一步；

4） 調 用SDSFCD-SOOG 子 算 法 來 映 射 隊 列QueuedSFC 中的第一個SFC 請求SFC1，執(zhí)行下一步；

5） 如果找到SFC1的一個部署方案M，就執(zhí)行下一步；否則，轉步驟7）；

DSFCD-SOOG 算法展示了將隊列QueuedSFC中所有到達的用戶到用戶的SFC 請求部署到物理網絡中的過程。當本文部署每個SFC 請求時，本研究調用SDSFCD-SOOG 子算法來部署SFC，如子算法1 所示。在部署每個SFC 請求時，本研究首先將用戶U1所在的霧接入網中的所有物理服務器存儲到UG中，然后將用戶U2所在的霧接入網中的所有物理服務器存儲到UG中，再將云網絡中所有物理服務器存儲到UC中，最后部署SFC 請求的每個VNFfi。

子算法1：單個SFC 請求的部署算法

輸入：一個SFC 請求GR= （NR,ER）和部署約束MC = （CN,CE,CD,LN,LU1,LU2）

輸出：部署方案M

1） 將用戶U1和用戶U2所在的霧接入網中的所有可用物理服務器儲存在UG中，將云網中的所有可用物理服務器儲存在UC中；

2） 遍歷NR中的每一個VNFfi，如果NR中的每一個VNF 已經遍歷完，就轉步驟14），否則執(zhí)行下一步；

3） 遍歷UG中的每個物理服務器nj∈UG，如果UG中的服務器已經遍歷完，就轉步驟7），否則執(zhí)行下一步；

4） 如果物理服務器nj滿足VNFfi的位置約束，執(zhí)行下一步，否則就轉步驟3）；

5） 嘗試將fi映射到服務器nj上，并根據(jù)公式（8）計算成本VNFCost（fi→nj），執(zhí)行下一步；

6） 找到鏈路ei的最小時延路徑pei和找到從服務 器nj到 用 戶U2的 最 小 時 延 路 徑pi+1（nj,LU2），根據(jù)式（3）和式（9）計算路徑pei的時延PathDelay（pei）和部署成本PathCost（pei），根據(jù)式（4）和式（10）計算路徑pi+1（nj,LU2）的路徑時延PathDelay（pi+1（nj,LU2））和部署成本PathCost（pi+1（nj,LU2）），根據(jù)式（11）和式（12）計算和記錄fi的總路徑時延TDelay（fi→nj）和總部署成本TCost（fi→nj），轉至步驟3）；

7） 從VNFfi在霧接入網中的所有部署方案中找到一個總路徑時延TDelay（fi→nj）最小的部署方案M（fi）和M（ei），執(zhí)行下一步；

8） 遍歷UC中的每個物理服務器nk∈UC，如果UC中的服務器已經遍歷完，就轉步驟12），否則執(zhí)行下一步；

9） 如果物理服務器nk滿足VNFfi的位置約束，執(zhí)行下一步，否則就轉步驟8）；

10） 嘗試將fi映射到服務器nk上，并根據(jù)式（8）計算部署成本VNFCost（fi→nk），執(zhí)行下一步；

12） 從虛擬網絡功能fi在云網絡中的所有部署方案中找到一個總路徑時延TDelay（fi→nk）′最小的部署方案M（fi）′和M（ei）′，執(zhí)行下一步；

13） 找到最小總時延的純策略納什均衡點作為聚點均衡點，并將部署方案存儲在M中，轉至步驟2）；

14） 找到最后一條鏈路e|ER|的最小時延路Pe|ER|并存儲在M中，根據(jù)式（2）計算總部署成本TCost（M）；

15） 返回M和TCost（M）。

本文將虛擬網絡功能fi部署到接入網的物理服務器nj上的部署成本定義為VNFCost（fi→nj）：

同時，當虛擬網絡功能fi被部署到接入網中的物理服務器nj上時，可以找到從服務器nj到用戶U2的 部 署 路 徑pi+1（nj,LU2）。將 物 理 路 徑pi+1（nj,LU2）的部署成本定義為PathCost（pi+1（nj,LU2））：

當虛擬網絡功能fi部署到接入網中的物理服務器nj上時，可以計算出總路徑時延TDelay（fi→nj）和總部署成本TCost（fi→nj），分別為：

SDSFCD-SOOG 子算法中部署方案M的總部署成本TCost（M）和總的部署時延TDelay（M）由式（1）和式（2）可計算得出。

4 仿真實驗與結果分析

4.1 仿真環(huán)境

為了解決用戶到用戶的服務功能鏈的最小化時延和資源有效的配置問題，本文考慮聯(lián)合調度云計算和霧計算的資源，因此物理網絡由多個分布式的霧無線接入網和集中式的云網絡組成。圖1 所示為霧無線接入網。本文使用有46 個節(jié)點和76 條鏈路的USANET 網絡作為云網絡，如圖2 所示。在本文的仿真中，有15 個霧無線接入網連接到USANET網絡中的黑色節(jié)點。

圖1 霧無線接入網

圖2 USANET 網絡

在本仿真中，假設云網絡中物理服務器的計算資源服從均勻分布U[50, 80]個CPU 核心，霧無線接入網中物理服務器的計算資源服從均勻分布U[20, 40]個CPU 核心，物理鏈路的帶寬資源服從均勻分布U[40, 60]單位。一般情況下，本文假設：1）霧接入網和云網絡的計算資源的單位成本服從均勻分布U[0.5, 1]元；2）云網絡的帶寬資源的單位成本服從均勻分布U[1, 1.5]元；3）霧接入網的帶寬資源的單位成本服從均勻分布U[0.1, 0.2]元；4）每條物理網絡鏈路的帶寬資源的單位成本與鏈路長度成正比，每條物理網絡鏈路的傳輸時延與鏈路長度成正比，因此本文假設每條物理鏈路的傳輸時延服從均勻分布U[0.1, 0.2]ms。

另外，當用戶到用戶的SFC 請求中的VNF 數(shù)量n=8 時，本文每次仿真10 000 個用戶到用戶的SFC 請求的結果。假設這些用戶到用戶的SFC 請求按照泊松過程動態(tài)到達，每個SFC 請求中每個VNF 的計算資源需求服從均勻分布U[5, 10]個CPU 核心，一個用戶到用戶的SFC 請求中所有虛擬鏈路的帶寬資源需求相同，但各個用戶到用戶的SFC 請求的帶寬資源需求服從均勻分布U[5,10]Gbps。

本文通過對比在云網絡的部署方案和在霧網絡的部署方案，論證了云計算與霧計算資源聯(lián)合調度在減少用戶到用戶的SFC 請求的路徑時延方面的優(yōu)勢，對比了文獻[14]和文獻[15]中提出的SFC部署算法，即PSECO 算法和SAMA 算法。PSECO算法用于將SFC 請求卸載并部署到接入網，而SAMA 算法用于將SFC 請求部署到云網絡中。

4.2 仿真結果與分析

圖3 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 路徑時延。從結果可以看出，本文DSFCD-SOOG 算法的平均SFC 路徑時延低于PSECO 算法和SAMA 算法。這是因為本文的主要優(yōu)化目標是最小化路徑時延，在部署每個虛擬網絡功能fi時，聯(lián)合調度云計算和霧計算資源，解決用戶到用戶的服務功能鏈的最小化時延和資源有效的部署問題，嘗試將VNFfi分別部署到接入網和云網絡中，并將VNFfi的部署問題建模為BoS 在線博弈問題，通過持續(xù)的在線博弈，最終確定每個虛擬網絡功能fi是否被卸載，以及最終的部署方案，利用服務卸載和霧計算資源來減少用戶到用戶的SFC 請求的總體時延。因此，與PSECO算法和SAMA 算法相比，本文算法的平均SFC 路徑時延更低。

圖3 平均SFC 路徑時延

圖4 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 鏈路部署成本。結果表明，本文算法的平均SFC 鏈路部署成本低于PSECO 算法和SAMA 算法。這是因為當本算法將SFC 的每個VNFfi部署到服務器nj上時，本研究會找到從VNFfi到之前的VNFfi-1的最小時延路徑pei，同時找到從服務器nj到用戶U2的最小時延路徑pi+1（nj,LU2），這將使部署路徑盡可能保持在最短路徑上。然而，SAMA 算法使用云網絡來部署SFC 請求，這使得VNF 部署方案遠離用戶。雖然PSECO 算法使用霧計算來部署SFC 請求，使得VNF 部署方案的部署方案更接近用戶，但由于接入網資源不足，為了保證部署成功率，PSECO 算法會盡可能多地部署VNF 到接入網中，這通常會造成乒乓路徑和導致部署路徑更長。因此，與PSECO 和SAMA 算法相比，本算法可以獲得更低的平均SFC 鏈路部署成本。

圖4 平均SFC 鏈路部署成本

圖5 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均VNF 部署成本。同樣地，從結果可以看出，本算法的平均VNF 部署成本低于PSECO 算法和SAMA 算法。這是因為本算法聯(lián)合調度云計算和霧計算資源來解決SFC 的最小化時延和資源有效的部署問題時，SAMA 算法使用云網絡來部署SFC請求，PSECO 算法使用霧接入網來部署SFC 請求，而本文DSFCD-SOOG 算法同時使用云計算和霧計算的資源來部署SFC 請求，這樣就有更多的服務器可供選擇，并且可以選擇成本較低的服務器。另外，雖然本文的主要優(yōu)化目標是最小化路徑時延，但還考慮了服務器成本、接入網的總計算資源與剩余計算資源的比例和云網絡的總計算資源與剩余計算資源的比例對部署時延的影響，因此在降低時延的同時，還可以在更合理地利用資源，從而減小VNF 的部署成本。因此，DSFCDSOOG 算法的平均VNF 部署成本低于PSECO 和SAMA 算法。

圖5 平均VNF 部署成本

圖6 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 部署成本，其中用戶到用戶的SFC 請求中的VNF 數(shù)量，即n=8。同樣地，可以看出本算法的平均SFC 部署成本低于PSECO 算法和SAMA 算法。這是因為平均SFC 部署成本是平均SFC 鏈路部署成本和平均VNF 部署成本之和，而本文DSFCD-SOOG 算法的平均SFC 鏈路部署成本和平均VNF 部署成本低于PSECO 和SAMA 算法。

圖6 平均SFC 部署成本

圖7 顯示了3 個算法的SFC 部署成功率。結果表明，本文DSFCD-SOOG 算法的SFC 部署成功率高于PSECO 算法和SAMA 算法。這是因為本研究的DSFCD-SOOG 算法聯(lián)合調度云計算和霧計算的資源，以解決SFC 的最小化時延和資源有效的部署問題，相比于PSECO 算法和SAMA 算法可以提供更多的資源。此外，考慮到接入網總計算資源與剩余計算資源的比例和云網絡的總計算資源與剩余計算資源的比例對部署時延的影響，部署SFC 時也會在更加合理地使用資源，為更多的請求提供服務。因此，本文算法比PSECO 算法和SAMA算法具有更高的SFC 部署成功率。

圖7 SFC 部署成功率

5 結 束 語

本文研究了具有時延需求的用戶到用戶的服務功能鏈的部署問題。為了盡量減少SFC 部署方案的路徑時延，提出了基于服務卸載和在線博弈的最小化時延的DSFCD-SOOG 算法，通過將在線博弈和服務卸載決策相結合，在云-霧網絡中部署用戶到用戶的SFC，以減少SFC 部署方案的路徑時延。最后，利用云-霧網絡的聯(lián)合環(huán)境對本文DSFCD-SOOG 算法進行了評估。結果表明，相比于對比算法，本算法的平均VNF 部署成本大約降低了5%、平均SFC 鏈路部署成本大約降低了14%、平均SFC 部署成本大約降低了10%、平均SFC 路徑時延大約降低了14%，同時SFC 部署成功率大約提升了40%。