SDN中用于动态路由的ACOSDN算法*

丁怀宝

(安徽文达信息工程学院计算机工程学院 安徽合肥 231201)

随着网络技术的飞速发展和网络规模的持续增长，尤其是当下5G网络的普及、大数据、物联网和云计算等各种多媒体数据的发展，使得网络流量急剧增加，网络拥塞现象时有发生。

网络拥塞不仅是传统网络系统中的问题，而且可能会导致软件定义网络(software defined network，SDN)[1]的性能下降。SDN被认为是从传统网络到未来Internet的最重要的模式转变之一，它使网络管理员可以根据他们自己定义的路由规则控制网络流量转发。SDN的出现，为网络拥塞控制策略提供了新的思路。

文章提出了一种改进的蚁群优化(ACO)[2]算法，称为“ACOSDN”，用以优化SDN中的动态路由，以应对当前复杂的网络体系结构和网络流量激增情况的需求。最后通过仿真实验可知，该算法可以提升网络负载均衡性，减少链路拥塞发生，保障网络性能。

1 SDN和OpenFlow[3]

1.1 SDN架构

SDN体系结构由三层组成：应用层、控制层和转发层(又称数据层)，如图1所示。

应用层是SDN应用程序是通过北向接口向SDN控制器传达网络要求和所需网络行为的程序，包含着各种基于SDN的网络应用，用户无需关心底层细节就可以编程、部署新应用。

控制层是网络的核心，掌握着全局网络信息，负责各种转发规则的控制，它通过北向接口从应用程序平面接收指令，处理信息，然后通过南向接口(主流协议为OpenFlow)将其传输到转发层。

转发层，又称为数据层，由支持SDN的网络设备组成。

1.2 OpenFlow协议

OpenFlow(OF)协议是使网络设备维护一个FlowTable，并且只通过FlowTable对报文进行处理，FlowTable本身的生成、维护和下发完全由SDN控制器来实现。此外，OF交换机把传统网络中，完全由交换机/路由器控制的报文转换为由交换机和控制器来共同完成数据的转发操作，从而实现数据的转发与路由控制的分离。

OF交换机包含安全通道、多级流表和组表。安全通道可以将OF交换机和控制器建立基于OF协议的连接；流表则用来匹配OF交换机收到的报文；组表用来定义流表需要执行的动作。使用此协议，控制器可以添加，更新和删除流条目。OF组件如图2所示。

图1 SDN架构

图2 OpenFlow组件

2 SDN相关路由算法

Dijkstra算法[4]是1959由Dijkstra设计的，最早是用于有效解决图论中最短路径的问题经典算法，当前大部分SDN的现有路由算法通常使用Dijkstra算法。该算法虽然能计算出单条最短路径，缺点在于当搜索范围很广时，找到最佳路径所需的时间变得非常长，因此具有搜索效率差和搜索时间长的缺点。

ExtendedDijkstra算法[5]由JR Jiang等人在2014年提出的，是经典的Dijkstra算法的扩展。该算法对于导出最佳路由路径以将数据包从特定的源节点发送到另一个节点中的SDN环境非常有用，缺点是当数据包经过中间节点和边缘时会出现较大的延迟(或链接)。

蚁群优化(ant colony optimization，ACO)算法[6]最早是由Marco Dorigo等人在1991年提出的基于群体智能种群的元启发式算法。该算法优势在于：蚁群算法的路由机制比其他算法更稳定，丢包率和延迟都在可控范围内，为减少网络链路或节点阻塞提供了有效的方法。

异化蚂蚁算法(alienated ant algorithm，AAA)[7]是基于信息素踪迹的不同解释而引入的ACO衍生算法。该算法具有很强的分配能力，尤其是在高度动态的环境中。因此，它已经被积极地应用于SDN中。

A4SDN算法(adaptive alienated ant algorithm)[7]也是一种用于SDN的路由算法。该算法应用于要路由的数据包，可提供自主的动态路由，并导致对网络带宽的更好利用，强制执行尽力而为流量并提高网络性能。

3 ACO算法

ACO是一组由蚂蚁搜索食物和在路线上沉积信息素启发的组合优化算法。路径上的信息素含量影响蚂蚁的行为，信息素含量最大的路径代表巢与食物来源之间的最短路径。

