跨域虛擬化網(wǎng)絡(luò)最優(yōu)映射模型的設(shè)計(jì)與仿真

王 堯，柴文光

(1.江蘇理工學(xué)院計(jì)算機(jī)工程學(xué)院，江蘇 常州 213001；2.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 廣東 廣州 510006)

1 引言

近年來(lái)，隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)中新型業(yè)務(wù)不斷更新，現(xiàn)有的網(wǎng)絡(luò)體系難以滿足網(wǎng)絡(luò)程序更新后出現(xiàn)的僵化問(wèn)題[1]。為解決網(wǎng)絡(luò)僵化問(wèn)題，跨域虛擬化網(wǎng)絡(luò)應(yīng)運(yùn)而生，而跨域虛擬化網(wǎng)絡(luò)作為各種網(wǎng)絡(luò)的共享虛擬設(shè)施，則需要將單個(gè)網(wǎng)絡(luò)自治域內(nèi)的用戶需求映射到多個(gè)自治域的網(wǎng)絡(luò)環(huán)境中，從而以最小的代價(jià)映射虛擬網(wǎng)絡(luò)請(qǐng)求[2]。

潘淑文[3]等人提出基于最小割集的跨域虛擬化網(wǎng)絡(luò)多層映射算法。該算法首先將無(wú)線接入網(wǎng)融合到虛擬化的資源管理架構(gòu)當(dāng)中；再基于最小割集原理獲取跨域虛擬化網(wǎng)絡(luò)的最小分割集；最后對(duì)獲取的最小分割集進(jìn)行計(jì)算獲取跨域虛擬化網(wǎng)絡(luò)的最佳映射范圍，從而實(shí)現(xiàn)跨域虛擬化網(wǎng)絡(luò)的多層映射。該算法由于未能利用TOPSIS(逼近理想解排序法)對(duì)虛擬化網(wǎng)絡(luò)中虛擬節(jié)點(diǎn)的映射優(yōu)先級(jí)進(jìn)行計(jì)算，所以該算法在對(duì)跨域虛擬化網(wǎng)絡(luò)進(jìn)行多層映射時(shí)，無(wú)法有效檢測(cè)出網(wǎng)絡(luò)中的路徑衰減曲線。趙季紅[4]等人提出基于軟件定義網(wǎng)絡(luò)的跨域虛擬化網(wǎng)絡(luò)多層映射算法。該算法首先對(duì)虛擬化網(wǎng)絡(luò)的區(qū)域性資源進(jìn)行感知；再利用先驗(yàn)式保護(hù)機(jī)制對(duì)映射區(qū)域內(nèi)的虛擬網(wǎng)絡(luò)資源進(jìn)行備份，并通過(guò)D-ViNE算法映射至物理網(wǎng)絡(luò)中；最后采用后驗(yàn)式恢復(fù)算法完成故障的恢復(fù)，從而實(shí)現(xiàn)跨域虛擬化網(wǎng)絡(luò)的多層映射。該算法由于未能對(duì)虛擬節(jié)點(diǎn)指標(biāo)值與正理想解、負(fù)理想解之間的距離進(jìn)行計(jì)算，獲取網(wǎng)絡(luò)內(nèi)指標(biāo)元素的相對(duì)接近程度，因此該算法的映射成本高，且映射精度低。

為解決上述跨域虛擬化網(wǎng)絡(luò)在多層映射時(shí)存在的問(wèn)題，提出基于拓?fù)涓兄目缬蛱摂M化網(wǎng)絡(luò)多層映射算法。

2 節(jié)點(diǎn)的多屬性特征分析

跨域虛擬化網(wǎng)絡(luò)的映射問(wèn)題通常分為鏈路映射與節(jié)點(diǎn)映射兩個(gè)部分[5]，節(jié)點(diǎn)映射作為映射中重要的一部分不僅要承載網(wǎng)絡(luò)的物理節(jié)點(diǎn)，還要滿足節(jié)點(diǎn)的資源請(qǐng)求，所以合理的網(wǎng)絡(luò)節(jié)點(diǎn)部署可以減少虛擬化網(wǎng)絡(luò)多層映射所需要的成本[6]。

