可編程數(shù)據(jù)平面下基于DDPG的路由優(yōu)化方法

徐 博，周建國(guó)，吳 靜，羅 威

1.武漢大學(xué) 電子信息學(xué)院，武漢 430072

2.中國(guó)艦船研究設(shè)計(jì)中心，武漢 430064

軟件定義網(wǎng)絡(luò)（software-defined network，SDN）由于其轉(zhuǎn)控分離、軟件可編程和開(kāi)放接口等特性，正變得越來(lái)越受歡迎。在使用OpenFlow的SDN框架下，數(shù)據(jù)平面處理數(shù)據(jù)包時(shí)的匹配域是協(xié)議相關(guān)的，并具有固定動(dòng)作集，軟件可編程僅局限于控制平面。為了進(jìn)一步提高網(wǎng)絡(luò)的可編程性和開(kāi)放程度，McKeown等人提出了可編程數(shù)據(jù)平面和可編程協(xié)議無(wú)關(guān)報(bào)文處理語(yǔ)言P4，以及相應(yīng)的抽象轉(zhuǎn)發(fā)模型RMT[1]。RMT模型主要由用于解析數(shù)據(jù)包包頭的解析器、多級(jí)匹配動(dòng)作表和多個(gè)緩存隊(duì)列組成。P4語(yǔ)言能夠?qū)MT模型中的解析器和匹配動(dòng)作表進(jìn)行編程，從而使網(wǎng)絡(luò)管理者能夠?qū)?shù)據(jù)平面的數(shù)據(jù)包處理邏輯和行為進(jìn)行深度定制。同時(shí)，新的南向協(xié)議P4Runtime被提出來(lái)。

在具有可編程數(shù)據(jù)平面的SDN框架下，控制平面不僅擁有全網(wǎng)視圖，還可以通過(guò)編程對(duì)網(wǎng)絡(luò)行為進(jìn)行靈活的配置和管理。處于數(shù)據(jù)平面的交換設(shè)備可以只根據(jù)P4程序完成數(shù)據(jù)包的解析、修改和轉(zhuǎn)發(fā)，傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下交換設(shè)備需要完成的路由算法可以作為一個(gè)應(yīng)用單獨(dú)運(yùn)行在具有更強(qiáng)通用算力的控制平面上，這使得部署更復(fù)雜的路由算法成為可能。

近年來(lái)，機(jī)器學(xué)習(xí)方法在圖像識(shí)別、自然語(yǔ)言處理等領(lǐng)域得到了十分廣泛的應(yīng)用。機(jī)器學(xué)習(xí)方法不需要對(duì)問(wèn)題進(jìn)行復(fù)雜的假設(shè)和精確的數(shù)學(xué)建模，經(jīng)過(guò)訓(xùn)練的機(jī)器學(xué)習(xí)模型能夠?qū)⑷我廨斎胗成涞酱_定的輸出，得到局部最優(yōu)解。因此利用機(jī)器學(xué)習(xí)方法進(jìn)行路由優(yōu)化，將使網(wǎng)絡(luò)變得更加智能。目前，用于路由優(yōu)化的機(jī)器學(xué)習(xí)算法主要是監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)，由于SDN網(wǎng)絡(luò)下的路由優(yōu)化問(wèn)題可以看成是在給定網(wǎng)絡(luò)環(huán)境狀態(tài)下的決策問(wèn)題，因此更適合使用強(qiáng)化學(xué)習(xí)方法求解[2-3]。

文獻(xiàn)[4]提出在SDN網(wǎng)絡(luò)下實(shí)現(xiàn)基于強(qiáng)化學(xué)習(xí)的智能路由協(xié)議，但沒(méi)有使用SDN控制器進(jìn)行路由決策，而是采用傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下的分布式自適應(yīng)路由，并且通過(guò)修改模擬軟件將智能算法添加到路由協(xié)議中，無(wú)法在實(shí)際物理網(wǎng)絡(luò)中部署。文獻(xiàn)[5]提出了一種基于深度強(qiáng)化學(xué)習(xí)的、由經(jīng)驗(yàn)驅(qū)動(dòng)的控制框架DRL-TE，用于解決通信網(wǎng)絡(luò)中的流量工程問(wèn)題。實(shí)驗(yàn)結(jié)果表明，相比于廣泛使用的最短路徑、負(fù)載均衡等方法，DRL-TE能夠提供更好的吞吐量，并顯著降低端到端的總時(shí)延，體現(xiàn)了使用強(qiáng)化學(xué)習(xí)解決網(wǎng)絡(luò)問(wèn)題的優(yōu)勢(shì)。文獻(xiàn)[6]將深度強(qiáng)化學(xué)習(xí)算法DDPG與長(zhǎng)短期記憶網(wǎng)絡(luò)LSTM結(jié)合在一起，用于增強(qiáng)路由算法對(duì)流之間上下文相關(guān)性的感知能力，以適應(yīng)空間-地面集成網(wǎng)絡(luò)環(huán)境下不斷變化的流和鏈路狀態(tài)。

