一种基于SPFA算法计算转发路径的动态路由控制方法

摘要

本发明公开了一种基于SPFA算法计算转发路径的动态路由控制方法，根据网络信息通过SPFA算法计算最优路径；从所有交换机中筛选出最优路径经过的交换机id；解析该路径的起始IP地址；删除所有经过的交换机中符合该起始IP的流表；获取链路信息，并根据链路信息以及最优路径转发顺序创建每个该交换机中需要下发的流表并下发。本发明使得域间的链路浪费大大减小，并更具有智能型；在可靠性、安全性、出错处理需求上更加具体有效的优化；使得健壮性和可用性更强，并且增加其自检能力，完成系统定期自检，并报告潜在问题，有利于开发者从长远的角度了解项目的情况，并对长远的维护和进一步的开发，打开一个SDN领域路由优化的新纪元。

说明书

技术领域

本发明属于路由控制技术领域，尤其涉及一种基于SPFA算法计算转发路径的动态路由控制方法。

背景技术

路由和交换之间的主要区别就是交换发生在OSI参考模型第二层(数据链路层)，而路由发生在第三层，即网络层。这一区别决定了路由和交换在移动信息的过程中需使用不同的控制信息，所以两者实现各自功能的方式是不同的。当数据从一个子网传输到另一个子网时，可通过路由来完成。因此，路由具有判断网络地址和选择路径还有转发的功能，它能在多网络互联环境中，建立灵活的连接，可用完全不同的数据分组和介质访问方法连接各种子网，它不关心各子网使用的硬件设备，但要求运行与网络层协议相一致的软件。在当前我国网络基础建设和信息建设方兴未艾之际，探讨路由在互连网络中的作用、地位及其发展方向，对于国内的网络技术研究、网络建设，以及明确网络市场上对于路由和网络互连的各种似是而非的概念，都有重要的意义。根据传统网络路由选路算法是全局的还是局部的，选路算法可以分为：全局选路算法：用完整的，全局性的网络信息来计算从源到目的的最低费用路径。这种算法通常称为链路状态算法即LS算法，因为该算法必须知道网络中每条链路的费用。分布式选路算法：以迭代的、分布式的方式计算出最低费用路径。没有节点拥有关于所有网络链路费用的完整信息，而每个节点仅有与其直接相连链路的费用信息即可开始工作。然后通过迭代计算过程并与相邻节点交换信息，一个节点逐渐计算出到达目的节点或者一组目的节点的最低费用路径。在传统的网络设备中，控制平面和数据平面在物理位置上是紧密耦合的，这样的耦合有利于两个平面 之间数据的快速交互，从而实现网络设备性能的提升。然而，这种分布式的网络控制方式也带来了一些问题，例如，管理非常困难，只能逐个配置，热河错误都可能导致管理行为失效，并且难以故障定位与排查；另外，灵活性也不够，当网络设备需求的功能越来越复杂时，在分布式平面上进行新功能部署的难度非常大，尤其对于类似数据中心这种变化较快、管理灵活的应用场景，当前数据控制耦合的技术模式就凸显出其缺点。

目前，同一时间从同一个路由器发出的、到达相同目的地址的分组，必然经历相同的路线，所以就会造成带宽的浪费、损失不必要的数据等弊端。其次，在传统网络路由选路算法中，全局选路算法和分布式选路算法也不是没有缺陷的，同样存在着一些弊端，例如：每个分组交换机都参与计算，但计算内容相同，造成了大量的冗余计算，还有就是两种算法采用迭代计算，时间复杂度为O(n^2)，更新慢。

发明内容

本发明的目的在于提供一种基于SPFA算法计算转发路径的动态路由控制方法，旨在解决目前同一时间从同一个路由器发出的、到达相同目的地址的分组方法存在造成带宽的浪费、损失不必要数据，造成大量的冗余计算，更新慢的问题。

本发明是这样实现的，一种基于SPFA算法计算转发路径的动态路由控制方法，所述基于SPFA算法计算转发路径的动态路由控制方法包括以下步骤：

根据网络信息通过SPFA算法计算最优路径；

从所有交换机中筛选出最优路径经过的交换机id；

解析该路径的起始IP地址；

删除所有经过的交换机中符合该起始IP的流表；

