高可用多實例虛擬網絡功能鏈彈性部署策略

黃 緯,張建德,溫志萍,彭煥峰

(南京工程學院 計算機工程學院, 南京 211167)

隨著互聯網規模不斷增大,網絡結構逐步復雜化．當前,網絡承載了大量的服務,而這些服務需要某些特定的網絡功能來實現或支撐．傳統的網絡功能由硬件實現,這帶來了升級維護不便和布線困難等弊端．為了提供更高的靈活性和擴展性,網絡功能虛擬化(network function virtualization,NFV)技術應運而生.通過將硬件和軟件解耦,使得虛擬網絡功能(virtualized network function,VNF)以軟件的形式運行在通用硬件平臺上,避免了硬件實現的弊端．在虛擬化環境中,網絡服務通常以虛擬網絡功能鏈(virtualized network function chain,VNFC)的形式提供,數據包按照一定的順序依次通過部署在服務器上的若干VNF,并進行相應處理[1]．

另一方面,由于互聯網的開放性和動態性,使得網絡服務不再絕對可靠和安全,服務中斷可能會帶來大量的經濟損失和極差的用戶體驗．文獻[2]中指出,2010年北美洲僅因為網絡服務中斷就承受了265億美元的損失．據調查,當企業關鍵系統出現結點失效時,營收能力將平均下降29%．文獻[3]中總結了可能引起服務中斷故障的幾種因素,其中包括硬件故障(服務器故障、電力中斷等)、軟件故障(通常是操作系統、虛擬機或軟件自身問題)以及操作故障(錯誤操作或配置等)．為了應對網絡故障并降低服務中斷影響,服務提供商與用戶間通常會定義一種雙方認可的服務水平協議，規定所提供服務的可用性要求,通常來說這個指標是驅動服務質量提升的主要因素．

為了提供高可用的網絡服務,目前有大量相關工作對VNFC部署策略進行了研究．文獻[4]中通過將VNFC部署問題抽象并分解為兩個NP難問題(設施選址問題和廣義分配問題),設計了一種近似算法,通過兩階段進行問題求解,實現了VNF部署．文獻[5]中則提出了一個考慮截止時間保證的VNF調度分配方案,目標是能夠最大化滿足服務等級協議保證的服務鏈請求的數量,同時保證租戶之間的隔離性．文獻[6]中考慮用預先指定的VNF實例部署策略來取代自由無約束的VNF部署,在總通信流量恒定的情況下,通過使服務器的內部帶寬最大化，以使外部通信開銷最小化．另外文獻[7-9]中從不同角度對VNFC部署進行了不同程度的探討和研究．

但是,實際網絡不會總是可靠的,需要對VNFC設計相應的容錯機制,以應對可能出現的各種網絡故障．因此在上述工作的基礎上,有些學者開始考慮NFV冗余容錯機制.文獻[10]中針對網絡設備故障設計了一種冗余備份策略,通過整合不同VNF的冗余備份資源,減少了容錯的資源消耗．文獻[11]中總結了3種典型的VNFC冗余備份模型(端到端冗余、節點冗余、鏈路冗余),并將其形式化,提出了一種基于線性規劃的求解策略．文獻[12]中圍繞VNF可靠性和路由優化問題進行了研究,假設各個網絡設備可靠性相互獨立，將問題描述為整數線性規劃,并提出了用一種啟發式方法對其進行高效求解．而文獻[13]中設計了一種VNF的故障回滾機制,保證在故障恢復過程中內部狀態的一致性．

