多域虛擬網(wǎng)絡(luò)映射算法研究

王 軒，楊龍祥

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著現(xiàn)階段網(wǎng)絡(luò)業(yè)務(wù)的不斷多元化，傳統(tǒng)的一個(gè)底層物理網(wǎng)絡(luò)只承載一個(gè)業(yè)務(wù)需求的網(wǎng)絡(luò)商業(yè)模式已經(jīng)不再適用，不可避免地需要提出新的模式—網(wǎng)絡(luò)虛擬化。網(wǎng)絡(luò)虛擬化可以將一個(gè)底層物理網(wǎng)絡(luò)實(shí)例化成虛擬網(wǎng)絡(luò)(virtual network，VN)，優(yōu)化布局達(dá)到配套服務(wù)指標(biāo)。虛擬網(wǎng)絡(luò)主要存在于底層物理網(wǎng)絡(luò)之上，由一些有源和無源的網(wǎng)絡(luò)單元(網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)鏈路)組成。虛擬節(jié)點(diǎn)通過虛擬鏈路連接，形成虛擬拓?fù)?。資源虛擬化技術(shù)的引入可以允許網(wǎng)絡(luò)運(yùn)營商以一種高度靈活和動(dòng)態(tài)的方式管理和修改網(wǎng)絡(luò)[1]。

由于虛擬網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路必須要在滿足用戶需求并且最優(yōu)化可用資源的情況下被映射到底層物理網(wǎng)絡(luò)上[2]，因此出現(xiàn)了虛擬網(wǎng)絡(luò)映射(virtual network embedding，VNE)問題。由于客觀限制的存在(如資源位置、類型)，一個(gè)單獨(dú)的InP可能并不能為虛擬網(wǎng)絡(luò)提供足夠的資源，根據(jù)在虛擬網(wǎng)絡(luò)映射中底層網(wǎng)絡(luò)提供商InP是否唯一，可以將虛擬網(wǎng)絡(luò)映射問題分為單域映射和多域映射[3]。文中重點(diǎn)對(duì)多域虛擬網(wǎng)絡(luò)映射問題進(jìn)行研究。

1 多域虛擬網(wǎng)絡(luò)映射

解決多域映射一種直接的思路是：服務(wù)提供商(SP)首先要與每個(gè)可能的InPs進(jìn)行協(xié)商，然后決定各個(gè)InP映射整個(gè)虛擬網(wǎng)絡(luò)的不同部分。這種方式可以在不改變傳統(tǒng)商業(yè)模式的前提下，相對(duì)簡(jiǎn)單地完成對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求的映射，但是其缺陷在于會(huì)導(dǎo)致SP涉及與多個(gè)InPs的協(xié)商，不能滿足功能分離的目標(biāo)，而且會(huì)增加SP的開銷[4]。針對(duì)這個(gè)問題，現(xiàn)有的多域映射解決方案主要采用如下兩種網(wǎng)絡(luò)商業(yè)模式。

其中一種模式的主要思路是為了避免SPs與InPs協(xié)商，擴(kuò)展傳統(tǒng)的商業(yè)模式(InPs和SPs)，引入虛擬網(wǎng)絡(luò)提供商(VNP)這個(gè)中間角色，它的作用是收集、統(tǒng)計(jì)和分析底層物理網(wǎng)絡(luò)的資源信息并且從服務(wù)提供商接收虛擬網(wǎng)絡(luò)請(qǐng)求，然后將虛擬網(wǎng)絡(luò)請(qǐng)求的不同部分分配給對(duì)應(yīng)的InP進(jìn)行域內(nèi)映射[5-6]。為了確保VNP能進(jìn)行有效的虛擬網(wǎng)絡(luò)分解，許多文獻(xiàn)都利用了一種新的信息共享方案，它需要InPs向VNP提供其物理資源的部分信息[7]，例如對(duì)等節(jié)點(diǎn)的位置以及對(duì)等鏈路的帶寬成本，而不用披露InPs網(wǎng)絡(luò)內(nèi)的拓?fù)浣Y(jié)構(gòu)等信息，保護(hù)了InPs的機(jī)密。利用這種模式的多域虛擬網(wǎng)絡(luò)映射算法的典型流程[8]如圖1所示。

