基于Q-learning的跨域服務(wù)鏈映射機(jī)制

張紅旗，黃睿，楊英杰，常德顯，張連成

（中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450001）

1 引言

軟件定義網(wǎng)絡(luò)（SDN, software defined network）將復(fù)雜的控制功能從傳統(tǒng)網(wǎng)絡(luò)設(shè)備中剝離出來，使數(shù)據(jù)平面僅負(fù)責(zé)高速轉(zhuǎn)發(fā)，而網(wǎng)絡(luò)的控制與管理由邏輯集中的控制平面基于全局網(wǎng)絡(luò)視圖與狀態(tài)進(jìn)行統(tǒng)一決策，有效簡化了網(wǎng)絡(luò)管理[1-2]。網(wǎng)絡(luò)功能虛擬化（NFV，network function virtualization）是針對運(yùn)營商網(wǎng)絡(luò)中網(wǎng)絡(luò)功能靜態(tài)僵化問題而提出的SDN解決方案[3-4]。NFV將以專有硬件形式部署的網(wǎng)絡(luò)功能轉(zhuǎn)變?yōu)樵谕ㄓ梅?wù)器上運(yùn)行的虛擬網(wǎng)絡(luò)功能（VNF, virtual network function），解耦傳統(tǒng)網(wǎng)絡(luò)設(shè)備的軟件功能和硬件載體，減少了在網(wǎng)絡(luò)特定位置部署中間件的開銷，增加了網(wǎng)絡(luò)設(shè)備部署的靈活性。由此，借助SDN/NFV的軟件定義網(wǎng)絡(luò)功能虛擬化（SDNFV, software defined network function virtualization）技術(shù)應(yīng)運(yùn)而生[5]。

作為SDNFV技術(shù)的典型應(yīng)用，服務(wù)鏈近年來頗受關(guān)注[6]。服務(wù)鏈在利用NFV技術(shù)將傳統(tǒng)網(wǎng)絡(luò)功能虛擬化并部署在服務(wù)節(jié)點(diǎn)的基礎(chǔ)上，借助 SDN的流量集中管控功能，依據(jù)用戶/業(yè)務(wù)的服務(wù)請求引導(dǎo)流量按序經(jīng)過服務(wù)節(jié)點(diǎn)上的 VNF實(shí)例，進(jìn)而為用戶/業(yè)務(wù)提供可定制的網(wǎng)絡(luò)服務(wù)。每條服務(wù)鏈可看作由一個(gè)或多個(gè) VNF實(shí)例按照既定次序連接而成的邏輯視圖。因此，如何設(shè)計(jì)合理的服務(wù)鏈映射方法完成邏輯視圖向物理拓?fù)涞挠成湟殉蔀樵擃I(lǐng)域的研究熱點(diǎn)。

文獻(xiàn)[7]提出一種可重構(gòu)的服務(wù)鏈映射機(jī)制，采用兩階段映射方法，分別基于物理節(jié)點(diǎn)的服務(wù)能力和物理鏈路的容量約束設(shè)計(jì)優(yōu)化算法選擇可映射的服務(wù)節(jié)點(diǎn)和路由路徑，但未考慮分階段映射過程中由于服務(wù)節(jié)點(diǎn)間距離過大而引入的時(shí)延開銷。為此，文獻(xiàn)[8]采用一階段映射方法，以最大化平均資源利用率和最小化平均響應(yīng)時(shí)間為目標(biāo)建立服務(wù)鏈映射多目標(biāo)優(yōu)化模型，并根據(jù)網(wǎng)絡(luò)情況和映射請求聯(lián)合優(yōu)化服務(wù)鏈映射問題。為進(jìn)一步提高服務(wù)鏈的映射效率，文獻(xiàn)[9]在文獻(xiàn)[8]的基礎(chǔ)上引入帶有回溯機(jī)制的啟發(fā)式算法聯(lián)合優(yōu)化 VNF組合和服務(wù)鏈映射問題，有效降低了網(wǎng)絡(luò)整體的帶寬消耗。為實(shí)現(xiàn)傳統(tǒng)網(wǎng)絡(luò)功能向VNF的平滑過渡，文獻(xiàn)[10]研究了硬件設(shè)備和虛擬機(jī)混合場景下的服務(wù)鏈映射問題，基于軟件工程流水線的理念，提出一種定制化的服務(wù)鏈映射算法。文獻(xiàn)[11]研究了多網(wǎng)絡(luò)服務(wù)供應(yīng)商條件下的服務(wù)鏈映射問題，并基于整數(shù)線性規(guī)劃和圖分割的方法給出了解決方案。由此可見，研究人員已對服務(wù)鏈映射問題進(jìn)行了諸多有益的探索，但是相關(guān)研究僅局限于單域條件下的服務(wù)鏈映射，尚未對跨域條件下服務(wù)鏈的映射問題開展深入細(xì)致的討論。

