CN110661704A - Calculation method of forwarding path and SDN controller - Google Patents

Abstract

Translated fromChinese

本发明公开了一种转发路径的计算方法，包括：获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条；根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。用本发明实施例有利于提高计算转发路径的效率和SDN网络的整体吞吐效率。

The invention discloses a method for calculating a forwarding path, comprising: acquiring network topology information, first service information and second service information, wherein the first service and the second service are any two of K services; the network topology information, the first service information and the second service information, and calculate the alternate forwarding path of the first service and the alternate forwarding path of the second service in parallel to obtain the alternate forwarding path of the first service set and a set of alternative forwarding paths for the second service; respectively selecting the target of the first service from the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service A forwarding path and a target forwarding path of the second service; sending the target forwarding path of the first service and the target forwarding path of the second service to a forwarding node. Using the embodiments of the present invention is beneficial to improve the efficiency of calculating the forwarding path and the overall throughput efficiency of the SDN network.

Description

Translated fromChinese

转发路径的计算方法及SDN控制器Calculation method of forwarding path and SDN controller

技术领域technical field

本发明涉及通信网络领域，尤其涉及一种转发路径的计算方法及SDN控制器。The present invention relates to the field of communication networks, and in particular, to a method for calculating a forwarding path and an SDN controller.

背景技术Background technique

软件定义网络(software defined network,SDN)是一种新型网络创新架构，是网络虚拟化的一种实现方式，通过其核心技术openflow将SDN的控制面与数据面分离开来，从而实现了网络流量的灵活控制，使网络作为管道变得更加智能。SDN控制器为SDN的大脑和中枢，掌管SDN的转发路径的计算，直接决定了网络的流量分布。Software Defined Network (SDN) is a new innovative network architecture and an implementation of network virtualization. Through its core technology openflow, the control plane and data plane of SDN are separated, thereby realizing network traffic. flexible control, making the network smarter as a conduit. The SDN controller is the brain and center of the SDN, in charge of the calculation of the forwarding path of the SDN, and directly determines the traffic distribution of the network.

在SDN中，解决如何为多个业务中的每个业务找到一条(不可分流)满足资源服务质量(quality of service,QoS)约束的最优转发路径是SDN的关键，这也是SDN全网优化问题。In SDN, the key to SDN is how to find an optimal forwarding path for each of multiple services (non-diverted) that satisfies the constraints of resource quality of service (QoS), which is also the problem of SDN network-wide optimization. .

针对SDN全网优化问题，现有技术主要有两种方案：方案一是采用串行计算并进行迭代的方式计算多业务的转发路径：首先对多个业务进行排序，然后按照排序结果依次串行计算多个业务中的每个业务的转发路径；对于此次无法计算得到转发路径的业务进行多次迭代计算。但是由于单个业务多约束转发路径计算耗时较大，串行计算耗时成倍增加，在业务量较大时计算转发路径耗时更大，迭代计算转发路径使得耗时进一步增加，使得串行计算业务转发路径效率低；串行计算转发路径时不能全局的考虑网络中各业务转发路径的带宽消耗，使得网络中各链路带宽消耗及其不均衡，即使多次迭代也无法改变这种网络带宽消耗不均衡的情况，从而导致整体吞吐率不高。方案二是将全网优化问题近似转变成带宽可分流问题，后采用列生成求解，再用启发式算法将解近似转回全网优化问题的解。但是列生成方法需要解大规模的线性规划，求解时间很长，计算效率极低。For SDN network-wide optimization, there are two main solutions in the existing technology: the first solution is to use serial calculation and iteration to calculate the forwarding path of multiple services: first, sort multiple services, and then serially serialize them according to the sorting results. Calculate the forwarding path of each service in the multiple services; perform multiple iterative calculations for the services whose forwarding paths cannot be calculated this time. However, since the calculation of the forwarding path with multiple constraints of a single service takes a lot of time, the time-consuming of serial calculation increases exponentially. When the traffic volume is large, the calculation of the forwarding path takes more time. The efficiency of calculating service forwarding paths is low; when calculating forwarding paths in series, the bandwidth consumption of each service forwarding path in the network cannot be considered globally, so that the bandwidth consumption of each link in the network is extremely unbalanced, and even multiple iterations cannot change this kind of network. Unbalanced bandwidth consumption, resulting in low overall throughput. The second solution is to approximately transform the whole network optimization problem into a bandwidth shunting problem, and then use column generation to solve it, and then use a heuristic algorithm to approximately convert the solution back to the solution of the whole network optimization problem. However, the column generation method needs to solve large-scale linear programming, the solution time is very long, and the computational efficiency is extremely low.

综上所述，针对SDN路由全网优化问题，现有技术计算得到的多业务的转发路径效率低，并且计算得到的转发路径使SDN的整体吞吐效率低。To sum up, for the whole network optimization problem of SDN routing, the multi-service forwarding paths calculated by the prior art have low efficiency, and the calculated forwarding paths make the overall throughput efficiency of SDN low.

发明内容SUMMARY OF THE INVENTION

本发明实施例提供一种转发路径的计算方法及SDN控制器，采用本发明实施例有利于提高计算转发路径的效率和SDN网络的整体吞吐效率。Embodiments of the present invention provide a method for calculating a forwarding path and an SDN controller. Using the embodiments of the present invention is beneficial to improve the efficiency of calculating the forwarding path and the overall throughput efficiency of the SDN network.

第一方面，本发明实施例提供一种转发路径的计算方法，包括：In a first aspect, an embodiment of the present invention provides a method for calculating a forwarding path, including:

获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；Obtain network topology information, first service information and second service information, where the first service and the second service are any two of the K services, and the K is an integer greater than 1;

根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；According to the network topology information, the first service information and the second service information, the alternative forwarding path of the first service and the alternative forwarding path of the second service are calculated in parallel to obtain the alternative forwarding path of the first service a set of forwarding paths and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths;

分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。Selecting the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service respectively; The target forwarding path of the first service and the target forwarding path of the second service are sent to the forwarding node.

在一种可行的实施例中，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：In a feasible embodiment, the alternative forwarding path of the first service and the alternative forwarding path of the second service are calculated in parallel according to the network topology information, the first service information and the second service information , to obtain the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service, perform calculation according to the network topology information and the first service information to obtain the first A set of alternative forwarding paths for a service, including:

根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；Calculate according to the network topology information and the first service information to obtain a first sub-path set and a second sub-path set of the first service; the first sub-path set includes one or more first sub-path sets path, the second sub-path set includes one or more second sub-paths;

根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。According to the first sub-path set and the second sub-path set, a set of candidate forwarding paths for the first service is obtained by calculation.

在一种可行的实施例中，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；In a feasible embodiment, the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the service information includes the starting forwarding node, Terminate forwarding nodes, required bandwidth and additivity constraints;

所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：The calculating according to the network topology information and the first service information to obtain the first sub-path set and the second sub-path set of the first service, including:

根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;

根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;

其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.

在一种可行的实施例中，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：In a feasible embodiment, calculating the set of alternative forwarding paths for the first service according to the first set of sub-paths and the set of second sub-paths includes:

从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;

获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;

根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.

在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：In a feasible embodiment, constructing an alternative forwarding path according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service ,include:

根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;

按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.

在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：In a feasible embodiment, the ordering of the sub-path pairs in the sub-path pair set according to the additivity constraint of the sub-path pairs to each sub-path pair in the set includes:

当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;

当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;

当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.

在一种可行的实施例中，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：In a feasible embodiment, the target forwarding path and When the target forwarding path of the second service is selected, the target forwarding path of the first service is selected from the set of alternative forwarding paths of the first service, including:

根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;

根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;

从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.

在一种可行的实施例中，所述备选转发路径包括多条链路；所述预设公式为：w_i＝∑_j1/b_i,j；In a feasible embodiment, the alternative forwarding path includes multiple links; the preset formula is: w_i =∑_j 1/b_i,j ;

其中，所述w_i为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述b_i,j为所述第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the_wi is the score of the ith alternative forwarding path in the set of alternative forwarding paths of the first service, and the b_i,j is the jth chain in the ith alternative forwarding path the remaining bandwidth of the path.

第二方面，本发明实施例提供一种SDN控制器，包括：In a second aspect, an embodiment of the present invention provides an SDN controller, including:

获取单元，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；an acquisition unit, configured to acquire network topology information, first service information and second service information, where the first service and the second service are any two of the K services, and the K is an integer greater than 1;

计算单元，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；A calculation unit, configured to calculate the alternative forwarding path of the first service and the alternative forwarding path of the second service in parallel according to the network topology information, the first service information and the second service information, so as to obtain the first service. A set of alternative forwarding paths for a service and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths;

选择单元，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；A selection unit, configured to select the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service respectively. target forwarding path;

发送单元，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。A sending unit, configured to send the target forwarding path of the first service and the target forwarding path of the second service to a forwarding node.

在一种可行的实施例中，所述计算单元包括：In a feasible embodiment, the computing unit includes:

第一计算子单元，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；a first calculation subunit, configured to perform calculation according to the network topology information and the first service information to obtain a first subpath set and a second subpath set of the first service; the first subpath set One or more first sub-paths are included, and the second sub-path set includes one or more second sub-paths;

第二计算子单元，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。A second calculation subunit, configured to calculate and obtain a set of alternative forwarding paths for the first service according to the first subpath set and the second subpath set.

在一种可行的实施例中，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元具体用于：In a feasible embodiment, the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the service information includes the starting forwarding node, Terminate forwarding node, required bandwidth and additivity constraints; the first calculation subunit is specifically used for:

根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;

根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;

其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.

在一种可行的实施例中，所述第二子计算单元具体用于：In a feasible embodiment, the second sub-computing unit is specifically used for:

从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;

获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;

根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.

在一种可行的实施例中，所述可加性约束包括跳数，所述第二子路径单元具体用于：In a feasible embodiment, the additivity constraint includes the number of hops, and the second sub-path unit is specifically used for:

根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;

按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.

在一种可行的实施例中，所述第二子路径单元具体用于：In a feasible embodiment, the second sub-path unit is specifically used for:

当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;

当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;

当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.

在一种可行的实施例中，所述选择单元具体用于：In a feasible embodiment, the selection unit is specifically used for:

根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;

根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;

从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.

在一种可行的实施例中，所述备选转发路径包括多条链路；所述预设公式为：w_i＝∑_j1/b_i,j；In a feasible embodiment, the alternative forwarding path includes multiple links; the preset formula is: w_i =∑_j 1/b_i,j ;

其中，所述w_i为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述b_i,j为所述第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the_wi is the score of the ith alternative forwarding path in the set of alternative forwarding paths of the first service, and the b_i,j is the jth chain in the ith alternative forwarding path the remaining bandwidth of the path.

第三方面，本发明实施例提供了一种SDN控制器，包括：In a third aspect, an embodiment of the present invention provides an SDN controller, including:

存储有可执行程序代码的存储器；a memory in which executable program code is stored;

与所述存储器耦合的处理器；a processor coupled to the memory;

所述处理器调用所述存储器中存储的所述可执行程序代码，执行如第一方面所述的全部或者部分方法。The processor invokes the executable program code stored in the memory to execute all or part of the method described in the first aspect.

第四方面，本发明实施例提供了一种计算机可读存储介质，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行如第一发面所述的全部或者部分方法。In a fourth aspect, an embodiment of the present invention provides a computer-readable storage medium, where the computer storage medium stores a computer program, the computer program includes program instructions, and the program instructions, when executed by a processor, cause the processing The controller executes all or part of the method described in the first aspect.

可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和共享风险链路组(shared risk linkgroups，SRLG)，提升网络的吞吐率。It can be seen that in the solution of the embodiment of the present invention, according to the network topology information and service information and the breadth-first search algorithm, multiple sub-paths are quickly calculated from the bidirectional path, and then multiple alternative forwarding services are constructed according to the multiple sub-paths. path, multiple alternative forwarding paths can be obtained in one calculation; and when constructing alternative forwarding paths, the additivity constraints of services and the additivity constraints of alternative forwarding paths, such as cost, delay, and hop count, have been considered Therefore, when selecting a target forwarding path for a service, there are multiple alternative forwarding paths to choose from, which greatly reduces the probability of bandwidth conflict, and decouples bandwidth constraints in a statistical sense, so that alternative forwarding paths for multiple services can be parallelized. calculation to improve the efficiency of calculating alternative forwarding paths. When multiple sub-paths are calculated from each direction according to the breadth-first search algorithm, each forwarding node in the network topology is traversed only once, which can greatly improve the efficiency of calculating multiple alternative forwarding paths, and obtain multiple backup paths. The forwarding paths are selected as separated as possible. Score multiple alternative forwarding paths according to the remaining bandwidth status of each link in the network topology, and sort them according to the scores, and determine the target forwarding path of the service according to the sequence of the sorted alternative forwarding paths. At this time, the service can be considered. Additivity constraint, which can determine the target forwarding path for each service as far as possible according to the direction of bandwidth load balancing of each link in the network topology, and the multiple alternative forwarding paths of the service are separated as much as possible, so that the determined target forwarding The path naturally satisfies the separation of active and standby and shared risk link groups (SRLG), which improves the throughput of the network.

本发明的这些方面或其他方面在以下实施例的描述中会更加简明易懂。These and other aspects of the invention will be more clearly understood from the description of the following embodiments.

附图说明Description of drawings

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

图1为本发明实施例提供的一种SDN的结构示意图；FIG. 1 is a schematic structural diagram of an SDN provided by an embodiment of the present invention;

