基于全局資源容量的虛擬網(wǎng)絡(luò)嵌入算法

孫新麗

摘要：采用全局資源容量（CRC）度量方法來量化每個底層物理節(jié)點的嵌入潛力，并提出了一種啟發(fā)式虛擬網(wǎng)絡(luò)嵌入算法（CRC-VNE），最大限度地提高基礎(chǔ)設(shè)施提供商（InP）的收益。該算法采用貪婪的負(fù)載均衡方式依次嵌入每個虛擬節(jié)點，并結(jié)合基于Dijkstra算法的最短路徑路由嵌入每個虛擬鏈路。仿真結(jié)果表明：與考慮整個底層物理網(wǎng)絡(luò)資源的RW-MM-SP算法和TA算法相比，所提出的GRC-VNE算法能夠?qū)崿F(xiàn)更低的請求阻塞概率和更高的收益。

關(guān)鍵詞：網(wǎng)絡(luò)虛擬化;全局資源容量;虛擬網(wǎng)絡(luò)嵌入;虛擬網(wǎng)絡(luò)請求

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

近年來網(wǎng)絡(luò)虛擬化受到了研究界的高度關(guān)注[1-3]，網(wǎng)絡(luò)虛擬化可在底層物理網(wǎng)絡(luò)上提供多個虛擬網(wǎng)絡(luò)（VN），以此共享計算和網(wǎng)絡(luò)資源。VN是由一組虛擬節(jié)點（如虛擬路由器）組成的邏輯拓?fù)浣Y(jié)構(gòu)，這些虛擬節(jié)點通過底層物理網(wǎng)絡(luò)上的相應(yīng)虛擬鏈路相互連接[4]。在這種情況下，傳統(tǒng)的互聯(lián)網(wǎng)服務(wù)提供商（ISP）可以分為基礎(chǔ)設(shè)施提供商（lnP）（如云提供商）和服務(wù)提供商（SP）（如云用戶）。多個SP可動態(tài)構(gòu)建VN，并從InP租賃基礎(chǔ)設(shè)施來聚合最終用戶的需求。如果給定一組在節(jié)點和鏈路上具有某些資源需求的VN請求（VNR），則在底層物理網(wǎng)絡(luò)中找到滿足每個VNR的節(jié)點和鏈路的特定子集的問題稱為虛擬網(wǎng)絡(luò)嵌入（VNE）問題[5-6]。在解決VNE問題時，InP通常在底層建立網(wǎng)絡(luò)來最大化其收益。

然而，VNE問題是NP問題[6]。文獻(xiàn)[7]對VNE問題的研究依賴啟發(fā)式算法來平衡性能和計算復(fù)雜性之間的權(quán)衡。通常現(xiàn)有算法只適用于兩種情況：（1）在沒有節(jié)點或鏈路要求的情況;（2）底層物理網(wǎng)絡(luò)中的節(jié)點和鏈路上具有無限的資源。文獻(xiàn)[8]通過分別求解節(jié)點映射和鏈路映射來降低計算復(fù)雜性。文獻(xiàn)[9]通過聯(lián)合優(yōu)化兩個子問題（即節(jié)點映射和鏈路映射）來提高計算性能。文獻(xiàn)[10]提出了協(xié)調(diào)VNE（ CO-VNE）算法來確定性能和計算復(fù)雜度之間的最佳權(quán)衡，即在節(jié)點映射階段考慮了鏈路映射約束，從而了減輕由于分離處理而導(dǎo)致的性能下降。

提出了一種有效的CO -VNE算法來最大化InP的收益，通過建立了全局資源容量（GRC）度量來量化所有節(jié)點在底層物理網(wǎng)絡(luò)中的嵌入潛力。每個節(jié)點的GRC計算都考慮了整個網(wǎng)絡(luò)的資源。利用隨機(jī)游走形式表示GRC并揭示了其物理意義。設(shè)計了一種基于GRC的CO-VNE算法，即基于全局資源容量的虛擬網(wǎng)絡(luò)嵌入（GRC-VNE）。該算法采用負(fù)載均衡的方式將虛擬節(jié)點嵌入到底層物理網(wǎng)絡(luò)中GRC最高的節(jié)點上，并利用最短路徑的路由方法進(jìn)行鏈路映射。

