趙季紅，喬琳琳，曲 樺，張文娟

（1.西安郵電大學通信與信息工程學院，西安710121；2.西安交通大學電子信息工程學院，西安710049）

0 概述

網(wǎng)絡切片（Network Slicing，NS）是5G 網(wǎng)絡中的關鍵架構技術［1］。軟件定義網(wǎng)絡（Software Defined Network，SDN）和網(wǎng)絡功能虛擬化（Network Function Virtualization，NFV）使網(wǎng)絡切片能夠以經(jīng)濟高效的方式滿足5G 業(yè)務多樣性的需求［2-4］，但與此同時也存在一些問題［5］，其中關鍵問題之一是如何確保網(wǎng)絡切片對底層網(wǎng)絡軟件和硬件故障的恢復能力。在網(wǎng)絡運行過程中，當?shù)讓泳W(wǎng)絡發(fā)生故障時，保障網(wǎng)絡切片上的多樣性業(yè)務正常運行是非常必要的，然而現(xiàn)階段SDN/NFV 網(wǎng)絡切片中的彈性和可靠性問題尚未得到較好解決［6］。

目前，關于網(wǎng)絡切片可靠性問題的研究較少。文獻［7］考慮到每個切片的流量需求是隨機的并且流量的劇烈變化可能會導致切片重新配置，從重映射恢復切片和重新配置切片兩個角度設計切片的彈性機制。本文從底層鏈路故障出發(fā)，基于可生存性虛擬網(wǎng)絡映射（Survivable Virtual Network Embedding，SVNE）［8］來解決網(wǎng)絡切片可靠性問題。網(wǎng)絡虛擬環(huán)境中對鏈路故障的研究主要分為恢復策略和保護策略［9］?；謴筒呗圆活A備任何備份資源，在鏈路故障時重映射故障鏈路，在底層資源有限的情況下，并不能保證恢復所有的故障鏈路［10］。保護機制又可分為專用保護［11］和共享保護［12］。文獻［13］針對鏈路故障，為每條鏈路采用1∶1 保護方法，盡管使虛擬網(wǎng)的生存性得到了保障，但這樣的備份方法在網(wǎng)絡正常工作時浪費了大量的底層資源。文獻［14-15］在為鏈路備份資源時雖然引入了資源共享機制，快速了恢復故障，但是資源消耗依然很大。文獻［16］將網(wǎng)絡編碼和p 圈保護相結合，對核心鏈路提供1+N 保護。該方法雖然能夠提高底層資源利用率并且保證虛擬網(wǎng)的可靠性，但過程相對復雜。以上解決鏈路故障問題的方法大都在共享保護策略上加以改進，并未對業(yè)務類型進行分類。

單一的應對故障的方法不能有效處理網(wǎng)絡切片業(yè)務類型多需求的問題。在實際網(wǎng)絡環(huán)境下，當一條物理鏈路發(fā)生故障時，引起失效的多個切片可能承載不同的業(yè)務類型。在承載自動駕駛、遠程控制、遠程醫(yī)療手術等對時延和可靠性極其敏感的業(yè)務時，發(fā)生故障應立即處理；而在承載高清視頻等高帶寬通信業(yè)務時，則可給予此類故障一定的恢復時延。因此，當鏈路發(fā)生故障時，應先判斷失效切片的類型，再選取適當?shù)姆椒☉獙收稀?/p>

本文提出一種區(qū)分業(yè)務類型的網(wǎng)絡切片可靠性映射方法。針對單鏈路故障失效的切片請求，遵循區(qū)分業(yè)務原則對其進行劃分。若故障鏈路承載高可靠性低時延業(yè)務類型，則將其直接遷移到備份鏈路，映射時對該切片請求中的最大生成樹鏈路（Maximum Spanning Tree Link，MSTL）進行備份，在提供共享保護的同時減少備份資源消耗；若故障鏈路承載高帶寬業(yè)務類型，則為其尋找滿足約束條件的高可靠性鏈路進行重映射，以此來提高故障恢復率。

1 問題描述與系統(tǒng)模型

1.1 物理平面和網(wǎng)絡切片請求

物理底層網(wǎng)絡（Substrate Network，SN）定義為加權無向圖GS=(NS,ES)。其中，NS為物理節(jié)點集合，ES為物理鏈路集合。每個節(jié)點ns∈NS的節(jié)點屬性包括節(jié)點CPU 資源c(ns)和每個物理鏈路ls∈ES的帶寬資源b(ls)。網(wǎng)絡切片同樣定義加權無向圖GV=(NV,EV)。每個虛擬節(jié)點nv∈NV的節(jié)點CPU 資源需求用c(nv)表示，每個虛擬鏈路lv∈EV的帶寬需求用b(lv)表示。