國內(nèi)清華大學(xué)畢軍教授團(tuán)隊(duì)率先對SDN“東西向”問題展開研究，提出一種協(xié)作式的域間 SDN互聯(lián)技術(shù)WE-Bridge[12]，并基于WE-Bridge技術(shù)構(gòu)建跨洲際的域間SDN實(shí)驗(yàn)床[13]，解決了目前SDN的研究集中在單個(gè)自治域內(nèi)采用邏輯集中的控制平面而自治域的數(shù)量呈現(xiàn)出超線性增長的矛盾沖突[14]。受此啟發(fā)，筆者認(rèn)為服務(wù)鏈映射問題的研究不應(yīng)局限于某一特定的OpenFlow自治域內(nèi)。實(shí)際中受地理位置等客觀條件的影響，VNF往往由不同的供應(yīng)商在各自治域內(nèi)進(jìn)行相應(yīng)的維護(hù)和管理，而用戶/業(yè)務(wù)的需求愈發(fā)呈現(xiàn)出多樣化的趨勢，因此，一條服務(wù)鏈可能需要跨越多個(gè)OpenFlow自治域進(jìn)行映射。此時(shí)，由于各個(gè)OpenFlow自治域內(nèi)網(wǎng)絡(luò)拓?fù)溥B接信息及虛擬服務(wù)資源信息的獨(dú)立性和封閉性，傳統(tǒng)的單域服務(wù)鏈映射方法已不再適用。為此，本文基于SDN/NFV的典型實(shí)現(xiàn)方式，提出一種區(qū)域集中管理、全局協(xié)同調(diào)度的虛擬服務(wù)資源管控架構(gòu)，在此基礎(chǔ)上，建立一種有效的跨域服務(wù)鏈映射框架，對涉及跨域映射的服務(wù)鏈構(gòu)建請求，以最小化映射開銷為目標(biāo)，設(shè)計(jì)基于Q-learning的跨域服務(wù)鏈構(gòu)建請求分割算法進(jìn)行優(yōu)化求解，從而有效完成跨域服務(wù)鏈的映射。本文貢獻(xiàn)主要包含以下3個(gè)方面。

1) 基于SDN的典型實(shí)現(xiàn)方式，提出一種分層分域的虛擬服務(wù)資源管控架構(gòu)，縱向包含基礎(chǔ)設(shè)施平面、邏輯控制平面和應(yīng)用管理平面，橫向包含各OpenFlow自治域、區(qū)域服務(wù)代理和全局服務(wù)代理，共同實(shí)現(xiàn)虛擬服務(wù)資源的區(qū)域集中管理和全局協(xié)同調(diào)度。

2) 在上述虛擬服務(wù)資源管控架構(gòu)的基礎(chǔ)上，建立一種基于輪詢機(jī)制的跨域服務(wù)鏈映射框架。該框架下，全局服務(wù)代理采用輪詢方式接受各區(qū)域服務(wù)代理上報(bào)的跨域服務(wù)鏈映射請求，在保證系統(tǒng)公平性的同時(shí)有效避免基礎(chǔ)設(shè)施平面資源分配的沖突。

3) 針對需要進(jìn)行跨域映射的服務(wù)鏈構(gòu)建請求，設(shè)計(jì)一種基于Q-learning機(jī)制的跨域服務(wù)鏈構(gòu)建請求分割算法，以最小化映射開銷為目標(biāo)，采用智能化的方法進(jìn)行優(yōu)化求解，實(shí)現(xiàn)跨域服務(wù)請求的及時(shí)響應(yīng)及跨域服務(wù)鏈的高效映射。

2 虛擬服務(wù)資源管控架構(gòu)

SDNFV環(huán)境下網(wǎng)絡(luò)功能的硬件載體和軟件功能改變了以往緊密耦合的特點(diǎn)，實(shí)現(xiàn)了虛擬服務(wù)資源的靈活管控，分離形成基礎(chǔ)設(shè)施平面、邏輯控制平面和應(yīng)用管理平面，如圖1所示。

2.1 基礎(chǔ)設(shè)施平面

傳統(tǒng)物理網(wǎng)絡(luò)的基礎(chǔ)設(shè)施平面是由各種異構(gòu)網(wǎng)絡(luò)體系相互融合形成的復(fù)雜巨網(wǎng)絡(luò)，其具有覆蓋范圍廣、組成結(jié)構(gòu)復(fù)雜的特點(diǎn)，要實(shí)現(xiàn)如此大規(guī)模的資源管理和維護(hù)是相當(dāng)困難的。本文提出了虛擬服務(wù)資源管控架構(gòu)，將基礎(chǔ)設(shè)施平面劃分為多個(gè)OpenFlow自治域（如圖1中OPNFV-D1～OPNFV-D3），每個(gè)自治域由各自的SDN控制器和NFV編排器進(jìn)行區(qū)域控制，管理和維護(hù)區(qū)域內(nèi)的網(wǎng)絡(luò)通信資源和虛擬服務(wù)資源。各個(gè)自治域之間相對獨(dú)立，共同協(xié)作以實(shí)現(xiàn)為用戶/業(yè)務(wù)的多樣化服務(wù)鏈映射請求提供及時(shí)有效的響應(yīng)。

2.2 邏輯控制平面

邏輯控制平面是上層應(yīng)用管理平面和底層基礎(chǔ)設(shè)施平面之間的“橋梁”。本文構(gòu)建的SDNFV環(huán)境下的虛擬服務(wù)資源管控架構(gòu)旨在實(shí)現(xiàn)虛擬服務(wù)資源的區(qū)域集中管理、全局協(xié)同調(diào)度。區(qū)域服務(wù)代理實(shí)時(shí)掌握本區(qū)域的狀態(tài)信息（包括拓?fù)?、虛擬資源的使用情況等），同時(shí)，接受區(qū)域內(nèi)用戶/業(yè)務(wù)的服務(wù)鏈映射請求，完成其向底層物理資源的映射。按照各自實(shí)現(xiàn)的功能和職責(zé)的不同，可將區(qū)域服務(wù)代理劃分為SDN控制器和NFV編排器2種類型。SDN控制器負(fù)責(zé)管理對應(yīng)OpenFlow自治域內(nèi)的交換機(jī)，實(shí)現(xiàn)流量的動(dòng)態(tài)牽引。NFV編排器負(fù)責(zé)管理對應(yīng)OpenFlow自治域內(nèi)提供VNF的X86服務(wù)器（也稱服務(wù)節(jié)點(diǎn)），實(shí)現(xiàn)虛擬服務(wù)資源的動(dòng)態(tài)調(diào)度。二者結(jié)合，為構(gòu)建靈活的基礎(chǔ)設(shè)施平面提供了保證。

