基于兩次優先級排序的虛擬網絡映射算法*

朱國暉，張 茵，劉秀霞，孫天驁

(西安郵電大學通信與信息工程學院，陜西 西安 710121)

1 引言

云計算可以定義為通過Internet交互并允許隨需訪問共享資源的一種模式[1]，云計算服務的快速部署需要在應用程序和物理設施之間建立穩定且高效的虛擬化層。網絡虛擬化是云計算的一個重要特性，是一種邏輯劃分物理資源的方法，簡化了在物理網絡上創建多個虛擬網絡的過程，可以滿足云計算基礎設施上的資源共享需求[2]。隨著云計算服務部署的增加，網絡虛擬化被認為是一種很有前途的解決方案[3,4]。虛擬資源在相應物理資源上的分配過程被稱為虛擬網絡映射VNE(Virtual Network Embedding)，帶有約束條件的映射問題被證明是NP-hard的[5]。

在過去幾年，許多學者投入到虛擬網絡映射領域并取得了突出的研究成果。蔡志平等人[6]總結了解決虛擬網絡映射模型優化問題的方法，Inführ等人[7]介紹了具有延遲、路由和位置約束的虛擬網絡映射問題，Fischer等人[8]概述了VNE領域的研究現狀并提出了一種全新的方案對VNE問題進行分類。目前，在解決虛擬網絡映射資源分配問題時，主流的虛擬網絡映射算法可根據對多個虛擬網絡請求映射順序是否進行預處理，分為基于順序的VNE算法和基于優先級的VNE算法2類。基于順序的虛擬網絡映射算法[9,10]只是根據請求到達的先后順序，對先到達的虛擬網絡請求優先分配物理資源，由于未考慮后續映射的成功率，容易造成因剩余物理資源不足而拒絕后續的虛擬網絡請求的問題，導致請求接受率較低。而基于優先級的虛擬網絡映射算法通常采用時間窗模型，通過分析具體業務類型來確定虛擬網絡請求的優先級[11 - 15]。其中，文獻[13]建立了基于用戶優先級的整數線性規劃模型,并提出基于改進粒子群算法進行虛擬網絡映射。文獻[14]通過引入蟻群算法來求解基于用戶優先級的虛擬網絡映射問題。文獻[15]根據不同虛擬網絡請求的優先級使用2種不同的鏈路映射方式，提高虛擬網絡請求的接受率和物理資源的利用率。由于虛擬網絡請求的優先級不僅受業務類型不同的影響，還由資源消耗、映射成本、等待時間和持續時間等綜合因素共同確定。然而以上的虛擬網絡映射算法都忽略了虛擬網絡請求自身業務的差異性和屬性參數對請求映射順序的影響，造成虛擬網絡請求等待時間過長從而可能導致映射失敗，請求接受率降低的同時后續鏈路映射成本相應增加，用戶體驗較差。而恰當地處理并調整虛擬網絡映射的順序，會有效提升虛擬網絡映射算法的性能，縮短虛擬網絡請求的等待時間并提高虛擬網絡請求接受率，帶給基礎設施提供商更大的收益。

為了克服虛擬網絡映射的難點并彌補上述算法的不足，同時高效利用物理網絡資源以提高請求接受率，本文考慮了虛擬網絡請求的粗化程度、業務類型、資源消耗、等待時間和生命周期等屬性參數，研究了基于虛擬網絡請求的特征，建立恰當的優先級模型，主要做了2部分工作：(1)提出一種基于兩次優先級排序的虛擬網絡映射算法，通過分析業務類型和屬性參數對多個請求進行優先級排序，并以鏈路優先級映射虛擬網絡。(2)設計仿真實驗證明本文所提算法降低了虛擬網絡請求的平均等待時間和映射成本，有效提升了虛擬網絡映射請求接受率和收益開銷比。

2 虛擬網絡映射問題描述

2.1 網絡模型

虛擬網絡映射:可以分為節點和鏈路2個映射階段。

虛擬網絡映射示意如圖1所示。

Figure 1 Diagram of virtual network embedding 圖1 虛擬網絡映射示意圖

