集中與分布：協同虛擬網絡映射

豐旻　廖建新　王敬宇

摘要：結合傳統集中式和分布式兩類算法各自的特性，提出了協同虛擬網絡映射算法。該算法保留了集中式算法中擁有全局視野的中心控制實體，負責總體控制和關鍵決策，同時將具體映射方案的計算過程交給有限的底層網絡子集實現；唯一的中心控制實體與多個底層節點相互配合協作，共同完成虛擬網絡映射的整個過程。該算法繼承了集中式和分布式算法各自的優勢，有效彌補了二者的缺陷，初步的仿真試驗也證明了其可行性和有效性。

關鍵詞： 網絡虛擬化；虛擬網絡映射；集中；分布；協同虛擬網絡映射

1 網絡虛擬化

作為消除互聯網僵化頑疾的強大工具，網絡虛擬化被視為下一代網絡架構的關鍵技術，獲得了學術界和產業界的廣泛關注[1-5]。網絡虛擬化通過虛擬化技術將作為基礎設施的底層網絡抽象為相應的虛擬底層，通過虛擬資源切片的方式，將多個彼此隔離且異構的虛擬網絡同時映射到其上。許多新的計算和網絡技術都受益于網絡虛擬化，如軟件定義網絡、云計算和數據中心網絡。在網絡虛擬化環境中，傳統的網絡服務提供商自然分化為負責部署、管理和維護底層網絡資源的基礎設施提供商和租用網絡資源構建虛擬網絡以向終端用戶提供多樣化服務的服務提供商。

2 集中式和分布式的虛擬

網絡映射

基礎設施提供商需要采用有效的算法來將虛擬網絡請求映射到底層網絡的特定節點和鏈路上，以更加有效且高效地使用底層網絡資源。這就是虛擬網絡映射問題。然而由于存在多維的資源限制和多個目標，使得無論問題空間是否受限，虛擬網絡映射問題都是NP難的[6]。隨著網絡虛擬化技術的快速發展和應用，虛擬網絡映射便成了其中亟待解決的核心問題之一。

難以駕馭的計算復雜性促使研究者們專注于設計各種啟發式算法來尋找接近最優解的切實可行的映射解決方案[7-14]?，F有虛擬網絡映射算法可以按照不同的標準進行多種分類，如按照節點映射與鏈路映射是同時進行還是先后進行，分為一階段算法和兩階段算法（如文獻[8]、文獻[9]、文獻[11]）；按照涉及單個還是多個基礎設施提供商，分為單域算法（如文獻[9]、文獻[10]、文獻[11]）和多域算法（如文獻[14]）；按照考慮可生存性分配備用冗余資源（如文獻[7]、文獻[8]）與否等標準進行分類。本文中我們考慮虛擬網絡映射實現的控制方式，將現有虛擬網絡映射算法分為集中式的虛擬網絡映射算法和分布式的虛擬網絡映射算法兩大類。

2.1 集中式虛擬網絡映射算法

在集中式算法中，只有一個唯一的中心控制實體負責映射的全部決策。集中式算法的優勢在于這個唯一的中心控制實體通過收集、評估和管理底層網絡中的所有資源信息而具有全局視野，清楚的了解整個網絡的各種信息，因此更可能找出全局最優或者至少接近全局最優的映射方案，資源分配的過程中也不會發生沖突等情況。邏輯上集中的控制也使得根據具體業務需求進行的全局資源調配和優化成為可能，并使得整個虛擬網絡的映射運營過程便于維護調整，提升了網絡控制的便捷性。但是另一方面，這個唯一的控制實體也就成為了整個網絡的“瓶頸”。隨著底層網絡的不斷擴容，中心控制實體與眾多節點間的通信數量將呈指數增長，及時獲取底層資源的實時信息將越來越難以完成，因此對于網絡拓撲不斷變化的動態網絡來說延遲較高。其面對大尺度網絡則很容易出現擴展性問題和產生系統單點故障，而一旦中心控制實體出現問題，整個網絡的映射、運行、管理和維護就會難以為繼。

俞敏嵐等[9]將虛擬網絡映射分為節點映射和鏈路映射兩個階段，并假定底層物理網絡支持靈活的路徑分割和周期性的路徑遷移。算法采用了貪婪的節點映射，鏈路映射階段則使用多商品流算法或K最短路徑算法求解。

Chowdhury等[10]通過在節點映射階段考慮鏈路的帶寬限制，來協調節點映射和鏈路映射。算法結合地理位置約束條件，由底層網絡加上元節點和元鏈路構成增廣的拓撲圖，進而將虛擬網絡映射問題建模成混合整數規劃，并利用確定或隨機取整求解可行的節點映射方案。其鏈路映射算法與文獻[9]相同。

