劉雅麗，史久根

（合肥工業(yè)大學(xué)計算機與信息學(xué)院，合肥 230009）

0 概述

網(wǎng)絡(luò)功能虛擬化（Network Function Virtualization，NFV）技術(shù)將網(wǎng)絡(luò)功能的實現(xiàn)從昂貴的硬件設(shè)備中轉(zhuǎn)換到服務(wù)器上的虛擬設(shè)備中，旨在克服網(wǎng)絡(luò)運營商（Internet Service Provider，ISP）日益增加的運營支出［1］（Operational Expenditure，OPEX）問題。NFV 將不同的網(wǎng)絡(luò)功能（如防火墻、深度包檢測、加密、解密等）與專用網(wǎng)絡(luò)服務(wù)器分離，通過編排不同的虛擬網(wǎng)絡(luò)功能（Virtual Network Functions，VNF）并將其映射到物理網(wǎng)絡(luò)設(shè)施中以實現(xiàn)網(wǎng)絡(luò)服務(wù)［2］，從而有效地提高部署和管理的靈活性［3］。但由于物理位置的選擇復(fù)雜多樣、VNF 改變流量的特性以及VNF 之間存在依賴關(guān)系［4］，因此充滿了挑戰(zhàn)性。

編排VNF 并將其合理部署在物理網(wǎng)絡(luò)中是NFV 的關(guān)鍵技術(shù)之一［5］，現(xiàn)有大量研究致力于VNF網(wǎng)絡(luò)功能的實現(xiàn)，其中多數(shù)僅考慮了部署問題［6-7］，例如，文獻［8］制定了VNF 中間件放置問題，其目的是最大程度地減少提供特定服務(wù)的實例總數(shù)，并提出具有恒定逼近率的漸近最優(yōu)貪婪算法。文獻［9］提出一種漸近最優(yōu)的在線算法用于服務(wù)鏈的準入控制和中間件的增量部署。除集中討論部署階段的研究外，也有部分學(xué)者考慮了組成與部署聯(lián)合優(yōu)化問題，文獻［10］探討VNF 資源優(yōu)化的多階段問題，研究服務(wù)功能鏈的協(xié)調(diào)分配和流量調(diào)度問題，提出一種基于CoordVNF 的啟發(fā)式方法來協(xié)調(diào)組成和部署兩個階段。另外，文獻［11］考慮并探討了具體流量變化的影響，文獻［12］則進一步分析了VNF 改變流的特性，并針對不同依賴關(guān)系狀態(tài)提出了對應(yīng)的放置算法。文獻［13］證明了VNF 改變流量的特性對成本的影響。但這些文獻都未考慮VNF 變化的相對資源需求對成本的影響，沒有綜合分析影響運營成本的具體因素。

為聯(lián)合VNF 組成與VNF 部署兩階段共同優(yōu)化，分析影響OPEX 的具體因素，本文綜合考慮VNF 改變流量的特性、相對資源消耗、依賴關(guān)系以及部署方式的選擇，提出一種面向成本的虛擬網(wǎng)絡(luò)鏈組成和部署聯(lián)合優(yōu)化策略。將節(jié)點映射成本、鏈路映射成本、激活成本和能耗成本公式化為OPEX，建立混合整數(shù)非線性規(guī)劃（Mixed-Integer Nonlinear Programming，MINLP）成本模型。根據(jù)依賴關(guān)系將請求集分成完全無序、部分有序和完全有序的VNF，并設(shè)計3 種對應(yīng)的優(yōu)化算法，分析影響成本的不同因素。

1 虛擬網(wǎng)絡(luò)功能部署問題

虛擬網(wǎng)絡(luò)功能（NFV）通過組成服務(wù)功能鏈（Service Function Chaining，SFC）并將其部署到物理網(wǎng)絡(luò)中的方式來實現(xiàn)服務(wù)，完成了網(wǎng)絡(luò)功能與物理設(shè)備的脫鉤［14］。不同SFC 組成與部署方式對成本的影響如圖1 所示（彩圖效果見《計算機工程》官網(wǎng)HTML 版）。每個物理節(jié)點對應(yīng)一個物理設(shè)備（Physical Machine，PM），如圖1（a）所示，當(dāng)網(wǎng)絡(luò)功能部署到未激活的PM 上時，對應(yīng)PM 需要分配一定的資源，如CPU、內(nèi)存等，用以實現(xiàn)對應(yīng)類型的虛擬設(shè)備（Virtual Machine，VM），以實例化VNF［15］。

