一种面向软件定义网络的多约束QoS路由策略设计方法

摘要

本发明公开一种面向软件定义网络的多约束QoS路由策略设计方法，该方法通过三个模块实现，包括流量监控模块、QoS路由计算模块和阻塞流量调度模块。流量监控模块记录链路的带宽信息、端口负载信息以及已下发流的详细信息；QoS路由计算模块根据流量监控模块获取链路带宽及端口负载信息作为路由选择指标，并利用优化算法计算符合多约束条件的最优路径；在端口发生拥塞时，控制器通过阻塞流量调度模块进行精准控制。本发明实现SDN控制器中基于多路径蚁群算法的路径计算功能；同时，采取路由计算与阻塞调度相组合的路由策略设计方法，有效提高链路的使用率、均衡网络负载。

说明书

技术领域

本发明属于计算机网络技术领域，具体涉及一种面向软件定义网络的多约束QoS路由策略设计方法。

背景技术

当前SDN网络环境下，Floodlight控制器的路径计算模块采用的是Dijkstra算法计算最短路径，但是这种算法容易使得网络中的所有数据包都走最短路径，导致网络中最短路径发生拥塞，而其他链路却处于空闲状态，不能得到充分的利用。因此，对于SDN环境下的多路径路由策略的研究就显得十分重要，多路径路由选择需要考虑到带宽、延时、丢包率、时延抖动以及成本等因素，这些因素是衡量网络QoS(Quality Of Service服务质量)的基本性能指标，所以，多路径路由选择问题就是在多约束条件下求最优解。

但是由于多约束条件没有统一的度量尺度，因此在传统网络环境下求出多约束条件下的路由最优解计算量十分巨大，使得目标优化很困难，在SDN环境中，控制器可以获得全局的网络拓扑视图，便于集中控制整个网络，在路径计算之前将不满足QoS约束的链路排除在路径选择对象之外，对于充分利用网络状态信息求最优路径的计算代价就会大大降低，然而，在现有的SDN控制器中所采用的Dijkstra算法仅仅适合通信量较小的小规模网络或实验室网络，对于时延及链路的使用率要求并不高，一般通过在带宽物理上限之内提高链路带宽即可达到正常通信的要求，而对于通信量大、时延要求高、不具备冗余链路的网络来说，Dijkstra算法就无法满足要求，当网络中出现较大规模的数据流，数据的发送速率达到路径的最大带宽时，就会造成数据传输时延迅速增加，甚至数据包的丢失。

此外，不管采取何种路由算法，链路都有发生阻塞的可能，当链路出现阻塞以后，对于传统网络方式下的阻塞调度方式或者采取对大流进行重路由或者切割流进行分流，无论采取何种方法，其流调度效率以及实用性都会显著降低，且实现复杂度和代价都会很高，在SDN环境下，利用控制器对网络的集中控制优势，控制器能够直接监听到拥塞发生的端口，采用多级反馈队列调度算法实现阻塞端口流量的分级分流，既能避免流量被切割传输的不实用性缺点也能降低重路由的高计算代价。

发明内容

发明目的：本发明的目的在于解决现有技术中存在的不足，提供一种面向软件定义网络的多约束QoS路由策略设计方法，本发明通过控制器中的各模块之间相互协作，充分利用SDN架构转发与控制相分离、集中控制和开放可编程的优势，向免费开源控制器Floodlight中添加自定义模块，从而达到高效多路径转发数据包的目的。

技术方案：本发明所述的一种面向软件定义网络的多约束QoS路由策略设计方法，包括流量监控模块、QoS路由计算模块和阻塞流量调度模块，所述流量监控模块记录链路的带宽信息、端口负载信息以及已下发流的详细信息；所述QoS路由计算模块根据流量监控模块获取的链路带宽和端口负载信息作为路由选择指标，并利用优化算法计算满足约束条件的最优路径；在端口发生拥塞时，控制器通过所述阻塞流量调度模块进行精准控制；

具体依次包括以下步骤：

(1)流量监控模块定期统计出各SDN交换机端口的实时流量，计算出流量速率；

(2)QoS路由计算模块根据拓扑发现模块所掌握的全局网络拓扑视图和流量监控模块确定的端口负载信息，采用多约束QoS路由算法计算满足QoS约束条件的最优路径；

(3)阻塞流量调度模块根据大流检测算法，将检测到的交换机端口的大流，采用多级反馈调度算法进行分级调度。

进一步的，所述步骤(1)的具体过程是：

SDN控制器通过流量监控模块每隔一定时间向网络内的所有SDN交换机发送flow_request端口统计请求消息获取端口信息，SDN交换机以packet_in格式封装消息，通过安全信道将端口统计应答消息statistics_reply发送给SDN控制器，控制器通过各交换机端口的应答消息收集到每个端口的实时流量并计算出每个端口的流速。

进一步的，所述步骤(2)的具体过程是：

