基于VF2算法的vEPC網(wǎng)絡(luò)高效部署策略

楊 路，趙 進(jìn)

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

0 引 言

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

1 系統(tǒng)模型與性能指標(biāo)

1.1 系統(tǒng)模型

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

圖1 vEPC系統(tǒng)模型

1.2 系統(tǒng)模型的表征

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

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

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

圖2 VNR部署示例

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

1.3 性能指標(biāo)

我們用以下指標(biāo)來衡量算法對于底層網(wǎng)絡(luò)資源的分配效率。

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

請求接受率：定義為部署成功的VNR與VNR總數(shù)之比。接受率是表現(xiàn)算法有效性的重要指標(biāo)，表征算法對動態(tài)變化的底層網(wǎng)絡(luò)資源狀態(tài)的感知能力。表示為

(1)

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

收益成本比：在5G時代，運營商網(wǎng)絡(luò)將會實現(xiàn)按需供給，用戶按需付費，所以運營商的收益可用用戶請求的資源數(shù)量代表。但有時為了完成用戶請求的部署，需要底層網(wǎng)絡(luò)通過轉(zhuǎn)發(fā)節(jié)點進(jìn)行多跳映射部署，產(chǎn)生額外資源消耗。實際消耗的資源量稱為成本。所以收益成本比表示為

(2)

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

2 問題描述與算法設(shè)計

2.1 問題描述

我們通過轉(zhuǎn)化圖理論中的子圖同構(gòu)問題(SIP)來解決上述VNR部署問題：VNR部署問題旨在于底層網(wǎng)絡(luò)上找出VNR的可部署位置；SIP指，在一圖中，找出與另一圖具備相同結(jié)構(gòu)的子圖。子圖是指節(jié)點和邊分別屬于某一圖的節(jié)點和邊的子集的圖。如果在底層網(wǎng)絡(luò)中找到了與VNR拓?fù)湟恢碌淖訄D，那么我們就通過解決SIP，解決了VNR部署問題。并且在開始子圖搜索之前，我們考慮底層網(wǎng)絡(luò)的動態(tài)特性：隨著VNR的部署與釋放，底層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)始終處于變化之中。其中最重要的是底層網(wǎng)絡(luò)會形成各個非連通區(qū)域，影響VNR的部署。網(wǎng)絡(luò)中連通的區(qū)域稱為連通子圖。子圖同構(gòu)問題和連通子圖的具體定義如下：

子圖同構(gòu)問題：在本文的模型下，VNRGV稱為請求圖，底層網(wǎng)絡(luò)GS稱為查詢圖。存在目標(biāo)圖TS?GS， 且TS與GV具有相同的圖形結(jié)構(gòu)，則稱GV與GS子圖同構(gòu)。子圖同構(gòu)的引進(jìn)為VNR問題提供了直接具體且簡單可行的映射策略。

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

2.2 算法設(shè)計

2.2.1 約束條件

(3)

(4)

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

(5)

(6)

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

2.2.2 PDLB(post-deployment load balancing)

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

表1 部署流程

CCDP：隨著VNR的不斷部署，由于資源有限，底層網(wǎng)絡(luò)逐漸資源碎片化，形成非連通區(qū)域。既底層網(wǎng)絡(luò)存在拓?fù)鋭討B(tài)特性，如圖3所示。

圖3 底層網(wǎng)絡(luò)動態(tài)特性

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

算法1： CCDP

Input：GS

Output： 連通子圖集合GC

(1)GC=?

(2)for節(jié)點ninGSdo

(3)if節(jié)點nnotinGCthen

(4) G=find_connected_graph(GS, node)

(5) Add G toGC

(6)endif

(7)endfor

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

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

算法2： 部署方案搜索

Input:GV，GC

Output: 部署方案M

(1)Mtemp=?,Ttemp=?

(2) 按節(jié)點數(shù)排序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)完成部署， 更新底層資源狀態(tài)

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

(7)

式(7)表示：按照目標(biāo)圖TkS所對應(yīng)的部署方案M進(jìn)行部署后，節(jié)點和鏈路的資源利用率加權(quán)和。每一種部署方案都會對底層網(wǎng)絡(luò)的資源狀態(tài)造成影響，本文通過比較得到的全部可行方案對底層網(wǎng)絡(luò)的資源利用率影響，選擇部署后底層網(wǎng)絡(luò)資源利用率最大的一種方案，這樣保證了每一次部署后的資源狀態(tài)是最佳的。最后，按照最優(yōu)部署方案M進(jìn)行VNR的部署，并更新底層物理網(wǎng)絡(luò)的資源狀態(tài)視圖。

3 仿真結(jié)果及分析

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

表2 比對算法

3.1 仿真環(huán)境

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

3.2 仿真分析

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

圖4 物理節(jié)點為50時的平均VNR接受數(shù)量

圖5 物理節(jié)點為100時的平均VNR接受數(shù)量

圖6 請求接受率變化

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

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

圖7 不同底層節(jié)點規(guī)模下的收益成本比

圖8是節(jié)點數(shù)為100時，底層網(wǎng)絡(luò)中連通子圖規(guī)模變化曲線?？梢钥吹奖疚乃惴ㄔ谡麄€部署過程中都維持了較低的連通子圖規(guī)模，說明本文算法有效的降低了網(wǎng)絡(luò)的資源碎片度。PS算法在底層資源不足時，會選擇分割鏈路進(jìn)行部署，形成較多的資源碎片，對底層網(wǎng)絡(luò)造成較大影響，所以在圖中有一個突變。

圖8 節(jié)點數(shù)100時，連通子圖規(guī)模變化

圖9 節(jié)點數(shù)100的BA網(wǎng)絡(luò)接受率曲線

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

4 結(jié)束語

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