CN111385198B - 路径确定方法、装置及通信系统 - Google Patents

Abstract

本申请公开了一种路径确定方法、装置及通信系统，属于通信技术领域。所述方法包括：接收路径计算请求；当源节点所属源区域和目的节点所属目的区域为不同的区域时，从源区域开始沿远离源区域的方向依次对每个区域执行链路确定过程，得到每个区域中入口节点到每个出口节点链路代价最小的目标子链路；基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路。本申请解决了路径计算单元的运算代价较高，运算效率较低的问题。本申请用于确定节点之间的路径。

Description

路径确定方法、装置及通信系统

技术领域

本申请涉及通信技术领域，特别涉及一种路径确定方法、装置及通信系统。

背景技术

随着通信技术的发展，部署到网络中的节点(也称网元或通讯设备)越来越多，故网络中的节点相互连接构成的网络拓扑结构也变得越来越复杂。

相关技术中，网络中还可以部署有路径计算单元(path computation element，PCE)和路径计算客户端(path computation client，PCC)。PCC可以向PCE发送路径计算请求，以请求PCE计算网络中的源节点到目的节点(也称宿节点)之间的链路代价最小的目标路径。PCE在接收到该路径计算请求后，会从源节点开始沿远离所述源节点的方向依次遍历网络中位于源节点与目的节点之间的所有节点，并计算源节点到目的节点之间的所有可行路径，也即是确定源节点到目的节点之间的所有节点的数据传输组合方式，最后在所有可行路径中确定目标路径。

但是，随着网络中的节点数量的增加，PCE需要依次遍历源节点与目的节点之间的其他节点，确定所有可行路径，PCE的运算代价较高，运算效率较低。

发明内容

本申请提供了一种路径确定方法、装置及通信系统，可以解决路径计算单元的运算代价较高，运算效率较低。

第一方面，提供一种路径确定方法，用于通信系统中的路径计算单元，通信系统包括相互连接且互不重叠的多个区域，每个区域包括多个节点，方法包括：接收路径计算请求，路径计算请求用于请求计算源节点到目的节点的链路代价最小的目标链路；当源节点所属源区域和目的节点所属目的区域为不同的区域时，从源区域开始沿远离源区域的方向依次对每个区域执行链路确定过程，得到每个区域中入口节点到每个出口节点链路代价最小的目标子链路；基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路；

其中，源区域中的入口节点为源节点，多个区域中除源区域之外的区域的入口节点为与前一个区域的出口节点连接的节点，多个区域中除目的区域之外的区域的出口节点为与后一个区域连接的节点，目的区域的出口节点为目的节点。

由于本申请通过分区域进行路径计算，仅需确定各个区域的目标子链路的组合方式，而无需确定源节点到目的节点之间的所有节点的数据传输组合方式，因此减少了路径计算单元的运算代价，提高了运算效率。

在一种可能的实现方式中，对于每个区域，链路确定过程包括：确定入口节点到每个出口节点的可行子链路；基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价；基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价，其中，源区域中的入口节点的初始链路代价为0，多个区域中除源区域之外的区域的入口节点的初始链路代价为：入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价；

基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路，包括：将目的区域中的目标子链路所属的可行链路确定为目标链路。

在另一种可能的实现方式中，对于每个区域，链路确定过程包括：确定入口节点到每个出口节点的可行子链路；基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价，入口节点的初始链路代价为0；基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价；

基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路，包括：基于每个区域的目标子链路的链路代价，以及每两个相邻区域的链路代价，确定所述目标链路。

在另一种可能的实现方式中，基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价，包括：按照单源最短路径算法，基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价。

在另一种可能的实现方式中，当多个区域为至少三个区域时，从源区域开始沿远离源区域的方向，多个区域中至少两个区域的链路确定过程并行执行。由于多个区域的链路确定过程并行执行，故可以提高路径计算单元确定通信系统中多个区域的目标子链路的速率。

在另一种可能的实现方式中，在接收路径计算请求之前，方法还包括：将通信系统中的多个节点进行划分得到多个区域；或者，接收区域划分信息，区域划分信息用于指示通信系统中多个区域包括的节点的信息。

在另一种可能的实现方式中，将通信系统中的多个节点进行划分得到多个区域，包括：获取通信系统的资源信息，资源信息包括通信系统中的多个节点间的连接关系；根据资源信息按照划分规则，将通信系统中的多个节点进行划分得到多个区域。

按照该划分规则划分得到的多个区域规模大小较为均衡，且各个区域与其他区域的连接数较小，则路径计算单元对每个区域执行链路确定过程的时间差异较小，利于各个区域的链路确定过程的并行执行，路径计算单元计算目标链路的速率可以较快。且虚拟机计算对应区域中的链路需耗费的计算资源大致相同，故可以采用相同性能的虚拟机对各个区域中的链路进行计算，无需对不同的区域分配不同性能的虚拟机，进而可以提高链路确定效率。且在通信系统中部署的节点增多使得通信系统中的区域增多时，仅需在路径计算单元中增加相同性能的虚拟机即可，路径计算单元的适应性较好，通用性较高。并且，通过设置多个虚拟机来进行执行上述链路确定过程，可以实现链路确定过程的并行计算。

在另一种可能的实现方式中，根据资源信息按照划分规则，将通信系统中的多个节点进行划分得到多个区域，包括：在通信系统中的多个节点中确定多个待划分节点，待划分节点连接的节点数大于第二连接个数阈值，或者所述待划分节点为指定类型的节点，或者所述待划分节点为所述通信系统中的非底层节点；根据资源信息按照划分规则，将所述多个待划分节点进行划分得到多个过渡区域；将通信系统中除待划分节点之外的剩余节点，划分至剩余节点连接的节点所属的过渡区域中，得到多个区域。

在另一种可能的实现方式中，根据资源信息按照划分规则，将所述多个待划分节点进行划分得到多个过渡区域，包括：按照待划分节点采用的数据传输控制类型，对多个待划分节点进行初步划分，得到多个初始区域；根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域。

在另一种可能的实现方式中，根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域，包括：基于社区发现算法，根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域。

在另一种可能的实现方式中，划分规则包括：各个区域的节点个数差异小于差异个数阈值，以及每个区域连接的区域个数小于第一连接个数阈值中的至少一项。

在另一种可能的实现方式中，路径计算单元包括与多个区域一一对应的多个虚拟机，每个区域中的目标子链路由对应的虚拟机计算。

第二方面，本申请提供一种路径确定装置，该路径确定装置包括用于执行第一方面或第一方面任一种可能实现方式中的路径确定方法的各个模块。

第三方面，本申请提供一种通信系统，该通信系统包括多个节点、路径计算单元和路径计算客户端，多个节点、路径计算单元和路径计算客户端相互连接，该路径计算单元包括第二方面所述的路径确定装置。

第四方面，本申请提供一种路径计算单元，包括：至少一个处理器、至少一个接口、存储器和至少一个通信总线，处理器用于执行第一方面或第一方面任一种可能实现方式中的路径确定方法。

第五方面，本申请提供一种计算机可读存储介质，所述计算机可读存储介质中存储有指令，当其在计算机上运行时，使得计算机执行上述各方面所述的方法。

第六方面，本申请提供一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述各方面所述的方法。

本申请在上述各方面提供的实现方式的基础上，还可以进行进一步组合以提供更多实现方式。

附图说明

图1是本申请实施例提供的一种通信系统的结构示意图；

图2是本申请实施例提供的一种路径计算方法的流程图；