(2.1)QoS路由计算模块根据SDN控制器所掌握的当前全局网络拓扑视图和流量监控模块获取的端口网络流量状态，利用多路径蚁群算法计算满足QoS 多约束条件的路径，计算出路径后，按照转发流程进行转发，给路径上的每台交换机下发流表；

(2.2)具体的转发流程为：创建flow_mod消息将流表安装在路径上的各台交换机上，当后续数据包进入网络后就按照流表指定的动作进行转发。

进一步的，所述步骤(3)的具体过程为：

(3.1)首先在全网设置一个阈值，当流量超过阈值时，判定网络中链路发生阻塞，启动多级反馈队列调度算法对新流进行调度，阈值一般取值为链路负载的75％～80％；

(3.2)大流检测算法通过流量监控模块周期性的统计交换机的流量信息，控制器每隔一段时间向交换机采集数据，流的大小通过ψ_t＝(B_t-B_t-p)/p进行计算，其中，B_t是交换机在t时刻采集的字节数，B_t-p是t-p时刻接收的字节数，p是时间间隔，ψ_t是对流量大小的统计；根据ψ_t值与界定的大流阈值Threshold的比较，对大流进行调度，Threshold的取值为链路容量的5％～10％；

(3.3)当流量达到阻塞条件，应用多级反馈调度算法具体为：为每个交换机端口设置一个队列，每个队列包括三个子队列，子队列的优先级又不同，一级队列的优先级最高，二级队列的优先级次之，三级队列的优先级最低，按照先来先服务的原则进行调度，每个队列的执行时间不同，一级队列的执行时间为T，二级队列的执行时间为2T，三级队列的执行时间为3T。

进一步的，所述建立QoS多约束条件的基本参数包括：带宽和时延约束条件；

进一步的，所述步骤(3.3)中应用多级反馈队列调度算法调度拥塞流量的具体过程包括：

采用多级反馈队列调度算法，对拥塞流量进行分流，设置三级队列，当网络中的流量达到全网设置的阈值后，通过大流检测算法将检测到的大流置于一级队列的末尾，按先来先调度原则排队等待传输，当轮到该流传输时，若它能在时间T内完成，便撤离系统；如果它在时间T结束时，尚未完成，调度程序便将该流转入第二级队列末尾，再同样地按先来先调度原则等待被传输，如果它在第二队列中运行2T后仍未完成，再将它放入第三级队列，若最终还未完成则将其移除 拥塞队列。

有益效果：本发明对SDN网络中Floodlight控制器的路由问题进行优化，根据QoS多约束条件，利用蚁群算法计算满足约束条件的多路径，避免网络中的所有数据包走最短路径造成最短路径的阻塞，利用多级反馈队列调度算法对拥塞的数据包进行分流，避免长时间得不到处理的数据包被丢弃，使SDN网络的整体性能得到提升。

综上所述，本发明实现SDN控制器中基于多路径蚁群算法的路径计算功能，同时，采取路由计算与阻塞调度相组合的路由策略设计方法，有效的提高链路使用率、均衡网络负载。

附图说明

图1为本发明中的QoS路由策略系统实施流程图；

图2为本发明中的路由计算过程流程图；

图3为本发明中的多级反馈队列调度示意图；

图4为实施例中的网络示意图；

图5为Dijkstra算法与MP_Ant算法的效果对比图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述实施例。

如图1和图2所示，本发明面向软件定义网络的多约束QoS路由策略设计方法，通过向Floodlight控制器中添加功能模块实现，包括流量监控模块、QoS路由计算模块、阻塞流量调度模块，所述流量监控模块记录链路的带宽信息、端口负载信息以及已下发流的详细信息；所述QoS路由计算模块根据流量监控模块获取链路带宽及端口负载信息作为路由选择指标，利用优化算法计算满足约束条件的最优路径；在端口发生拥塞时，控制器通过所述阻塞流量调度模块进行控制；具体依次包括以下步骤：

(1)SDN控制器通过流量监控模块每隔一定时间向网络内的所有SDN交换机发送flow_request端口统计请求消息获取端口信息，SDN交换机以packet_in格式封装消息通过安全信道将端口统计应答消息statistics_reply发送给SDN控制器，控制器通过各交换机端口的应答消息收集到每个端口的实时流量并计算出每个端口的流速。

(2)QoS路由计算模块根据拓扑发现模块所掌握的当前全局网络拓扑视图和流量监控模块获取的端口网络流量状态，利用改进的多路径蚁群算法计算满足QoS约束条件的路径，选出路径后，按照转发流程进行转发，给路径上的每台交换机下发流表。当数据包到达边缘交换机以后，交换机首先会获取packet_in消息匹配，然后查看dstDevice是否存在，如果不存在，则边缘层交换机会调用doFlood方法将数据包洪泛出去，如果存在，则获取srcDevice，查询入口和出口交换机所在簇，判断两者是否在同一个簇，如果不在同一个簇，则调用doFlood方法洪泛，如果在同一个簇，则继续判断是否在同一端口，如果属于同一端口，则调用doFlood方法洪泛，如果不在，则调用Qos路由计算的getRoutes方法获取路径，调用pushRoute方法向位于路径上的交换机添加流表项。

