多域網(wǎng)絡(luò)中基于時延感知的虛擬網(wǎng)絡(luò)映射方法

趙季紅 崔曌銘 曲樺 張富

收稿日期：2023-06-18；修回日期：2023-08-07? 基金項目：國家重點研發(fā)計劃重點專項資助項目（2018YFB1800305）

作者簡介：趙季紅（1964—），女，陜西西安人，教授，博導(dǎo)，主要研究方向為寬帶通信網(wǎng)、新一代網(wǎng)絡(luò)的管理和控制、物聯(lián)網(wǎng)、語義Web、異構(gòu)融合網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化；崔曌銘（1999—），女（通信作者），陜西西安人，碩士研究生，主要研究方向為網(wǎng)絡(luò)虛擬化、虛擬網(wǎng)絡(luò)映射、資源分配（1019467295@qq.com）；曲樺（1961—），男，陜西西安人，教授，博導(dǎo)，主要研究方向為現(xiàn)代通信網(wǎng)、計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)、5G網(wǎng)絡(luò)關(guān)鍵技術(shù)、新一代網(wǎng)絡(luò)技術(shù)等；張富（1999—），男，陜西西安人，碩士研究生，主要研究方向為網(wǎng)絡(luò)切片資源配置．

摘? 要：隨著各種時延敏感型應(yīng)用的出現(xiàn)，如何提高系統(tǒng)的時延性能已經(jīng)成為了學(xué)術(shù)界的熱門話題。然而，現(xiàn)有的多域映射算法很難滿足虛擬網(wǎng)絡(luò)對時延性能的要求。因此，為了解決這一問題，提出了一種基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法（time delay sensitive virtual network embedding，TDS-VNE）。在節(jié)點映射階段定義了一個節(jié)點傳播時延評價函數(shù)（D），在鏈路映射階段定義了路徑時延感知參數(shù)。仿真結(jié)果表明，提出的映射算法降低了平均網(wǎng)絡(luò)傳播時延且在虛擬網(wǎng)絡(luò)請求接受率、長期收益成本比等指標(biāo)上具有良好的效果。

關(guān)鍵詞：多域網(wǎng)絡(luò)； 虛擬網(wǎng)絡(luò)映射； 網(wǎng)絡(luò)功能虛擬化； 機(jī)器學(xué)習(xí)； 時延感知

中圖分類號：TP393??? 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）02-034-0548-05

doi：10.19734/j.issn.1001-3695.2023.06.0251

Virtual network embedding method based on time delaysensing in multi-domain networks

Zhao Jihong1，2， Cui Zhaoming1， Qu Hua2， Zhang Fu1

（1.School of Communication & Information Engineering， Xian University of Post & Telecommunications， Xian 710121， China; 2.School of Electronic & Information Engineering， Xian Jiaotong University， Xian 710049， China）

Abstract：With the emergence of various delay-sensitive applications， how to improve the systems delay performance has become a hot topic in academic. However， it is difficult for existing multi-domain embedding algorithms to meet the delay performance requirements of virtual networks. Therefore， to solve this problem， this paper proposed a TDS-VNE algorithm. In the node embedding phase，it defined a propagation delay evaluation function（D）. In the link embedding phase，it defined a path delay sensing parameter. Simulation results show that the proposed embedding algorithm reduces the average network propagation delay and has good results on the virtual network request acceptance rate and long-term benefit-cost ratio.

Key words：multi-domain networks; virtual network embedding; network function virtualization; machine learning; delay sensing

0? 引言

現(xiàn)代網(wǎng)絡(luò)已經(jīng)形成了固定網(wǎng)絡(luò)、移動網(wǎng)絡(luò)、空間網(wǎng)絡(luò)等多種異構(gòu)網(wǎng)絡(luò)融合的局面［1，2］。無線網(wǎng)絡(luò)作為上述網(wǎng)絡(luò)的典型代表之一，經(jīng)常應(yīng)用于各種人工智能場景。在這種人工智能場景下，多數(shù)應(yīng)用對時延較敏感，低時延在醫(yī)療、自動駕駛、軍隊等領(lǐng)域的重要性不言而喻。然而，這些高性能的要求對底層網(wǎng)絡(luò)來說是非常嚴(yán)格的。傳統(tǒng)的網(wǎng)絡(luò)系統(tǒng)不能夠有效處理在低時延要求下的資源分配問題，即虛擬網(wǎng)絡(luò)映射問題（virtual network embedding，VNE）［3］。網(wǎng)絡(luò)虛擬化技術(shù)（network virtualization，NV）［4，5］的出現(xiàn)克服了該問題，并且軟件定義網(wǎng)絡(luò)（software defined network，SDN）［6］和網(wǎng)絡(luò)功能虛擬化（network function virtualization，NFV）是解決這一問題的關(guān)鍵。

