【《基于拥塞预测的负载均衡路由算法分析》6100字】

V基于拥塞预测的负载均衡路由算法研究目录TOC\o"1-3"\h\u5554基于拥塞预测的负载均衡路由算法研究 1273391.1网络模型 2245621.2问题描述 3147411.2.1基本思想 3322771.2.2链路剩余带宽预测机制 416101.2.3链路拥塞预测的流量分配与约束 6201631.2.4流量路由模型 8275201.3基于链路拥塞预测的路由算法 998521.4仿真实验与结果分析 1199461.1.1仿真实验环境设置 1189531.1.2结果分析 11数据中心网络在运行中，网络运行环境与网络流量状态总是在不断发生改变，这也导致网络的服务质量（QualityofService，QoS）总是不断发生改变。当网络运行环境发生改变时，如何灵活调整和配置网络资源来应对网络状态变化满足用户的服务质量需求成为了一个极大的困难挑战。如何实现网络资源利用与路由调整收敛速度的平衡，在发生拥塞之前避免，这既能改善用户体验也有效防止网络性能恶化。随着通信网络的不断发展，流量工程成为解决上述困难的研究热点之一。本章基于软件定义网络中的流量工程问题，提出了基于拥塞预测的路由算法。流量工程通过不断的监测和分析过去和当前的网络状态，可以预测未来的网络流量状态，平衡网络流量分布，提高网络链路利用率，对网络流路由问题进行求解，实现网络负载均衡。1.1网络模型图1.1基于链路拥塞预测的网络模型如图1.1所示，本章对网络流的拥塞预测和网络负载均衡路由问题进行了研究。在特定的网络中，终端用户使用不同类型的应用程序，产生各类QoS要求的数据流量，同时网络运行环境也在不断的变化，网络由OF交换节点组成，网络流进行接入，到达边缘交换机，数据流进行链路拥塞预测和路由转发，SDN控制器具有全局视图，采集接入网数据流量的类型和相关路由参数以及网络中节点和链路的状态信息。为了描述网络拓扑，将该网络表示为无向连通图，其中V代表网络中的交换机集合，E代表网络中的链路集合，定义网络中有n个相互链接的OpenFlow交换机，表示网络的带宽矩阵，表示交换机i与交换机j之间的链路带宽。定义P表示网络中流的数量，矩阵表示每个流的路由矩阵。其中表示流f是否选择链路。考虑多个流量类别（本文考虑带宽与时延），使用表示流量需求矩阵，其中表示流f对应的带宽矩阵，表示流f对应的时延矩阵（流f的最大可允许延迟矩阵）。表示流f的实际消耗带宽，表示流f的预测消耗带宽。1.2问题描述随着移动互联网迅猛发展，大量应用不断涌现，网络中对不同流量类别有不同的要求，但用户对延迟敏感的业务体验要求越来越高。解决由于网络拥塞造成的传输延时增加问题以及由于流量状况随着空间和时间变化而造成的负载不均衡问题也是我们面临的挑战。网络流量的动态性和突发性使得静态资源分配方法变得毫无用处。在这种背景下，存在以下几个问题，如：利用网络的动态行为来实际地调整网络资源问题和利用SDN控制器的先验信息在保证QoS的前提下为当前流分配资源问题。针对链路产生的拥塞问题，大都是在拥塞发生之后才进行拥塞处理，没有很好的预测链路拥塞的可能性并进行流量调整。为了能够更合理地解决上述问题，本文提出一种基于拥塞预测的负载均衡路由算法，SDN中控制器利用在逻辑上集中控制的优势，感知网络负载，预测网络拥塞，更合理有效的进行流量分配，动态调节网络负载，从而保证无论网络状态如何变化，都能够充分利用网络资源，保证整个网络更好的性能，提升网络的吞吐量。1.2.1基本思想本章的基本思想是依据控制器实时监测交换机端口的吞吐量，当链路的剩余带宽超过一定阈值的时候，根据之前时间的流量传输速率与链路剩余带宽，预测链路发生拥塞的可能性，将此可能性作为权值加入到流量分配公式中，实时调节流量分配，来达到减缓以及预防网络拥塞的目的。其整个工作流程如图1.1所示。图1.1工作流程图1.2.2链路剩余带宽预测机制在网络流量传输之前，根据QoS要求（如时延，带宽等），寻找到符合要求的多条路径，并进行流量分配。但随着流量传输的进行，链路中的流量在不断增加，各链路与路径都有可能导致拥塞，产生丢包问题。因此需要周期性的测量交换机的吞吐率、计算链路的拥塞可能性，并适时更改流量的路径，以防止链路拥塞，减少数据包的丢失。SDN控制器实时监控各交换机的流量与各链路的剩余带宽情况，当某个交换机的吞吐率超过一定阈值（链路剩余带宽达到一定阈值），则开始计算当前路径的拥塞可能性，并将其作为权值，加入到控制器的流量分配中。为了防止网络中的“流量噪声”造成的流量抖动带来的极值影响，本章采用指数加权平均移动模型（ExponentiallyWeightedMoving-Average，EWMA）[33]，使得本章中的流量传输速度不会因为“流量噪声”的存在产生突变而影响预测结果，提升整个系统的鲁棒性与稳定性。其具体公式如下：（1.1）其中，N表示拓扑网络中交换机的个数，表示交换机i与交换机j之间的链路，表示滤波之后链路在t时刻的流量传输速率估计值。表示在t-1时刻的链路传输速率实际测量值。表示上一时刻链路传输速率估计值的可信度，其值越接近1，表示t-1时刻的测量值越可信（其是突变数据的可能性越低）。其决定了链路传输速率估计器估计实际数据发生变化的能力，即时效性。显而易见，随着其值的增大，估计器的时效性就越强，可信度就越高，随着的降低，表示实际数据的突变性越大，估计器的时效性越差。另一方面，正是由于的存在，该估计器才有了吸收突发数据的能力，增强数据的平稳性。在本章中，某段时间内端口的平均传输速率计算方法如下：（1.2）公式（1.2）中，表示链路在t-1到t时刻所传输的流量，表示t-1到t时刻的时间差。对于公式（1.1）中的可信度加权因子，采用Goldoni提出的十字过滤线（VerticalHorizontalFilter，VHF）方法[34]估计加权因子，对其进行实时修正，具体计算方式如下：（1.3）其中，表示最近观察到的m个带宽值中的最大值和最小值之间的差值，即样本的极差；为常数，是VHF的常数因子。m表示最近的带宽个数。根据上述公式，可以估算经过t时刻（即下一时刻t+1）后，链路的剩余带宽：（1.4）公式（1.4）中，表示链路的整体带宽。1.2.3链路拥塞预测的流量分配与约束（1）基于拥塞预测的流量分配按照当前预测的传输速率，可以估算链路造成拥塞的时间：（1.5）为保证各个链路的拥塞可能性的统一量纲处理，按照下式计算各个链路的拥塞可能性：（1.6）公式（1.6）中，表示链路阈值（即超过该阈值后，才有可能会发生拥塞），表示按照当前传输速率，传输完成阈值之后的剩余带宽需要的时间。值越小，则拥塞的可能性就越大。值越大，当前链路产生拥塞的可能性就越小。在流量传输之前，按照传统的QoS多路径路由方法，选取符合带宽与时延要求的n条路径。控制器按照以下方法计算各个路径的流量分配概率：（1.7）公式（1.7）中，表示整条路径p的最少剩余带宽，表示链路剩余带宽，表示链路时延，表示整条路径p的时延，表示当前链路的带宽。若当前路径中的各链路均未达到带宽阈值，则按照无阻塞权重的公式计算流量分配概率。若当前路径中存在链路达到阈值的情况，则按照1.2.2小节所述计算各链路的阻塞可能性，并选择该条路径中的最小权值。因为当前路径的拥塞情况由最可能拥塞的链路决定。本文中没有对带宽与时延最初优先级区分，若需要区分时延与带宽的优先级，如时延的敏感度超过带宽的敏感度，则公式（1.7）可以改写为：（1.8）以当前计算得到的流量分配概率，参与到控制器的流量分配中。本文使用OpenFlow组表技术中的select组表，将计算得到的流量分配概率应用到select组表中，将其作为动作桶的权值参与控制器的流量分配。为了进一步阐述多路径的流量分配过程，建立简单的数学模型进行模拟。假设两个主机之间存在n条可选路径，动作桶的权值为（即公式（1.8）计算的分配概率）。每当有新流量到来的时候，select组表在处理流量中的所有数据包时，会根据各路径的分配概率的不同，将需要转发的数据包散列所有可选路径中。假设流量中包含的数据包个数为Q，则每条可选路径所分配的数据包流量定义如下：（1.9）通过结合使用OpenFlow组表中的select组表和各个路径的流量分配概率，包含转发路径的OpenFlow交换机在每次流量转发的时候都可以实现数据包的按比例分配，从而实现了流量的均衡分配，缓解了流量拥塞现象，减少了数据包的丢失，达到了多路径负载均衡的目标。（2）链路负载约束网络中节点根据角色可以分为源节点、目的节点以及转发节点，流从源节点出发，经过转发节点，流向源节点。为保证流的有向性，建立约束1：（1.10）（1.11）对于当前流来说，若当前链路的剩余带宽不足以通过，则不会选择当前链路（或者选择当前链路，产生拥塞）。要满足经过某条链路的所有流不能大于该条链路的带宽利用率的条件，即约束2：（1.12）对于当前流与当前路径，当前路径的所有链路总时延不能大于当前流所允许的最大时延，即约束3：（1.13）对于网络链路矩阵而言，流对于某条链路只有两种选择结果：选中与未选中即约束4：（1.14）1.2.4流量路由模型对于流f来说，取预测消耗带宽与实际消耗带宽的最大值，即根据以上分析，以最大化带宽利用率为优化目标，建立以下路由模型（1.15）约束条件如上所述：（1.16）针对上述问题，本章提出基于链路拥塞预测的路由算法，对该问题的进行求解。1.3基于链路拥塞预测的路由算法在流量分配之初，链路剩余带宽没有超过阈值，不会进行拥塞预测，仅会按照公式（1.17）中优化目标最大的路径进行流量分配。当链路剩余带宽超过阈值的时候，将会进行拥塞预测。按照前述计算链路拥塞情况，并将结果带入优化目标中，进行路径选取，具体过程如下：表1.1基于拥塞预测的路由算法输入：数据流、网络拓扑图G（V，E）输出：网路带宽总利用率、路由路径1：For数据流中的第f个流Flowf：2：If路径中所有链路没有达到带宽阈值then3：寻找源节点到目的节点之间的可选路径4：For可选路径中的每条路径5：选择满足最小代价函数C1的路径作为候选路径，6：按照流量分配概率进行流Flowf的路径分配。7：8：更新网络的带宽矩阵与时延矩阵9：Endfor10：Endif11：If路径中存在到达带宽阈值的链路then12：预测链路拥塞可能性13：If可能产生拥塞或已经发生拥塞then14：更新链路代价函数15：16：按照流量分配概率进行流Flowf的路径分配。17：18：重新路由，更新流量分配策略19：Endif20：If拥塞缓解then21：更新链路代价函数22：23：重新路由，更新流量分配策略24：endif25：endif26：endfor通过上述算法，对所有的输入流，预测网络中的拥塞情况，并根据拥塞预测情况实时调整链路的代价函数与流量分配策略，降低链路拥塞的可能性，实现网络负载均衡，提高网络吞吐量。1.4仿真实验与结果分析1.1.1仿真实验环境设置本文的实验使用了mininet模拟器来构造网络拓扑图来模拟真实的网络环境，网络拓扑图采用了当前主流的数据中心拓扑模型FatTree模型，其中k=4，利用FatTree拓扑的主要原因是在任意两点之间存在着多条可用链路，除了标注的链路带宽，其余均为默认带宽1Gbps。该实验部分分别从丢包率、平均时延、网络吞吐量以及资源利用率四个方面进行对比，本文所使用的测量工具包括iperf以及ping命令，4个数据发送端和4个数据接收端。1.1.2结果分析首先，通过在发送端设置不同的发送端数量来测量该网络的丢包率，仿真结果如图1.4所示。图1.4丢包率对比图本实验中丢包率的测试均是在同一网络环境下进行的，对比的算法分为ECMP、WSP以及本章提出的算法。通过仿真结果可以看出：当数据流大小低于170MB/s时，3算法的表现相当;但是当发送端数据流大小大于170MB/s时，几种算法开始出现不同程度的丢包现象，相比其他几种算法，本章提出算法的丢包率基本不变，保持在一个相对较低的水平。通过分析实验结果：ECMP算法的丢包率存在一定的反复性；WSP在跳数最少的链路集合中选择带宽最大的传输路径；而ECMP算法作为一种等价路径传输机制，发送端传输路径的选择算法为哈希算法，当发送端数据流被分配到负载较大的链路时导致丢包率增加，当数据流被分配到负载较少的链路时，整个网络的丢包率会降低；本章所提出的算法依据链路拥塞情况及时调整不同的策略，相比于ECMP，WSP算法表现效果更优。本章所提出算法通过链路拥塞预测动态迁移数据流的方式缓解链路负载，从而降低网络的丢包率，相较于其他几种算法表现更优。图1.5吞吐量对比图该部分测量了各个算法在发送端不同数据流大小时的吞吐量大小，仿真实验结果如图1.5所示。从图1.5可以看出：当数据流速率小于180M/s时，各算法吞吐量基本相同，呈现出线性增加的趋势，随着发送端数量逐渐增加；当发送速率大于180M/s时，几种算法的吞吐量趋势差距逐渐明显，其中当数据流速率大于220M/s时，WSP算法的吞吐量达到饱和，这主要是由于WSP算法选择跳数最小的传输路径，但并没有考虑该传输路径的链路可用带宽大小;当数据流数速率大于240M/s时，ECMP算法出现一定的平稳趋势，但总体来看还是逐渐升高;本章算法比ECMP算法吞吐量更高，本章提出的算法则呈现出线性上升的变化趋势。主要原因在于，当发送端数量较少时，链路负载较小，各条数据流之间没有干扰，整个网络的吞吐量不会由于链路拥塞而发生变化;当发送端的数据流速率大于180M/s时，链路负载加重，由于链路发生拥塞导致吞吐量效果不佳。而本文提出的传输机制，充分考虑到了链路剩余带宽以及链路时延对整个网络吞吐量的影响，因此，相比较其他两种种算法，能够获得更高的吞吐量。图1.6链路利用率对比图最后，测量了各个算法的链路带宽的利用率，从图1.6中可以看出，随着数据流的增加，所有算法的链路带宽利用率都大体上呈现出逐步上升的趋势。当数据流速率在40~80时，ECMP和本文两种算法的链路利用率呈现出先下降后上升的趋势，这是由两种算法本身的性质所决定的：ECMP通过哈希的方式为每条数据流选择路径，在等数量大小的数据流前提下，由于所占链路带宽的总和变大，因此链路利用率相对较低;本文算法呈现出和ECMP算法大致相同的趋势是因为Hedera算法中使用ECMP算法处理老鼠流，在本实验中并没有严格区分大象流和老鼠流，因此二者的变化趋势整体上相似。同时，从实验