其中，doFlood方法的执行过程为：首先创建packet_out方法，然后为其设置执行动作列表(action)，向其中添加Flood操作，最后将其转发给交换机；

本步骤中，建立多约束QoS路由模型的目标是根据衡量QoS的性能指标：带宽、时延、丢包率以及链路利用率，选择满足以上组合条件的最优路径。

(3)所述阻塞流量调度模块根据阈值判断是否达到流量调度的条件，达到调度条件则通过大流检测算法将检测到的交换机端口的大流采用多级反馈队列调度算法进行分级调度。

实施例1

本实施例是面向软件定义网络的多约束QoS路由策略设计方法，采用如图3和图4所示的网络拓扑示意图。控制器负责集中式的控制整个网络，通过向控制器中添加三个应用模块实现QoS路由策略的设计，具体方法包括以下步骤：

步骤I，流量监控模块对SDN交换机各端口进行流速检测：

首先，由于本实施例只考虑QoS约束条件中的带宽和时延约束，因此，需要对拓扑结构中的各条链路的带宽和时延设定约束，接着通过主机H1使用iperf工具向网络中主机H2打流，持续较长时间，流的速率设为不同的值，模拟网络中的不同业务流，以区分大流和小流。然后流量监控模块每隔5s向网络内的SDN交换机S1发送端口统计请求消息，交换机以packet_in消息的格式将端口统计应答消息发送给Floodlight控制器。流量监控模块从端口统计应答消息中提取各端口的流量值，计算出流速值，且得到的流速值及数据流在不停的变化。

步骤II，QoS路由计算模块根据拓扑发现模块和流量监控模块确定的拓扑结构和端口负载信息，采用多约束QoS路由算法计算出满足QoS约束条件的最优路径。

首先，SDN控制器会发送LLDP(链路发现协议)嗅探包对网络连接情况有一个全局的拓扑视图。然后，对蚁群算法中的各参数进行设置，路由计算模块会根据蚁群算法求解出满足QoS路由模型中的多约束路径。

如图4，本实施中由S1～S8共8台SDN交换机组成的网络，从S1节点开始计算路径，因此将S1设为起始节点，将S1置于最优路径树的路径中，与S1相连的S2、S3、S4作为未确定路径添加到最优路径树中，根据蚁群算法选路概率公式计算路径。由设定的链路带宽和时延约束可知，最优路径树未确定路径中的最优路径是S1至S2的路径，因此确定S1到S2的路径。由于S2节点的路径已经确定，因此将S2节点所连接的节点S3、S5作为未确定路径添加到最优路径树中，如此一来，再利用蚁群算法的选路概率公式继续选路，可知S5被优先加入到最优路径树中，依次向下寻路，S8被加入到最优路径树中，从而确定一条路径S1-S2-S5-S8，在选路的过程中，为了避免陷入局部最优的状态，蚁群算法会根据信息素的更新规则选择其它路径分散链路的负载，因此，当S2节点加入到最优路径树中后，随着网络中端口流量的变化，根据信息素的更新规则，S3也会被加入到最优路径树中，接着根据选路概率公式S6、S8依次会被加入到最优路径树中，从而也确定另一条路径S1-S2-S3-S6-S8，这样一来，从S1节点开始面向所有的节点的路径都已确定。

步骤III，阻塞流量调度模块根据大流检测算法检测交换机端口的大流，采用多级反馈队列调度算法将检测到的各端口的大流进行分级调度。

首先阻塞流量调度模块根据阈值判断是否达到流量调度的条件，这里阈值设为链路负载的75％，达到调度条件则通过大流检测算法检测网络中的大流。这里大流阈值设为链路容量的10％，检测到大流之后，将检测到的大流采用多级反馈队列调度算法进行分级调度，避免长时间得不到处理的大流被丢弃。

通过上述实例流程，从路径端到端的传输时延方面分析本发明相比于floodlight控制器默认的路由策略方面的优势，2种算法的路径选择结果如表1所示。

表1路径选择结果

从图5中可以看出，只有在刚开始阶段，Dijkstra算法相较于MP_Ant算法的时延较小，而随着数据包发送速率的增加，Dijkstra算法的时延要大于MP_Ant算法，并且当发送速率达到最大带宽值时，Dijkstra算法的时延迅速增加，虽然MP_Ant的时延也在增长，但增加幅度较为缓和，总体上说MP_Ant算法的传输时延比Dijkstra算法要小。

综上所述，本发明基于SDN网络体系架构，在SDN控制器中进行模块化编程，实现了流量监控模块、路由计算模块和阻塞调度模块，并且本发明在数据包的端到端传输时延方面要优于现有的floodlight控制器中默认的路由策略，其次，本发明的路由策略是多路径路由选择，在链路利用率方面也要高于始终选择最短路径的Dijkstra算法。