孫新麗

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

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

中圖分類(lèi)號(hào)：TP393

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

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

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

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

1 模型建立

1.1 VNE模型

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

1.3 VNE收益模型

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

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

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

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

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

2.2 收益懲罰因素

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

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

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

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

3.1 全局資源容量（GRC）

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

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

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

3.2 貪婪節(jié)點(diǎn)映射

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

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

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

4 數(shù)值模擬

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

4.1 模型模擬

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

4.2 性能比較

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

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

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

4.3 敏感性分析

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

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

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

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

4.4 時(shí)間復(fù)雜性

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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