孫 立,史久根

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院, 安徽 合肥 230601)

0 引 言

網(wǎng)絡(luò)功能虛擬化(network function virtualization,NFV),也稱為“中間盒”,將網(wǎng)絡(luò)功能的實現(xiàn)方式從基于專有硬件的設(shè)備轉(zhuǎn)為可在標準服務(wù)器中運行的虛擬機(virtual mechine,VM)中[1]。基于虛擬化技術(shù)來靈活部署網(wǎng)絡(luò)功能可以為運營商獲得更好的收益,降低運營成本[2]。但是中間盒之間的依賴關(guān)系約束使得中間盒部署充滿了挑戰(zhàn)。例如,IPSec通常被部署在NAT(network address translation)之前[3];IDS(intrwsion detection system)需要部署在Firewall之后,作為系統(tǒng)防御的第2道防線[4];VPN(virtual private network)可以部署在Firewall之前或之后[5]。因此不當?shù)闹虚g盒部署策略將會給運營商產(chǎn)生不必要的路由成本,降低路由效率。將由多個網(wǎng)絡(luò)功能組合而成的功能集稱為服務(wù)鏈(service chain,SC)[6]。在服務(wù)鏈中,若所有的功能都存在依賴關(guān)系,則稱為服務(wù)鏈的有序性;若存在部分功能有依賴性,則稱為服務(wù)鏈的部分有序性;若無存在依賴關(guān)系的功能,則稱為服務(wù)鏈的無序性。

文獻[7]基于服務(wù)鏈的3種狀態(tài)研究了流率的變化對路由的影響,提出了一種基于動態(tài)規(guī)劃的算法來部署一條有序服務(wù)鏈,并提出了一種最優(yōu)的貪婪解決方案,用于部署一個無序服務(wù)鏈,此外也證明了對于部分有序性服務(wù)鏈的部署是NP-hard問題,但是他們所研究的目標是負載均衡而不是成本優(yōu)化。文獻[8]也是基于服務(wù)鏈的3種狀態(tài)研究了流率的變化對路由的影響,同時考慮到了中間盒的部署成本,但是研究只適用于樹狀網(wǎng)絡(luò)拓撲,對更為一般的圖狀網(wǎng)絡(luò)拓撲并不適用。文獻[9]在受鏈路帶寬約束的條件下提出一種啟發(fā)式算法用于解決聯(lián)合中間盒部署和路由優(yōu)化問題,并證明了有序性服務(wù)鏈的部署是NP-hard的,但是只考慮了服務(wù)鏈有序的情況,對于服務(wù)鏈部分有序以及無序并沒有考慮。

本文將在鏈路帶寬以及中間盒的依賴關(guān)系約束條件下,針對聯(lián)合中間盒部署以及路由問題,提出服務(wù)鏈感知精準算法(service chain aware exact algorithm,SCAEA)用于解決該問題。該算法首先是根據(jù)網(wǎng)絡(luò)拓撲圖和中間盒依賴關(guān)系來構(gòu)建有向?qū)蛹増D,進而消除中間盒的依賴約束。之后在該有向?qū)蛹増D中采用k-shortest paths算法[10]來篩選出帶寬滿足用戶請求的鏈路。仿真結(jié)果表明,本文所提出的SCAEA在真實網(wǎng)絡(luò)拓撲下具有很好的應(yīng)用前景。

1 問題描述與模型構(gòu)建

1.1 問題描述