ACO首先生成m个随机蚂蚁，并评估每个蚂蚁对应于目标函数的适应度，然后使用公式(1)更新每条可能的路径上的信息素浓度：

τij(t)=ρτij(t-1)+Δτij

(1)

其中i和j是节点，τij(t)是第t次迭代时与链路λij相关的信息素浓度，τij(t-1)是在第(t-1)次迭代时的信息素浓度；Δτij是信息素浓度的变化值；ρ是信息素蒸发(衰减)系数，其值从0到1不等，其中，此衰减值等于网络窗口大小的平均值。Δτij是迭代t时与λij相关的所有蚂蚁的贡献之和，可以使用公式(2)计算：

(2)

(3)

一旦信息素被更新，每个蚂蚁都必须根据公式(4)根据以下概率更新其路线，尊重信息素浓度和一些启发式偏好)：

(4)

其中pij(k,t)是蚂蚁k在第t次迭代时选择链路λij的概率；τij(t)是第t次迭代时与链路λij相关的信息素浓度；ηij是选择可用链接的启发式因素，同时也是是蚂蚁k选择链接λij的一个关键性指标。α和β是指数参数，分别指定跟踪和吸引力的影响，并取大于0的值。

4 ACOSDN算法

SDN的实施基于数据流的路由策略，而ACO路由算法刚好具有以基于流的方式工作的特点。因此，将ACO算法根据SDN架构进行改进，形成“ACOSDN算法”，用来优化SDN中的流量调度。ACOSDN算法通过以下三个并行的优化步骤来优化SDN路由。

Step1：ACOSDN使用Box-Covering[8]方法将SDN网络划分为一个个子网(或称为盒子)。这样可以优化搜索空间，并最大程度地减少数据包找到最佳路径所花费的时间。

Step2：ACOSDN使用非自然行为，迫使蚂蚁在所有可用路径上分配自己，而不是像传统ACO中那样收敛到单个路径，从而减少了网络拥塞。ACOSDN算法中的蚂蚁会根据路径上的信息素轨迹来确定要遵循的路径，但是，与其覆盖自然信息蚂蚁会形成的信息素轨迹更强的路径，而是探索信息素强度超过预定义阈值的路径,这样可以避免拥塞并使网络吞吐量最大化。

Step3：ACOSDN通过在OF管道中使用发现的最佳路径的条目创建一个新的匹配表并将该匹配表赋予第一优先级，从而使每个路由器花费的包匹配时间最小化，从而减少了在包匹配中花费的时间处理并最小化总延迟时间和丢包率,所提出的ACOSDN的伪代码如图3中所示。

图3 ACOSDN算法的伪代码

选择节点的概率取决于轮盘统计分布，如公式(5)所示：

(5)

其中τij(t)是节点i和节点j之间的信息素浓度，ηj(t)是节点j中启发式信息的值，为0.01，τik(t)是节点i和节点k之间信息素的浓度，其中k的值是从1到节点i的后继数量增加的值，ηk(t)是其启发式函数的当前值。

在所有路径上，局部信息素水平ρ值表示信息素衰减率，全局信息素水平α值表示在被更新或增加的最佳路径上，如公式(6)所示。

τij(t)=τij(t-1)+α

(6)

5 ACOSDN算法在SDN仿真实验中的实现

5.1 SDN仿真实验环境的部署

(1)阶段1：搭建SDN仿真环境。

在此阶段，将使用Ryu控制器在VMware Workstation虚拟机管理程序下使用Mininet来仿真SDN环境。ACOSDN算法在Ryu控制器的功能模块上实现，如图4所示。

图4 ACOSDN算法在SDN内部执行

(2)阶段2：网络发现和Box-Covering算法。

Ryu控制器中网络发现模块会自动调整网络拓扑结构，当每个数据包经过(数据包进入)后，此模块会更新网络拓扑，因此Ryu控制器动态地具有网络拓扑的完整映像。然后再利用Box-Covering算法(BCR)将复杂的大规模网络划分为一个个子网。

