叶叶

摘要 本文提出基于K-Dijkstra算法的SDN负载均衡方法。首先利用控制器评估当前网络负载情况，其次基于已知的K条备选链路，利用K-Dijkstra算法分析符合现有网络环境的链路;由于过载链路中存在部分流量拥塞的情况，所以需要进行迁移，最终实现均衡化链路负载。

【关键词】SDNK-Dijkstra 算法 负载均衡

随着云计算、大数据的兴起。在IT服务发展领域中数据中心扮演着至关重要的角色，是承载网络负荷的基础设施。要想确保网络服务质量，关键在于均衡化网络负载。从数据中心发展的层面分析，当务之急是解决网络中存在的流量拥塞问题，在此基础上优化网络资源，改善网络性能。

提高网络带宽，重新规划网络架构，是传统的改善网络性能、均衡化负载的基本方法。其常见的实现方法是使用负载均衡器，但是其复杂性高且费用高，同时其所有请求仅依赖于负载均衡器进行传递。均衡器一旦由于某种原因而突发故障，则降低网络性能，甚至使网络陷入瘫痪。众所周知可编程性差、创新性不足是传统网络的主要瓶颈性问题，从数据中心网络发展的角度来看，仅改善TCP/IP网络架构很难真正发挥其应有的作用，基于此，而形成软件定义网络。

1SDN介绍

1.1 SDN定义

Software Defined Network，简称SDN，即软件定义网络。SDN是近年来最流行的网络分层架构。此类架构从上至下可细分为三层：其一是应用层;其二是控制层;其三是数据层。由控制层完成传统网络中交换机、路由器的转移权限的操作，集中化网络功能。应用层是管理层进行网络监管的切入点。数据层的作用是执行控制层下发的决策，其中的路由器、交换机的功能仅局限于转发，应用层包含可编程接口，有助于减少系统工作压力，优化系统性能，实现灵活操作。

1.2 SDN特点

1.2.1转控分离

网元的控制平面在控制器上，负责协议计算，产生流表;而转发平面只在网络设备上。

1.2.2集中控制

设备网元通过控制器集中管理和下发流表，这样就不需要对设备进行逐一操作，具有简化操作的作用，实际操作中仅需要对控制器进行配置即可。

1.2.3开放接口

第三方应用只需要通过控制器提供的开放接口，通过编程方式定义一个新的网络功能，然后在控制器上运行即可。

1.3 0pen Flow协议介绍

灵活、规范、稳定性强的Open Flow协议是底层交换设备、控制器接口的重要协议，同时SDN领域普遍将该协议定义为南向接口标准。该技术的核心思想是支持分离SDN控制，同时协议还是控制器与底层交换设备实现通信的重要载体。网络管理者及广大用户依托Open Flow协议，可结合实际需求制定相应的转发策略，而非仅依赖传统硬件设备。如此一来，即可全面提升网络资源分配管理的灵活性。

在SDN架构中Open Flow控制器是最为核心的部件，该控制器可控制、管理整个网络，是SDN的关键要素之一。

2负载均衡的意义

在现有网络结构上负载均衡负责向各服务器平均分配主机请求，避免部分链路拥塞或空闲的情况。简而言之即有助于平衡各类链路的请求，缩短服务延长，提高服务吞吐量。

负载均衡调度算法，可具体分为如下两类，其分类依据即负载调度策略。

（1）静态负载均衡算法：立足网络现状，预设固定调度策略，并作为调度执行，而无需实时参考网络现状。此种算法无需立足网络现状实时变动，可有效缩短执行时间，节省成本。但是该算法的负载均衡效率差，不具有灵活性。

（2）动态负载均衡算法：可实现实时分析服务器、网络现状，在此基础上结合负载信息，动态的向服务器平均分配请求。该算法具有灵活性高的特点，所以可及时获取网络现状，并动态的实现调度负载，因此，解决了静态负载均衡算法灵活性差，不能够动态结合网络现状部署方案的缺点。

本文逐一分析了两种算法的优劣势。在此基础上提出了SDN负载均衡方法。该算法的核心思想是K-Dijkstra算法，优化SDN架构，并改进该算法，在已获得的短路径中删除某中一条边，重新寻找新的替代边，获取其他路径，通过控制器对转发策略调度进行重新制度，避免部分链路被流量拥堵的情况，进一步实现负载均衡。下文将具体说明算法的基本思想及核心理念。