2.3 應(yīng)用管理平面

應(yīng)用管理平面是位于邏輯控制平面之上的擴(kuò)展平面，可根據(jù)需要進(jìn)行擴(kuò)充。本文構(gòu)建了由全局服務(wù)代理、服務(wù)信息數(shù)據(jù)庫、服務(wù)鏈分割算法和單域映射算法組成的管理中心以滿足跨域服務(wù)鏈映射的需求。全局服務(wù)代理是為了實(shí)現(xiàn)分布式協(xié)同調(diào)度的需要，負(fù)責(zé)管理區(qū)域服務(wù)代理的加入或退出，并實(shí)時(shí)掌握域內(nèi)邊界節(jié)點(diǎn)以及域間鏈路的拓?fù)溥B接關(guān)系及使用情況。當(dāng)出現(xiàn)跨域服務(wù)鏈映射請求時(shí)，統(tǒng)一協(xié)調(diào)各區(qū)域服務(wù)代理進(jìn)行協(xié)同處理。服務(wù)信息數(shù)據(jù)庫負(fù)責(zé)存儲域內(nèi)的虛擬服務(wù)資源信息及域間的狀態(tài)連接信息，為算法提供計(jì)算依據(jù)。服務(wù)鏈分割算法是解決跨域服務(wù)鏈映射問題的核心，當(dāng)服務(wù)鏈不需要進(jìn)行分割時(shí)即轉(zhuǎn)化為單域服務(wù)鏈映射問題，可采用相應(yīng)的單域映射算法進(jìn)行求解。

3 跨域服務(wù)鏈映射問題描述

在第2節(jié)的架構(gòu)中，基礎(chǔ)設(shè)施平面為滿足區(qū)域集中管理、全局協(xié)同調(diào)度的需求被劃分為不同的OpenFlow自治域，本節(jié)的跨域服務(wù)鏈映射問題研究正是基于此進(jìn)行的。服務(wù)代理依據(jù)用戶/業(yè)務(wù)的服務(wù)鏈映射需求及網(wǎng)絡(luò)資源狀態(tài)完成服務(wù)鏈的構(gòu)建，從而實(shí)現(xiàn)邏輯映射需求與物理網(wǎng)絡(luò)資源之間的有效匹配，如圖2所示。

3.1 底層物理網(wǎng)絡(luò)

如圖2所示，底層物理網(wǎng)絡(luò)被劃分為DN個(gè)不同的 OpenFlow自治域（此處DN=3），可用有權(quán)無向圖表示。其中，NS代表底層物理節(jié)點(diǎn)集合，包括域內(nèi)節(jié)點(diǎn)集合NSi和邊界節(jié)點(diǎn)集合NSb，域內(nèi)節(jié)點(diǎn)集合NSi又可細(xì)分為服務(wù)節(jié)點(diǎn)集合NSi_S和轉(zhuǎn)發(fā)節(jié)點(diǎn)集合NSi_F，對表示服務(wù)節(jié)點(diǎn)ns的I類資源的容量，代表底層物理鏈路集合，包括域內(nèi)鏈路集合LSi和域間鏈路集合表示其帶寬資源容量。依據(jù)第2節(jié)的虛擬服務(wù)資源管控架構(gòu)，可將整個(gè)底層物理網(wǎng)絡(luò)視圖劃分為全局視圖和區(qū)域視圖。全局視圖用表示，描述了全網(wǎng)邊界節(jié)點(diǎn)和域間鏈路的分布狀況，而區(qū)域視圖描述了每個(gè)OpenFlow自治域內(nèi)的物理拓?fù)溥B接情況。

圖2 跨域服務(wù)鏈映射問題描述

3.2 服務(wù)鏈構(gòu)建請求

對于包含p個(gè)原子服務(wù)功能的服務(wù)鏈映射請求可將其抽象為一個(gè)有權(quán)無向圖其中，NR為服務(wù)鏈中VNF實(shí)例節(jié)點(diǎn)構(gòu)成的集合，LR為VNF實(shí)例鏈路構(gòu)成的集合。對 ?nr∈NR，用rvI(nr)表示VNF實(shí)例節(jié)點(diǎn)nr的I類資源需求；對 ?lr∈LR，用rb(lr)表示VNF實(shí)例鏈路lr的帶寬資源需求。

3.3 服務(wù)鏈映射

服務(wù)鏈映射問題可形式化表示如下。Mapping:，按照映射區(qū)域的不同可將其劃分為單域映射和跨域映射。單域服務(wù)鏈映射是將VNF實(shí)例和VNF鏈路根據(jù)一定的約束條件及目標(biāo)函數(shù)映射到某一OpenFlow自治域范圍內(nèi)的底層物理網(wǎng)絡(luò)上，而跨域服務(wù)鏈映射不同于單域服務(wù)鏈映射。因?yàn)樵趩斡蛴成鋯栴}中，域內(nèi)的拓?fù)溥B接情況及虛擬資源狀態(tài)都是已知的，而對于跨域映射，不同的OpenFlow自治域之間信息都是不對外公開的。因此，需要采取分布式映射機(jī)制，實(shí)現(xiàn)域間映射和域內(nèi)映射的協(xié)同，有效滿足映射需求，并實(shí)現(xiàn)網(wǎng)絡(luò)資源的充分使用。

4 跨域服務(wù)鏈映射策略

