基于SFC的業(yè)務(wù)路徑選擇算法

朱永慶，龔霞，陳華南

?

基于SFC的業(yè)務(wù)路徑選擇算法

朱永慶，龔霞，陳華南

（中國(guó)電信股份有限公司廣州研究院，廣東廣州 510630）

產(chǎn)業(yè)界正在推進(jìn)SFC（service function chain，業(yè)務(wù)鏈）技術(shù)發(fā)展，以實(shí)現(xiàn)云網(wǎng)融合的新型業(yè)務(wù)部署模式。業(yè)務(wù)路徑選擇策略是業(yè)務(wù)鏈的核心技術(shù)，直接影響網(wǎng)絡(luò)性能與業(yè)務(wù)體驗(yàn)。針對(duì)現(xiàn)有業(yè)務(wù)路徑選擇策略存在的單一目標(biāo)缺陷，創(chuàng)新提出并仿真驗(yàn)證了一種基于時(shí)延和負(fù)載的最小權(quán)重法，優(yōu)化網(wǎng)絡(luò)資源分配，提升業(yè)務(wù)鏈處理性能，為運(yùn)營(yíng)商未來(lái)網(wǎng)絡(luò)和資源部署提供技術(shù)參考。

業(yè)務(wù)鏈；業(yè)務(wù)路徑；網(wǎng)絡(luò)時(shí)延；網(wǎng)絡(luò)負(fù)載

1 引言

SDN/NFV技術(shù)的應(yīng)用促使互聯(lián)網(wǎng)向異構(gòu)網(wǎng)絡(luò)演進(jìn)，虛擬化網(wǎng)元將成為主流，如何實(shí)現(xiàn)靈活業(yè)務(wù)模式成為焦點(diǎn)[1,2]。同時(shí)上層應(yīng)用提出靈活調(diào)用網(wǎng)絡(luò)能力的迫切需求，以提供靈活的業(yè)務(wù)選擇。在此背景下，業(yè)務(wù)鏈（service function chain，SFC）應(yīng)運(yùn)而生[3]，并迅速成為產(chǎn)業(yè)界各方的研究投入方向。業(yè)務(wù)鏈可按照用戶需求，靈活地使用戶流量按序通過相應(yīng)的網(wǎng)絡(luò)功能（service function，SF）單元進(jìn)行處理，以實(shí)現(xiàn)用戶不同流量的處理目標(biāo)。基于集中式控制理念，業(yè)務(wù)鏈可實(shí)現(xiàn)網(wǎng)絡(luò)資源整合和共享，支持端到端的網(wǎng)絡(luò)業(yè)務(wù)編排功能，從而實(shí)現(xiàn)一體化業(yè)務(wù)提供，極大地提高業(yè)務(wù)功能部署的靈活性及快捷性。

業(yè)務(wù)鏈實(shí)現(xiàn)方案涉及業(yè)務(wù)鏈封裝格式、業(yè)務(wù)鏈組網(wǎng)拓?fù)?、業(yè)務(wù)路徑（service function path，SFP）選擇策略等關(guān)鍵技術(shù)，其中業(yè)務(wù)路徑選擇策略直接影響網(wǎng)絡(luò)的處理效率，得到廣泛關(guān)注。目前業(yè)務(wù)路徑選擇策略主要包括網(wǎng)絡(luò)時(shí)延最小算法[4]、負(fù)載均衡算法[5,6]等，其中參考文獻(xiàn)[4]給出了一種業(yè)務(wù)鏈中權(quán)衡網(wǎng)絡(luò)端到端時(shí)延和VNF（virtualization network function）資源利用率的方法，在減少網(wǎng)絡(luò)時(shí)延的同時(shí)，降低建網(wǎng)成本，但是這種方式?jīng)]有考慮網(wǎng)絡(luò)負(fù)載等因素，在網(wǎng)絡(luò)流量較大的情況下，易造成網(wǎng)絡(luò)擁塞，降低用戶體驗(yàn)；參考文獻(xiàn)[5]提出了一種負(fù)載均衡的業(yè)務(wù)路徑選擇方法，通過線性處理業(yè)務(wù)鏈中SF負(fù)載情況，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載分擔(dān)。但是此算法采用單一目標(biāo)和逐跳最優(yōu)的選路方式實(shí)現(xiàn)，導(dǎo)致網(wǎng)絡(luò)時(shí)延增加。針對(duì)上述分析，為了提高業(yè)務(wù)鏈系統(tǒng)業(yè)務(wù)處理性能，需考慮網(wǎng)絡(luò)中多個(gè)尺度因素對(duì)網(wǎng)絡(luò)性能的影響。但是另一方面又會(huì)增加算法復(fù)雜度，給網(wǎng)絡(luò)帶來(lái)計(jì)算和存儲(chǔ)負(fù)擔(dān)。綜合考慮網(wǎng)絡(luò)性能和算法復(fù)雜度，本文基于業(yè)務(wù)鏈架構(gòu)及關(guān)鍵技術(shù)研究，提出了一種新型業(yè)務(wù)鏈業(yè)務(wù)路徑選擇算法，同時(shí)考慮時(shí)延和負(fù)載因素，提升算法的普適性與實(shí)用性，并通過仿真驗(yàn)證了其實(shí)現(xiàn)效果，為后續(xù)業(yè)務(wù)鏈部署提供技術(shù)基礎(chǔ)。