廖建新等[11]提出將多個拓撲特征值集成應用于設計拓撲感知的映射算法。文中提出了6個反映不同網絡拓撲屬性的拓撲特征值，進而利用其各自特點和優勢設計了基于多拓撲特征值的拓撲感知算法。算法核心的節點排序策略也可用于改進其他映射算法。拓撲特征值還被用于拓撲分解，以解開大尺寸虛擬網絡的層次結構，優化映射過程。

2.2 分布式虛擬網絡映射算法

相比于依賴單一中心控制實體的集中式算法，分布式算法則依靠分布廣泛且數量眾多的底層節點。虛擬網絡映射的整個決策由各底層節點共同實現完成，于是負載得以分散，可擴展性得以增強，整個映射過程和網絡運行不會因為單點故障而完全失效。然而，分布式的設計思路也一把雙刃劍，與更好可擴展性、魯棒性相伴的是節點間更大的同步開銷。底層網絡的全局信息，如各個節點和鏈路的狀態，實時資源占用情況等等，都需要有完善的消息傳遞機制在所有底層節點間隨時進行更新和同步，以在各底層節點維護最新的統一的全局信息。因為只有每個底層節點對全局信息了解得越清楚越及時，才越可能做出當前真實網絡條件下的最佳映射決策，并且避免可能出現的沖突和不一致。

Houidi等[12]提出使用多代理系統設計分布式算法。實現節點間協商與同步的消息傳遞采用了洪泛機制，即每個底層節點映射虛擬節點和鏈路后，都向所有其他節點發送消息，告知映射結果。因此消息的數量相對底層網絡的尺寸成指數增長，算法受到過多同步消息和較大映射開銷的困擾，在擴展性和映射性能方面還無法與集中式算法相比。

卿蘇德等[13]提出了基于布隆過濾器的分布式映射算法。算法利用機器學習和推理技術，通過積累的歷史信息在沒有或缺乏底層網絡信息的情況下對節點的能力進行評估，并依賴底層節點的自主映射完成整個虛擬網絡映射。同步消息中捎帶的布隆過濾器實現了有限范圍的信息同步，既有效避免了映射沖突，又規避了傳統洪泛算法的巨大通信開銷。

Chowdhury等[14-15]針對多個基礎設施提供商，提出了根據地域切分和映射的PolyViNE架構，以協調解決基礎設施提供商與服務提供商間的利益沖突。服務提供商將虛擬網絡請求發給多個基礎設施提供商，由其各自提出涉及自己和其他基礎設施提供商網絡的跨域映射方案和報價，最終由服務提供商擇優確定映射方案。另外基礎設施提供商之間也存在競爭，爭奪高利潤的映射任務并盡力將難以牟利的部分留給其他基礎設施提供商。

3 協同虛擬網絡映射算法

集中式算法和分布式算法各自的優劣勢啟發我們在本文中嘗試充分結合利用兩者的特點與優勢，設計一個介于集中與分布控制之間的虛擬網絡映射算法，我們稱之為協同虛擬網絡映射（CVNE）。

集中式算法的優勢源于中心控制實體擁有全局視野，因此我們保留全局唯一的中心控制實體，依然負責收集、評估和管理底層網絡中的所有資源信息，并具有全局視野和關鍵決策的控制權。分布式算法的優勢在于映射的整個決策由眾多底層節點實現完成，分散負載，于是我們將具體細節的映射方案計算過程交給底層節點實現。中心控制實體與底層節點相互配合協作，共同完成虛擬網絡映射。

3.1 協同算法總體流程

當一個虛擬網絡請求達到后，首先進入中心控制實體維護的虛擬網絡請求隊列。中心控制實體采取自定義的排隊機制依次進行虛擬網絡映射。

對于當前進行映射的虛擬網絡請求，如果其虛擬節點數量較少、拓撲結構簡單且無需分區域映射，則中心控制實體首先采取特定算法選取一個或多個底層節點作為“中心節點”。選取中心節點的具體數量由整個系統（包括底層網絡和中心控制實體）的負載情況決定：系統負載較輕時可以選擇合理數量的多個中心節點，而負載較重時則將只選取唯一的中心節點。中心節點的選擇算法可借鑒文獻[11]中的拓撲感知的節點排序算法，即利用基于多拓撲特征值的節點排序策略對底層節點排序，然后選取初步滿足映射要求的候選底層節點中排名較高且自身資源占用率較低的作為中心節點。中心控制實體將當前虛擬網絡請求和全局網絡信息一同發給各中心節點，由其為該虛擬網絡計算映射方案。中心節點獲得全局網絡信息后，進一步從與相鄰節點（一定跳數范圍內）的通信中獲取自己所處局部網絡的實時信息，更新全局網絡信息，以解決中心控制實體獲取底層網絡信息的延遲問題。節點和鏈路映射算法可根據中心節點所屬網絡的具體設置，靈活選用定制的算法。每個中心節點計算出映射方案后發回給中心控制實體，由中心控制實體比較選定最優方案（默認總開銷最少為最優）進行資源分配，完成映射。如果中心節點計算映射方案失敗，則將失敗情況告知中心控制實體，由中心控制實體進行相應調整：重新選擇其他中心節點計算映射方案，或在多次映射失敗后推遲或放棄該虛擬網絡請求。我們將上述過程稱為“簡單網絡映射”。