針對跨域服務(wù)鏈映射問題的特殊性，本文提出一種基于請求分割的分布式跨域服務(wù)鏈映射策略。首先，在第2節(jié)虛擬服務(wù)資源管控架構(gòu)的基礎(chǔ)上建立跨域服務(wù)鏈映射框架，描述服務(wù)鏈映射的具體流程。在此基礎(chǔ)上，基于Q-learning機(jī)制設(shè)計(jì)跨域服務(wù)鏈構(gòu)建請求分割算法，以實(shí)現(xiàn)跨域服務(wù)鏈構(gòu)建請求在域間和域內(nèi)的協(xié)同映射。

4.1 跨域服務(wù)鏈映射框架

如圖3所示，為提高服務(wù)鏈構(gòu)建請求的映射成功率，簡化處理流程，可將映射框架設(shè)置如下。

1) 用戶/業(yè)務(wù)依據(jù)就近原則向區(qū)域服務(wù)代理發(fā)出服務(wù)鏈構(gòu)建請求，區(qū)域服務(wù)代理將其轉(zhuǎn)化為服務(wù)鏈邏輯視圖，判斷其需要進(jìn)行單域映射還是跨域映射，并將其劃歸于相應(yīng)的集合

3) 由于各個(gè)OpenFlow自治域中的網(wǎng)絡(luò)信息是不對外公開的，因此跨域映射請求需要由全局服務(wù)代理完成。全局服務(wù)代理根據(jù)其掌握的全局資源信息及域間資源約束進(jìn)行規(guī)劃，將跨域服務(wù)鏈映射請求分割為多個(gè)單域服務(wù)鏈映射請求，并交由各區(qū)域服務(wù)代理進(jìn)行處理。

4) 全局服務(wù)代理周期性地對各個(gè)區(qū)域服務(wù)代理進(jìn)行輪詢，只有輪詢到的區(qū)域服務(wù)代理才能向全局服務(wù)代理發(fā)出跨域映射請求，以避免跨域映射請求處理出現(xiàn)沖突和全局服務(wù)代理發(fā)生過載。

4.2 基于Q-learning的跨域服務(wù)鏈構(gòu)建請求分割

單域服務(wù)鏈構(gòu)建請求的映射算法很多，這里不再贅述。本文關(guān)注的重點(diǎn)在于跨域服務(wù)鏈構(gòu)建請求的映射。依據(jù)圖3提出的跨域服務(wù)鏈映射框架，跨域映射需要被分割為多個(gè)不同的單域映射進(jìn)行處理，而如何進(jìn)行合理分割正是本文研究的重點(diǎn)。文獻(xiàn)[15]從理論上證明了虛擬網(wǎng)絡(luò)分割問題是非確定性多項(xiàng)式（NP，non-deterministic polynomial）難問題，而跨域服務(wù)鏈構(gòu)建請求分割問題可以看作是虛擬網(wǎng)絡(luò)分割問題的特例，因此，也難以在多項(xiàng)式時(shí)間內(nèi)得到解決。為此，本文首先建立跨域服務(wù)鏈構(gòu)建請求分割問題模型，然后設(shè)計(jì)基于Q-learning的智能優(yōu)化算法求取問題的近似最優(yōu)解。

4.2.1 模型建立

跨域服務(wù)鏈構(gòu)建請求分割問題是指以降低跨域服務(wù)鏈映射開銷為目標(biāo)，根據(jù)各OpenFlow自治域的資源匹配狀況和邊界節(jié)點(diǎn)的相關(guān)信息，將跨域服務(wù)鏈映射請求分割為多個(gè)單域服務(wù)鏈映射請求，從而形成一套有效的服務(wù)鏈映射方案。

跨域服務(wù)鏈映射開銷用Cost表示，主要包含3個(gè)部分：節(jié)點(diǎn)映射開銷（Node_cost）、域間鏈路映射開銷（Link_cost）和域內(nèi)鏈路映射開銷。對于一條固定的服務(wù)鏈，節(jié)點(diǎn)映射開銷是一定的，不同的是承載路徑不同而導(dǎo)致的不同鏈路映射開銷。當(dāng)分別位于兩個(gè)OpenFlow自治域中的VNF實(shí)例節(jié)點(diǎn)間需要建立域間鏈路時(shí)，選擇不同的邊界節(jié)點(diǎn)會(huì)產(chǎn)生不同的Link_cost。因此，在某一服務(wù)鏈分割方案中，既需要為每個(gè) VNF實(shí)例節(jié)點(diǎn)指明承擔(dān)其映射的OpenFlow自治域，還需要指明經(jīng)由域中具體哪一個(gè)邊界節(jié)點(diǎn)完成域間鏈路的連接。由于各OpenFlow自治域的鏈路連接信息不會(huì)完全對外公開，且域間鏈路映射開銷與域內(nèi)鏈路映射開銷相差較大。因此，本文著重考慮節(jié)點(diǎn)映射開銷和域間鏈路開銷。將跨域服務(wù)鏈映射的總開銷Cost表示為

跨域服務(wù)鏈構(gòu)建請求分割問題可看作是滿足以下映射條件，以最小化跨域服務(wù)鏈映射開銷為目標(biāo)的最優(yōu)化問題。

式(2)中的fn表示VNF實(shí)例節(jié)點(diǎn)映射，即把VNF實(shí)例節(jié)點(diǎn)映射到某個(gè)OpenFlow自治域的邊界節(jié)點(diǎn)上，滿足 VNF實(shí)例節(jié)點(diǎn)nr映射條件的所有邊界節(jié)點(diǎn)構(gòu)成的集合用MS(nr)表示。值得注意的是，邊界節(jié)點(diǎn)不承載具體的 VNF實(shí)例節(jié)點(diǎn)映射，本文提到的將某一VNF實(shí)例節(jié)點(diǎn)映射到某一邊界節(jié)點(diǎn)上僅表示將該VNF實(shí)例節(jié)點(diǎn)劃分到該邊界節(jié)點(diǎn)所在的OpenFlow自治域；式(3)中的fl表示 VNF實(shí)例鏈路映射，有權(quán)無向圖GSb中邊界節(jié)點(diǎn)i′和j′間的所有可行映射路徑構(gòu)成的集合用Path(i′ ,j′)表示。當(dāng)VNF實(shí)例鏈路lr(i,j)的兩個(gè)端點(diǎn)i和j分別映射到邊界節(jié)點(diǎn)i′和j′上時(shí)，lr(i,j)必須映射到集合Path(i′ ,j′)中的路徑上以完成服務(wù)鏈映射請求的有效分割。