受固定功能交換機(jī)的限制，在不具備可編程數(shù)據(jù)平面的SDN環(huán)境下利用強(qiáng)化學(xué)習(xí)進(jìn)行路由優(yōu)化的研究[7-11]多采用流量矩陣等作為強(qiáng)化學(xué)習(xí)模型的狀態(tài)輸入，只考慮到了網(wǎng)絡(luò)中的流量特征和鏈路狀況，忽視了交換機(jī)對(duì)路由決策的影響。同時(shí)，通過(guò)粗粒度、不精確的測(cè)量方法獲得狀態(tài)參數(shù)不能真實(shí)準(zhǔn)確地反映網(wǎng)絡(luò)狀態(tài)，容易導(dǎo)致強(qiáng)化學(xué)習(xí)出現(xiàn)決策偏差，使路由性能受限。同時(shí)，最終得到的路由路徑多為單路徑，沒(méi)有有效利用網(wǎng)絡(luò)中的多條端到端傳輸路徑，導(dǎo)致網(wǎng)絡(luò)吞吐量較低，資源利用率不夠，容易造成網(wǎng)絡(luò)擁塞，丟包率和傳輸時(shí)延增加。

本文針對(duì)SDN架構(gòu)下進(jìn)行路由優(yōu)化存在的上述問(wèn)題，利用具有可編程數(shù)據(jù)平面的SDN交換機(jī)，設(shè)計(jì)了一種基于強(qiáng)化學(xué)習(xí)的多路徑路由機(jī)制，具體而言主要是：

（1）利用可編程數(shù)據(jù)平面和P4Runtime協(xié)議，設(shè)計(jì)了一種新的細(xì)粒度、高精度的網(wǎng)絡(luò)測(cè)量方法，使控制器可以靈活獲取當(dāng)前網(wǎng)絡(luò)中交換機(jī)的狀態(tài)參數(shù)。

（2）引入深度強(qiáng)化學(xué)習(xí)算法DDPG，根據(jù)網(wǎng)絡(luò)測(cè)量獲得的網(wǎng)狀狀態(tài)參數(shù)和路由優(yōu)化目標(biāo)確定網(wǎng)絡(luò)中每條鏈路用于路由選擇的權(quán)值。

（3）在數(shù)據(jù)中心網(wǎng)絡(luò)下，利用具有可編程數(shù)據(jù)平面的交換機(jī)設(shè)計(jì)了一種新的源路由協(xié)議，以實(shí)現(xiàn)多路徑路由，進(jìn)一步提高網(wǎng)絡(luò)吞吐量，降低傳輸時(shí)延，同時(shí)減小數(shù)據(jù)平面和控制平面之間的南向通信開(kāi)銷(xiāo)。

1 路由優(yōu)化方法

本文研究的路由優(yōu)化問(wèn)題表述如下：考慮一個(gè)具有K個(gè)端到端通信會(huì)話(huà)的網(wǎng)絡(luò)，其中每個(gè)通信會(huì)話(huà)k由其五元組信息，即源IP地址、目的IP地址、傳輸層協(xié)議、源端口和目的端口標(biāo)識(shí)，本文需要解決的問(wèn)題是在網(wǎng)絡(luò)中一組連接源節(jié)點(diǎn)和目的節(jié)點(diǎn)的可選路徑中，選擇路徑權(quán)值最大的路徑p ik作為路由路徑，使會(huì)話(huà)k的吞吐量最大，并降低時(shí)延和丟包率，其中w k i,j=f(P k)表示由某種方法f得到的會(huì)話(huà)k的第i條可選路徑上的第j個(gè)鏈路的權(quán)值。

為了解決上述問(wèn)題，本文在具有可編程數(shù)據(jù)平面的數(shù)據(jù)中心網(wǎng)絡(luò)下提出了一種基于強(qiáng)化學(xué)習(xí)和多路徑傳輸?shù)穆酚蓛?yōu)化方法。如圖1所示，該方法主要由四個(gè)部分組成，分別是網(wǎng)絡(luò)狀態(tài)感知、鏈路權(quán)值計(jì)算、多路徑路由計(jì)算和流表規(guī)則下發(fā)，本章將對(duì)這四個(gè)部分做設(shè)計(jì)分析，并描述其主要實(shí)現(xiàn)過(guò)程。

圖1 總體結(jié)構(gòu)圖Fig.1 Overall structure diagram

1.1 網(wǎng)絡(luò)狀態(tài)感知

傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下，網(wǎng)絡(luò)管理員一般通過(guò)Sflow、Netflow等工具在網(wǎng)絡(luò)邊緣的終端設(shè)備來(lái)間接獲取滯后且不精確的網(wǎng)絡(luò)測(cè)量數(shù)據(jù)?？删幊虜?shù)據(jù)平面的出現(xiàn)為自定義交換機(jī)數(shù)據(jù)包處理邏輯提供了更大的靈活度。Kim等人提出了INT測(cè)量方法[12]，該方法是基于路徑的，通過(guò)在數(shù)據(jù)包中設(shè)置指示位，可編程交換機(jī)解析到該指示位之后，將選擇的交換機(jī)的內(nèi)部元數(shù)據(jù)（例如隊(duì)列深度、排隊(duì)時(shí)延等）或自定義數(shù)據(jù)（例如丟包個(gè)數(shù)、傳輸?shù)牧髁看笮〉龋┣度胫翑?shù)據(jù)包中，并在路徑終端解析數(shù)據(jù)包，提取相關(guān)數(shù)據(jù)。該方法需要在網(wǎng)絡(luò)的入口和出口處設(shè)置額外主機(jī)用于注入和提取INT信息，同時(shí)基于路徑的方式使得INT難以快速獲取全網(wǎng)數(shù)據(jù)，且將遙測(cè)指令和數(shù)據(jù)封裝到正常數(shù)據(jù)包中會(huì)產(chǎn)生較高的探測(cè)開(kāi)銷(xiāo)和部署運(yùn)維復(fù)雜性[13]。為了克服INT方法存在的問(wèn)題，同時(shí)保留其靈活、細(xì)粒度特性，本文設(shè)計(jì)了一種基于設(shè)備的輪詢(xún)式測(cè)量方法，用于獲取網(wǎng)絡(luò)狀態(tài)參數(shù)。