但是,現有的相關工作仍存在一些不足．目前有一些工作已經開始對VNFC的高可用部署和狀態管理進行初步探究[13-15],但是在VNFC的構建和部署方面依然存在一些難題．首先,由于目前的VNF狀態一致性問題尚未有成熟的解決方案,因此現有工作中的VNFC部署問題多考慮的是具有較廣適用性的單實例場景,在這些工作中,多數仍假設NFV系統工作在可靠網絡的環境中,并沒有考慮系統故障和容錯方面的問題．另一方面,由于服務的動態伸縮已經成為當前網絡中愈加明顯的特征,為了應對傳統部署方案中單點故障和性能瓶頸這兩個問題,多實例的部署問題也將成為NFV技術中不可忽視的一項挑戰．為了保證多實例VNFC正常工作和遷移操作的狀態一致性,目前有工作開始從系統方面對NFV狀態管理機制進行研究,但是在VNFC部署策略方面則尚未出現較為成熟的解決方案,現有的相關算法因為抽象度高或缺少深度優化等原因,并不適用于實際場景．基于上述研究現狀,文中針對多實例VNFC部署問題,基于共享狀態的NFV機制，提出一種彈性VNFC部署策略,通過基于節點評分的多實例擴展算法減少部署帶來的通信開銷和實例開銷,并使用多實例冗余備份策略提高VNFC的可用性．實驗證明文中提出的部署策略相比于現有策略,能夠有效減少虛擬網絡功能鏈部署的資源開銷．

1 網絡功能狀態與彈性部署

1.1 網絡功能狀態

在NFV的實現中,各類VNF通常需要保存某些網絡狀態信息，如數據流信息、地址映射等,以支持數據包過濾、內容分析等各種復雜操作．根據文獻[16]中總結的典型VNF的數據包處理流程,當VNF接收到數據包時,根據包頭的五元組信息在VNF存儲的狀態中進行查詢,并決定對包進行修改、丟棄、轉發等操作．狀態可分為內部狀態和外部狀態，內部狀態只與當前VNF實例相關,而外部狀態與網絡中的其他同類VNF相關,需要維持其一致性．另外,外部狀態中還分為相關狀態和非相關狀態，前者與數據流無關,只涉及此類VNF本身的信息,而后者則可能隨著數據流的到達和處理而被修改．

以負載均衡(load balancer, LB)為例,負載均衡是數據中心基礎設施的一個基本功能,對數據中心中的各種在線服務非常關鍵．為了應對大量服務請求,一個服務的背后通常有大量服務器在進行請求分流,以保證整體服務的性能．如圖1,用戶訪問服務的地址稱為虛擬IP(virtual IP address,VIP),這是由服務公開的一個或多個用于接受外界訪問的地址．由多臺提供此服務的服務器構成服務集群,每臺服務器都有自身的直接IP(direct IP address,DIP)．LB接收所有發往VIP的請求流量,并根據特定的策略(隨機、哈希等)為請求分配一個服務器并指定DIP,通過IP-in-IP封裝將數據流分配到對應的服務器進行處理．為了將同一條流的數據包正確地轉發到一個服務器,需要在LB中記錄每條數據流與分配的服務器之間的映射關系,這通常為一個IP五元組到IP地址的映射表．每次接收到數據包,LB根據包頭的五元組在表中查詢是否存在IP映射,如果存在則直接轉發,如果不存在,說明這是一條新的數據流,則根據特定策略為其分配一個服務器,并將這條新的五元組到DIP的條目加入映射表．這樣的映射表就屬于網絡功能LB的內部狀態,而每次到來的數據包都有可能對這個內部狀態進行修改更新．

圖1 負載均衡功能的工作流程Fig.1 Workflow of load balance function

1.2 服務彈性部署與共享狀態機制

隨著移動計算的發展和用戶需求的快速變化,網絡中的各類VNF對資源的需求也隨著時間推移而不斷變化．文獻[17]中對數據中心網絡中不同時段的VNF利用率進行了調研,并指出VNF的利用率在時間維度上劇烈變化,而這對于NFV的性能是一個巨大的考驗,當對VNF的需求增長或減少時,需要對各類VNF進行性能伸縮，以最大限度地利用網絡資源并減少性能開銷．一般來說，對網絡功能進行性能伸縮可以通過橫向調整和縱向調整實現.以性能擴展為例,縱向擴展指為單臺機器添加更多或更強的CPU、 存儲和網卡設備,網絡功能能夠從硬件資源中獲得更強的處理能力,從而滿足用戶的需求;橫向擴展指添加更多的網絡功能設備,設備之間互相協調合作,利用更多的機器資源來提升整體處理能力,從而達到滿足用戶需求的性能水平．而對于VNF來說,由于虛擬化技術和靈活彈性部署的需求,對通用設備友好的橫向調整策略通常是更優的性能伸縮方案．