圖1 不同SFC 組成與部署方式對成本的影響Fig.1 The impact of different SFC composition and deployment methods on cost

1.1 虛擬網(wǎng)絡(luò)功能

網(wǎng)絡(luò)功能是執(zhí)行特定功能的網(wǎng)絡(luò)實體，本文用fi表示VNFi，F(xiàn)={fi|i=1,2,…,n}表示網(wǎng)絡(luò)功能集合。VNF 多數(shù)是流處理設(shè)備，常以不同方式修改網(wǎng)絡(luò)流［4］。例如Citrix Cloud Bridge 廣域網(wǎng)優(yōu)化器，通過壓縮流量將流量減少了80%［16］。將VNF 的流量縮放比定義為λf=rout/rin，rin和rout分別為VNF 的輸入、輸出流。運行VNF 需要一定資源（如CPU、內(nèi)存等），所需資源量dfi通常與該VNF 的相對數(shù)據(jù)速率和通過的流相關(guān)［17］為處理一個VNF 所需數(shù)據(jù)資源量。

1.2 服務(wù)功能鏈

服務(wù)功能鏈是服務(wù)流所需要遍歷的一系列網(wǎng)絡(luò)功能。假設(shè)共有K個服務(wù)請求，SFC 請求集為S={sk|k=1,2,…,K}，每 個SFC 由n種類型 的VNF 組成，即sk={fk1,fk2,…,fkn|fki∈F}。VNF 之間可能存在依賴關(guān)系：IPSec 解密器通常放置在NAT 網(wǎng)關(guān)之前［18］。本文用fdei?fi表示fi依賴于fdei。為分析影響成本的不同因素，同時提高特殊依賴情況下的處理效率，本文將請求集分為完全無序、部分有序和完全有序的VNF 集合進行討論。完全無序的請求集為{f1,f2}，部分有序的請求集為{f3,f4?f5}，完全有序的請求集為{f6?f7?f8}。

1.3 問題描述

面向成本的VNF 鏈組成與部署問題是通過編排合適的SFC 并合理部署，從而最小化網(wǎng)絡(luò)產(chǎn)生的OPEX。問題示例見圖1，請求集{f1,f2,f3}完全無序，VNF 的縮放比分別為0.5、0.8、1.5，相對數(shù)據(jù)速率為10、20、30，請求初始流為1 Gb/s，源點為x1，終點為x6。各方案對應(yīng)成本如圖1（b）所示，通過比較可知：不同VNF 的縮放比、相對數(shù)據(jù)速率、SFC 的組成和路由選擇都會對OPEX 造成影響，本文通過考慮各個因素，綜合建模以優(yōu)化OPEX。

2 混合整數(shù)非線性模型

將物理網(wǎng)絡(luò)拓撲抽象表示為無向圖G(E,V)，E和V分別表示物理鏈路和物理節(jié)點的集合。G中每個節(jié)點可以部署一定數(shù)量的虛擬機，每個虛擬機只能實例化一種類型的VNF。其中：zx∈{0,1}表示節(jié)點x∈V是否被激活∈{0,1}表示請 求k∈K的fi是否被映射到了物理節(jié)點x上；∈{0,1}表示虛擬鏈路(fi,fj)是否被映射到了物理鏈路(x,y)。OPEX中各成本描述如下：

1）節(jié)點映射成本。部署一個VNF 實例需要消耗一定成本，不同類型的VNF 有不同的資源消耗需求，本文將這種資源需求稱為節(jié)點映射成本，將服務(wù)鏈sk中fi映射到節(jié)點所需的數(shù)據(jù)資源為部署K個服務(wù)功能鏈的總節(jié)點成本如下［19］：

2）鏈路映射成本。將虛擬鏈路映射到物理鏈路中需要消耗一定帶寬資源，不同的鏈路組成方式、映射方式會導(dǎo)致不同的鏈路成本。部署K條服務(wù)功能鏈的總鏈路成本可以表示如下：

