兩段式虛擬網(wǎng)絡(luò)功能硬件加速資源部署機(jī)制

范宏偉，胡宇翔，蘭巨龍

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002)

0 引言

軟件定義網(wǎng)絡(luò)(Software Defined Networking, SDN)將控制和數(shù)據(jù)平面分離，通過開放網(wǎng)絡(luò)控制接口，實(shí)現(xiàn)上層應(yīng)用對網(wǎng)絡(luò)的管控。網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization, NFV)通過虛擬化技術(shù)，將虛擬網(wǎng)絡(luò)功能(Virtual Network Function, VNF)運(yùn)行在虛擬機(jī)(Virtual Machine, VM)或者容器中，按需實(shí)現(xiàn)網(wǎng)絡(luò)功能的動態(tài)靈活部署[1]。相比傳統(tǒng)網(wǎng)絡(luò)，SDN/NFV架構(gòu)符合未來信息產(chǎn)業(yè)的發(fā)展需求，得到了學(xué)術(shù)界和運(yùn)營商的重點(diǎn)發(fā)展和推動。然而，基于軟件實(shí)現(xiàn)的VNF，在數(shù)據(jù)轉(zhuǎn)發(fā)、處理上的性能遠(yuǎn)落后于傳統(tǒng)網(wǎng)絡(luò)硬件設(shè)備，無法滿足線速要求到達(dá)40～100 Gb/s網(wǎng)絡(luò)功能的業(yè)務(wù)需求。VNF的性能瓶頸限制了SDN/NFV架構(gòu)的進(jìn)一步發(fā)展[2-3]。

為此，針對VNF數(shù)據(jù)處理的加速機(jī)制成為學(xué)術(shù)界的研究熱點(diǎn)。當(dāng)前VNF的主要加速機(jī)制是將部分網(wǎng)絡(luò)功能卸載到硬件中，利用硬件的高性能提升VNF的吞吐量和減少時(shí)延。根據(jù)承載VNF的加速硬件種類，可以將現(xiàn)有的研究歸納為兩個(gè)方向。一是利用SDN交換機(jī)的硬件處理能力，以表項(xiàng)形式實(shí)現(xiàn)對VNF數(shù)據(jù)處理的加速。文獻(xiàn)[4]利用OpenFlow交換機(jī)承載無狀態(tài)網(wǎng)絡(luò)功能，實(shí)現(xiàn)了對大量數(shù)據(jù)包的快速處理，提高了網(wǎng)絡(luò)功能的性能。文獻(xiàn)[5]通過在交換機(jī)中引入狀態(tài)表，實(shí)現(xiàn)了SDN交換機(jī)對有狀態(tài)網(wǎng)絡(luò)功能的加速，極大提升了轉(zhuǎn)發(fā)效率。方向二則是利用服務(wù)器端的智能網(wǎng)卡、網(wǎng)絡(luò)處理器(Network Processer, NP)、圖形處理器(Graphics Processing Unit, GPU)[6-7]和現(xiàn)場可編程門陣列(Field-Programmable Gate Array, FPGA)[8-9]等可編程硬件，將相對固化的數(shù)據(jù)處理功能卸載到硬件加速單元中，而軟件完成復(fù)雜多變的邏輯任務(wù)，將兩者結(jié)合從而提升VNF處理性能。文獻(xiàn)[6]利用GPU的大規(guī)模并行處理能力，結(jié)合定制的流處理程序，實(shí)現(xiàn)對網(wǎng)絡(luò)功能加速的有效支持。文獻(xiàn)[9]根據(jù)VNF的加速需求，靈活改變FPGA的邏輯功能，實(shí)現(xiàn)與CPU細(xì)粒度分工合作，提升VNF的吞吐量，降低了處理時(shí)延。

在SDN/NFV架構(gòu)中，網(wǎng)絡(luò)中的業(yè)務(wù)流量要按順序經(jīng)過多個(gè)、不同類型VNF的處理，構(gòu)成“服務(wù)鏈”，服務(wù)鏈中的網(wǎng)絡(luò)功能分布式地運(yùn)行在網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)之中，并受限于各節(jié)點(diǎn)內(nèi)的物理資源[10-11]。從目前對VNF加速機(jī)制的研究來看，僅限于單節(jié)點(diǎn)內(nèi)加速架構(gòu)的設(shè)計(jì)，缺乏對全網(wǎng)硬件加速資源的統(tǒng)一管理和部署研究，難以滿足服務(wù)鏈中位于不同節(jié)點(diǎn)內(nèi)VNF的加速需求。因此，當(dāng)SDN/NFV架構(gòu)引入VNF硬件加速資源后，如何最優(yōu)地部署這些加速資源到各網(wǎng)絡(luò)節(jié)點(diǎn)中，以實(shí)現(xiàn)對服務(wù)鏈的加速處理，是亟待解決的問題。