2 業(yè)務(wù)鏈技術(shù)總體架構(gòu)

業(yè)務(wù)鏈架構(gòu)[7]如圖1所示，主要功能組件包括業(yè)務(wù)鏈編排器、業(yè)務(wù)鏈控制器、策略控制器、業(yè)務(wù)功能控制器、流分類器、業(yè)務(wù)功能轉(zhuǎn)發(fā)（service function forwarder，SFF）節(jié)點(diǎn)及SF等[8]。

業(yè)務(wù)鏈編排器將業(yè)務(wù)鏈服務(wù)所需的基礎(chǔ)資源預(yù)置傳遞至控制器，包括流分類器、SFF和SF的預(yù)置及基礎(chǔ)配置。業(yè)務(wù)鏈控制器主要實(shí)現(xiàn)業(yè)務(wù)鏈特性的網(wǎng)絡(luò)控制功能，包括業(yè)務(wù)鏈所需的overlay網(wǎng)絡(luò)管理及業(yè)務(wù)鏈路徑計(jì)算和流表下發(fā)等功能。策略控制器根據(jù)用戶的指令制定相關(guān)的業(yè)務(wù)鏈策略，負(fù)責(zé)把流量的分類策略下發(fā)到流分類器。業(yè)務(wù)功能控制器主要實(shí)現(xiàn)對(duì)業(yè)務(wù)功能的管理和資源配置。流分類器根據(jù)策略控制器下發(fā)的策略，對(duì)進(jìn)入業(yè)務(wù)鏈的業(yè)務(wù)流量進(jìn)行分類和標(biāo)識(shí)。SFF是服務(wù)功能轉(zhuǎn)發(fā)模塊，主要功能包括對(duì)業(yè)務(wù)報(bào)文的封裝和解封裝、實(shí)現(xiàn)對(duì)業(yè)務(wù)處理的順序執(zhí)行。SF為服務(wù)功能單元，提供相應(yīng)的網(wǎng)絡(luò)增值業(yè)務(wù)。

業(yè)務(wù)鏈中流量分類的顆粒度可根據(jù)設(shè)備能力、客戶要求和提供的服務(wù)而有所不同。流分類器對(duì)流量進(jìn)行分類并確定需經(jīng)過的業(yè)務(wù)功能鏈，另外在給定的業(yè)務(wù)鏈中可以通過后續(xù)流量分類來(lái)改變應(yīng)用的業(yè)務(wù)功能的順序。同時(shí)對(duì)稱流量分類可確保正向和反向業(yè)務(wù)處理，類似地，也可以通過流量分類實(shí)現(xiàn)相對(duì)于所需業(yè)務(wù)功能鏈的非對(duì)稱性[3]。目前，業(yè)務(wù)鏈中還沒有成型的流量分類相關(guān)標(biāo)準(zhǔn)，但業(yè)界實(shí)現(xiàn)網(wǎng)絡(luò)流量分類的方法相對(duì)成熟，可根據(jù)需要參考采用深度分組檢測(cè)或機(jī)器學(xué)習(xí)等方法實(shí)現(xiàn)。

