朱曉榮，高 健

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

隨著新一代網(wǎng)絡(luò)技術(shù)的發(fā)展，傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)已經(jīng)不適應(yīng)現(xiàn)在的網(wǎng)絡(luò)服務(wù)功能的需求，網(wǎng)絡(luò)資源的適配和資源調(diào)度缺乏靈活性。而軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）和網(wǎng)絡(luò)功能虛擬化（Network Function Virtualizations，NFV）是實(shí)現(xiàn)這一目標(biāo)的關(guān)鍵技術(shù)［1］。SDN采用邏輯上集中式的SDN控制器，實(shí)現(xiàn)了數(shù)據(jù)平面和控制平面的分離，實(shí)現(xiàn)對網(wǎng)絡(luò)的可編程性，優(yōu)化網(wǎng)絡(luò)資源的利用。NFV將傳統(tǒng)網(wǎng)絡(luò)的物理網(wǎng)元功能虛擬化，使得網(wǎng)絡(luò)功能不再局限于專用的硬件內(nèi)，區(qū)別于傳統(tǒng)的網(wǎng)絡(luò)，實(shí)現(xiàn)了網(wǎng)絡(luò)功能和硬件的解耦。NFV使服務(wù)運(yùn)營商能夠靈活地部署網(wǎng)絡(luò)功能，可以為每個(gè)服務(wù)請求構(gòu)建定制化的虛擬網(wǎng)絡(luò)。因此，SDN和NFV為設(shè)計(jì)可擴(kuò)展、動(dòng)態(tài)的可編程的下一代網(wǎng)絡(luò)提供了解決方案。

ITU定義了5G的三大應(yīng)用場景：增強(qiáng)的移動(dòng)寬帶（eMBB），解決以人為中心的多媒體內(nèi)容、服務(wù)和數(shù)據(jù)訪問用例［2］；超可靠低延遲通信（uRLLC），面向的是高可靠和低延時(shí)的應(yīng)用場景，比如無人駕駛，工業(yè)控制等方面；大規(guī)模機(jī)器類型通信（mMTC），面向的是海量連接的物聯(lián)網(wǎng)應(yīng)用，通常傳輸相對低容量的非延遲敏感數(shù)據(jù)。為了滿足不同應(yīng)用的需求，網(wǎng)絡(luò)切片技術(shù)得到了廣泛的研究和應(yīng)用。網(wǎng)絡(luò)切片實(shí)現(xiàn)的邏輯上端到端的網(wǎng)絡(luò)，根據(jù)客戶的需求服務(wù)供應(yīng)商，進(jìn)行業(yè)務(wù)和虛擬網(wǎng)絡(luò)功能的編排為其提供服務(wù)，再將編排好的網(wǎng)絡(luò)切片在網(wǎng)絡(luò)設(shè)備層進(jìn)行實(shí)例化提供服務(wù)。這些不同邏輯網(wǎng)絡(luò)提供不同的服務(wù)，來滿足不同場景用戶的通信需求。網(wǎng)絡(luò)切片由一組虛擬網(wǎng)絡(luò)功能按照一定的邏輯編排和虛擬網(wǎng)絡(luò)功能之間的鏈路組成，這樣經(jīng)過編排實(shí)現(xiàn)的功能邏輯被稱為服務(wù)功能鏈（SFC）。服務(wù)功能鏈可以根據(jù)動(dòng)態(tài)的需求靈活地分配資源，從而可以為各種復(fù)雜的5G通信場景定制網(wǎng)絡(luò)切片。借助網(wǎng)絡(luò)切片，服務(wù)提供商可以靈活、快速地部署他們的定制化應(yīng)用和服務(wù)，以適應(yīng)多樣化服務(wù)的特殊需求。

因此，在提供服務(wù)的過程中就需要將編排好的虛擬網(wǎng)絡(luò)功能和鏈路進(jìn)行映射，服務(wù)功能鏈的映射就是為每個(gè)虛擬網(wǎng)絡(luò)功能分配最優(yōu)的物理節(jié)點(diǎn)和鏈路，所以我們可以把虛擬網(wǎng)絡(luò)功能鏈映射問題轉(zhuǎn)化為虛擬網(wǎng)絡(luò)功能的資源分配問題。NFV-RA（Network Function Virtualization-Resource Allocation）是選擇合適的物理節(jié)點(diǎn)和鏈路來進(jìn)行服務(wù)功能的放置，同時(shí)，資源的使用必須滿足特定的約束目標(biāo)，例如最大化剩余的物理資源，最小化時(shí)延等。

