節點效用最大化的服務功能鏈構建方法

張傳浩，周　橋

(1.鐵道警察學院 公安技術系，鄭州 450053；　2.國家數字交換系統工程技術研究中心，鄭州 450002)(*通信作者電子郵箱zhangchuanhao@rpc.edu.cn)

0　引言

隨著網絡流量的急劇膨脹和網絡業務的不斷更新，當今的計算機網絡越來越依賴于中間件盒子(middlebox)所提供的功能。文獻[1]定義中間件盒子是工作在計算機網絡4～7層的一種網絡設備，用來對經過它的流量進行檢測和修改。中間件盒子在網絡中發揮著越來越重要的作用，如改善安全、提高性能、減小帶寬以及提供其他新穎功能[2]等。但如何在網絡中引導流量通過一定順序的中間件盒子構成服務功能鏈來提供豐富的功能卻是一個非常復雜的過程：首先需要在網絡中的合適位置部署中間件盒子，然后需要手工配置轉發規則來引導流量通過一定順序的盒子。隨著軟件定義網絡(Software Defined Networ, SDN)[3]和網絡功能虛擬化(Network Function Virtualization, NFV)[4]技術的興起，如何靈活高效地解決這些問題再次成為研究的熱點。

SDN技術提供了邏輯集中式的管理控制，解耦了數據平面和轉發平面，給中間件盒子提供了可編程的轉發規則配置方式。StEERING方法[5]通過對OpenFlow多級流表進行改進來實現流量引導；SIMPLE方法[6]構建了基于SDN的策略執行層，能夠使中間件的深度策略轉化更加有效，并解決了流量引導中的環路問題；FlowTags方法[7]則通過對中間件以及交換機的改進，使之能夠對進出的流進行標記來實現流量引導。但是基于SDN技術實現的服務功能鏈存在著一些共性的問題：首先，無法根據業務需求來實現中間件的動態部署；其次，當網絡中部署著大量中間件盒子時，硬件成本及管理開銷太大；最后，中間件盒子出現故障以及過載時，恢復速度過慢難以滿足用戶需求。

NFV技術克服了傳統中間件盒子種類繁多、價格昂貴、結構封閉且十分不利于統一集中管理配置等缺點，由基于軟件實現的虛擬功能代替基于硬件實現的硬件盒子，并部署于廉價的商用設備(例如x86服務器)上。Sekar等[8]提出了一種集成統一的中間件盒子結構CoMB(Consolidated MiddleBox)來解決傳統中間件盒子所帶來的弊端，每個CoMB運行多個基于軟件的中間件，根據不同的業務啟動相應的中間件。ClickOS[9]是基于Xen實現的軟件平臺，通過優化中間盒子處理能夠創建快速啟動的、低延遲的小型虛擬機。這些基于NFV的虛擬化中間件盒子主要側重于提升數據平面以及軟件上的實現，沒有涉及虛擬功能實例的最優控制。基于SDN+NFV的方法能夠很好地解決上面出現的問題：首先能實現虛擬中間件盒子間的流量引導；其次能根據業務需求動態部署虛擬的中間件盒子；最后還能對故障或者過載的中間件盒子實現遷移，從而實現虛擬功能實例的最優控制。OpenNF[10]和Slick[11-12]都是國外最新提出的基于SDN+NFV的服務功能部署架構。OpenNF利用SDN控制器設計了一個服務功能控制平面、一系列的API接口以及服務功能組合與轉發機制；Slick設計了一個允許用戶對某些指定流的服務功能進行編程處理的架構，通過用戶自定義編程來完成虛擬中間件盒子的部署和流量引導。OpenNF和Slick的研究重點偏向于控制平面設計和控制軟件的實現，且其服務功能鏈構建算法往往將流量引導和中間件盒子部署問題分開考慮，達不到節點資源效用最大化。

與當前主流方法不同，本文將虛擬化的中間件盒子部署問題和流量引導問題聯合考慮，提出了一種節點效用最大化的服務功能鏈構建方法NUM(Node Utility Maximization)。實驗結果表明，與主流方法相比，NUM在構建時間、構建成功率、網絡擁塞率以及節點效用上均具有優越性。

1　服務功能鏈構建問題

SDN技術使得中間件盒子的流量引導更加靈活便利，NFV技術則可虛擬化中間件盒子且使其易于動態部署。在SDN+NFV環境下，為了實現用戶訂制的服務功能，需要利用NFV技術動態部署虛擬化的中間件盒子，再利用SDN技術從源節點引導流量通過特定順序的中間件盒子到達目的節點構成服務功能鏈。本文將中間件盒子部署問題和流量引導問題聯合起來，定義為服務功能鏈構建問題(Service Function Chain Construction Problem, SFCCP)。

