基于SDN 的多目标路径优化算法研究

潘晓君

(安徽工商职业学院信息工程学院，安徽合肥 231131)

0 引言

软件定义网络（Software Defined Networking，SDN）[1]通过分离控制平面与数据平面，将控制权移到软件控制器中，把复杂性操作从硬件中移开，致使硬件只需关注转发流量，更加趋于简单化，使得传统网络在满足当今复杂需求方面的局限性问题能够得到很好解决.

随着网络中应用程序的不断更替，程序的业务需求也越来越趋于多元化，这就要求集中控制平面需要在较短时间内完成对不同数据流量需求的路径计算.因此，针对SDN 网络中快速有效的路径优化方案的研究就显得尤为重要.

1 多目标路由优化框架

多目标优化问题的通常解决方法是找到一组称为Pareto 最优集的最优折中解[2].Pareto 最优集是对于每个不同目标都具有独立支配能力的解，且不会被其它解所支配.在SDN中，当网络的交换机收到一条新的数据流时，会首先检查自身已有的数据流表，对该数据流进行逐项匹配.若没有匹配项，就将数据流以Packet_in 消息的形式发往控制器，控制器对数据流的处理方式会依据最短路径算法进行运算，并将运算结果以Packet_out 消息的形式下发到路径中的所有交换机中[3].但这种路由策略没有将网络拓扑中相关的链路资源（如网络链路剩余带宽、链路时延、链路丢包率）考虑其中，在网络中数据流量较大时，这种路由方法较容易形成网络的拥塞[4].

由于多目标路径优化算法会依据链路资源信息进行路由决策，因此在设计路由策略时，要求控制器能够实时获取网络中的相关资源信息，包括网络拓扑结构信息、网络链路资源信息、交换机节点个数等.

多目标路径优化框架如图1所示，控制器利用Hello、Packet_in、Packet_out、Flow Stats 等模块与交换机进行数据交互.

图1 多目标路径优化框架

2 多目标路径优化算法设计

多目标路径优化算法流程如图2所示，主要包括种群数量、初始化链路资源、多目标函数确定、选择操作、交叉及变异操作.下面将对流程图中的每个操作内容做详细介绍.

图2 多目标路径优化算法流程

2.1 链路资源信息概述

将收集到的链路信息及网络拓扑信息转换成一个具有m个节点h条连接的无向图G(V，E)[5-6].其中V表示网络中节点，E为被检测到的链路，且有|V|=m，|E|=h.对于备选路径，遗传算法中的染色体则可以表示为一个三维组合(X，Link，Y)，其中X代表的是源主机，Y代表的是目的主机，Link则为从源主机到目的主机间的不重复路径的链路集合，即Link={l1,l2,…,lt}(1 ≤t≤h).

具体参数介绍说明如下：

（1）网络链路带宽biq：链路带宽为网络拓扑初始化值；

（2）网络链路剩余带宽alq：当网络数据流确定其转发的路径后，控制器则会下发转发流表至交换机，交换机节点间的链路剩余带宽是由网络中的监控模块进行计算得出，一般情况下，链路的剩余带宽越大，则此条链路被选中的概率越高；

掌握公司设备技术状况及配置情况，负责设备按拆施工，根据生产实际情况制定维修计划，对设备实施维修，确保生产能力和产品质量要求，做好设备事故分析，做好处理和上报工作，负责建立设备技术资料档案，完善各种设备资料，定期对设备开展大检查，排查不安全因素和隐患，并提出整改意见，参与设备更新、改型等工作。

（3）网络链路带宽利用率ulq：表示被选路径发生拥塞的可能性，它由链路总带宽及链路剩余带宽共同表示，其表达式为

（4）链路时延dlq：在SDN 网络中，控制器发送地址为mac地址的广播数据包；

（5）链路丢包率plle：该参数在网络资源信息初始化时设置，依据每条链路上的资源信息可计算得出对于一条被选路径上的总资源信息.

路径剩余带宽的表达式为

路径剩余带宽的表达式为

