基于SDN的虛擬網絡映射問題研究綜述

張 鑫，賈瑩瑩，王曉璇

(1.南京郵電大學 寬帶無線通信與傳感器技術教育部重點實驗室，江蘇 南京 210003；2.江蘇省無線通信點實驗室，江蘇 南京 210003)

基于SDN的虛擬網絡映射問題研究綜述

張 鑫1,2，賈瑩瑩1,2，王曉璇1,2

(1.南京郵電大學 寬帶無線通信與傳感器技術教育部重點實驗室，江蘇 南京210003；2.江蘇省無線通信點實驗室，江蘇 南京210003)

傳統IP網絡架構越來越不適應日益增長的網絡業務與應用，一種新型的網絡架構應運而生，即軟件定義網絡。它實現數據面和控制面相分離，同時具有集中控制、開放接口、可編程等特性。研究了基于該網絡架構的虛擬網絡映射問題，即如何將帶有約束條件的虛擬網絡請求映射到由傳統電信商提供的底層物理網絡中。首先給出虛擬網絡映射問題的定義及目標，然后對現有的多種經典映射算法進行分類，并同時對比與分析，最后在此基礎上對未來虛擬網絡映射算法提出一些建議與改進思路。

軟件定義網絡；虛擬網絡映射；網絡虛擬化；映射算法

0 引言

目前傳統互聯網的架構難以應對日益復雜和多樣的社會發展，尤其是處在大數據和云計算時代，面對各種紛繁的用戶需求與業務，現有的網絡體系面臨著巨大的壓力與挑戰。針對這種情況，研究學者們提出一種新型的網絡架構——軟件定義網絡(Software Defined Network,SDN)及OpenFlow[1-2]協議，將網絡分為基礎設施層、控制層、應用層，使得網絡扁平化，更好地適應未來網絡的發展趨勢。由于SDN是將底層數據平面分離出一個邏輯的集中控制平面，而網絡虛擬化[3-5]是將物理網絡抽象成一個個虛擬網絡，兩者的相似使得新型網絡下的網絡虛擬化變得更加靈活高效，可以更好地為用戶提供服務與應用。SDN網絡架構圖如圖1所示。

圖1 SDN網絡架構圖

1 虛擬網絡映射問題模型

虛擬網絡映射問題就是將帶有條件約束的虛擬網絡映射到底層物理網絡中。虛擬網絡映射又分為節點映射和鏈路映射，但因節點資源屬性眾多，在映射過程中物理網絡都要滿足，這便成為NP-hard問題。其中映射目標函數的選擇、節點與鏈路的匹配原則都是虛網映射中需要解決的問題。

1.1底層網絡

1.2虛擬網絡

1.3虛擬網絡映射問題描述

MN:?nv∈Nv,MN(nv)∈NS(C(nv)lt;RN(MN(nv)))

(1)

鏈路映射可表示為：

ML:對?lv=(mv,nv)∈Lv,ML(lv)?PS(MN(mv),

MN(nv))

constraints:b(lv)≤RL(P),?P∈ML(lv)

(2)

虛擬網絡映射模型如圖2所示。

圖2 虛擬網絡映射模型

1.4虛網映射算法的主要評價標準

虛擬網絡映射的主要目標是充分利用物理網絡資源，接受更多的虛擬網絡請求，提高底層網絡的運營收益。評價標準相關函數具體定義如下。

(1)收益函數

所有成功映射的虛擬網絡所請求的節點CPU資源和鏈路帶寬資源總和決定虛擬網絡收益，t時刻映射一個虛擬網絡收益可表示為:

(3)

(2)開銷函數

映射開銷即底層網絡為滿足虛網的節點及鏈路資源約束而消耗的物理資源，可表示為：

(4)

(3)底層網絡平均收益函數

(5)

(4)虛擬網絡請求接受率函數

虛網請求接受率是指在某個時間段內虛擬網絡請求成功映射的個數，定義為：

(6)