從式（8）可以看出：SFC 的鏈路成本變化僅與已部署VNF 之間的物理路徑跳數(shù)hxk有關(guān)。綜合式（4）、式（8）分析可知，SFC 順序決定了節(jié)點映射成本，SFC 部署方式?jīng)Q定了鏈路映射成本。

3）激活成本。在部署VNF 之前，每個物理節(jié)點都需要消耗一定的成本來完成預(yù)配置等前提準備工作。激活成本由所激活節(jié)點的數(shù)量決定，用cx表示各節(jié)點的激活代價。總激活成本如下：

4）能耗成本。PM、VM 一旦被激活，就會消耗一定的資源用于維持自身運轉(zhuǎn)［20］，而沒有被激活的休眠PM、休眠VM 基本不會產(chǎn)生能耗，一般不考慮?；钴SPM 與活躍VM 產(chǎn)生的總能耗成本如下：

綜上，本文優(yōu)化目標為最小化網(wǎng)絡(luò)服務(wù)實現(xiàn)的總運營成本OPEX，表示為：

OPEX 受到以下約束：式（11）保證了每個請求的SFC 都必須被部署到網(wǎng)絡(luò)中，并且每個VNF 只需要一個結(jié)點的虛擬機來實例化。

VNF 之間的依賴關(guān)系如式（12）所示：

每條物理鏈路上的流量之和不能超過其帶寬容量B(x,y)，如式（13）所示：

式（14）、式（15）確保每個節(jié)點上所有VNF 的總資源消耗不應(yīng)超過其資源容量，即要滿足各類型虛擬機的容量和節(jié)點可供承載虛擬機的總資源量Cx的限制：

每個請求流不超過時延上限D(zhuǎn)k，如式(16)所示：

VNF 的聯(lián)合鏈接和部署如式(17)所示：

3 算法設(shè)計

3.1 完全無序的VNF 算法設(shè)計

由于3 種情況均需調(diào)用完全有序的VNF 放置算法（TOCP）的部署方式，本節(jié)主要描述組成方式的影響與算法設(shè)計。由上文可知，將縮小流的VNF 盡可能靠近源點放置，放大流的VNF 盡可能靠近終點放置，可以將鏈路成本最小化?？紤]到相對數(shù)據(jù)速率影響，對部署在同一節(jié)點上的VNF 再次調(diào)整，可以在不改變鏈路成本的同時降低節(jié)點成本。同一節(jié)點上不同VNF 部署順序影如圖2 所示，調(diào)整節(jié)點x上的{f1→f2→f3}?{f3→f2→f1}，輸出流量相同，節(jié)點成本從80.8 減少到了76.2。

圖2 同一節(jié)點上不同VNF 部署順序影響Fig.2 Impact of different VNF deployment orders on same node

完全無序VNF 的組成與放置算法（NOCP）設(shè)計如下：

1）將sk的所有fi根據(jù)升序排序；

2）將λf＞1 的VNF 從流路徑的尾部按照λf降序預(yù)部署，將λf≤1 的VNF 從流路徑的首部按照λf升序預(yù)部署；

3）對部署在同一節(jié)點上的VNF 通過全排列算法組合，并搜索具有最小的SFC；

4）通過完全有序VNF 的最短路徑放置算法（TOSP）確定最終方案。

算法時間復(fù)雜度與TOSP 相同，由于篇幅限制，該部分偽代碼不再贅述。

3.2 部分有序的VNF 算法設(shè)計

部分有序的VNF 需要考慮對應(yīng)的依賴約束，本節(jié)主要描述部分有序VNF 的組成與放置算法（POCP）中獨有的依賴關(guān)系處理算法——部分有序VNF 的SFC 組合算法（PO-C）。根據(jù)NOCP 設(shè)計原則可獲得無依賴約束下的最優(yōu)預(yù)部署方案，僅需對違背依賴約束的VNF 進行調(diào)整。算法按照預(yù)部署的SFC 順序，依次將違背了依賴關(guān)系的fi緊隨之后放置并組成一個新的f0，f0繼承了fi和的依賴約束，將f0按 照大小插入原SFC 中即可獲得新的SFC 隊列，調(diào)整過程如圖3所示，首先將所有VNF 按照λ排序，然后依次將違背了依賴關(guān)系的fi放到后組成新的f0，再插入原SFC，最終得到符合依賴約束的SFC 組成的預(yù)部署結(jié)果。

