《路由优化算法和网络模型的设计与实现》6800字（论文）

路由优化算法和网络模型的设计与实现摘要 随着通信技术和互联网产业的高速发展，网络的形态出现了多样化、复杂化和扁平化的趋势。在软件定义网络的背景下，传统的面对网络层的路由优化技术收敛速度不足，无法及时应对网络结构变化等问题越加凸显。近年来试图利用机器学习实现路由优化的研究越来越多，例如将Q-Learning应用到网络路由中的尝试。由于强化学习拥有较强的决策能力，其在网络优化中的应用较为常见。本论文设计了基于深度强化学习的DDPG算法的网络路由优化算法。由于DDPG算法改进了强化学习中的固定策略梯度算法，可以更准确地拟合策略函数，拥有解决连续高维度规划的能力，适应目前实际网络控制的需要，并且对特定的网络形态依赖较小，因而采取了这一算法。首先采用了OMNeT++网络仿真软件搭建了一个小型的软件控制网络作为仿真平台，网络节点之间通过三种数据包传递信息，通过流量控制组件读取网络权重更新路由。进而基于Keras+tensorflow编写了路由优化算法的主体部分，调用并读取网络自发产生的流量矩阵并在每个步骤中对其进行学习和优化。定义了该算法输入的状态为流量矩阵，输出的动作为链路权重，并且可以针对不同需求和网络指标灵活调整反馈函数，来适应不同的网络形态。最后，进行了仿真实验检验算法性能。实验结果表明，相对于传统的最短路径优先算法，该算法可以有效地降低网络平均时延，减少网络流量浪费，并且具有较好的泛化性。关键词：深度强化学习路由优化DDPG目录TOC\o"1-2"\h\u31549路由优化算法和网络模型的设计与实现 i18207摘要 i237331.1基于DRL的路由优化算法需求分析 ii256481.2路由优化算法的设计 ii64611.2.1路由算法设计的分析 ii274051.2.2路由算法设计的实现 v267311.3网络模型的设计与实现 vii17461.3.1网络模型的分析 vii233651.3.2网络模型的实现 viii13672结语 x11581参考文献 xi1.1基于DRL的路由优化算法需求分析 路由优化算法是根据一系列网络条件来优化路由的选取，从而提高网络性能的算法。在传统的网络形态中，动态路由算法诸如OSPF和BGP虽然能动态生成路由表，但大多只是参考静态的网络参数来确定最佳路径，例如路由器时延、路径跳数、网络容量等。然而容量大、条数少的路径往往数据量也更大，总是选取最佳路径有时候未必会获得最佳的效果。而在软件定义网络架构中，位于控制平面的控制器（controller）不仅可以知道网络的拓扑结构、线路容量、往返时延等整体数据，也可以获得诸如端到端的流量、网络节点的加入和离开等实时性的信息。充分利用这些实时性的信息，实时性改变局部节点的路由策略，可以获得更优秀的路由效果。已经有一些采用智能算法优化路由关系的研究，但它们的应用大多并不广泛，而且没有结合深度强化学习。 本项目组基于DDPG算法开发出的路由优化算法可以接收网络产生的流量矩阵（即以特定节点对为起点和终点的流量分布），产生链路权重，通过链路权重计算出最佳路由，从而实时调整路由策略。 因此，本次毕设的目的就是通过网络流量矩阵调整链路权重，在控制平面生成新路由表，并改变转发层面的转发策略。使用此算法，用户可以通过训练程序内的神经网络使之产生更准确的链路信息，实现路由优化。并且可以根据网络的具体环境修改参数，来改变优化目标和链路信息的生成规则。1.2路由优化算法的设计1.2.1路由算法设计的分析 强化学习中智能体通过状态、动作，和奖励与环境交互，合理设置这些输入输出值以及它们与网络模型的关系，是将DRL引入网络路由优化最重要的事情。根据一系列相关深度强化学习路由优化的研究可知，传统意义上学术界常用的解决网络路由的方法是将某一时刻所有节点和通路的路由状态视为神经网络输入的状态，动作影响所有节点到其下一跳节点的路由选择，最后使用最短路径优先算法（ShortestPathFirst，SPF）得到每对源-目的节点之间的最短路径。对于每一状态——动作对，环境都根据下一时间段单个或多个网络状态指标决定反馈的奖励，这些指标可能包括时延、吞吐量、丢包率、带宽、拥塞水平等。在此可以对深度强化学习模型的诸要素作出限定。 （1）状态：状态应当是智能体所处环境的实时特征，否则难以反映网络需要。由于路由器一般以数据包的形式进行数据转发，通常使用业务流的传输状况指代整个网络的路由情况。可以定义所有数据包的集合为P，对每个通过网络传播的数据包pi而言，它在一个又一个的节点间的相互传播，可以简化为单位时间从di节点传输到dj节点的运动，到达dj后可以视为离开了网络。不妨假设网络节点总数为N，而且每个节点都可以转发信息而且将数据包传入传出网络，则所有源——目的节点对构成了一个N×N的方阵。可以将状态s定义为维度N×N的流量矩阵（TrafficMatrix,TM），其中每个元素dijs= （2）动作：动作是智能体每一时刻对网络发出的具体路由规定，它需要根据当前观察到的网络状态和策略做出。不同于传统的路由策略，基于概率的路由输出的动作给所有链路指定权重，然后根据最短路径优先计算出具体的路由表，根据链路权重可以唯一确定一个路由表。可以定义节点i到节点j的权重是wij，如果此节点有m个邻接节点，则可以组成一个权重向量Wi={wi1 （3）奖励：奖励的形式是强化学习的核心问题，网络根据智能体的指令做出行动之后，返还给智能体的评价指标，是当前状态对应当前动作的映射。它可以由很多网络指标组成，再依据现实需要加入一些超参数来调整不同指标的比例，比如如下公式2-6的情况。R它描述了在状态st的情况下发出动作at获得的奖励，其中ℎ(at)是一个函数，表明动作at产生作用的时间（包含转换网络权重，数据包重新开始发送的时间）。而α,β,γ∈[0,1]则分别是时延、带宽、丢包率的权重参数。TPij是节点 （4）策略：智能体的策略指导智能体在特定环境下的行为方式，是从当前状态到当前动作的映射。DDPG的Action模块应用了固定策略算法，策略网络会直接选择预期回报之和最大的动作，而不是输出概率分布，因此可以有效减少算法的计算量，提升收敛速度。为了引入随机性，一般会给动作加一个随机噪声。整体模型训练的伪代码大体可以写成如下形式： 1.随机初始化DDPG的决策网络μθ(s)和价值网络 2.设置相对于μθ(s)的贪婪策略π0 3.whilenotDone: 4.根据环境初始化状态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中随机抽取数据计算yt 13.根据公式2.1计算损失函数。 14.计算出∇ 15.用梯度下降法最小化损失函数，更新参数 16.ifk%n==0，更新目标网络参数 17.endfor 18.endwhile 以上算法中，第6到11行为正向采样的过程，第12到第16行为根据数据训练并更新模型参数的过程，其中第8行对网络环境进行了封装，省略了网络模型的创建部分。 以上状态空间、动作空间和策略的具体设计就是DRL路由优化网络的主要工作，和网络形态关系紧密，而且基本不需要补充额外的内容。处在知识平面上的DRL全局规划网络周期性地从控制平面接收网络的流量状态，然后输入内部的两个神经网络，得出下一步的链路信息并训练预测模型，再将计算后的链路信息通过控制平面下发给数据平面的每个路由器，展开新一轮的循环。1.2.2路由算法设计的实现 算法程序部分主要内容均使用Python完成，少部分重要参数写在JSON文件中。主要包括DDPG算法与环境的设置。参照通行的强化学习框架，设置为智能体和环境两个部分。 智能体部分分别构建了Actor模块和的Critic模块，它们分别在程序中对应AcotorNetwork类和CriticNetwork类。使用Keras构建主神经网络和目标神经网络，两个网络的结构是完全一致的。Actor网络有三个全连接层，输入层输入的是去掉对角线的路由矩阵（状态），由于网络采用的是14*14的无圈网络，输入长度为184个单位，信息的维度在三个全连接层之间逐渐收缩。第一个隐藏层有91个单元，第二个隐藏层收缩到了42个神经元，输出层输出21维链路权重向量（动作）。前两层的激活函数采用sigmoid函数，而输出层采用relu函数作为激活函数。Critic网络结合了强化学习的动作与状态，分别对应两个输入层，流量数据会经过两个全连接层，将维度降低到42，动作数据只经过一个全连接层，两者被加工成相等维度，进入一个融合层（Merge）汇合，再由两个全连接层得出对价值函数的价值。奖励采用网络的平均时延，可以根据参数改为最大时延或时延的中位数，是一个标量。为了以奖励最大化算法缩减时延，奖励的数值取负数。环境部分拟定了环境类OmnetBalancerEnv和OmnetLinkweightEnv作为和算法程序交互的环境，也起到联系仿真平台的作用。主函数定义环境实例，并在神经网络训练前初始化，迭代过程中不断接收主动作，并返回强化学习的状态、奖励和完成情况（done），同时将必要的信息存储到文件中。环境的主要参数如表3-1所示：参数名称具体说明ENV环境环境的名称ROUTING路由路由的格式folder文件夹存取文件的文件夹ACTIVE_NODES活动节点网络结点的数目graph拓扑图网络的拓扑图（采用networkx的图格式）a_dim动作维度强化学习动作对应的长度s_dim状态维度强化学习状态对应的长度tgen流量方阵流量矩阵（采用单独编写的Trafftic类）capacity容量网络的容量，即能正常传输的流量最大值之和env_T流量矩阵环境的流量矩阵（ndarray形式）env_W权重各条链路的权重env_R路由网络的路由表env_D时延各条链路的时延表3-1环境的参数环境类主要有两个方法，一个是环境初始化函数reset，一个是迭代函数step。reset函数会随机初始化链路权重，并生成一个流量矩阵，并转化成向量形式作为强化学习的状态返还给主函数，reset函数不需要参数。step函数在训练模型的每个循环内都会被调用一次，它接收Actor神经网络生成的权重，依据Dijkstra计算并存储最佳路由，并通过命令行启动OMNeT++程序，读取仿真数据并调用函数，生成对应的奖励。最后会把奖励、更新后的状态和是否完成传送到主函数。同时还包含一些转化函数负责各种职能。（1）读取文件：file_to_csv、ned_to_capacity等。（2）存储文件：vector_to_file等。（3）转换数据格式：matrix_to_rl、matrix_to_omnet_v、csv_to_matrix等。（4）最终输出内容：rl_state、rl_reward等。程序主函数是playGame，它负责接收参数、训练网络，并将将数据存储到特定文件夹中。函数流程如图所示：图3-1playGame的流程图1.3网络模型的设计与实现1.3.1网络模型的分析 本论文设计的基于深度强化学习的路由优化算法预期会运行在知识定义网络的知识平面，利用网络设备的编程接口API和控制层交互，自动化接收和分析网络传输的时延等网络指标。再把更新的链路权重以及其他控制信息发送给控制平面，控制平面的流量控制组件接收网络权重，再搜索出特定的链路数据信息转发给数据平面的路由器，路由器会根据链路权重更新路由表，决定转发方向。从而对网络上有限的资源进行优化，减少网络资源的浪费。根据软件定义网络编程的可扩展性，在不需要逐一配置每个交换设备的情况下，利用控制器提供的更新策略完成流量管理功能升级，智能地整合全网资源。一个路由器对应着多个端口，它的每个端口都对应着信息队列，如果一个数据包在队列里的时间过长，则会视为超时丢弃。路由器会读取路由优化算法计算出来的路由信息，然后依照特定的路由信息决定该把数据包发送到哪个信息队列中去。网络分组到达路由可以视为一个离散时间排队系统的问题，上级的交换机负责将数据包传送给下级的交换机，容量为一个单位。一般使用先入先出的准则，路由器需要提前为队列的队首分组安排一个下级交换机承接信息。所有分组到达下一个交换机后，继续进行新一轮分组，类似的路由和分组方法依次重复。网络中的应用不定期地产生数据在网络中相互传输，统计模块会将采集到的信息存储在相应的模块中（模拟程序里是存储到文件中）以备知识平面提取。定期获得全网拓扑已经流量状态等信息，监控网络层数，调节网络活动。总体而言控制平面包流量控制组件和信息采集组件，数据平面包括具体的网络节点和转发器（也包括路由器）。每经过一定时间，知识平面地路由优化算法就会读出网络数据进行优化，再将优化后的链路权重信息下发出去，进一步增强了网络管理的多样性和灵活性。1.3.2网络模型的实现网络仿真部分采用的仿真软件是OMNeT++，OMNeT++是一个应用广泛的离散事件仿真器，同时也是一个开源网络仿真平台，拥有较为完善的图形界面。本实验模拟了SDN网络的控制平面和数据平面，并完成了收集记录网络时延的功能。OMNeT++程序主要由ned程序和相对应的c++程序，以及负责初始化的ini文件和组装程序的makefile文件组成，网络的主体部分定义在包package中。本实验构建了一个14节点的全连通网络，网络的结构如图所示。图3-2网络的结构NetworkAll文件定义了网络节点和它们之间的通路。网络节点可以是服务器（server）也可以是负载均衡器（balancer），本实验的节点均为服务器。服务器内部结构如图3-3所示：图3-3server内部结构其中包含若干元件：（1）流量控制器（TrafficController）：从主程序中读取更新的流量矩阵并将流量数据发送给对应的应用。（2）应用（Application）：模拟网络中实际的应用，数量就是网络中的节点数，可以根据流量控制器传入的间隔，定期发送不定长的数据。本实验中数据长度采用指数分布，但最长不超过5000比特，实际操作也可以采用其他分布。每个Application对应一个目的节点，通过设置发送间隔来控制端口之间流量大小。（3）路由器：负责数据的转发和接收。如果此节点就是接受数据的目的节点则将数据接收，如果数据包的转发次数到达TTL则删除数据，视为丢包。如果处在中间节点则转发到对应端口。路由器通过读取主程序更新的路由表指导路由，内部没有算法模块。（4）端口队列（NodeQueue）：对应服务器的一个端口，数量和服务器的端口相等，负责数据队列的等待和管理。负责数据队列的加入和添加，对于待输出的数据包，如果数据等待时间过长则会删除掉，视为丢包。对从外部接收到的数据包则直接传给路由器，由路由器决定下一步的处理方式。仿真数据定义了控制消息ControlPacket、数据消息DataPacket、计时消息TimerNextPacket三种。流量控制器传输出控制消息提供流量强度信息，应用产生长度不等的数据消息来模拟显示网络中的数据包，计时消息用于计算时间，以便应用定期传出数据。结语路由是传统通信网络的核心功能之一，在网络需求和形式日趋多样化和复杂化的今天，一些新的应用场景需要新的路由策略。路由器本质上就是一种特殊的计算机，随着芯片技术的发展和路由器等网络硬件性能的不断提升，以及包括深度强化学习的各种人工智能技术的提升，基于深度强化学习的路由优化算法的出现成为了可能。在本论文中，我们实现了使用深度强化学习技术实现自动路由以及路由优化的程序。具有深度学习能力的智能硬件设备使用该算法尽可能压低传输时延，平均网络流量分布，提升网络的性能。经检验，基于DDPG的路由优化算法对路由时延和网络稳定性有较好的效果，尤其是在网络流量密集，网络负载大的地方更为突出。该训练方法可以适应不断变化的网络流量和链路模型，提升了强化学习对网络的不同状态的稳定性。在本实验中，我们发现深度强化学习应用于路由优化算法有相对于传统路由算法以及启发性路由优化有以下较为明显的优点：不依赖模型：深度强化学习只需要知道网络的状态和延迟即可更新数据，它可以通过和环境不断进行动态信息交互（比如动作、状态、奖励等）来提升自己的性能，对于有些算法并不需要对网络建模。而传统的路由优化算法大多数需要对网络模型进行详细的考察，还要加入一些特殊的条件和简化方式。更新频率高：传统的路由优化算法需要走很多步才会有一次更新，有时候只有接收方接收到包才能知道传输的时延。而基于深度强化学习的路由优化算法可以让网络节点在传播几步之内更新自己的数据，获得接近最优的路由配置。甚至通过适当的参数设定可以实现在一步之内实现近乎最优的网络配置更新。泛用性强：DRL算法驱动的网络节点不需要知道网络的整体形态，它们一般假定网络是一个黑盒而自动优化算法，对于不同的网络，只需要修改回报函数，不需要重新设计算法，即可获得不错的路由优化效果。这样就节约了大量网络建模的时间以及适配不同网络和硬件花费的时间和网络资源。参考文献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