[go: up one dir, main page]

CN108900413B - A routing path selection method, device, electronic device and storage medium - Google Patents

A routing path selection method, device, electronic device and storage medium Download PDF

Info

Publication number
CN108900413B
CN108900413B CN201810570409.5A CN201810570409A CN108900413B CN 108900413 B CN108900413 B CN 108900413B CN 201810570409 A CN201810570409 A CN 201810570409A CN 108900413 B CN108900413 B CN 108900413B
Authority
CN
China
Prior art keywords
routing path
satisfies
shortest
constraint condition
condition
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.)
Expired - Fee Related
Application number
CN201810570409.5A
Other languages
Chinese (zh)
Other versions
CN108900413A (en
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.)
Beijing University of Posts and Telecommunications
Original Assignee
Beijing University of Posts and Telecommunications
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 Beijing University of Posts and Telecommunications filed Critical Beijing University of Posts and Telecommunications
Priority to CN201810570409.5A priority Critical patent/CN108900413B/en
Publication of CN108900413A publication Critical patent/CN108900413A/en
Application granted granted Critical
Publication of CN108900413B publication Critical patent/CN108900413B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/02Topology update or discovery
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/12Shortest path evaluation
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/22Alternate routing

Landscapes

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

Abstract

本发明实施例提供了一种路由路径选择方法、装置、电子设备及存储介质,其中,该方法包括:获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。

Figure 201810570409

Embodiments of the present invention provide a routing path selection method, apparatus, electronic device, and storage medium, wherein the method includes: acquiring two restriction conditions, and taking the first restriction condition among the two restriction conditions as the first restriction condition , when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, and when the routing path that satisfies the first constraint condition satisfies the two constraint conditions In the case of the second restriction condition in the restriction conditions, it is determined that the routing path satisfying the first restriction condition is the optimal routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions.

Figure 201810570409

Description

一种路由路径选择方法、装置、电子设备及存储介质A routing path selection method, device, electronic device and storage medium

技术领域technical field

本发明涉及软件定义网络技术领域,特别是涉及一种路由路径选择方法、装置、电子设备及存储介质。The present invention relates to the technical field of software-defined networks, and in particular, to a routing path selection method, apparatus, electronic device and storage medium.

背景技术Background technique

随着SDN的出现,用户对网络的期待也逐渐增高,用户希望网络可以对不同类型的数据流提供不同的服务保障,即差异化服务。有一些普通数据流对QoS(Quaility ofService,服务质量)要求不高,可以采用普通的路由算法进行路由路径选择,但是有一些重要的数据流对QoS有严格的要求,需要考虑多个限制条件,如何在的复杂的网络中根据用户提出的多个限制条件,高效快速地选取符合该多个限制条件的可靠路由路径成为一个亟待解决的问题。With the emergence of SDN, users' expectations for the network are gradually increasing. Users hope that the network can provide different service guarantees for different types of data streams, that is, differentiated services. Some common data flows do not have high requirements on QoS (Quality of Service), and common routing algorithms can be used for routing path selection. However, some important data flows have strict requirements on QoS, and multiple constraints need to be considered. How to efficiently and quickly select a reliable routing path that meets the multiple constraints in a complex network based on multiple constraints proposed by users has become an urgent problem to be solved.

在现有技术中,有些研究人员提出了一种通过层次分析法选择路由路径的方法,具体地,该方法首先按照重要性比例标度构建包括所选择的限制条件的判断矩阵,然后计算该判断矩阵的特征向量,将该判断矩阵的特征向量,作为所选择的限制条件对应的权重值,然后计算所选择的限制条件的综合值,并根据该综合值选择路由路径,In the prior art, some researchers have proposed a method for selecting routing paths through AHP. Specifically, the method first constructs a judgment matrix including the selected constraints according to the importance scale, and then calculates the judgment matrix. The eigenvector of the matrix, the eigenvector of the judgment matrix is used as the weight value corresponding to the selected restriction condition, and then the comprehensive value of the selected restriction condition is calculated, and the routing path is selected according to the comprehensive value,

然而,发明人发现现有技术存在以下问题:However, the inventors found that the prior art has the following problems:

通过层次分析法选择路由路径时,该方法是将所选择的限制条件整合为综合值,再根据综合值进行路由路径选择的,该方法并不能保证选择的路由路径完全符合所选择的限制条件。When selecting routing paths through AHP, this method integrates the selected constraints into comprehensive values, and then selects routing paths according to the comprehensive values. This method cannot guarantee that the selected routing paths fully meet the selected constraints.

发明内容SUMMARY OF THE INVENTION

本发明实施例的目的在于提供一种路由路径选择方法、装置、电子设备及存储介质,以实现在网络拓扑中选择完全满足所选择的限制条件的路由路径。具体技术方案如下:The purpose of the embodiments of the present invention is to provide a routing path selection method, apparatus, electronic device and storage medium, so as to realize the selection of a routing path that fully satisfies the selected restriction conditions in the network topology. The specific technical solutions are as follows:

第一方面,本发明实施例提供了一种路由路径选择方法,应用于网络拓扑中,该方法包括:In a first aspect, an embodiment of the present invention provides a routing path selection method, which is applied to a network topology, and the method includes:

获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,其中,第一限制条件为两个限制条件中的任一限制条件;Obtain two restriction conditions, and use the first restriction condition in the two restriction conditions as the first restriction condition to determine whether there is a routing path that satisfies the first restriction condition in the network topology, wherein the first restriction condition is the two restriction conditions any of the restrictions in;

当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件;When there is a routing path that satisfies the first constraint condition in the network topology, it is judged whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, wherein the second constraint condition is that among the two constraint conditions, restrictions other than the first restriction;

当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。When the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, the routing path that satisfies the first constraint condition is determined to be the best routing path.

可选的,在判断网络拓扑中是否存在满足第一约束条件的路由路径之后,本发明实施例的一种路由路径选择方法,还包括:Optionally, after judging whether there is a routing path that satisfies the first constraint condition in the network topology, the method for selecting a routing path according to an embodiment of the present invention further includes:

当网络拓扑中不存在满足第一约束条件的路由路径时,根据两个限制条件,采用层次分析法在网络拓扑中选择最佳路由路径。When there is no routing path that satisfies the first constraint condition in the network topology, according to the two constraints, the best routing path is selected in the network topology by using AHP.

可选的,在判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件之后,本发明实施例的一种路由路径选择方法,还包括:Optionally, after judging whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, a routing path selection method according to an embodiment of the present invention further includes:

在满足第一约束条件的路由路径,不满足两个限制条件中的第二限制条件时,以第二限制条件为第二约束条件,在网络拓扑中选择满足第二约束条件的路由路径;When the routing path that satisfies the first constraint condition does not meet the second constraint condition of the two constraint conditions, the second constraint condition is used as the second constraint condition, and the routing path that satisfies the second constraint condition is selected in the network topology;

根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。According to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition, the Lagrangian relaxation algorithm is used to calculate the optimal routing path.

可选的,根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径,包括:Optionally, according to the routing path that satisfies the first constraint condition and the routing path that satisfies the second constraint condition, a Lagrangian relaxation algorithm is used to calculate the optimal routing path, including:

根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式According to the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, through the first formula

Figure GDA0002629676720000021
Figure GDA0002629676720000021