為了滿足服務擴展性,虛擬網絡功能組成的網絡功能鏈不再以單鏈拓撲的形式出現,每類VNF可能由多個運行于不同服務器的VNF實例共同組成,而每類VNF的多個實例之間又按照特定的順序互相連接,形成了一種有序的網狀結構,如圖2． 然而,一旦使用多實例網絡功能,實例之間的狀態問題就不可避免地凸顯出來,無論是多實例協同工作還是進行動態性能伸縮,如何保證網絡功能狀態的無縫同步和快速遷移就成為亟待解決的問題．針對該問題，文獻[15]中調研了大量網絡功能的內部狀態,設計了一套通用的支持VNF狀態遷移的API,并通過修改網絡功能的內部實現,對虛擬網絡功能的遷移和動態擴展提供了一定的支持．但是文獻[14]中指出,對各個獨立的網絡功能實例內部狀態進行操作來實現全局狀態一致的策略是非常低效的,且本質上并沒有解決狀態一致性與錯誤恢復等問題．

圖2 網狀虛擬網絡功能鏈Fig.2 Reticular virtual network function chain

另一方面,為了滿足服務的可用性,必須保證當網絡中某個設備故障時,服務的處理速率不出現明顯降低．但是由于內部狀態容易因機器故障而丟失,因此對于突發性故障,如何保證網絡功能的快速故障轉移與恢復是另一個亟待解決的難題．現有的對突發性故障的解決思路一般有兩種,一種是設置周期性的檢查點，定期將網絡功能的內部狀態作為快照存儲下來,一旦出現突發故障,就能夠根據最近的快照對原實例進行重建[18];第二種是對每個輸入的數據包進行記錄，發生故障后根據日志記錄對內部狀態進行推演,從而還原故障的虛擬網絡功能[13]． 但是這些策略可能會顯著增加每個數據包的轉發延遲(通常數量級達到10 ms),而且狀態重建也可能會耗費大量的時間,這對于大部分對穩定性要求較高的服務來說是無法接受的．

為了從根本上解決由于多實例VNFC部署帶來的狀態一致性問題,現在有一些研究者開始考慮對狀態進行集中化管理,處理數據包，對狀態數據解耦,把現有的網絡功能分解成無狀態的處理單元和通用的數據層,由處理單元負責具體的功能處理,并將處理后的網絡狀態與通用的數據層同步,可以使VNF更加易于擴展、升級．如文獻[14]中提出了一種狀態集中化的網絡功能虛擬化架構StatelessNF,通過將系統中的VNF部分內部狀態托管于低延遲、高可靠的數據存儲系統,實現了網絡功能實例之間的獨立．VNF狀態的共享集中管理對處理單元和狀態數據進行了解耦,極大地增強了服務的靈活性和可靠性,是一種具有樂觀前景的NFV解決方案．目前學術界對于這種無狀態網絡功能鏈的資源部署等研究較少,由于狀態管理方式的不同,現有的網絡功能鏈部署策略也都無法適用,因此文中對共享狀態的多實例網絡功能鏈進行研究,并提出一種有效的高可用VNFC部署策略．

2 高可用多實例虛擬網絡功能鏈部署問題

為了解決虛擬網絡功能鏈的部署問題,同時提供一定的可用性保障,需要對網絡資源約束和服務水平約束進行形式化處理,從而構建一個有效的網絡功能鏈模型,并定義相應的網絡功能鏈部署問題．文中基于集中化的VNF狀態管理機制,對 VNFC 的模型構建與彈性部署問題進行研究分析．

2.1 可用性模型

由于VNF實例的去狀態化,對于同一類VNF來說,多個位于不同服務器的實例之間的狀態可以認為是同步的,邏輯上可以將其視為同一個VNF實例,因此經過各個實例的數據流不再不可分流;另一方面,共享狀態的VNF實例之間能夠進行互相備份,將同類VNF的實例分別部署在不同的服務器上,一旦某個VNF實例發生突發性故障,系統整體的流量處理能力將出現不同程度下降,從而導致服務吞吐量下降等性能損失．

(1)