图2为本发明实施例提供的一种转发路径的计算方法的流程示意图；2 is a schematic flowchart of a method for calculating a forwarding path according to an embodiment of the present invention;

图3为本发明实施例提供的一种网络拓扑结构示意图；3 is a schematic diagram of a network topology structure according to an embodiment of the present invention;

图4为一个转发路径的示意图；4 is a schematic diagram of a forwarding path;

图5为本发明实施例提供的另一种转发路径的计算方法的流程示意图；5 is a schematic flowchart of another method for calculating a forwarding path according to an embodiment of the present invention;

图6为本发明实施例提供的一个搜索子路径的流程示意图；6 is a schematic flowchart of a search subpath provided by an embodiment of the present invention;

图7为本发明实施例提供的一种SDN控制器的结构示意图；FIG. 7 is a schematic structural diagram of an SDN controller according to an embodiment of the present invention;

图8为本发明实施例提供的一种SDN控制器的局部结构示意图；FIG. 8 is a schematic partial structure diagram of an SDN controller according to an embodiment of the present invention;

图9为本发明实施例提供的另一种SDN控制器的结构示意图。FIG. 9 is a schematic structural diagram of another SDN controller according to an embodiment of the present invention.

具体实施方式Detailed ways

为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。In order for those skilled in the art to better understand the solutions of the present invention, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention.

参见图1，图1为本发明实施例提供的一种SDN的结构示意图。该SDN包括SDN控制器101和多个转发节点102。Referring to FIG. 1, FIG. 1 is a schematic structural diagram of an SDN provided by an embodiment of the present invention. The SDN includes anSDN controller 101 and a plurality of forwardingnodes 102 .

其中，上述转发节点102可为交换机、路由器或其他设备。The above-mentionedforwarding node 102 may be a switch, a router or other devices.

上述SDN控制器根据上述多个转发节点102构成上述SDN网络拓扑结构和待转发的多业务信息并行计算得到多业务的目标转发路径，然后通过openflow将该多业务的目标转发路径发送至上述SDN网络拓扑结构上，使得网络拓扑结构中转发节点构建上述多业务的目标转发路径，以实现多业务的转发。The above-mentioned SDN controller forms the above-mentioned SDN network topology structure according to the above-mentionedmultiple forwarding nodes 102 and calculates the multi-service target forwarding path in parallel to obtain the multi-service target forwarding path, and then sends the multi-service target forwarding path to the above-mentioned SDN network through openflow. In terms of topology, the forwarding nodes in the network topology structure build the target forwarding paths of the above multi-services, so as to realize the forwarding of multi-services.

参见图2，图2为本发明实施例提供的一种转发路径的计算方法的流程示意图。如图2所示，该方法包括：Referring to FIG. 2, FIG. 2 is a schematic flowchart of a method for calculating a forwarding path according to an embodiment of the present invention. As shown in Figure 2, the method includes:

S201、SDN控制器获取网络拓扑结构信息、第一业务信息和第二业务信息。S201. The SDN controller acquires network topology information, first service information and second service information.

其中，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；上述K条业务均为上述SDN控制器待转发的业务。Wherein, the first service and the second service are any two of the K services, and the K is an integer greater than 1; the K services are all services to be forwarded by the SDN controller.

其中，上述网络拓扑结构信息包括转发节点的数量和任两个转发节点之间的链路信息。该链路状态信息包括带宽和可加性约束。The above-mentioned network topology information includes the number of forwarding nodes and link information between any two forwarding nodes. The link state information includes bandwidth and additivity constraints.

进一步地，上述可加性约束包括但不限定于代价、时延和跳数。Further, the above additivity constraints include but are not limited to cost, delay and hop count.

参见图3，图3为本发明实施例提供的一种网络拓扑结构的示意图。如图3所示，该网络拓扑结构包括6个转发节点，分别为转发节点s、转发节点i、转发节点j、转发节点k、转发节点l和转发节点t。Referring to FIG. 3 , FIG. 3 is a schematic diagram of a network topology structure according to an embodiment of the present invention. As shown in FIG. 3 , the network topology structure includes 6 forwarding nodes, namely forwarding node s, forwarding node i, forwarding node j, forwarding node k, forwardingnode 1 and forwarding node t.

其中，转发节点s与转发节点i之间的链路信息为(1,2,80)，表示转发节点s与转发节点i之间的链路的带宽为80，业务从转发节点s到转发节点i的代价为1，时延为2；转发节点i和转发节点j之间的链路信息为(1,6,120)，表示转发节点i与转发节点j之间的链路的带宽为120，业务从转发节点i到转发节点j的代价为1，时延为6。Among them, the link information between the forwarding node s and the forwarding node i is (1, 2, 80), which means that the bandwidth of the link between the forwarding node s and the forwarding node i is 80, and the service goes from the forwarding node s to the forwarding node. The cost of i is 1, and the delay is 2; the link information between forwarding node i and forwarding node j is (1, 6, 120), indicating that the bandwidth of the link between forwarding node i and forwarding node j is 120, and the service The cost from forwarding node i to forwarding node j is 1, and the delay is 6.

转发节点s与转发节点k之间的、转发节点k与转发节点j之间的、转发节点k与转发节点l之间的、转发节点j与转发节点t之间的、转发节点i与转发节点l之间的和转发节点l与转发节点t之间的链路信息分别为(1,1,100)、(3,3,80)、(2,1,200)、(3,2,180)、(4,2,150)和(3,2,120)，该链路信息的含义可参见上述相关描述，在此不再叙述。between forwarding node s and forwarding node k, between forwarding node k and forwarding node j, between forwarding node k and forwarding node l, between forwarding node j and forwarding node t, between forwarding node i and forwarding node The link information between l and between forwarding node l and forwarding node t is (1,1,100), (3,3,80), (2,1,200), (3,2,180), (4,2,150) ) and (3, 2, 120), the meaning of the link information can be found in the above related descriptions, and will not be described here.

其中，上述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束，该可加性约束包括但不限定于时延、代价和跳数。Wherein, the above-mentioned service information includes the starting forwarding node, the terminating forwarding node, the required bandwidth, and additivity constraints, and the additivity constraints include but are not limited to delay, cost, and hop count.

需要说明的是，上述业务的时延、代价和跳数分别为业务从其起始转发节点至终止转发节点所能容忍的最大时延，最大代价和最大跳数。It should be noted that the delay, cost and hop count of the above-mentioned services are respectively the maximum delay, the maximum cost and the maximum hop count that the service can tolerate from its initial forwarding node to its terminating forwarding node.

S202、SDN控制器根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径。S202. The SDN controller calculates the alternate forwarding path of the first service and the alternate forwarding path of the second service in parallel according to the network topology information, the first service information and the second service information, to obtain the first service A set of alternative forwarding paths for a service and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths.

需要指出的是，针对上述第一业务和第二业务，上述SDN控制器启动两条线程，实现并行计算上述第一业务的备选转发路径集合和上述第二业务的备选转发路径集合。It should be noted that, for the first service and the second service, the SDN controller starts two threads to implement parallel calculation of the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service.

具体地，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：Specifically, calculating the alternative forwarding path of the first service and the alternative forwarding path of the second service in parallel according to the network topology information, the first service information and the second service information, so as to obtain the first service When a set of alternative forwarding paths for a service and a set of alternative forwarding paths for the second service, calculation is performed according to the network topology information and the information of the first service to obtain the alternative forwarding of the first service A collection of paths, including:

根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；Calculate according to the network topology information and the first service information to obtain a first sub-path set and a second sub-path set of the first service; the first sub-path set includes one or more first sub-path sets path, the second sub-path set includes one or more second sub-paths;

根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。According to the first sub-path set and the second sub-path set, a set of candidate forwarding paths for the first service is obtained by calculation.

进一步地，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；Further, the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the service information includes the starting forwarding node, the terminating forwarding node, the required bandwidth and additivity constraints;

所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：The calculating according to the network topology information and the first service information to obtain the first sub-path set and the second sub-path set of the first service, including:

根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;

根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;

其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.

其中，上述可加性约束包括但不限于代价、时延和跳数。The above additivity constraints include but are not limited to cost, delay and hop count.

具体地，上述SDN控制器根据上述第一业务信息获取该第一业务的起始转发节点和终止转发节点，然后根据广度优先搜索算法，从上述第一业务的起始转发节点沿第一方向搜索，遍历上述网络拓扑结构中除了该第一业务的起始转发节点之外的每个转发节点，确定上述拓扑网络结构中除了该第一业务的起始转节点之外的任一转发节点k到该第一业务的起始转发节点的子路径的带宽、代价、时延和跳数；判断该子路径的带宽是否大于或者等于上述第一业务的所需带宽、该子路径的代价、时延和跳数是否均分别小于上述第一业务的代价、时延和跳数；当确定该子路径的带宽大于或者等于上述第一业务的所需带宽，且该子路径的代价、时延和跳数均小于或者等于上述第一业务的代价、时延和跳数，则确定该子路径为第一子路径；当该子路径的带宽小于上述第一业务的所需带宽，或者该子路径的代价大于上述第一业务的代价，或者该子路径的时延大于上述第一业务的代价，或者该子路径的跳数大于上述第一业务的跳数时，上述SDN控制器跳过，继续搜索下一转发节点。Specifically, the SDN controller obtains the starting forwarding node and the ending forwarding node of the first service according to the first service information, and then searches from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm. , traverse each forwarding node except the initial forwarding node of the first service in the above-mentioned network topology structure, and determine any forwarding node k to The bandwidth, cost, delay and hop count of the subpath of the initial forwarding node of the first service; determine whether the bandwidth of the subpath is greater than or equal to the required bandwidth of the first service, the cost and delay of the subpath and the number of hops are respectively less than the cost, delay and number of hops of the first service; when it is determined that the bandwidth of the subpath is greater than or equal to the required bandwidth of the first service, and the cost, delay and hop of the subpath If the numbers are less than or equal to the cost, delay, and hop count of the first service, the subpath is determined to be the first subpath; when the bandwidth of the subpath is less than the required bandwidth of the first service, or the subpath is the first subpath When the cost is greater than the cost of the first service, or the delay of the sub-path is greater than the cost of the first service, or the number of hops of the sub-path is greater than the number of hops of the first service, the SDN controller skips and continues the search next forwarding node.

按照上述方法，上述SDN控制器获取上述第一子路径集合，该第一子路径集合包括一条或者多条第一子路径。对于上述网络拓扑结构的除了第一业务的起始转发节点之外的每个转发节点，上述SDN控制器只遍历一次。According to the above method, the above-mentioned SDN controller obtains the above-mentioned first sub-path set, where the first sub-path set includes one or more first sub-paths. For each forwarding node of the above network topology structure except the initial forwarding node of the first service, the above SDN controller traverses only once.

同理，上述SDN控制器按照上述方法，根据广度优先搜索算法，从上述第一业务的终止转发节点沿第二方向搜索，以得到上述第二子路径集合。Similarly, the above-mentioned SDN controller searches along the second direction from the terminating forwarding node of the above-mentioned first service according to the above-mentioned method and the breadth-first search algorithm to obtain the above-mentioned second sub-path set.

在一种可行的实施例中，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：In a feasible embodiment, calculating the set of alternative forwarding paths for the first service according to the first set of sub-paths and the set of second sub-paths includes:

从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;

获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;

根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.

具体地，上述SDN控制器根据上述第一子路径集合和第二子路径集合获取上述子路径集合，该子路径集合包括一个或多个子路径对，该子路径对集合中的每个子路径对中的两条子路径的终止转发节点相同，且该子路径集合中的每个子路径对中的两条子路径分别属于上述第一子路径集合和第二子路径集合。然后上述SDN控制器根据上述子路径对集合中每个子路径对的两条子路径的可加性约束，获取上述子路径对集合中每个子路径对的可加性约束。Specifically, the above-mentioned SDN controller obtains the above-mentioned sub-path set according to the above-mentioned first sub-path set and the above-mentioned second sub-path set, the sub-path set includes one or more sub-path pairs, and each sub-path pair in the sub-path pair set is in the middle The terminating forwarding nodes of the two sub-paths are the same, and the two sub-paths in each sub-path pair in the sub-path set respectively belong to the first sub-path set and the second sub-path set. Then, the above-mentioned SDN controller obtains the additivity constraint of each sub-path pair in the above-mentioned sub-path pair set according to the additivity constraints of the two sub-paths of each sub-path pair in the above-mentioned sub-path pair set.

其中，上述子路径对的可加性约束为该子路径对的两条子路径的可加性约束之和，比如若上述子路径的可加性约束包括代价时，则子路径对的可加性约束为该子路径对的两条子路径的代价之和，若上述子路径的可加性约束包括时延时，则上述子路径对的可加性约束为该子路径对的两条子路径的时延之和；若上述子路径的可加性约束包括跳数时，则该子路径对的可加性约束为该子路径对的两条子路径的跳数之和。The additivity constraint of the above-mentioned sub-path pair is the sum of the additivity constraints of the two sub-paths of the sub-path pair. The constraint is the sum of the costs of the two subpaths of the subpath pair. If the additivity constraint of the subpath pair includes time delay, the additivity constraint of the subpath pair is the time delay of the two subpaths of the subpath pair. The sum of extension; if the additivity constraint of the subpath includes the hop count, the additivity constraint of the subpath pair is the sum of the hop counts of the two subpaths of the subpath pair.