跨域虛擬網(wǎng)絡(luò)中節(jié)點(diǎn)中心性能評(píng)價(jià)指標(biāo)分為度中心性、緊密中心性以及中介中心性三種：

度中心性指的是網(wǎng)絡(luò)節(jié)點(diǎn)的鄰接邊數(shù)，可以刻畫節(jié)點(diǎn)的本地影響力，度中心性的值越大作用于鄰邊的節(jié)點(diǎn)就越多，也更加重要。緊密中心性指的是節(jié)點(diǎn)信息傳遞時(shí)的難易程度，若節(jié)點(diǎn)的緊密中心性較高，那么該節(jié)點(diǎn)與虛擬化網(wǎng)絡(luò)中的其他節(jié)點(diǎn)進(jìn)行連接時(shí)會(huì)較為容易，網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)的傳輸時(shí)延也相對(duì)較低。中介中心性指的是虛擬化網(wǎng)絡(luò)中節(jié)點(diǎn)最短路徑數(shù)量與總路徑數(shù)量的占用比。

2.1 節(jié)點(diǎn)屬性分析

跨域虛擬化網(wǎng)絡(luò)的虛擬節(jié)點(diǎn)度值與鏈路數(shù)目有關(guān)，獲取過(guò)程如下式所示：

(1)

式中，獲取的虛擬節(jié)點(diǎn)度值為DC(nV)，網(wǎng)絡(luò)中虛擬鏈路與虛擬節(jié)點(diǎn)的連接用lV→nV表示。

中介中心性可以精準(zhǔn)地表述節(jié)點(diǎn)請(qǐng)求對(duì)于網(wǎng)絡(luò)的重要程度，過(guò)程中虛擬節(jié)點(diǎn)承載的資源請(qǐng)求越多，請(qǐng)求時(shí)映射的成功率也就越大，獲取虛擬節(jié)點(diǎn)的中介中心度過(guò)程如下式所示：

(2)

式中，網(wǎng)絡(luò)中請(qǐng)求節(jié)點(diǎn)之間的最短路徑上虛擬節(jié)點(diǎn)nV的數(shù)量為p(nV)，節(jié)點(diǎn)之間最短路徑的總數(shù)量為p(NV)。

基于主成分分析法對(duì)上述幾種指標(biāo)進(jìn)行降維處理，以此來(lái)規(guī)避由于主觀因素給節(jié)點(diǎn)指標(biāo)權(quán)重帶來(lái)的影響。對(duì)虛擬節(jié)點(diǎn)屬性進(jìn)行評(píng)價(jià)計(jì)算，過(guò)程如下：

1)設(shè)定需要評(píng)價(jià)的虛擬節(jié)點(diǎn)有m個(gè)，構(gòu)建的虛擬節(jié)點(diǎn)的多屬性評(píng)價(jià)指標(biāo)矩陣如下式所示：

(3)

式中，構(gòu)建的虛擬節(jié)點(diǎn)的多屬性評(píng)價(jià)指標(biāo)矩陣用MPV表示[7]。

2)利用Z-score法對(duì)矩陣進(jìn)行標(biāo)準(zhǔn)化處理，獲取標(biāo)準(zhǔn)化矩陣Z。

4)依據(jù)|λI-R|=0對(duì)矩陣的特征值與特征向量進(jìn)行計(jì)算，其中特征值用λj(j=1，2，…，n)表示，特征向量用bj=(b1j，b2j，…，bmj)表示。

(4)

式中，獲取的主成分指標(biāo)矩陣用HV表示。

2.2 虛擬節(jié)點(diǎn)映射優(yōu)先級(jí)

基于TOPSIS(逼近理想解排序法)計(jì)算跨域虛擬化網(wǎng)絡(luò)中虛擬節(jié)點(diǎn)的映射優(yōu)先級(jí)，過(guò)程如下：