图3是本申请实施例提供的一种划分得到多个区域的方法流程图；

图4是本申请实施例提供的一种通信系统中的部分区域的示意图；

图5是本申请实施例提供的一种链路确定过程的流程图；

图6是本申请实施例提供的另一种链路确定过程的流程图；

图7是本申请实施例提供的一种路径计算单元的结构示意图；

图8是本申请实施例提供的一种通信系统中一个区域的结构示意图；

图9是本申请实施例提供的一种路径确定装置的结构示意图；

图10是本申请实施例提供的一种子链路确定模块的结构示意图；

图11是本申请实施例提供的另一种子链路确定模块的结构示意图；

图12是本申请实施例提供的另一种路径确定装置的结构示意图；

图13是本申请实施例提供的再一种路径确定装置的结构示意图；

图14是本申请实施例提供的一种划分模块的结构示意图；

图15是本申请实施例提供的一种路径计算单元的结构示意图。

具体实施方式

为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施方式作进一步地详细描述。

图1是本申请实施例提供的一种通信系统的结构示意图。如图1所示，该通信系统10包括相互连接且不重叠的多个区域Q、路径计算单元和路径计算客户端。其中，该通信系统10也可以称为通信网络，例如光传送网，通信系统10中的每个区域Q可以包括多个节点(也称网元或通讯设备)101，该多个区域Q可以通过其中的节点101建立相互之间的通信连接(如有线连接或无线连接)。

示例地，路径计算单元可以为独立的设备，或者也可以集成在服务器102内部(图1以路径计算单元集成在服务器内部为例进行说明)，或者也可以集成在一个服务器集群或云计算中心中。路径计算客户端可以安装在用户设备(User Equipment，UE)103上，当用户为个人用户或企业用户时，用户设备103可以为手机或者电脑等终端；当用户为企业用户时，用户设备103也可以为服务器。通信系统10中的多个节点101分别和用户设备103与服务器102均建立有通信连接，且该多个节点101之间也建立有通信连接，构成网络拓扑结构。路径计算单元可以获取通信系统10的所有节点信息和链路信息。其中，节点信息为用于表征节点的属性或特征的信息，其包括节点的标识(如节点的编号或名称)、所在位置和设备类型等中的至少一种。节点的设备类型可以用节点能够接入的网络类型表征，如若该通信系统为光传送网，节点的设备类型可以为多业务光传送网(multi-service opticaltransport network，MSOTN)类型或自动交换光网络(automatically switched opticalnetwork，ASON)类型等。若该通信系统为光传送网，则节点信息还可以包括节点传输数据所需的光波长。链路信息为用于表征链路的属性或特征的信息，包括各个节点之间的连接关系、连接各个节点的线缆传输数据的时延以及线缆中剩余的数据传输通道等中的至少一种。需要说明的是，每条线缆中可以有至少一个数据传输通道，通常有多个数据传输通道，不同的数据传输通道可以用于传输不同的数据，线缆中剩余的数据传输通道也即是线缆中空闲的未用于传输数据的通道。当通信系统为光传送网时，链路信息还可以包括线缆能够传输的光的波长。图1中的节点间的连接关系及区域中的节点个数仅为示意，本申请实施例对区域Q中的节点间的连接关系及节点个数并不限定。

路径计算客户端可以被授权获取通信系统10中源节点与目的节点的节点信息，且路径计算客户端可以在用户的触发下，向路径计算单元发送路径计算请求，以请求路径计算单元计算源节点到目的节点之间的目标链路。示例地，该路径计算请求可以携带有源节点的标识和目的节点的标识，该目标链路可以为链路代价最小的链路。链路代价表示业务通过该链路所消耗的代价。任意两个节点间的链路可能经过多条线缆以及多个节点，链路的链路代价可以通过该链路传输数据的时延，和/或，该链路经过的节点数表征，其中，链路传输数据的时延与链路代价正相关，也即是，链路传输数据的时延越小，链路代价越少；链路经过的节点数与链路代价正相关，链路经过的节点数越少，链路代价越少。

图2是本申请实施例提供的一种路径确定方法的流程图。该方法可以用于图1所示的通信系统10中的路径计算单元，如图2所示，该方法可以包括：

步骤201、将通信系统中的多个节点进行划分得到多个区域。

在该通信系统中，每个节点与至少一个节点建立有通信连接，每个节点与其他节点的连接关系反映了该节点与其他节点进行数据交互的情况，也即是，若某一节点仅与一个节点连接，则该某一节点与其他节点进行数据交互的频率较低，若某一节点与多个节点连接，则该某一节点与其他节点进行数据交互的频率较高。路径计算单元可以根据每个节点与其他节点的连接关系，将通信系统中的多个节点划分得到多个区域，且将数据交互频率较高的节点划分在同一区域中，将数据交互频率较低的节点划分在不同区域中。

示例地，请参考图3，步骤201可以包括：

步骤2011、获取通信系统的资源信息。

通信系统的资源信息可以包括通信系统中各个节点间的连接关系，该连接关系包括各个节点连接的节点的标识及连接的节点数等中的至少一个。可选地，该连接关系还可以包括通信系统中的节点个数、节点所在位置(例如该节点在通信系统中的位置坐标)以及各个节点之间连接的线缆的信息等中的至少一种。其中，线缆的信息可以包括：线缆的链路代价(如该线缆传输数据的时延)、线缆的数据传输通道个数和线缆能够传输的数据类型等中的至少一种。

步骤2012、根据资源信息按照划分规则，将通信系统中的多个节点进行划分得到多个区域。

示例的，该划分规则包括：各个区域的节点个数差异小于差异个数阈值，以及每个区域连接的区域个数小于第一连接个数阈值中的至少一项。示例地，该差异个数阈值为50，该第一连接个数阈值为20。在本申请实施例中，区域划分方式可以有多种，本申请对此不做限定，只要保证最终划分得到的多个区域符合上述划分规则即可。

根据前述的区域划分原理，要将数据交互频率较低的节点划分在不同区域中，则需使划分得到的多个区域间的数据交互频率较低。某一区域与其他区域的数据交互频率可以用该区域连接的其他区域的个数反映，如某一区域连接的区域个数与该区域和其他区域的数据交互频率正相关，故可以使划分得到的每个区域连接的区域个数较小。使各个区域的节点个数差异小于差异个数阈值，也即是使划分得到的各个区域的规模较为均衡，以便于提高区域划分的效率。

在一种可选的实现方式中，路径计算单元可以直接基于划分规则进行多个区域的划分。例如采用预先建立的规则划分模型来进行该多个区域的划分。

在另一种可选的实现方式中，由于通信系统中存在较多节点仅与少量(如1个或2个)的其他节点连接，为了提高区域划分的效率，路径计算单元可以基于划分规则进行多次划分，以得到多个区域。例如，可以先对少量的主要节点进行划分得到过渡区域，再对多数的次要节点进行划分得到最终的多个区域，其中主要节点连接的节点数大于次要节点连接的节点数。也即是可以先对通信系统中连接的节点数较多的节点进行划分，接着将通信系统中剩余的节点划分至其连接的节点所属的区域。则该步骤2012可以包括以下步骤：

步骤X1、在通信系统中的多个节点中确定多个待划分节点。

如前所述，路径计算单元可以先确定通信系统中连接的节点数较多的节点，将该节点确定为待划分节点，也即前述的主要节点，再对待划分节点进行划分。其中，待划分节点连接的节点数(也称为节点的出入度)可以大于第二连接个数阈值，也即是，路径计算单元可以将通信系统中连接的节点数大于第二连接个数阈值的节点确定为待划分节点。第二连接个数阈值可以为2，可选地，该第二连接个数阈值也可以为3或4，本申请实施例对此不做限定。