NFV-RA主要包含三個(gè)階段：VNFs（Virtual Network Functions）鏈構(gòu)建（VNFs-Chain Composition，VNFs-CC），稱為服務(wù)功能鏈接；VNF轉(zhuǎn)發(fā)圖嵌入（VNF-Forward Graph Embedding，VNF-FGE）以及VNF調(diào)度（VNF-Scheduling，VNF-SCH）。VNF轉(zhuǎn)發(fā)圖嵌入實(shí)現(xiàn)的是把服務(wù)功能鏈中的虛擬網(wǎng)絡(luò)功能放置到合適的位置滿足其QoS（Quality of Service）需求，VNF調(diào)度是將映射完成的VNF實(shí)例之間的流量進(jìn)行調(diào)度。最近幾年有很多關(guān)于這方面的研究，大部分在對NFV-RA建模時(shí)，建立為一個(gè)整數(shù)線性規(guī)劃的問題（這被證明了是一個(gè)NP-hard問題），通過傳統(tǒng)的啟發(fā)式算法進(jìn)行迭代求解，但是使用啟發(fā)式算法不能夠?qū)?shí)時(shí)的業(yè)務(wù)進(jìn)行映射，降低了系統(tǒng)的實(shí)時(shí)性。

5G核心網(wǎng)中網(wǎng)絡(luò)切片的資源分配問題受到了國內(nèi)外學(xué)者的廣泛關(guān)注。文獻(xiàn)［3］考慮了在核心網(wǎng)中服務(wù)功能鏈的部署，文中形成的最優(yōu)化的問題是在滿足節(jié)點(diǎn)和鏈路資源約束的條件下，一個(gè)物理網(wǎng)絡(luò)中最多可以同時(shí)部署的服務(wù)功能鏈的條數(shù)。作者提出了基于最優(yōu)加權(quán)圖匹配的算法來解決服務(wù)功能鏈映射的問題，但是模型中沒有考慮各類業(yè)務(wù)的Qos的約束。文獻(xiàn)［4］考慮了服務(wù)功能鏈部署的帶寬、時(shí)延和鏈路部署成本作為優(yōu)化的目標(biāo)，作者提出了服務(wù)功能鏈局部的貪婪部署算法，最后用全局的貪婪算法迭代地確定每個(gè)虛擬功能放置的位置。文獻(xiàn)［5］作者也是以部署成本最小化為優(yōu)化目標(biāo)，在維特比算法的基礎(chǔ)上提出了分割融合維特比（Merge-Split Viterbi）算法的啟發(fā)式算法求解近似最優(yōu)解。文獻(xiàn)［6］采用深度強(qiáng)化學(xué)習(xí)算法，以整個(gè)服務(wù)功能鏈的QoS為優(yōu)化目標(biāo)進(jìn)行網(wǎng)絡(luò)切片的路由和資源分配的最優(yōu)策略的求解。文獻(xiàn)［7］以最大化鏈路利用率和最小化帶寬消耗聯(lián)合優(yōu)化，提出了基于多目標(biāo)的遺傳算法進(jìn)行問題的求解。文獻(xiàn)［8］考慮了服務(wù)功能鏈的時(shí)延約束和各種VNFs之間次序的限制，先提出單條服務(wù)功能鏈的路由和資源分配問題，在一條服務(wù)功能鏈的基礎(chǔ)上提出了全局的路由和資源分配的問題。最后作者提出了一種快速的啟發(fā)式算法進(jìn)行求解。文獻(xiàn)［9］VNF的放置和路由資源的分配看起來和 VNE（Virtual Network Embedding）類似，但作者在文中提出了一種更加復(fù)雜的VNF鏈路需求，包括放置VNFs的源目節(jié)點(diǎn)之間的流量控制。

