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 PDFInfo
- 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
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/22—Alternate routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明实施例提供了一种路由路径选择方法、装置、电子设备及存储介质,其中,该方法包括:获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。
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.
Description
技术领域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
计算拉格朗日松弛算法的第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:
计算第j次迭代时每条链路的加权值并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration 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次迭代时的迭代因子λj;When 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次迭代时的迭代因子λj。When 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
计算拉格朗日松弛算法的第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:
计算第j次迭代时每条链路的加权值并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration 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
在一些示例中,为了保证文件的传输质量,在选择路由路径时,可以预先设置限制条件,然后根据该限制条件在网络拓扑中选择最佳路由路径。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
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
通过本发明实施例的一种路由路径选择方法,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。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
在本发明实施例一种可选的实施例中,在图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
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
通过使用拉格朗日松弛算法,可以在图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
计算拉格朗日松弛算法的第j次迭代时的迭代因子λj。Calculates 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:
计算第j次迭代时每条链路的加权值并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径。Calculate the weighted value of each link at the jth iteration 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次迭代时的迭代因子λj。Step 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次迭代时的迭代因子λj。Step 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:
其中,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:
计算第0次迭代时每条链路的加权值 Calculate the weighted value of each link at the 0th iteration
其中,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.
上述的路由路径选择装置在计算得到每条链路的加权值后,可以根据第0次迭代时每条链路的加权值在网络拓扑中,通过Dijkstra算法选择最短路由路径。The above-mentioned routing path selection device obtains the weighted value of each link in the calculation After that, the weighted value of each link at the 0th iteration can be 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
当上述的路由路径选择装置在确定该第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:
计算拉格朗日松弛算法的第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:
计算第1次迭代时每条链路的加权值并根据每条链路的加权值通过Dijkstra算法选择第1次迭代时的最短路由路径p1;Calculate the weight of each link at the first iteration and according to the weighted value of each link 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:
计算拉格朗日松弛算法的第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:
计算第2次迭代时每条链路的加权值并根据每条链路的加权值通过Dijkstra算法选择第2次迭代时的最短路由路径p2。Calculate the weighted value of each link at the 2nd iteration and according to the weighted value of each link 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
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',
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 "
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
最佳路由路径为:由第一交换设备110、第二链路202、第三交换设备130、第八链路208、第六交换设备160、第十二链路212、第八交换设备180、第十五链路215、第九交换设备190组成的路由路径组成的路由路径。The optimal routing path is: the
由于第八链路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
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
则可以在由删除第八链路208的路径的所有链路和删除第八链路208的反向链路208'的路径的所有链路中,选择两条路径,作为备用路由路径。Then, two paths may be selected as backup routing paths among all the links of the path where the
例如,上述的路由路径选择装置选择的两条路径可以是如图分别为:由第一交换设备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
相应于上述的方法实施例,本发明实施例还提供了一种路由路径选择装置,如图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
第一判断模块720,用于当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,其中,第二限制条件为两个限制条件中,除第一限制条件外的限制条件;The
第一最佳路径选择模块730,用于当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。The first optimal
本发明实施例提供的一种路由路径选择装置,在网络拓扑中选择最佳路由路径时,可以获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,当网络拓扑中存在满足第一约束条件的路由路径时,判断满足第一约束条件的路由路径是否满足两个限制条件中的第二限制条件,当满足第一约束条件的路由路径满足两个限制条件中的第二限制条件时,确定满足第一约束条件的路由路径为最佳路由路径。从而可以实现在网络拓扑中选择的路由路径完全满足所选择的限制条件。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
计算拉格朗日松弛算法的第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:
计算第j次迭代时每条链路的加权值并根据每条链路的加权值,通过Dijkstra算法选择第j次迭代时的第三最短路由路径;Calculate the weighted value of each link at the jth iteration 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
存储器830,用于存放计算机程序;a
处理器810,用于执行存储器830上所存放的程序时,实现如下步骤:When the
获取两个限制条件,并以两个限制条件中的第一限制条件为第一约束条件,判断网络拓扑中是否存在满足第一约束条件的路由路径,其中,第一限制条件为两个限制条件中的任一限制条件;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)
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)
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)
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)
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 |
-
2018
- 2018-06-05 CN CN201810570409.5A patent/CN108900413B/en not_active Expired - Fee Related
Patent Citations (5)
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 |