可选地，路径计算单元也可以根据通信系统中各个节点的设备类型确定通信系统中的待划分节点，该设备类型可以用于反映节点的最大可连接节点数。例如，路径计算单元也可以将设备类型为第一指定类型的节点确定为待划分节点，该第一指定类型反映的最大可连接节点数大于或等于第二连接个数阈值，又或者，路径计算单元也可以将设备类型为第二指定类型的节点之外的节点确定为待划分节点，该第二指定类型反映的最大可连接节点数小于或等于第二连接个数阈值。例如，通信系统为光传送网，第二指定设备类型为光交换网络(optical switch network，OSN)1800I/II设备类型，第二连接个数阈值为3，而OSN1800I/II设备类型反映的最大可连接节点数为2，该最大可连接节点数小于第二连接个数阈值，故可以确定该节点为通信系统中除待划分节点之外的剩余节点。其中，“1800I/II”为一种多业务传送平台(multi-service transport platform，MSTP)的类型，多业务传送平台是指同时实现数据传输通道的时分复用(time division multiplexing，TDM)、数据的异步传输(asynchronous transfer mode，ATM)以及以太网等业务的接入、处理和传送，用于提供统一网管的节点。

另外，通信系统中的各个节点通常按照层级连接，通信系统包括多个级别的网络，高级别的网络可以对多个低级别的网络进行管理。如通信系统为光传送网时，该通信系统包括国干网、多个省干网、多个城域网和多个接入环网，其中，国干网可以为上级网络，各个省干网可以为国干网的下级网络，各个城域网可以为对应省的省干网的下级网络，各个接入环网为对应城域网的下级网络。国干网可以对各个省干网进行管理，每个省干网可以对省域范围的各个城域网进行管理，每个城域网可以对城市范围内的接入环网进行管理。多个级别的网络可以根据地理位置划分，也可以根据网络部署的逻辑原则划分。下级网络可以获取本级网络中的节点信息，并将该信息发送至管理该下级网络的上级网络，以便该上级网络对该下级网络进行管理。

示例地，通信系统中国干网包括多个第三节点，每个省干网包括多个第二节点，每个城域网包括多个第一节点。每个城域网中的第一节点可以连接至一个第二节点，该第二节点用于管理该组第一节点，或者为该组第一节点提供数据接入或转发服务，其可以称为第一节点的汇聚节点(如网管设备或无线网络接入点)。每个省干网中的第二节点又可以均连接至一个第三节点，该第三节点用于管理该组第二节点，或者为该组第二节点提供数据接入或转发服务，其可以称为第二节点的汇聚节点(如网管设备或无线网络接入点)。

示例地，某地区可以设置有基站，且该地区中的通讯设备(如手机)均会连接至该基站，且通过该基站传输数据。该地区中的通讯设备均可以为通信系统中的一个节点，该基站可以为该地区中的通讯设备的一个汇聚节点。

可选地，由于层级高的节点可以做层级低的节点的汇聚节点，而汇聚节点连接的节点数较多，因此，本申请实施例中的待划分节点也可以为通信系统中的非底层的节点。例如，假设前述第一节点为底层的节点，则本申请实施例中的待划分节点为第二节点和第三节点。

步骤X2、根据资源信息按照划分规则，将多个待划分节点进行划分得到多个过渡区域。

在一种可选的实现方式中，路径计算单元可以直接基于划分规则将多个待划分节点进行划分得到过渡区域。例如采用预先建立的规则划分模型来进行该多个过渡区域的划分。

在另一种可选的实现方式中，由于通信系统中待划分节点的数据传输控制类型可能不同，为了提高区域划分的效率，路径计算单元可以先基于待划分节点的数据传输控制类型进行粗划分。然后再基于划分规则进行细化分得到过渡区域。则该步骤X2可以包括以下步骤：

步骤X21、按照待划分节点采用的数据传输控制类型，对多个待划分节点进行初步划分，得到多个初始区域。

通信系统可以包括控制平面与传送平面，控制平面用于控制传送平面的多个节点传输数据，控制平面可以包括光层与电层这两层网络。数据传输控制类型指的是控制平面控制各个节点进行数据传输所基于的网络类型。通信系统中采用相同数据传输控制类型的各个节点之间相互连接的可能性较大，该各个节点进行数据交互的频率较高。故可以先按照各个节点采用的数据传输控制类型对通信系统中的待划分节点进行初步划分，将通信系统中采用相同数据传输控制类型的待划分节点划分至同一初始区域。

例如，该数据传输控制类型可以包括：自动交换光网络(automatically switchedoptical network，ASON)控制类型和全静态控制类型。其中，ASON控制类型指多个节点传输数据的过程由控制平面控制的网络类型，全静态控制类型指多个节点传输数据的过程不由控制平面控制的网络类型。另外，基于ASON控制类型的控制平面能够在任意两个节点间的原链路出现故障时，自动计算新的链路并控制该两个节点通过该新的链路传输数据。全静态控制类型的网络中会预先为任意两个节点均分配两条用于数据传输的链路，分别为主链路和备链路，在该两个节点间的该两条链路中，若传输数据的主链路出现故障，则启用备链路传输数据。

可选地，ASON控制类型可以细分为：电层ASON控制类型、光层ASON控制类型和光电ASON控制类型。电层ASON控制类型即为仅通过控制平面中的电层控制各个节点传送数据的网络类型，光层ASON控制类型即为仅通过控制平面中的光层控制各个节点传送数据的网络类型，光电ASON控制即为同时通过控制平面中的光层与电层控制各个节点传送数据的网络类型。

步骤X22、根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域。

示例地，可以基于社区发现算法，对该多个初始区域中每个初始区域的待划分节点进行划分，进而得到多个过渡区域。该社区发现算法可以为GN算法(也即是Newman andGirvan算法)，或者也可以为其他算法，如标签传播算法(label propagation algorithm，LPA)等，本申请实施例对此不做限定。

在采用GN算法对初始区域进行划分时，可以将初始区域中连接任意两个待划分节点的光纤线缆记为边，然后确定每条边的介数。该介数也即是该每条边所属的目标链路数，该目标链路为通信系统中两个节点之间链路代价最小的链路。接着删除通信系统中介数最大的边，并重新计算通信系统中剩下的边的介数。重复该删除边与重新计算介数的过程，直至通信系统中的待划分节点分为多个独立的过渡区域，每个过渡区域中的待划分节点通过未被删除的边连接，且各个过渡区域中的待划分节点个数差异小于差异个数阈值。

步骤X3、将通信系统中除待划分节点之外的剩余节点，划分至剩余节点连接的节点所属的过渡区域中，得到所述多个区域。

其中，剩余节点连接的节点数小于或等于第二连接个数阈值，且通常该第二连接个数阈值较小(例如2或3)。若剩余节点仅与一个节点连接，则可以直接将该剩余节点划分至其连接的节点所属的过渡区域中；若该剩余节点与多个节点连接，则可以将该剩余节点划分至其连接的任一节点所属的过渡区域中，且一个剩余节点仅可被划分至一个过渡区域。

需要说明的是，上述步骤2012中的划分规则中的阈值设定可以根据实际的应用场景变化，例如，在上述步骤2012的两种可选实现方式中，划分规则中的差异个数阈值可以相同也可以不同，第一连接个数阈值可以相同也可以不同。

