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

(南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院, 南京 211167)

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

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

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

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

但是,現(xiàn)有的相關(guān)工作仍存在一些不足．目前有一些工作已經(jīng)開始對(duì)VNFC的高可用部署和狀態(tài)管理進(jìn)行初步探究[13-15],但是在VNFC的構(gòu)建和部署方面依然存在一些難題．首先,由于目前的VNF狀態(tài)一致性問題尚未有成熟的解決方案,因此現(xiàn)有工作中的VNFC部署問題多考慮的是具有較廣適用性的單實(shí)例場(chǎng)景,在這些工作中,多數(shù)仍假設(shè)NFV系統(tǒng)工作在可靠網(wǎng)絡(luò)的環(huán)境中,并沒有考慮系統(tǒng)故障和容錯(cuò)方面的問題．另一方面,由于服務(wù)的動(dòng)態(tài)伸縮已經(jīng)成為當(dāng)前網(wǎng)絡(luò)中愈加明顯的特征,為了應(yīng)對(duì)傳統(tǒng)部署方案中單點(diǎn)故障和性能瓶頸這兩個(gè)問題,多實(shí)例的部署問題也將成為NFV技術(shù)中不可忽視的一項(xiàng)挑戰(zhàn)．為了保證多實(shí)例VNFC正常工作和遷移操作的狀態(tài)一致性,目前有工作開始從系統(tǒng)方面對(duì)NFV狀態(tài)管理機(jī)制進(jìn)行研究,但是在VNFC部署策略方面則尚未出現(xiàn)較為成熟的解決方案,現(xiàn)有的相關(guān)算法因?yàn)槌橄蠖雀呋蛉鄙偕疃葍?yōu)化等原因,并不適用于實(shí)際場(chǎng)景．基于上述研究現(xiàn)狀,文中針對(duì)多實(shí)例VNFC部署問題,基于共享狀態(tài)的NFV機(jī)制，提出一種彈性VNFC部署策略,通過基于節(jié)點(diǎn)評(píng)分的多實(shí)例擴(kuò)展算法減少部署帶來的通信開銷和實(shí)例開銷,并使用多實(shí)例冗余備份策略提高VNFC的可用性．實(shí)驗(yàn)證明文中提出的部署策略相比于現(xiàn)有策略,能夠有效減少虛擬網(wǎng)絡(luò)功能鏈部署的資源開銷．

1 網(wǎng)絡(luò)功能狀態(tài)與彈性部署

1.1 網(wǎng)絡(luò)功能狀態(tài)

在NFV的實(shí)現(xiàn)中,各類VNF通常需要保存某些網(wǎng)絡(luò)狀態(tài)信息，如數(shù)據(jù)流信息、地址映射等,以支持?jǐn)?shù)據(jù)包過濾、內(nèi)容分析等各種復(fù)雜操作．根據(jù)文獻(xiàn)[16]中總結(jié)的典型VNF的數(shù)據(jù)包處理流程,當(dāng)VNF接收到數(shù)據(jù)包時(shí),根據(jù)包頭的五元組信息在VNF存儲(chǔ)的狀態(tài)中進(jìn)行查詢,并決定對(duì)包進(jìn)行修改、丟棄、轉(zhuǎn)發(fā)等操作．狀態(tài)可分為內(nèi)部狀態(tài)和外部狀態(tài)，內(nèi)部狀態(tài)只與當(dāng)前VNF實(shí)例相關(guān),而外部狀態(tài)與網(wǎng)絡(luò)中的其他同類VNF相關(guān),需要維持其一致性．另外,外部狀態(tài)中還分為相關(guān)狀態(tài)和非相關(guān)狀態(tài)，前者與數(shù)據(jù)流無(wú)關(guān),只涉及此類VNF本身的信息,而后者則可能隨著數(shù)據(jù)流的到達(dá)和處理而被修改．

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

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

1.2 服務(wù)彈性部署與共享狀態(tài)機(jī)制

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