目前，研究人員已經(jīng)提出了各種虛擬網(wǎng)絡(luò)映射算法。傳統(tǒng)的優(yōu)化目標(biāo)是最大化收益和映射接受率［7～9］，文獻(xiàn)［10］將虛擬網(wǎng)絡(luò)請求（virtual network request，VNR）劃分為多個分區(qū)，并提出基于延遲預(yù)測的多域虛擬網(wǎng)絡(luò)映射算法，通過估計虛擬請求的時延選擇候選物理節(jié)點，并用粒子群優(yōu)化算法生成虛擬網(wǎng)絡(luò)映射結(jié)果，解決了不同域的虛擬網(wǎng)絡(luò)映射，在一定程度上降低了時延。如今，深度學(xué)習(xí)［11］已經(jīng)應(yīng)用于科學(xué)研究的各個領(lǐng)域。文獻(xiàn)［12，13］分別把半監(jiān)督深度強化學(xué)習(xí)和深度遷移強化學(xué)習(xí)算法應(yīng)用于網(wǎng)絡(luò)異常流量的檢測。文獻(xiàn)［14］基于適應(yīng)度矩陣，重點研究了適合虛擬網(wǎng)絡(luò)映射的物理分量。此外，GCN可以更好地關(guān)注網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，實時提取網(wǎng)絡(luò)環(huán)境特征。Zhang等人［15］將聯(lián)邦強化學(xué)習(xí)應(yīng)用于多域虛擬網(wǎng)絡(luò)映射中，提出水平聯(lián)邦學(xué)習(xí)的VNE架構(gòu)，在每個本地服務(wù)器中部署深度強化學(xué)習(xí)（deep reinforcement learning，DRL）模型，重點關(guān)注了多個供應(yīng)商之間的隱私問題，并顯著降低了資源碎片，然而，該算法沒有關(guān)注虛擬網(wǎng)絡(luò)映射的時延特性。文獻(xiàn)［16］提出了圖卷積網(wǎng)絡(luò)（graph convolutional network，GCN）輔助的VNE算法，GCN提取物理節(jié)點的高階空間結(jié)構(gòu)信息，并在節(jié)點映射階段引入強化學(xué)習(xí)，用Floyed算法進(jìn)行鏈路映射。但該算法的有效性是基于單域網(wǎng)絡(luò)環(huán)境的，并且沒有考慮到時延特性。

從現(xiàn)有研究的角度看，已有的虛擬網(wǎng)絡(luò)映射算法多是基于單個域的映射算法，并且映射過程中著重考慮了節(jié)點的計算資源和鏈路的帶寬資源，而忽略了虛擬網(wǎng)絡(luò)映射時產(chǎn)生的網(wǎng)絡(luò)傳播時延，因此在映射過程中這些虛擬網(wǎng)絡(luò)映射算法的有效性不理想。在此基礎(chǔ)上，本文充分考慮了時延感知的相關(guān)問題，并提出基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法。從減少虛擬網(wǎng)絡(luò)平均傳播時延出發(fā)，將強化學(xué)習(xí)應(yīng)用于節(jié)點映射階段并使用批處理梯度下降算法對策略網(wǎng)絡(luò)進(jìn)行訓(xùn)練，選取處理時延較小的物理節(jié)點進(jìn)行映射。在鏈路映射階段設(shè)定路徑時延感知參數(shù)并采用K最短路徑（K-shortest path，KSP）算法進(jìn)行路徑的選擇。

1? 系統(tǒng)模型與問題描述

1.1? 系統(tǒng)模型

1.1.1? 物理網(wǎng)絡(luò)模型

在網(wǎng)絡(luò)虛擬化的環(huán)境中，虛擬網(wǎng)絡(luò)映射需要解決的問題是如何給虛擬網(wǎng)絡(luò)進(jìn)行資源分配。用無向圖GP=（NP，EP，AP）表示物理網(wǎng)絡(luò)，其中AP={CPUNP，BWEP，DNP，DEP，DENP}。

1.1.2? 虛擬網(wǎng)絡(luò)模型

虛擬網(wǎng)絡(luò)將VNR建模為無向加權(quán)圖GV=（NV，EV，AV），其中AV={CPUNV，BWEV，DNV，DEV}。虛擬網(wǎng)絡(luò)映射問題就是在給定物理網(wǎng)絡(luò)GP=（NP，EP，AP）和虛擬網(wǎng)絡(luò)GV=（NV，EV，AV）的情況下，得到映射結(jié)果的過程。圖1表示了一個具體的多域虛擬網(wǎng)絡(luò)映射過程的示意圖，其中底層物理網(wǎng)絡(luò)由固定網(wǎng)絡(luò)域、移動網(wǎng)絡(luò)域和空間網(wǎng)絡(luò)域組成。并且本文在表1中總結(jié)了常用的符號。