本申请实施例仅以路径计算单元对通信系统中的多个节点进行划分得到多个区域为例。可选地，若路径计算单元安装在服务器上，则在服务器启动时，该路径计算单元就可以执行步骤201，也即是对通信系统中的多个节点进行划分得到多个区域。可选地，该多个区域也可以由通信系统中的其他节点划分得到区域划分信息并存储在该其他节点，或者由工作人员预先划分得到区域划分信息并存储在存储设备，该区域划分信息用于指示通信系统中多个区域包括的节点的信息。在这种情况下，路径计算单元仅需接收该其他节点或存储设备发送的区域划分信息，基于该区域划分信息确定当前通信系统中多个区域包括的节点的信息，无需执行上述步骤201。

步骤202、接收路径计算请求。

示例地，通信系统中连接各个节点的光纤线缆为预先布置完成的，企业用户可以通过路径计算客户端请求路径计算单元为该企业分配专用的数据传输链路，该数据传输链路即为路径计算单元需确定的目标链路。或者，当用户需在源节点与目的节点之间传输数据时，用户可以通过路径计算客户端请求路径计算单元确定传输数据的目标链路。

该路径计算请求可以携带有源节点的标识和目的节点的标识，该目标链路可以为源节点到目的节点的链路代价最小的链路。需要说明的是，在用户的需求不同时，链路代价可以通过不同的参数表征。例如，该链路代价可以用链路传输数据的时延表征，或者该链路代价也可以用链路经过的节点个数表征，本申请实施例对此不做限定。可选地，该路径计算请求还可以携带有用于表征链路代价的参数。

步骤203、当源区域和目的区域为不同的区域时，从源区域开始沿远离源区域的方向依次对每个区域执行链路确定过程，得到每个区域中的入口节点到每个出口节点链路代价最小的目标子链路。

其中，源区域为通信系统中的多个区域中源节点所属的区域，目的区域为该多个区域中目的节点所属的区域。源区域中的入口节点为源节点，多个区域中除源区域之外的区域的入口节点为与前一个区域的出口节点连接的节点，多个区域中除目的区域之外的区域的出口节点为该区域中与后一个区域连接的节点，目的区域的出口节点为目的节点。

以通信系统中的两个区域为例，假设该两个区域分别为第一区域与第二区域，第一区域与源区域直接连接，第二区域通过第一区域与源区域连接，则可以确定第一区域为第二区域的前一个区域，第二区域为第一区域的后一个区域。远离源区域的方向为第一区域到第二区域的方向。

示例地，图4示出了通信系统中的部分区域的示意图。假设，该通信系统中的路径计算单元接收到路径计算请求，且该路径计算请求计算源节点101a与目的节点101h之间的目标路径，则路径计算单元可以确定在图4所示的通信系统中，101a所在的区域Q0为源区域，目的节点101h所在的区域Q2为目的区域。如图4所示，源区域Q0包括源节点101a、节点101b和节点101c，第一区域Q1包括节点101d、节点101e和节点101f，目的区域Q2包括目的节点101h、节点101m和节点101n。源区域Q0中的节点101c与区域Q1中的节点101d连接，区域Q1中的节点101e与目的区域Q2中的节点101m连接。在图4所示的该种通信系统中，源区域Q0中的源节点101a为入口节点，节点101c为出口节点；第一区域Q1中的节点101d为入口节点，节点101e为出口节点；目的区域Q2中的节点101m为入口节点，目的节点101h为出口节点。需要说明的是，图4中示出的各个区域仅用于对各个区域的入口节点与出口节点进行解释，对本申请实施例中各个区域的节点个数与连接关系不作限定。

可选地，当多个区域为至少三个区域时，从源区域开始沿远离源区域的方向，多个区域中至少两个区域的链路确定过程可以并行执行。若图4所示的通信系统还包括第三区域(图4中未示出)，且源区域与目的区域还可以通过该第三区域连接，则在对源区域执行链路确定过程之后，可以并行执行对第一区域的链路确定过程和对第三区域的链路确定过程。另外，对第一区域和第三区域中的任一区域的链路执行过程执行完毕后，均可以开始对目的区域执行链路确定过程。如在对第一区域的链路确定过程执行完毕后，就可以开始执行对目的区域的链路确定过程，若此时对第三区域的链路确定过程还未执行完毕，则可以并行执行对第三区域的链路确定过程和对目的区域的链路确定过程。

需要说明的是，由于在步骤201中划分得到的多个区域规模大小较为均衡，且各个区域与其他区域的连接数较小，则路径计算单元对每个区域执行链路确定过程的时间差异较小，利于各个区域的链路确定过程的并行执行，路径计算单元计算目标链路的速率可以较快。

本申请实施例中的链路确定过程可以有多种实现方式，本申请实施例以以下两种实现方式为例进行解释说明。

第一种实现方式，请参考图5，链路确定过程中可以包括：

步骤501、确定入口节点到每个出口节点的可行子链路。

示例地，对于图4所示的通信系统中的区域Q0，入口节点101a到出口节点101c的可行子链路包括：“101a→101c”和“101a→101b→101c”这两条可行子链路。其中，“A→B”表示节点A直接到节点B的链路，且节点A与节点B直接连接。示例地，“101a→101c”表示从入口节点101a直接到出口节点101c的子链路，“101a→101b→101c”表示从入口节点101a经过节点101b再到出口节点101c的子链路。

步骤502、基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价，其中，源区域中的入口节点的初始链路代价为0，多个区域中除源区域之外的区域的入口节点的初始链路代价为：入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价。

示例地，以图4中的源区域Q0为例，假设链路代价通过链路传输数据的时延表征，且入口节点101a的初始链路代价为t0，节点101a直接到节点101b的链路代价为t1，节点101b直接到节点101c的链路代价为t2，节点101a直接到节点101c的链路代价为t3；此种情况下，可行子链路“101a→101b→101c”的链路代价为t0+t1+t2，可行子链路“101a→101c”的链路代价为t0+t3。

可选地，路径计算单元可以按照单源最短路径算法，基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价。该单源最短路径算法包括：迪杰斯特拉(Dijkstra，DJ)算法和最短路径快速算法(Shortest Path Faster Algorithm，SPFA)算法中的至少一种，SPFA算法也称为贝尔曼-福特算法的队列优化形式。

步骤503、基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价。

示例地，对于通信系统中的每个区域，路径计算单元均可以对该区域中每个入口节点到每个出口节点的多个可行子链路的链路代价进行比较，并将每个入口节点到每个出口节点的链路代价最小的可行子链路确定为该区域的一个目标子链路。且路径计算单元可以记录每个目标子链路的链路代价。

第二种实现方式，请参考图6，链路确定过程中可以包括：

步骤601、确定入口节点到每个出口节点的可行子链路。

步骤601可以参考步骤501，本申请实施例对此不再赘述。

步骤602、基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价，入口节点的初始链路代价为0。

其中，入口节点到出口节点的可行子链路的链路代价可以为：该可行子链路中每两个相邻节点间的链路代价之和。示例地，以图4中的源区域Q0为例，假设链路代价通过链路传输数据的时延表征，且入口节点101a的初始链路代价为0，节点101a直接到节点101b的链路代价为t1，节点101b直接到节点101c的链路代价为t2，节点101a直接到节点101c的链路代价为t3；此种情况下，可行子链路“101a→101b→101c”的链路代价为t1+t2，可行子链路“101a→101c”的链路代价为t3。

