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

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

0 概述

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

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

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

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

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

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

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

1.2 切片映射描述

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

1.2.1 切片基本映射過程

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

1）節(jié)點(diǎn)映射

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

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

2）鏈路映射

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

1.2.2 切片可靠性問題描述

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

圖1 切片請(qǐng)求映射示例Fig.1 Example of slice request mapping

1）高可靠性低時(shí)延切片請(qǐng)求可靠性映射

對(duì)于這一類請(qǐng)求，在映射工作路徑的同時(shí)，設(shè)計(jì)一種基于最大生成樹鏈路的備份資源共享保護(hù)方法。如圖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 鏈路備份保護(hù)方案為｛（a，b）→（B，A，C），（a，c）→（B，D，E）｝。NMST 鏈路通過與MST 鏈路共享備份資源獲得間接保護(hù)：｛（b，c）→（C，A，B，D，E）｝。

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

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

2）高帶寬切片請(qǐng)求可靠性映射

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

3）鏈路可靠性定義

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

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

1.3 目標(biāo)函數(shù)

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

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

1.4 問題復(fù)雜性分析

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

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

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

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

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

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

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

2.2 備份路徑構(gòu)建

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

子算法2高可靠性低時(shí)延切片備份鏈路構(gòu)建

3 仿真與性能分析

3.1 實(shí)驗(yàn)環(huán)境配置

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

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

3.2 性能分析

3.2.1 評(píng)價(jià)指標(biāo)

通過平均成功運(yùn)行率、長期收益開銷比和故障恢復(fù)率這3 項(xiàng)指標(biāo)，評(píng)估本文算法性能。

1）平均成功運(yùn)行率

平均成功運(yùn)行率反映了NS 可靠性映射以及對(duì)鏈路故障恢復(fù)的有效性，計(jì)算公式為：

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

2）長期收益開銷比

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

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

3）物理鏈路利用率

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

4）故障恢復(fù)率

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

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

3.2.2 結(jié)果分析

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

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

圖2 平均成功運(yùn)行率Fig.2 Average success operating rate

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

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

3 種算法物理鏈路利用率的變化情況如圖4所示?？梢钥闯觯篠VNE1+1 算法的鏈路資源利用率遠(yuǎn)低于其他兩種算法，這是因?yàn)樵撍惴ㄕ加昧舜罅挎溌纷鳛閭浞萋窂?；本文DST-NSRE 算法在切片映射時(shí)綜合考慮可靠性和資源利用率的因素，以最大化底層資源作為映射目標(biāo)，通過鏈路備份共享的方式，使得有大量的底層資源用以恢復(fù)，以此提高切片請(qǐng)求的成功映射，因此具有較高的鏈路利用率。

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

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

圖5 平均故障恢復(fù)率Fig.5 Average failure recovery rate

4 結(jié)束語

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