1.2? 問題描述

1.2.1? 問題描述

虛擬節(jié)點映射和虛擬鏈路映射是虛擬網(wǎng)絡(luò)映射問題的兩個階段。這兩個階段在滿足虛擬節(jié)點約束和虛擬鏈路約束的條件下，將虛擬網(wǎng)絡(luò)請求映射至底層的物理網(wǎng)絡(luò)。如今，隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，對時延敏感的應(yīng)用層出不窮，平均網(wǎng)絡(luò)傳播時延是一個非常重要的性能指標(biāo)。由于網(wǎng)絡(luò)傳播時延的產(chǎn)生主要體現(xiàn)在節(jié)點和鏈路的傳播上，所以優(yōu)先選擇物理網(wǎng)絡(luò)中節(jié)點處理時延和鏈路傳播時延較低的節(jié)點和鏈路進(jìn)行映射。這樣就可以滿足網(wǎng)絡(luò)對低時延業(yè)務(wù)的服務(wù)需求。

1.2.2? 約束條件

每個VNR都會消耗一定的物理網(wǎng)絡(luò)資源。當(dāng)物理網(wǎng)絡(luò)資源不滿足需求時，會影響VNE的效果。因此，VNE需要滿足一些約束。

a）若虛擬節(jié)點nv映射到物理節(jié)點np上，則nv的計算資源需求應(yīng)小于等于np的計算資源容量。表示如下：

CPU（nv）≤CPU（np），若nv↑np（1）

b）對于虛擬節(jié)點nv，虛擬節(jié)點nv的時延需求不能超過np的處理時延。表示如下：

D（nv）≥D（np）（2）

c）若物理鏈路（npm，npn）上映射了虛擬鏈路（nvj，nvk），則 （nvj，nvk）的帶寬需求應(yīng)小于等于（npm，npn）的帶寬資源容量。

BW（nvj，nvk）≤BW（npm，npn），若（nvj，nvk）↑（npm，npn）（3）

d）對于物理鏈路（npm，npn），映射在物理鏈路中的所有虛擬鏈路的總帶寬資源不能超過物理鏈路的總寬帶資源。

∑|VNR|i=1∑（nvj，nvk）↑（npm，npn）BW（nvj，nvk）i≤BW（npm，npn）（4）

1.2.3? 評價指標(biāo)

a）VNR接受率。

AR=∑Tt=0Ms（GV）∑Tt=0GV（5）

其中：∑Tt=0Ms（GV）代表在時間T內(nèi)成功映射的虛擬網(wǎng)絡(luò)請求的個數(shù)，∑Tt=0GV代表在時間段T內(nèi)到達(dá)的VNR的總數(shù)。在同樣的時間段內(nèi)，接受更多的VNR的算法效果更好。

b）長期平均收益。

LAR=∑Tt=0∑GV∈VNmap（t）RE（GV，t）T（6）

其中：RE（GV，t）代表在t時刻，一個VNR映射成功后的收益；VNmap（t）表示t時刻成功映射的VNR。

c）長期平均收益成本比。

它是一段時間內(nèi)所映射成功的VNR得到的收益和成本的比值。其中CO（GV，t）表示在t時刻，一個VNR映射成功后的成本；RE（GV，t）表示在t時刻，一個VNR映射成功后的收益。

RTC=∑Tt=0∑GV∈VNmap（t）RE（GV，t）∑Tt=0∑GV∈VNmap（t）CO（GV，t）（7）

d）平均網(wǎng)絡(luò)傳播時延。

在t時刻，一個VNR映射成功后的網(wǎng)絡(luò)傳播時延定義為

Delay（GV）=∑nv∈NV∑np∈M（nv）processdelay（np）+∑ev∈EV∑ep∈M（ev）D（ep）（8）

其中：M（nv）表示映射該虛擬節(jié)點的物理節(jié)點；M（ev）表示映射該虛擬鏈路的物理路徑。平均網(wǎng)絡(luò)傳播時延則定義為

AveDelay（GV）=Delay（GV）NUM（NV）+NUM（EV）（9）

2? 一種基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法

基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法（TDS-VNE）為兩階段算法，在節(jié)點映射階段，引入節(jié)點傳播時延評價函數(shù)，映射過程中采用強化學(xué)習(xí)算法。強化學(xué)習(xí)代理通過模型與環(huán)境交互的學(xué)習(xí)能力使虛擬網(wǎng)絡(luò)請求實現(xiàn)動態(tài)映射。策略網(wǎng)絡(luò)以物理網(wǎng)絡(luò)的特征矩陣作為輸入，利用訓(xùn)練好的策略網(wǎng)絡(luò)對矩陣進(jìn)行訓(xùn)練，得到映射概率最高的物理節(jié)點。在鏈路映射階段，引入路徑時延感知參數(shù)，映射過程中采用K最短路徑算法進(jìn)行時延感知的鏈路映射。整體算法框架如圖2所示。

