基于強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法

魏亮，黃韜，張嬌，王澤南，劉江，劉韻潔

?

基于強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法

魏亮，黃韜，張嬌，王澤南，劉江，劉韻潔

（北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876）

提出基于人工智能技術(shù)的多智能體服務(wù)鏈資源調(diào)度架構(gòu)，設(shè)計(jì)一種基于強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法。通過Q-learning的機(jī)制，根據(jù)系統(tǒng)狀態(tài)、執(zhí)行部署動(dòng)作后的獎(jiǎng)懲反饋來決定服務(wù)鏈中各虛擬網(wǎng)元的部署位置。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典算法相比，該算法有效降低了業(yè)務(wù)的平均傳輸延時(shí)，提升了系統(tǒng)的負(fù)載均衡情況。

網(wǎng)絡(luò)功能虛擬化；人工智能；服務(wù)鏈；強(qiáng)化學(xué)習(xí)

1 引言

網(wǎng)絡(luò)功能虛擬化[1]（NFV, network function virtualization）是未來網(wǎng)絡(luò)領(lǐng)域的重要研究方向。NFV技術(shù)將網(wǎng)絡(luò)功能軟件整合部署到行業(yè)標(biāo)準(zhǔn)的服務(wù)器、交換機(jī)和存儲硬件上，取代傳統(tǒng)專用物理設(shè)備，從而達(dá)到降低成本、能耗和復(fù)雜性的目的。NFV同時(shí)具備軟件與硬件解耦、靈活的網(wǎng)絡(luò)功能部署、動(dòng)態(tài)的服務(wù)提供等能力。以運(yùn)營商為主導(dǎo)的NFV組織就是希望將NFV引入到運(yùn)營商網(wǎng)絡(luò)中，使傳統(tǒng)的運(yùn)營商網(wǎng)絡(luò)逐漸演進(jìn)為面向業(yè)務(wù)的新型網(wǎng)絡(luò)，進(jìn)而能夠快速將新業(yè)務(wù)帶給網(wǎng)絡(luò)用戶。因此，NFV具有硬件通用化、業(yè)務(wù)軟件化、資源彈性伸縮等特征，可以實(shí)現(xiàn)網(wǎng)絡(luò)低成本建設(shè)、高效率運(yùn)營和靈活業(yè)務(wù)提供。NFV MANO（NFV management and orchestration）[2]在ETSI ISG NFV架構(gòu)中被定義為由多個(gè)功能實(shí)體組合而成，主要負(fù)責(zé)管理和編排基礎(chǔ)設(shè)施、資源以及服務(wù)等。通過組合不同虛擬網(wǎng)絡(luò)功能來實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)的自動(dòng)化部署、生命周期管理和端到端的管理。

在NFV環(huán)境中，虛擬網(wǎng)絡(luò)功能（VNF, virtual network function）運(yùn)行在一個(gè)或多個(gè)虛擬機(jī)（也可以是容器）上，負(fù)責(zé)執(zhí)行處理特定的網(wǎng)絡(luò)功能[3]。單個(gè)虛擬網(wǎng)絡(luò)功能可以連接或組合在一起構(gòu)建全面的網(wǎng)絡(luò)通信服務(wù)。原先實(shí)體化網(wǎng)絡(luò)組件可以被相應(yīng)的虛擬網(wǎng)絡(luò)功能組件所替代，由NFVI來承載提供所需的虛擬化資源[4]，由MANO進(jìn)行統(tǒng)一地編排管理。常見的VNF包括虛擬的交換機(jī)（vSwitch）、虛擬的路由器（vRouter）、虛擬的防火墻（vFW）、虛擬的負(fù)載均衡（vLB）等網(wǎng)元。

網(wǎng)絡(luò)功能虛擬化可以和軟件定義網(wǎng)絡(luò)[5]（SDN, software-defined networking）技術(shù)有機(jī)結(jié)合。充分利用SDN設(shè)計(jì)理念將網(wǎng)絡(luò)的數(shù)據(jù)平面和控制平面進(jìn)行分離，并實(shí)現(xiàn)可編程控制[6]，形成應(yīng)用、控制、轉(zhuǎn)發(fā)3層架構(gòu)。SDN通過集中控制實(shí)現(xiàn)網(wǎng)絡(luò)資源的靈活調(diào)度、按需調(diào)控，而NFV可通過虛擬化技術(shù)實(shí)現(xiàn)網(wǎng)絡(luò)功能的靈活部署與動(dòng)態(tài)調(diào)整。NFV和SDN兩者可以相互補(bǔ)充，共同構(gòu)建智能化的網(wǎng)絡(luò)系統(tǒng)。

服務(wù)鏈（service chain）借助軟件定義網(wǎng)絡(luò)技術(shù)自動(dòng)創(chuàng)建一個(gè)連接網(wǎng)絡(luò)服務(wù)的虛擬服務(wù)鏈[7]，網(wǎng)絡(luò)流量可以按照業(yè)務(wù)邏輯要求的既定順序穿過VNF。服務(wù)鏈基于軟件的方式來創(chuàng)建虛擬鏈路連接，因此，這些連接可以通過NFV編排層來創(chuàng)建和釋放。NFV編排層不但能夠?qū)⒍鄠€(gè)VNF與物理網(wǎng)絡(luò)組件組合成服務(wù)鏈，同時(shí)還提供VNF放置和鏈接以及動(dòng)態(tài)擴(kuò)展和彈性服務(wù)。為了實(shí)現(xiàn)各種業(yè)務(wù)邏輯，服務(wù)鏈需要面向業(yè)務(wù)流來定義所需要的網(wǎng)絡(luò)功能以及處理方式。服務(wù)鏈技術(shù)可以廣泛應(yīng)用于數(shù)據(jù)中心、運(yùn)營商網(wǎng)絡(luò)、企業(yè)網(wǎng)絡(luò)等。

服務(wù)鏈定義了特定順序的網(wǎng)絡(luò)功能集合，其放置將影響業(yè)務(wù)編排、服務(wù)提供以及物理資源的使用效率。服務(wù)鏈需要面臨資源分配優(yōu)化、動(dòng)態(tài)流量調(diào)控、動(dòng)態(tài)服務(wù)映射、服務(wù)策略實(shí)施、服務(wù)可靠性及可用性、安全等方面的挑戰(zhàn)。它常常以最小化網(wǎng)絡(luò)延時(shí)、最小化能耗、最小化代價(jià)、最大化資源利用率等為目標(biāo)進(jìn)行建模優(yōu)化服務(wù)鏈映射問題[8]。

2 相關(guān)研究

