面向SDN/NFV架構的VNF硬件加速資源編排機制

段通，蘭巨龍，胡宇翔，范宏偉

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

1 引言

當前，互聯(lián)網(wǎng)體系正在醞釀著巨大變革，以軟件定義網(wǎng)絡（SDN, software defined networking）和網(wǎng)絡功能虛擬化（NFV, network function virtualization）技術為典型代表的新型網(wǎng)絡體系隨之涌現(xiàn)。SDN將網(wǎng)絡控制與轉發(fā)邏輯解耦合，通過網(wǎng)絡控制接口的開放，支持上層應用對網(wǎng)絡的管控；NFV將傳統(tǒng)網(wǎng)絡硬件設備的功能軟件化，轉移到數(shù)據(jù)中心的通用服務器中，從而實現(xiàn)網(wǎng)絡功能的靈活部署和快速升級。由于SDN和NFV技術能夠顯著提升網(wǎng)絡資源利用率、降低網(wǎng)絡運維成本、加快網(wǎng)絡業(yè)務部署，其引起了產(chǎn)業(yè)界和學術界的重點關注。然而，在SDN/NFV架構中，虛擬網(wǎng)絡功能（VNF, virtual network function）一般部署在服務器上的虛擬機（VM, virtual machine）或容器（docker）中，由于虛擬I/O接口速率和軟件處理速率的限制，其在轉發(fā)性能上遠遠落后于傳統(tǒng)的專用功能硬件設備。在處理網(wǎng)絡流量較大、時延敏感的業(yè)務時，VNF相對低下的轉發(fā)處理能力使 NFV往往難以提供相應的服務保障。

因此，針對 VNF的硬件加速機制成為研究熱點[1-2]。當前，針對 NFV加速處理的研究可歸納為2個方面：1) 在服務器端對VNF進行加速，多通過FPGA加速卡[3-4]等實現(xiàn)；2) 借助轉發(fā)節(jié)點（通常為OpenFlow交換機）的硬件處理能力，將VNF的一部分處理邏輯以表項形式加載到交換機上，實現(xiàn)對VNF的硬件處理加速[5-6]。然而，網(wǎng)絡業(yè)務往往需要對數(shù)據(jù)流進行多重功能處理，即“服務功能鏈”（SFC, service function chain）；針對不同的網(wǎng)絡業(yè)務需求，需要通過合適的功能部署和編排，實現(xiàn)對數(shù)據(jù)流相應功能的處理。因此，在網(wǎng)絡中加入硬件加速資源后，如何統(tǒng)一地管控這些加速資源使網(wǎng)絡在業(yè)務請求下最優(yōu)地部署、編排這些硬件加速資源，以實現(xiàn)對服務功能鏈的加速處理，是亟待解決的問題。

在現(xiàn)有研究方面，網(wǎng)絡功能的部署和編排問題一直是NFV的研究熱點。Chi等[7]針對VNF在數(shù)據(jù)中心內(nèi)部的3-tire樹形結構，設計了VNF部署和流量調(diào)度算法。隨后，Xia等[8]和湯紅波等[9]分別將該問題擴展到多數(shù)據(jù)中心網(wǎng)絡和移動核心網(wǎng)中，研究了 VNF的部署和流量調(diào)度問題。Cohen等[10]將VNF部署問題統(tǒng)一建模為線性約束下的最優(yōu)化問題，并針對該問題進行了詳細的數(shù)學算法分析。在VNF部署之后，需要針對不同的業(yè)務需求進行功能實例選取和路徑計算。段通等[11]就功能實例選取及組合問題進行了理論建模，旨在實現(xiàn)網(wǎng)絡效用函數(shù)的最大化。Gushchin等[12]研究了硬件功能部署后的流量傳輸算法。隨后，Dwaraki等[13]將算法擴展至虛擬功能的路由。Bari等[14]和劉彩霞等[15]對 NFV功能部署和編排問題進行了統(tǒng)一建模，并借鑒維特比算法思想，將路徑開銷與部署開銷統(tǒng)一到維特比狀態(tài)轉移表的狀態(tài)轉移權值中，從而同時求解出功能部署位置以及流量傳輸路徑。Li等[16]將功能部署、實例選取、路由3個部分統(tǒng)一成NFV編排問題進行了建模并提出了啟發(fā)式算法，從整體上對 NFV功能部署和編排問題進行了建模求解。Ma等[17]對該問題進行了更深一步的研究，加入了對流量經(jīng)過 VNF后速率變化情況的考慮以及功能鏈無序或部分有序情況的考慮，并設計了相應的啟發(fā)式算法求解。然而，由于網(wǎng)絡加速資源的形態(tài)與通用的NFV服務器和OpenFlow交換機均有一定差異，其部署和編排方法也與基于虛擬機的 VNF編排方法有所不同，但以上研究中的網(wǎng)絡功能部署和編排算法均未考慮網(wǎng)絡加速資源的部署和編排。就目前研究來看，只有華為在架構層面上提及了加速資源的部署編排問題[18]，但未給出具體的模型及算法實現(xiàn)。

