基于VF2算法的vEPC網絡高效部署策略

楊 路，趙 進

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

5G要求網絡實現超高速，超低時延，超可靠的通信[1]等能力。演進分組核心網(EPC)引入軟件定義網絡(SDN)[2]和網絡功能虛擬化(NFV)[3]進行架構變革，形成vEPC[4]架構。這是一種基于云數據中心的網絡架構。云數據中心具有計算、存儲和網絡資源的聯合編排能力，可實現資源的按需提供，隨取隨用。其中，解決虛擬網絡嵌入(VNE)[4]問題是實現資源按需供應的關鍵。文獻[5,6]將由多個VNF，按一定次序組合而成的線性VNR(虛擬網絡請求)定義為服務功能鏈(service function chain，SFC)。文獻[7]針對vEPC中SFC的部署問題，提出一種基于Viterbi算法的自適應部署方法。該方法并不適用于非線性結構的VNR。文獻[8]結合機器學習，提出一種改進的Q-learning算法，該方法根據物理網絡資源狀態對已部署VNR進行重新部署，以期獲得物理網絡的負載均衡，但這種重配置的機制會浪費更多的資源。文獻[9]提出節點全局資源度的概念，根據備選部署區域的剩余資源數量選擇部署方案。但剩余資源數量并不能真正反應物理網絡的資源狀態。綜上，目前對于SFC部署的研究較多，缺乏針對非線性VNR的部署算法。對于負載均衡問題，許多研究基于物理網絡剩余資源數量進行部署方案確定，但是資源利用率才更能反應網絡負載情況。此外，大多數研究根據用戶請求到達時刻的物理資源狀態進行VNR的部署，未考慮按照這種方案部署VNR后，對物理網絡的影響。本文研究了一種適用于非線性VNR部署的算法，給出了明確的部署過程，并根據網絡拓撲結構與綜合效用值做負載均衡。相對其余算法，能處理多種結構的VNR，有著更高資源利用率，更少的資源碎片。

1 系統模型與性能指標

1.1 系統模型

在vEPC架構中，用戶業務的滿足有著以下過程，如圖1所示，云數據中心接受用戶請求，根據其具體需求，組合相應的VNF組件形成VNR，再根據底層網絡的資源狀態，按照部署算法，將該VNR映射到底層網絡，由底層物理網絡完成業務服務。這種基于云端的部署方式，讓物理資源得到統一調配，底層網絡可承載多樣化業務。業務終止后，物理資源能被釋放并復用，消除了以往定制化、單一化的硬件模式。使得物理資源被更加合理的運用，提升了資源的利用效率，使網絡變得靈活高效。

圖1 vEPC系統模型

1.2 系統模型的表征

虛擬網絡請求：將VNR抽象為加權的無向圖GV=(NV,EV)， 其中NV表示VNF的集合，NV中的VNF稱為虛擬節點。EV表示虛擬鏈路的集合。虛擬節點有計算資源需求，用c(nv) 表示。虛擬鏈路ev=(nv,mv) 有帶寬需求，用b(ev) 表示。

底層網絡：底層網絡也抽象為加權無向圖GS=(NS,ES)，NS和ES分別表示底層網絡的節點集合和鏈路集合。節點具有屬性c(ns)， 表示物理節點的計算資源總量。物理節點有位置約束IFi(vnf)， 表示VNF能否部署在本節點。物理鏈路es=(ns，ms) 具有帶寬總量b(es)。 從底層網絡的實際架構出發，物理節點具有“交換機—服務器”層疊式結構，即交換機設備安裝于服務器機架之上。底層網絡連接結構如下：節點位置是服務器與交換機相連；節點之間是交換機與交換機相連。這樣的架構使得節點在計算資源不足時，仍可作為轉發節點完成VNR的部署。

