基于Q-learning的跨域服務鏈映射機制

2019-01-31 02:34:24張紅旗黃睿楊英杰常德顯張連成

通信學報 2018年12期

關鍵詞：服務

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

（中國人民解放軍戰略支援部隊信息工程大學密碼工程學院，河南鄭州 450001）

1 引言

軟件定義網絡（SDN, software defined network）將復雜的控制功能從傳統網絡設備中剝離出來，使數據平面僅負責高速轉發，而網絡的控制與管理由邏輯集中的控制平面基于全局網絡視圖與狀態進行統一決策，有效簡化了網絡管理[1-2]。網絡功能虛擬化（NFV，network function virtualization）是針對運營商網絡中網絡功能靜態僵化問題而提出的SDN解決方案[3-4]。NFV將以專有硬件形式部署的網絡功能轉變為在通用服務器上運行的虛擬網絡功能（VNF, virtual network function），解耦傳統網絡設備的軟件功能和硬件載體，減少了在網絡特定位置部署中間件的開銷，增加了網絡設備部署的靈活性。由此，借助SDN/NFV的軟件定義網絡功能虛擬化（SDNFV, software defined network function virtualization）技術應運而生[5]。

作為SDNFV技術的典型應用，服務鏈近年來頗受關注[6]。服務鏈在利用NFV技術將傳統網絡功能虛擬化并部署在服務節點的基礎上，借助 SDN的流量集中管控功能，依據用戶/業務的服務請求引導流量按序經過服務節點上的 VNF實例，進而為用戶/業務提供可定制的網絡服務。每條服務鏈可看作由一個或多個 VNF實例按照既定次序連接而成的邏輯視圖。因此，如何設計合理的服務鏈映射方法完成邏輯視圖向物理拓撲的映射已成為該領域的研究熱點。

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

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

1) 基于SDN的典型實現方式，提出一種分層分域的虛擬服務資源管控架構，縱向包含基礎設施平面、邏輯控制平面和應用管理平面，橫向包含各OpenFlow自治域、區域服務代理和全局服務代理，共同實現虛擬服務資源的區域集中管理和全局協同調度。

2) 在上述虛擬服務資源管控架構的基礎上，建立一種基于輪詢機制的跨域服務鏈映射框架。該框架下，全局服務代理采用輪詢方式接受各區域服務代理上報的跨域服務鏈映射請求，在保證系統公平性的同時有效避免基礎設施平面資源分配的沖突。

3) 針對需要進行跨域映射的服務鏈構建請求，設計一種基于Q-learning機制的跨域服務鏈構建請求分割算法，以最小化映射開銷為目標，采用智能化的方法進行優化求解，實現跨域服務請求的及時響應及跨域服務鏈的高效映射。

2 虛擬服務資源管控架構

SDNFV環境下網絡功能的硬件載體和軟件功能改變了以往緊密耦合的特點，實現了虛擬服務資源的靈活管控，分離形成基礎設施平面、邏輯控制平面和應用管理平面，如圖1所示。

2.1 基礎設施平面

傳統物理網絡的基礎設施平面是由各種異構網絡體系相互融合形成的復雜巨網絡，其具有覆蓋范圍廣、組成結構復雜的特點，要實現如此大規模的資源管理和維護是相當困難的。本文提出了虛擬服務資源管控架構，將基礎設施平面劃分為多個OpenFlow自治域（如圖1中OPNFV-D1～OPNFV-D3），每個自治域由各自的SDN控制器和NFV編排器進行區域控制，管理和維護區域內的網絡通信資源和虛擬服務資源。各個自治域之間相對獨立，共同協作以實現為用戶/業務的多樣化服務鏈映射請求提供及時有效的響應。

2.2 邏輯控制平面

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

2.3 應用管理平面