1 模型建立

1.1 VNE模型

在VNE問題中，從底層物理網(wǎng)絡(luò)分配資源（用于節(jié)點的計算資源和鏈路的帶寬資源）來滿足VNR的需求。當(dāng)InP得到一個VNR時，InP應(yīng)該決定是否接受它。如果VNR被接受，則應(yīng)該在相應(yīng)的物理節(jié)點上分配計算資源，并在相應(yīng)的物理鏈路上分配帶寬來滿足VNR的需求，當(dāng)VNR返回時，所分配的資源將被釋放。底層物理網(wǎng)絡(luò)和VNR的模型如下所示：

1.3 VNE收益模型

對于每個VNR，本文都采用基于Amazon WebServices（ AWS）中“按需”云服務(wù)價格方案的“按用戶付費”收益模式[11]。對于VNR的ω為InP創(chuàng)造的收益為：

該上界可以通過以下假設(shè)情況來確定：

（1）每個VNR等同于底層物理網(wǎng)絡(luò);

（2）當(dāng)前的VNR過期時，后續(xù)的VNR到達(dá)。

在這種情況下，每個VNR都滿足于最小的底層物理資源量，并且底層物理網(wǎng)絡(luò)被完全占用。因此，時間積累的收益將最大化，從而收益將最大化。

2.2 收益懲罰因素

實際上，觀察到的InP收益遠(yuǎn)低于底層物理網(wǎng)絡(luò)提供的上界。這種差距是由于與VNR到達(dá)相關(guān)的不規(guī)則性而導(dǎo)致。對于一組非理想的VNR，以下兩種情況將增加InP對收益的懲罰：

（1）情況1：由于資源不足，底層物理網(wǎng)絡(luò)無法容納VNR，因此拒絕VNR。資源不足可能是由于基礎(chǔ)資源限制或不適當(dāng)?shù)腣NE算法浪費了資源。

（2）情況2：即使接受VNR，虛擬邊緣的子集映射到跨越多個邊緣的底層物理網(wǎng)絡(luò)中的路徑上。對于情況1，本文可以將阻塞概率降到最低，使底層物理網(wǎng)絡(luò)以其有限的資源接受大多數(shù)的VNR。對于情況2，本文可以最大限度地提高每個VNR的收益一成本比，從而在單個VNR上盡可能減少資源成本。

3 基于全局資源容量的VNE算法

3.1 全局資源容量（GRC）

作為節(jié)點映射階段考慮鏈路映射約束的嘗試之一，文獻(xiàn)[12]在節(jié)點映射階段考慮了鏈路映射約束，制定了局部資源容量（IRC），并定義為節(jié)點計算資源和鏈路帶寬資源總和的乘積。但是，LRC有以下缺點：

①局部性問題：如文獻(xiàn)[13]所述，節(jié)點的LRC僅考慮節(jié)點本身的資源及其事件鏈路，這并不能揭示節(jié)點的實際嵌入潛力。例如，如圖2（a）所示，節(jié)點A和D的LRC值與50x（ 20+20） =2000個單位相同的LRC值。當(dāng)節(jié)點A的相鄰節(jié)點可用資源大于節(jié)點D的相鄰節(jié)點可用資源時，節(jié)點A的嵌入潛力應(yīng)大于節(jié)點D的嵌入潛力。

②“孤島”問題：當(dāng)網(wǎng)絡(luò)中的負(fù)載分配不平衡時，仍然有大量可用資源的節(jié)點將成為網(wǎng)絡(luò)中的“孤島”，并且基于LRC無法正常利用這些資源節(jié)點。例如，如圖2（b）所示，節(jié)點A仍然有相當(dāng)大量的計算資源，因此即使其事件鏈路的帶寬資源非常有限，其LRC值仍然與節(jié)點B相同。

3.2 貪婪節(jié)點映射