举例说明，假如子路径对的两条子路径的可加性约束包括对代价、时延和跳数，两条子路径的代价分别为3和5、时延分别为2和3，跳数分别为4和5，则上述子路径对的可加性约束包括代价、时延和跳数，且代价为8、时延为5和跳数为9。For example, if the additivity constraints of the two subpaths of a subpath pair include cost, delay and hop count, the cost of the two subpaths is 3 and 5, the delay is 2 and 3 respectively, and the number of hops is 4 and 5, then the additivity constraints of the above sub-path pair include cost, delay and hop count, and the cost is 8, the delay is 5 and the hop count is 9.

上述SDN控制器根据上述方法获取上述子路径集合中每个子路径对的可加性约束。然后上述SDN控制器确定每个子路径对的可加性约束是否小于或者等于第一业务的可加性约束；当子路径对的可加性约束小于或者等于上述第一业务的可加性约束时，上述SDN控制器以该子路径对的两条子路径的终止转发节点为连接点，构建备选转发路径。The above-mentioned SDN controller obtains the additivity constraint of each sub-path pair in the above-mentioned sub-path set according to the above-mentioned method. Then the SDN controller determines whether the additivity constraint of each sub-path pair is less than or equal to the additivity constraint of the first service; when the additivity constraint of the sub-path pair is less than or equal to the additivity constraint of the first service , the above-mentioned SDN controller uses the terminating forwarding node of the two sub-paths of the sub-path pair as a connection point to construct an alternative forwarding path.

其中，子路径对的可加性约束小于或者等于上述第一业务的可加性约束，包括：Wherein, the additivity constraint of the sub-path pair is less than or equal to the additivity constraint of the first service, including:

当上述可加性约束包括代价时，上述子路径对的代价小于或者等于上述第一业务的代价；当上述可加性约束包括时延时；上述子路径对的时延小于或者等于上述第一业务的时延；当上述可加性约束包括跳数时，上述子路径对的跳数小于或者等于上述第一业务的跳数；When the additivity constraint includes a cost, the cost of the subpath pair is less than or equal to the cost of the first service; when the additivity constraint includes time delay; the delay of the subpath pair is less than or equal to the first service The delay of the service; when the above-mentioned additivity constraint includes the number of hops, the number of hops of the above-mentioned sub-path pair is less than or equal to the number of hops of the above-mentioned first service;

当上述可加性约束包括代价和时延时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的时延小于或等于第一业务的时延；当上述可加性约束包括时延和跳数时，上述子路径对的时延小于或等于第一业务的时延，且上述子路径对的跳数小于或等于第一业务的跳数；当上述可加性约束包括代价和跳数时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的跳数小于或等于第一业务的跳数；When the above additivity constraint includes cost and time delay, the cost of the above-mentioned sub-path pair is less than or equal to the cost of the first service, and the delay of the above-mentioned sub-path pair is less than or equal to the delay of the first service; When the property constraints include the delay and the number of hops, the delay of the above-mentioned sub-path pair is less than or equal to the delay of the first service, and the number of hops of the above-mentioned sub-path pair is less than or equal to the number of hops of the first service; when the above-mentioned additivity When the constraint includes cost and hop count, the cost of the above-mentioned subpath pair is less than or equal to the cost of the first service, and the hop count of the above-mentioned subpath pair is less than or equal to the hop count of the first service;

当上述可加性约束包括代价、时延和跳数时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的时延小于或等于第一业务的时延；且上述子路径对的代价小于或等于第一业务的代价。When the above additivity constraints include cost, delay and hop count, the cost of the sub-path pair is less than or equal to the cost of the first service, and the delay of the sub-path pair is less than or equal to the delay of the first service; and The cost of the above sub-path pair is less than or equal to the cost of the first service.

在一种可行的实施例中，上述SDN控制器按照上述方法构建备选转发路径m之前，该SDN控制器判断该备选转发路径m是否成环，即备选转发路径m是否经过同一转发节点至少两次。当确定该备选转发路径m成环时，上述SDN控制器不构建上述备选转发路径m。如图4所示，备选转发路径m经过转发节点1-2-3-4-2-5-6-7，其中，该备选转发路径经过转发节点2两次，因此上述SDN控制器确定该备选转发路径m成环，不构建该备选转发路径m。In a feasible embodiment, before the SDN controller constructs the alternative forwarding path m according to the above method, the SDN controller determines whether the alternative forwarding path m forms a loop, that is, whether the alternative forwarding path m passes through the same forwarding node At least twice. When it is determined that the alternative forwarding path m forms a loop, the above-mentioned SDN controller does not construct the above-mentioned alternative forwarding path m. As shown in FIG. 4 , the alternative forwarding path m passes through the forwarding node 1-2-3-4-2-5-6-7, wherein the alternative forwarding path passes through the forwardingnode 2 twice, so the above-mentioned SDN controller determines The alternative forwarding path m forms a loop, and the alternative forwarding path m is not constructed.

当确定上述备选转发路径m未成环时，上述SDN控制器确定该备选转发路径m是否与已构建的备选转发路径重复；当确定上述备选转发路径m与已构建的备选转发路径重复时，上述SDN控制器不构建上述备选转发路径m；当确定上述备选转发路径m未与已构建的备选转发路径重复时，上述SDN控制器构建并保存上述备选转发路径m。When it is determined that the alternative forwarding path m does not form a loop, the SDN controller determines whether the alternative forwarding path m overlaps with the constructed alternative forwarding path; when it is determined that the alternative forwarding path m and the constructed alternative forwarding path When repeated, the SDN controller does not construct the alternative forwarding path m; when it is determined that the alternative forwarding path m does not overlap with the constructed alternative forwarding path, the SDN controller constructs and saves the alternative forwarding path m.

按照上述方法，上述SDN控制器得到上述第一业务的备选转发路径集合。According to the above method, the above-mentioned SDN controller obtains the set of alternative forwarding paths of the above-mentioned first service.

在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的带宽和可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：In a feasible embodiment, the alternative forwarding path is constructed according to the bandwidth and additivity constraints of each sub-path pair in the sub-path pair set, so as to obtain the alternative forwarding of the first service A collection of paths, including:

根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;

按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.

其中，述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：Wherein, sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of the sub-path pairs to each sub-path pair in the set includes:

当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;

当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;

当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.

进一步地，当上述可加性约束包括跳数和代价，且跳数为第一优先级，代价为第二优先级时，上述SDN控制器根据子路径对的跳数对上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，代价小的子路径对排序靠前；Further, when the above-mentioned additivity constraint includes the number of hops and the cost, and the number of hops is the first priority, and the cost is the second priority, the above-mentioned SDN controller according to the number of hops of the sub-path pair is in the above-mentioned sub-path pair set. For subpath pairs with the same number of hops, the subpath pairs with the smaller hops are sorted first;

当上述可加性约束包括跳数和时延，且跳数为第一优先级，时延为第二优先级时，上述SDN控制器根据子路径对的跳数对上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，时延小的子路径对排序靠前；When the additivity constraint includes the number of hops and the delay, and the number of hops is the first priority and the delay is the second priority, the SDN controller determines the number of subpath pairs in the set of subpath pairs according to the number of hops of the subpath pair. The sub-path pairs are sorted, and the sub-path pairs with the small hops are sorted first; for the sub-path pairs with the same hop count, the sub-path pairs with the small delay are sorted first;

当上述可加性约束包括代价和时延，且时延为第一优先级，代价为第二优先级时，上述SDN控制器根据子路径对的时延对上述子路径对集合中的子路径对进行排序，时延小的子路径对排序靠前；对于时延相同的子路径对，代价小的子路径对排序靠前；When the above additivity constraint includes cost and delay, and the delay is the first priority and the cost is the second priority, the SDN controller determines the sub-paths in the sub-path pair set according to the delay of the sub-path pair. For the sub-path pair with the same delay, the sub-path pair with the small cost is ranked first;

当上述可加性约束包括跳数、代价和时延，且跳数为第一优先级，时延为第二优先级，代价为第三优先级时，上述SDN控制器首先根据子路径对的跳数上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，时延小的子路径对排序靠前；对于跳数和时延均相同的子路径对，代价小的子路径对排序靠前。When the above additivity constraints include the number of hops, the cost, and the delay, and the number of hops is the first priority, the delay is the second priority, and the cost is the third priority, the SDN controller first determines the The above subpaths in the hop count sort the subpath pairs in the set, and the subpaths with the smaller hops are sorted first; for the subpaths with the same hops, the subpaths with the smaller delay are sorted first; for the hops and For sub-path pairs with the same delay, the sub-path pairs with the lowest cost are ranked first.

按照上述方法，上述SDN控制器得到排序后的子路径对。According to the above method, the above-mentioned SDN controller obtains the sorted sub-path pairs.

当上述可加性约束包括跳数时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数，直至判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数。When the additivity constraint includes the number of hops, the SDN controller determines, one by one, whether the number of hops of each sub-path pair in the set of sub-path pairs is less than or equal to that of the first service according to the sequence of the sorted sub-path pairs. Hop count; when it is determined that the hop count of the s-th sub-path pair in the sorted sub-path pair is less than the hop count of the first service, the SDN controller determines the sub-path pair that is sorted after the s-th sub-path pair The hop count of the first service is less than the hop count of the first service, and the construction of the alternative forwarding path for the first service ends; when the SDN controller determines that the hop count of the s-th sub-path pair is less than or equal to the hop count of the first service When , the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as a connection point to construct an alternative forwarding path for the first service. Then, the SDN controller continues to judge whether the hop count of the s+1th sub-path pair is less than or equal to the hop count of the first service according to the above method, until it judges whether the hop count of each sub-path pair in the set of sub-path pairs is not Less than or equal to the number of hops of the first service.

当上述可加性约束包括代价时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的代价是否小于或者等于上述第一业务的代价；当确定上述排序后的子路径对中的第s个子路径对的代价小于上述第一业务的代价时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的代价均小于上述第一业务的代价，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的代价是否小于或者等于上述第一业务的代价，直至判断上述子路径对集合中的每个子路径对的代价是否小于或者等于上述第一业务的代价。When the above-mentioned additivity constraint includes a cost, the above-mentioned SDN controller judges, according to the sequence of the sorted sub-path pairs, whether the cost of each sub-path pair in the above-mentioned sub-path pair set is less than or equal to the cost of the above-mentioned first service one by one; When it is determined that the cost of the s-th sub-path pair in the sorted sub-path pair is less than the cost of the first service, the SDN controller determines that the costs of the sub-path pairs after the s-th sub-path pair are all less than the above-mentioned cost The cost of the first service, the construction of the alternative forwarding path for the first service ends; when the SDN controller determines that the cost of the s-th sub-path pair is less than or equal to the cost of the first service, the SDN controller takes the s-th sub-path pair as the cost. The termination and forwarding nodes of two sub-paths in the sub-path pair are connection points, and an alternative forwarding path for the first service is constructed. Then, the SDN controller continues to judge whether the cost of the s+1th sub-path pair is less than or equal to the cost of the first service according to the above method, until it judges whether the cost of each sub-path pair in the set of sub-path pairs is less than or equal to The price of the above-mentioned first business.

当上述可加性约束包括时延时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的时延是否小于或者等于上述第一业务的时延；当确定上述排序后的子路径对中的第s个子路径对的时延小于上述第一业务的时延时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的时延均小于上述第一业务的时延，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的时延是否小于或者等于上述第一业务的时延，直至判断上述子路径对集合中的子路径对的时延是否小于或者等于上述第一业务的时延。When the additivity constraint includes time delay, the SDN controller determines whether the delay of each sub-path pair in the set of sub-path pairs is less than or equal to the delay of the first service according to the sequence of the sorted sub-path pairs. time delay; when it is determined that the time delay of the s th sub-path pair in the above-mentioned sorted sub-path pair is less than the time delay of the above-mentioned first service, the above-mentioned SDN controller determines the sub-path pair after the s-th sub-path pair. The delay of the first service is less than the delay of the first service, and the construction of the alternative forwarding path of the first service ends; when the SDN controller determines that the delay of the s-th sub-path pair is less than or equal to the delay of the first service When , the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as a connection point to construct an alternative forwarding path for the first service. Then, the SDN controller continues to judge whether the delay of the s+1th sub-path pair is less than or equal to the delay of the first service according to the above method, until it judges whether the delay of the sub-path pairs in the set of sub-path pairs is less than or equal to Or equal to the time delay of the above-mentioned first service.

当上述可加性约束包括跳数和代价，且跳数为第一优先级，代价为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器判断上述第s个子路径对的代价是否小于上述第一业务的代价；当确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数；当上述第s个子路径对的代价大于上述第一业务的代价时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的跳数相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。When the additivity constraint includes the number of hops and the cost, and the number of hops is the first priority and the cost is the second priority, the SDN controller determines the set of sub-path pairs one by one according to the sequence of the sorted sub-path pairs Whether the hop count of each sub-path pair in the above is less than or equal to the hop count of the above-mentioned first service; when it is determined that the hop count of the s-th sub-path pair in the above-mentioned sorted sub-path pair is less than the hop count of the above-mentioned first service, The above-mentioned SDN controller determines that the number of hops of the sub-path pairs after the s-th sub-path pair is less than the number of hops of the above-mentioned first service, and the construction of the alternative forwarding path of the first service ends; when the above-mentioned SDN controller determines that the above-mentioned When the hop count of the s-th sub-path pair is less than or equal to the hop count of the first service, the SDN controller determines whether the cost of the s-th sub-path pair is less than the cost of the first service; When the cost of s is less than or equal to the cost of the first service, the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as a connection point to construct an alternative forwarding path for the first service. Then, the SDN controller continues to judge whether the hop count of the s+1th subpath pair is less than or equal to the hop count of the first service according to the above method; when the cost of the sth subpath pair is greater than the cost of the first service , the SDN controller directly jumps to the s+nth subpath pair, and performs the above operations on the s+nth subpath pair. Wherein, n is the number of sub-path pairs that are the same as the hops of the s-th sub-path pair. According to the above method, it is determined whether the additivity constraint of each subpath pair in the subpath pair set is less than or equal to the additivity constraint of the first service.