2.1? 基于時延感知的節(jié)點映射

將強化學(xué)習(xí)（reinforcement learning，RL）模型引入到節(jié)點映射過程中，在具有最新剩余資源的當(dāng)前物理網(wǎng)絡(luò)下，為虛擬網(wǎng)絡(luò)請求選取最優(yōu)的節(jié)點映射策略。

2.1.1? 環(huán)境狀態(tài)

物理網(wǎng)絡(luò)的資源會隨著VNR的到達(dá)和離開發(fā)生變化，網(wǎng)絡(luò)節(jié)點也具有更多的拓?fù)鋵傩浴Ｊ紫缺疚慕⒕哂匈Y源和拓?fù)鋵傩缘牡讓泳W(wǎng)絡(luò)的節(jié)點向量并組合成矩陣，并把該矩陣表示為RL模型的環(huán)境狀態(tài)。

環(huán)境狀態(tài)包括以下幾部分：

a）剩余CPU容量：物理網(wǎng)絡(luò)節(jié)點npm剩余CPU容量表示為

CPU（npm）=cpu（npm）（10）

b）帶寬的總和：底層節(jié)點npm連接的多條物理鏈路的帶寬之和。若該節(jié)點帶寬的總和較大時，可以獲得更好的鏈路映射選擇，其中EPnpm表示連接到物理節(jié)點npm的物理鏈路。

SUM_BW（npm）=∑（npm，npn）∈EpnpBW［（npm，npn）］（11）

c）節(jié)點度：連接到底層節(jié)點npm的鏈路數(shù)。如果一個節(jié)點相鄰鏈路較多且級別較低，則更容易連接到其他物理節(jié)點。

DEG（npm）=∑npm∈NPLink（EPnpm）（12）

d）節(jié)點親密度：兩個底層節(jié)點間的跳數(shù)，親密度高的節(jié)點周圍的節(jié)點和鏈路更集中，映射成功率較高。

CLOSENESS（npm）=1∑npn∈φ（npm）hops（npm，npn）（13）

其中：npm與npn代表任意兩個物理節(jié)點；φ（npm）是物理網(wǎng)絡(luò)中滿足約束的節(jié)點集合；hops（npm，npn）代表兩個節(jié)點間的跳數(shù)距離。

e）歐氏距離：歐氏距離體現(xiàn)了節(jié)點的物理位置約束，若忽視了歐氏距離約束，會導(dǎo)致在映射過程中底層物理節(jié)點過于分散，映射成功率下降，且映射成功后網(wǎng)絡(luò)的傳播時延不理想。

DIS（npm，npn）=（Xnpn-Xnpm）2+（Ynpn-Ynpm）2（14）

其中：Xnpm與Xnpn代表了節(jié)點npm和npn的橫坐標(biāo)，Ynpm與Ynpn代表了節(jié)點npm和npn的縱坐標(biāo)。

f）節(jié)點傳播時延評價：節(jié)點傳播時延評價由該節(jié)點的處理時延和與該節(jié)點相連的所有鄰接鏈路的時延平均值之和組成。若底層節(jié)點的節(jié)點傳播時延評價值越小，則該節(jié)點滿足虛擬節(jié)點時延需求的能力越強。節(jié)點傳播時延評價函數(shù)可以表示為

D（npm）=processDelay（npm）+∑Nep∈E（epm）delay（ep）N-1（15）

其中：processDelay（npm）為節(jié)點的處理時延，∑Nep∈E（epm）delay（ep）N-1為與該節(jié)點相連的所有鄰接鏈路的時延平均值之和。

提取物理節(jié)點特征之后，將歸一化值連接到特征向量中。對于底層節(jié)點，特征向量表示如下：

Am={CPU（npm），SUM_BW（npm），DEG（npm），CLOSENESS（npm），DIS（npm，npn），D（npm）}（16）

用一個矩陣表示底層節(jié)點的所有特征向量，得到特征矩陣Mf。

Mf=（A1，A2，…，Ak）T（17）

2.1.2? 策略網(wǎng)絡(luò)

本文的策略網(wǎng)絡(luò)模型使用卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）模型，如圖3所示。

每一級的功能是：

a）輸入層：讀取環(huán)境的最新狀態(tài)，即式（17）計算的狀態(tài)矩陣。

b）卷積層：卷積層對特征矩陣中的每個向量進(jìn)行卷積運算，得到每個特征向量的可用資源形式。本文通過式（18）對節(jié)點的特征矩陣進(jìn)行卷積。其中arvm表示卷積層的第m個輸出，ω表示權(quán)重向量，d表示偏差。

arvm=ω·Am+d（18）