圖1 多域虛擬網(wǎng)絡(luò)映射算法典型流程

在這種模式下，由VNP代替SP，與各個(gè)底層網(wǎng)絡(luò)提供商InPs進(jìn)行映射協(xié)商，從而實(shí)現(xiàn)了網(wǎng)絡(luò)功能的分離，并且減少了SP的開銷。但是VNP必須知道各個(gè)InPs之間的內(nèi)部細(xì)節(jié)和相互協(xié)定，才能做出一個(gè)信息全面的映射，但實(shí)際上VNP在獲取資源信息時(shí)存在困難，并且可能還會(huì)出現(xiàn)VNP壟斷虛擬網(wǎng)絡(luò)映射的情況[9]。

針對(duì)利用VNP的網(wǎng)絡(luò)商業(yè)模式存在的問題，一些文獻(xiàn)提出了另一種多域映射模式，它不需要VNP作為中間商進(jìn)行協(xié)調(diào)映射，而是允許各個(gè)InPs基于共同協(xié)定進(jìn)行分布式映射，而且，在這種分布式的映射模式中將不再有單點(diǎn)的映射失敗或者壟斷權(quán)威(VNP)的存在[10]。

2 多域映射算法分類

基于當(dāng)前多域虛擬映射的相關(guān)映射算法，文中提出一種分類方法，如圖2所示。

圖2 多域虛擬網(wǎng)絡(luò)映射算法分類

首先根據(jù)是否需要VNP作為中間商進(jìn)行協(xié)調(diào)映射，將多域映射算法分為集中式和分布式兩類。隨后，在集中式的多域映射算法中，根據(jù)分解虛擬網(wǎng)絡(luò)請(qǐng)求時(shí)的方法不同，可以分為基于流量矩陣、基于拓?fù)浣Y(jié)構(gòu)和基于演進(jìn)算法三類?；谕?fù)浣Y(jié)構(gòu)研究多域映射的文章主要的研究方向有兩類，一類著眼于對(duì)底層物理網(wǎng)絡(luò)的抽象化，另一類則是通過VNP產(chǎn)生虛擬網(wǎng)絡(luò)請(qǐng)求分段，再在每個(gè)InP上利用網(wǎng)絡(luò)增廣圖分別進(jìn)行映射。

在分布式多域映射算法中，根據(jù)映射算法的目標(biāo)不同，可以分為基于市場(chǎng)的分布式映射和基于競(jìng)價(jià)的分布式映射。

2.1 集中式多域映射算法

2.1.1 基于拓?fù)浣Y(jié)構(gòu)

(1)抽象化映射。

有文獻(xiàn)提出了將多域物理資源抽象化，從而使其看起來像是一個(gè)平面的網(wǎng)絡(luò)底層結(jié)構(gòu)。Vaishnavi等在文獻(xiàn)[11]中擴(kuò)展了該思想，提出了更先進(jìn)的算法，從而使映射包括計(jì)算能力、存儲(chǔ)以及網(wǎng)絡(luò)資源的整個(gè)底層網(wǎng)絡(luò)，將每個(gè)物理域看作是一個(gè)偽節(jié)點(diǎn)[12](pseudo-node)。抽象化完成后得到的偽圖即可認(rèn)為是一個(gè)正常的物理網(wǎng)絡(luò)圖，并且可以利用任何現(xiàn)存的虛擬網(wǎng)絡(luò)映射算法對(duì)其進(jìn)行映射，從而使得現(xiàn)存的映射算法僅需要少許改動(dòng)即可重復(fù)使用。

除了文獻(xiàn)[11]外，Baldine等[13]也提出了一種將底層網(wǎng)絡(luò)提供商抽象化成節(jié)點(diǎn)的機(jī)制?；谔摂M圖的min k-cut，將虛擬網(wǎng)絡(luò)分解成子請(qǐng)求，嘗試對(duì)每個(gè)子集使用子圖同構(gòu)算法，該過程如果失敗則會(huì)重復(fù)進(jìn)行。但其并沒有給出算法實(shí)際的仿真結(jié)果，算法計(jì)算過程復(fù)雜，需要后續(xù)優(yōu)化，并且沒有考慮映射時(shí)間，靜態(tài)的啟發(fā)式算法對(duì)于動(dòng)態(tài)環(huán)境也是不合適的。