如圖2所示，SDN控制器使用P4Runtime南向協(xié)議向指定的可編程交換機(jī)發(fā)送自定義的PacketOut消息，該消息由攜帶指令的元數(shù)據(jù)包頭和空負(fù)載組成。為了區(qū)分不同功能的PacketOut消息，在元數(shù)據(jù)報(bào)頭中設(shè)置一個(gè)用于指示消息類(lèi)型的字段req_t，其值為1時(shí)表示該消息為控制器向數(shù)據(jù)平面發(fā)送的測(cè)量請(qǐng)求。為了根據(jù)需要獲取指定的測(cè)量數(shù)據(jù)，將需要的測(cè)量項(xiàng)以Bitmap的形式編碼，作為元數(shù)據(jù)報(bào)頭中的第二個(gè)字段inst。Bitmap中的每一位與可編程交換機(jī)提供的測(cè)量項(xiàng)相關(guān)聯(lián)，值為1時(shí)表示控制器需要該項(xiàng)測(cè)量數(shù)據(jù)。根據(jù)測(cè)量項(xiàng)與路由選擇的相關(guān)性，本文選擇的測(cè)量項(xiàng)如表1所示。

圖2 網(wǎng)絡(luò)參數(shù)獲取Fig.2 Network parameter acquisition

表1 測(cè)量項(xiàng)編碼Table 1 Measurement item coding

PacketOut消息通過(guò)P4Runtime發(fā)送至運(yùn)行在可編程交換機(jī)CPU上的P4Runtime服務(wù)器端，服務(wù)器端再通過(guò)CPU_PORT將元數(shù)據(jù)和負(fù)載以數(shù)據(jù)包的形式發(fā)送至可編程交換芯片。可編程交換芯片收到來(lái)自控制器的數(shù)據(jù)包后，根據(jù)解析得到信息類(lèi)型req_t和測(cè)量項(xiàng)inst，將相應(yīng)的測(cè)量數(shù)據(jù)封裝至數(shù)據(jù)包中并發(fā)送至CPU_PORT。服務(wù)器端將該數(shù)據(jù)包通過(guò)P4Runtime中的PacketIn信息發(fā)送至控制器。與PacketOut消息一致，PacketIn消息也是由元數(shù)據(jù)和負(fù)載組成，但由于測(cè)量項(xiàng)是不確定的，因此將測(cè)量數(shù)據(jù)作為PacketIn消息的負(fù)載，元數(shù)據(jù)僅包含指示該P(yáng)acketIn消息類(lèi)型的字段res_t。

為了獲取交換機(jī)端口網(wǎng)絡(luò)流的發(fā)送速率，在P4程序中為交換機(jī)的每一個(gè)端口定義一個(gè)計(jì)數(shù)器，在處理數(shù)據(jù)包時(shí)計(jì)算其五元組的哈希值，值相等的數(shù)據(jù)包屬于同一個(gè)網(wǎng)絡(luò)流。以哈希值作為網(wǎng)絡(luò)流轉(zhuǎn)發(fā)端口的計(jì)數(shù)器的索引，記錄端口轉(zhuǎn)發(fā)的該網(wǎng)絡(luò)流的總字節(jié)數(shù)?？刂破魍ㄟ^(guò)P4Runtime定時(shí)地讀取計(jì)數(shù)器值，即可計(jì)算出每個(gè)網(wǎng)絡(luò)流和每個(gè)端口的數(shù)據(jù)發(fā)送速率，再根據(jù)端口帶寬計(jì)算得到鏈路利用率。在可編程數(shù)據(jù)平面上實(shí)現(xiàn)上述方法的算法如算法1所示。

上述方法不需要引入新的測(cè)量工具，測(cè)量任務(wù)直接由交換機(jī)芯片以線(xiàn)速轉(zhuǎn)發(fā)的方式完成，能夠在降低資源消耗的同時(shí)實(shí)現(xiàn)包級(jí)細(xì)粒度測(cè)量。并且控制器可以根據(jù)應(yīng)用需求選擇需要測(cè)量的交換機(jī)、測(cè)量時(shí)間和測(cè)量項(xiàng)，具有較高的靈活性。

1.2 鏈路權(quán)值計(jì)算