c）softmax層：將卷積層的輸出傳入到該層，為每個物理節(jié)點生成一個概率，表示將虛擬節(jié)點映射到每個物理節(jié)點的概率。對于第m個底層節(jié)點，其概率Pm如式（19）所示。

Pm=earvm∑iearvi（19）

d）過濾層：該層負(fù)責(zé)選擇候選物理節(jié)點。

2.1.3? 獎勵函數(shù)

強化學(xué)習(xí)模型中的代理需要學(xué)習(xí)映射策略πθ（s，a），并且根據(jù)該策略選取合適的底層節(jié)點進(jìn)行虛擬網(wǎng)絡(luò)節(jié)點的映射。映射完所有的節(jié)點后得到的長期累積獎勵影響著該映射策略的性能。但是，成功映射完所有虛擬節(jié)點后并不代表著能成功映射完所有的虛擬鏈路。因此，系統(tǒng)需要在所有虛擬節(jié)點和所有虛擬鏈路成功映射后再根據(jù)結(jié)果計算該請求的獎勵值，并反饋給策略網(wǎng)絡(luò)進(jìn)行權(quán)重系數(shù)的更新，通過不斷迭代優(yōu)化以達(dá)到更好的性能效果。降低映射成本、增加映射收益和降低網(wǎng)絡(luò)傳播時延是本文的主要目標(biāo)，因此本文定義了以下獎勵函數(shù)：

Re=REα×CO+β×D? 若VNR映射成功-∞? 其他（20）

其中：RE表示一個VNR映射成功后的收益；CO表示一個VNR映射成功后的成本；D表示一個VNR映射成功后的網(wǎng)絡(luò)傳播時延；α和β表示常數(shù)參數(shù)，最終將α和β調(diào)整為0.75和0.25。

2.1.4? 模型訓(xùn)練

本文采用批處理梯度下降算法對策略網(wǎng)絡(luò)進(jìn)行更新，每次將選擇batch_size個樣本進(jìn)行訓(xùn)練。本文為VNR中的每個節(jié)點定義一個符號，這個符號代表虛擬節(jié)點所映射的物理節(jié)點，若虛擬節(jié)點nvi定義的符號為m，則表示底層節(jié)點npm對應(yīng)的特征向量的第m維為1，其他維為0，表示為

npm=（01，02，…，1m，…，0k）T（21）

下一步輸出目標(biāo)向量Apm和npm之間的誤差，利用交叉熵?fù)p失定義節(jié)點映射階段的損失函數(shù)。交叉熵?fù)p失公式如下：

Loss（npm，Apm）=-∑mnpmlog（Apm）（22）

然后，使用梯度下降算法計算梯度gf的損失，其中Re為獎勵函數(shù)，α為學(xué)習(xí)率，為了獲取較好的訓(xùn)練效果，本文經(jīng)過多次參數(shù)調(diào)試，最終將α和batch_size調(diào)整為0.05和100。

gl=gf·α·Re（23）

算法1? 基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法

輸入：物理網(wǎng)絡(luò)GP，虛擬網(wǎng)絡(luò)請求GV，迭代次數(shù)P。

輸出：節(jié)點映射結(jié)果M（Node），策略網(wǎng)絡(luò)參數(shù)ω，d。

1? ?initialize（ω，d）? //初始化參數(shù)

2? ?while iteration＜p do

3? ?counter=0

4? ?for req∈GV do? //當(dāng)前虛擬網(wǎng)絡(luò)請求

5??? ?for nv∈req do? //當(dāng)前請求的虛擬節(jié)點

6????? ?initialize（Mf） //初始化狀態(tài)矩陣

7????? ?for npm∈GP do

8??????? Mf←Mf+Am? //提取特征向量

9????? ?end for

10????? α′（Mf）? ?//特征矩陣歸一化

11????? Pm←police_network ω and d? //輸出映射概率

12????? np=e-greddy_select（pm）

13????? update resource in Gp? //更新底層資源

14??? end for

15??? if nv∈req is mapped then? //鏈路映射

16????? linkmap（req）

17??? end if

18??? if req_Map is successfully then

19????? reward=r（req）=REα·CO+β·D

20????? compute Gradient（reward）

21??? end if

22??? counter++

23??? if counter=batch_size then

24????? update（α）? ?//更新學(xué)習(xí)速率

25??? end if

26? end for

27? iteration++

28? end while

2.2? 基于時延感知的鏈路映射

在鏈路映射過程中，本文采用K最短路徑算法將虛擬鏈路映射到固定節(jié)點之間的最短物理路徑上。為了感知時延較小的物理路徑，本文提出了路徑時延感知參數(shù)，具體為

PathPri（l）=bw（l）μ×delay（l）? l∈ep（24）