当上述可加性约束包括跳数和时延，且跳数为第一优先级，时延为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器判断上述第s个子路径对的时延是否小于上述第一业务的时延；当确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数；当上述第s个子路径对的时延大于上述第一业务的时延时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的跳数相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。When the above additivity constraints include the number of hops and the delay, and the number of hops is the first priority and the delay is the second priority, the SDN controller determines the sub-paths one by one according to the sequence of the sorted sub-path pairs Whether the hop count of each subpath pair in the set is less than or equal to the hop count of the first service; when it is determined that the hop count of the s-th subpath pair in the sorted subpath pair is less than the hop count of the first service When the above-mentioned SDN controller determines that the hops of the sub-path pairs after the s-th sub-path pair are all less than the hops of the above-mentioned first service, the construction of the alternative forwarding path for the first service ends; when the above-mentioned SDN controller When it is determined that the hop count of the s-th sub-path pair is less than or equal to the hop count of the first service, the SDN controller determines whether the delay of the s-th sub-path pair is less than the delay of the first service; The delay of the s sub-path pairs is less than or equal to the delay of the first service, and the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as the connection points to construct the alternative of the first service. forwarding path. Then, the SDN controller continues to judge whether the hop count of the s+1th subpath pair is less than or equal to the hop count of the first service according to the above method; when the delay of the sth subpath pair is greater than the first service Delay, the SDN controller directly jumps to the s+nth sub-path pair, and performs the above operations on the s+nth sub-path pair. Wherein, n is the number of sub-path pairs that are the same as the hops of the s-th sub-path pair. According to the above method, it is determined whether the additivity constraint of each subpath pair in the subpath pair set is less than or equal to the additivity constraint of the first service.

当上述可加性约束包括时延和代价，且时延为第一优先级，代价为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的时延是否小于或者等于上述第一业务的时延；当确定上述排序后的子路径对中的第s个子路径对的时延小于上述第一业务的时延时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的时延均小于上述第一业务的时延，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器判断上述第s个子路径对的代价是否小于上述第一业务的代价；当确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的时延是否小于或者等于上述第一业务的时延；当上述第s个子路径对的代价大于上述第一业务的代价时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的时延相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。When the above additivity constraints include delay and cost, and the delay is the first priority and the cost is the second priority, the SDN controller determines the set of sub-path pairs one by one according to the sequence of the sorted sub-path pairs Whether the delay of each sub-path pair is less than or equal to the delay of the first service; when it is determined that the delay of the s-th sub-path pair in the sorted sub-path pair is less than the delay of the first service, The SDN controller determines that the delays of the sub-path pairs after the s-th sub-path pair are all smaller than the delay of the first service, and the construction of the alternative forwarding path for the first service ends; when the SDN controller determines that the above-mentioned The delay of the s-th sub-path pair is less than or equal to the delay of the first service, and the SDN controller determines whether the cost of the s-th sub-path pair is less than the cost of the first service; When the cost of s is less than or equal to the cost of the first service, the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as a connection point to construct an alternative forwarding path for the first service. Then, the SDN controller continues to judge whether the delay of the s+1th subpath pair is less than or equal to the delay of the first service according to the above method; when the cost of the sth subpath pair is greater than the cost of the first service , the SDN controller directly jumps to the s+nth subpath pair, and performs the above operations on the s+nth subpath pair. Wherein, n is the number of sub-path pairs with the same delay as the above-mentioned s-th sub-path pair. According to the above method, it is determined whether the additivity constraint of each subpath pair in the subpath pair set is less than or equal to the additivity constraint of the first service.

当上述可加性约束包括跳数、时延和代价，且跳数为第一优先级、时延为第二优先级，代价为第三优先级时，上述上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的时跳数，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器判断上述第s个子路径对的时延是否小于或者等于上述第一业务的时延；当确定第s个子路径对的时延大于上述第一业务的时延时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为排序在上述s个子路径之后的且与该第s个子路径对的时延相同的子路径对的个数。当上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器判断上述第s个子路径对的代价是否小于或者等于上述第一业务的代价；当确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。当确定上述第s个子路径对的代价大于上述第一业务的代价时，上述SDN控制器直接跳转至第s+n’个子路径对，并对第s+n’个子路径对进行上述操作，其中，n’为排序在第s个子路径对之后的且跳数和时延均与该第s个子路径对相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。When the above additivity constraints include the number of hops, the delay and the cost, and the number of hops is the first priority, the delay is the second priority, and the cost is the third priority, the above-mentioned SDN controller according to the sorted child In the order of the path pairs, judge one by one whether the hop count of each subpath pair in the above subpath pair set is less than or equal to the hop count of the above first service; when determining the s th subpath pair in the above sorted subpath pair When the number of hops is less than the number of hops of the first service, the SDN controller determines that the number of hops of sub-path pairs after the s-th sub-path pair is less than the number of hops of the first service, and the alternative forwarding of the first service The construction of the path is completed; when it is determined that the hop number of the s-th sub-path pair is less than or equal to the hop number of the first service, the SDN controller determines whether the delay of the s-th sub-path pair is less than or equal to the first service. When it is determined that the delay of the s-th sub-path pair is greater than the time delay of the first service, the SDN controller directly jumps to the s+n-th sub-path pair, and performs the s+n-th sub-path pair. the above operation. Wherein, n is the number of sub-path pairs that are ranked after the above-mentioned s sub-paths and have the same delay as the s-th sub-path pair. When the delay of the s-th sub-path pair is less than or equal to the delay of the first service, the SDN controller determines whether the cost of the s-th sub-path pair is less than or equal to the cost of the first service; When the cost of the s sub-path pairs is less than or equal to the cost of the first service, the SDN controller uses the terminating forwarding nodes of the two sub-paths in the s-th sub-path pair as a connection point to construct an alternative forwarding path for the first service. . Then, the SDN controller continues to judge whether the additivity constraint of the s+1th subpath pair is less than or equal to the additivity constraint of the first service according to the above method. When it is determined that the cost of the s-th sub-path pair is greater than the cost of the first service, the SDN controller directly jumps to the s+n'th sub-path pair, and performs the above operations on the s+n'-th sub-path pair, Wherein, n' is the number of sub-path pairs that are sorted after the s-th sub-path pair and have the same hop count and delay as the s-th sub-path pair. According to the above method, it is determined whether the additivity constraint of each subpath pair in the subpath pair set is less than or equal to the additivity constraint of the first service.

在一种可行的实施例中，当上述第s个子路径对的可加性约束小于或者等于上述第一业务的可加性约束时，且在以上述第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径之前，上述SDN控制器还需判断根据上述第s个子路径对得到备选转发路径是否成环；当确定根据第s个子路径对得到的备选转发路径成环时，上述SDN控制器不根据第s个子路径对构建备选转发路径；当确定根据第s个子路径对得到的备选转发路径不成环时，上述SDN控制器判断根据第s个子路径对得到的备选转发路径是否与已构建的备选转发路径重复；当确定根据第s个子路径对得到的备选转发路径与已构建的备选转发路径重复时，上述SDN控制器不根据上述第s个子路径对构建备选转发路径；当确定根据第s个子路径对得到的备选转发路径不与已构建的备选转发路径重复时，上述SDN控制器以上述第s个子路径对中的两条子路径的终止转发节点为连接点，构建备选转发路径。In a feasible embodiment, when the additivity constraint of the s-th sub-path pair is less than or equal to the additivity constraint of the first service, and the sum of the two sub-paths in the s-th sub-path pair is based on the The termination forwarding node is a connection point, and before constructing an alternative forwarding path for the first service, the SDN controller also needs to determine whether the alternative forwarding path obtained according to the s th sub-path pair is a loop; When the obtained alternative forwarding path forms a loop, the above-mentioned SDN controller does not construct an alternative forwarding path according to the s-th sub-path pair; when it is determined that the alternative forwarding path obtained according to the s-th sub-path pair does not form a loop, the above-mentioned SDN controller judges Whether the alternative forwarding path obtained according to the s-th sub-path pair is duplicated with the constructed alternative forwarding path; when it is determined that the alternative forwarding path obtained according to the s-th sub-path pair is duplicated with the constructed alternative forwarding path, the above SDN The controller does not construct an alternative forwarding path according to the above-mentioned s-th sub-path pair; when it is determined that the alternative forwarding path obtained according to the s-th sub-path pair does not duplicate the constructed alternative forwarding path, the above-mentioned SDN controller uses the above-mentioned s-th sub-path pair. The terminating forwarding nodes of the two subpaths in each subpath pair are connection points, and an alternative forwarding path is constructed.

需要指出的是，上述可加性约束包括但不限定于代价、时延和跳数。当可加性约束还包括其他参数时，上述SDN控制器按照上述方法进行判断并构建备选转发路径。It should be pointed out that the above additivity constraints include but are not limited to cost, delay and hop count. When the additivity constraint further includes other parameters, the above-mentioned SDN controller judges and constructs an alternative forwarding path according to the above-mentioned method.

需要指出的是，上述第s个子路径对为上述排序后的子路径对中的任一个子路径对。It should be noted that the above-mentioned s-th sub-path pair is any one of the above-mentioned sorted sub-path pairs.

通过对上述子路径对集合中的子路径对继续排序，然后判断排序后的子路径对是否满足上述第一业务的需求的方法，可以提高根据子路径对集合构建上述第一业务的备选转发路径集合的效率。By continuing to sort the sub-path pairs in the above-mentioned sub-path pair set, and then judging whether the sorted sub-path pairs meet the requirements of the above-mentioned first service, the alternative forwarding of constructing the above-mentioned first service according to the set of sub-path pairs can be improved. Efficiency of Path Collections.

按照上述方法，上述SDN控制器根据第二业务的第一子路径集合和第二子路径集合，计算得到第二业务的备选转发路径集合。According to the above method, the SDN controller calculates and obtains the set of alternative forwarding paths for the second service according to the first set of sub-paths and the set of second sub-paths of the second service.

S203、SDN控制器分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。S203. The SDN controller selects the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service, respectively. Destination forwarding path.

在一种可行的实施例中，上述业务信息还包括业务优先级，上述SDN控制器根据业务优先级和所需带宽对上述第一业务和第二业务进行排序；其中，业务优先级为第一排序优先级，所需带宽为第二排序优先级，即上述SDN控制器先根据业务优先级对上述第一业务和第二业务排序，业务优先级高的业务排序靠前；当第一业务和第二业务的业务优先级相同时，则上述SDN控制器根据业务的所需带宽对上述第一业务和第二业务进行排序，所需带宽大的业务排序靠前。In a feasible embodiment, the service information further includes a service priority, and the SDN controller sorts the first service and the second service according to the service priority and the required bandwidth; wherein, the service priority is the first Sorting priority, the required bandwidth is the second sorting priority, that is, the SDN controller first sorts the first service and the second service according to the service priority, and the service with a higher service priority is ranked first; when the first service and the second service are sorted first; When the service priorities of the second services are the same, the SDN controller sorts the first service and the second service according to the required bandwidth of the services, and the service with the larger required bandwidth is ranked first.

假设上述SDN控制器根据业务优先级和所需带宽对上述第一业务和第二业务排序得到的结果为：第一业务排序在上述第二业务之前。Assuming that the above-mentioned SDN controller sorts the above-mentioned first service and the second service according to the service priority and the required bandwidth, the result obtained is that the above-mentioned first service is ordered before the above-mentioned second service.

在一种可行的实施例中，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：In a feasible embodiment, the target forwarding path and When the target forwarding path of the second service is selected, the target forwarding path of the first service is selected from the set of alternative forwarding paths of the first service, including:

根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;

根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;

从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.

具体地，上述第一业务的备选转发路径集合中包括一条或者多条备选转发路径。当上述第一业务的备选转发路径集合中包括一条备选转发路径时，上述SDN控制器直接获取该备选转发路径的剩余带宽，并判断该备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽；当确定该备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器确定该备选转发路径为上述第一业务的目标转发路径；当确定该备选转发路径的剩余带宽小于上述第一业务的所需带宽时，上述SDN控制器确定无法获取第一业务的目标转发路径。Specifically, the set of alternative forwarding paths for the first service includes one or more alternative forwarding paths. When the set of alternative forwarding paths for the first service includes an alternative forwarding path, the SDN controller directly obtains the remaining bandwidth of the alternative forwarding path, and determines whether the remaining bandwidth of the alternative forwarding path is greater than or equal to the above The required bandwidth of the first service; when it is determined that the remaining bandwidth of the alternative forwarding path is greater than or equal to the required bandwidth of the first service, the SDN controller determines that the alternative forwarding path is the target forwarding path of the first service ; when it is determined that the remaining bandwidth of the alternative forwarding path is less than the required bandwidth of the first service, the SDN controller determines that the target forwarding path of the first service cannot be obtained.