聯(lián)合中間盒部署與路由如圖1所示。圖1a中節(jié)點v0為請求的源點,v5為終點,{v1,v2,v3,v4}為部署中間盒{m1,m2,m3}的候選節(jié)點,也就是說,在節(jié)點v1上,既可以部署中間盒m1,也可以部署中間盒m2,還可以部署中間盒m3。不失一般性,假設(shè)每個候選節(jié)點的放置容量為1,即最多只能部署一個中間盒。當中間盒m1部署在候選節(jié)點v1上,m2部署在候選節(jié)點v3上,m3部署在v2上時,如圖1b所示,從源點v0到目的點v5的數(shù)據(jù)流按照m1到m2,再到m3的順序來獲取相應(yīng)的功能服務(wù),可以得到該圖所示的路由路徑。在路徑中,邊(v2,v3)被重復(fù)路由了3次,這是因為數(shù)據(jù)流第1次從節(jié)點v2到節(jié)點v3是為了獲取部署在節(jié)點v3上的中間盒m2的服務(wù);而第2次經(jīng)過是為了獲取部署在節(jié)點v2上的中間盒m3的服務(wù);第3次是因為數(shù)據(jù)流此時已經(jīng)獲取了所有的功能服務(wù),接下來將向目的點進行路由,所以又從節(jié)點v2到節(jié)點v3經(jīng)過一次。當考慮到鏈路帶寬資源的約束時,顯然,在這種情況下對邊(v2,v3)的帶寬資源需求是對只經(jīng)過一次邊的3倍多,例如對(v2,v3)的帶寬資源需求將是對邊(v0,v1)的3倍。

圖1 聯(lián)合中間盒部署與路由

若按照這種中間盒編排、部署的位置以及路由選擇這種方式,只有邊(v2,v3)對鏈路資源的需求比較高。

首先，若將中間盒m1部署在候選點v4處,m2部署在候選點v3處,m3部署在候選點v2處時,如圖1c所示,在從源點到目的點的路由路徑中,邊(v2,v3)和(v3,v4)都被路由了3次。因此,若按照這種方式進行部署,將會對網(wǎng)絡(luò)的帶寬資源有較高的要求。其次,當中間盒{m1,m2,m3}之間不存在依賴關(guān)系時,即該服務(wù)鏈是無序性的,則中間盒可能存在多種編排方式,例如從m1到m3再到m2,或者是從m3到m2再到m1……。因此,在這些編排以及放置策略中,如何選擇出總成本最低的路由具有重要的研究意義,同時也具有巨大的挑戰(zhàn)性。

1.2 系統(tǒng)模型

用無向有權(quán)圖G=(V,E)表示網(wǎng)絡(luò)拓撲結(jié)構(gòu),其中V為節(jié)點集合,E為無向邊集合。然后用src∈V表示請求的發(fā)送方,dst∈V表示請求的接收方,M表示請求所需的中間盒集合。對于任意的2個中間盒m∈M和m′∈M規(guī)定:若m′依賴于m,即數(shù)據(jù)包必須首先獲取中間盒m的服務(wù)后才能再來獲取m′的服務(wù),m→m′;若中間盒m反依賴于m′,即數(shù)據(jù)包必須首先獲取到m′的服務(wù)后才能再來獲取m的服務(wù),m←m′;若中間盒m不依賴也不反依賴于m′,即數(shù)據(jù)包不必優(yōu)先獲取到m′的服務(wù)后才能再來獲取m的服務(wù),或是先獲取到m的服務(wù)后才能再來獲取m′的服務(wù),m∞m′。此外,還需要規(guī)定中間盒之間的依賴關(guān)系具有不可逆性:若m→m′,則有m′→/m;依賴關(guān)系也具有傳遞性:若m→m′并且m′→m″,則有m→m″。本文不考慮一條服務(wù)鏈中存在多個同種功能的中間盒的情況,也就是說請求對某種網(wǎng)絡(luò)功能的需求只需要獲取一次服務(wù)即可。