(5)

3)對(duì)獲取的主成分指標(biāo)進(jìn)行正理想解與負(fù)理想解進(jìn)行計(jì)算，正理想解為Z+=max(yi1，yi2，…，yip)，負(fù)理想解為Z-=min(yi1，yi2，…，yip)。

4)對(duì)上述獲取的指標(biāo)值與正理想解、負(fù)理想解之間的距離進(jìn)行計(jì)算。

5)利用獲取的距離對(duì)指標(biāo)元素的相對(duì)接近程度進(jìn)行計(jì)算，過(guò)程如下式所示：

(6)

這時(shí)，令：

(7)

式中，虛擬節(jié)點(diǎn)的映射優(yōu)先級(jí)為EP(nV)。

依據(jù)上述的計(jì)算結(jié)果對(duì)虛擬化網(wǎng)絡(luò)的虛擬節(jié)點(diǎn)映射優(yōu)先級(jí)[8]。

3 虛擬化網(wǎng)絡(luò)的多層映射

基于上述獲取的虛擬節(jié)點(diǎn)映射優(yōu)先級(jí)構(gòu)建面向跨域虛擬化網(wǎng)絡(luò)的多層映射算法。

該算法結(jié)合虛擬化網(wǎng)絡(luò)節(jié)點(diǎn)映射與鏈路映射，為一種復(fù)合型映射算法。多層映射算法的整體框架如圖1所示[9]。

圖1 多層映射算法的整體框架

3.1 節(jié)點(diǎn)映射

在跨域虛擬化網(wǎng)絡(luò)中，所有的通信流量都要經(jīng)過(guò)網(wǎng)絡(luò)的中心節(jié)點(diǎn)，因此，要對(duì)中心節(jié)點(diǎn)進(jìn)行映射處理，再按照遞減順序?qū)吘壒?jié)點(diǎn)進(jìn)行映射[10]。

首先設(shè)定中心節(jié)點(diǎn)的最大值為Nsubstrate，獲取過(guò)程如下式所示：

(8)

式中，跨域虛擬化網(wǎng)絡(luò)的底層物理節(jié)點(diǎn)為ns，除ns外的其他物理節(jié)點(diǎn)集用N(ns)表示，節(jié)點(diǎn)ni的CPU資源和ns的連通性用CCPU(ni)與Ccon(ns，ni)表示。

再依據(jù)設(shè)定的Nsubstrate值對(duì)網(wǎng)絡(luò)中物理節(jié)點(diǎn)的承載節(jié)點(diǎn)進(jìn)行映射；再基于網(wǎng)絡(luò)的虛擬邊緣節(jié)點(diǎn)將剩余的物理節(jié)點(diǎn)與中心節(jié)點(diǎn)進(jìn)行連接處理，基于節(jié)點(diǎn)的連通性對(duì)其進(jìn)行排序，過(guò)程如下式所示：

Rstar(ni)=Ccon(ni，nj)CL(ni)

(9)

式中，中心節(jié)點(diǎn)的承載節(jié)點(diǎn)用nj表示，網(wǎng)絡(luò)中物理節(jié)點(diǎn)ni與nj的連通性用Ccon(ni，nj)表示，而節(jié)點(diǎn)的本地資源用CL(ni)表示。在跨域虛擬化網(wǎng)絡(luò)的映射過(guò)程中，邊緣節(jié)點(diǎn)與中心節(jié)點(diǎn)的物理連接值Rstar會(huì)偏高，所以要對(duì)其進(jìn)行優(yōu)先選擇。

3.2 虛擬節(jié)點(diǎn)排序

依據(jù)拓?fù)涓兄Y(jié)構(gòu)，構(gòu)建虛擬節(jié)點(diǎn)排序模型。將網(wǎng)絡(luò)中層次較高的虛擬節(jié)點(diǎn)進(jìn)行映射，并通過(guò)映射結(jié)果對(duì)虛擬節(jié)點(diǎn)進(jìn)行排序；再依據(jù)排序結(jié)果對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)進(jìn)行映射處理，構(gòu)建的排序模型如下式所示：

