用戶QoS與網(wǎng)絡(luò)資源感知的服務(wù)功能鏈部署方法

崔雅君，李 華，阮宏瑋，許 彤，王顯榮

(內(nèi)蒙古大學(xué) 計(jì)算機(jī)學(xué)院，呼和浩特 010020)

1 引 言

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和云應(yīng)用技術(shù)的發(fā)展，運(yùn)營(yíng)商希望可以自動(dòng)化的為客戶提供更多的服務(wù)，從各類資源的供給到資源的彈性伸縮，提高運(yùn)維的自動(dòng)化，并支撐業(yè)務(wù)生態(tài)系統(tǒng)的進(jìn)化.網(wǎng)絡(luò)功能虛擬化(NFV)與軟件定義網(wǎng)絡(luò)(SDN)的協(xié)同應(yīng)用為云數(shù)據(jù)中心運(yùn)營(yíng)商提供了自動(dòng)化管理云數(shù)據(jù)中心存儲(chǔ)、計(jì)算資源的工具，實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)服務(wù)的靈活管理和高效利用.服務(wù)提供商為了滿足用戶的動(dòng)態(tài)需求，選擇將虛擬服務(wù)功能按照一定邏輯順序進(jìn)行合理鏈接并部署在物理網(wǎng)絡(luò)上提供完整的端到端服務(wù).這種將網(wǎng)絡(luò)中兩個(gè)或多個(gè)服務(wù)功能(SF)互連，為應(yīng)用驅(qū)動(dòng)的網(wǎng)絡(luò)提供支持的技術(shù)被稱為服務(wù)功能鏈(SFC).SFC適應(yīng)各種網(wǎng)絡(luò)場(chǎng)景，如：電信運(yùn)營(yíng)商網(wǎng)絡(luò)(TSP)、物理網(wǎng)絡(luò)功能與虛擬網(wǎng)絡(luò)功能共存的混合NFV網(wǎng)絡(luò)以及云網(wǎng)絡(luò)等為用戶提供指定的網(wǎng)絡(luò)服務(wù)，處理用戶請(qǐng)求產(chǎn)生的大量流量[1].

盡管SFC使得服務(wù)模式變得更加靈活和經(jīng)濟(jì)，目前也有一些關(guān)于SFC部署方法的研究，但多從如何降低運(yùn)營(yíng)商的運(yùn)營(yíng)成本及資源利用率等考慮問(wèn)題，忽略了對(duì)用戶QoS體驗(yàn)的考慮，或者對(duì)用戶QoS維度的考慮較為單一，導(dǎo)致用戶的體驗(yàn)并不理想.在目前服務(wù)市場(chǎng)競(jìng)爭(zhēng)非常激烈的情形下，可能導(dǎo)致用戶的流失.因此需要深入的分析SFC的部署問(wèn)題及其現(xiàn)有解決方法，從更多維度考慮用戶的QoS需求研究SFC的部署方法.

2 相關(guān)工作