式中：Av和Aw為服務器節點的可用性．g(n)為當n中節點均發生故障時VNFCc總處理能力的剩余比例,計算為:

(2)

式中：C(i)為單個VNFi實例能夠提供的最大處理能力；Ci,v,h為VNFi在節點v上實例h已使用的處理能力；ratec為VNFCc的流量速率．式(2)給出了當n中節點均故障時,整條VNFC在使用所有實例剩余處理能力后,能夠提供的總處理性能相比VNFC請求速率的比例．綜上所述,式(3)給出了一條VNFCc的可用性計算公式:

(3)

需要指出的是,文中的可用性計算更多考慮網絡故障時VNFC的服務性能損失比例,因此使用g(·)刻畫VNF實例處理能力的變化．

為了滿足部署策略的可行性,需要保證每個VNF實例得到足夠的CPU資源進行流量處理,因此任何一個服務器上所有VNF占用的CPU資源總和不能超過機器的物理資源上限:

(4)

同樣的,每條物理鏈路上經過的流量總和不能超過其帶寬上限:

(5)

為了保證用戶請求的數據流都能夠被處理,每個VNF實例處理的流量速率總和不能超過其處理能力上限:

(6)

另外,為了保證網絡中的流量是可行流,必須保證每個非端點節點的入流和出流相等:

(7)

(8)

2.2 問題定義

不同于單實例VNFC部署問題，當狀態集中共享之后,部署請求中的VNF可能在部署策略中由若干個同類VNF實例組成,具體的實例數量是未知的．

問題優化目標是使部署開銷最小化，其中包含了部署VNF實例產生的開銷(授權、維護等)以及實例之間流量轉發產生的通信開銷:

(9)

式中,Be表示物理鏈路e的帶寬上限．每個VNF部署的實例數量對最終的部署策略和總體開銷會產生一定的影響,如實例數量較多,用戶可用性要求較容易滿足,但是增加了實例部署開銷,且容易較快用完網絡中的計算資源;而若實例數量較少,每個實例的處理能力有限,會導致請求的流量無法及時處理,且可能導致路由的路徑過于集中而產生流量熱點,進而出現網絡擁塞,影響網絡整體性能．接下來,根據上文描述的問題模型,給出多實例VNFC部署問題的定義．

高可用多實例虛擬網絡功能鏈部署問題定義：給定物理網絡G(V,E)及一組部署請求,將每類VNF的若干實例部署在網絡中形成VNFC,給出請求到VNFC的映射關系,滿足部署的可行性約束式(4～7),且通過實例互相備份使得每條VNFC的可用性滿足式(8),并使部署策略的總開銷式(9)最小化．

3 多實例虛擬網絡功能鏈部署策略

現有工作中對于單實例VNFC部署問題及虛擬網絡嵌入(virtual network embedding,VNE)的研究較為成熟,但是對于文中討論的多實例部署問題,由于部署的實例數量事先并不知道,需要根據物理網絡、用戶部署請求的信息進行動態決策,所以現有工作中的解決方案無法適用．一種可行的部署策略是,預先根據輸入信息,估計每類VNF部署的數量,使得部署請求中的VNF鏈轉換為一個有向無環圖(directed acyclic graph,DAG),將其視為一個虛擬網絡(virtual network,VN)并利用現有的VNE算法進行虛擬網絡部署．這種方法將文中的多實例部署問題轉化為一個已經有成熟解法的問題,但是由于在DAG轉化過程中,并沒有物理網絡和部署信息的指導,形成了一個兩階段分離的部署策略,其中的第1步DAG 轉換可能導致形成的VN不適合部署于當前的物理網絡,導致最后的部署開銷較大．文中實驗部分將會實現一個基于VNE算法的多實例部署方案,通過實驗證明其可能會導致較大的部署開銷．

文中針對多實例虛擬網絡功能鏈部署問題,提出了一種基于多實例擴展的部署算法,避免了多階段部署帶來的缺點,在使用盡可能少的節點數的前提下,使整體的帶寬消耗最小化．

3.1 問題最優解形式與開銷分析

