英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
基于ACO的SDN链路负载均衡算法
王春芝，张刚，徐辉，陈宏伟
Abstract-Software Defined Networking是一种新颖的网络架构，它通过OpenFlow分离数据平面和控制平面，具有集中控制获取和分配全球网络资源的特点。 因此，SDN的链路负载均衡并不像传统网络那样困难。 本文提出了一种基于蚁群优化（LLBACO）的链路负载均衡算法。 该算法利用ACO的搜索规则，将链路负载，时延和丢包作为蚂蚁选择下一节点的影响因子。 为了保持链路负载均衡并减少端到端传输延迟，蚂蚁可以获得所有路径中最宽和最短的路径。 仿真结果表明，与现有算法相比，LLBACO可以有效平衡网络链路负载，提高服务质量（QoS），降低网络开销。
关键词 - 软件定义网络，ACO，链路负载平衡，QoS。
介绍
软件定义网络[1]具有集中控制，开放接口和网络虚拟化等特点，突破了传统网络的诸多局限，成为当前业界关注的焦点，在数据中心，广域网等领域得到广泛应用。 B4 [2]，一个连接全球Google数据中心的专用广域网由SDN转变。 这是一个非常成功的大规模SDN商用案例，将链路带宽利用率从30％〜40％提高到接近100％。B4的成功吸引了更多的企业加入SDN的浪潮。随着云计算和大数据的兴起，越来越多的数据需要在网络中传输和处理。不同的业务需求造成各个环节的负载差异很大，出现了局部负载不均衡的现象。因此，链路负载均衡策略的实施对保证网络运行的稳定性是必不可少的。
现有的 OpenFlow 控制器系统提供了简单的完成数据流转发的模块，如 FloodLight 中的路由算法使用 Dijstra 算法通过计算源节点到目的节点的最短跳数，来规划路径控制数据流的转发． 前 k 条最短路径( KSP，top-k shortest path distance) 算法的目的是寻找起点到终点的多条路径，形成最短路径组，以满足对路径的需求［9］，KSP 算法是 Dijkstra 算法的延伸，k 值越大，最短路径组规模越大，算法的复杂度也越高，当 k = 1 时，退化为 Dijkstra 算法［10］．当网络拓扑比较简单或以找到路径为目标时，k 最短路径有较好的效果． 而当网络拓扑较复杂，求解目标为全局的负载均衡度时，由于 KSP 算法路径选择多样性差． 随着网络流的增加，链路负载不均衡性越来越严重，进而造成网络流丢包率和延迟上升以及吞吐量下降等网络性能问题． 为此，以提高网络链路均衡和流传输质量为目标，设计了针对网络流的路径分配策略． 蚁群优化算法在寻路问题上应用广泛，同时其自组织性和正反馈性也使得算法具有环境适应能力强、收敛性佳的优点． 将蚁群算法用于控制器的路径选择，利用其群体智能性来规划路径，可提高网络链路的负载均衡度和流传输质量．
蚁群优化（Ant Colony Optimization，ACO）是一种新兴的启发式算法，它具有分布式计算，信息正反馈和启发式搜索等优点，已广泛应用于NoC系统负载均衡[3]，Bin包装问题[4]，Job 车间调度[5]，路由问题[6]等。在解决路由问题的过程中，所有蚂蚁都会搜索新路径并收集现有路径的状态。如果蚂蚁成功地搜寻目的地，那么它们将沿着原始路径返回到源。根据当前路径更新所有节点的路由表后，蚁群可以完成路径搜索的任务。
多约束路由是一个NP完全问题[7]。 为了简化问题，控制平面中的LLBACO充分利用了蚁群搜索路径，以链路负载为主要因素的机制，延迟和包丢失是次要因素。因此，该算法可以保证服务尽可能在最广泛和最短的路径上流转。
其余的论文组织如下。第2节展示了一些解决负载平衡问题的现有方法。 我们在第3节提供了我们的链接平衡框架。在第4节中，详细描述了LLBACO。 第5节分析了模拟结果。 第六部分结束了我们的研究。
相关工作
Plug-n-Server [8]是由斯坦福大学研究人员提出的基于OpenFlow的网络负载平衡系统。系统中的控制器有三个模块：网络管理器模块，主机管理器模块和流量管理器模块。 网络管理员收集有关拓扑和链路利用率的信息。主机管理器监视每个服务器的状态和负载。流管理器是一个OpenFlow控制器，它使用负载平衡算法管理和路由流。该系统对SDN负载均衡的研究具有较强的指导意义。
LABERIO [9]是OpenFlow网络中的动态负载均衡路由算法。当负载检测器发现网络负载的数值超过了算法预设的阈值时，控制器会将高负载链路中的数据流分配给其他链路。但是，当控制器收到新请求时，该算法必须计算两个节点之间的所有路径。这个过程在复杂的网络中非常耗时。2015年，Li-Der将遗传算法[10]应用于OpenFlow网络中的负载平衡问题。他们首先预设交换机中的流表。一旦流量爆发或负载突然在服务器上增加，该算法将平衡链路和服务器的负载。遗传算法的使用可以节省网络成本，避免单个控制器的瓶颈。 Dijkstra是解决最短路径问题的经典算法。 FSEM [11]是一种基于SDN的路径负载均衡解决方案。它使用Top-K算法来选择最短的Top-K路径。然后，在Top-K路径中选择一条具有模糊综合评估方法的最佳路径。该方案提高了整体网络的性能，但Top-K算法仅考虑跳数，这可能会排除一些更好的路径。
链路负载平衡框架
本文所提出的链路负载平衡系统旨在平衡每个链路的负载并避免拥塞。我们的链路负载平衡解决方案框架如图1所示。它由控制平面和数据平面组成。OpenFlow是两个平面的接口标准。然后，将详细介绍平面和处理流程的过程。
A.控制平面
控制平面可以控制数据平面中的所有设备作为软件定义网络的大脑。为了实现链路负载均衡，我们的系统主要在控制器中定义以下四个模块。
1）监视模块
SFlow是传统网络中使用的网络监控应用程序。但是，OpenFlow有许多元组，SFlow只能通过采样来关注其中一个域。当网络异常时，SFlow无法及时发现故障。监控模块使网络管理员获得可见性。同时，管理者可以决定要监视的流向。。
2）数据收集模块
数据采集模块能够通过南向接口支持的OpenFlow的上行通道统计，存储和分析来自数据层的信息。这有利于发现网络中的问题，并及时制定相应的策略。
负载均衡模块
集中控制是SDN最重要的特性之一，该模块明显体现了这一特点。无论何时Packet-In消息从交换机到达控制器，负载均衡模块都可以根据其他模块的数据计算到达目的地的最佳路径。 LLBACO会部署在此模块中，具体将在下面进行介绍。
4）负载均衡模块
流量表是控制器通知交换机如何处理数据包的工具。控制器制定转发策略后，流量控制模块通过打包名为Flow-mod的消息向交换机发送新的流表。
B.数据平面
SDN的数据平面主要集中在快速转发功能上。因此，与传统网络相比，其复杂性较低。控制器通过OpenFlow协议对设备进行统一控制和管理，实现底层设备的虚拟化。
C.数据流处理
数据流进入数据平面时，入口处的交换机接收数据包并解析数据包头。匹配从第一个流程表开始。流条目按优先级顺序匹配数据包。如果匹配成功，则将执行与特定流条目相关联的指令。
如果匹配无效，交换机会将数据包放入缓存中，并将Packet-In消息发送到控制器，来决定如何处理数据包。
数据平面将数据流沿着由负载平衡模块计算的路径传输到目标主机。
LINK负载平衡ACO SDN
A.下一个节点选择策略
在蚁群算法中，轮盘赌是所有蚂蚁选择下一个站点的方法。如图2所示，节点1上的蚂蚁选择节点2和节点3的概率分别为P（1,2）和P（1,3）。 P（i，j）的方程如下给出。
参数alpha;，beta;和gamma;表示每个因素的相对影响，allowSet是蚂蚁可以选择的一组节点，是链路（i，j）上的信息素强度， = 1/ ，= 1 / ，是链路（i，j）的负载，是链路（i，j）的传输成本。 当蚂蚁选择下一个节点时，它们都是影响因素。然后被描述为：
=delta;* (1-delta;) 0lt;delta;lt;1 (2)
其中是延迟，是链路（i，j）上的包丢失。
B.信息素更新策略
蚂蚁抵达目的地后，会以相同的方式释放信息素。信息素总是随着时间蒸发，这个过程被称为信息素更新。在这个算法中，信息素更新的方法是全局更新，蚂蚁在所有的蚂蚁完成任务后，仅仅将信息素留在最佳路径上。 信息素更新定义为：
=（1-rho;）* ∆ （3）
其中
∆是信息素的数量，它由蚂蚁留在节点i和j之间。Rho; ϵ（0,1），它代表信息素挥发的速度，Q是信息素的总量，L是最佳路径的长度。信息素是蚂蚁相互沟通的媒介，直接影响蚂蚁搜索路径的效率。
C.计算最佳路径
LLBACO将平衡链路负载并确保网络服务的质量。因此，选择最佳路径负载，延迟和封装损耗。在一个复杂的网络中，低负载路径可能有较高的延迟和丢包。为了获得最佳路径，我们的算法设置动态阈值并排除那些路径，其负载值超过阈值。然后，在剩余路径中选择最小成本路径。
1）计算路径负载和成本
图3显示了一条路径，其中三条链路的带宽相等，红线的高度表示链路负载，列的长度表示链路成本。显然，路径负载是最大链路负载，路径成本是所有链路成本的总和。等式如下。
2）计算阈值并更新pathlistk
pathlistk是第k次迭代中的一组路径。 在计算阈值之后，可以通过去除负载值大于的一些路径来获得新路径列表k。
3）获得最佳路径
如公式8所示，最佳路径是新pathlistk中的最小成本路径。
- 算法描述
LB-ACO 算法以网络拓扑的负载均衡度为适应度函数，对源节点每次到达的流进行路径选择，蚂蚁的路径优化选择即为确定流由源地址到目的地址的最佳路径算法步骤如下．
步骤 1 初始化网络拓扑和流事件． 网络拓扑节点数为 N，链路数为 L，链路带宽最大值和最小值分别为 Lmax和 Lmin，流事件单流数为 X，多流数为 Y，到来的泊松分布参数为 lambda;，流持续的寿命分布参数为 gamma;，每条流的源地址为 S，目的地址为 D．
步骤 2 初始化蚁群算法参数． 蚂蚁规模为 A，蚂蚁初始位置为 L，网络拓扑初始信息素为 tau;，最大寻找次数为 Fmax，算法迭代数为 I．
步骤 3 对到来的流事件使用蚁群算法，蚂蚁根据状态转移式( 5) ，选择下一个节点．
步骤 4 判断选择的节点是否在 D 中，若是则将源节点到此节点的路径存储在路径序列 Ｒ 中; 否则判断寻找次数是否小于 Fmax，是则选择下一个节点，否则执行步骤 6．
步骤 5 根据式( 1) ，选择最合适的路径，根据式( 6) 和式( 7) 更新信息素．
步骤 6 检查迭代数，如果小于 I，执行步骤 3，否则执行步骤 7．
步骤 7 输出本次流事件路径，更新网络拓扑负载．
LLBACO的输入是给定的图G（V，E）。 每个蚂蚁根据公式1搜索路径。该算法使用PathList来存储从源节点src到目的节点dst的路径。 在蚁群完成搜索之后，公式8可以计算当前最佳路径，该路径被追加到名为BestPathList的列表中。 信息素也将被等式3更新，然后蚁群开始下一个搜索。 最后，我们可以在BestPathList中获得最佳路径。
SIMULATIONS和结果分析
A.实验方法
我们的算法的优点是它不仅可以平衡链路负载，还可以提高QoS。 因此，实验将LLBACO与基于负载均衡的ACO（LBACO）[12]和循环（RR）相比较，以链路负载和传输成本的标准偏差进行比较。 当链路负载和传输成本的标准偏差较小时，负载均衡和QoS的影响较好。 链路负载的标准偏差定义如下。
B.实验结果
仿真使用图4所示的网络拓扑结构，它由6个节点和10个边组成。 我们在50M〜100M之间注入了随机数的流量，注入总量为200次。 我们记录了注入流量后的网络负载和成本。 表1是来自仿真的数据。
从图5中可以看出，Round Robin在整个过程中具有最大的链路负载标准差，LBACO和LLBACO有一个小的差别。 但是，LBACO是一种算法，专注于负载平衡并忽略延迟和丢包。 所以图5说明了所提出的算法在平衡链路负载方面具有良好的性能。
然后，我们可以比较图6中的总传输成本。与LBACO和RR相比，LLBACO使用的网络具有较低的传输成本。 在我们的仿真中进行了200次流量注入之后，与LBACO和RR相比，我们的算法可以降低30％和45％的传输成本。
我们提取延迟和丢包作为参考数据来表达LLBACO在提高QoS方面的性能。 如图7和图8所示，LLBACO和LBACO在初始阶段具有相似的性能。 然而，随着网络负载的增加，LLBACO的延迟稳定在8ms，包丢失率为0.1％。 但LBACO的延迟和丢包有剧烈的波动，这对QoS有严重影响。
在本文中，我们详细介
全文共8216字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11722]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
