一種智能多路徑路由及子流分配協同算法

徐 嘯，顧玲麗，陳建平，傅啟明，3，陸 悠，3

（1.蘇州科技大學電子與信息工程學院，江蘇蘇州 215009；2.蘇州科技大學江蘇省建筑智慧節能重點實驗室，江蘇蘇州 215009；3.蘇州科技大學天平學院電子與信息工程學院，江蘇 蘇州 215011）

0 概述

隨著智慧城市的快速發展，實時監控、遠程控制、虛擬現實等應用對帶寬、時延、丟包率等網絡性能提出了更高要求。傳統的單一接入技術受限于有限的網絡資源以及資源利用的不均衡性，很難滿足需求，因此，能充分利用網絡資源的多路徑傳輸技術成為了當前的研究熱點［1］。與傳統的單路徑傳輸技術相比，端到端多路徑傳輸技術主要利用終端上的多種接入方式（如WiFi、WLAN、蜂窩網絡接口）以及兩端之間的多條可達路徑，實現端到端多條路徑并行傳輸數據，進一步提高對網絡資源的利用并滿足應用需求［2］。多路徑傳輸本質是在源節點與宿節點之間的多條可達路徑中選取合適的路徑并分配子流進行并行傳輸，所以多路徑路由是實現高效傳輸的關鍵因素［3］。由于不同路徑間的實際狀況存在差異，路由與子流分配的協同也會對多路徑傳輸性能造成較大影響，因此多路徑路由和子流分配成為當前多路徑傳輸研究的重點。

針對上述問題，研究人員提出許多不同的解決方案。在多路徑路由方面，解決方案主要分為兩類。第一類方案是根據路由可達性進行多路徑路由計算，為不同子流選擇互不相交的路徑，避免出現不同子流共用瓶頸路徑的問題。例如文獻［4］提出的算法以最短路徑為依據，依次選擇多條互不相交的短路徑作為多路徑傳輸路徑。文獻［5］采用類似的選路算法，根據需求選出k條節點不相交或鏈路不相交路徑。文獻［6］在選出k條不相交路徑的同時要求最小帶寬路徑最大。第二類方案在選路的同時考慮鏈路負載。文獻［7-8］在選路時以鏈路負載為依據，優先選擇負載較輕的路徑。文獻［9］選擇帶寬較大且相互帶寬差異較小的路徑進行傳輸。文獻［10］在進行路由選擇的同時考慮上層業務的需求，根據傳輸任務的優先級進行選路和分配資源。上述工作從不同角度實現了多路徑路由，在一定程度上提高多路徑傳輸性能。但這些多路徑路由大多數是靜態的，無法根據實時網絡狀態及時調整路由。除上述針對多路徑路由問題的解決方案外，也有許多從子流分配角度入手提高多路徑傳輸效率的工作。等價多路徑（Equal-Cost Multi-Path，ECMP）路由算法是一種較早提出的解決方案［11-12］，但僅將子流均勻地分配給多條可選路徑，并未考慮不同路徑的網絡狀態［13-14］。文 獻［15］提出加 權多路 徑（Weight-Cost Multi-Path，WCMP）路由策略對多路徑路由進行改進，按不同路徑的帶寬為多路徑路由分配不同的子流，但其參考的帶寬為靜態值，由于網絡的動態變化，其分配決策不一定能確保是最優的。根據路徑長度及懲罰性指數函數，DEFT 算法在最短路徑與長路徑上分配流量［16］，以此突破等價多路徑平均分配子流的限制，但其與最短路徑機制不兼容，限制在實際網絡中的應用。