圖3 依賴關(guān)系調(diào)整過程Fig.3 Adjustment process of dependency relation

PO-C 算法如算法1 所示，將違規(guī)重組的f0插入有序SFC 需要O(logan)，重組后的|sk|對應(yīng)減少，因此將原SFC 調(diào)整為符合依賴約束的SFC，需要：O(logan)+O(loga(n-1))+…+O(loga1)＜O(nlogan)。因此，PO-C 算法低于自相關(guān)樹轉(zhuǎn)換算法［4］前瞻k值時的時間復(fù)雜度，且PO-C 算法不受參數(shù)k約束。POCP 其余部分與NOCP 類似，總時間復(fù)雜度與TOCP 算法的時間復(fù)雜度相同。

算法1部分有序VNF 的SFC 組合算法（PO-C）

3.3 完全有序的VNF 算法設(shè)計

完全有序VNF 組成的SFC 順序固定，鏈路成本變化取決于物理鏈路長度，而能耗成本和激活成本則取決于激活的PM、VM 數(shù)。為優(yōu)化OPEX，應(yīng)盡可能地將VNF 放置在相同或相近的物理節(jié)點上。為此，TOCP 從最短路徑開始，按序依次部署VNF。優(yōu)先考慮復(fù)用已激活的VM、PM 數(shù)，若其剩余資源不足，再嘗試開辟新的VM、PM 數(shù)，以免浪費。得到一組請求集的部署方案后，再嘗試在該方案中關(guān)閉活躍度較低的節(jié)點，并遷移VM 以進一步節(jié)約成本。

分析TOCP 算法可知：尋路時使用DFS 回溯算法，時間復(fù)雜度為；預(yù)部署時間復(fù)雜度為；迭代地尋找并關(guān)閉負載低的PM，時間復(fù)雜度為因此，TOCP 總時間復(fù)雜度為

算法2完全有序VNF 的放置算法（TOCP）

4 仿真實驗結(jié)果與分析

為保證模型可行性和算法的有效性，仿真實驗建立在真實的網(wǎng)絡(luò)拓撲中，數(shù)據(jù)來自SNDlib［21］。算法使用JUN 框架搭建，運行在2 個Intel Core I5-8300H 處理器和128 GB 內(nèi)存的機器上。對NOCP、POCP 算法，實驗選擇在較大規(guī)模和流量的城域網(wǎng)絡(luò)newyork（|V|=16，|E|=49，|S|=56）中比較；對TOCP 算法，在小型網(wǎng)絡(luò)pdh（|V|=11，|E|=34，|S|=18）中仿真比較。由于校驗和開銷，用于無線通信的BCH（48，36）編碼器使流量增加1.3 倍（48/36≈1.3），BCH（31，11）編碼器使流量放大2.8 倍（31/11≈2.8）［22］。綜合參考文獻［12-13，22］，選取并設(shè)置了6 種不同VNF，對應(yīng)縮放比分別為1.2、2.8、0.2、1.0、1.3 和0.8；對應(yīng)數(shù)據(jù)比分別為64、32、2、8、4 和16。請求長度則按照1～6隨機產(chǎn)生，請求流從0.01 Gb/s～2.50 Gb/s 分別進行實驗。同時，實驗使用對應(yīng)OPEX 的4 種成本作為性能指標進行評估。節(jié)點成本為所有請求消耗的數(shù)據(jù)資源總和；鏈路成本為所有請求流在物理鏈路中的傳輸流量總和；激活成本為激活節(jié)點總數(shù)；能耗成本為活躍PM 與活躍VM 在運行過程中所消耗的能耗總和，其中一個PM 和VM 在活躍狀態(tài)下的能耗分別為80.5 W、165.9 W［20］。

4.1 完全無序的VNF

本文引入3 種不同的算法進行比較：

1）首次適應(yīng)（FF）［4］算法。從流路徑的首部開始，按照縮放比升序連續(xù)放置排序后的VNF。

2）隨機擬合（RF）［11］算法。在滿足約束條件的前提下，隨機組成并放置VNF。

