吳譽蘭，舒建文

(1.南昌航空大學(xué)科技學(xué)院，江西南昌332020；2.南昌航空大學(xué)信息工程學(xué)院，江西南昌330063)

1 引言

節(jié)點多屬性網(wǎng)絡(luò)可以在底層的物理網(wǎng)絡(luò)內(nèi)，抽象出多個結(jié)構(gòu)不一致且獨立的網(wǎng)絡(luò)，并且能夠加快資源共享的速度[1]。在節(jié)點多屬性網(wǎng)絡(luò)內(nèi)，基礎(chǔ)設(shè)施供應(yīng)商主要負(fù)責(zé)供給可用的物理資源，網(wǎng)絡(luò)供應(yīng)商主要負(fù)責(zé)把資源轉(zhuǎn)化成網(wǎng)絡(luò)資源，服務(wù)商則會通過網(wǎng)絡(luò)資源為用戶提供服務(wù)。所有網(wǎng)絡(luò)資源都會經(jīng)過多種鏈路和節(jié)點組成[2]。但因為不能無限供應(yīng)資源，所以，在資源有限的情況下收取更多的網(wǎng)絡(luò)請求、同時提升資源使用率，成為當(dāng)前領(lǐng)域內(nèi)較為熱點研究話題。

文獻(xiàn)[3]根據(jù)業(yè)務(wù)類型，粗化虛擬網(wǎng)絡(luò)請求，計算請求優(yōu)先級，初步確定虛擬網(wǎng)絡(luò)映射順序，考慮鏈路帶寬資源需求，根據(jù)鏈路權(quán)重獲取優(yōu)先級，計算最佳映射路徑。該算法縮短了虛擬網(wǎng)絡(luò)請求等待時間，但該算法的平均鏈路映射長度較長。文獻(xiàn)[4]通過管理和編排網(wǎng)絡(luò)功能虛擬化及服務(wù)器，構(gòu)建兩級隊列動態(tài)調(diào)度模型，感知并動態(tài)調(diào)度目前隊列積壓狀態(tài)，并使其穩(wěn)定為較小值，利用Lyapunov隨機優(yōu)化方法，完成映射與時延控制。該算法能夠?qū)崿F(xiàn)最優(yōu)化資源調(diào)度，但網(wǎng)絡(luò)請求接受率和收益開銷較低。

針對上述問題，提出基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點多屬性網(wǎng)絡(luò)映射算法，通過構(gòu)建拓?fù)浣Y(jié)構(gòu)與評價指標(biāo)，挑選網(wǎng)絡(luò)映射區(qū)域，依靠回溯型算法計算sumTR值，得到備選網(wǎng)絡(luò)節(jié)點集合進(jìn)行映射，實現(xiàn)節(jié)點多屬性網(wǎng)絡(luò)映射。

2 節(jié)點多屬性網(wǎng)絡(luò)映射問題描述

2.1 形式化定義

定義3：節(jié)點多屬性網(wǎng)絡(luò)映射問題即一種GV至Gs的映射過程，其能夠描述成M:GV其中，需要滿足與此外，RV與RE分別代表已經(jīng)將底層資源分配至屬性與節(jié)點中的數(shù)量。

在大多數(shù)狀態(tài)下，節(jié)點多屬性網(wǎng)絡(luò)映射問題會通過節(jié)點映射節(jié)點與鏈接映射節(jié)點來構(gòu)成。

1)節(jié)點映射節(jié)點即在滿足CPU約束的基礎(chǔ)上，把節(jié)點屬性映射到底層節(jié)點中；

2)鏈路映射階段即在滿足帶寬約束的基礎(chǔ)上，把鏈接屬性映射到底層路徑中。

2.2 解決目標(biāo)

接收節(jié)點多屬性網(wǎng)絡(luò)的GV在時間t的收益能夠被擬定成

(1)

式中，CPU(vV)為節(jié)點vV需要的CPU，BW(eV)為鏈路eV需要的帶寬[6]。考慮到CPU與帶寬在不同應(yīng)用程序的關(guān)鍵性，因此擬定成一種因子α來調(diào)整式(1)，一種節(jié)點多屬性網(wǎng)絡(luò)的接收收益能夠擬定成

(2)

一種節(jié)點多屬性網(wǎng)絡(luò)的GV在時間t的接收代價能夠描述成式(3)，其也能夠用于擬定分配至底層路徑的資源

(3)

網(wǎng)絡(luò)的長期收益平均值能夠擬定成

(4)

(5)

考慮訪問控制機制[7]，在底層資源沒有被有效地分配至一種新到達(dá)的節(jié)點多屬性網(wǎng)絡(luò)中時，會拒絕對該網(wǎng)絡(luò)的訪問。所以，擬定網(wǎng)絡(luò)的接收比例，其能夠描述成

(6)

式中，VNS為網(wǎng)絡(luò)請求被接收的總量，而VN代表達(dá)到節(jié)點多屬性網(wǎng)絡(luò)的請求數(shù)量。