需要指出的是，上述SDN控制器分别从上述第一业务的备选转发路径集合和第二业务的备选转发路径集合中选取出上述第一业务的目标转发路径和第二业务的目标转发路径是串行进行的，即上述SDN控制器先从上述第一业务的备选转发路径集合中选取出第一业务的目标转发路径，再从上述第二业务的备选转发路径集合中选取出该第二业务的目标转发路径。并且第一业务的目标转发路径和第二业务的目标转发路径存在相同链路的情形，因此在从备选转发路径集合中选取出目标转发路径时，需要考虑备选转发路径的剩余带宽，备选转发路径的剩余带宽为该备选转发路径的链路的剩余带宽的最小值。It should be noted that the SDN controller selects the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service, respectively. It is carried out in series, that is, the SDN controller first selects the target forwarding path of the first service from the set of alternative forwarding paths of the first service, and then selects the target forwarding path of the first service from the set of alternative forwarding paths of the second service. The target forwarding path of the second service. In addition, the target forwarding path of the first service and the target forwarding path of the second service have the same link. Therefore, when selecting the target forwarding path from the set of alternative forwarding paths, the remaining bandwidth of the alternative forwarding path needs to be considered. The remaining bandwidth of the selected forwarding path is the minimum value of the remaining bandwidth of the links of the alternate forwarding path.

当上述第一业务的备选转发路径集合中包括多条备选转发路径时，上述SDN控制器根据预设公式计算得到上述第一业务的多条备选转发路径中每条备选转发的得分。When the set of alternative forwarding paths for the first service includes multiple alternative forwarding paths, the SDN controller calculates, according to a preset formula, a score for each alternative forwarding among the multiple alternative forwarding paths for the first service .

其中，该预设公式可为：w_i＝∑_j1/b_i,j；w_i为第一业务的备选转发路径集合中排序后的多条备选转发路径中的第i条备选转发路径的得分，所述b_i,j为该第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the preset formula may be: w_i =∑_j 1/b_i,j ; w_i is the i-th candidate in the sequenced multiple candidate forwarding paths in the set of candidate forwarding paths of the first service The score of the forwarding path, where b_i,j is the remaining bandwidth of the jth link in the ith candidate forwarding path.

上述SDN控制器然后根据每条备选转发路径的得分，对上述第一业务的多条备选转发路径进行排序，以得到排序后的多条备选转发路径；其中，得分小的备选转发路径的排序靠前。然后按照排序后的多条备选转发路径的顺序，从该排序后的多条备选转发路径中选取出上述第一业务的目标转发路径。当排序在第q条备选转发路径之前的备选转发路径之前的备选转发路径的剩余带宽均小于上述第一业务的所需带宽时，上述SDN控制器获取上述第q条备选转发路径的剩余带宽，并判断第q条备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽时，当上述第q条备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽，则上述SDN控制器确定上述第q条备选转发路径为上述第一业务的目标转发路径；当上述第q条备选转发路径的剩余带宽小于上述第一业务的所需带宽，上述SDN控制器继续获取上述第q+1条备选转发路径的剩余带宽，并重复执行上述过程。The above-mentioned SDN controller then sorts the multiple alternative forwarding paths of the first service according to the score of each alternative forwarding path, so as to obtain a plurality of sorted alternative forwarding paths; wherein, the alternative forwarding with a smaller score is the forwarding path. Paths are sorted first. Then, according to the order of the multiple alternative forwarding paths after sorting, the target forwarding path of the first service is selected from the multiple alternative forwarding paths after sorting. When the remaining bandwidths of the alternative forwarding paths before the alternative forwarding paths ranked before the q-th alternative forwarding path are all smaller than the required bandwidth of the first service, the SDN controller obtains the q-th alternative forwarding path When judging whether the remaining bandwidth of the q-th alternative forwarding path is greater than or equal to the required bandwidth of the first service, when the remaining bandwidth of the q-th alternative forwarding path is greater than or equal to the first service required bandwidth, the SDN controller determines that the qth alternative forwarding path is the target forwarding path of the first service; when the remaining bandwidth of the qth alternative forwarding path is less than the required bandwidth of the first service, The above-mentioned SDN controller continues to obtain the remaining bandwidth of the above-mentioned q+1th alternative forwarding path, and repeats the above-mentioned process.

当上述第q条备选转发路径为上述第一业务的备选转发路径集中的最后一条备选转发路径时，上述SDN控制器则确定上述备选转发路径集合中的备选转发路径的剩余带宽均小于上述第一业务的所需带宽，即上述SDN控制器从上述第一业务的备选转发路径集合中未获取目标转发路径。When the q-th alternative forwarding path is the last alternative forwarding path in the set of alternative forwarding paths for the first service, the SDN controller determines the remaining bandwidth of the alternative forwarding paths in the set of alternative forwarding paths are smaller than the required bandwidth of the first service, that is, the SDN controller does not obtain the target forwarding path from the set of alternative forwarding paths for the first service.

按照上述方法，上述SDN控制器从上述第二业务的备选转发路径集合中获取第二业务的目标转发路径。According to the above method, the SDN controller obtains the target forwarding path of the second service from the set of candidate forwarding paths for the second service.

需要指出的是，上述SDN控制器对业务进行排序，并根据业务排序的顺序为上述业务从其备选转发路径集合中选取出目标转发路径。It should be pointed out that the above-mentioned SDN controller sorts the services, and selects a target forwarding path for the above-mentioned service from the set of alternative forwarding paths for the above-mentioned services according to the order of the service sorting.

在一种可行的实施例中，当上述SDN控制器从上述第一业务的备选转发路径集合中未获取上述第一业务的目标转发路径，则上述SDN控制器重复执行上述步骤S202和S203所述的方法，直至获取上述第一业务的目标转发路径或者重复执行上述步骤S202和S203所述方法的次数超过预设次数。In a feasible embodiment, when the SDN controller does not obtain the target forwarding path of the first service from the set of alternative forwarding paths for the first service, the SDN controller repeats the execution of steps S202 and S203 above. The method described above is performed until the target forwarding path of the first service is acquired or the number of times the method described in steps S202 and S203 is repeatedly performed exceeds a preset number of times.

S204、SDN控制器将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。S204. The SDN controller sends the target forwarding path of the first service and the target forwarding path of the second service to the forwarding node.

具体地，上述SDN控制器将上述第一业务的目标转发路径和上述第二业务的目标转发路径发送至上述网路拓扑结构中的转发节点，以使转发节点构建上述第一业务的目标转发路径和第二业务的目标转发路径。Specifically, the SDN controller sends the target forwarding path of the first service and the target forwarding path of the second service to the forwarding node in the network topology structure, so that the forwarding node constructs the target forwarding path of the first service and the target forwarding path of the second service.

可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和SRLG，提升网络的吞吐率。It can be seen that in the solution of the embodiment of the present invention, according to the network topology information and service information and the breadth-first search algorithm, multiple sub-paths are quickly calculated from the bidirectional path, and then multiple alternative forwarding services are constructed according to the multiple sub-paths. path, multiple alternative forwarding paths can be obtained in one calculation; and when constructing alternative forwarding paths, the additivity constraints of services and the additivity constraints of alternative forwarding paths, such as cost, delay, and hop count, have been considered Therefore, when selecting a target forwarding path for a service, there are multiple alternative forwarding paths to choose from, which greatly reduces the probability of bandwidth conflict, and decouples bandwidth constraints in a statistical sense, so that alternative forwarding paths for multiple services can be parallelized. calculation to improve the efficiency of calculating alternative forwarding paths. When multiple sub-paths are calculated from each direction according to the breadth-first search algorithm, each forwarding node in the network topology is traversed only once, which can greatly improve the efficiency of calculating multiple alternative forwarding paths, and obtain multiple backup paths. The forwarding paths are selected as separated as possible. Score multiple alternative forwarding paths according to the remaining bandwidth status of each link in the network topology, and sort them according to the scores, and determine the target forwarding path of the service according to the sequence of the sorted alternative forwarding paths. At this time, the service can be considered. Additivity constraint, which can determine the target forwarding path for each service as far as possible according to the direction of bandwidth load balancing of each link in the network topology, and the multiple alternative forwarding paths of the service are separated as much as possible, so that the determined target forwarding The path naturally satisfies the separation of active and standby and SRLG, which improves the throughput of the network.

参见图5，图5为本发明实施例提供的另一种转发路径的计算方法的流程示意图。如图5所示，该方法包括：Referring to FIG. 5, FIG. 5 is a schematic flowchart of another method for calculating a forwarding path according to an embodiment of the present invention. As shown in Figure 5, the method includes:

S501、SDN控制器获取所述网络拓扑信息结构信息、第一业务信息和第二业务信息。S501. The SDN controller acquires the network topology information structure information, the first service information and the second service information.

其中，所述第一业务和第二业务为K条业务中任意的两条，所述K为大于1的整数；上述K条业务均为上述SDN控制器待转发的业务。The first service and the second service are any two of the K services, and the K is an integer greater than 1; the K services are all services to be forwarded by the SDN controller.

其中，上述网络拓扑结构信息包括转发节点的数量和任两个转发节点之间的链路信息。该链路状态信息包括带宽和可加性约束。The above-mentioned network topology information includes the number of forwarding nodes and link information between any two forwarding nodes. The link state information includes bandwidth and additivity constraints.

进一步地，上述可加性约束包括但不限定于代价、时延和跳数。Further, the above additivity constraints include but are not limited to cost, delay and hop count.

上述业务信息包括但不限定于起始转发节点、终止转发节点、所需带宽、代价、时延和跳数。The above service information includes, but is not limited to, the initial forwarding node, the terminating forwarding node, required bandwidth, cost, delay and hop count.

S502、SDN控制器根据广度搜索算法分别从第一业务的起始转发节点沿第一方向搜索和第一业务的终止转发节点沿第二方向搜索，以得到第一业务的第一子路径集合和第二子路径集合。S502. According to the breadth search algorithm, the SDN controller searches from the start forwarding node of the first service along the first direction and the terminating forwarding node of the first service along the second direction to obtain the first subpath set of the first service and The second set of subpaths.

其中，上述第一方向为上述第一业务的起始转发节点到其终止转发节点的方向，第二方向为上述第一业务的终止转发节点到其起始转发节点的方向。The first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node, and the second direction is the direction from the terminating forwarding node of the first service to the starting forwarding node.

上述第一业务的第一子路径集合包括一条或者多条第一子路径，第二子路径集合包括一套或者多条第二子路径。且上述第一子路径集合中的任一条第一子路径s1的起始转发节点为上述第一业务的起始转发节点，上述第二子路径集合中的任一条第一子路径s2的起始转发节点为上述第一业务的终止转发节点。The first sub-path set of the first service includes one or more first sub-paths, and the second sub-path set includes one or more second sub-paths. And the initial forwarding node of any first sub-path s1 in the above-mentioned first sub-path set is the initial forwarding node of the above-mentioned first service, and the initial forwarding node of any first sub-path s2 in the above-mentioned second sub-path set The forwarding node is the terminating forwarding node of the above-mentioned first service.

其中，上述第一子路径s1和第二子路径s2的带宽均大于或者等于上述第一业务的所需带宽，上述第一子路径s1和第二子路径s2的可加性约束均未超过上述第一业务的可加性约束。Wherein, the bandwidths of the first subpath s1 and the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the additivity constraints of the first subpath s1 and the second subpath s2 do not exceed the above Additivity constraint of the first service.

进一步地，上述第一子路径s1的可加性约束未超过上述第一业务的可加性约束具体包括：上述第一子路径s1的代价小于或等于上述第一业务的代价上限、且该第一子路径s1的延时小于或等于上述第一业务的时延，且该第一子路径s1的跳数小于或等于上述第一业务的跳数；同理，上述第二子路径s2的可加性约束未超过上述第一业务的可加性约束具体包括：上述第二子路径s2的代价小于或等于上述第一业务的代价上限、且该第二子路径s2的延时小于或等于上述第一业务的时延，且该第二子路径s2的跳数小于或等于上述第一业务的跳数。Further, the additivity constraint of the above-mentioned first sub-path s1 does not exceed the additivity constraint of the above-mentioned first service specifically includes: the cost of the above-mentioned first sub-path s1 is less than or equal to the upper limit of the cost of the above-mentioned first service, and the first sub-path s1. The delay of a sub-path s1 is less than or equal to the delay of the above-mentioned first service, and the number of hops of the first sub-path s1 is less than or equal to the number of hops of the above-mentioned first service; similarly, the above-mentioned second sub-path s2 can be The additive constraint does not exceed the additivity constraint of the above-mentioned first service specifically includes: the cost of the above-mentioned second sub-path s2 is less than or equal to the upper limit of the cost of the above-mentioned first service, and the delay of the second sub-path s2 is less than or equal to the above-mentioned The delay of the first service, and the number of hops of the second sub-path s2 is less than or equal to the number of hops of the first service.