子流分配工作的最大問題是子流分配決策往往取決于靜態的鏈路狀態，缺少對網絡狀態動態變化的感知，無法實時發現當前負載較輕的路徑［17］。因此，也有研究人員在子流分配過程中考慮流量的動態特征，如軟件定義混合路由（Software-defined Hybrid Routing，SHR）算法依據網絡中長流與短流的分布特點［18-19］，在軟件定義網絡（Software Defined Network，SDN）架構支撐下［20-21］，通過控制器感知流的截止時間及網絡轉發節點的等待隊列長度，對網絡中的長流進行優化調度，短流則由交換節點根據帶寬狀態隨機選路。MLF 算法［22］考慮長流、短流的分布特點，依據鏈路剩余帶寬和哈希運算對長流進行調度，在此基礎上為短流分配剩余帶寬最大的路徑。這些方法雖然考慮到長流、短流的動態特點，通過有側重調度來優化多路徑傳輸，但這種將流量區分進而分別調度的做法會導致路由與子流分配相互缺少協同，影響多路徑傳輸性能。除此之外，也有研究從網絡全局負載角度入手解決子流分配問題，例如文獻［23］提出一種負載均衡算法，設計多路徑路由模型，以鏈路可用帶寬作為輸入，從全網角度確定傳輸路徑和子流分配。文獻［24］則基于全局資源視圖設計擁塞控制機制，同樣以鏈路帶寬利用率為依據，為流量分配合適的路徑，并可以實時調整傳輸速率。但這兩種算法側重點為網絡負載均衡，缺乏依據網絡狀態實時調整路由和子流分配的能力。

在網絡動態變化環境下，當前多路徑傳輸機制在多路徑路由、子流分配以及兩者協同方面的局限性主要有：1）在路由方面缺少實時、智能的方法，能夠自適應依據網絡狀態變化實時調整多路徑傳輸所使用的路由，因此在網絡負載變化較大時，很難及時調整傳輸路徑；2）子流分配缺乏與多路徑路由的協同。在已有多路徑路由信息的基礎上，根據鏈路帶寬等狀態指標，按固定或動態調整子流的分配、傳輸速率等，較少根據網絡實時狀態動態地與路由協同決策。因此，子流分配調度無法充分配合路由的變化，從而限制多路徑傳輸的性能，不能充分發揮多路徑傳輸優勢。

本文引入在線學習思路［25］，利用SDN 提供的集中控制以及網絡一致性狀態視圖等方面優勢，提出一種智能多路徑路由及子流分配協同算法。采用Q-learning 設計多路徑路由算法使傳輸路由和子流分配能夠相互協同和在線更新，并通過Q-value 的回環消除方法，提高算法收斂速度。

1 問題描述與建模

1.1 問題描述

端到端多路徑傳輸拓撲（選用智能路由場景下經典的NSFNet［26］拓撲）如圖1 所示，在網絡環境下源節點A、宿節點B之間存在傳輸任務，節點A與B之間的網絡拓撲如圖1 所示存在多條可達路徑。在路由和子流分配方面，根據網絡實時運行狀態描述節點A與B之間多路徑傳輸的決策問題，尋找A與B之間的多條路徑，并在路徑中合理分配子流，以滿足網絡性能指標。

圖1 端到端多路徑傳輸拓撲Fig.1 End-to-end multi-path transmission topology

為方便后續算法描述和討論，給出如下定義：

定義1（圖、源節點、宿節點、轉發節點、邊、鄰接矩陣）如圖1 所示的網絡拓撲中，網絡鏈路、轉發節點、發送和接收端可以用無向圖G=（V，E，c（v），m，n）表示。其中：V=｛A，B，V*｝為網絡中節點集合，代表傳輸層設備；A表示源節點；B表示宿節點；集合V*=｛v1，v2，…，vi｝表示轉發節點。E為網絡中邊集合，代表鏈路，c（vi）代表集合V*中的轉發節點vi的容量，并且m和n分別表示圖G中節點數和邊數。為了便于討論，用n行n列的鄰接矩陣D表示無向圖G，如式（1）所示。當節點i與節點j是鄰居節點時，Dij和Dji都為1，否則為0。

定義2（路由、鄰居節點、下一跳節點選擇）在網絡傳輸過程中，路由規定了流量從源節點到宿節點的路徑。在圖1 中，傳輸路徑A、v1、v7、v9、B為源節點A到宿節點B的一個路由。定義F（v）為路由中轉發節點v的鄰居節點。例如，F（v7）=｛v1，v6，v9｝。由于轉發節點v需從鄰居節點F（v）中選取一個節點作為下一跳節點和組成路由的一部分，因此定義下一跳節點選擇，將其描述為nnext=R（v，B），其中v（v∈V*）為定義1 中討論的轉發節點，B為定義1 中討論的的宿節點，nnext（nnext∈F（v））表示路由算法為轉發節點v上待轉發流量分配的下一跳節點。在此基礎上，由源節點A到宿節點B的傳輸路徑由多個下一跳節點通過nnext=R（v，B）迭代生成，過程如下：v1=R（A，B），v7=R（v1，B），v9=R（v7，B），B=R（v9，B），最終形成傳輸路徑A、v1、v7、v9、B。