3 基于拓?fù)浣Y(jié)構(gòu)感知的網(wǎng)絡(luò)模型與評測指標(biāo)

3.1 網(wǎng)絡(luò)模型

節(jié)點多屬性網(wǎng)絡(luò)映射過程如圖1所示。

圖1 節(jié)點多屬性網(wǎng)絡(luò)映射過程

在圖1中，a，b，c代表屬性節(jié)點，A，B，C，D，E，F(xiàn)代表物理節(jié)點，數(shù)字分別表示可用計算資源與節(jié)點計算資源，矩形框代表坐標(biāo)約束，框中的物理節(jié)點為可用的映射節(jié)點。節(jié)點的映射結(jié)果為{a→A，b→B，c→F}，鏈路映射的結(jié)果為{(a，b)→(A，B)，(a，c)→(A，D，E，F(xiàn))}。在節(jié)點多屬性網(wǎng)絡(luò)請求在底層物理網(wǎng)絡(luò)中存在的時間達(dá)到Tv時，底層物理網(wǎng)絡(luò)就會剔除被占用的資源。

3.2 評測指標(biāo)

節(jié)點多屬性網(wǎng)絡(luò)映射評測指標(biāo)如下所示

1)節(jié)點多屬性網(wǎng)絡(luò)的平均鏈路映射長度，其運算如式(7)所示

(7)

式中，h(ev)代表網(wǎng)絡(luò)鏈路映射至物理網(wǎng)絡(luò)中通過的跳數(shù)，|Ev|代表網(wǎng)絡(luò)鏈路的總量。

2)節(jié)點多屬性網(wǎng)絡(luò)的請求接受率，在T時間中，其運算如式(8)所示

(8)

式中，VNrecv(T)代表實現(xiàn)映射的網(wǎng)絡(luò)請求總量，VNrecv(T)代表網(wǎng)絡(luò)請求的總量[8]，δ代表防止分母是0而擬定的無限接近于0的正數(shù)。

3)在t時刻，每映射一個網(wǎng)絡(luò)請求所產(chǎn)生的收益開銷能夠擬定成

(9)

式中，參數(shù)α可以更改節(jié)點收益與鏈路收益權(quán)重，其取值是1。

4 節(jié)點多屬性網(wǎng)絡(luò)映射算法實現(xiàn)

4.1 挑選資源分配區(qū)域

回溯型算法的每次運算即實現(xiàn)一個節(jié)點分配資源[9]。第一個節(jié)點的宿主物理節(jié)點決定了該節(jié)點多屬性網(wǎng)絡(luò)在物理網(wǎng)絡(luò)內(nèi)的資源分配區(qū)域。優(yōu)先使用資源較為豐富的子區(qū)域進(jìn)行資源分配，可以有效地對物理網(wǎng)絡(luò)的負(fù)載進(jìn)行平衡，縮減瓶頸節(jié)點、鏈路與局部堵塞的出現(xiàn)[10]。因此，針對所有物理節(jié)點，運算以該節(jié)點作為中心，以GV平均尺寸的一半作為半徑之中所有節(jié)點的和與sumTR值，挑選與值最大的物理節(jié)點作為第一個節(jié)點的宿主物理節(jié)點。

4.2 物理節(jié)點與網(wǎng)絡(luò)節(jié)點的選擇

本文算法中，網(wǎng)絡(luò)節(jié)點的映射順序與映射坐標(biāo)對算法運行成功率與映射質(zhì)量存在較大的干擾。算法每次運算首先獲得該次運算的備選網(wǎng)絡(luò)節(jié)點集合，隨后從中挑選sumTR值最大的節(jié)點進(jìn)行映射。每次映射的備選網(wǎng)絡(luò)節(jié)點集合能夠描述成：

為了提升網(wǎng)絡(luò)鏈路的映射質(zhì)量，對這些預(yù)選的物理節(jié)點進(jìn)行排序時，除了需要考慮該節(jié)點的資源能力，還需要考慮目前被選取的網(wǎng)絡(luò)節(jié)點存在直接通信關(guān)系與已經(jīng)實現(xiàn)映射的網(wǎng)絡(luò)節(jié)點所映射到的物理節(jié)點。擬定一種備選物理節(jié)點n，其優(yōu)先級擬定成

(10)

4.3 節(jié)點多屬性分析

緊密中心度較高的節(jié)點不一定是處于整體網(wǎng)絡(luò)中心坐標(biāo)的固定節(jié)點，但和網(wǎng)絡(luò)內(nèi)其它節(jié)點的鏈接性一定是最好的。鏈路映射取決于已經(jīng)部署的物理節(jié)點，連接性較高的節(jié)點在鏈路部署的過程中存在更為豐富的選擇[12]。所以，在節(jié)點映射的階段，有限映射距離網(wǎng)絡(luò)中其它節(jié)點鏈接性較好的物理節(jié)點，這樣挑選的節(jié)點間的請求帶寬需求會更加容易滿足，縮減鏈路帶寬的開銷。

物理節(jié)點的度值就是節(jié)點鄰接鏈路數(shù)，其能夠描述成

