路由查询方法及装置

摘要

本发明公开了一种路由查询方法及装置，其中，路由查询方法包括：在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；根据第一链路标记和第二链路标记确定满足约束条件的路由。通过本发明，达到了只需一次查询就能获取满足约束条件的路由，使得查询次数减少，显著地提高了路由查询效率的效果。

权利要求

1.一种路由查询方法，其特征在于，包括：

在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与所述约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；

根据所述第一链路标记和第二链路标记确定满足所述约束条件的路由。

2.根据权利要求1所述的方法，其特征在于，所述业务属性为链路保护类型；所述为不完全匹配的链路设置第二链路标记的步骤包括：为不完全匹配且链路保护类型高于所述约束条件中的链路保护类型的链路设置第二链路标记。

3.根据权利要求1所述的方法，其特征在于，根据所述第一链路标记和第二链路标记确定满足所述约束条件的路由的步骤包括：判断所有可用路由中，是否存在所有链路标记均为所述第一链路标记的路由；

若是，则确定该路由为满足所述约束条件的路由；若否，则根据预先设定的规则从所述所有可用路由中确定一条路由，为满足所述约束条件的路由。

4.根据权利要求3所述的方法，其特征在于，所述预先设定的规则为链路代价最小规则。

5.根据权利要求1或2所述的方法，其特征在于，若所述确定的满足约束条件的路由包括多个，则根据设定的规则从所述多个路由中选择一个。

6.根据权利要求5所述的方法，其特征在于，所述设定的规则为路由选择优先级规则，所述路由选择优先级规则用于根据多个路由选择策略的不同优先级进行路由选择。

7.根据权利要求2所述的方法，其特征在于，所述第一链路标记设置为0，所述第二链路标记设置为1。

8.根据权利要求7所述的方法，其特征在于，根据所述第一链路标记和第二链路标记确定满足所述约束条件的路由的步骤包括：判断所有可用路由中，是否存在链路标记之和为零的路由；

若是，则确定该路由为满足所述约束条件的路由；若否，则根据预先设定的规则从所述所有可用路由中确定一条路由，为满足所述约束条件的路由。

9.一种路由查询装置，其特征在于，包括：

设置模块，用于在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与所述约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；

查询模块，用于根据所述第一链路标记和第二链路标记确定满足所述约束条件的路由。

10.根据权利要求9所述的装置，其特征在于，所述业务属性为链路保护类型；

所述设置模块为不完全匹配且链路保护类型高于所述约束条件中的链路保护类型的链路设置第二链路标记。

11.根据权利要求9或10所述的装置，其特征在于，所述查询模块包括：判断模块，用于判断所有可用路由中，是否存在所有链路标记均为所述第一链路标记的路由；

执行模块，用于若所述判断模块的判断结果为是，则确定该路由为满足所述约束条件的路由；若所述判断模块的判断结果为否，则根据预先设定的规则从所述所有可用路由中确定一条路由，为满足所述约束条件的路由。

12.根据权利要求11所述的装置，其特征在于，所述第一链路标记设置为0，所述第二链路标记设置为1；

所述判断模块，用于判断所有可用路由中，是否存在链路标记之和为零的路由；

所述执行模块，用于若所述判断模块的判断结果为是，则确定该路由为满足所述约束条件的路由；若所述判断模块的判断结果为否，则根据预先设定的规则从所述所有可用路由中确定一条路由，为满足所述约束条件的路由。

说明书

路由查询方法及装置

技术领域

[0001] 本发明涉及通信领域，具体而言，涉及一种路由查询方法及装置。

背景技术

[0002] 目前，各种网络中运用路由查询接口下发路由查询请求时，通常附带许多约束条件，例如：严格排除和松散排除、共享、抢占、必经、链路保护类型的严格匹配和向下兼容匹配等约束条件，以满足不同的路由查询需求。以ASON(Automatic Switched Optical Network，自动交换光网络)为例，由于路由查询时约束条件的增多，使得ASON的路由查询效率逐渐降低。

[0003] 如ASON中，以最短路径为路由查询的约束条件时，其主要通过CSPF(Constrained Shortest Path First，最短路径优先)约束式最短路径优先模块来实现。CSPF模块采用Dijkstra(迪杰斯特拉)算法来计算最短路径，而Dijkstra算法是业界常用的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路径，其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离，当所有边权重都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。