服務(wù)鏈的映射放置能夠靈活利用基礎(chǔ)設(shè)施的資源，動(dòng)態(tài)編排網(wǎng)絡(luò)功能服務(wù)。因此，此方向領(lǐng)域是網(wǎng)絡(luò)功能虛擬化中的研究熱點(diǎn)。Kuo等[9]研究VNF放置和路徑選擇聯(lián)合優(yōu)化問題，提出了一種根據(jù)鏈路長度和服務(wù)器的使用情況來進(jìn)行服務(wù)鏈部署的算法。Mechtri等[10]提出一種基于基礎(chǔ)設(shè)施拓?fù)鋱D和請求的VNF轉(zhuǎn)發(fā)圖的鄰接矩陣特征分解的算法來實(shí)現(xiàn)分布式云環(huán)境下尋找服務(wù)鏈的最佳放置方案。Wang等[11]在考慮網(wǎng)絡(luò)代價(jià)和服務(wù)性能的基礎(chǔ)上提出了基于一跳流量調(diào)度和基于貪婪算法搜索多條路徑的兩階段服務(wù)鏈映射算法。Ye等[12]提出了基于關(guān)鍵子拓?fù)溆成浞答伒拈]環(huán)算法來聯(lián)合優(yōu)化VNF組合和服務(wù)鏈映射，從而達(dá)到最小化整體帶寬消耗的目的。Reddy等[13]提出了基于混合整數(shù)線性規(guī)劃的可變鄰域搜索算法來實(shí)現(xiàn)流量變化和延時(shí)受限情況下的服務(wù)鏈映射。Mehraghdam等[14]在考慮最小化延時(shí)等目標(biāo)的基礎(chǔ)上將服務(wù)鏈映射問題建模成混合整數(shù)二次約束規(guī)劃問題求解。Zhang等[15]提出根據(jù)網(wǎng)絡(luò)和請求來聯(lián)合優(yōu)化調(diào)度服務(wù)鏈放置問題，實(shí)現(xiàn)最大化平均資源利用率和最小化平均響應(yīng)時(shí)間。Hirwe等[16]通過有向無環(huán)圖來表征服務(wù)鏈，對拓?fù)渑判蛞宰疃搪窂椒胖梅?wù)鏈，達(dá)到最小化服務(wù)鏈跳數(shù)、減少SDN交換機(jī)上流規(guī)則條目、消除ping-pong流量的目的。Zhang等[17]針對流量增長情況下服務(wù)鏈的按需擴(kuò)展問題提出了兩步選擇的啟發(fā)式算法。Sahhaf等[18]提出了基于服務(wù)分解的服務(wù)鏈映射算法，指出基于資源感知的分解策略選擇將顯著提升算法性能。Moens等[19]研究了基于物理硬件和虛擬機(jī)混合場景下部署服務(wù)鏈的問題，借鑒軟件生產(chǎn)線工程理念提出了定制化的服務(wù)鏈放置算法。Fei等[20]針對分布式網(wǎng)絡(luò)功能虛擬化場景下端局選擇和VNF分配問題給出優(yōu)于啟發(fā)式的算法。Dietrich等[21]提出了基于線性規(guī)劃和圖分割的方法來解決多網(wǎng)絡(luò)服務(wù)提供商的服務(wù)鏈映射問題。

Habib等[22]提出了使用強(qiáng)化學(xué)習(xí)算法來解決云間資源分配和虛擬機(jī)管理問題，Groléat等[23]提出了基于分布式強(qiáng)化學(xué)習(xí)的方式來解決端到端服務(wù)質(zhì)量保證的問題，Lin等[24]提出了在多級層次化SDN中，使用強(qiáng)化學(xué)習(xí)的手段來構(gòu)建QoS感知的自適應(yīng)路由機(jī)制。

綜上所述，盡管目前在服務(wù)鏈放置等問題上已經(jīng)取得了很多研究成果，但是在動(dòng)態(tài)場景下資源智能調(diào)度研究方面依然欠缺。因此，在利用人工智能領(lǐng)域強(qiáng)化學(xué)習(xí)方法來提升服務(wù)鏈映射效果方面還存在進(jìn)一步深入研究的必要性。

3 問題描述

一般服務(wù)鏈映射問題可以分解成2個(gè)子問題，分別是VNF放置和VNF組鏈。VNF放置主要是考慮如何選擇合適的物理節(jié)點(diǎn)部署VNF虛擬機(jī)，而VNF組鏈?zhǔn)强紤]如何利用SDN技術(shù)進(jìn)行流量調(diào)度構(gòu)建服務(wù)鏈。

將服務(wù)鏈的平均鏈路延時(shí)和服務(wù)器的負(fù)載作為優(yōu)化目標(biāo)。

優(yōu)化目標(biāo)1 最小化服務(wù)鏈的平均鏈路延時(shí)

表1 變量及意義

優(yōu)化目標(biāo)2 使服務(wù)器的負(fù)載最均衡

使用簡單的線性加權(quán)法將2個(gè)優(yōu)化目標(biāo)進(jìn)行組合，得到最終的優(yōu)化目標(biāo)

4 系統(tǒng)設(shè)計(jì)

服務(wù)鏈技術(shù)將在5G、物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)等新興應(yīng)用場景中大顯身手，可以利用SDN/NFV技術(shù)和人工智能技術(shù)實(shí)現(xiàn)網(wǎng)絡(luò)資源的智能調(diào)度和服務(wù)鏈的映射。SDN控制器作為網(wǎng)絡(luò)的大腦，可以賦予強(qiáng)化學(xué)習(xí)的能力。能夠?qū)崟r(shí)收集網(wǎng)絡(luò)的狀態(tài)和行為數(shù)據(jù)，捕獲路由信息、流量信息、拓?fù)滏溌?，?shí)時(shí)遙測、分析、計(jì)算、優(yōu)化、控制。同樣，NFV MANO平臺也可以集成智能管理的能力，能夠統(tǒng)一化、精細(xì)化、智能化管理計(jì)算、存儲、網(wǎng)絡(luò)三維資源。基于兩者的協(xié)同控制就可以形成自動(dòng)化閉環(huán)管理，可以構(gòu)建自學(xué)習(xí)、自愈、自優(yōu)化、自服務(wù)的智能網(wǎng)絡(luò)。

基于SDN/NFV技術(shù)構(gòu)建的新型網(wǎng)絡(luò)毫無疑問具有高度復(fù)雜性和內(nèi)在分布性，而且處于開放變化的動(dòng)態(tài)環(huán)境中。多agent技術(shù)主要研究一組自治的agent在分布式開放的動(dòng)態(tài)環(huán)境下，通過交互、合作、競爭、協(xié)商等智能行為完成復(fù)雜的控制。本文提出一種基于多智能體強(qiáng)化學(xué)習(xí)技術(shù)的服務(wù)鏈資源調(diào)度架構(gòu)。

