基于遗传算法的SDN增强路径装箱问题研究

何利文，唐澄澄，周 睿，侯小宇

(1.南京邮电大学，江苏 南京 210003；2.中兴通讯股份有限公司，江苏 南京 210012)

0 引 言

在SDN路由器的网络环境中，带宽是非常紧俏的资源。当网络流量负载不均衡时，网络中部分线路带宽利用率过高，其余网络资源利用率过低，导致无法添加新的业务，系统负载下降[1]。为了解决该问题，对SDN网络增强路径装箱问题进行研究。文中的研究目标是调整已有业务所在的通信链路，达到网络中带宽利用率的负载均衡，部署新的业务，并且在调整业务所在的通信链路时对系统的扰动最小[2]。

在传统的路由器解决方案中，路由的选择是通过以跳数，延迟，所占带宽资源与链路代价为量度的最短路径优先算法实现的。传统方案的缺陷在于：如果从一个源节点到目的节点的流量超过了最短路径的容量，最短路径将变得拥塞，但同时这两点之间可能有一条更长的路径没有被充分利用[3]；在来自不同源节点的最短路径在一条链路上重叠的情况下，如果通过该链路的总流量超过了该链路的容量，就会发生拥塞[4]。

在现有的网络拓扑结构下，为优化路由选择的路径，找到流量分配的最优方案，需要对网络实施流量工程。负载均衡是流量工程中的重要功能，其本质是一类装箱问题，即在带宽等不变的信道中容纳最多业务的问题[5]。

无论是多约束路由算法还是对现有的网络路径，实现新增业务路径的部署，这些都是具有复杂约束条件的组合优化问题,在理论上属NP问题。由于其目标解的搜索涉及解空间的组合爆炸,传统优化方法难以求最优解的完全问题，通常采用启发式算法求其近似解[6]。实践表明，引入遗传算法、采用新陈代谢的选择策略、保持进化过程中的遗传多样性，可以使装箱效率有明显的改善和提高。

1 当前网络装箱问题的解决方案

1.1 瞻博网络TE++方案

1.1.1 TE++简介

瞻博网络公司为解决网络装箱问题，使用TE++方案来最大限度地提高带宽利用率[7]。网络流量工程结构中的包转发单元是多协议标记交换(MPLS)，MPLS负责引导IP包流按一条预先确定的路径通过网络，这条路径被称作标记交换路径(LSP)。瞻博网络定义了一个称为“容器LSP”的新结构，这些LSP被称为“成员LSP”。为了处理网络条件和带宽需求的变化，TE++使用“拆分”和“合并”技术。

在“拆分”过程中，新增成员LSP重新发送带有更新带宽的成员LSP。在“合并”过程中，流量需求显著下降，一个或多个成员LSP被动态移除，把该部分带宽给其他容器LSP使用。通过计算几个小带宽LSP来满足应用程序或服务的带宽需求的方法，启用容器LSP来创建多个带宽较小的成员LSP。

1.1.2 TE++工作流程

容器LSP在入口路由器上管理成员LSP，入口路由器负责从成员LSP的带宽样本中计算容器LSP的总带宽。每个LSP成员都可以启用自动带宽机制，TE++会根据网络中的流量情况动态调整成员数量和每个成员的带宽。通过“拆分”将现有容器LSP细分成更多的成员LSP，如果需要的LSP不多，则入口路由器将移除多余的成员来“合并”，或用更高的带宽重新通知所保留的成员承担累计带宽。

图1说明了TE++的拆分和合并过程。最小信令带宽和最大信令带宽是在规范化期间使用的两个阈值，以确定应该有多少LSP以及与每个成员关联的带宽。示例：最小信令带宽：2 Gbps，最大信令带宽：8 Gbps，合并带宽：2 Gbps，拆分带宽：9 Gbps。容器LSP创建具有最小信令带宽的最小数目LSP(AE-1)的2 Gbps，虚线表示正在被移除的LSP。当流量开始在LSP上移动时，入口路由器A将从样本中计算总带宽。假设由于自动带宽机制调整，LSP增长到7 Gbps。容器LSP流量激增到10 Gbps。由于原路由路径带宽不够，所以通过计算将决定拆分原LSP。经过拆分，重新创建一个带有5 Gbps带宽的新成员LSPA-E-2，并以先断后合的方式用5 GB带宽重新发送现有成员LSP A-E-1。

图1 TE++的拆分和合并过程

经过规范化过程合并后，容器LSP上的聚合流量已经下降到4 Gbps，当规格化定时器到期时，由于每个成员的利用率达到了2 Gbps的合并带宽，因此发生合并。容器LSP删除成员LSP-A-E-2，并以4 Gbps的带宽重新给现有成员A-E-1发送信号。

1.2 诺基亚的STAR算法

1.2.1 诺基亚贝尔实验室的自适应路由(STAR)算法

诺基亚贝尔实验室对传统网络最短路径算法和多目标的路径计算要求进行改进，提出了基于集中路径计算元件(PCE)自适应路由调整(STAR)算法[8]。采用IP/MPLS网络使用的链路状态协议，开放最短路径优先协议(OSPF)，中间系统到中间系统协议(IS-IS)，路由标签交换路径协议(LSP)来选择更高效的路径，提高网络利用率。

1.2.2 STAR路径算法目标

从数学的角度来看，网络容量的调整是一个多维的装箱问题，在这个网络利用率的优化问题中，每个服务请求代表一定数值的项目，为了优化网络容量利用率，优化两个目标条件是：效率，在消耗最少的总网络带宽的前提下，优化资源利用；平衡，避免链路的重载，以避免出现拥塞和死锁的情况。