云計(jì)算及網(wǎng)絡(luò)功能虛擬化的快速發(fā)展，使得傳統(tǒng)以終端為中心的網(wǎng)絡(luò)服務(wù)模型正在向以數(shù)據(jù)為中心的動(dòng)態(tài)網(wǎng)絡(luò)服務(wù)模型以及以云計(jì)算為核心的邊緣計(jì)算服務(wù)模型轉(zhuǎn)變.為了實(shí)現(xiàn)服務(wù)部署的靈活性，運(yùn)行商開(kāi)始基于虛擬網(wǎng)絡(luò)功能進(jìn)行服務(wù)功能鏈的部署.因此，SFC部署問(wèn)題已經(jīng)成為近年來(lái)國(guó)內(nèi)外的研究熱點(diǎn).SFC部署問(wèn)題可概述為在網(wǎng)絡(luò)中尋找服務(wù)的最佳放置位置，也即服務(wù)如何映射到物理網(wǎng)絡(luò)的可用資源上.可利用優(yōu)化理論將其規(guī)約為多約束條件下求解SFC優(yōu)化部署的問(wèn)題，此類問(wèn)題現(xiàn)已被證明是NP-Hard問(wèn)題[2]，也即在NP≠P的條件下，如果要使目標(biāo)函數(shù)在多項(xiàng)式時(shí)間內(nèi)獲得可行解，需要通過(guò)應(yīng)用精確、啟發(fā)式或元啟發(fā)式算法進(jìn)行解決.但是在采用精確算法方面，Moen等將服務(wù)功能的資源映射建模成了整數(shù)線性規(guī)劃問(wèn)題(ILP)進(jìn)行求解[3]，但該方法僅在網(wǎng)絡(luò)規(guī)模較小時(shí)適用，在大規(guī)模網(wǎng)絡(luò)中可能會(huì)產(chǎn)生組合爆炸帶來(lái)較高的運(yùn)行成本.因而目前研究提出的算法大多是啟發(fā)式或元啟發(fā)式的.如文獻(xiàn)[4]提出了一種可擴(kuò)展的啟發(fā)式方法CoordVNF，該方法能夠在合理的運(yùn)行時(shí)間內(nèi)解決服務(wù)的放置及資源分配問(wèn)題，同時(shí)該方法可擴(kuò)展應(yīng)用到較大規(guī)模的網(wǎng)絡(luò)場(chǎng)景中.但是這些研究?jī)H考慮了運(yùn)營(yíng)商的運(yùn)營(yíng)成本，未考慮提供給用戶的服務(wù)質(zhì)量問(wèn)題，這可能會(huì)使提供的服務(wù)不能滿足用戶服務(wù)需求從而影響服務(wù)鏈的部署.還有一些研究雖考慮了用戶體驗(yàn)，但是未能考慮用戶對(duì)服務(wù)更多維度的QoS需求.如：文獻(xiàn)[5，6]考慮了時(shí)延問(wèn)題，將服務(wù)鏈映射問(wèn)題建模成了整數(shù)線性規(guī)劃(ILP)問(wèn)題進(jìn)行求解，同時(shí)作者還提出了一種基于Viterbi的啟發(fā)式算法處理ILP的復(fù)雜性.文獻(xiàn)[7]研究了SFC部署對(duì)用戶服務(wù)水平協(xié)議(SLA)的影響，提出了一種啟發(fā)式算法使得部署的SFC能耗及負(fù)載最小，也即通過(guò)降低服務(wù)器能耗保證用戶體驗(yàn).文獻(xiàn)[8]提出了一種基于強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法，解決了動(dòng)態(tài)場(chǎng)景下服務(wù)功能與資源的映射問(wèn)題，該算法有效降低了業(yè)務(wù)的平均傳輸時(shí)延，提升了系統(tǒng)的負(fù)載均衡性能.文獻(xiàn)[9]考慮了SFC部署對(duì)時(shí)延敏感型用戶服務(wù)體驗(yàn)的影響，提出了一種以最小化SFC延遲為目標(biāo)的啟發(fā)式方法來(lái)部署SFC.文獻(xiàn)[10]以最小化運(yùn)營(yíng)商代價(jià)為目標(biāo)，考慮了服務(wù)時(shí)延以及資源可用性.文獻(xiàn)[11]提出了一種MILP模型和一種啟發(fā)式算法BACON，通過(guò)最小化服務(wù)功能間的通信延遲來(lái)提高QoS.文獻(xiàn)[12]構(gòu)建了一個(gè)虛擬功能干擾度評(píng)估模型，提出了考慮虛擬功能間干擾的部署算法，將求解干擾度最小化問(wèn)題轉(zhuǎn)換為多目標(biāo)優(yōu)化問(wèn)題并利用模擬退火算法進(jìn)行求解，提高了服務(wù)鏈的執(zhí)行性能.文獻(xiàn)[13]在部署虛擬網(wǎng)絡(luò)功能時(shí)考慮了提供給用戶的服務(wù)質(zhì)量問(wèn)題，并采用啟發(fā)式的貪心算法求解.

為了更好的比較現(xiàn)有方法，表1按解決方法，優(yōu)化目標(biāo)，評(píng)價(jià)指標(biāo)以及是否考慮QoS等條目對(duì)現(xiàn)有工作進(jìn)行了總結(jié).

表1 現(xiàn)有SFC部署方法

從上述工作看SFC的部署策略大多考慮了運(yùn)營(yíng)商的運(yùn)營(yíng)成本以及節(jié)點(diǎn)資源利用率等問(wèn)題，但對(duì)提供給用戶服務(wù)質(zhì)量的考量較為單一，如：僅考慮了服務(wù)時(shí)延.但事實(shí)上，QoS是各種存在服務(wù)供需關(guān)系的場(chǎng)合中普遍存在的概念，用于評(píng)估服務(wù)方滿足客戶服務(wù)需求的能力[14].在目前市場(chǎng)競(jìng)爭(zhēng)如此激烈的情況下，運(yùn)營(yíng)商要保證在市場(chǎng)中的競(jìng)爭(zhēng)力，其提供的服務(wù)必須滿足用戶需求，否則此次部署的服務(wù)就是失敗的.因此，本文在研究SFC部署時(shí)要著重解決的關(guān)鍵問(wèn)題就是保證運(yùn)營(yíng)商提供的服務(wù)是滿足用戶QoS要求的.相比于目前SFC部署工作中不考慮或僅考慮服務(wù)時(shí)延的單維度的QoS參數(shù)，本文進(jìn)一步考慮了影響用戶體驗(yàn)的服務(wù)時(shí)延、服務(wù)可用性、鏈路丟包及鏈路擁塞多個(gè)維度的QoS參數(shù)，并且探索了新的方法旨在保證用戶多維度需求的同時(shí)使運(yùn)營(yíng)商的成本代價(jià)最小.