為了實(shí)現(xiàn)VNF硬件加速資源到全網(wǎng)節(jié)點(diǎn)的最優(yōu)部署，本文將服務(wù)器端的加速卡和轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)的加速表項(xiàng)進(jìn)行統(tǒng)一管理，提出了兩段式加速資源部署模型，在不引入額外開銷的情況下，部署在各節(jié)點(diǎn)中的加速資源最大限度滿足VNF的加速需求。首先，提出了VNF加速資源的統(tǒng)一管理架構(gòu)，以實(shí)現(xiàn)對全網(wǎng)硬件加速資源的統(tǒng)一管控；然后，對VNF加速資源的部署問題進(jìn)行數(shù)學(xué)建模，并分析加速資源對服務(wù)鏈映射的影響，提出了加速資源部署算法的性能指標(biāo)；其次，設(shè)計(jì)了基于拓?fù)鋭莺凸?jié)點(diǎn)協(xié)作的兩段式加速資源部署算法，對問題進(jìn)行求解；最后，對算法進(jìn)行了仿真驗(yàn)證，證明了算法的有效性。

1 VNF硬件加速資源統(tǒng)一管理架構(gòu)

針對當(dāng)前SDN/NFV架構(gòu)中存在的加速資源部署問題，本文提出了VNF硬件加速資源在現(xiàn)有SDN/NFV架構(gòu)中的統(tǒng)一管理架構(gòu)(Uniform Hardware Acceleration Management architecture, UHAM)，總體結(jié)構(gòu)如圖1所示。結(jié)合華為提出的硬件資源統(tǒng)一抽象概念[12],不論是服務(wù)器端的加速卡，還是轉(zhuǎn)發(fā)設(shè)備內(nèi)的加速表項(xiàng)，并沒有引入新的物理資源種類，都屬于NFV標(biāo)準(zhǔn)架構(gòu)基礎(chǔ)設(shè)施(NFV Infrastructure, NFVI)中的計(jì)算資源和網(wǎng)絡(luò)資源。因此，對于VNF硬件加速資源，仍由虛擬化的基礎(chǔ)設(shè)施管理模塊(Virtual Infrastructure Manager, VIM)負(fù)責(zé)管理和分配，在降低管理開銷的同時(shí)，隱藏了引入加速資源的復(fù)雜性。在VIM倉庫清單要包含硬件加速資源的能力和特性信息，并與虛擬資源之間進(jìn)行關(guān)聯(lián)。VNF管理器(VNF Manager, VNFM)負(fù)責(zé)VNF實(shí)例的生命周期管理，通過讀取VNF的描述(VNF Description, VNFD)模板，與VIM模塊進(jìn)行信息交互，將NFVI資源按需求分配給相應(yīng)的VNF。在引入硬件加速資源后，VNFD內(nèi)對于虛擬資源的需求可以根據(jù)通用物理資源、硬件加速資源之間的特性進(jìn)行細(xì)化，上傳多個(gè)相應(yīng)的VNF模板，以支持多種類型的硬件加速資源。

編排器(NFV Orchestrator, NFVO)負(fù)責(zé)NFVI資源的編排和網(wǎng)絡(luò)服務(wù)生命周期的管理。SDN控制器通過標(biāo)準(zhǔn)的南向接口與整個(gè)NFV服務(wù)管理和編排模塊進(jìn)行連接，根據(jù)網(wǎng)絡(luò)拓?fù)浜筒呗砸筮M(jìn)行路由規(guī)劃，控制轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)的轉(zhuǎn)發(fā)表項(xiàng)(Forwarding Table, FT)和加速表項(xiàng)(Acceleration Table, AT)。當(dāng)SDN交換機(jī)承載網(wǎng)絡(luò)功能時(shí)，為避免引起控制器的負(fù)載和表項(xiàng)之間的沖突，在UHAM架構(gòu)中，引入了主從控制器模式來解決該問題。其中，主控制器負(fù)責(zé)管理和下發(fā)流量轉(zhuǎn)發(fā)規(guī)則，而從控制器負(fù)責(zé)管理和下發(fā)VNF加速功能表項(xiàng)，實(shí)現(xiàn)二者的分離。此外，從控制器與VIM模塊進(jìn)行交互，實(shí)現(xiàn)對轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)硬件加速資源的管理，結(jié)合服務(wù)器端加速卡資源信息，從而實(shí)現(xiàn)對全網(wǎng)內(nèi)加速資源的統(tǒng)一管理。

圖1 VNF硬件加速資源統(tǒng)一管理架構(gòu)

2 問題建模

基于UHAM架構(gòu)，本文重點(diǎn)研究在SDN/NFV架構(gòu)中統(tǒng)一管理VNF硬件加速資源后，如何優(yōu)化部署硬件加速資源到網(wǎng)絡(luò)節(jié)點(diǎn)中，在不引入額外開銷的情況下，提升硬件加速資源對VNF的承載效率。首先，定義本文所要解決的硬件加速資源部署問題。

定義1 VNF硬件加速資源的部署問題(VNF hardware acceleration resource deployment problem)。網(wǎng)絡(luò)中節(jié)點(diǎn)資源和鏈路連接都已確定，在用戶服務(wù)鏈請求未知的情況下，運(yùn)營商如何將VNF硬件加速資源，包括轉(zhuǎn)發(fā)設(shè)備端和服務(wù)器端兩類資源，合理地部署到各網(wǎng)絡(luò)節(jié)點(diǎn)中，實(shí)現(xiàn)按一定策略完成服務(wù)鏈的映射后，部署在網(wǎng)絡(luò)節(jié)點(diǎn)內(nèi)的硬件加速資源能最優(yōu)承載有加速需求的網(wǎng)絡(luò)功能，最大化所部署加速資源的使用效率。

2.1 符號描述