(10)

式中，網(wǎng)絡(luò)的虛擬節(jié)點(diǎn)子節(jié)點(diǎn)集合為Nchild(nv)。

映射過(guò)程中，首先選擇網(wǎng)絡(luò)中層級(jí)高的根節(jié)點(diǎn)作為映射的承載節(jié)點(diǎn)。再依據(jù)式(10)對(duì)網(wǎng)絡(luò)中的其余物理節(jié)點(diǎn)進(jìn)行排序。

3.3 網(wǎng)絡(luò)節(jié)點(diǎn)評(píng)價(jià)模型

基于網(wǎng)絡(luò)中物理節(jié)點(diǎn)的本地資源，對(duì)虛擬化網(wǎng)絡(luò)中待選的物理節(jié)點(diǎn)優(yōu)先次序進(jìn)行衡量，具體的獲取過(guò)程如下式所示：

(11)

式中，節(jié)點(diǎn)的CPU資源為CCPU(n)。

為了能夠使跨域虛擬化網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接關(guān)系更加平衡，需要構(gòu)建節(jié)點(diǎn)連通性的計(jì)算模型Ccon，基于跨域虛擬化網(wǎng)絡(luò)的可用帶寬資源與節(jié)點(diǎn)距離對(duì)節(jié)點(diǎn)之間的連接性進(jìn)行計(jì)算，過(guò)程如下式所示：

(12)

式中，跨域虛擬化網(wǎng)絡(luò)中節(jié)點(diǎn)ni與nj之間的路徑集為Path(ni，nj)，路徑的可用資源為CBW(p)，路徑條數(shù)為Cdis(p)。這時(shí)若ni與nj并存于同一節(jié)點(diǎn)上，那么上式的計(jì)算結(jié)果為0，獲取的Ccon(ni，nj)值為最大值，而ni與nj之間的距離為二者之間的最短路徑距離，以此代表ni與nj之間的連通性。

基于上述分析，構(gòu)建跨域虛擬化網(wǎng)絡(luò)的底層物理節(jié)點(diǎn)評(píng)價(jià)模型，具體過(guò)程如下式所示：

X=Ccon(ni，nj)+CL(ns)

(13)

式中，構(gòu)建的跨域虛擬化網(wǎng)絡(luò)物理節(jié)點(diǎn)評(píng)價(jià)模型為X。最后對(duì)上述模型進(jìn)行求解，完成對(duì)跨域虛擬化網(wǎng)絡(luò)的多層映射。

4 實(shí)驗(yàn)

為了驗(yàn)證上述算法的整體有效性，需要對(duì)所提方法進(jìn)行測(cè)試。

4.1 實(shí)驗(yàn)結(jié)果及分析

分別采用基于拓?fù)涓兄目缬蛱摂M化網(wǎng)絡(luò)多層映射算法(算法1)、基于最小割集的跨域虛擬化網(wǎng)絡(luò)多層映射算法(算法2)、基于軟件定義網(wǎng)絡(luò)的跨域虛擬化網(wǎng)絡(luò)多層映射算法(算法3)進(jìn)行測(cè)試：

1)采用算法1、算法2以及算法3對(duì)跨域虛擬化網(wǎng)絡(luò)中的路徑衰減曲線進(jìn)行檢測(cè)，檢測(cè)結(jié)果如圖2所示。

圖2 不同算法的路徑衰減曲線測(cè)試結(jié)果

依據(jù)圖2可知，算法1可以有效檢測(cè)出跨域虛擬化網(wǎng)絡(luò)在多層映射時(shí)的路徑衰減曲線，并且檢測(cè)出的路徑衰減曲線與標(biāo)準(zhǔn)的路徑衰減無(wú)限接近，這主要是因?yàn)樗惴?利用TOPSIS(逼近理想解排序法)對(duì)虛擬化網(wǎng)絡(luò)中虛擬節(jié)點(diǎn)的映射優(yōu)先級(jí)進(jìn)行計(jì)算，所以該算法在跨域虛擬化網(wǎng)絡(luò)多層映射時(shí)可以有效檢測(cè)出網(wǎng)絡(luò)中的路徑衰減曲線。

