一種支持節點分割的vEPC虛擬網絡功能部署模型

湯紅波 袁 泉 盧干強 王曉雷 趙 宇

?

一種支持節點分割的vEPC虛擬網絡功能部署模型

湯紅波*袁 泉 盧干強 王曉雷 趙 宇

(國家數字交換系統工程技術研究中心 鄭州 450002) (移動互聯網安全技術國家工程實驗室 北京 100876)

軟件定義網絡(SDN)和網絡功能虛擬化(NFV)促進了網絡的創新，NFV實現了虛擬網絡功能(VNF)的邏輯集中部署。針對vEPC(virtualized Evolved Packed Core)網絡中VNF的池組化部署問題，該文提出一種支持節點分割的VNF部署模型，該模型基于虛擬請求業務流量的感知，利用節點分割算法動態調整VNF與底層網絡資源切片的映射關系，實現VNF的跨域組池。與傳統的多功能鏈聯合映射算法相比，該方法能夠實現節點資源細粒度化管理和統籌調度，優化網絡視圖，減少資源碎片。在SNDlib提供的網絡拓撲實例下仿真證明，該模型可以降低虛擬網絡的資源開銷，并提高虛擬網絡的請求接收率。

網絡功能虛擬化；虛擬網絡功能部署；5G；EPC(Evolved Packed Core)；節點分割

1 引言

當前，有限的網絡資源和僵化的網絡結構限制了網絡的發展。為了滿足未來網絡的需求，提高網絡的管理能力和靈活性，IMT-2020(5G)推進組提出應用軟件定義網絡(Software-Defined Network, SDN)和網絡功能虛擬化(Network Function Virtualization, NFV)技術實現演進分組核心(Evolved Packet Core, EPC)網網元功能基于數據中心網絡的集中化部署、編排與管理[1]。

目前，多數文獻[2]都是研究互聯網服務功能鏈場景下的虛擬網絡功能(Virtualized Network Function, VNF)部署問題。近些年，隨著5G的興起，國內外學者對vEPC網絡中VNF部署問題進行了相關研究。由于傳統的數據中心網絡難以滿足5G移動通信高帶寬、低時延和集中管控的要求，文獻[3]提出了一種分布式云平臺上的虛擬化EPC (virtualized EPC, vEPC)網絡組網方案。該平臺通過分布式云數據中心節點提供vEPC網絡中VNF實例化所需的底層資源。云節點之間基于SDN技術實現動態組網，所有的云節點由一個統一的管理和編排模塊集中管控。文獻[4]首次提出了vEPC網絡中VNF的部署問題，并提出了兩種部署方式：(1)僅在數據中心內部虛擬化VNF的控制面，數據面通過增強的SDN轉發設備實現。(2)將VNF的控制面和數據面全部虛擬化，利用現有骨干網設備完成轉發。該文統籌考慮了網絡中處理時延和傳輸時延之間的關系，優化了數據中心網絡的總體時延，但該模型必須先對物理網絡進行靜態子網劃分，在每一個子網分別部署相應的EPC服務鏈，模型中各個子網互相獨立，網絡視圖復雜且不利于全網資源統一編排管理。文獻[5]提出了多服務鏈聯合映射模型，該模型對域內的eNodeB進行動態聚簇，每個eNodeB簇連接一條完整的vEPC服務鏈，假設各條服務鏈之間相互獨立，將一條服務鏈上的EPC網元功能盡可能集中部署到相鄰的數據中心內部，采用定時更新底層網絡狀態的方式，完成多條獨立EPC服務鏈的聯合映射。相比于靜態子網劃分策略，聯合映射思想的優點是對子網進行動態劃分，能夠相對靈活地調度全網資源而缺點是使網絡的全局視圖更加復雜，提高了網絡功能管理和編排的難度。此外，文獻[4]和文獻[5]都是以“網元”作為資源分配的粒度，當云節點中剩余的資源不足以實例化一個完整的網元功能時，節點的剩余資源將保持不可達狀態，形成資源碎片，降低了物理網絡資源的利用率。

