基于拓撲結構感知的節(jié)點多屬性網絡映射算法

吳譽蘭，舒建文

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

1 引言

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

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

針對上述問題，提出基于拓撲結構感知的節(jié)點多屬性網絡映射算法，通過構建拓撲結構與評價指標，挑選網絡映射區(qū)域，依靠回溯型算法計算sumTR值，得到備選網絡節(jié)點集合進行映射，實現節(jié)點多屬性網絡映射。

2 節(jié)點多屬性網絡映射問題描述

2.1 形式化定義

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

在大多數狀態(tài)下，節(jié)點多屬性網絡映射問題會通過節(jié)點映射節(jié)點與鏈接映射節(jié)點來構成。

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

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

2.2 解決目標

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

(1)

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

(2)

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

(3)

網絡的長期收益平均值能夠擬定成

(4)

(5)

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

(6)

式中，VNS為網絡請求被接收的總量，而VN代表達到節(jié)點多屬性網絡的請求數量。

3 基于拓撲結構感知的網絡模型與評測指標

3.1 網絡模型

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

圖1 節(jié)點多屬性網絡映射過程

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

3.2 評測指標

節(jié)點多屬性網絡映射評測指標如下所示

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

(7)

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

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

(8)

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

3)在t時刻，每映射一個網絡請求所產生的收益開銷能夠擬定成

(9)

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

4 節(jié)點多屬性網絡映射算法實現

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

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

4.2 物理節(jié)點與網絡節(jié)點的選擇

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

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

(10)

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

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

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

(11)

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

(12)

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

(13)

4.4 節(jié)點多屬性網絡映射

在對節(jié)點多屬性分析的基礎上，本文通過動態(tài)拓撲感知與資源屬性組成了節(jié)點多屬性網絡映射方法，該方法能夠分成兩階段：鏈路映射與節(jié)點映射。

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

在實現請求中所有節(jié)點的部署之后，以鏈路帶寬資源作為權重，使用k-最短路徑算法，挑選一條滿足虛擬鏈路帶寬，同時跳數最小的物理路徑部署虛擬鏈路，實現鏈路映射，由此完成基于拓撲結構感知的節(jié)點多屬性網絡映射。

5 仿真分析

為了驗證基于拓撲結構感知的節(jié)點多屬性網絡映射算法的有效性，在仿真平臺MATLAB下進行對比實驗。設置節(jié)點個數為200個，運行時間為40s，坐標約束為300、600和900。分別采用文獻[3]算法、文獻[4]算法和所提算法進行節(jié)點多屬性網絡映射，得到不同方法的平均鏈路映射長度如表1所示。

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

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

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

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

通過圖2能夠看出，當運行時間達到40s時，文獻[3]算法的平均請求接受率為87%，文獻[4]算法的平均請求接受率為83%，而所提算法的平均請求接受率高達93%。由此可知，所提算法的請求接受率較高，這是因為所提算法采用拓撲結構感知方法，受結構的影響，在選取鏈接路徑時，將已經選取過的路徑剔除，以防止路徑資源消耗過度，從而有效提高了請求接受率。

進一步驗證所提算法與文獻[3]算法、文獻[4]算法的鏈路映射收益開銷比，對比結果如圖3所示。

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

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

6 結束語

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