4.1 系統(tǒng)架構(gòu)

在NFV MANO架構(gòu)中，SDN orchestrator（SDN-O）負(fù)責(zé)端到端的網(wǎng)絡(luò)連接服務(wù)、服務(wù)資源編排、流量工程等；一般會(huì)管理多個(gè)域內(nèi)控制器或超級控制器。NFV orchestrator（NFV-O）負(fù)責(zé)網(wǎng)絡(luò)服務(wù)的生命周期管理、VNF部署等；一般部署在數(shù)據(jù)中心或企業(yè)網(wǎng)等。Global service orchestrator（GS-O）負(fù)責(zé)跨域之間的協(xié)同編排、端到端的服務(wù)編排等。一般會(huì)管理一個(gè)SDN-O以及多個(gè)NFV-O，同時(shí)一個(gè)SDN-O會(huì)管理一個(gè)或多個(gè)SDN域（SDN domain）。每個(gè)SDN域有相應(yīng)的控制器側(cè)重實(shí)現(xiàn)網(wǎng)絡(luò)資源抽象、路徑計(jì)算等功能。NFV-O一般部署在數(shù)據(jù)中心或企業(yè)網(wǎng)，而SDN控制器依據(jù)其應(yīng)用在數(shù)據(jù)中心、廣域網(wǎng)、光傳輸網(wǎng)等不同場景進(jìn)行細(xì)分。

本文系統(tǒng)架構(gòu)在基礎(chǔ)設(shè)施平面、控制管理平面的基礎(chǔ)上增加一個(gè)智能服務(wù)平面，在智能服務(wù)平面上構(gòu)建由SDN domain agent、NFV-O agent、GS-O agent等部件組成的多agent智能協(xié)同管理系統(tǒng)。根據(jù)架構(gòu)設(shè)計(jì)的需要，定義幾個(gè)新的功能實(shí)體，如下所示。

1) SDN domain agent?；赟DN控制器進(jìn)行網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)的收集、分析、策略執(zhí)行。具體包含監(jiān)控引擎、分析引擎、策略引擎。其中，監(jiān)控引擎主要通過南向接口協(xié)議的統(tǒng)計(jì)分組、發(fā)送探測分組等手段獲得鏈路拓?fù)洹①|(zhì)量、延時(shí)、利用率等網(wǎng)絡(luò)的全局監(jiān)控信息。

2) NFV-O agent。通過NFVO、VNF manager、VIM等系統(tǒng)部件完成網(wǎng)絡(luò)服務(wù)、VNF等信息的收集、分析、策略執(zhí)行。NFV-O agent亦包含監(jiān)控引擎、分析引擎、策略引擎。其中，監(jiān)控引擎主要通過VIM、VNF manager等渠道實(shí)時(shí)掌握基礎(chǔ)設(shè)施資源使用情況、網(wǎng)絡(luò)服務(wù)的運(yùn)行情況等。

3) GS-O agent。負(fù)責(zé)全局資源及業(yè)務(wù)信息的收集、分析、策略執(zhí)行。根據(jù)SDN domain agent以及NFV-O agent搜集的信息進(jìn)行全局的精細(xì)化智能，實(shí)現(xiàn)SDN域和NFV域的有機(jī)協(xié)同。其同樣包含監(jiān)控引擎、分析引擎、策略引擎。

由于SDN domain agent、NFV-O agent、GS-O agent的分析引擎和策略引擎需要根據(jù)業(yè)務(wù)場景等靈活構(gòu)建，涉及技術(shù)手段繁多，本文簡要介紹其功能作用。分析引擎先將監(jiān)控引擎存儲到數(shù)據(jù)庫的信息進(jìn)行聚合和關(guān)聯(lián)，如數(shù)據(jù)規(guī)范化、刪除冗余信息等。然后全面分析預(yù)測網(wǎng)絡(luò)的未來狀態(tài)，通過數(shù)據(jù)挖掘和人工智能等技術(shù)手段對未來趨勢進(jìn)行研究判斷。策略引擎通過對網(wǎng)絡(luò)狀態(tài)的診斷，決策產(chǎn)生主動(dòng)或被動(dòng)的措施或策略，避免出現(xiàn)已經(jīng)發(fā)現(xiàn)或可能出現(xiàn)的網(wǎng)絡(luò)問題，并通過SDN控制器或NFV-O來執(zhí)行具體的策略。

本文系統(tǒng)架構(gòu)將構(gòu)建一個(gè)層次化的多agent強(qiáng)化學(xué)習(xí)管理體系，該體系中的每一個(gè)agent 都代表一定的角色。其中，GS-O agent是全局管理者，主要擔(dān)當(dāng)網(wǎng)絡(luò)服務(wù)的總體控制決策功能，根據(jù)網(wǎng)絡(luò)服務(wù)特征、拓?fù)浣Y(jié)構(gòu)、需求預(yù)測及工作負(fù)載等因素對整個(gè)基礎(chǔ)設(shè)施的運(yùn)行狀況做出評估，其目的是尋求總體控制效果最優(yōu)。SDN domain agent或NFV-O agent作為局域控制agent，由若干區(qū)域協(xié)調(diào)控制系統(tǒng)構(gòu)成，接收局部信息和限制條件，在接收GS-O agent綜合評估的基礎(chǔ)上，自主決定相應(yīng)的控制策略，進(jìn)而達(dá)到最優(yōu)化控制本域基礎(chǔ)設(shè)施運(yùn)行的目標(biāo)，并及時(shí)將業(yè)務(wù)需求預(yù)測和控制效果傳送給GS-O agent，作為后續(xù)評估的參考。該架構(gòu)可以支持多個(gè)域之間協(xié)同編排，針對不同應(yīng)用場景的跨域服務(wù)鏈。具體系統(tǒng)架構(gòu)如圖1所示。

4.2 系統(tǒng)控制及流程