其中：ep為經(jīng)過最短路徑算法選出的路徑的集合，且l∈ep，每條物理鏈路的時延均為1個時間單位，鏈路的傳播時延由路徑跳數(shù)決定。若當(dāng)前路徑的帶寬資源越高，傳播時延越小，則該路徑的時延感知參數(shù)就越大，就優(yōu)先選取該鏈路。在本文中μ為權(quán)重系數(shù)，取值為1。用K最短路徑算法得到K條候選物理路徑集合，本文中K取值為5。檢查候選路徑是否滿足帶寬約束，若不滿足就直接從候選集合中刪除該路徑。判斷候選路徑集合是否為空集，若為空集則該虛擬鏈路映射失敗。根據(jù)式（24）計算其路徑時延感知參數(shù)，將虛擬鏈路請求映射到時延感知參數(shù)最大的物理路徑上，重復(fù)以上步驟，直至虛擬鏈路集合全部被映射，則該請求被映射成功。具體流程如算法2所示。

算法2? 基于時延感知的鏈路映射算法

輸入：物理網(wǎng)絡(luò)GP；網(wǎng)絡(luò)切片請求GV；節(jié)點映射結(jié)果M（Node）。

輸出：鏈路映射結(jié)果M（Link）。

1? M（Link）←

2? initialize （M（Link））

3? for virtual link ev in GV do

4? Node A=M（Node）.get（.startNode）

5? Node B=M（Node）.get（.endNode）

6? Node Pair=〈Node A ， Node B〉

7????? ep= KSP（Node Pair）

8? for path l in ev do? //剪枝開始

9??? if bw（l）

10? cut l in ep? //剪枝結(jié)束

11? else

12??? 根據(jù)式（24）計算路徑時延感知參數(shù)，并記錄下該集合中參數(shù)最大的路徑lfirst

13? end if

14? end for

15? if ep=

16??? refuse map， return mapped_failed

17? end if

18? M（Link）←M（Link）+{ev→lfirst}

19? break

20? end for

21? ?return M（Link）

2.3? 時間復(fù)雜度分析

基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法（TDS-VNE）的時間復(fù)雜度主要由RL代理的訓(xùn)練和測試兩個階段產(chǎn)生。由于代理在線訓(xùn)練、離線測試，所以只考慮訓(xùn)練階段的時間復(fù)雜度。該算法的時間復(fù)雜度為O（n+n2+mn2），其中提取特征矩陣的復(fù)雜度為O（n），所有特征向量的時間復(fù)雜度為O（n2），對于所有的VNR，更新特征矩陣的復(fù)雜度為O（mn2），n代表物理節(jié)點數(shù)量，m代表成功映射的VNR中的節(jié)點數(shù)。

3? 性能分析

3.1? 實驗環(huán)境

使用GT-ITM工具的transit-stub模型生成多域的底層網(wǎng)絡(luò)。其參數(shù)設(shè)置如表2所示，在物理網(wǎng)絡(luò)中所有節(jié)點都是隨機(jī)的，并且以一定的概率連接。在多域網(wǎng)絡(luò)中，定義了固定網(wǎng)絡(luò)域、移動網(wǎng)絡(luò)域和空間網(wǎng)絡(luò)域。移動網(wǎng)絡(luò)域由骨干節(jié)點組成，存根域與骨干節(jié)點連接。本文把存根域表示為固定網(wǎng)絡(luò)域和空間網(wǎng)絡(luò)域，三個物理域之間各有兩條域間鏈路，且域間鏈路的帶寬資源隨機(jī)分布在50～100 Mbps。本文還生成了一些VNR，其參數(shù)設(shè)置如表3所示，VNR的到達(dá)過程服從泊松分布，在100個時間單位內(nèi)約有4個虛擬網(wǎng)絡(luò)請求。每個虛擬網(wǎng)絡(luò)請求的時間服從指數(shù)分布且平均持續(xù)時間為1 000個時間單位。本文將2 000個請求分為訓(xùn)練集和測試集，仿真運行時間為50 000個時間單位。本文在操作系統(tǒng)為Windows 10、64位的環(huán)境下使用深度學(xué)習(xí)框架TensorFlow［17］構(gòu)建策略網(wǎng)絡(luò)。

3.2? 性能分析

為了評估TDS-VNE算法的性能，本文使用第1章提出的評價指標(biāo)來評估基于時延感知的虛擬網(wǎng)絡(luò)映射算法（TDS-VNE）的性能。將TDS-VNE與蒙特卡羅樹映射算法（Mento Carlo tree search，MCTS）［18］和基于貪婪策略的分布式映射算法（distributed center，DC）［19］以及深度強化學(xué)習(xí)映射算法（DRL）［20］進(jìn)行比較。MCTS需要嘗試多種映射策略，利用強化學(xué)習(xí)算法中的蒙特卡羅樹搜索算法來進(jìn)行虛擬網(wǎng)絡(luò)映射。DRL算法通過多次與環(huán)境進(jìn)行交互，尋找最合適的映射策略。與這兩個算法相比，可以體現(xiàn)出在使用強化學(xué)習(xí)進(jìn)行節(jié)點映射時設(shè)置節(jié)點傳播時延評價函數(shù)的有效性。DC算法使用貪婪策略映射代理節(jié)點，以代理為根節(jié)點使用BFS來完成鏈路映射和剩余節(jié)點映射。與該算法相比，可以體現(xiàn)出強化學(xué)習(xí)與環(huán)境的動態(tài)交互，通過獎勵函數(shù)不斷優(yōu)化最優(yōu)解的特性。