1.2 切片映射描述

本節(jié)針對網(wǎng)絡切片可靠性問題構建一個混合整數(shù)規(guī)劃模型，對約束條件和目標函數(shù)進行表述。

1.2.1 切片基本映射過程

分節(jié)點映射和鏈路映射兩部分介紹切片的基本映射過程。

1）節(jié)點映射

本文主要關注鏈路映射，節(jié)點映射采取貪婪的算法［17］，這種算法與遞歸算法和元優(yōu)化算法（例如模擬退火算法）相比既簡單又高效。貪婪算法將節(jié)點映射到底層資源最充足的節(jié)點上，有利于映射成功。約束條件包括：

式（2）表示虛擬節(jié)點CPU 需求不得超過底層節(jié)點的CPU 資源，式（3）保證底層節(jié)點最多承載來自同一切片中的一個節(jié)點。

2）鏈路映射

將已完成映射的節(jié)點作為端點進行鏈路映射。底層網(wǎng)絡的物理鏈路的帶寬資源必須滿足所承載虛擬鏈路的帶寬需求，約束條件包括：

1.2.2 切片可靠性問題描述

網(wǎng)絡切片可靠性映射本質上與可生存性虛擬網(wǎng)映射［7］類似，即在映射過程中加入故障恢復策略以確保底層網(wǎng)絡故障時NS 能夠快速恢復，并保證網(wǎng)絡服務的連續(xù)性。圖1 是切片請求映射示意圖，下文分別描述2 種業(yè)務類型切片的可靠性問題。

圖1 切片請求映射示例Fig.1 Example of slice request mapping

1）高可靠性低時延切片請求可靠性映射

對于這一類請求，在映射工作路徑的同時，設計一種基于最大生成樹鏈路的備份資源共享保護方法。如圖1所示，將虛擬鏈路分為最大生成樹（Maximum Spanning Tree，MST）鏈路（a，b）、（a，c）和非最大生成樹（Non-Maximum Spanning Tree，NMST）鏈路（b，c）。虛擬鏈路映射方案為｛（a，b）→（B，C），（a，c）→（B，E），（b，c）→（C，E）｝，MST 鏈路備份保護方案為｛（a，b）→（B，A，C），（a，c）→（B，D，E）｝。NMST 鏈路通過與MST 鏈路共享備份資源獲得間接保護：｛（b，c）→（C，A，B，D，E）｝。

在映射過程中，不僅要避免將MST 鏈路和NMST 鏈路映射到同一SN 路徑，而且還要避免主要路徑和備份路徑重合，約束條件包括：

式（6）表示切片請求中MST 的虛擬鏈路lv映射至物理鏈路ls，式（7）表示切片請求中NMST 的虛擬鏈路lv'映射至物理鏈路ls'，式（8）表示同一切片請求中的MST 鏈路和NMST 鏈路不能映射至同一條物理鏈路。

2）高帶寬切片請求可靠性映射

如果要恢復因底層鏈路故障而失效的高帶寬切片請求，就需要為其重新分配資源。給定底層網(wǎng)絡GS以及失效的這一類切片請求，對于圖1 中的切片映射關系，若底層鏈路（D，F(xiàn)）發(fā)生故障，則將虛擬故障鏈路（d，e）重映射至底層鏈路（D，E，F(xiàn)）。

3）鏈路可靠性定義

將高帶寬請求中故障鏈路映射在高可靠性底層鏈路能夠提高恢復率。鏈路發(fā)生故障的次數(shù)以及可用資源都是影響底層鏈路可靠性的因素。鏈路可靠性與其發(fā)生故障次數(shù)以及所承載的虛擬鏈路成反比，與鏈路剩余資源成正比。借鑒文獻［18］定義節(jié)點可靠性的思想，將鏈路可靠性定義如下：

其中：br(ls)表示物理鏈路ls剩余帶寬資源；f(ls)表示物理鏈路ls的失效次數(shù)；m(ls)表示物理鏈路ls所承載虛擬鏈路的數(shù)量。

1.3 目標函數(shù)

由于要對部分切片請求采取備份，為提高物理資源利用率，用最少的物理資源接受更多的切片請求，以最大化底層剩余資源為映射目標。

其中：α和β分別表示節(jié)點資源和鏈路資源的價值轉換權重；cr(ns)表示節(jié)點剩余資源；br(ls)表示鏈路剩余帶寬資源。剩余資源越大表示有更多的可用資源去承載更多的切片請求。

1.4 問題復雜性分析