定義3（傳輸任務、子流）對于一個端到端多路徑傳輸任務（Task），T=｛Tid，Tsrc，Tdst，Tsize｝四元組表示，如圖1 拓撲中A到B的傳輸任務可表述為：Tid為任務編號，源節點Tsrc=A，宿節點Tdst=B，Tsize表示傳輸任務大小。對于任務（Task）在多路徑傳輸中產生的子流（Subflow），S=｛Sid，Ssrc，Sdst，Ssize，Spnode，Snnode｝六元組表示，Sid表示子流的編號，Ssrc=A表示源節點，Sdst=B表示宿節點，Ssize表示子流大小，Spnode（Spnode∈V*）表示子流當前所在的轉發節點，Snnode=R（Spnode，B）表示路由算法為子流分配的下一跳節點。

定義4（節點負載）在網絡運行過程中，隨著新任務和舊任務的完成，網絡負載都處于不斷變化的過程中。本文定義L（v）為節點v的負載，并通過節點負載的變化表示網絡負載變化。例如，對于轉發節點v，L（v）=50%表示節點v的當前負載占其負載能力的50%。

1.2 基于強化學習的路由模型

考慮到多路徑傳輸對路由實時調整能力的需求，引入強化學習中的Q-learning 算法，建立面向在線學習的多路徑路由模型。

強化學習作為機器學習的一個重要分支，區別于有監督學習和無監督學習，其通過Agent 不斷地與環境交互，可以在線學習到解決問題的最優策略。經典強化學習模型如圖2 所示，主要包括Agent、環境、動作、狀態、獎賞元素。在多路徑路由問題中，經典模型每個智能體Agent（代表路由中的轉發節點）感知當前所處環境狀態St（待轉發流量的目標節點），根據策略（路由選擇策略）選擇動作at（選擇下一跳節點）執行，環境在動作at的作用下返回獎賞Rt（從轉發節點到達下一跳節點的傳輸時延）并到達下一狀態，不斷重復此過程直到任務結束。

圖2 強化學習基本模型Fig.2 Basic model of reinforcement learning

本文的路由算法主要基于強化學習中Q-learning算法，該算法是一種經典的off-policy 的TD 控制算法，同時也是一種基于狀態動作值函數的算法，如式（2）所示：

其中：a為學習速率，決定對之前訓練效果的保留程度；γ為折扣因子，決定對未來獎賞的重視程度。初始化時算法需建立一個Q 值表（Q-table），初始值設置為0。在學習過程中，假設時刻t，Agent 所處狀態為St（算法輸入），采取動作at（算法響應事件）遷移至下一狀態St+1，并獲得立即獎賞Rt，根據式（2）更新Q 值表。通過不斷迭代，最終收斂至最優狀態動作值函數，并依此獲得最優動作策略。

基于上述理論，強化學習在路由選擇上的模型如圖3 所示，每個節點都有相應的Q-table 作為該節點的下一跳節點選擇策略。其中，Q-table 的行代表狀態，即宿節點，列代表動作，即流量在該節點可選擇的鄰居節點。結合1.1 節中下一跳節點選擇的定義，以圖3 為例，形如nnext=R（v1，v4）的路由選擇策略描述如下，對于位于轉發節點v1且宿節點為v4的待轉發流量，從節點v1對應的Q-table 中選取宿節點v4所在的行，通過ε-greedy 策略根據該行中Q-value 值從鄰居節點F（v1）中選取某節點nnext作為下一跳節點。

圖3 基于強化學習的路由模型Fig.3 Routing model based on reinforcement learning

在Agent 更新方面，以k為宿節點的流量完成從本節點i到下一跳節點j的傳輸后，將這一段傳輸時延作為Agent 執行動作后從環境獲得的立即獎賞r，并更新節點i的Q-table，如式（3）所示：