[0004] 若在最短路径的基础上，还要求在路由查询中关于链路保护类型的先严格匹配后向下兼容匹配约束，如图1所示，ASON下发查询1-4点的最短路径，假设ASON下发的查询请求还要求链路保护类型的先严格匹配后向下兼容匹配，即最短路径上的链路保护类型最好是与业务的保护类型完全匹配，若没有这样的路径，最短路径上的链路保护类型也可以是与业务的保护类型不完全匹配，但路径上的所有链路的保护类型要高于业务的保护类型。此时，传统的CSPF模块运用Dijkstra算法实现该约束条件的路由查询过程如下：

[0005] (1)，返回所有链路的链路保护类型与业务保护类型完全匹配的最短路径，否则路径查询失败。

[0006] (2)，在(1)的路径查询失败时，重新查询，返回并非所有的链路的链路保护类型与业务保护类型完全匹配的最短路径，否则路径查询失败。

[0007] 可见，上述路径查询过程中，当没有链路保护类型与业务保护类型完全匹配的最短路径时，需要经过回调向CSPF模块进行至少两次查询才能查找到满足该约束的路由。而当回调后，所有可用的且并非所有的链路的链路保护类型与业务保护类型完全匹配的最短路径有多条时，则还要进行多次查询才能最终确定满足约束的路由。这使得在进行带约束条件的路由查询时，路由查询次数较多，查询效率较低。

发明内容

[0008] 本发明的主要目的在于提供一种路由查询方法及装置，以至少解决上述的在进行带约束条件的路由查询时，路由查询次数较多，查询效率较低的问题。

[0009] 根据本发明的一个方面，提供了一种路由查询方法，包括：在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；根据第一链路标记和第二链路标记确定满足约束条件的路由。

[0010] 根据本发明的另一方面，提供了一种路由查询装置，包括：设置模块，用于在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；查询模块，用于根据第一链路标记和第二链路标记确定满足约束条件的路由。

[0011] 通过本发明，采用为完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记，使得在进行带约束条件的路由查询时，可以根据链路标记首先判断是否有完全匹配的路由，若没有，则根据第一链路标记和第二链路标记选择满足约束条件的路由，而不必回调查询，从而解决了路由查询次数较多，查询效率较低的问题，进而达到了只需一次查询就能获取满足约束条件的路由，使得查询次数减少，显著地提高了路由查询效率的效果。

附图说明

[0012] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

[0013] 图1是根据相关技术的一种路由查询方法中的路由示意图；

[0014] 图2是根据本发明实施例一的一种路由查询方法的步骤流程图；

[0015] 图3是根据本发明实施例二的一种路由查询方法中的步骤流程图；

[0016] 图4是根据本发明实施例三的一种路由查询方法中的路由示意图；

[0017] 图5是根据本发明实施例四的一种路由查询方法中的路由示意图；

[0018] 图6是根据本发明实施例五的一种路由查询装置的结构框图。

具体实施方式

[0019] 下文中将参考附图并结合实施例来详细说明本发明。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

[0020] 参照图2，示出了根据本发明实施例一的一种路由查询方法的步骤流程图，包括以下步骤：

[0021] 步骤S202：在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；

[0022] 本实施例适用于以业务属性的先严格匹配后向下兼容匹配为约束条件的路由查询。通过在进行路由查询过程中，需要从多个节点中选择出满足条件的路由，而任意两个直接相连的节点之间都会存在一条链路，多个节点间则存在多条链路，本步骤中，为多条链路中存在的那些业务属性与约束条件中的业务属性完全一致(即完全匹配)的链路设置第一链路标记，为不完全一致(即不完全匹配)的链路设置第二链路标记。

[0023] 其中，业务属性可以为任意适当的路由选择时的业务属性，如链路保护类型，或者，如链路的安全级别等。

[0024] 步骤S204：根据第一链路标记和第二链路标记确定满足约束条件的路由。

[0025] 本步骤中，根据设置的链路标记，包括第一链路标记和第二链路标记，确定满足业务属性的先严格匹配后向下兼容匹配的约束条件的路由。如，因一个路由可能包括多个链路，那么在多个可用路由中，选择其中那个所有链路标记均为第一链路标记的那个路由，作为满足约束条件的路由，若没有这样的路由，则从所有可用路由中，根据设定规则选择一个，如链路代价最小规则等。