图2 给定拓扑和链路利用率的优化样例

图2显示了给定拓扑和链路利用率的优化样例。源节点和目标节点之间有三种不同的路径：P1，P2和P3。可以选择较长的路径P3(6跳)，避免使用链路60%容量的路径P1；或选择最具成本效益的途径，否则将会导致未来请求的死锁；在另一种路由协议下，如Min-max，牺牲更长的路线以达到平衡，确保当前最大链路利用率尽可能小，选择路径P3。

STAR算法旨在找到最佳的链路平衡率和网络利用率，在避免链路拥塞的同时，确保路径不占用过多网络资源。

2 基于遗传算法SDN增强路径装箱方法

2.1 模型设计

通过遗传算法计算每条业务的多条优秀的可行路径，在该路径的基础上再次使用遗传算法将每条业务的路径放置到网络中的合适位置，满足新添加的业务的网络需求，并使已有业务的扰动最小[9]。利用遗传算法这类启发式算法替代传统算法，逐代产生适应新增业务之后的网络环境的个体，最终产生高质量的可行解作为最优解。

如图3所示，SDN网络增强路径装箱问题基本框架的执行过程大概分为如下几个步骤：

图3 SDN网络增强路径装箱问题基本架构

步骤一：新的业务进入系统；一个新业务的第一个数据分组进入SDN时，到达SDN交换机，执行步骤二。

步骤二：SDN交换机将该数据分组或者数据分组头部发送给SDN控制器，执行步骤四。

步骤三：SDN控制器收集其控制的网络中的所有业务信息与资源信息：交换机、链路、业务等使用情况[10]，进入步骤五。

步骤四：SDN控制器启动PCE，计算出该业务需要通过的路径，如果成功计算出，则将该业务的路径信息加入到SDN交换机的流表项中部署；如果SDN控制器无法查找到合适的路由路径，执行步骤三。

步骤五：SDN控制器启动PCE,生成每条业务的多条备用路径，将这些路径作为输入使用遗传算法，算出业务装箱的最佳方案，保证新业务可以加入到SDN网络中，实现负载均衡，进入步骤六。

步骤六：SDN控制器将计算出的配置信息传输给网络中的SDN交换机，进入步骤七。

步骤七：SDN交换机收到配置信息，调整不满足要求的业务流的路径、修改该业务流所经过的SDN交换机的流表项，同时将新添加的业务下发给相应交换机的流表中，完成新业务的转发。

步骤八：完成新业务的部署并完成SDN网络的负载均衡[11]。

2.2 算法思路

在图4中，链路中三元组(0/1,0/1,0/1)第一个位置代表业务1是否经过该链路，经过为1，不经过为0，第二、三个位置代表业务2、3是否经过该链路，经过为1，不经过为0。

图5是优化后的网络状态。

图4 负载均衡示意(优化前)(最大带宽利用率ω=0.90)

图5 负载均衡示意(优化后)(最大带宽利用率ω=0.57)

优化的目标是使经过调整后的全局网络路径部署相对于装箱前网络扰动率最小，同时链路的剩余带宽得到最大化，网络对将来到达的连接请求具有更高的接纳能力[13]。

2.3 装箱问题的数学模型

在SDN网络中，链路装箱问题的核心是如何妥善地部署新增的若干业务，通过遗传找到合适的路径组合优化目标使得整个网络相较原来的部署扰动率最小并且负载最优。装箱问题的优化目标：

Y=minf=min[f1,f2]

(1)

(2)

2.4 算法的时间复杂度分析

文中算法是基于路径选择进行原有的路径优化并装入新增业务，算法复杂度由备用路由集的计算和遗传算法的搜索寻优过程决定[14]。遗传算法本质是一个群体迭代寻优过程，其算法运行时间与参数的选择(包括群体规模popSize和遗传算法终止条件，如最大运行代数maxGen)相关。各备用路由集的计算采用多约束路径遗传算法，其复杂度为O(m·maxGen1·n·(n+popSize1))，其中m是业务个数，popSize1是多约束路由计算的种群规模，n是网络节点个数，maxGen1是多约束路由计算的迭代次数。装箱时，对染色体的每一条链路的适应度评价是算法执行次数最多的基本运算，文中算法的编码长度是m+φ，m是已经存在的业务，φ是新增业务个数。通过计算，可以知道一个解的总复杂度为：O(maxGen2·popSize2·(popSize2+m)+φ·maxGen1·n·(n+popSize1))。其中popSize2是遗传算法的种群规模，maxGen2是迭代次数。

3 实验仿真与分析

实验基于500节点的网络，现有24k链路，50条业务。请求的新业务的带宽要求在1 G、800 M、500 M、50 M中随机选取，跳数约束为不大于80跳。

图6 实验结果分析

图6的实验结果是在初始种群规模为50，遗传算法迭代次数在250，500，750，和1 000代时生成的结果。由此可说明文中算法对大规模的约束网络模型具有良好的收敛速度。

4 结束语

基于遗传算法的SDN增强路径装箱方法，将SDN控制器负责路径计算和流量规划的PCE模块中遇到的装箱问题抽象成整数规划的多约束数学模型[15]。当网络空载时，多个不同要求的业务同时部署进当前网络中，可以调用本算法计算每个业务使用的工作路由的整数序列，找出最优的备用路由序列组合；当部分业务不能直接计算出可行路径时，可以调用全局寻优的方式找到一个新的路由整数序列，使得新业务部署后网络的整体扰动率最小，实现网络资源的优化。