為了滿足服務(wù)擴(kuò)展性,虛擬網(wǎng)絡(luò)功能組成的網(wǎng)絡(luò)功能鏈不再以單鏈拓?fù)涞男问匠霈F(xiàn),每類VNF可能由多個(gè)運(yùn)行于不同服務(wù)器的VNF實(shí)例共同組成,而每類VNF的多個(gè)實(shí)例之間又按照特定的順序互相連接,形成了一種有序的網(wǎng)狀結(jié)構(gòu),如圖2． 然而,一旦使用多實(shí)例網(wǎng)絡(luò)功能,實(shí)例之間的狀態(tài)問題就不可避免地凸顯出來,無(wú)論是多實(shí)例協(xié)同工作還是進(jìn)行動(dòng)態(tài)性能伸縮,如何保證網(wǎng)絡(luò)功能狀態(tài)的無(wú)縫同步和快速遷移就成為亟待解決的問題．針對(duì)該問題，文獻(xiàn)[15]中調(diào)研了大量網(wǎng)絡(luò)功能的內(nèi)部狀態(tài),設(shè)計(jì)了一套通用的支持VNF狀態(tài)遷移的API,并通過修改網(wǎng)絡(luò)功能的內(nèi)部實(shí)現(xiàn),對(duì)虛擬網(wǎng)絡(luò)功能的遷移和動(dòng)態(tài)擴(kuò)展提供了一定的支持．但是文獻(xiàn)[14]中指出,對(duì)各個(gè)獨(dú)立的網(wǎng)絡(luò)功能實(shí)例內(nèi)部狀態(tài)進(jìn)行操作來實(shí)現(xiàn)全局狀態(tài)一致的策略是非常低效的,且本質(zhì)上并沒有解決狀態(tài)一致性與錯(cuò)誤恢復(fù)等問題．

圖2 網(wǎng)狀虛擬網(wǎng)絡(luò)功能鏈Fig.2 Reticular virtual network function chain

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

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

2 高可用多實(shí)例虛擬網(wǎng)絡(luò)功能鏈部署問題

為了解決虛擬網(wǎng)絡(luò)功能鏈的部署問題,同時(shí)提供一定的可用性保障,需要對(duì)網(wǎng)絡(luò)資源約束和服務(wù)水平約束進(jìn)行形式化處理,從而構(gòu)建一個(gè)有效的網(wǎng)絡(luò)功能鏈模型,并定義相應(yīng)的網(wǎng)絡(luò)功能鏈部署問題．文中基于集中化的VNF狀態(tài)管理機(jī)制,對(duì) VNFC 的模型構(gòu)建與彈性部署問題進(jìn)行研究分析．

2.1 可用性模型

由于VNF實(shí)例的去狀態(tài)化,對(duì)于同一類VNF來說,多個(gè)位于不同服務(wù)器的實(shí)例之間的狀態(tài)可以認(rèn)為是同步的,邏輯上可以將其視為同一個(gè)VNF實(shí)例,因此經(jīng)過各個(gè)實(shí)例的數(shù)據(jù)流不再不可分流;另一方面,共享狀態(tài)的VNF實(shí)例之間能夠進(jìn)行互相備份,將同類VNF的實(shí)例分別部署在不同的服務(wù)器上,一旦某個(gè)VNF實(shí)例發(fā)生突發(fā)性故障,系統(tǒng)整體的流量處理能力將出現(xiàn)不同程度下降,從而導(dǎo)致服務(wù)吞吐量下降等性能損失．

(1)

式中：Av和Aw為服務(wù)器節(jié)點(diǎn)的可用性．g(n)為當(dāng)n中節(jié)點(diǎn)均發(fā)生故障時(shí)VNFCc總處理能力的剩余比例,計(jì)算為:

(2)

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

(3)

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

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

(4)

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

(5)

為了保證用戶請(qǐng)求的數(shù)據(jù)流都能夠被處理,每個(gè)VNF實(shí)例處理的流量速率總和不能超過其處理能力上限:

(6)

另外,為了保證網(wǎng)絡(luò)中的流量是可行流,必須保證每個(gè)非端點(diǎn)節(jié)點(diǎn)的入流和出流相等:

(7)

(8)