現有研究多數假設vEPC保留了EPC現行架構的主要網元功能，包括移動管理實體(Mobility Management Entity, MME)、服務網關(Serving GateWay, SGW)、PDN網關(PDN GateWay, PGW)和歸屬簽約用戶服務器(Home Subscriber Server, HSS)。文獻[4]和文獻[5]借鑒了互聯網服務功能鏈的鏈式結構部署vEPC服務鏈，但是在LTE網絡中，MME和SGW都采用池組的形式組網。池組技術是指在一定區域內，多套相同的網元設備組成池組，通過通用接口實現資源共享和業務分擔，是解決核心網切換、負載均衡和容災備份的重要方案[6]。為了支持vEPC網絡中VNF的組池，本文提出一種基于節點分割的vEPC虛擬網絡功能部署模型。該模型將虛擬網絡請求的實時業務流量作為節點分割的決策變量，根據物理網絡剩余資源的全局視圖，動態調整虛擬節點分割的子節點數量，以及各個子節點與物理節點的映射關系。相比于傳統多條服務鏈聯合映射部署模型，節點分割模型不再對同一vEPC管理區域內的物理網絡進行子網劃分，優化了虛擬網絡視圖，完成了EPC虛擬網絡功能的組池，進一步細化資源分配的粒度，提高了資源利用率。

2 數學模型

本文采用虛擬網絡映射方法對vEPC網絡中的VNF部署問題建模，將底層網絡和虛擬網絡請求分別表示為一個無向帶權圖，根據優化目標設計相應的映射算法尋找最優部署結果。

2.1 底層網絡

2.2 虛擬網絡請求

支持池組技術的vEPC虛擬網絡視圖如圖1所示，接入網中將同一跟蹤區域內的eNodeB聚合在一起，對接入云進行分簇，并假設同一個簇內的eNodeB在回傳網絡中都連接到了同一個匯聚節點(Traffic Aggregation Point, TAP)。虛擬網絡請求可表示為一個無向帶權圖。其中，表示VNF的集合，。表示虛擬鏈路的集合，每一條虛擬鏈路表示為。是表示虛擬網絡功能屬性的集合，與物理網絡相同，。是表示虛擬鏈路屬性的集合，即虛擬鏈路的帶寬。虛擬網絡映射可以定義為：虛擬節點映射和虛擬鏈路映射。

2.3 構建一個底層網絡的增廣圖

區別于傳統數據中心網絡中各節點同質化，各個云節點提供的服務類型具有差異性，因此在進行功能部署之前必須預先判斷每一個云節點能夠承載的EPC網絡功能類型。本文參考了ViNEYard[7]算法，通過構建基于底層網絡和虛擬網絡的增廣網絡，為虛擬網絡功能選擇候選底層節點。

圖1 移動核心網功能鏈

圖2 增廣網絡示意圖

3 節點分割算法

文獻[8-10]針對互聯網功能鏈部署提出了多種節點分割算法，文獻[8]研究了物理節點可接受同一虛擬網絡的多個節點映射問題，提高了請求接受率，但是該算法是一個兩階段的映射算法，無法同時獲得節點和鏈路映射的最優解。文獻[9]提出了節點和鏈路協同映射的一階段映射算法，但是該算法僅支持物理節點承載不在同一個虛擬網絡的多個節點映射。文獻[10]提出了虛擬機功能鏈部署模型中，根據底層網絡資源分配情況拆分虛擬網絡節點的方法。參考以上文獻，本文提出了EPC網絡的節點分割算法，該算法基于5G非棧式協議，提出了根據底層網絡流量動態拆分EPC虛擬網絡功能的分割方案。節點分割EPC模型用到的符號和含義如表1所示。

表1 節點分割EPC模型用到的符號和含義