获取链路信息，并根据链路信息以及最优路径转发顺序创建每个该交换机中需要下发的流表并下发。

本发明的另一目的在于提供一种所述基于SPFA算法计算转发路径的动态路由控制方法的基于SDN的分布式服务器负载均衡方法，＝所述基于SDN的分布式服务器负载均衡方法包括以下步骤：

(1)用户对服务器的访问请求通过SDN网络的接入口进入到SDN网络中；

(2)用户请求到达的SDN网络设备上部署匹配该请求的路由规则时，则SDN网络设备执行匹配对应的网络操作集；否则，SDN网络设备将访问请求传递给SDN控制器，由控制器根据负载均衡算法决策网络操作规则，并将网络操作规则部署到相应SDN网络设备上由相应SDN网络设备执行；

(3)服务器对最终到达的访问请求进行处理，并反馈请求结果；

(4)SDN网络设备接收到服务器的反馈结果后，如果反馈结果到达的SDN网络设备上已经部署了匹配该反馈结果的路由规则时，则SDN网络设备执行匹配对应的网络操作集；否则，SDN网络设备将反馈结果传递给SDN控制器，由控制器根据负载均衡算法决策网络操作规则，并将网络操作规则部署到相应SDN网络设备上由相应SDN网络设备执行；

(5)SPFA算法实现，建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径；然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路径，如果刷新成功并且被刷新点不在队列中则把该点加入到队列最后，重复执行直到队列为空。

进一步，所述SPFA算法包括：某个点进入队列的次数超过N次则存在负环；在执行算法前做一次拓扑排序，以判断是否存在负权回路；用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图；采取动态逼近法：设立先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾；不断从队列中取出结点来进行松弛操作，直至队列空为止。

进一步，采用网络拓扑传值来监测流量，具体包括以下步骤：

通过REST API获取当前时刻中所有交换机中所储存的流表；

对于每一个交换机中的流表进行记录；

经过500ms延时后再次获取所有流表；

对于两次获取中同一个id的流表计算其count字段的差值；

如果第二次获取时存在第一次不存在的流表，则直接使用其count值作为该条流的压力值；

如果第二次获取后不存在与第一次中某条流表相匹配的流表则忽略该条流表；

计算差值若为0则忽略该条流表；

对每个交换机上的流表进行端口分类；

将每个交换机中所有正在通过数据的流表的差值相加看作该交换机的压力数值；

对于一条链路来讲两头的端口的压力值得平均值设为该条链路的权值以此生成带有权值的图。

本发明的另一目的在于提供一种所述基于SPFA算法计算转发路径的动态路由控制方法的动态路由控制系统，所述动态路由控制系统包括：

信息获取模块，用于通过Java向Floodlight REST API发送POST、DELETE请求用来获取、删除符合要求的信息；

信息发送模块，用于通过封装JSON数据发送给REST API用来向信息控制器发送所需信息；

信息解析模块，用于通过解析返回的JSON数据获取链路信息、设备信息以及流表信息；

生成模块，用于通过所获得信息生成有向加权的图；

计算模块，用于根据图运算SPFA算法计算最优路径；

下发模块，用于通过获取的设备信息及最优路径生成双向流表进行下发。

本发明的另一目的在于提供一种应用所述基于SPFA算法计算转发路径的 动态路由控制方法的局域网路由控制方法。

本发明的另一目的在于提供一种应用所述基于SPFA算法计算转发路径的动态路由控制方法的局域间路由控制方法。

本发明的另一目的在于提供一种应用所述基于SPFA算法计算转发路径的动态路由控制方法的跨网段路由控制方法。

本发明的另一目的在于提供一种应用所述基于SPFA算法计算转发路径的动态路由控制方法的分布式网络控制方法。

本发明提供的基于SPFA算法计算转发路径的动态路由控制方法，公开了一种基于SDN的分布式服务器负载均衡方法，利用软件定义网络(SDN)控制面与转发面相分离的架构优势，用户访问请求到达SDN网络的某个设备上，由SDN控制器根据网络运行状态，动态地将用户请求调度至合适的服务器，实现了服务器的负载均衡。该方法能够提供从接入、转发到服务的全方位容错，充分发掘服务器集群的总负载能力，提高整个系统运行的扩展性和可靠性。