1) 變量定義

定義1分割方案矩陣Hm×n。服務(wù)鏈構(gòu)建請求中 VNF實(shí)例節(jié)點(diǎn)的數(shù)目用m表示，物理網(wǎng)絡(luò)中邊界節(jié)點(diǎn)的數(shù)目用n表示。如式(4)所示，矩陣項(xiàng)H[i] [j]的取值表示 VNF實(shí)例節(jié)點(diǎn)i和邊界節(jié)點(diǎn)j之間的映射關(guān)系。

圖3 跨域服務(wù)鏈映射框架

以圖2中的請求分割方案為例，可將其分割方案矩陣表示為表1。

表1 請求分割方案的矩陣表示

定義 2鏈路類型變量Xi,j。其中，i和j為VNF實(shí)例鏈路lr(i,j)的2個(gè)端點(diǎn)，可以根據(jù)矩陣H的值判斷VNF實(shí)例鏈路lr(i,j)的類型，如式(5)所示，變量Xi,j的值代表鏈路的不同類型。

2) 約束條件

跨域服務(wù)鏈構(gòu)建請求分割問題需滿足以下約束條件。

式(6)表示矩陣H中的每一行之和小于或等于1，因?yàn)槊總€(gè)VNF實(shí)例節(jié)點(diǎn)只能被映射到一個(gè)OpenFlow自治域。式(7)確保了 VNF實(shí)例鏈路的帶寬資源需求不超過物理鏈路的帶寬資源容量。

3) 目標(biāo)函數(shù)

跨域服務(wù)鏈構(gòu)建請求分割問題的求解目標(biāo)找到使得服務(wù)鏈映射開銷最小的分割方案，其目標(biāo)函數(shù)Obj可表示為

目標(biāo)函數(shù)Obj中的3個(gè)參數(shù)具體含義如下。

Hm×n：VNF實(shí)例節(jié)點(diǎn)與物理網(wǎng)絡(luò)邊界節(jié)點(diǎn)的映射關(guān)系矩陣。

FMm×m：服務(wù)鏈構(gòu)建請求的流量矩陣，表示VNF實(shí)例節(jié)點(diǎn)i和VNF實(shí)例節(jié)點(diǎn)j之間的帶寬資源需求。

BMn×n：連接邊界節(jié)點(diǎn)間鏈路的最小單位開銷矩陣，表示通過Floyd算法[16]計(jì)算得出的邊界節(jié)點(diǎn)i和j之間所有鏈路的單位開銷的最小值。

為便于目標(biāo)函數(shù)Obj的計(jì)算，本文定義一種特殊的運(yùn)算，用符號⊙表示。

由于服務(wù)鏈的節(jié)點(diǎn)映射開銷是一定的，而服務(wù)鏈的域間鏈路映射開銷隨邊界節(jié)點(diǎn)選取的不同而不同。因此，用常數(shù)C表示節(jié)點(diǎn)映射開銷Objn，用表示域間鏈路映射開銷表示VNF實(shí)例節(jié)點(diǎn)i映射到了邊界節(jié)點(diǎn)u，而VNF實(shí)例節(jié)點(diǎn)j映射到了邊界節(jié)點(diǎn)v。目標(biāo)函數(shù)Obj中的系數(shù)α和β用于調(diào)節(jié)節(jié)點(diǎn)映射開銷Objn和域間鏈路映射開銷Objl的權(quán)重。

4.2.2 算法準(zhǔn)備

強(qiáng)化學(xué)習(xí)是人工智能領(lǐng)域機(jī)器學(xué)習(xí)技術(shù)中的重要方法之一。作為一種交互式學(xué)習(xí)方法，其強(qiáng)調(diào)在與環(huán)境的作用中學(xué)習(xí)獲得評價(jià)性的反饋信號，并據(jù)此改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境，從而達(dá)到預(yù)期的目的。

作為強(qiáng)化學(xué)習(xí)的典型實(shí)現(xiàn)方式，Q-learning算法常用于求解先驗(yàn)知識較少的復(fù)雜決策優(yōu)化問題。如圖4所示，Q-learning算法模型是一個(gè)自適應(yīng)閉環(huán)控制系統(tǒng)。智能體Q-A gent 首先通過感知環(huán)境狀態(tài)，在當(dāng)前狀態(tài)s的基礎(chǔ)上依據(jù)Q值函數(shù)選擇一個(gè)動(dòng)作a并執(zhí)行，當(dāng)遷移到下一狀態(tài)s′時(shí)，智能體Q-A gent 依據(jù)環(huán)境的反饋計(jì)算收益函數(shù)R(s,a)并據(jù)此更新Q值函數(shù)Q(s,a)，然后依據(jù)新的Q值和當(dāng)前環(huán)境狀態(tài)選擇下一個(gè)動(dòng)作，迭代進(jìn)行直至得到問題的最優(yōu)策略。

圖4 Q-learning算法模型

Q-learning算法中Q值函數(shù)是狀態(tài)和行為的評價(jià)值，可用瞬時(shí)回報(bào)和未來回報(bào)來表示。