混合整數(shù)規(guī)劃問題在本質上是一個NP-hard 問題，這使得在大規(guī)模網(wǎng)絡環(huán)境中不能直接使用此模型來求解。為解決這個問題，本文提出一種基于上述數(shù)學模型快速恢復故障鏈路的啟發(fā)式算法。

2 區(qū)分業(yè)務類型的網(wǎng)絡切片故障恢復策略

本文根據(jù)不同的切片承載業(yè)務類型，提出對故障切片采取不同的故障恢復策略。該策略對高可靠低時延業(yè)務請求提供備份，對高帶寬切片請求故障鏈路采取重映射，這樣既能滿足故障的快速修復，又能減少資源消耗。該策略包括區(qū)分失效切片請求以及完成高可靠性低時延切片備份鏈路構建。整個策略的算法描述如下：

算法1區(qū)分業(yè)務類型的鏈路故障恢復

2.1 業(yè)務類型區(qū)分

通過自適應分類算法將失效的網(wǎng)絡切片請求劃分為高可靠性低時延業(yè)務和高帶寬業(yè)務2 種類型，根據(jù)帶寬閾值BW對切片進行分類，具體過程如下：

子算法1區(qū)分網(wǎng)絡切片請求

2.2 備份路徑構建

本文考慮底層單鏈路失效問題，基于節(jié)點映射完成鏈路映射過程。對高可靠性低時延切片請求，如1.2.2 節(jié)鏈路映射所述，采取Kruskal 算法［19］獲取其最大生成樹鏈路，為保證備份資源能夠共享，應確保滿足以下約束條件：1）主鏈路和備份鏈路不能重疊；2）若不同切片請求的虛擬鏈路的備份鏈路為同一底層路徑，則不能共享備份資源；3）如果底層備份資源滿足新到達的備份請求，則可以共享備份鏈路資源。在滿足上述約束條件的情況下，通過最短路徑算法分別完成主備份路徑映射，具體過程如下：

子算法2高可靠性低時延切片備份鏈路構建

3 仿真與性能分析

3.1 實驗環(huán)境配置

本文實驗的底層網(wǎng)絡拓撲和網(wǎng)絡切片請求拓撲均由GT-ITM［20］工具生成，通過Matlab R2018a 進行仿真結果分析，具體參數(shù)如表1所示。在仿真中，物理故障鏈路的到達服從泊松分布，參數(shù)為0.05，對于區(qū)分切片請求的閾值，根據(jù)實驗所設切片帶寬需求變化范圍，選取變化范圍的中間值8 作為閾值。每次實驗運行30 000 個時間單元，每1 500 個單位對數(shù)據(jù)做統(tǒng)計，取10 次實驗的平均值作為最終結果。

表1 實驗配置參數(shù)Table 1 Experimental configuration parameters

3.2 性能分析

3.2.1 評價指標

通過平均成功運行率、長期收益開銷比和故障恢復率這3 項指標，評估本文算法性能。

1）平均成功運行率

平均成功運行率反映了NS 可靠性映射以及對鏈路故障恢復的有效性，計算公式為：

其中：N(T)是T時刻所有到達NS 的數(shù)量集合；Nsuc(T)表示成功運行的NS 數(shù)量，成功運行的NS 數(shù)量既包括映射成功的NS 請求，又包括恢復成功的NS 請求；δ是趨近于0 的變量。

2）長期收益開銷比

對于切片請求GV=(NV,EV)，長期收益與接受虛擬請求的收入和故障產生的懲罰金相關，定義收入R(GV,T)、懲罰金P(GV)和成本開銷C(GV,T)為：

其中：μ和υ分別是用于平衡CPU 和帶寬資源的加權系數(shù)，本文假設μ=υ=1，表明CPU 和帶寬的重要性相似；A(GV)表示無法恢復的鏈路集合；ω為懲罰系數(shù)，假設為5；h(lv)是對應于虛擬鏈路的底層路徑的跳數(shù)，本文設為4。因此，長期收益開銷比的計算公式為：

3）物理鏈路利用率

物理鏈路利用率表示一段時間內映射的所有物理鏈路已占用帶寬資源與底層網(wǎng)絡鏈路帶寬資源總和之比，計算公式為：

4）故障恢復率

故障恢復率用于反映切片映射算法的可靠性，計算公式為：

其中：Nfail(T)是T時刻所有失效的NS 數(shù)量集合；Nrec(T)表示NS 重映射成功的數(shù)量；δ是趨近于0 的變量。故障恢復率越高，表示這段時間內恢復的NS 數(shù)量就越多，則切片映射算法的可靠性就越高。