3 問(wèn)題描述

軟件定義網(wǎng)絡(luò)和網(wǎng)絡(luò)功能虛擬化的不斷發(fā)展，使得運(yùn)營(yíng)商對(duì)數(shù)據(jù)中心的網(wǎng)絡(luò)管理更加的高效和靈活.SFC是云數(shù)據(jù)中心構(gòu)建基于網(wǎng)絡(luò)的安全高效服務(wù)的基礎(chǔ)關(guān)鍵步驟之一，在SDN網(wǎng)絡(luò)中，控制器需要根據(jù)用戶的需求制定部署策略來(lái)構(gòu)建服務(wù)鏈，同時(shí)部署服務(wù)鏈上每個(gè)節(jié)點(diǎn)的業(yè)務(wù)邏輯.

3.1 部署模型

運(yùn)營(yíng)商及服務(wù)商多通過(guò)SLA體現(xiàn)為用戶提供的服務(wù)質(zhì)量.本文的服務(wù)鏈部署目標(biāo)是在網(wǎng)絡(luò)資源有限的情況下，運(yùn)營(yíng)商仍能保證用戶與之簽訂的SLA中規(guī)定的QoS，同時(shí)使運(yùn)營(yíng)商的代價(jià)最低，涉及的QoS參數(shù)主要包括服務(wù)時(shí)延及服務(wù)可用性等網(wǎng)絡(luò)性能指標(biāo).

為了更加直觀的描述待解決的問(wèn)題，本文給出如圖1所示的部署模型，示意部署工作的輸入及輸出.

圖1 部署模型

圖1中的用戶QoS需求由SLA中規(guī)定的關(guān)鍵性指標(biāo)表示，如：在高可用網(wǎng)絡(luò)中服務(wù)時(shí)延不得超過(guò)150ms，包的丟失率小于1%等.SLA是用于評(píng)價(jià)SFC成功部署的關(guān)鍵指標(biāo)，若不滿足約定，則部署失敗.網(wǎng)絡(luò)資源約束表示當(dāng)前部署SFC的網(wǎng)絡(luò)拓?fù)洵h(huán)境，由有限的節(jié)點(diǎn)資源、鏈路資源、帶寬資源等體現(xiàn).

SFC構(gòu)建策略根據(jù)業(yè)務(wù)需求及應(yīng)用場(chǎng)景組合虛擬網(wǎng)絡(luò)功能，形成邏輯上的服務(wù)功能鏈，如圖2所示.SFC部署策略基于SDN控制器獲取全局網(wǎng)絡(luò)視圖，根據(jù)已得到的邏輯服務(wù)鏈路、網(wǎng)絡(luò)資源約束和用戶QoS需求為每個(gè)虛擬網(wǎng)絡(luò)功能找到在物理鏈路中最佳的放置位置，得到一條實(shí)例化的服務(wù)路徑.

圖2 服務(wù)鏈的構(gòu)建

實(shí)例化的服務(wù)鏈為視頻會(huì)議、網(wǎng)絡(luò)購(gòu)物等利用網(wǎng)絡(luò)作為數(shù)據(jù)傳輸平臺(tái)的業(yè)務(wù)提供服務(wù)，運(yùn)營(yíng)商需要基于業(yè)務(wù)特點(diǎn)與用戶簽訂協(xié)議以提供滿足用戶要求的服務(wù).如視頻會(huì)議以及視頻點(diǎn)播等業(yè)務(wù)需要滿足用戶對(duì)低延遲和低抖動(dòng)等傳輸性能的需求.但是網(wǎng)絡(luò)規(guī)模以及用戶數(shù)量的不斷增長(zhǎng)降低了SFC部署的成功率，在資源總量能夠滿足需求的情況下，究其原因是現(xiàn)有網(wǎng)絡(luò)不考慮用戶的QoS需求，僅提供“盡力而為”的服務(wù)，考慮的服務(wù)質(zhì)量較少，導(dǎo)致了服務(wù)可用性差，SFC部署的失敗率增高.如果在部署SFC時(shí)，先滿足用戶QoS需求再考慮運(yùn)營(yíng)商部署成本的最小化將會(huì)大大提高SFC部署的成功率.