2.2 評價指標

本文以虛擬網絡請求的平均等待時間、鏈路映射平均跳數、接受率和收益開銷比評價算法性能。

(1)平均等待時間。在一個時間周期內，虛擬網絡請求的平均等待時間定義為所有接受的虛擬網絡請求等待時間的集合與總到達的請求數量之比。

(1)

其中，Tw(t)為請求的等待時間，A(t)為所有到達網絡的請求集合，|A(t)|為到達網絡的請求的總數，τ為趨近于0的正數，防止分母為0。

(2)鏈路映射平均跳數。鏈路的平均跳數定義為所有接受的虛擬鏈路映射在物理路徑上的平均，對于一個成功映射的虛擬網絡，其平均跳數可反映虛擬網絡在物理網絡上的緊湊程度。

(2)

其中，ML(lv)為lv映射的物理路徑，h(ML(lv))為物理路徑的跳數，|Lv|為虛擬網絡請求中鏈路的總數。

(3)請求接受率。定義為在物理網絡中成功接收的虛擬網絡請求數量與總到達請求數量之比。虛擬網絡請求接受率越高，在一個時間周期T內虛擬網絡請求被成功接受的數目越大，基礎設施提供商所獲得的收益越高。

(3)

其中，Ae(t)為網絡上映射成功的請求集合,|Ae(t)|為映射成功的請求數量。

(4)收益開銷比。

虛擬網絡請求Gv在t時刻的映射收益定義為它所需的資源:

(4)

其中，α是節點與鏈路收益的均衡因子，由于對比算法[9]中均衡因子等于1,為了實現橫向比較，本文統一取α=1。

虛擬網絡請求Gv在t時刻的映射開銷為其總物理資源消耗：

(5)

其中，h(lv)為虛擬鏈路lv映射到物理鏈路的跳數，β為節點與鏈路開銷的均衡因子，本文中β=1，其意義與式(4)中的α一致。

定義網絡的收益開銷比為長期平均收入與長期平均成本之比R/C，值越大，網絡資源利用率越高，VNE算法越高效。

(6)

3 基于兩次優先級排序的虛擬網絡映射算法

相比基于順序的映射算法，基于優先級的映射算法可以協調不同的映射請求，優化資源分配，提高物理資源利用率。因此，本文采用兩次優先級映射排序，對窗口中所有的請求根據優先級確定映射順序，并基于鏈路優先完成虛擬網絡到物理網絡的映射。

3.1 基于業務類型和屬性參數的第一次排序

不同的虛擬網絡請求所承載的業務類型是不同的，根據對時延的敏感程度，業務可以劃分為會話、流、交互和后臺4種[16]。4種業務對應的優先級如表1所示。

Table 1 Service types and priorities of virtual network request

一個待映射請求所需的計算資源是固定的，但消耗的帶寬資源是可變的。為使多個虛擬網絡共享物理資源時申請的資源總量最小化，本文采用邊權重匹配HEM(Heavy Edge Matching)技術粗化請求的拓撲結構。將待映射請求中的鏈路根據帶寬值從大到小排序，如果鏈路2端節點計算資源和小于物理網絡剩余計算資源最大值cpumax，則將2節點整合，并更新請求，生成擁有更大帶寬需求的虛擬網絡拓撲，如果新生成鏈路的帶寬大于最大剩余物理帶寬bwmax且鏈路2端節點計算資源和大于cpumax，則放棄此次整合。具體粗化步驟如算法1所示。

算法1粗化虛擬網絡請求

輸入：Gv,cpumax,bwmax。

輸出：Gv。

1.將鏈路依據帶寬值從大到小排序，結果存入Linklist;

2.for 每一條虛擬鏈路lv∈Linklistdo

4. returnGv

6. 合并2個虛擬節點，更新虛擬網絡請求為G′v;/*G′v為粗化后的Gv*/

7.Coarsening(Gv);

8. returnGv;

9. end if

10. end if

11.end for