3K-Dijkstr算法

3.1 K-Dijkstr算法基本思想

确定有向图最短径并删除其中某条边，在此基础上删除其中某条边，基于K条备选路路径选择一条可代替的路径。通过公式（1）说明图边中的权重值w。 w=αχ+βγ+γγ（1）

其中α+β+γ=1，χ、γ、z分别用于表示其一平均延迟;其二平均丢包率;其三跳数。具体由流量监测模块提供数值。给定初始权重值，即w =l/3（x+y+z），此后结合网络情况可方便用户、管理员结合需求改变并计算w值。假设所计算的值较w值小，对应的该值为有效值。如较w值大，则说明相关值为无效值，此时需要重新设计。

应用层软件可满足管理员结合具体要求设置当前网络跳数、丢包率、网络延迟等相关参数及占比。如经计算的w值越小，则说明对应的路径负载、优先级良好。结合己删除边计算寻找下一个可替代的最短路径，以小到大的順序排序总权重值w，由控制器下发转发策略，向优先级较高调度流量，缓解链路拥堵塞的情况，均衡负载。

3.2 K-Dijkstr算法描述

（1）基于向图G（N，A）采用该算法计算根节点为m的节点，并确定最短路径，s为终点，用Sn，表示该条路径，n=l;

（2）假设存在该路径的候选路径，且n

（3）在路径S点中，确定首个节点后，进行遍历操作从中确定首个入度较1大的节点，并记为ka，假设ka不存在于任何节点之中，换言之即节点中不存在ka的扩展节点，如符合条件，则直接进入（4）;如未符合条件，需找出ka后续首个不基于点集P的扩展节点，记为ka，则，继续执行步骤（5）;

（4）生成ka，即ka的扩展节点，同时加入点集P中，kn所有前驱节点（除前一个节点ka-1外）连接至ka，此时不改变弧权重，在弧集A中添加该弧值，基于m、ka计算两者的最短路径，代表初始节点与扩展节点的距离，并记为ki=ka+1;

（5）将所有ka之后路径S遍历的所有节点记为kc，同时需要执行相关操作：

首先将kc加入节点集合P中;

基于路径S分别连接kc的前驱节点至kc的弧（不包含前一个节点kc-1），在弧集A中添加这些弧，并不改变权值。

最后计算s到kc两者间的最短路径。假设扩展节点kc-1，存在于路径S中，且在kc-1存上，并形成kc-1与kc，该弧度具有连接两者的作用，对应的权值刚好为弧（kc-1，kc）相等：

（6）计算第n条最短路径，即m与t（n）的距离，即开始节点到结束节点的距离，同时n+l=n，具体执行上述第二个步骤。

扩展节点：具体指在上次节点集合中引入新节点。

前驱节点：顾名思义即某一节点的前一节点（同一最短路径）。

算法流程图如图1所示。

4小结

本文基于SDN架构详细研究并部署了均衡负载的方案，首先运用已有的控制器获取并评估网络负载;在此基础上结合K-Dijkstra算法具体求解出相关算法，即最短路径，在此基础上进行优先级排序，其排序依据为路径权重值大小，如经排序认为路径的权重值较小，则说明对应的最短路径具备较高的优先级;最后是转发策略，本步骤的重点是把存在流量过多的过载链路中的流量迁移至最符合要求的链路之中，均衡负载。同时结合该算法计算向图权重值，并利用三元函数组，满足用户在不同环境中的使用需求。综上本文所提出的方法不仅可显著优化网络性能，同时减少网络丢包率、网络延迟等情况的发生。当然本文尚存不足之处，有待后续研究完善。

参考文献

[1]武泽慧，魏强，王清贤，基于Open Flow的SDN网络攻防方法[J]，计算机科学，2017， 44 （06）：121-132.

[2]竇焕娟，基于Open Flow的服务器集群负载均衡的研究[D].北京：华北电力大学，2016.

[3]黄小曼.SDN网络控制器负载均衡技术研究与实现[D].南京：南京邮电大学，2015.

[4]胡延楠，软件定义网络关键技术及相关问题的研究[D].北京：北京邮电大学，2015.

[5]吴舢，一种基于SDN的网络负载均衡方案的设计与实现[D].上海：复旦大学，2014.