(2)機(jī)制化映射。

與抽象化映射不同，機(jī)制化映射在完成虛擬網(wǎng)絡(luò)請(qǐng)求分解后，需要利用每個(gè)InP的域內(nèi)拓?fù)湫畔?，一般?huì)在虛擬網(wǎng)絡(luò)請(qǐng)求分段映射中利用增廣圖以獲取映射最優(yōu)解，代表性的算法如下：

Shen Meng等[7]針對(duì)多域映射問題，提出采用一種估算方案來處理未知的域內(nèi)拓?fù)?，生成增廣的網(wǎng)絡(luò)圖來協(xié)調(diào)節(jié)點(diǎn)映射和鏈路映射的方案,可以在多項(xiàng)式時(shí)間內(nèi)解決虛擬網(wǎng)絡(luò)請(qǐng)求。

Leivadeas等[14]為了解決多域資源映射固有的復(fù)雜性及可擴(kuò)展性等問題，提出了一種請(qǐng)求分解方案—基于迭代本地搜索的元啟發(fā)式算法，以一種能促進(jìn)下一步虛擬鏈路映射到底層路徑的方式，將虛擬節(jié)點(diǎn)映射到底層物理節(jié)點(diǎn)，進(jìn)而實(shí)現(xiàn)成本的有效性，并且有助于在線分解網(wǎng)絡(luò)云環(huán)境中云服務(wù)提供商之間的用戶請(qǐng)求。

之后，Li Shuopeng等[15-16]著重考慮域內(nèi)鏈路與域間對(duì)等鏈路的聯(lián)合關(guān)系，協(xié)調(diào)并最優(yōu)化域內(nèi)和域間鏈路的映射。文中提出的算法在VN請(qǐng)求接受率、網(wǎng)絡(luò)資源利用率以及收益方面都優(yōu)于文獻(xiàn)[7]中提出的方法，在現(xiàn)存的網(wǎng)絡(luò)結(jié)構(gòu)上更容易部署。

2.1.2 基于流量矩陣

現(xiàn)有的集中式多域映射算法都將所處理的虛擬網(wǎng)絡(luò)拓?fù)湔?qǐng)求假設(shè)為無相加權(quán)圖[17]，虛擬網(wǎng)絡(luò)拓?fù)鋾?huì)在虛擬網(wǎng)絡(luò)映射中引入不必要的限制，利用虛擬網(wǎng)絡(luò)拓?fù)涞姆绞饺狈ΜF(xiàn)實(shí)性[18]。從另一方面來說，服務(wù)提供商SPs也更希望將虛擬網(wǎng)絡(luò)請(qǐng)求以一個(gè)較為抽象的形態(tài)進(jìn)行分發(fā)，從而排除對(duì)任何虛擬網(wǎng)絡(luò)拓?fù)涮匦缘囊蕾嚒?/p>

因此，在文獻(xiàn)[19]中，主要研究方向?yàn)橛邢扌畔⑴断碌亩嘤騐NE問題。文章討論了VNP對(duì)底層物理網(wǎng)絡(luò)資源的可見性，提出了基于流量矩陣的虛擬網(wǎng)絡(luò)映射架構(gòu)，從而能夠利用線性整數(shù)規(guī)劃解決虛擬網(wǎng)絡(luò)請(qǐng)求分解問題。

為了克服文獻(xiàn)[19]中虛擬網(wǎng)絡(luò)請(qǐng)求分解和域內(nèi)資源分配問題所耗費(fèi)的大量時(shí)間復(fù)雜度的不足，Dietrich等[8]雖然也是采用流量矩陣來描述虛擬網(wǎng)絡(luò)，但是放寬了在虛擬網(wǎng)絡(luò)請(qǐng)求分解中的整數(shù)限制，從而降低了時(shí)間復(fù)雜度；放寬了域內(nèi)資源分配中的整數(shù)限制，從而減少了運(yùn)行時(shí)間。