1)網(wǎng)絡(luò)拓?fù)?。如圖2所示，網(wǎng)絡(luò)拓?fù)浔硎緸橐粋€(gè)無向帶權(quán)圖G=(S,L)，其中，S和L分別代表轉(zhuǎn)發(fā)節(jié)點(diǎn)集和鏈路集合。鏈路L的資源屬性是帶寬容量B(lu,v)(其中，u,v∈S,lu,v∈L)。用N表示服務(wù)器節(jié)點(diǎn)集合，其物理資源屬性(CPU、內(nèi)存、硬盤等)表示為R；服務(wù)器節(jié)點(diǎn)n與轉(zhuǎn)發(fā)節(jié)點(diǎn)s的連接關(guān)系用η(n,s)∈{0,1}(n∈N,s∈S)表示，若η(n,s)為1，則假定服務(wù)節(jié)點(diǎn)n和轉(zhuǎn)發(fā)節(jié)點(diǎn)s之間相連，且鏈路帶寬為轉(zhuǎn)發(fā)節(jié)點(diǎn)s與相鄰轉(zhuǎn)發(fā)節(jié)點(diǎn)的鏈路帶寬之和，而且假定服務(wù)器節(jié)點(diǎn)最多與一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)相連。

圖2 網(wǎng)絡(luò)拓?fù)涫疽鈭D

3)網(wǎng)絡(luò)功能。服務(wù)鏈根據(jù)資源(計(jì)算、存儲和網(wǎng)絡(luò))需求和VNF間的順序約束將網(wǎng)絡(luò)功能映射到網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)中。F=(f1,f2, …,fp)表示網(wǎng)絡(luò)中存在的網(wǎng)絡(luò)功能實(shí)例集合，網(wǎng)絡(luò)功能fj∈F(j=1,2,…,p)處理的數(shù)據(jù)流量為dj。網(wǎng)絡(luò)功能fj對不同類型加速資源的開銷用CHk(fj)(k=0,1,…,q)表示。γ(fj，Hk)∈{0,1}(j=1,2,…,p,k=0,1,…,q)表示網(wǎng)絡(luò)功能fj與節(jié)點(diǎn)內(nèi)硬件資源Hk之間的承載關(guān)系。

2.2 評價(jià)指標(biāo)

服務(wù)器端存在多種類型的加速資源卡，而且彼此之間承載的網(wǎng)絡(luò)功能類型有一定的重合，存在相似性，為服務(wù)端加速資源的部署問題求解帶來一定的困擾。為簡化模型，本文假設(shè)服務(wù)器端的加速資源卡均為FPGA加速卡，即：

假設(shè)1H=(H0,H1)，其中H1為FPGA加速卡。因?yàn)?，相比FPGA，GPU加速需要對數(shù)據(jù)進(jìn)行格式化處理，耗時(shí)過長，難以滿足對時(shí)延敏感的網(wǎng)絡(luò)功能需求，而且能耗相對較高；而NP的適用領(lǐng)域相對受限，無法同F(xiàn)PGA可以為任何網(wǎng)絡(luò)功能重構(gòu)硬件邏輯。由于FPGA對VNF承載的可擴(kuò)展性最強(qiáng)，能夠加速報(bào)文轉(zhuǎn)發(fā)、加解密和視頻轉(zhuǎn)碼等幾乎所有領(lǐng)域內(nèi)的VNF，可以替代其他類型的加速卡，而且該假設(shè)并未改變該問題的性質(zhì)和求解方法，而僅僅是簡化了問題的復(fù)雜度。

VNF硬件加速資源優(yōu)化部署主要是為了實(shí)現(xiàn)：當(dāng)運(yùn)營商考慮加速資源影響服務(wù)鏈映射策略時(shí)，部署到各節(jié)點(diǎn)的加速資源的類型和數(shù)量，與網(wǎng)絡(luò)中原有的物理資源(計(jì)算、網(wǎng)絡(luò)、存儲)相適應(yīng)，硬件加速資源能夠盡可能承載網(wǎng)絡(luò)功能，同時(shí)不引入額外開銷(傳輸時(shí)延等)和避免加速資源閑置造成的浪費(fèi)。因此，為較好地刻畫加速資源在全網(wǎng)節(jié)點(diǎn)內(nèi)的部署情況，現(xiàn)提出加速資源承載的流量和加速資源的利用率兩個(gè)評價(jià)指標(biāo)來描述加速資源的使用效率，其定義如下。

定義2 加速資源承載的流量。網(wǎng)絡(luò)中被硬件加速資源處理的總的數(shù)據(jù)流量，如下所示：

(1)

定義3 加速資源的利用率：網(wǎng)絡(luò)中處于加載狀態(tài)下的單位加速資源處理的數(shù)據(jù)流量，如下所示：

(2)

其中，r0+r1=1,r是兩類加速資源的權(quán)重調(diào)節(jié)系數(shù)，對兩類加速資源進(jìn)行統(tǒng)一。加速資源承載的DH表示由加速資源處理的流量，當(dāng)網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)部署的加速資源足夠多時(shí)，網(wǎng)絡(luò)中映射固定數(shù)目的服務(wù)鏈時(shí)，DH將為定值，此時(shí)所有VNF的加速需求都能被滿足，但在部署有限加速資源的情況下，DH越大，則證明加速資源部署結(jié)果越合理，能夠滿足服務(wù)鏈的加速需求；而加速資源的利用率QH越大，表示單位加速資源處理的業(yè)務(wù)流量越接近加速后網(wǎng)絡(luò)功能的吞吐量上限，處于高負(fù)載狀態(tài)，實(shí)現(xiàn)了對加速資源的高效利用。