计算拉格朗日松弛算法的第j次迭代时的迭代因子λj,其中,λj为第j次迭代时的迭代因子,c(pr)为第一最短路由路径pr的第一路由路径信息,d(pr)为第一最短路由路径pr的第二路由路径信息,c(ps)第二最短路由路径ps的第一路由路径信息,d(ps)为第二最短路由路径ps的第二路由路径信息,第一路由路径信息和第二路由路径信息包括:最短路由路径的时延信息和最短路由路径的带宽信息,j、r、s为大于或等于0的整数,0≤r<j,0≤s<j,当r与s不同时为0时,r与s不同;当r=0,且s=0时,pr为满足第一约束条件的路由路径pc,c(pr)=c(pc),c(pc)为满足第一约束条件的路由路径pc的第一限制条件,d(pr)=d(pc),d(pc)为满足第一约束条件的路由路径pc的第二限制条件,ps为满足第二约束条件的路由路径pd,c(ps)=c(pd),c(pd)为满足第二约束条件的路由路径pd的第一限制条件,d(ps)=d(pd),d(pd)为满足第二约束条件的路由路径pd的第二限制条件;Calculate the iteration factor λ j at the j-th iteration of the Lagrangian relaxation algorithm, where λ j is the iteration factor at the j-th iteration, and c( pr ) is the first route of the first shortest route pr Path information, d( pr ) is the second routing path information of the first shortest routing path pr , c(ps) is the first routing path information of the second shortest routing path ps , d ( ps ) is the second routing path information The second routing path information of the shortest routing path ps , the first routing path information and the second routing path information include: the delay information of the shortest routing path and the bandwidth information of the shortest routing path, j, r, s are greater than or equal to 0 The integer of , 0≤r<j, 0≤s<j, when r is different from s, it is 0, and r is different from s; when r=0, and s=0, p r is the one that satisfies the first constraint condition Routing path pc , c( pr )= c ( pc ), c( pc ) is the first restriction condition of the routing path pc satisfying the first constraint condition, d( pr )= d ( pc ) , d(p c ) is the second constraint condition of the routing path p c that satisfies the first constraint condition, ps is the routing path p d that satisfies the second constraint condition, c( ps )=c(p d ) , c (p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition, d(ps )=d(p d ), d(p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition the second restriction;

获取网络拓扑中每条链路的链路信息,根据链路信息和迭代因子,通过第二公式:Obtain the link information of each link in the network topology, and use the second formula according to the link information and iteration factor:

Figure GDA0002629676720000031
Figure GDA0002629676720000031

计算第j次迭代时每条链路的加权值

Figure GDA0002629676720000032
并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration
Figure GDA0002629676720000032
And according to the weighted value of each link, the third shortest routing path in the jth iteration is selected by Dijkstra algorithm;

判断第j次迭代时的第三最短路由路径是否满足第一限制条件和第二限制条件;Judging whether the third shortest routing path in the j-th iteration satisfies the first restriction condition and the second restriction condition;

当第j次迭代时的第三最短路由路径满足第一限制条件和第二限制条件,将第j次迭代时的第三最短路由路径确定为最佳路由路径;When the third shortest routing path in the jth iteration satisfies the first constraint condition and the second constraint condition, the third shortest routing path in the jth iteration is determined as the best routing path;

当第j次迭代时的第三最短路由路径仅满足第一限制条件,将第j次迭代时的第三最短路由路径作为第r次迭代时选择的第一最短路由路径pr,并重复执行根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算拉格朗日松弛算法的第j次迭代时的迭代因子λjWhen the third shortest routing path at the jth iteration only satisfies the first constraint condition, the third shortest routing path at the jth iteration is taken as the first shortest routing path p r selected at the rth iteration, and the execution is repeated. According to the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, the iteration in the jth iteration of the Lagrangian relaxation algorithm is calculated by the first formula factor λ j ;

当第j次迭代时的第三最短路由路径仅满足第二限制条件,将第三最短路由路径作为第s次迭代时选择的第二最短路由路径ps,并重复执行根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算拉格朗日松弛算法的第j次迭代时的迭代因子λjWhen the third shortest routing path at the jth iteration only satisfies the second constraint condition, take the third shortest routing path as the second shortest routing path ps selected at the sth iteration, and repeat the execution according to the rth iteration The selected first shortest routing path pr and the second shortest routing path ps selected in the s -th iteration are used to calculate the iteration factor λ j in the j-th iteration of the Lagrangian relaxation algorithm through the first formula.

可选的,在当第一路由路径满足两个限制条件中,除第一限制条件外的其他限制条件时,确定第一路由路径为最佳路由路径之后,本发明实施例的一种路由路径选择方法,还包括:Optionally, after the first routing path is determined to be the optimal routing path when the first routing path satisfies other restriction conditions except the first restriction condition among the two restriction conditions, a routing path according to an embodiment of the present invention Choose a method, which also includes:

获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点;Obtain the directed graph of the network topology corresponding to the optimal routing path and the source and destination nodes of the optimal routing path;

获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图;Obtain the reverse routing path of the optimal routing path, and modify the directed graph of the network topology through the reverse routing path of the optimal routing path to obtain a modified graph of the directed graph of the network topology;

根据源节点和目的节点,通过Dijkstra算法在网络拓扑的有向图的修正图中查找第四最短路由路径;According to the source node and the destination node, find the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm;

获取最佳路由路径和第四最短路由路径中相同的链路,并分别从最佳路由路径和第四最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径;Obtain the same link in the best routing path and the fourth shortest routing path, and delete the same link from the best routing path and the fourth shortest routing path respectively, get the best routing path and delete the same link The shortest routing path of the same link;

将删除相同的链路的最佳路由路径的所有链路和删除相同的链路的最短路由路径的所有链路,组成两条路径,并将两条路径作为最佳路由路径的备用路由路径。All links of the best routing path of the same link and all links of the shortest routing path of the same link will be deleted to form two paths, and the two paths will be used as backup routing paths of the best routing path.

第二方面,本发明实施例还提供了一种路由路径选择装置,应用于网络拓扑中,该装置包括:In a second aspect, an embodiment of the present invention further provides a routing path selection device, which is applied in a network topology, and the device includes:

第一路径选择模块,用于获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,其中,第一限制条件为两个限制条件中的任一限制条件;The first path selection module is configured to obtain two restriction conditions, and use the first restriction condition of the two restriction conditions as the first restriction condition to determine whether there is a routing path that satisfies the first restriction condition in the network topology, wherein the first restriction condition is the first restriction condition. A restriction is any one of two restrictions;

第一判断模块,用于当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件;A first judging module, configured to judge whether a routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions when there is a routing path that satisfies the first constraint condition in the network topology, wherein the second constraint condition is the restriction condition except the first restriction condition among the two restriction conditions;

第一最佳路径选择模块,用于当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。The first optimal path selection module is configured to determine the routing path that satisfies the first constraint condition as the optimal routing path when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions.

可选的,本发明实施例的一种路由路径选择装置,还包括:Optionally, a routing path selection apparatus according to an embodiment of the present invention further includes:

第二最佳路径选择模块,用于当网络拓扑中不存在满足第一约束条件的路由路径时,根据两个限制条件,采用层次分析法在网络拓扑中选择最佳路由路径。The second optimal path selection module is used to select the optimal routing path in the network topology by using the Analytic Hierarchy Process (AHP) method according to the two constraints when there is no routing path satisfying the first constraint condition in the network topology.

可选的,本发明实施例的一种路由路径选择装置,还包括:Optionally, a routing path selection apparatus according to an embodiment of the present invention further includes:

第二路径选择模块,用于在满足第一约束条件的路由路径,不满足两个限制条件中的第二限制条件时,以第二限制条件为第二约束条件,在网络拓扑中选择满足第二约束条件的路由路径;The second path selection module is configured to use the second restriction condition as the second restriction condition when the routing path satisfying the first constraint condition does not satisfy the second restriction condition of the two restriction conditions, and select the second restriction condition in the network topology that satisfies the first restriction condition. The routing path of the two constraints;

第三最佳路径选择模块,用于根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。The third optimal path selection module is used for calculating the optimal routing path by using the Lagrangian relaxation algorithm according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition.

可选的,第三最佳路径选择模块,包括:Optionally, a third best path selection module, including:

迭代因子计算子模块,用于根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式The iteration factor calculation sub-module is used to calculate the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration through the first formula

Figure GDA0002629676720000051
Figure GDA0002629676720000051

计算拉格朗日松弛算法的第j次迭代时的迭代因子λj,其中,λj为第j次迭代时的迭代因子,c(pr)为第一最短路由路径pr的第一路由路径信息,d(pr)为第一最短路由路径pr的第二路由路径信息,c(ps)第二最短路由路径ps的第一路由路径信息,d(ps)为第二最短路由路径ps的第二路由路径信息,第一路由路径信息和第二路由路径信息包括:最短路由路径的时延信息和最短路由路径的带宽信息,j、r、s为大于或等于0的整数,0≤r<j,0≤s<j,当r与s不同时为0时,r与s不同;当r=0,且s=0时,pr为满足第一约束条件的路由路径pc,c(pr)=c(pc),c(pc)为满足第一约束条件的路由路径pc的第一限制条件,d(pr)=d(pc),d(pc)为满足第一约束条件的路由路径pc的第二限制条件,ps为满足第二约束条件的路由路径pd,c(ps)=c(pd),c(pd)为满足第二约束条件的路由路径pd的第一限制条件,d(ps)=d(pd),d(pd)为满足第二约束条件的路由路径pd的第二限制条件;Calculate the iteration factor λ j at the j-th iteration of the Lagrangian relaxation algorithm, where λ j is the iteration factor at the j-th iteration, and c( pr ) is the first route of the first shortest route pr Path information, d( pr ) is the second routing path information of the first shortest routing path pr , c(ps) is the first routing path information of the second shortest routing path ps , d ( ps ) is the second routing path information The second routing path information of the shortest routing path ps , the first routing path information and the second routing path information include: the delay information of the shortest routing path and the bandwidth information of the shortest routing path, j, r, s are greater than or equal to 0 The integer of , 0≤r<j, 0≤s<j, when r is different from s, it is 0, and r is different from s; when r=0, and s=0, p r is the one that satisfies the first constraint condition Routing path pc , c( pr )= c ( pc ), c( pc ) is the first restriction condition of the routing path pc satisfying the first constraint condition, d( pr )= d ( pc ) , d(p c ) is the second constraint condition of the routing path p c that satisfies the first constraint condition, ps is the routing path p d that satisfies the second constraint condition, c( ps )=c(p d ) , c (p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition, d(ps )=d(p d ), d(p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition the second restriction;

加权值计算子模块,用于获取网络拓扑中每条链路的链路信息,根据链路信息和迭代因子,通过第二公式:The weighted value calculation sub-module is used to obtain the link information of each link in the network topology, according to the link information and the iteration factor, through the second formula:

Figure GDA0002629676720000052
Figure GDA0002629676720000052

计算第j次迭代时每条链路的加权值

Figure GDA0002629676720000061
并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration
Figure GDA0002629676720000061
And according to the weighted value of each link, the third shortest routing path in the jth iteration is selected by Dijkstra algorithm;

第一判断子模块,用于判断第j次迭代时的第三最短路由路径是否满足第一限制条件和第二限制条件;The first judgment submodule is used for judging whether the third shortest routing path in the j-th iteration satisfies the first restriction condition and the second restriction condition;

第一最佳路径选择子模块,当第j次迭代时的第三最短路由路径满足第一限制条件和第二限制条件,将第j次迭代时的第三最短路由路径确定为最佳路由路径;The first best path selection sub-module, when the third shortest routing path in the jth iteration satisfies the first constraint condition and the second constraint condition, determines the third shortest routing path in the jth iteration as the best routing path ;

当第j次迭代时的第三最短路由路径仅满足第一限制条件,将第j次迭代时的第三最短路由路径作为第r次迭代时选择的第一最短路由路径pr,并触发迭代因子计算子模块;When the third shortest routing path in the jth iteration only satisfies the first constraint, the third shortest routing path in the jth iteration is taken as the first shortest routing path pr selected in the rth iteration, and the iteration is triggered Factor calculation submodule;

当第j次迭代时的第三最短路由路径仅满足第二限制条件,将第三最短路由路径作为第s次迭代时选择的第二最短路由路径ps,并触发迭代因子计算子模块。When the third shortest routing path in the jth iteration only satisfies the second constraint condition, the third shortest routing path is taken as the second shortest routing path ps selected in the sth iteration, and the iteration factor calculation submodule is triggered.

可选的,本发明实施例的一种路由路径选择装置,还包括:Optionally, a routing path selection apparatus according to an embodiment of the present invention further includes:

有向图获取模块,用于获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点;A directed graph obtaining module, used for obtaining the directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path;

修正模块,用于获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图;The correction module is used to obtain the reverse routing path of the optimal routing path, and modify the directed graph of the network topology through the reverse routing path of the optimal routing path, so as to obtain the modified graph of the directed graph of the network topology;

最短路径查找模块,用于根据源节点和目的节点,通过Dijkstra算法在网络拓扑的有向图的修正图中查找第四最短路由路径;The shortest path finding module is used to find the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm according to the source node and the destination node;

删除模块,用于获取最佳路由路径和第四最短路由路径中相同的链路,并分别从最佳路由路径和第四最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径;The deletion module is used to obtain the same link in the best routing path and the fourth shortest routing path, and delete the same link from the best routing path and the fourth shortest routing path respectively, and obtain the best link for deleting the same link. optimal routing path and delete the shortest routing path of the same link;

备用路径选择模块,用于将删除相同的链路的最佳路由路径的所有链路和删除相同的链路的最短路由路径的所有链路,组成两条路径,并将两条路径作为最佳路由路径的备用路由路径。The alternate path selection module is used to delete all the links of the best routing path of the same link and all the links of the shortest routing path of the same link to form two paths, and use the two paths as the best route Alternate routing paths for routing paths.

第三方面,本发明实施例还提供了一种电子设备,该电子设备包括处理器、通信接口、存储器和通信总线,其中,处理器,通信接口,存储器通过通信总线完成相互间的通信;In a third aspect, an embodiment of the present invention also provides an electronic device, the electronic device includes a processor, a communication interface, a memory, and a communication bus, wherein the processor, the communication interface, and the memory communicate with each other through the communication bus;

存储器,用于存放计算机程序;memory for storing computer programs;

处理器,用于执行存储器上所存放的程序时,实现以上任一所述的路由路径选择方法。The processor is configured to implement any one of the above routing path selection methods when executing the program stored in the memory.

第四方面,本发明实施例还提供了一种计算机可读存储介质,该计算机可读存储介质内存储有计算机程序,该计算机程序被处理器执行时实现以上任一所述的路由路径选择方法。In a fourth aspect, an embodiment of the present invention further provides a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, any one of the above routing path selection methods is implemented .

本发明实施例提供的一种路由路径选择方法、装置、电子设备及存储介质,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。当然,实施本发明的任一产品或方法并不一定需要同时达到以上所述的所有优点。In a routing path selection method, device, electronic device, and storage medium provided by the embodiments of the present invention, when selecting an optimal routing path in a network topology, two constraints can be obtained, and the first constraint of the two constraints can be used. The condition is the first constraint condition, determine whether there is a routing path that satisfies the first constraint condition in the network topology, and when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies two The second restriction condition in the restriction conditions: when the routing path satisfying the first restriction condition meets the second restriction condition in the two restriction conditions, the routing path satisfying the first restriction condition is determined as the optimal routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions. Of course, it is not necessary for any product or method of the present invention to achieve all of the advantages described above at the same time.

附图说明Description of drawings

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

图1为本发明实施例的一种路由路径选择方法第一种实施方式的流程图;1 is a flowchart of a first implementation manner of a routing path selection method according to an embodiment of the present invention;

图2为应用本发明实施例的一种路由路径选择方法的网络拓扑的结构示意图;2 is a schematic structural diagram of a network topology applying a routing path selection method according to an embodiment of the present invention;

图3为本发明实施例的一种路由路径选择方法第二种实施方式的流程图;3 is a flowchart of a second implementation manner of a routing path selection method according to an embodiment of the present invention;

图4为本发明实施例的一种路由路径选择方法第三种实施方式的流程图;4 is a flowchart of a third implementation manner of a routing path selection method according to an embodiment of the present invention;

图5为本发明实施例的一种路由路径选择方法第四种实施方式的流程图;5 is a flowchart of a fourth implementation manner of a routing path selection method according to an embodiment of the present invention;

图6a为图2所示的网络拓扑的有向图的结构示意图;Figure 6a is a schematic structural diagram of a directed graph of the network topology shown in Figure 2;

图6b为图6a所示的网络拓扑的有向图的修正图的结构示意图;Figure 6b is a schematic structural diagram of a modified graph of the directed graph of the network topology shown in Figure 6a;

图7为本发明实施例的一种路由路径选择装置的结构示意图;7 is a schematic structural diagram of a routing path selection apparatus according to an embodiment of the present invention;

图8为本发明实施例的一种电子设备的结构示意图。FIG. 8 is a schematic structural diagram of an electronic device according to an embodiment of the present invention.

具体实施方式Detailed ways

下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例,都属于本发明保护的范围。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. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

为了解决现有技术中存在的问题,本发明实施例提供了一种路由路径选择方法、装置、电子设备及存储介质,以实现在网络拓扑中选择完全满足所选择的限制条件的路由路径。In order to solve the problems in the prior art, the embodiments of the present invention provide a routing path selection method, apparatus, electronic device and storage medium, so as to select a routing path that fully satisfies the selected restriction conditions in the network topology.

下面,首先对本发明实施例的一种路由路径选择方法进行介绍,如图1所示,为本发明实施例的一种路由路径选择方法第一种实施方式的流程图,在图1中,该方法可以包括:Below, a routing path selection method according to an embodiment of the present invention is first introduced. As shown in FIG. 1 , it is a flowchart of the first implementation manner of a routing path selection method according to an embodiment of the present invention. In FIG. 1 , the Methods can include:

S110,获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径。S110: Acquire two restriction conditions, and use the first restriction condition of the two restriction conditions as the first restriction condition, and determine whether there is a routing path that satisfies the first restriction condition in the network topology.

其中,第一限制条件为两个限制条件中的任一限制条件。Wherein, the first restriction condition is any one of the two restriction conditions.

具体的,为了使用网络拓扑对文件进行传输,可以首先在该网络拓扑中选择最佳路由路径,然后按照选择的路由路径对文件进行传输。Specifically, in order to use the network topology to transfer the file, an optimal routing path may be selected in the network topology first, and then the file is transferred according to the selected routing path.

例如,可以在图2所示的网络拓扑网络拓扑中选择最佳路由路径,其中,图2为应用本发明实施例的一种路由路径选择方法的网络拓扑的结构示意图,在图2中,可以包括第一交换设备110、第二交换设备120、第三交换设备130、第四交换设备140、第五交换设备150、第六交换设备160、第七交换设备170、第八交换设备180、第九交换设备190。还可以包括:第一链路201、第二链路202、第三链路203、第四链路204、第五链路205、第六链路206、第七链路207、第八链路208、第九链路209、第十链路210、第十一链路211、第十二链路212、第十三链路213、第十四链路214、第十五链路215。For example, an optimal routing path can be selected in the network topology shown in FIG. 2, wherein FIG. 2 is a schematic structural diagram of a network topology applying a routing path selection method according to an embodiment of the present invention. In FIG. 2, you can Including the first switching device 110, the second switching device 120, the third switching device 130, the fourth switching device 140, the fifth switching device 150, the sixth switching device 160, the seventh switching device 170, the eighth switching device 180, the Nine switching devices 190 . It may also include: a first link 201, a second link 202, a third link 203, a fourth link 204, a fifth link 205, a sixth link 206, a seventh link 207, and an eighth link 208 , the ninth link 209 , the tenth link 210 , the eleventh link 211 , the twelfth link 212 , the thirteenth link 213 , the fourteenth link 214 , and the fifteenth link 215 .

在一些示例中,为了保证文件的传输质量,在选择路由路径时,可以预先设置限制条件,然后根据该限制条件在网络拓扑中选择最佳路由路径。In some examples, in order to ensure the quality of file transmission, when selecting a routing path, a restriction condition may be set in advance, and then an optimal routing path is selected in the network topology according to the restriction condition.

在根据该限制条件在网络拓扑中选择最佳路由路径时,可以应用本发明实施例的一种路由路径选择方法选择最佳路由路径。When selecting the best routing path in the network topology according to the constraint condition, a routing path selection method according to an embodiment of the present invention can be applied to select the best routing path.

具体的,用户可以预先向应用本发明实施例的一种路由路径选择方法的路由路径选择装置中输入网络拓扑信息和两个限制条件。其中,该网络拓扑信息可以包括:网络拓扑中的节点信息、每两个节点之间的链路信息,该节点信息可以包括该节点的标识信息,每两个节点之间的链路信息可以包括:每两个节点之间的时延信息、每两个节点之间的带宽信息等。因此,上述的路由路径选择装置可以获取到网络拓扑,以及和该网络拓扑对应的两个限制条件。Specifically, the user may input network topology information and two restriction conditions in advance into the routing path selection device applying the routing path selection method of the embodiment of the present invention. Wherein, the network topology information may include: node information in the network topology, link information between every two nodes, the node information may include identification information of the node, and link information between every two nodes may include : delay information between every two nodes, bandwidth information between every two nodes, etc. Therefore, the above-mentioned routing path selection device can obtain the network topology and two restriction conditions corresponding to the network topology.

在一些示例中,上述的两个限制条件可以分别是时延限制条件和带宽限制条件。In some examples, the above two constraints may be delay constraints and bandwidth constraints, respectively.

上述的路由路径选择装置在获取到该两个限制条件后,可以在该两个限制条件中选择任一个限制条件为约束条件,也就是在该两个限制条件中选择第一限制条件为第一约束条件,然后在网络拓扑中寻找满足该第一约束条件的路由路径。After obtaining the two restriction conditions, the above-mentioned routing path selection apparatus may select any one of the restriction conditions as the restriction condition, that is, select the first restriction condition as the first restriction condition among the two restriction conditions. constraints, and then search for a routing path that satisfies the first constraint in the network topology.

例如,可以选择时延限制条件为约束条件,在图2所示网络拓扑中选择满足时延限制条件的路由路径。或者选择带宽限制条件为约束条件,在图2所示网络拓扑中选择满足带宽限制条件的路由路径。For example, the delay restriction condition can be selected as the constraint condition, and a routing path that satisfies the delay restriction condition is selected in the network topology shown in FIG. 2 . Alternatively, the bandwidth limitation condition is selected as the constraint condition, and a routing path that satisfies the bandwidth limitation condition is selected in the network topology shown in FIG. 2 .

在一些示例中,在网络拓扑中寻找满足该第一约束条件的路由路径时,可以在网络拓扑中随机选择一条路由路径,然后判断该随机选择的路由路径是否满足第一约束条件,当满足第一约束条件时,则将该随机选择的路由路径确定为满足该第一约束条件的路由路径。In some examples, when searching for a routing path that satisfies the first constraint condition in the network topology, a routing path may be randomly selected in the network topology, and then it is determined whether the randomly selected routing path satisfies the first constraint condition. When there is a constraint condition, the randomly selected routing path is determined as a routing path satisfying the first constraint condition.

否则,重新随机选择一条路由路径,并判断是否满足第一约束条件。Otherwise, a routing path is randomly selected again, and it is judged whether the first constraint condition is satisfied.

具体的,上述的路由路径选择装置在选择一条路由路径后,可以获取该路由路径上的每两个节点之间的链路信息中与约束条件对应的信息,然后对该路由路径上的所有链路链路信息中与约束条件对应的信息求和,然后与约束条件进行对比,以判断是否满足第一约束条件。Specifically, after selecting a routing path, the above-mentioned routing path selection device can obtain information corresponding to the constraint conditions in the link information between every two nodes on the routing path, and then all links on the routing path can be obtained. The information corresponding to the constraint condition in the road link information is summed, and then compared with the constraint condition to determine whether the first constraint condition is satisfied.

假设,上述的路由路径选择装置选择的约束条件是时延限制条件,则在选择一条路由路径后,可以获取该路由路径上的每两个节点之间的时延信息,然后对该路由路径上的所有的时延信息求和,判断是否满足约束条件。Assuming that the constraint condition selected by the above-mentioned routing path selection device is the delay restriction condition, after selecting a routing path, the delay information between every two nodes on the routing path can be obtained, and then the routing path Sum all the delay information of , and judge whether the constraints are satisfied.

S120,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件。S120, when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions.

其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件。The second restriction condition is the restriction condition other than the first restriction condition among the two restriction conditions.

当上述的路由路径选择装置确定网络拓扑中存在满足第一约束条件的路由路径后,为了使得选择的最佳路由路径能够同时满足两个限制条件,在本步骤中,可以判断该满足第一约束条件的路由路径是否满足第二限制条件。After the above-mentioned routing path selection device determines that there is a routing path that satisfies the first constraint condition in the network topology, in order to enable the selected optimal routing path to satisfy the two constraints at the same time, in this step, it can be determined that the routing path that satisfies the first constraint condition Whether the routing path of the condition satisfies the second restriction condition.

假设,上述的路由路径选择装置选择的第一约束条件为时延限制条件,选择的满足第一约束条件的路由路径为:由第一交换设备110、第二链路202、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190组成的路由路径。在本步骤中,可以判断该路由路径是否满足带宽限制条件。It is assumed that the first constraint condition selected by the above routing path selection apparatus is a delay constraint condition, and the selected routing path satisfying the first constraint condition is: the first switching device 110 , the second link 202 , and the third switching device 130 , the seventh link 207 , the fifth switching device 150 , the tenth link 210 , the seventh switching device 170 , the thirteenth link 213 , and the ninth switching device 190 . In this step, it can be determined whether the routing path satisfies the bandwidth limitation condition.

S130,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。S130, when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, determine that the routing path that satisfies the first constraint condition is the optimal routing path.

具体的,当上述的路由路径选择装置在确定满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,说明该满足第一约束条件的路由路径同时满足第一限制条件和第二限制条件,因此,可以将该满足第一约束条件的路由路径确定为最佳路由路径。Specifically, when the above-mentioned routing path selection device determines that the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, it indicates that the routing path that satisfies the first constraint condition satisfies both the first constraint condition and the second constraint condition. The second constraint condition, therefore, the routing path satisfying the first constraint condition can be determined as the best routing path.

例如,假设上述的路由路径选择装置在对上述满足第一约束条件的路由路径中的各个链路的带宽信息进行求和,并与带宽限制条件进行对比后,满足该带宽限制条件,在本步骤中,可以将该满足第一约束条件的、由第一交换设备110、第二链路202、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190组成的路由路径,确定为最佳路由路径。For example, it is assumed that the above-mentioned routing path selection device satisfies the bandwidth restriction condition after summing the bandwidth information of each link in the routing path satisfying the first constraint condition and comparing it with the bandwidth restriction condition, in this step , the first switching device 110 , the second link 202 , the third switching device 130 , the seventh link 207 , the fifth switching device 150 , the tenth link 210 , the third The routing path composed of the seventh switching device 170, the thirteenth link 213, and the ninth switching device 190 is determined as the best routing path.

通过本发明实施例的一种路由路径选择方法,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。With the method for selecting a routing path according to an embodiment of the present invention, when selecting an optimal routing path in a network topology, two restriction conditions can be obtained, and the first restriction condition among the two restriction conditions is used as the first restriction condition to determine Whether there is a routing path that satisfies the first constraint condition in the network topology, when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints , when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, the routing path that satisfies the first constraint condition is determined to be the best routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions.

在本发明实施例一种可选的实施例中,在图1所示的一种路由路径选择方法的基础上,本发明实施例还提供了一种可能的实现方式,如图3所示,为本发明实施例的一种路由路径选择方法第二种实施方式的流程图,在图3中,在S110,判断网络拓扑中是否存在满足第一约束条件的路由路径之后,本发明实施例的一种路由路径选择方法,还可以包括:In an optional embodiment of the embodiment of the present invention, on the basis of a routing path selection method shown in FIG. 1 , an embodiment of the present invention further provides a possible implementation manner, as shown in FIG. 3 , This is a flowchart of the second implementation manner of a routing path selection method according to an embodiment of the present invention. In FIG. 3, in S110, after judging whether there is a routing path that satisfies the first constraint condition in the network topology, the A routing path selection method, which can also include:

S140,当网络拓扑中不存在满足第一约束条件的路由路径时,根据两个限制条件,采用层次分析法在网络拓扑中选择最佳路由路径。S140 , when there is no routing path satisfying the first constraint condition in the network topology, according to the two constraints, an AHP method is used to select the best routing path in the network topology.

在一些示例中,上述的路由路径选择装置在确定上述的网络拓扑中,不存在满足第一约束条件的路由路径时,则可以说明,该网络拓扑中必然不存在同时满足该两个限制条件的路由路径。对此,本发明实施例还提供了一种可能的实现方式,以选择最接近上述限制条件的最佳路由路径。In some examples, when the above-mentioned routing path selection apparatus determines that there is no routing path that satisfies the first constraint condition in the above-mentioned network topology, it can be indicated that there must not exist in the network topology that simultaneously satisfies the two constraints. routing path. In this regard, the embodiments of the present invention also provide a possible implementation manner to select an optimal routing path that is closest to the above-mentioned restriction conditions.

具体的,上述的路由路径选择装置本地可以保存有如表1所示的重要性比例标度表,然后根据该两个限制条件和表1所示的重要性比例标度表,构建判断矩阵,进而可以计算该判断矩阵的特征向量,并将该特征向量作为该两个限制条件的权重值,最后,可以根据计算得到的该两个限制条件的权重值的综合值选择路由路径。以实现选择最接近上述限制条件的最佳路由路径。Specifically, the above-mentioned routing path selection device may locally store the importance scale table shown in Table 1, and then construct a judgment matrix according to the two constraints and the importance scale table shown in Table 1, and then The eigenvector of the judgment matrix can be calculated, and the eigenvector can be used as the weight value of the two restriction conditions. Finally, a routing path can be selected according to the calculated comprehensive value of the weight values of the two restriction conditions. In order to achieve the selection of the best routing path that is closest to the above constraints.

表1重要性比例标度表Table 1 Importance scale table

重要度项目importance item 重要度指标importance index 重要度项目importance item 重要度指标importance index 同等重要equally important 11 明显更加重要significantly more important 77 相对重要relatively important 33 绝对重要absolutely important 99 更加重要more important 55 中间值Median 2,4,6,82, 4, 6, 8

在本发明实施例一种可选的实施例中,在图1所示的一种路由路径选择方法的基础上,本发明实施例还提供了一种可能的实现方式,如图4所示,为本发明实施例的一种路由路径选择方法第三种实施方式的流程图,在图4中,在S120,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件之后,本发明实施例的一种路由路径选择方法,还可以包括:In an optional embodiment of the embodiment of the present invention, on the basis of a routing path selection method shown in FIG. 1 , an embodiment of the present invention further provides a possible implementation manner, as shown in FIG. 4 , This is a flowchart of a third implementation manner of a routing path selection method according to an embodiment of the present invention. In FIG. 4 , in S120, it is judged whether a routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions. Afterwards, a routing path selection method according to an embodiment of the present invention may further include:

S150,在满足第一约束条件的路由路径,不满足两个限制条件中的第二限制条件时,以第二限制条件为第二约束条件,在网络拓扑中选择满足第二约束条件的路由路径。S150, when the routing path that satisfies the first constraint condition does not satisfy the second constraint condition of the two constraints, select the routing path that satisfies the second constraint condition in the network topology by using the second constraint condition as the second constraint condition .

在一些示例中,上述的路由路径选择装置在确定满足第一约束条件的路由路径后,为了寻找同时满足第一限制条件和第二限制条件的最佳路由路径,可以判断该满足第一约束条件的路由路径是否满足第二限制条件。当该满足第一约束条件的路由路径不满足第二限制条件时,本发明实施例的一种路由路径选择方法还提供了一种可能的实现方式。In some examples, after determining the routing path that satisfies the first constraint condition, the above-mentioned routing path selection apparatus may determine that the routing path that satisfies the first constraint condition satisfies the first constraint condition in order to find the best routing path that satisfies both the first constraint condition and the second constraint condition Whether the routing path satisfies the second restriction condition. When the routing path that satisfies the first constraint condition does not satisfy the second constraint condition, a routing path selection method according to an embodiment of the present invention also provides a possible implementation manner.

具体的,上述的路由路径选择装置在判断该满足第一约束条件的路由路径不满足第二限制条件时,可以以第二限制条件为第二约束条件,在网络拓扑中选择满足第二约束条件的路由路径。Specifically, when judging that the routing path that satisfies the first constraint condition does not satisfy the second constraint condition, the above-mentioned routing path selection device may take the second constraint condition as the second constraint condition, and select the routing path that satisfies the second constraint condition in the network topology routing path.

例如,上述的路由路径选择装置选择的第一约束条件为时延限制条件,选择的满足第一约束条件的路由路径为:由第一交换设备110、第二链路202、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190组成的路由路径。在本步骤中,可以判断该路由路径是否满足带宽限制条件。当该满足第一约束条件的路由路径不满足第二限制条件时,则可以在图2所示的网络拓扑中以第二限制条件为第二约束条件,选择满足第二约束条件的路由路径。For example, the first constraint condition selected by the above routing path selection apparatus is a delay constraint condition, and the selected routing path satisfying the first constraint condition is: the first switching device 110 , the second link 202 , and the third switching device 130 , the seventh link 207 , the fifth switching device 150 , the tenth link 210 , the seventh switching device 170 , the thirteenth link 213 , and the ninth switching device 190 . In this step, it can be determined whether the routing path satisfies the bandwidth limitation condition. When the routing path satisfying the first constraint condition does not satisfy the second constraint condition, the routing path satisfying the second constraint condition may be selected by taking the second constraint condition as the second constraint condition in the network topology shown in FIG. 2 .

S160,根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。S160, according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition, use the Lagrangian relaxation algorithm to calculate the optimal routing path.

具体的,上述的路由路径选择装置在选择到满足第二约束条件的路由路径后,可以采用拉格朗日松弛算法,计算同时满足第一约束条件和第二约束条件的路由路径,也就是计算同时满足第一限制条件和第二限制条件的路由路径。Specifically, after the above-mentioned routing path selection device selects a routing path that satisfies the second constraint condition, the Lagrangian relaxation algorithm can be used to calculate the routing path that satisfies the first constraint condition and the second constraint condition at the same time, that is, calculating A routing path that satisfies both the first restriction condition and the second restriction condition.

例如,假设上述的路由路径选择装置选择的满足第二约束条件的路由路径为:由第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路由路径,在本步骤中,上述的路由路径选择装置可以根据由第一交换设备110、第二链路202、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190组成的路由路径,和由第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路由路径,采用拉格朗日松弛算法计算最佳路由路径。For example, it is assumed that the routing path selected by the above-mentioned routing path selection apparatus that satisfies the second constraint condition is: the first switching device 110, the third link 203, the fourth switching device 140, the ninth link 209, the sixth switching device 160, the twelfth link 212, the eighth switching device 180, the fifteenth link 215, and the routing path composed of the ninth switching device 190, in this step, the above-mentioned routing path selection device can be based on the first switching device. 110, second link 202, third switching device 130, seventh link 207, fifth switching device 150, tenth link 210, seventh switching device 170, thirteenth link 213, ninth switching device 190 The routing path composed of the first switching device 110, the third link 203, the fourth switching device 140, the ninth link 209, the sixth switching device 160, the twelfth link 212, the eighth switching device 180, For the routing path formed by the fifteenth link 215 and the ninth switching device 190, the Lagrangian relaxation algorithm is used to calculate the optimal routing path.

通过使用拉格朗日松弛算法,可以在图2所示的网络拓扑中,选择出同时满足上述的两个限制条件的路由路径,从而使得选择的最佳路由路径能够同时满足该两个限制条件。By using the Lagrangian relaxation algorithm, in the network topology shown in Figure 2, a routing path that satisfies the above two constraints at the same time can be selected, so that the selected optimal routing path can meet the two constraints at the same time .

在一些示例中,在根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径时,可以通过以下步骤进行计算:In some examples, when the Lagrangian relaxation algorithm is used to calculate the optimal routing path according to the routing path that satisfies the first constraint condition and the routing path that satisfies the second constraint condition, the calculation can be performed by the following steps:

步骤A,根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式Step A, according to the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, through the first formula

Figure GDA0002629676720000131
Figure GDA0002629676720000131

计算拉格朗日松弛算法的第j次迭代时的迭代因子λjCalculates the iteration factor λ j at the jth iteration of the Lagrangian relaxation algorithm.

其中,λj为第j次迭代时的迭代因子,c(pr)为第一最短路由路径pr的第一路由路径信息,d(pr)为第一最短路由路径pr的第二路由路径信息,c(ps)第二最短路由路径ps的第一路由路径信息,d(ps)为第二最短路由路径ps的第二路由路径信息。j、r、s为大于或等于0的整数,0≤r<j,0≤s<j,当r与s不同时为0时,r与s不同。Among them, λ j is the iteration factor in the j-th iteration, c( pr ) is the first routing path information of the first shortest routing path pr, d(pr ) is the second shortest routing path pr Routing path information, c( ps ) is the first routing path information of the second shortest routing path ps , and d ( ps ) is the second routing path information of the second shortest routing path ps. j, r, and s are integers greater than or equal to 0, 0≤r<j, 0≤s<j, and when r and s are different, they are 0, and r and s are different.

当r=0,且s=0时,则说明上述的路由路径选择装置还未进行迭代,pr为满足第一约束条件的路由路径pc,c(pr)=c(pc),c(pc)为满足第一约束条件的路由路径pc的第一限制条件,d(pr)=d(pc),d(pc)为满足第一约束条件的路由路径pc的第二限制条件,ps为满足第二约束条件的路由路径pd,c(ps)=c(pd),c(pd)为满足第二约束条件的路由路径pd的第一限制条件,d(ps)=d(pd),d(pd)为满足第二约束条件的路由路径pd的第二限制条件。When r =0 and s=0, it means that the above-mentioned routing path selection device has not been iterated yet, pr is the routing path p c that satisfies the first constraint condition, c( pr )= c (pc ), c(p c ) is the first restriction condition of the routing path p c that satisfies the first restriction condition, d( pr )=d(p c ), d(p c ) is the routing path p c that satisfies the first restriction condition The second restriction condition of , p s is the routing path p d that satisfies the second restriction condition, c(ps )=c(p d ), c(p d ) is the second restriction condition of the routing path p d that satisfies the second restriction condition A restriction condition, d(ps )=d(p d ), d(p d ) is the second restriction condition of the routing path p d that satisfies the second restriction condition.

步骤B,获取网络拓扑中每条链路的链路信息,并根据链路信息和迭代因子,通过第二公式:Step B: Obtain the link information of each link in the network topology, and pass the second formula according to the link information and the iteration factor:

Figure GDA0002629676720000141
Figure GDA0002629676720000141

计算第j次迭代时每条链路的加权值

Figure GDA0002629676720000142
并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径。Calculate the weighted value of each link at the jth iteration
Figure GDA0002629676720000142
And according to the weighted value of each link, the third shortest routing path in the jth iteration is selected by Dijkstra algorithm.

步骤C,判断第j次迭代时的第三最短路由路径是否满足第一限制条件和第二限制条件。Step C, judging whether the third shortest routing path in the j-th iteration satisfies the first restriction condition and the second restriction condition.

步骤D,当第j次迭代时的第三最短路由路径满足第一限制条件和第二限制条件,将第j次迭代时的第三最短路由路径确定为最佳路由路径。Step D, when the third shortest routing path in the jth iteration satisfies the first constraint condition and the second constraint condition, determine the third shortest routing path in the jth iteration as the best routing path.

步骤E,当第j次迭代时的第三最短路由路径仅满足第一限制条件,将第j次迭代时的第三最短路由路径作为第r次迭代时选择的第一最短路由路径pr,并重复执行根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算拉格朗日松弛算法的第j次迭代时的迭代因子λjStep E, when the third shortest routing path in the jth iteration only satisfies the first constraint condition, the third shortest routing path in the jth iteration is taken as the first shortest routing path p r selected in the rth iteration, And repeatedly execute the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, and calculate the jth iteration of the Lagrangian relaxation algorithm through the first formula The iteration factor λ j when .

步骤F,当第j次迭代时的第三最短路由路径仅满足第二限制条件,将第三最短路由路径作为第s次迭代时选择的第二最短路由路径ps,并重复执行根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算拉格朗日松弛算法的第j次迭代时的迭代因子λjStep F, when the third shortest routing path in the jth iteration only satisfies the second constraint condition, take the third shortest routing path as the second shortest routing path ps selected in the sth iteration, and repeat the execution according to the rth iteration. The first shortest routing path pr selected in the second iteration and the second shortest routing path p s selected in the s-th iteration, calculate the iteration factor λ j of the j-th iteration of the Lagrangian relaxation algorithm through the first formula .

为了更清楚的说明本发明实施例中,根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径的过程,下面以第一次迭代和第二次迭代为例进行说明。In order to more clearly illustrate the process of calculating the optimal routing path by using the Lagrangian relaxation algorithm according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition, the following uses the first The second iteration and the second iteration are used as examples to illustrate.

当r=0,且s=0时,则说明在采用拉格朗日算法计算最佳路由路径时,还未进行迭代,则pr为满足第一约束条件的路由路径pc,ps为满足第一约束条件的路由路径pd,因此,上述的第一公式可以等效为以下公式:When r =0, and s=0, it means that when the Lagrangian algorithm is used to calculate the optimal routing path, no iteration has been performed, then pr is the routing path p c that satisfies the first constraint condition, and ps is The routing path p d that satisfies the first constraint condition, therefore, the above-mentioned first formula can be equivalent to the following formula:

Figure GDA0002629676720000143
Figure GDA0002629676720000143

其中,c(pr)=c(pc),c(pc)为满足第一约束条件的路由路径pc的第一限制条件,d(pr)=d(pc),d(pc)为满足第一约束条件的路由路径pc的第二限制条件,c(ps)=c(pd),c(pd)为满足第二约束条件的路由路径pd的第一限制条件,d(ps)=d(pd),d(pd)为满足第二约束条件的路由路径pd的第二限制条件;Wherein, c( pr )= c (pc), c( pc ) is the first restriction condition of the routing path pc satisfying the first restriction condition, d( pr )= d ( pc ), d( p c ) is the second restriction condition of the routing path p c that satisfies the first restriction condition, c(ps )=c(p d ), c(p d ) is the second restriction condition of the routing path p d that satisfies the second restriction condition a restriction condition, d (ps)= d (pd), d (pd) is the second restriction condition of the routing path pd that satisfies the second restriction condition ;

通过该公式,上述的路由路径选择装置,可以计算出初始迭代因子λ0,然后可以获取每条链路上的至少两个链路信息,并通过以下公式:Through this formula, the above-mentioned routing path selection device can calculate the initial iteration factor λ 0 , and then obtain at least two link information on each link, and use the following formula:

Figure GDA0002629676720000151
Figure GDA0002629676720000151

计算第0次迭代时每条链路的加权值

Figure GDA0002629676720000152
Calculate the weighted value of each link at the 0th iteration
Figure GDA0002629676720000152

其中,ci为第i条链路的第一链路信息,di第i条链路的第二链路信息。Wherein, c i is the first link information of the ith link, and d i is the second link information of the ith link.

上述的路由路径选择装置在计算得到每条链路的加权值

Figure GDA0002629676720000153
后,可以根据第0次迭代时每条链路的加权值
Figure GDA0002629676720000154
在网络拓扑中,通过Dijkstra算法选择最短路由路径。The above-mentioned routing path selection device obtains the weighted value of each link in the calculation
Figure GDA0002629676720000153
After that, the weighted value of each link at the 0th iteration can be
Figure GDA0002629676720000154
In the network topology, the shortest routing path is selected by Dijkstra algorithm.

例如,上述的路由路径选择装置可以获取图2所示的网络拓扑中的第一链路201、第二链路202、第三链路203、第四链路204、第五链路205、第六链路206、第七链路207、第八链路208、第九链路209、第十链路210、第十一链路211、第十二链路212、第十三链路213、第十四链路214、第十五链路215,共十五条链路的带宽信息和时延信息,然后通过上述公式对每条链路的时延信息和带宽信息进行加权处理,进而可以通过Dijkstra算法,在图2所示的网络拓扑中选择第0次迭代时的最短路由路径。For example, the above-mentioned routing path selection apparatus can obtain the first link 201 , the second link 202 , the third link 203 , the fourth link 204 , the fifth link 205 , the first link 202 , the third link 203 , the fifth link 205 , the third link Sixth link 206, seventh link 207, eighth link 208, ninth link 209, tenth link 210, eleventh link 211, twelfth link 212, thirteenth link 213, The fourteenth link 214 and the fifteenth link 215 are the bandwidth information and delay information of fifteen links in total, and then the delay information and bandwidth information of each link are weighted by the above formula, and then the Through the Dijkstra algorithm, the shortest routing path at the 0th iteration is selected in the network topology shown in Figure 2.

当上述的路由路径选择装置在确定该第0次迭代时的最短路由路径满足第一限制条件和第二限制条件时,则说明该第0次迭代时的最短路由路径是最佳路由路径,因此,可以将该第0次迭代时的最短路由路径确定为最佳路由路径。When the above-mentioned routing path selection device determines that the shortest routing path in the 0th iteration satisfies the first constraint condition and the second constraint condition, it means that the shortest routing path in the 0th iteration is the best routing path, so , the shortest routing path at the 0th iteration can be determined as the best routing path.

在一些示例中,当上述的路由路径选择装置在确定该第0次迭代时的最短路由路径仅满足第一限制条件时,本发明实施例还提供了一种可能的实现方式,以通过迭代的方式在网络拓扑中查找同时满足第一限制条件和第二限制条件的路由路径。In some examples, when the above-mentioned routing path selection apparatus determines that the shortest routing path in the 0th iteration only satisfies the first constraint condition, the embodiment of the present invention also provides a possible implementation manner to perform the iterative The method searches the network topology for a routing path that satisfies the first restriction condition and the second restriction condition at the same time.

例如,假设上述的路由路径选择装置判断第0次迭代时的最短路由路径仅满足第一限制条件,则可以将第0次迭代时的最短路由路径,作为满足第一限制条件的路由路径,并执行根据第0次迭代时选择的最短路由路径p0和满足第二限制条件的路由路径,通过以下公式:For example, assuming that the above-mentioned routing path selection device determines that the shortest routing path in the 0th iteration only satisfies the first constraint condition, the shortest routing path in the 0th iteration can be regarded as the routing path that satisfies the first constraint condition, and Execute according to the shortest routing path p 0 selected at the 0th iteration and the routing path that satisfies the second constraint condition, through the following formula:

Figure GDA0002629676720000161
Figure GDA0002629676720000161

计算拉格朗日松弛算法的第1次迭代时的迭代因子λ1。其中,c(p0)为最短路由路径p0的第一路由路径信息,d(p0)为最短路由路径p0的第二路由路径信息。其中,该第一路由路径信息和第二路由路径信息可以是最短路由路径p0的多个路由路径信息中的任两个路由路径信息,例如,该第一路由路径信息和第二路由路径信息可以分别是最短路由路径p0的时延信息和带宽信息。Calculates the iteration factor λ 1 for the first iteration of the Lagrangian relaxation algorithm. Wherein, c(p 0 ) is the first routing path information of the shortest routing path p 0 , and d(p 0 ) is the second routing path information of the shortest routing path p 0 . Wherein, the first routing path information and the second routing path information may be any two routing path information in the multiple routing path information of the shortest routing path p 0 , for example, the first routing path information and the second routing path information They can be delay information and bandwidth information of the shortest routing path p 0 respectively.

然后再根据该迭代因子以及网络拓扑中每条链路的链路信息,通过第二公式:Then, according to the iteration factor and the link information of each link in the network topology, the second formula is passed:

Figure GDA0002629676720000162
Figure GDA0002629676720000162

计算第1次迭代时每条链路的加权值

Figure GDA0002629676720000163
并根据每条链路的加权值
Figure GDA0002629676720000164
通过Dijkstra算法选择第1次迭代时的最短路由路径p1;Calculate the weight of each link at the first iteration
Figure GDA0002629676720000163
and according to the weighted value of each link
Figure GDA0002629676720000164
Select the shortest routing path p 1 in the first iteration by Dijkstra algorithm;

假设上述的路由路径选择装置在得到第1次迭代时的最短路由路径p1,并确定该第1次迭代时的最短路由路径p1仅满足第二限制条件时,则可以将第1次迭代时的最短路由路径p1,作为满足第二限制条件的路由路径,并执行根据第1次迭代时选择的最短路由路径p1和第0次迭代时的最短路由路径p0,通过以下公式:Assuming that the above-mentioned routing path selection device obtains the shortest routing path p 1 in the first iteration, and determines that the shortest routing path p 1 in the first iteration only satisfies the second constraint, the first iteration can be The shortest routing path p 1 at the time of iteration is taken as the routing path satisfying the second constraint condition, and the shortest routing path p 1 selected at the first iteration and the shortest routing path p 0 at the 0th iteration are executed according to the following formula:

Figure GDA0002629676720000165
Figure GDA0002629676720000165

计算拉格朗日松弛算法的第2次迭代时的迭代因子λ2。其中,c(p1)为最短路由路径p1的第一路由路径信息,d(p1)为最短路由路径p1的第二路由路径信息,然后再根据该迭代因子以及网络拓扑中每条链路的链路信息,通过第二公式:Calculate the iteration factor λ 2 for the second iteration of the Lagrangian relaxation algorithm. Among them, c(p 1 ) is the first routing path information of the shortest routing path p 1 , and d(p 1 ) is the second routing path information of the shortest routing path p 1 , and then according to the iteration factor and each route in the network topology Link information of the link, through the second formula:

Figure GDA0002629676720000166
Figure GDA0002629676720000166

计算第2次迭代时每条链路的加权值

Figure GDA0002629676720000167
并根据每条链路的加权值
Figure GDA0002629676720000168
通过Dijkstra算法选择第2次迭代时的最短路由路径p2。Calculate the weighted value of each link at the 2nd iteration
Figure GDA0002629676720000167
and according to the weighted value of each link
Figure GDA0002629676720000168
The shortest routing path p 2 in the second iteration is selected by Dijkstra's algorithm.

假设上述的路由路径选择装置在判断该第2次迭代时的最短路由路径p2满足第一限制条件和第二限制条件时,则可以将该第2次迭代时的最短路由路径p2确定为最佳路由路径。Assuming that the above-mentioned routing path selection device determines that the shortest routing path p 2 in the second iteration satisfies the first constraint condition and the second constraint condition, the shortest routing path p 2 in the second iteration can be determined as best routing path.

与现有技术中的采用拉格朗日松弛算法只能计算满足一个限制条件的路由路径的方式相比,通过本发明实施例的一种路由路径选择方法,可以实现采用拉格朗日松弛算法,计算同时满足两个限制条件的路由路径。Compared with the method in the prior art in which the Lagrangian relaxation algorithm can only be used to calculate a routing path that satisfies one constraint condition, the routing path selection method according to the embodiment of the present invention can realize the use of the Lagrangian relaxation algorithm. , and calculate the routing path that satisfies both constraints at the same time.

在本发明实施例一种可选的实施例中,在图1所示的一种路由路径选择方法的基础上,本发明实施例还提供了一种可能的实现方式,如图5所示,为本发明实施例的一种路由路径选择方法第四种实施方式的流程图,在图5中,在S130,当第一路由路径满足两个限制条件中,除第一限制条件外的其他限制条件时,确定第一路由路径为最佳路由路径之后,本发明实施例的一种路由路径选择方法,还可以包括:In an optional embodiment of the embodiment of the present invention, on the basis of a routing path selection method shown in FIG. 1 , the embodiment of the present invention further provides a possible implementation manner, as shown in FIG. 5 , This is a flowchart of a fourth implementation manner of a routing path selection method according to an embodiment of the present invention. In FIG. 5, in S130, when the first routing path satisfies two restriction conditions, other restrictions except the first restriction condition When conditions are met, after determining that the first routing path is the best routing path, the method for selecting a routing path according to an embodiment of the present invention may further include:

S170,获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点。S170: Obtain a directed graph of the network topology corresponding to the optimal routing path, and source nodes and destination nodes of the optimal routing path.

在一些示例中,上述的路由路径选择装置在确定最佳路由路径后,为了在该最佳路由路径出现故障时,能够及时向用户提供服务,本发明实施例的一种路径选择方法还可以在该网络拓扑中选择备用路径,以避免最佳路径路由出现故障后,网络拓扑不能向用户提供服务。In some examples, after the above-mentioned routing path selection apparatus determines the optimal routing path, in order to provide services to users in time when the optimal routing path fails, a path selection method according to the embodiment of the present invention may also be performed in In this network topology, an alternate path is selected to avoid that the network topology cannot provide services to users after the optimal path routing fails.

具体的,上述的路由路径选择装置可以获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点。Specifically, the above-mentioned routing path selection apparatus can acquire a directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path.

例如,假设上述的路由路径选择装置得到的最佳路由路径,为由第一交换设备110、第二链路202、第三交换设备130、第八链路208、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路由路径组成的路由路径,该网络拓扑的有向图如图6a所示,则该最佳路由路径的源节点为第一交换设备110,目的节点为第九交换设备190。For example, it is assumed that the optimal routing path obtained by the above-mentioned routing path selection device is the first switching device 110, the second link 202, the third switching device 130, the eighth link 208, the sixth switching device 160, the tenth The routing path composed of the routing path composed of the second link 212, the eighth switching device 180, the fifteenth link 215, and the ninth switching device 190, the directed graph of the network topology is shown in Figure 6a, then the optimal route The source node of the path is the first switching device 110 , and the destination node is the ninth switching device 190 .

S180,获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图。S180: Obtain the reverse routing path of the optimal routing path, and modify the directed graph of the network topology through the reverse routing path of the optimal routing path, so as to obtain a modified graph of the directed graph of the network topology.

具体的,上述的路由路径选择装置,在获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点后,可以在该网络拓扑的有向图中,获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图。Specifically, after obtaining the directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path, the above-mentioned routing path selection apparatus can obtain the directed graph of the network topology in the directed graph of the optimal routing path. The reverse routing path of the optimal routing path is used to correct the directed graph of the network topology through the reverse routing path of the optimal routing path to obtain a modified graph of the directed graph of the network topology.

例如,如图6b所示,为图6a所示的网络拓扑的有向图的修正图的结构示意图,在图6b中,可以包括由第一交换设备110、第二链路202的反向链路202'、第三交换设备130、第八链路208的反向链路208'、第六交换设备160、第十二链路212的反向链路212'、第八交换设备180、第十五链路215反向链路215'、第九交换设备190组成的反向路由路径。For example, as shown in FIG. 6b, which is a schematic structural diagram of a modified graph of the directed graph of the network topology shown in FIG. 6a, in FIG. circuit 202', third switching device 130, reverse link 208' of eighth link 208, sixth switching device 160, reverse link 212' of twelfth link 212, eighth switching device 180, th The reverse routing path composed of the fifteenth link 215, the reverse link 215', and the ninth switching device 190.

S190,根据源节点和目的节点,通过Dijkstra算法在网络拓扑的有向图的修正图中查找第四最短路由路径;S190, according to the source node and the destination node, search for the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm;

上述的路由路径选择装置在得到图2所示的网络拓扑的有向图的修正图后,可以根据源节点和目的节点,在该网络拓扑的有向图的修正图中,通过Dijkstra算法查找第四最短路由路径。After the above-mentioned routing path selection device obtains the modified graph of the directed graph of the network topology shown in FIG. 2, according to the source node and the destination node, in the modified graph of the directed graph of the network topology, the Dijkstra algorithm can be used to find the No. Four shortest routing paths.

例如,假设上述的网络拓扑的有向图的修正图为图6b所示的修正图,则可以根据源节点“第一交换设备110”和目的节点“第九交换设备190”,通过Dijkstra算法,在图6b所示的修正图中查找最短路由路径。For example, assuming that the above-mentioned modified graph of the directed graph of the network topology is the modified graph shown in Fig. 6b, then according to the source node "first switching device 110" and the destination node "ninth switching device 190", through the Dijkstra algorithm, Find the shortest routing path in the modified graph shown in Figure 6b.

S200,获取最佳路由路径和最短路由路径中相同的链路,并分别从最佳路由路径和最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径。S200, obtain the same link in the best routing path and the shortest routing path, and delete the same link from the best routing path and the shortest routing path respectively, obtain the best routing path for deleting the same link and delete the same link The shortest routing path of the link.

具体的,上述的路由路径选择装置在从网络拓扑的有向图的修正图中查找到第四最短路由路径后,可以获取最佳路由路径和最短路由路径中相同的链路,并分别从最佳路由路径和最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径。Specifically, after finding the fourth shortest routing path in the modified graph of the directed graph of the network topology, the above-mentioned routing path selection device can obtain the same link in the optimal routing path and the shortest routing path, and select the same link from the shortest routing path respectively. The same link is deleted from the optimal routing path and the shortest routing path, and the optimal routing path for deleting the same link and the shortest routing path for deleting the same link are obtained.

例如,假设上述的路由路径选择装置选择的第四最短路由路径为:由第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第八链路208的反向链路208'、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190。For example, it is assumed that the fourth shortest routing path selected by the above routing path selection apparatus is: the first switching device 110, the third link 203, the fourth switching device 140, the ninth link 209, the sixth switching device 160, the Reverse link 208' of eight link 208, third switching device 130, seventh link 207, fifth switching device 150, tenth link 210, seventh switching device 170, thirteenth link 213, Nine switching devices 190 .

最佳路由路径为:由第一交换设备110、第二链路202、第三交换设备130、第八链路208、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路由路径组成的路由路径。The optimal routing path is: the first switching device 110, the second link 202, the third switching device 130, the eighth link 208, the sixth switching device 160, the twelfth link 212, the eighth switching device 180, A routing path composed of the fifteenth link 215 and the routing path composed of the ninth switching device 190 .

由于第八链路208和第八链路208的反向链路208'仅仅是方向相反,可以认为该两条链路相同,因此,分别将第八链路208和第八链路208的反向链路208'从各自所在的路径中删除。得到删除第八链路208的路径:第一交换设备110、第二链路202、第三交换设备130、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190,删除第八链路208的反向链路208'的路径:第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190。Since the eighth link 208 and the reverse link 208' of the eighth link 208 are only in opposite directions, it can be considered that the two links are the same. Therefore, the eighth link 208 and the reverse link 208' of the eighth link 208 are respectively Toward links 208' are removed from their respective paths. Obtain the path for deleting the eighth link 208: the first switching device 110, the second link 202, the third switching device 130, the sixth switching device 160, the twelfth link 212, the eighth switching device 180, the fifteenth switching device link 215, ninth switching device 190, delete the path of the reverse link 208' of the eighth link 208: first switching device 110, third link 203, fourth switching device 140, ninth link 209, The sixth switching device 160 , the third switching device 130 , the seventh link 207 , the fifth switching device 150 , the tenth link 210 , the seventh switching device 170 , the thirteenth link 213 , and the ninth switching device 190 .

S210,将删除相同的链路的最佳路由路径的所有链路和删除相同的链路的最短路由路径的所有链路,组成两条路径,并将该两条路径作为最佳路由路径的备用路由路径。S210, delete all the links of the best routing path of the same link and delete all the links of the shortest routing path of the same link to form two paths, and use the two paths as the backup of the best routing path routing path.

上述的路由路径选择装置在得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径后,可以根据该删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径,选择两条路径作为最佳路由路径的备用路由路径,以实现在最佳路由路径故障时,采用备用路由路径提供服务。After the above-mentioned routing path selection device obtains the best routing path for deleting the same link and the shortest routing path for deleting the same link, the optimal routing path for deleting the same link and the For the shortest routing path, two paths are selected as the backup routing paths of the optimal routing path, so that when the optimal routing path fails, the backup routing path is used to provide services.

例如,上述的路由路径选择装置,得到的删除第八链路208的路径:第一交换设备110、第二链路202、第三交换设备130、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190。得到的删除第八链路208的反向链路208'的路径:第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190。For example, the above-mentioned routing path selection apparatus obtains a path for deleting the eighth link 208: the first switching device 110, the second link 202, the third switching device 130, the sixth switching device 160, and the twelfth link 212 , an eighth switching device 180 , a fifteenth link 215 , and a ninth switching device 190 . The obtained path for deleting the reverse link 208' of the eighth link 208: the first switching device 110, the third link 203, the fourth switching device 140, the ninth link 209, the sixth switching device 160, the third Switching device 130 , seventh link 207 , fifth switching device 150 , tenth link 210 , seventh switching device 170 , thirteenth link 213 , ninth switching device 190 .

则可以在由删除第八链路208的路径的所有链路和删除第八链路208的反向链路208'的路径的所有链路中,选择两条路径,作为备用路由路径。Then, two paths may be selected as backup routing paths among all the links of the path where the eighth link 208 is deleted and the path of the reverse link 208 ′ of the eighth link 208 is deleted.

例如,上述的路由路径选择装置选择的两条路径可以是如图分别为:由第一交换设备110、第二链路202、第三交换设备130、第七链路207、第五交换设备150、第十链路210、第七交换设备170、第十三链路213、第九交换设备190组成的路径,和由第一交换设备110、第三链路203、第四交换设备140、第九链路209、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路径。For example, the two paths selected by the above routing path selection apparatus may be respectively as shown in the figure: the first switching device 110 , the second link 202 , the third switching device 130 , the seventh link 207 , and the fifth switching device 150 , the tenth link 210, the seventh switching device 170, the thirteenth link 213, the ninth switching device 190, and the path composed of the first switching device 110, the third link 203, the fourth switching device 140, the ninth switching device 190, and the A path composed of the nine link 209 , the sixth switching device 160 , the twelfth link 212 , the eighth switching device 180 , the fifteenth link 215 , and the ninth switching device 190 .

相应于上述的方法实施例,本发明实施例还提供了一种路由路径选择装置,如图7所示,为本发明实施例的一种路由路径选择装置的结构示意图,在图7中,该装置可以包括:Corresponding to the above method embodiments, an embodiment of the present invention further provides a routing path selection apparatus. As shown in FIG. 7 , it is a schematic structural diagram of a routing path selection apparatus according to an embodiment of the present invention. In FIG. 7 , the The device may include:

第一路径选择模块710,用于获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,其中,第一限制条件为两个限制条件中的任一限制条件;The first path selection module 710 is configured to obtain two restriction conditions, and use the first restriction condition of the two restriction conditions as the first restriction condition to determine whether there is a routing path that satisfies the first restriction condition in the network topology, wherein, The first constraint is any one of the two constraints;

第一判断模块720,用于当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件;The first judging module 720 is configured to judge whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions when there is a routing path that satisfies the first constraint condition in the network topology, wherein the second constraint condition is The condition is the restriction condition other than the first restriction condition among the two restriction conditions;

第一最佳路径选择模块730,用于当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。The first optimal path selection module 730 is configured to determine the routing path that satisfies the first constraint condition as the optimal routing path when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions.

本发明实施例提供的一种路由路径选择装置,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。In a routing path selection device provided by an embodiment of the present invention, when selecting an optimal routing path in a network topology, two restriction conditions can be obtained, and the first restriction condition among the two restriction conditions is used as the first restriction condition to determine Whether there is a routing path that satisfies the first constraint condition in the network topology, when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints , when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints, the routing path that satisfies the first constraint condition is determined to be the best routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions.

具体的,本发明实施例的一种路由路径选择装置,还可以包括:Specifically, a routing path selection device according to an embodiment of the present invention may further include:

第二最佳路径选择模块,用于当网络拓扑中不存在满足第一约束条件的路由路径时,根据两个限制条件,采用层次分析法在网络拓扑中选择最佳路由路径。The second optimal path selection module is used to select the optimal routing path in the network topology by using the Analytic Hierarchy Process (AHP) method according to the two constraints when there is no routing path satisfying the first constraint condition in the network topology.

具体的,本发明实施例的一种路由路径选择装置,还可以包括:Specifically, a routing path selection device according to an embodiment of the present invention may further include:

第二路径选择模块,用于在满足第一约束条件的路由路径,不满足两个限制条件中的第二限制条件时,以第二限制条件为第二约束条件,在网络拓扑中选择满足第二约束条件的路由路径;The second path selection module is configured to use the second restriction condition as the second restriction condition when the routing path satisfying the first constraint condition does not satisfy the second restriction condition of the two restriction conditions, and select the second restriction condition in the network topology that satisfies the first restriction condition. The routing path of the two constraints;

第三最佳路径选择模块,用于根据满足第一约束条件的路由路径和满足第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。The third optimal path selection module is used for calculating the optimal routing path by using the Lagrangian relaxation algorithm according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition.

具体的,第三最佳路径选择模块,可以包括:Specifically, the third optimal path selection module may include:

迭代因子计算子模块,用于根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式The iteration factor calculation sub-module is used to calculate the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration through the first formula

Figure GDA0002629676720000211
Figure GDA0002629676720000211

计算拉格朗日松弛算法的第j次迭代时的迭代因子λj,其中,λj为第j次迭代时的迭代因子,c(pr)为第一最短路由路径pr的第一路由路径信息,d(pr)为第一最短路由路径pr的第二路由路径信息,c(ps)第二最短路由路径ps的第一路由路径信息,d(ps)为第二最短路由路径ps的第二路由路径信息,第一路由路径信息和第二路由路径信息包括:最短路由路径的时延信息和最短路由路径的带宽信息,j、r、s为大于或等于0的整数,0≤r<j,0≤s<j,当r与s不同时为0时,r与s不同;当r=0,且s=0时,pr为满足第一约束条件的路由路径pc,c(pr)=c(pc),c(pc)为满足第一约束条件的路由路径pc的第一限制条件,d(pr)=d(pc),d(pc)为满足第一约束条件的路由路径pc的第二限制条件,ps为满足第二约束条件的路由路径pd,c(ps)=c(pd),c(pd)为满足第二约束条件的路由路径pd的第一限制条件,d(ps)=d(pd),d(pd)为满足第二约束条件的路由路径pd的第二限制条件;Calculate the iteration factor λ j at the j-th iteration of the Lagrangian relaxation algorithm, where λ j is the iteration factor at the j-th iteration, and c( pr ) is the first route of the first shortest route pr Path information, d( pr ) is the second routing path information of the first shortest routing path pr , c(ps) is the first routing path information of the second shortest routing path ps , d ( ps ) is the second routing path information The second routing path information of the shortest routing path ps , the first routing path information and the second routing path information include: the delay information of the shortest routing path and the bandwidth information of the shortest routing path, j, r, s are greater than or equal to 0 , 0≤r<j, 0≤s<j, when r is different from s, it is 0, and r is different from s; when r=0, and s=0, p r is the one that satisfies the first constraint Routing path pc , c( pr )= c ( pc ), c( pc ) is the first restriction condition of the routing path pc satisfying the first constraint condition, d( pr )= d ( pc ) , d(p c ) is the second constraint condition of the routing path p c that satisfies the first constraint condition, ps is the routing path p d that satisfies the second constraint condition, c(p s )=c(p d ) , c (p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition, d(ps )=d(p d ), d(p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition the second restriction;

加权值计算子模块,用于获取网络拓扑中每条链路的链路信息,根据链路信息和迭代因子,通过第二公式:The weighted value calculation sub-module is used to obtain the link information of each link in the network topology, according to the link information and the iteration factor, through the second formula:

Figure GDA0002629676720000212
Figure GDA0002629676720000212

计算第j次迭代时每条链路的加权值

Figure GDA0002629676720000213
并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration
Figure GDA0002629676720000213
And according to the weighted value of each link, the third shortest routing path in the jth iteration is selected by Dijkstra algorithm;

第一判断子模块,用于判断第j次迭代时的第三最短路由路径是否满足第一限制条件和第二限制条件;The first judgment submodule is used for judging whether the third shortest routing path in the j-th iteration satisfies the first restriction condition and the second restriction condition;

第一最佳路径选择子模块,当第j次迭代时的第三最短路由路径满足第一限制条件和第二限制条件,将第j次迭代时的第三最短路由路径确定为最佳路由路径;The first best path selection sub-module, when the third shortest routing path in the jth iteration satisfies the first constraint condition and the second constraint condition, determines the third shortest routing path in the jth iteration as the best routing path ;

当第j次迭代时的第三最短路由路径仅满足第一限制条件,将第j次迭代时的第三最短路由路径作为第r次迭代时选择的第一最短路由路径pr,并触发迭代因子计算子模块;When the third shortest routing path in the jth iteration only satisfies the first constraint, the third shortest routing path in the jth iteration is taken as the first shortest routing path pr selected in the rth iteration, and the iteration is triggered Factor calculation submodule;

当第j次迭代时的第三最短路由路径仅满足第二限制条件,将第三最短路由路径作为第s次迭代时选择的第二最短路由路径ps,并触发迭代因子计算子模块。When the third shortest routing path in the jth iteration only satisfies the second constraint condition, the third shortest routing path is taken as the second shortest routing path ps selected in the sth iteration, and the iteration factor calculation submodule is triggered.

具体的,本发明实施例的一种路由路径选择装置,还可以包括:Specifically, a routing path selection device according to an embodiment of the present invention may further include:

有向图获取模块,用于获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点;A directed graph obtaining module, used for obtaining the directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path;

修正模块,用于获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图;The correction module is used to obtain the reverse routing path of the optimal routing path, and modify the directed graph of the network topology through the reverse routing path of the optimal routing path, so as to obtain the modified graph of the directed graph of the network topology;

最短路径查找模块,用于根据源节点和目的节点,通过Dijkstra算法在网络拓扑的有向图的修正图中查找第四最短路由路径;The shortest path finding module is used to find the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm according to the source node and the destination node;

删除模块,用于获取最佳路由路径和第四最短路由路径中相同的链路,并分别从最佳路由路径和第四最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径;The deletion module is used to obtain the same link in the best routing path and the fourth shortest routing path, and delete the same link from the best routing path and the fourth shortest routing path respectively, and obtain the best link for deleting the same link. optimal routing path and delete the shortest routing path of the same link;

备用路径选择模块,用于将删除相同的链路的最佳路由路径的所有链路和删除相同的链路的最短路由路径的所有链路,组成两条路径,并将两条路径作为最佳路由路径的备用路由路径。The alternate path selection module is used to delete all the links of the best routing path of the same link and all the links of the shortest routing path of the same link to form two paths, and use the two paths as the best route Alternate routing paths for routing paths.

本发明实施例还提供了一种电子设备,如图8所示,包括处理器810、通信接口820、存储器830和通信总线840,其中,处理器810,通信接口820,存储器830通过通信总线840完成相互间的通信,An embodiment of the present invention further provides an electronic device, as shown in FIG. 8 , including a processor 810 , a communication interface 820 , a memory 830 and a communication bus 840 , wherein the processor 810 , the communication interface 820 , and the memory 830 pass through the communication bus 840 complete communication with each other,

存储器830,用于存放计算机程序;a memory 830 for storing computer programs;

处理器810,用于执行存储器830上所存放的程序时,实现如下步骤:When the processor 810 is used to execute the program stored in the memory 830, the following steps are implemented:

获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,其中,第一限制条件为两个限制条件中的任一限制条件;Obtain two restriction conditions, and use the first restriction condition in the two restriction conditions as the first restriction condition to determine whether there is a routing path that satisfies the first restriction condition in the network topology, wherein the first restriction condition is the two restriction conditions any of the restrictions in;

当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件;When there is a routing path that satisfies the first constraint condition in the network topology, it is judged whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, wherein the second constraint condition is that among the two constraint conditions, restrictions other than the first restriction;

当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。When the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, the routing path that satisfies the first constraint condition is determined to be the best routing path.

本发明实施例提供的一种电子设备,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。In an electronic device provided by an embodiment of the present invention, when selecting an optimal routing path in a network topology, two restriction conditions can be obtained, and the first restriction condition among the two restriction conditions is used as the first restriction condition to determine the network topology Whether there is a routing path that satisfies the first constraint condition in the network topology, when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints, when When the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints, the routing path that satisfies the first constraint condition is determined to be the best routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions.

上述电子设备提到的通信总线可以是外设部件互连标准(Peripheral ComponentInterconnect,PCI)总线或扩展工业标准结构(Extended Industry StandardArchitecture,EISA)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示,图中仅用一条粗线表示,但并不表示仅有一根总线或一种类型的总线。The communication bus mentioned in the above electronic device may be a peripheral component interconnect standard (Peripheral Component Interconnect, PCI) bus or an Extended Industry Standard Architecture (Extended Industry Standard Architecture, EISA) bus or the like. The communication bus can be divided into an address bus, a data bus, a control bus, and the like. For ease of presentation, only one thick line is used in the figure, but it does not mean that there is only one bus or one type of bus.

通信接口用于上述电子设备与其他设备之间的通信。The communication interface is used for communication between the above electronic device and other devices.

存储器可以包括随机存取存储器(Random Access Memory,RAM),也可以包括非易失性存储器(Non-Volatile Memory,NVM),例如至少一个磁盘存储器。可选的,存储器还可以是至少一个位于远离前述处理器的存储装置。The memory may include random access memory (Random Access Memory, RAM), and may also include non-volatile memory (Non-Volatile Memory, NVM), such as at least one disk memory. Optionally, the memory may also be at least one storage device located away from the aforementioned processor.

上述的处理器可以是通用处理器,包括中央处理器(Central Processing Unit,CPU)、网络处理器(Network Processor,NP)等;还可以是数字信号处理器(Digital SignalProcessing,DSP)、专用集成电路(Application Specific Integrated Circuit,ASIC)、现场可编程门阵列(Field-Programmable Gate Array,FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。The above-mentioned processor may be a general-purpose processor, including a central processing unit (Central Processing Unit, CPU), a network processor (Network Processor, NP), etc.; may also be a digital signal processor (Digital Signal Processing, DSP), an application-specific integrated circuit (Application Specific Integrated Circuit, ASIC), Field-Programmable Gate Array (Field-Programmable Gate Array, FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components.

本发明实施例还提供了一种计算机可读存储介质,该计算机可读存储介质内存储有计算机程序,该计算机程序被处理器执行时实现以上任一所述的路由路径选择方法。Embodiments of the present invention further provide a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, any one of the above routing path selection methods is implemented.

本发明实施例提供的一种计算机可读存储介质,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。In a computer-readable storage medium provided by an embodiment of the present invention, when selecting an optimal routing path in a network topology, two constraints can be obtained, and the first constraint among the two constraints is used as the first constraint, Determine whether there is a routing path that satisfies the first constraint condition in the network topology, and when there is a routing path that satisfies the first constraint condition in the network topology, determine whether the routing path that satisfies the first constraint condition satisfies the second restriction of the two constraints Condition, when the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, the routing path that satisfies the first constraint condition is determined to be the best routing path. Therefore, it can be realized that the routing path selected in the network topology fully satisfies the selected restriction conditions.

需要说明的是,在本文中,诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来,而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且,术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含,从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素,而且还包括没有明确列出的其他要素,或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下,由语句“包括一个……”限定的要素,并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。It should be noted that, in this document, relational terms such as first and second are used only to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply any relationship between these entities or operations. any such actual relationship or sequence exists. Moreover, the terms "comprising", "comprising" or any other variation thereof are intended to encompass a non-exclusive inclusion such that a process, method, article or device that includes a list of elements includes not only those elements, but also includes not explicitly listed or other elements inherent to such a process, method, article or apparatus. Without further limitation, an element qualified by the phrase "comprising a..." does not preclude the presence of additional identical elements in a process, method, article or apparatus that includes the element.

本说明书中的各个实施例均采用相关的方式描述,各个实施例之间相同相似的部分互相参见即可,每个实施例重点说明的都是与其他实施例的不同之处。尤其,对于系统实施例而言,由于其基本相似于方法实施例,所以描述的比较简单,相关之处参见方法实施例的部分说明即可。Each embodiment in this specification is described in a related manner, and the same and similar parts between the various embodiments may be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, for the system embodiments, since they are basically similar to the method embodiments, the description is relatively simple, and for related parts, please refer to the partial descriptions of the method embodiments.

以上所述仅为本发明的较佳实施例而已,并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等,均包含在本发明的保护范围内。The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the protection scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention are included in the protection scope of the present invention.

Claims (9)

1.一种路由路径选择方法,其特征在于,应用于网络拓扑中,所述方法包括:1. A routing path selection method, characterized in that, applied to a network topology, the method comprising: 获取两个限制条件,并以所述两个限制条件中的第一限制条件为第一约束条件,判断所述网络拓扑中是否存在满足所述第一约束条件的路由路径,其中,所述第一限制条件为所述两个限制条件中的任一限制条件;Acquire two restriction conditions, and use the first restriction condition in the two restriction conditions as the first restriction condition, and determine whether there is a routing path that satisfies the first restriction condition in the network topology, wherein the first restriction condition is A restriction is any one of the two restrictions; 当所述网络拓扑中存在满足所述第一约束条件的路由路径时,判断所述满足所述第一约束条件的路由路径是否满足所述两个限制条件中的第二限制条件,其中,所述第二限制条件为所述两个限制条件中,除所述第一限制条件外的限制条件;When there is a routing path that satisfies the first constraint condition in the network topology, it is judged whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, wherein the The second restriction condition is the restriction condition other than the first restriction condition among the two restriction conditions; 当所述满足所述第一约束条件的路由路径满足所述两个限制条件中的第二限制条件时,确定所述满足所述第一约束条件的路由路径为最佳路由路径;When the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraints, determining that the routing path that satisfies the first constraint condition is the best routing path; 获取与所述最佳路由路径对应的所述网络拓扑的有向图以及所述最佳路由路径的源节点和目的节点;obtaining a directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path; 获取所述最佳路由路径的反向路由路径,并通过所述最佳路由路径的反向路由路径对所述网络拓扑的有向图进行修正,得到所述网络拓扑的有向图的修正图;Obtain the reverse routing path of the best routing path, and modify the directed graph of the network topology through the reverse routing path of the best routing path to obtain a modified graph of the directed graph of the network topology ; 根据所述源节点和所述目的节点,通过Dijkstra算法在所述网络拓扑的有向图的修正图中查找第四最短路由路径;According to the source node and the destination node, find the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm; 获取所述最佳路由路径和所述第四最短路由路径中相同的链路,并分别从所述最佳路由路径和所述第四最短路由路径中删除所述相同的链路,得到删除所述相同的链路的最佳路由路径和删除所述相同的链路的最短路由路径;Obtain the same link in the best routing path and the fourth shortest routing path, and delete the same link from the best routing path and the fourth shortest routing path, respectively, to obtain the deleted all links. the best routing path for the same link and the shortest routing path for deleting the same link; 将所述删除所述相同的链路的最佳路由路径的所有链路和所述删除所述相同的链路的最短路由路径的所有链路,组成两条路径,并将所述两条路径作为所述最佳路由路径的备用路由路径。All the links of the best routing path of the deleted the same link and all the links of the shortest routing path of the deleted the same link are composed of two paths, and the two paths are combined. as an alternate routing path for the best routing path. 2.根据权利要求1所述的方法,其特征在于,在所述判断所述网络拓扑中是否存在满足所述第一约束条件的路由路径之后,所述方法还包括:2. The method according to claim 1, wherein after judging whether there is a routing path that satisfies the first constraint condition in the network topology, the method further comprises: 当所述网络拓扑中不存在满足所述第一约束条件的路由路径时,根据所述两个限制条件,采用层次分析法在所述网络拓扑中选择最佳路由路径。When there is no routing path satisfying the first constraint condition in the network topology, according to the two constraints, an AHP method is used to select the best routing path in the network topology. 3.根据权利要求1所述的方法,其特征在于,在所述判断所述满足所述第一约束条件的路由路径是否满足所述两个限制条件中的第二限制条件之后,所述方法还包括:3. The method according to claim 1, characterized in that, after judging whether the routing path that satisfies the first constraint condition satisfies the second constraint condition of the two constraint conditions, the method Also includes: 在所述满足所述第一约束条件的路由路径,不满足所述两个限制条件中的第二限制条件时,以所述第二限制条件为第二约束条件,在所述网络拓扑中选择满足所述第二约束条件的路由路径;When the routing path that satisfies the first constraint condition does not satisfy the second constraint condition of the two constraint conditions, the second constraint condition is used as the second constraint condition, and the selection is made in the network topology. a routing path that satisfies the second constraint; 根据所述满足第一约束条件的路由路径和所述满足所述第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。According to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition, a Lagrangian relaxation algorithm is used to calculate the optimal routing path. 4.根据权利要求3所述的方法,其特征在于,所述根据所述满足第一约束条件的路由路径和所述满足所述第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径,包括:4. The method according to claim 3, wherein, according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition, a Lagrangian relaxation algorithm is used, Calculate the best routing path, including: 根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式According to the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, through the first formula
Figure FDA0002629676710000021
Figure FDA0002629676710000021
计算所述拉格朗日松弛算法的第j次迭代时的迭代因子λj,其中,所述λj为第j次迭代时的迭代因子,所述c(pr)为第一最短路由路径pr的第一路由路径信息,所述d(pr)为第一最短路由路径pr的第二路由路径信息,所述c(ps)第二最短路由路径ps的第一路由路径信息,所述d(ps)为第二最短路由路径ps的第二路由路径信息,所述第一路由路径信息和所述第二路由路径信息包括:最短路由路径的时延信息和最短路由路径的带宽信息,所述j、r、s为大于或等于0的整数,0≤r<j,0≤s<j,当所述r与所述s不同时为0时,所述r与所述s不同;当r=0,且s=0时,所述pr为所述满足第一约束条件的路由路径pc,所述c(pr)=c(pc),所述c(pc)为所述满足第一约束条件的路由路径pc的第一限制条件,所述d(pr)=d(pc),所述d(pc)为所述满足第一约束条件的路由路径pc的第二限制条件,所述ps为所述满足第二约束条件的路由路径pd,所述c(ps)=c(pd),所述c(pd)为所述满足第二约束条件的路由路径pd的第一限制条件,所述d(ps)=d(pd),所述d(pd)为所述满足第二约束条件的路由路径pd的第二限制条件;Calculate the iteration factor λ j at the j-th iteration of the Lagrangian relaxation algorithm, where the λ j is the iteration factor at the j-th iteration, and the c( pr ) is the first shortest routing path The first routing path information of pr, the d(pr ) is the second routing path information of the first shortest routing path pr , and the c( ps ) is the first routing path of the second shortest routing path ps information, the d ( ps ) is the second routing path information of the second shortest routing path ps, the first routing path information and the second routing path information include: the delay information of the shortest routing path and the shortest routing path information Bandwidth information of the routing path, the j, r, and s are integers greater than or equal to 0, 0≤r<j, 0≤s<j, when the r is different from the s, it is 0, the r Different from the s; when r =0 and s=0, the pr is the routing path p c that satisfies the first constraint condition, and the c( pr )= c (pc ), so The c(p c ) is the first restriction condition of the routing path p c that satisfies the first constraint condition, the d( pr )=d(p c ), and the d(p c ) is the The second restriction condition of the routing path pc of the first constraint condition, the ps is the routing path p d that satisfies the second constraint condition, the c ( ps )=c(p d ) , the c (p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition, the d(ps )=d(p d ), and the d(p d ) is the first restriction condition of the routing path p d that satisfies the second restriction condition the second constraint condition of the routing path p d of the constraint condition; 获取所述网络拓扑中每条链路的链路信息,根据所述链路信息和所述迭代因子,通过第二公式:Obtain the link information of each link in the network topology, and use the second formula according to the link information and the iteration factor:
Figure FDA0002629676710000031
Figure FDA0002629676710000031
计算第j次迭代时每条链路的加权值
Figure FDA0002629676710000032
并根据所述每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径,其中,所述ci为第i条链路的第一链路信息,所述di为所述第i条链路的第二链路信息;
Calculate the weighted value of each link at the jth iteration
Figure FDA0002629676710000032
And according to the weighted value of each link, the third shortest routing path at the jth iteration is selected by the Dijkstra algorithm, wherein the c i is the first link information of the ith link, and the d i is the second link information of the i-th link;
判断所述第j次迭代时的第三最短路由路径是否满足第一限制条件和所述第二限制条件;Judging whether the third shortest routing path in the j-th iteration satisfies the first restriction condition and the second restriction condition; 当所述第j次迭代时的第三最短路由路径满足第一限制条件和所述第二限制条件,将所述第j次迭代时的第三最短路由路径确定为所述最佳路由路径;When the third shortest routing path in the jth iteration satisfies the first constraint condition and the second constraint condition, determining the third shortest routing path in the jth iteration as the best routing path; 当所述第j次迭代时的第三最短路由路径仅满足所述第一限制条件,将所述第j次迭代时的第三最短路由路径作为所述第r次迭代时选择的第一最短路由路径pr,并重复执行所述根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算所述拉格朗日松弛算法的第j次迭代时的迭代因子λjWhen the third shortest routing path in the jth iteration only satisfies the first constraint condition, the third shortest routing path in the jth iteration is taken as the first shortest selected in the rth iteration routing path p r , and repeatedly executing the first shortest routing path p r selected in the r-th iteration and the second shortest routing path ps selected in the s -th iteration, calculating the Lage by the first formula The iteration factor λ j of the jth iteration of the Langjian relaxation algorithm; 当所述第j次迭代时的第三最短路由路径仅满足所述第二限制条件,将所述第三最短路由路径作为所述第s次迭代时选择的第二最短路由路径ps,并重复执行所述根据第r次迭代时选择的第一最短路由路径pr和第s次迭代时选择的第二最短路由路径ps,通过第一公式计算所述拉格朗日松弛算法的第j次迭代时的迭代因子λjWhen the third shortest routing path in the jth iteration only satisfies the second constraint condition, the third shortest routing path is taken as the second shortest routing path ps selected in the sth iteration, and Repeatedly executing the first shortest routing path pr selected in the rth iteration and the second shortest routing path ps selected in the sth iteration, and calculating the first shortest routing path of the Lagrangian relaxation algorithm through the first formula. The iteration factor λ j at j iterations.
5.一种路由路径选择装置,其特征在于,应用于网络拓扑中,所述装置包括:5. A routing path selection device, characterized in that, when applied to a network topology, the device comprises: 第一路径选择模块,用于获取两个限制条件,并以所述两个限制条件中的第一限制条件为第一约束条件,判断所述网络拓扑中是否存在满足所述第一约束条件的路由路径,其中,所述第一限制条件为所述两个限制条件中的任一限制条件;A first path selection module, configured to obtain two restriction conditions, and use the first restriction condition of the two restriction conditions as the first restriction condition, and determine whether there is a system that satisfies the first restriction condition in the network topology A routing path, wherein the first restriction condition is any one of the two restriction conditions; 第一判断模块,用于当所述网络拓扑中存在满足所述第一约束条件的路由路径时,判断所述满足所述第一约束条件的路由路径是否满足所述两个限制条件中的第二限制条件,其中,所述第二限制条件为所述两个限制条件中,除所述第一限制条件外的限制条件;A first judging module, configured to judge whether the routing path that satisfies the first constraint condition satisfies the first one of the two constraints when there is a routing path that satisfies the first constraint condition in the network topology. Two constraints, wherein the second constraint is a constraint other than the first constraint among the two constraints; 第一最佳路径选择模块,用于当所述满足所述第一约束条件的路由路径满足所述两个限制条件中的第二限制条件时,确定所述满足所述第一约束条件的路由路径为最佳路由路径;A first optimal path selection module, configured to determine the route that satisfies the first constraint when the routing path that satisfies the first constraint satisfies the second constraint of the two constraints The path is the best routing path; 有向图获取模块,用于获取与最佳路由路径对应的网络拓扑的有向图以及最佳路由路径的源节点和目的节点;A directed graph obtaining module, used for obtaining the directed graph of the network topology corresponding to the optimal routing path and the source node and destination node of the optimal routing path; 修正模块,用于获取最佳路由路径的反向路由路径,并通过最佳路由路径的反向路由路径对网络拓扑的有向图进行修正,得到网络拓扑的有向图的修正图;The correction module is used to obtain the reverse routing path of the optimal routing path, and modify the directed graph of the network topology through the reverse routing path of the optimal routing path, so as to obtain the modified graph of the directed graph of the network topology; 最短路径查找模块,用于根据源节点和目的节点,通过Dijkstra算法在网络拓扑的有向图的修正图中查找第四最短路由路径;The shortest path finding module is used to find the fourth shortest routing path in the modified graph of the directed graph of the network topology through the Dijkstra algorithm according to the source node and the destination node; 删除模块,用于获取最佳路由路径和第四最短路由路径中相同的链路,并分别从最佳路由路径和第四最短路由路径中删除相同的链路,得到删除相同的链路的最佳路由路径和删除相同的链路的最短路由路径;The deletion module is used to obtain the same link in the best routing path and the fourth shortest routing path, and delete the same link from the best routing path and the fourth shortest routing path respectively, and obtain the best link for deleting the same link. optimal routing path and delete the shortest routing path of the same link; 备用路径选择模块,用于将删除相同的链路的最佳路由路径的所有链路和删除相同的链路的最短路由路径的所有链路,组成两条路径,并将两条路径作为最佳路由路径的备用路由路径。The alternate path selection module is used to delete all the links of the best routing path of the same link and all the links of the shortest routing path of the same link to form two paths, and use the two paths as the best route Alternate routing paths for routing paths. 6.根据权利要求5所述的装置,其特征在于,所述装置还包括:6. The apparatus according to claim 5, wherein the apparatus further comprises: 第二最佳路径选择模块,用于当所述网络拓扑中不存在满足所述第一约束条件的路由路径时,根据所述两个限制条件,采用层次分析法在所述网络拓扑中选择最佳路由路径。The second best path selection module is configured to, when there is no routing path satisfying the first constraint condition in the network topology, select the best path in the network topology by using AHP according to the two constraints optimal routing path. 7.根据权利要求5所述的装置,其特征在于,所述装置还包括:7. The apparatus of claim 5, wherein the apparatus further comprises: 第二路径选择模块,用于在所述满足所述第一约束条件的路由路径,不满足所述两个限制条件中的第二限制条件时,以所述第二限制条件为第二约束条件,在所述网络拓扑中选择满足所述第二约束条件的路由路径;The second path selection module is configured to use the second restriction condition as the second restriction condition when the routing path satisfying the first restriction condition does not satisfy the second restriction condition of the two restriction conditions , selecting a routing path that satisfies the second constraint condition in the network topology; 第三最佳路径选择模块,用于根据所述满足第一约束条件的路由路径和所述满足所述第二约束条件的路由路径,采用拉格朗日松弛算法,计算最佳路由路径。The third optimal path selection module is configured to calculate the optimal routing path by using the Lagrangian relaxation algorithm according to the routing path satisfying the first constraint condition and the routing path satisfying the second constraint condition. 8.一种电子设备,其特征在于,包括处理器、通信接口、存储器和通信总线,其中,处理器,通信接口,存储器通过通信总线完成相互间的通信;8. An electronic device, characterized in that it comprises a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface, and the memory complete mutual communication through the communication bus; 存储器,用于存放计算机程序;memory for storing computer programs; 处理器,用于执行存储器上所存放的程序时,实现权利要求1-4任一所述的方法步骤。The processor is configured to implement the method steps described in any one of claims 1-4 when executing the program stored in the memory. 9.一种计算机可读存储介质,其特征在于,所述计算机可读存储介质内存储有计算机程序,所述计算机程序被处理器执行时实现权利要求1-4任一所述的方法步骤。9 . A computer-readable storage medium, wherein a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, the method steps of any one of claims 1-4 are implemented.
CN201810570409.5A 2018-06-05 2018-06-05 A routing path selection method, device, electronic device and storage medium Expired - Fee Related CN108900413B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810570409.5A CN108900413B (en) 2018-06-05 2018-06-05 A routing path selection method, device, electronic device and storage medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810570409.5A CN108900413B (en) 2018-06-05 2018-06-05 A routing path selection method, device, electronic device and storage medium

Publications (2)

Publication Number Publication Date
CN108900413A CN108900413A (en) 2018-11-27
CN108900413B true CN108900413B (en) 2020-10-02

Family

ID=64344395

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810570409.5A Expired - Fee Related CN108900413B (en) 2018-06-05 2018-06-05 A routing path selection method, device, electronic device and storage medium

Country Status (1)

Country Link
CN (1) CN108900413B (en)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2020142873A1 (en) 2019-01-07 2020-07-16 华为技术有限公司 Method, device and system for controlling route iteration
CN110611620B (en) * 2019-09-29 2021-11-05 新华三信息安全技术有限公司 Link updating method and device
CN111404815B (en) * 2020-03-06 2021-03-16 武汉大学 Constrained routing method based on deep learning
CN113595902A (en) * 2020-04-30 2021-11-02 华为技术有限公司 Routing method and network equipment based on border gateway protocol
CN111866986B (en) * 2020-08-03 2022-04-29 苏州卓智创芯电子科技有限公司 Route self-adaptive forming method of wireless MESH internet of things
CN116016310B (en) * 2022-12-20 2025-08-01 紫金山实验室 Routing method and device, electronic equipment and storage medium

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6996065B2 (en) * 2000-07-06 2006-02-07 Lucent Technologies Inc. Dynamic backup routing of network tunnel paths for local restoration in a packet network
CN102281200A (en) * 2011-08-24 2011-12-14 华为技术有限公司 Method for selecting current backup route and router
CN103871090A (en) * 2012-12-17 2014-06-18 北京大学 Interactive path generating method and system
CN105471764A (en) * 2015-11-16 2016-04-06 中国科学院信息工程研究所 Method for guaranteeing end-to-end QoS in SDN network
US10560367B2 (en) * 2016-01-18 2020-02-11 Nokia Of America Corporation Bidirectional constrained path search

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102664802B (en) * 2012-04-20 2014-10-22 同济大学 Self-adaptive multi-constraint path searching method based on feedback
US9565689B2 (en) * 2013-10-23 2017-02-07 Texas Instruments Incorporated Near-optimal QoS-based resource allocation for hybrid-medium communication networks
CN105357068B (en) * 2015-11-03 2018-06-12 华中科技大学 The OpenFlow method for controlling network flow that a kind of application-oriented QoS is ensured
CN107896192B (en) * 2017-11-20 2020-09-25 电子科技大学 QoS control method for differentiating service priority in SDN network

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6996065B2 (en) * 2000-07-06 2006-02-07 Lucent Technologies Inc. Dynamic backup routing of network tunnel paths for local restoration in a packet network
CN102281200A (en) * 2011-08-24 2011-12-14 华为技术有限公司 Method for selecting current backup route and router
CN103871090A (en) * 2012-12-17 2014-06-18 北京大学 Interactive path generating method and system
CN105471764A (en) * 2015-11-16 2016-04-06 中国科学院信息工程研究所 Method for guaranteeing end-to-end QoS in SDN network
US10560367B2 (en) * 2016-01-18 2020-02-11 Nokia Of America Corporation Bidirectional constrained path search

Also Published As

Publication number Publication date
CN108900413A (en) 2018-11-27

Similar Documents

Publication Publication Date Title
CN108900413B (en) A routing path selection method, device, electronic device and storage medium
CN107454019B (en) Software-defined network dynamic bandwidth allocation method, device, device and storage medium
US20170111225A1 (en) Design validation using natural language processing
TWI760325B (en) Method and device for classifying application programs
CN105447131B (en) Method and device for determining network resource association
CN111930859A (en) Node processing method, device and equipment based on heterogeneous graph neural network
Mestre Weighted popular matchings
Zhou et al. Butterfly counting and bitruss decomposition on uncertain bipartite graphs
Eldan et al. Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
Sylvester Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
Cook Discrepancy properties for random regular digraphs
Faenza et al. Two-stage stochastic stable matching
CN104125146B (en) A kind of method for processing business and device
CN113014302B (en) Network function service chain deployment method facing satellite network
CN108965016B (en) A virtual network mapping method and device
CN109992631B (en) Dynamic heterogeneous information network embedding method and device and electronic equipment
Jonckheere et al. Stability of multi-dimensional birth-and-death processes with state-dependent 0-homogeneous jumps
Wang et al. Towards fast-convergence, low-delay and low-complexity network optimization
CN112243247A (en) Base station optimization priority determination method, device and computing device
CN109495305A (en) A kind of polymorphic flow network reliability estimation method of the more commodity of mostly distribution and device
Hairi et al. Beyond scaling: Calculable error bounds of the power-of-two-choices mean-field model in heavy-traffic
CN109245948A (en) The mapping method of virtual network and its device perceived safely
Igarashi et al. Higher-order bias corrections for kernel type density estimators on the unit or semi-infinite interval
CN115277570A (en) Flow distribution method and device, computer equipment and storage medium
WO2011061890A1 (en) Information processing device

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
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20201002

CF01 Termination of patent right due to non-payment of annual fee