3.1 決策變量設置和底層網絡資源測量

(1)決策變量設置： 傳統網絡協議棧中傳輸流量不可分割，節點分割算法一般選擇虛擬節點和底層節點的映射關系變量作為決策變量，此時，虛擬網絡功能到底層網絡節點的映射關系是一個模糊集合，應用混合整數規劃的方法不能獲得全局最優解。目前，多采用兩階段映射與啟發式算法相結合的方式尋找節點分割算法最優解，但是兩階段映射策略無法同時獲得節點和鏈路的最優解而啟發式會陷入局部最優[11]。5G移動通信提出了“非棧式”協議架構[12]，對協議棧進行虛擬化，使5G網絡具備智能處理數據流的能力?；?G非棧式協議的設想以及流分割技術的研究成果，本文提出在映射過程中，將底層網絡的流量作為決策變量，利用混合整數規劃設計一階段的節點分割算法。整數規劃決策變量和映射關系變量的符號和含義如表2所示。

表2 整數規劃決策變量和映射關系變量

(2)底層網絡資源測量： 本文提出的節點分割算法是一種動態映射算法，在映射過程中根據底層網絡流量不斷調整映射關系矩陣。為了降低計算時延，基于已有研究，我們利用了以下兩個結論來降低底層網絡測量的計算復雜度。

結論1 根據文獻[13]，假設在映射過程中一個虛擬網絡功能()分割成個子節點，其與業務量相關的節點屬性資源需求按照承擔的業務量映射到個子節點上，如式(1)所示。其中，是子節點序號，表示部署該虛擬網絡功能所必須消耗的基本屬性資源，表示第個節點所承擔的該虛擬網絡功能的業務量，表示第個節點承擔的業務量而消耗的屬性資源。同樣，虛擬網絡功能的總帶寬資源請求等于各個子節點上的數據流量之和，即。

結論2 文獻[14]中軟件路由器的測量結果表明，處理單位分組所消耗的平均計算和存儲資源近似為常數。因此，根據式(1)節點計算、存儲和帶寬資源表達式可以分別近似為式(2)~式(4)，其中和為常數。

(2)

(4)

在上述簡化的基礎上，我們將在單位時間映射結束后更新底層網絡的剩余資源。如式(5)，式(6)所示，表示在單位時間里，網絡中被占用的資源與被釋放的資源之差。

(6)

3.2 優化目標和約束條件

優化目標：

式(7)中，第1項表示節點間鏈路流量占用的帶寬資源，第2項表示虛擬網絡請求占用底層網絡節點的計算資源，其中，表示在底層節點上部署某個虛擬網絡功能所需要的基本資源，則表示在映射某個的過程中，由節點處理的業務量所產生的資源需求。第3項表示虛擬網絡請求占用底層網絡節點的存儲資源，第4項表示承載虛擬網絡功能的底層節點轉發業務流所消耗的網絡資源。是表示權重的常數，滿足條件。對于特定網絡環境，可以相應地調整權重參數，例如要著重考慮計算資源的分配時，應該適當增大的權重。

約束條件：

容量約束：

(9)

(10)

流相關約束：

(12)

(14)

二進制變量約束：

(16)

變量定義域約束：

(18)

(19)

式(8)-式(19)詳細說明如下：

式(8)-式(11)表示虛擬網絡請求的資源數量與底層網絡提供的資源數量之間的約束關系。其中，式(8)是對底層網絡鏈路帶寬的約束條件，當虛擬鏈路映射到底層鏈路時，所有映射經過同一條底層網絡路徑的流量總和不能大于該路徑的可用帶寬值，在這里我們假設物理鏈路是全雙工的。式(9)，式(10)是對底層網絡節點計算和存儲資源的限制條件，當虛擬節點映射到底層時，底層網絡節點的資源值必須不小于虛擬網絡請求占用的資源。由于式(9)，式(10)是非線性約束且是一個二值化變量，所以我們把式(9)，式(10)簡化為式(20)，式(21)的形式。式(11)是對底層網絡節點網絡資源的約束條件，對于任意一個底層網絡節點，流入和流出該節點的流量總和應該小于該節點剩余的網絡資源。