步骤602中的其他过程可以参考步骤502，本申请实施例对此不再赘述。

步骤603、基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价。

步骤603可以参考步骤503，本申请实施例对此不再赘述。可选地，路径计算单元可以记录各个目标子链路与该目标子链路的链路代价的对应关系并存储。

需要说明的是，目标子链路的链路代价可以通过不同的参数表征，且在用于表征目标子链路的链路代价的参数不同时，目标子链路所属区域的入口节点的初始链路代价会不同，目标子链路的链路代价也会不同。

在上述第一种实现方式中，目标子链路的链路代价通过源节点到该目标子链路的出口节点的最小链路代价表征，目标子链路的链路代价与该目标子链路之前链路的链路代价相关。此时，若目标子链路所属区域为源节点所属的源区域(该区域的入口节点为源节点)，则入口节点的初始链路代价为0。若目标子链路所属区域为通信系统中的多个区域中除源区域之外的区域，则入口节点的初始链路代价为：入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价。例如，对于图4所示的通信系统，假设链路代价为链路传输数据的时延，源区域Q0中源节点101a到节点101c的目标子链路为“101a→101c”，且该目标子链路的链路代价为100毫秒，则第一区域Q1的入口节点101d的初始链路代价为100毫秒。若第一区域Q1中的目标子链路“101d→101f→101e”传输数据的时延为50毫秒，则该目标子链路“101d→101f→101e”的链路代价为100毫秒+50毫秒＝150毫秒。

在上述第二种实现方式中，目标子链路的链路代价可以仅用该目标子链路本身的链路代价表征，目标子链路的链路代价与该目标子链路之前链路的链路代价不相关。此时目标子链路所属的区域中入口节点的初始链路代价均为0。若链路代价用链路传输数据的时延表征，且第一区域Q1中的目标子链路“101d→101f→101e”传输数据的时延为50毫秒，则该目标子链路“101d→101f→101e”的链路代价为50毫秒。

步骤204、基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路。

第一方面，对应于上述步骤203中的第一种实现方式，在步骤204中路径计算单元可以直接将目的区域中的目标子链路所属的可行链路确定为目标链路。如前所述，源节点到目的节点之间存在多条可行链路，路径计算单元记录各个目标子链路的链路代价与该目标子链路所属的已遍历链路的对应关系并存储，在确定了目的区域中的目标子链路后，该目标子链路所属的已遍历链路即为目标子链路所属的可行链路，将该可行链路确定为目标链路。

示例地，对于图4所示的通信系统，若路径计算单元确定目的区域中的目标子链路为“101m→101h”，且在路径计算单元记录的对应关系中，该目标子链路所属的已遍历链路为可行链路“101a→101c→101d→101f→101e→101m→101h”，则可以直接将该可行链路确定为源节点到目的节点的链路代价最小的目标链路。

可选地，路径计算单元在执行上述步骤203的第一种实现方式的过程中，在确定每个目标子链路后，需要对该目标子链路上的节点进行标记，以便在步骤204中基于该目标子链路确定目标链路。

第一种可选的实现方式，路径计算单元在执行上述步骤203的第一种实现方式的过程中，对每个区域中位于目标子链路上的节点进行标记，在执行完步骤203之后，基于标记的结果以及记录的链路代价，从目标区域开始逆向(即从目的节点到源节点的方向)依次获取每个区域对应的最优前向目标子链路，直至获取到源区域中的目标子链路，将获取的目标子链路连接得到的一条链路确定为目的区域中的目标子链路所属的可行链路，该可行链路即为目标链路。其中，任一区域的最优前向目标子链路为该区域中的目标子链路连接的目标子链路中链路代价最小的子链路。

在第二种可选的实现方式，路径计算单元在执行上述步骤203的第一种实现方式的过程中，指示每个节点记录该每个节点的最优前向节点，以对每个节点最优前向节点进行标记，任一节点的最优前向节点为该任一节点与源节点之间链路代价最小的链路中，与该任一节点直接连接的节点。在路径计算单元确定目的区域中的目标子链路后，可以从目的节点开始逆向(即从目的节点到源节点的方向)依次获取每个节点对应的最优前向节点，直至获取到源节点。并按照获取顺序将获取的节点连接得到一条链路，该链路即为目的区域中的目标子链路所属的可行链路，将该可行链路确定为目标链路。此种情况下，每个节点中仅需存储一个节点的信息，路径计算单元在确定目标链路时仅需依次获取各个节点的最优前向节点就可以得到目标链路，故对各个节点和路径计算单元的资源占用均较少。

当然，路径计算单元在执行上述步骤203的第一种实现方式的过程中，路径计算节点还可以将确定的所有目标子链路与其链路代价的对应关系进行记录，基于该对应关系，确定目的区域中的目标子链路所属的可行链路，并将目的区域中的目标子链路所属的可行链路确定为目标链路。

第二方面，对应于上述步骤203中的第二种实现方式，在步骤204中，路径计算单元可以基于每个区域的目标子链路的链路代价，以及每两个相邻区域的链路代价，确定目标链路。

需要说明的是，路径计算单元在执行上述步骤203的第二种实现方式的过程中，各个入口节点的初始链路代价为0，实际上指的是若该入口节点所属区域之前连接有另一区域，则假设该入口节点与连接的前一个区域的出口节点的链路代价为0，这样在计算当前区域的目标子链路时不考虑在先区域的影响。实际计算过程中，路径计算单元可以记录每两个相邻的区域之间的链路代价，即后一个区域的入口节点与前一个区域的出口节点之间的链路代价，以便确定目标链路。例如，图4中，区域Q0和区域Q1的链路代价为节点101c与节点101d之间的链路代价。

在一种可选示例中，从源区域开始沿远离源区域的方向，将确定的多个目标子链路进行组合，得到源节点到目的节点之间的多条可行链路。接着，将组成每条可行链路的目标子链路的链路代价之和确定为每条可行链路的链路代价，并将多条可行链路中链路代价最小的链路确定为目标链路。如前所述，路径计算单元可以记录各个目标子链路与该目标子链路的链路代价的对应关系并存储。路径计算单元可以查询该对应关系得到该多个目标子链路，并将得到的多个目标子链路进行组合。

示例地，对于图4所示的通信系统，假设目标子链路的链路代价采用第二种链路代价表征方式，且源区域Q0中的目标子链路包括“101a→101c”，第一区域Q1中的目标子链路包括“101d→101f→101e”，目的区域Q2中的目标子链路包括“101m→101n→101h”，则路径计算单元可以对该三个区域中的目标子链路进行组合，得到第一可行链路“101a→101c→101d→101f→101e→101m→101h”。若源区域、第一区域与目的区域并不包括其他目标子链路，则路径计算单元会将该第一可行链路确定为源节点到目的节点的目标链路。若源区域、第一区域与目的区域还包括其他目标子链路，则路径计算单元可以将目标子链路“101a→101c”、“101d→101f→101e”和“101m→101h”的链路代价，以及每两个区域的链路代价(即“101c→101d”之间的链路代价和“101e→101m”之间的链路代价)之和确定为该第一可行链路的链路代价。接着路径计算单元对各个区域中的目标子链路进行组合会得到其他可行链路，并会将该第一可行链路与该其他可行链路中链路代价较小的可行链路，确定为源节点到目的节点的目标链路。

在另一种可选示例中，路径计算单元也可以采用前述第一方面的确定目标链路的方式，在执行上述步骤203的第二种实现方式的过程中，在确定每个目标子链路后，对该目标子链路上的节点进行标记，然后采用上述第一方面的两种可选的实现方式来确定目标链路。