如圖1所示，本文所用的中間件盒子是建立在商用服務器中ClickOS平臺上虛擬化的中間件盒子，控制器控制交換機根據業務需求動態地進行虛擬中間件盒子的實例化，在沒有業務需求時關閉來節省資源。以圖1為例簡單說明服務功能鏈構建問題：根據業務需求，流量1需分別經過防火墻、入侵檢測系統以及一個內容過濾器，流量2僅需經過防火墻和入侵檢測系統，流量3則僅需經過防火墻和內容過濾器。為了滿足用戶的服務功能需求，首先需要選擇出最優節點并求解出一條最優路徑和資源分配，然后以業務需求和路徑上的資源分配為條件來實現虛擬化中間件盒子的實例化，最后控制器引導流量在確定的路徑上通過實例化的中間件盒子完成服務功能鏈構建。

圖1　服務功能鏈構建示例Fig. 1　Example of service function chain construction

在SDN+NFV的網絡環境中，主要有以下因素影響著SFCCP：

1)用戶策略：用戶制定策略的數量和復雜度直接決定了SFCCP的求解難度。本文對用戶策略進行劃分，每條策略劃分成多個經過單一中間件盒子的流，以此來降低求解難度。

2)網絡拓撲限制：主要是網絡節點數量和網絡節點的鏈接情況，以及鏈路帶寬限制。

3)節點資源限制：交換機節點的轉發處理能力主要被單個物理設備的三態內容尋址存儲器(Ternary Content Addressable Memory, TCAM)資源所限制，屬于底層轉發能力。

4)服務器資源限制：在服務器上的ClickOS平臺上虛擬出中間件盒子需要耗費計算資源與存儲和帶寬資源，屬于配置層計算能力。

5)虛擬網絡功能相關性問題：本文討論的虛擬網絡功能模塊均具備獨立性特點，即均以用戶需求為驅動進行部署，模塊間交互接口網絡數據流量；同時本文考慮的重點也是以模塊為基本單元的服務鏈部署策略，所以模塊之間的層級相同，可以不考慮其相關性。

2　服務功能鏈構建方法

2.1　服務功能鏈構建機制

各種因素互相影響、相互制約，使得虛擬中間件盒子的部署以及部署完成后的流量引導變成一個極為復雜的過程。為了解決SFCCP，本文設計如圖2所示的服務功能鏈構建機制，通過擴展現有SDN控制器的南向接口實現對服務器上虛擬中間件的部署與管理。該機制核心的控制器主要由三部分組成：資源處理器、轉發規則產生器以及服務器管理器。

1)資源處理器以網絡拓撲結構、用戶制定的服務功能需求以及交換機和服務器等的資源限制為輸入，通過一定的算法實現對服務器的資源分配和網絡節點及路徑的選擇；資源處理器計算的結果直接輸出到轉發規則產生器和服務器管理器。

2)服務器管理器根據資源處理器所計算的資源分配在對應的服務器上進行中間件盒子的實例化，并根據網絡流量動態地進行開啟和關閉處理。

3)轉發規則產生器根據資源處理器所計算出的網絡節點和路徑下發轉發規則。

在服務功能鏈構建機制中，規則產生器和服務器管理器是重要的組成部分，根據資源處理器所處理的結果，服務器管理器先進行虛擬中間件盒子的實例化，規則產生器再引導流量通過實例化的虛擬中間件盒子；而資源處理器是整個機制的核心，它負責對各種輸入進行建模并計算，下一節將描述資源處理器建模的主要內容。

圖2　服務功能鏈構建機制Fig. 2　Mechanism of service function chain construction

2.2　服務功能鏈構建模型

在SDN+NFV的環境下，虛擬中間件在網絡節點的部署問題等同于節點資源對虛擬中間件的分配問題，而流量引導問題等同于對網絡中最優節點的選擇問題。因此服務功能鏈構建問題可簡化成一種考慮鏈路帶寬分配、節點資源分配以及服務器資源分配的新型路由問題。

模型描述如下：流量根據其不同的業務需求，可被劃分成若干個從si到ti的流comi(si,ti,di)，di表示總的業務需求量；給定網絡拓撲G=(V,E)，鏈路E的鏈路容量為B(E)，節點V的容量為C(V)，分配給V節點的服務器資源為S(V)，以及一系列的服務功能業務流量D={com1,com2，…,comk}。