為避免引入額外開銷和加速資源部署位置對服務(wù)鏈映射的影響，在評價(jià)加速資源部署策略時(shí)，服務(wù)鏈的映射策略中應(yīng)不考慮加速資源這一因素，將有加速需求的網(wǎng)絡(luò)功能以“未知狀態(tài)”下映射到網(wǎng)絡(luò)節(jié)點(diǎn)中。完成服務(wù)鏈映射后，根據(jù)流量的傳輸路徑，位于該路徑節(jié)點(diǎn)內(nèi)的加速資源盡可能承載有加速需求的網(wǎng)絡(luò)功能，計(jì)算加速資源承載的流量DH和利用率QH，作為加速資源部署算法的評價(jià)指標(biāo)，判斷部署策略的合理性。

3 兩段式加速資源部署算法

為實(shí)現(xiàn)加速資源的優(yōu)化部署，要根據(jù)兩類加速資源各自的特性，來確定部署的策略和算法。服務(wù)器端FPGA加速卡能承載服務(wù)鏈中復(fù)雜的VNF，具有更高的靈活性，但成本和功耗開銷相對較大；轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)的加速資源，能夠承載無狀態(tài)網(wǎng)絡(luò)功能或者輕量級有狀態(tài)功能，對承載的功能類型限制較大，但網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量較多，而且配置的加速表項(xiàng)容量更大。因此，有加速需求的網(wǎng)絡(luò)功能可以優(yōu)先由轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)的加速資源進(jìn)行承載，當(dāng)超出轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源的承載能力時(shí)，再由服務(wù)節(jié)點(diǎn)的加速卡進(jìn)行承載，來發(fā)揮加速資源的最大效用。

基于以上分析，本文針對全網(wǎng)加速資源部署問題，提出一種兩段式加速資源部署(Two-stage Acceleration Resource Deployment, TARD)算法。TARD算法在分析兩類加速資源不同特點(diǎn)的基礎(chǔ)上，考慮交換設(shè)備的物理屬性和拓?fù)湮恢茫赃m應(yīng)轉(zhuǎn)發(fā)節(jié)點(diǎn)承載的流量為目標(biāo)，利用拓?fù)鋭輀13]思想量化部署的加速資源；增強(qiáng)轉(zhuǎn)發(fā)節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)間加速資源的協(xié)作性，提高加速資源利用率，盡可能多地承載網(wǎng)絡(luò)功能。TARD算法分為兩個(gè)階段，算法流程如圖3所示：第一階段利用基于拓?fù)鋭莸募铀儋Y源部署算法將轉(zhuǎn)發(fā)節(jié)點(diǎn)的加速表項(xiàng)資源部署到相應(yīng)轉(zhuǎn)發(fā)節(jié)點(diǎn)；第二階段結(jié)合轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源的部署情況，利用節(jié)點(diǎn)協(xié)作思想將服務(wù)端加速卡配置到服務(wù)節(jié)點(diǎn)內(nèi)，完成VNF硬件加速資源的部署。

圖3 TARD算法流程

3.1 基于拓?fù)鋭莸募铀儋Y源部署算法

在引入硬件加速資源前，轉(zhuǎn)發(fā)節(jié)點(diǎn)負(fù)責(zé)服務(wù)鏈內(nèi)網(wǎng)絡(luò)功能的連接，引導(dǎo)流量轉(zhuǎn)發(fā)到正確的服務(wù)節(jié)點(diǎn)中。因此，傳統(tǒng)的服務(wù)鏈部署策略中對轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇，主要考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)自身的固有屬性(位置、帶寬、度數(shù)等)。為不引入額外的開銷，提高硬件加速資源的利用率，轉(zhuǎn)發(fā)節(jié)點(diǎn)是否所部署加速資源以及具體的數(shù)量，要與轉(zhuǎn)發(fā)節(jié)點(diǎn)在服務(wù)鏈映射中所承載的流量相適應(yīng)。本節(jié)通過分析轉(zhuǎn)發(fā)節(jié)點(diǎn)影響服務(wù)鏈映射時(shí)的屬性內(nèi)容，并引入拓?fù)鋭莘椒?，分析轉(zhuǎn)發(fā)節(jié)點(diǎn)間的相互作用，通過轉(zhuǎn)發(fā)節(jié)點(diǎn)的改進(jìn)拓?fù)鋭輥砹炕铀儋Y源的部署數(shù)量。

在數(shù)據(jù)場理論中，物理系統(tǒng)被視為包含s個(gè)節(jié)點(diǎn)并相互作用的網(wǎng)絡(luò)。該系統(tǒng)中每個(gè)節(jié)點(diǎn)的周圍都存在一個(gè)空間上的虛擬場，該場會作用于場內(nèi)的任何節(jié)點(diǎn)。網(wǎng)絡(luò)中任何一個(gè)節(jié)點(diǎn)都將與其他節(jié)點(diǎn)相互作用，形成整個(gè)拓?fù)渖系囊粋€(gè)場，定義為拓?fù)鋭輬?。根?jù)數(shù)據(jù)場中勢函數(shù)定義，場中任意節(jié)點(diǎn)si的拓?fù)鋭菘梢杂筛咚购瘮?shù)表示為：