文獻(xiàn)［10］將網(wǎng)絡(luò)切片中的資源分配問題表示為分布式服務(wù)函數(shù)鏈問題，作者采用局部搜索的啟發(fā)式方法來求解。文獻(xiàn)［11］提出了一種啟發(fā)式算法來解決服務(wù)功能鏈的映射，來減少全局的能量消耗。文獻(xiàn)［12］提出了一種基于SDN／NFV場景下的服務(wù)功能鏈的放置模型和VNF的基于時(shí)延的調(diào)度算法以滿足各個(gè)不同服務(wù)功能鏈的時(shí)延約束。文獻(xiàn)［13］以在網(wǎng)絡(luò)切片過程中出現(xiàn)故障進(jìn)行VNF和鏈路的遷移，以最小化整個(gè)過程所消耗的帶寬為優(yōu)化目標(biāo)，提出了基于變鄰域搜索的網(wǎng)絡(luò)切片啟發(fā)式算法對故障進(jìn)行修正。文獻(xiàn)［14］以最小化網(wǎng)絡(luò)中所有的鏈路流量為目標(biāo)，形成了混合整數(shù)線性問題，提出了 PSUM （Penalty Successive Upper-bound Minimization）算法和PSUM-R的算法來進(jìn)行求解。文獻(xiàn)［15］分析了不同網(wǎng)絡(luò)業(yè)務(wù)的網(wǎng)絡(luò)切片和物理網(wǎng)絡(luò)之間的關(guān)系，建立邏輯網(wǎng)絡(luò)函數(shù)映射到物理網(wǎng)絡(luò)的數(shù)學(xué)模型，并且針對5G的三類業(yè)務(wù)的QoS分別提出了最優(yōu)的目標(biāo)函數(shù)進(jìn)行優(yōu)化。文獻(xiàn)［16］提出了新的混合整數(shù)線性規(guī)劃（MILP）優(yōu)化模型，在模型中考慮了端到端的時(shí)延，提出了一種新的啟發(fā)式解決方案——NFV平臺組件編排的介數(shù)中心性算法（BACON）來解決VNF布局問題。文獻(xiàn)［17］提出了一種新的映射方案，對具有相同VNF鏈路集合的鏈路只選擇同一條物理鏈路進(jìn)行映射，減少網(wǎng)絡(luò)的負(fù)載和部署成本，并仿真驗(yàn)證了所提模型在相同的成本下可以部署更多的服務(wù)功能鏈。文獻(xiàn)［18］提出了一個(gè)基于特征分解方法來執(zhí)行VNF映射和VNF轉(zhuǎn)發(fā)圖的流量控制的方案，但是這只是簡單的圖映射關(guān)系，沒有動(dòng)態(tài)實(shí)時(shí)業(yè)務(wù)的處理，因此不能滿足業(yè)務(wù)的實(shí)時(shí)性。文獻(xiàn)［19］對要部署的VNF對各種資源的消耗進(jìn)行了相關(guān)性分析，提出了一個(gè)線性整數(shù)規(guī)劃問題，從時(shí)變工作量和維持基本功能所需能量的角度提出了資源消耗的兩階段啟發(fā)式算法提高資源利用率。

文獻(xiàn)［20］考慮5G的三個(gè)典型業(yè)務(wù)場景為其提供不同的部署策略來滿足各自的QoS需求。在此基礎(chǔ)上，利用復(fù)雜網(wǎng)絡(luò)理論獲得了基礎(chǔ)網(wǎng)絡(luò)的拓?fù)湫畔ⅲ猛負(fù)湫畔⒍x了節(jié)點(diǎn)重要性度量，對節(jié)點(diǎn)映射中的節(jié)點(diǎn)進(jìn)行排序。文獻(xiàn)［21］提出了基于強(qiáng)化學(xué)習(xí)的網(wǎng)絡(luò)切片的資源分配，在智能體的學(xué)習(xí)過程中以資源的利用率和QoE（Quality of Experience）的滿足率為聯(lián)合獎(jiǎng)勵(lì)值對智能體進(jìn)行訓(xùn)練，實(shí)現(xiàn)了實(shí)時(shí)業(yè)務(wù)的資源分配策略。文獻(xiàn)［22］提出了一種最小化VNF遷移和放置總費(fèi)用和收益損失的整數(shù)線性規(guī)劃模型。但是作者所提出的工作忽略了其中的各種約束，如時(shí)延的容忍以及兩個(gè)虛擬功能之間的依賴關(guān)系。上述文獻(xiàn)研究的場景均是將底層網(wǎng)絡(luò)視為一個(gè)整體，從整體上進(jìn)行映射，沒有考慮底層物理設(shè)備資源的分布類別，提出將底層物理設(shè)備按照功能和區(qū)域進(jìn)行聚類，按照三大場景，為每類業(yè)務(wù)劃分出優(yōu)先映射的物理節(jié)點(diǎn)集合，再進(jìn)行相應(yīng)的映射，而且他們在進(jìn)行最優(yōu)化問題的求解過程中大多采用了啟發(fā)式算法，不能滿足業(yè)務(wù)的實(shí)時(shí)性需求，所以有研究提出基于深度強(qiáng)行學(xué)習(xí)的網(wǎng)絡(luò)切片資源分配優(yōu)化算法，對實(shí)時(shí)的業(yè)務(wù)需求提供更好的解決方案。