一般而言用戶服務(wù)質(zhì)量通常用丟包率、延遲和延遲抖動(dòng)3個(gè)參數(shù)來(lái)衡量，只有有效地控制這3個(gè)參數(shù)，才能夠?yàn)橛脩籼峁﹥?yōu)質(zhì)的QoS[15].由此，本文將SFC部署中要解決的關(guān)鍵問(wèn)題定義為在資源受限的網(wǎng)絡(luò)環(huán)境中盡可能多的部署滿足用戶多維度QoS需求的服務(wù)鏈路并且使運(yùn)營(yíng)商的部署代價(jià)最低.

3.2 形式化描述

為了對(duì)本文提出的SFC部署問(wèn)題進(jìn)行求解，需要進(jìn)一步解釋說(shuō)明部署模型中涉及的相關(guān)定義，下面給出網(wǎng)絡(luò)資源和用戶QoS需求的形式化描述.

3.2.1 網(wǎng)絡(luò)資源的形式化描述

現(xiàn)實(shí)中云數(shù)據(jù)中心的資源是有限的且是動(dòng)態(tài)變化的，當(dāng)前網(wǎng)絡(luò)環(huán)境中資源的使用情況對(duì)SFC部署的成功率有很大影響.基于此，本文對(duì)使用的物理網(wǎng)絡(luò)資源情況做了以下描述：

假設(shè)構(gòu)建SFC所需的網(wǎng)絡(luò)功能集為S=，其中SFi表示第i個(gè)服務(wù)功能，1<=i<=n，n表示請(qǐng)求的服務(wù)功能數(shù)量.將一系列虛擬服務(wù)功能組合成的SFC映射到物理網(wǎng)絡(luò)中為用戶提供服務(wù)，也即SFC的服務(wù)路徑SFCpath描述為：SF1→SF2→…→SFn.

P=<，S>表示從源節(jié)點(diǎn)Ns到目的節(jié)點(diǎn)Nt的流量必須經(jīng)過(guò)S描述的服務(wù)功能序列.在此路徑中未部署服務(wù)的節(jié)點(diǎn)僅起到轉(zhuǎn)發(fā)數(shù)據(jù)的作用.

文中涉及的主要參數(shù)及定義如表2所示.

表2 參數(shù)及意義

本文的主要目標(biāo)是滿足用戶QoS需求的同時(shí)，網(wǎng)絡(luò)資源消耗最小.目標(biāo)函數(shù)如式(1)所示.

Min(Rcost)

(1)

本文SFC的部署需要遵守的網(wǎng)絡(luò)資源約束由式(2)-式(4)表示.

ΣCsfi≤TCj

(2)

ΣBsfi≤TBj

(3)

ΣMsfi≤TMj

(4)

式(2)-式(4)表示需要遵守的網(wǎng)絡(luò)資源約束，即當(dāng)前在節(jié)點(diǎn)j部署的服務(wù)所需的計(jì)算資源、存儲(chǔ)資源以及帶寬資源不能超過(guò)節(jié)點(diǎn)j現(xiàn)有的物理資源.

假設(shè)節(jié)點(diǎn)j的可用程度由SFAvailj表示，它由節(jié)點(diǎn)j的物理資源使用情況決定，也即要求節(jié)點(diǎn)j現(xiàn)有的計(jì)算資源、存儲(chǔ)資源和帶寬資源量滿足當(dāng)前服務(wù)的資源需求.在本文中表示為所需資源與現(xiàn)有資源比值的乘積，計(jì)算方法如式(5)所示.

(5)

其中任意一個(gè)子項(xiàng)比值小于1時(shí)，令子項(xiàng)的值為1，否則為0.

服務(wù)鏈路的可用程度由每個(gè)節(jié)點(diǎn)的可用程度共同決定，計(jì)算方法如式(6)所示.

(6)

本文將目標(biāo)函數(shù)定義為最小化的網(wǎng)絡(luò)資源消耗，其求解的關(guān)鍵前提之一是滿足底層資源約束.上文已對(duì)此進(jìn)行了具體的定義，接下來(lái)將對(duì)求解的另一前提進(jìn)行形式化描述.

3.2.2 用戶QoS需求的形式化描述