(3)

其中:mj為節(jié)點(diǎn)的質(zhì)量，di, j為節(jié)點(diǎn)間距離，σ為影響因子，表示節(jié)點(diǎn)的影響力，用于控制節(jié)點(diǎn)拓?fù)鋭輬鲎饔梅秶?/p>

根據(jù)以上數(shù)據(jù)場理論，將拓?fù)鋭莘椒☉?yīng)用于由轉(zhuǎn)發(fā)節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)渲?，用來描繪轉(zhuǎn)發(fā)節(jié)點(diǎn)在服務(wù)鏈部署時(shí)的影響力，從而確定加速資源部署數(shù)量。由于在服務(wù)鏈部署中對于轉(zhuǎn)發(fā)節(jié)點(diǎn)屬性的選擇具有多樣性和特殊性，對拓?fù)鋭莘椒ㄟM(jìn)行了改進(jìn)，將轉(zhuǎn)發(fā)節(jié)點(diǎn)的拓?fù)鋭荻x如下：

(4)

其中:mj1和mj2分別表示轉(zhuǎn)發(fā)節(jié)點(diǎn)的度數(shù)和該節(jié)點(diǎn)到相鄰轉(zhuǎn)發(fā)節(jié)點(diǎn)的帶寬和，M1和M2表示各自屬性的權(quán)重，其值由熵權(quán)法確定，統(tǒng)一兩個(gè)屬性的數(shù)量級；di, j表示節(jié)點(diǎn)si和sj之間最短距離的跳數(shù)；be(j)表示轉(zhuǎn)發(fā)節(jié)點(diǎn)的介數(shù)中心度，衡量節(jié)點(diǎn)的作用范圍。度數(shù)和帶寬和是轉(zhuǎn)發(fā)節(jié)點(diǎn)承載服務(wù)鏈能力的約束表示；介數(shù)中心度表示網(wǎng)絡(luò)中經(jīng)過該節(jié)點(diǎn)的所有點(diǎn)與點(diǎn)之間的最短路徑數(shù)目。在服務(wù)鏈映射過程中，不同網(wǎng)絡(luò)功能之間的流量大都選擇節(jié)點(diǎn)間的最短路徑進(jìn)行轉(zhuǎn)發(fā)，因此介數(shù)中心度反映了服務(wù)鏈映射中對轉(zhuǎn)發(fā)節(jié)點(diǎn)的偏好。

轉(zhuǎn)發(fā)節(jié)點(diǎn)的加速資源部署數(shù)量與拓?fù)鋭葜g的關(guān)系可以表示為：

(5)

算法1 基于拓?fù)鋭莸霓D(zhuǎn)發(fā)節(jié)點(diǎn)加速資源部署算法。

輸入：轉(zhuǎn)發(fā)節(jié)點(diǎn)所組網(wǎng)絡(luò)的鄰接矩陣，其中，兩個(gè)節(jié)點(diǎn)相連為1，不相連為∞；

步驟1 確定網(wǎng)絡(luò)中各轉(zhuǎn)發(fā)節(jié)點(diǎn)的兩個(gè)固有屬性：轉(zhuǎn)發(fā)節(jié)點(diǎn)的度數(shù)m1和帶寬總和m2；

步驟2 用Floyd算法求節(jié)點(diǎn)的路徑矩陣和距離矩陣，算出各節(jié)點(diǎn)間的距離和節(jié)點(diǎn)的介數(shù)；

步驟3 根據(jù)熵權(quán)法計(jì)算權(quán)重M1和M2，得到各節(jié)點(diǎn)的質(zhì)量m=M1×m1+M2×m2；

步驟4 根據(jù)式(4)、(5)計(jì)算各節(jié)點(diǎn)的拓?fù)鋭莺图铀儋Y源部署數(shù)量；

3.2 基于節(jié)點(diǎn)協(xié)作的加速資源部署算法

對于服務(wù)器端加速資源的部署，當(dāng)服務(wù)節(jié)點(diǎn)內(nèi)加速資源恰好滿足節(jié)點(diǎn)內(nèi)工作時(shí)的VNF加速需求，表明加速資源部署數(shù)量的合理性。在NFV環(huán)境下，服務(wù)節(jié)點(diǎn)間相互同構(gòu)，在用戶請求到達(dá)和服務(wù)鏈映射完成的情況下，每個(gè)服務(wù)節(jié)點(diǎn)內(nèi)運(yùn)行的VNF類型和數(shù)量可以認(rèn)為是均勻分布，即服務(wù)節(jié)點(diǎn)內(nèi)VNF對加速資源的需求開銷與節(jié)點(diǎn)內(nèi)運(yùn)行的VNF總量成比例的，而服務(wù)節(jié)點(diǎn)本身的物理資源R(CPU、內(nèi)存、硬盤)限制了節(jié)點(diǎn)內(nèi)部署網(wǎng)絡(luò)功能的最大數(shù)量，也就反映了節(jié)點(diǎn)內(nèi)VNF對加速資源的需求數(shù)量。因此，服務(wù)節(jié)點(diǎn)內(nèi)加速資源的部署數(shù)量與節(jié)點(diǎn)內(nèi)物理資源R直接相關(guān)。