可选地，在路径计算单元在确定出源节点到目的节点之间的链路代价最小的目标链路后，可以将该目标链路的信息发送至路径计算客户端，以将该目标链路的信息告知用户。该目标链路的信息可以包括：目标链路的链路代价，以及目标链路所经过的节点与光纤线缆等。用户获知该目标链路的信息可以便于对目标链路的维护，或者基于该目标链路进行数据传输。

路径计算单元可以包括多个虚拟机(Virtual Machine，VM)，多个虚拟机与多个区域一一对应，每个区域中的目标子链路由对应的虚拟机计算，也即是每个虚拟机用于执行上述链路确定过程，即执行上述步骤501至503，或执行上述步骤601至603。该多个虚拟机可以部署于一个或多个设备中。每个虚拟机可以包括一个或多个计算实例。如前所述，通信系统中的该多个区域中每个区域中的节点个数可以大致相同，如每个区域的节点个数范围可以为350～450。这样一来，虚拟机计算对应区域中的链路需耗费的计算资源大致相同，故可以采用相同性能的虚拟机对各个区域中的链路进行计算，无需对不同的区域分配不同性能的虚拟机，进而可以提高链路确定效率。且在通信系统中部署的节点增多使得通信系统中的区域增多(可以将新增的节点单独划分一个区域，或者对整个通信系统的节点重新执行上述步骤201，以划分得到新的区域)时，仅需在路径计算单元中增加相同性能的虚拟机即可，路径计算单元的适应性较好，通用性较高。并且，通过设置多个虚拟机来进行执行上述链路确定过程，可以实现链路确定过程的并行计算。

请参考图7，图7为本申请实施例提供的一种路径计算单元70的结构示意图，该路径计算单元70包括划分模块701、路径计算控制模块702和与多个区域一一对应的多个虚拟机703，该划分模块701用于执行上述步骤201，每个虚拟机703用于执行上述链路确定过程，路径计算控制模块702用于执行上述步骤202、步骤203中除虚拟机703所执行的过程，以及步骤204。

如图8所示，假设一个区域包括6个节点，采用传统的路径确定方法，路径计算单元需要遍历该区域中的每个节点，运算复杂度较高，而本申请中，对应于上述步骤203中的第一种实现方式，路径计算控制模块702无需参与虚拟机的计算过程，只需基于目标区域所对应的虚拟机输出的链路代价来确定目标链路；对应于上述步骤203中的第二种实现方式，路径计算控制模块702无需参与虚拟机的计算过程，只需基于各个虚拟机输出的链路代价之和来确定目标链路，通过对路径计算单元中的各个功能单元的合理划分，使得路径计算单元的整体运算复杂度较低。图8是以上述步骤203中的第一种实现方式为例进行说明的，图8中虚拟机所对应的区域的初始链路代价为100，目标子链路共3个，链路代价分别为111、105和103。

需要说明的是，随着通信技术的发展，通信系统中的节点个数越来越多。如今，通信系统已覆盖三百多个城市，该网络中已存在超过十万个节点。很快网络中的网元个数将会达到三十万个节点，届时现有技术中路径计算单元计算单条目标链路约需10秒左右的时间，较难满足对路径计算单元的计算效率的要求。而本申请实施例提供的路径确定方法中，分区域进行路径计算，且各个区域的链路确定过程可以并行执行，即使网络中的节点数量达到三十万，也可以使路径计算单元在200毫秒内确定单条目标链路，可以满足对路径计算单元的计算效率的要求。

综上所述，本申请实施例提供的路径确定方法中，分别确定每个区域中入口节点到每个出口节点链路代价最小的目标子链路，并基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，确定目标链路。这样通过分区域进行路径计算，仅需确定各个区域的目标子链路的组合方式，而无需确定源节点到目的节点之间的所有节点的数据传输组合方式，因此减少了路径计算单元的运算代价，提高了运算效率。另外，多个区域的链路确定过程可以并行执行，进一步提高了路径计算单元的运算效率。

图9是本申请实施例提供的一种路径确定装置的结构示意图。该路径确定装置可以用于图1所示的通信系统10中的路径计算单元，通信系统10包括相互连接且互不重叠的多个区域，每个区域包括多个节点。如图9所示，该路径计算装置90可以包括：

第一接收模块901，用于接收路径计算请求，路径计算请求用于请求计算源节点到目的节点的链路代价最小的目标链路。

子链路确定模块902，用于当源节点所属源区域和目的节点所属目的区域为不同的区域时，从源区域开始沿远离源区域的方向依次对每个区域执行链路确定过程，得到每个区域中入口节点到每个出口节点链路代价最小的目标子链路。

链路确定模块903，用于基于每个区域中入口节点到每个出口节点链路代价最小的目标子链路，将源节点到目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路；

其中，源区域中的入口节点为源节点，多个区域中除源区域之外的区域的入口节点为与前一个区域的出口节点连接的节点，多个区域中除目的区域之外的区域的出口节点为与后一个区域连接的节点，目的区域的出口节点为目的节点。

综上所述，本申请实施例提供的路径确定装置中，子链路确定模块分别确定每个区域中入口节点到每个出口节点链路代价最小的目标子链路，链路确定模块基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，确定目标链路。这样通过分区域进行路径计算，仅需确定各个区域的目标子链路的组合方式，而无需确定源节点到目的节点之间的所有节点的数据传输组合方式，因此减少了路径确定装置的运算代价，提高了运算效率。

可选地，如图10所示，子链路确定模块902可以包括：

第一确定子模块9021，用于确定每个区域中，入口节点到每个出口节点的可行子链路。

第一计算子模块9022，用于基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价。

第二确定子模块9023，用于基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价，其中，源区域中的入口节点的初始链路代价为0，多个区域中除源区域之外的区域的入口节点的初始链路代价为：入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价。

链路确定模块903，用于将目的区域中的目标子链路所属的可行链路确定为目标链路。

可选地，如图11所示，子链路确定模块902可以包括：

第三确定子模块9024，用于确定每个区域中，入口节点到每个出口节点的可行子链路。

第二计算子模块9025，用于基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价，入口节点的初始链路代价为0。

第四确定子模块9026，用于基于计算的链路代价，将入口节点到每个出口节点的链路代价最小的可行子链路确定为目标子链路，并记录目标子链路的链路代价。

链路确定模块903用于：基于每个区域的目标子链路的链路代价，以及每两个相邻区域的链路代价，确定目标链路。

可选地，子链路确定模块902用于：按照单源最短路径算法，基于入口节点的初始链路代价，计算入口节点到每个出口节点的可行子链路的链路代价。

可选地，子链路确定模块902用于：当多个区域为至少三个区域时，从源区域开始沿远离源区域的方向，并行执行多个区域中至少两个区域的链路确定过程。

可选地，如图12所示，在图9的基础上，路径确定装置90还包括：

划分模块904，用于在接收路径计算请求之前，将通信系统中的多个节点进行划分得到多个区域；

或者，如图13所示，在图9的基础上，路径确定装置90还包括：

第二接收模块905，用于在接收路径计算请求之前，接收区域划分信息，区域划分信息用于指示通信系统中多个区域包括的节点的信息。

可选地，如图14所示，划分模块904包括：

获取子模块9041，用于获取通信系统的资源信息，资源信息包括通信系统中的多个节点间的连接关系。

划分子模块9042，用于根据资源信息按照划分规则，将通信系统中的多个节点进行划分得到多个区域。

