朱國(guó)暉，梁申麟，李 慶

（西安郵電大學(xué)通信與信息工程學(xué)院，西安 710121）

0 概述

隨著云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)等新型網(wǎng)絡(luò)服務(wù)的迅猛發(fā)展，人們對(duì)網(wǎng)絡(luò)服務(wù)的需求發(fā)生了巨大變化，并趨于向高帶寬、高突發(fā)、低延遲的方向發(fā)展［1］。為更好地利用光資源來(lái)適應(yīng)新的網(wǎng)絡(luò)業(yè)務(wù)，新興的彈性光網(wǎng)絡(luò)（Elastic Optical Network，EON）因?yàn)榫哂徐`活的頻譜分配和可擴(kuò)展的數(shù)據(jù)傳輸速率等特點(diǎn)，被作為下一代智能光網(wǎng)絡(luò)［2］。與傳統(tǒng)的WDM 網(wǎng)絡(luò)相比，EON 采用粒度更小的頻譜柵格，可以動(dòng)態(tài)地根據(jù)用戶對(duì)帶寬的實(shí)際需求，采取不同的頻譜資源分配方法，設(shè)置最佳的調(diào)制格式，因此極大地提高了頻譜利用率［3-5］。

近年來(lái)，網(wǎng)絡(luò)虛擬化技術(shù)克服了傳統(tǒng)互聯(lián)網(wǎng)的僵化問(wèn)題，在共享公共物理基礎(chǔ)設(shè)施方面展現(xiàn)了極大的靈活性和可擴(kuò)展性，促進(jìn)了廣泛多樣的云服務(wù)和應(yīng)用的發(fā)展［6］。光網(wǎng)絡(luò)是保證高帶寬、低時(shí)延傳輸?shù)幕A(chǔ)部分，將網(wǎng)絡(luò)虛擬化技術(shù)引入EON 被認(rèn)為是解決網(wǎng)絡(luò)剛性問(wèn)題和資源利用率較低的有效方法［7-8］。而網(wǎng)絡(luò)虛擬化技術(shù)的引入也會(huì)帶來(lái)一些新的挑戰(zhàn)，在進(jìn)行虛擬網(wǎng)絡(luò)映射時(shí)涉及到為虛擬光網(wǎng)絡(luò)請(qǐng)求分配底層物理網(wǎng)絡(luò)資源，還需滿足多方面約束條件，如節(jié)點(diǎn)計(jì)算資源、鏈路頻譜資源、映射位置、底層網(wǎng)絡(luò)拓?fù)湟蟮龋?］。而且，底層網(wǎng)絡(luò)中故障難免發(fā)生，自然災(zāi)害或人為操作可能會(huì)導(dǎo)致節(jié)點(diǎn)或鏈路損壞，無(wú)法正常工作，影響映射至物理網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)，降低用戶體驗(yàn)，給運(yùn)營(yíng)商帶來(lái)不必要的經(jīng)濟(jì)損失［10-12］。

針對(duì)虛擬光網(wǎng)絡(luò)的生存性映射問(wèn)題，目前已有很多文獻(xiàn)提出了相關(guān)的解決策略。文獻(xiàn)［13］在保證VON 生存性的前提下綜合考慮節(jié)點(diǎn)間距離和頻譜碎片度，設(shè)計(jì)一種鏈路頻譜資源消耗較小的節(jié)點(diǎn)與鏈路協(xié)同映射策略，提高了鏈路頻譜資源利用率和VON 映射成功率。文獻(xiàn)［14］采用共享保護(hù)方法將虛擬光網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò)，在映射過(guò)程中考慮鏈路的頻譜一致性，以增強(qiáng)虛擬節(jié)點(diǎn)和虛擬鏈路映射時(shí)的相關(guān)性，降低了頻譜資源碎片度。文獻(xiàn)［15］針對(duì)備份資源的冗余度相對(duì)較高的問(wèn)題，考慮物理鏈路的故障概率，以鏈路安全性作為重要排序指標(biāo)，并允許路徑分割來(lái)提升虛擬光網(wǎng)絡(luò)的映射成功率，但存在鏈路碎片度較高的問(wèn)題。文獻(xiàn)［16］提出一種基于自適應(yīng)路徑分裂的映射策略，利用部分備份資源提供針對(duì)單鏈路故障的完全保護(hù)，引入頻譜窗選擇機(jī)制以降低頻譜碎片，降低了預(yù)留資源的冗余度，然而路徑分裂增加了虛擬鏈路映射失敗的發(fā)生率。

針對(duì)EON 中虛擬網(wǎng)絡(luò)映射時(shí)出現(xiàn)的單鏈路故障問(wèn)題，本文考慮鏈路映射開(kāi)銷，提出節(jié)點(diǎn)與鏈路協(xié)同映射的生存性虛擬光網(wǎng)絡(luò)映射算法，并為虛擬光網(wǎng)絡(luò)的部分重要鏈路提供保護(hù)。該算法在虛擬網(wǎng)絡(luò)請(qǐng)求時(shí)依據(jù)虛擬節(jié)點(diǎn)的重要度將虛擬節(jié)點(diǎn)與鏈路分別劃分為兩種不同類型，并設(shè)計(jì)不同策略完成映射。在鏈路映射時(shí)將鏈路頻譜碎片度作為映射開(kāi)銷的重要參數(shù)，利用匈牙利算法解出主動(dòng)鏈路的最優(yōu)映射方案，降低虛擬鏈路的映射總開(kāi)銷以節(jié)省頻譜資源，提升后續(xù)虛擬網(wǎng)絡(luò)請(qǐng)求的映射成功率。在此基礎(chǔ)上，對(duì)虛擬網(wǎng)絡(luò)部分重要的工作路徑提供保護(hù)路徑，并采用首端與末端聯(lián)合的方式進(jìn)行頻譜資源分配，以在保證虛擬網(wǎng)絡(luò)生存性的同時(shí)，減少物理鏈路頻譜碎片的產(chǎn)生。

1 虛擬光網(wǎng)絡(luò)映射問(wèn)題

本節(jié)從底層物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)請(qǐng)求的角度描述網(wǎng)絡(luò)模型，介紹可生存性虛擬光網(wǎng)絡(luò)映射的目標(biāo)和約束條件。

1.1 網(wǎng)絡(luò)模型

彈性光網(wǎng)絡(luò)表示為Gs=(Ns,Es,Cs,Bs)，其中：Ns表示物理節(jié)點(diǎn)集；Es表示物理鏈路集；Cs表示物理節(jié)點(diǎn)的可用計(jì)算資源；Bs表示物理鏈路中可用頻譜資源。虛擬網(wǎng)絡(luò)請(qǐng)求可以表示為Gv=(Nv,Ev,Cv,Bv)，其中：Nv表示虛擬節(jié)點(diǎn)集；Ev表示虛擬鏈路集；Cv表示對(duì)應(yīng)虛擬節(jié)點(diǎn)所需計(jì)算資源；Bv表示對(duì)應(yīng)虛擬鏈路所需頻譜數(shù)。

1.2 目標(biāo)函數(shù)與約束條件

本文以虛擬網(wǎng)絡(luò)請(qǐng)求的平均資源消耗最小為目標(biāo)，研究彈性光網(wǎng)絡(luò)中可生存性虛擬網(wǎng)絡(luò)映射問(wèn)題，優(yōu)化目標(biāo)如式（1）所示，約束條件如式（2）～式（9）所示。

其中：式（2）確保一個(gè)虛擬網(wǎng)絡(luò)的虛擬節(jié)點(diǎn)只能被映射到一個(gè)物理節(jié)點(diǎn)；式（3）確保虛擬節(jié)點(diǎn)所映射物理節(jié)點(diǎn)的節(jié)點(diǎn)度大于等于其自身節(jié)點(diǎn)度；式（4）和式（5）確保有足夠的計(jì)算資源和頻譜資源來(lái)滿足虛擬節(jié)點(diǎn)和虛擬鏈路的需求；式（6）確保對(duì)于給定的虛擬鏈路其工作路徑和保護(hù)路徑不相交；式（7）和式（8）指定所映射的物理鏈路必須使用連續(xù)的頻譜隙；式（9）確保給定的頻隙最多只能由一個(gè)虛擬請(qǐng)求使用。

本文符號(hào)說(shuō)明如表1 所示。

表1 符號(hào)說(shuō)明Table 1 Symbol description

2 生存性虛擬光網(wǎng)絡(luò)算法設(shè)計(jì)

2.1 虛擬節(jié)點(diǎn)重要度

在虛擬光網(wǎng)絡(luò)映射過(guò)程中，因?yàn)椴煌摂M節(jié)點(diǎn)的節(jié)點(diǎn)度與計(jì)算資源需求不同，其鄰接鏈路對(duì)頻譜資源的需求也不同，所以采用文獻(xiàn)［17］定義虛擬節(jié)點(diǎn)的綜合評(píng)價(jià)：

其中：e表示節(jié)點(diǎn)nV的鄰接鏈路；為虛擬節(jié)點(diǎn)的節(jié)點(diǎn)度。由于本文采用節(jié)點(diǎn)與鏈路交替進(jìn)行的方法完成虛擬網(wǎng)絡(luò)映射，因此虛擬節(jié)點(diǎn)所映射的順序和位置在一定程度上也影響著鏈路映射情況。

2.2 虛擬網(wǎng)絡(luò)節(jié)點(diǎn)與鏈路分類策略

根據(jù)式（10）計(jì)算其虛擬節(jié)點(diǎn)重要度，將重要度最大的虛擬節(jié)點(diǎn)選取為主動(dòng)節(jié)點(diǎn)放入主動(dòng)節(jié)點(diǎn)集合NVZ中，而其鄰接節(jié)點(diǎn)則選取為被動(dòng)節(jié)點(diǎn)放入被動(dòng)節(jié)點(diǎn)集合NVB中。剔除已分類節(jié)點(diǎn)，將剩余未分類節(jié)點(diǎn)再次按照上述過(guò)程排序并分類，重復(fù)上述過(guò)程，直至所有虛擬節(jié)點(diǎn)均完成分類并放入對(duì)應(yīng)的節(jié)點(diǎn)集合中。如圖1 所示，經(jīng)計(jì)算可得出節(jié)點(diǎn)B重要度最大，選取為主動(dòng)節(jié)點(diǎn)，因此與節(jié)點(diǎn)B鄰接的節(jié)點(diǎn)均為被動(dòng)節(jié)點(diǎn)。而節(jié)點(diǎn)E和節(jié)點(diǎn)D還未分類，需再次對(duì)其排序，最后將重要度較大的節(jié)點(diǎn)E放入主動(dòng)節(jié)點(diǎn)集合NVZ中，與其相連的節(jié)點(diǎn)D放入被動(dòng)集合NVB中，此時(shí)虛擬分類已完成。

圖1 虛擬網(wǎng)絡(luò)模型Fig.1 Virtual network model

虛擬節(jié)點(diǎn)分類完成后再繼續(xù)進(jìn)行虛擬鏈路的分類，劃分依據(jù)是判斷鏈路兩端的虛擬節(jié)點(diǎn)已映射個(gè)數(shù)，若該鏈路僅有一個(gè)虛擬節(jié)點(diǎn)被映射，則該虛擬鏈路被劃分為主動(dòng)鏈路，若該鏈路兩端的虛擬節(jié)點(diǎn)均已被映射，則該虛擬鏈路被劃為被動(dòng)鏈路。如主動(dòng)節(jié)點(diǎn)B映射成功后，其鄰接鏈路B-A、B-F、B-C即作為主動(dòng)鏈路被劃分至集合EVZ中，當(dāng)主動(dòng)鏈路均完成映射時(shí)，虛擬節(jié)點(diǎn)A、F、C的位置隨之確定，鏈路C-D、C-E、A-F、E-F兩端節(jié)點(diǎn)映射均已完成，則作為被動(dòng)鏈路被劃分至被動(dòng)鏈路集合EVZ中，完成后續(xù)鏈路映射。

2.3 物理節(jié)點(diǎn)重要度

物理節(jié)點(diǎn)的選取決定著主動(dòng)節(jié)點(diǎn)映射能否成功映射，也對(duì)后續(xù)主動(dòng)鏈路能否在較小跳數(shù)內(nèi)映射成功有著重要影響。因此，當(dāng)選擇物理節(jié)點(diǎn)映射時(shí)，在考慮該節(jié)點(diǎn)計(jì)算資源和節(jié)點(diǎn)度是否滿足需求的前提下，應(yīng)將其鄰接鏈路的頻譜資源和鄰接節(jié)點(diǎn)的計(jì)算資源使用情況作為重要參考指標(biāo)，如式（11）所示：

2.4 基于匈牙利算法的虛擬鏈路映射策略

在虛擬鏈路映射時(shí)，綜合考慮其映射至物理鏈路所需頻譜資源與映射后物理鏈路的頻譜碎片程度［18］，構(gòu)建映射路徑映射開(kāi)銷計(jì)算公式：

圖2 所示為虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)計(jì)算資源需求與鏈路頻譜需求。圖3 所示為底層物理節(jié)點(diǎn)B及其鄰接鏈路的頻譜使用狀態(tài)。若虛擬網(wǎng)絡(luò)請(qǐng)求中主動(dòng)節(jié)點(diǎn)a成功映射至物理網(wǎng)絡(luò)中節(jié)點(diǎn)B時(shí)，則開(kāi)始映射與其相連的主動(dòng)鏈路，虛擬鏈路a-b、a-c、a-d可分別映射至物理鏈路B-C、B-D、B-E、B-F等4 條鏈路方向。若所選映射物理鏈路的頻譜資源和下一跳節(jié)點(diǎn)計(jì)算資源均滿足需求，則可成功映射并確定被動(dòng)節(jié)點(diǎn)的映射位置，若所選鏈路頻譜資源滿足需求而下一跳節(jié)點(diǎn)計(jì)算資源不足，則將該節(jié)點(diǎn)加入路徑集合，并繼續(xù)計(jì)算該節(jié)點(diǎn)的下一跳節(jié)點(diǎn)及路徑頻譜資源是否滿足映射需求，直至找到滿足映射需求的物理路徑和被動(dòng)節(jié)點(diǎn)映射位置；否則，說(shuō)明該鏈路方向無(wú)法成功映射。

圖2 虛擬網(wǎng)絡(luò)請(qǐng)求Fig.2 Virtual network request

圖3 底層光網(wǎng)絡(luò)模型Fig.3 The underlying optical network model

以圖2 中虛擬鏈路a-c為例，將其分別映射至候選映射路徑上時(shí)，利用式（13）計(jì)算其映射開(kāi)銷，若物理節(jié)點(diǎn)B的鄰接節(jié)點(diǎn)（C，D，E，F(xiàn)）計(jì)算資源充足可滿足主動(dòng)節(jié)點(diǎn)a的鄰接節(jié)點(diǎn)（b，c，d）的計(jì)算資源需求，則可計(jì)算其映射開(kāi)銷分別為：8、N（虛擬鏈路B-D無(wú)法滿足其頻譜資源需求），20、8。再分別計(jì)算其他主動(dòng)鏈路映射至候選物理鏈路不同方向時(shí)的映射開(kāi)銷。如表2 所示，可將鏈路映射問(wèn)題轉(zhuǎn)為指派問(wèn)題，若候選可映射物理鏈路數(shù)大于待映射虛擬鏈路時(shí)，則可對(duì)其補(bǔ)0 使其構(gòu)成標(biāo)準(zhǔn)指派問(wèn)題［19］。使用匈牙利算法求解最優(yōu)映射方案，得出最小虛擬鏈路映射總開(kāi)銷為23，即應(yīng)將虛擬鏈路a-b映射至物理鏈路B-C，a-c映射至B-F，a-d映射至B-D，該鏈路映射方案不僅節(jié)約了頻譜資源消耗，而且也降低了物理鏈路的頻譜碎片度。

表2 虛擬鏈路映射方案Table 2 Virtual link mapping scheme

2.5 首末端聯(lián)合頻譜分配方法

如圖4 所示，若按照FF（First-Fit）頻譜分配法為保護(hù)路徑分配頻譜塊6 與7，而頻譜塊8 則將作為頻譜碎片被浪費(fèi)，不利于為后續(xù)的業(yè)務(wù)進(jìn)行頻譜資源分配。當(dāng)使用FLF（First-Last-Fit）頻譜分配方法時(shí)，將鏈路頻譜資源分為工作和保護(hù)2 個(gè)頻譜區(qū)，此分區(qū)方法要求工作和保護(hù)路徑在進(jìn)行頻譜分配時(shí)盡量使用自己分區(qū)的資源，而頻譜資源不足時(shí)依然可以跨區(qū)使用［20］。為保護(hù)路徑分配頻譜時(shí)，采用LF（Last-Fit）頻譜分配法為其分配頻譜塊15 與16，避免了頻譜碎片的產(chǎn)生，提高了頻譜資源的利用率。

圖4 FLF 頻譜分配示意圖Fig.4 Schematic diagram of FLF spectrum allocation

生存性虛擬光網(wǎng)絡(luò)算法如下：

輸入物理網(wǎng)絡(luò)GS，虛擬網(wǎng)絡(luò)請(qǐng)求GV

輸出映射結(jié)果

步驟1根據(jù)式（10）計(jì)算虛擬節(jié)點(diǎn)重要度，并將其降序排列。

步驟2將首個(gè)節(jié)點(diǎn)放入主動(dòng)節(jié)點(diǎn)集合內(nèi)，其他與之連接的節(jié)點(diǎn)放入被動(dòng)節(jié)點(diǎn)集合內(nèi)。

步驟3將剩余節(jié)點(diǎn)按照步驟1、步驟2 重復(fù)執(zhí)行直至所有節(jié)點(diǎn)分類完畢。

步驟4求出滿足主動(dòng)節(jié)點(diǎn)計(jì)算資源和節(jié)點(diǎn)度需求的物理節(jié)點(diǎn)候選集，按式（11）計(jì)算其物理節(jié)點(diǎn)重要度并降序排列。

步驟5將主動(dòng)節(jié)點(diǎn)映射至物理節(jié)點(diǎn)重要度最大的節(jié)點(diǎn)上。

步驟6將主動(dòng)鏈路根據(jù)頻譜資源需求降序排列，確定其映射順序。

步驟7使用式（13）計(jì)算將主動(dòng)鏈路分別映射至候選不同物理鏈路上的映射開(kāi)銷。

步驟8使用匈牙利算法求解出映射開(kāi)銷最小的方案。

步驟9將主動(dòng)鏈路依照所求方案按序映射并分配頻譜資源同時(shí)確定與之相連的被動(dòng)節(jié)點(diǎn)的映射位置。

步驟10重復(fù)步驟4～步驟9 直至所有的節(jié)點(diǎn)和主動(dòng)鏈路映射成功。

步驟11用KSP 算法為被動(dòng)鏈路分配映射開(kāi)銷較小的工作路徑，并分配頻譜資源。

步驟12再以首個(gè)主動(dòng)節(jié)點(diǎn)為根節(jié)點(diǎn)用prim 算法計(jì)算虛擬網(wǎng)絡(luò)請(qǐng)求的最小生成樹。

步驟13用KSP 算法為該最小生成樹鏈路分配映射開(kāi)銷較小的保護(hù)路徑。

步驟14返回映射結(jié)果。

CMST-HA 算法的虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)排序時(shí)間復(fù)雜度分別為O（Nv×lbNv）與O(Ns×F)，工作路徑與的選擇和頻譜分配復(fù)雜度為O(K2×F2×(|Ls|+Ns×lbNs))，保護(hù)路徑的選擇和頻譜分配時(shí)間復(fù)雜度為O(|Ls|+Ns×lbNs)，其中：F為鏈路可用頻譜數(shù)；|Ls|為物理鏈路數(shù)。因此，CMST-HA 算法的算法復(fù)雜度為O（Nv×lbNv+Ns×F+K2×F2×（|Ls|+Ns×lbNs)+|Ls|+Ns×lbNs)。

3 仿真與性能分析

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

本文所提算法在MATLAB R2018a 中編程實(shí)現(xiàn)，在拓?fù)鋱D為24 個(gè)節(jié)點(diǎn)與43 條鏈路的USNET 網(wǎng)絡(luò)中進(jìn)行仿真，且虛擬網(wǎng)絡(luò)請(qǐng)求拓?fù)渚鶠檫B通圖，具體參數(shù)如表3 所示。為保證仿真結(jié)果的相對(duì)準(zhǔn)確性，每組仿真運(yùn)行5 000 組虛擬網(wǎng)絡(luò)，并取3 次仿真的平均值作為最終結(jié)果。

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

3.2 結(jié)果分析

將本文所提CMST-HA 算法與文獻(xiàn)［21］RVNM算法、文獻(xiàn)［22］CMST 算法進(jìn)行對(duì)比，在不同網(wǎng)絡(luò)負(fù)載下，從虛擬網(wǎng)絡(luò)的請(qǐng)求阻塞率、虛擬網(wǎng)絡(luò)映射平均頻譜資源消耗、鏈路映射平均跳數(shù)和物理網(wǎng)絡(luò)收益這4 個(gè)方面來(lái)所驗(yàn)證提方法性能。3 種算法的簡(jiǎn)要描述如表4 所示。

表4 對(duì)比算法描述Table 4 Comparison algorithm description

表5 所示為3 個(gè)算法的時(shí)間復(fù)雜度對(duì)比，均在多項(xiàng)式時(shí)間內(nèi)可解。3 個(gè)算法的虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)排序時(shí)間復(fù)雜度相同，主要區(qū)別在于工作路徑和保護(hù)路徑的選擇與頻譜分配時(shí)間復(fù)雜度不同。

表5 算法復(fù)雜度對(duì)比Table 5 Comparison of algorithm complexity

RVNM 算法需在確定工作路徑或保護(hù)路徑后，不斷更新鏈路映射方案以降低頻譜消耗，因而復(fù)雜度較高，CMST 算法只需在確定工作路徑后為虛擬網(wǎng)絡(luò)的最小生成樹鏈路提供保護(hù)路徑，復(fù)雜度較低，而CMST-HA 算法為降低工作路徑的頻譜資源消耗與鏈路頻譜碎片度，引入匈牙利算法進(jìn)行映射方案的求解，故復(fù)雜度位于兩者之間。

圖5所示為3種算法在不同網(wǎng)絡(luò)負(fù)載下的阻塞率。CMST 算法和CMST-HA 算法均采用節(jié)點(diǎn)與鏈路協(xié)同映射的方式，選擇跳數(shù)較小的物理路徑進(jìn)行映射，并通過(guò)為虛擬網(wǎng)絡(luò)的最小生成樹鏈路提供保護(hù)路徑，降低了頻譜資源消耗。但RVNM 算法和CMST 算法在頻譜分配時(shí)沒(méi)有考慮頻譜碎片的因素，增加了VON 請(qǐng)求被阻塞的概率，而CMST-HA 算法采用匈牙利算法求解主動(dòng)類型的虛擬鏈路最優(yōu)映射方案進(jìn)一步降低了頻譜資源的消耗與鏈路頻譜碎片度，另外采用工作路徑和保護(hù)路徑分離的首端末端聯(lián)合頻譜分配方法，提升了頻譜資源的利用率，進(jìn)而增加了后續(xù)虛擬網(wǎng)絡(luò)請(qǐng)求映射成功的機(jī)率，因此CMST-HA 算法的阻塞率最低。

圖5 3 種算法在不同網(wǎng)絡(luò)負(fù)載下的阻塞率Fig.5 The blocking rate of three algorithms under different network loads

圖6 所示為3 種算法在不同網(wǎng)絡(luò)負(fù)載下鏈路映射平均跳數(shù)。

圖6 3 種算法在不同網(wǎng)絡(luò)負(fù)載下鏈路映射平均跳數(shù)Fig.6 The average number of link mapping hops for the three algorithms under different network loads

RVNM 算法在VON 映射時(shí)采用兩階段映射方法，將虛擬節(jié)點(diǎn)映射至可靠性較高的物理節(jié)點(diǎn)上，但未考慮節(jié)點(diǎn)間的映射距離，導(dǎo)致虛擬鏈路的映射跳數(shù)較大。CMST 算法在鏈路映射時(shí)忽視了主動(dòng)節(jié)點(diǎn)間的位置約束，導(dǎo)致虛擬網(wǎng)絡(luò)各部分分布較遠(yuǎn)，增加了被動(dòng)鏈路的映射資源消耗。CMST-HA 算法將主動(dòng)節(jié)點(diǎn)映射至鄰接鏈路與鄰接節(jié)點(diǎn)資源豐富物理節(jié)點(diǎn)上，提高了主動(dòng)鏈路在較小跳數(shù)內(nèi)映射成功的機(jī)率，鏈路映射時(shí)采用匈牙利算法求解最優(yōu)映射方案降低了物理鏈路的頻譜碎片度與頻譜資源的消耗，提升了后續(xù)虛擬鏈路映射成功的機(jī)率。因此，其鏈路映射平均跳數(shù)最短。

圖7 分析了不同虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量下的虛擬網(wǎng)絡(luò)映射頻譜資源消耗。CMST 算法和CMST-HA 算法都是為虛擬網(wǎng)絡(luò)請(qǐng)求的最小生成樹提供保護(hù)路徑，相較RVNM 算法為每條虛擬鏈路都提供保護(hù)路徑節(jié)省了頻譜資源。由圖6 可知，CMST-HA 算法的鏈路映射平均跳數(shù)是三者中最小的，且虛擬鏈路的頻譜需求為定值，因此跳數(shù)越小虛擬網(wǎng)絡(luò)映射所占用頻譜資源越少。

圖7 不同虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量下虛擬網(wǎng)絡(luò)映射頻譜資源消耗Fig.7 Spectral resource consumption of virtual network mapping under different virtual network requests

圖8 所示為3 種算法的物理網(wǎng)絡(luò)收益均隨著虛擬網(wǎng)絡(luò)數(shù)量的增加而增加，但CMST-HA 算法的收益比其他2 個(gè)對(duì)比算法更高，因?yàn)樵撍惴ň哂休^低的虛擬網(wǎng)絡(luò)請(qǐng)求阻塞率和平均頻譜資源消耗，能使更多的虛擬網(wǎng)絡(luò)成功映射至底層物理網(wǎng)絡(luò)，所以物理網(wǎng)絡(luò)收益也更高。

圖8 物理網(wǎng)絡(luò)收益Fig.8 Physical network benefits

4 結(jié)束語(yǔ)

本文針對(duì)EON 中可生存性虛擬網(wǎng)絡(luò)映射問(wèn)題，提出一種針對(duì)單鏈路故障的專用保護(hù)算法。采用節(jié)點(diǎn)和鏈路協(xié)同映射的方法完成虛擬網(wǎng)絡(luò)映射并對(duì)其最小生成樹鏈路進(jìn)行專有保護(hù)，在鏈路映射時(shí)選擇映射開(kāi)銷較低的映射方案減少頻譜消耗，在頻譜分配時(shí)采用首末端聯(lián)合分配的方法提升頻譜資源利用率。仿真結(jié)果表明，CMST-HA 算法可以提高虛擬網(wǎng)絡(luò)請(qǐng)求的阻塞率，降低平均頻譜資源消耗。本文研究的是單域VONE，當(dāng)涉及到多域VONE 時(shí)會(huì)產(chǎn)生域內(nèi)和域間的鏈路故障問(wèn)題，因此探索多域鏈路的生存性虛擬光網(wǎng)絡(luò)映射算法將是下一步的研究方向。