虛擬網絡請求部署：在VNR和底層網絡之間找到匹配結果的過程稱為VNR部署。此過程中，底層網絡的資源必須滿足VNR的相應需求。部署方案用M={NV→NP,f|NV?GV;NP,f?GS} 表示。其中NP稱為部署節點集合，是底層網絡中用于部署VNF的節點集；f是轉發節點集合，由部署節點ns，ms之間的有序節點組成。轉發節點可做如下理解：相鄰的虛擬節點nv，mv被部署到不相鄰的物理節點ns，ms之上，ns，ms之間通過f節點集連接，則稱虛擬鏈路ev=(nv，mv) 在物理鏈路 (ns,f,ms) 之上部署。如圖2所示。

圖2 VNR部署示例

圖2中，由于物理節點4、7計算資源不足，虛擬節點D無法部署。最終，節點D部署到物理節點3，節點4、7作為轉發節點轉發B、D間業務。這種方式下，物理鏈路(1,7)，(7,4)，(4,3)均需要消耗虛擬鏈路(B,D)等量的帶寬需求，但節點4、7不消耗計算資源。

1.3 性能指標

我們用以下指標來衡量算法對于底層網絡資源的分配效率。

靜態請求接受數量：定義為在靜態資源配置條件下，底層網絡能接受的最大VNR數量。靜態資源配置指的是，VNR部署到底層網絡后，不會離開網絡。該指標可以考察算法對于底層網絡資源的利用效率。對于特定的底層網絡，其資源總量是一定的。高效的部署算法考慮的資源分配方式及負載均衡策略更加合理，可以使得資源有限的底層網絡接受更多的VNR。

請求接受率：定義為部署成功的VNR與VNR總數之比。接受率是表現算法有效性的重要指標，表征算法對動態變化的底層網絡資源狀態的感知能力。表示為

(1)

式中：分母表示VNR總量，DA表示成功部署的VNR數量。

收益成本比：在5G時代，運營商網絡將會實現按需供給，用戶按需付費，所以運營商的收益可用用戶請求的資源數量代表。但有時為了完成用戶請求的部署，需要底層網絡通過轉發節點進行多跳映射部署，產生額外資源消耗。實際消耗的資源量稱為成本。所以收益成本比表示為

(2)

其中，αb，βb，αc，βc分別代表VNR和底層網絡的CPU和帶寬的權重系數。n(ev) 表示虛擬鏈路ev占用的物理鏈路條數。式(2)中，分子表示收益，既VNR的資源需求數量。分母表示成本，既完成VNR部署所消耗的實際資源量。對于一次VNR部署來講，多跳映射部署會消耗額外資源，增加成本。

2 問題描述與算法設計

2.1 問題描述

我們通過轉化圖理論中的子圖同構問題(SIP)來解決上述VNR部署問題：VNR部署問題旨在于底層網絡上找出VNR的可部署位置；SIP指，在一圖中，找出與另一圖具備相同結構的子圖。子圖是指節點和邊分別屬于某一圖的節點和邊的子集的圖。如果在底層網絡中找到了與VNR拓撲一致的子圖，那么我們就通過解決SIP，解決了VNR部署問題。并且在開始子圖搜索之前，我們考慮底層網絡的動態特性：隨著VNR的部署與釋放，底層網絡拓撲結構始終處于變化之中。其中最重要的是底層網絡會形成各個非連通區域，影響VNR的部署。網絡中連通的區域稱為連通子圖。子圖同構問題和連通子圖的具體定義如下：

子圖同構問題：在本文的模型下，VNRGV稱為請求圖，底層網絡GS稱為查詢圖。存在目標圖TS?GS， 且TS與GV具有相同的圖形結構，則稱GV與GS子圖同構。子圖同構的引進為VNR問題提供了直接具體且簡單可行的映射策略。