本发明运用不仅仅局限在局域内，而是进行域间的路由，从而进一步实现跨网段的路由；可以利用在更多的路由选择中，使得域间的链路浪费大大减小，并更具有智能型；在可靠性、安全性、出错处理需求上下一步也会进行更加具体有效的优化；使得健壮性和可用性更强，并且增加其自检能力，完成系统定期自检，并报告潜在问题，有利于开发者从长远的角度了解项目的情况，并对项目进行长远的维护和进一步的开发，将打开一个SDN领域路由优化的新纪元。

附图说明

图1是本发明实施例提供的基于SPFA算法计算转发路径的动态路由控制方法流程图。

图2是本发明实施例提供的采用网络拓扑传值来监测流量流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

下面结合附图对本发明的应用原理作详细的描述。

如图1所示，本发明实施例的基于SPFA算法计算转发路径的动态路由控制方法包括以下步骤：

S101：根据网络信息通过SPFA算法计算最优路径；

S:02：从所有交换机中筛选出最优路径经过的交换机id；

S103：解析该路径的起始IP地址；

S104：删除所有经过的交换机中符合该起始IP的流表；

S105：获取链路信息，并根据链路信息以及最优路径转发顺序创建每个该交换机中需要下发的流表并下发。

系统实现，核心代码实现

本发明实施例的基于SPFA算法计算转发路径的动态路由控制系统包括：

信息获取模块，用于通过Java向Floodlight REST API发送POST、DELETE请求用来获取、删除符合要求的信息。

信息发送模块，用于通过封装JSON数据发送给REST API用来向信息控制器发送所需信息。

信息解析模块，用于通过解析返回的JSON数据获取链路信息、设备信息以及流表信息。

生成模块，用于通过所获得信息生成有向加权的图。

计算模块，用于根据图运算SPFA算法计算最优路径。

下发模块，用于通过获取的设备信息及最优路径生成双向流表进行下发。

本发明提供了一种基于SDN的分布式服务器负载均衡方法，所述方法包括以下步骤：

(1)用户对服务器的访问请求通过SDN网络的接入口进入到SDN网络中；

(2)如果用户请求到达的SDN网络设备上已经部署了匹配该请求的路由规则时，则SDN网络设备执行匹配对应的网络操作集；否则，SDN网络设备将访问请求传递给SDN控制器，由控制器根据负载均衡算法决策网络操作规则，并将网络操作规则部署到相应SDN网络设备上由相应SDN网络设备执行；

(3)服务器对最终到达的访问请求进行处理，并反馈请求结果；

(4)SDN网络设备接收到服务器的反馈结果后，如果反馈结果到达的SDN网络设备上已经部署了匹配该反馈结果的路由规则时，则SDN网络设备执行匹配对应的网络操作集；否则，SDN网络设备将反馈结果传递给SDN控制器，由控制器根据负载均衡算法决策网络操作规则，并将网络操作规则部署到相应SDN网络设备上由相应SDN网络设备执行；

(5)SPFA算法实现

建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值，该点到他本身的路径赋为0)。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路径，如果刷新成功并且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

本发明实施例的SPFA算法包括：

如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)。在执行该算法前做一次拓扑排序，以判断是否存在负权回路。用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图。采取动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

如图2所示，本发明实施例采用网络拓扑传值来监测流量，具体包括以下步骤：

通过REST API获取当前时刻中所有交换机中所储存的流表。

对于每一个交换机中的流表进行记录。

经过500ms延时后再次获取所有流表。

对于两次获取中同一个id的流表计算其count字段的差值。

如果第二次获取时存在第一次不存在的流表，则直接使用其count值作为该条流的压力值。

如果第二次获取后不存在与第一次中某条流表相匹配的流表则忽略该条流表。

计算差值若为0则忽略该条流表。

对每个交换机上的流表进行端口分类。

将每个交换机中所有正在通过数据的流表的差值相加看作该交换机的压力数值。

对于一条链路来讲两头的端口的压力值得平均值设为该条链路的权值以此生成带有权值的图。

通过对动态路由器的性能、可靠性等方面的测试，并在实际的环境中，验证了功能的正确性，并实现了路径的动态路由，使得传输的数据在链路中的传出呈现出均衡的状态，通过测试，证明了该软件具有可用性和实用价值。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。