其中：r為流量在節點執行轉發后獲得的立即獎賞，即流量從節點i到節點j的傳輸時延；Qj（k，n）為節點j的Q-table 中表示宿節點為k且下一跳節點為n的Q-value 值。

1.3 策略部署與實施

本文算法采用基于時間片段的控制反饋機制，Agent 在每個時間片段內根據網絡狀態給出路由決策，并根據反饋更新策略。考慮到算法建立在對網絡實時狀態數據的獲取和分析基礎之上，其在部署和實施時一方面需要準確感知網絡整體的狀態視圖信息，另一方面也需要網絡具備邏輯集中的決策能力以及決策中心到各個相關節點的統一部署和管控能力。因此，本文算法選擇面向SDN 架構的控制框架。

在控制框架中，決策等核心功能置于控制器，通過SDN 下的網絡視圖功能獲得網絡狀態。當決策結果轉化為流表后，通過SDN 的流表將功能下發至轉發節點執行?？蚣芫唧w工作流程是在每個時間片段內，網絡根據上一個時間片段生成的策略執行流量轉發；然后采集網絡狀態信息，交由控制框架在原來基礎上迭代計算，生成新的控制策略并將其轉化為流表，通過SDN 下發到網絡用于下一個時間片段執行，以此類推，構成閉環反饋。多路徑路由及子流分配協同控制框架如圖4 所示。

圖4 多路徑路由及子流分配協同控制框架Fig.4 Multi-path routing and subflow allocation cooperative control framework

在控制框架工作流程的基礎上，構建多路徑路由及子流分配協同控制框架，由網絡狀態信息處理模塊、協同控制智能決策模塊以及控制策略生成和部署模塊組成。其中，算法部署于SDN 控制器，由協同控制智能決策模塊與控制策略生成和部署模塊協同實現?？刂瓶蚣苤懈髂K作用如下：

1）網絡狀態信息處理模塊具有網絡狀態感知功能和策略反饋更新功能。網絡狀態感知功能通過基于SDN 的信息采集及策略部署交互接口獲取全局的網絡狀態視圖得到來自轉發節點的狀態感知信息，如網絡節點負載、網絡拓撲等，以供其他模塊實現對網絡的優化控制。策略反饋更新功能通過獲取已完成傳輸任務的反饋信息對策略進行更新。

2）協同控制智能決策模塊具備數據預處理功能和協同決策功能。數據預處理功能是將相關網絡信息抽象成傳輸任務T=｛Tid，Tsrc，Tdst，Tsize｝、Q-table、鄰居節點F（v）、無向圖G=（V，E，c（v），m，n）作為算法的輸入。協同決策功能根據輸入為傳輸任務提供子流分配方案和傳輸路徑，并將其交由后續模塊下發至網絡中。

3）控制策略生成和部署模塊具備流表生成功能和流表下發功能。流表生成功能是根據前一模塊生成的路由及子流分配決策生成路由轉發流表。然后流表下發功能通過基于SDN 的信息采集及策略部署交互接口將其下發到傳輸網絡。

基于上述框架及模塊工作流程，將算法與SDN兩者優勢相互結合，實現路由集中控制與快速更新，有利于充分發揮多路徑傳輸的優勢。

2 算法實現

2.1 多路徑路由選擇算法

在路由方面，本文設計基于Q-learning 的多路徑路由選擇算法，通過在線學習實現路由策略的實時更新?；趫D1 所示的拓撲，從源節點A到宿節點B的多條傳輸路徑生成過程如圖5 所示。

圖5 多路徑路由選擇算法Fig.5 Multi-path routing selection algorithm

從圖5 可以看出，傳輸任務在源節點根據網絡接口數拆分成多個子流。在傳輸路徑選擇上，通過1.1 節中定義nnext=R（v，B）為轉發節點v上宿節點為B的待轉發流量提供下一跳節點。當傳輸任務每個子流都成功完成傳輸時，認為任務傳輸成功，并且將從流量出發到最后一個子流到達宿節點的總時間作為任務完成時間。若子流在傳輸過程中出現路由回環或節點過載，則認為任務傳輸失敗。