3）LFGL 算法［12］。將縮減流量的VNF 從路徑首部按照縮放比升序放置；其余VNF 從流路徑尾部開始按照縮放比降序放置。

為減少部署方式的干擾，3 種比較算法與NOshortest 均采用最短路徑算法放置，各算法性能表現(xiàn)如圖4 所示，其中圖4（a）是各算法比NOCP 多的節(jié)點映射成本，可以看到NO-shortest 各項性能均優(yōu)于3 種比較算法。并且，在相同的部署方式下，不同的組成方式造成的成本差將隨著請求流的增大而不斷擴大。對比NO-shortest，采用不同部署方式的NOCP 僅犧牲了一點鏈路成本，能耗成本和激活成本上性能顯著提高。

圖4 完全無序VNF 仿真結(jié)果Fig.4 Simulation results of complete non-order VNF

4.2 部分有序的VNF

對于部分有序的VNF，實驗假設(shè)VNF 間存在依賴關(guān)系：f1→f2，f4→f3。LFGL、FF 和RF 對比方法的依賴性調(diào)整策略采用k=2 時的自相關(guān)樹轉(zhuǎn)換算法，各算法性能如圖5 所示，POCP 算法可以在滿足NF之間的依賴約束的前提下有效降低總成本。圖5 整體趨勢與圖4 相似，但各成本均有一定程度的增加與波動。因為相較于完全無序的VNF 而言，部分有序的VNF 在組成與部署的過程中約束更多，常常無法獲得NOCP 中的較優(yōu)方案。

圖5 部分有序VNF 仿真結(jié)果Fig.5 Simulation results of partial-order VNF

4.3 完全有序的VNF

由于TOCP 在不同流量大小下的實驗與NOCP、POCP 結(jié)果類似，本文不做贅述。本節(jié)考慮資源受限時TOCP的性能變化。由于VNF完全有序時，式（2）、式（6）為線性關(guān)系，系統(tǒng)模型為混合整數(shù)線性規(guī)劃（Mixed-Integer Linear Programming，MILP）模型。通過采用OPL語言建模，并使用CPLEX12.7 求解得到了MILP 模型結(jié)果。同時，引入采用最大限度激活VM思想的HEU［23］算法作為對比實驗進行比較。為減少不同初始SFC 設(shè)置的干擾，統(tǒng)一設(shè)置請求由長度為3 的SFC 組成：f1→f2→f3，初始請求流率設(shè)置為1 Gb/s。節(jié)點資源配比p=Cx/Cmin的范圍設(shè)置為(0%,100%]，其中Cmin為資源不受限時請求所需的節(jié)點最小活躍VM 數(shù)。各算法的性能表現(xiàn)如圖6 所示。從圖6 可以看出：TOCP 算法的性能明顯優(yōu)于HEU、Shortest 算法，接近MILP 最優(yōu)解；另外，當(dāng)p＞50%時，TOCP 算法與最優(yōu)解的差距很小，但隨著節(jié)點資源的逐漸不足，部署結(jié)果產(chǎn)生了波動，與最優(yōu)解存在一定的差距。

圖6 完全有序VNF 仿真結(jié)果Fig.6 Simulation results of total-order VNF

5 結(jié)束語

網(wǎng)絡(luò)功能虛擬化技術(shù)在實現(xiàn)網(wǎng)絡(luò)靈活管理的同時降低了OPEX，對網(wǎng)絡(luò)供應(yīng)商有重要意義。本文考慮面向OPEX 的VNF 鏈組成與部署聯(lián)合優(yōu)化問題，研究不同依賴關(guān)系下的VNF 組成與放置，分析流量縮放比、相對數(shù)據(jù)率、依賴關(guān)系以及部署方式對OPEX 的影響。建立一種新的MINLP 成本模型，并根據(jù)依賴關(guān)系的不同將請求集分成完全無序、部分有序和完全有序3 種情況，設(shè)計相應(yīng)的啟發(fā)式算法。實驗結(jié)果驗證了本文算法的有效性。下一步考慮引入流量預(yù)測、網(wǎng)絡(luò)可靠性評估、請求動態(tài)調(diào)度等算法，提高算法的可擴展性，以應(yīng)對真實網(wǎng)絡(luò)環(huán)境中的各種突發(fā)情況。