[0026] 相关技术中，在进行带约束条件的路由查询时，当没有完全匹配的路由时，需要回调再次重新查询，因而查询次数较多，查询效率较低。通过本实施例，采用为完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记，使得在进行带约束条件的路由查询时，可以根据链路标记首先判断是否有完全匹配的路由，若没有，则根据第一链路标记和第二链路标记选择满足约束条件的路由，而不必回调查询，从而解决了路由查询次数较多，查询效率较低的问题，进而达到了只需一次查询就能获取满足约束条件的路由，使得查询次数减少，显著地提高了路由查询效率的效果。

[0027] 参照图3，示出了根据本发明实施例二的一种路由查询方法的步骤流程图。本实施例中，针对ASON约束最短路径查询时间过长的缺陷，提供了一种提高ASON应用的带约束条件的最短路径查路效率的路由查询方法，使得ASON进行约束最短路径查询时能在更短的时间里返回相同的结果。

[0028] 本实施例的路由查询方法包括以下步骤：

[0029] 步骤S302：当源节点进行路由查询时，根据ASON下发业务的保护类型将该节点保存的全网拓扑数据库中在每条链路上新增一个链路保护类型完全匹配标志。

[0030] 例如，若链路的保护类型与业务的保护类型一致，则将该链路的链路保护类型完全匹配标志设置为0；若链路的保护类型与业务的保护类型不一致，但该链路的链路保护类型大于业务的保护类型，则将该链路的链路保护类型完全匹配标志设置为1；若链路的保护类型与业务的保护类型不一致，且链路的保护类型小于业务的保护类型，则该链路的链路保护类型完全匹配标志可以不设置，也可以随便设置值，但该值应为在传统的CSPF中会将该链路置为不可用的值。通过将链路保护类型完全匹配标志设置为0，将链路保护类型大于业务的保护类型的链路保护类型完全匹配标志设置为1，在进行链路保护类型完全匹配查找时，只需根据该路由的链路保护类型完全匹配标志是否为0即可确定是否完全匹配，极大地方便了查找，提高了查找效率。

[0031] 需要说明的是，也可以将链路保护类型完全匹配标志设置为其它值，这时，在判断是否完全匹配时，只需知道完全匹配的链路的个数，判断路由的链路保护类型完全匹配标志之和是否等于链路个数与设置的值的乘积，即可确定是否完全匹配。

[0032] 步骤S304：将源节点作为最短路径树的根节点。

[0033] 初始时，源节点为最短路径树的根节点。此时，各个比较单元都为0(其中，比较单元用于获取与本节点相连的下一个节点与本节点的metric(度)值，例如源节点到下一跳节点路径的总metric值，或源节点与下一跳节点的权重值等，本实施例中，可以为步骤S302中的链路保护类型匹配标志的总和等)。

[0034] 因为初始，所以此时下一跳节点依然是本节点。

[0035] 步骤S306：根据链路保护类型完全匹配标志，使用Dijkstra算法获取下一跳节点。

[0036] 本实施例中，若本节点与相连的下一跳节点的链路中，有链路保护类型完全匹配标志为0的链路，则选取该链路中与本节点相连的那个节点。

[0037] 需要说明的是，运用Dijkstra算法获取下一跳节点时，传统的比较方法是按照设定的比较策略的优先级顺序依次进行比较，如链路保护类型优先级高于链路代价优先级，则先按照链路保护类型进行路由选择，若选择出的路由有多个，再在选择出的路由中根据链路代价进行选择。而本实施例中，则是根据各个比较单元的实际应用场景，每个比较单元进行比较时不是严格的按照传统的优先级进行比较，而是当某个比较单元到达某种程度时，降低优先级级别进行接下来的比较。(如，以链路保护类型的比较为例，当两条路径的链路保护类型总和都大于等于1，如同为2时，认为该两条路径相同，此时对这两条路径的权重进行比较，选择代价较小，即权重值较小的那条路径。)

[0038] 步骤S308：重复步骤S306，获得到达目的节点的最短路径树。