由于多agent學(xué)習(xí)離不開agent之間的通信，因此基于層次化的多agent強(qiáng)化學(xué)習(xí)通過梳理不同職能的agent之間的管理關(guān)系以及共享智能平面的信息數(shù)據(jù)，大大減少了各agent之間的通信開銷。各自治agent主要采用強(qiáng)化學(xué)習(xí)的方式進(jìn)行學(xué)習(xí)，通過不斷與基礎(chǔ)設(shè)施和業(yè)務(wù)服務(wù)環(huán)境的接觸獲取控制經(jīng)驗(yàn)并改善控制行為。通過外部環(huán)境提供的強(qiáng)化信號（獎(jiǎng)勵(lì)或懲罰）對控制動(dòng)作的好壞做出客觀評價(jià)。通過這種方式，各agent在行動(dòng)—評價(jià)的體系中獲得知識，改進(jìn)行動(dòng)方案以適應(yīng)外部環(huán)境需求。同時(shí)每一個(gè)agent強(qiáng)化學(xué)習(xí)框架結(jié)構(gòu)包含監(jiān)控引擎、分析引擎、策略引擎，分別對應(yīng)狀態(tài)感知器、學(xué)習(xí)器、動(dòng)作選擇器等能力。狀態(tài)感知器把環(huán)境狀態(tài)映射成agent的內(nèi)部感知；學(xué)習(xí)器根據(jù)環(huán)境狀態(tài)的獎(jiǎng)賞值以及內(nèi)部感知，更新agent的策略知識；動(dòng)作選擇器根據(jù)當(dāng)前策略選擇動(dòng)作作用于環(huán)境。這樣整個(gè)系統(tǒng)控制如圖2所示，非常適合以強(qiáng)化學(xué)習(xí)的算法框架進(jìn)行建模處理。

圖1 基于多agent強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射資源調(diào)度系統(tǒng)架構(gòu)

在這個(gè)多agent強(qiáng)化學(xué)習(xí)服務(wù)鏈調(diào)度體系架構(gòu)中存在agent之間的協(xié)作。如一般SDN controller和NFV-O部署在同一物理場所（如數(shù)據(jù)中心等）。因此，SDN domain agent和NFV-O agent之間可以充分協(xié)作，交互同步虛擬網(wǎng)元、網(wǎng)絡(luò)接入端口、網(wǎng)絡(luò)流量等信息。此外，2個(gè)SDN域之間也存在協(xié)同調(diào)度，如一個(gè)數(shù)據(jù)中心SDN控制器和一個(gè)廣域網(wǎng)SDN控制器等。同樣2個(gè)NFV域之間有時(shí)也需要?jiǎng)討B(tài)交換計(jì)算、存儲、網(wǎng)絡(luò)的資源分配情況以及虛擬機(jī)的生成銷毀情況等。根據(jù)任務(wù)類型分類，可以認(rèn)為各agent之間是充分合作的，可以雙向通知感知對方狀態(tài)。

系統(tǒng)可以承載虛擬化核心網(wǎng)、虛擬化內(nèi)容分發(fā)網(wǎng)絡(luò)、云安全防護(hù)等多種業(yè)務(wù)，動(dòng)態(tài)智能調(diào)度底層計(jì)算、存儲、網(wǎng)絡(luò)資源并依據(jù)業(yè)務(wù)特性進(jìn)行編排。當(dāng)需要進(jìn)行服務(wù)鏈映射時(shí)，其處理流程如圖3所示。

1) 用戶向GS-O發(fā)起服務(wù)鏈構(gòu)建請求，GS-O agent根據(jù)請求描述輸出放置決策。

2) GS-O進(jìn)行響應(yīng)檢查可用資源并進(jìn)行資源預(yù)留，通知NFV-O和SDN controller執(zhí)行具體資源分配。

3) NFV-O向NFV-O agent請求資源分配策略，實(shí)例化VNF。

4) SDN controller向SDN domain agent請求SDN組鏈策略，下發(fā)流表進(jìn)行流量調(diào)度構(gòu)建服務(wù)鏈。

5) GS-O給用戶反饋服務(wù)鏈構(gòu)建成功信息。

5 基于強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法

強(qiáng)化學(xué)習(xí)是人工智能領(lǐng)域機(jī)器學(xué)習(xí)技術(shù)中的重要方法之一，它區(qū)別于監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)的地方在于其與環(huán)境交互的特點(diǎn)。強(qiáng)化學(xué)習(xí)是一種交互式的學(xué)習(xí)方法，強(qiáng)調(diào)在與環(huán)境的交互中學(xué)習(xí)獲得評價(jià)性的反饋信號，在不需要給定各種狀態(tài)下輸入信號的期望輸出情況下，通過最大化未來回報(bào)為學(xué)習(xí)目標(biāo)。因此，強(qiáng)化學(xué)習(xí)具有自學(xué)習(xí)和在線學(xué)習(xí)的優(yōu)點(diǎn)，在求解先驗(yàn)信息較少的復(fù)雜優(yōu)化決策問題中具有廣泛的應(yīng)用場景。

強(qiáng)化學(xué)習(xí)運(yùn)用智能體對環(huán)境做出主動(dòng)試探，不斷地試錯(cuò)交互來進(jìn)行學(xué)習(xí)。智能體首先感知環(huán)境狀態(tài)，并根據(jù)環(huán)境當(dāng)前狀態(tài)和內(nèi)部控制策略選擇一個(gè)動(dòng)作并執(zhí)行。環(huán)境遷移到新狀態(tài)后，給出一個(gè)新的強(qiáng)化信號對智能體選擇動(dòng)作的好壞做出評價(jià)。智能體根據(jù)環(huán)境反饋的獎(jiǎng)賞值計(jì)算回報(bào)并更新內(nèi)部控制策略。然后根據(jù)新的強(qiáng)化信號和當(dāng)前環(huán)境狀態(tài)選擇下一個(gè)動(dòng)作。智能體選擇動(dòng)作的原則是使從環(huán)境中獲得正強(qiáng)化信號的概率增大，受到懲罰的概率變小。智能體應(yīng)選擇能最大化長期獎(jiǎng)賞之和的動(dòng)作。因此，在利用強(qiáng)化學(xué)習(xí)解決現(xiàn)實(shí)問題過程中，最重要的是將一個(gè)實(shí)際的問題轉(zhuǎn)化成為強(qiáng)化學(xué)習(xí)的模型并利用相關(guān)的算法來得到優(yōu)化的策略結(jié)果。即根據(jù)所要解決的實(shí)際問題，定義環(huán)境中的狀態(tài)集、動(dòng)作集和反饋函數(shù)。在服務(wù)鏈映射問題中，定義如下。

圖2 基于多agent強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射資源調(diào)度控制架構(gòu)

圖3 基于多agent的服務(wù)鏈映射資源調(diào)度流程