連通子圖定義：若一張圖中任意兩點間都存在至少一條通路，稱此圖為連通圖。若一張圖中存在滿足連通圖定義的子圖，則稱該子圖為連通子圖。VNR部署初始階段，整個底層網絡可看作一張連通圖，隨著部署的進行，底層網絡因鏈路帶寬不足而形成相互不連通的區域，這種現象稱之為底層網絡的資源碎片化。資源碎片化會影響算法效率，對于兩階段部署算法，在不連通的區域上的VNR部署將會失敗，對于一階段部署算法，資源碎片將會增加算法的搜索代價。

2.2 算法設計

2.2.1 約束條件

(3)

(4)

VNR部署階段，VNR的計算資源、帶寬資源的需求必須小于底層網絡的剩余可用資源量

(5)

(6)

考慮到EPC網絡架構，PGW為核心網與Internet之間的連接點，其數量、部署位置有著一定的要求。因此在vEPC網絡中，本文引入變量IFi(vPGW)， 表示該約束。其值為1表示物理節點i允許部署vPGW，值為0表示節點不允許部署vPGW。

2.2.2 PDLB(post-deployment load balancing)

我們期望通過解決SIP來解決VNR部署問題。VF2算法是解決SIP問題的傳統算法。本文基于VF2算法，根據底層網絡的動態特性，考慮實際中算法需支持多跳映射部署，并考慮了底層網絡的負載均衡，提出PDLB[10]算法。VNR部署流程見表1。

表1 部署流程

CCDP：隨著VNR的不斷部署，由于資源有限，底層網絡逐漸資源碎片化，形成非連通區域。既底層網絡存在拓撲動態特性，如圖3所示。

圖3 底層網絡動態特性

圖3中黑色節點和虛線表示物理節點和鏈路的剩余可用資源已經不足以提供VNR的部署。物理節點剩余可用計算資源不足時，可作為轉發節點來使用，有轉發節點參與的部署稱為多跳映射部署。鏈路剩余可用帶寬資源不足時會產生非連通子圖，在非連通的子圖上無法完成VNR部署，而如果不識別連通子圖，算法又會在非連通子圖間進行不必要的搜索，為優化算法效率，本文運用CCDP事先計算出底層網絡的連通子圖集合，并篩選出可供VNR部署的連通子圖，提高了部署方案搜索過程的搜索效率。CCDP基于廣度優先搜索，從某一節點出發，所有與該節點之間存在路徑的節點屬于同一連通子圖。如算法1所示。

算法1： CCDP

Input：GS

Output： 連通子圖集合GC

(1)GC=?

(2)for節點ninGSdo

(3)if節點nnotinGCthen

(4) G=find_connected_graph(GS, node)

(5) Add G toGC

(6)endif

(7)endfor

部署方案搜索：根據文獻[11]，用節點數量最多的連通子圖來部署VNR，可以在初期獲得比較高的請求接受率。但隨之，底層網絡非連通區域的數量將會增加，資源碎片化程度升高，整個網絡的長期收益受到影響。所以本文算法優先選擇節點數量大于等于VNR節點數量的連通子圖來進行部署方案的搜索。

搜索過程如算法2。變量Mtemp，Ttemp分別保存每一次搜索得到的部署方案和對應的目標圖。算法從節點數量大于等于VNR節點數量的第一個連通子圖GkC中搜索可行部署方案，當在該連通子圖中未獲取部署方案時，才在下一連通子圖中進行搜索。函數Candidate_node_pairs(GV,GkC) 的作用是生成匹配節點對，初始匹配節點對的生成規則如下：①若VNR中存在vPGW，判斷GkC中是否存在可供vPGW部署的節點，存在，生成節點對，不存在，搜索下一連通子圖；②VNR中不存在vPGW，優先將VNR中計算資源需求最大的節點生成匹配節點對。函數Constraint_condition(nav,nis) 對節點對 (nav,nis) 進行資源約束檢查，包括匹配節點間的計算資源約束，及匹配節點與已完成匹配節點間的鏈路資源約束。函數Structural_constraints(nav,nis) 分析當前匹配節點對的節點度數信息，及節點各自一步鄰居的拓撲信息，若節點度數信息不匹配或一步鄰居拓撲信息不匹配，說明無法完成最終的搜索，算法會中止當前匹配，重新選擇匹配節點對。這一步稱之為剪枝，剪枝方法“減掉”了錯誤的搜索方向，提高了算法效率。當VNR的所有節點都匹配完成時，獲得一次可行的部署方案。