在節(jié)點映射階段，采用貪婪映射算法。其工作原理如下：在計算了底層物理網(wǎng)絡(luò)和VNR的GRC向量后，分別根據(jù)GRC對兩種拓?fù)涞墓?jié)點進(jìn)行降序排序。從底層物理網(wǎng)絡(luò)的負(fù)載平衡角度來看，貪婪節(jié)點映射是通過對兩個節(jié)點進(jìn)行自上而下的處理，并逐個映射節(jié)點來實現(xiàn)，類似于Mergesort算法，只要滿足計算要求，VNR中GRC最大虛擬節(jié)點總可以映射到底層物理。如果使用任何底層物理節(jié)點都不能滿足計算資源需求，那么VNR將會被阻塞。并且該貪婪映射算法的時間復(fù)雜度為O（|V^s‖V^r|）。

3.3 基于最短路徑的鏈路映射

在鏈路映射階段，采用基于最短路徑的鏈路映射算法。對于VN請求中的每一條邊，使用Dijkstra算法來計算底層物理網(wǎng)絡(luò)中相應(yīng)節(jié)點之間的最短路徑。該算法通過對底層物理中沒有足夠可用帶寬資源的所有鏈路進(jìn)行預(yù)分割來提高效率。如果鏈路映射失?。礋o法成功嵌入任何虛擬鏈路），則將恢復(fù)底層物理網(wǎng)絡(luò)狀態(tài)，并將VNR標(biāo)記為阻塞?；谧疃搪窂降逆溌酚成渌惴ǖ臅r間復(fù)雜度為O（|E^r‖E^s|log|V^s|）。

4 數(shù)值模擬

利用數(shù)值模擬來比較GRC-VNE與RW-MM-SP算法[16]和TA算法[17]的性能。考慮兩個性能指標(biāo)：等式（6）的收益和等式（7）的VNR阻塞概率。

4.1 模型模擬

采用了與文獻(xiàn)[18]相似的模型模擬，底層物理網(wǎng)絡(luò)和VNR的拓?fù)浣Y(jié)構(gòu)由GT-ITM工具隨機(jī)生成。對于底層物理網(wǎng)絡(luò)，采用均勻分布隨機(jī)選擇初始可用計算資源和帶寬資源。在每個VNR中，隨機(jī)選擇每個虛擬節(jié)點的計算資源需求和每個虛擬鏈路的帶寬需求。VNR中的虛擬節(jié)點數(shù)根據(jù)均勻分布從2到20進(jìn)行選擇。虛擬鏈路連通率（VNR中任意兩個節(jié)點連接的概率）設(shè)為η。因此，VNR中的平均鏈路數(shù)為η[n（n-l）]/2，其中n是虛擬節(jié)點的數(shù)量。VNR逐個到達(dá)形成泊松過程，平均到達(dá)率為A個請求，每個請求的存在期遵循負(fù)指數(shù)分布，平均為I/μ=500 s。因此，VNR的負(fù)載可以用λ/μ在Erlangs中進(jìn)行量化。實驗?zāi)M的參數(shù)如表1所示。

4.2 性能比較

使用固定流量負(fù)載評估上述三種VNE算法的性能，固定鏈路連通率為0.5 MB/s，并模擬運行50000 s來查看其長期運行結(jié)果。在模擬中，設(shè)定α=β=1，σ=0.00001，d=0.85，。RW-MM-SP和TA的所有參數(shù)分別取選自文獻(xiàn)[16]和[17]。三種算法的長期平均收益如圖3所示。

由圖3可以看出，所提出的GRC-VNE優(yōu)于其他兩種算法。這是由于GRC可以通過克服LRC的局部性問題和“孤島”問題來更有效地量化嵌入潛力。因此，在提供的負(fù)載下，GRC-VNE只有VNR的較小阻塞概率。在我們假設(shè)的隨機(jī)流量模型下，收益可以近似為：

其中，R0（ω）和τω分別是指每個請求的平均收益和每個請求的平均存在期。三種算法的阻塞概率如圖4所示。由圖4可見，本文所提出的算法具有最低的長期阻塞概率，從而收益最高。

4.3 敏感性分析

比較了三種算法在VNR的不同的流量負(fù)載和鏈路連通率下的性能。三種算法在不同流量負(fù)載下的收益和阻塞概率分別如圖5和圖6所示。