(21)

式(12)-式(14)描述的是流量守恒約束。式(12)表示除了在源節點和目的節點的其他節點(在網絡中僅作為轉發節點存在)上流入和流出的流量是相等的。式(13)，式(14)表示流出(流入)源節點(目的節點)的流量等于相應的虛擬鏈路的帶寬請求。

式(15)表示底層網絡是一個無向圖，即節點間進行對等通信。式(16)表示候選節點集合約束，考慮到不同的云節點之間存在差異性，對每一個節點所能承載的虛擬網絡功能進行了約束。式(17)，式(18)表示決策變量定義域的取值范圍，式(19)表示映射關系變量是一個二值變量。

3.3 算法描述

本文提出的節點分割算法命名為EPC-NS算法(表3)，算法分成3個階段：第1階段是拓撲準備階段，根據輸入算法的底層網絡無向圖和虛擬網絡請求無向圖生成底層網絡增廣圖；第2階段是資源判斷階段，為了降低混合整數規劃的計算發雜度，避免不必要的映射，在運行整數規劃之前先對網絡中的候選節點集合的剩余節點資源進行判斷；第3階段是算法執行階段，對增廣圖運行混合整數規劃算法，獲取功能部署結果。

(1)拓撲準備：(1)~(4)算法第1行表示EPC-NS算法以在線的虛擬網絡請求作為輸入，并把嵌入底層網絡圖生成元節點集合。第2，第3行根據SNDlib中的節點參數初始化變量，選擇每個元節點的候選集合。第4行將元節點和候選節點通過元鏈路鏈接，生成增廣網絡圖。

(3)算法執行：(9)~(14)對增廣網絡圖運行混合整數規劃算法。如果成功完成映射則更新底層網絡資源并獲取映射結果，如不成功，則直接拒絕請求。

表3 EPC-NS算法

4 模型仿真與性能分析

4.1 參數設置

EPC-NS算法仿真所使用的底層網絡拓撲結構取自SNDlib中的Polska12節點測試例[15]，如圖3(a)所示。圖中節點位置部署了運營商的云數據中心，假設所有節點都可以承載除了PGW之外的任意核心網功能，PGW作為移動核心網和互聯網之間的錨點，位置通常是固定的。在Polska12節點測試例中，設定只有Rzeszow和Bydgoszcz節點可以承載PGW。在底層網絡中，節點網絡資源的數量和鏈路帶寬由SNDlib給出，底層節點的計算和存儲資源根據節點網絡資源按比例隨機生成。在虛擬網絡請求中，用戶面的流量是服從泊松分布的隨機過程，控制面中節點所需的計算、存儲和網絡資源請求與用戶面業務流量呈預定的比例，根據SNDlib給出的測試數據，下文將采用流量因數(Traffic Demand Scaling Factor, TDSF)表示流量的變化情況，Polska12節點測試例中TDSF的理論取值范圍是。為了便于比較且不失一般性，我們假設所有節點上單位計算、存儲和網絡資源的開銷是相等的。為了使部署節點所需的基本開銷與該節點上由業務量產生的開銷能夠保持在同一個數量級，設定目標函數中。此外，需要根據網絡拓撲中的資源分布情況通過實驗確定資源權重參數,和。本次仿真實驗的平臺是CPU型號為Intel i7 4790，內存為4 GB的個人電腦。混合整數規劃的求解方案選擇了CPLEX version 12.4，在MATLAB環境下使用YALMIP接口編寫了仿真程序。

4.2 性能評估

圖3 對部署結果的影響

圖4 EPC-NS算法在TDSF=20時的部署結果

