多域虛擬網絡映射算法研究

王 軒，楊龍祥

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

0 引 言

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

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

1 多域虛擬網絡映射

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

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

圖1 多域虛擬網絡映射算法典型流程

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

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

2 多域映射算法分類

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

圖2 多域虛擬網絡映射算法分類

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

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

2.1 集中式多域映射算法

2.1.1 基于拓撲結構

(1)抽象化映射。

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

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

(2)機制化映射。

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

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

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

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

2.1.2 基于流量矩陣

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

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

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

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

2.1.3 基于演進算法

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

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

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

2.2 分布式多域映射算法

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

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

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

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

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

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

圖3 CAD算法過程

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

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

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

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

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

表1 典型算法總結

3 結束語

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

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

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

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