定義請求的粗化值Coa(Gv)為請求粗化前的帶寬需求與粗化后的帶寬需求的比值。本文使用粗化值表示請求的粗化程度，相同映射條件下，粗化值越高，請求消耗的物理資源越少，因此對粗化值較高的請求設置更高的優先級。在物理資源有限的情況下，為了獲得最高的收益，由于不同請求的資源需求量和生存周期不同，對持續時間較短的并且資源需求量大的請求設置高優先級可以提高后續請求的映射成功率，提高物理資源利用率。

綜上所述，本文采用粗化程度、請求資源、持續時間和等待時間作為虛擬網絡請求的屬性參數。請求的屬性參數表示為：

(7)

其中，tw為請求的等待時間，當twTw時，η=0。對ψ進行歸一化處理，確保屬性參數的優先級與業務優先級一致。

(8)

其中，ψmax和ψmin分別表示本窗口中所有請求粗化值的最大值和最小值。則請求的優先級如式(9)所示。P(Gv)越大，請求的優先級越高。

P(Gv)=ηPr(Gv)+ψ′

(9)

3.2 基于鏈路權重的第二次排序

3.2.1 概念定義

通過第一次基于業務類型和屬性參數的優先級處理，生成相應的待映射子隊列。對于每一個待映射的虛擬網絡請求，為了將帶寬資源需求大的虛擬鏈路映射至資源充足的物理路徑上，同時保障相鄰虛擬鏈路映射至相鄰物理路徑，第二次優先級排序基于虛擬鏈路權重優先級，優先映射該虛擬網絡請求中權重較高的鏈路上的虛擬節點，并在節點映射完成后選擇跳數最短的物理路徑映射該請求的虛擬鏈路。

(1)鏈路權重：

(10)

其中，dis(ni,ne)min為2節點之間的距離的最小值，本文以節點間的跳數表示2節點的距離;ne代表已經映射的虛擬節點，Ev(nv)為已映射虛擬節點集合。

(2)節點資源度：

(11)

其中，L(nv)為節點nv相鄰鏈路的鏈路集合。

(3)路徑重要度：

(12)

虛擬節點的約束條件為：

cpu(nv)≤cpu(ns)

(13)

bw(nv)≤bw(ns)

(14)

R(nv)≤R(ns)

(15)

虛擬鏈路的約束條件為：

bw(lv)≤bw(Ps)

(16)

其中，路徑的帶寬為路徑上所有鏈路帶寬的最小值。

3.2.2 基于鏈路權重排序算法

計算虛擬網絡中所有鏈路的權重，并按照權重值將鏈路從大到小排序。根據鏈路2端節點映射情況將待映射鏈路分為3類：2端節點都未映射；2端節點已有1個映射成功；2端節點都已映射成功。

算法2TP-VNE

輸入：Gv,Gs。

輸出：M(Gv)。

1. for each虛擬鏈路 do

2. 計算鏈路的權重;

3. end for

4. 將請求中的所有虛擬鏈路按照權重值從大到小排序;

5. for each 待映射鏈路lvdo

6. iflv為第1類虛擬鏈路 do

9. 將集合中的候選物理路徑按照重要度值從大到小排序;

10. for each 候選路徑 do

11. if 路徑2端物理節點滿足ni或nj約束條件式(12)、式(13) do

13. end if

14. end for

15. else iflv為第2類虛擬鏈路 do

18. else

20. end if

21. end if

22.end for

4 性能評估與分析

為了驗證所提算法，本文使用Matlab進行仿真實驗，將本文所提TP-VNE算法與文獻[9]中NC-VNE算法、文獻[13]中M-DPSO算法、文獻[14]中P-VNE算法及文獻[15]中S-VNE算法進行比較，并在平均等待時間、鏈路映射平均跳數、請求接受率、收益開銷比、節點資源利用率和鏈路資源利用率等方面進行性能分析。其中，NC-VNE算法通過建立節點間的連通度模型對節點的資源等級進行劃分；M-DPSO算法利用資源搶占和重映射的方法來建立用戶的優先級，并利用改進后的粒子群算法解決虛擬網絡映射問題；P-VNE算法采用蟻群算法來解決虛擬網絡映射問題，使高優先級用戶相比低優先級用戶獲得更多的額外資源；S-VNE算法利用啟發式虛擬網絡映射算法使虛擬網絡請求可跨越優先級共享底層物理資源，以最小化映射成本。

