推荐星级：
- 1
- 2
- 3
- 4
- 5
SDN中基于遗传机制的自适应路由算法研究
资料介绍
SDN以集中式的控制、可编程的接口等优点,极大地提高了网络的管控效率及操作的灵活性。但在SDN部署运行中,也暴露出传输时延大、丢包率高等缺点。针对这些问题,提出了一种基于遗传算法的自适应SDN路由算法,该算法利用遗传算法在SDN的全局网络视图中搜索优化路径。算法设计时,对交叉、变异操作进行条件约束,避免产生无效的路径,减小求解空间,降低控制器计算开销。同时能根据网络的动态变化,自适应地选择转发路径。通过Mininet仿真平台进行实验,与其他算法相比,该算法降低了网络的时延以及丢包率,提高了网络性能。
部分文件列表
| 文件名 | 大小 |
| SDN中基于遗传机制的自适应路由算法研究.pdf | 2M |
部分页面预览
（完整内容请下载后查看）86
2019，55（2）
Computer Engineering and Applications计算机工程与应用
SDN中基于遗传机制的自适应路由算法研究
周飞杰，张坤丽，王国卿，庄 雷
郑州大学 信息工程学院，郑州 450001
摘
要：SDN以集中式的控制、可编程的接口等优点，极大地提高了网络的管控效率及操作的灵活性。但在SDN部
署运行中，也暴露出传输时延大、丢包率高等缺点。针对这些问题，提出了一种基于遗传算法的自适应SDN路由算
法，该算法利用遗传算法在SDN的全局网络视图中搜索优化路径。算法设计时，对交叉、变异操作进行条件约束，避
免产生无效的路径，减小求解空间，降低控制器计算开销。同时能根据网络的动态变化，自适应地选择转发路径。
通过Mininet仿真平台进行实验，与其他算法相比，该算法降低了网络的时延以及丢包率，提高了网络性能。
关键词：软件定义网络（SDN）；传输时延；丢包率；遗传算法；路由算法
文献标志码：A 中图分类号：TP39 doi：10.3778/j.issn.1002-8331.1710-0289
周飞杰，张坤丽，王国卿，等.SDN中基于遗传机制的自适应路由算法研究.计算机工程与应用，2019，55（2）：86-91.
ZHOU Feijie, ZHANG Kunli, WANG Guoqing, et al. Research of adaptive SDN routing algorithm based on genetic mecha-
nism. Computer Engineering and Applications, 2019, 55（2）：86-91.
Research of Adaptive SDN Routing Algorithm Based on Genetic Mechanism
ZHOU Feijie, ZHANG Kunli, WANG Guoqing, ZHUANG Lei
College of Information Engineering, Zhengzhou University, Zhengzhou 450001, China
Abstract：With the advantages of centralized control and programmable interface, SDN greatly improves the control effi-
ciency and operation flexibility of the network. However, in the deployment and operation of SDN, the high transmission
delay, high packet loss rate and other shortcomings are also exposed. To solve these problems, an Adaptive SDN Routing
Algorithm based on Genetic Algorithm（ASRAGA）is proposed, which uses genetic algorithm in the global view of SDN
to search the optimized path. By constraining the crossover and mutation operation in the design, it can avoid the invalid
path, reduce the search space scale and the computational overhead of the controller. The ASRAGA adjusts the packet for-
warding path by the state of network adaptively. Compared with other algorithms, ASRAGA can improve the network per-
formance and reduce the packet loss rate and network delay on the Mininet simulation platform.
Key words：Software Defined Network（SDN）； transmission delay； packet loss rate； genetic algorithm； routing algorithm
结构中含有 Match Field（匹配字段），对交换机所接收
到数据的包头内容进行匹配，并根据匹配的结果完成相
应的动作，摆脱了对协议的依赖，避免了设计出新的协
1 引言
[1-2]
软件定义网络（Software Defined Network，SDN）
作为一种新型网络架构，具有可编程、操作简单、集中控
制、不依赖协议等特点，从诞生便受到很高的关注。采
用SDN网络架构，网络管理变得更加高效，可编程的接
口使得网络操作更加灵活，能满足不同用户的不同需
求。SDN 主流通信协议是 OpenFlow[3-4]，在协议的流表
议导致现有芯片不支持或开发新芯片带来的开销[5-6]
在SDN中进行网络路由时，控制器通过接收OpenvSwitch
上报的packet-in消息启动处理流程，控制器计算转发路
径，并通过 OpenFlow 下发给转发器，打通链路，实现主
。
基金项目：国家自然科学基金（No.61379079）；河南省科技厅科技攻关项目（No.172102210478）；河南省科技厅国际合作项目
（No.152102410021）。
作者简介：周飞杰（1992—），男，硕士研究生，研究领域为软件定义网络，E-mail：；张坤丽（1977—），女，博士
研究生，讲师，研究领域为人工智能方向；王国卿（1989—），男，博士研究生，研究领域为软件工程；庄雷（1963—），女，
博士，教授，研究领域为网络虚拟化、下一代互联网。
收稿日期：2017-10-30
修回日期：2017-12-15
文章编号：1002-8331（2019）02-0086-06
CNKI网络出版：2018-04-09, http://kns.cnki.net/kcms/detail/11.2127.TP.20180409.1529.028.html
周飞杰，等：SDN中基于遗传机制的自适应路由算法研究
2019，55（2）
87
机间的互通。与 SDN 相比，传统网络为每一台途经的
设备进行配置，需要人为规划整个网络的拓扑、端口IP、
路由协议等，这个过程是繁琐耗时的[7]。另外，SDN 采
用集中控制的方式对全局网络视图进行网络管控，与传
统分布式的网络相比更能实现流量均衡。但SDN带来
诸多便利的同时，仍然存在传输时延大、丢包率高的问
题，这些问题的产生大多与网络路由算法的性能相关，
许多专家学者在SDN路由算法方面进行了研究。
该算法利用遗传算法建模对 SDN 的拓扑结构建模，通
过设计的适应度函数来衡量染色体所对应转发路径的
优劣，限制交叉和变异操作的对象，避免了产生无效解，
又能根据网络的动态变化，自适应地选择优化的转发路
径。最后进行了仿真对比实验，结果表明本文算法与其
他算法相比具有降低时延和丢包率的特性。
3 ASRAGA建模
遗传算法是一种模拟自然选择和遗传机制的搜索
最优解的计算模型，采用概率化的寻优方法，能自动获
2 相关研究
取和指导优化的搜索空间，自适应地调整搜索方向[12-14]
，
在 SDN 路由算法研究方面，主要集中于多路径路
由算法，可分为两种类型：无类路由算法和自适应路由
算法。无类路由算法在进行决策时不考虑当前网络状
态，如文献[8]提到的最短路径算法、等价多路径路由算
法（Equal-Cost Multi-Path，ECMP）等，ECMP 算法为任
一源和目的相同的主机提供了多条路径，基于流的数量
平均分配流量，在一定程度上提高了系统吞吐量，但未
考虑链路状态动态变化。在流量较大时，这会导致两种
情况的产生，大数据流分配在同一链路上，造成网络拥
塞，拥塞的结果便是时延增大，出现丢包；小数据流被分
配在大数据流之后时，增大了小数据流的时延。而自适
应路由算法在对数据包进行路由决策时，会根据当前的
网络状态动态地调整数据包转发路径。如文献[8]提出
了负载均衡多路径路由算法，能够在胖树拓扑结构中很
好地分发流量负载和充分利用有效的带宽，但其缺点是
未对不同的业务流进行分类处理，这就会导致需要及时
响应的业务流传输时延很大，不能保证良好的服务质
量，并且丢包率偏高。文献[9]提出了一种基于多路径
传 输 的 动 态 路 由 算 法（Dynamic Routing Algorithm
based on Multipath Propagation，DRAMP），该算法在重
新定义链路关键度并求解链路权值优化问题的基础上，
完成路由优化的目的，但该算法并不能很好地保证服务
质量，增加计算消耗，且不能充分利用剩余带宽。文
献[10]提出了一种SDN中基于博弈的混合路由算法，在
保证流量均衡的前提下，采用少量的显示路由和基于目
的的聚合流配置，优化网络的平均端到端的时延，但存
在系统吞吐量低、以及不能充分利用网络的带宽资源的
缺点。文献[11]提出了两个算法：其中一个是全局优先
匹配，该算法仅仅选择所有备选路径中第一个满足条件
的作为转发路径，这就需要获得所有节点间对间的路径
信息，但不能动态地考虑路径的参数信息，也未实现多
路径，难以保证性能最佳。另一个使用模拟退火算法，
该算法使用概率性搜索方法，确定最优路径，算法执行
速度快，但有时收敛速度很慢，造成算法性能不够稳定。
针对上述的时延和丢包率问题，本文提出了基于遗传
算法的自适应的 SDN 路由算法（Adaptive SDN Routing
Algorithm based on Genetic Algorithm，ASRAGA）。
并具有很好的全局寻优能力。这恰好能与采用集中式
控制 SDN 结合一起，为数据流的转发寻找全局范围优
化链路。但采用传统的遗传算法会产生无效的链路，因
此在算法设计时，对遗传算法中的交叉和变异运算进行
条件约束，仅染色体对有公共节点的进行交叉操作，这
样有效地避免交叉运算后，产生的染色体无对应的链
路，进一步缩小了优化解的搜索空间，节省计算时间。
对于变异操作同样也进行限制，避免无效路径产生，同
时把剩余带宽、节点可信度以及数据堆积率当作计算变
异概率的参数，使变异的结果总是向着优化解的方向发
展，进而提升了算法的执行速度。
在本章中，主要对 SDN 中的物理节点采用遗传算
法建立计算模型，其中有节点编码、种群初始化、适应度
函数设计、选择操作、交叉操作及变异操作，并包含与网
络性能相关的参数计算方法、评估转发路径优劣的适应
度函数、选择概率计算方法等，以下分别进行介绍。
3.1 拓扑节点编码
遗传算法的运算对象是表示个体符号串，所以需要
对网络中的物理节点进行编码，即对网络的拓扑中的交
换机节点、终端节点及控制器节点进行编码。遗传算法
常用的编码方式有二进制编码和字符编码两种，两种编
码方式有各自的优点。二进制编码的优点在于稳定性
高，但存储空间大，解码过程复杂。而字符编码容易理
解且不需要解码，所以本文选用字符编码，用于直观地
表示编码代表的物理节点。终端节点、交换节点、控制
节点分别采用 hn、sn、cn 编码，其中下标 n 表示所属节点
类别下的编号。如图1网络拓扑编码样例所示，对拓扑
中的物理节点进行字符编码，加上染色体对应的有向
边，就构成一张有向图 G（V,E）,V 表示节点集，即 V =
{c1,h1,h2,s1,s2,s3,s4,s5},E 表示网络拓扑的有向边集合，
每条链路可对应到遗传算法中的一条染色体。
3.2 初始化种群
根据网络拓扑，采用深度优先搜索算法（DFS）产生
第一代种群。对于每一个主机节点 hi 调用一次DFS算
法，生成 hi 到其他所有节点的路径，源节点到目的节点
用相应的节点编号序列表示一条染色体，用符号 ems,d,n 表
全部评论(0)