本文的鏈路權(quán)值是對(duì)網(wǎng)絡(luò)中交換機(jī)和對(duì)應(yīng)鏈路組成的網(wǎng)絡(luò)基本轉(zhuǎn)發(fā)單元的綜合剩余負(fù)載能力的描述，區(qū)別于僅以帶寬表征負(fù)載能力，此處綜合考慮網(wǎng)絡(luò)測(cè)量得到的多個(gè)指標(biāo)：交換機(jī)處理時(shí)延、交換機(jī)隊(duì)列深度、鏈路利用率等。鏈路權(quán)值計(jì)算是根據(jù)上述多個(gè)測(cè)量指標(biāo)組成的網(wǎng)絡(luò)狀態(tài)描述，得到確定輸出值的回歸問(wèn)題，可以使用機(jī)器學(xué)習(xí)方法。由于SDN網(wǎng)絡(luò)下的路由優(yōu)化問(wèn)題可以看成是在給定網(wǎng)絡(luò)環(huán)境狀態(tài)下的決策問(wèn)題，因此更適合使用機(jī)器學(xué)習(xí)方法中的強(qiáng)化學(xué)習(xí)方法求解[2-3]。

強(qiáng)化學(xué)習(xí)主要用于解決智能體通過(guò)與動(dòng)態(tài)環(huán)境不斷交互來(lái)學(xué)習(xí)其行為的問(wèn)題。具體而言如圖3所示，智能體在每個(gè)時(shí)間點(diǎn)t獲得環(huán)境的當(dāng)前狀態(tài)s t，并依據(jù)某一策略函數(shù)π執(zhí)行行動(dòng)a，使環(huán)境轉(zhuǎn)移到另一個(gè)狀態(tài)s t+1，同時(shí)收到環(huán)境反饋的獎(jiǎng)勵(lì)r t。強(qiáng)化學(xué)習(xí)的目標(biāo)是尋找到一個(gè)最優(yōu)策略π*:s→a，能最大化長(zhǎng)期折扣獎(jiǎng)勵(lì)（回報(bào)）：

圖3 強(qiáng)化學(xué)習(xí)模型Fig.3 Reinforcement learning model

其中，γ∈[0,1]為獎(jiǎng)勵(lì)衰減系數(shù)，表示對(duì)長(zhǎng)期獎(jiǎng)勵(lì)的關(guān)注程度。為了評(píng)估不同策略的優(yōu)劣程度，強(qiáng)化學(xué)習(xí)定義了值函數(shù)Q來(lái)表示給定策略下期望獲得的回報(bào)，例如動(dòng)作值函數(shù)：

表示智能體在狀態(tài)s下依據(jù)策略π采取行動(dòng)a后獲得的期望回報(bào)。

在文本研究的SDN網(wǎng)絡(luò)路由優(yōu)化問(wèn)題中，環(huán)境為部署了可編程交換機(jī)的SDN網(wǎng)絡(luò)，智能體為控制器，狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)的具體定義如下：

狀態(tài)：利用1.1節(jié)提出的網(wǎng)絡(luò)測(cè)量方法，控制器在某一時(shí)刻t進(jìn)行一次網(wǎng)絡(luò)測(cè)量后可以獲得當(dāng)前時(shí)刻交換機(jī)的內(nèi)部狀態(tài)參數(shù)和鏈路利用率，這些測(cè)量數(shù)據(jù)是對(duì)當(dāng)前網(wǎng)絡(luò)狀態(tài)的描述，可用作DDPG模型的狀態(tài)輸入，表示為s t=[dt,qd t,qt,ut]，其中dt表示t時(shí)刻各交換機(jī)的處理時(shí)延，由進(jìn)出交換機(jī)時(shí)間戳相減可得，qd t表示t時(shí)刻各交換機(jī)的平均隊(duì)列深度，為進(jìn)出交換機(jī)隊(duì)列時(shí)隊(duì)列深度的平均值，q t表示t時(shí)刻各交換機(jī)的排隊(duì)時(shí)延，u t表示t時(shí)刻可選路徑上各鏈路的鏈路利用率。

動(dòng)作：使用強(qiáng)化學(xué)習(xí)解決路由優(yōu)化問(wèn)題時(shí)，最直接的動(dòng)作是輸出某個(gè)流在全網(wǎng)的路由表項(xiàng)，再由控制器下發(fā)至交換機(jī)中，但隨著網(wǎng)絡(luò)規(guī)模的增大，路由表項(xiàng)的數(shù)量將會(huì)出現(xiàn)指數(shù)爆炸問(wèn)題[14]。一個(gè)可行的動(dòng)作是改變網(wǎng)絡(luò)鏈路的權(quán)值，控制器再通過(guò)其他方法確定路由路徑，本文采用該方法，即將DDPG模型的輸出表示為a t=[w1,t,w2,t,…,w|P k|,t]，其中w i,t表示t時(shí)刻第i條可選路徑上各鏈路權(quán)值構(gòu)成的向量。該方法的另一個(gè)好處是控制器可以根據(jù)鏈路權(quán)值靈活確定路由方式，例如使用多路徑路由。

獎(jiǎng)勵(lì)：強(qiáng)化學(xué)習(xí)中的獎(jiǎng)勵(lì)是對(duì)上一次動(dòng)作，此處為設(shè)置的鏈路權(quán)重的優(yōu)劣程度的評(píng)價(jià)，隱式地定了學(xué)習(xí)的目標(biāo)。當(dāng)由鏈路權(quán)值得到路由路徑的策略確定時(shí)，鏈路權(quán)值的優(yōu)劣與網(wǎng)絡(luò)性能的優(yōu)劣正相關(guān)。本文路由優(yōu)化的目標(biāo)是提高網(wǎng)絡(luò)性能，即提高網(wǎng)絡(luò)中所有數(shù)據(jù)流的平均吞吐量Tt并降低端到端平均時(shí)延Dt和平均丟包率L t，因此可以將DDPG模型的獎(jiǎng)勵(lì)定義為：

