節(jié)點與鏈路協(xié)同映射的生存性虛擬光網絡映射算法

朱國暉，梁申麟，李 慶

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

0 概述

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

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

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

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

1 虛擬光網絡映射問題

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

1.1 網絡模型

彈性光網絡表示為Gs=(Ns,Es,Cs,Bs)，其中：Ns表示物理節(jié)點集；Es表示物理鏈路集；Cs表示物理節(jié)點的可用計算資源；Bs表示物理鏈路中可用頻譜資源。虛擬網絡請求可以表示為Gv=(Nv,Ev,Cv,Bv)，其中：Nv表示虛擬節(jié)點集；Ev表示虛擬鏈路集；Cv表示對應虛擬節(jié)點所需計算資源；Bv表示對應虛擬鏈路所需頻譜數。

1.2 目標函數與約束條件

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

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

本文符號說明如表1 所示。

表1 符號說明Table 1 Symbol description

2 生存性虛擬光網絡算法設計

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

在虛擬光網絡映射過程中，因為不同虛擬節(jié)點的節(jié)點度與計算資源需求不同，其鄰接鏈路對頻譜資源的需求也不同，所以采用文獻［17］定義虛擬節(jié)點的綜合評價：

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

2.2 虛擬網絡節(jié)點與鏈路分類策略

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

圖1 虛擬網絡模型Fig.1 Virtual network model

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

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

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

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

在虛擬鏈路映射時，綜合考慮其映射至物理鏈路所需頻譜資源與映射后物理鏈路的頻譜碎片程度［18］，構建映射路徑映射開銷計算公式：

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

圖2 虛擬網絡請求Fig.2 Virtual network request

圖3 底層光網絡模型Fig.3 The underlying optical network model

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

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

2.5 首末端聯合頻譜分配方法

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

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

生存性虛擬光網絡算法如下：

輸入物理網絡GS，虛擬網絡請求GV

輸出映射結果

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

步驟2將首個節(jié)點放入主動節(jié)點集合內，其他與之連接的節(jié)點放入被動節(jié)點集合內。

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

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

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

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

步驟7使用式（13）計算將主動鏈路分別映射至候選不同物理鏈路上的映射開銷。

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

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

步驟10重復步驟4～步驟9 直至所有的節(jié)點和主動鏈路映射成功。

步驟11用KSP 算法為被動鏈路分配映射開銷較小的工作路徑，并分配頻譜資源。

步驟12再以首個主動節(jié)點為根節(jié)點用prim 算法計算虛擬網絡請求的最小生成樹。

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

步驟14返回映射結果。

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

3 仿真與性能分析

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

本文所提算法在MATLAB R2018a 中編程實現，在拓撲圖為24 個節(jié)點與43 條鏈路的USNET 網絡中進行仿真，且虛擬網絡請求拓撲均為連通圖，具體參數如表3 所示。為保證仿真結果的相對準確性，每組仿真運行5 000 組虛擬網絡，并取3 次仿真的平均值作為最終結果。

表3 實驗配置參數Table 3 Experimental configuration parameters

3.2 結果分析

將本文所提CMST-HA 算法與文獻［21］RVNM算法、文獻［22］CMST 算法進行對比，在不同網絡負載下，從虛擬網絡的請求阻塞率、虛擬網絡映射平均頻譜資源消耗、鏈路映射平均跳數和物理網絡收益這4 個方面來所驗證提方法性能。3 種算法的簡要描述如表4 所示。

表4 對比算法描述Table 4 Comparison algorithm description

表5 所示為3 個算法的時間復雜度對比，均在多項式時間內可解。3 個算法的虛擬節(jié)點和物理節(jié)點排序時間復雜度相同，主要區(qū)別在于工作路徑和保護路徑的選擇與頻譜分配時間復雜度不同。

表5 算法復雜度對比Table 5 Comparison of algorithm complexity

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

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

圖5 3 種算法在不同網絡負載下的阻塞率Fig.5 The blocking rate of three algorithms under different network loads

圖6 所示為3 種算法在不同網絡負載下鏈路映射平均跳數。

圖6 3 種算法在不同網絡負載下鏈路映射平均跳數Fig.6 The average number of link mapping hops for the three algorithms under different network loads

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

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

圖7 不同虛擬網絡請求數量下虛擬網絡映射頻譜資源消耗Fig.7 Spectral resource consumption of virtual network mapping under different virtual network requests

圖8 所示為3 種算法的物理網絡收益均隨著虛擬網絡數量的增加而增加，但CMST-HA 算法的收益比其他2 個對比算法更高，因為該算法具有較低的虛擬網絡請求阻塞率和平均頻譜資源消耗，能使更多的虛擬網絡成功映射至底層物理網絡，所以物理網絡收益也更高。

圖8 物理網絡收益Fig.8 Physical network benefits

4 結束語

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