4.1 實驗參數配置

利用GT-ITM(Georgia Tech Internetwork Topology Models)工具生成參數如表2所示的物理網絡和虛擬網絡拓撲，其中，虛擬網絡的到達時間、生存周期和最長等待時限都是以時間窗為單位，每個時間窗中有100個時間單元。每次實驗運行5 000個時間單元，即50個時間窗，期間約有600個請求到達。為保證實驗的準確性，進行10次實驗，取結果的平均值。

Table 2 Configuration of experimental parameters

4.2 實驗結果與分析

圖2 顯示了5種算法請求的平均等待時間對比情況。從圖2中可以看出，TP-VNE算法的平均等待時間最少，且隨著請求的不斷達到，平均等待時間增長幅度較小，其他4種算法的平均等待時間相對較高，且隨著更多請求的到達，平均等待時間增加較為明顯。這是因為TP-VNE算法考慮了窗口中待映射請求的等待時間屬性參數，對等待時間較長的請求優先進行映射，而其他4種算法則未考慮這一點，使得請求的等待時間較長。因此，TP-VNE算法在請求平均等待時間方面明顯優于其他4種算法。

Figure 2 Average waiting time for requests圖2 請求的平均等待時間

Figure 3 Link average embedding hops圖3 鏈路平均映射跳數

圖4和圖5分別為5種算法的請求接受率和收益開銷比隨著請求不斷增加的變化情況。由圖4和圖5可知，TP-VNE算法的請求接受率和收益開銷比是最高的。這是因為TP-VNE優先映射接近等待時限的請求，降低了請求因等待時間超過Tw被拒絕的可能性，而且相比于其他4種算法，在虛擬網絡請求映射階段，TP-VNE算法考慮了鏈路映射跳數對映射成本的影響，優先映射帶寬需求大的鏈路，盡可能地將虛擬鏈路映射至較短的物理路徑上，減小了映射資源消耗，提高了物理資源利用率。

Figure 4 Request receiving rate圖4 請求接受率

Figure 5 Revenue-cost ratio圖5 收益開銷比

圖6和圖7分別為5種算法的節點資源利用率和鏈路資源利用率的對比情況，其值主要受虛擬網絡請求接受率的影響。由圖6和圖7可知，在仿真運行一段時間后，虛擬網絡請求接受率達到動態平衡，因此節點資源利用率和鏈路資源利用率曲線也趨于平穩，當成功映射1個虛擬網絡請求時，資源利用率曲線就會上升，而拆除1個虛擬網絡節點和鏈路時，資源利用率曲線就會相應降低。TP-VNE算法的節點資源利用率和鏈路資源利用率是最高的，這是由于TP-VNE算法首先根據業務類型進行第一次排序，考慮了窗口中待映射請求的等待時間屬性參數,并優先映射接近等待時限的虛擬網絡請求，保證了最短的等待時間和最大的業務收益；其次按照鏈路權重進行第二次排序，優先將鏈路帶寬資源豐富的虛擬鏈路映射至較短的物理路徑上，提高節點和鏈路的資源利用率，從而提高了物理資源的利用率。

Figure 6 Node resource utilization圖6 節點資源利用率

Figure 7 Link resource utilization圖7 鏈路資源利用率

5 結束語

云計算中的許多資源分配問題可以被描述為虛擬網絡映射問題，盡可能多地接受虛擬網絡請求，增加云數據中心的收入，是云計算提供商的主要目標之一。本文對云計算中多個虛擬網絡請求同時到達時的映射優先級問題和映射過程的消耗問題進行了研究，提出了基于兩次優先級排序的虛擬網絡映射算法，協同多個映射請求。仿真實驗表明，本文所提算法有效降低了請求的平均等待時間，提高了收益開銷比和物理資源利用率。由于算法并未考慮請求的到達、離開導致的資源碎片化對資源利用率的影響，因此，如何在有限的物理資源基礎上承載更多的虛擬網絡請求是下一步的研究方向。