定義1 狀態(tài)集。為服務(wù)鏈中各VNF選擇物理服務(wù)器節(jié)點(diǎn)進(jìn)行部署的關(guān)鍵在于根據(jù)各個(gè)節(jié)點(diǎn)的實(shí)時(shí)狀態(tài)選擇合適的放置節(jié)點(diǎn)。首先，基于物理服務(wù)器節(jié)點(diǎn)已經(jīng)使用的vCPU數(shù)量定義單個(gè)節(jié)點(diǎn)的狀態(tài)，為每個(gè)節(jié)點(diǎn)的vCPU使用量設(shè)置一個(gè)門限值，假設(shè)超過該門限值，則該節(jié)點(diǎn)狀態(tài)為1，否則，節(jié)點(diǎn)狀態(tài)為0。然后考慮全局節(jié)點(diǎn)的狀態(tài)，假設(shè)有個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有0和1這2種狀態(tài)，則全局有2種狀態(tài)。如用二進(jìn)制表示狀態(tài)值為“0010”，則表示其中一個(gè)節(jié)點(diǎn)的資源使用超過門限，其余節(jié)點(diǎn)沒有超過門限。除了全局節(jié)點(diǎn)的狀態(tài)，由于業(yè)務(wù)流量需要按順序經(jīng)過服務(wù)鏈中的VNF，因此，當(dāng)前VNF的部署位置與其在服務(wù)鏈中的上一個(gè)VNF的部署位置有一定的聯(lián)系，流量會(huì)在這2個(gè)相鄰的VNF節(jié)點(diǎn)位置之間進(jìn)行轉(zhuǎn)發(fā)。所以本文將上一個(gè)VNF部署的節(jié)點(diǎn)位置引入狀態(tài)信息中，假設(shè)有個(gè)節(jié)點(diǎn)，則有種可能。綜上，狀態(tài)集中的狀態(tài)個(gè)數(shù)為2N。狀態(tài)空間表示為

={1,2,3,…,s}

其中，=2N。

定義2 動(dòng)作集。根據(jù)每個(gè)時(shí)刻的狀態(tài)信息，需要為當(dāng)前需要部署的VNF選擇一個(gè)物理服務(wù)器節(jié)點(diǎn)進(jìn)行部署，假設(shè)有個(gè)節(jié)點(diǎn)，則動(dòng)作集中的每個(gè)動(dòng)作對應(yīng)一個(gè)節(jié)點(diǎn)，則有種動(dòng)作。動(dòng)作集為

={1,2,3,…,a}

定義3 反饋函數(shù)。針對不同的情況，設(shè)置不同的反饋值，當(dāng)動(dòng)作選取的節(jié)點(diǎn)資源使用已經(jīng)超過門限值時(shí)，設(shè)置反饋值為固定的-50；當(dāng)動(dòng)作選取的節(jié)點(diǎn)資源沒有超過門限值時(shí)，反饋函數(shù)為

其中，L()表示狀態(tài)時(shí)系統(tǒng)的負(fù)載均衡性，計(jì)算方法為全部節(jié)點(diǎn)已用vCPU的方差，D為該動(dòng)作選擇的節(jié)點(diǎn)與上一個(gè)VNF部署節(jié)點(diǎn)之間路徑的最小延時(shí)。

此外，由于強(qiáng)化學(xué)習(xí)算法存在維數(shù)災(zāi)難、收斂速度慢、探索和利用平衡等問題，本文算法將重點(diǎn)考慮在一個(gè)數(shù)據(jù)中心或企業(yè)網(wǎng)內(nèi)部署服務(wù)鏈的情形，暫時(shí)不考慮需要同時(shí)在多個(gè)域部署某一服務(wù)鏈的情況。即暫時(shí)不考慮多個(gè)SDN域和NFV-O域，僅考慮服務(wù)鏈在某一個(gè)基礎(chǔ)設(shè)施上的映射。另外，在服務(wù)鏈的組鏈階段基本通過SDN控制器下發(fā)流表控制不同VNF之間的流量走向，一般都按最短路徑策略進(jìn)行選路。

5.1 基于Q-learning的服務(wù)鏈映射

強(qiáng)化學(xué)習(xí)任務(wù)通常用馬爾可夫決策過程（MDP, Markov decision process）來描述。由于系統(tǒng)建模的馬爾可夫決策過程中模型的狀態(tài)轉(zhuǎn)移概率未知，本文在模型中采用Q-learning算法來進(jìn)行學(xué)習(xí)控制。Q-learning算法是一種模型無關(guān)的值迭代方法，不需要提前知道狀態(tài)轉(zhuǎn)移矩陣，以求解具有延時(shí)回報(bào)的序貫優(yōu)化決策問題。

當(dāng)動(dòng)作選定后，執(zhí)行該動(dòng)作，系統(tǒng)進(jìn)入下一狀態(tài)s+1，同時(shí)也能得到系統(tǒng)的一個(gè)反饋(s,a)。根據(jù)式(6)對矩陣進(jìn)行迭代更新。

5.2 算法描述

結(jié)合5.1節(jié)給出具體的算法實(shí)現(xiàn)描述，算法1側(cè)重描述整個(gè)服務(wù)鏈的映射算法過程，如下所示。

算法1 基于Q-learning服務(wù)鏈映射算法

接收到服務(wù)鏈放置請求

檢查基礎(chǔ)設(shè)施計(jì)算存儲網(wǎng)絡(luò)資源是否滿足服務(wù)鏈請求資源總量需求

if (滿足資源總量需求)

將服務(wù)鏈的頭節(jié)點(diǎn)放置在負(fù)載最小的節(jié)點(diǎn)上

for(后續(xù)服務(wù)鏈需要放置的VNF)

根據(jù)Q-learning算法選擇合適的VNF放置節(jié)點(diǎn)

else

拒絕服務(wù)鏈放置請求

算法2側(cè)重描述基于Q-learning的VNF放置過程，如下所示。

算法2 基于Q-learning的VNF放置算法

接收到VNF放置請求

隨機(jī)選擇動(dòng)作對VNF進(jìn)行放置，即隨機(jī)選擇節(jié)點(diǎn)對VNF進(jìn)行放置

else

根據(jù)矩陣計(jì)算選擇可選動(dòng)作將VNF放置在合適節(jié)點(diǎn)

根據(jù)式(6)更新矩陣用于下一次計(jì)算放置策略

6 算法仿真與分析

6.1 仿真環(huán)境