其中，st和at表示當(dāng)前狀態(tài)和行為，st+1和at+1表示下一個(gè)狀態(tài)和行為，折扣系數(shù)γ是滿足0＜γ＜1的常數(shù)，用于調(diào)節(jié)智能體Q-A gent對未來回報(bào)的關(guān)注程度。

當(dāng)系統(tǒng)處于狀態(tài)st時(shí)，依據(jù)式(11)來選擇行為at。

為了避免算法落入局部最優(yōu)，本文采取ε- g reedy[17]的動(dòng)作選取方式，即以小概率ε隨機(jī)選擇一個(gè)動(dòng)作進(jìn)行探索，以1-ε的概率根據(jù)Q值選取當(dāng)前最佳動(dòng)作，ε可動(dòng)態(tài)改變，將其設(shè)置為其中E表示學(xué)習(xí)循環(huán)的次數(shù)。其目的在于，智能體Q-A gent在學(xué)習(xí)前期可采用隨機(jī)方式進(jìn)行更好地探索，而在學(xué)習(xí)后期更偏向于根據(jù)Q值指導(dǎo)下一步的動(dòng)作選擇。

當(dāng)選定并執(zhí)行該動(dòng)作后，系統(tǒng)進(jìn)入下一狀態(tài)at+1，同時(shí)系統(tǒng)也得到相應(yīng)的收益函數(shù)R(st,at)，可依據(jù)式(12)對Q值函數(shù)進(jìn)行迭代更新。

其中， λ ( 0 ＜ λ≤ 1 )是智能體Q- Agent 的學(xué)習(xí)因子，可表示為表示經(jīng)過num次行為選擇后，行為at被選擇的次數(shù)。如果在迭代過程中，某個(gè)行為被選中次數(shù)少，則在接下來的選擇中偏向選擇該行為，從而確保智能體Q-A gent擁有較好的探索特性。

在利用 Q-learning算法解決現(xiàn)實(shí)問題的過程中，最重要的是將一個(gè)實(shí)際的問題轉(zhuǎn)化成為Q-learning算法模型并以此得到優(yōu)化的策略結(jié)果。即根據(jù)所要解決的實(shí)際問題，定義環(huán)境中的狀態(tài)空間、動(dòng)作集合和收益函數(shù)。結(jié)合本文所提的跨域服務(wù)鏈構(gòu)建請求分割問題，可分別將其定義如下。

定義 3狀態(tài)空間S。跨域服務(wù)鏈構(gòu)建請求分割問題的關(guān)鍵在于確定 VNF實(shí)例節(jié)點(diǎn)和邊界節(jié)點(diǎn)的映射關(guān)系。因此，將VNF實(shí)例節(jié)點(diǎn)i和邊界節(jié)點(diǎn)j組成的二元組(i,j)定義為一個(gè)狀態(tài)s，如果服務(wù)鏈中VNF實(shí)例節(jié)點(diǎn)數(shù)目為m，物理網(wǎng)絡(luò)中邊界節(jié)點(diǎn)數(shù)目為n，則共有m×n個(gè)狀態(tài)，記為SN。因此，狀態(tài)空間可表示為S= {s1,s2,… ,sSN}。

定義4動(dòng)作集合A。對每一個(gè)VNF實(shí)例節(jié)點(diǎn)i和邊界節(jié)點(diǎn)j組成的狀態(tài)二元組s(i,j)，可對其進(jìn)行映射、不映射和不在映射范圍3種操作，分別對應(yīng)動(dòng)作a1、a0和a-1。因此，動(dòng)作集合可表示為

定義5收益函數(shù)R(s,a)。對某狀態(tài)s(i,j)執(zhí)行不同的動(dòng)作a將會(huì)獲得不同的收益，此處，利的式(8)計(jì)算當(dāng)前方案的映射開銷，取其相反數(shù)作為對應(yīng)的收益，即R(s,a)= - ( αObjn+ βObjl)。

Q-learning算法收斂的本質(zhì)在于Q值函數(shù)的收斂[18]。此處對算法的收斂性進(jìn)行分析，將最優(yōu)Q值表示為Q*(s,a)。

tt

定理1由式(8)定義的收益函數(shù)R的值在不同系統(tǒng)狀態(tài)下有界。

證明見附錄A。

定理 2對于有界收益函數(shù)R的Q值迭代問題，學(xué)習(xí)因子0＜λ≤1，且滿足

則當(dāng)t→∞時(shí)，有

證明見附錄B[19]。

4.2.3 算法描述

如表2所示，在上述準(zhǔn)備工作的基礎(chǔ)上，可將基于Q-learning的跨域服務(wù)鏈構(gòu)建請求分割算法描述如下。需要注意的是該算法將針對某一特定的跨域服務(wù)鏈構(gòu)建請求中 VNF實(shí)例節(jié)點(diǎn)與邊界節(jié)點(diǎn)的映射關(guān)系進(jìn)行說明。

算法1首先對相關(guān)參數(shù)進(jìn)行初始化，隨后利用ε- g reedy[17]方法指導(dǎo)智能體Q-A gent的行為選擇，并依據(jù)式(12)進(jìn)行Q值函數(shù)的更新，迭代進(jìn)行，直至Q值函數(shù)收斂，從而據(jù)此為跨域服務(wù)鏈構(gòu)建請求分割方案做出決策。

5 方案分析與評估

為全面評估本文所提跨域服務(wù)鏈映射策略的有效性，本文從以下兩方面開展仿真實(shí)驗(yàn)。