可选地，划分子模块9042用于：

在通信系统中的多个节点中确定多个待划分节点，待划分节点连接的节点数大于第二连接个数阈值，或者待划分节点为指定类型的节点，或者待划分节点为通信系统中的非底层节点；根据资源信息按照划分规则，将多个待划分节点进行划分得到多个过渡区域；将通信系统中除待划分节点之外的剩余节点，划分至剩余节点连接的节点所属的过渡区域中，得到多个区域。

可选地，划分子模块9042用于：

按照待划分节点采用的数据传输控制类型，对多个待划分节点进行初步划分，得到多个初始区域；根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域。

可选地，划分子模块9042用于：基于社区发现算法，根据资源信息按照划分规则，对多个初始区域进行划分得到多个过渡区域。

可选地，划分规则包括：各个区域的节点个数差异小于差异个数阈值，以及每个区域连接的区域个数小于第一连接个数阈值中的至少一项。

可选地，路径计算单元包括与所述多个区域一一对应的多个虚拟机，每个所述区域中的目标子链路由对应的虚拟机计算。

综上所述，本申请实施例提供的路径确定装置中，子链路确定模块分别确定每个区域中入口节点到每个出口节点链路代价最小的目标子链路，链路确定模块基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，确定目标链路。这样通过分区域进行路径计算，仅需确定各个区域的目标子链路的组合方式，而无需确定源节点到目的节点之间的所有节点的数据传输组合方式，因此减少了路径确定装置的运算代价，提高了运算效率。

图15是本申请实施例提供的一种路径计算单元的结构示意图。如图15所示，路径计算单元150可以包括：至少一个处理器1501(例如中央处理器)、至少一个网络接口1502、存储器1503和至少一个总线1504，总线1504用于实现处理器、网络接口和存储器之间的连接通信；存储器1503与网络接口1502分别通过总线1504与处理器1501相连。处理器1501用于执行存储器1503中存储的可执行模块，例如计算机程序。存储器1503可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，存储器1503可能包含高速随机存取存储器(Random Access Memory，RAM)，也可能还包括非不稳定的存储器(non-volatilememory)，例如至少一个磁盘存储器。通过至少一个网络接口1502(有线或者无线)实现该装置与至少一个其他装置之间的通信连接。在一些实施方式中，存储器1503存储了程序以及模块，该程序或模块能够被处理器1501执行以实现本申请实施例提供的路径确定方法。如图15所示，该存储器1503中可以存储划分模块1503a、路径计算控制模块1503b和虚拟机1503c，以及至少一个其它功能所需的应用程序。处理器1501可以执行存储器1503中的划分模块1503a以实现上述步骤201，处理器1501可以执行虚拟机1503c以实现上述步骤203中的链路确定过程，处理器1501可以执行路径计算控制模块1503b以实现上述步骤202、步骤203中除虚拟机1503c所执行的过程，以及步骤204。其中，划分模块1503a的功能可以参考图7中划分模块701的功能，路径计算控制模块1503b的功能可以参考图7中路径计算控制模块702的功能，虚拟机1503c的功能可以参考图7中虚拟机703的功能，本申请实施例在此不做赘述。

示例地，上述通信连接均可以通过有线网络或者无线网络连接，其中，有线网络可以包括但不限于：采用光纤、通用串行总线(universal serial bus，USB)、同轴电缆或双绞线等来连接的计算机网络，无线网络可以包括但不限于：无线保真(wireless fidelity，WIFI)、蓝牙、红外、紫蜂(Zigbee)、数据网络等。

上述实施例，可以全部或部分地通过软件、硬件、固件或其他任意组合来实现。当使用软件实现时，上述实施例可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载或执行所述计算机程序指令时，全部或部分地产生按照本申请实施例所述的流程或功能。所述计算机可以为通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(DSL))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集合的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质(例如，软盘、硬盘、磁带)、光介质(例如，DVD)、或者半导体介质。半导体介质可以是固态硬盘(solid state drive，SSD)。

需要说明的是：上述实施例提供的路径确定装置在确定目标链路时，仅以上述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能模块完成，即将路径计算单元的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。另外，上述实施例提供的路径确定装置与路径确定方法实施例属于同一构思，其具体实现过程详见方法实施例，这里不再赘述。

上述本申请实施例序号仅仅为了描述，不代表实施例的优劣。以上所述仅为本申请的可选实施例，并不用以限制本申请，凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。

Claims (27)

1.一种路径确定方法，其特征在于，用于通信系统中的路径计算单元，所述通信系统包括相互连接且互不重叠的多个区域，每个所述区域包括多个节点，所述方法包括：

接收路径计算请求，所述路径计算请求用于请求计算源节点到目的节点的链路代价最小的目标链路；

当所述源节点所属源区域和所述目的节点所属目的区域为不同的区域时，从源区域开始沿远离所述源区域的方向依次对每个所述区域执行链路确定过程，得到每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路；

基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，将所述源节点到所述目的节点之间的多条可行链路中链路代价最小的链路确定为所述目标链路；

其中，所述源区域中的入口节点为所述源节点，所述多个区域中除所述源区域之外的区域的入口节点为与前一个区域的出口节点连接的节点，所述多个区域中除所述目的区域之外的区域的出口节点为与后一个区域连接的节点，所述目的区域的出口节点为所述目的节点。

2.根据权利要求1所述的方法，其特征在于，对于每个所述区域，所述链路确定过程包括：

确定入口节点到每个出口节点的可行子链路；

基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价；

基于计算的链路代价，将所述入口节点到每个出口节点的链路代价最小的可行子链路确定为所述目标子链路，并记录所述目标子链路的链路代价，其中，所述源区域中的入口节点的初始链路代价为0，所述多个区域中除所述源区域之外的区域的入口节点的初始链路代价为：所述入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价；

所述基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，将所述源节点到所述目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路，包括：

将所述目的区域中的目标子链路所属的可行链路确定为所述目标链路。

3.根据权利要求1所述的方法，其特征在于，对于每个所述区域，所述链路确定过程包括：

确定入口节点到每个出口节点的可行子链路；

基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价，所述入口节点的初始链路代价为0；

基于计算的链路代价，将所述入口节点到每个出口节点的链路代价最小的可行子链路确定为所述目标子链路，并记录所述目标子链路的链路代价；

所述基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，将所述源节点到所述目的节点之间的多条可行链路中链路代价最小的链路确定为目标链路，包括：

基于每个区域的目标子链路的链路代价，以及每两个相邻区域的链路代价，确定所述目标链路。

4.根据权利要求2或3所述的方法，其特征在于，所述基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价，包括：

按照单源最短路径算法，基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价。

5.根据权利要求1至3任一所述的方法，其特征在于，当所述多个区域为至少三个区域时，从源区域开始沿远离所述源区域的方向，所述多个区域中至少两个区域的链路确定过程并行执行。

6.根据权利要求1至3任一所述的方法，其特征在于，在所述接收路径计算请求之前，所述方法还包括：

将所述通信系统中的多个节点进行划分得到所述多个区域；

或者，接收区域划分信息，所述区域划分信息用于指示所述通信系统中所述多个区域包括的节点的信息。

7.根据权利要求6所述的方法，其特征在于，所述将所述通信系统中的多个节点进行划分得到所述多个区域，包括：

获取通信系统的资源信息，所述资源信息包括所述通信系统中的多个节点间的连接关系；

根据所述资源信息按照划分规则，将所述通信系统中的多个节点进行划分得到所述多个区域。