2.2 問題定義

不同于單實(shí)例VNFC部署問題，當(dāng)狀態(tài)集中共享之后,部署請(qǐng)求中的VNF可能在部署策略中由若干個(gè)同類VNF實(shí)例組成,具體的實(shí)例數(shù)量是未知的．

問題優(yōu)化目標(biāo)是使部署開銷最小化，其中包含了部署VNF實(shí)例產(chǎn)生的開銷(授權(quán)、維護(hù)等)以及實(shí)例之間流量轉(zhuǎn)發(fā)產(chǎn)生的通信開銷:

(9)

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

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

3 多實(shí)例虛擬網(wǎng)絡(luò)功能鏈部署策略

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

文中針對(duì)多實(shí)例虛擬網(wǎng)絡(luò)功能鏈部署問題,提出了一種基于多實(shí)例擴(kuò)展的部署算法,避免了多階段部署帶來的缺點(diǎn),在使用盡可能少的節(jié)點(diǎn)數(shù)的前提下,使整體的帶寬消耗最小化．

3.1 問題最優(yōu)解形式與開銷分析

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

(10)

(11)

對(duì)上式進(jìn)行變換得到:

(12)

(13)

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

(14)

綜上所述,多實(shí)例網(wǎng)絡(luò)功能鏈部署問題的理論下界可以表示為:

(15)

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

3.2 部署算法

文中提出一種基于多實(shí)例擴(kuò)展的多實(shí)例部署策略EXTEND．首先,根據(jù)到來的用戶請(qǐng)求的流量速率和可用性要求,計(jì)算每個(gè)請(qǐng)求的權(quán)重:

(16)

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

每類VNF的首個(gè)實(shí)例部署完成后,需要判斷當(dāng)前的網(wǎng)絡(luò)功能鏈?zhǔn)欠駶M足要求,需要滿足兩個(gè)標(biāo)準(zhǔn)：① 計(jì)算當(dāng)前網(wǎng)絡(luò)功能鏈的可用性,判斷是否達(dá)到用戶請(qǐng)求的可用性要求;② 判斷每類VNF的實(shí)例處理能力之和是否大于請(qǐng)求的流量速率．若兩個(gè)條件都達(dá)到,則此請(qǐng)求部署完成,繼續(xù)部署下一個(gè)請(qǐng)求;否則,需要為這一輪部署中的瓶頸VNFb∈c.NF增加實(shí)例．這里的瓶頸指當(dāng)前功能鏈中可用性最小的VNF或者實(shí)例處理能力不足的VNF．

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

(17)

(18)

式中：Vpre(b)和Vpost(b)分別表示請(qǐng)求c的VNF列表中VNFb的前驅(qū)和后繼VNF的所有已部署實(shí)例所在的節(jié)點(diǎn)集合；Cb,v,h指節(jié)點(diǎn)v上對(duì)應(yīng)VNFb的實(shí)例h的已使用處理能力比例,若不存在則為0． 根據(jù)式(17，18),每個(gè)節(jié)點(diǎn)的評(píng)分依據(jù)標(biāo)準(zhǔn)化的節(jié)點(diǎn)帶寬開銷與已有VNF實(shí)例占用處理能力比例來衡量,其中帶寬開銷指距離前驅(qū)和后繼VNF所有實(shí)例的距離之和．將實(shí)例部署在評(píng)分最小的節(jié)點(diǎn)上,能夠減少部署時(shí)的帶寬消耗,同時(shí)充分利用已部署實(shí)例資源,提高整體的資源利用率．以此進(jìn)行迭代,重新判斷當(dāng)前的網(wǎng)絡(luò)功能鏈?zhǔn)欠駶M足要求,并按相同的策略進(jìn)行處理,直到滿足要求為止．

(19)

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

算法的偽代碼如下:

(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()∥判斷當(dāng)前鏈?zhǔn)欠駶M足要求

(10) ifbn==-1

(11) break

(12) endif

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

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

(15)update(G)

(16) endloop

(17)route[r]=Flow(G,place)∥計(jì)算網(wǎng)絡(luò)流