3.2.2 結果分析

將本文提出的DST-NSRE 算法與SVNE1+1［13］和DPS-VNRA［21］算法進行對比。SVNE1+1 算法節(jié)點采取隨機映射，利用最短路徑為每條鏈路都采取備份，且備份資源不共享。DPS-VNRA 算法將故障鏈路按帶寬大小降序排列，采用路徑分割法為故障鏈路重新選路。本節(jié)從網(wǎng)絡切片請求成功運行率、長期收益開銷比、鏈路利用率和平均故障恢復率這4 個方面來評估算法應對故障的能力，驗證區(qū)分業(yè)務類型切片可靠性映射方法的有效性。

3 種算法的平均成功運行率如圖2所示。可以看出，隨著NS 請求的到達和鏈路故障的增多，平均成功運行率逐步下降。本文DST-NSRE 算法此項指標較高的原因在于該算法屬于部分備份，僅對高可靠切片類型進行備份，采取基于最大生成樹鏈路的方法盡可能減少備份資源，從而使更多的底層資源接受NS 請求，而且在恢復另一類型切片故障鏈路時用較可靠性高的底層鏈路進行承載，使恢復成功的NS 數(shù)量增多，從而提高了平均成功運行率。DPS-VNRA 算法對所有的故障鏈路采取路徑分裂進行重映射，由于故障鏈路的增多會影響NS 的運行，因此導致平均成功運行率較低。SVNE1+1 保護算法為每條鏈路都進行備份，造成了大量的鏈路資源浪費，同時拒絕了大量的虛擬請求，因此，其成功運行率最低。

圖2 平均成功運行率Fig.2 Average success operating rate

3 種算法的長期平均收益開銷比如圖3所示?？梢钥闯?，長期平均收益開銷比隨著時間的增長出現(xiàn)不同程度的下降，最終趨于穩(wěn)定。DST-NSRE 算法能夠獲得更高的收益開銷比，這是因為該算法對故障的虛擬鏈路按帶寬進行排列，優(yōu)先恢復價值更高的高可靠性低時延切片，增加了網(wǎng)絡收益，并且對備份資源的合理共享減少了資源消耗，使網(wǎng)絡資源開銷減少。此外，算法在重映射時選擇可靠性高的底層鏈路，提高了恢復率，減少了因故障恢復失敗而產生的罰款，從而提高了長期收益開銷比。

圖3 長期收益開銷比Fig.3 Long-term income-cost ratio

3 種算法物理鏈路利用率的變化情況如圖4所示?？梢钥闯觯篠VNE1+1 算法的鏈路資源利用率遠低于其他兩種算法，這是因為該算法占用了大量鏈路作為備份路徑；本文DST-NSRE 算法在切片映射時綜合考慮可靠性和資源利用率的因素，以最大化底層資源作為映射目標，通過鏈路備份共享的方式，使得有大量的底層資源用以恢復，以此提高切片請求的成功映射，因此具有較高的鏈路利用率。

圖4 物理鏈路利用率Fig.4 Physical link utilization rate

3 種算法的平均故障恢復率如圖5所示?？梢钥闯觯篋PS-VNRA 算法故障恢復率最低，因為它在故障發(fā)生后才尋找可替代路徑，當切片請求逐漸增多時，就沒有多余的可用資源用來恢復故障鏈路，所以平均故障恢復率最低；其他兩種算法都有備份鏈路資源；本文DST-NSRE 算法切片類型1 的平均故障恢復率穩(wěn)定在0.88 左右，備份資源的共享與算法SVNE1+1 相比既能減少冗余備份同時又滿足了切片高可靠性需求，切片類型2 即高帶寬類型故障恢復率高于重映射DPS-VNRA 算法，這得益于本文算法將故障鏈路重映射至高可靠性的底層鏈路，提高了恢復率，穩(wěn)定在0.84 左右。

圖5 平均故障恢復率Fig.5 Average failure recovery rate

4 結束語

本文研究單鏈路故障下網(wǎng)絡切片的可靠性映射問題，提出一種基于業(yè)務類型的網(wǎng)絡切片可靠性映射算法。仿真結果表明，與SVNE1+1 和DST-VNRA算法相比，該算法具有較高的切片成功運行率、長期收益比、物理鏈路利用率和故障恢復率。本文只是將切片類型簡單地根據(jù)帶寬閾值分為兩類，而目前網(wǎng)絡切片有三大應用場景。因此，下一步將繼續(xù)完善區(qū)分切片業(yè)務類型的評價方案，并設計更好的啟發(fā)式可靠性映射算法，以此來平衡可靠性與資源利用率之間的關系。