1）VNR接受率? 圖4表示VNR接受率：從圖4可以看出，開始時底層物理資源比較充足，四種算法的VNR接受率都比較高，隨著時間增加資源被迅速占用，四種算法的接受率都開始出現(xiàn)下降的趨勢，伴隨底層資源逐漸減少，算法趨于穩(wěn)定。TDS-VNE依靠強化學(xué)習(xí)選取包含資源和拓?fù)鋵傩缘?個特征與其他三個算法相比有較好的表現(xiàn)。本文可以看到MCTS和DRL的接受率僅次于TDS-VNE，這是因為在真正映射VNR之前，DRL和MCTS都會嘗試進(jìn)行多次迭代，以獲得最優(yōu)的映射策略。它們一直與環(huán)境交互并調(diào)整自己的策略使物理網(wǎng)絡(luò)接受更多的VNR。DC不能根據(jù)環(huán)境來調(diào)整自己的映射策略，無法動態(tài)優(yōu)化，因此接受率較低。

2）長期平均收益和長期收益成本比? 圖5、6分別表示長期平均收益和長期收益成本比。當(dāng)模擬時間為50 000個時間單位時，TDS-VNE相較于其他三種算法有著較高的長期平均收益，是因為它具有較高的VNR接受率，所以獲得了較高的長期平均收益。并且在強化學(xué)習(xí)訓(xùn)練的過程中重置了獎勵函數(shù)，將收益成本比作為虛擬網(wǎng)絡(luò)映射的第一目標(biāo)并返回給強化學(xué)習(xí)代理。因此，與其他算法相比TDS-VNE在長期平均收益和長期收益成本比方面有著更好的效果。

3）平均網(wǎng)絡(luò)傳播時延? 圖7表示平均網(wǎng)絡(luò)傳播時延。四種算法的平均網(wǎng)絡(luò)傳播時延都隨著時間的增長即虛擬網(wǎng)絡(luò)請求的增多而增長。TDS-VNE相較于其他三種算法來說在全階段都有著較低的平均網(wǎng)絡(luò)傳播時延。在虛擬網(wǎng)絡(luò)映射過程中，低時延的節(jié)點和鏈路有限，MCTS算法并未考慮時延性能，因此可能將虛擬節(jié)點和鏈路映射至高時延的節(jié)點和鏈路上，導(dǎo)致映射成功后的平均網(wǎng)絡(luò)傳播時延較高。TDS-VNE算法相較于其他三個算法來說，在節(jié)點映射階段引入節(jié)點傳播時延評價函數(shù)，在鏈路映射階段引入路徑時延感知參數(shù)，選取節(jié)點處理時延較低的節(jié)點和鏈路傳播時延較低的鏈路進(jìn)行映射。因此相較于其他三種算法來說，平均網(wǎng)絡(luò)傳播時延較低。

4? 結(jié)束語

本文研究了在多域異構(gòu)網(wǎng)絡(luò)環(huán)境下，虛擬網(wǎng)絡(luò)映射的時延感知問題，提出了一種基于時延感知的多域虛擬網(wǎng)絡(luò)映射算法。該算法在節(jié)點映射階段定義了一個節(jié)點傳播時延評價函數(shù)，并引入強化學(xué)習(xí)進(jìn)行節(jié)點映射。在鏈路映射階段定義了路徑時延感知參數(shù)，并用K最短路徑算法進(jìn)行鏈路映射。仿真結(jié)果表明，在多域異構(gòu)的網(wǎng)絡(luò)環(huán)境下，TDS-VNE算法得到了較好的性能效果，降低了平均網(wǎng)絡(luò)傳播時延。然而由于本文僅從時延感知的角度出發(fā)，未考慮在節(jié)點和鏈路故障時的虛擬網(wǎng)絡(luò)重映射問題，所以下一步將重點考慮虛擬網(wǎng)絡(luò)重映射。

參考文獻(xiàn)：

［1］Qu Hua， Ma Nan， Yuan Xiaodong， et al.Survivable virtual network embedding based on multi-domain dynamic weighting in space-air-ground integrated network［C］//Proc of the 7th International Confe-rence on Computer and Communication System. Piscataway， NJ： IEEE Press， 2022： 610-615.