如果當前虛擬網絡請求的虛擬節點數量較多、拓撲結構復雜或者有地域限制需要分區域映射，則中心控制實體需要在中心節點選擇之前首先對虛擬網絡拓撲進行預處理：對于有地域限制或者跨多個運營商等情況的虛擬網絡請求，優先根據具體限制情況將其自然分解為多個虛擬子網；對于虛擬節點數量較多或拓撲結構復雜的虛擬網絡我們采用KS核分解算法[11]將其分解為一個核心網絡和多個邊緣網絡。自然分解的多個虛擬子網將被相應分配給各底層網絡自治域中處于相鄰邊界的一個或多個中心節點，分別進行多個簡單網絡映射，然后各中心節點將各自的虛擬子網映射方案發回給中心控制實體，由其選擇其中的全局最優（默認總開銷最少為最優）的方案組合進行映射，或進行相應調整。拓撲分解后的核心網絡則首先進行簡單網絡映射。由于每個邊緣網絡通過KS核分解算法生成，核心網絡中與之相連的銜接節點已確定映射方案，因此我們在邊緣網絡映射中將已映射的銜接節點作為下階段的中心節點，其從上階段核心網絡映射的中心節點處得到全局網絡信息和邊緣網絡信息后進行簡單網絡映射。如果邊緣網絡映射的中心節點計算映射方案失敗，則將失敗原因告知核心網絡的中心節點，由其進行相應調整，重新映射對應的銜接節點，或在多次映射失敗后推遲或放棄該虛擬網絡請求。

協同虛擬網絡映射算法相比傳統集中式算法，由于將大量具體的映射任務交由底層中心節點完成，中心控制實體在映射中只負責虛擬網絡請求的預處理、分配、重分配、方案確定和資源分配等，因此負載明顯減輕。由中心控制實體在頭尾階段進行全局最優的決策，由分布的中心節點進行局部最優的方案計算，保證了最終的映射方案是接近最優解的，也不會出現映射沖突等情況。動態網絡的延遲問題由于中心節點從中心控制實體處獲取的全局網絡信息與在所處局部網絡中的實時信息更新相結合而得以有效解決；面對大尺度網絡的擴展性問題和系統單點故障問題也將得到極大緩解。

相比傳統分布式算法，協同虛擬網絡映射算法中雖然每個底層節點都具備成為中心節點的能力，但是每一次映射只有少數更有能力的優質節點被選中，映射任務限定在有限的底層網絡子集中。映射沖突由于中心控制實體的存在得以有效避免。這些都使得節點間的同步開銷大大降低，無需采取洪泛等產生大量同步消息的消息傳遞機制。多個中心節點同時計算部分或整體映射方案也實現了虛擬網絡映射的并行計算，可以明顯降低映射耗時。

3.2 協同算法映射實例

圖1顯示了服務提供商的兩個虛擬網絡請求通過協同算法映射到基礎設施提供商的底層網絡的實例。圖中實線代表鏈路連接，其粗細反映帶寬大??；虛線代表映射成功的虛擬鏈路；底層網絡節點用大寫字母表示，虛擬網絡節點用小寫字母表示，在映射中被指定為中心節點的底層網絡節點用綠色標明。虛擬網絡請求1和2先后到達，進入虛擬網絡請求隊列中，但由于虛擬網絡請求2預期收益較高，因此將優先映射。虛擬網絡請求2節點較多，于是通過KS核分解算法被分解為紅色的1個核心網絡和藍色的3個邊緣網絡。其核心網絡被中心控制實體分配給底層網絡的中心節點A計算映射方案。3個邊緣網絡在核心網絡映射方案確定后被分別交給下階段的中心節點B、C、F，同時計算各自邊緣網絡的映射方案。最后的總體映射方案由中心控制實體確定，并進行資源分配以完成映射。虛擬網絡請求1由于節點數量少，拓撲簡單，也沒有地域限制，因此無需分解。其被中心控制實體交給底層節點I計算映射方案，最后得以映射。

4 仿真結果