在任務傳輸成功后，根據式（3）更新子流經過的節點的Q-table，并將更新后的Q-table 和nnext=R（v，B）作為算法輸出用于后續的傳輸任務。通過不斷迭代上述過程，算法最終能使Agent 學習到較好的策略。

2.2 多路徑路由與子流分配協同決策算法

對于多路徑傳輸，只進行路由選擇優化是不夠的，還需要路由與子流分配策略相互協同，才能更大地發揮多路徑傳輸的優勢。正確的分配方式為資源充裕的路徑分配相對多的流量，以此為資源緊張的路徑減輕傳輸壓力。因此提出路由協同的子流分配算法。

以1.1 節中的問題描述及定義為背景，路由協同的子流分配算法首先根據宿節點B和源節點A的不同接 口，從A的Q-table 中取對應的Q-value 為QA（B，v1）、QA（B，v2）和QA（B，v3）；其次分別將Q-value 取倒數。最終將傳輸流量按的比例分配給每一個接口。

路由協同的子流分配算法的優化效果由Q-value 性質決定。在強化學習模型中，動作的好壞能通過Q-value 值反映。因此，在本文模型中能通過源節點不同接口對應的Q-value 值衡量其所在路徑傳輸能力的好壞，并且兩者關系呈負相關。由于在路由與子流分配兩方面的決策都基于Q-value 進行，兩者共同計算，并且Q-value 隨著傳輸任務的完成而更新，因此，通過提出路由協同的子流分配方法能實現兩者相互協同與在線優化。在將2.1 節算法結合本方法后，可形成多路徑路由與子流分配協同決策算法。以圖1 拓撲為例，算法詳細偽代碼見算法1。

算法1多路徑路由與子流分配協同決策算法

輸入傳輸任務T=｛Tid，Tsrc，Tdst，Tsize｝、Q-table、鄰居節點F（v）、無向圖G=（V，E，c（v），m，n）

輸出下一跳節點選擇R（v，B）、Q-table

1.從源節點A 的Q-table 中獲取子流分配比例，1/QA（B，v1），1/QA（B，v2），1/QA（B，v3）

2.根據Task 所在源節點A 的網絡接口數以及子流分配比例生成對應的n 個子流Si=｛Sid，Ssrc，Sdst，Ssize，Spnode，Snnode｝，n=3，i≤3

3.WHILE 傳輸任務的子流沒有完成傳輸路徑生成

4.IF 子 流Si=｛Sid，Ssrc，Sdst，Ssize，Spnode，Snnode｝（Sid≤n）在 節點Spnode待轉發

5.Snnode=R（Spnode，B），Snnode∈F（Spnode）

6.將Snnode記入子流Si的傳輸路徑

7.END IF

8.END WHILE

9.將傳輸策略轉化為流表下發到網絡，并獲取根據流表進行傳輸的反饋信息

10.根據式（3）和反饋信息更新Q-table

11.return R（v，B）、Q-table

在以上算法中，第1 步為子流分配，第4 步到第7步為子流的路由選擇，第9 步將選出的路徑通過SDN 下發到轉發節點。在轉發完成后，算法第10 步將對Agent 中的Q-table 進行更新，并在第11 步輸出R（v，B）、Q-table 用于后續傳輸任務的決策。

2.3 無回環的多路徑路由及子流分配協同決策算法

在實際網絡運行環境下，轉發節點在執行算法1時僅基于ε-greedy 策略生成下一跳節點，在某些情況下會導致回環問題，即一系列轉發節點的下一跳節點匯聚成完整路由時出現循環，例如在拓撲圖1中，生成路徑A、v1、v7、v9、v12、v5、v4、v6、v7、v9、B。從長遠分析，這類結果在迭代訓練中會由于傳輸任務時延過長，導致獎賞值降低而被修改，但對于執行這個選擇的傳輸任務而言，會出現傳輸失敗問題。因此，有必要根據網絡路由有效性、準確性和穩定性要求，在上文算法1 基礎上增加回環消除的方法。

由1.2節中所提的路由模型可知，Agent根據Q-value選擇下一跳節點并生成路徑。因此，將Q-value與路由回環掛鉤，根據回環路徑對Q-value做出懲罰，從而使Agent傾向選擇正確路徑。同時，需要為傳輸任務提供備用路徑，防止路由回環導致傳輸失敗。基于以上思路，提出一種基于Q-value 的回環消除方法。

1）為傳輸任務提供備用路徑。如果Agent 選擇的節點導致路由回路，則將這一次傳輸任務視為失敗，終止本次迭代和路徑生成，傳輸任務直接選擇由Dijkstra 算法生成的備用路徑A、v3、v8、B來確保其完成傳輸。

2）在式（3）基礎上引入懲罰系數β（β>1）構造式（4）。一旦轉發節點的下一跳選擇導致回環出現，則直接設置一個預定的高時延閾值作為學習模型的獎賞值（此時節點實際采用備用路徑進行傳輸），然后根據式（4）更新相應的Q-value。在懲罰系數β作用下，以放大Q-value 值的方式主動改變Agent 的選路傾向，使得Agent 在迭代過程中更傾向于不選擇帶回環的路徑，從而保證算法在迭代過程中迅速摒棄會導致回環的策略。

結合式（4）對算法1 進行改進，提出無回環的多路徑路由及子流分配協同決策算法，該算法是針對多路徑路由及子流分配所提的最終算法。

算法2無回環的多路徑路由及子流分配協同決策算法（改進算法）

輸入傳輸任務T=｛Tid，Tsrc，Tdst，Tsize｝、Q-table、鄰居節點F（v）、無向圖G=（V，E，c（v），m，n）

輸出下一跳節點選擇R（v，B）、Q-table

1.為v1、v2、v33 個不同網絡接口分配子流，比例按從源節點A 的Q-table 中獲取 的Q-value 的 倒數：1/QA（B，v1），1/QA（B，v2），1/QA（B，v3）

2.根據TASK 所在源節點A 的網絡接口數以及子流分配比例生成對應的n 個子流Si=｛Sid，Ssrc，Sdst，Ssize，Spnode，Snnode｝，n=3，i≤3

3.設置子流Si的回環標志fi=false

4.WHILE 傳輸任務的子流沒有完成傳輸路徑生成

5.IF 子流Si=｛Sid，Ssrc，Sdst，Ssize，Spnode，Snnode｝（Sid<=n）在節點Spnode待轉發

6.Snnode=R（Spnode，B）

7.IF Snnodenot in pathiand Snnodein Fi（Spnode）：

8.將Snnode記入子流Si的路徑pathi，Fi（Spnode）remove Snnode

9.ELSE

10.出現回環，子流Si停止生成路徑，fi=true

11.END IF

12.END IF

13.END WHILE

14.將傳輸策略轉化為流表下發到網絡，并獲取根據流表進行傳輸的反饋信息。

15.FOR i in range（n）：

16.IF fi=false：

17.對子流Si根據式（3）更新Q-table

18.ELSE

19.對子流Si根據式（4）更新Q-table

20.END IF

21.END FOR

22.return Route（v，B）、Q-table

為消除回環方法對算法的影響，在圖1 的拓撲上采用算法2 的思路，設定源節點為節點A，宿節點為節點B，以不限制回環出現的基于強化學習的多路徑傳輸方法為對比方法（算法1），觀察算法改進前后在任務傳輸成功率上的差異。不同回環處理下任務傳輸成功率對比如圖6 所示。從圖6 可以看出，在迭代前期，采用回環消除方法的算法2 的任務傳輸成功率能保持在一個較高的水平，并且能迅速收斂，避免出現更多回環。與此相反，允許回環算法1 的任務傳輸成功率在前期處于一個較低的值，并且收斂速度緩慢。經過大量迭代后其任務傳輸成功率依舊存在波動，無法完全避免回環。因此，在采用基于Q-value 的回環消除方法后，不僅可以加快任務傳輸成功率的收斂速度，還能提高路由決策的準確性，最終實現完全避免回環的出現，使算法更貼合應用場景。

圖6 不同回環處理下任務傳輸成功率對比Fig.6 Comparison of task transmission success rate under different loopback processing

3 實驗與結果分析

3.1 實驗環境

基于江蘇省建筑智慧節能重點實驗室，設計端到端多路徑傳輸控制網絡實驗床進行實驗，網絡環境拓撲如圖7 所示。網絡環境中有轉發節點12 臺，主機2 臺，服務器1 臺。轉發節點采用支持安裝OpenvSwitch 的主機模擬SDN 網絡轉發設備，使其能采集包括鏈路負載、帶寬使用率、緩沖區長度等網絡狀態信息上傳至控制中心，接收控制中心下發的傳輸決策并執行；服務器C 則安裝FloodLight 作為SDN 網絡控制器，獲取轉發節點的狀態信息，同時部署本文控制機制進行傳輸決策，并將決策結果部署至傳輸節點。主機A 和B 為網絡接入點，通過模擬生成傳輸流量作為傳輸任務的發起者和接收者。在硬件方面，實驗主機配置2.9 GHz Intel Core i5 處理器，8 GB 內存，并安裝Ubuntu19.10 版本操作系統。編程語言采用python，版本為3.7.1，編輯器采用Visual Studio Code。

圖7 實驗網絡環境拓撲Fig.7 Experimental network environment topology

3.2 實驗設置與評估指標

本實驗流量的生成基于泊松分布模型計算。在網絡負載方面采用分級方式表示，按當前網絡負載占網絡總容量的百分比將網絡負載分為無負載、25%負載、50%負載、75%負載4 個等級。按接入節點的鏈路數量將節點緩沖區劃分成3 個等級，分別為12 MB、16 MB、32 MB。此外，實驗假設流量傳輸不受鏈路影響，設置鏈路帶寬為1 000 MB。在數據統計方面，忽略背景流量，將丟包率轉化為任務傳輸成功率作為性能指標，設置時延的統計單位為ms，吞吐量的統計單位為MB。實驗的相關參數設置如表1 所示。

表1 實驗參數設置Table 1 Experimental parameters setting

采用的對照實驗有：算法1 使用傳統最短路徑進行數據傳輸；算法2 使用基于強化學習的Q-routing 進行數據傳輸；算法3 使用等價多路徑傳輸轉發算法ECMP 進行數據傳輸。

3.3 算法收斂性評估

針對多路徑路由及子流分配協同算法在不同網絡負載下的訓練情況進行實驗，記錄訓練過程中時延的變化，通過每輪迭代間傳輸時延的變化觀察算法的收斂情況。此外，設定一個閾值，當時延波動小于閾值時，認為時延仍處于穩定狀態。算法在訓練時針對不同網絡負載下的時延收斂情況如圖8 所示。從圖8 可以看出，在無負載、25%負載、50%負載、75%負載網絡情況下，隨著訓練不斷進行，傳輸時延不斷降低，在迭代次數為20～40趨于穩定。此時，認為算法收斂到最優值。因此，該算法具有良好的收斂性。

圖8 在不同網絡負載下算法時延收斂對比Fig.8 Delay convergence comparison of algorithm under different network loads

3.4 對照實驗及結果分析

為驗證多路徑路由及子流分配協同算法在網絡動態運行時，能否根據網絡狀態實時計算多路徑路由并與子流分配協同，從而提高傳輸性能。本文從時延、任務傳輸成功率、吞吐量3 個性能指標，分別統計在靜態網絡負載下與動態網絡負載下本算法的性能表現以及與對比算法之間的差異。在靜態網絡負載下，實驗根據3.2 節中的設計，按百分比劃分網絡負載，在強度相同的網絡負載下對比不同算法間的差異。在動態網絡負載下，初始網絡負載強度設置為低負載，并在迭代過程中使某一節點負載變高（選取節點v8發生負載變動），對比各算法在網絡負載變動時各項性能指標變化情況。

3.4.1 時延對比

