【《基于大象流的负载均衡路由算法分析报告》7600字】

V基于大象流的负载均衡路由算法研究报告目录TOC\o"1-3"\h\u2812基于大象流的负载均衡路由算法研究报告 157611.1网络模型 2179841.2问题描述 3260591.2.1网络中流的定义 3188851.2.2大象流调度策略 4105491.2.3路由约束与路由模型 6120881.3大象流负载均衡算法设计 873981.3.1基于自适应阈值的大象流检测算法 8201391.3.2基于概率选择的重路由路径算法 869441.3.3自适应轮询周期调整算法 11230151.4仿真实验与结果分析 1253291.4.1仿真实验环境设置 1249301.4.2结果分析 13在网络环境越来越复杂的情况下，大流小流现象的存在为快速提升网络性能提供了一种有效的改善思路。现有的研究表明，数据中心网络中90%的流小于100KB（老鼠流），而10%的流则具有大量的数据（100KB到1GB）或更长的生存周期（大象流），它们产生超过80%的数据量。相比于小流，大象流更易于导致网络拥塞而影响到网络性能。考虑到大流和小流各有特点，其各自对应的调度算法也必然存在不同，如果采用相同的调度算法，其调度效果可能不显著，甚至导致网络性能恶化。为了有效提高整个网络的拥塞避免和数据高效传输能力，实现大象流的检测与链路负载均衡。本章提出了基于大象流的负载均衡路由算法。通过检测大象流的自适应阈值，并基于概率选择进行重路由以及设计自适应轮询周期，进一步提高网络性能，实现网络负载均衡。1.1网络模型图1.1网络架构图如图1.1所示，本章SDN网络架构主要有OpenFlow交换机与SDN控制器组成，其中，SDN控制器主要由以下几个模块组成：拓扑发现模块：控制器定期向交换机发送LLDP包以便搜集网络设备的链接信息。网络检测模块：定期收集交换机的接口数据以及流数据，以便获取整个网络的信息。阈值计算模块：根据拓扑发现模块以及网络检测模块收集到的链路状态信息，计算链路的平均剩余可用带宽，基于平均剩余可用带宽求出流分类的阈值，并且把该阈值发送给边缘层交换机，由边缘层交换机判定是否是大象流。大象流检测模块与重路由模块：如果存在拥塞的链路，则控制器将查找通过该链路的大象流，并将具有最大传输速率的大象流依次重新调度到新的拥塞最少的路径，直到消除该链路上的拥塞为止。大象流的新路径将根据基于概率的路径选择算法进行计算。拥塞检测模块：根据端口统计信息，控制器可以获取每个链路的负载。当链路的负载超过拥塞阈值时，该链路被标记为拥塞链路。在本文中拥塞阈值定义为链路容量的70％。轮询周期调整模块：控制器将会根据链路与流的状态，按照自适应轮询周期调整算法调整轮询周期。流表管理模块：一旦计算出流的转发路径，流表管理模块则以流表的形式在路径上的交换机中安装转发规则。当数据流进入交换机时，该交换机仅根据流表中的规则转发数据包即可。为验证本文的SDN的负载均衡算法啊，章节采用Fat-Tree拓扑，如图1.2所示。图1.2Fat-tree拓扑结构用图来表示Fat-Tree网络，其中V表示所有节点的集合，E表示所有链路的集合。表示任意两个源、目的主机节点。整个网络拓扑分为三层，从上到下依次为汇聚层、聚合层和边缘层。汇聚层和边缘层交换机构成一个Pod，用K表示网络中Pod的数量。假设，则与不同Pod相连的主机之间均有4条路径，并且每个边缘层交换机连接着两台主机，一共有16台主机，20个交换机，每个交换机均支持OpenFlow协议。每条链路可以传输的最大速率为其链路容量大小。对于给定的网络拓扑，用R表示源、目的节点间的所有路径的集合，表示第k条路径。表示链路上的流量，表示链路总容量。定义瓶颈链路为每条路径中具有最大带宽利用率的链路，用表示链路带宽利用率。(1.1)1.2问题描述1.2.1网络中流的定义在庞大的数据中心网络中，存在着两种数据流量，一种是生存时间短的老鼠流，一种是生存时间长的大象流，当有大量的大象流出现在数据中心网络中时网络会出现拥塞等现象，因此会对网络的性能产生影响，并且由于目前大数据以及云计算的不断发展和普及，使得用户对网络的需求逐渐提升，大象流对于网络的影响直接导致网络的传输速率，因此对于大象流的研究十分必要。在数据中心网络中存在多种流，并且每种流的生存时间均不相同，每条数据流所携带的信息量也均不相同，若数据流所携带的信息量越大，则表明数据流的生存时间越长，该数据流为大象流的可能性越大；经Benson等人研究发现约50%的数据流小于10KB，将这种小于10KB的流称之为老鼠流；而仅存在10%的数据流携带有大量的数据信息[36]，虽然这种数据流占比很小却占网络总流量的90%，同时生存时间也较长，将这种持续时间长并且携带数据量大的数据流量称之为大象流，由于大象流的生存时间较长，在端口处的排列中老鼠流总在大象流的后面，使得网络出现延时或者链路的拥塞等情况，为了使网络传输更为高效并同时减少控制器的负载，需要对流量进行集中化的控制处理，所以在数据中心网络中对于大象流的识别、数据流路径选择等对于网络性能来讲十分关键。数据中心网络存在大量交换机的同时也存在多条等价链路，常用的等价链路路由算法为ECMP算法，该算法可以充分利用网络中的带宽，并可以均衡分配网络中的流量，但是在数据中心网络中大象流的占比为10%，其余的为数据流较小的老鼠流，ECMP算法主要采用哈希算法对传输的数据流进行分配，因此当同一个路径上同时分配了两种类型的数据流，就可能会导致链路的拥塞[37]，因此在进行流量传输前就必须要清楚分辨流量类型，然后根据不同数据流类型选择不同的路由方式；ECMP算法对于老鼠流来说能够很好地进行等价路径的路由，但对于大象流不仅不能很好地实现等价多路径，还会带来额外的网络资源浪费；在大象流与老鼠流之间除了携带信息量不同以外，这些流量对于带宽的需求量也不相同，大象流具有较高的带宽需求，老鼠流因为携带的信息量少因此对时延很敏感。当在老鼠流和大象流同时存在的情况下会首先传输老鼠流，而大象流因为携带的信息量大可能会占满交换机上的缓存区，老鼠流传输延迟较长，因此必须对老鼠流与大象流分开转发并制定不同的转发路径1.2.2大象流调度策略目前对于大象流的调度思路主要存在两种：a)利用SDN全局网络视图和动态规则配置能力，对大象流进行动态调度，选择无冲突路径，避免大流冲突；b)将大象流分解成多个子流，多路径传输。表1.1大象流调度策略对比方案检测大象流位置多路径转发方案Hedera控制器对大象流重路由，采用全局优先匹配算法计算路径Mahout终端大象流重路由，采用increasingfirstfit算法TinyFlow控制器大象流分解成子流，再采用ECMP算法路由SMFS终端对部分大象流利用SR进行重路由，并采用全局优先匹配算法计算路径EFLB终端设置网络负载阈值，将大象流分解成子流，选择负载最小的下一跳Hedera[38]首次将SDN技术应用到数据中心网络中的流量管理中，他认为大流是导致网络拥塞的主要原因，提出动态地调度大流，以提高网络吞吐量。Hedera界定大流的标准是一条流的传输带宽大于链路带宽的10%，则认为是大流。通常情况下，Hedera采用ECMP路由算法，同时周期性地检测网络中的大流和链路的负载情况，确定需要重新调度的大流，并估计大流的带宽需求，计算出合适的传输路径，完成对大象流动态调度。但由于Hedera中大象流和网络状态的检测是周期性的，会导致控制粒度过粗，不够精细，不能保障网络中的突发状况。同时，在大象流的路径选择上，Hedera采用的是全局优先匹配(GFF)算法，该算法在所有可用路径中选择第一个符合带宽需求的路径，具有一定的局限性，精确度较低，无法保证转发路径为最优路径Mahout[36]同样结合了SDN的集中控制方式，对大流进行精细路由。Mahout是在终端主机上对大象流进行检测并标记，被标记的大流由increasingfirstfit算法计算转发路径，在多条可用路径中选择负载最少的路径进行传输，没有被标记的流则采用静态的ECMP算法进行路由。相比于Hedera，Mahout可以更快地检测到大象流，且减少了控制器的开销。Mahout在路径选择上更加精细，相对来说算法复杂性也有所提高，并且还需要在终端主机上设置检测大象流的算法，故Mahout算法的实现比较复杂。TinyFlow[39]很好地解决了ECMP中不区分大小流的问题。TinyFlow将大象流分解成老鼠流，并将其随机均匀地分布在所有路径上，即在仅有老鼠流的网络中采用ECMP算法进行数据流传输，避免了大流路由碰撞的缺陷。文献[40]提出基于SDN的大象流负载均衡机制EFLB，该机制也是一种有选择地对大象流进行调度的方法。EFLB以轮询方式监听网络，当网络负载超过阈值时，控制器将检测到的大象流分解成多个老鼠流，并利用SDN控制器的全局网络视图，计算出负载最小的下一跳交换机。实验结果表明，EFLB机制相比ECMP，提高了网络吞吐量和链路利用率，更好地实现了网络负载均衡。根据大象流的特性，无论是为大象流选择可用带宽大的无冲突路径，还是将大象流分解成多个子流再传输，或设置网络负载阈值，有选择地对大流调度，这些方法均提高了网络吞吐量，使网络性能得到改善。然而对于大象流的调度还存在以下难点：在网络比较繁忙时，可能会选择不到适合大象流传输的最优路径。将大象流分解成多个子流，并在不同的路径上进行传输，但不同路径的性能存在差异，比如丢包率和延迟的不同，这些会造成数据包的乱序，数据包的重新排序会增加接收端的占用内存和CPU利用率，既增加了传输开销，也造成了额外的延迟;其次，大象流分解的数目也是一个难点，理想情况下子流的数目越多，越可以避免网络拥塞的发生，但是子流的数目过多会造成维护费用和资源消耗的骤增，子流的数目太少，会达不到大象流分解的效果，不能避免大流的碰撞问题。1.2.3路由约束与路由模型通过SDN控制器获取网络节点和链路状态信息，结合节点流表资源以及链路带宽资源使用情况，本小节对网络流路由约束进行阐述。SDN控制器具有网络能力感知功能，收集网络节点处的流表资源使用、链路带宽资源占用、链路时延和丢包率等参数，定义节点v处前一时刻流表使用量为，链路l前一时刻带宽使用量为，定义网络流经过节点v时占用的流表资源为。定义路径是网络流自源节点（即接入节点）至目的节点的可达路由路径，集合R是网络流自源节点至目的节点的可达路径集合,。定义二进制变量，描述OF节点是否在路径上；定义二进制变量，描述链路是否在路径上；定义二进制变量，描述路径是否被网络流使用；定义节点v处的单位流表开销为，链路上的单位带宽开销为。另外，考虑到交换机容量限制以及链路传输能力，分别定义节点处流表容量上限和链路容量上限。建立如下约束：（1）链路负载约束网络流使用路径p进行转发时，经过的每条回程链路都应符合带宽资源容量约束，即已使用带宽与网络流即将占用带宽资源之和不超过链路l的带宽容量上限（1.2）（2）流表容量约束当网络流在回程网络中使用路径p进行转发，网络流经过节点时均需要满足该节点处流表资源容量的约束，即经过节点的网络流对流表资源的占用不应超过该节点流表资源的容量上限，否则会在该节点处发生流表溢出现象，因此需要满足流表容量约束：（1.3）网络流在路由过程中经过链路产生的带宽资源开销为：（1.4）网络流经过节点产生的流表资源开销为：（1.5）综上，以网络流路由中的带宽和流表资源开销之和为优化目标，考虑链路负载和流表流量等约束，建立优化模型如下：（1.6）1.3大象流负载均衡算法设计为实现大象流的检测与链路负载均衡，本文提出了基于自适应阈值的大象流检测算法、基于概率选择的重路由路径算法以及自适应轮询周期算法。1.3.1基于自适应阈值的大象流检测算法通过设定阈值的方法检测大象流，一般设置阈值为总带宽的1%左右。但是这种设置方法无法根据网络的状态实时调整。在网络状态好的时候，100M可能才能作为大象流，但是网络状态不好时，10M的流都可能作为大象流。因此，本章节根据网络的链路状态，动态调整阈值，方法如下所示：（1.7）其中，N表示所有链路总数，表示链路l的带宽利用率，表示链路l的带宽，Th表示大流检测的阈值。根据链路的平均剩余可用带宽来计算大流检测的阈值的好处是，平均剩余可用带宽可以反映网络负载的高低。平均剩余可用带宽越多说明网络负载越轻，阈值应该设置的比较大，因为有足够的带宽来传输更多的流量；反之负载越重，相应的阈值应该设置的较小，以避免链路拥塞[41]。1.3.2基于概率选择的重路由路径算法为了平衡网络负载和减少带宽碎片[42]，我们提出了一种基于概率的路径选择算法来计算大象流的最小拥塞路径。为了提高网络的吞吐量，在大象流进行重路由的时候，本章节采用大象流的传输速率而不是带宽作为评估参数[43]。图1.3示意图如图1.3所示，假设源节点与目的节点之间存在4条路径（A、B、C、D），大象流的带宽需求是30M，本应该在A路径进行传输，但是因为A路径拥塞（或者即将拥塞）导致带宽容量仅为10M，因此需要对进行重路由。此时B、C、D三条路径的剩余带宽为11M，15M，25M，均不满足大象流的传输需求。因此大象流将会继续沿着路径A进行传输。但是如果按照大象流的传输速率进行重路由，则将会选择传输速率最快的路径D，传输速率达到25M，远高于现路径A的10M，因此整体来看，网络的吞吐量肯定会有所提升。假设大象流重路由后存在K条路径，本文以大象流的传输速率以及每条路径的剩余带宽比值作为每条路径的权重，即：（1.8）式中，l表示第l条路径，表示大象流的传输速率，表示链路l的带宽利用率，表示链路l的带宽。定义每条路径的选中概率为：（1.9）由此可见，当路径的剩余带宽与大象流的涮熟速率接近的时候，每条路径的权重越大，概率越高。为防止某条路径为重复选择，导致链路拥塞。采用如下算法：在候选K条路径中随机选择路径。定义为前l条路径的概率总和，表示0到1之间的一个随机数，当某条路径满足以下关系的时候，则选择该条路径：（1.10）本章算法的伪代码如下表所示：表1.1基于概率的路径选择算法基于概率的路径选择算法输入：大象流F输出：新的路径Path获取源节点与目的节点的所有路径pathsForpaths中的所有路径pathIfpath的剩余带宽大于大象流F的传输速率then将path加入到候选路径队列candidate中EndifEndforfor候选路径队列candidate中的所有路径path计算路径的权重weightEndfor计算所有候选路径的权重之和sumWeight产生一个0-1之间的随机数random，以及sump＝０for候选路径队列candidate中的所有路径path计算每个路径的概率Psump＝sump+pifsump＞randomthenresult=pathEndifEndforReturnresult1.3.3自适应轮询周期调整算法为了检测象流并保持网络的正确负载信息，控制器需要定期从交换机收集网络统计信息。然后，控制器可以获得网络的全局视图，并动态地重新调度象流以避免网络拥塞。具体来说，轮询周期不仅决定流检测的准确性和网络统计的正确性，而且还决定控制器的消息开销。然而，在大多数现有的方法中，控制器查询具有固定轮询周期的交换机。如果轮询周期较长，控制器收集到的网络统计信息就不能及时更新，从而降低了象流检测的准确性，并可能导致某些路径上的持续拥塞。如果轮询周期很短，则会增加控制器的消息开销，因为控制器需要频繁地查询交换机[44]。为了在控制器的消息开销和网络统计的正确性之间进行权衡，本章节采用了动态轮询周期，并提出了一种自适应轮询周期调整算法，该算法可以根据网络负载动态调整轮询周期。当网络稳定且大部分链路负载较轻时，控制器不必频繁地查询交换机，因为这种情况下发生网络拥塞的可能性很低。因此，控制器将设置更大的轮询周期，以减少查询交换机的频率，并相应地节省消息开销。当网络繁忙，某些链路发生拥塞时，控制器会设置较小的轮询周期，以便及时更新网络统计信息，快速消除网络拥塞。定义网络的平均链路利用率如下：（1.11）但是为了防止某些链路拥塞而整体平均利用率较低的情况，并且充分测量网络的负载并检查某些链路是否拥塞，我们定义了如下总负载（1.12）公式（1.12）中，表示网络中的链路最高利利用率，表示链路平均利用率，分别表示两个参数的权重系数，且，其值分别为0.7、0.3。根据网络负载情况，按照下式计算轮询周期：（1.13）其中，表示基础轮询周期，一般设置为5秒。因为上式是递减函数，随着网络负载的变大，轮询周期变短。为了防止无限大与无限小的存在，给周期T设置上下限。本算法的伪代码如下表所示：表1.2自适应轮询周期调整算法自适应轮询周期调整算法输入：网络拓扑，输出：轮询周期T获取所有链路的链路利用率情况If多个（5个）链路利用率超过阈值Endif计算网络负载计算轮询周期IfthenEndififthenEndifReturnT1.4仿真实验与结果分析1.4.1仿真实验环境设置本实验在较为稳定的Ubuntu16.04系统上搭建，并选择在轻量级网络仿真工具Mininet上进行模拟，控制器使用开源的Ryu控制器，对于实验拓扑采用K=4的胖树DCN拓扑，链路带宽设置为100Mbit/s，由于Fat-Tree架构可以采用一般商业的交换机来构建，因此网络链路的带宽能够保持一致。仿真使用2种数据中心常用的流量模式：1)Random：每台主机等概率地向其他主机发送数据。2)StaggeredProb(EdgeP，PodP)：主机以概率EdgeP发送到同一边缘交换机中的另一个主机，称为机柜流量。以概率PodP发送到其相同的pod且不在同一边缘交换机的主机，即pod内流量。以概率1-EdgeP-PodP发送到网络的其余部分，即pod间流量。1.4.2结果分析本文从平均吞吐率、平均流完成时间(FCT)和链路利用率这3个角度比较了本章算法、Hedera和ECMP这3种策略，以验证本章算法的优越性。如图1.1所示，在EdgeP较低时，即网络内有较多的pod内流和pod间流时，DPMS、Hedera和ECMP这3种策略的吞吐率差距较大。因为在pod内流和pod间流多的情境下，ECMP无法根据链路拥塞状态动态地分配链路资源，大象流的碰撞率增大。Hedera区分大象流和老鼠流，动态对大象流进行调度，所以效果比ECM