［2］Zhang Peiying， Yao Haipeng， Li Maozhen， et al.Virtual network embedding based on modified genetic algorithm［J］. Peer-to-Peer Networking and Applications， 2019，12：481-492.

［3］蔣煒， 索龍， 晉路遙， 等. 數(shù)據(jù)中心虛擬網(wǎng)絡(luò)映射綜述［J］. 電力信息與通信技術(shù)， 2021，19（4）： 9-17. （Jiang Wei， Suo Long， Jin Luyao， et al. Overview of virtual network embedding in data centers［J］. Electric Power Information and Communication Techno-logy， 2021，19（4）： 9-17.）

［4］Shen Xuemin， Gao Jie， Wu Wen， et al. Holistic network virtualization and pervasive network intelligence for 6G［J］. IEEE Communications Surveys & Tutorials， 2021，24（1）： 1-30.

［5］Li Yun， Zhang Zhaoyang， Xia Shichao， et al. A load-balanced re-embedding scheme for wireless network virtualization［J］. IEEE Trans on Vehicular Technology， 2021，70（4）： 3761-3772.

［6］Yang G S， Shin C Y， Yoo Y， et al. A case for SDN-based network virtualization［C］//Proc of the 29th International Symposium on Modeling， Analysis， and Simulation of Computer and Telecommunication Systems. Piscataway， NJ： IEEE Press， 2021： 1-8.

［7］趙季紅， 宋航， 曲樺， 等. 基于強化學(xué)習(xí)的高可靠性多域虛擬網(wǎng)絡(luò)映射算法［J］. 計算機(jī)應(yīng)用研究， 2022，39（6）：1809-1813，1819. （Zhao Jihong， Song Hang， Qu Hua， et al. High-reliability multi-domain virtual network mapping algorithm based on reinforcement learning［J］. Application Research of Computers， 2022，39（6）：1809-1813，1819.）

［8］Hashmi A， Gupta C P. VNE-NR： a node-ranking method for performing topology-aware and resource-driven virtual network embedding［C］//Proc of the 11th International Conference on Computing， Communication and Networking Technologies. Piscataway， NJ： IEEE Press， 2020： 1-6.

［9］Zhang Shunli. Reliable virtual network mapping algorithm with network characteristics and associations［J］. IEEE Access， 2021，9： 48121-48130.

［10］Zhang Peiying， Pang Xue， Ni Yongjing， et al. A multi-domain virtual network embedding algorithm with delay prediction［EB/OL］.（2022）. https：//arxiv.org/abs/2202. 01473.

［11］Dong Shi， Wang Ping， Abbas K. A survey on deep learning and its applications［J］. Computer Science Review， 2021，40： 100379.

［12］Xia Yuanjun， Dong Shi， Peng Tao， et al. Wireless network abnormal traffic detection method based on deep transfer reinforcement learning［C］//Proc of the 17th International Conference on Mobility， Sensing and Networking. Piscataway， NJ： IEEE Press， 2021： 528-535.

［13］Dong Shi， Xia Yuanjun， Peng Tao. Network abnormal traffic detection model based on semi-supervised deep reinforcement learning［J］. IEEE Trans on Network and Service Management， 2021，18（4）： 4197-4212.

［14］Yao Haipeng， Ma Sihan， Wang Jingjing， et al. A continuous-decision virtual network embedding scheme relying on reinforcement learning［J］. IEEE Trans on Network and Service Management， 2020，17（2）： 864-875.

［15］Zhang Peiying， Chen Ning， Li Shibao， et al. Multi-domain virtual network embedding algorithm based on horizontal federated learning［J］. IEEE Trans on Information Forensics and Security， 2023，18：3363-3375.［16］Ma Sihan， Yao Haipeng， Mai Tianle， et al. Graph convolutional network aided virtual network embedding for Internet of Things［J］. IEEE Trans on Network Science and Engineering， 2022，10（1）： 265-274.

［17］Singh P， Manure A. Introduction to TensorFlow 2. 0［M］. Berkeley， CA： Apress， 2020： 1-24.

［18］Haeri S， Trajkovic＇L. Virtual network embedding via Monte Carlo tree search［J］. IEEE Trans on Cybernetics， 2017，48（2）： 510-521.

［19］Nasiri A A， Derakhshan F. An agent based approach for assignment of virtual networks to substrate network for software defined networking［C］//Proc of IEEE International Conference on Smart Energy and Engineering. Piscataway， NJ： IEEE Press， 2018： 308-312.

［20］Zhang Peiying， Wang Chao， Kumar N， et al. Space-air-ground integrated multi-domain network resource orchestration based on virtual network architecture： a DRL method［J］. IEEE Trans on Intelligent Transportation Systems， 2021，23（3）： 2798-2808.