基于以上分析可知，針對網(wǎng)絡硬件加速資源的編排管理機制仍需進一步研究。因此，本文將服務器加速板卡和OpenFlow交換機統(tǒng)一為硬件加速資源，研究了針對硬件加速的資源管控和編排機制，從而使網(wǎng)絡在上層業(yè)務的需求下，能夠以最優(yōu)的方式調(diào)度、編排資源，以實現(xiàn)對服務功能鏈的最優(yōu)承載。具體地，本文的創(chuàng)新點包括以下3個方面。

1) 在架構層面，通過分析當前硬件加速資源管控方法所存在的結構性矛盾，提出了網(wǎng)絡轉發(fā)和VNF處理分離的硬件加速資源管控架構，實現(xiàn)了對硬件加速資源的一致管控。

2) 在建模層面，將傳統(tǒng)網(wǎng)絡資源與硬件加速資源統(tǒng)一到同一網(wǎng)絡功能部署和編排問題模型中，通過理論分析確定該問題為NP-難問題，并設計了相應的啟發(fā)式算法進行求解。

3) 在實現(xiàn)層面，提出了可行性方案，即針對目前 OpenFlow交換機設計不支持分離式管控的問題，利用OpenFlow 1.3協(xié)議中的多控制器技術來實現(xiàn)對硬件加速資源的單獨管控。

2 加速資源統(tǒng)一管控架構

SDN和 NFV分別打破了原本封閉僵化的網(wǎng)絡設備和功能設備，使整個網(wǎng)絡體系朝著開放虛擬化的方向發(fā)展。從架構上看，SDN和 NFV分別作用于網(wǎng)絡的不同部分且略有交叉，在實用上存在互補關系，使兩者的結合變得順理成章。2014年，全球開放網(wǎng)絡基金會提出了基于 OpenFlow的SDN/NFV架構，旨在結合NFV在功能部署和SDN在流量調(diào)度方面的優(yōu)勢，構建靈活開放的新型網(wǎng)絡體系架構。然而，現(xiàn)有 SDN/NFV架構并未考慮在嵌入硬件加速資源（如 FPGA、SmartNIC、OpenFlow交換機等）之后如何管理使用這些加速資源。

華為提出了硬件資源統(tǒng)一化編排管理平臺[18]，將網(wǎng)絡中的所有硬件設備進行統(tǒng)一編排控制，包括硬件網(wǎng)絡設備、FPGA加速卡、網(wǎng)卡、GPU、多核板卡等。在這種架構下，NFV基礎設施由OpenFlow交換機和通用服務器擴展到幾乎所有現(xiàn)有的網(wǎng)絡硬件設備和專用加速卡，為SDN/NFV數(shù)據(jù)平面描繪了宏偉藍圖，但其并未給出具體的實現(xiàn)細節(jié)。另外一種通用的思想是利用 SDN控制器來控制硬件加速資源，文獻[5]提出了基于SDN的NFV功能加載機制，將VNF的部分功能加載到OpenFlow交換機中，并采用 SDN控制器對這部分功能邏輯進行管理。但OpenFlow交換機的硬件處理是無狀態(tài)的，狀態(tài)管理依然運行于上層 VNF中。因此，清華大學畢軍教授團隊[6]提出了帶狀態(tài)處理的加速架構設計，通過在交換機的硬件中加入狀態(tài)表，使上層VNF的功能幾乎可以全部加載到交換機中，從而減少硬件上傳數(shù)據(jù)分組的頻次。然而，這種 SDN擔負部分VNF處理的架構會帶來2個方面的問題：首先，為管理OpenFlow交換機內(nèi)的功能表項，VNF往往運行在 SDN控制器之上，這會使原本就負責網(wǎng)絡狀態(tài)管理的控制器的負載進一步加大，造成控制器過載；其次，由于VNF功能表項與SDN轉發(fā)表項同時混雜在交換機的流表里，極易導致交換機內(nèi)的流表表項沖突。經(jīng)以上分析可知，現(xiàn)有研究為實現(xiàn)對硬件加速資源的管控，將本應屬于 VNF所控制的硬件加速資源劃歸到專門負責網(wǎng)絡轉發(fā)的SDN控制器下，由此產(chǎn)生的結構性矛盾必然會導致網(wǎng)絡轉發(fā)和VNF處理的管控混疊以及SDN控制器的任務過載。