其中，α,β,θ∈[0,1]是各個(gè)優(yōu)化目標(biāo)的權(quán)重，由路由策略決定，本文中令其全等于1。

經(jīng)典的強(qiáng)化學(xué)習(xí)方法，例如Q-Learning等使用的狀態(tài)/動(dòng)作空間是離散且小規(guī)模的，通常將值函數(shù)存儲(chǔ)為表格的形式。但在網(wǎng)絡(luò)路由優(yōu)化問(wèn)題中，狀態(tài)和動(dòng)作空間的維數(shù)很大，存儲(chǔ)這些信息需要巨大的存儲(chǔ)空間，且查表時(shí)間也會(huì)顯著增加。在某些情況下，狀態(tài)和動(dòng)作空間甚至是連續(xù)的，無(wú)法用表格表示。深度強(qiáng)化學(xué)習(xí)使用深層神經(jīng)網(wǎng)絡(luò)做值函數(shù)近似，能夠解決上述問(wèn)題[15]。

深度強(qiáng)化學(xué)習(xí)將深度學(xué)習(xí)的感知能力與強(qiáng)化學(xué)習(xí)的決策能力結(jié)合起來(lái)。但是基于價(jià)值的深度強(qiáng)化學(xué)習(xí)機(jī)制如深度Q網(wǎng)絡(luò)（deep Q network，DQN），不能解決連續(xù)動(dòng)作的建模和控制，不適合動(dòng)態(tài)實(shí)時(shí)的網(wǎng)絡(luò)系統(tǒng)。基于策略的方法如確定性策略梯度（deterministic policy gradient，DPG），可以實(shí)現(xiàn)連續(xù)時(shí)間的控制與優(yōu)化，但僅對(duì)線(xiàn)性函數(shù)生成策略函數(shù)，且存過(guò)擬合問(wèn)題[9]。為了解決這些問(wèn)題，DeepMind將DQN方法和DPG方法結(jié)合在一個(gè)Actor-Critic框架中，提出了DDPG[16]方法，實(shí)現(xiàn)了高效穩(wěn)定的連續(xù)動(dòng)作控制，適合于求解網(wǎng)絡(luò)路由優(yōu)化問(wèn)題。

圖4為DDPG框架，圖中μ和Q分別表示神經(jīng)網(wǎng)絡(luò)生成的確定性策略函數(shù)和Q函數(shù)。其中Actor模塊采用DPG方法，Critic模塊采用DQN方法。兩個(gè)模塊都是由用于訓(xùn)練和學(xué)習(xí)的在線(xiàn)網(wǎng)絡(luò)和用于防止訓(xùn)練數(shù)據(jù)相關(guān)性的目標(biāo)網(wǎng)絡(luò)組成，兩個(gè)網(wǎng)絡(luò)的初始參數(shù)和結(jié)構(gòu)完全相同，在線(xiàn)網(wǎng)絡(luò)定期地用自身參數(shù)更新目標(biāo)網(wǎng)絡(luò)的參數(shù)。DDPG在訓(xùn)練期間會(huì)將每次與環(huán)境交互的信息存儲(chǔ)在經(jīng)驗(yàn)池中，并通過(guò)在經(jīng)驗(yàn)池中隨機(jī)采樣得到神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)樣本。

圖4 DDPG框架Fig.4 DDPG framework

DDPG中四個(gè)網(wǎng)絡(luò)的功能描述如下[16]：

Actor在線(xiàn)網(wǎng)絡(luò)：根據(jù)當(dāng)前狀態(tài)s t和策略函數(shù)μ選擇動(dòng)作at=μ(s t|θμ)與環(huán)境交互得到s t+1和rt，并依據(jù)損失梯度?θμJ更新策略網(wǎng)絡(luò)參數(shù)θμ。

Actor目標(biāo)網(wǎng)絡(luò)：根據(jù)從經(jīng)驗(yàn)池中采樣得到的每個(gè)樣本的樣本狀態(tài)s i+1選擇動(dòng)作

Critic目標(biāo)網(wǎng)絡(luò)：計(jì)算目標(biāo)Q值

1.3 多路徑路由計(jì)算

由于SDN網(wǎng)絡(luò)架構(gòu)可以實(shí)現(xiàn)靈活的集中控制，因此被廣泛應(yīng)用于數(shù)據(jù)中心網(wǎng)絡(luò)。數(shù)據(jù)中心網(wǎng)絡(luò)的流量主要是由分布式存儲(chǔ)和計(jì)算產(chǎn)生的內(nèi)部流量，因此多采用Fat-Tree、Leaf-Spine等高連通度網(wǎng)絡(luò)拓?fù)鋄17]。在這類(lèi)網(wǎng)絡(luò)拓?fù)渲?，任意兩臺(tái)服務(wù)器之間存在多條物理路徑，而傳統(tǒng)單路徑路由機(jī)制無(wú)法有效利用多條端到端的傳輸路徑，導(dǎo)致網(wǎng)絡(luò)吞吐量較低，資源利用率不夠，容易造成網(wǎng)絡(luò)擁塞，丟包率和傳輸時(shí)延增加。一個(gè)可行的辦法是使用等價(jià)多路徑路由（equal-cost multi-path，ECMP），通過(guò)計(jì)算數(shù)據(jù)流的五元組的哈希值，再根據(jù)哈希值在多個(gè)與目的節(jié)點(diǎn)具有相同最小跳數(shù)的下一跳中隨機(jī)選擇。ECMP方法沒(méi)有考慮鏈路和流量的差異性，不能充分利用網(wǎng)絡(luò)資源，容易造成網(wǎng)絡(luò)負(fù)載失衡[18]。得益于可編程數(shù)據(jù)平面的靈活性和SDN的集中控制特性，本文針對(duì)于數(shù)據(jù)中心的Leaf-Spine網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)了一種新的加權(quán)多路徑路由，用于提高網(wǎng)絡(luò)資源利用率。