QoS于業(yè)務(wù)應(yīng)用而言代表用戶對(duì)網(wǎng)絡(luò)服務(wù)的滿意程度，于網(wǎng)絡(luò)而言代表運(yùn)營(yíng)商向用戶提供的服務(wù)參數(shù)指標(biāo)，因此本文將SLA中大多數(shù)用戶較為關(guān)心的服務(wù)時(shí)延及服務(wù)可用性等QoS參數(shù)作為成功部署的關(guān)鍵評(píng)價(jià)指標(biāo)，其中服務(wù)可用性在本文中描述為節(jié)點(diǎn)資源的可用性.服務(wù)的處理時(shí)間與當(dāng)前節(jié)點(diǎn)的可用程度有關(guān)，假設(shè)服務(wù)在理想狀態(tài)下的處理時(shí)延為DSF，本文根據(jù)節(jié)點(diǎn)的可用程度定義SFi在節(jié)點(diǎn)j上的處理時(shí)延為D(Nsfi，j)，計(jì)算方法如式(7)所示.

(7)

當(dāng)SFAvailj≠0時(shí)，SFi在節(jié)點(diǎn)j上的處理時(shí)延D(Nsfi，j)被描述為服務(wù)在理想狀態(tài)下的處理時(shí)延DSF與節(jié)點(diǎn)可用程度SFAvailj的乘積.當(dāng)SFAvailj=0時(shí)，即節(jié)點(diǎn)j不可用時(shí)，SFi在節(jié)點(diǎn)j上的處理時(shí)延D(Nsfi，j)是無(wú)窮大的.

假設(shè)服務(wù)鏈路的時(shí)延開(kāi)銷為DSFC，包括SF間傳輸時(shí)延以及SF的處理時(shí)延，計(jì)算方法如式(8)所示.

DSFC=D((Nsfi，p)，(Nsfi+1，k))+D(Nsfi，j)

(8)

其中D((Nsfi，p)，(Nsfi+1，k))表示承載SFi的節(jié)點(diǎn)p到承載SFi+1的節(jié)點(diǎn)k之間的傳輸時(shí)延.

為了滿足SLA，鏈路中總的時(shí)延開(kāi)銷不能超過(guò)SLA中規(guī)定的時(shí)延QDSFC，如式(9)所示.

(9)

數(shù)據(jù)傳輸過(guò)程中，若數(shù)據(jù)無(wú)法被及時(shí)轉(zhuǎn)發(fā)出去會(huì)造成轉(zhuǎn)發(fā)設(shè)備的緩沖過(guò)載而造成網(wǎng)絡(luò)傳輸性能下降的情況.當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時(shí)，通常會(huì)導(dǎo)致鏈路的丟包率上升，時(shí)延增加，吞吐量下降[16].由此可見(jiàn)網(wǎng)絡(luò)擁塞會(huì)影響當(dāng)前鏈路的吞吐量，同時(shí)也是衡量鏈路負(fù)載性能的重要指標(biāo).

式(10)定義了鏈路的擁塞情況，用于衡量模型的負(fù)載均衡度.

(10)

式(11)定義了當(dāng)前節(jié)點(diǎn)j的緩存.式(12)定義了當(dāng)前路徑的丟包情況.鏈路中丟包率不能超過(guò)SLA中規(guī)定的丟包率QLRSFC，如式(13)所示.

Ncachej=Msfj-Msri

(11)

(12)

LR≤QLRSFC

(13)

本文將用戶的QoS需求刻畫(huà)為用戶對(duì)服務(wù)時(shí)延、服務(wù)可用程度和鏈路丟包率的需求.同時(shí)為保證網(wǎng)絡(luò)服務(wù)的傳輸性能進(jìn)一步提高服務(wù)質(zhì)量還考慮了鏈路的擁塞情況.相比于目前的研究工作，本文從更多維度考慮影響SFC部署成功率的因素.

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

SFC的部署問(wèn)題是一個(gè)多目標(biāo)組合優(yōu)化求最優(yōu)解的問(wèn)題.目前此類問(wèn)題通常采用啟發(fā)式或者元啟發(fā)式方法進(jìn)行求解，但是啟發(fā)式方法可能會(huì)陷入與真實(shí)最優(yōu)解相差很大的局部最優(yōu)中[1]，也即可行解與最優(yōu)解的偏離程度無(wú)法被預(yù)計(jì).而元啟發(fā)式解決方法可以在合理的時(shí)間內(nèi)脫離局部最優(yōu)，提高解的質(zhì)量.目前用到的元啟發(fā)式解決方法有遺傳算法，模擬退火算法等.

4.1 算法的考慮