模型整體目標是在盡可能多業務的同時，耗費最少的節點資源滿足所有流量的業務功能需求，從而達到節點最優和效能最大化的目的。服務功能鏈構建問題核心在于選擇最優的節點構建服務功能鏈來滿足服務需求，根據模型整體目標，將該問題分為兩部分：第一部分是最小化問題，即選擇最小的節點集合來滿足所有的服務需求；第二部分是最大化問題，即在已選節點的基礎上滿足最大的業務流量，從而達到節點資源和服務器資源最大效用。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?i∈[1,m],j∈{1,2},v∈V,?u∈Vcomi

(8)

(9)

(10)

(11)

其中:式(1)是整體優化目標，選擇最小的節點集合來滿足業務需求；式(2)～(6)表示鏈路帶寬限制、節點資源限制、服務器資源限制以及滿足服務需求的約束；式(7)則要求節點資源處理能力大于業務需求，從而滿足處理條件；式(8)～(11)表示在節點和鏈路上的流量守恒約束。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

其中：式(15)、(16)表示節點v的總流量守恒，式(17)、(18)分別是鏈路和節點資源限制；式(19)則是流量非負約束。

2.3　求解算法

該服務功能鏈部署問題是一個組合優化問題，同時也是NP難問題，此類問題求解方法通常采用模擬退火等啟發式算法來尋找最優解。模擬退火(Simulated Annealing，SA)算法[13]能夠有限度地接受劣解，可以跳出局部最優解，并且具有原理簡單、使用方便、所求解全局最優或近似全局最優等特點，但是其求解時間過長，步長和溫度T的初值較難設置，而且搜索過程中有概率遺失當前的最優解。而禁忌搜索算法(Tabu Search, TS)[14]模仿人類的記憶能力，在搜索過程采用設置禁忌表的方式來避免陷入局部最優以及迂回搜索，很好地克服了模擬退火算法的缺點。本文參考目前解決網絡路徑選擇與節點資源分配問題常用的組合算法思路[15-16]，使用基于TS改進的組合模擬退火算法TS-CSA來解決服務功能鏈部署問題。

以下簡單說明基于TS改進的組合模擬退火算法的主要步驟。TS-CSA算法共分為兩層：其中內層算法是對節點選擇決策進行優化，即對問題第一部分進行優化；外層算法則是在節點選擇決策的基礎上進行效用最大化，即對問題第二部分進行優化。設g為該問題的一個解，該解在SA算法中稱為一個配置或狀態。設Ω為狀態空間，定義E(g)為狀態g的能量。Metropolis策略[17]用于計算在溫度t時從狀態g到狀態g′的轉移概率，即：

(20)

其中溫度T控制著SA算法的速度。

在外層優化算法中，利用禁忌搜索算法中的禁忌表思想對組合模擬退火算法進行改進，同時增加了升溫操作，提高算法搜索效率。外層優化算法的具體步驟如下:

1)置空禁忌表H，設置模擬退火計劃表，令初始溫度為t，升溫系數τ=1，降溫系數ξ=0．9，隨機生成問題的初始解X0，同時令當前記憶最優解Xbest=X0，Ω←Ω∪X0，且令禁忌長度λ(X0)=n，K=1。

2)執行外層鄰域函數，同時更新禁忌表中各對象的禁忌長度。

3)執行內層優化算法。

4)若未滿足同溫度下的抽樣穩定準則，返回步驟2)繼續尋找新解，否則執行降溫操作。

5)若未滿足升溫條件，則返回步驟2)繼續尋找新解，否則執行升溫操作。

6)檢驗收斂性。

算法偽代碼如下所示：

1)

while not stop

2)

Xbest=X0;tk=t;

3)

fori=1 toL

4)

ifλ(X0)>0

5)

getXnew,calculateE(Xnew)

6)

λ(X0)=λ(X0)-1;

7)

ifλ(X0)=0;

8)

goto procedure TS-CSA partⅡ

9)

end if

10)

Update the tabu listH;

11)

end if

12)

ifE(Xnew′)

13)

Xbest=Xnew′;

14)

ifE(Xnew)

15)

X0=Xnew;

16)

else CalculateP(tk)=

exp[-(E(Xnew)-E(Xk))/τt];

17)

end if

18)

if random(0,1)

19)

X0=Xnew;

20)

end if

21)

end if

22)

end for

23)

K=K+1;t=ζt;

24)

end while

25)

printXbest

內層優化算法的步驟為:

1)以Xnew為當前初始解和最優解，構造內層鄰域解，得到新解Xnew′。

2)判斷新解的優劣性。

3)若未達到同溫度下的抽樣穩定準則，則返回步驟2);否則算法終止，返回外層優化算法。

內層算法(TS-CSA partⅡ)偽代碼如下所示：