1 系統(tǒng)模型

文中研究的基于SDN和NFV的網(wǎng)絡(luò)切片按業(yè)務(wù)進(jìn)行映射的應(yīng)用場景如圖1所示，從圖中可以看出，由SDN控制器層、網(wǎng)絡(luò)切片實(shí)例層和物理資源層組成。物理資源層由各種交換機(jī)和路由器等設(shè)備構(gòu)成，可以實(shí)例化部署一些虛擬網(wǎng)絡(luò)功能，按照提出的物理器件的聚類方法，將底層的物理節(jié)點(diǎn)聚類為三類專用器件。網(wǎng)絡(luò)切片實(shí)例層按照用戶的業(yè)務(wù)需求，對各種虛擬網(wǎng)絡(luò)功能進(jìn)行設(shè)計(jì)和編排形成相應(yīng)的服務(wù)功能鏈。SDN控制器層從底層的物理網(wǎng)絡(luò)中收集節(jié)點(diǎn)和鏈路的資源使用情況并且從網(wǎng)絡(luò)切片實(shí)例層得到需要實(shí)時(shí)映射的服務(wù)功能鏈的信息，根據(jù)各條服務(wù)功能鏈的業(yè)務(wù)類別以及帶寬、時(shí)延等的QoS約束選擇最適合的節(jié)點(diǎn)進(jìn)行映射，以此為用戶提供服務(wù)。

圖1 基于SDN和NFV的網(wǎng)絡(luò)切片按業(yè)務(wù)映射應(yīng)用場景圖

1.1 底層物理網(wǎng)絡(luò)模型

1.3.6 優(yōu)化目標(biāo)

針對上面的網(wǎng)絡(luò)切片資源分配的場景，所提出的優(yōu)化目標(biāo)為整個(gè)網(wǎng)絡(luò)的資源利用率最大化，即使得網(wǎng)絡(luò)中資源利用率最低的節(jié)點(diǎn)及鏈路的資源利用率達(dá)到最大。

因此，基于SDN和NFV的網(wǎng)絡(luò)切片的資源分配的全局最優(yōu)化問題為

將上面網(wǎng)絡(luò)整體資源利用率最大化的復(fù)雜優(yōu)化問題拆分為以下三個(gè)子業(yè)務(wù)的聯(lián)合優(yōu)化問題。

低時(shí)延的uRLLC業(yè)務(wù)的子問題為

mMTC的業(yè)務(wù)子問題為最大化節(jié)點(diǎn)和每條鏈路上的資源使用率，使網(wǎng)絡(luò)可以接入更多的業(yè)務(wù)

2 本文算法

2.1 基于對偶分解的求解算法

針對uRLLC低時(shí)延業(yè)務(wù)，將目標(biāo)問題轉(zhuǎn)化為節(jié)點(diǎn)和鏈路的資源使用率最大化：

1.3.5 mMTC服務(wù)功能鏈約束

mMTC服務(wù)功能鏈要求高計(jì)算資源和低擁塞率。因此，部署目標(biāo)應(yīng)該是最小化物理鏈路上的帶寬使用。盡可能使每條鏈路的帶寬負(fù)載均衡，換言之，使得物理鏈路上的剩余帶寬最大化。