模擬退火算法(SA)模仿固體退火的過(guò)程[17]，迭代自適應(yīng)的尋找解，多用來(lái)求解多目標(biāo)優(yōu)化問(wèn)題中的最小值問(wèn)題，其求解方法簡(jiǎn)單通用，易于加入約束條件，編寫(xiě)程序簡(jiǎn)單.更重要的是，模擬退火算法能以一定的概率接收相較于當(dāng)前目標(biāo)函數(shù)值較差的解[18]，但是這個(gè)概率會(huì)隨著時(shí)間的推移而降低(逐漸降低才能趨向穩(wěn)定得到終解)，也即理論上經(jīng)過(guò)足夠長(zhǎng)的時(shí)間后此算法可跳出局部陷阱從而收斂到全局最優(yōu)解.但是也帶來(lái)了一個(gè)矛盾：解的質(zhì)量與求解時(shí)間之間的矛盾.由于網(wǎng)絡(luò)環(huán)境是動(dòng)態(tài)變化且規(guī)模不斷增大的，因此單純的使用模擬退火算法求解本文提出的問(wèn)題，此矛盾將更為突出.

為了在不增加求解時(shí)間的同時(shí)提高解的質(zhì)量，需要反復(fù)進(jìn)行迭代運(yùn)算，也即在有限的時(shí)間內(nèi)求解目標(biāo)函數(shù).換言之，當(dāng)問(wèn)題的規(guī)模不可避免地增大時(shí)，能否能得到最優(yōu)解取決于影響迭代次數(shù)的控制參數(shù)Δt的設(shè)定，因此，參數(shù)設(shè)定成了模擬退火算法應(yīng)用中的一個(gè)關(guān)鍵環(huán)節(jié).

禁忌搜索算法(TS)模仿人類的記憶，通過(guò)記憶能力指導(dǎo)搜索過(guò)程，對(duì)已搜索的局部最優(yōu)解進(jìn)行標(biāo)記，避免了搜索中的迂回、重復(fù)，并且在搜索過(guò)程中可以接受劣解從而增強(qiáng)獲取全局最優(yōu)解的概率[19].但是禁忌搜索算法對(duì)于初始解的依賴性很強(qiáng)，一個(gè)好的初始解可使禁忌搜索算法在解空間中搜索到更好的解，而一個(gè)差的初始解則會(huì)降低禁忌搜索算法的收斂速度，搜索到的解也相對(duì)較差.為了更加直觀的分析兩種算法，表3從5個(gè)維度對(duì)兩種算法進(jìn)行了歸納總結(jié).

表3 SA與TS算法對(duì)比

綜上所述，模擬退火算法和禁忌搜索算法各有優(yōu)缺點(diǎn)，對(duì)于本文研究的在資源約束與用戶QoS約束下部署SFC的問(wèn)題，雖然應(yīng)用這兩種算法都可以解決，但是單一使用某一算法存在依賴于控制迭代的參數(shù)或者依賴于初始解的問(wèn)題，所以如果想取得更好的優(yōu)化效果和更高的優(yōu)化效率，需要將兩種算法相結(jié)合.因此，本文利用模擬退火算法與禁忌搜索算法的優(yōu)點(diǎn)，提出了一種模擬退火算法與禁忌搜索算法相結(jié)合的算法求解SFC部署問(wèn)題，用禁忌搜索的記憶功能降低因模擬退火對(duì)參數(shù)的強(qiáng)依賴帶來(lái)的無(wú)法收斂到全局最優(yōu)的概率.

4.2 算法描述

本文的問(wèn)題是在既考慮用戶QoS需求約束又考慮網(wǎng)絡(luò)資源約束下尋找目標(biāo)函數(shù)最優(yōu)值，其求解過(guò)程需要兩個(gè)核心功能，一是找到一個(gè)滿足條件的較好的初始解，也即可行的解(算法2描述了對(duì)解可行性的判斷)，二是需要不斷對(duì)解尋優(yōu)以期得到全局最優(yōu)解.本文設(shè)計(jì)的SA-TS算法如算法1所示.

算法1.SA-TS算法

輸入：網(wǎng)絡(luò)拓?fù)銰=(N，L)，服務(wù)請(qǐng)求S;

輸出：最優(yōu)路徑SFCpath，鏈路代價(jià)Rcost(SFCpath);

1.while不滿足終止條件

2. 隨機(jī)產(chǎn)生一個(gè)初始解SFCpath0，計(jì)算其物理資源消耗Rcost(SFCpath0);

3. 構(gòu)造新解SFCpathnew，計(jì)算Rcost(SFCpathnew);

4.ifRcost(SFCpathnew)>Rcost(SFCpath0)

5. 以概率p設(shè)置SFCpathnew=SFCpath0;//以概率p接受劣解

6.endif

7.endwhile

8.ifSFCpath0滿足可行性//調(diào)用算法1判斷SFCpath0的可行性

9. 計(jì)算物理資源消耗Rcost(SFCpath0);

10.else

11. 跳轉(zhuǎn)到步驟2 // 不滿足可行性，重新隨機(jī)初始解

12.endif

13.SFCcurrent=SFCpath0;//初始化當(dāng)前解SFCcurrent等于SFCpath0

