《路由優(yōu)化算法和網絡模型的設計與實現(xiàn)》6800字（論文）

路由優(yōu)化算法和網絡模型的設計與實現(xiàn)摘要 隨著通信技術和互聯(lián)網產業(yè)的高速發(fā)展，網絡的形態(tài)出現(xiàn)了多樣化、復雜化和扁平化的趨勢。在軟件定義網絡的背景下，傳統(tǒng)的面對網絡層的路由優(yōu)化技術收斂速度不足，無法及時應對網絡結構變化等問題越加凸顯。近年來試圖利用機器學習實現(xiàn)路由優(yōu)化的研究越來越多，例如將Q-Learning應用到網絡路由中的嘗試。由于強化學習擁有較強的決策能力，其在網絡優(yōu)化中的應用較為常見。本論文設計了基于深度強化學習的DDPG算法的網絡路由優(yōu)化算法。由于DDPG算法改進了強化學習中的固定策略梯度算法，可以更準確地擬合策略函數(shù)，擁有解決連續(xù)高維度規(guī)劃的能力，適應目前實際網絡控制的需要，并且對特定的網絡形態(tài)依賴較小，因而采取了這一算法。首先采用了OMNeT++網絡仿真軟件搭建了一個小型的軟件控制網絡作為仿真平臺，網絡節(jié)點之間通過三種數(shù)據包傳遞信息，通過流量控制組件讀取網絡權重更新路由。進而基于Keras+tensorflow編寫了路由優(yōu)化算法的主體部分，調用并讀取網絡自發(fā)產生的流量矩陣并在每個步驟中對其進行學習和優(yōu)化。定義了該算法輸入的狀態(tài)為流量矩陣，輸出的動作為鏈路權重，并且可以針對不同需求和網絡指標靈活調整反饋函數(shù)，來適應不同的網絡形態(tài)。最后，進行了仿真實驗檢驗算法性能。實驗結果表明，相對于傳統(tǒng)的最短路徑優(yōu)先算法，該算法可以有效地降低網絡平均時延，減少網絡流量浪費，并且具有較好的泛化性。關鍵詞：深度強化學習路由優(yōu)化DDPG目錄TOC\o"1-2"\h\u31549路由優(yōu)化算法和網絡模型的設計與實現(xiàn) i18207摘要 i237331.1基于DRL的路由優(yōu)化算法需求分析 ii256481.2路由優(yōu)化算法的設計 ii64611.2.1路由算法設計的分析 ii274051.2.2路由算法設計的實現(xiàn) v267311.3網絡模型的設計與實現(xiàn) vii17461.3.1網絡模型的分析 vii233651.3.2網絡模型的實現(xiàn) viii13672結語 x11581參考文獻 xi1.1基于DRL的路由優(yōu)化算法需求分析 路由優(yōu)化算法是根據一系列網絡條件來優(yōu)化路由的選取，從而提高網絡性能的算法。在傳統(tǒng)的網絡形態(tài)中，動態(tài)路由算法諸如OSPF和BGP雖然能動態(tài)生成路由表，但大多只是參考靜態(tài)的網絡參數(shù)來確定最佳路徑，例如路由器時延、路徑跳數(shù)、網絡容量等。然而容量大、條數(shù)少的路徑往往數(shù)據量也更大，總是選取最佳路徑有時候未必會獲得最佳的效果。而在軟件定義網絡架構中，位于控制平面的控制器（controller）不僅可以知道網絡的拓撲結構、線路容量、往返時延等整體數(shù)據，也可以獲得諸如端到端的流量、網絡節(jié)點的加入和離開等實時性的信息。充分利用這些實時性的信息，實時性改變局部節(jié)點的路由策略，可以獲得更優(yōu)秀的路由效果。已經有一些采用智能算法優(yōu)化路由關系的研究，但它們的應用大多并不廣泛，而且沒有結合深度強化學習。 本項目組基于DDPG算法開發(fā)出的路由優(yōu)化算法可以接收網絡產生的流量矩陣（即以特定節(jié)點對為起點和終點的流量分布），產生鏈路權重，通過鏈路權重計算出最佳路由，從而實時調整路由策略。 因此，本次畢設的目的就是通過網絡流量矩陣調整鏈路權重，在控制平面生成新路由表，并改變轉發(fā)層面的轉發(fā)策略。使用此算法，用戶可以通過訓練程序內的神經網絡使之產生更準確的鏈路信息，實現(xiàn)路由優(yōu)化。并且可以根據網絡的具體環(huán)境修改參數(shù)，來改變優(yōu)化目標和鏈路信息的生成規(guī)則。1.2路由優(yōu)化算法的設計1.2.1路由算法設計的分析 強化學習中智能體通過狀態(tài)、動作，和獎勵與環(huán)境交互，合理設置這些輸入輸出值以及它們與網絡模型的關系，是將DRL引入網絡路由優(yōu)化最重要的事情。根據一系列相關深度強化學習路由優(yōu)化的研究可知，傳統(tǒng)意義上學術界常用的解決網絡路由的方法是將某一時刻所有節(jié)點和通路的路由狀態(tài)視為神經網絡輸入的狀態(tài)，動作影響所有節(jié)點到其下一跳節(jié)點的路由選擇，最后使用最短路徑優(yōu)先算法（ShortestPathFirst，SPF）得到每對源-目的節(jié)點之間的最短路徑。對于每一狀態(tài)——動作對，環(huán)境都根據下一時間段單個或多個網絡狀態(tài)指標決定反饋的獎勵，這些指標可能包括時延、吞吐量、丟包率、帶寬、擁塞水平等。在此可以對深度強化學習模型的諸要素作出限定。 （1）狀態(tài)：狀態(tài)應當是智能體所處環(huán)境的實時特征，否則難以反映網絡需要。由于路由器一般以數(shù)據包的形式進行數(shù)據轉發(fā)，通常使用業(yè)務流的傳輸狀況指代整個網絡的路由情況?？梢远x所有數(shù)據包的集合為P，對每個通過網絡傳播的數(shù)據包pi而言，它在一個又一個的節(jié)點間的相互傳播，可以簡化為單位時間從di節(jié)點傳輸?shù)絛j節(jié)點的運動，到達dj后可以視為離開了網絡。不妨假設網絡節(jié)點總數(shù)為N，而且每個節(jié)點都可以轉發(fā)信息而且將數(shù)據包傳入傳出網絡，則所有源——目的節(jié)點對構成了一個N×N的方陣。可以將狀態(tài)s定義為維度N×N的流量矩陣（TrafficMatrix,TM），其中每個元素dijs= （2）動作：動作是智能體每一時刻對網絡發(fā)出的具體路由規(guī)定，它需要根據當前觀察到的網絡狀態(tài)和策略做出。不同于傳統(tǒng)的路由策略，基于概率的路由輸出的動作給所有鏈路指定權重，然后根據最短路徑優(yōu)先計算出具體的路由表，根據鏈路權重可以唯一確定一個路由表。可以定義節(jié)點i到節(jié)點j的權重是wij，如果此節(jié)點有m個鄰接節(jié)點，則可以組成一個權重向量Wi={wi1 （3）獎勵：獎勵的形式是強化學習的核心問題，網絡根據智能體的指令做出行動之后，返還給智能體的評價指標，是當前狀態(tài)對應當前動作的映射。它可以由很多網絡指標組成，再依據現(xiàn)實需要加入一些超參數(shù)來調整不同指標的比例，比如如下公式2-6的情況。R它描述了在狀態(tài)st的情況下發(fā)出動作at獲得的獎勵，其中?(at)是一個函數(shù)，表明動作at產生作用的時間（包含轉換網絡權重，數(shù)據包重新開始發(fā)送的時間）。而α,β,γ∈[0,1]則分別是時延、帶寬、丟包率的權重參數(shù)。TPij是節(jié)點 （4）策略：智能體的策略指導智能體在特定環(huán)境下的行為方式，是從當前狀態(tài)到當前動作的映射。DDPG的Action模塊應用了固定策略算法，策略網絡會直接選擇預期回報之和最大的動作，而不是輸出概率分布，因此可以有效減少算法的計算量，提升收斂速度。為了引入隨機性，一般會給動作加一個隨機噪聲。整體模型訓練的偽代碼大體可以寫成如下形式： 1.隨機初始化DDPG的決策網絡μθ(s)和價值網絡 2.設置相對于μθ(s)的貪婪策略π0 3.whilenotDone: 4.根據環(huán)境初始化狀態(tài)s0 5.for(n=1,2,3,…): 6.從策略網絡中獲取動作a。 7.給動作引入OU噪聲，獲得更新的動作a'。 8.sk+1 9.將軌跡[s 10.sk 11.k←k+1 12.從經驗池buffer中隨機抽取數(shù)據計算yt 13.根據公式2.1計算損失函數(shù)。 14.計算出? 15.用梯度下降法最小化損失函數(shù)，更新參數(shù) 16.ifk%n==0，更新目標網絡參數(shù) 17.endfor 18.endwhile 以上算法中，第6到11行為正向采樣的過程，第12到第16行為根據數(shù)據訓練并更新模型參數(shù)的過程，其中第8行對網絡環(huán)境進行了封裝，省略了網絡模型的創(chuàng)建部分。 以上狀態(tài)空間、動作空間和策略的具體設計就是DRL路由優(yōu)化網絡的主要工作，和網絡形態(tài)關系緊密，而且基本不需要補充額外的內容。處在知識平面上的DRL全局規(guī)劃網絡周期性地從控制平面接收網絡的流量狀態(tài)，然后輸入內部的兩個神經網絡，得出下一步的鏈路信息并訓練預測模型，再將計算后的鏈路信息通過控制平面下發(fā)給數(shù)據平面的每個路由器，展開新一輪的循環(huán)。1.2.2路由算法設計的實現(xiàn) 算法程序部分主要內容均使用Python完成，少部分重要參數(shù)寫在JSON文件中。主要包括DDPG算法與環(huán)境的設置。參照通行的強化學習框架，設置為智能體和環(huán)境兩個部分。 智能體部分分別構建了Actor模塊和的Critic模塊，它們分別在程序中對應AcotorNetwork類和CriticNetwork類。使用Keras構建主神經網絡和目標神經網絡，兩個網絡的結構是完全一致的。Actor網絡有三個全連接層，輸入層輸入的是去掉對角線的路由矩陣（狀態(tài)），由于網絡采用的是14*14的無圈網絡，輸入長度為184個單位，信息的維度在三個全連接層之間逐漸收縮。第一個隱藏層有91個單元，第二個隱藏層收縮到了42個神經元，輸出層輸出21維鏈路權重向量（動作）。前兩層的激活函數(shù)采用sigmoid函數(shù)，而輸出層采用relu函數(shù)作為激活函數(shù)。Critic網絡結合了強化學習的動作與狀態(tài)，分別對應兩個輸入層，流量數(shù)據會經過兩個全連接層，將維度降低到42，動作數(shù)據只經過一個全連接層，兩者被加工成相等維度，進入一個融合層（Merge）匯合，再由兩個全連接層得出對價值函數(shù)的價值。獎勵采用網絡的平均時延，可以根據參數(shù)改為最大時延或時延的中位數(shù)，是一個標量。為了以獎勵最大化算法縮減時延，獎勵的數(shù)值取負數(shù)。環(huán)境部分擬定了環(huán)境類OmnetBalancerEnv和OmnetLinkweightEnv作為和算法程序交互的環(huán)境，也起到聯(lián)系仿真平臺的作用。主函數(shù)定義環(huán)境實例，并在神經網絡訓練前初始化，迭代過程中不斷接收主動作，并返回強化學習的狀態(tài)、獎勵和完成情況（done），同時將必要的信息存儲到文件中。環(huán)境的主要參數(shù)如表3-1所示：參數(shù)名稱具體說明ENV環(huán)境環(huán)境的名稱ROUTING路由路由的格式folder文件夾存取文件的文件夾ACTIVE_NODES活動節(jié)點網絡結點的數(shù)目graph拓撲圖網絡的拓撲圖（采用networkx的圖格式）a_dim動作維度強化學習動作對應的長度s_dim狀態(tài)維度強化學習狀態(tài)對應的長度tgen流量方陣流量矩陣（采用單獨編寫的Trafftic類）capacity容量網絡的容量，即能正常傳輸?shù)牧髁孔畲笾抵蚭nv_T流量矩陣環(huán)境的流量矩陣（ndarray形式）env_W權重各條鏈路的權重env_R路由網絡的路由表env_D時延各條鏈路的時延表3-1環(huán)境的參數(shù)環(huán)境類主要有兩個方法，一個是環(huán)境初始化函數(shù)reset，一個是迭代函數(shù)step。reset函數(shù)會隨機初始化鏈路權重，并生成一個流量矩陣，并轉化成向量形式作為強化學習的狀態(tài)返還給主函數(shù)，reset函數(shù)不需要參數(shù)。step函數(shù)在訓練模型的每個循環(huán)內都會被調用一次，它接收Actor神經網絡生成的權重，依據Dijkstra計算并存儲最佳路由，并通過命令行啟動OMNeT++程序，讀取仿真數(shù)據并調用函數(shù)，生成對應的獎勵。最后會把獎勵、更新后的狀態(tài)和是否完成傳送到主函數(shù)。同時還包含一些轉化函數(shù)負責各種職能。（1）讀取文件：file_to_csv、ned_to_capacity等。（2）存儲文件：vector_to_file等。（3）轉換數(shù)據格式：matrix_to_rl、matrix_to_omnet_v、csv_to_matrix等。（4）最終輸出內容：rl_state、rl_reward等。程序主函數(shù)是playGame，它負責接收參數(shù)、訓練網絡，并將將數(shù)據存儲到特定文件夾中。函數(shù)流程如圖所示：圖3-1playGame的流程圖1.3網絡模型的設計與實現(xiàn)1.3.1網絡模型的分析 本論文設計的基于深度強化學習的路由優(yōu)化算法預期會運行在知識定義網絡的知識平面，利用網絡設備的編程接口API和控制層交互，自動化接收和分析網絡傳輸?shù)臅r延等網絡指標。再把更新的鏈路權重以及其他控制信息發(fā)送給控制平面，控制平面的流量控制組件接收網絡權重，再搜索出特定的鏈路數(shù)據信息轉發(fā)給數(shù)據平面的路由器，路由器會根據鏈路權重更新路由表，決定轉發(fā)方向。從而對網絡上有限的資源進行優(yōu)化，減少網絡資源的浪費。根據軟件定義網絡編程的可擴展性，在不需要逐一配置每個交換設備的情況下，利用控制器提供的更新策略完成流量管理功能升級，智能地整合全網資源。一個路由器對應著多個端口，它的每個端口都對應著信息隊列，如果一個數(shù)據包在隊列里的時間過長，則會視為超時丟棄。路由器會讀取路由優(yōu)化算法計算出來的路由信息，然后依照特定的路由信息決定該把數(shù)據包發(fā)送到哪個信息隊列中去。網絡分組到達路由可以視為一個離散時間排隊系統(tǒng)的問題，上級的交換機負責將數(shù)據包傳送給下級的交換機，容量為一個單位。一般使用先入先出的準則，路由器需要提前為隊列的隊首分組安排一個下級交換機承接信息。所有分組到達下一個交換機后，繼續(xù)進行新一輪分組，類似的路由和分組方法依次重復。網絡中的應用不定期地產生數(shù)據在網絡中相互傳輸，統(tǒng)計模塊會將采集到的信息存儲在相應的模塊中（模擬程序里是存儲到文件中）以備知識平面提取。定期獲得全網拓撲已經流量狀態(tài)等信息，監(jiān)控網絡層數(shù)，調節(jié)網絡活動?？傮w而言控制平面包流量控制組件和信息采集組件，數(shù)據平面包括具體的網絡節(jié)點和轉發(fā)器（也包括路由器）。每經過一定時間，知識平面地路由優(yōu)化算法就會讀出網絡數(shù)據進行優(yōu)化，再將優(yōu)化后的鏈路權重信息下發(fā)出去，進一步增強了網絡管理的多樣性和靈活性。1.3.2網絡模型的實現(xiàn)網絡仿真部分采用的仿真軟件是OMNeT++，OMNeT++是一個應用廣泛的離散事件仿真器，同時也是一個開源網絡仿真平臺，擁有較為完善的圖形界面。本實驗模擬了SDN網絡的控制平面和數(shù)據平面，并完成了收集記錄網絡時延的功能。OMNeT++程序主要由ned程序和相對應的c++程序，以及負責初始化的ini文件和組裝程序的makefile文件組成，網絡的主體部分定義在包package中。本實驗構建了一個14節(jié)點的全連通網絡，網絡的結構如圖所示。圖3-2網絡的結構NetworkAll文件定義了網絡節(jié)點和它們之間的通路。網絡節(jié)點可以是服務器（server）也可以是負載均衡器（balancer），本實驗的節(jié)點均為服務器。服務器內部結構如圖3-3所示：圖3-3server內部結構其中包含若干元件：（1）流量控制器（TrafficController）：從主程序中讀取更新的流量矩陣并將流量數(shù)據發(fā)送給對應的應用。（2）應用（Application）：模擬網絡中實際的應用，數(shù)量就是網絡中的節(jié)點數(shù)，可以根據流量控制器傳入的間隔，定期發(fā)送不定長的數(shù)據。本實驗中數(shù)據長度采用指數(shù)分布，但最長不超過5000比特，實際操作也可以采用其他分布。每個Application對應一個目的節(jié)點，通過設置發(fā)送間隔來控制端口之間流量大小。（3）路由器：負責數(shù)據的轉發(fā)和接收。如果此節(jié)點就是接受數(shù)據的目的節(jié)點則將數(shù)據接收，如果數(shù)據包的轉發(fā)次數(shù)到達TTL則刪除數(shù)據，視為丟包。如果處在中間節(jié)點則轉發(fā)到對應端口。路由器通過讀取主程序更新的路由表指導路由，內部沒有算法模塊。（4）端口隊列（NodeQueue）：對應服務器的一個端口，數(shù)量和服務器的端口相等，負責數(shù)據隊列的等待和管理。負責數(shù)據隊列的加入和添加，對于待輸出的數(shù)據包，如果數(shù)據等待時間過長則會刪除掉，視為丟包。對從外部接收到的數(shù)據包則直接傳給路由器，由路由器決定下一步的處理方式。仿真數(shù)據定義了控制消息ControlPacket、數(shù)據消息DataPacket、計時消息TimerNextPacket三種。流量控制器傳輸出控制消息提供流量強度信息，應用產生長度不等的數(shù)據消息來模擬顯示網絡中的數(shù)據包，計時消息用于計算時間，以便應用定期傳出數(shù)據。結語路由是傳統(tǒng)通信網絡的核心功能之一，在網絡需求和形式日趨多樣化和復雜化的今天，一些新的應用場景需要新的路由策略。路由器本質上就是一種特殊的計算機，隨著芯片技術的發(fā)展和路由器等網絡硬件性能的不斷提升，以及包括深度強化學習的各種人工智能技術的提升，基于深度強化學習的路由優(yōu)化算法的出現(xiàn)成為了可能。在本論文中，我們實現(xiàn)了使用深度強化學習技術實現(xiàn)自動路由以及路由優(yōu)化的程序。具有深度學習能力的智能硬件設備使用該算法盡可能壓低傳輸時延，平均網絡流量分布，提升網絡的性能。經檢驗，基于DDPG的路由優(yōu)化算法對路由時延和網絡穩(wěn)定性有較好的效果，尤其是在網絡流量密集，網絡負載大的地方更為突出。該訓練方法可以適應不斷變化的網絡流量和鏈路模型，提升了強化學習對網絡的不同狀態(tài)的穩(wěn)定性。在本實驗中，我們發(fā)現(xiàn)深度強化學習應用于路由優(yōu)化算法有相對于傳統(tǒng)路由算法以及啟發(fā)性路由優(yōu)化有以下較為明顯的優(yōu)點：不依賴模型：深度強化學習只需要知道網絡的狀態(tài)和延遲即可更新數(shù)據，它可以通過和環(huán)境不斷進行動態(tài)信息交互（比如動作、狀態(tài)、獎勵等）來提升自己的性能，對于有些算法并不需要對網絡建模。而傳統(tǒng)的路由優(yōu)化算法大多數(shù)需要對網絡模型進行詳細的考察，還要加入一些特殊的條件和簡化方式。更新頻率高：傳統(tǒng)的路由優(yōu)化算法需要走很多步才會有一次更新，有時候只有接收方接收到包才能知道傳輸?shù)臅r延。而基于深度強化學習的路由優(yōu)化算法可以讓網絡節(jié)點在傳播幾步之內更新自己的數(shù)據，獲得接近最優(yōu)的路由配置。甚至通過適當?shù)膮?shù)設定可以實現(xiàn)在一步之內實現(xiàn)近乎最優(yōu)的網絡配置更新。泛用性強：DRL算法驅動的網絡節(jié)點不需要知道網絡的整體形態(tài)，它們一般假定網絡是一個黑盒而自動優(yōu)化算法，對于不同的網絡，只需要修改回報函數(shù)，不需要重新設計算法，即可獲得不錯的路由優(yōu)化效果。這樣就節(jié)約了大量網絡建模的時間以及適配不同網絡和硬件花費的時間和網絡資源。參考文獻BouzidiEH,OuttagartsA,LangarR.Deepreinforcementlearningapplicationfornetworklatencymanagementinsoftwaredefinednetworks[C]//2019IEEEGlobalCommunicationsConference(GLOBECOM).IEEE,2019:1-6.LiW,LiG,YuX.AfasttrafficclassificationmethodbasedonSDNnetwork[C]//The4thInternationalConferenceonElectronics,CommunicationsandNetworks,Beijing,China.2015:223-229.ParsaeiMR,MohammadiR,JavidanR.AnewadaptivetrafficengineeringmethodfortelesurgeryusingACOalgorithmoversoftwaredefinednetworks[J].EuropeanResearchinTelemedicine/LaRechercheEuropeenneenTelemedecine,2017,6(3-4):173-180.WangJ,deLaatC,ZhaoZ.QoS-awarevirtualSDNnetworkplanning[C]//2017IFIP/IEEESymposiumonIntegratedNetworkandServiceManagement(IM).IEEE,2017:644