1) 由于現(xiàn)有研究僅對單域服務(wù)鏈映射問題進(jìn)行探討，而未對跨域服務(wù)鏈映射問題開展深入研究，故現(xiàn)有算法都不便與本文方法直接進(jìn)行比較。虛擬網(wǎng)絡(luò)映射（VNE）問題中，有研究者專門對跨域條件下的虛擬網(wǎng)絡(luò)映射問題進(jìn)行了研究，其中，2種較為經(jīng)典的算法分別為基于二元整數(shù)規(guī)劃的跨域虛擬網(wǎng)絡(luò)映射算法（LID-partition）[20]和基于人工蜂群算法的跨域虛擬網(wǎng)絡(luò)映射算法（ABC- partition）[21]。本文分別對這兩種算法進(jìn)行改造，使其適用于跨域服務(wù)鏈映射問題，并將它們與本文所提的基于Q-learning的跨域服務(wù)鏈構(gòu)建請求分割算法（Q-partition）進(jìn)行比較，以驗(yàn)證本文方法的性能優(yōu)勢。

2) 在不同物理網(wǎng)絡(luò)拓?fù)溥B接條件下，比較本文算法在平均分割時(shí)間和平均映射開銷方面的變化，以驗(yàn)證本文方法（Q-partition）的適應(yīng)性。

5.1 實(shí)驗(yàn)設(shè)置

仿真實(shí)驗(yàn)在配置Ubuntu 14.04 64位操作系統(tǒng)的Intel Core i7-6300HQ @3.40 GHz、8 GB內(nèi)存的PC機(jī)上進(jìn)行。以Mininet模擬器為基礎(chǔ)，采用開源的Floodlight控制器，使用Java語言編寫實(shí)驗(yàn)代碼并利用Matlab工具對實(shí)驗(yàn)結(jié)果進(jìn)行分析。每次實(shí)驗(yàn)運(yùn)行50 000個(gè)時(shí)間單位。

將底層物理網(wǎng)絡(luò)劃分為10個(gè)OpenFlow自治域，每個(gè)域內(nèi)用GT-ITM[22]工具生成物理網(wǎng)絡(luò)拓?fù)?，拓?fù)溆?0個(gè)節(jié)點(diǎn)組成，包括6個(gè)服務(wù)節(jié)點(diǎn)、40個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)和4個(gè)邊界節(jié)點(diǎn)，邊界節(jié)點(diǎn)之間采用全連接的方式，域內(nèi)節(jié)點(diǎn)以0.5的概率相連。為評估算法的自適應(yīng)性，假設(shè)跨域服務(wù)鏈構(gòu)建請求動(dòng)態(tài)到達(dá)，且服從時(shí)間單位為1 000，強(qiáng)度為pA的泊松過程，請求的生命周期服從均值為60個(gè)時(shí)間單位的指數(shù)分布。假設(shè)網(wǎng)絡(luò)中有8種VNF，每種VNF有3種不同的VNF實(shí)例，每個(gè)構(gòu)建請求由一個(gè)或多個(gè) VNF實(shí)例組成，數(shù)量服從的均勻分布。為便于討論，目標(biāo)函數(shù)Obj中的系數(shù)α和β均取1，折扣系數(shù)γ取0.8。

5.2 實(shí)驗(yàn)結(jié)果分析

5.2.1 算法性能對比

將本文算法（Q-partition）與LID-partition算法和ABC-partition算法進(jìn)行對比，幾種算法域內(nèi)映射統(tǒng)一采用文獻(xiàn)[23]中的算法，從平均分割時(shí)間、平均映射開銷和服務(wù)鏈構(gòu)建請求接受率3個(gè)方面進(jìn)行分析。

1) 對比3種算法的平均分割時(shí)間。觀察當(dāng)服務(wù)鏈構(gòu)建請求長度增加時(shí)，各算法平均分割時(shí)間的變化趨勢。如圖5所示，3種算法的平均分割時(shí)間都隨著服務(wù)鏈構(gòu)建請求長度的增加而增加。LID-partition算法的平均分割時(shí)間要明顯高于其他2種算法，且隨著問題規(guī)模的增大呈指數(shù)增長，在服務(wù)鏈構(gòu)建請求長度為 8時(shí)，平均分割時(shí)間高達(dá)

3.8× 104ms。這是因?yàn)?LID-partition算法的二元整數(shù)規(guī)劃中還涉及虛擬鏈路的分割，其中二元變量的數(shù)目要多于另外2種算法，故計(jì)算時(shí)間較長。Q-partition算法和ABC-partition算法的平均分割時(shí)間要明顯小于LID-partition算法，且隨著服務(wù)鏈構(gòu)建請求長度的增加呈線性增長，即使在問題規(guī)模較大時(shí)，也能夠在可接受的時(shí)間范圍內(nèi)收斂。圖5(b)中，Q-partition算法采用智能化的方法，不斷地朝著最大收益方向調(diào)整算法的搜索方向，避免了盲目遍歷全部狀態(tài)空間，相較于ABC-partition算法表現(xiàn)出更好的尋優(yōu)能力，因而具有最小的平均分割時(shí)間。

2) 對比3種算法的平均映射開銷。觀察當(dāng)服務(wù)鏈構(gòu)建請求長度增加時(shí)，各算法平均映射開銷的變化趨勢。為便于表述，對3種算法的平均映射開銷進(jìn)行“歸一化”處理，假設(shè)一定請求長度下，某種算法的映射開銷為Cost(A)，最大映射開銷為Cost(M)，則可依據(jù)式(15)評估算法的平均映射開銷。

圖5 服務(wù)鏈構(gòu)建請求平均分割時(shí)間

如圖 6所示，3種算法的平均映射開銷都隨著服務(wù)鏈構(gòu)建請求長度的增加而增加。LID-partition算法在服務(wù)鏈構(gòu)建請求長度較小時(shí)（長度在1～4之間），就呈現(xiàn)出較高的平均映射開銷值（平均映射開銷在58%左右），而隨著構(gòu)建請求長度的增加，平均映射開銷高達(dá)87%。是因?yàn)長ID-partition算法中的虛擬鏈路分割是二次規(guī)劃問題，因此在問題規(guī)模較大時(shí)，顯著增加了映射的開銷。Q-partition算法和ABC-partition算法的平均映射開銷相差不大，在實(shí)驗(yàn)請求長度的范圍內(nèi)，兩者映射開銷均小于 25%，并且 Q-partition算法略優(yōu)于 ABC-partition算法，這是因?yàn)镼-partition算法具有更加智能的尋優(yōu)能力，保證了開銷的最小化。