在Leaf-Spine網(wǎng)絡(luò)結(jié)構(gòu)下，當(dāng)與主機(jī)相連的Leaf交換機(jī)收到一個(gè)數(shù)據(jù)包后，計(jì)算其五元組的哈希值，具有相同哈希值的數(shù)據(jù)包屬于同一個(gè)網(wǎng)絡(luò)流，本文對(duì)流進(jìn)行路由調(diào)度。當(dāng)一條新流進(jìn)入網(wǎng)絡(luò)時(shí)，本文按照如下步驟確定多路徑路由：

步驟1 Leaf交換機(jī)將該流的第一個(gè)數(shù)據(jù)包發(fā)送至控制器。如果流的目的主機(jī)和源主機(jī)在同一個(gè)Leaf節(jié)點(diǎn)下，則直接轉(zhuǎn)發(fā)，否則執(zhí)行步驟2。

步驟2 Leaf-Spine結(jié)構(gòu)的網(wǎng)絡(luò)中的任意兩個(gè)不同Spine下的Leaf節(jié)點(diǎn)之間的路徑是冗余且相對(duì)固定的，控制器在全局網(wǎng)絡(luò)視圖中根據(jù)流的目的節(jié)點(diǎn)可以直接確定多條不重疊可選路徑，再通過(guò)1.1節(jié)描述的測(cè)量方法，向可選路徑上的交換機(jī)發(fā)送測(cè)量請(qǐng)求。

步驟3控制器收集交換機(jī)的狀態(tài)參數(shù)，并讀取相應(yīng)計(jì)數(shù)器值，計(jì)算鏈路利用率。

步驟4將步驟3中獲得的數(shù)據(jù)作為DDPG模型的輸入，得到可選路徑上各段鏈路的鏈路權(quán)值。

步驟5定義可選路徑上鏈路權(quán)值的最小值為路徑權(quán)值，選擇路徑權(quán)值最大的路徑為路由路徑。

1.4 流表規(guī)則下發(fā)

受固定功能交換機(jī)的限制，在使用OpenFlow的SDN網(wǎng)絡(luò)中，控制器得到的路由路徑需要轉(zhuǎn)換成單個(gè)交換機(jī)的流表，再通過(guò)南向接口下發(fā)，這增加了控制器的計(jì)算開(kāi)銷(xiāo)、南向通信開(kāi)銷(xiāo)和交換機(jī)的查表時(shí)延。因此本文借助于可編程數(shù)據(jù)平面可自定義數(shù)據(jù)包處理邏輯的優(yōu)勢(shì)，借鑒分段路由[19]的思想，設(shè)計(jì)了一種基于源路由的路由協(xié)議。

區(qū)別于使用路徑標(biāo)簽的分段路由協(xié)議，本文提出的源路由協(xié)議直接將路由路徑上各交換機(jī)的轉(zhuǎn)發(fā)端口保存在數(shù)據(jù)包的包頭中。如圖5所示，該路由協(xié)議的包頭由多個(gè)交換機(jī)的轉(zhuǎn)發(fā)端口port和用于指示該交換機(jī)是否為最后一跳交換機(jī)的bos組成?？刂破鲗⒘鞯霓D(zhuǎn)發(fā)規(guī)則，即路由路徑上每個(gè)交換機(jī)的轉(zhuǎn)發(fā)端口下發(fā)至流的源Leaf交換機(jī)，該交換機(jī)將后續(xù)交換機(jī)的轉(zhuǎn)發(fā)端口按照協(xié)議格式嵌入至數(shù)據(jù)包中，再轉(zhuǎn)發(fā)至下一跳。后續(xù)交換機(jī)解析嵌入在數(shù)據(jù)包中的第一個(gè)轉(zhuǎn)發(fā)端口并將其彈出，再據(jù)此將數(shù)據(jù)包轉(zhuǎn)發(fā)至下一跳，直至目的主機(jī)。該方式將多次流表規(guī)則的計(jì)算和下發(fā)縮減為單次，能夠減少控制平面的計(jì)算開(kāi)銷(xiāo)和南向通信開(kāi)銷(xiāo)，同時(shí)，由于后續(xù)交換機(jī)不需要再進(jìn)行查表操作，能減少交換機(jī)的處理時(shí)延。

圖5 源路由示意圖Fig.5 Source routing diagram

2 實(shí)驗(yàn)與評(píng)估