由圖5和圖6可以看出，所提出的GRC-VNE算法在所有流量負(fù)載中都獲得了最高收益。收益隨著流量負(fù)載的增加而增加。隨著流量負(fù)載的增加，底層物理網(wǎng)絡(luò)的性能越來越接近其容量。因此，如果接受額外的VNR可能會消耗更多的資源，從而降低收益一成本比。隨著流量負(fù)載的進(jìn)一步增加，收益將趨于平緩。通過觀測所有三種算法的阻塞概率，這些算法將隨著流量負(fù)載的增加而合并。

通過改變VNR的鏈路連通率來進(jìn)行相同的靈敏度分析。靜止?fàn)顟B(tài)下不同鏈路連通率下長期平均收益的比較和阻塞概率的比較分別如圖7和圖8所示。

由圖7和圖8可以看出，所提出的算法產(chǎn)生的收益最高，阻塞概率最低。此外，當(dāng)鏈路連通率為固定值時，收益首先增加然后降低，當(dāng)鏈路連通率是固定值時，導(dǎo)致收益達(dá)到峰值。如等式（18）所示，由阻塞概率和每個請求的收益之間的基本權(quán)衡來實現(xiàn)。隨著鏈路連通率的提高，阻塞概率將單調(diào)增加;而每個請求的平均收益也隨著需要更多資源而增加。由于阻塞概率增加而導(dǎo)致的邊際懲罰完全由每個請求增加收益的邊際收益補(bǔ)償。

4.4 時間復(fù)雜性

比較了在同一底層物理網(wǎng)絡(luò)上嵌入VNR每種算法的平均運行時間，該度量可作為三種算法時間復(fù)雜度的指標(biāo)。本文的仿真環(huán)境為Matlab R2012A，在3.10 GHz Intel Core i3 -2100 CPU和2.00 GBRAM的計算機(jī)上運行。三種算法在不同鏈路連通率下的平均運行時間如表2所示。

由表2所示，所提出的算法對于所有情況下的運行時間最短，其運行時間約為其他兩種算法運行時間的20-30%。該運行時間增益的一部分來源于算法中的優(yōu)化步驟，即在嵌入虛擬鏈路之前預(yù)分割了所有不可行的鏈路，并且對于每個虛擬鏈路只需要執(zhí)行一次最短路徑算法。而對于其它兩種VNE算法中的最短路徑方案，在路徑計算中仍然考慮了不可行鏈路，從而增加了運行時間。

5 結(jié)論

建立了GRC來量化節(jié)點在底層物理網(wǎng)絡(luò)中的嵌入潛力，并提出了一種新型的VNE算法。該算法使用GRC平衡負(fù)載的方式將虛擬節(jié)點映射到底層物理節(jié)點上，采用基于最短路徑的鏈路映射。仿真結(jié)果表明，所提出的算法優(yōu)于其他兩種VNE算法。

參考文獻(xiàn)

[1]范宏偉，胡宇翔，蘭巨龍，基于FPGA的虛擬網(wǎng)絡(luò)功能數(shù)據(jù)包處理加速架構(gòu)[J].計算機(jī)工程，2018，44（08）：112-119+126.

[2]方子璐，楊俊杰，劉娟.基于虛擬局域網(wǎng)的智能變電站通信網(wǎng)絡(luò)實時性仿真[J]電測與儀表，2017，54（24）：62-67+93.

[3]高興海，計算機(jī)網(wǎng)絡(luò)信息安全中虛擬專用網(wǎng)絡(luò)技術(shù)的運用[J].通訊世界，2017（24）：134-135.

[4]周非，高建軍，范馨月，等.無線傳感網(wǎng)絡(luò)中基于虛擬力的節(jié)點動態(tài)覆蓋算法[J].系統(tǒng)仿真學(xué)報，2018，30（08）：2908-2917.

[5]鄒裕，覃中平，混合網(wǎng)絡(luò)的資源分配與虛擬機(jī)部署優(yōu)化算法[J].控制工程，2018，25（ 03）：509-515.

[6]李芳，高翔.局部線性嵌入和深度自編碼網(wǎng)絡(luò)的降維方法的比較[J]中國海洋大學(xué)學(xué)報：自然科學(xué)版，2018，48（2）：215- 222.