算法2： 部署方案搜索

Input:GV，GC

Output: 部署方案M

(1)Mtemp=?,Ttemp=?

(2) 按節點數排序GC：Sorted(GC)

(3)forGkCinGCdo

(4) P=Candidate_node_pairs(GV,GkC)

(5)for(nav，nis)inPdo

(6)ifConstraint_condition(nav，nis)then

(7)ifStructural_constraints(nav，nis)then

(8) Add (nav，nis) toMk, updateTkS

(9)endif

(10)endif

(11)endfor

(12)ifSize(NkP)==Size(NkV)then

(13) AddMktoMtemp

(14) AddTkStoTtemp

(15)endif

(16)forallTkSinTtempdo

(17) 計算使得γ最大的TkSthen

(18)TS=TkS

(19)M=Mk

(20)endfor

(21)完成部署， 更新底層資源狀態

計算出連通子圖GkC中全部可行方案后，根據資源綜合效用值γ選擇最優的部署方案。γ定義如下

(7)

式(7)表示：按照目標圖TkS所對應的部署方案M進行部署后，節點和鏈路的資源利用率加權和。每一種部署方案都會對底層網絡的資源狀態造成影響，本文通過比較得到的全部可行方案對底層網絡的資源利用率影響，選擇部署后底層網絡資源利用率最大的一種方案，這樣保證了每一次部署后的資源狀態是最佳的。最后，按照最優部署方案M進行VNR的部署，并更新底層物理網絡的資源狀態視圖。

3 仿真結果及分析

為了評估本文算法的可行性、高效性，本文以靜態請求接受數量、請求接受率、收益成本比以及連通子圖的規模為評價指標，并與表2中列出的算法對比。本文所提PDLB的負載均衡策略基于資源利用率。為做對比，本文使其支持基于剩余資源數量的負載均衡策略，命名為 PDLB_R。同樣的，調整VF2-H[9]算法使其支持基于資源利用率負載均衡。

表2 比對算法

3.1 仿真環境

仿真所使用的硬件環境為Intel?Core i7-6700 CPU, 8 GB 內存。基于Python實現各算法，通過Matplotlib庫進行數據處理、分析。底層網絡和VNR使用Networkx庫隨機產生。有{5，7，9}3種不同節點規模的VNR。底層網絡中，有占總節點數的10%的節點可用于部署vPGW。VNR所需資源大小以及底層的資源容量大小服從均勻分布，VNR動態到達，服從λ∈(100,300) 的泊松分布，VNR在底層網絡上的生存周期滿足μ=1/50的指數分布。

3.2 仿真分析

圖4、圖5分別是在靜態資源配置下，底層網絡節點數為50和100時各算法的平均最大VNR接受數量。仿真結果表明，在相同的底層網絡結構下PDLB能夠接收更多的用戶請求，可以更高效的利用底層網絡的資源。基于資源利用率的PDLB與VF2-H_U分別比基于剩余資源數量的PDLB_R和VF2-H算法獲得了更多的VNR接受數量。兩圖中，各算法仿真結果橫線以上部分表示經過多跳映射完成部署的VNR數量。分析結果可以得到，對于PDLB，PDLB_R算法，底層網絡為50節點時，經過多跳部署的VNR數量占比，比底層網絡節點為100時高。這是因為物理節點數量較少時，網絡拓撲較簡單，算法傾向于選擇多跳映射完成部署。本文算法能更好的識別網絡拓撲結構，在物理節點較多時，資源利用的更為合理高效。而對比算法在兩種底層網絡中均有著較高的多跳部署占比。

圖4 物理節點為50時的平均VNR接受數量

圖5 物理節點為100時的平均VNR接受數量