2.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文利用Mininet網(wǎng)絡(luò)仿真平臺(tái)搭建了一個(gè)如圖6所示的小型Leaf-Spine網(wǎng)絡(luò)，其中任意2個(gè)Leaf交換機(jī)之間具有3條相連鏈路。網(wǎng)絡(luò)中的軟件交換機(jī)使用的是支持?jǐn)?shù)據(jù)平面可編程的BMv2，南向協(xié)議使用的是P4Runtime，控制器使用Python語(yǔ)言編寫(xiě)。

圖6 Leaf-Spine網(wǎng)絡(luò)拓?fù)銯ig.6 Leaf-Spine network topology

為了模擬數(shù)據(jù)中心環(huán)境，網(wǎng)絡(luò)中的鏈路帶寬設(shè)置為50 Mb/s，延時(shí)設(shè)置為1 ms。通過(guò)隨機(jī)選取K對(duì)源和目的主機(jī)，使用Iperf工具各產(chǎn)生一個(gè)網(wǎng)絡(luò)會(huì)話(huà)，其中每個(gè)會(huì)話(huà)的帶寬需求，即每個(gè)數(shù)據(jù)流的數(shù)據(jù)包發(fā)送速率R i（i=1,2,…,K）滿(mǎn)足在長(zhǎng)度為10 Mb/s的窗口內(nèi)取值的泊松分布，均值λ為窗口中心：

設(shè)置初始窗口為[0，10]Mb/s，并以5 Mb/s的步長(zhǎng)滑動(dòng)窗口來(lái)改變網(wǎng)絡(luò)負(fù)載。使用Iperf和ping工具統(tǒng)計(jì)每個(gè)窗口內(nèi)每個(gè)流的吞吐量、時(shí)延和丟包率，并取平均值，用以表示當(dāng)前帶寬需求下路由方法的性能。

本文在Ubuntu 16.04系統(tǒng)上使用機(jī)器學(xué)習(xí)平臺(tái)TensorFlow和基于Python的深度學(xué)習(xí)庫(kù)Keras，按照?qǐng)D4所示的DDPG框架，搭建了神經(jīng)網(wǎng)絡(luò)模型[20]，并在上述實(shí)驗(yàn)環(huán)境中完成了模型訓(xùn)練。

2.2 性能比較

2.2.1 路由性能比較

為了驗(yàn)證本文提出的路由方法的性能優(yōu)勢(shì)，本小節(jié)選取網(wǎng)絡(luò)平均吞吐量、時(shí)延和鏈路利用率作為性能評(píng)價(jià)指標(biāo)，設(shè)置網(wǎng)絡(luò)會(huì)話(huà)數(shù)K=6，與ECMP和RRMP（round robin multi-path，輪詢(xún)多路徑路由[21]，該算法從所有端到端可選路徑中循環(huán)選擇不同的傳輸路徑）兩種多路徑路由算法做對(duì)比分析。在ECMP和RRMP算法實(shí)驗(yàn)中，控制器根據(jù)全網(wǎng)視圖計(jì)算路由路徑，并轉(zhuǎn)換成單個(gè)交換機(jī)的流表，下發(fā)至交換機(jī)。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 不同帶寬需求下的路由性能比較Fig.7 Routing performance comparison under different bandwidth requireme

實(shí)驗(yàn)結(jié)果表明，在帶寬需求比較小的情況下，三種路由算法的性能差異非常小，吞吐量、鏈路利用率與帶寬需求近似成線(xiàn)性關(guān)系，因?yàn)榇藭r(shí)的網(wǎng)絡(luò)資源能夠滿(mǎn)足全部需求，沒(méi)有產(chǎn)生擁塞。但本文提出的方法的時(shí)延要大于另外兩種方法，這是由于在計(jì)算路由時(shí)使用強(qiáng)化學(xué)習(xí)模型計(jì)算鏈路權(quán)值需要更多的時(shí)間。隨著帶寬需求增加，吞吐量和鏈路利用率無(wú)法隨帶寬需求線(xiàn)性增加，組建趨于一個(gè)恒定值，此時(shí)網(wǎng)絡(luò)資源無(wú)法滿(mǎn)足全部需求，產(chǎn)生擁塞，并出現(xiàn)丟包現(xiàn)象。但本文提出的方法的三項(xiàng)性能指標(biāo)都要優(yōu)于另外兩種，這是因?yàn)镋CMP和RRMP無(wú)法感知鏈路狀態(tài)和交換機(jī)負(fù)載情況的變化，不能根據(jù)網(wǎng)絡(luò)狀態(tài)改變流量在多條可選路徑上的分配比例，容易造成數(shù)據(jù)包大量聚集在某些交換節(jié)點(diǎn)或多條大象流經(jīng)過(guò)同一鏈路，使整個(gè)網(wǎng)絡(luò)的負(fù)載不均衡，鏈路平均利用率低，導(dǎo)致吞吐量較早達(dá)到瓶頸。同時(shí)，數(shù)據(jù)包在交換機(jī)緩存隊(duì)列中排隊(duì)時(shí)間較長(zhǎng)，使傳輸時(shí)延增加。而本文提出的方法可以在采集網(wǎng)絡(luò)狀態(tài)信息，計(jì)算網(wǎng)絡(luò)鏈路在不同網(wǎng)絡(luò)狀況下的權(quán)值，能夠在高帶寬需求時(shí)為數(shù)據(jù)流選擇鏈路資源較為充裕的路徑，從而實(shí)現(xiàn)負(fù)載均衡，提高網(wǎng)絡(luò)平均吞吐量和資源利用率，減小傳輸時(shí)延。因此本文提出的方法更適合在帶寬需求較大的網(wǎng)絡(luò)環(huán)境中使用，例如數(shù)據(jù)中心網(wǎng)絡(luò)。