初步的仿真實驗參照文獻[9]、文獻[11]和文獻[13]的網絡環境和參數設置進行，將集中式算法的代表——文獻[9]的算法（以BL表示），以及分布式算法的代表——文獻[13]的基于布隆過濾器的分布式算法（以P2PVNE表示）作為對比算法，定量測試我們的協同虛擬網絡算法（以CVNE表示）在長期平均收益、接受率和收益開銷比3項性能指標上的表現。協同算法中虛擬網絡請求隊列采用了傳統收益優先的排隊機制，即按照預期收益由多到少的順序先后進行映射；各中心節點處的映射算法采用了文獻[11]中的NDC算法。

協同算法與集中式、分布式代表算法的長期平均收益比較如圖2所示。協同算法與集中式、分布式代表算法的長期接受率比較如圖3所示。協同算法與集中式、分布式代表算法的長期收益開銷比比較如圖4所示。從圖2、圖3和圖4中我們可以看到，文獻[13]中的分布式算法在長期平均收益、接受率和收益開銷比3項性能指標上相比文獻[9]中的集中式算法都有了明顯提升，而我們的協同算法在長期接受率和收益開銷比兩項性能指標相比前兩者又有了更大的提升，在長期平均收益上相比分布式算法也有一定的提升?？偟膩砜?，協同虛擬網絡映射算法由于將集中式算法和分布式算法的相對優勢充分結合，有效彌補了二者的缺陷，從而達到了更好的映射性能。

5 結束語

虛擬網絡映射問題是網絡虛擬化中的關鍵挑戰，傳統集中式和分布式的映射算法各有利弊。我們在本文中充分結合利用兩大類算法的相對優勢，設計了兼具集中與分布特點的協同虛擬網絡映射算法。算法相比傳統的集中式和分布式算法的綜合優勢明顯，初步的仿真試驗結果也證明了算法的可行性和有效性。

參考文獻

[1] CHOWDHURY N， BOUTABA R. A survey of network virtualization [J]. Computer Networks， 2010，54（5）： 862-876.

[2] FEAMSTER N， GAO L， REXFORD J. How to lease the Internet in your spare time [J]. ACM SIGCOMM Computer Communication Review， 2007，37（1）： 61-64.

[3] BAVIER A， FEAMSTER N， HUANG M， et al. In VINI veritas： Realistic and controlled network experimentation [J]. ACM SIGCOMM Computer Communication Review， 2006，36（4）： 3-14.

[4] ANDERSON T， PETERSON L， SHENKER S， et al. Overcoming the Internet impasse through virtualization [J]. IEEE Computer Magazine， 2005，38（4）： 34-41.

[5] TURNER J， TAYLOR D. Diversifying the Internet [C]//Proceedings of the Global Telecommunications Conference， 2005. St. Louis， MO， 2005，2： 755-760. doi：10.1109/GLOCOM.2005.1577741.

[6] ANDERSEN D G. Theoretical approaches to node assignment [R]. Unpublished Manuscript， 2002.

[7] YU H， QIAO C， ANAND V， et al. Survivable Virtual Infrastructure Mapping in a Federated Computing and Networking System under Single Regional failures [C]//Proceedings of the IEEE GLOBECOM， 2010：1-6.

[8] YU H， ANAND V， QIAO C， et al. Cost Efficient Design of Survivable Virtual Infrastructure to Recover from Facility Node Failures [C]//Proceedings of the IEEE ICC， 2011：1-6.

[9] YU M， YI Y， REXFORD J， et al. Rethinking virtual network embedding： substrate support for path splitting and migration [J]. ACM SIGCOMM Computer Communication Review， 2008，38（2）： 17-29.

[10] CHOWDHURY N， RAHMAN M， BOUTABA R. Virtual network embedding with coordinated node and link mapping [C]//Proceedings of the IEEE INFOCOM， 2009： 783-791.

[11] LIAO J， FENG M， LI T， et al. Topology-aware Virtual Network Embedding Using Multiple Characteristics [J]. KSII Transactions on Internet and Information Systems， 2014，8（1）： 145-164.

[12] HOUIDI I， LOUATI W， ZEGHLACHE D. A distributed virtual network mapping algorithm [C]//Proceedings of the IEEE ICC， 2008：5634-5640.

[13] 卿蘇德. 網絡虛擬化映射算法研究 [R]. 北京郵電大學博士學位論文. 2013.

[14] CHOWDHURY M， SAMUEL F， BOUTABA R. Polyvine： policy-based virtual network embedding across multiple domains [C]//Proceedings of the 2nd ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures， New York， USA， 2010：49-56.

[15] FENG M， ZHANG L， ZHU X， et al. Topology-aware virtual network embedding through the degree [C]//Proceedings of the IET National Doctoral Academic Forum on Information and Communications Technology， 2013：1-6.