圖5 Andreas算法在TDSF=20時的部署結果

圖8顯示了兩種算法在不同流量因子條件下的虛擬網絡映射開銷。映射開銷由式(7)所示的目標函數定義，采用虛擬網絡請求在映射過程中消耗的節點計算、存儲、網絡資源以及鏈路帶寬資源的加權和表示。文獻[5]算法以“網元”為顆粒度進行資源分配，當節點的剩余資源不足以承載任何EPC“網元”時，剩余資源將成為資源碎片，在底層網絡視圖更新前保持不可達狀態。EPC-NS算法在混合整數規劃尋優過程中選擇底層鏈路的流量值作為決策變量，因此底層網絡流量必須是最小分組的整數倍。根據文獻[14]，底層節點處理單位分組所消耗的平均計算和存儲資源近似為常數。綜上，EPC-NS算法將資源分配的顆粒度由“網元級”降低為處理單位數據流占用的資源片，實現了資源的細粒度分配。在相同的虛擬網絡請求下，EPC-NS部署的節點數量更少，減少了網絡中非業務因素占用的基本資源開銷。當網絡流量因子時，因網絡中資源碎片過多文獻[5]算法無法生成有效解空間，虛擬網絡請求被拒絕。

5 結束語

本文從vEPC中VNF的池組化部署問題入手，兼顧5G移動通信更高的資源需求，提出了一種支持節點分割的VNF部署模型。該模型借助EPC-NS算法將資源分配的粒度從傳統模型的“網元級”降低到處理單位流量所占用的網絡切片，提高了網絡的靈活性和硬件資源利用率。仿真結果和性能評估驗證了其有效性。后續將針對vEPC池組模型的可靠性問題進行研究，以滿足5G移動業務的高可靠性要求。

圖6 EPC-NS算法在TDSF=80時的部署結果

圖7 文獻[5]算法在TDSF=80時的部署結果

圖8 網絡開銷對比圖

圖9 請求接受率對比圖

[1] IMT-2020(5G). 5G concept whitepaper[OL]. http://www. imt-2020.cn/zh/documents/download/23. 2015.

[2] FISCHER A, BOTERO J F, TILL BECK M,Virtual network embedding: a survey[J].&, 2013, 15(4): 1888-1906. doi: 10.1109/ SURV.2013.013013.00155.

[3] SAMA M R, CONTRERAS L M, KAIPPALLIMALIL J,Software-defined control of the virtualized mobile packet core[J]., 2015, 53(2): 107-115. doi:10.1109/MCOM.2015.7045398.

[4] BASTA A, KELLERER W, HOFFMANN M,Applying NFV and SDN to LTE mobile core gateways, the functions placement problem[C]. ACM Workshop on All Things Cellular: Operations, Applications, & Challenges, Chicago, USA, 2014: 33-38. doi:10.1145/2627585.2627592.

[5] BAUMGARTNER A, REDDY V S, and BAUSCHERT T. Mobile core network virtualization: a model for combined virtual core network function placement and topology optimization[C]. IEEE Conference on Network Softwarization, London, United Kingdom, 2015: 1-9. doi:10.1109/NETSOFT.2015.7116162.

[6] TALEB T, CORICI M, PARADA C,EASE: EPC as a service to ease mobile core network deployment over cloud[J]., 2015, 29(2): 78-88. doi:10.1109/MNET. 2015.7064907.

[7] CHOWDHURY M, RAHMAN M R, and BOUTABA R. Vineyard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219. doi: 10.1109/TNET.2011.2159308.

[8] 李文, 吳春明, 陳健, 等. 物理節點可重復映射的虛擬網映射算法[J]. 電子與信息學報, 2011, 33(4): 908-914. doi: 10.3724/ SP.J.1146.2010.00735.

LI Wen, WU Chunming, CHEN Jian,Virtual network mapping algorithm with repeatable mapping over substrate nodes[J].&, 2011, 33(4): 908-914. doi: 10.3724/SP.J.1146.2010.00735.