14.SFCpath=SFCpath0;//初始化最優(yōu)解SFCpath等于SFCpath0

15.Rcost(SFCpath)=Rcost(SFCpath0);//初始化最小消耗Rcost(SFCpath)等于Rcost(SFCpath0)

16.在SFCcurrent鄰域內(nèi)構(gòu)建包含M個(gè)互不相同的候選解SFCtest1…SFCtestm的集合candi;

17.計(jì)算候選解集合candi中每個(gè)候選解的物理資源消耗Rcost(SFCtest1) …Rcost(SFCtestm)，并存入矩陣FitR;

18.將FitR按資源消耗總值排序，得到最小值MinFitR，及其路徑SFCtemp;

19.ifMinFitR

20.Rcost(SFCpath)=MinFitR;

21.SFCpath=SFCtemp;//令最優(yōu)解作為當(dāng)前解

22.SFCcurrent=SFCtemp;//更新截止目前的最優(yōu)解

23. 更新禁忌表中各禁忌對(duì)象長(zhǎng)度;

24.Tslist(SFCtemp)=L;//將候選解加入禁忌表，設(shè)置禁忌長(zhǎng)度為L(zhǎng)

25.else//候選解的值不如當(dāng)前

26.ifTslist(SFCtemp)==0

27.SFCcurrent=SFCtemp;//解禁

28. 更新禁忌表中各禁忌對(duì)象長(zhǎng)度;

29.endif

30.Tslist(SFCtemp)=L;//將候選解加入禁忌表，設(shè)置禁忌長(zhǎng)度為L(zhǎng)

31.endif

32.returnSFCpath，Rcost(SFCpath)//返回最優(yōu)路徑，及最優(yōu)路徑的鏈路代價(jià);

算法2.解的可行性判斷

輸入：TCi，TMi，TBi，Csfi，Msfi，Bsfi，QDSFC，QLRSFC，SFCpath

輸出：解可行or解不可行

1.利用式(5)和式(6)分別計(jì)算部署服務(wù)的節(jié)點(diǎn)可用性SFAvailj和服務(wù)鏈可用性SFCAvail;

2.ifSFAvailj=0 orSFCAvail=0 //資源可用性約束

3.return解不可行

4.else

5. 利用式(7)計(jì)算節(jié)點(diǎn)j上的服務(wù)功能SFi的處理時(shí)延;

6. 利用式(8)計(jì)算服務(wù)鏈路的時(shí)延開(kāi)銷DSFC;

7. 利用式(9)計(jì)算總的鏈路時(shí)延TotalDelay;

8.ifTotalDelay>QDSFC//時(shí)延約束

9.return解不可行;

10.else

11.利用式(11)和式(12)分別計(jì)算當(dāng)前節(jié)點(diǎn)j的緩存Ncachej及當(dāng)前路徑的丟包情況LR

12.ifLR>QLRSFC//丟包約束

13.return解不可行;

14.endif

15.endif

16.endif

17.return解可行;

5 仿真實(shí)驗(yàn)及性能分析

5.1 仿真環(huán)境和參數(shù)設(shè)置

本文仿真實(shí)驗(yàn)在配置為Intel(R)Core(TM) i5-4210M 2.0GHz，8GB內(nèi)存的計(jì)算機(jī)上進(jìn)行.仿真網(wǎng)絡(luò)由12個(gè)節(jié)點(diǎn)提供底層資源.每個(gè)節(jié)點(diǎn)隨機(jī)分配計(jì)算、存儲(chǔ)以及帶寬資源，同時(shí)為了使模擬場(chǎng)景更加通用，用"單元"來(lái)量化資源單位.分配到的資源服從[10000，15000]單元的均勻分布.鏈路中的帶寬資源在[10，15]單元上均勻分布.服務(wù)的請(qǐng)求數(shù)量服從250-450的泊松分布.

假設(shè)實(shí)驗(yàn)中用戶的請(qǐng)求序列S包括4個(gè)虛擬服務(wù)功能，每個(gè)功能的資源使用互不影響.用戶的QoS需求包括：請(qǐng)求時(shí)延在100ms以內(nèi)，丟包率在5%以內(nèi)，可用性在90%以上.

5.2 仿真結(jié)果與分析

為了驗(yàn)證SA-TS算法的性能，本文采用服務(wù)功能鏈部署成功率，總的資源消耗以及服務(wù)鏈路擁塞率作為評(píng)價(jià)指標(biāo)，并與基于貪婪算法的GLT和GLR[20]進(jìn)行了比較.貪婪算法對(duì)問(wèn)題求解時(shí)不做全局考慮，而是依據(jù)某個(gè)原則進(jìn)行選擇優(yōu)化.GLT算法僅考慮服務(wù)請(qǐng)求時(shí)延的最小化，GLR算法僅考慮資源消耗最小.