然而上述算法缺乏對(duì)多域映射的有效性的考慮，于是Guo Kailing等[20]對(duì)此進(jìn)行改進(jìn)。在虛擬網(wǎng)絡(luò)請(qǐng)求分解階段，他們繼承了Dietrich利用流量矩陣描述虛擬網(wǎng)絡(luò)的思想，隨后采用一種基于粒子群優(yōu)化算法的啟發(fā)式虛擬網(wǎng)絡(luò)請(qǐng)求分解方法。與Dietrich提出的算法相比，該算法可以增加虛擬網(wǎng)絡(luò)請(qǐng)求分解的有效性，其運(yùn)行時(shí)間隨虛擬請(qǐng)求節(jié)點(diǎn)的增加呈線性增加。

2.1.3 基于演進(jìn)算法

近年來，研究者利用蟻群優(yōu)化、顆粒群優(yōu)化[21-23]、遺傳算法[24]等演進(jìn)算法，有效地解決了計(jì)算復(fù)雜的問題，這些問題包括調(diào)度問題、最小重量三角測(cè)量問題、二次阻塞分派問題等。因此針對(duì)虛擬網(wǎng)絡(luò)映射問題，也可以利用演進(jìn)算法進(jìn)行解決。例如，文獻(xiàn)[25]使用顆粒群優(yōu)化算法，在平均收益、虛擬網(wǎng)絡(luò)請(qǐng)求接收率的性能上優(yōu)于Chowdhury等[26]提出的協(xié)調(diào)節(jié)點(diǎn)鏈路映射算法。文獻(xiàn)[27]通過引入基于蟻群優(yōu)化的元啟發(fā)式算法，在服務(wù)質(zhì)量QoS的性能上達(dá)到了最優(yōu)化。文獻(xiàn)[28]根據(jù)節(jié)點(diǎn)排序方法產(chǎn)生基于成本-帶寬和基于馬爾可夫隨機(jī)游走的兩類遺傳算法，與文獻(xiàn)[25]中的顆粒群優(yōu)化算法相比，它們?cè)诘讓泳W(wǎng)絡(luò)提供商InPs的平均收益、請(qǐng)求接收率及收益成本比率等參數(shù)上具有更好的性能。

Isha等[29]提出利用遺傳算法來解決多域虛擬網(wǎng)絡(luò)映射問題，是當(dāng)前應(yīng)用演進(jìn)算法解決多域映射問題的首次嘗試。該算法與文獻(xiàn)[30]中Houidi等提出的動(dòng)態(tài)適應(yīng)性映射算法相比，通過最大化底層網(wǎng)絡(luò)的剩余資源，從而允許InPs具有更大的能力承載其他的虛擬網(wǎng)絡(luò)請(qǐng)求，最終增加底層網(wǎng)絡(luò)的利用率及InPs的收入。

在上一節(jié)基于流量矩陣進(jìn)行多域映射中，Guo Kailing等[21]也利用了基于粒子群優(yōu)化的演進(jìn)算法對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行分解，從而增加虛擬網(wǎng)絡(luò)請(qǐng)求分解的有效性。因此，也可以將其歸為基于演進(jìn)算法進(jìn)行多域虛擬網(wǎng)絡(luò)映射一類。

2.2 分布式多域映射算法

2.2.1 基于市場(chǎng)的分布式多域映射算法

Chowdhury等在文獻(xiàn)[9]中引入了PolyViNE，是一個(gè)基于策略的端到端虛擬網(wǎng)絡(luò)映射架構(gòu)，可以用一個(gè)全局分布式的方式對(duì)跨越多個(gè)InPs的虛擬網(wǎng)絡(luò)進(jìn)行映射，同時(shí)能允許每個(gè)相關(guān)InP在各自的映射域內(nèi)執(zhí)行自己的映射策略。PolyViNE中很重要的一步就是轉(zhuǎn)發(fā)(forwarding)，如果一個(gè)InP只能部分映射一個(gè)VN請(qǐng)求，那么它會(huì)在控制網(wǎng)絡(luò)中，將剩余的請(qǐng)求轉(zhuǎn)發(fā)給別的InPs，以完成整個(gè)VN請(qǐng)求。該方案通過運(yùn)用經(jīng)濟(jì)學(xué)的market-based機(jī)制，在映射過程中的每一步都進(jìn)行重復(fù)投標(biāo)，以保證每個(gè)InP都能提供具有競(jìng)爭(zhēng)性的價(jià)格，從而最小化SP的成本。