在SDN/NFV架構(gòu)中，服務(wù)器端加速資源與轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源共同協(xié)作完成對服務(wù)鏈的加速。因此除了節(jié)點(diǎn)內(nèi)物理資源R對服務(wù)器端加速資源部署的影響，還要考慮兩類加速資源間協(xié)作關(guān)系，保證加速資源整體部署的合理性。根據(jù)上述對兩種加速資源對網(wǎng)絡(luò)功能承載的設(shè)定，服務(wù)節(jié)點(diǎn)內(nèi)有加速需求的VNF，優(yōu)先由服務(wù)鏈流量傳輸路徑中，與服務(wù)節(jié)點(diǎn)相鄰近的轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)的加速資源承載。換句話說，服務(wù)節(jié)點(diǎn)與部署有加速資源的交換節(jié)點(diǎn)越近，節(jié)點(diǎn)內(nèi)有加速需求的網(wǎng)絡(luò)功能被轉(zhuǎn)發(fā)節(jié)點(diǎn)承載的可能性越大，相應(yīng)地，可以據(jù)此減少服務(wù)節(jié)點(diǎn)內(nèi)部署的加速資源數(shù)量。所以，服務(wù)節(jié)點(diǎn)內(nèi)加速資源的部署數(shù)量還與部署有加速資源的轉(zhuǎn)發(fā)節(jié)點(diǎn)距離有關(guān)。

綜合以上兩點(diǎn)分析，服務(wù)節(jié)點(diǎn)內(nèi)加速資源與流量轉(zhuǎn)發(fā)路徑中轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)加速資源共同協(xié)作，完成對服務(wù)鏈的加速處理，對服務(wù)節(jié)點(diǎn)內(nèi)加速資源部署數(shù)量可以定義如下：

(6)

dsj(ni)=|ni-sj|B

(7)

算法2 基于節(jié)點(diǎn)協(xié)作的服務(wù)節(jié)點(diǎn)加速資源部署算法。

輸入：各服務(wù)節(jié)點(diǎn)內(nèi)配置的物理資源R，以及轉(zhuǎn)發(fā)節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)所組網(wǎng)絡(luò)的鄰接矩陣。其中，兩個(gè)節(jié)點(diǎn)相連為鏈路帶寬值，不相連為0；

步驟1 根據(jù)算法1，確定網(wǎng)絡(luò)中各轉(zhuǎn)發(fā)節(jié)點(diǎn)內(nèi)加速資源部署數(shù)量；

步驟2 用Floyd算法求各服務(wù)節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)間的最短距離；

步驟3 根據(jù)式(6)、(7)計(jì)算各服務(wù)節(jié)點(diǎn)的加速資源部署數(shù)量；

在TARD算法的階段1和2，都需要Floyd算法求解節(jié)點(diǎn)間的最短路徑，需要O(n3)的時(shí)間，若網(wǎng)絡(luò)為疏松圖，則時(shí)間復(fù)雜度可降為O(n2logn+nm)[14]，其中n和m分別代表網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)與鏈路數(shù)目。

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

為了評估TARD部署算法的有效性，首先TARD算法完成加速資源到各節(jié)點(diǎn)內(nèi)的部署，然后利用基于貪婪算法(Greedy)和禁忌搜素(Tabu Search)的服務(wù)鏈映射算法[15]完成網(wǎng)絡(luò)功能的映射，部署到各節(jié)點(diǎn)內(nèi)的加速資源盡可能承載網(wǎng)絡(luò)功能，計(jì)算加速資源承載的流量和利用率，作為評價(jià)指標(biāo)。因?yàn)槟壳皼]有其他的加速資源部署算法，本章只能與考慮節(jié)點(diǎn)單一屬性的加速資源部署算法(Single-attribute Acceleration Resource Deployment algorithm, SARD)和均勻分配的加速資源部署算法(Uniform Acceleration Resource Deployment algorithm, UARD)進(jìn)行比較。其中：考慮節(jié)點(diǎn)單一屬性的部署算法(SARD)是指，對轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源只考慮度數(shù)、帶寬或者介數(shù)中心度，而服務(wù)節(jié)點(diǎn)加速資源只考慮物理資源R；均勻部署算法(UARD)是指將全部的轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源和服務(wù)節(jié)點(diǎn)加速資源平均分配到兩類節(jié)點(diǎn)內(nèi)。

4.1 實(shí)驗(yàn)環(huán)境

采用如圖4所示的網(wǎng)絡(luò)拓?fù)鋄16]，網(wǎng)絡(luò)中有13個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)、6個(gè)服務(wù)節(jié)點(diǎn)，轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的鏈路帶寬和服務(wù)節(jié)點(diǎn)內(nèi)的物理資源，根據(jù)表1的參數(shù)設(shè)置隨機(jī)生成。仿真平臺采用Matlab R2015a搭建，計(jì)算機(jī)處理器為Intel Core i5-3450、3.10 GHz，8 GB RAM。

圖4 仿真網(wǎng)絡(luò)拓?fù)?/p>

參數(shù)最小值最大值服務(wù)節(jié)點(diǎn)資源R6001000鏈路帶寬B/(Mb·s-1)300500