(11)

其中，lS→nS代表物理鏈路和物理節(jié)點的鏈接，綜合考慮物理節(jié)點的最短鏈接尺寸、可用資源與帶寬資源的實時拓?fù)鋵傩?，?gòu)建物理節(jié)點的緊密中心度運算模型

(12)

擬定存在t種物理節(jié)點，x代表已經(jīng)映射的物理節(jié)點總量，綜合考慮C(nS)，E(nS)，DC(nS)，CC(nS)與已經(jīng)映射節(jié)點的尺寸DI(nS)，其共存在k種評測指標(biāo)，k=4+x，那么節(jié)點多屬性評測指標(biāo)矩陣MPS能夠描述成

(13)

4.4 節(jié)點多屬性網(wǎng)絡(luò)映射

在對節(jié)點多屬性分析的基礎(chǔ)上，本文通過動態(tài)拓?fù)涓兄c資源屬性組成了節(jié)點多屬性網(wǎng)絡(luò)映射方法，該方法能夠分成兩階段：鏈路映射與節(jié)點映射。

首先放置網(wǎng)絡(luò)節(jié)點，把該節(jié)點按照映射優(yōu)先級EP(nV)進(jìn)行排列，挑選出隊列首位的節(jié)點。把該節(jié)點的備用物理節(jié)點按映射優(yōu)先級EP(nS)降序排列。挑選EP(nS)值最大同時滿足節(jié)點資源需求的底層節(jié)點進(jìn)行部署。

在實現(xiàn)請求中所有節(jié)點的部署之后，以鏈路帶寬資源作為權(quán)重，使用k-最短路徑算法，挑選一條滿足虛擬鏈路帶寬，同時跳數(shù)最小的物理路徑部署虛擬鏈路，實現(xiàn)鏈路映射，由此完成基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點多屬性網(wǎng)絡(luò)映射。

5 仿真分析

為了驗證基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點多屬性網(wǎng)絡(luò)映射算法的有效性，在仿真平臺MATLAB下進(jìn)行對比實驗。設(shè)置節(jié)點個數(shù)為200個，運行時間為40s，坐標(biāo)約束為300、600和900。分別采用文獻(xiàn)[3]算法、文獻(xiàn)[4]算法和所提算法進(jìn)行節(jié)點多屬性網(wǎng)絡(luò)映射，得到不同方法的平均鏈路映射長度如表1所示。

表1 不同方法的平均鏈路映射長度

根據(jù)表1中的數(shù)據(jù)可知，在不同坐標(biāo)約束下，所提算法的平均鏈路映射長度均最小，文獻(xiàn)[4]算法的平均鏈路映射長度次之，而文獻(xiàn)[3]算法的平均鏈路映射長度最大，由此可知，所提算法能夠有效縮短鏈路映射長度。

在此基礎(chǔ)上對比不同方法的請求接受率結(jié)果如圖2所示。

圖2 不同方法的請求接受率對比結(jié)果

通過圖2能夠看出，當(dāng)運行時間達(dá)到40s時，文獻(xiàn)[3]算法的平均請求接受率為87%，文獻(xiàn)[4]算法的平均請求接受率為83%，而所提算法的平均請求接受率高達(dá)93%。由此可知，所提算法的請求接受率較高，這是因為所提算法采用拓?fù)浣Y(jié)構(gòu)感知方法，受結(jié)構(gòu)的影響，在選取鏈接路徑時，將已經(jīng)選取過的路徑剔除，以防止路徑資源消耗過度，從而有效提高了請求接受率。

進(jìn)一步驗證所提算法與文獻(xiàn)[3]算法、文獻(xiàn)[4]算法的鏈路映射收益開銷比，對比結(jié)果如圖3所示。

圖3 不同方法的映射收益開銷比對比結(jié)果

通過圖3能夠看出，當(dāng)運行時間達(dá)到40s時，文獻(xiàn)[3]算法的平均映射收益開銷比為0.76，文獻(xiàn)[4]算法的平均映射收益開銷比為0.65，而所提算法的映射收益開銷比為0.87。由此可知，所提算法的鏈路映射收益開銷比相對較高，這是由于拓?fù)浣Y(jié)構(gòu)感知算法的資源濃度能夠綜合路徑啟發(fā)信息，以此來選取路徑，使得資源的消耗更為均勻，接受資源需求高的網(wǎng)絡(luò)幾率更大，從而提高鏈路映射收益開銷比。

6 結(jié)束語

為了提高網(wǎng)絡(luò)請求接受率和收益開銷，縮短平均鏈路映射長度，提出基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點多屬性網(wǎng)絡(luò)映射算法，該算法能夠有效提高網(wǎng)絡(luò)請求接受率和收益開銷，縮短平均鏈路映射長度。但該方法通過拓?fù)浣Y(jié)構(gòu)感知模型依次計算節(jié)點與連接消耗大量的時間，導(dǎo)致映射效率下降。因此下一步的研究，在此基礎(chǔ)上加以優(yōu)化，進(jìn)而提升計算效率。