基于此，本文提出了基于 VNF與轉發(fā)分離控制的硬件加速資源管理架構（MSC, management based on separated control），如圖1所示。在傳統(tǒng)SDN/NFV架構下，虛擬資源管理器（VIM, virtual infrastructure manager）負責虛擬資源的控制，包括對網(wǎng)絡資源的管理（NC, network controller）以及對計算、存儲資源的管理（CSC, compute & storage control），在上層用戶需求的驅動下，為網(wǎng)絡服務分配相應的資源。VNF管理器（VNFM, VNF manager）負責VNF的管理平面，負責對VNF的功能進行描述、注冊、實例化以及生存時間的管理。編排器（NFVO, NFV orchestrator）則在用戶服務需求下對網(wǎng)絡功能進行編排，包括計算網(wǎng)絡功能的部署位置以及網(wǎng)絡流量的轉發(fā)路徑等。

MSC在基于傳統(tǒng)SDN/NFV架構的基礎上進行了改進：1)在 VIM 中添加了硬件加速資源管理器（HAM, hardware accelerator manager），作為所有硬件加速資源的管理器，包括轉發(fā)元件中的硬件加速資源和VNF服務器中的硬件加速卡資源；2)為實現(xiàn)HAM 對硬件加速表的管理，底層轉發(fā)元件的架構也應做出相應調(diào)整，即OpenFlow交換機的流表分成了2個部分，即為硬件加速表和轉發(fā)表，2個類型的流表分別承載VNF下發(fā)的處理規(guī)則和SDN控制器下發(fā)的流量轉發(fā)規(guī)則，并分別被HAM 和NC所控制；3) VNFM 對 VNF的描述（VNFD, VNF description）文件中加入了對VNF硬件加速需求的描述，包括對硬件加速資源類型（如L3層或L7層處理等）、容量（如能承載的規(guī)則數(shù)量等）、處理流程的描述，通過Vi-Vnfm接口向VIM通告，然后HAM即可根據(jù)VNFD以及VNF實例化需求來為其分配相應的硬件加速資源進行承載。通過以上3種改進，網(wǎng)絡轉發(fā)控制和 VNF加速資源管控實現(xiàn)了分離，這種混疊的消除使網(wǎng)絡可以對各種類型的硬件加速資源進行統(tǒng)一管控，從而能在較大程度上緩解 SDN控制器負載的同時，充分利用網(wǎng)絡中的加速資源，提升網(wǎng)絡功能處理的加速效果。

圖1 基于VNF與轉發(fā)分離控制的硬件加速資源管理架構

3 問題建模

MSC硬件加速資源統(tǒng)一管控架構可以使網(wǎng)絡根據(jù) VNF的加速需求，選取相應的硬件加速資源對其進行承載?；诖?，本文重點研究在網(wǎng)絡中部署硬件加速資源后，如何對硬件加速資源進行編排以實現(xiàn)對SFC的處理加速。首先，定義本文所要解決的功能部署和硬件加速資源編排問題。

定義 1 支持硬件加速的功能部署和編排問題（VDOP-HA, VNF deployment and orchestration problem enabling hardware acceleration）。網(wǎng)絡中已經(jīng)部署了交換機、服務器以及硬件加速資源，在用戶的服務功能鏈請求下，首先，最優(yōu)地部署VNF，并將有硬件加速需求的 VNF處理邏輯映射至相應的硬件加速資源中進行承載；然后，選擇一條從源節(jié)點到目的節(jié)點的最優(yōu)轉發(fā)路徑，使流量順序流經(jīng)服務鏈的各個 VNF或承載其處理邏輯的硬件加速資源，實現(xiàn)對服務功能鏈的最優(yōu)承載。

3.1 符號描述

1) 網(wǎng)絡拓撲

VDOP-HA網(wǎng)絡拓撲模型示意如圖2所示，網(wǎng)絡中包含轉發(fā)節(jié)點和 VNF服務器節(jié)點，其中，轉發(fā)節(jié)點采用MSC架構中的交換機結構，VNF服務器節(jié)點則是可承載多個 VNF運行的商用服務器。硬件加速資源包括分布于轉發(fā)節(jié)點中的硬件加速表和插在 VNF服務器中的硬件加速卡。網(wǎng)絡拓撲記為無向圖G(V,E)，其中，V是轉發(fā)節(jié)點集，E是鏈路集；鏈路代價權值為 w(eij)，鏈路帶寬容量為B(eij)，其中，eij∈E，i, j∈V；網(wǎng)絡服務器節(jié)點集為S，其中，服務器s的計算存儲資源容量表示為Cs；網(wǎng)絡服務器與網(wǎng)絡轉發(fā)節(jié)點的連接關系用h(s,v)∈{0,1}（s∈S，v∈V）表示。