8.根据权利要求7所述的方法，其特征在于，所述根据所述资源信息按照划分规则，将所述通信系统中的多个节点进行划分得到所述多个区域，包括：

在所述通信系统中的多个节点中确定多个待划分节点，所述待划分节点连接的节点数大于第二连接个数阈值，或者所述待划分节点为指定类型的节点，或者所述待划分节点为所述通信系统中的非底层节点；

根据所述资源信息按照划分规则，将所述多个待划分节点进行划分得到多个过渡区域；

将所述通信系统中除所述待划分节点之外的剩余节点，划分至所述剩余节点连接的节点所属的过渡区域中，得到所述多个区域。

9.根据权利要求8所述的方法，其特征在于，所述根据所述资源信息按照划分规则，将所述多个待划分节点进行划分得到多个过渡区域，包括：

按照所述待划分节点采用的数据传输控制类型，对所述多个待划分节点进行初步划分，得到多个初始区域；

根据所述资源信息按照划分规则，对所述多个初始区域进行划分得到所述多个过渡区域。

10.根据权利要求9所述的方法，其特征在于，所述根据所述资源信息按照划分规则，对所述多个初始区域进行划分得到所述多个过渡区域，包括：

基于社区发现算法，根据所述资源信息按照划分规则，对所述多个初始区域进行划分得到所述多个过渡区域。

11.根据权利要求7所述的方法，其特征在于，

所述划分规则包括：各个所述区域的节点个数差异小于差异个数阈值，以及每个所述区域连接的区域个数小于第一连接个数阈值中的至少一项。

12.根据权利要求1至3任一所述的方法，其特征在于，所述路径计算单元包括与所述多个区域一一对应的多个虚拟机，每个所述区域中的目标子链路由对应的虚拟机计算。

13.一种路径确定装置，其特征在于，用于通信系统中的路径计算单元，所述通信系统包括相互连接且互不重叠的多个区域，每个所述区域包括多个节点，所述路径确定装置包括：

接收模块，用于接收路径计算请求，所述路径计算请求用于请求计算源节点到目的节点的链路代价最小的目标链路；

子链路确定模块，用于当所述源节点所属源区域和所述目的节点所属目的区域为不同的区域时，从源区域开始沿远离所述源区域的方向依次对每个所述区域执行链路确定过程，得到每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路；

链路确定模块，用于基于每个所述区域中入口节点到每个出口节点链路代价最小的目标子链路，将所述源节点到所述目的节点之间的多条可行链路中链路代价最小的链路确定为所述目标链路；

其中，所述源区域中的入口节点为所述源节点，所述多个区域中除所述源区域之外的区域的入口节点为与前一个区域的出口节点连接的节点，所述多个区域中除所述目的区域之外的区域的出口节点为与后一个区域连接的节点，所述目的区域的出口节点为所述目的节点。

14.根据权利要求13所述的路径确定装置，其特征在于，所述子链路确定模块包括：

第一确定子模块，用于确定每个所述区域中，入口节点到每个出口节点的可行子链路；

第一计算子模块，用于基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价；

第二确定子模块，用于基于计算的链路代价，将所述入口节点到每个出口节点的链路代价最小的可行子链路确定为所述目标子链路，并记录所述目标子链路的链路代价，其中，所述源区域中的入口节点的初始链路代价为0，所述多个区域中除所述源区域之外的区域的入口节点的初始链路代价为：所述入口节点连接的前一个区域的出口节点所属的目标子链路的链路代价；

所述链路确定模块用于：

将所述目的区域中的目标子链路所属的可行链路确定为所述目标链路。

15.根据权利要求13所述的路径确定装置，其特征在于，所述子链路确定模块包括：

第三确定子模块，用于确定每个所述区域中，入口节点到每个出口节点的可行子链路；

第二计算子模块，用于基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价，所述入口节点的初始链路代价为0；

第四确定子模块，用于基于计算的链路代价，将所述入口节点到每个出口节点的链路代价最小的可行子链路确定为所述目标子链路，并记录所述目标子链路的链路代价；

所述链路确定模块用于：

基于每个区域的目标子链路的链路代价，以及每两个相邻区域的链路代价，确定所述目标链路。

16.根据权利要求14或15所述的路径确定装置，其特征在于，所述子链路确定模块用于：

按照单源最短路径算法，基于所述入口节点的初始链路代价，计算所述入口节点到每个出口节点的可行子链路的链路代价。

17.根据权利要求13至15任一所述的路径确定装置，其特征在于，所述子链路确定模块用于：

当所述多个区域为至少三个区域时，从源区域开始沿远离所述源区域的方向，并行执行所述多个区域中至少两个区域的链路确定过程。

18.根据权利要求13至15任一所述的路径确定装置，其特征在于，所述路径确定装置还包括：

划分模块，用于在所述接收路径计算请求之前，将所述通信系统中的多个节点进行划分得到所述多个区域；

或者，第二接收模块，用于在所述接收路径计算请求之前，接收区域划分信息，所述区域划分信息用于指示所述通信系统中所述多个区域包括的节点的信息。

19.根据权利要求18所述的路径确定装置，其特征在于，所述划分模块包括：

获取子模块，用于获取通信系统的资源信息，所述资源信息包括所述通信系统中的多个节点间的连接关系；

划分子模块，用于根据所述资源信息按照划分规则，将所述通信系统中的多个节点进行划分得到所述多个区域。

20.根据权利要求19所述的路径确定装置，其特征在于，所述划分子模块用于：

在所述通信系统中的多个节点中确定多个待划分节点，所述待划分节点连接的节点数大于第二连接个数阈值，或者所述待划分节点为指定类型的节点，或者所述待划分节点为所述通信系统中的非底层节点；

根据所述资源信息按照划分规则，将所述多个待划分节点进行划分得到多个过渡区域；

将所述通信系统中除所述待划分节点之外的剩余节点，划分至所述剩余节点连接的节点所属的过渡区域中，得到所述多个区域。

21.根据权利要求20所述的路径确定装置，其特征在于，所述划分子模块用于：

按照所述待划分节点采用的数据传输控制类型，对所述多个待划分节点进行初步划分，得到多个初始区域；

根据所述资源信息按照划分规则，对所述多个初始区域进行划分得到所述多个过渡区域。

22.根据权利要求21所述的路径确定装置，其特征在于，所述划分子模块用于：

基于社区发现算法，根据所述资源信息按照划分规则，对所述多个初始区域进行划分得到所述多个过渡区域。

23.根据权利要求19所述的路径确定装置，其特征在于，

所述划分规则包括：各个所述区域的节点个数差异小于差异个数阈值，以及每个所述区域连接的区域个数小于第一连接个数阈值中的至少一项。

24.根据权利要求13至15任一所述的路径确定装置，其特征在于，所述路径计算单元包括与所述多个区域一一对应的多个虚拟机，每个所述区域中的目标子链路由对应的虚拟机计算。

25.一种通信系统，其特征在于，所述通信系统包括：多个节点、路径计算单元和路径计算客户端，所述多个节点、所述路径计算单元和所述路径计算客户端相互连接，所述路径计算单元包括权利要求13至24任一所述的路径确定装置。

26.一种路径确定装置，其特征在于，所述路径确定装置包括：至少一个处理器、至少一个接口、存储器和至少一个通信总线，所述处理器用于执行权利要求1至12任一所述的路径确定方法。

27.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有指令，当所述计算机可读存储介质中存储的指令在计算机上运行时，使得计算机执行如权利要求1至12任一所述的路径确定方法。

Images