業(yè)務(wù)鏈實(shí)現(xiàn)流程如下：

?? 流分類器對(duì)進(jìn)入業(yè)務(wù)鏈的流量進(jìn)行分類，確定所需經(jīng)過的有序SF單元集合；

?? 按照所需經(jīng)過的有序SF集合，基于特定的業(yè)務(wù)路徑選擇策略確定相應(yīng)的有序SFF集合；

?? 流量依次經(jīng)過這些SFF，實(shí)現(xiàn)業(yè)務(wù)的處理。

SFF部署有多種組網(wǎng)模式，包括串型、星型及分布式串型等[9]。業(yè)務(wù)路徑選擇與網(wǎng)絡(luò)拓?fù)錈o(wú)關(guān)，可滿足所有業(yè)務(wù)鏈組網(wǎng)模型。業(yè)務(wù)路徑選擇算法研究將以隨機(jī)生成的網(wǎng)絡(luò)組網(wǎng)架構(gòu)模型為例，進(jìn)行算法和仿真分析，業(yè)務(wù)鏈組網(wǎng)模型如圖2所示。

3 基于時(shí)延和負(fù)載的最小權(quán)重法

由于SFF之間的時(shí)延與距離成正比，可用SFF節(jié)點(diǎn)之間的距離大小表示時(shí)延的高低。基于圖2所示的網(wǎng)絡(luò)模型，結(jié)合網(wǎng)絡(luò)中節(jié)點(diǎn)間的傳輸距離和網(wǎng)絡(luò)功能單元的負(fù)載狀態(tài)，提出了一種計(jì)算網(wǎng)絡(luò)鏈路權(quán)值方法。

其中，w為鏈路權(quán)值，其中，為當(dāng)前SF單元，為下一跳的SF單元，為所在的SFF單元，為所在的SFF單元，D為與之間的傳輸距離，max為與具有的SFF之間的最大傳輸距離，l為中的現(xiàn)有負(fù)載，L為中的最大負(fù)載，和為系數(shù)，并且+1。和的取值可根據(jù)網(wǎng)絡(luò)優(yōu)化指標(biāo)的側(cè)重點(diǎn)來(lái)定義，如傳輸時(shí)延和負(fù)載同樣重要時(shí)，可令=0.5。

針對(duì)上述計(jì)算的網(wǎng)絡(luò)鏈路權(quán)值，用戶按照業(yè)務(wù)需求，計(jì)算所有經(jīng)過所需網(wǎng)絡(luò)功能單元的業(yè)務(wù)路徑權(quán)值之和，即每條可選業(yè)務(wù)路徑的權(quán)重，并選擇一條權(quán)重最小的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)和處理。

算法流程如圖3所示。

圖3 基于時(shí)延和負(fù)載的最小權(quán)重算法流程

算法流程如下所示：

?? 流分類器對(duì)網(wǎng)絡(luò)流量進(jìn)行分類，并得到所需經(jīng)過的業(yè)務(wù)功能的順序：{}={1,2,…,f}；

?? 計(jì)算網(wǎng)絡(luò)中每條鏈路（任意兩個(gè)SF之間的）的權(quán)值w；

?? 按照{(diào)}集合中的業(yè)務(wù)功能順序，計(jì)算每條依次經(jīng)過這些網(wǎng)絡(luò)功能單元的路徑權(quán)值之和；

?? 選擇擁有最小權(quán)重min的業(yè)務(wù)路徑作為所選方案。

4 仿真分析

為了驗(yàn)證本文所提的基于時(shí)延和負(fù)載的最小權(quán)重算法的優(yōu)勢(shì)，以時(shí)延最小算法和負(fù)載最小算法為對(duì)比，對(duì)3種算法進(jìn)行了仿真。3種算法都以整條鏈路性能參數(shù)為指標(biāo)進(jìn)行仿真，且為了避免偶然性，共仿真了10次。設(shè)置參數(shù)見表1。

表1 仿真設(shè)置參數(shù)

網(wǎng)絡(luò)中所有的流量都通過流分類器進(jìn)入業(yè)務(wù)鏈，假設(shè)流分類器的編號(hào)為101，SF編號(hào)為[1,2,…,10]，SFF編號(hào)為[1,2,…,100]。以第10次仿真結(jié)果為例，流量所需經(jīng)過的業(yè)務(wù)功能單元順序?yàn)椋簕} ={8,9,1,4,7}，通過仿真得到3種算法的所選的業(yè)務(wù)路徑，具體見表2和圖4。圖4中，沒有規(guī)定網(wǎng)格大小，因此橫縱坐標(biāo)只是示意網(wǎng)絡(luò)距離。

表2 3種算法業(yè)務(wù)路徑

仿真中定義SF的負(fù)載狀態(tài)為其處理能力占比，單個(gè)SF的負(fù)載為介于0和1之間的百分?jǐn)?shù)，定義傳輸時(shí)延為每跳數(shù)據(jù)傳輸所需時(shí)延。網(wǎng)絡(luò)中所選業(yè)務(wù)路徑的總負(fù)載為路徑中所有SF負(fù)載之和；所選業(yè)務(wù)路徑的總時(shí)延即業(yè)務(wù)路徑中每跳數(shù)據(jù)傳輸時(shí)延之和。從圖4可看出，最小時(shí)延算法所選業(yè)務(wù)路徑最短，最小負(fù)載算法所選業(yè)務(wù)路徑最長(zhǎng)，而基于時(shí)延和負(fù)載的最小權(quán)重法中，越大，越側(cè)重于時(shí)延因素，所選業(yè)務(wù)路徑越短。這是因?yàn)榛谪?fù)載最小的業(yè)務(wù)路徑選擇算法僅僅考慮網(wǎng)絡(luò)功能單元的負(fù)載，從而帶來(lái)了時(shí)延上的代價(jià)。下面對(duì)10次仿真結(jié)果進(jìn)行分析，分別了對(duì)比了3種算法的鏈路總時(shí)延和鏈路總負(fù)載情況，具體如圖5、圖6所示。

如圖5、圖6所示，在10次仿真過程中，時(shí)延最小算法的網(wǎng)絡(luò)時(shí)延都是最小的，但是鏈路的總負(fù)載則相對(duì)很大；相反，負(fù)載最小算法的網(wǎng)絡(luò)負(fù)載都是最小的，但是鏈路的總時(shí)延卻很大。而基于時(shí)延和負(fù)載的最小權(quán)重法得到的網(wǎng)絡(luò)時(shí)延和負(fù)載雖不是最小，但卻不會(huì)出現(xiàn)一方很大的情況，兩者都在可接受的范圍內(nèi)。這是由于基于時(shí)延和負(fù)載的最小權(quán)重法同時(shí)考慮了網(wǎng)絡(luò)時(shí)延和負(fù)載的情況，權(quán)衡了兩者的影響而選擇折中的方案。網(wǎng)絡(luò)中具體SFF的選取也與和的取值有關(guān)，越大、越小，所選業(yè)務(wù)路徑網(wǎng)絡(luò)時(shí)延越小，負(fù)載則相對(duì)越大。

仿真結(jié)果表明，基于時(shí)延和負(fù)載的業(yè)務(wù)路徑選擇方案，通過選擇網(wǎng)絡(luò)鏈路總代價(jià)最小的業(yè)務(wù)路徑，實(shí)現(xiàn)業(yè)務(wù)鏈端到端鏈路的靈活選擇，降低網(wǎng)絡(luò)時(shí)延，達(dá)到負(fù)載均衡，優(yōu)化業(yè)務(wù)處理性能。

5 結(jié)束語(yǔ)

業(yè)務(wù)鏈?zhǔn)俏磥?lái)網(wǎng)絡(luò)業(yè)務(wù)承載的終極目標(biāo)，其核心要素研究處在百家爭(zhēng)鳴階段，不斷推動(dòng)業(yè)務(wù)鏈發(fā)展?，F(xiàn)階段，暫無(wú)成熟可用的商用產(chǎn)品，標(biāo)準(zhǔn)組織和開源組織進(jìn)行了實(shí)驗(yàn)室概念驗(yàn)證。目前所提出基于時(shí)延和負(fù)載的最小權(quán)重算法，可提高網(wǎng)絡(luò)處理性能，對(duì)運(yùn)營(yíng)部署具有參考意義。后續(xù)將結(jié)合業(yè)務(wù)鏈封裝技術(shù)、業(yè)務(wù)鏈控制和編排等技術(shù)進(jìn)一步優(yōu)化算法，提升其實(shí)用性。

[1] 韋樂平. SDN的戰(zhàn)略性思考[J]. 電信科學(xué), 2015, 31(1): 7-12.

WEI L P. Strategic thinking on SDN [J]. Telecommunications Science, 2015, 31(1): 7-12.

[2] 何曉明,冀暉,毛東峰,等. 電信IP網(wǎng)向SDN演進(jìn)的探討[J]. 電信科學(xué), 2014, 30(6): 131-137.

HE X M,JI H,MAO D F, et al. Discussion of evolution of carrier IP network to SDN [J]. Telecommunications Science, 2014, 30(6): 131-137.

[3] IETF. Problem statement for service function chaining: RFC7498[S]. 2015.

[4] CHUA F C. Stringer: balancing latency and resource usage in service function chain. provisioning[J]. IEEE Internet Computing, 2016(20): 22-31.

[5] QAZI Z A, TU C C, CHIANG L, et al. SIMPLE-fying middlebox policy enforcement using SDN[C]//ACM SIGCOMM 2013 Conference on SIGCOMM, August 12?16, 2013, Hong Kong, China. New York: ACM Press, 2013: 27-38.

[6] SONG W E, JUNG S H. Load balance system for the sfc based DLP solution[J]. The Journal of Korean Institute of Communications and Information Sciences, 2016, 41(4): 451-453.

[7] HALPERN E J, PIGNATARO E C. Service function chaining (SFC) architecture[J]. 2015.

[8] 楊紹光, 王翔, 賈智宇. 基于SDN和NFV的業(yè)務(wù)鏈管理系統(tǒng)研究[J]. 信息通信技術(shù), 2016, 10(2): 23-27.

YANG S G, WANG X, JIA Z Y. Research of service chaining based on SDN and NFV[J]. Information and Communications Technologies, 2016, 10(2): 23-27.

[9] 唐宏, 羅雨佳. NFV業(yè)務(wù)鏈資源分配技術(shù)[J]. 電信科學(xué), 2015, 31(11): 143-148.

TANG H, LUO Y J. NFV service chain resource allocation technology[J]. Telecommunications Science, 2015, 31(11): 143-148.

SFP selection algorithm for SFC

ZHU Yongqing, GONG Xia, CHEN Huanan

Guangzhou Research Institute of China Telecom Co., Ltd., Guangzhou 510630, China

In order to achieve the new business deployment model by the convergence of cloud and network, SFC technology has been promoted greatly. As one of the key technologies in SFC, the SFP selection strategy affects the network performance and business experience directly. Aiming at the single target defect existing in business path selection strategy, the minimum weight algorithm based on the network delay and load was proposed and simulated. It could optimize the resources allocation and improve the network performance. A technical reference was provided for the operators to deploy the network and resources in the future.

service function chain, service function path, network delay, network load

TN919

A

10.11959/j.issn.1000?0801.2017111

2017?03?10；

2017?04?18

朱永慶（1974?），男，中國(guó)電信股份有限公司廣州研究院高級(jí)工程師，主要從事網(wǎng)絡(luò)新技術(shù)、SDN/NFV技術(shù)及5G技術(shù)的研究工作。

龔霞（1991?），女，現(xiàn)就職于中國(guó)電信股份有限公司廣州研究院，主要從事新IP網(wǎng)絡(luò)技術(shù)、SDN及業(yè)務(wù)鏈技術(shù)和5G相關(guān)技術(shù)研究工作。

陳華南（1981?），男，中國(guó)電信股份有限公司廣州研究院工程師，主要從事新IP網(wǎng)絡(luò)技術(shù)、SDN/NFV技術(shù)及5G技術(shù)研究工作等。