(18) endfor

(19) return {place,route}

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

(1) forv∈V:

(2) ifv上已有VNFi的實(shí)例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)計(jì)算每個(gè)節(jié)點(diǎn)v的rankv

(11) endfor

∥升序?qū)c進(jìn)行排序

(12)sortedV=sortByRank(Vc)

(14) returnsortedV[0]

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)配置

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

現(xiàn)有工作中還沒有考慮進(jìn)行多實(shí)例相互備份的高可用VNFC部署算法,為此,文中將貪心算法Greedy作為對(duì)比算法,同EXTEND算法的性能進(jìn)行比較．Greedy在部署實(shí)例時(shí),選擇計(jì)算資源最大的節(jié)點(diǎn)作為候選節(jié)點(diǎn),直到滿足網(wǎng)絡(luò)功能鏈可用性．

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

4.2 結(jié)果與分析

首先,文中對(duì)EXTEND本身的性能進(jìn)行一些測(cè)試．圖3展示了分別在長(zhǎng)鏈(功能鏈長(zhǎng)度為[4,6],默認(rèn)為[2,4])和高可用性(可用性要求為[0.9, 0.99],默認(rèn)為[0.8, 0.9])，而其他參數(shù)默認(rèn)的情況下,隨著請(qǐng)求速率增長(zhǎng),EXTEND的通信帶寬使用量變化情況；而圖4展示了實(shí)例個(gè)數(shù)的使用情況．可以看出,可用性要求較高的情況下,部署的帶寬消耗沒有額外增加,而實(shí)例個(gè)數(shù)顯著增加,這是因?yàn)榫W(wǎng)絡(luò)中增加了額外的VNF實(shí)例以滿足可用性要求,但是由于實(shí)例之間分?jǐn)偭髁?數(shù)據(jù)包路由的路徑長(zhǎng)度基本不變．而長(zhǎng)鏈情況下,為了部署更多的VNF,帶寬消耗略有增加,而實(shí)例個(gè)數(shù)顯著增加．

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

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

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

圖5 不同請(qǐng)求數(shù)量下的通信帶寬使用量Fig.5 Communication bandwidth usage ofdifferent request number

圖6展示了不同請(qǐng)求數(shù)量下,3種部署算法的實(shí)例使用數(shù)量的變化情況．

圖6 不同請(qǐng)求數(shù)量下的VNF實(shí)例使用數(shù)量Fig.6 VNF number of different request number

可以從圖中看出,EXTEND和Greedy的實(shí)例個(gè)數(shù)差別不大,而OVNM則比EXTEND平均高大約49.4%,這是因?yàn)镺VNM是多階段方法,為了使用這個(gè)針對(duì)VNE的部署算法,在形成虛擬網(wǎng)絡(luò)時(shí)沒有物理網(wǎng)絡(luò)和請(qǐng)求的信息作為指導(dǎo),因此可能導(dǎo)致部署多余的實(shí)例,使得實(shí)例部署數(shù)量較大．

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

圖7 不同請(qǐng)求數(shù)量下的部署開銷指數(shù)Fig.7 Deployment cost index of different request number

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

圖8 不同請(qǐng)求數(shù)量下的執(zhí)行時(shí)間Fig.8 Processing time of different request number

5 結(jié)論

(1) 文中針對(duì)多實(shí)例VNFC彈性部署問題,對(duì)虛擬網(wǎng)絡(luò)功能內(nèi)部的狀態(tài)和一致性問題進(jìn)行了闡述,并介紹了幾種現(xiàn)有的解決方案和機(jī)制．

(2) 為了達(dá)到最優(yōu)化的部署效果,基于現(xiàn)有的共享狀態(tài)的系統(tǒng)機(jī)制,文中構(gòu)建了一種用于衡量可用性的模型,并針對(duì)高可用的多實(shí)例VNFC部署問題,提出一種基于多實(shí)例擴(kuò)展的優(yōu)化部署算法,通過多個(gè)實(shí)例間的冗余備份及迭代引入VNF,在滿足可用性要求的前提下使帶寬使用最小化．

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