3) 對比3種算法的服務(wù)鏈構(gòu)建請求接受率。觀察當(dāng)服務(wù)鏈構(gòu)建請求強(qiáng)度增加時(shí)，各算法服務(wù)鏈構(gòu)建請求接受率的變化趨勢。為便于觀察，將服務(wù)鏈構(gòu)建請求強(qiáng)度pA分別設(shè)置為(0 ,2,4,8,16,32,64)。如圖7所示，Q-partition算法具有最優(yōu)的服務(wù)鏈構(gòu)建請求接受率，這得益于本文提出的跨域服務(wù)鏈映射框架。該框架下，全局服務(wù)代理采用輪詢方式接受跨域服務(wù)鏈映射請求，在保證公平性的同時(shí)，避免了基礎(chǔ)設(shè)施平面資源分配的沖突，因此能夠更好地完成服務(wù)鏈構(gòu)建請求的映射任務(wù)。此外，基于 Q-learning的Q-partition算法能夠高效地完成構(gòu)建請求的映射任務(wù)，因此可以在有限時(shí)間內(nèi)接受更多的服務(wù)鏈構(gòu)建請求。

圖6 服務(wù)鏈構(gòu)建請求平均映射開銷

圖7 服務(wù)鏈構(gòu)建請求接受率

5.2.2 算法適應(yīng)性評估

針對本文所提Q-partition算法，在不同物理網(wǎng)絡(luò)拓?fù)溥B接條件下，從平均分割時(shí)間和平均映射開銷2個(gè)方面分析算法的適應(yīng)性。

上述實(shí)驗(yàn)中，邊界節(jié)點(diǎn)間采用全連接的方式進(jìn)行。但應(yīng)指出的是，全連接的物理網(wǎng)絡(luò)在實(shí)際運(yùn)用中并不具有代表性。參考文獻(xiàn)[24]中的實(shí)驗(yàn)參數(shù)設(shè)置，本節(jié)將連接概率設(shè)置為 0.2、0.5和 1.0，分別對應(yīng)topology1、topology2和topology3，體現(xiàn)邊界節(jié)點(diǎn)低概率、中概率和全連接的3種方式，從而有效評估算法的適應(yīng)性。

如圖8所示，Q-partition算法并沒有受物理網(wǎng)絡(luò)拓?fù)渥兓挠绊?，擁有較好的適應(yīng)性。

圖8 不同拓?fù)湎碌乃惴ǚ€(wěn)定性

6 結(jié)束語

本文研究了 SDNFV環(huán)境下跨域服務(wù)鏈映射問題。提出了一種分層分域、區(qū)域集中管理與全局協(xié)同調(diào)度相結(jié)合的虛擬服務(wù)資源管控架構(gòu)。在此基礎(chǔ)上，針對跨域服務(wù)鏈映射問題，建立了一種采用輪詢機(jī)制的請求響應(yīng)框架，在此框架下設(shè)計(jì)了一種基于 Q-learning機(jī)制的跨域服務(wù)鏈構(gòu)建請求分割算法。仿真實(shí)驗(yàn)表明，本文方法相較傳統(tǒng)方法在平均分割時(shí)間、平均映射開銷和服務(wù)鏈構(gòu)建請求接受率等方面具有更好的優(yōu)化效果。后續(xù)工作中將針對可靠性條件下的跨域服務(wù)鏈映射問題進(jìn)行進(jìn)一步研究。

附錄A 定理1證明

證明式(8)由兩部分組成，分別是節(jié)點(diǎn)映射開銷Objn和域間鏈路映射開銷Objl。節(jié)點(diǎn)映射開銷Objn是固定的常數(shù)，所以是有界的，域間鏈路映射開銷Objl由流量矩陣和連接邊界節(jié)點(diǎn)間鏈路的最小單位開銷矩陣的乘積形式表示，是離散的有限值，故式(8)定義的收益函數(shù)R的值有界。證畢。

附錄B 定理2證明

將Q值函數(shù)初始值定義為均依據(jù)式(12)更新，直至獲得最優(yōu)值

1234和 γ ( 0 ＜ γ＜ 1 )滿足

如果 0 ≤ ε3≤ ε4＜1，對 ?t= 1 ,2,…，函數(shù)滿足

下面，通過數(shù)學(xué)歸納法證明式(18)。

當(dāng)t=1時(shí)，有

同理可得

即當(dāng)t=1時(shí)，滿足式(18)。

假設(shè)t=?-1，? = 2 ,3,...時(shí)，滿足式(18)。那么，當(dāng)t=?時(shí)，有

同理可得

因此，對 ?t= 1 ,2,… ，滿足式(18)。

隨后，證明當(dāng) 0 ≤ ε3≤ 1 ≤ ε4＜ ∞ 時(shí)，滿足

由式(19)和式(21)可證式(23)的左半部分，這里不再贅述。對于式(23)的右半部分，令t=1，有

同上，利用數(shù)學(xué)歸納法可得式(23)的右半部分。因此，當(dāng)0 ≤ ε3≤ ε4＜ ∞ ，對 ?t= 1 ,2,… ，Q值函數(shù)滿足式(18)。

綜上，對任意常量 ε1,ε2, ε3, ε4，當(dāng)t→ ∞ 時(shí)，可得式(14)。證畢。