[9] JARRAY A and KARMOUCH A. Decomposition approaches for virtual network embedding with one-shot node and link mapping[J]./, 2015, 23(3): 1012-1025. doi: 10.1109/TNET. 2014.2312928.

[10] LIU L, XU J, YU H,A novel performance preserving VM splitting and assignment scheme[C]. IEEE International Conference on Communications, Sydney, Australia, 2014: 4215-4220. doi: 10.1109/ICC.2014.6883982.

[11] ZHOU Y, LI Y, JIN D,A virtual network embedding scheme with two-stage node mapping based on physical resource migration[C]. IEEE International Conference on Communication Systems, Amsterdam, Netherlands, 2010: 761-766. doi: 10.1109/ICCS.2010.5686504.

[12] CHIH-LIN I, HAN S, XU Z,5G: rethink mobile communications for 2020+[J]., 2016, 374(2062): 20140432. doi: 10.1098/ rsta.2014.0432.

[13] 蔡志平, 劉強, 呂品, 等. 虛擬網絡映射模型及其優化算法[J]. 軟件學報, 2012, 23(4): 864-877. doi: 10.3724/SP.J.1001.2012. 04063.

CAI Zhiping, LIU Qiang, Lü Pin,Virtual network mapping and optimization algorithm[J].2012, 23(4): 864-877. doi: 10.3724/SP.J.1001.2012.04063.

[14] DOBRESCU M, EGI N, ARGYRAKI K,RouteBricks: exploiting parallelism to scale software routers[C]. ACM SIGOPS Symposium on Operating systems principles, Big Sky, USA, 2009: 15-28. doi: 10.1145/1629575.1629578.

[15] Orlowski S, Wess?ly R, Pióro M,SNDlib 1.0-survivable network design library[OL]. http://sndlib. zib.de/home.action. 2015.

A Model for Virtualized Network Function Deployment Based on Node-splitting in vEPC

TANG Hongbo YUAN Quan LU Ganqiang WANG Xiaolei ZHAO Yu

(450002,) (,100876,)

Software Defined Networking (SDN) and Network Function Virtualization (NFV) promote network innovation. NFV realizes logic centralized deployment of Virtualized Network Function (VNF). This paper proposes a kind of node-splitting VNF deployment model for problem of pooling deployment of VNF in virtualized Evolved Packet Core (vEPC) network. Based on the acknowledgement of virtual request traffic-aware, the model uses node-splitting algorithm to realize the dynamic adjustment of the mapping relation between VNF and physical network slices and organize the same VNFs across different domains as one pool. Compared with the traditional joint mapping algorithm of multi-function chain, the method can realize fine-grained management and overall scheduling of node resources, optimize network view, and reduce resource fragments. It is proven by network topology instance provided by SNDlib that the model can reduce resource overhead of virtual network and improve the ratio of acceptance of virtual network requests.

Network Function Virtualization (NFV); Virtualized network function placement; 5G;Evolved Packet Core(EPC); Node-splitting

TN915.81

A

1009-5896(2017)03-0546-08

10.11999/JEIT160507

2016-05-17；改回日期：2016-09-06；

2016-11-17

湯紅波 thb@mail.ndsc.com.cn

國家863計劃項目(2014AA01A701)，國家自然科學基金(61521003)，科技部支撐計劃(2014BAH30B01)

The National 863 Program of China (2014AA01A701), The National Natural Science Foundation of China (61521003), The Ministry of Science and Technology Support Plan (2014BAH30B01)

湯紅波： 男，1968年生，教授，研究方向為移動通信網絡、新型網絡體系結構.

袁 泉： 男，1991年生，碩士生，研究方向為移動通信網絡、網絡功能虛擬化.

盧干強： 男，1990年生，碩士生，研究方向為移動通信網絡、網絡功能虛擬化.