圖6 請求接受率變化

圖6顯示了物理節點數為100時，各算法的請求接受率曲線，可以看到本文算法得到了最高的接受率，這是因為本文設計的CCDP，以及基于“部署后”資源利用率的負載均衡策略，都使得VNR的部署位置更加合理，使底層網絡資源碎片更少，從而提高了整體的資源利用效率。可以看到，基于資源利用率的算法的請求接受率要高于基于剩余資源數量的算法，這是由于資源利用率更能反映底層網絡的負載狀態，而基于剩余資源數量的策略將會導致底層網絡局部擁塞，使得VNR接受率降低。還可以看到，PS算法有著最陡峭的下降趨勢，最先達到了最低的接受率，這是因為PS算法是一種兩階段部署算法，且會進行鏈路分割部署，這使得它消耗了更多的鏈路資源，使底層網絡資源碎片化嚴重，資源碎片度高必然使得接受率降低。KSP算法雖然是兩階段算法，但因其基于K最短路徑算法支持多跳部署，而與傳統的一階段算法VF2保持了較為相近的水平。

圖7是不同節點規模的底層網絡中，各算法的收益成本比。在底層節點數較少時，各算法都需通過多跳來部署VNR，增加了帶寬資源的消耗，導致收益成本比較低。隨著物理節點的增加，除了基于資源利用率的算法PDLB和VF2-H_U，其余算法的收益成本比呈現先增后降的趨勢。這說明基于資源利用率的算法使得底層網絡資源更加均衡。而基于剩余資源量的算法，會造成局部擁塞，使得經過多跳映射的VNR數量增多，導致收益成本比下降。PDLB首先考慮與VNR拓撲結構一致的目標圖，其次才是多跳映射部署，所以取得了最好的收益成本比。兩階段算法KSP，PS會產生更多的鏈路資源消耗，收益成本比最低。

圖7 不同底層節點規模下的收益成本比

圖8是節點數為100時，底層網絡中連通子圖規模變化曲線。可以看到本文算法在整個部署過程中都維持了較低的連通子圖規模，說明本文算法有效的降低了網絡的資源碎片度。PS算法在底層資源不足時，會選擇分割鏈路進行部署，形成較多的資源碎片，對底層網絡造成較大影響，所以在圖中有一個突變。

圖8 節點數100時，連通子圖規模變化

圖9 節點數100的BA網絡接受率曲線

本文還在節點數為100的BA網絡下，進行了各算法的請求接受率仿真對比。BA網絡是指離散度較高的一類網絡。如圖9所示，對比圖6，各算法接受率均下降了一些，但本文算法依舊保持了較高的接受率，這是因為本文算法針對連通子圖內進行部署，對底層網絡的離散度不敏感。KSP算法的性能有明顯的降低，這是因為KSP是兩階段的算法，在進行鏈路映射時，在非連通的子圖間的部署將會失敗。該結果表明本文算法設計的CCDP是正確且有效的。

4 結束語

本文針對下一代移動通信vEPC網絡中虛擬網絡部署過程中用戶請求接受率低、底層網絡資源碎片化嚴重等問題，提出了一種基于VF2算法的改進算法，并與其它算法進行了仿真對比。本文算法搜索得到目標區域中所有的可行部署方案，再通過對比這些方案最終導致的底層網絡資源利用率大小，選擇最優的部署方案。讓每次部署對底層網絡來講是最優的。同時，考慮到底層網絡的拓撲動態特性，本文引入CCDP，用于識別底層網絡中的連通區域，使本文算法精準地在連通區域中進行搜索，加快了VNR部署速度，提高了接受率。結果表明，本文算法能接受更多的用戶請求、有效的提高了用戶請求接受率、提高了底層網絡的資源利用率、降低了底層網絡的資源碎片度。本文算法初步展現了在物理節點數較多的情況下的良好性能，未來我們將會在大規模網絡下，研究并驗證其各方面性能。