1)

while not stop

2)

ifE(Xnew′)

3)

Xnew=Xnew′;

4)

else CalculateP(t)=exp[-(E(Xnew′)-E(Xnew))/τt];

5)

if random(0,1)

6)

Xnew=Xnew′;

7)

end if

8)

end while

3　實驗仿真與性能評估

3.1　實驗平臺

為了驗證模型與算法的可靠性與有效性，本實驗算法仿真部分在配置Intel Core i7 CPU 3.40 GHz、4 GB內存的計算機上運行。實驗網絡模型如圖3所示，底層網絡拓撲和服務功能請求的拓撲由GT-ITM[18]工具生成，通過仿真來驗證算法的性能。本文設計的服務功能鏈構建原型模型采用ClickOS模擬網絡中的大量元服務實例，ClickOS是一款高性能的虛擬化平臺，當單個物理CPU核運行100個實例時，ClickOS虛擬機(Virtual Machine, VM)能實現整體10 Gb/s的速率。實驗平臺由NetFPGA 10G實現的OpenFlow交換機的全連接網絡組成：每臺交換機連接一臺服務器，運行ClickOS平臺；每臺服務器配置3.4 GHz Intel Core i7處理器、4 GB內存和1 Gb/s網絡接口。

3.2　實驗仿真

3.2.1服務功能鏈構建時間

分別用GT-ITM模擬節點數k=5，連接度d=2，以及按照網絡復雜度越來越高的原則分別設計：k=15,d=4;k=25,d=6;k=50,d=8;k=100,d=8等網絡拓撲結構，服務功能鏈數M=10保持不變。通過Matlab實驗分別仿真StEERING、SIMPLE和本文NUM方法的服務功能鏈的構建時間隨節點數的變化，結果如圖4所示；再用GT-ITM模擬節點數k=10，連接度d=3的網絡拓撲，使服務功能鏈數逐漸增加，分別為M=5,10,20,50,100，通過Matlab實驗分別仿真模擬退火算法、禁忌搜索算法和改進的組合模擬退火算法計算服務功能鏈的構建時間隨服務功能鏈數的變化，結果如圖5所示。構建時間越短，說明算法效率越高。

圖3　實驗網絡拓撲Fig. 3　Experimental network topology

圖4　服務功能鏈構建時間隨節點數變化情況Fig. 4　Service function chain construction time changes with the number of nodes

圖5　服務功能鏈構建時間隨服務功能鏈數變化情況Fig. 5　Service function chain construction time changes with the number of service function chains

3.2.2服務功能鏈構建成功率

定義服務功能鏈構建成功率SR=m/M,其中:M為需求服務功能鏈數量，m為實際成功構建的服務功能鏈數量。按照3.2.1節的數據設定通過Matlab仿真以下情況：隨著拓撲節點數增多不同算法的構建成功率，結果如圖6所示；隨著服務功能鏈增多不同算法的構建成功率，結果如圖7所示。成功率越高說明算法越有效。

3.2.3網絡擁塞率

圖6　服務功能鏈構建成功率隨節點數變化情況Fig. 6　Success rate of service function chain construction changes with the number of nodes

圖7　服務功能鏈構建成功率隨服務功能鏈數變化情況Fig. 7　Success rate of service function chain construction changes with the number of service function chains

圖8　構建擁塞率隨服務功能鏈數變化情況Fig. 8　Congestion rate of construction changes with the number of service function chains

3.2.4節點平均效用

圖9　節點平均效用隨服務功能鏈數變化情況Fig. 9　Mean utility of nodes changes with the number of service function chains

3.3　性能分析

圖4和圖5反映了隨著網絡節點數和網絡中服務功能鏈數增多時不同算法的服務功能鏈構建時間變化情況，可以看到，NUM在構建時間上明顯少于其他兩種方法，其算法采用分層式的結構降低了模型求解的復雜度，更利于最優解的尋找；圖6和圖7反映了網絡節點數和網絡中服務功能鏈數與服務功能鏈構建成功率之間的關系，可以看到，隨著節點數和服務功能鏈數的增多，構建成功率呈下降趨勢，但是NUM方法構建成功率仍高于其他兩種算法，這是因為構建成功率取決于解的優異性，而本文TS-CSA算法尋找到的最優解優于其他方法；圖8反映了網絡中服務功能鏈數與網絡擁塞率之間的關系，可以看出服務功能鏈數和擁塞率成正比，但采用NUM擁塞率較低，負載均衡性能優于其他兩種方法，因為該方法在網絡中所選的節點優于其他方法，能夠避免節點擁塞；而圖9反映了網絡中服務功能鏈數與節點平均效用之間的關系，可以看出本文方法明顯提升了節點的效用(約20%)，因為該方法可以在全網范圍內找到最優節點并進行資源最大化利用，能達到節點效用最優。