應用管理平面是位于邏輯控制平面之上的擴展平面，可根據需要進行擴充。本文構建了由全局服務代理、服務信息數據庫、服務鏈分割算法和單域映射算法組成的管理中心以滿足跨域服務鏈映射的需求。全局服務代理是為了實現分布式協同調度的需要，負責管理區域服務代理的加入或退出，并實時掌握域內邊界節點以及域間鏈路的拓撲連接關系及使用情況。當出現跨域服務鏈映射請求時，統一協調各區域服務代理進行協同處理。服務信息數據庫負責存儲域內的虛擬服務資源信息及域間的狀態連接信息，為算法提供計算依據。服務鏈分割算法是解決跨域服務鏈映射問題的核心，當服務鏈不需要進行分割時即轉化為單域服務鏈映射問題，可采用相應的單域映射算法進行求解。

3 跨域服務鏈映射問題描述

在第2節的架構中，基礎設施平面為滿足區域集中管理、全局協同調度的需求被劃分為不同的OpenFlow自治域，本節的跨域服務鏈映射問題研究正是基于此進行的。服務代理依據用戶/業務的服務鏈映射需求及網絡資源狀態完成服務鏈的構建，從而實現邏輯映射需求與物理網絡資源之間的有效匹配，如圖2所示。

3.1 底層物理網絡

如圖2所示，底層物理網絡被劃分為DN個不同的 OpenFlow自治域（此處DN=3），可用有權無向圖表示。其中，NS代表底層物理節點集合，包括域內節點集合NSi和邊界節點集合NSb，域內節點集合NSi又可細分為服務節點集合NSi_S和轉發節點集合NSi_F，對表示服務節點ns的I類資源的容量，代表底層物理鏈路集合，包括域內鏈路集合LSi和域間鏈路集合表示其帶寬資源容量。依據第2節的虛擬服務資源管控架構，可將整個底層物理網絡視圖劃分為全局視圖和區域視圖。全局視圖用表示，描述了全網邊界節點和域間鏈路的分布狀況，而區域視圖描述了每個OpenFlow自治域內的物理拓撲連接情況。

圖2 跨域服務鏈映射問題描述

3.2 服務鏈構建請求

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

3.3 服務鏈映射

服務鏈映射問題可形式化表示如下。Mapping:，按照映射區域的不同可將其劃分為單域映射和跨域映射。單域服務鏈映射是將VNF實例和VNF鏈路根據一定的約束條件及目標函數映射到某一OpenFlow自治域范圍內的底層物理網絡上，而跨域服務鏈映射不同于單域服務鏈映射。因為在單域映射問題中，域內的拓撲連接情況及虛擬資源狀態都是已知的，而對于跨域映射，不同的OpenFlow自治域之間信息都是不對外公開的。因此，需要采取分布式映射機制，實現域間映射和域內映射的協同，有效滿足映射需求，并實現網絡資源的充分使用。

4 跨域服務鏈映射策略

針對跨域服務鏈映射問題的特殊性，本文提出一種基于請求分割的分布式跨域服務鏈映射策略。首先，在第2節虛擬服務資源管控架構的基礎上建立跨域服務鏈映射框架，描述服務鏈映射的具體流程。在此基礎上，基于Q-learning機制設計跨域服務鏈構建請求分割算法，以實現跨域服務鏈構建請求在域間和域內的協同映射。

4.1 跨域服務鏈映射框架

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

1) 用戶/業務依據就近原則向區域服務代理發出服務鏈構建請求，區域服務代理將其轉化為服務鏈邏輯視圖，判斷其需要進行單域映射還是跨域映射，并將其劃歸于相應的集合

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

4) 全局服務代理周期性地對各個區域服務代理進行輪詢，只有輪詢到的區域服務代理才能向全局服務代理發出跨域映射請求，以避免跨域映射請求處理出現沖突和全局服務代理發生過載。

4.2 基于Q-learning的跨域服務鏈構建請求分割

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

4.2.1 模型建立

跨域服務鏈構建請求分割問題是指以降低跨域服務鏈映射開銷為目標，根據各OpenFlow自治域的資源匹配狀況和邊界節點的相關信息，將跨域服務鏈映射請求分割為多個單域服務鏈映射請求，從而形成一套有效的服務鏈映射方案。

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