首先對多實例虛擬網絡功能鏈部署問題的最優解進行分析,并試圖找到其開銷的理論下界．根據式(9),部署開銷分為實例開銷和通信開銷．一方面,為了盡可能減小部署帶來的實例開銷,應該在滿足用戶請求可用性要求的前提下,盡可能減少VNF實例的個數．為得到VNF實例數量的理論下界,假設物理網絡的每個節點的可用性都取所有節點可用性中的最大值,即:

(10)

(11)

對上式進行變換得到:

(12)

(13)

另一方面,為了盡可能減少實例間的通信開銷,在部署請求的流量速率不變的情況下,應盡量減小每條流量路徑的長度．為了得到通信開銷的理論下界,假設對于網絡功能鏈c,部署在網絡中的每條路徑長度都是最小值,即從c的源點s到終點d之間的最短路徑的長度|shortestPath(G,s,d)|．當VNF的狀態集中共享之后,用戶請求的流量是可分流的，因此對于功能鏈c,通信開銷的理論下界為:

(14)

綜上所述,多實例網絡功能鏈部署問題的理論下界可以表示為:

(15)

文中分析了問題最優解可能的形式,但是由于這是一個NP難問題,直接尋找其最優解是困難的,其對應的整數線性規劃問題求解的復雜度也是不可接受的．因此文中根據上述的問題分析,同時考慮實例開銷和通信開銷,提出一種基于多節點擴展的優化部署算法,在不斷迭代過程中,將需要的VNF實例依次引入,并保證帶寬消耗最小,直到滿足處理能力要求和可用性要求．

3.2 部署算法

文中提出一種基于多實例擴展的多實例部署策略EXTEND．首先,根據到來的用戶請求的流量速率和可用性要求,計算每個請求的權重:

(16)

按照權重從大到小的順序對請求進行排序,依次部署．之后,對于一個待部署的請求,將其需要的VNF各部署一個實例,使得網絡功能鏈具有初步的完整形狀．根據式(9),為了保證帶寬消耗最小,部署每個VNF的第1個實例時,選擇部署節點的依據是使該節點u∈V到源點和終點的距離之和distance(s,u)+distance(u,d)盡可能小,在距離之和相同的情況下,選擇可用性最大的節點．

每類VNF的首個實例部署完成后,需要判斷當前的網絡功能鏈是否滿足要求,需要滿足兩個標準：① 計算當前網絡功能鏈的可用性,判斷是否達到用戶請求的可用性要求;② 判斷每類VNF的實例處理能力之和是否大于請求的流量速率．若兩個條件都達到,則此請求部署完成,繼續部署下一個請求;否則,需要為這一輪部署中的瓶頸VNFb∈c.NF增加實例．這里的瓶頸指當前功能鏈中可用性最小的VNF或者實例處理能力不足的VNF．

為VNFb增加實例時,需要選擇實例的放置節點,為了形成互相冗余備份,候選節點應該排除已經部署了b的實例的節點．定義候選集合Vc,其中包含了所有已部署同類VNF實例的節點和CPU計算資源足夠增加新實例的節點．為了使部署的通信開銷最小化,同時充分利用VNF實例,按照式(17，18)計算每個候選節點t的評分:

(17)

(18)

式中：Vpre(b)和Vpost(b)分別表示請求c的VNF列表中VNFb的前驅和后繼VNF的所有已部署實例所在的節點集合；Cb,v,h指節點v上對應VNFb的實例h的已使用處理能力比例,若不存在則為0． 根據式(17，18),每個節點的評分依據標準化的節點帶寬開銷與已有VNF實例占用處理能力比例來衡量,其中帶寬開銷指距離前驅和后繼VNF所有實例的距離之和．將實例部署在評分最小的節點上,能夠減少部署時的帶寬消耗,同時充分利用已部署實例資源,提高整體的資源利用率．以此進行迭代,重新判斷當前的網絡功能鏈是否滿足要求,并按相同的策略進行處理,直到滿足要求為止．

(19)

需要注意的是,在本問題中,計算的網絡流是多源多匯的,因此每次計算最大流時,為源點集和終點集添加一對虛擬源點s′和虛擬匯點d′,與其他節點連接的帶寬根據上述分配原則分別設置為各個源點和各個匯點對應的流量,s′到d′的最大流即為要求的VNF多實例間的網絡流．每類VNF 實例間的路由策略計算完成后,當前的請求部署完成,之后按照上述過程部署下一個請求,直到所有請求都成功部署到物理網絡中．