圖3對(duì)比了在3種策略下，SFC部署的成功率隨SFC請(qǐng)求數(shù)量增多的變化.當(dāng)服務(wù)請(qǐng)求數(shù)量較少時(shí)，網(wǎng)絡(luò)資源充足，因此3種策略的部署成功率都很高.隨著服務(wù)請(qǐng)求數(shù)量的增多，網(wǎng)絡(luò)中的可用資源逐漸緊張，此時(shí)SA-TS算法的部署成功率最高，GLR算法的成功率最低，這是因?yàn)镚LR算法僅考慮網(wǎng)絡(luò)資源消耗的最小化，未考慮用戶的QoS需求，當(dāng)提供的服務(wù)不能達(dá)到用戶的最低要求時(shí)會(huì)重新發(fā)送請(qǐng)求，導(dǎo)致部署成功率最低.SA-TS算法優(yōu)先考慮了用戶的QoS的需求，在不超出網(wǎng)絡(luò)資源容量的前提下，部署成功率最高.并且隨著請(qǐng)求強(qiáng)度的增加，SA-TS算法下SFC的部署成功率下降幅度最小，相比于其他兩種算法，本文提出的SA-TS算法平均提升了11%的部署成功率.

圖3 3種算法下SFC部署成功率對(duì)比

圖4對(duì)比了在3種策略下，運(yùn)營(yíng)商提供的總的資源消耗情況.其中GLR算法的資源消耗最少，原因是GLR算法不考慮提供的服務(wù)質(zhì)量，每次部署僅考慮最低的資源消耗代價(jià)，故而對(duì)底層資源的消耗最少.GLT算法的資源消耗最多，SA-TS算法與之相比資源消耗降低了5%，原因是GLT算法部署時(shí)僅考慮時(shí)延最小，沒(méi)有將時(shí)延限制在一個(gè)可容忍的范圍內(nèi)，也即未充分利用底層資源，造成了資源的浪費(fèi).

圖4 3種算法下資源消耗總量對(duì)比

本文用鏈路的擁塞率來(lái)衡量模型的負(fù)載情況，擁塞率越低，模型的負(fù)載均衡性能越高.圖5對(duì)比了在3種策略下，服務(wù)鏈的負(fù)載均衡情況.隨著服務(wù)請(qǐng)求數(shù)目的增多，計(jì)算資源等物理資源被逐漸消耗，緩存占用逐漸增多，導(dǎo)致服務(wù)鏈的擁塞率逐漸上升.仿真結(jié)果表明，SA-TS算法的鏈路性能較好，鏈路擁塞率平均降低了16%.這是因?yàn)镾A-TS算法保證了QoS，減少了服務(wù)請(qǐng)求重發(fā)的次數(shù)，降低了鏈路緩存量.

圖5 3種算法下服務(wù)鏈擁塞率對(duì)比

6 結(jié) 論

運(yùn)營(yíng)商在實(shí)際部署服務(wù)功能鏈時(shí)需要滿足SLA中關(guān)于服務(wù)質(zhì)量的約定，因此服務(wù)部署的成功與否很大程度上與用戶能夠體驗(yàn)的服務(wù)質(zhì)量有關(guān).為在網(wǎng)絡(luò)資源有限的環(huán)境下進(jìn)一步提高服務(wù)功能鏈的部署成功率，本文綜合考慮了用戶的QoS需求與最小化的運(yùn)營(yíng)商代價(jià)，形式化描述了用戶的QoS需求及網(wǎng)絡(luò)資源情況，并在此基礎(chǔ)上提出了一種用戶QoS與網(wǎng)絡(luò)資源感知的服務(wù)功能鏈部署方法(SA-TS).針對(duì)當(dāng)前的部署研究不考慮用戶QoS或?qū)oS維度考慮單一帶來(lái)的部署成功率低等問(wèn)題，SA-TS方法從時(shí)延、服務(wù)可用性及擁塞等多個(gè)維度保證用戶QoS需求，提高了部署效率，優(yōu)化降低了運(yùn)營(yíng)商的部署成本，并且本文的算法既不依賴于初始解，又有記憶功能，避免走回頭路，降低了單純使用SA的隨機(jī)性，使其不錯(cuò)過(guò)鄰域中的好解.仿真結(jié)果顯示，相比于其他部署方法，SA-TS方法在有限的資源環(huán)境下保證了用戶多個(gè)維度的QoS需求并以較低的代價(jià)達(dá)到了部署的SFC成功率最高的目的.