BCR算法的过程如图5所示。①假设需要找到从节点1到节点25的最短路径。网络被BCR算法分为六个子网。②每个子网被视为一个单独的节点(此时每个子网的大小明显大规模缩小)。如果在两个不同的子网中的两个节点之间有一条边，则这两个子网是相连的。③利用ACOSDN算法代替Dijkstra算法，找到节点1与节点4之间的最短路径。④计算每个子网中的最短路径，然后将最短路径连接在一起，得到从节点1到节点25的全局最短路径(红线)，这种修改最小化了寻找最佳路径所需的时间和分组往返时间(RTT)。

图5 BCR算法举例

(3)阶段3：ACOSDN算法实现。

在SDN部署和网络发现之后，路由过程再次由ACOSDN算法来执行。

(4)阶段4：转发。

在此阶段，通过搜索并选择在阶段3中实现的最佳路径来转发数据包。如果没有匹配发生，则通知控制器对该数据包采取新的操作(丢弃或滞留在管道表中)。

该实验主要从以下两个方面来考察ACOSDN的有效性。

(1)在网络拓扑动态变化的情况下测量ACOSDN的性能。

(2)将ACOSDN的性能与SDN中的文献相关算法和其他路由技术进行比较。

在SDN仿真实验环境中搭建如下网络拓扑图，如图6所示。将ACOSDN的性能与SDN中的文献相关算法和其他路由技术进行比较。

图6 仿真实验中的网络拓扑图

5.2 在网络拓扑动态变化的情况下考查ACOSDN的性能

在预定义的时间实例处，新增网络节点(S11)并且重新配置网络，使得创建两个新的链路(S1-S11和S11-S10)。ACOSDN成功处理了此动态更改，如表1所示，主机PC1和PC5之间的最佳路径是Sl-S11-S10，跃点数等于2。

表1 由ACOSDN算法得出的最佳路径

5.3 ACOSDN算法与SDN中的相关算法比较

将文章提出的ACOSDN算法与Dijkstra、Extended Dijkstra、AAA、A4SDN作为SDN中的其他路由算法进行了比较，分别从网络延迟、丢包率和吞吐量等三个网络性能指标进行比较。

(1)网络延迟。如图7所示，使用ACOSDN算法生成的延迟分别比Dijkstra、Extended Dijkstra、AAA、A4SDN算法生成的延迟少1.628 ms、1.008 ms、0.999 ms、0.898 ms。该结果是由于OF管道中新创建的匹配表而使ACOSDN能够进行快速数据包匹配的结果。

图7 延迟比较

(2)丢包率。如图8所示，在使用ACOSDN算法产生的分组丢失率分别比Dijkstra、Extended Dijkstra、AAA、A4SDN算法小2.161%、1.125%、1.005%、0.995%。该结果主要与ACOSDN算法能更好地管理拥塞，快速数据包匹配以及改进的Box-Covering方法有关。

图8 丢包率比较

(3)吞吐量。如图9所示，使用ACOSDN算法生成的吞吐量比分别比Dijkstra、Extended Dijkstra、AAA、A4SDN算法大1MB/s、0.66MB/s、0.59MB/s、0.446MB/s。该结果主要与ACOSDN实现最小延迟和丢包率有关。

图9 吞吐量比较

综上所述，ACOSDN算法能够处理网络配置中的路由动态变化，并针对延迟和丢包率实现可接受的网络吞吐量水平。另一方面，将ACOSDN与Dijkstra、Extended Dijkstra、AAA和A4SDN算法进行了比较，结果表明，在延迟、丢包率和吞吐量方面，ACOSDN优于其他三种相关路由算法。

6结语

文章提出了一种改进的蚂蚁优化算法ACOSDN，以优化SDN框架中的动态路由。ACOSDN将相关工作算法的所有功能组合为一种算法。它通过探索所有可用路径而不是收敛到单个最短路径来避免拥塞。整个网络分为逻辑子网。ACOSDN修改了所使用的Box-Covering方法，以优化搜索空间并最小化数据包找到其最佳路径所花费的时间，从而使ACOSDN比相关算法更快。

ACOSDN添加了一项新功能，即创建一个包含所有已发现路径的新表。这样可以将花费在每个路由器上的数据包匹配时间最小化，并将总延迟时间和数据包丢失率均最小化，从而将网络吞吐量最大化。未来，可以在大型SDN上，结合Box-Covering算法的功能，测试ACOSDN算法的性能。