跨域服務鏈構建請求分割問題可看作是滿足以下映射條件，以最小化跨域服務鏈映射開銷為目標的最優化問題。

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

1) 變量定義

定義1分割方案矩陣Hm×n。服務鏈構建請求中 VNF實例節點的數目用m表示，物理網絡中邊界節點的數目用n表示。如式(4)所示，矩陣項H[i] [j]的取值表示 VNF實例節點i和邊界節點j之間的映射關系。

圖3 跨域服務鏈映射框架

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

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

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

2) 約束條件

跨域服務鏈構建請求分割問題需滿足以下約束條件。

式(6)表示矩陣H中的每一行之和小于或等于1，因為每個VNF實例節點只能被映射到一個OpenFlow自治域。式(7)確保了 VNF實例鏈路的帶寬資源需求不超過物理鏈路的帶寬資源容量。

3) 目標函數

跨域服務鏈構建請求分割問題的求解目標找到使得服務鏈映射開銷最小的分割方案，其目標函數Obj可表示為

目標函數Obj中的3個參數具體含義如下。

Hm×n：VNF實例節點與物理網絡邊界節點的映射關系矩陣。

FMm×m：服務鏈構建請求的流量矩陣，表示VNF實例節點i和VNF實例節點j之間的帶寬資源需求。

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

為便于目標函數Obj的計算，本文定義一種特殊的運算，用符號⊙表示。

由于服務鏈的節點映射開銷是一定的，而服務鏈的域間鏈路映射開銷隨邊界節點選取的不同而不同。因此，用常數C表示節點映射開銷Objn，用表示域間鏈路映射開銷表示VNF實例節點i映射到了邊界節點u，而VNF實例節點j映射到了邊界節點v。目標函數Obj中的系數α和β用于調節節點映射開銷Objn和域間鏈路映射開銷Objl的權重。

4.2.2 算法準備

強化學習是人工智能領域機器學習技術中的重要方法之一。作為一種交互式學習方法，其強調在與環境的作用中學習獲得評價性的反饋信號，并據此改進行動方案以適應環境，從而達到預期的目的。

作為強化學習的典型實現方式，Q-learning算法常用于求解先驗知識較少的復雜決策優化問題。如圖4所示，Q-learning算法模型是一個自適應閉環控制系統。智能體Q-A gent 首先通過感知環境狀態，在當前狀態s的基礎上依據Q值函數選擇一個動作a并執行，當遷移到下一狀態s′時，智能體Q-A gent 依據環境的反饋計算收益函數R(s,a)并據此更新Q值函數Q(s,a)，然后依據新的Q值和當前環境狀態選擇下一個動作，迭代進行直至得到問題的最優策略。

圖4 Q-learning算法模型

Q-learning算法中Q值函數是狀態和行為的評價值，可用瞬時回報和未來回報來表示。

其中，st和at表示當前狀態和行為，st+1和at+1表示下一個狀態和行為，折扣系數γ是滿足0＜γ＜1的常數，用于調節智能體Q-A gent對未來回報的關注程度。

當系統處于狀態st時，依據式(11)來選擇行為at。

為了避免算法落入局部最優，本文采取ε- g reedy[17]的動作選取方式，即以小概率ε隨機選擇一個動作進行探索，以1-ε的概率根據Q值選取當前最佳動作，ε可動態改變，將其設置為其中E表示學習循環的次數。其目的在于，智能體Q-A gent在學習前期可采用隨機方式進行更好地探索，而在學習后期更偏向于根據Q值指導下一步的動作選擇。

當選定并執行該動作后，系統進入下一狀態at+1，同時系統也得到相應的收益函數R(st,at)，可依據式(12)對Q值函數進行迭代更新。

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

在利用 Q-learning算法解決現實問題的過程中，最重要的是將一個實際的問題轉化成為Q-learning算法模型并以此得到優化的策略結果。即根據所要解決的實際問題，定義環境中的狀態空間、動作集合和收益函數。結合本文所提的跨域服務鏈構建請求分割問題，可分別將其定義如下。

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