接下來對所需要用到的一些常量進行定義。定義一個整型常量depend[m,m′]用于表示2個中間盒之間是否存在依賴關(guān)系,即對于?m,m′∈M,當m→m′時,常量depend[m,m′]=1,并且depend[m′,m]=-1;否則其值為0。定義一個二進制常量candidate[u,m]用于表示節(jié)點u是否是部署中間盒m的候選節(jié)點,即對于任意的節(jié)點?u∈V,若節(jié)點u是部署中間盒m的候選節(jié)點,則常量candidate[u,m]=1;否則其值為0。對于邊(u,v)∈E的帶寬容量本文定義一個正實數(shù)常量capacity[u,v]表示。為了方便計算,本文采用i=1表示服務(wù)鏈的起始,用標識中間盒ms占位;采用i=n表示服務(wù)鏈的終止,用標識中間盒md占位。并且，定義{ms,md}?M,ms→md。對于任意的功能中間盒?m∈M-{ms,md}都存在這種依賴關(guān)系:起始中間盒ms必須被編排在功能中間盒之前,ms→m;終止中間盒md必須被編排在功能中間盒之后,m→md。另外定義成本函數(shù):對邊(u,v)∈E的傳輸成本用正實數(shù)C[u,v]表示,功能中間盒m在節(jié)點u上的部署成本用正實數(shù)C[u,m]表示。

接下來定義一個二進制變量place(m,i)用于表示是否將中間盒m編排為第i個。為了方便進行闡述,本文將數(shù)據(jù)包轉(zhuǎn)發(fā)到編排序號為第i個中間盒的過程稱為第i跳。定義二進制變量branch(u,m,i)用于表示是否將編號為i(1≤i≤n)的中間盒m∈M部署在節(jié)點u∈V上。定義一個二進制變量route(u,i)用于表示數(shù)據(jù)包的第i(1≤i≤n)跳是否將會路由到節(jié)點u∈V上。用二進制變量link(u,v,i)表示邊(u,v)∈E是否存在于數(shù)據(jù)包從第i跳到第i+1跳的路由路徑中(1≤i≤n-1)。為了將起始中間盒ms編排為第1個,將終止中間盒md編排為最后一個,分別作如下定義：

place(ms,1)=1

(1)

place(md,n)=1

(2)

(3)

(4)

(3)式保證了對于每一個中間盒m∈M都必須被編排上序號,并且最多只能被編排一次。(4)式確保了對于每一個編排序號i(1≤i≤n)都能對應(yīng)的上一個中間盒。

depend[m′,m]≥0,?m,m′∈M

(5)

(5)式表示根據(jù)每一對中間盒之間的依賴關(guān)系,按序編排這兩個中間盒的序號。例如,當中間盒m和m′滿足m→m′時,常量depend[m,m′]=1,則這就要求中間盒m的編排序號要小于中間盒m′的;當m←m′時,常量depend[m,m′]=-1,則m的編排序號要大于中間盒m′的;當m∞m′時,depend[m,m′]=0,則m與m′可以任意編排序號。

branch(src,ms,1)=1

(6)

branch(dst,md,n)=1

(7)

(6)式確保將編號為1的起始中間盒ms部署在請求的源點src∈V處。(7)式確保將編號為n的終止中間盒md部署在請求的目的點dst∈V處。

branch(u,m,i)=0,?m∈M,1≤i≤n

(8)

(8)式表示將每一個被編排上序號的中間盒都要被部署在對應(yīng)的某一個候選點上。如當u是中間盒m的部署候選點,則candidate[u,m]=1,且中間盒m也被編排為第i個,即place(m,i)=1,因此變量branch(u,m,i)=1必須存在,也就是說,要將編號為i的中間盒m部署在節(jié)點u上。

(9)

因為網(wǎng)絡(luò)中的有些節(jié)點可以是多種中間盒的部署候選點,根據(jù)之前的前提假設(shè),每個候選點最多只能部署一個中間盒,所以(9)式確保了這個前提假設(shè)的成立,即將候選點的部署容量設(shè)置為1,并且對每一個節(jié)點?u∈V都滿足約束條件。

?u∈V,1≤i≤n

(10)

(11)

(10)式、(11)式聯(lián)合保證了對數(shù)據(jù)包的每一跳都有唯一的網(wǎng)絡(luò)節(jié)點作為對應(yīng),即將中間盒的編排次序映射成網(wǎng)絡(luò)拓撲上的部署位置。