設(shè)網(wǎng)絡(luò)有10種功能，其中4種功能需要加速，即γ=1，而有3種功能可以被兩類加速資源承載，1種功能只能被服務(wù)器端加速卡承載。各類功能傳統(tǒng)的物理開銷和加速開銷以及加速后的吞吐量，根據(jù)表2的參數(shù)設(shè)置隨機(jī)生成。每條服務(wù)鏈由10類功能中多個(gè)VNF組成，數(shù)量服從3～5的均勻分布，而服務(wù)鏈的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，隨機(jī)從13個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)中選取。每條服務(wù)鏈的數(shù)據(jù)流量服從[3,5] Mb/s的隨機(jī)分布。根據(jù)網(wǎng)絡(luò)功能對兩類加速資源的開銷，設(shè)定轉(zhuǎn)發(fā)節(jié)點(diǎn)加速資源可部署的總量為800，部署加速資源節(jié)點(diǎn)拓?fù)鋭莸淖畹烷T限Qmin設(shè)定為0，服務(wù)節(jié)點(diǎn)加速資源可部署的總量為135。設(shè)定算法性能指標(biāo)的參數(shù)，r0為0.75，r1為0.25。仿真平臺用Matlab R2015a搭建，在PC機(jī)上(Intel Core CPU i5-3450 3.10 GHz，8 GB RAM)運(yùn)行。

當(dāng)?shù)讓泳W(wǎng)絡(luò)的資源確定后，分別利用Greedy和TS算法將不同服務(wù)鏈數(shù)目成功映射到網(wǎng)絡(luò)中，要求每條服務(wù)鏈中的網(wǎng)絡(luò)功能映射到不同的服務(wù)節(jié)點(diǎn)內(nèi)。其中，Greedy算法根據(jù)策略的不同可以分為GFP(Greedy Fast Processing)算法和GLL(Greedy Least Loaded)算法?；谪澙匪惴ǖ腉FP算法是指，在鏈路帶寬約束下，對每條服務(wù)鏈，依次搜索確定有足夠的剩余資源能夠承載網(wǎng)絡(luò)功能的服務(wù)器節(jié)點(diǎn)，當(dāng)有多個(gè)服務(wù)節(jié)點(diǎn)均滿足要求時(shí)，選取相距較近的服務(wù)節(jié)點(diǎn)進(jìn)行承載，此時(shí)，從源節(jié)點(diǎn)到最后一個(gè)所選服務(wù)器的路徑也隨之確定；然后，計(jì)算出一條從最后一個(gè)所選服務(wù)節(jié)點(diǎn)到目的節(jié)點(diǎn)的(最短)路徑，依次完成每條服務(wù)鏈的部署；基于貪婪算法的GLL算法與GFP思想類似，從選取距離最近的服務(wù)節(jié)點(diǎn)，換為選取剩余資源最大的服務(wù)節(jié)點(diǎn)；TS算法設(shè)定服務(wù)節(jié)點(diǎn)負(fù)載均衡為全局優(yōu)化目標(biāo)，通過多次搜索完成不同數(shù)目服務(wù)鏈到網(wǎng)絡(luò)中的映射。每種服務(wù)鏈數(shù)目重復(fù)仿真50次，得到不同服務(wù)鏈映射算法下，TARD算法和要比較的加速資源部署算法的平均性能指標(biāo)。

表2 VNF參數(shù)

4.2 性能分析

圖5分別表示利用GFP、GLL和TS算法映射不同數(shù)目服務(wù)鏈情況下，不同部署算法下的加速資源承載流量。從圖中可以看出，隨著服務(wù)鏈數(shù)目的增大，加速資源承載的流量不斷增大，但不同算法的流量的數(shù)值和增長幅度不同。在三種的服務(wù)鏈映射算法和不同服務(wù)鏈數(shù)目下，TARD算法的加速資源承載的流量最大，相比其他部署算法承載流量的平均值，能夠提升38.4%、41.4%和30.4%。隨著服務(wù)鏈數(shù)目的進(jìn)一步增大，尤其是在TS映射算法下，加速資源承載的總流量增長速度開始放緩，已經(jīng)接近所部署加速資源承載的流量上限。均勻部署算法沒有考慮節(jié)點(diǎn)間彼此的差異性，部署的加速資源與節(jié)點(diǎn)本身的屬性不相適應(yīng)，性能指標(biāo)最差。只考慮節(jié)點(diǎn)單一屬性主要考慮節(jié)點(diǎn)本身的屬性，沒有考慮服務(wù)鏈部署時(shí)的路徑選取，以及兩類加速資源間相互影響。隨著服務(wù)鏈數(shù)目的增加，加速資源承載的總流量較低，是因?yàn)椴糠旨铀儋Y源部署不合理造成的。TARD算法的部署方法綜合考慮節(jié)點(diǎn)資源對服務(wù)鏈部署時(shí)的影響和兩類加速資源間的相互作用，增加了加速資源部署的合理性。因此，TARD算法的加速資源配置策略更加合理，能夠負(fù)載更多的業(yè)務(wù)流量。