[0039] 通过本实施例，在实现细节上突破了传统的CSPF在针对各个约束条件(比较单元)按固定优先级顺序的比较方法，而是根据约束条件的实际应用场景调整优先级进行比较，改进了传统CSPF模块实现链路保护类型匹配的方法，提高了ASON进行带约束条件的路由查询效率。

[0040] 参照图4，示出了根据本发明实施例三的一种路由查询方法中的路由示意图。图4中，黑色细线代表与路由查询请求完全匹配的保护类型链路，黑色粗线段代表可兼容路由查询请求保护类型链路，线段上的数字代表链路权重。

[0041] 本实施例的路由查询方法包括以下步骤：

[0042] 步骤S402：ASON向CSPF下发查询节点1到节点4的带约束条件的路由请求，该约束条件为：链路保护类型先严格匹配后向下兼容匹配。

[0043] 步骤S404：CSPF根据链路保护类型是否与约束条件中的链路保护类型完全匹配，对链路打上链路标记，标记该链路是否是完全匹配。

[0044] 本实施例中，设定节点1-2的链路标记为1，节点1-3的链路标记为0，节点2-3的链路标记为1，节点2-4的链路标记为0，节点3-4的链路标记为0。其中，0表示完全匹配，1表示不完全匹配且链路保护类型高于约束条件中的链路保护类型。

[0045] 步骤S406：将节点1到节点4路由上的所有链路的链路保护类型匹配标记累加。

[0046] 本实施例中，节点1到节点4有四条可用路由，分别是：节点1-2-4，节点1-3-4，节点1-2-3-4，节点1-3-2-4。其中，节点1-2-4的链路保护类型匹配标记的累加和为1，节点1-3-4的链路保护类型匹配标记的累加和为0，节点1-2-3-4的链路保护类型匹配标记的累加和为2，节点1-3-2-4的链路保护类型匹配标记的累加和为1。

[0047] 步骤S408：比较路由的链路保护类型匹配累加和，确定最优路由结果。

[0048] 本实施例中，路由1-3-4的链路保护类型标记的累加和为0，表示链路保护类型完全匹配。假设链路保护类型匹配优先级高于其它路由选择策略优先级，则确定路由1-3-4为最优路由结果。

[0049] 通过本实施例，CSPF模块通过设置完全匹配的链路保护类型标识为0，通过判断链路保护类型标记的累加和是否为0，即可快速判断出是否存在满足约束条件的最短路径，从而显著地提高了ASON的查路效率。

[0050] 参照图5，示出了根据本发明实施例四的一种路由查询方法中的路由示意图。图5中，黑色细线代表与路由查询请求完全匹配的保护类型链路，黑色粗线段代表可兼容路由查询请求保护类型链路，线段上的数字代表链路权重。

[0051] 本实施例的路由查询方法包括以下步骤：

[0052] 步骤S502：ASON向CSPF下发查询节点1到节点4的带约束条件的路由请求，该约束条件为：链路保护类型先严格匹配后向下兼容匹配。

[0053] 步骤S504：CSPF根据链路保护类型是否与约束条件中的链路保护类型完全匹配，对链路打上链路标记，标记该链路是否是完全匹配。

[0054] 本实施例中，设定节点1-2的链路标记为1，节点1-3的链路标记为0，节点2-3的链路标记为1，节点2-4的链路标记为0，节点3-4的链路标记为1。其中，0表示完全匹配，1表示不完全匹配且链路保护类型高于约束条件中的链路保护类型。

[0055] 步骤S506：将节点1到节点4路由上的所有链路的链路保护类型匹配标记累加。

[0056] 本实施例中，节点1到节点4有四条可用路由，分别是：节点1-2-4，节点1-3-4，节点1-2-3-4，节点1-3-2-4。其中，节点1-2-4的链路保护类型匹配标记的累加和为1，节点1-3-4的链路保护类型匹配标记的累加和为1，节点1-2-3-4的链路保护类型匹配标记的累加和为3，节点1-3-2-4的链路保护类型匹配标记的累加和为1。

[0057] 步骤S508：比较路由的链路保护类型匹配累加和，确定最优路由结果。

[0058] 本实施例中，四条路由中都没有链路保护类型完全匹配的，此时，则降低链路保护类型匹配优先级，即不再进行链路保护类型匹配的比较(只当链路保护类型匹配累加中有0时才比较)，而是根据设定的路由选择规则继续选择路由，以比较各路由的链路代价，即从多个路由中查询链路代价最小的路由为例，则继续比较四条路由的权重总和，根据比较结果，CSPF返回1-2-3-4为最优路由结果。