route(u,i)-route(u,i+1),

?u∈V,1≤i≤n-1

(12)

(12)式用于保證數(shù)據(jù)包從第i跳到第i+1跳滿足流守恒約束條件,其中符號Nu表示u∈V在圖G中的鄰接節(jié)點集合。

(13)

(14)

(15)

(14)式為所有的中間盒部署成本之和,其中編號i從2開始計數(shù)到n-1為止,是因為起始中間盒ms和終止中間盒md只是一個占位符號,因此其部署成本為0。(15)式表示路由中的路徑傳輸成本之和,從數(shù)據(jù)包的第1跳到第2跳再到第3跳,一直累加到目的點。接著定義本問題的優(yōu)化目標C,該目標是由中間盒部署成本和鏈路的傳輸成本組成的,是用來最小化總路由成本。

minC=Z+N

(16)

2 算法設(shè)計

為了能夠快速精準地解決受中間盒依賴關(guān)系約束以及鏈路帶寬資源約束的路由成本最小化問題,本小節(jié)提出服務(wù)鏈感知精準算法(service chain aware exact algorithm, SCAEA)。該算法由有向?qū)蛹増D構(gòu)造和路由路徑選擇2個部分組成。

2.1 有向?qū)蛹増D構(gòu)造

在層級圖中,數(shù)據(jù)包每跨一級路由,意味著它可以再次獲取一種中間盒服務(wù),依次類推,只要數(shù)據(jù)包可以連續(xù)地跨越n-1級,就可以獲得所有功能中間盒的服務(wù)。假設(shè)第i級內(nèi)的第j層為Li,j,其所代表的中間盒組合為A第i+1級內(nèi)的第k層為Li+1,k,其所代表的中間盒組合為B,若A?B,則數(shù)據(jù)包可從Li,j層跨級路由到Li+1,k層。需要注意的是,跨級路由的交叉點需為中間盒m=B-A的候選部署節(jié)點。此外,跨層間的有向邊權(quán)值是C[u,v]與C[u,m]之和,而同層內(nèi)的有向邊權(quán)值為C[u,v]。

例如,假設(shè)中間盒{m1,m2,m3}只存在唯一的依賴關(guān)系為m3→m2,由圖1a所構(gòu)造的層級圖如圖2所示,其中每個虛線框代表一級,每一級由多層拓撲組成。因為數(shù)據(jù)包獲取的第1個中間盒服務(wù)必須為ms,因此第1級只有一層,所代表的中間盒組合為{ms}。第2級表明數(shù)據(jù)包已經(jīng)獲取過某2種中間盒服務(wù),因此,由任意的2種中間盒所產(chǎn)生的組合為{ms,m1}、{ms,m2}、{ms,m3}、{m1,m2}、{m1,m3}以及{m2,m3},在排除不符合依賴關(guān)系的組合后為{ms,m1}和{ms,m3},因此在第2級中,可分為2層,分別代表{ms,m1}和{ms,m3}。

圖2 有向?qū)蛹増D

依此類推,在第3級中,存在2層,分別代表{ms,m1,m3}和{ms,m2,m3};第4級只有一層,代表{ms,m1,m2,m3},同時也表明,當數(shù)據(jù)包路由到這一層時,已經(jīng)獲取到所有所需的功能服務(wù)了。當數(shù)據(jù)包從第1級的第1層L1,1跨級路由到第2級的第2層L2,2,首先有{ms}?{ms,m3},這滿足跨級路由條件;其次,L2,2層的第2列、第3列、第4列以及第5列節(jié)點都為中間盒m3的部署節(jié)點,因此通過將m3放置于該點處后,數(shù)據(jù)包可以在已獲取過{ms}服務(wù)的基礎(chǔ)上跨到L2,2層來繼續(xù)獲取m3的服務(wù)。