Yahaya等在文獻(xiàn)[31]中也運(yùn)用經(jīng)濟(jì)學(xué)基于市場(chǎng)的market-based機(jī)制，通過在參與的InPs之間進(jìn)行協(xié)商自動(dòng)地執(zhí)行QoS策略，也允許域內(nèi)策略的執(zhí)行，這與PolyViNE類似。但是兩者的區(qū)別在于，前者只關(guān)注映射簡(jiǎn)單的路徑，而PolyViNE則致力于映射更復(fù)雜的虛擬網(wǎng)路請(qǐng)求。

基于對(duì)底層網(wǎng)絡(luò)提供商InPs的隱私信息保護(hù)，Toru Mano等借鑒文獻(xiàn)[32]中安全多方計(jì)算(multi-party computation，MPC)的思想，在文獻(xiàn)[33]中使用一個(gè)MPC排序算法得到各個(gè)InP映射價(jià)格的排序，SP通過價(jià)格順序選擇能夠映射整個(gè)虛擬網(wǎng)絡(luò)的價(jià)格最優(yōu)的映射方案。該方案是在運(yùn)行時(shí)間和解的準(zhǔn)確性之間的折中，因此得到的映射解是近似最優(yōu)解，但是它有效地解決了大規(guī)模虛擬網(wǎng)絡(luò)請(qǐng)求下進(jìn)行快速、有效映射的實(shí)際問題，同時(shí)保護(hù)了各個(gè)InPs的機(jī)密信息。

2.2.2 基于競(jìng)價(jià)的分布式多域映射算法

Esposito等[10]針對(duì)虛擬網(wǎng)絡(luò)映射分配問題，借鑒了有關(guān)一致性資源分配的文獻(xiàn)，提出一種一般性的分布式一致性競(jìng)價(jià)機(jī)制(consensus-based auction mechanism for distributed slice embedding，CAD)。該算法的一般性在于通過調(diào)節(jié)策略，可以根據(jù)對(duì)應(yīng)的分布式模型，支持廣泛的應(yīng)用和提供商的目標(biāo)。算法過程如圖3所示。

圖3 CAD算法過程

文章通過將CAD映射方案與兩個(gè)現(xiàn)存的分布式解決方案進(jìn)行對(duì)比(PolyViNE[9]和分布式VNE算法[34])，發(fā)現(xiàn)一致性競(jìng)價(jià)機(jī)制具有更好的收斂特性和資源利用率。并且，作者證實(shí)了通過合理的策略設(shè)計(jì)，CAD算法可以適應(yīng)不同SP和InPs的映射目標(biāo)，從而為多域網(wǎng)絡(luò)虛擬化提供了靈活的資源分配方案。

Esposito以CAD算法為基礎(chǔ)，在文獻(xiàn)中又補(bǔ)充了分布式路徑競(jìng)價(jià)機(jī)制(path auction for distributed embedding，PAD)。在CAD的基礎(chǔ)上要求物理節(jié)點(diǎn)盡可能承載鄰近的虛擬節(jié)點(diǎn)，從而使得每條虛擬鏈路能夠在單獨(dú)的物理鏈路上分配資源，而不是被分配在任意一條無回路的物理路徑上。這樣做的好處在于，可以避免在無回路的物理路徑上映射虛擬鏈路時(shí)引入中介物理節(jié)點(diǎn)。與文獻(xiàn)[10]中的CAD算法相比，當(dāng)需要映射的虛擬鏈路數(shù)量較大時(shí)，PAD具有更高的虛擬網(wǎng)絡(luò)請(qǐng)求接收率。

