端到端时延下网络多路径负载均衡算法仿真_苏富林.pdf

基金项目:国家民委 2021 年度高等教育教学改革研究项目(21102)收稿日期:20220216第 40 卷第 2 期计算机仿真2023 年 2 月文章编号:10069348(2023)02042905端到端时延下网络多路径负载均衡算法仿真苏富林1，冯桂莲2(1 甘肃民族师范学院计算机科学系，甘肃 合作 747000;2 青海民族大学物理与电子信息工程学院，青海 西宁 810007)摘要:为了提高网络的通讯性能，降低网络能量消耗，提出基于蚁群优化的网络多路径负载均衡算法。通过路由模块确定转发路径，在大象流检测模块中检测网络中存在的大象流，构建大象流调度目标函数，利用网络监听模块监听各节点在网络中的实时信息。根据获取的信息采用蚁群优化算法调度网络中存在的大象流，通过路由模块、大象流检测模块、网络监听模块和计算决策模块构成网络多路径负载均衡机制，完成网络多路径的负载均衡。仿真结果表明，所提算法的端到端时延短、网络能量消耗小、分组丢失率低和网络生命周期长。关键词:蚁群优化算法;大象流检测;网络多路径传输;网络监听;负载均衡中图分类号:TP393文献标识码:BSimulation of Network Multipath Load BalancingAlgorithm with End to End DelaySU Fulin1，FENG Guilian2(1 Department of Computer Science，Gansu Normal College for Nationalities，Hezuo Gansu 747000，China;2 School of Physics and Electronic Information Engineering，Qinghai Nationalities University，Xining Qinghai 810007，China)ABSTACT:In order to improve the communication performance of the network and reduce energy consumption，amultipath load balancing algorithm for the network based on ant colony optimization was proposed Firstly，the for-warding path was determined by a routing module And then，the elephant flow in the network was detected by the ele-phant flow module Meanwhile，the elephant flow scheduling objective function was constructed，and the network sniff-ing module was used to monitor the realtime information of each node in the network According to the information，the ant colony optimization algorithm was adopted to schedule the elephant flow existing in the network Finally，themultipath load balancing mechanism was formed through the routing module，elephant flow detection module，networksniffing module and calculation decision module Thus，the multipath load balancing of the network was completedSimulation results show that the proposed algorithm has short endtoend delay，low network energy consumption，lowpacket loss rate and long network life cycleKEYWODS:Ant colony optimization algorithm;Elephant flow detection;Network multipath transmission;Networkmonitoring;Load balancing1引言传感器节点通常由多个部分组成，其主要负责数据的传输与接收、节点供电和数据处理等工作1，传感器节点在网络中所占的空间较小，其电源供应能力、计算能力等都会受到约束，为了降低网络能耗、延长网络寿命，需要保证节点之间数据稳定、可靠地传输2，在此背景下，研究网络多路径负载均衡算法具有重要意义。许红亮3 等人通过蜘蛛猴算法根据路径信息计算链路空闲率，并将其作为路径在网络中的适应度值，根据计算结果评估路径，并对路径更新，将链路占用率最小作为指标选取最优转发路径，实现网络多路径负载均衡。该算法的端到端时延较长，且数据传输过程中的分组丢失率较高。吕翊4 924等人根据网络前端结构特点构建路径选取模型，计算路径差分延迟和数据传输延迟，在粒子群优化算法的基础上通过多级惩罚函数分配网络负载，实现负载均衡，该算法的节点平均能耗较高，存在网络能量消耗高的问题。李锐5 等人根据节点特性，计算节点在网络中的移动状态概率和剩余能量，将链路质量最优作为目标，根据上述计算结果选取最优路径，实现负载均衡，该算法的存活节点数量较少，网络生命周期短。为了解决上述算法中存在的问题，提出基于蚁群优化的网络多路径负载均衡算法。2网络多路径负载均衡算法基于蚁群优化的网络多路径负载均衡算法主要在 Floo-dlinght 控制器中通过路由模块、大象流检测模块、网络监听模块和计算决策模块实现网络多路径负载均衡，如图 1所示。图 1网络多路径负载均衡机制2.1路由模块数据中心网络中的流可以分为大象流和老鼠流，通过路由模块区分网络中的大象流和老鼠流，确定转发路径，并在哈希散列的基础上通过 ECMP 算法6 调度老鼠流，在决策模块中完成网络大象流的调度。2.2大象流检测标记网络中存在的大象流是调度的首要步骤，在大象流检测过程中，用 F=f1，f2，fx 表示链路中存在的大象流，可通过下式判断网络中存在的数据流是否为大象流fxxi=1fi tth(1)式中，tth代表的是数据流平均大小的倍数。根据节点在网络中构成的集合 V=v1，v2，vn 以及链路构成的集合 L 组建图 G(V，L)，用于表示网络的拓扑结构。设 ul代表的是链路利用率，其计算公式如下ul=fFxflnfCl(2)式中，xfl 0，1 主要用于描述链路 l 中是否流过大象流 f;nf代表的是大象流 f 对应的带宽;Cl代表的是链路 l 对应的容量。根据上式计算结果，通过下式确定网络的最大链路利用率 umaxumax=max ul(3)设置集合 Li，该集合中包含的链路主要负责向节点 vi中传输数据流，同时设置集合 Li，该集合中包含的链路主要负责传送节点 vi中存在的数据流，可用下述函数描述大象流在网络中的调度问题minumaxstfFxflnf Cll LlLixflnflLixflnf=nfvi=vfs，f Fnfvi=vfd，f F0vi V vfs，vfdxfl 0，1 l L，f F(4)式中，vfd描述的是数据流传输的终点;vfs描述的是发送数据流的源点。2.3网络监听模块网络监听模块的主要任务是监听各节点在网络中的实时信息。1)链路延迟:设 tdij代表的是单线链路在网络中的延迟，其计算公式如下tdij=taij tsijvi+vj2(5)式中，vi代表的是控制器将数据传输到 OpenFlow 交换机 vi所需的时间;taij代表的是控制器传输探测报文的时间;vj代表的是控制器将数据传输到 OpenFlow 交换机 vj所需的时间;tsij代表的是控制器接收探测报文的时间。2)链路负载均衡度7，8，用 n 表示节点在网络中的数量，设 ZB(t)代表的是链路在当前网络中的负载均衡程度，可通过下式计算得到ZB(t)=ni=1nj=1 lcij(ni=1nj=1lcij)/m2(6)式中，lcij代表的是链路(i，j)在网络中的带宽;m 描述的是网络中链路的实际数量。3)网络流接收率 GA(t)GA(t)=gs(t)/gc(t)(7)式中，gc(t)代表的是总共发送的数据流;gs(t)代表的是接收到的数据流。4)网络带宽占用率 BPBP=1 (ni=1nj=1lcij)/(ni=1nj=1lpij)(8)式中，lpij代表的是链路在初始时刻的最大带宽容量。5)网络吞吐量 Y，描述的是网络拓扑在网络流时间无034限长的情况下能够发送成功的最大流数目9，其计算公式如下Y=limtgs(t)(9)2.4计算决策模块2.4.1兴趣扩散经调查发现，由于大象流中包含了大量的数据，因此，在传输过程中容易造成网络拥塞现象，在计算决策模块中通过蚁群优化算法10，11 合理地调度大象流，避免网络出现拥塞现象，实现多路径的负载均衡。目的节点 vd在网络中周期性地传送兴趣消息，兴趣消息包可以采集节点在网络中的剩余能量信息，通过格式interest=(type，interval，rect，timestamp，expiresat，energy)表示，将 energy 域增加到网络多路径负载均衡算法中，其主要目的是表示节点在网络中的剩余能量。将邻居节点 vi内存在的兴趣消息存储到节点 vj对应的梯度表中，邻居节点 vi的剩余能量均记录在兴趣消息中，在梯度表中添加启发因子ji，启发因子 ji可通过下式计算得到ji=ridji(10)式中，dji代表的是节点 j 和节点 i 在网络中的路径距离;ri代表的是节点 i 在网络中的剩余能量。根据节点剩余能量完成兴趣消息中 energy 域的更新，消息包完成更新后通过链路传输到网络的邻居节点中，停止传播兴趣消息的条件是兴趣信息经过多个节点最终传输到源节点中。2.4.2多路径建立在源节点中，M 只蚂蚁获取探测数据包，并将其传输到下一个节点中，用 probe=(type，instance，location，intensity，confidence，timestamp，minband，minenergy)描述源节点中存在的探测数据包。为了记录传输路径对应的带宽瓶颈和能量瓶颈，在探测数据包中设置 minband 域和 minenergy 域，minband 域和 minenergy 域在网络中的初始化处理可通过源节点完成，处理时需要利用邻居节点在网络中的带宽以及源节点自身存储的能量，在下述规则的基础上使蚂蚁自身携带的探测数据包传输到网络的任意中继节点 vi中:1)判断蚂蚁在前进过程中是否经过该节点，若经过该节点，终止前进;若没有经过该节点，判断下一个目的节点与当前节点之间的距离，选择距离较近的节点作为蚂蚁访问的节点12，13。2)获取链路带宽 bij和节点 vi的能量 ri，针对探测数据包中 存 在 的 minenergy 域 和 minband 域，通 过 min(ri，minenergy)、min(bij，minband)完成更新。3)当邻居节点在网络中无法传输探测数据包时，返回上一步重新选择可以传输探测数据包的邻居节点。4)当梯度表中存在的邻居节点在网络中都无法传输探测数据包时，节点 vi需要重新设置一个梯度表，删除原始的梯度表，新设置的梯度表中不包含目前获取的探测数据包内存在的信息。根据上述过程，在网络中获得用于数据传输的多条路径。2.4.3路径加强与负载均衡根据前向蚂蚁建立的传输路径，后向蚂蚁可以