本文基于Java語言編寫測試驗(yàn)證工具來實(shí)現(xiàn)算法的仿真。算法的仿真實(shí)現(xiàn)分為3個(gè)模塊，首先是底層網(wǎng)絡(luò)環(huán)境構(gòu)建，包括網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)和物理服務(wù)器節(jié)點(diǎn)資源的模擬等；然后是業(yè)務(wù)的生成模塊，每個(gè)業(yè)務(wù)包含一個(gè)服務(wù)鏈，業(yè)務(wù)以泊松流到達(dá)，在系統(tǒng)中完成的時(shí)間服從負(fù)指數(shù)分布，所以在系統(tǒng)中停留一定的時(shí)間后也以泊松分布離去。最后是基于增強(qiáng)學(xué)習(xí)的服務(wù)鏈映射算法模塊，該模塊運(yùn)行著Q-learning算法，為業(yè)務(wù)中服務(wù)鏈的部署做決策，然后在每次部署后查看系統(tǒng)的下一狀態(tài)和反饋，更新矩陣。

1) 服務(wù)鏈的產(chǎn)生

假設(shè)網(wǎng)絡(luò)中存在的VNF種類的個(gè)數(shù)為10種。服務(wù)鏈的長度從[1, 8]中按均勻分布隨機(jī)產(chǎn)生。服務(wù)鏈中的每個(gè)VNF的產(chǎn)生從集合中隨機(jī)選取，并保證選取過的VNF種類不再選取，使一條服務(wù)鏈中的VNF種類都不相同。

2) 實(shí)驗(yàn)拓?fù)洚a(chǎn)生

網(wǎng)絡(luò)拓?fù)涫褂肂rite拓?fù)洚a(chǎn)生器產(chǎn)生，一共選取產(chǎn)生了10個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)?，?jié)點(diǎn)之間的連接關(guān)系和鏈路的時(shí)延都由拓?fù)洚a(chǎn)生器產(chǎn)生。假設(shè)每個(gè)服務(wù)器節(jié)點(diǎn)有10個(gè)vCPU，本文假設(shè)每個(gè)vCPU能承載一個(gè)VNF，所以每個(gè)服務(wù)器節(jié)點(diǎn)上可以放置10個(gè)VNF。

3) 基于Q-learning的服務(wù)鏈映射算法

Q-learning 算法的核心在于矩陣，由于實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)渲袨?0個(gè)節(jié)點(diǎn)，所以，狀態(tài)集中狀態(tài)的個(gè)數(shù)為10 240，動(dòng)作集中的動(dòng)作個(gè)數(shù)為10，矩陣中“狀態(tài)—?jiǎng)幼鳌睂Φ膫€(gè)數(shù)為10 240×10。每到來一個(gè)服務(wù)鏈的請求，就會(huì)進(jìn)行一次部署，然后將矩陣進(jìn)行一個(gè)更新。對算法進(jìn)行評估時(shí)，是當(dāng)矩陣收斂后，利用收斂后的矩陣來為服務(wù)鏈的部署做決策，以測試算法的性能。

6.2 對比算法

為了對比驗(yàn)證本文提出算法的有效性，選擇了以下幾種經(jīng)典的服務(wù)鏈映射算法進(jìn)行比較分析。

RL（reinforcement learning）。強(qiáng)化學(xué)習(xí)算法，即本文算法。

SPG（short path greedy）。如果上一個(gè)VNF部署的節(jié)點(diǎn)有可用的資源，則在上一個(gè)VNF部署的節(jié)點(diǎn)上放置當(dāng)前VNF。如果上一個(gè)VNF部署的節(jié)點(diǎn)上沒有可用的資源，則在鏈路傳輸延時(shí)最短的節(jié)點(diǎn)上放置，即在距離上一個(gè)VNF部署節(jié)點(diǎn)傳輸延時(shí)最小的節(jié)點(diǎn)上放置，SPG的目標(biāo)是為了減少業(yè)務(wù)數(shù)據(jù)分組在服務(wù)鏈中轉(zhuǎn)發(fā)的時(shí)延。

LLG（least loaded greedy）。每個(gè)VNF都選擇在負(fù)載最小的服務(wù)器節(jié)點(diǎn)上放置。

RD（random）。隨機(jī)選擇服務(wù)器節(jié)點(diǎn)放置VNF。

6.3 評價(jià)指標(biāo)

由于服務(wù)鏈放置涉及資源利用率、網(wǎng)絡(luò)延時(shí)、系統(tǒng)能耗等指標(biāo)，暫時(shí)先選取2個(gè)重要的評價(jià)指標(biāo)來衡量本文提出算法的有效性：1) 每個(gè)業(yè)務(wù)的服務(wù)鏈的平均傳輸延時(shí)；2) 系統(tǒng)中服務(wù)器節(jié)點(diǎn)的負(fù)載均衡性。本文算法適用于優(yōu)化不同的目標(biāo)，只需要更改反饋值即可。

1) 業(yè)務(wù)的平均傳輸延時(shí)

記錄每個(gè)業(yè)務(wù)在映射完成后業(yè)務(wù)鏈整體在鏈路上的傳輸延時(shí)，然后取平均值。如某個(gè)業(yè)務(wù)鏈的形式為VNF1→VNF2→VNF3，則該業(yè)務(wù)的傳輸時(shí)延為VNF1所在節(jié)點(diǎn)→VNF2所在節(jié)點(diǎn)→VNF3所在節(jié)點(diǎn)的鏈路傳輸時(shí)延。其中，如果2個(gè)VNF部署在同一節(jié)點(diǎn)上，則2個(gè)VNF間的傳輸時(shí)延極小，可以忽略不計(jì)，即((s,j),(s,j+1))=0。如果2個(gè)VNF部署在不同節(jié)點(diǎn)上，((s,j),(s,j+1))為2個(gè)節(jié)點(diǎn)之間路徑的最小時(shí)延。

2) 服務(wù)器節(jié)點(diǎn)負(fù)載均衡

在系統(tǒng)運(yùn)行過程中，在不同時(shí)刻采集不同物理服務(wù)器節(jié)點(diǎn)上的負(fù)載情況，然后，計(jì)算不同服務(wù)器節(jié)點(diǎn)上負(fù)載情況的方差來衡量系統(tǒng)的負(fù)載均衡。方差越小表明系統(tǒng)負(fù)載越均衡；方差越大表明系統(tǒng)負(fù)載波動(dòng)越大。

6.4 實(shí)驗(yàn)結(jié)果

1) 業(yè)務(wù)的平均傳輸延時(shí)結(jié)果

按照收斂后的矩陣來部署服務(wù)鏈，對算法性能進(jìn)行評估。實(shí)驗(yàn)中隨機(jī)生成500條服務(wù)鏈并按照不同的算法進(jìn)行部署實(shí)驗(yàn)，然后統(tǒng)計(jì)服務(wù)鏈承載業(yè)務(wù)的平均鏈路延時(shí)，業(yè)務(wù)平均鏈路延時(shí)指標(biāo)對比如圖4所示。

圖4 業(yè)務(wù)平均鏈路時(shí)延指標(biāo)對比