2) 網(wǎng)絡加速資源

各個服務器中插入的硬件加速卡資源容量記為Hs（s∈S，若無硬件加速資源，則Hs為0），通常表現(xiàn)為所能承載的表項數(shù)量或所能處理的功能類型；網(wǎng)絡轉發(fā)節(jié)點的硬件加速資源記為Hv，通常表現(xiàn)為所能承載的加速表項容量。

3) 網(wǎng)絡功能

網(wǎng)絡功能集合為F={FS, FH, FN}，其中，F(xiàn)S、FH、FN分別表示能夠映射至硬件加速卡資源、能夠映射至轉發(fā)節(jié)點硬件加速表以及不能夠進行硬件加速處理的VNF類型，功能f∈F的計算存儲需求為c(f)，加速資源需求為h(f)。

圖2 VDOP-HA網(wǎng)絡拓撲模型示意

4) 業(yè)務需求

用戶流量處理需求記為 T={vs, vt, (f1,f2,….,fn),Bt|s, t∈V, fi∈F, 1≤i≤n}，其中，vs和 vt分別為流量傳輸?shù)脑?、目的?jié)點，Bt為該流量的帶寬需求。例如，圖2所示的網(wǎng)絡拓撲，用戶需求為T={v1, v7,(f1, f2,f3), 3 Mbit/s}，表示用戶的業(yè)務需求是對從v1到 v7的流量進行 f1→f2→f3的順序功能處理，帶寬需求為3 Mbit/s。那么就需要將(f1, f2, f3)部署于合適的服務器中，并選擇一條合適的路徑依次流經(jīng)功能f1、f2、f3所部署的轉發(fā)節(jié)點（以硬件加速資源方式部署）或NFV服務器。

3.2 優(yōu)化目標

為簡化模型，本文假設用戶需求的網(wǎng)絡功能中，能夠被硬件加速處理的功能均可映射至相應的硬件加速資源。

假設 1 對?fi∈{FS, FH},i∈{1, 2,…, n}，功能的硬件加速需求均可滿足。由于不能被滿足硬件加速處理需求的功能可以當作 fi∈{FN}進行部署，因此，該假設并未改變該問題的性質(zhì)以及求解方法，而僅僅是簡化了模型復雜度。

功能部署問題和流量路由問題通常是獨立的，但在SDN/NFV網(wǎng)絡環(huán)境下，這2個問題往往不是獨立的：首先，功能的部署往往影響流量的轉發(fā)順序及路徑；其次，流量轉發(fā)路徑的長度往往又影響功能的部署位置。為體現(xiàn)功能部署和流量傳輸?shù)穆?lián)合處理，問題的目標一般選為最小化總開銷，包括鏈路開銷和功能部署開銷。此時，VDOP-HA可表述為

其中，式(1)中的α和β是權重調(diào)節(jié)系數(shù)，用于將鏈路開銷和功能部署開銷統(tǒng)一到同一個優(yōu)化目標中；式(2)和式(3)是所要求解的功能部署和路徑選擇參數(shù)；式(4)表示服務器的計算存儲資源約束；式(5)表示鏈路帶寬約束；式(6)和式(7)表示采用硬件加速卡資源做加速的功能部署約束以及流量傳輸約束，即流量一定流經(jīng)與功能部署服務器相連的轉發(fā)節(jié)點；式(8)和式(9)表示采用轉發(fā)節(jié)點中加速表做加速的功能部署約束以及流量傳輸約束，即流量一定流經(jīng)與功能表項部署的轉發(fā)節(jié)點，其中，z(fk,v)表示功能fk是否將功能表項部署于轉發(fā)節(jié)點v中的加速表內(nèi)。

在VDOP-HA問題中，不僅要求解出VNF所要部署的服務器位置以及流量的轉發(fā)路徑，還需求解出VNF部署于服務器之后將軟件功能的處理邏輯映射至硬件加速資源的映射參數(shù)。例如，對于圖2所示的拓撲而言，VDOP-HA需要求解的參數(shù)如圖 3所示。