圖6分別表示GFP、GLL和TS算法部署不同數(shù)目服務(wù)鏈情況下，不同部署算法的加速資源利用率。從圖中可以看出，隨著服務(wù)鏈數(shù)目的增大，加速資源的使用效率不斷增大，但不同算法的加速資源使用效率的上升速度和幅度不同。在相同條件下，相比其他算法利用率的平均值，TARD算法的加速資源使用率最高，提升了10.9%、8.3%和14.5%。由于TARD算法部署的加速資源與節(jié)點(diǎn)的傳統(tǒng)物理資源相適應(yīng)，在較少的服務(wù)鏈數(shù)目時(shí)，就已經(jīng)實(shí)現(xiàn)對使用狀態(tài)下加速資源的復(fù)用，使得加速資源利用率達(dá)到較高的標(biāo)準(zhǔn)；隨著服務(wù)鏈數(shù)目的增加，加速資源的利用率進(jìn)一步提高，接近滿載狀態(tài)，因此上升速度和幅度相對有限。

圖5 加速資源承載的流量對比

圖6 加速資源的利用率對比

圖7表示不同服務(wù)鏈映射算法下的TARD性能指標(biāo)。從圖中可以看出，相較于GFP算法和GLL算法，不論是加速資源承載的流量，還是加速資源的利用率，使用TS算法映射服務(wù)鏈時(shí)，TARD算法的性能指標(biāo)達(dá)到最高。TS算法通過反復(fù)迭代計(jì)算得到的服務(wù)鏈映射方案更優(yōu)，節(jié)點(diǎn)的物理資源與部署的網(wǎng)絡(luò)功能更加契合，同樣，節(jié)點(diǎn)內(nèi)部署的加速資源與網(wǎng)絡(luò)功能的加速需求更加匹配。因此，在相同的條件下，當(dāng)服務(wù)鏈映射算法更優(yōu)時(shí)，TARD算法的性能指標(biāo)能進(jìn)一步提高。

5 結(jié)語

VNF加速資源能夠提升網(wǎng)絡(luò)功能的數(shù)據(jù)處理速率，從而滿足高速率轉(zhuǎn)發(fā)的業(yè)務(wù)需求，推動了SDN和NFV的進(jìn)一步發(fā)展。本文在所提VNF加速資源統(tǒng)一管理平臺的基礎(chǔ)上，研究了全網(wǎng)范圍內(nèi)如何將VNF加速資源合理部署到各轉(zhuǎn)發(fā)節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)問題。首先，通過分析VNF加速資源對服務(wù)鏈部署的影響，構(gòu)建了VNF加速資源部署模型，提出了加速資源部署算法的性能評價(jià)指標(biāo)；然后，針對該問題提出了兩段式加速資源部署算法，對轉(zhuǎn)發(fā)節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)內(nèi)的加速資源部署問題進(jìn)行了求解，并對算法進(jìn)行了性能仿真。仿真實(shí)驗(yàn)證明，所提算法能夠保證加速資源承載更多的業(yè)務(wù)流量，同時(shí)提高加速資源的利用率。在SDN/NFV架構(gòu)中完成硬件加速資源的部署后，如何高效編排加速資源從而實(shí)現(xiàn)服務(wù)鏈的最優(yōu)承載，目前缺乏相關(guān)研究，設(shè)計(jì)加速資源編排機(jī)制將是下一步的研究方向和目標(biāo)。

[7] YI X, DUAN J, WU C. GPUNFV: a GPU-accelerated NFV system [C]// APNet ’17: Proceedings of the 1st Asia-Pacific Workshop on Networking. New York: ACM, 2017: 85-91.

[8] GE X, LIU Y, DU D H C, et al. OpenANFV: accelerating network function virtualization with a consolidated framework in openstack [C]// SIGCOMM ’14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM, 2014: 353-354.

[9] LI B, TAN K, LUO L, et al. ClickNP: highly flexible and high performance network processing with reconfigurable hardware [C]// SIGCOMM ’16: Proceedings of the 2016 ACM SIGCOMM Conference. New York: ACM, 2016: 1-14.

[10] DWARAKI A, WOLF T. Adaptive service-chain routing for virtual network functions in software-defined networks [C]// HotMiddlebox ’16: Proceedings of the 2016 Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2016: 32-37.

[11] 劉彩霞,盧干強(qiáng),湯紅波,等.一種基于Viterbi算法的虛擬網(wǎng)絡(luò)功能自適應(yīng)部署方法[J].電子與信息學(xué)報(bào),2016,38(11):2922-2930.(LIU C X, LU G Q, TANG H B, et al. Adaptive deployment method for virtualized network function based on viterbi algorithm [J]. Journal of Electronics and Information Technology, 2016, 38(11): 2922-2930.)

[12] BRONSTEIN Z, ROCH E, XIA J, et al. Uniform handling and abstraction of NFV hardware accelerators [J]. IEEE Network, 2015, 29(3): 22-29.

[13] 李德毅,劉常昱,杜鹢,等.不確定性人工智能[J].軟件學(xué)報(bào),2004,15(11):1583-1594.(LI D Y, LIU C Y, DU Y, et al. Artificial intelligence with uncertainty [J]. Journal of Software, 2004, 15(11): 1583-1594.)

[14] CORMEN T T, LEISERSON C E, RIVEST R L. Introduction to algorithms [J]. Resonance, 2009, 1(9): 14-24.

[15] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions [C]// NetSoft ’15: Proceedings of the 2015 1st IEEE Conference on Network Softwarization. Piscataway, NJ: IEEE, 2015: 1-9.

[16] FENG H, LLORCA J, TULINO A M, et al. Approximation algorithms for the NFV service distribution problem [C]// IEEE INFOCOM ’17: Proceedings of the 2017 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2017:1-9.