具体地，当从第一方向搜索到转发节点t2时，上述SDN控制器获取该转发节点t2与前一个搜索到的转发节点t1之间链路的带宽，代价、时延和跳数与第一子路径p_t1的带宽、代价、时延和跳数，该第一子路径p_t1为起始转发节点为上述第一业务的起始转发节点和终止转发节点为上述转发节点t1的路径。上述SDN控制器将上述转发节点t1和转发节点t2之间链路的代价、时延和跳数分别与上述第一子路径p_t1的代价、时延和跳数进行累加，得到子路径p_t2的代价时延和跳数。当该子路径p_t2的代价、时延和跳数均未超过上述第一业务的代价、时延和跳数，且上述转发节点t1和转发节点t2之间链路的带宽大于或者等于上述第第一业务的所需带宽时，则该子路径p_t2为上述第一子路径。Specifically, when the forwarding node t2 is searched from the first direction, the above-mentioned SDN controller obtains the bandwidth of the link between the forwarding node t2 and the previously searched forwarding node t1, and the cost, delay and hop count are the same as the first Bandwidth, cost, delay and hop count of the sub-path p_t1 , the first sub-path p_t1 is a path where the starting forwarding node is the starting forwarding node of the first service and the terminating forwarding node is the forwarding node t1. The above SDN controller accumulates the cost, delay and hop count of the link between the forwarding node t1 and the forwarding node t2 and the cost, delay and hop count of the first sub-path p_t1 , respectively, to obtain the sub-path p_t2 The cost delay and hop count. When the cost, delay and number of hops of the sub-path p_{t2 do} not exceed the cost, delay and number of hops of the first service, and the bandwidth of the link between the forwarding node t1 and the forwarding node t2 is greater than or equal to the first service When the required bandwidth of the first service is reached, the sub-path_pt2 is the above-mentioned first sub-path.

当上述子路径p_t2的代价、时延和跳数中的任一项大于上述第一业务的代价上限、时延上限和跳数上限，或者上述转发节点t1和转发节点t2之间链路的带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器则跳过上述转发节点t2，搜索下一个转发节点t3。When any one of the cost, delay and hop count of the sub-path pt2 is greater than the cost upper limit, delay limit and hop count limit of the first service, or the link between the forwarding node t1 and the forwarding node_t2 When the bandwidth is greater than or equal to the required bandwidth of the first service, the SDN controller skips the forwarding node t2 and searches for the next forwarding node t3.

举例说明，参见图6，图6为本发明实施例提供的一种网络拓扑结构示意图。如图6所示，上述第一业务的起始转发节点为转发节点1，终止转发节点为转发节点10。假设上述第一业务的代价上限为5，时延上限为6，所需带宽为30。上述SDN控制器从上述转发节点1进行搜索，搜索到转发节点3时，获取转发节点3与转发节点1之间链路的代价、时延和带宽，即2,2,80，确定该链路满足上述第一业务的需求，从转发节点3继续搜索，当搜索到转发节点5时，获取转发节点3和转发节点6之间链路的代价、时延和带宽，即4,2,80，根据转发节点1与转发节点3之间的链路信息和转发节点3和转发节点5之间的链路信息确定子路径1-3-5的代价、时延和带宽分别为6,4,70，由于上述第一业务的代价上限为5可知，该子路径1-3-5不能满足上述第一业务的需求，因此上述SDN控制器跳过转发节点5继续搜索；当搜索到转发节点6时，获取转发节点3和转发节点5之间链路的代价、时延和带宽，即1,2,80。根据转发节点1与转发节点3之间的链路信息和转发节点3和转发节点6之间的链路信息确定子路径1-3-6的代价、时延和带宽分别为3,4,80，由于该子路径1-3-6的时延和代价均小于上述第一业务的时延上限和代价上限，且该子路径1-3-6的带宽大于上述第一业务的所需带宽，故子路径1-3-6为上述第一业务的第一子路径。上述SDN控制器从转发节点6继续搜索。For example, referring to FIG. 6 , FIG. 6 is a schematic diagram of a network topology structure according to an embodiment of the present invention. As shown in FIG. 6 , the starting forwarding node of the first service is forwardingnode 1 , and the terminating forwarding node is forwardingnode 10 . It is assumed that the upper limit of the cost of the above-mentioned first service is 5, the upper limit of the delay is 6, and the required bandwidth is 30. The above-mentioned SDN controller searches from the above-mentionedforwarding node 1. When the forwardingnode 3 is searched, it obtains the cost, delay and bandwidth of the link between the forwardingnode 3 and the forwardingnode 1, that is, 2, 2, and 80, and determines the link. To meet the requirements of the first service above, continue searching from forwardingnode 3. When forwardingnode 5 is found, obtain the cost, delay, and bandwidth of the link between forwardingnode 3 and forwardingnode 6, that is, 4, 2, and 80. According to the link information between forwardingnode 1 and forwardingnode 3 and the link information between forwardingnode 3 and forwardingnode 5, it is determined that the cost, delay and bandwidth of sub-paths 1-3-5 are 6, 4, and 70, respectively. , since the upper limit of the cost of the above-mentioned first service is 5, it can be seen that the sub-path 1-3-5 cannot meet the requirements of the above-mentioned first service, so the above-mentioned SDN controllerskips forwarding node 5 and continues to search; when forwardingnode 6 is searched for , obtain the cost, delay and bandwidth of the link between forwardingnode 3 and forwardingnode 5, that is, 1, 2, and 80. According to the link information between forwardingnode 1 and forwardingnode 3 and the link information between forwardingnode 3 and forwardingnode 6, it is determined that the cost, delay and bandwidth of sub-paths 1-3-6 are 3, 4, and 80, respectively. , since the delay and cost of the subpath 1-3-6 are both smaller than the upper limit of the delay and the upper limit of the cost of the first service, and the bandwidth of the subpath 1-3-6 is greater than the required bandwidth of the first service, Therefore, the sub-path 1-3-6 is the first sub-path of the above-mentioned first service. The above-mentioned SDN controller continues the search from the forwardingnode 6 .

按照上述方法，上述SDN控制器遍历上述网络拓扑结构中的每个转发节点，得到第一业务的第一子路径集合和第二子路径集合。在上述遍历过程中，上述网络拓扑结构中的每个转发节点只遍历一次。According to the above method, the above-mentioned SDN controller traverses each forwarding node in the above-mentioned network topology structure, and obtains the first sub-path set and the second sub-path set of the first service. In the above traversal process, each forwarding node in the above network topology structure is traversed only once.

S503、SDN控制器根据广度搜索算法分别从第二业务的起始转发节点沿第一方向搜索和第二业务的终止转发节点沿第二方向搜索，以得到第二业务的第一子路径集合和第二子路径集合。S503. According to the breadth search algorithm, the SDN controller searches from the start forwarding node of the second service along the first direction and the terminating forwarding node of the second service along the second direction, so as to obtain the first subpath set of the second service and The second set of subpaths.

在此需要说明的是，上述SDN控制器搜索得到第二业务的第一子路径集合和第二子路径集合的具体过程可参见上述步骤S502的相关描述，在此不再叙述。It should be noted here that the specific process of obtaining the first sub-path set and the second sub-path set of the second service by the foregoing SDN controller may refer to the relevant description of the foregoing step S502, which will not be described here.

S504、SDN控制器从第一业务的第一子路径集合和第二子路径集合中选取出子路径对集合。S504. The SDN controller selects a sub-path pair set from the first sub-path set and the second sub-path set of the first service.

其中，上述子路径对集合包括一个或者多个子路径对，该子路径对集合中每个子路径对的两条子路径分别属于上述第一业务的第一子路径集合和第二子路径集合，且上述每个子路径对的两条子路径具有相同的终止转发节点。The above-mentioned sub-path pair set includes one or more sub-path pairs, and the two sub-paths of each sub-path pair in the sub-path pair set belong to the first sub-path set and the second sub-path set of the first service, respectively, and the above-mentioned Both subpaths of each subpath pair have the same terminating forwarding node.

S505、SDN控制器对第一业务的子路径对集合中的子路径对进行排序，以得到排序后的子路径对。S505. The SDN controller sorts the sub-path pairs in the set of sub-path pairs of the first service to obtain the sorted sub-path pairs.

在此需要说明的是，上述SDN控制器对上述子路径对集合中的子路径对进行排序的过程可参见上述步骤S202的相关描述，在此不再叙述。It should be noted here that the process of sorting the sub-path pairs in the sub-path pair set by the above-mentioned SDN controller may refer to the relevant description of the above-mentioned step S202, which will not be described here.

S506、SDN控制器根据排序后的子路径对，获取第一业务的备选转发路径集合。S506. The SDN controller acquires a set of candidate forwarding paths for the first service according to the sorted sub-path pairs.

其中，上述第一业务的备选转发路径集合包括一条或者多条备选转发路径。Wherein, the set of alternative forwarding paths for the first service includes one or more alternative forwarding paths.

在此需要说明的是，上述SDN控制器对上述子路径对集合中的子路径对进行排序和根据排序后的子路径对获取第一业务的备选转发路径集合的过程可参见上述步骤S202的相关描述，在此不再叙述。It should be noted here that the process of sorting the sub-path pairs in the sub-path pair set by the above-mentioned SDN controller and obtaining the set of alternative forwarding paths of the first service according to the sorted sub-path pairs may refer to the above step S202. Related descriptions are not described here.

按照步骤S402-S406所描述的方法，上述SDN控制器并行计算得到上述第一业务中的备选转发路径集合和第二业务的备选转发路径集合。According to the method described in steps S402-S406, the SDN controller obtains the set of alternative forwarding paths in the first service and the set of alternative forwarding paths of the second service by parallel calculation.

S507、SDN控制器分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。S507. The SDN controller selects the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service, respectively. Destination forwarding path.

具体地，上述第一业务的备选转发路径集合中包括一条或者多条备选转发路径。当上述第一业务的备选转发路径集合中包括一条备选转发路径时，上述SDN控制器直接该备选转发路径的剩余带宽，并判断该备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽；当确定该备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器确定该备选转发路径为上述第一业务的目标转发路径；当确定该备选转发路径的剩余带宽小于上述第一业务的所需带宽时，上述SDN控制器确定无法获取第一业务的目标转发路径。Specifically, the set of alternative forwarding paths for the first service includes one or more alternative forwarding paths. When the set of alternative forwarding paths for the first service includes an alternative forwarding path, the SDN controller directly determines the remaining bandwidth of the alternative forwarding path, and determines whether the remaining bandwidth of the alternative forwarding path is greater than or equal to the above-mentioned first forwarding path. A required bandwidth of a service; when it is determined that the remaining bandwidth of the alternative forwarding path is greater than or equal to the required bandwidth of the first service, the SDN controller determines that the alternative forwarding path is the target forwarding path of the first service; When it is determined that the remaining bandwidth of the alternative forwarding path is less than the required bandwidth of the first service, the SDN controller determines that the target forwarding path of the first service cannot be obtained.

需要指出的是，上述SDN控制器分别从上述第一业务的备选转发路径集合和第二业务的备选转发路径集合中选取出上述第一业务的目标转发路径和第二业务的目标转发路径是串行进行的，即上述SDN控制器先从上述第一业务的备选转发路径集合中选取出第一业务的目标转发路径，再从上述第二业务的备选转发路径集合中选取出该第二业务的目标转发路径。并且第一业务的目标转发路径和第二业务的目标转发路径存在相同链路的情形，因此在从备选转发路径集合中选取出目标转发路径时，需要考虑备选转发路径的剩余带宽，备选转发路径的剩余带宽为该备选转发路径的链路的剩余带宽的最小值。It should be noted that the SDN controller selects the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service, respectively. It is carried out in series, that is, the SDN controller first selects the target forwarding path of the first service from the set of alternative forwarding paths of the first service, and then selects the target forwarding path of the first service from the set of alternative forwarding paths of the second service. The target forwarding path of the second service. In addition, the target forwarding path of the first service and the target forwarding path of the second service have the same link. Therefore, when selecting the target forwarding path from the set of alternative forwarding paths, the remaining bandwidth of the alternative forwarding path needs to be considered. The remaining bandwidth of the selected forwarding path is the minimum value of the remaining bandwidth of the links of the alternate forwarding path.

当上述第一业务的备选转发路径集合中包括多条备选转发路径时，上述SDN控制器根据预设公式计算得到上述第一业务的多条备选转发路径中每条备选转发的得分。When the set of alternative forwarding paths for the first service includes multiple alternative forwarding paths, the SDN controller calculates, according to a preset formula, a score for each alternative forwarding among the multiple alternative forwarding paths for the first service .

其中，该预设公式可为：w_i＝∑_j1/b_i,j；w_i为第一业务的备选转发路径集合中排序后的多条备选转发路径中的第i条备选转发路径的得分，所述b_i,j为该第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the preset formula may be: w_i =∑_j 1/b_i,j ; w_i is the i-th candidate in the sequenced multiple candidate forwarding paths in the set of candidate forwarding paths of the first service The score of the forwarding path, where b_i,j is the remaining bandwidth of the jth link in the ith candidate forwarding path.

上述SDN控制器然后根据每条备选转发路径的得分，对上述第一业务的多条备选转发路径进行排序，以得到排序后的多条备选转发路径；其中，得分小的备选转发路径的排序靠前。然后按照排序后的多条备选转发路径的顺序，从该排序后的多条备选转发路径中选取出上述第一业务的目标转发路径。当排序在第q条备选转发路径之前的备选转发路径之前的备选转发路径的剩余带宽均小于上述第一业务的所需带宽时，上述SDN控制器获取上述第q条备选转发路径的剩余带宽，并判断第q条备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽时，当上述第q条备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽，则上述SDN控制器确定上述第q条备选转发路径为上述第一业务的目标转发路径；当上述第q条备选转发路径的剩余带宽小于上述第一业务的所需带宽，上述SDN控制器继续获取上述第q+1条备选转发路径的剩余带宽，并重复执行上述过程。The above-mentioned SDN controller then sorts the multiple alternative forwarding paths of the first service according to the score of each alternative forwarding path, so as to obtain a plurality of sorted alternative forwarding paths; wherein, the alternative forwarding with a smaller score is the forwarding path. Paths are sorted first. Then, according to the order of the multiple alternative forwarding paths after sorting, the target forwarding path of the first service is selected from the multiple alternative forwarding paths after sorting. When the remaining bandwidths of the alternative forwarding paths before the alternative forwarding paths ranked before the q-th alternative forwarding path are all smaller than the required bandwidth of the first service, the SDN controller obtains the q-th alternative forwarding path When judging whether the remaining bandwidth of the q-th alternative forwarding path is greater than or equal to the required bandwidth of the first service, when the remaining bandwidth of the q-th alternative forwarding path is greater than or equal to the first service required bandwidth, the SDN controller determines that the qth alternative forwarding path is the target forwarding path of the first service; when the remaining bandwidth of the qth alternative forwarding path is less than the required bandwidth of the first service, The above-mentioned SDN controller continues to obtain the remaining bandwidth of the above-mentioned q+1th alternative forwarding path, and repeats the above-mentioned process.