首先，所有的功能都需要以VM（或docker）的形式部署于服務器上，這是所需要求解的第一層參數(shù)，即VM 部署參數(shù)x(fi,s)；其次，部署于 VM中的功能有一部分是可以將其功能表項或處理邏輯映射至硬件加速資源的，這是所需求解的第二層參數(shù)，即功能到加速資源的映射參數(shù)z(fk, v)，其中，對于fi∈FS的功能，其加速資源就直接位于其所在服務器的加速卡中，因此，這里的映射參數(shù)只是到交換機加速表的映射參數(shù)；最后，數(shù)據(jù)流需要（依次）流經(jīng)這些功能，形成一條從源到目的節(jié)點的路徑，這是所需求解的第三層參數(shù)，即路徑選取參數(shù)y(i, j)，其中，若功能被映射至加速資源，則流量要流經(jīng)其加速資源所在節(jié)點而非其VM部署的節(jié)點。

4 加速資源編排算法

首先，證明了VDOP-HA問題是NP-難問題；其次，針對該問題進行了啟發(fā)式算法設計；最后，分析了算法的時間復雜度。

圖3 VDOP-HA問題求解過程示意

4.1 問題分析

為簡化VDOP-HA問題，本節(jié)首先將VDOP-HA模型進行簡化，假設網(wǎng)絡鏈路的帶寬總是滿足業(yè)務需求。

假設 2 網(wǎng)絡的鏈路帶寬總滿足業(yè)務需求。由于在算法運行時可將不滿足帶寬需求的鏈路從拓撲中去掉（該轉化過程在多項式時間內(nèi)即可完成）并進行求解，因此，該假設并未改變該問題的性質(zhì)以及求解難度，而僅僅是簡化了求解步驟。

定理1 VDOP-HA問題是NP-難問題。

證明 已知哈密頓環(huán)路問題（Hamiltonian cycle problem）是NP-難問題[19]，即對于有向圖G=(V, E)，判斷其是否存在包含所有節(jié)點且只包含一次的簡單環(huán)路。對于圖G=(V, E)的VDOP-HA問題，其一個特例可在多項式時間內(nèi)歸約到哈密頓環(huán)路問題，如圖4所示。

圖4 VDOP-HA到哈密頓環(huán)的歸約示例

1) 每個節(jié)點v均有NFV服務器相連，即對于?s∈S，v∈V，均有 h(s,v)=1。

2) 每個功能f所需要的計算存儲需求為c(f)，加速資源需求為h(f)均相同。

3) 每個服務器節(jié)點的計算資源容量 Cs=c(f)，加速卡資源容量Hs=h(f)。

4) 用戶流量需求T={vs, vt, (f1,f2,…,fn), Bt|s, t∈V,fi∈F, 1≤i≤n}，其中 n=|V|。

此時，如果G存在哈密頓環(huán)路，則VDOP-HA問題的特例存在最短路徑，且該路徑即為哈密頓環(huán)，此時，各個功能分別部署于各個節(jié)點的服務器中；反之亦然。因此，VDOP-HA問題也是NP-難問題。

VDOP-HA問題是 NP-難問題，難以在多項式時間內(nèi)求出問題的最優(yōu)解?，F(xiàn)有功能部署和編排的啟發(fā)式算法主要求出的是功能所要部署的服務器位置參數(shù)以及流量的轉發(fā)路徑參數(shù)，但在VDOP-HA問題中，還需求解出功能部署于服務器之后將軟件功能的處理邏輯映射至硬件加速資源的映射參數(shù)。因此，在現(xiàn)有研究的基礎上，本文主要考慮求解 VNF到硬件加速資源的映射參數(shù)以及流量的路由參數(shù)，即僅考慮能夠映射至硬件加速資源的功能（fi∈{FS, FH}）的部署與編排問題。

4.2 算法設計

需要加速資源映射的功能分為2種：1) 可映射至服務器加速卡的功能，2) 可映射至交換機內(nèi)加速表資源的功能。對這2種功能的映射原則表述如下。

1) 當有空閑硬件加速資源時，將能夠映射至硬件加速資源的功能優(yōu)先映射至相應硬件加速資源。由于功能經(jīng)過硬件加速處理后的處理速率相比基于軟件的處理速率要提升幾十甚至上百倍，因此，雖然將功能映射至加速資源進行處理可能會改變傳輸路徑，從而帶來額外的路徑時延，但是相比于硬件加速帶來的處理性能提升和處理時延降低，其額外的路徑時延可以忽略不計。

2) 當功能既可映射至交換機加速表又可映射至服務器加速卡時，優(yōu)先將功能映射至交換機加速表。這主要是由于：首先，服務器加速卡資源的成本更高；其次，轉發(fā)節(jié)點的節(jié)點數(shù)多且其加速表資源容量更大；最后，加速卡相比交換機內(nèi)的加速表的靈活性更高。因此，將其承載交換機加速表無法承載的功能處理將帶來更高的效用。