算法1為中間盒組合算法的偽代碼。其中第4行表示集合J只有一個{ms}是大小為1的元素。第6行到第11行用于判斷集合Qi中的所有元素與未包含的其他元素的依賴關(guān)系,若Qi中存在一個元素依賴于Qi之外的元素,則Qi不能作為J的元素,并且要求ms必須是Qi的一個元素,否則Qi也不能作為J的元素。算法1步驟如下。

輸入:中間盒集合M,依賴關(guān)系depend(m,m′)∈{-1,0,1} 。

輸出:M-{md}的所有滿足依賴關(guān)系的子集J。

1. 獲取M-{md}中的所有元素的全組合集合Q;

2. 將J初始化為含有{ms}的集合;

3. forQiinQdo

4. ifQi只有一個元素then continue;

5.k=true;

6. forminQido

7. form′ inM-{ms,md}-Qido

8. if depend(m′,m)=1 orms?Qithen

9.k=false

10. ifk=true then

11. 將集合Qi作為J的一個元素;

12. returnJ;

算法2為構(gòu)造層級圖的偽代碼,結(jié)合圖2來說明下該偽代碼中的一些符號含義。Pi是由所有J中元素個數(shù)為i個的子集組成的集合,例如,當i=2時,P2={{ms,m1},{ms,m3}};當i=3時,P3={{ms,m1,m3}, {ms,m2,m3}}。此外P2,1={ms,m1},P2,2={ms,m3},因此P3,1-P2,2=m1。節(jié)點ui,j表示第i級第j層節(jié)點。算法2步驟如下。

輸入:網(wǎng)絡(luò)拓撲圖G,中間盒組合J。

1. fori=1 ton-1 do

2.Pi是由所有J中元素個數(shù)為i個的子集組成的集合;

3. forj=1 to |Pi| do

4. foruin do

6. for (u,v) inEdo

8.C[ui,j,vi,j] =C[vi,j,ui,j] =C[u,v];

9. fori=1 ton-2 do

10. forj=1 to |Pi| do

11. fork=1 to |Pi+1| do

12.m=Pi+1，k-Pi,j;

13. foruinVdo;

14. ifu是部署中間盒m的候選節(jié)點then

15. forvinNudo

17.C[ui,j,vi+1,k] =C[u,v]+C[u,m];

2.2 路由路徑選擇

算法3為路由路徑選擇的偽代碼。首先通過Eppstein算法不斷迭代出第k條最短路徑,并對該路徑進行如下判斷:① 第2～3行用remainder表示當前鏈路帶寬剩余量,并在第7～8行將鏈路p中的〈ux1,y1,vx2,y2〉映射為圖G中所對應(yīng)的邊(u,v),根據(jù)這條邊被路由到的次數(shù),在remainder[u,v]中減去消耗量,當remainder[u,v]<0時,說明邊(u,v)的帶寬容量不夠支撐路由所需,因此剔除這條路由;② 變量visited用于記錄圖G中的點是否已經(jīng)被部署過了中間盒,代碼第11行對邊〈ux1,y1,vx2,y2〉進行判斷是否為跨級邊,若為跨級邊則節(jié)點v應(yīng)為部署中間盒的節(jié)點,并在第12行對該節(jié)點進行判斷是否之前已經(jīng)部署過了中間盒,若已經(jīng)部署過了,則剔除這條路由。最終能滿足以上條件的路由,則為最終最優(yōu)的可行路由。算法3步驟如下。

輸出:從源點到目的點的路由路徑L。

2. for (u,v) inEdo

3. remainder[u,v] = capacity(u,v);

4. foruinVdo

5. visited[u] = false;

6. success =true;

7. for〈ux1,y1,vx2,y2〉 inpdo

8. 將〈ux1,y1,vx2,y2〉 映射為圖G中的邊(u,v);

9. remainder[u,v] = remainder[u,v] - demand;

10. if remainder[u,v]<0 then success=false;

11. ifx1

12. if visited[v]=true then success=false;

13. visited[v] = true;

14. if success=true then returnp;

15. return不存在滿足條件的路由;

3 算法分析