其中，式(6)中分子部分表示0～T時刻內成功映射虛擬網絡請求個數，式(6)中分母部分表示0～T時刻內虛擬網絡請求總個數。

綜合以上，選擇不同的評價標準會產生不同的結果，在實際問題中要根據不同應用場景，選擇合適的度量函數，以求獲得最大收益和資源的利用率。

2 虛擬網絡映射算法分類

從各種因素考慮，根據資源約束、接入控制、虛網請求處理方式、虛網映射的計算方式、映射類型、拓撲信息等方面比較了最近10年一些經典虛擬網絡映射算法[6-12]，如表1所示。

由于受節點CPU、鏈路帶寬條件約束，而且存在虛擬網絡請求的時間等是不可知的，因此使得虛擬網絡映射研究變得復雜，一些采用忽略節點資源約束、忽略接入控制、假設預先已知虛擬網絡請求信息(離線)等限制地址位置的方式尋求虛擬網絡映射的解決方案；另一些則從擴大問題空間的角度出發，研究貼近實際生活的映射算法。最終可將已有的虛網映射算法分為兩大類：限制地理位置的映射算法[6-7]和不限制地理位置的映射算法[8-12]。

2.1限制地理位置的虛網映射算法

文獻[6]在忽略節點資源約束、假設所有的虛網請求事先已知等限制地理位置的條件下，提出了一種QoSMap機制，該機制在建立虛擬網絡時著重考慮了虛網的QoS與拓撲彈性問題。通過選擇高質量保證的物理鏈路滿足虛網的QoS要求，并利用一跳中繼路由節點構建后備路由路徑以提供虛擬鏈路映射的彈性保障。該算法雖能獲得更優的服務質量和彈性保證，但其資源利用率低，計算開銷大。

表1 虛擬網絡映射算法比較

文獻[7]在離線且未考慮節點映射階段，提出將隱藏跳數(虛擬鏈路映射到的底層路徑經過的中間物理節點)納入到鏈路映射階段，鏈路映射后作為中間節點的物理節點也要消耗CPU資源。算法將虛擬網絡請求分成有特定資源請求和無明確資源請求兩類，先處理有特定需求的請求，目的是在成功映射每個虛擬網絡請求后使得剩余資源盡可能地大(即開銷盡可能小)，再處理資源請求不明確的虛擬網絡請求，對它們進行資源的平均分配。該算法中間節點的資源消耗更接近實際，但不適合于大規模虛網請求，對于支持鏈路可分流的情況計算復雜度比較高。

2.2不限制地理位置的虛網映射算法

不限制地理位置的虛網映射算法，又可根據是否考慮拓撲特性，細分為同時考慮拓撲信息的虛網映射算法[10-12]和未考慮拓撲信息的虛網絡映射算法[8-9]。

(1)考慮拓撲信息的虛網映射算法

文獻[10]從已有的算法平等地對待底層網絡的節點和鏈路資源，實際上這些物理資源中某些資源相比其他的資源更重要，這些關鍵資源的耗盡會對未來的請求接受率有較大的影響。因此根據物理網絡節點和鏈路的剩余可用容量和在底層網絡中的重要程度分配不同的權重，拓撲感知映射在已有算法的成本函數中引入比例因子，對資源進行區分。同時，新的虛擬網絡到達和已有的虛擬網絡服務終止使得底層網絡可用資源的分布變得零散，底層網絡資源利用率降低，請求接受率下降。解決方案是引入重優化機制，周期性的重優化機制不適用于實際的網絡，文獻中提出當有虛擬網絡請求被拒絕時執行重優化算法，有效地均衡負載。

文獻[11]在節點映射階段引入網絡拓撲屬性，即在考慮CPU和帶寬的同時考慮節點的度(度是節點最基本和最重要的拓撲屬性，可衡量在拓撲結構中節點的相對影響和相對重要性，反映了與網絡剩余部分的連接程度，節點的度等于其與鄰居節點的直接鏈路數)以增強節點與其他節點聯系能力的影響，從而提高虛擬網絡接受率、長期平均收益和底層資源利用率。