基于以上原則，本節(jié)設計了加速卡優(yōu)先部署的啟發(fā)式（HCPD, HA card-prior deployment）算法，如算法1所示。由于服務功能鏈一般不超過5個功能，功能fi∈FH的個數(shù)一般不超過3個，而且轉發(fā)節(jié)點的加速表fi∈FH一般均能夠滿足功能的映射需求，因此，可優(yōu)先滿足功能fi∈FS的硬件加速需求。算法的基本思路是：首先，依次搜索確定能夠承載功能fi∈FS的加速卡所在的服務器位置，當有多個服務器均滿足要求時，選取相距較近的服務器進行承載，此時，從源節(jié)點到最后一個所選服務器的路徑也隨之確定；然后，計算出一條從最后一個所選服務器到目的節(jié)點的（最短）路徑；最后，再將功能 fi∈FH的規(guī)則表項映射至路徑上滿足功能鏈功能順序約束的轉發(fā)節(jié)點的加速表中。

算法1 HCPD算法

1) NS=|{f|f∈FS}|, NH=|{f|f∈FH}|, i=1, j=1,v_temp=vs, path =[]; // path記錄流量流經(jīng)的路徑

2) while i≤NS(fi∈ FS) //將 fi∈ FS的處理邏輯映射至服務器的加速卡資源

3) start_node = v_temp; //從 start_node開始找距離最近的可映射的硬件加速卡

4) deploy_fs (start_node, fi, s); //deploy_fs函數(shù)選取鄰近的服務器部署fi

5) i = i +1, v_temp=(v|h(s,v)=1);

6) Addroute(path, v_temp}; //將搜索的路徑加入path中

7) Delete(G, path); //并將該鏈路從圖G中刪去以保證路徑無重復使用

8) end while

9) Findroute (G, vv_temp, vt, v_set);//從最后一個服務器節(jié)點到目的節(jié)點的最短路徑，G已刪除已用鏈路

10) while j≤NH(fj∈ FH) //將 fi∈ FH的規(guī)則表項映射至轉發(fā)節(jié)點內(nèi)的加速表資源

11) start node = vs;

12) deploy_fh (start_node, fj, v); //在路徑上將fj依順序部署于相應的轉發(fā)節(jié)點中的加速表中

13) j = j +1;

14) end while

其中，deploy_fs函數(shù)依次搜索離start_node最近的能夠滿足功能加速需求的服務器部署 fi，若無加速卡可承載 fi，則選取相近的服務器部署（此時該功能并未被加速），具體步驟如下。

Function deploy_fs (start_node, fi, s)

1) find nearest s, s.t. Hs≥h(fi) //尋 找 離start_node最近的滿足功能硬件加速需求的加速卡所在的服務器

2) if exist s //如果存在，則將功能映射至服務器的加速卡中

3) x(fi,s)=1;

4) else //如果不存在，則將功能就近部署

5) find nearest s, x(fi,s)=1;

6)end if

對于圖2所示的網(wǎng)絡拓撲，假設各個服務器只能部署一個功能，如果用戶需要一條從v1到v7包含3個功能（L7 Firewall–NAT–DPI）的服務功能鏈，首先，L7 Firewall功能和DPI功能屬于集合fi∈FS，優(yōu)先部署于含有加速卡的服務器s1/s3/s4，從v1開始依次搜索含有加速卡的服務器，得到 s1和 s4承載L7 Firewall功能和DPI功能，此時，流經(jīng)2個功能的路徑也隨搜索過程而確定（v1→v2→v3）；然后，計算從v3到v7的最短路徑，最終得到v1→v2→v3→v7的流量傳輸路徑；最后，將NAT功能部署于含有加速表資源的轉發(fā)節(jié)點v2或v3中（部署在2個節(jié)點中的任意一個均可保證服務鏈的順序）。

4.3 算法性能分析

HCPD算法中 f∈FS的映射部分按距離從小到大的順序依次搜索加速卡資源，最短距離可采用Dijkstra算法計算，其基于斐波那契堆實現(xiàn)的時間復雜度為O(|E|+|V|log|V|)，一次搜索最多遍歷|S|個服務器節(jié)點，因此，該部分的時間復雜度為O(|E|+|S|+|V|log|V|)；選路的 Findroute()部分也可采用Dijkstra算法求解，時間復雜度為O(|E|+|V|log|V|)；功能f∈FH的映射部分采用普通搜索即可，時間復雜度為O(|V|)。HCPD算法的f∈FS映射部分需要搜索n次，因此，忽略低階項后HCPD算法的時間復雜度為O(n(|E|+|S|+|V|log|V|))，其中，n為用戶需求的服務功能鏈長度。

