朱国晖，牛皎月，王丹妮
(西安邮电大学 通信与信息工程学院，陕西 西安 710121)
随着云计算和大数据相关技术的快速发展，互联网业务量呈爆炸式增长。传统的网络结构及其所运用的传输控制协议/互联网协议(Transmission Control Protocol/Internet Protocol,TCP/IP)，越来越难以有效地处理海量数据流和根据不同的业务对网络中的资源进行灵活调度。因此，研究新型网络体系结构满足用户需求是非常有必要的。对更强大和高效的网络体系结构的需求促使了软件定义网络(Software Define Network,SDN)体系结构的发展，其核心思想是将转发平面和控制平面分离[1]，利用其集中式架构的特性实现网络的高效管理，只需对控制器进行程序设计即可实现数据转发。
SDN在带来诸多便利的同时，也存在带宽利用率低、丢包率高等问题，此问题大多与SDN路由算法的性能有关。因此，为数据流量制定高效又合理的路由成为众多研究者的关注点。文献[2]针对SDN数据中心网络提出了一种联合-路由服务器负载均衡算法，可在流量负荷较高时实现网络资源全局调度，提高网络吞吐量，降低网络延迟。但是，该算法在网络资源利用率方面稍有欠缺，且易受到初始种群状态影响。文献[3]提出了一种基于遗传机制的自适应路由算法，对遗传算法中的变异、交叉操作进行约束，避免产生无效路径，降低了控制器的计算开销，提高了算法效率。但是，在适应度函数设计时，选用的指标皆为与链路状态相关的因素，对路径层面的影响因素考虑不足。文献[4]的融合遗传蚁群算法充分利用正反馈缩小最大搜索时间，减少了进化次数，提高路由效率和最佳路径选择的精度，但该算法对于小规模网络会引入额外的时间成本，并且忽略了链路利用率和时延等参数。文献[5]提出了一种基于多路径传输的动态路由算法。该算法通过重新定义SDN数据中心网络中的关键链路以及链路关键度，充分利用了链路中的冗余路径，降低关键链路产生拥塞的概率。文献[6]提出的模拟退火-遗传混合算法首先通过模拟退火算法快速搜索得到较优解，之后利用遗传算法找到基于代价和时延优化的最优解，通过正反馈信息缩小最大搜索次数，快速得到最优路径，降低网络延迟与开销。
以上研究多关注的是网络中与链路状态相关的因素，忽略了路径层面的因素，在直观反应网络状态信息方面仍有不足。为了改善SDN网络中资源分配不合理等问题，拟提出一种基于路径层面的遗传算法(Path Level-based Genetic Algorithm，PLGA)。该算法在初始种群的产生时引用了Yen算法[7]，利用偏离路径的算法对初始种群进行优化选择。通过改变传统适应度函数设计的影响因素，选用路径层面的指标设计适应度函数[8]，再对算法进行优化。同时，与等价多路径(Equal Cost Multi Path，ECMP)、基于多路径传输的动态负载均衡路由(Multipath Transmission-based Dynamic Load-balanced Routing，MTDLR)、全局负载均衡(Global Load Balancing，GLB)算法相比较，验证所提算法的性能。
为了应对复杂的网络情况，采用SDN网络架构可以实现集中控制，提高网络的灵活性。SDN最大的特点就是转控分离的网络架构，其将转发和控制平面分离开，便于对网络进行集中化管理，能够增强网络的灵活性，具体架构如图1所示。
图1 SDN的控制与数据分离架构
SDN控制器能够管理多个网络设备并及时获取网络的状态信息，实现对整个网络的集中控制。转发平面，如交换机可以将网络中传输数据进行转发。在对网络进行规划时，可以通过对SDN控制器进行编程进而实现对整个网络的部署，提高了系统的灵活性，也使得网络的智能化部署能力得到提高。
PLGA算法分为编码、初始化种群、适应度函数设计、选择、交叉和变异等6个部分。
2.1 编码
根据输入的网络拓扑[9]G(V,E)，V表示网络中的节点集合，E表示网络链路集合。采用字符编码的编码方式，拓扑结构中从源节点到目的节点的每条路径表示一条染色体[10]。网络结构中的终端节点、交换节点和控制节点分别采用hn、sn、cn进行编码，其中n表示相应的节点类别下的编号，将图2所示的网络拓扑结构用字符编码的形式可表示为V={c1,h1,h2,s1,s2,s3,s4,s5,s6}。
图2 网络拓扑结构
2.2 初始化种群
对网络拓扑结构完成字符编码后，通过Yen算法产生初始种群。Yen算法属于限定无环K条最短路径算法(K-Shortest Pathes,KSP)算法。该算法采用偏离路径算法的思想，首先通过Dijkstra算法得出一条最短路径，再在该条最短路径中确定偏离点，在偏离点的基础上生成偏离路径，求得前K条最短路径。在使用Yen算法进行搜索时，所生成的所有路径为初始种群。Yen算法的步骤如下。
步骤1首先利用Dijkstra算法求出源节点s到目的节点d的最短路径e(s,d)。
步骤2选择偏离节点a(i)(源节点和目的节点除外)。
步骤3计算偏离节点到目的节点之间的路径l(s,d)，构成候选路径。
步骤4从候选路径中选择出最短偏离路径，得到p(K)，即为K条最短路径。
2.3 适应度函数设计
初始种群生成后，对所生成的初始种群进行适应度函数的设计，计算出个体的适应度，测量每条路径优劣程度，适应度函数在某种程度上间接影响最优路径的准确度。引入可用带宽质量、链路均衡度和路由跳数等3个因素构造适应度函数，将其作为衡量路径质量的标准，以此提高系统吞吐量、平均带宽利用率和降低传输时延。相比于链路状态，网络路径层面的因素更能直接影响网络传输效率。
1)可用带宽质量。每条链路的可用带宽越大，传输速率就越快，路径的传输速率也因此增大。相比于链路，路径总的可用带宽之和更能表示其优劣程度。引入路径的可用带宽质量(Available Bandwidth Quality of Path，ABQP)作为适应度函数设计的一个指标，将其定义为该条路径的可用带宽与所有路径中最大可用带宽之比，表达式为
(1)
2)链路均衡度。链路之间的差异影响数据传输速率，若每条链路之间带宽差异过大，容易造成链路拥塞或冗余，影响整个路径的传输效率。链路均衡度(Uniformity of the Link-available Bandwidth of the Path，ULBP)反映了路径中每条链路之间的差异程度，链路间差异越大，传输效率越低。相反，差异越小，则更有利于数据传输。链路均衡度定义为该条路径中最小链路带宽和最大链路带宽之比，表达式为
(2)
3)路由跳数指标R。路由跳数的减少可以降低发送时延、排队时延和处理时延，从而减少路径总传输时延。在一个路径中，路由跳数最小取值为2，故路由跳数取值范围为R≥2。
综合以上因素，适应度函数设计应表示为
(3)
式中，ε1、ε2、ε3为常数，且ε1+ε2+ε3=1，分别表示对应指标的所占比例。根据不同业务取值不同，路径可用带宽的质量和链路均衡度与适应度函数成正比，路由跳数与之成反比。
2.4 遗传算子及参数的确定
在获得所有染色体适应度函数值后，通过选择、交叉和变异操作确定新的种群[11]，具体包括以下3个方面。
1)选择操作。选择操作中常用的选择策略是轮盘赌选择法[12]。根据个体的适应度值计算其被选作下一代的概率，适应度值越大，被选作下一代的概率越高，个体被选中的概率表示为
(4)
随机产生处于[0，1]区间的数，判断产生的随机数所在的概率区间，选择出对应个体。再根据计算出的个体被选中的概率选择个体。
2)交叉操作。将选择出的个体进行交叉操作。为避免产生无效路径，在进行交叉操作时要选用有公共节点的路径行交叉操作，且交叉时按照一定概率进行操作，两条基因交叉概率分为以下两种情况。
(5)
p[ey(i,j)ez(i,j)]=k2
(6)
3)变异操作。在遗传算法中，变异概率的多样性可以确保所有的解空间都被搜索，避免出现局部最优[13]。节点变异概率分为两种情况。
(7)
p[ey(i)]=k4
(8)
式中，f′(eh)表示的是要变异个体的适应度值。考虑变异概率过大则无法控制算法搜索方向，过小则无法产生新的个体。因此，k3,k4∈(0.001,0.1)。在实验中，如果随机生成[0,1]之间的数小于变异概率，则该节点进行变异。在迭代次数达到设置的最大次数或最优个体占据总数一半时，算法终止[14]。
3.1 PLGA算法实现
在对路径完成编码后，记录每个节点的相邻节点、公共节点，并标志是否存在公共节点。如果没有相同的节点，则不交叉，直接将两条路径回。如果有相同的节点，随机选择一个公共节点进行交换，根据公共结点找到路径1和路径2中的索引，交换公共节点后面的片段，并更新路径。计算每一个个体的适应度值，并找出最佳适应度的个体，依照概率将交配池中的个体进行交叉、变异操作，更新种群及最佳适应值对应的个体。PLGA算法的实现步骤如下。
步骤1对网络拓扑结构进行字符编码。
步骤2利用Yen算法得到初始种群。
步骤3计算出个体的适应度值f(e)。
步骤4采用轮盘赌选择法，从初始种群中选择优良个体遗传到下一代。
步骤5按照交叉概率对种群执行交叉操作，生成新的个体。
步骤6将变异算子作用于种群，产生新个体。
步骤7得到新的种群后，判断是否满足终止条件，若不满足，重复步骤3。
3.2 算法复杂度分析
传统遗传算法的时间复杂度可以表示为O(max_gen·K)，max_gen表示最大迭代次数，K表示初始种群数。PLGA算法复杂度分析步骤如下。
步骤1产生初始种群时所用Yen算法时间复杂度为O(K2)。
步骤2根据种群代数进行产生新种群的循环。
步骤3根据初始种群的个体数，计算适应度函数，进行循环。
经过以上过程，PLGA算法时间复杂度可表示为O(K2)。
由此得出，PLGA算法的时间复杂度与初始种群的规模有关。
4.1 实验环境
实验环境是Mininet仿真平台，采用Open Vswitch交换机，Floodlight控制器，搭建的Pod=4的Fat-Tree结构模拟SDN数据中心网络如图3所示。整个拓扑网络自上而下分别为核心层、汇聚层和边缘层等3个层次，其中汇聚层交换机和边缘层交换机构成一个Pod。Fat-Tree为4元结构，Pod数目为4，一共有4台核心交换机，8台汇聚层交换机和8台边缘层交换机，16台主机。
图3 Fat-Tree网络拓扑结构
在实验中，每台虚拟机使用Iperf[15]产生所需要的数据流，在生成网络拓扑结构的Python脚本中，设置带宽为100 Mbit·s-1，时延设置为2 ms。逐渐增大负载率，利用Iperf测试丢包率、时延及吞吐量，指定链路负载从0.1～0.9进行测试，多次实验取平均值。
4.2 实验结果分析
将PLGA算法与ECMP、MTDLR[8]、GLB[16]等算法进行比较。
图4是4种算法在平均带宽利用率方面的对比情况。由图4可知，在链路负载较低时，4种算法平均带宽利用率差异不大。当链路负载超过0.3时，差异逐渐增大，ECMP算法属于静态路由算法，无法实时动态调节路由，造成带宽利用率较低。PLGA算法相比GLB算法，考虑了与链路相关的因素，MTDLR算法未与遗传算法融合，无法实现自适应搜索方向。因此，PLGA算法平均带宽利用率最大。
图4 Fat-Tree拓扑不同算法平均带宽利用率对比
图5是4种算法在系统吞吐量方面的对比情况，可以看出，随着链路负载的增大，4种算法的系统吞吐量均有所上升，但PLGA算法上升的程度高于其他3种算法。
图5 Fat-Tree拓扑不同算法系统吞吐量对比
图6是4种算法在平均传输时延方面的对比情况。当链路负载较小时，4种算法时延抖动几乎都为0；
当链路负载超过0.3时，随着链路负载的增加，4种算法的时延增加。PLGA算法的平均时延抖动明显低于其他3种算法，这是因为PLGA算法在设计适应度函数时考虑到了路由跳数这一指标，减少了链路传输的总时延。
图6 Fat-Tree拓扑不同算法平均传输时延对比
针对SDN网络在路径选择过程中出现的资源分配不合理和资源利用率低的问题，提出了一种PLGA算法。综合考虑了路径层面的可用带宽质量、链路均衡度和路由跳数等3个影响因素，构造遗传算法适应度函数，提高网络传输性能。验证结果表明，与ECMP、MTDLR和GLB等算法相比，PLGA算法在平均带宽利用率和系统吞吐量方面的性能提高，网络时延也有所降低。
猜你喜欢 适应度路由链路 改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28一种移动感知的混合FSO/RF 下行链路方案*火力与指挥控制(2022年8期)2022-09-16天空地一体化网络多中继链路自适应调度技术移动通信(2021年5期)2021-10-25数据通信中路由策略的匹配模式计算机与网络(2020年9期)2020-07-29一种用于6LoWPAN的多路径路由协议电脑知识与技术(2019年22期)2019-10-31OSPF外部路由引起的环路问题传播力研究(2019年24期)2019-10-21启发式搜索算法进行乐曲编辑的基本原理分析当代旅游(2016年10期)2017-04-17一种IS?IS网络中的链路异常检测方法、系统、装置、芯片科技创新导报(2016年27期)2017-03-14基于人群搜索算法的上市公司的Z—Score模型财务预警研究财经理论与实践(2015年2期)2015-04-16