算法的偽代碼如下:

(1)sortedRequests=sortByWeight(Requests)

(2) forr∈sortedRequests:

(3) fori∈r.NF:

(4)candidate=FindNode(G,{r.src},{r.dst},i)

(5)place[r][i]=candidate

(6)update(G)

(7) endfor

(8) loop

(9)bn=Check()∥判斷當前鏈是否滿足要求

(10) ifbn==-1

(11) break

(12) endif

(13)candidate=FindNode(G,pre(bn),post(bn),bn)∥按照式(17，18)選擇候選節點

(14)place[r][i]=candidate

(15)update(G)

(16) endloop

(17)route[r]=Flow(G,place)∥計算網絡流

(18) endfor

(19) return {place,route}

其中選擇部署候選節點位置的過程FindNode(G,{r.src},{r.dst},i)的偽代碼如下:

(1) forv∈V:

(2) ifv上已有VNFi的實例h或v.CPU≥U(i)

(3)Vc.add(v)

(4) endif

(5) ifVc==?:

(6) returnnull

(7) endif

(8) endfor

(9) forv∈Vc:

(10) 按照式(17，18)計算每個節點v的rankv

(11) endfor

∥升序對Vc進行排序

(12)sortedV=sortByRank(Vc)

(14) returnsortedV[0]

4 實驗結果與分析

4.1 實驗配置

模擬實驗平臺配置為Intel Core i5-4590 3.30GHz CPU,8GB內存．實驗中使用的物理網絡拓撲來自SNDlib[19]的nobel-germany網絡,其中包含50個物理節點,由88 條物理鏈路互相連接．對于每個物理節點,設定其CPU 計算資源為800單位(為簡化問題,文中只考慮CPU計算資源,但易于擴展到內存、網卡等多資源情況),其可用性在90%～99%之間按均勻分布隨機取值,而每條物理鏈路的雙向帶寬均為2 000 Mbps;用戶的部署請求隨機生成,每個請求的流量速率要求在[20, 40]之間按均勻分布隨機取值,且可用性要求在[0.8,0.9]之間按均勻分布隨機取值．實驗中設置8種VNF,其CPU資源消耗分別為45、35、30、25、35、40、20、30，數據包實時處理能力分別為15、20、20、15、15、20、25、30，生成的隨機VNF序列長度分別在[2,4]和[4,6]間隨機取值．

現有工作中還沒有考慮進行多實例相互備份的高可用VNFC部署算法,為此,文中將貪心算法Greedy作為對比算法,同EXTEND算法的性能進行比較．Greedy在部署實例時,選擇計算資源最大的節點作為候選節點,直到滿足網絡功能鏈可用性．

考慮到本問題的形式與VNE問題也存在一定的相似性,因此文中選擇了文獻[20]中提出的VNE 部署算法OVNM作為對比算法,并進行了相應修改．VNE問題給定一組虛擬網絡請求和一個物理網絡,將所有虛擬網絡部署到物理網絡中．OVNM的思路是在部署虛擬網絡時,盡可能選擇相鄰鏈路帶寬總和最大的節點作為首個部屬節點,以提升后續節點和鏈路成功部署的概率,當發生無法部署的情況時進行回溯．相比于VNE問題,多實例VNFC部署問題也需要將一個虛擬網絡部署到物理網絡中,但是這個虛擬網絡并不是給定的,事實上部署請求中只規定了VNF順序、流量速率等,因此本質上這是兩類不同的問題．文中對OVNM進行了一定的修改,首先計算出每個部署請求的每類VNF 實例數量的最小值,使其滿足請求的可用性要求,形成明確的虛擬網絡,之后使用OVNM原算法對生成的虛擬網絡進行部署．

4.2 結果與分析

