[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN110661704A - 转发路径的计算方法及sdn控制器 - Google Patents

转发路径的计算方法及sdn控制器 Download PDF

Info

Publication number
CN110661704A
CN110661704A CN201810710799.1A CN201810710799A CN110661704A CN 110661704 A CN110661704 A CN 110661704A CN 201810710799 A CN201810710799 A CN 201810710799A CN 110661704 A CN110661704 A CN 110661704A
Authority
CN
China
Prior art keywords
path
sub
service
forwarding
alternative
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201810710799.1A
Other languages
English (en)
Other versions
CN110661704B (zh
Inventor
吴花精灵
盛镇醴
于璠
李翰林
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to CN201810710799.1A priority Critical patent/CN110661704B/zh
Publication of CN110661704A publication Critical patent/CN110661704A/zh
Application granted granted Critical
Publication of CN110661704B publication Critical patent/CN110661704B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/22—Alternate routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/20—Hop count for routing purposes, e.g. TTL
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/24—Multipath
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/12—Avoiding congestion; Recovering from congestion
    • H04L47/125—Avoiding congestion; Recovering from congestion by balancing the load, e.g. traffic engineering

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

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

Description

转发路径的计算方法及SDN控制器
技术领域
本发明涉及通信网络领域，尤其涉及一种转发路径的计算方法及SDN控制器。
背景技术
软件定义网络(software defined network,SDN)是一种新型网络创新架构，是网络虚拟化的一种实现方式，通过其核心技术openflow将SDN的控制面与数据面分离开来，从而实现了网络流量的灵活控制，使网络作为管道变得更加智能。SDN控制器为SDN的大脑和中枢，掌管SDN的转发路径的计算，直接决定了网络的流量分布。
在SDN中，解决如何为多个业务中的每个业务找到一条(不可分流)满足资源服务质量(quality of service,QoS)约束的最优转发路径是SDN的关键，这也是SDN全网优化问题。
针对SDN全网优化问题，现有技术主要有两种方案：方案一是采用串行计算并进行迭代的方式计算多业务的转发路径：首先对多个业务进行排序，然后按照排序结果依次串行计算多个业务中的每个业务的转发路径；对于此次无法计算得到转发路径的业务进行多次迭代计算。但是由于单个业务多约束转发路径计算耗时较大，串行计算耗时成倍增加，在业务量较大时计算转发路径耗时更大，迭代计算转发路径使得耗时进一步增加，使得串行计算业务转发路径效率低；串行计算转发路径时不能全局的考虑网络中各业务转发路径的带宽消耗，使得网络中各链路带宽消耗及其不均衡，即使多次迭代也无法改变这种网络带宽消耗不均衡的情况，从而导致整体吞吐率不高。方案二是将全网优化问题近似转变成带宽可分流问题，后采用列生成求解，再用启发式算法将解近似转回全网优化问题的解。但是列生成方法需要解大规模的线性规划，求解时间很长，计算效率极低。
综上所述，针对SDN路由全网优化问题，现有技术计算得到的多业务的转发路径效率低，并且计算得到的转发路径使SDN的整体吞吐效率低。
发明内容
本发明实施例提供一种转发路径的计算方法及SDN控制器，采用本发明实施例有利于提高计算转发路径的效率和SDN网络的整体吞吐效率。
第一方面，本发明实施例提供一种转发路径的计算方法，包括：
获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；
根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；
分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
在一种可行的实施例中，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：
根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；
根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；
所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
在一种可行的实施例中，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
在一种可行的实施例中，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
在一种可行的实施例中，所述备选转发路径包括多条链路；所述预设公式为：wi＝∑j1/bi,j；
其中，所述wi为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述bi,j为所述第i条备选转发路径中的第j条链路的剩余带宽。
第二方面，本发明实施例提供一种SDN控制器，包括：
获取单元，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；
计算单元，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；
选择单元，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；
发送单元，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
在一种可行的实施例中，所述计算单元包括：
第一计算子单元，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；
第二计算子单元，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元具体用于：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
在一种可行的实施例中，所述第二子计算单元具体用于：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述可加性约束包括跳数，所述第二子路径单元具体用于：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
在一种可行的实施例中，所述第二子路径单元具体用于：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
在一种可行的实施例中，所述选择单元具体用于：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
在一种可行的实施例中，所述备选转发路径包括多条链路；所述预设公式为：wi＝∑j1/bi,j；
其中，所述wi为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述bi,j为所述第i条备选转发路径中的第j条链路的剩余带宽。
第三方面，本发明实施例提供了一种SDN控制器，包括：
存储有可执行程序代码的存储器；
与所述存储器耦合的处理器；
所述处理器调用所述存储器中存储的所述可执行程序代码，执行如第一方面所述的全部或者部分方法。
第四方面，本发明实施例提供了一种计算机可读存储介质，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行如第一发面所述的全部或者部分方法。
可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和共享风险链路组(shared risk linkgroups，SRLG)，提升网络的吞吐率。
本发明的这些方面或其他方面在以下实施例的描述中会更加简明易懂。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明实施例提供的一种SDN的结构示意图；
图2为本发明实施例提供的一种转发路径的计算方法的流程示意图；
图3为本发明实施例提供的一种网络拓扑结构示意图；
图4为一个转发路径的示意图；
图5为本发明实施例提供的另一种转发路径的计算方法的流程示意图；
图6为本发明实施例提供的一个搜索子路径的流程示意图；
图7为本发明实施例提供的一种SDN控制器的结构示意图；
图8为本发明实施例提供的一种SDN控制器的局部结构示意图；
图9为本发明实施例提供的另一种SDN控制器的结构示意图。
具体实施方式
为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。
参见图1，图1为本发明实施例提供的一种SDN的结构示意图。该SDN包括SDN控制器101和多个转发节点102。
其中，上述转发节点102可为交换机、路由器或其他设备。
上述SDN控制器根据上述多个转发节点102构成上述SDN网络拓扑结构和待转发的多业务信息并行计算得到多业务的目标转发路径，然后通过openflow将该多业务的目标转发路径发送至上述SDN网络拓扑结构上，使得网络拓扑结构中转发节点构建上述多业务的目标转发路径，以实现多业务的转发。
参见图2，图2为本发明实施例提供的一种转发路径的计算方法的流程示意图。如图2所示，该方法包括：
S201、SDN控制器获取网络拓扑结构信息、第一业务信息和第二业务信息。
其中，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；上述K条业务均为上述SDN控制器待转发的业务。
其中，上述网络拓扑结构信息包括转发节点的数量和任两个转发节点之间的链路信息。该链路状态信息包括带宽和可加性约束。
进一步地，上述可加性约束包括但不限定于代价、时延和跳数。
参见图3，图3为本发明实施例提供的一种网络拓扑结构的示意图。如图3所示，该网络拓扑结构包括6个转发节点，分别为转发节点s、转发节点i、转发节点j、转发节点k、转发节点l和转发节点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。
转发节点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)，该链路信息的含义可参见上述相关描述，在此不再叙述。
其中，上述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束，该可加性约束包括但不限定于时延、代价和跳数。
需要说明的是，上述业务的时延、代价和跳数分别为业务从其起始转发节点至终止转发节点所能容忍的最大时延，最大代价和最大跳数。
S202、SDN控制器根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径。
需要指出的是，针对上述第一业务和第二业务，上述SDN控制器启动两条线程，实现并行计算上述第一业务的备选转发路径集合和上述第二业务的备选转发路径集合。
具体地，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：
根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；
根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
进一步地，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；
所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
其中，上述可加性约束包括但不限于代价、时延和跳数。
具体地，上述SDN控制器根据上述第一业务信息获取该第一业务的起始转发节点和终止转发节点，然后根据广度优先搜索算法，从上述第一业务的起始转发节点沿第一方向搜索，遍历上述网络拓扑结构中除了该第一业务的起始转发节点之外的每个转发节点，确定上述拓扑网络结构中除了该第一业务的起始转节点之外的任一转发节点k到该第一业务的起始转发节点的子路径的带宽、代价、时延和跳数；判断该子路径的带宽是否大于或者等于上述第一业务的所需带宽、该子路径的代价、时延和跳数是否均分别小于上述第一业务的代价、时延和跳数；当确定该子路径的带宽大于或者等于上述第一业务的所需带宽，且该子路径的代价、时延和跳数均小于或者等于上述第一业务的代价、时延和跳数，则确定该子路径为第一子路径；当该子路径的带宽小于上述第一业务的所需带宽，或者该子路径的代价大于上述第一业务的代价，或者该子路径的时延大于上述第一业务的代价，或者该子路径的跳数大于上述第一业务的跳数时，上述SDN控制器跳过，继续搜索下一转发节点。
按照上述方法，上述SDN控制器获取上述第一子路径集合，该第一子路径集合包括一条或者多条第一子路径。对于上述网络拓扑结构的除了第一业务的起始转发节点之外的每个转发节点，上述SDN控制器只遍历一次。
同理，上述SDN控制器按照上述方法，根据广度优先搜索算法，从上述第一业务的终止转发节点沿第二方向搜索，以得到上述第二子路径集合。
在一种可行的实施例中，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
具体地，上述SDN控制器根据上述第一子路径集合和第二子路径集合获取上述子路径集合，该子路径集合包括一个或多个子路径对，该子路径对集合中的每个子路径对中的两条子路径的终止转发节点相同，且该子路径集合中的每个子路径对中的两条子路径分别属于上述第一子路径集合和第二子路径集合。然后上述SDN控制器根据上述子路径对集合中每个子路径对的两条子路径的可加性约束，获取上述子路径对集合中每个子路径对的可加性约束。
其中，上述子路径对的可加性约束为该子路径对的两条子路径的可加性约束之和，比如若上述子路径的可加性约束包括代价时，则子路径对的可加性约束为该子路径对的两条子路径的代价之和，若上述子路径的可加性约束包括时延时，则上述子路径对的可加性约束为该子路径对的两条子路径的时延之和；若上述子路径的可加性约束包括跳数时，则该子路径对的可加性约束为该子路径对的两条子路径的跳数之和。
举例说明，假如子路径对的两条子路径的可加性约束包括对代价、时延和跳数，两条子路径的代价分别为3和5、时延分别为2和3，跳数分别为4和5，则上述子路径对的可加性约束包括代价、时延和跳数，且代价为8、时延为5和跳数为9。
上述SDN控制器根据上述方法获取上述子路径集合中每个子路径对的可加性约束。然后上述SDN控制器确定每个子路径对的可加性约束是否小于或者等于第一业务的可加性约束；当子路径对的可加性约束小于或者等于上述第一业务的可加性约束时，上述SDN控制器以该子路径对的两条子路径的终止转发节点为连接点，构建备选转发路径。
其中，子路径对的可加性约束小于或者等于上述第一业务的可加性约束，包括：
当上述可加性约束包括代价时，上述子路径对的代价小于或者等于上述第一业务的代价；当上述可加性约束包括时延时；上述子路径对的时延小于或者等于上述第一业务的时延；当上述可加性约束包括跳数时，上述子路径对的跳数小于或者等于上述第一业务的跳数；
当上述可加性约束包括代价和时延时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的时延小于或等于第一业务的时延；当上述可加性约束包括时延和跳数时，上述子路径对的时延小于或等于第一业务的时延，且上述子路径对的跳数小于或等于第一业务的跳数；当上述可加性约束包括代价和跳数时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的跳数小于或等于第一业务的跳数；
当上述可加性约束包括代价、时延和跳数时，上述子路径对的代价小于或等于第一业务的代价，且上述子路径对的时延小于或等于第一业务的时延；且上述子路径对的代价小于或等于第一业务的代价。
在一种可行的实施例中，上述SDN控制器按照上述方法构建备选转发路径m之前，该SDN控制器判断该备选转发路径m是否成环，即备选转发路径m是否经过同一转发节点至少两次。当确定该备选转发路径m成环时，上述SDN控制器不构建上述备选转发路径m。如图4所示，备选转发路径m经过转发节点1-2-3-4-2-5-6-7，其中，该备选转发路径经过转发节点2两次，因此上述SDN控制器确定该备选转发路径m成环，不构建该备选转发路径m。
当确定上述备选转发路径m未成环时，上述SDN控制器确定该备选转发路径m是否与已构建的备选转发路径重复；当确定上述备选转发路径m与已构建的备选转发路径重复时，上述SDN控制器不构建上述备选转发路径m；当确定上述备选转发路径m未与已构建的备选转发路径重复时，上述SDN控制器构建并保存上述备选转发路径m。
按照上述方法，上述SDN控制器得到上述第一业务的备选转发路径集合。
在一种可行的实施例中，所述根据所述子路径对集合中的每个子路径对的带宽和可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
其中，述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
进一步地，当上述可加性约束包括跳数和代价，且跳数为第一优先级，代价为第二优先级时，上述SDN控制器根据子路径对的跳数对上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，代价小的子路径对排序靠前；
当上述可加性约束包括跳数和时延，且跳数为第一优先级，时延为第二优先级时，上述SDN控制器根据子路径对的跳数对上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，时延小的子路径对排序靠前；
当上述可加性约束包括代价和时延，且时延为第一优先级，代价为第二优先级时，上述SDN控制器根据子路径对的时延对上述子路径对集合中的子路径对进行排序，时延小的子路径对排序靠前；对于时延相同的子路径对，代价小的子路径对排序靠前；
当上述可加性约束包括跳数、代价和时延，且跳数为第一优先级，时延为第二优先级，代价为第三优先级时，上述SDN控制器首先根据子路径对的跳数上述子路径对集合中的子路径对进行排序，跳数小的子路径对排序靠前；对于跳数相同的子路径对，时延小的子路径对排序靠前；对于跳数和时延均相同的子路径对，代价小的子路径对排序靠前。
按照上述方法，上述SDN控制器得到排序后的子路径对。
当上述可加性约束包括跳数时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数，直至判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数。
当上述可加性约束包括代价时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的代价是否小于或者等于上述第一业务的代价；当确定上述排序后的子路径对中的第s个子路径对的代价小于上述第一业务的代价时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的代价均小于上述第一业务的代价，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的代价是否小于或者等于上述第一业务的代价，直至判断上述子路径对集合中的每个子路径对的代价是否小于或者等于上述第一业务的代价。
当上述可加性约束包括时延时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的时延是否小于或者等于上述第一业务的时延；当确定上述排序后的子路径对中的第s个子路径对的时延小于上述第一业务的时延时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的时延均小于上述第一业务的时延，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的时延是否小于或者等于上述第一业务的时延，直至判断上述子路径对集合中的子路径对的时延是否小于或者等于上述第一业务的时延。
当上述可加性约束包括跳数和代价，且跳数为第一优先级，代价为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器判断上述第s个子路径对的代价是否小于上述第一业务的代价；当确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数；当上述第s个子路径对的代价大于上述第一业务的代价时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的跳数相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。
当上述可加性约束包括跳数和时延，且跳数为第一优先级，时延为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的跳数是否小于或者等于上述第一业务的跳数；当确定上述排序后的子路径对中的第s个子路径对的跳数小于上述第一业务的跳数时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的跳数均小于上述第一业务的跳数，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的跳数小于或者等于上述第一业务的跳数时，上述SDN控制器判断上述第s个子路径对的时延是否小于上述第一业务的时延；当确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的跳数是否小于或者等于上述第一业务的跳数；当上述第s个子路径对的时延大于上述第一业务的时延时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的跳数相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。
当上述可加性约束包括时延和代价，且时延为第一优先级，代价为第二优先级时，上述SDN控制器根据排序后的子路径对的顺序，逐个判断上述子路径对集合中的每个子路径对的时延是否小于或者等于上述第一业务的时延；当确定上述排序后的子路径对中的第s个子路径对的时延小于上述第一业务的时延时，上述SDN控制器确定排序在该第s个子路径对之后的子路径对的时延均小于上述第一业务的时延，第一业务的备选转发路径的构建结束；当上述SDN控制器确定上述第s个子路径对的时延小于或者等于上述第一业务的时延时，上述SDN控制器判断上述第s个子路径对的代价是否小于上述第一业务的代价；当确定上述第s个子路径对的代价小于或者等于上述第一业务的代价时，上述SDN控制器以第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径。然后，上述SDN控制器根据上述方法继续判断第s+1个子路径对的时延是否小于或者等于上述第一业务的时延；当上述第s个子路径对的代价大于上述第一业务的代价时，上述SDN控制器直接跳转至第s+n个子路径对，并对第s+n个子路径对进行上述操作。其中，n为与上述第s个子路径对的时延相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。
当上述可加性约束包括跳数、时延和代价，且跳数为第一优先级、时延为第二优先级，代价为第三优先级时，上述上述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个子路径对相同的子路径对的个数。按照上述方法，直至判断上述子路径对集合中的每个子路径对的可加性约束是否小于或者等于上述第一业务的可加性约束。
在一种可行的实施例中，当上述第s个子路径对的可加性约束小于或者等于上述第一业务的可加性约束时，且在以上述第s个子路径对中的两条子路径的终止转发节点为连接点，构建上述第一业务的备选转发路径之前，上述SDN控制器还需判断根据上述第s个子路径对得到备选转发路径是否成环；当确定根据第s个子路径对得到的备选转发路径成环时，上述SDN控制器不根据第s个子路径对构建备选转发路径；当确定根据第s个子路径对得到的备选转发路径不成环时，上述SDN控制器判断根据第s个子路径对得到的备选转发路径是否与已构建的备选转发路径重复；当确定根据第s个子路径对得到的备选转发路径与已构建的备选转发路径重复时，上述SDN控制器不根据上述第s个子路径对构建备选转发路径；当确定根据第s个子路径对得到的备选转发路径不与已构建的备选转发路径重复时，上述SDN控制器以上述第s个子路径对中的两条子路径的终止转发节点为连接点，构建备选转发路径。
需要指出的是，上述可加性约束包括但不限定于代价、时延和跳数。当可加性约束还包括其他参数时，上述SDN控制器按照上述方法进行判断并构建备选转发路径。
需要指出的是，上述第s个子路径对为上述排序后的子路径对中的任一个子路径对。
通过对上述子路径对集合中的子路径对继续排序，然后判断排序后的子路径对是否满足上述第一业务的需求的方法，可以提高根据子路径对集合构建上述第一业务的备选转发路径集合的效率。
按照上述方法，上述SDN控制器根据第二业务的第一子路径集合和第二子路径集合，计算得到第二业务的备选转发路径集合。
S203、SDN控制器分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。
在一种可行的实施例中，上述业务信息还包括业务优先级，上述SDN控制器根据业务优先级和所需带宽对上述第一业务和第二业务进行排序；其中，业务优先级为第一排序优先级，所需带宽为第二排序优先级，即上述SDN控制器先根据业务优先级对上述第一业务和第二业务排序，业务优先级高的业务排序靠前；当第一业务和第二业务的业务优先级相同时，则上述SDN控制器根据业务的所需带宽对上述第一业务和第二业务进行排序，所需带宽大的业务排序靠前。
假设上述SDN控制器根据业务优先级和所需带宽对上述第一业务和第二业务排序得到的结果为：第一业务排序在上述第二业务之前。
在一种可行的实施例中，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
具体地，上述第一业务的备选转发路径集合中包括一条或者多条备选转发路径。当上述第一业务的备选转发路径集合中包括一条备选转发路径时，上述SDN控制器直接获取该备选转发路径的剩余带宽，并判断该备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽；当确定该备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器确定该备选转发路径为上述第一业务的目标转发路径；当确定该备选转发路径的剩余带宽小于上述第一业务的所需带宽时，上述SDN控制器确定无法获取第一业务的目标转发路径。
需要指出的是，上述SDN控制器分别从上述第一业务的备选转发路径集合和第二业务的备选转发路径集合中选取出上述第一业务的目标转发路径和第二业务的目标转发路径是串行进行的，即上述SDN控制器先从上述第一业务的备选转发路径集合中选取出第一业务的目标转发路径，再从上述第二业务的备选转发路径集合中选取出该第二业务的目标转发路径。并且第一业务的目标转发路径和第二业务的目标转发路径存在相同链路的情形，因此在从备选转发路径集合中选取出目标转发路径时，需要考虑备选转发路径的剩余带宽，备选转发路径的剩余带宽为该备选转发路径的链路的剩余带宽的最小值。
当上述第一业务的备选转发路径集合中包括多条备选转发路径时，上述SDN控制器根据预设公式计算得到上述第一业务的多条备选转发路径中每条备选转发的得分。
其中，该预设公式可为：wi＝∑j1/bi,j；wi为第一业务的备选转发路径集合中排序后的多条备选转发路径中的第i条备选转发路径的得分，所述bi,j为该第i条备选转发路径中的第j条链路的剩余带宽。
上述SDN控制器然后根据每条备选转发路径的得分，对上述第一业务的多条备选转发路径进行排序，以得到排序后的多条备选转发路径；其中，得分小的备选转发路径的排序靠前。然后按照排序后的多条备选转发路径的顺序，从该排序后的多条备选转发路径中选取出上述第一业务的目标转发路径。当排序在第q条备选转发路径之前的备选转发路径之前的备选转发路径的剩余带宽均小于上述第一业务的所需带宽时，上述SDN控制器获取上述第q条备选转发路径的剩余带宽，并判断第q条备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽时，当上述第q条备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽，则上述SDN控制器确定上述第q条备选转发路径为上述第一业务的目标转发路径；当上述第q条备选转发路径的剩余带宽小于上述第一业务的所需带宽，上述SDN控制器继续获取上述第q+1条备选转发路径的剩余带宽，并重复执行上述过程。
当上述第q条备选转发路径为上述第一业务的备选转发路径集中的最后一条备选转发路径时，上述SDN控制器则确定上述备选转发路径集合中的备选转发路径的剩余带宽均小于上述第一业务的所需带宽，即上述SDN控制器从上述第一业务的备选转发路径集合中未获取目标转发路径。
按照上述方法，上述SDN控制器从上述第二业务的备选转发路径集合中获取第二业务的目标转发路径。
需要指出的是，上述SDN控制器对业务进行排序，并根据业务排序的顺序为上述业务从其备选转发路径集合中选取出目标转发路径。
在一种可行的实施例中，当上述SDN控制器从上述第一业务的备选转发路径集合中未获取上述第一业务的目标转发路径，则上述SDN控制器重复执行上述步骤S202和S203所述的方法，直至获取上述第一业务的目标转发路径或者重复执行上述步骤S202和S203所述方法的次数超过预设次数。
S204、SDN控制器将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
具体地，上述SDN控制器将上述第一业务的目标转发路径和上述第二业务的目标转发路径发送至上述网路拓扑结构中的转发节点，以使转发节点构建上述第一业务的目标转发路径和第二业务的目标转发路径。
可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和SRLG，提升网络的吞吐率。
参见图5，图5为本发明实施例提供的另一种转发路径的计算方法的流程示意图。如图5所示，该方法包括：
S501、SDN控制器获取所述网络拓扑信息结构信息、第一业务信息和第二业务信息。
其中，所述第一业务和第二业务为K条业务中任意的两条，所述K为大于1的整数；上述K条业务均为上述SDN控制器待转发的业务。
其中，上述网络拓扑结构信息包括转发节点的数量和任两个转发节点之间的链路信息。该链路状态信息包括带宽和可加性约束。
进一步地，上述可加性约束包括但不限定于代价、时延和跳数。
上述业务信息包括但不限定于起始转发节点、终止转发节点、所需带宽、代价、时延和跳数。
S502、SDN控制器根据广度搜索算法分别从第一业务的起始转发节点沿第一方向搜索和第一业务的终止转发节点沿第二方向搜索，以得到第一业务的第一子路径集合和第二子路径集合。
其中，上述第一方向为上述第一业务的起始转发节点到其终止转发节点的方向，第二方向为上述第一业务的终止转发节点到其起始转发节点的方向。
上述第一业务的第一子路径集合包括一条或者多条第一子路径，第二子路径集合包括一套或者多条第二子路径。且上述第一子路径集合中的任一条第一子路径s1的起始转发节点为上述第一业务的起始转发节点，上述第二子路径集合中的任一条第一子路径s2的起始转发节点为上述第一业务的终止转发节点。
其中，上述第一子路径s1和第二子路径s2的带宽均大于或者等于上述第一业务的所需带宽，上述第一子路径s1和第二子路径s2的可加性约束均未超过上述第一业务的可加性约束。
进一步地，上述第一子路径s1的可加性约束未超过上述第一业务的可加性约束具体包括：上述第一子路径s1的代价小于或等于上述第一业务的代价上限、且该第一子路径s1的延时小于或等于上述第一业务的时延，且该第一子路径s1的跳数小于或等于上述第一业务的跳数；同理，上述第二子路径s2的可加性约束未超过上述第一业务的可加性约束具体包括：上述第二子路径s2的代价小于或等于上述第一业务的代价上限、且该第二子路径s2的延时小于或等于上述第一业务的时延，且该第二子路径s2的跳数小于或等于上述第一业务的跳数。
具体地，当从第一方向搜索到转发节点t2时，上述SDN控制器获取该转发节点t2与前一个搜索到的转发节点t1之间链路的带宽，代价、时延和跳数与第一子路径pt1的带宽、代价、时延和跳数，该第一子路径pt1为起始转发节点为上述第一业务的起始转发节点和终止转发节点为上述转发节点t1的路径。上述SDN控制器将上述转发节点t1和转发节点t2之间链路的代价、时延和跳数分别与上述第一子路径pt1的代价、时延和跳数进行累加，得到子路径pt2的代价时延和跳数。当该子路径pt2的代价、时延和跳数均未超过上述第一业务的代价、时延和跳数，且上述转发节点t1和转发节点t2之间链路的带宽大于或者等于上述第第一业务的所需带宽时，则该子路径pt2为上述第一子路径。
当上述子路径pt2的代价、时延和跳数中的任一项大于上述第一业务的代价上限、时延上限和跳数上限，或者上述转发节点t1和转发节点t2之间链路的带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器则跳过上述转发节点t2，搜索下一个转发节点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继续搜索。
按照上述方法，上述SDN控制器遍历上述网络拓扑结构中的每个转发节点，得到第一业务的第一子路径集合和第二子路径集合。在上述遍历过程中，上述网络拓扑结构中的每个转发节点只遍历一次。
S503、SDN控制器根据广度搜索算法分别从第二业务的起始转发节点沿第一方向搜索和第二业务的终止转发节点沿第二方向搜索，以得到第二业务的第一子路径集合和第二子路径集合。
在此需要说明的是，上述SDN控制器搜索得到第二业务的第一子路径集合和第二子路径集合的具体过程可参见上述步骤S502的相关描述，在此不再叙述。
S504、SDN控制器从第一业务的第一子路径集合和第二子路径集合中选取出子路径对集合。
其中，上述子路径对集合包括一个或者多个子路径对，该子路径对集合中每个子路径对的两条子路径分别属于上述第一业务的第一子路径集合和第二子路径集合，且上述每个子路径对的两条子路径具有相同的终止转发节点。
S505、SDN控制器对第一业务的子路径对集合中的子路径对进行排序，以得到排序后的子路径对。
在此需要说明的是，上述SDN控制器对上述子路径对集合中的子路径对进行排序的过程可参见上述步骤S202的相关描述，在此不再叙述。
S506、SDN控制器根据排序后的子路径对，获取第一业务的备选转发路径集合。
其中，上述第一业务的备选转发路径集合包括一条或者多条备选转发路径。
在此需要说明的是，上述SDN控制器对上述子路径对集合中的子路径对进行排序和根据排序后的子路径对获取第一业务的备选转发路径集合的过程可参见上述步骤S202的相关描述，在此不再叙述。
按照步骤S402-S406所描述的方法，上述SDN控制器并行计算得到上述第一业务中的备选转发路径集合和第二业务的备选转发路径集合。
S507、SDN控制器分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。
具体地，上述第一业务的备选转发路径集合中包括一条或者多条备选转发路径。当上述第一业务的备选转发路径集合中包括一条备选转发路径时，上述SDN控制器直接该备选转发路径的剩余带宽，并判断该备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽；当确定该备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽时，上述SDN控制器确定该备选转发路径为上述第一业务的目标转发路径；当确定该备选转发路径的剩余带宽小于上述第一业务的所需带宽时，上述SDN控制器确定无法获取第一业务的目标转发路径。
需要指出的是，上述SDN控制器分别从上述第一业务的备选转发路径集合和第二业务的备选转发路径集合中选取出上述第一业务的目标转发路径和第二业务的目标转发路径是串行进行的，即上述SDN控制器先从上述第一业务的备选转发路径集合中选取出第一业务的目标转发路径，再从上述第二业务的备选转发路径集合中选取出该第二业务的目标转发路径。并且第一业务的目标转发路径和第二业务的目标转发路径存在相同链路的情形，因此在从备选转发路径集合中选取出目标转发路径时，需要考虑备选转发路径的剩余带宽，备选转发路径的剩余带宽为该备选转发路径的链路的剩余带宽的最小值。
当上述第一业务的备选转发路径集合中包括多条备选转发路径时，上述SDN控制器根据预设公式计算得到上述第一业务的多条备选转发路径中每条备选转发的得分。
其中，该预设公式可为：wi＝∑j1/bi,j；wi为第一业务的备选转发路径集合中排序后的多条备选转发路径中的第i条备选转发路径的得分，所述bi,j为该第i条备选转发路径中的第j条链路的剩余带宽。
上述SDN控制器然后根据每条备选转发路径的得分，对上述第一业务的多条备选转发路径进行排序，以得到排序后的多条备选转发路径；其中，得分小的备选转发路径的排序靠前。然后按照排序后的多条备选转发路径的顺序，从该排序后的多条备选转发路径中选取出上述第一业务的目标转发路径。当排序在第q条备选转发路径之前的备选转发路径之前的备选转发路径的剩余带宽均小于上述第一业务的所需带宽时，上述SDN控制器获取上述第q条备选转发路径的剩余带宽，并判断第q条备选转发路径的剩余带宽是否大于或者等于上述第一业务的所需带宽时，当上述第q条备选转发路径的剩余带宽大于或者等于上述第一业务的所需带宽，则上述SDN控制器确定上述第q条备选转发路径为上述第一业务的目标转发路径；当上述第q条备选转发路径的剩余带宽小于上述第一业务的所需带宽，上述SDN控制器继续获取上述第q+1条备选转发路径的剩余带宽，并重复执行上述过程。
当上述第q条备选转发路径为上述第一业务的备选转发路径集中的最后一条备选转发路径时，上述SDN控制器则确定上述备选转发路径集合中的备选转发路径的剩余带宽均小于上述第一业务的所需带宽，即上述SDN控制器从上述第一业务的备选转发路径集合中未获取目标转发路径。
按照上述方法，上述SDN控制器从上述第二业务的备选转发路径集合中获取第二业务的目标转发路径。
需要指出的是，上述SDN控制器对业务进行排序，并根据业务排序的顺序为上述业务从其备选转发路径集合中选取出目标转发路径。
在一种可行的实施例中，当上述SDN控制器从上述第一业务的备选转发路径集合中未获取上述第一业务的目标转发路径，则上述SDN控制器重复执行上述步骤S402-S407所述的方法，直至获取上述第一业务的目标转发路径或者重复执行上述步骤S402-S407所述方法的次数超过预设次数。
S508、SDN控制器将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
具体地，上述SDN控制器将上述第一业务的目标转发路径和上述第二业务的目标转发路径发送至上述网路拓扑结构中的转发节点，以使转发节点构建上述第一业务的目标转发路径和第二业务的目标转发路径。
可以看出，在本发明实施例的方案中，根据网路拓扑结构信息和业务信息和广度优先搜索算法从双向路径快速计算出多条子路径，然后根据多条子路径构建业务的多条备选转发路径，一次计算可以得到多条备选转发路径；并且在构建备选转发路径时，已考虑业务的可加性约束和备选转发路径的可加性约束，比如代价、时延和跳数等，因此在为业务选择目标转发路径时，有多条备选转发路径可供选择，使得带宽的冲突概率大大降低，在统计意义上解耦宽带约束，从而使得多业务的备选转发路径可以并行计算，提高计算备选转发路径的效率。在根据广度优先搜索算法从每个方向计算出多条子路径时网络拓扑结构中的每个转发节点只遍历一次，可以极快提高计算出多条备选转发路径的效率，并且得到的多条备选转发路径都是尽量分离的。根据网络拓扑结构中各链路剩余带宽状况为多条备选转发路径进行打分，并根据打分进排序，按照排序后的备选转发路径的顺序确定出业务的目标转发路径，此时可以考虑业务可加性约束，这就可以尽量按网络拓扑结构中各链路带宽负载均衡的方向为各业务确定目标转发路径，并且业务的多条备选转发路径都是尽量分离的，使得确定的目标转发路径天然满足主备分离和SRLG，提升网络的吞吐率。
参见图7，图7为本发明实施例提供的一种SDN控制器的结构示意图。如图7所示，该SDN控制器700包括：
获取单元701，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数。
计算单元702，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径。
进一步地，所述计算单元702包括：
第一计算子单元7021，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径。
进一步地，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元7021具体用于：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
第二计算子单元7022，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
进一步地，所述第二子计算单元7022具体用于：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
进一步地，所述可加性约束包括跳数，所述第二子路径单元7022具体用于：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
进一步地，所述第二子路径单元7022具体用于：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
选择单元703，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径。
具体地，所述选择单元703具体用于：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
可选地，所述备选转发路径包括多条链路；所述预设公式为：wi＝∑j1/bi,j；
其中，所述wi为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述bi,j为所述第i条备选转发路径中的第j条链路的剩余带宽。
发送单元704，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
需要说明的是，上述各单元(获取单元701、计算单元702、选择单元703和发送单元704)用于执行上述方法的相关步骤。比如，获取单元701用于执行上述步骤S201和步骤S501；计算单元702用于执行上述步骤S202和步骤S502-506；选择单元703用于执行上述步骤S203和步骤S507；上述发送单元704用于执行上述步骤S204和步骤S507。
在本实施例中，SDN控制器700是以单元的形式来呈现。这里的“单元”可以指特定应用集成电路(application-specific integrated circuit，ASIC)，执行一个或多个软件或固件程序的处理器和存储器，集成逻辑电路，和/或其他可以提供上述功能的器件。此外，以上获取单元701、计算单元702和选择单元703可通过图9所示的SDN控制器的处理器901来实现，发送单元可通过图9所示的通信接口903来实现。
如图9所示，SDN控制器900可以以图9中的结构来实现，该SDN控制器900包括至少一个处理器901，至少一个存储器902以及至少一个通信接口903。所述处理器901、所述存储器902和所述通信接口903通过所述通信总线连接并完成相互间的通信。
处理器901可以是通用中央处理器(CPU)，微处理器，特定应用集成电路(application-specific integrated circuit，ASIC)，或一个或多个用于控制以上方案程序执行的集成电路。
通信接口903，用于与其他设备或通信网络通信，如以太网，无线接入网(RAN)，无线局域网(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)或其他光盘存储、光碟存储(包括压缩光碟、激光碟、光碟、数字通用光碟、蓝光光碟等)、磁盘存储介质或者其他磁存储设备、或者能够用于携带或存储具有指令或数据结构形式的期望的程序代码并能够由计算机存取的任何其他介质，但不限于此。存储器可以是独立存在，通过总线与处理器相连接。存储器也可以和处理器集成在一起。
其中，所述存储器902用于存储执行以上方案的应用程序代码，并由处理器901来控制执行。所述处理器901用于执行所述存储器902中存储的应用程序代码。
存储器902存储的代码可执行以上图2所示实施例提供的转发路径的计算方法，比如：获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
本发明实施例还提供一种计算机存储介质，其中，该计算机存储介质可存储有程序，该程序执行时包括上述方法实施例中记载的任何一种转发路径的计算方法的部分或全部步骤。
需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本发明所必须的。
在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。
在本申请所提供的几个实施例中，应该理解到，所揭露的装置，可通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性或其它的形式。
所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。
另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。
所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储器中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储器中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储器包括：U盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。
本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储器中，存储器可以包括：闪存盘、只读存储器(英文：Read-Only Memory，简称：ROM)、随机存取器(英文：Random Access Memory，简称：RAM)、磁盘或光盘等。
以上对本发明实施例进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上上述，本说明书内容不应理解为对本发明的限制。

Claims (18)

1.一种转发路径的计算方法，其特征在于，包括：
获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；
根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；
分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；
将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
2.根据权利要求1所述的方法，其特征在于，所述根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合时，根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到所述第一业务的备选转发路径集合，包括：
根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；
根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
3.根据权利要求2所述的方法，其特征在于，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；
所述根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合，包括：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
4.根据权利要求2或3所述的方法，其特征在于，所述根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合，包括：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
5.根据权利要求4所述的方法，其特征在于，所述根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合，包括：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
6.根据权利要求5所述的方法，其特征在于，所述根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，包括：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
7.根据权利要求1-6任一项所述的方法，其特征在于，所述分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径时，从所述第一业务的备选转发路径集合中，选择出所述第一业务的目标转发路径，包括：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
8.根据权利要求7所述方法，其特征在于，所述备选转发路径包括多条链路；所述预设公式为：wi＝∑j1/bi,j；
其中，所述wi为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述bi,j为所述第i条备选转发路径中的第j条链路的剩余带宽。
9.一种软件定义网络SDN控制器，其特征在于，包括：
获取单元，用于获取网络拓扑结构信息、第一业务信息和第二业务信息，所述第一业务和第二业务为K条业务中任意两条，所述K为大于1的整数；
计算单元，用于根据所述网拓扑结构信息、所述第一业务信息和第二业务信息，并行计算第一业务的备选转发路径和第二业务的备选转发路径，以得到所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合；所述备选转发路径集合包括一条或者多条备选转发路径；
选择单元，用于分别从所述第一业务的备选转发路径集合和所述第二业务的备选转发路径集合中，选择出所述第一业务的目标转发路径和所述第二业务的目标转发路径；
发送单元，用于将所述第一业务的目标转发路径和所述第二业务的目标转发路径发送至转发节点。
10.根据权利要求9所述的SDN控制器，其特征在于，所述计算单元包括：
第一计算子单元，用于根据所述网络拓扑结构信息和所述第一业务信息进行计算，以得到第一业务的第一子路径集合和第二子路径集合；所述第一子路径集合包括一条或多条第一子路径，所述第二子路径集合包括一条或多条第二子路径；
第二计算子单元，用于根据所述第一子路径集合和所述第二子路径集合，计算得到所述第一业务的备选转发路径集合。
11.根据权利要求10所述的SDN控制器，其特征在于，所述网络拓扑结构信息包括任两个转发节点间的链路信息，所述链路信息包括可加性约束和带宽；所述业务信息包括起始转发节点、终止转发节点、所需带宽和可加性约束；所述第一计算子单元具体用于：
根据广度优先搜索算法从所述第一业务的起始转发节点沿第一方向搜索，以得到所述第一子路径集合，所述第一子路径集合中的任一条第一子路径s1的起始转发节点为所述第一业务的起始转发节点；
根据所述广度优先搜索算法从所述第一业务的终止转发节点沿第二方向搜索，以得到所述第二子路径集合，所述第二子路径集合中的任一条第二子路径s2的起始转发节点为所述第一业务的终止转发节点；
其中，所述第一子路径s1的带宽和所述第二子路径s2的带宽均大于或者等于所述第一业务的所需带宽，所述第一子路径s1和所述第二子路径s2的可加性约束均未超过所述第一业务的可加性约束；所述第一方向为从所述第一业务的起始转发节点到其终止转发节点的方向；所述第二方向为从所述第一业务的终止转发节点到其起始转发节点的方向。
12.根据权利要求10或11所述的SDN控制器，其特征在于，所述第二子计算单元具体用于：
从所述第一子路径集合和所述第二子路径集合中获取子路径对集合，所述子路径对集合包括一个或多个子路径对，所述子路径对集合中的每个子路径对的两个子路径分别属于所述第一子路径集合和所述第二子路径集合，且所述每个子路径对中的两个子路径的终止转发节点相同；
获取所述子路径对集合中的每个子路径对的可加性约束；
根据所述子路径对集合中的每个子路径对的可加性约束进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
13.根据权利要求12所述的SDN控制器，其特征在于，所述可加性约束包括跳数，所述第二子路径单元具体用于：
根据所述子路径对集合中的每个子路径对的可加性约束，对所述子路径对集合中的子路径对进行排序，以得到排序后的子路径对集合；
按照所述排序后的子路径对集合中子路径对的排序，对所述排序后的子路径对集合中的每个子路径对的两个子路径进行备选转发路径的构建，以得到所述第一业务的备选转发路径集合。
14.根据权利要求13所述的方法，其特征在于，所述第二子路径单元具体用于：
当所述可加性约束包括跳数时，根据子路径对的跳数对所述子路径对集合中的子路径对进行排序，且跳数小的子路径对排序靠前；
当所述可加性约束包括代价时，根据子路径对的代价对所述子路径对集合中的子路径对进行排序，且代价小的子路径对排序靠前；
当所述可加性约束包括时延时，根据子路径对的时延对所述子路径对集合中的子路径对进行排序，且时延小的子路径对排序靠前。
15.根据权利要求9-14任一项所述的SDN控制器，其特征在于，所述选择单元具体用于：
根据预设公式计算得到所述第一业务的备选转发路径集合中的每条备选转发路径的得分；
根据所述第一业务的备选转发路径集合中每条备选转发路径的得分，对所述第一业务的备选转发路径集合中的备选转发路径进行排序，以得到排序后的备选转发路径；其中，得分小的备选转发路径的排序靠前；
从所述排序后的备选转发路径中，选择出所述第一业务的目标转发路径。
16.根据权利要求15所述的SDN控制器，其特征在于，所述备选转发路径包括多条链路；所述预设公式为：wi＝∑j1/bi,j；
其中，所述wi为第一业务的备选转发路径集合中的第i条备选转发路径的得分，所述bi,j为所述第i条备选转发路径中的第j条链路的剩余带宽。
17.一种软件定义网络SDN控制器，其特征在于，包括
存储有可执行程序代码的存储器；
与所述存储器耦合的处理器；
所述处理器调用所述存储器中存储的所述可执行程序代码，执行如权利要求1-8任一项所述的方法。
18.一种计算机可读存储介质，其特征在于，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行如权利要求1-8任一项所述的方法。
CN201810710799.1A 2018-06-30 2018-06-30 转发路径的计算方法及sdn控制器 Active CN110661704B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810710799.1A CN110661704B (zh) 2018-06-30 2018-06-30 转发路径的计算方法及sdn控制器

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810710799.1A CN110661704B (zh) 2018-06-30 2018-06-30 转发路径的计算方法及sdn控制器

Publications (2)

Publication Number Publication Date
CN110661704A true CN110661704A (zh) 2020-01-07
CN110661704B CN110661704B (zh) 2021-10-26

Family

ID=69027148

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810710799.1A Active CN110661704B (zh) 2018-06-30 2018-06-30 转发路径的计算方法及sdn控制器

Country Status (1)

Country Link
CN (1) CN110661704B (zh)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111786887A (zh) * 2020-06-30 2020-10-16 中国工商银行股份有限公司 由控制设备执行的数据转发方法、装置、计算设备和介质
CN114285789A (zh) * 2021-12-14 2022-04-05 国网吉林省电力有限公司信息通信公司 一种电力通信网中自动生成业务疏导方案的方法
CN114500354A (zh) * 2022-01-25 2022-05-13 中国农业银行股份有限公司 一种交换机控制方法、装置、控制设备及存储介质
WO2023125175A1 (zh) * 2021-12-31 2023-07-06 华为技术有限公司 一种算路系统路径推荐方法及相关设备

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101471853A (zh) * 2007-12-29 2009-07-01 华为技术有限公司 一种路由计算方法、单元及系统
CN103051533A (zh) * 2011-10-11 2013-04-17 中兴通讯股份有限公司 一种带保护业务的路由计算方法及装置
CN105049353A (zh) * 2015-07-28 2015-11-11 华为技术有限公司 一种为业务配置路由路径的方法及控制器
CN105429894A (zh) * 2015-11-30 2016-03-23 国网冀北电力有限公司信息通信分公司 一种电力通信网中业务路由选择方法及装置
US20160191391A1 (en) * 2014-12-29 2016-06-30 Juniper Networks, Inc. Point-to-multipoint path computation for wide area network optimization
CN106961343A (zh) * 2016-01-08 2017-07-18 中兴通讯股份有限公司 一种虚拟映射方法及装置
US9774520B1 (en) * 2008-10-20 2017-09-26 Juniper Networks, Inc. Service aware path selection with a network acceleration device
CN108040012A (zh) * 2017-12-05 2018-05-15 西南交通大学 基于天牛须搜索的sdn网络中多目标组播路由路径构建方法

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101471853A (zh) * 2007-12-29 2009-07-01 华为技术有限公司 一种路由计算方法、单元及系统
US9774520B1 (en) * 2008-10-20 2017-09-26 Juniper Networks, Inc. Service aware path selection with a network acceleration device
CN103051533A (zh) * 2011-10-11 2013-04-17 中兴通讯股份有限公司 一种带保护业务的路由计算方法及装置
US20160191391A1 (en) * 2014-12-29 2016-06-30 Juniper Networks, Inc. Point-to-multipoint path computation for wide area network optimization
CN105049353A (zh) * 2015-07-28 2015-11-11 华为技术有限公司 一种为业务配置路由路径的方法及控制器
CN105429894A (zh) * 2015-11-30 2016-03-23 国网冀北电力有限公司信息通信分公司 一种电力通信网中业务路由选择方法及装置
CN106961343A (zh) * 2016-01-08 2017-07-18 中兴通讯股份有限公司 一种虚拟映射方法及装置
CN108040012A (zh) * 2017-12-05 2018-05-15 西南交通大学 基于天牛须搜索的sdn网络中多目标组播路由路径构建方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
邱莉榕: "《算法设计与优化》", 28 February 2017, 中央民族大学出版社 *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111786887A (zh) * 2020-06-30 2020-10-16 中国工商银行股份有限公司 由控制设备执行的数据转发方法、装置、计算设备和介质
CN114285789A (zh) * 2021-12-14 2022-04-05 国网吉林省电力有限公司信息通信公司 一种电力通信网中自动生成业务疏导方案的方法
WO2023125175A1 (zh) * 2021-12-31 2023-07-06 华为技术有限公司 一种算路系统路径推荐方法及相关设备
CN114500354A (zh) * 2022-01-25 2022-05-13 中国农业银行股份有限公司 一种交换机控制方法、装置、控制设备及存储介质

Also Published As

Publication number Publication date
CN110661704B (zh) 2021-10-26

Similar Documents

Publication Publication Date Title
CN110661704B (zh) 转发路径的计算方法及sdn控制器
US7366114B2 (en) Method for providing QoS (quality of service)—guaranteeing multi-path and method for providing disjoint path using the same
JP5551253B2 (ja) 複数の等コストパスから選択するための方法および装置
US8897141B2 (en) Network system and routing method
CN101965715B (zh) 最短路径确定中的打破平局
TWI493926B (zh) 複雜型樹狀網路之自動化訊務工程
CN112738820A (zh) 一种服务功能链的动态部署方法、装置及计算机设备
JP5830539B2 (ja) タイブレーキング機構へのフィードバックとしてリンク利用を用いることに基づいた８０２．１ａｑのための自動化トラフィックエンジニアリング
US9680665B2 (en) Apparatus and method for dynamic hybrid routing in SDN networks to avoid congestion and balance loads under changing traffic load
TWI445361B (zh) 網路伺服器及其平均負載的路由方法
CN107294852B (zh) 一种使用拓扑分散短路径集的网络路由方法
EP3300413B1 (en) Method and apparatus for determining position of routing node and terminal equipment
EP2675120A1 (en) Path selection method and control server
CN104396198A (zh) 在最短路径确定中打破平局
CN105634974A (zh) 软件定义网络中的路由确定方法和装置
CN102420797B (zh) 一种拓扑映射方法及系统
US20120093164A1 (en) Method and Apparatus for Generating Constraint Route
CN112187642B (zh) 自适应路由的加权带宽分配
JP5595342B2 (ja) 複数経路探索方法及び装置
CN112995032B (zh) 一种基于受限最宽路径的段路由流量工程方法及装置
CN105306367A (zh) 通过网络传输信息的方法和用于通过网络传输信息的系统
CN111030852B (zh) 基于丢包率优化的服务功能链部署方法
CN109151621B (zh) 基于分层pce与双矩阵博弈的多域光网络静态组播保护方法
CN116057905A (zh) 网络子图根节点选择的参数化方法
CN111245719B (zh) 基于蚁群优化的纠删编码存储系统数据更新方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant