2021, Vol. 47
2. 苏州科技大学 江苏省建筑智慧节能重点实验室, 江苏 苏州 215009;
3. 苏州科技大学天平学院 电子与信息工程学院, 江苏 苏州 215011
2. Jiangsu Province Key Laboratory of Intelligent Building Energy Efficiency, Suzhou University of Science and Technology, Suzhou, Jiangsu 215009, China;
3. School of Electronical and Information Engineering, Tianping College of Suzhou University of Science and Technology, Suzhou, Jiangsu 215011, China
开放科学（资源服务）标志码（OSID）：
随着智慧城市的快速发展，实时监控、远程控制、虚拟现实等应用对带宽、时延、丢包率等网络性能提出了更高要求。传统的单一接入技术受限于有限的网络资源以及资源利用的不均衡性，很难满足需求，因此，能充分利用网络资源的多路径传输技术成为了当前的研究热点[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之间的多条路径，并在路径中合理分配子流，以满足网络性能指标。
|
Download:
|
| 图 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。
| $ \mathit{\boldsymbol{D}}=\left[\begin{array}{l}{D}_{11}&{D}_{12}&\dots &{D}_{1n}\\ {D}_{21}&{D}_{22}&\dots &{D}_{2n}\\ & \vdots & \vdots & \vdots &\\ {D}_{n1}&{D}_{n2}&\dots &{D}_{nn}\end{array}\right] $ | (1) |
定义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(从转发节点到达下一跳节点的传输时延)并到达下一状态，不断重复此过程直到任务结束。
|
Download:
|
| 图 2 强化学习基本模型 Fig. 2 Basic model of reinforcement learning | |
本文的路由算法主要基于强化学习中Q-learning算法，该算法是一种经典的off-policy的TD控制算法，同时也是一种基于状态动作值函数的算法，如式(2)所示：
| $ Q\left(S_{t}, a\right)=(1-\alpha) Q\left(S_{t}, a\right)+\alpha\left[R_{t}+\gamma \max \limits_{a^{\prime}} Q\left(S_{t+1}, a^{\prime}\right)\right] $ | (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作为下一跳节点。
|
Download:
|
| 图 3 基于强化学习的路由模型 Fig. 3 Routing model based on reinforcement learning | |
在Agent更新方面，以k为宿节点的流量完成从本节点i到下一跳节点j的传输后，将这一段传输时延作为Agent执行动作后从环境获得的立即奖赏r，并更新节点i的Q-table，如式(3)所示：
| $ Q_{i}(k, j)=(1-\alpha) Q_{i}(k, j)+\alpha\left[r+\gamma \min \limits_{n \in F(j)} Q_{j}(k, n)\right] $ | (3) |
其中：r为流量在节点执行转发后获得的立即奖赏，即流量从节点i到节点j的传输时延；Qj(k，n)为节点j的Q-table中表示宿节点为k且下一跳节点为n的Q-value值。
1.3 策略部署与实施本文算法采用基于时间片段的控制反馈机制，Agent在每个时间片段内根据网络状态给出路由决策，并根据反馈更新策略。考虑到算法建立在对网络实时状态数据的获取和分析基础之上，其在部署和实施时一方面需要准确感知网络整体的状态视图信息，另一方面也需要网络具备逻辑集中的决策能力以及决策中心到各个相关节点的统一部署和管控能力。因此，本文算法选择面向SDN架构的控制框架。
在控制框架中，决策等核心功能置于控制器，通过SDN下的网络视图功能获得网络状态。当决策结果转化为流表后，通过SDN的流表将功能下发至转发节点执行。框架具体工作流程是在每个时间片段内，网络根据上一个时间片段生成的策略执行流量转发；然后采集网络状态信息，交由控制框架在原来基础上迭代计算，生成新的控制策略并将其转化为流表，通过SDN下发到网络用于下一个时间片段执行，以此类推，构成闭环反馈。多路径路由及子流分配协同控制框架如图 4所示。
|
Download:
|
| 图 4 多路径路由及子流分配协同控制框架 Fig. 4 Multi-path routing and subflow allocation cooperative control framework | |
在控制框架工作流程的基础上，构建多路径路由及子流分配协同控制框架，由网络状态信息处理模块、协同控制智能决策模块以及控制策略生成和部署模块组成。其中，算法部署于SDN控制器，由协同控制智能决策模块与控制策略生成和部署模块协同实现。控制框架中各模块作用如下：
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的多路径路由选择算法，通过在线学习实现路由策略的实时更新。基于图 1所示的拓扑，从源节点A到宿节点B的多条传输路径生成过程如图 5所示。
|
Download:
|
| 图 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在迭代过程中更倾向于不选择带回环的路径，从而保证算法在迭代过程中迅速摒弃会导致回环的策略。
| $ Q_{i}(k, j)=(1-\alpha) Q_{i}(k, j)+\alpha\left[\beta r+\gamma \min\limits _{n \in F(j)} Q_{j}(k, n)\right] $ | (4) |
结合式(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 Snnode not in pathi and Snnode in 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的回环消除方法后，不仅可以加快任务传输成功率的收敛速度，还能提高路由决策的准确性，最终实现完全避免回环的出现，使算法更贴合应用场景。
|
Download:
|
| 图 6 不同回环处理下任务传输成功率对比 Fig. 6 Comparison of task transmission success rate under different loopback processing | |
基于江苏省建筑智慧节能重点实验室，设计端到端多路径传输控制网络实验床进行实验，网络环境拓扑如图 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。
|
Download:
|
| 图 7 实验网络环境拓扑 Fig. 7 Experimental network environment topology | |
本实验流量的生成基于泊松分布模型计算。在网络负载方面采用分级方式表示，按当前网络负载占网络总容量的百分比将网络负载分为无负载、25%负载、50%负载、75%负载4个等级。按接入节点的链路数量将节点缓冲区划分成3个等级，分别为12 MB、16 MB、32 MB。此外，实验假设流量传输不受链路影响，设置链路带宽为1 000 MB。在数据统计方面，忽略背景流量，将丢包率转化为任务传输成功率作为性能指标，设置时延的统计单位为ms，吞吐量的统计单位为MB。实验的相关参数设置如表 1所示。
|
下载CSV 表 1 实验参数设置 Table 1 Experimental parameters setting |
采用的对照实验有：算法1使用传统最短路径进行数据传输；算法2使用基于强化学习的Q-routing进行数据传输；算法3使用等价多路径传输转发算法ECMP进行数据传输。
3.3 算法收敛性评估针对多路径路由及子流分配协同算法在不同网络负载下的训练情况进行实验，记录训练过程中时延的变化，通过每轮迭代间传输时延的变化观察算法的收敛情况。此外，设定一个阈值，当时延波动小于阈值时，认为时延仍处于稳定状态。算法在训练时针对不同网络负载下的时延收敛情况如图 8所示。从图 8可以看出，在无负载、25%负载、50%负载、75%负载网络情况下，随着训练不断进行，传输时延不断降低，在迭代次数为20~40趋于稳定。此时，认为算法收敛到最优值。因此，该算法具有良好的收敛性。
|
Download:
|
| 图 8 在不同网络负载下算法时延收敛对比 Fig. 8 Delay convergence comparison of algorithm under different network loads | |
为验证多路径路由及子流分配协同算法在网络动态运行时，能否根据网络状态实时计算多路径路由并与子流分配协同，从而提高传输性能。本文从时延、任务传输成功率、吞吐量3个性能指标，分别统计在静态网络负载下与动态网络负载下本算法的性能表现以及与对比算法之间的差异。在静态网络负载下，实验根据3.2节中的设计，按百分比划分网络负载，在强度相同的网络负载下对比不同算法间的差异。在动态网络负载下，初始网络负载强度设置为低负载，并在迭代过程中使某一节点负载变高(选取节点v8发生负载变动)，对比各算法在网络负载变动时各项性能指标变化情况。
3.4.1 时延对比在静态网络负载下，对比不同算法在不同网络负载下的传输时延差异如图 9所示。在动态网络负载下，对比节点负载变化前后各算法在时延上的表现如图 10所示。从图 9可以看出，在不同强度的网络负载下，本文算法传输时延低于其他对比算法，且差距随着网络负载变大而变大。尤其在75%负载下，相比其他3种算法，本文算法传输时延分别降低了33.6%、27.6%和18.8%。说明本文提出的多路径路由及子流分配协同算法能充分发挥多路径传输的优势。从图 10可以看出，在迭代次数为40，发生节点负载变化，此时，本文算法的传输时延已实现收敛。网络负载变化后，虽然时延在一段时间内升高了，但随着算法在线学习进行，时延迅速降低了17%并收敛至稳定。对比算法无法有效针对实时网络状态调整策略，导致传输时延处于一个较大值。通过对比不同算法在面对负载变化时时延的波动，本文算法适应了新的网络环境，降低了因网络负载变化而变大的网络负载。
|
Download:
|
| 图 9 静态网络负载下不同算法时延对比 Fig. 9 Delay comparison of different algorithms under static network load | |
|
Download:
|
| 图 10 动态网络负载下不同算法时延对比 Fig. 10 Delay comparison of different algorithms under dynamic network load | |
在静态网络负载下各算法任务传输成功率对比如表 2所示，在动态网络负载下各算法任务传输成功率对比如表 3所示。
|
下载CSV 表 2 静态网络负载下不同算法任务传输成功率对比 Table 2 Task transmission success rate comparison of different algorithms under static network load |
|
下载CSV 表 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所示。
|
Download:
|
| 图 11 静态网络负载下不同算法吞吐量对比 Fig. 11 Throughput comparison of different algorithms under static network load | |
|
Download:
|
| 图 12 动态网络负载下不同算法吞吐量对比 Fig. 12 Throughput comparison of different algorithms under dynamic network load | |
从图 11可以看出，随着网络负载变大，各算法的吞吐量均呈递减趋势。由于受任务传输成功率的影响，本文算法吞吐量减小幅度较小。在高负载下，借助良好的路由发现和子流分配能力，本文算法依旧能保证较高的吞吐量。从图 12可以看出，通过对比各算法在网络负载变化前后吞吐量上的变化，即使网络负载突然变大，但对本文算法吞吐量的影响很小，这得益于强化学习提供的在线学习能力，能针对网络实时状态调整路由与子流分配。对比算法在网络负载变化后无法很好适应新的网络环境，吞吐量分别下降了53.33%、35.61%和28.37%，无法满足稳定的吞吐量需求。
4 结束语本文基于强化学习提出一种智能多路径路由及子流分配协同算法。通过多路径路由方法和Q-value的回环消除算法，提高算法的收敛速度。实验结果表明，与常用路由算法相比，多路径路由及子流分配协同算法在网络环境发生变化时，能实时调整多路径路由及子流分配协同策略，提高传输成功率和吞吐量，降低传输时延。为进一步考虑端到端多路径传输跨层优化的必要性，后续将研究智能多路径路由及子流分配协同算法与传输层的拥塞处理机制。
| [1] |
JIANG Z, WU Q, LI H W, et al. Survey on internet end-to-end multipath transfer research with cross-layer optimization[J]. Journal of Software, 2019, 30(2): 112-132. (in Chinese) 江卓, 吴茜, 李贺武, 等. 互联网端到端多路径传输跨层优化研究综述[J]. 软件学报, 2019, 30(2): 112-132. |
| [2] |
WANG Z, YUAN Q Y, HAO F F, et al. Multipath congestion control algorithm based on link capacity[J]. Journal on Communications, 2020, 41(5): 59-71. (in Chinese) 王竹, 袁青云, 郝凡凡, 等. 基于链路容量的多路径拥塞控制算法[J]. 通信学报, 2020, 41(5): 59-71. |
| [3] |
YANG Y, YANG J H, WEN H S. Routing algorithm design based on timeslot of transmission for data centers[J]. Journal of Software, 2018, 29(8): 2485-2500. (in Chinese) 杨洋, 杨家海, 温皓森. 基于时隙传输的数据中心路由算法设计[J]. 软件学报, 2018, 29(8): 2485-2500. |
| [4] |
ALHARBI F, FEI Z. An SDN architecture for improving throughput of large flows using multipath TCP[C]//Proceedings of the 5th IEEE International Conference on Cyber Security and Cloud Computing. Washington D.C., USA: IEEE Press, 2018: 1-6.
|
| [5] |
DU P, PANG F, BRAUN T, et al. Traffic optimization in software defined naval network for satellite communications[C]//Proceedings of 2017 IEEE Military Communications Conference. Washington D.C., USA: IEEE Press, 2017: 12-15.
|
| [6] |
ZHAO P, ZHAO W, LIU Q. Multi-objective link-separation multipath selection using k max-min for software-defined MANETs[C]//Proceedings of the 15th International Conference on Mobile Ad-Hoc and Sensor Networks. Washington D.C., USA: IEEE Press, 2019: 12-18.
|
| [7] |
DUAN J, WANG Z, WU C. Responsive multipath TCP in SDN-based datacenters[C]//Proceedings of 2015 IEEE International Conference on Communications. Washington D.C., USA: IEEE Press, 2015: 5296-5301.
|
| [8] |
ZHAO J, LIU J, WANG H, et al. Multipath TCP for datacenters: from energy efficiency perspective[C]//Proceedings of 2017 IEEE Conference on Computer Communications. Washington D.C., USA: IEEE Press, 2017: 1-9.
|
| [9] |
NAM H, CALIN D, SCHULZRINNE H. Towards dynamic MPTCP path control using SDN[C]//Proceedings of 2016 IEEE NetSoft Conference. Washington D.C., USA: IEEE Press, 2016: 286-294.
|
| [10] |
TARIQ S, BASSIOUNI M. QAMO-SDN: QoS aware multipath TCP for software defined optical networks[C]//Proceedings of the 12th Annual IEEE Consumer Communications and Networking Conference. Washington D.C., USA: IEEE Press, 2015: 485-491.
|
| [11] |
DHALIWAL H K, LUNG C H. Load balancing using ECMP in multi-stage clos topology in a datacenter[C]//Proceedings of 2018 IEEE Conference on Dependable and Secure Computing. Washington D.C., USA: IEEE Press, 2018: 1-7.
|
| [12] |
RHAMDANI F, SUWASTIKA N A, NUGROHO M A. Equal-cost multipath routing in data center network based on software defined network[C]//Proceedings of the 6th International Conference on Information and Communication Technology. Washington D.C., USA: IEEE Press, 2018: 222-226.
|
| [13] |
CHEN Z Y, ZHU S M. Designing and implementation of multi-path QoS routing algorithm based on overlay network[J]. Journal on Communications, 2018, 39(S1): 200-205. (in Chinese) 陈章迎, 朱尚明. 基于重叠网络的多路径路由设计和实现[J]. 通信学报, 2018, 39(S1): 200-205. |
| [14] |
GAO X M, WANG B S, DENG W P. SDRS: elastic multi-path routing mechanism with integration of centralization control and distribution control[J]. Chinese Journal of Computers, 2018, 41(9): 1976-1989. (in Chinese) 高先明, 王宝生, 邓文平. SDRS: 集中与分布控制相结合的弹性多路径路由机制[J]. 计算机学报, 2018, 41(9): 1976-1989. |
| [15] |
YE J L, CHEN C, CHU Y H. A weighted ECMP load balancing scheme for data centers using P4 switches[C]//Proceedings of 2018 IEEE International Conference on Cloud Networking. Washington D.C., USA: IEEE Press, 2018: 1-4.
|
| [16] |
MARCO C, GABOR R, MICHAEL S. Oblivious routing in IP networks[J]. IEEE/ACM Transactions on Networking, 2018, 1-14. |
| [17] |
HUANG J Y, LAN J L, HU Y X, et al. A segment routing based multipath flow transmission mechanism[J]. Acta Electronica Sinica, 2018, 46(6): 1488-1495. (in Chinese) 黄建洋, 兰巨龙, 胡宇翔, 等. 一种基于分段路由的多路径流传输机制[J]. 电子学报, 2018, 46(6): 1488-1495. DOI:10.3969/j.issn.0372-2112.2018.06.031 |
| [18] |
CAI Y P, WANG C P. Software defined data center network with hybrid routing[J]. Journal on Communications, 2016, 37(4): 44-52. (in Chinese) 蔡岳平, 王昌平. 软件定义数据中心网络混合路由机制[J]. 通信学报, 2016, 37(4): 44-52. |
| [19] |
XU J W, WU M Q, HOU X L. A traffic scheduling scheme for data center networks based on SDN[C]//Proceedings of the 5th International Conference on Computer and Communications. Washington D.C., USA: IEEE Press, 2019: 1417-1422.
|
| [20] |
HUANG X, CHENG S, CAO K, et al. A survey of deployment solutions and optimization strategies for hybrid SDN networks[J]. IEEE Communications Surveys & Tutorials, 2019, 21(2): 1483-1507. |
| [21] |
PAN C S, LIU Y, SHI H F, et al. Spatial information network business identification technology under SDN architecture[J]. Computer Engineering, 2019, 45(4): 18-24. (in Chinese) 潘成胜, 刘勇, 石怀峰, 等. SDN架构下的空间信息网络业务识别技术[J]. 计算机工程, 2019, 45(4): 18-24. |
| [22] |
PENG D Q, LAI X W, LIU Y L. Multi-path routing algorithm for fat-tree data center network based on SDN[J]. Computer Engineering, 2018, 44(4): 41-45, 65. (in Chinese) 彭大芹, 赖香武, 刘艳林. 基于SDN的胖树数据中心网络多路径路由算法[J]. 计算机工程, 2018, 44(4): 41-45, 65. DOI:10.3969/j.issn.1000-3428.2018.04.007 |
| [23] |
MAKSIC N. Two-phase load balancing for data center networks using OpenFlow[C]//Proceedings of the 25th Telecommunication Forum. Washington D.C., USA: IEEE Press, 2017: 1-4.
|
| [24] |
NARAYAN D G, MUDENAGUDI U. A joint approach to routing metrics and application-aware rate adaptation in multi-radio wireless mesh networks[J]. Journal of High Speed Networks, 2017, 23(2): 93-108. DOI:10.3233/JHS-170559 |
| [25] |
LIU C Y, XU M W, GENG N, et al. A survey on machine learning based routing algorithms[J]. Journal of Computer Research and Development, 2020, 57(4): 671-687. (in Chinese) 刘辰屹, 徐明伟, 耿男, 等. 基于机器学习的智能路由算法综述[J]. 计算机研究与发展, 2020, 57(4): 671-687. |
| [26] |
LUONG N C, HOANG D T, GONG S, et al. Applications of deep reinforcement learning in communications and networking: a survey[J]. IEEE Communications Surveys and Tutorials, 2019, 21(4): 3133-3174. DOI:10.1109/COMST.2019.2916583 |