王 軒，楊龍祥

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

0 引 言

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

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

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

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

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

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

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

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

2 多域映射算法分類

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

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

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

在分布式多域映射算法中，根據(jù)映射算法的目標不同，可以分為基于市場的分布式映射和基于競價的分布式映射。

2.1 集中式多域映射算法

2.1.1 基于拓撲結構

(1)抽象化映射。

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

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

(2)機制化映射。

與抽象化映射不同，機制化映射在完成虛擬網(wǎng)絡請求分解后，需要利用每個InP的域內(nèi)拓撲信息，一般會在虛擬網(wǎng)絡請求分段映射中利用增廣圖以獲取映射最優(yōu)解，代表性的算法如下：

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

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

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

2.1.2 基于流量矩陣

現(xiàn)有的集中式多域映射算法都將所處理的虛擬網(wǎng)絡拓撲請求假設為無相加權圖[17]，虛擬網(wǎng)絡拓撲會在虛擬網(wǎng)絡映射中引入不必要的限制，利用虛擬網(wǎng)絡拓撲的方式缺乏現(xiàn)實性[18]。從另一方面來說，服務提供商SPs也更希望將虛擬網(wǎng)絡請求以一個較為抽象的形態(tài)進行分發(fā)，從而排除對任何虛擬網(wǎng)絡拓撲特性的依賴。

因此，在文獻[19]中，主要研究方向為有限信息披露下的多域VNE問題。文章討論了VNP對底層物理網(wǎng)絡資源的可見性，提出了基于流量矩陣的虛擬網(wǎng)絡映射架構，從而能夠利用線性整數(shù)規(guī)劃解決虛擬網(wǎng)絡請求分解問題。

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

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

2.1.3 基于演進算法

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

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

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

2.2 分布式多域映射算法

2.2.1 基于市場的分布式多域映射算法

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

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

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

2.2.2 基于競價的分布式多域映射算法

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

圖3 CAD算法過程

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

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

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

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

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

表1 典型算法總結

3 結束語

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

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

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

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