当上述第q条备选转发路径为上述第一业务的备选转发路径集中的最后一条备选转发路径时，上述SDN控制器则确定上述备选转发路径集合中的备选转发路径的剩余带宽均小于上述第一业务的所需带宽，即上述SDN控制器从上述第一业务的备选转发路径集合中未获取目标转发路径。When the q-th alternative forwarding path is the last alternative forwarding path in the set of alternative forwarding paths for the first service, the SDN controller determines the remaining bandwidth of the alternative forwarding paths in the set of alternative forwarding paths are smaller than the required bandwidth of the first service, that is, the SDN controller does not obtain the target forwarding path from the set of alternative forwarding paths for the first service.

按照上述方法，上述SDN控制器从上述第二业务的备选转发路径集合中获取第二业务的目标转发路径。According to the above method, the SDN controller obtains the target forwarding path of the second service from the set of candidate forwarding paths for the second service.

需要指出的是，上述SDN控制器对业务进行排序，并根据业务排序的顺序为上述业务从其备选转发路径集合中选取出目标转发路径。It should be pointed out that the above-mentioned SDN controller sorts the services, and selects a target forwarding path for the above-mentioned service from the set of alternative forwarding paths for the above-mentioned services according to the order of the service sorting.

在一种可行的实施例中，当上述SDN控制器从上述第一业务的备选转发路径集合中未获取上述第一业务的目标转发路径，则上述SDN控制器重复执行上述步骤S402-S407所述的方法，直至获取上述第一业务的目标转发路径或者重复执行上述步骤S402-S407所述方法的次数超过预设次数。In a feasible embodiment, when the SDN controller does not obtain the target forwarding path of the first service from the set of alternative forwarding paths for the first service, the SDN controller repeats the execution of steps S402-S407. The method described above is performed until the target forwarding path of the first service is acquired or the number of times the method described in steps S402-S407 is repeatedly performed exceeds a preset number of times.

S508、SDN控制器将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。S508. The SDN controller sends the target forwarding path of the first service and the target forwarding path of the second service to the forwarding node.

具体地，上述SDN控制器将上述第一业务的目标转发路径和上述第二业务的目标转发路径发送至上述网路拓扑结构中的转发节点，以使转发节点构建上述第一业务的目标转发路径和第二业务的目标转发路径。Specifically, the SDN controller sends the target forwarding path of the first service and the target forwarding path of the second service to the forwarding node in the network topology structure, so that the forwarding node constructs the target forwarding path of the first service and the target forwarding path of the second service.

可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和SRLG，提升网络的吞吐率。It can be seen that in the solution of the embodiment of the present invention, according to the network topology information and service information and the breadth-first search algorithm, multiple sub-paths are quickly calculated from the bidirectional path, and then multiple alternative forwarding services are constructed according to the multiple sub-paths. path, multiple alternative forwarding paths can be obtained in one calculation; and when constructing alternative forwarding paths, the additivity constraints of services and the additivity constraints of alternative forwarding paths, such as cost, delay, and hop count, have been considered Therefore, when selecting a target forwarding path for a service, there are multiple alternative forwarding paths to choose from, which greatly reduces the probability of bandwidth conflict, and decouples bandwidth constraints in a statistical sense, so that alternative forwarding paths for multiple services can be parallelized. calculation to improve the efficiency of calculating alternative forwarding paths. When multiple sub-paths are calculated from each direction according to the breadth-first search algorithm, each forwarding node in the network topology is traversed only once, which can greatly improve the efficiency of calculating multiple alternative forwarding paths, and obtain multiple backup paths. The forwarding paths are selected as separated as possible. Score multiple alternative forwarding paths according to the remaining bandwidth status of each link in the network topology, and sort them according to the scores, and determine the target forwarding path of the service according to the sequence of the sorted alternative forwarding paths. At this time, the service can be considered. Additivity constraint, which can determine the target forwarding path for each service as far as possible according to the direction of bandwidth load balancing of each link in the network topology, and the multiple alternative forwarding paths of the service are separated as much as possible, so that the determined target forwarding The path naturally satisfies the separation of active and standby and SRLG, which improves the throughput of the network.

参见图7，图7为本发明实施例提供的一种SDN控制器的结构示意图。如图7所示，该SDN控制器700包括：Referring to FIG. 7, FIG. 7 is a schematic structural diagram of an SDN controller according to an embodiment of the present invention. As shown in FIG. 7, theSDN controller 700 includes:

获取单元701，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数。The obtaining unit 701 is configured to obtain network topology information, first service information and second service information, where the first service and the second service are any two of K services, and the K is an integer greater than 1.

计算单元702，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径。Acalculation unit 702, configured to calculate the alternative forwarding path of the first service and the alternative forwarding path of the second service in parallel according to the network topology information, the first service information and the second service information, so as to obtain the A set of alternative forwarding paths for the first service and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths.

进一步地，所述计算单元702包括：Further, thecomputing unit 702 includes:

第一计算子单元7021，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径。The first calculation subunit 7021 is configured to perform calculation according to the network topology information and the first service information to obtain a first subpath set and a second subpath set of the first service; the first subpath The set includes one or more first sub-paths, and the second set of sub-paths includes one or more second sub-paths.

进一步地，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元7021具体用于：Further, the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the service information includes the starting forwarding node, the terminating forwarding node, the required Bandwidth and additivity constraints; the first calculation subunit 7021 is specifically used for:

根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;

根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;

其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.

第二计算子单元7022，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。The second calculation subunit 7022 is configured to calculate, according to the first subpath set and the second subpath set, a set of alternative forwarding paths for the first service.

进一步地，所述第二子计算单元7022具体用于：Further, the second sub-computing unit 7022 is specifically used for:

从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;

获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;

根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.

进一步地，所述可加性约束包括跳数，所述第二子路径单元7022具体用于：Further, the additivity constraint includes the number of hops, and the second sub-path unit 7022 is specifically used for:

根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;

按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.

进一步地，所述第二子路径单元7022具体用于：Further, the second sub-path unit 7022 is specifically used for:

当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;

当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;

当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.

选择单元703，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。A selection unit 703, configured to select the target forwarding path of the first service and the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service, respectively target forwarding path.

具体地，所述选择单元703具体用于：Specifically, the selection unit 703 is specifically used for:

根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;

根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;

从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.

可选地，所述备选转发路径包括多条链路；所述预设公式为：w_i＝∑_j1/b_i,j；Optionally, the alternative forwarding path includes multiple links; the preset formula is: w_i =∑_j 1/b_i,j ;

其中，所述w_i为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述b_i,j为所述第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the_wi is the score of the ith alternative forwarding path in the set of alternative forwarding paths of the first service, and the b_i,j is the jth chain in the ith alternative forwarding path the remaining bandwidth of the path.

发送单元704，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。The sending unit 704 is configured to send the target forwarding path of the first service and the target forwarding path of the second service to a forwarding node.

需要说明的是，上述各单元(获取单元701、计算单元702、选择单元703和发送单元704)用于执行上述方法的相关步骤。比如，获取单元701用于执行上述步骤S201和步骤S501；计算单元702用于执行上述步骤S202和步骤S502-506；选择单元703用于执行上述步骤S203和步骤S507；上述发送单元704用于执行上述步骤S204和步骤S507。It should be noted that the above units (the acquiring unit 701 , the calculatingunit 702 , the selecting unit 703 and the sending unit 704 ) are used to execute the relevant steps of the above method. For example, the obtaining unit 701 is used to execute the above steps S201 and S501; thecalculation unit 702 is used to execute the above steps S202 and S502-506; the selection unit 703 is used to execute the above steps S203 and S507; the above sending unit 704 is used to execute The above steps S204 and S507.

在本实施例中，SDN控制器700是以单元的形式来呈现。这里的“单元”可以指特定应用集成电路(application-specific integrated circuit，ASIC)，执行一个或多个软件或固件程序的处理器和存储器，集成逻辑电路，和/或其他可以提供上述功能的器件。此外，以上获取单元701、计算单元702和选择单元703可通过图9所示的SDN控制器的处理器901来实现，发送单元可通过图9所示的通信接口903来实现。In this embodiment, theSDN controller 700 is presented in the form of a unit. A "unit" herein may refer to an application-specific integrated circuit (ASIC), a processor and memory executing one or more software or firmware programs, an integrated logic circuit, and/or other devices that may provide the above-described functions . In addition, the above obtaining unit 701 , calculatingunit 702 and selecting unit 703 may be implemented by theprocessor 901 of the SDN controller shown in FIG. 9 , and the sending unit may be implemented by thecommunication interface 903 shown in FIG. 9 .

如图9所示，SDN控制器900可以以图9中的结构来实现，该SDN控制器900包括至少一个处理器901，至少一个存储器902以及至少一个通信接口903。所述处理器901、所述存储器902和所述通信接口903通过所述通信总线连接并完成相互间的通信。As shown in FIG. 9 , theSDN controller 900 can be implemented with the structure in FIG. 9 , and theSDN controller 900 includes at least oneprocessor 901 , at least one memory 902 and at least onecommunication interface 903 . Theprocessor 901, the memory 902 and thecommunication interface 903 are connected through the communication bus and complete the communication with each other.

处理器901可以是通用中央处理器(CPU)，微处理器，特定应用集成电路(application-specific integrated circuit，ASIC)，或一个或多个用于控制以上方案程序执行的集成电路。Theprocessor 901 may be a general-purpose central processing unit (CPU), a microprocessor, an application-specific integrated circuit (ASIC), or one or more integrated circuits for controlling the execution of the programs of the above solutions.

通信接口903，用于与其他设备或通信网络通信，如以太网，无线接入网(RAN)，无线局域网(Wireless Local Area Networks，WLAN)等。Thecommunication interface 903 is used to communicate with other devices or communication networks, such as Ethernet, Radio Access Network (RAN), Wireless Local Area Networks (Wireless Local Area Networks, WLAN).

存储器902可以是只读存储器(read-only memory，ROM)或可存储静态信息和指令的其他类型的静态存储设备，随机存取存储器(random access memory，RAM)或者可存储信息和指令的其他类型的动态存储设备，也可以是电可擦可编程只读存储器(ElectricallyErasable Programmable Read-Only Memory，EEPROM)、只读光盘(Compact Disc Read-Only Memory，CD-ROM)或其他光盘存储、光碟存储(包括压缩光碟、激光碟、光碟、数字通用光碟、蓝光光碟等)、磁盘存储介质或者其他磁存储设备、或者能够用于携带或存储具有指令或数据结构形式的期望的程序代码并能够由计算机存取的任何其他介质，但不限于此。存储器可以是独立存在，通过总线与处理器相连接。存储器也可以和处理器集成在一起。Memory 902 may be read-only memory (ROM) or other type of static storage device that can store static information and instructions, random access memory (RAM), or other type of static storage device that can store information and instructions The dynamic storage device can also be an Electrically Erasable Programmable Read-Only Memory (EEPROM), a Compact Disc Read-Only Memory (CD-ROM) or other optical disk storage, optical disk storage ( including compact discs, laser discs, compact discs, digital versatile discs, Blu-ray discs, etc.), magnetic disk storage media or other magnetic storage devices, or capable of carrying or storing desired program code in the form of instructions or data structures and capable of being stored by a computer any other medium taken, but not limited to this. The memory can exist independently and be connected to the processor through a bus. The memory can also be integrated with the processor.

其中，所述存储器902用于存储执行以上方案的应用程序代码，并由处理器901来控制执行。所述处理器901用于执行所述存储器902中存储的应用程序代码。Wherein, the memory 902 is used for storing the application code for executing the above solution, and the execution is controlled by theprocessor 901 . Theprocessor 901 is used for executing the application code stored in the memory 902 .

存储器902存储的代码可执行以上图2所示实施例提供的转发路径的计算方法，比如：获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。The code stored in the memory 902 can execute the calculation method of the forwarding path provided by the embodiment shown in FIG. 2 above, such as: acquiring network topology information, first service information and second service information, where the first service and the second service are: Any two of the K services, where K is an integer greater than 1; according to the network topology information, the first service information and the second service information, the alternative forwarding path of the first service and the second service information are calculated in parallel Alternative forwarding paths for services to obtain an alternative forwarding path set for the first service and an alternative forwarding path set for the second service; the alternative forwarding path set includes one or more alternative forwarding paths; Selecting the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service respectively; The target forwarding path of the first service and the target forwarding path of the second service are sent to the forwarding node.