其中，p、l分別表示虛擬功能的映射和鏈路的映射關(guān)系是原始變量，μ、v、ω稱為對偶變量。

如果已知對偶變量μ，v，ω，則拉格朗日函數(shù)可以改寫為節(jié)點(diǎn)和鏈路的函數(shù)之和

上面的對偶問題可以分解為虛擬功能的當(dāng)前節(jié)點(diǎn)映射和當(dāng)前節(jié)點(diǎn)到下一跳鏈路映射兩個(gè)子問題進(jìn)行分別求解。

其中，Δ（m）表示對偶變量迭代的步長，步長后面的乘積分別是對偶變量在拉格朗日函數(shù)中的次梯度表達(dá)式。

2.2 計(jì)算復(fù)雜度分析

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

本文仿真實(shí)驗(yàn)利用Matlab2019a軟件對服務(wù)功能鏈部署算法程序進(jìn)行仿真，運(yùn)行在Intel Core i7-8500、1.80 GHz CPU、8 GB內(nèi)存的Windows 10系統(tǒng)PC機(jī)上。

3.1 仿真參數(shù)設(shè)置

本節(jié)對文中提出的基于對偶分解的服務(wù)功能鏈部署算法進(jìn)行仿真評估，我們將本文方法與CoordVNF［23］和一種基于模擬退火SA的算法進(jìn)行了比較。在CoordVNF中，作者提供了一種啟發(fā)式方法來協(xié)調(diào)VNF功能鏈的組成以及將服務(wù)功能鏈映射到子網(wǎng)網(wǎng)絡(luò)中。我們將從服務(wù)功能鏈請求接受率、負(fù)載均衡度、平均執(zhí)行時(shí)間等方面將文中提出的算法與上述兩種算法進(jìn)行對比。在仿真圖中，本文算法的圖例使用DD進(jìn)行標(biāo)識。

本實(shí)驗(yàn)在初始階段，實(shí)驗(yàn)拓?fù)浣Y(jié)構(gòu)采用10個(gè)節(jié)點(diǎn)，18條鏈路，每個(gè)節(jié)點(diǎn)具有三種資源類型，資源總量服從均值為100、方差為30的均勻分布，鏈路帶寬為200 units，鏈路時(shí)延服從均值為3，方差為1的均勻分布。SFCs的數(shù)量為10～100，VNFs種類共有5種，服務(wù)功能鏈所需的VNFs為2～4種，對三種類型的資源需求為0.2～1 units，服務(wù)功能鏈的傳輸速率需求為1～5 units。

然后，將網(wǎng)絡(luò)規(guī)模擴(kuò)展為20～100節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)，VNFs的種類共有9種，每條服務(wù)功能鏈所需的VNFs為3～6種，SFCs數(shù)量由200條逐漸增加到1 000條。

3.2 算法實(shí)驗(yàn)比對

圖2為不同服務(wù)請求數(shù)量下的服務(wù)接受率對比，可以看出，當(dāng)服務(wù)請求數(shù)量不超過400時(shí)，出現(xiàn)了小幅的服務(wù)功能鏈接受率下降，在服務(wù)請求數(shù)量超過500時(shí)，曲線呈直線下降趨勢，請求服務(wù)功能鏈的部署接受率下降嚴(yán)重。對偶分解算法的服務(wù)請求接受率比CoordVNF算法平均提高了3%左右，比SA算法提高了10%左右，主要因?yàn)閷ε挤纸馑惴ú渴鸱?wù)功能鏈的目標(biāo)是最大化使用節(jié)點(diǎn)和鏈路的物理資源，因此在相同的資源設(shè)置時(shí)能夠容納更多的服務(wù)功能鏈部署。

圖2 不同服務(wù)請求數(shù)量下的接受率

圖3表示的是不同服務(wù)鏈請求數(shù)量下節(jié)點(diǎn)資源和鏈路帶寬資源平均利用率的變化，可以看出，隨著服務(wù)功能鏈數(shù)量的增加，使用的物理節(jié)點(diǎn)的資源和鏈路帶寬的平均利用率總體上是上升的，從圖中可以看出基于對偶分解的算法，由于首先將底層的物理網(wǎng)絡(luò)按照功能劃分為三個(gè)不同的虛擬子網(wǎng)以及優(yōu)化目標(biāo)為最大化資源的使用率，使得物理節(jié)點(diǎn)和鏈路帶寬的平均資源使用率得到了提升，明顯優(yōu)于CoordVNF和SA。