定義4動作集合A。對每一個VNF實例節點i和邊界節點j組成的狀態二元組s(i,j)，可對其進行映射、不映射和不在映射范圍3種操作，分別對應動作a1、a0和a-1。因此，動作集合可表示為

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

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

定理1由式(8)定義的收益函數R的值在不同系統狀態下有界。

證明見附錄A。

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

則當t→∞時，有

證明見附錄B[19]。

4.2.3 算法描述

如表2所示，在上述準備工作的基礎上，可將基于Q-learning的跨域服務鏈構建請求分割算法描述如下。需要注意的是該算法將針對某一特定的跨域服務鏈構建請求中 VNF實例節點與邊界節點的映射關系進行說明。

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

5 方案分析與評估

為全面評估本文所提跨域服務鏈映射策略的有效性，本文從以下兩方面開展仿真實驗。

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

2) 在不同物理網絡拓撲連接條件下，比較本文算法在平均分割時間和平均映射開銷方面的變化，以驗證本文方法（Q-partition）的適應性。

5.1 實驗設置

仿真實驗在配置Ubuntu 14.04 64位操作系統的Intel Core i7-6300HQ @3.40 GHz、8 GB內存的PC機上進行。以Mininet模擬器為基礎，采用開源的Floodlight控制器，使用Java語言編寫實驗代碼并利用Matlab工具對實驗結果進行分析。每次實驗運行50 000個時間單位。

將底層物理網絡劃分為10個OpenFlow自治域，每個域內用GT-ITM[22]工具生成物理網絡拓撲，拓撲由50個節點組成，包括6個服務節點、40個轉發節點和4個邊界節點，邊界節點之間采用全連接的方式，域內節點以0.5的概率相連。為評估算法的自適應性，假設跨域服務鏈構建請求動態到達，且服從時間單位為1 000，強度為pA的泊松過程，請求的生命周期服從均值為60個時間單位的指數分布。假設網絡中有8種VNF，每種VNF有3種不同的VNF實例，每個構建請求由一個或多個 VNF實例組成，數量服從的均勻分布。為便于討論，目標函數Obj中的系數α和β均取1，折扣系數γ取0.8。

5.2 實驗結果分析

5.2.1 算法性能對比

將本文算法（Q-partition）與LID-partition算法和ABC-partition算法進行對比，幾種算法域內映射統一采用文獻[23]中的算法，從平均分割時間、平均映射開銷和服務鏈構建請求接受率3個方面進行分析。

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

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

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

圖5 服務鏈構建請求平均分割時間

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

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

圖6 服務鏈構建請求平均映射開銷

圖7 服務鏈構建請求接受率

5.2.2 算法適應性評估

針對本文所提Q-partition算法，在不同物理網絡拓撲連接條件下，從平均分割時間和平均映射開銷2個方面分析算法的適應性。

上述實驗中，邊界節點間采用全連接的方式進行。但應指出的是，全連接的物理網絡在實際運用中并不具有代表性。參考文獻[24]中的實驗參數設置，本節將連接概率設置為 0.2、0.5和 1.0，分別對應topology1、topology2和topology3，體現邊界節點低概率、中概率和全連接的3種方式，從而有效評估算法的適應性。

如圖8所示，Q-partition算法并沒有受物理網絡拓撲變化的影響，擁有較好的適應性。

圖8 不同拓撲下的算法穩定性

6 結束語

本文研究了 SDNFV環境下跨域服務鏈映射問題。提出了一種分層分域、區域集中管理與全局協同調度相結合的虛擬服務資源管控架構。在此基礎上，針對跨域服務鏈映射問題，建立了一種采用輪詢機制的請求響應框架，在此框架下設計了一種基于 Q-learning機制的跨域服務鏈構建請求分割算法。仿真實驗表明，本文方法相較傳統方法在平均分割時間、平均映射開銷和服務鏈構建請求接受率等方面具有更好的優化效果。后續工作中將針對可靠性條件下的跨域服務鏈映射問題進行進一步研究。