[0059] 这种情况下，约束条件要求若多条路径中包含超过1条链路保护类型向下兼容匹配的链路，且不考虑其他约束条件时，多条路径视为相同。此时，可以再根据其他约束条件从多条路径中最终选择出符合条件的路径。与目前CSPF对于链路保护类型匹配约束给外部提供的接口或者是完全匹配，或者是向下兼容匹配，如果ASON下发的路由查询要求链路保护类型匹配约束先严格匹配，如果没有则向下兼容匹配时，必须向CSPF查询两次才能返回路由相比，本实施例的ASON只需要向CSPF查询一次即可以返回链路保护类型匹配先严格后向下兼容的路由，而无须回调查询，减少了查询次数，提高了查询效率。

[0060] 当然，在所有路由中均没有链路保护类型完全匹配的路由时，本领域技术人员也可以设定其他比较条件，以选择出合适的路由，本发明对此不作限制。

[0061] 参照图6，示出了根据本发明实施例五的一种路由查询装置的结构框图，包括：

[0062] 设置模块602，用于在以业务属性的先严格匹配后向下兼容匹配为约束条件进行路由查询时，为待查询的多条链路中存在的业务属性与约束条件中的业务属性完全匹配的链路设置第一链路标记，为不完全匹配的链路设置第二链路标记；查询模块604，用于根据第一链路标记和第二链路标记确定满足约束条件的路由。

[0063] 优选的，业务属性为链路保护类型；设置模块602为不完全匹配且链路保护类型高于约束条件中的链路保护类型的链路设置第二链路标记。

[0064] 优选的，查询模块604包括：判断模块6042，用于判断所有可用路由中，是否存在所有链路标记均为第一链路标记的路由；执行模块6044，用于若判断模块6042的判断结果为是，则确定该路由为满足约束条件的路由；若判断模块6042的判断结果为否，则根据预先设定的规则从所有可用路由中确定一条路由，为满足约束条件的路由。

[0065] 优选的，上述预先设定的规则为链路代价最小规则。

[0066] 优选的，查询模块604还包括：选择模块，用于若确定的满足约束条件的路由包括多个，则根据设定的规则从多个路由中选择一个。优选的，该设定的规则为路由选择优先级规则，路由选择优先级规则用于根据多个路由选择策略的不同优先级进行路由选择。

[0067] 优选的，第一链路标记设置为0，第二链路标记设置为1；判断模块6042用于判断所有可用路由中，是否存在链路标记之和为零的路由；执行模块6044用于若判断模块6042的判断结果为是，则确定该路由为满足约束条件的路由；若判断模块6044的判断结果为否，则根据预先设定的规则从所有可用路由中确定一条路由，为满足约束条件的路由。

[0068] 需要说明的是，本发明的多个实施例均以ASON为例，但本发明的路由查询方法及装置，不仅适用于ASON网络，也适用于其它使用路由查询的网络。此外，本发明的多个实施例中的约束条件均以链路保护类型的先严格匹配后向下兼容匹配为例，但不限于此，所有要求先严格匹配后向下兼容匹配的约束条件均可适用本发明的方法和装置，本发明对此不作限制。并且，本发明的多个实施例使用Dijkstra算法查找最短路径，但不限于此，本领域技术人员还可以根据实际需要，选择其它适当的最短路径查找算法，本发明对此也不作限制。

[0069] 本发明针对现有技术中带约束路由查询时间长，查询次数多，查询效率低的缺陷，提供了一种带约束条件的路由查询方案。该方案在进行查询路由时，要求返回的路由的所有链路的业务属性最好是与约束条件中的业务属性完全匹配，如果没有这样的路径，路径上某些链路的业务属性也可以与约束条件的业务属性不完全匹配。按照传统的实现该约束条件的方式，则在路由查询中关于业务属性的先严格匹配后向下兼容匹配约束时需要回调两次才能查询到满足要求的路径。而通过本发明的技术方案，可以实现一次查询就能返回满足约束条件的路径，使得路由查询次数减少，显著地提高了查路效率。

[0070] 显然，本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，并且在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

[0071] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。