如圖4所示，SPG在業(yè)務(wù)平均鏈路延時(shí)上最小，這是因?yàn)槊看味歼x擇在同一個(gè)節(jié)點(diǎn)上部署同一條服務(wù)鏈上相鄰的2個(gè)VNF，或在鏈路時(shí)延最小的2個(gè)節(jié)點(diǎn)上去部署相鄰的2個(gè)VNF，這樣可以有效地降低業(yè)務(wù)的時(shí)延。RL算法業(yè)務(wù)平均鏈路時(shí)延上的表現(xiàn)僅次于SPG，這是因?yàn)樵撍惴ㄔ趶?qiáng)化學(xué)習(xí)的獎(jiǎng)懲反饋中加入了關(guān)于鏈路延時(shí)優(yōu)化的激勵(lì)，當(dāng)鏈路延時(shí)越小，則得到的獎(jiǎng)賞越大，所以策略選擇上會(huì)選擇延時(shí)較小的節(jié)點(diǎn)去部署VNF。LLG的表現(xiàn)最差，這是因?yàn)槊看蜭LG都選擇負(fù)載最小的節(jié)點(diǎn)去部署VNF，導(dǎo)致同一條服務(wù)鏈中的VNF可能分散部署在多臺服務(wù)器節(jié)點(diǎn)上，使鏈路時(shí)延增大。

2) 系統(tǒng)負(fù)載均衡結(jié)果

當(dāng)仿真平臺運(yùn)行過程中，業(yè)務(wù)按泊松流到達(dá)，按泊松流離去，則在系統(tǒng)中會(huì)存在一些正在處理的業(yè)務(wù)鏈，這些業(yè)務(wù)鏈的部署情況，系統(tǒng)的負(fù)載情況是否比較均衡，也是系統(tǒng)需要評估的重要因素。

在系統(tǒng)運(yùn)行過程中，按一定間隔采集系統(tǒng)當(dāng)前的負(fù)載均衡狀況，即監(jiān)測節(jié)點(diǎn)vCPU資源使用量，然后統(tǒng)計(jì)不同節(jié)點(diǎn)資源使用量的方差值，共采集20組數(shù)據(jù)來計(jì)算方差，然后取20次方差的平均值。本文用方差的平均值來描述系統(tǒng)的均衡性，如圖5所示。

統(tǒng)計(jì)應(yīng)用不同算法的系統(tǒng)負(fù)載均衡情況，計(jì)算其平均值。系統(tǒng)均衡性的指標(biāo)對比如圖5所示。

圖5 系統(tǒng)均衡性的指標(biāo)對比

圖6 20次系統(tǒng)負(fù)載均衡方差數(shù)據(jù)對比

如圖5所示，LLG的波動(dòng)小且系統(tǒng)的負(fù)載方差值小，說明系統(tǒng)負(fù)載比較均衡，表現(xiàn)最佳，這是因?yàn)長LG每次都將服務(wù)鏈中各VNF部署在負(fù)載最小的節(jié)點(diǎn)上。RL算法的表現(xiàn)比LLG稍差，這是因?yàn)樵谒惴í?jiǎng)懲反饋中考慮了系統(tǒng)負(fù)載的因素，策略每次選擇會(huì)將服務(wù)鏈中各VNF部署在負(fù)載較小的節(jié)點(diǎn)上，使系統(tǒng)的負(fù)載能夠比較均衡。SPG算法表現(xiàn)得最差，這是因?yàn)镾PG為了減少鏈路的時(shí)延，常常將相鄰的2個(gè)VNF部署在同一個(gè)節(jié)點(diǎn)上，導(dǎo)致系統(tǒng)的負(fù)載均衡性表現(xiàn)較差。

為了更加直觀地反映底層網(wǎng)絡(luò)的負(fù)載均衡性，將這20次的方差數(shù)據(jù)按時(shí)序表示為圖6，LLG在不同時(shí)刻的節(jié)點(diǎn)負(fù)載方差值基本都接近0，說明在不同時(shí)刻，不同節(jié)點(diǎn)上的負(fù)載基本是相同的，RL算法在不同時(shí)刻的方差值也比較小。

7 討論

根據(jù)互聯(lián)網(wǎng)公司和電信運(yùn)營商的實(shí)操經(jīng)驗(yàn)，一般單一網(wǎng)絡(luò)業(yè)務(wù)鏈部署所需服務(wù)器數(shù)目為幾臺到幾百臺不等，具體視負(fù)載均衡、安全防護(hù)、內(nèi)容分發(fā)等不同業(yè)務(wù)需求而定，本文在實(shí)驗(yàn)中選擇10個(gè)節(jié)點(diǎn)的拓?fù)溥M(jìn)行驗(yàn)證性實(shí)驗(yàn)，具有一定的參考價(jià)值。

本實(shí)驗(yàn)中選擇策略矩陣作為Q-learning算法的策略表示。由于策略矩陣存在著天然的可拓展性問題，導(dǎo)致該算法不能支持大規(guī)模的網(wǎng)絡(luò)拓?fù)?。因此，針對算法的可拓展性問題，本文提出以下改進(jìn)的思路作為未來的研究工作。首先，當(dāng)節(jié)點(diǎn)數(shù)量較多時(shí)，可以選擇根據(jù)經(jīng)驗(yàn)將策略矩陣進(jìn)行初始化，使策略矩陣接近最優(yōu)的結(jié)果，來加速策略矩陣的收斂。其次，可以使用深度神經(jīng)網(wǎng)絡(luò)來表述狀態(tài)—?jiǎng)幼骷?，業(yè)界已經(jīng)在游戲場景中使用深度神經(jīng)網(wǎng)絡(luò)表征狀態(tài)—?jiǎng)幼骷希C明了深度神經(jīng)網(wǎng)絡(luò)可以適用于復(fù)雜的場景。

8 結(jié)束語

服務(wù)鏈的映射是NFV架構(gòu)體系中的核心，重點(diǎn)解決網(wǎng)絡(luò)服務(wù)資源的動(dòng)態(tài)提供和靈活編排問題。本文設(shè)計(jì)了基于多智能體強(qiáng)化學(xué)習(xí)技術(shù)的服務(wù)鏈資源調(diào)度架構(gòu)，提出了一種基于Q-learning強(qiáng)化學(xué)習(xí)的服務(wù)鏈映射算法，通過仿真驗(yàn)證表明在業(yè)務(wù)的平均傳輸延時(shí)和服務(wù)器節(jié)點(diǎn)負(fù)載均衡性上取得了很好的優(yōu)化效果。后續(xù)工作中將針對虛擬化核心網(wǎng)、虛擬內(nèi)容分發(fā)網(wǎng)絡(luò)等不同業(yè)務(wù)特征驅(qū)動(dòng)下的服務(wù)鏈映射方式展開深入研究。