文獻[12]從馬爾可夫隨機游動模型出發，利用K-核分解技術將虛擬網絡劃分為核心網絡和邊緣網絡兩大部分，同時優先考慮生存時間最短的虛擬網絡請求(區別于以收入為導向的調度策略)。在映射過程中，首先采用RW-MM-SP算法映射核心網絡，然后采用RW-BFS算法映射邊緣網絡，其中核心網絡中與邊緣網絡直接相連的節點稱為星節點。

(2)未考慮拓撲信息的虛網映射算法

文獻[8]中，在不限制地理位置的條件下，底層物理網絡支持路徑遷移與路徑分裂特性，節點映射按照貪心算法來映射，鏈路映射采用基于商品流鏈路映射，從而提高虛擬網絡請求接受率，但由于節點屬性是節點CPU與鄰接鏈路帶寬之和的乘積，容易導致任意一個值的變化，從而導致鏈路映射失敗。

文獻[9]中，為應對底層資源浪費大的問題，將虛網的資源請求劃分為兩部分：基本子請求和可變子請求，提出了一種新的ORS(Opportunistic Resource Sharing)映射框架，包括宏觀層面的虛網映射和微觀層面的虛網映射。宏觀層面的虛網映射，采用傳統的貪婪算法，為基本子請求分配固定的專用時隙。微觀層面的虛網映射，由于可變子請求以小于1的概率發生，因此共享時隙可節約底層資源，其映射問題即可轉化為如何為可變子請求分配底層時隙的問題。文獻[9]定義沖突閾值以代表底層時隙的量，繼而提出了沖突概率的第一擬合算法(First-Fit by Collision Probability，CFF)和指標和的第一擬合期望算法(First-Fit Expectation of Indicators Sum,EFF)兩種共享時隙的映射算法。CFF將可變子請求映射到率先滿足沖突概率不大于沖突閾值的底層時隙上，直到分配給可變子請求的時隙數滿足要求為止。EFF是對CFF的改進，減少了沖突概率的計算量，比CFF運行得快。

3 虛擬網絡映射算法的改進思路與方向

盡管現有的虛擬網絡映射算法取得了一些進展與突破，但是仍然面臨著以下一些問題：

(1)目前絕大多數映射算法的假設條件都是由單個電信運營商提供底層物理資源，但是在實際應用中會面臨著由多個提供商提供的網絡，如何在多個底層網絡中進行選擇和映射，這將是未來研究的重點與熱點。

(2)虛擬網絡映射過程遇到因某種原因突然出現節點和鏈路失效，從而使得映射失敗，導致虛網映射可靠性降低，例如可以考慮為虛擬網絡分配冗余資源，或者為節點、鏈路建立資源備份池，當該節點或者鏈路失效時，可以及時切換到其他節點和鏈路上，確保網絡可以繼續運行下去。

(3)網絡安全也應該成為未來虛擬網絡映射潛在的研究點，考慮虛擬網絡映射過程中引入身份認證機制，使得虛擬網絡變得更加安全與可靠。

(4)同時虛擬網絡映射過程中會消耗一定的能量，可以考慮將能耗這一因素納入映射算法的衡量指標中，使得未來的映射變得更加綠色和節能。

(5)電信運營商為了利益最大化，優先接受收益大的虛網請求，即收益為導向的調度策略，一些虛擬映射算法中采用以時間為導向的調度策略，率先映射生存周期短的虛擬網絡，為未來的VNR預留更多的剩余資源，提高了虛網的接受率，進一步增加了收益。因此，從虛擬網絡請求排隊機制的優先級出發，尋找更高效的虛擬網絡映射算法。

4 結論

SDN網絡的特性與網絡虛擬化技術相契合，為未來網絡的發展提供基礎，同時也有利于網絡技術的革新和用戶業務的發展。虛擬網絡映射過程中，不僅需要考慮虛擬網絡請求的鏈路帶寬和CPU資源的約束，還要考慮傳輸時延及物理網絡中可用資源大小，這是今后研究的重點和難點。本文從限制地理位置與不限制地理位置兩個方面對多種虛擬網絡映射算法進行了簡要分析，并指明了今后進一步的研究發展方向。

[1] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008.

[2] CHOWDHURY N M M K, BOUTABA R. Network virtualization: state of the art and research challenges[J]. IEEE Communieations Magazine, 2009, 47(7):20-26.

[3] CHOWDHURY M, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5):862-876.

[4] 姜明，王保進，吳春明,等.網絡虛擬化與虛擬網映射算法研究[J].電子學報,2011,39(6):1315-1320.

[5] 溫濤，虞紅芳，李樂民.網絡虛擬化的過去、現在和未來[J].中興通訊技術,2014,20(3):2-7.

[6] SHAMSI J, BROCKMEYER M. QoSMap: QoS aware mapping of virtual networks for resiliency and efficiency[A]. Proceedings of the IEEE GLOBECOM Workshop[C]. Washington, DC, USA, 2007: 1-6.

[7] BETORO J F, HEESELBACH X, FISCHER A, et al. Optimal mapping of virtual networks with hidden hops[J]. Telecommunication Systems, 2013, 52(3): 1-10.

[8] Yu Minlan, 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.

[9] Zhang Sheng, Qian Zhuzhong, Wu Jie, et al. Virtual network embedding with opportunistic resource sharing[C]. IEEE Transactions on Parallel and Distributed Systems, 2014: 816-827.

[10] BUTT N F, CHOWDHURY N M M K, BOUTABA R. Topology awareness and reoptimization mechanism for virtual network embedding[C]. Networking, 2010: 27-39.

[11] Feng Min, Zhang Lei, Zhu Xiaomin, et al. Topology-aware virtual network embedding through the degree[C]. National Doctoral Academic Forum on Information and Communications Technology 2013, IET, 2013: 1-6.

[12] Qing Sude, Liao Jianxin, Wang Jingyu, et al. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. Proceedings of IEEE International Conference on Communications, 2012: 2695-2699.

[13] 桂燕興，沈蘇彬，毛燕琴.基于SDN的虛擬映射技術的研究與實現[J].微型機與應用,2015,34(13):69-76.

2017-05-17)

張鑫(1993-)，通信作者，男，碩士研究生，主要研究方向：軟件定義網絡與網絡虛擬化。E-mail：zhangxin9312@163.com。

賈瑩瑩(1992-)，女，碩士研究生，主要研究方向：下一代網絡、無線傳感器網絡。

王曉璇(1993-)，女，碩士研究生，主要研究方向：下一代網絡、無線傳感器網絡。

Research on virtual network embedding problems based on SDN

Zhang Xin1,2, Jia Yingying1,2, Wang Xiaoxuan1,2

(1. Key Lab of Broadband Wireless Communication and Sensor Network Technology, Nanjing University of Posts and Telecommunications, Ministry of Education, Nanjing 210003, China; 2. Jiangsu Key Lab of Wireless Communication, Nanjing 210003, China)

Traditional IP network architecture is not adaptive to the increasing number of network services and applications ,and then a new type of network architecture is introduced, which is software defined network. It enables data plane and control plane to separate, and has central control,open interfaces,and programmable features. This paper studies the virtual network embedding problem based on the network architecture, that is, how to map virtual network requests with constraints to the underlying physical network provided by traditional telecommunication operators. Firstly, the definition and goal of the virtual network embedding problem are given. Then, a variety of classical mapping algorithms are classified and compared with each other. Finally, the future virtual network embedding algorithms’ suggestions and improvements are offered.

software defined network; virtual network embedding; network virtualization; mapping algorithm

TP393

A

10.19358/j.issn.1674- 7720.2017.22.004

張鑫，賈瑩瑩，王曉璇.基于SDN的虛擬網絡映射問題研究綜述J.微型機與應用，2017,36(22)：11-14.