2.2.2 源路由性能比較

為了驗(yàn)證本文提出的源路由方法在降低交換機(jī)處理時(shí)延和南向通信開(kāi)銷(xiāo)的作用，本小節(jié)設(shè)置了一組對(duì)比實(shí)驗(yàn)，對(duì)比組中的控制器得到路由路徑后轉(zhuǎn)換成單個(gè)交換機(jī)的流表，逐一下發(fā)到路徑上的每個(gè)交換機(jī)中，實(shí)驗(yàn)組采用本文提出的源路由方法。

（1）平均時(shí)延比較

由于數(shù)據(jù)流的時(shí)延變化主要是由交換機(jī)的處理時(shí)延變化造成，因此可以使用數(shù)據(jù)流平均時(shí)延反映交換機(jī)的處理時(shí)延。設(shè)置網(wǎng)絡(luò)會(huì)話(huà)數(shù)K=6，實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 平均時(shí)延比較Fig.8 Mean delay comparison

（2）南向通信開(kāi)銷(xiāo)比較

南向通信主要發(fā)生在新流進(jìn)入網(wǎng)絡(luò)時(shí)的網(wǎng)絡(luò)測(cè)量和流表下發(fā)過(guò)程，與帶寬需求無(wú)關(guān)，與網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)量相關(guān)，因此在某一帶寬需求（10 Mb/s）下通過(guò)增加網(wǎng)絡(luò)會(huì)話(huà)數(shù)K，統(tǒng)計(jì)南向協(xié)議P4Runtime所使用的端口上的網(wǎng)絡(luò)流量，得到南向通信開(kāi)銷(xiāo)比較，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 南向通信開(kāi)銷(xiāo)比較Fig.9 Southbound communication overhead comparison

實(shí)驗(yàn)結(jié)果表明，相比于向單個(gè)交換機(jī)下發(fā)流表，本文提出的源路由方法能夠在一定程度上減小數(shù)據(jù)流的傳輸時(shí)延，大幅減小南向通信開(kāi)銷(xiāo)。這是由于在本文提出的方法中，每一條新數(shù)據(jù)流進(jìn)入網(wǎng)絡(luò)時(shí)，僅需要入口交換機(jī)與控制器發(fā)生一次通信，路徑上其他交換機(jī)直接根據(jù)數(shù)據(jù)包中的轉(zhuǎn)發(fā)信息進(jìn)行轉(zhuǎn)發(fā)，而不需要與控制器進(jìn)行通信，這減小了南向通信開(kāi)銷(xiāo)。同時(shí)其他交換機(jī)不需要執(zhí)行查表操作，減小了處理時(shí)延，尤其是交換機(jī)中存在大量表項(xiàng)或有大量數(shù)據(jù)包需要轉(zhuǎn)發(fā)時(shí)，這種優(yōu)勢(shì)將更加明顯。

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

本文在具有可編程數(shù)據(jù)平面的SDN網(wǎng)絡(luò)架構(gòu)下，針對(duì)于具有Leaf-Spine拓?fù)浣Y(jié)構(gòu)的數(shù)據(jù)中心網(wǎng)絡(luò)，提出了一種基于強(qiáng)化學(xué)習(xí)和多路徑傳輸?shù)穆酚蓛?yōu)化方法?？刂破魍ㄟ^(guò)南向協(xié)議直接獲取網(wǎng)絡(luò)中數(shù)據(jù)平面可編程交換機(jī)的狀態(tài)參數(shù)，并使用DDPG強(qiáng)化學(xué)習(xí)算法根據(jù)網(wǎng)絡(luò)狀態(tài)參數(shù)得到不同網(wǎng)絡(luò)狀況下表示鏈路剩余負(fù)載能力的權(quán)值。通過(guò)選取具有最大最小鏈路權(quán)值的路徑，使網(wǎng)絡(luò)流量在網(wǎng)絡(luò)中分布更加均衡，以提高網(wǎng)絡(luò)資源利用率。同時(shí)，充分利用可編程數(shù)據(jù)平面帶來(lái)的靈活性，設(shè)計(jì)了一種新的基于源路由的路由協(xié)議。對(duì)比實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的路由優(yōu)化方法能夠在較高帶寬需求下提高網(wǎng)絡(luò)平均吞吐量和鏈路平均利用率，減小傳輸時(shí)延和南向通信開(kāi)銷(xiāo)，充分展示了可編程數(shù)據(jù)平面在新路由協(xié)議應(yīng)用方面存在的巨大優(yōu)勢(shì)，以及將機(jī)器學(xué)習(xí)方法引入網(wǎng)絡(luò)領(lǐng)域的巨大潛力。下一步將完善測(cè)量方法，實(shí)現(xiàn)網(wǎng)絡(luò)快照，以獲取同一時(shí)刻的網(wǎng)絡(luò)狀態(tài)參數(shù)。同時(shí)改進(jìn)路由方法，使之適用于不同的網(wǎng)絡(luò)拓?fù)洌⒏唪敯粜院涂赏卣剐浴?/p>