[1] HAN B, GOPALAKRISHNAN V, JI L, et al. Network function virtualization: challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90-97.

[2] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: state-of-the-art and research challenges[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 236-262.

[3] RIERA J F, ESCALONA E, BATALLé J, et al. Virtual network function scheduling: concept and challenges[C]//2014 International Conference on Smart Communications in Network Technologies (SaCoNeT). 2014: 1-5.

[4] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions [C]//2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[5] KREUTZ D, RAMOS F M V, VERíSSIMO P E, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1):14-76.

[6] NUNES B A A, MENDONCA M, NGUYEN X N, et al. A survey of software-defined networking: past, present, and future of programmable networks[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1617-1634.

[7] LI Y, CHEN M. Software-defined network function virtualization: a survey[J]. IEEE Access, 2015, 3: 2542-2553.

[8] BHAMARE D, JAIN R, SAMAKA M, et al. A survey on service function chaining[J]. Journal of Network and Computer Applications, 2016, 75:138-155.

[9] KUO T W, LIOU B H, LIN K C J, et al. Deploying chains of virtual network functions: on the relation between link and server usage[C]// IEEE INFOCOM 2016-the 35th Annual IEEE International Conference on Computer Communications.2016: 1-9.

[10] MECHTRI M, GHRIBI C, ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 533-546.

[11] WANG L, LU Z, WEN X, et al. Joint optimization of service function chaining and resource allocation in network function virtualization[J]. IEEE Access, 2016, 4: 8084-8094.

[12] YE Z, CAO X, WANG J, et al. Joint topology design and mapping of service function chains for efficient, scalable, and reliable network functions virtualization[J].IEEE Network, 2016, 30(3): 81-87.

[13] REDDY V S, BAUMGARTNER A, BAUSCHERT T. Robust embedding of VNF/service chains with delay bounds[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). 2016: 93-99.

[14] MEHRAGHDAM S, KELLER M, KARL H. Specifying and placing chains of virtual network functions[C]// 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet). 2014: 7-13.

[15] ZHANG Q, XIAO Y, LIU F, et al. Joint optimization of chain placement and request scheduling for network function virtualization[C]// 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). 2017:731-741.

[16] HIRWE A, KATAOKA K. LightChain: a lightweight optimisation of VNF placement for service chaining in NFV[C]// 2016 IEEE NetSoft Conference and Workshops (NetSoft). 2016: 33-37.

[17] ZHANG B, ZHANG P, ZHAO Y. Co-scaler: cooperative scaling of software-defined NFV service function chain[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). 2016: 33-38.

[18] SAHHAF S, TAVERNIER W, COLLE D, et al. Network service chaining with efficient network function mapping based on service decompositions[C]//2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-5.

[19] MOENS H, TURCK F D. Customizable function chains: managing service chain variability in hybrid NFV networks[J].IEEE Transactions on Network and Service Management, 2016,13(4): 711-724.

[20] FEI X, LIU F, XU H, et al. Towards load-balanced VNF assignment in geo-distributed NFV Infrastructure[C]//IEEE/ACM 25th International Symposium on Quality of Service (IWQoS).2017: 1-10.

[21] DIETRICH D, ABUJODA A, RIZK A, et al. Multi-provider service chain embedding with nestor[J]. IEEE Transactions on Network and Service Management, 2017,14(1): 91-105.

[22] HABIB A, KHAN M I. Reinforcement learning based autonomic virtual machine management in clouds[C]//2016 5th International Conference on Informatics, Electronics and Vision (ICIEV). 2016: 1083-1088.

[23] GROLéAT T, POUYLLAU H. Distributed inter-domain SLA negotiation using Reinforcement Learning[C]//12th IFIP/IEEE International Symposium on Integrated Network Management (IM 2011) and Workshops. 2011: 33-40.

[24] LIN S C, AKYILDIZ I F, WANG P, et al. QoS-aware adaptive routing in multi-layer hierarchical software defined networks: a reinforcement learning approach[C]//2016 IEEE International Conference on Services Computing (SCC).2016: 25-33.

Service chain mapping algorithm based on reinforcement learning

WEI Liang, HUANG Tao, ZHANG Jiao, WANG Zenan, LIU Jiang, LIU Yunjie

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

A service chain resource scheduling architecture of multi-agent based on artificial intelligence technology was proposed. Meanwhile, a service chain mapping algorithm based on reinforcement learning was designed. Through the Q-learning mechanism, the location of each virtual network element in the service chain was determined according to the system status and the reward and punishment feedback after the deployment. The experimental results show that compared with the classical algorithms, the algorithm effectively reduces the average transmission delay of the service and improves the load balance of the system.

network function virtualization, artificial intelligence, service chain, reinforcement learning

TP302

A

10.11959/j.issn.1000-436x.2018002

魏亮（1981-），男，江蘇揚(yáng)州人，北京郵電大學(xué)博士生，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化等。

黃韜（1980-），男，重慶人，博士，北京郵電大學(xué)教授，主要研究方向?yàn)槁酚膳c交換、軟件定義網(wǎng)絡(luò)、內(nèi)容分發(fā)網(wǎng)絡(luò)等。

張嬌（1986-），女，河北保定人，北京郵電大學(xué)副教授，主要研究方向?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化、軟件定義網(wǎng)絡(luò)、未來網(wǎng)絡(luò)體系架構(gòu)等。

王澤南（1994-），男，浙江湖州人，北京郵電大學(xué)博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)功能虛擬化、網(wǎng)絡(luò)智能等。

劉江（1983-），男，河南鄭州人，博士，北京郵電大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)體系架構(gòu)、網(wǎng)絡(luò)虛擬化、軟件定義網(wǎng)絡(luò)、信息中心網(wǎng)絡(luò)等。

劉韻潔（1943-），男，山東煙臺人，中國工程院院士，北京郵電大學(xué)教授，主要研究方向?yàn)槲磥砭W(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)體系架構(gòu)、網(wǎng)絡(luò)融合與演進(jìn)等。

2017-09-07；

2017-11-29

國家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（No.2015AA016101）；國家自然科學(xué)基金資助項(xiàng)目（No.61501042）；北京科技新星基金資助項(xiàng)目（No.Z151100000315078）

: The National High Technology Research and Development Program of China (863 Program) (No.2015AA016101), The National Natural Science Foundation of China (No.61501042), Beijing New-Star Plan of Science and Technology (No.Z151100000315078)