4　結語

本文主要解決了SDN+NFV環境下的服務功能鏈構建問題。首先，對SDN+NFV環境下的服務功能鏈構建問題進行詳細描述，分析了影響SFCCP的主要因素；然后介紹了本文所設計的服務功能鏈構建機制，分別建立了最優化節點選擇模型和最大效能模型，并利用禁忌搜索改進模擬退火算法對模型進行求解；最后，對比測試了在網絡節點和服務功能鏈數增多的情況下，不同算法的服務功能鏈構建時間、構建成功率和網絡擁塞率的變化以及采用本文方法在節點效用上的提升，結果表明本文方法具有明顯優勢。下一步的研究主要集中在節點數及服務功能鏈數增多時如何進一步提高構建服務功能鏈的成功率，以及如何對過載的服務器虛擬機進行遷移來達到網絡中負載均衡的目的。

參考文獻:

[1]GEMBER A, PRABHU P, GHADIYALI Z, et al. Toward software-defined middlebox networking [C]// HotNets-XI: Proceedings of the 2012 11th ACM Workshop on Hot Topics in Networks. New York: ACM, 2012: 7-12.

[2]SHERRY J, HASAN S, SCOTT C, et al. Making middleboxes someone else’s problem: network processing as a cloud service [J]. ACM SIGCOMM Computer Communication Review — Special October issue SIGCOMM ’12, 2012, 42(4): 13-24.

[3]McKEOWN N. Software-defined networking [J]. INFOCOM Keynote Talk, 2009, 17(2): 30-32.

[4]CARAPINHA J, JIMéNEZ J. Network virtualization: a view from the bottom [C]// VISA ’09: Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 73-80.

[5]ZHANG Y, BEHESHTI N, BELIVEAU L, et al. StEERING: a software-defined networking for inline service chaining [C]// ICNP 2013: Proceedings of the 2013 21st IEEE International Conference on Network Protocols. Piscataway, NJ: IEEE, 2013: 1-10.

[6]QAZI Z A, TU C-C, CHIANG L, et al. SIMPLE-fying middlebox policy enforcement using SDN [C]// SIGCOMM ’13: Proceedings of the ACM SIGCOMM 2013 Computer Communication. New York: ACM, 2013: 27-38.

[7]FAYAZBAKHSH S K, SEKAR V, YU M, et al. FlowTags: enforcing network-wide policies in the presence of dynamic middlebox actions [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 19-24.

[8]SEKAR V, EGI N, RATNASAMY S, et al. Design and implementation of a consolidated middlebox architecture [C]// NSDI’12: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 24.

[9]MARTINS J, AHMED M, RAICIU C, et al. ClickOS and the art of network function virtualization [C]// NSDI’14: Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 459-473.

[10]GEMBER-JACOBSON A, VISWANATHAN R, PRAKASH C, et al. OpenNF: Enabling innovation in network function control [C]// SIGCOMM ’14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM, 2014: 163-174.

[11]ANWER B, BENSON T, FEAMSTER N, et al. A slick control plane for network middleboxes [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 147-148.

[12]ANWER B, BENSON T, FEAMSTER N, et al. Programming slick network functions [C]// SOSR ’15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research. New York: ACM, 2015: Article No. 14.

[13]KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671-680.

[14]GLOVER F, LAGUNA M. Tabu search [M]// Metaheuristic Procedures for Training Neutral Networks. Boston: Springer, 1993: 53-69.

[15]秦進,倪玲霖,繆立新.多級多商品流物流網絡設計的優化模型與組合模擬退火算法[J].計算機應用研究,2010,27(9):3348-3351. (QIN J, NI L L, MIU L X. Optimization model and combined simulated annealing algorithm for multi-level multi-commodity logistics network design [J]. Application Research of Computers, 2010, 27(9): 3348-3351.)

[16]LIN Y, BIAN Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing Tabu search algorithm to solve the symmetrical traveling salesman problem [J]. Applied Soft Computing, 2016, 49(C): 937-952.

[17]METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines [J]. The Journal of Chemical Physics, 1953, 21(6): 1087-1092.

[18]ZEGURA E W, CALVERT K L, ACHARJEE S B. How to model an internetwork [C]// INFOCOM’96: Proceedings of the Fifteenth Annual Joint Conference of the IEEE Computer Societies on Networking the Next Generation. Washington, DC: IEEE Computer Society, 1996, 2: 594-602.