基于成本的服務(wù)鏈組成與部署聯(lián)合優(yōu)化策略

劉雅麗，史久根

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

0 概述

網(wǎng)絡(luò)功能虛擬化（Network Function Virtualization，NFV）技術(shù)將網(wǎng)絡(luò)功能的實(shí)現(xiàn)從昂貴的硬件設(shè)備中轉(zhuǎn)換到服務(wù)器上的虛擬設(shè)備中，旨在克服網(wǎng)絡(luò)運(yùn)營商（Internet Service Provider，ISP）日益增加的運(yùn)營支出［1］（Operational Expenditure，OPEX）問題。NFV 將不同的網(wǎng)絡(luò)功能（如防火墻、深度包檢測、加密、解密等）與專用網(wǎng)絡(luò)服務(wù)器分離，通過編排不同的虛擬網(wǎng)絡(luò)功能（Virtual Network Functions，VNF）并將其映射到物理網(wǎng)絡(luò)設(shè)施中以實(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ò)功能的實(shí)現(xiàn)，其中多數(shù)僅考慮了部署問題［6-7］，例如，文獻(xiàn)［8］制定了VNF 中間件放置問題，其目的是最大程度地減少提供特定服務(wù)的實(shí)例總數(shù)，并提出具有恒定逼近率的漸近最優(yōu)貪婪算法。文獻(xiàn)［9］提出一種漸近最優(yōu)的在線算法用于服務(wù)鏈的準(zhǔn)入控制和中間件的增量部署。除集中討論部署階段的研究外，也有部分學(xué)者考慮了組成與部署聯(lián)合優(yōu)化問題，文獻(xiàn)［10］探討VNF 資源優(yōu)化的多階段問題，研究服務(wù)功能鏈的協(xié)調(diào)分配和流量調(diào)度問題，提出一種基于CoordVNF 的啟發(fā)式方法來協(xié)調(diào)組成和部署兩個(gè)階段。另外，文獻(xiàn)［11］考慮并探討了具體流量變化的影響，文獻(xiàn)［12］則進(jìn)一步分析了VNF 改變流的特性，并針對不同依賴關(guān)系狀態(tài)提出了對應(yīng)的放置算法。文獻(xiàn)［13］證明了VNF 改變流量的特性對成本的影響。但這些文獻(xiàn)都未考慮VNF 變化的相對資源需求對成本的影響，沒有綜合分析影響運(yùn)營成本的具體因素。

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

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

虛擬網(wǎng)絡(luò)功能（NFV）通過組成服務(wù)功能鏈（Service Function Chaining，SFC）并將其部署到物理網(wǎng)絡(luò)中的方式來實(shí)現(xiàn)服務(wù)，完成了網(wǎng)絡(luò)功能與物理設(shè)備的脫鉤［14］。不同SFC 組成與部署方式對成本的影響如圖1 所示（彩圖效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版）。每個(gè)物理節(jié)點(diǎn)對應(yīng)一個(gè)物理設(shè)備（Physical Machine，PM），如圖1（a）所示，當(dāng)網(wǎng)絡(luò)功能部署到未激活的PM 上時(shí)，對應(yīng)PM 需要分配一定的資源，如CPU、內(nèi)存等，用以實(shí)現(xiàn)對應(yīng)類型的虛擬設(shè)備（Virtual Machine，VM），以實(shí)例化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ò)實(shí)體，本文用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 的輸入、輸出流。運(yùn)行VNF 需要一定資源（如CPU、內(nèi)存等），所需資源量dfi通常與該VNF 的相對數(shù)據(jù)速率和通過的流相關(guān)［17］為處理一個(gè)VNF 所需數(shù)據(jù)資源量。

1.2 服務(wù)功能鏈

服務(wù)功能鏈?zhǔn)欠?wù)流所需要遍歷的一系列網(wǎng)絡(luò)功能。假設(shè)共有K個(gè)服務(wù)請求，SFC 請求集為S={sk|k=1,2,…,K}，每 個(gè)SFC 由n種類型 的VNF 組成，即sk={fk1,fk2,…,fkn|fki∈F}。VNF 之間可能存在依賴關(guān)系：IPSec 解密器通常放置在NAT 網(wǎng)關(guān)之前［18］。本文用fdei?fi表示fi依賴于fdei。為分析影響成本的不同因素，同時(shí)提高特殊依賴情況下的處理效率，本文將請求集分為完全無序、部分有序和完全有序的VNF 集合進(jìn)行討論。完全無序的請求集為{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，源點(diǎn)為x1，終點(diǎn)為x6。各方案對應(yīng)成本如圖1（b）所示，通過比較可知：不同VNF 的縮放比、相對數(shù)據(jù)速率、SFC 的組成和路由選擇都會(huì)對OPEX 造成影響，本文通過考慮各個(gè)因素，綜合建模以優(yōu)化OPEX。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

部分有序的VNF 需要考慮對應(yīng)的依賴約束，本節(jié)主要描述部分有序VNF 的組成與放置算法（POCP）中獨(dú)有的依賴關(guān)系處理算法——部分有序VNF 的SFC 組合算法（PO-C）。根據(jù)NOCP 設(shè)計(jì)原則可獲得無依賴約束下的最優(yōu)預(yù)部署方案，僅需對違背依賴約束的VNF 進(jìn)行調(diào)整。算法按照預(yù)部署的SFC 順序，依次將違背了依賴關(guān)系的fi緊隨之后放置并組成一個(gè)新的f0，f0繼承了fi和的依賴約束，將f0按 照大小插入原SFC 中即可獲得新的SFC 隊(duì)列，調(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值時(shí)的時(shí)間復(fù)雜度，且PO-C 算法不受參數(shù)k約束。POCP 其余部分與NOCP 類似，總時(shí)間復(fù)雜度與TOCP 算法的時(shí)間復(fù)雜度相同。

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

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

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

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

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

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

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

4.1 完全無序的VNF

本文引入3 種不同的算法進(jìn)行比較：

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

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

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

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

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

4.2 部分有序的VNF

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

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

4.3 完全有序的VNF

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

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

5 結(jié)束語

網(wǎng)絡(luò)功能虛擬化技術(shù)在實(shí)現(xiàn)網(wǎng)絡(luò)靈活管理的同時(shí)降低了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è)計(jì)相應(yīng)的啟發(fā)式算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性。下一步考慮引入流量預(yù)測、網(wǎng)絡(luò)可靠性評(píng)估、請求動(dòng)態(tài)調(diào)度等算法，提高算法的可擴(kuò)展性，以應(yīng)對真實(shí)網(wǎng)絡(luò)環(huán)境中的各種突發(fā)情況。