朱曉榮，高 健

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

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

圖1 基于SDN和NFV的網絡切片按業(yè)務映射應用場景圖

1.1 底層物理網絡模型

1.3.6 優(yōu)化目標

針對上面的網絡切片資源分配的場景，所提出的優(yōu)化目標為整個網絡的資源利用率最大化，即使得網絡中資源利用率最低的節(jié)點及鏈路的資源利用率達到最大。

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

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

低時延的uRLLC業(yè)務的子問題為

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

2 本文算法

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

針對uRLLC低時延業(yè)務，將目標問題轉化為節(jié)點和鏈路的資源使用率最大化：

1.3.5 mMTC服務功能鏈約束

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

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

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

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

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

2.2 計算復雜度分析

3 仿真結果與性能分析

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

3.1 仿真參數設置

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

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

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

3.2 算法實驗比對

圖2為不同服務請求數量下的服務接受率對比，可以看出，當服務請求數量不超過400時，出現了小幅的服務功能鏈接受率下降，在服務請求數量超過500時，曲線呈直線下降趨勢，請求服務功能鏈的部署接受率下降嚴重。對偶分解算法的服務請求接受率比CoordVNF算法平均提高了3%左右，比SA算法提高了10%左右，主要因為對偶分解算法部署服務功能鏈的目標是最大化使用節(jié)點和鏈路的物理資源，因此在相同的資源設置時能夠容納更多的服務功能鏈部署。

圖2 不同服務請求數量下的接受率

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

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

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

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

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

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

4 結束語

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