2)將跨域虛擬化網(wǎng)絡(luò)中的虛擬節(jié)點(diǎn)進(jìn)行變換，利用算法1、算法2以及算法3對(duì)映射時(shí)的路徑損耗進(jìn)行測(cè)試，測(cè)試結(jié)果如表1所示。

表1 不同算法的網(wǎng)絡(luò)路徑損耗測(cè)試結(jié)果

依據(jù)表1可知，算法1在虛擬節(jié)點(diǎn)變換的情況下，依然能夠精準(zhǔn)地計(jì)算出網(wǎng)絡(luò)在映射時(shí)的路徑損耗，并且能夠?qū)⒂成鋾r(shí)的映射精準(zhǔn)度維持在98%以上，這主要是因?yàn)樗惴?利用主成分評(píng)價(jià)指標(biāo)矩陣對(duì)虛擬節(jié)點(diǎn)計(jì)算，獲取節(jié)點(diǎn)的正理想解與負(fù)理想解，所以該算法在虛擬節(jié)點(diǎn)變換的情況下依然能夠精準(zhǔn)地檢測(cè)出網(wǎng)絡(luò)的路徑損耗，因此該算法的映射精準(zhǔn)度高。

3)基于上述測(cè)試結(jié)果，在跨域虛擬化網(wǎng)絡(luò)中加入一組噪聲，對(duì)算法1、算法2以及算法3的映射成本進(jìn)行測(cè)試，測(cè)試結(jié)果如表2所示。

表2 不同映射算法的映射成本測(cè)試結(jié)果

依據(jù)表2可知，算法1在噪聲介入的情況下所需的映射成本要低于算法2和算法3，這主要是因?yàn)樗惴?通過(guò)對(duì)指標(biāo)值與正理想解、負(fù)理想解之間的距離進(jìn)行計(jì)算，獲取網(wǎng)絡(luò)內(nèi)指標(biāo)元素的相對(duì)接近程度，所以該算法在對(duì)跨域虛擬化網(wǎng)絡(luò)多層映射時(shí)的映射成本低。

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

近年來(lái)隨著社會(huì)的進(jìn)步科技的發(fā)展，網(wǎng)絡(luò)中的業(yè)務(wù)也在不斷地推陳出新，跨域虛擬化網(wǎng)絡(luò)的出現(xiàn)及時(shí)地解決了業(yè)務(wù)更新后出現(xiàn)的網(wǎng)絡(luò)僵化問(wèn)題，這時(shí)對(duì)網(wǎng)絡(luò)進(jìn)行必要的映射處理成為人們的焦點(diǎn)話題之一。針對(duì)傳統(tǒng)網(wǎng)絡(luò)映射算法中存在的問(wèn)題，提出基于拓?fù)涓兄目缬蛱摂M化網(wǎng)絡(luò)多層映射處理算法。該算法首先對(duì)虛擬化網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性特征進(jìn)行分析；再依據(jù)虛擬化網(wǎng)絡(luò)的分層式拓?fù)浣Y(jié)構(gòu)構(gòu)建虛擬化網(wǎng)絡(luò)節(jié)點(diǎn)映射與鏈路映射相結(jié)合的復(fù)合型映射算法；最后根據(jù)對(duì)網(wǎng)絡(luò)的底層物理節(jié)點(diǎn)評(píng)價(jià)模型的計(jì)算，完成對(duì)跨域虛擬化網(wǎng)絡(luò)的多層映射。該算法在對(duì)虛擬節(jié)點(diǎn)進(jìn)行排序時(shí)還存在一定問(wèn)題，今后會(huì)針對(duì)這一缺陷繼續(xù)對(duì)該算法進(jìn)行優(yōu)化處理。