3.1 算法正確性分析

證明取鏈路l上的任意一個跨級有向邊〈ui,j,vi+1,k〉,ui,j位于第i級,vi+1位于i+1級,假設(shè)Pi,j為i級j層所對應(yīng)的中間盒組合,Pi+1,k為i+1級k層所對應(yīng)的中間盒組合,則m=Pi+1,k-Pi,j且Pi,j.?Pi+1,k。對于?m′∈Pi,j,根據(jù)依賴關(guān)系的傳遞性和不可逆性,有m′→m或m′∞m。因此根據(jù)數(shù)學(xué)歸納法可證得定理1成立。

3.2 算法時間復(fù)雜度分析

4 實驗仿真

本文仿真實驗所采用的系統(tǒng)為Intel Celeron CPU 1005M,RAM 10 GB的Win7 64位專業(yè)版;采用Java 8作為仿真編程語言;對于混合整數(shù)線性模型(1)～(16)式,采用GLPK求解[11]。假設(shè)中間盒的部署成本服從正態(tài)分布N(μlG,σ2),其中μ∈{1,3},σ=lG/4,lG為從源點src到目的點dst的最短路徑成本[12]。網(wǎng)絡(luò)拓撲sun(|V|=27,|E|=51)、鏈路成本、鏈路帶寬以及用戶請求均采用SNDlib網(wǎng)站所提供的真實數(shù)據(jù)[13],其中用戶請求選取前3條(D1,D2,D3)。對于每一條請求,隨機選取網(wǎng)絡(luò)中50%的節(jié)點作為所有中間盒部署候選點,并且源點和目的點不作為部署候選點。

設(shè)置4個中間盒{m1,m2,m3,m4},根據(jù)中間盒的依賴關(guān)系做以下仿真實驗。

(1) 服務(wù)鏈有序:m1→m2→m3→m4。仿真實驗結(jié)果見表4所列。

表4 服務(wù)鏈有序?qū)嶒瀸Ρ?/p>

(2) 服務(wù)鏈部分有序:m1→m2且m3→m4。仿真實驗結(jié)果見表5所列。

表5 服務(wù)鏈部分有序?qū)嶒瀸Ρ?/p>

(3) 服務(wù)鏈無序:m1∞m2∞m3∞m4。仿真實驗結(jié)果見表6所列。

表6 服務(wù)鏈無序?qū)嶒瀸Ρ?/p>

3個仿真實驗中,中間盒都嚴格按照其依賴關(guān)系進行部署。例如在服務(wù)鏈為有序時,SCAEA為D1請求規(guī)劃的路由為12→14→15(m1) →16(m2)→12→11(m3)→9(m4)→8,將中間盒m1部署在v15上,m2部署在v16上,m3部署在v11上,m4部署在v9上。雖然SCAEA規(guī)劃的路由不能與GLPK始終保持一致,如在實驗(2)的D3請求中,GLPK對數(shù)據(jù)包規(guī)劃的路由方式與SCAEA的不一致,但是總體路由成本都是最低的。此外,GLPK采用的是C語言實現(xiàn)的一個線性規(guī)劃求解器[11],而本文的算法實現(xiàn)采用Java編寫,因此,SCAEA在該網(wǎng)絡(luò)拓撲下還是可以較快地計算出最優(yōu)解,為用戶請求及時規(guī)劃出最優(yōu)路由。

5 結(jié) 論

本文在受中間盒依賴關(guān)系以及鏈路帶寬約束下,研究了NFV中間盒的最佳部署位置,進而來降低總路由成本,據(jù)此提出一種精準算法SCAEA。通過實驗仿真,驗證了該算法具有較好的應(yīng)用前景。但是本文所研究的對象是一對一的用戶請求,考慮到當前視頻會議、軟件更新以及新聞推送等應(yīng)用都是基于多播方式實現(xiàn)的,因此可以根據(jù)本文的研究成果進一步針對SDN/NFV多播開展深入的研究。