Zaheer等在文獻(xiàn)[35]中，依靠虛擬資源競(jìng)價(jià)(auction)的真實(shí)性，提出了V-Mart架構(gòu)，利用兩步Vickrey競(jìng)價(jià)模型，為VNP和InPs提供一個(gè)開放的市場(chǎng)模型以及一個(gè)公平的競(jìng)爭(zhēng)環(huán)境。通過在參與的InPs之間進(jìn)行競(jìng)價(jià)和協(xié)商，進(jìn)行虛擬網(wǎng)絡(luò)請(qǐng)求分解，解決多域虛擬網(wǎng)絡(luò)映射問題。但是與文獻(xiàn)[10]相比，V-Mart不能保證本地和InP之間的策略執(zhí)行以及整體的資源利用率。Hausheer等在文獻(xiàn)[36]中也運(yùn)用基于競(jìng)價(jià)的機(jī)制，在網(wǎng)絡(luò)虛擬化環(huán)境中進(jìn)行資源交易，但只是基本解決了虛擬鏈路競(jìng)價(jià)問題。

Flavio Esposito等在文獻(xiàn)[37]中，提出一種基于策略的(policy-based)虛擬網(wǎng)絡(luò)映射架構(gòu)VINEA。該算法的主要優(yōu)點(diǎn)是將策略(高層目標(biāo))與底層映射機(jī)制(資源發(fā)現(xiàn)、虛擬網(wǎng)絡(luò)映射、在物理網(wǎng)絡(luò)上的分配)分離開，可以包含現(xiàn)存的映射方法，并且僅通過實(shí)例化不同的策略就可以將其用于設(shè)計(jì)適用于不同場(chǎng)景的虛擬網(wǎng)絡(luò)映射解決方案。由于VINEA算法也是在一致性協(xié)商的基礎(chǔ)上，以最大化底層物理網(wǎng)絡(luò)的使用率為目標(biāo)，從而最大化InPs的收入，這與作者和Zaheer等在文獻(xiàn)[35-36]中提出的算法是一致的，因此文中也將VINEA算法歸類為基于競(jìng)價(jià)的分布式多域映射。

表1為不同分類下典型算法的總結(jié)。

表1 典型算法總結(jié)

3 結(jié)束語

文中對(duì)當(dāng)前多域虛擬網(wǎng)絡(luò)映射算法進(jìn)行了重點(diǎn)研究，從不同角度對(duì)現(xiàn)有幾種主要的多域虛擬網(wǎng)絡(luò)映射算法進(jìn)行了系統(tǒng)分類，然后詳細(xì)介紹了每種分類下的典型算法，并深入分析了各類算法的優(yōu)缺點(diǎn)。

當(dāng)前多域虛擬網(wǎng)絡(luò)映射算法在虛擬網(wǎng)絡(luò)請(qǐng)求接收率、網(wǎng)絡(luò)資源利用率以及映射成本及收益等性能指標(biāo)上都可以達(dá)到最優(yōu)或者次優(yōu)的映射結(jié)果，通過對(duì)底層網(wǎng)絡(luò)的抽象化以及演進(jìn)算法等方案也可以在解的準(zhǔn)確性和運(yùn)算時(shí)間上達(dá)到折中，但多域映射的研究仍舊有很大的發(fā)展空間，未來的研究方向可以關(guān)注以下兩個(gè)方面：

(1)集中式多域映射：VNP從InPs獲取的信息量越多，映射求解時(shí)間則越長(zhǎng)，但是解的準(zhǔn)確性也會(huì)隨之增加，這需要映射算法進(jìn)行平衡；在有限信息披露下的多域映射問題處理的是靜態(tài)資源信息，而在實(shí)際的虛擬網(wǎng)絡(luò)映射中，需要能根據(jù)當(dāng)前網(wǎng)絡(luò)資源的變化動(dòng)態(tài)調(diào)整參數(shù)的自適應(yīng)映射算法，對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行重映射，從而提高底層物理網(wǎng)絡(luò)的利用率以及虛擬網(wǎng)絡(luò)請(qǐng)求接收率。

(2)分布式多域映射：映射算法中的價(jià)格模型、各個(gè)InPs之間的交互、信譽(yù)管理以及如何對(duì)參與的InPs給予一定的激勵(lì)策略等問題仍舊有很大的研究空間；映射算法的擴(kuò)展性、穩(wěn)定性需要在具有不同域內(nèi)虛擬網(wǎng)絡(luò)映射算法的InPs之間，通過更大的仿真和分布式實(shí)驗(yàn)進(jìn)行探究。