路径总时延为

路径总丢包率为

2.2 多目标函数的约束

要实现多目标路径的优化功能，首先是要进行多目标函数的确立.确定多目标函数，主要考虑被选路径上的总时延、剩余总带宽、总丢包率等参数.依据式（1）、（3）、（4）可确定多目标路径优化算法中的目标函数分别为

这里Link为被选路径，适应度函数值越大，则被选路径越容易产生其后代，所以采用的目标函数为路径既要链路上剩余带宽较大、又要确保链路时延及数据丢包率较小.

多目标优化算法中需要确定网络拥挤度算子，这需要对上面三个目标函数进行归一化操作，这里面使用消除量纲影响最简易的操作即离差标准化[7].具体运算公式如下：

3 实验环境与结果分析

3.1 实验环境

为验证本文提出的多目标路径优化算法的性能，这里在SDN 上进行仿真实验.在软件定义网络中，多目标路径优化算法中的网络信息主要包括节点与链路资源信息.为实现多目标路径优化，该算法中的network_monitor（网络监听）模块需要每经过一定的单位时间t1进行一次监听.如果监听到网络中数据流所需带宽超过目前路径中的链路带宽阈值或数据链路利用率较高时，network_configu⁃ration（网络配置）模块便开始进行一次新的多目标路径优化操作.首先利用链路发现协议来识别网络中的所有转发路径，通过染色体编码方案生成初始种群，然后运用多目标函数来寻找第一代子代个体，接着进行非支配选择、交叉与变异操作产生新的子代，并将上一代与这一代合并来获取最优个体.为了维护网络状态的多目标最佳路径，反复使用算法进行重路由.

实验环境所用参数如表1所示.

表1 实验环境参数表

3.2 实验结果与分析

3.2.1 吞吐量

为了反应多目标路径优化算法的性能，将该算法与最短路径算法[8]在网络数据吞吐量、数据链路利用率、平均时延及数据丢包率等参数进行比较.

本文的多目标路径优化算法与最短路径算法数据转发后的链路吞吐量对如图3所示.当客户端发送速率逐步增大时，可以有效的降低网络发送拥塞的概率，网络丢包的情况也随之减少，进而提高了数据链路的吞吐量.

图3 吞吐量比较

3.2.2 链路利用率

平均链路利用率对比结果如图4所示，最短路径算法根据路径中交换机节点数最少进行选路，导致客户端发送速率逐渐增大时其链路利用率依然较小且变化不大.与最短路径相比，多目标路径优化算法平均链路利用率有所提高.

图4 链路利用率比较

3.2.3 平均时延

随着客户端数据发送速率的不断增大，两种路由算法的平均时延的变化如图5所示.相对于最短路径算法，本文的多目标路径优化算法的时延增幅明显小于它.最短路径算法由于没有考虑链路剩余带宽大小与数据流所需带宽大小之间的关系，从而导致流量发送速率较大时的转发时延变化较大，网络发送拥塞的概率增大.

图5 平均时延比较

3.2.4 丢包率

图6 显示的为多目标路径优化算法与最短路径算法在不同发送速率下的数据丢包率的情况.最短路径算法在数据流量较小时，它的网络丢包率较小，但当数据流量较大时，若将所有流量按最短路径进行转发，非常容易形成数据链路资源的短缺，进而导致网络的拥塞，网络数据的丢包率也随之加快.

图6 丢包率比较

4 结语

由于SDN 网络是基于跳数的最短路径转发策略，当有大数据流量情况下，这种策略非常的不灵活，极易形成网络的拥塞，进而影响网络的服务质量.依据SDN 网络的结构特点，在控制器中添加多目标路由优化模块，通过多目标路由优化算法选出最佳的转发路径.实验结果表明，与传统的最短路径路由算法相比，本文提出的多目标路由优化算法在数据吞吐量、通信链路利用率、链路时延以及数据丢包率等性能方面均具有较好的提升，使网络发生拥塞的概率大幅降低，为SDN 网络的进一步研究，提供了一定的技术支持.