CN114726772B - Route protection method based on optimized network topology structure - Google Patents
Route protection method based on optimized network topology structureDownload PDFInfo
- Publication number
- CN114726772B CN114726772BCN202210197631.1ACN202210197631ACN114726772BCN 114726772 BCN114726772 BCN 114726772BCN 202210197631 ACN202210197631 ACN 202210197631ACN 114726772 BCN114726772 BCN 114726772B
- Authority
- CN
- China
- Prior art keywords
- network topology
- link
- path
- deleted
- overlap
- 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.)
- Active
Links
- 238000000034methodMethods0.000titleclaimsabstractdescription24
- 230000000295complement effectEffects0.000claimsabstractdescription20
- 238000012217deletionMethods0.000claimsdescription30
- 230000037430deletionEffects0.000claimsdescription30
- 238000004364calculation methodMethods0.000claimsdescription13
- 238000010586diagramMethods0.000description3
- 238000011084recoveryMethods0.000description3
- 101000827703Homo sapiens Polyphosphoinositide phosphataseProteins0.000description2
- 102100023591Polyphosphoinositide phosphataseHuman genes0.000description2
- 101100233916Saccharomyces cerevisiae (strain ATCC 204508 / S288c) KAR5 geneProteins0.000description2
- 101001121408Homo sapiens L-amino-acid oxidaseProteins0.000description1
- 102100026388L-amino-acid oxidaseHuman genes0.000description1
- 101100012902Saccharomyces cerevisiae (strain ATCC 204508 / S288c) FIG2 geneProteins0.000description1
- 230000009286beneficial effectEffects0.000description1
- 238000011161developmentMethods0.000description1
- 238000012986modificationMethods0.000description1
- 230000004048modificationEffects0.000description1
- 238000004904shorteningMethods0.000description1
- 238000001356surgical procedureMethods0.000description1
- 238000012546transferMethods0.000description1
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
- 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/28—Routing or path finding of packets in data switching networks using route fault recovery
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/50—Reducing energy consumption in communication networks in wire-line communication networks, e.g. low power modes or reduced link rate
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Description
Translated fromChinese技术领域Technical Field
本发明涉及路由保护技术领域，更具体地说，涉及一种基于优化网络拓扑结构的路由保护方法。The present invention relates to the technical field of routing protection, and more specifically to a routing protection method based on optimizing network topology structure.
背景技术Background Art
随着互联网的发展，其支持的应用范围呈现出了显著的变化。最初，互联网主要支持一些非实时应用，如电子邮件，传输文件等。而如今大量的实时业务数据在互联网上广泛传播，如IP语音(Voice overInternet Protocol，VoIP)、股票在线交易、远程手术、视频流媒体和即时通信等，这些新型应用对路由可用性提出了更高的要求。由此可见，路由可用性将直接影响用户的财产安全甚至生命安全。相关研究表明，网络中的故障频繁发生，并且不可避免。在故障修复期间，路由协议需要经历一段时间的收敛过程，在此过程中会出现路由黑洞、路由环路等现象，从而导致网络中断，报文丢失，大大降低了路由可用性。有研究表明，当一条OC-48的链路断开10秒钟将导致300万个大小为1KB的报文丢失。在实时应用中通常要求修复故障的时间为毫秒级，就目前互联网部署的域内路由协议而言，如OSPF和IS-IS，则需要几秒甚至几十秒的时间来完成收敛，无法满足实时应用对路由可用性的要求。因此，如何提高域内路由可用性成为互联网亟待需要解决的一个科学问题，这使得越来越多的科研工作者开始投身于研究如何提升网络快速应对故障的能力。With the development of the Internet, the scope of applications it supports has changed significantly. Initially, the Internet mainly supported some non-real-time applications, such as e-mail and file transfer. Now, a large amount of real-time business data is widely spread on the Internet, such as Voice over Internet Protocol (VoIP), online stock trading, remote surgery, video streaming and instant messaging. These new applications have put forward higher requirements for routing availability. It can be seen that routing availability will directly affect the property safety and even life safety of users. Related studies have shown that network failures occur frequently and are inevitable. During the fault repair period, the routing protocol needs to go through a period of convergence, during which routing black holes and routing loops will occur, resulting in network interruption and message loss, which greatly reduces the routing availability. Studies have shown that when an OC-48 link is disconnected for 10 seconds, 3 million 1KB messages will be lost. In real-time applications, the time required to repair the fault is usually in milliseconds. As for the intra-domain routing protocols currently deployed on the Internet, such as OSPF and IS-IS, it takes several seconds or even tens of seconds to complete convergence, which cannot meet the requirements of real-time applications for routing availability. Therefore, how to improve the availability of intra-domain routing has become a scientific problem that the Internet urgently needs to solve, which has led to an increasing number of scientific researchers beginning to devote themselves to studying how to improve the network's ability to quickly respond to failures.
目前，提高域内路由可用性的算法可以分为两类，被动恢复算法和路由保护算法。其中被动恢复算法主要研究当网络出现故障时如何加快路由收敛速度，尽量缩短网络中断时间，但是当网络中的链路频繁断开时，该算法可能导致路由不稳定。路由保护算法则是根据相关规则事先计算备份路由，当网络中出现故障时，利用事先计算的备份路由转发数据包，从而最大化减少报文丢失，缩短网络服务中断时间。相比较而言，路由保护算法更受学术界青睐。At present, algorithms for improving intra-domain routing availability can be divided into two categories: passive recovery algorithms and routing protection algorithms. The passive recovery algorithm mainly studies how to speed up routing convergence and minimize network interruption time when a network failure occurs. However, when links in the network are frequently disconnected, the algorithm may cause routing instability. The routing protection algorithm calculates backup routes in advance according to relevant rules. When a failure occurs in the network, the pre-calculated backup routes are used to forward data packets, thereby minimizing packet loss and shortening network service interruption time. In comparison, routing protection algorithms are more favored by the academic community.
发明内容Summary of the invention
为了解决现有技术中路由保护方法故障保护率低和无法实际部署的难题，本发明提出了一种基于优化网络拓扑结构的路由保护方法(ERPBONT)。本发明的算法容易实现，部署简易，能够有效的解决备份路径与最短路径有着大量的公共链路而导致的故障恢复率低的问题,能够显著的降低路径重合度,具有能够快速恢复故障网络的能力。In order to solve the problems of low fault protection rate and impractical deployment of routing protection methods in the prior art, the present invention proposes a routing protection method (ERPBONT) based on optimized network topology. The algorithm of the present invention is easy to implement and deploy, and can effectively solve the problem of low fault recovery rate caused by a large number of common links between the backup path and the shortest path, can significantly reduce the path overlap, and has the ability to quickly recover the faulty network.
为了解决上述技术问题，本发明采用的技术方案为：一种基于优化网络拓扑结构的路由保护方法，包括以下步骤：In order to solve the above technical problems, the technical solution adopted by the present invention is: a routing protection method based on optimizing the network topology structure, comprising the following steps:
S1、读取配置文件生成网络拓扑G(V，E，W)，其中V表示网络拓扑的节点集合，E表示网络拓扑的链路集合，W表示网络拓扑链路代价的集合；S1. Read the configuration file to generate the network topology G(V, E, W), where V represents the node set of the network topology, E represents the link set of the network topology, and W represents the set of link costs of the network topology;
S2、计算网络拓扑G中边的补集
S3、根据网络拓扑G及其补集
S301、从补集
S302、更新网络拓扑G，重复步骤S3，直至新增链路集合AL中的链路数量等于第一阈值T1；S302, updating the network topology G, and repeating step S3 until the number of links in the newly added link set AL is equal to the first threshold T1 ;
S4、根据网络拓扑G和新增链路集合AL来计算删除链路集合DL，具体步骤为：S4. Calculate the deleted link set DL according to the network topology G and the newly added link set AL. The specific steps are as follows:
S401、将网络拓扑G与新增链路集合AL并集形成新网络拓扑G’，初始化备选删除链路集合L＝E；S401, the network topology G and the newly added link set AL are combined to form a new network topology G', and the candidate deletion link set L=E is initialized;
S402、从备选删除链路集合L中选择各个链路从新网络拓扑G’中删除，计算删除前后网络的路径重合度，将路径重合度达到最小值，且网络拓扑为连通图时对应的删除链路加入删除链路集合DL，同时将其从备选删除链路集合L和新网络拓扑G’中删除；S402, select each link from the candidate deletion link set L and delete it from the new network topology G', calculate the path overlap of the network before and after the deletion, add the corresponding deletion link when the path overlap reaches the minimum value and the network topology is a connected graph to the deletion link set DL, and delete it from the candidate deletion link set L and the new network topology G';
S403、重复步骤S402，直至删除链路集合DL中的链路数量等于第二阈值T2；S403, repeat step S402 until the number of links in the deleted link set DL is equal to the second threshold T2 ;
S5、根据新增链路集合AL和删除链路集合DL更新网络拓扑，根据更新后的网络拓扑计算每一个节点之间的最短路径即备份路径。S5. Update the network topology according to the newly added link set AL and the deleted link set DL, and calculate the shortest path between each node, that is, the backup path, according to the updated network topology.
优选地，所述第一阈值T1的取值范围为5～10。Preferably, the value range of the first threshold T1 is 5-10.
优选地，所述第二阈值T2的取值范围为5～10。Preferably, the value range of the second threshold T2 is 5-10.
优选地，所述步骤S2中，每条链路的权值的计算公式为：Preferably, in step S2, the calculation formula for the weight of each link is:
w(u，v)＝cost(u，v)-min(W)；w(u, v)=cost(u, v)-min(W);
其中，w(u，v)表示(u,v)链路的权值，cost(u，v)表示节点u和节点v最短路径之间的代价，min(W)表示网络中所有链路代价的最小值。Among them, w(u, v) represents the weight of the (u, v) link, cost(u, v) represents the cost of the shortest path between node u and node v, and min(W) represents the minimum cost of all links in the network.
优选地，所述步骤S301中，计算路径重合度时，根据网络拓扑中的最短路径进行计算，其计算公式为：Preferably, in step S301, when calculating the path overlap, the calculation is performed based on the shortest path in the network topology, and the calculation formula is:
其中，C(G0，G1)表示当前网络拓扑结构G0和增加链路后的网络拓扑结构G1之间的路径重合度，CD(s，d)表示节点对s和d之间的路径重合度，V表示当前网络拓扑结构G0中节点的集合，SP(s，d)表示当前网络拓扑结构G0中的节点对s和d之间的最短路径集合，BP(s，d)表示增加链路后的网络拓扑结构G1中的节点对s和d之间的最短路径集合。Among them, C(G0 ,G1 ) represents the path overlap between the current network topologyG0 and the network topologyG1 after adding links, CD(s, d) represents the path overlap between node pairs s and d, V represents the set of nodes in the current network topologyG0 , SP(s, d) represents the shortest path set between node pairs s and d in the current network topologyG0 , and BP(s, d) represents the shortest path set between node pairs s and d in the network topologyG1 after adding links.
优选地，所述步骤S402中，计算路径重合度时，根据网络拓扑中的最短路径进行计算，其计算公式为：Preferably, in step S402, when calculating the path overlap, the calculation is performed based on the shortest path in the network topology, and the calculation formula is:
其中，C(G0，G2)表示当前网络拓扑结构G0和删除链路后的网络拓扑结构G2之间的路径重合度，CD(s，d)表示节点对s和d之间的路径重合度，V表示当前网络拓扑结构G0中节点的集合，SP(s，d)表示当前网络拓扑结构G0中的节点对s和d之间的最短路径集合，BP(s，d)表示删除链路后的网络拓扑结构G2中的节点对s和d之间的最短路径集合。Among them, C(G0 ,G2 ) represents the path overlap between the current network topologyG0 and the network topologyG2 after deleting the link, CD(s, d) represents the path overlap between the node pair s and d, V represents the set of nodes in the current network topologyG0 , SP(s, d) represents the shortest path set between the node pair s and d in the current network topologyG0 , and BP(s, d) represents the shortest path set between the node pair s and d in the network topologyG2 after deleting the link.
优选地，所述最短路径采用迪杰斯特拉算法进行计算。Preferably, the shortest path is calculated using Dijkstra's algorithm.
优选地，所述步骤S402的具体步骤为：Preferably, the specific steps of step S402 are:
S4021、从备选删除链路集合L中选择一个链路从新网络拓扑G’中删除，判断待删除链路从网络拓扑G’中删除后，网络拓扑是否为连通图，若为连通图，则计算该链路删除前后网络的路径重合度；S4021, selecting a link from the candidate deletion link set L to be deleted from the new network topology G', determining whether the network topology is a connected graph after the link to be deleted is deleted from the network topology G', and if it is a connected graph, calculating the path overlap degree of the network before and after the link is deleted;
S4022、重复步骤S4021，遍历备选删除链路集合L中所有链路，计算各个链路删除前后网络的路径重合度，找到路径重合度达到最小值时对应的链路作为待删除链路T’；S4022, repeat step S4021, traverse all links in the candidate deletion link set L, calculate the path overlap of the network before and after each link is deleted, and find the link corresponding to the minimum path overlap as the link to be deleted T';
S4023、将该待删除链路T’加入删除链路集合DL，同时将其从备选删除链路集合L和新网络拓扑G’中删除。S4023. Add the link to be deleted T' to the deletion link set DL, and delete it from the candidate deletion link set L and the new network topology G'.
优选地，所述步骤S301中，若有两条路径重合度最小且相同，随机选取一条加入网络拓扑G。Preferably, in step S301, if there are two paths with the smallest overlap and the same overlap, one of them is randomly selected to join the network topology G.
优选地，所述步骤S402中，若有两条路径重合度最小且相同，随机选取一条从网络拓扑G中删除。Preferably, in step S402, if there are two paths with the smallest overlap and the same overlap, one of them is randomly selected and deleted from the network topology G.
本发明与现有技术相比具有以下有益效果：Compared with the prior art, the present invention has the following beneficial effects:
本发明克服了已有路由保护方法计算过多备份路径和不易部署的问题，本发明为所有的源目的仅仅计算一条备份路径，该路径和最短路径具有最小的路径重合度，从而大大提高了网络可用性。本发明计算简单，算法复杂度低，容易在实际网路中部署。The present invention overcomes the problem that the existing routing protection method calculates too many backup paths and is difficult to deploy. The present invention only calculates one backup path for all source destinations, and the path has the minimum path overlap with the shortest path, thereby greatly improving network availability. The present invention is simple to calculate, has low algorithm complexity, and is easy to deploy in an actual network.
附图说明BRIEF DESCRIPTION OF THE DRAWINGS
图1为本发明实施例提供的一种基于优化网络拓扑结构的路由保护方法的流程示意图；FIG1 is a schematic flow chart of a routing protection method based on optimizing a network topology structure provided by an embodiment of the present invention;
图2为本发明实施例中新增链路的流程示意图；FIG2 is a schematic diagram of a process of adding a new link in an embodiment of the present invention;
图3为本发明实施例中删除链路集合的流程示意图；FIG3 is a schematic diagram of a process of deleting a link set in an embodiment of the present invention;
图4是本发明提供的一种基于优化网络拓扑结构的路由保护方法的网络拓扑结构示意图。FIG4 is a schematic diagram of a network topology structure of a routing protection method based on optimizing the network topology structure provided by the present invention.
具体实施方式DETAILED DESCRIPTION
为使本发明实施例的目的、技术方案和优点更加清楚，下面将对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例；基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below. Obviously, the described embodiments are part of the embodiments of the present invention, rather than all the embodiments; based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without making creative work are within the scope of protection of the present invention.
如图1～3所示，本发明实施例提供了一种基于优化网络拓扑结构的路由保护方法，包括以下步骤：As shown in FIGS. 1 to 3 , an embodiment of the present invention provides a routing protection method based on optimizing a network topology structure, comprising the following steps:
S1、读取配置文件生成网络拓扑G＝(V，E，W)，其中V表示网络拓扑的节点集合，E表示网络拓扑的链路集合，W表示网络拓扑链路代价的集合。S1. Read the configuration file to generate a network topology G=(V, E, W), where V represents a set of nodes in the network topology, E represents a set of links in the network topology, and W represents a set of link costs in the network topology.
S2、计算网络拓扑G中边的补集
具体地，本实施例中，所述步骤S2中，每条链路的权值的计算公式为：Specifically, in this embodiment, in step S2, the calculation formula for the weight of each link is:
w(u，v)＝cost(u，v)-min(W)； (1)w(u, v)=cost(u, v)-min(W); (1)
其中，w(u，v)表示(u,v)链路的权值，cost(u，v)表示节点u和节点v最短路径之间的代价，min(W)表示网络中所有链路代价的最小值。Among them, w(u, v) represents the weight of the (u, v) link, cost(u, v) represents the cost of the shortest path between node u and node v, and min(W) represents the minimum cost of all links in the network.
S3、根据网络拓扑G及其补集
S301、从补集
S302、更新网络拓扑G，重复步骤S301，直至新增链路集合AL中的链路数量等于第一阈值T1。S302, updating the network topology G, and repeating step S301 until the number of links in the newly added link set AL is equal to the first threshold T1 .
进一步地，所述步骤S301中，计算路径重合度时，根据网络拓扑中的最短路径进行计算，其计算公式为：Furthermore, in step S301, when calculating the path overlap, the calculation is performed based on the shortest path in the network topology, and the calculation formula is:
其中，C(G0，G1)表示当前网络拓扑结构G0和增加链路后的网络拓扑结构G1之间的路径重合度，CD(s，d)表示节点对s和d之间的路径重合度，V表示当前网络拓扑结构G0中节点的集合，SP(s，d)表示当前网络拓扑结构G0中的节点对s和d之间的最短路径集合，BP(s，d)表示增加链路后的网络拓扑结构G1中的节点对s和d之间的最短路径集合。Among them, C(G0 ,G1 ) represents the path overlap between the current network topologyG0 and the network topologyG1 after adding links, CD(s, d) represents the path overlap between node pairs s and d, V represents the set of nodes in the current network topologyG0 , SP(s, d) represents the shortest path set between node pairs s and d in the current network topologyG0 , and BP(s, d) represents the shortest path set between node pairs s and d in the network topologyG1 after adding links.
S4、根据网络拓扑G＝(V，E，W)和新增链路集合AL来计算删除链路集合DL，如图3所示，其具体步骤为：S4. Calculate the deleted link set DL according to the network topology G=(V, E, W) and the newly added link set AL, as shown in FIG3 , and the specific steps are as follows:
S401、将网络拓扑G＝(V，E，W)与新增链路集合AL并集形成新网络拓扑G’＝(V，E’＝E∪AL，W)，初始化备选删除链路集合L＝E；要删除的链路不考虑之前新增的链路。S401. The network topology G = (V, E, W) is combined with the newly added link set AL to form a new network topology G' = (V, E' = E∪AL, W), and the candidate deletion link set L = E is initialized; the links to be deleted do not consider the previously added links.
S402、从备选删除链路集合L中选择各个链路从新网络拓扑G’中删除，计算删除前后网络的路径重合度，将路径重合度达到最小值，且网络拓扑为连通图时对应的删除链路加入删除链路集合DL，同时将其从备选删除链路集合L和新网络拓扑G’中删除；S402, select each link from the candidate deletion link set L and delete it from the new network topology G', calculate the path overlap of the network before and after the deletion, add the corresponding deletion link when the path overlap reaches the minimum value and the network topology is a connected graph to the deletion link set DL, and delete it from the candidate deletion link set L and the new network topology G';
具体地，所述步骤S402中，计算路径重合度时，也是根据公式(2)和公式(3)进行计算。Specifically, in step S402, when calculating the path overlap, it is also calculated according to formula (2) and formula (3).
具体地，所述步骤S402的具体步骤为：Specifically, the specific steps of step S402 are:
S4021、从备选删除链路集合L中选择一个链路从新网络拓扑G’中删除，判断待删除链路从网络拓扑G’中删除后，网络拓扑是否为连通图，若为连通图，则计算该链路删除前后网络的路径重合度；S4021, selecting a link from the candidate deletion link set L to be deleted from the new network topology G', determining whether the network topology is a connected graph after the link to be deleted is deleted from the network topology G', and if it is a connected graph, calculating the path overlap degree of the network before and after the link is deleted;
S4022、重复步骤S4021，遍历备选删除链路集合L中所有链路，计算各个链路删除前后网络的路径重合度，找到路径重合度达到最小值时对应的链路作为待删除链路T’；S4022, repeat step S4021, traverse all links in the candidate deletion link set L, calculate the path overlap of the network before and after each link is deleted, and find the link corresponding to the minimum path overlap as the link to be deleted T';
S4023、将该待删除链路T’加入删除链路集合DL，同时将其从备选删除链路集合L和新网络拓扑G’中删除。S4023. Add the link to be deleted T' to the deletion link set DL, and delete it from the candidate deletion link set L and the new network topology G'.
S403、更新新网络拓扑G’，重复步骤S402，直至删除链路集合DL中的链路数量等于第二阈值T2。本实施例中，循环寻找第二条待删除链路时，新网络拓扑G’中不包括前一个循环已经删除的链路。S403, update the new network topology G', and repeat step S402 until the number of links in the deleted link set DL is equal to the second thresholdT2 . In this embodiment, when cyclically searching for the second link to be deleted, the new network topology G' does not include the links that have been deleted in the previous cycle.
S5、根据新增链路集合AL和删除链路集合DL更新网络拓扑，根据更新后的网络拓扑计算每一个节点之间的最短路径即备份路径。S5. Update the network topology according to the newly added link set AL and the deleted link set DL, and calculate the shortest path between each node, that is, the backup path, according to the updated network topology.
具体地，本实施例中，所述第一阈值T1的取值范围为5～10。所述第二阈值T2的取值范围为5～10。也就是说，本实施例中，新增链路集合AL和删除链路集合DL中的链路数量可以根据网络大小和具体情况需要进行设定。Specifically, in this embodiment, the value range of the first threshold T1 is 5 to 10. The value range of the second threshold T2 is 5 to 10. That is, in this embodiment, the number of links in the newly added link set AL and the deleted link set DL can be set according to the network size and specific situation.
具体地，本实施例中，所述最短路径采用迪杰斯特拉算法进行计算。Specifically, in this embodiment, the shortest path is calculated using the Dijkstra algorithm.
以图4所述的拓扑结构为例，说明本发明实施例的具体步骤。The topology structure shown in FIG. 4 is taken as an example to illustrate specific steps of the embodiment of the present invention.
步骤1、读取配置文件生成无向图G＝(V，E，W)；如图4中所描述的拓扑结构；V是节点集合，E是边的集合，W是链路权值的集合。Step 1: Read the configuration file to generate an undirected graph G=(V, E, W); a topological structure as described in FIG4 ; V is a set of nodes, E is a set of edges, and W is a set of link weights.
步骤2：计算出G所有节点对之间的最短路径集合SP＝{(a,b),(a,b,c),(a,d),(b,c),(b,c,d),(c,d)}。Step 2: Calculate the shortest path set SP = {(a,b), (a,b,c), (a,d), (b,c), (b,c,d), (c,d)} between all node pairs in G.
步骤3：计算网络拓扑G中边的补集
步骤4：将扩展网络拓扑结构初始化为G，将增加链路的集合AL初始化为空集，根据公式(2)和(3)计算网络中所有节点对之间的路径重合度，作为计入在original＝current＝1。Step 4: Initialize the extended network topology to G, initialize the set of added links AL to an empty set, and calculate the path overlap between all node pairs in the network according to formulas (2) and (3), which is included in original=current=1.
步骤5：满足新增链路数量是否小于阈值，若是，进行步骤6；Step 5: Check whether the number of newly added links is less than the threshold. If so, proceed to step 6.
步骤6：从集合
步骤7：更新扩展网络拓扑结构的参数，将链路(a,c)从集合E中删除，计算当前网络重合度为original＝original1。Step 7: Update the parameters of the extended network topology, delete the link (a, c) from the set E, and calculate the current network overlap as original = original1.
步骤8：满足条件original＞current进行步骤9；Step 8: If the condition original＞current is satisfied, proceed to step 9;
步骤9：将链路(a,c)加入到集合AL＝{(a,c)}中；Step 9: Add link (a, c) to the set AL = {(a, c)};
步骤10：再次判断是否满足新增链路数量是否小于阈值，是，则进行步骤11；Step 10: Determine again whether the number of newly added links is less than the threshold, if yes, proceed to step 11;
步骤11：从集合
步骤12：更新扩展网络拓扑结构的参数，将链路(b,d)从集合
步骤13：判断满足条件original＞current，将链路(b,d)加入到集合AL＝{(a,c)}中；Step 13: determine whether the condition original＞current is satisfied, and add link (b, d) to the set AL＝{(a, c)};
步骤14：重新判断是否满足循环条件，新增链路数量是小于阈值，但不满足T＞0条件，进行步骤15；Step 14: Re-determine whether the loop condition is met. If the number of newly added links is less than the threshold but does not meet the condition T＞0, proceed to step 15;
步骤15：返回增加链路集合AL＝{(a,c),(b,d)}；Step 15: Return to add link set AL = {(a,c), (b,d)};
步骤16：设置第二阈值为2，将扩展网络拓扑结构初始化为G(V,E'＝E∪AL)，将删除链路的集合DL初始化为空集，将删除链路集合L初始化为L＝E＝{(a,b),(b,c),(c,d),(a,d)}，current＝original；Step 16: Set the second threshold to 2, initialize the extended network topology structure to G(V,E'＝E∪AL), initialize the set of deleted links DL to an empty set, initialize the deleted link set L to L＝E＝{(a,b),(b,c),(c,d),(a,d)}, current＝original;
步骤17：判断删除链路数量小于5且T＞0且Current＞＝0，进行步骤18；Step 17: If the number of deleted links is less than 5 and T>0 and Current>=0, proceed to step 18;
步骤18：从删除链路集合L中选择一条链路(a,b)从网络拓扑G中删除生成拓扑G′1，计算G′1的路径所有节点对之间的最短路径集合SP1＝{(a,c,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，计算网络中所有节点对之间的路径重合度计入在
步骤18：判断网络G’为连通图，进行步骤19；Step 18: Determine that the network G' is a connected graph, and proceed to step 19;
步骤19：新扩展网络拓扑结构的参数，将链路(a,b)从集合E中删除，current＝original1；Step 19: Parameters of the newly expanded network topology, delete link (a, b) from set E, current = original1;
步骤20：满足original＞current，将链路(a,b)加入到集合DL中，之后进行步骤13；Step 20: If original>current is satisfied, add link (a,b) to the set DL, and then proceed to step 13;
步骤20：重复判断是否满足循环条件，满足，进入步骤21；Step 20: Repeat the judgment to see whether the loop condition is met. If so, proceed to step 21.
步骤21：从集合L中选择一条链路(b,c)从网络拓扑G中删除生成拓扑G′2，计算G′2的路径所有节点对之间的最短路径集合SP2＝{(a,d,b),(a,c),(a,d),(b,d,c),(b,d),(c,d)}，计算网络中所有节点对之间的路径重合度计入在
步骤22：网络G′为连通图，新扩展网络拓扑结构的参数，将链路(c,d)从集合E中删除，current＝original3；Step 22: The network G′ is a connected graph, the parameters of the newly expanded network topology structure are deleted from the set E, and current = original3;
步骤23：满足original＞current条件，将链路(a,b)加入到集合DL中；Step 23: If the condition original＞current is satisfied, add link (a, b) to the set DL;
步骤24：不满足循环条件：不满足T＞0，返回增加链路集合DL＝{(a,b),(c,d)}；Step 24: The loop condition is not satisfied: T＞0 is not satisfied, and the link set DL＝{(a,b),(c,d)} is added.
步骤25：根据新增链路集合AL和删除链路集合DL中的链路更新拓扑G′拓扑G′如图四右边拓扑结构，其中虚线为删除边，粗实线为新增边；Step 25: Update the topology G′ according to the links in the newly added link set AL and the deleted link set DL. The topology G′ is shown in the topology structure on the right side of Figure 4, where the dotted lines are deleted edges and the thick solid lines are added edges;
步骤26：计算新拓扑的每一个节点对之间的最短路径即备份路径SP＝{(a,c,b),(a,c),(a,d),(b,c),(b,d),(c,b,d)}。Step 26: Calculate the shortest path between each node pair of the new topology, i.e., the backup path SP = {(a,c,b),(a,c),(a,d),(b,c),(b,d),(c,b,d)}.
本发明提供了一种基于优化网络拓扑结构的路由保护方法，解决了已有的路由保护方案为了提高路由可用性而增加大量网络开销，导致无法在实际网络中部署的问题。本发明利用优化后的网络拓扑结构为所有的源目的对计算一条与最短路径具有最小路径重合度的备份路径。本发明提出的方案有效降低了最短路径和备份路径的路径重合度，极大地提高了路由可用性。因此本发明是一种可以基于优化网络拓扑结构的路由保护方法。The present invention provides a routing protection method based on an optimized network topology structure, which solves the problem that the existing routing protection scheme increases a large amount of network overhead in order to improve routing availability, resulting in the inability to be deployed in an actual network. The present invention uses the optimized network topology structure to calculate a backup path with the minimum path overlap with the shortest path for all source-destination pairs. The scheme proposed by the present invention effectively reduces the path overlap between the shortest path and the backup path, greatly improving routing availability. Therefore, the present invention is a routing protection method that can be based on an optimized network topology structure.
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit it. Although the present invention has been described in detail with reference to the aforementioned embodiments, those skilled in the art should understand that they can still modify the technical solutions described in the aforementioned embodiments, or replace some or all of the technical features therein by equivalents. However, these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the scope of the technical solutions of the embodiments of the present invention.
Claims (10)
Translated fromChinese
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210197631.1ACN114726772B (en) | 2022-03-02 | 2022-03-02 | Route protection method based on optimized network topology structure |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210197631.1ACN114726772B (en) | 2022-03-02 | 2022-03-02 | Route protection method based on optimized network topology structure |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114726772A CN114726772A (en) | 2022-07-08 |
| CN114726772Btrue CN114726772B (en) | 2023-03-24 |
Family
ID=82235303
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210197631.1AActiveCN114726772B (en) | 2022-03-02 | 2022-03-02 | Route protection method based on optimized network topology structure |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114726772B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115987870B (en)* | 2022-12-09 | 2024-05-28 | 山西大学 | A green routing energy-saving method for the Internet based on link correlation |
| CN116319512B (en)* | 2023-02-16 | 2024-04-12 | 山西大学 | Intra-domain route protection method based on node reverse order relation |
| CN116319537B (en)* | 2023-03-30 | 2024-04-12 | 山西大学 | A method for calculating routing availability based on node sequence |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105634938A (en)* | 2014-11-30 | 2016-06-01 | 中国科学院沈阳自动化研究所 | Data double-path backup transmission method for software-defined network |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007140843A (en)* | 2005-11-17 | 2007-06-07 | Fuji Xerox Co Ltd | Link relationship display, control method for link relationship display, and program |
| CN101562556B (en)* | 2008-04-15 | 2011-08-03 | 华为技术有限公司 | A method, device and system for reducing the cost of network coding |
| JP5771832B2 (en)* | 2012-02-14 | 2015-09-02 | 株式会社日立製作所 | Transmission system, management computer, and logical path construction method |
| CN104202176B (en)* | 2014-07-15 | 2018-08-10 | 华信咨询设计研究院有限公司 | Optical-fiber network topology computer method for auto constructing |
| EP3759966A1 (en)* | 2018-03-28 | 2021-01-06 | Sony Corporation | Methods, wireless communications networks and infrastructure equipment |
- 2022
- 2022-03-02CNCN202210197631.1Apatent/CN114726772B/enactiveActive
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105634938A (en)* | 2014-11-30 | 2016-06-01 | 中国科学院沈阳自动化研究所 | Data double-path backup transmission method for software-defined network |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114726772A (en) | 2022-07-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN114726772B (en) | Route protection method based on optimized network topology structure | |
| EP3732894B1 (en) | Interior gateway protocol flood minimization | |
| Labovitz et al. | Delayed Internet routing convergence | |
| JP2014534776A (en) | IP fast reroute scheme providing full range of protection | |
| CN113261245A (en) | Recovery system and method for network link or node failure | |
| CN102197625A (en) | Provider link state bridging (PLSB) computation method | |
| CN115065634B (en) | Loop-free efficient route protection method based on DC rule | |
| CN107248954B (en) | An intra-domain routing protection method based on network intersection degree | |
| CN116648893A (en) | Bit Index Explicit Copy Traffic Engineering Egress Protection | |
| JP4128944B2 (en) | Multicast transfer route setting method, multicast transfer route calculation device, program, and recording medium | |
| CN108429688B (en) | A single-node fault routing protection method based on segment routing | |
| CN111277495B (en) | Method for presetting fault protection path of bit index display copy multicast | |
| JP4373929B2 (en) | Path route calculation method, path route calculation device, and communication system | |
| WO2005015834A1 (en) | A method of automatic protection switching | |
| CN107453990A (en) | A kind of intra-area routes guard method based on key node | |
| CN115766573B (en) | A routing protection method with high fault protection rate based on SDN | |
| CN114745320B (en) | Route protection method for single fault situation | |
| US11811611B2 (en) | System and method for backup flooding topology split | |
| CN116319537B (en) | A method for calculating routing availability based on node sequence | |
| CN116633851A (en) | Single link fault route protection method based on reconstructed SPT | |
| CN114827010A (en) | Intra-domain route protection method based on node forwarding probability | |
| JP4128937B2 (en) | Multicast transfer route setting method, multicast transfer route calculation device, program, and recording medium | |
| Fransson et al. | Loop-free link-state routing | |
| CN118175086A (en) | A method for fast recovery mechanism of path selection based on multi-objectives | |
| CN119697531A (en) | A SPOTN network tunnel rerouting method |
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 |