除了時間復雜度分析外，編排成功率也是衡量HCPD算法的重要指標。編排成功率，即在VDOP-HA問題有解情況下，HCPD計算出解（不一定是最優(yōu)解）的概率。影響HCPD算法編排成功率的決定性因素是網(wǎng)絡拓撲以及加速資源的分布位置，因為將功能 f∈FS映射至加速資源時采用貪心策略，即最短路徑策略搜索，所以在映射一個功能完成之后，并不能夠保證該功能映射到的服務器加速卡在不復用鏈路的情況下，能夠到達下一個部署功能的服務器節(jié)點，而且也不能保證從f∈FS的最后一個功能部署服務器節(jié)點到目的節(jié)點有路徑。例如，在圖2所示的拓撲中，從v1到v7的流請求中，有3個功能f∈FS的映射需求，按照HCPD算法搜索到了s1和s4中的加速卡承載前2個功能，但由于轉發(fā)鏈路不可復用，因此，從s4已經(jīng)不能夠再到達下一個加速卡所在的服務器s3；而事實上，這個問題的最優(yōu)解是 v1→v5→v6(s3)→v4→v2(s1)→v3(s4)→v7。

5 性能仿真

本節(jié)分別對所提算法的時間開銷和編排成功率進行了仿真驗證，并基于 SDN控制器和NetFPGA-10G[20]平臺進行了原型系統(tǒng)仿真。

5.1 算法性能仿真

采用如圖5所示的網(wǎng)絡拓撲，網(wǎng)絡中有11個轉發(fā)節(jié)點（v1～v11），6個服務器節(jié)點（s1～s6，其中 5個節(jié)點包含加速卡資源）。為不失一般性，假設所有轉發(fā)節(jié)點的硬件加速表資源容量相同。仿真平臺采用Matlab搭建，計算機處理器為Inter? Core?i7-3770、4 GB RAM。設有10種功能，其中，5種功能fi∈FS，加速資源需求服從[1,10]之間的隨機分布；5種功能fi∈FH，加速資源需求服從[5,15]之間的隨機分布。令每個轉發(fā)節(jié)點的加速資源容量為20，服務器內(nèi)加速卡資源容量為10。

考慮到現(xiàn)有硬件加速資源管理編排的研究缺乏算法層面的討論，因此，本文只能與現(xiàn)有服務功能鏈部署選路方面的算法進行對比。本文選取了具有代表性的2種思路進行對比：ProvisionTraffic[14]以功能鏈為導向，將不同功能所能夠部署的節(jié)點分列到不同的級中，各級各節(jié)點之間的傳輸權值由節(jié)點之間的最短路徑確定，然后采用維特比算法求解出最佳部署位置及轉發(fā)路徑；Greedy則以路徑為導向，采用廣度或深度優(yōu)先的搜索思路依次按照服務鏈上的功能搜索，選取最近的可部署節(jié)點進行部署。仿真不同服務鏈長度下算法的時間開銷，隨機生成數(shù)據(jù)流傳輸請求，重復100次，得到3種算法的平均時間開銷，如圖6(a)所示。

實驗結果表明，3種算法的處理時延均與服務功能鏈長度呈線性關系，結果符合上文對算法復雜度的理論分析，且ProvisionTraffic算法的處理時延最高，因為其算法要計算各級各節(jié)點之間的最短路徑，這最多需要計算 次，而HCPD算法和Greedy算法最多計算n次，其中，n為用戶需求的服務功能鏈長度。Greedy算法的處理時延比 HCPD高近 30%，因為HCPD 區(qū)分了 f∈FS和 f∈FH的情況，對功能 f∈FH的映射進行了簡化處理，而 Greedy算法不加區(qū)分地進行搜索，帶來了額外的時間開銷。

圖5 算法性能仿真網(wǎng)絡拓撲

為仿真算法的編排成功率，隨機生成1 000次數(shù)據(jù)流請求，得到3種算法的編排成功率，即能夠完成硬件加速資源映射并找到一條從源到目的地址傳輸路徑的概率，實驗結果如圖 6(b)所示。由仿真結果可知，在相同請求次數(shù)下，3種算法的編排成功率均隨功能鏈長度增長而降低。這是由于功能越多，其所需要的服務器節(jié)點也就越多，滿足功能順序的條件下選路成功的概率也就越低。在相同功能鏈長度下，ProvisionTraffic與 Greedy算法的編排成功率相當，HCPD算法的編排成功率要比這 2種算法高出近30%。這是由于前2種算法的思想相近，針對功能鏈上每一個功能依次進行貪心搜索；而HCPD則根據(jù)功能類型進行有差別搜索，且其搜索的次數(shù)要低于前2種算法，因此成功率要高。