圖3 不同服務(wù)請求數(shù)量下的節(jié)點(diǎn)和鏈路的平均資源利用率

圖4表示的是在不同規(guī)模的底層物理節(jié)點(diǎn)，部署長度相同以及數(shù)據(jù)速率相同的服務(wù)功能鏈所需要的平均執(zhí)行時(shí)間。為了評估平均執(zhí)行時(shí)間，我們分別使用所提出的對偶分解的算法和CoordVNF算法以及基于SA的方法來同時(shí)部署相同的服務(wù)功能鏈，從圖中的大體趨勢可以看出隨著服務(wù)功能鏈長度的增加，我們的算法和CoordVNF算法以及SA平均執(zhí)行時(shí)間都在增加?；趯ε挤纸獾牟渴鹚惴ㄅcCoordVNF的執(zhí)行時(shí)間大體相似，比SA的執(zhí)行時(shí)間要明顯縮短很多。在執(zhí)行時(shí)間上有一定的優(yōu)越性。

圖4 部署服務(wù)功能鏈的平均執(zhí)行時(shí)間

由于在進(jìn)行服務(wù)功能鏈的映射之前，先按照物理節(jié)點(diǎn)的集合劃分為三個(gè)虛擬的子網(wǎng)，因此在圖5中對映射到不同子網(wǎng)上面的不同類型的服務(wù)功能鏈的節(jié)點(diǎn)資源和鏈路資源的平均使用率進(jìn)行了仿真，底層采用的實(shí)驗(yàn)拓?fù)錇?5個(gè)節(jié)點(diǎn)，30條鏈路，從圖中可以看出隨著服務(wù)功能鏈數(shù)量的增加，三類業(yè)務(wù)的節(jié)點(diǎn)和鏈路的平均資源利用率總體上呈上升趨勢，eMBB類型服務(wù)功能鏈?zhǔn)冀K使用較少的物理節(jié)點(diǎn)和鏈路，因此物理節(jié)點(diǎn)和鏈路的資源利用率最高。mMTC類型服務(wù)功能鏈?zhǔn)冀K要選擇較多的物理節(jié)點(diǎn)以及使得物理鏈路帶寬最小，以達(dá)到減少底層網(wǎng)絡(luò)沖突的目的，因此物理節(jié)點(diǎn)和鏈路的資源利用率最低。特別地，由于僅考慮了服務(wù)功能鏈的總延遲，uRLLC類型服務(wù)功能鏈的結(jié)果基本上位于它們之間。

圖5 不同子網(wǎng)的節(jié)點(diǎn)和鏈路的平均資源利用率

4 結(jié)束語

文中提出了一種基于SDN和NFV的網(wǎng)絡(luò)切片資源分配優(yōu)化算法，在算法中首先將底層物理網(wǎng)絡(luò)按照服務(wù)功能劃分為三個(gè)虛擬的子網(wǎng)，然后根據(jù)5G網(wǎng)絡(luò)三大業(yè)務(wù)的不同需求建立最大化節(jié)點(diǎn)和鏈路使用率的最優(yōu)化模型，在問題求解的過程中由于鏈路映射問題存在著變量的耦合，因此首先將鏈路條件解耦，分割為相鄰的兩個(gè)節(jié)點(diǎn)之間的映射問題，通過拉格朗日對偶分解的方法，對節(jié)點(diǎn)問題和鏈路分別進(jìn)行求解，實(shí)現(xiàn)服務(wù)功能鏈優(yōu)化部署。該方法基于多個(gè)不同類型服務(wù)的同時(shí)請求，具有實(shí)時(shí)、快速、高效特點(diǎn)，能夠滿足未來5G網(wǎng)絡(luò)定制化服務(wù)場景需求。在執(zhí)行時(shí)間、資源利用率等方面具有較好的性能，在以后的工作中要加入一些人工智能的方法，以滿足智慧化網(wǎng)絡(luò)運(yùn)營需求。