首先,文中對EXTEND本身的性能進行一些測試．圖3展示了分別在長鏈(功能鏈長度為[4,6],默認為[2,4])和高可用性(可用性要求為[0.9, 0.99],默認為[0.8, 0.9])，而其他參數默認的情況下,隨著請求速率增長,EXTEND的通信帶寬使用量變化情況；而圖4展示了實例個數的使用情況．可以看出,可用性要求較高的情況下,部署的帶寬消耗沒有額外增加,而實例個數顯著增加,這是因為網絡中增加了額外的VNF實例以滿足可用性要求,但是由于實例之間分攤流量,數據包路由的路徑長度基本不變．而長鏈情況下,為了部署更多的VNF,帶寬消耗略有增加,而實例個數顯著增加．

圖3 EXTEND在不同參數下的通信帶寬開銷Fig.3 Communication bandwidth cost in differentparameters of EXTEND

圖4 EXTEND在不同參數下的實例開銷Fig.4 Deployment cost in differentparameters of EXTEND

然后,文中將提出的EXTEND與前述的OVNM算法和Greedy算法進行對比．圖5展示了在部署請求的數量增加時,3種部署算法的通信開銷變化情況,可以看出Greedy消耗了較多通信帶寬,EXTEND帶寬開銷最小,而OVNM的通信開銷略高于EXTEND,總的來說,EXTEND相比Greedy和OVNM,在相同環境下能夠平均節省約39.9%和13.7%的通信帶寬開銷．這是因為EXTEND在部署時,從最短路徑開始進行擴充,且每一步盡可能減少路由路徑的長度,使得總路徑長度較其他算法更短,因此節省了更多的帶寬資源．

圖5 不同請求數量下的通信帶寬使用量Fig.5 Communication bandwidth usage ofdifferent request number

圖6展示了不同請求數量下,3種部署算法的實例使用數量的變化情況．

圖6 不同請求數量下的VNF實例使用數量Fig.6 VNF number of different request number

可以從圖中看出,EXTEND和Greedy的實例個數差別不大,而OVNM則比EXTEND平均高大約49.4%,這是因為OVNM是多階段方法,為了使用這個針對VNE的部署算法,在形成虛擬網絡時沒有物理網絡和請求的信息作為指導,因此可能導致部署多余的實例,使得實例部署數量較大．

為了衡量部署策略的總體性能,文中綜合考慮部署的通信帶寬使用量和VNF實例數量,根據式(9)定義部署開銷指數,其中β=1,γ=15．此指標衡量了VNFC部署結果的總體資源消耗,并反映了部署策略的資源利用率．從圖7中可以看出3種部署算法的總體部署開銷指數,文中提出的EXTEND算法比其他兩種算法具有更低的部署開銷,比OVMN 和Greedy 分別降低了23.1% 和26.6%．Greedy在部署過程中優先選擇剩余計算資源較多的節點,因而節點之間路徑長度較大,導致通信開銷較大;OVNM為了滿足可用性要求，生成的虛擬網絡冗余節點數量可能過多,因此實例開銷較大．反之,EXTEND算法從最短路徑開始擴展,且按照節點位置計算評分,使得整體通信開銷較小,另外在部署過程中不斷迭代,每次在合適的位置添加實例,因此保證能夠在滿足可用性要求的前提下使實例開銷最小化．

圖7 不同請求數量下的部署開銷指數Fig.7 Deployment cost index of different request number

最后,圖8展示了3種算法的平均執行時間,可以看出EXTEND 的執行時間比Greedy略微增加了一些,而OVMN 由于需要進行回溯，執行時間增加了約1倍．

圖8 不同請求數量下的執行時間Fig.8 Processing time of different request number

5 結論

(1) 文中針對多實例VNFC彈性部署問題,對虛擬網絡功能內部的狀態和一致性問題進行了闡述,并介紹了幾種現有的解決方案和機制．

(2) 為了達到最優化的部署效果,基于現有的共享狀態的系統機制,文中構建了一種用于衡量可用性的模型,并針對高可用的多實例VNFC部署問題,提出一種基于多實例擴展的優化部署算法,通過多個實例間的冗余備份及迭代引入VNF,在滿足可用性要求的前提下使帶寬使用最小化．

(3) 模擬實驗表明,相比于現有算法,文中提出的算法在降低部署實例數量和通信帶寬方面能夠達到更好的效果．