圖6 算法性能對比

從3種算法的對比結果可以看出，在相同請求下，與現(xiàn)有算法相比，HCPD算法能在更短的處理時延下得到更高的編排成功率。綜合時間復雜度和編排成功率來看，HCPD算法性能更優(yōu)。

5.2 原型系統(tǒng)仿真

為實現(xiàn)對交換機中硬件加速表的管控，需要有單獨的HAM連接交換機，而目前OpenFlow交換機設計并不支持 HAM 的連接。因此，本文利用OpenFlow 1.3協(xié)議中的多控制器技術來實現(xiàn) MSC的原型系統(tǒng)。多控制器技術允許有多個控制器同時控制轉發(fā)元件，其中，有一個主控制器（MASTER）和多個從控制器（EQUAL）。多個控制器均可向轉發(fā)元件發(fā)送指令，交換機則可向任意控制器發(fā)送回復或錯誤信息。多控制器技術的提出最初是為了提升控制器的可靠性，使交換機與一個控制器連接的中斷不會影響對交換機處理行為的控制。在 MSC的原型實現(xiàn)中，這種多控制器技術正好提供了HAM的一個實現(xiàn)方案，即主控制器實現(xiàn)SDN控制器的任務，包括網(wǎng)絡狀態(tài)收集、處理網(wǎng)絡事件、確保網(wǎng)絡連接、網(wǎng)絡流量調(diào)度等；從控制器實現(xiàn)HAM，用于配置交換機中的加速表。

MSC原型系統(tǒng)仿真環(huán)境如圖7所示，SDN控制器和HA管理器都基于Floodlight控制器實現(xiàn)；OpenFlow 交換機和 NFV 服務器均采用NetFPGA-10G板卡實現(xiàn)，其中，OpenFlow交換機中的加速表最大支持容納128條加速規(guī)則，NFV服務器加速卡最大可容納 64條自定義加速規(guī)則，并支持32 bit的正則匹配。為簡化與現(xiàn)有算法的對比，本文假設算法中的拓撲信息已經(jīng)給定，不需要通過控制器來獲取，算法僅用來根據(jù)數(shù)據(jù)流的需求來計算功能映射位置及轉發(fā)路徑。

圖7 MSC原型系統(tǒng)仿真環(huán)境

原型系統(tǒng)仿真選取從用戶到視頻服務器的數(shù)據(jù)流，針對有MSC以及未使用HAM的加速架構的端到端轉發(fā)性能進行了測試。首先測試了不同數(shù)據(jù)分組長度下用戶機到視頻服務器的傳輸時延，然后測試了不同請求次數(shù)下的傳輸時延，實驗結果如圖8所示。其中，未使用HAM的架構是當前通用的NFV加速架構，其VNF運行于SDN控制器之上，這種架構可以看作HAM和SDN控制器集成到一個控制器之中。由于文獻[6]已經(jīng)給出了防火墻的實現(xiàn)，為簡化實驗復雜度，選取防火墻和 NAT作為數(shù)據(jù)流的功能處理需求。由圖8仿真結果可知，HAM的引入使MSC的轉發(fā)時延相比DPAK降低了約30%，這是由于不添加HAM進行分離式控制時，VNF處理的數(shù)據(jù)流會經(jīng)過控制器進入上層的VNF，使原本負責網(wǎng)絡狀態(tài)控制和網(wǎng)絡連接的 SDN控制器的負載增大，導致流時延增大。實驗僅采用2個VNF進行仿真，可以預知，當功能數(shù)量增多時，MSC的性能優(yōu)勢將會更加明顯。

圖8 有MSC以及未使用HAM的端到端轉發(fā)性能對比

6 結束語

本文在所提硬件加速資源統(tǒng)一管控平臺的基礎上，研究了如何將上層用戶的功能需求映射到相應的硬件加速資源中進行加速處理的問題。首先，將包括 NFV服務器節(jié)點中的加速卡資源和轉發(fā)節(jié)點中的加速表資源在內(nèi)的網(wǎng)絡硬件加速資源統(tǒng)一到網(wǎng)絡功能部署和編排模型中；然后，對該問題模型進行了理論分析，得出了該問題為NP-難問題的結論；最后，通過對該模型簡化并設計了相應的啟發(fā)式算法，對功能部署和編排問題進行了求解。仿真實驗和原型系統(tǒng)仿真表明，所提機制具有更低的時間開銷，能夠獲得更高的編排成功率，且對未來SDN/NFV網(wǎng)絡中硬件加速資源的管控和編排具有一定實用價值。