在靜態網絡負載下，對比不同算法在不同網絡負載下的傳輸時延差異如圖9 所示。在動態網絡負載下，對比節點負載變化前后各算法在時延上的表現如圖10 所示。從圖9 可以看出，在不同強度的網絡負載下，本文算法傳輸時延低于其他對比算法，且差距隨著網絡負載變大而變大。尤其在75%負載下，相比其他3 種算法，本文算法傳輸時延分別降低了33.6%、27.6%和18.8%。說明本文提出的多路徑路由及子流分配協同算法能充分發揮多路徑傳輸的優勢。從圖10 可以看出，在迭代次數為40，發生節點負載變化，此時，本文算法的傳輸時延已實現收斂。網絡負載變化后，雖然時延在一段時間內升高了，但隨著算法在線學習進行，時延迅速降低了17%并收斂至穩定。對比算法無法有效針對實時網絡狀態調整策略，導致傳輸時延處于一個較大值。通過對比不同算法在面對負載變化時時延的波動，本文算法適應了新的網絡環境，降低了因網絡負載變化而變大的網絡負載。

圖9 靜態網絡負載下不同算法時延對比Fig.9 Delay comparison of different algorithms under static network load

圖10 動態網絡負載下不同算法時延對比Fig.10 Delay comparison of different algorithms under dynamic network load

3.4.2 任務傳輸成功率對比

在靜態網絡負載下各算法任務傳輸成功率對比如表2 所示，在動態網絡負載下各算法任務傳輸成功率對比如表3 所示。

表2 靜態網絡負載下不同算法任務傳輸成功率對比Table 2 Task transmission success rate comparison of different algorithms under static network load %

表3 動態網絡負載下不同算法任務傳輸成功率對比Table 3 Task transmission success rate comparison of different algorithms under dynamic network load %

從表2 可以看出，低網絡負載下本文算法能保持一個較高的成功率，雖然回環導致失敗任務較少，但通過2.3 節提出的回環消除方法避免產生更多回環。在高網絡負載下，基于ECMP 的多路徑傳輸受益于多路徑傳輸的優勢，仍能進行任務傳輸，但其發生任務傳輸成功率大幅度下降，而最短路徑算法與Q-routing 算法受限于單路徑傳輸而導致任務傳輸成功率迅速下降。尤其是在75%負載下，其他算法的任務傳輸成功率相對于本文算法分別少了49.91%、30.64%和10.23%。從表3 可以看出，在動態網絡負載下，其他算法的任務傳輸成功率相對于本算法分別少了23.62%、19.12%和12.62%。本算法能通過與環境的交互及時調整路由策略，實現任務的穩定傳輸，避免任務傳輸成功率因網絡負載變大而大幅降低。

3.4.3 吞吐量對比

在靜態和動態網絡負載下，對比不同算法間在吞吐量上的差異。在不同靜態網絡負載下各算法吞吐量的差異如圖11 所示。在動態網絡負載下，網絡負載變化前后對比各算法在吞吐量上的差異如圖12所示。

圖11 靜態網絡負載下不同算法吞吐量對比Fig.11 Throughput comparison of different algorithms under static network load

圖12 動態網絡負載下不同算法吞吐量對比Fig.12 Throughput comparison of different algorithms under dynamic network load

從圖11 可以看出，隨著網絡負載變大，各算法的吞吐量均呈遞減趨勢。由于受任務傳輸成功率的影響，本文算法吞吐量減小幅度較小。在高負載下，借助良好的路由發現和子流分配能力，本文算法依舊能保證較高的吞吐量。從圖12 可以看出，通過對比各算法在網絡負載變化前后吞吐量上的變化，即使網絡負載突然變大，但對本文算法吞吐量的影響很小，這得益于強化學習提供的在線學習能力，能針對網絡實時狀態調整路由與子流分配。對比算法在網絡負載變化后無法很好適應新的網絡環境，吞吐量分別下降了53.33%、35.61%和28.37%，無法滿足穩定的吞吐量需求。

4 結束語

本文基于強化學習提出一種智能多路徑路由及子流分配協同算法。通過多路徑路由方法和Q-value的回環消除算法，提高算法的收斂速度。實驗結果表明，與常用路由算法相比，多路徑路由及子流分配協同算法在網絡環境發生變化時，能實時調整多路徑路由及子流分配協同策略，提高傳輸成功率和吞吐量，降低傳輸時延。為進一步考慮端到端多路徑傳輸跨層優化的必要性，后續將研究智能多路徑路由及子流分配協同算法與傳輸層的擁塞處理機制。