本发明实施例还提供一种计算机存储介质，其中，该计算机存储介质可存储有程序，该程序执行时包括上述方法实施例中记载的任何一种转发路径的计算方法的部分或全部步骤。Embodiments of the present invention further provide a computer storage medium, wherein the computer storage medium may store a program, and when the program is executed, the program includes part or all of the steps of any forwarding path calculation method described in the above method embodiments.

需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本发明所必须的。It should be noted that, for the sake of simple description, the foregoing method embodiments are all expressed as a series of action combinations, but those skilled in the art should know that the present invention is not limited by the described action sequence. As in accordance with the present invention, certain steps may be performed in other orders or simultaneously. Secondly, those skilled in the art should also know that the embodiments described in the specification are all preferred embodiments, and the actions and modules involved are not necessarily required by the present invention.

在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。In the above-mentioned embodiments, the description of each embodiment has its own emphasis. For parts that are not described in detail in a certain embodiment, reference may be made to the relevant descriptions of other embodiments.

在本申请所提供的几个实施例中，应该理解到，所揭露的装置，可通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性或其它的形式。In the several embodiments provided in this application, it should be understood that the disclosed apparatus may be implemented in other manners. For example, the apparatus embodiments described above are only illustrative, for example, the division of the units is only a logical function division, and there may be other division methods in actual implementation, for example, multiple units or components may be combined or Integration into another system, or some features can be ignored, or not implemented. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be through some interfaces, indirect coupling or communication connection of devices or units, and may be in electrical or other forms.

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。The units described as separate components may or may not be physically separated, and components displayed as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution in this embodiment.

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。In addition, each functional unit in each embodiment of the present invention may be integrated into one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit. The above-mentioned integrated units may be implemented in the form of hardware, or may be implemented in the form of software functional units.

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储器中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储器中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储器包括：U盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。The integrated unit, if implemented as a software functional unit and sold or used as a stand-alone product, may be stored in a computer-readable memory. Based on such understanding, the technical solution of the present invention is essentially or the part that contributes to the prior art or all or part of the technical solution can be embodied in the form of a software product, and the computer software product is stored in a memory, Several instructions are included to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in the various embodiments of the present invention. The aforementioned memory includes: U disk, read-only memory (ROM, Read-Only Memory), random access memory (RAM, Random Access Memory), mobile hard disk, magnetic disk or optical disk and other media that can store program codes.

本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储器中，存储器可以包括：闪存盘、只读存储器(英文：Read-Only Memory，简称：ROM)、随机存取器(英文：Random Access Memory，简称：RAM)、磁盘或光盘等。Those skilled in the art can understand that all or part of the steps in the various methods of the above embodiments can be completed by instructing relevant hardware through a program, and the program can be stored in a computer-readable memory, and the memory can include: a flash disk , Read-only memory (English: Read-Only Memory, referred to as: ROM), random access device (English: Random Access Memory, referred to as: RAM), magnetic disk or optical disk, etc.

以上对本发明实施例进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上上述，本说明书内容不应理解为对本发明的限制。The embodiments of the present invention have been introduced in detail above, and specific examples are used to illustrate the principles and implementations of the present invention. The descriptions of the above embodiments are only used to help understand the methods and core ideas of the present invention; at the same time, for Persons of ordinary skill in the art, according to the idea of the present invention, will have changes in the specific embodiments and application scope. To sum up, the content of this description should not be construed as a limitation of the present invention.

Claims (18)

Translated fromChinese

1.一种转发路径的计算方法，其特征在于，包括：1. a calculation method of forwarding path, is characterized in that, comprises:获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；Obtain network topology information, first service information and second service information, where the first service and the second service are any two of the K services, and the K is an integer greater than 1;根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；According to the network topology information, the first service information and the second service information, the alternative forwarding path of the first service and the alternative forwarding path of the second service are calculated in parallel to obtain the alternative forwarding path of the first service a set of forwarding paths and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths;分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；Selecting a target forwarding path for the first service and a target forwarding path for the second service from the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service, respectively;将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。The target forwarding path of the first service and the target forwarding path of the second service are sent to a forwarding node.2.根据权利要求1所述的方法，其特征在于，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：2. The method according to claim 1, wherein, according to the network topology information, the first service information and the second service information, the alternative forwarding path of the first service and the second service information are calculated in parallel. The alternative forwarding path of the service is calculated according to the network topology information and the first service information when obtaining the set of alternative forwarding paths for the first service and the set of alternative forwarding paths for the second service , to obtain the set of alternative forwarding paths for the first service, including:根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；Calculate according to the network topology information and the first service information to obtain a first sub-path set and a second sub-path set of the first service; the first sub-path set includes one or more first sub-path sets path, the second sub-path set includes one or more second sub-paths;根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。According to the first sub-path set and the second sub-path set, a set of candidate forwarding paths for the first service is obtained by calculation.3.根据权利要求2所述的方法，其特征在于，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；3. The method according to claim 2, wherein the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the service information Including starting forwarding node, terminating forwarding node, required bandwidth and additivity constraints;所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：The calculating according to the network topology information and the first service information to obtain the first sub-path set and the second sub-path set of the first service, including:根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.4.根据权利要求2或3所述的方法，其特征在于，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：4. The method according to claim 2 or 3, wherein, according to the first sub-path set and the second sub-path set, the alternative forwarding path set of the first service is obtained by calculating, include:从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.5.根据权利要求4所述的方法，其特征在于，所述根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：5. The method according to claim 4, wherein the construction of an alternative forwarding path is performed according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain the first service The set of alternative forwarding paths for , including:根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.6.根据权利要求5所述的方法，其特征在于，所述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：6 . The method according to claim 5 , wherein the sub-path pairs in the set of sub-path pairs are sorted according to the additivity constraint of the sub-path pairs for each sub-path pair in the set. 7 . ,include:当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.7.根据权利要求1-6任一项所述的方法，其特征在于，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：7. The method according to any one of claims 1-6, wherein the selecting is respectively selected from a set of alternative forwarding paths for the first service and a set of alternative forwarding paths for the second service When selecting the target forwarding path of the first service and the target forwarding path of the second service, selecting the target forwarding path of the first service from the set of candidate forwarding paths of the first service, including:根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.8.根据权利要求7所述方法，其特征在于，所述备选转发路径包括多条链路；所述预设公式为：w_i＝∑_j1/b_i,j；8. The method according to claim 7, wherein the alternative forwarding path comprises multiple links; the preset formula is: w_i =∑_j 1/b_i,j ;其中，所述w_i为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述b_i,j为所述第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the_wi is the score of the ith alternative forwarding path in the set of alternative forwarding paths of the first service, and the b_i,j is the jth chain in the ith alternative forwarding path the remaining bandwidth of the path.9.一种软件定义网络SDN控制器，其特征在于，包括：9. A software-defined network SDN controller, comprising:获取单元，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；an acquisition unit, configured to acquire network topology information, first service information and second service information, where the first service and the second service are any two of the K services, and the K is an integer greater than 1;计算单元，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；A calculation unit, configured to calculate the alternative forwarding path of the first service and the alternative forwarding path of the second service in parallel according to the network topology information, the first service information and the second service information, so as to obtain the first service. A set of alternative forwarding paths for a service and a set of alternative forwarding paths for the second service; the set of alternative forwarding paths includes one or more alternative forwarding paths;选择单元，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；A selection unit, configured to select the target forwarding path of the first service and the target forwarding path of the second service from the set of alternative forwarding paths of the first service and the set of alternative forwarding paths of the second service respectively. target forwarding path;发送单元，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。A sending unit, configured to send the target forwarding path of the first service and the target forwarding path of the second service to a forwarding node.10.根据权利要求9所述的SDN控制器，其特征在于，所述计算单元包括：10. The SDN controller according to claim 9, wherein the computing unit comprises:第一计算子单元，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；a first calculation subunit, configured to perform calculation according to the network topology information and the first service information to obtain a first subpath set and a second subpath set of the first service; the first subpath set One or more first sub-paths are included, and the second sub-path set includes one or more second sub-paths;第二计算子单元，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。A second calculation subunit, configured to calculate and obtain a set of alternative forwarding paths for the first service according to the first subpath set and the second subpath set.11.根据权利要求10所述的SDN控制器，其特征在于，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元具体用于：11. The SDN controller according to claim 10, wherein the network topology information includes link information between any two forwarding nodes, and the link information includes additivity constraints and bandwidth; the The service information includes the starting forwarding node, the terminating forwarding node, the required bandwidth and the additivity constraint; the first calculation subunit is specifically used for:根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；Search from the starting forwarding node of the first service along the first direction according to the breadth-first search algorithm to obtain the first sub-path set, the starting point of any first sub-path s1 in the first sub-path set The initial forwarding node is the initial forwarding node of the first service;根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；Search along the second direction from the terminating forwarding node of the first service according to the breadth-first search algorithm to obtain the second sub-path set, where any one of the second sub-paths s2 in the second sub-path set The starting forwarding node is the terminating forwarding node of the first service;其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。Wherein, the bandwidth of the first subpath s1 and the bandwidth of the second subpath s2 are both greater than or equal to the required bandwidth of the first service, and the first subpath s1 and the second subpath s2 The additivity constraints of the first service do not exceed the additivity constraints of the first service; the first direction is the direction from the starting forwarding node of the first service to the terminating forwarding node; the second direction is The direction from the terminating forwarding node of the first service to its starting forwarding node.12.根据权利要求10或11所述的SDN控制器，其特征在于，所述第二子计算单元具体用于：12. The SDN controller according to claim 10 or 11, wherein the second sub-computing unit is specifically used for:从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；A set of sub-path pairs is obtained from the first set of sub-paths and the second set of sub-paths, the set of sub-path pairs includes one or more pairs of sub-paths, and the value of each sub-path pair in the set of sub-path pairs is The two sub-paths belong to the first sub-path set and the second sub-path set respectively, and the termination and forwarding nodes of the two sub-paths in each sub-path pair are the same;获取所述子路径对集合中的每个子路径对的可加性约束；obtaining an additivity constraint for each subpath pair in the set of subpath pairs;根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。An alternative forwarding path is constructed according to the additivity constraint of each sub-path pair in the set of sub-path pairs, so as to obtain a set of alternative forwarding paths for the first service.13.根据权利要求12所述的SDN控制器，其特征在于，所述可加性约束包括跳数，所述第二子路径单元具体用于：13. The SDN controller according to claim 12, wherein the additivity constraint comprises a hop count, and the second sub-path unit is specifically used for:根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；sorting the sub-path pairs in the sub-path pair set according to the additivity constraint of each sub-path pair in the sub-path pair set to obtain a sorted sub-path pair set;按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。Sort the sub-path pairs in the set according to the sorted sub-paths, and construct alternative forwarding paths for the two sub-paths of each sub-path pair in the sorted sub-path pair set to obtain the first A set of alternative forwarding paths for a service.14.根据权利要求13所述的方法，其特征在于，所述第二子路径单元具体用于：14. The method according to claim 13, wherein the second sub-path unit is specifically used for:当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；When the additivity constraint includes the number of hops, the sub-path pairs in the set of sub-path pairs are sorted according to the number of hops of the sub-path pair, and the sub-path pairs with the smaller hop number are sorted first;当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；When the additivity constraint includes a cost, the sub-path pairs in the set of sub-path pairs are sorted according to the cost of the sub-path pair, and the sub-path pairs with smaller cost are sorted first;当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。When the additivity constraint includes time delay, the sub-path pairs in the sub-path pair set are sorted according to the time delay of the sub-path pair, and the sub-path pair with the smaller time delay is ranked first.15.根据权利要求9-14任一项所述的SDN控制器，其特征在于，所述选择单元具体用于：15. The SDN controller according to any one of claims 9-14, wherein the selection unit is specifically configured to:根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；The score of each alternative forwarding path in the set of alternative forwarding paths of the first service is obtained by calculating according to a preset formula;根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；According to the score of each alternative forwarding path in the set of alternative forwarding paths of the first service, sort the alternative forwarding paths in the set of alternative forwarding paths of the first service to obtain sorted alternative forwarding paths Forwarding paths; wherein, the alternative forwarding paths with the smallest scores are ranked first;从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。From the sorted alternative forwarding paths, a target forwarding path of the first service is selected.16.根据权利要求15所述的SDN控制器，其特征在于，所述备选转发路径包括多条链路；所述预设公式为：w_i＝∑_j1/b_i,j；16. The SDN controller according to claim 15, wherein the alternative forwarding path comprises multiple links; and the preset formula is: w_i =∑_j 1/b_i,j ;其中，所述w_i为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述b_i,j为所述第i条备选转发路径中的第j条链路的剩余带宽。Wherein, the_wi is the score of the ith alternative forwarding path in the set of alternative forwarding paths of the first service, and the b_i,j is the jth chain in the ith alternative forwarding path the remaining bandwidth of the path.17.一种软件定义网络SDN控制器，其特征在于，包括17. A software-defined network SDN controller, comprising:存储有可执行程序代码的存储器；a memory in which executable program code is stored;与所述存储器耦合的处理器；a processor coupled to the memory;所述处理器调用所述存储器中存储的所述可执行程序代码，执行如权利要求1-8任一项所述的方法。The processor invokes the executable program code stored in the memory to execute the method according to any one of claims 1-8.18.一种计算机可读存储介质，其特征在于，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行如权利要求1-8任一项所述的方法。18. A computer-readable storage medium, wherein the computer storage medium stores a computer program, the computer program comprising program instructions, the program instructions, when executed by a processor, cause the processor to perform as claimed The method of any one of claims 1-8.

Images