CN117978320A - Method and system for solving shortest disjoint path pair in WDM network - Google Patents
Method and system for solving shortest disjoint path pair in WDM network Download PDFInfo
- Publication number
- CN117978320A CN117978320A CN202410209908.7A CN202410209908A CN117978320A CN 117978320 A CN117978320 A CN 117978320A CN 202410209908 A CN202410209908 A CN 202410209908A CN 117978320 A CN117978320 A CN 117978320A
- Authority
- CN
- China
- Prior art keywords
- shortest
- node
- path
- pair
- disjoint
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 48
- 238000004891 communication Methods 0.000 description 5
- 230000006870 function Effects 0.000 description 4
- 238000010586 diagram Methods 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 230000003287 optical effect Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 239000000835 fiber Substances 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J14/00—Optical multiplex systems
- H04J14/02—Wavelength-division multiplex systems
- H04J14/0227—Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
- H04J14/0254—Optical medium access
- H04J14/0267—Optical signaling or 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/12—Shortest path evaluation
- H04L45/126—Shortest path evaluation minimising geographical or physical path length
-
- 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
- H04L45/128—Shortest path evaluation for finding disjoint paths
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
A method and system for solving shortest disjoint path pair in WDM network, belonging to network planning field, comprising constructing undirected weighted graph of WDM network and obtaining first shortest path; the weight and the direction of all edges on the path are reversed, and the first node is split into a pair of in nodes and out nodes which are sequentially arranged along the path direction; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node; acquiring a second shortest path again; and comparing the two shortest paths, and removing the edges with opposite weights and directions to obtain the shortest disjoint path pair. The application adopts a mode of searching the path pair by pair instead of searching the path by path pair, thereby improving the success rate of the service and the utilization rate of the network topology.
Description
Technical Field
The application relates to the field of network planning, in particular to a method and a system for solving shortest disjoint path pairs in a WDM (WAVELENGTH DIVISION MULTIPLEXING ) network.
Background
In network planning, in order to ensure service transmission, the service often adopts a concurrent selection and reception strategy, and when the service is planned, reasonable planning is required to be carried out on the transmission paths of the service, a plurality of disjoint paths are searched in network topology, and topology resources are fully utilized.
In general, the shortest path can be searched by adopting the traditional path-finding algorithm, and after the path is rejected, the path is continuously searched for the secondary path, so that the purpose of searching for a plurality of disjoint paths is achieved.
The traditional path-finding algorithm can generally give the global shortest path and the global secondary path, but the total length of the pair of disjoint paths does not necessarily meet the shortest condition, and under partial scenes, the situation that a plurality of pairs of disjoint paths cannot be obtained possibly exists, so that topology resources are not fully utilized, and path planning is not reasonable enough.
Disclosure of Invention
The application provides a method and a system for solving the shortest disjoint path pair in a WDM network, which can solve the technical problems that the traditional path searching algorithm in the prior art can only search paths one by one, so that the utilization of topology resources is insufficient and the path planning is unreasonable.
In a first aspect, an embodiment of the present application provides a method for solving a shortest disjoint path pair in a WDM network, where the method for solving the shortest disjoint path pair in the WDM network includes:
Constructing an undirected weighted graph of the WDM network and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
when any intermediate node has a connection relation with a side branch node outside the first shortest path, the intermediate node is defined as a first node, and the corresponding side branch node is defined as a second node;
After the weights and the directions of all edges on the first shortest path are reversed, all the first nodes are split into a pair of in nodes and out nodes which are sequentially arranged along the path direction; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node so as to obtain an updated weighted graph and obtain a second shortest path;
And comparing the two shortest paths, and removing the edges with opposite weights and directions to obtain a shortest disjoint path pair.
With reference to the first aspect, in an embodiment, the method further includes:
and after each shortest disjoint path pair is obtained, shielding the found shortest disjoint path pair in the undirected weighted graph, and searching the shortest disjoint path pair again.
With reference to the first aspect, in an implementation manner, the comparing the two shortest paths specifically includes the following steps:
And combining each pair of in nodes and out nodes on the second shortest path into an intermediate node, and comparing the weight and the direction of edges between all adjacent two intermediate nodes in the two shortest paths.
With reference to the first aspect, in one implementation manner, the removing the edges with opposite weights and directions, to obtain a shortest disjoint path pair, specifically includes the following steps:
and removing the edges with opposite weights and directions in the second shortest path by combining the first shortest path to obtain a shortest disjoint path pair.
In a second aspect, an embodiment of the present application provides a system for finding a shortest disjoint path pair in a WDM network, where the system for finding a shortest disjoint path pair in a WDM network includes:
the first path finding module is used for constructing an undirected weighted graph of the wavelength division multiplexing WDM network and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
The second path finding module is used for defining any intermediate node as a first node and defining a corresponding side branch node as a second node when the intermediate node and the side branch node outside the first shortest path have a connection relation; the method is also used for splitting all the first nodes into a pair of in nodes and out nodes which are sequentially arranged along the path direction after the weights and the directions of all the edges on the first shortest path are reversed; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node so as to obtain an updated weighted graph and obtain a second shortest path;
and the third path searching module is used for comparing the two shortest paths so as to remove the edges with opposite weight and direction and obtain a shortest disjoint path pair.
With reference to the second aspect, in one embodiment, the system for finding the shortest disjoint path pair in the WDM network further includes:
And the control module is used for shielding the searched shortest disjoint path pair in the WDM network after the third path searching module obtains the shortest disjoint path pair, and controlling the three path searching modules to search the shortest disjoint path pair again.
With reference to the second aspect, in one implementation manner, when the third routing module compares the two shortest paths, each pair of in nodes and out nodes on the second shortest path are combined into an intermediate node, and weights and directions of edges between all adjacent two intermediate nodes in the two shortest paths are compared.
In combination with the second aspect, in one implementation manner, the third routing module removes edges with opposite weights and opposite directions to obtain a shortest disjoint path pair, and removes edges with opposite weights and opposite directions in the second shortest path in combination with the first shortest path to obtain a shortest disjoint path pair.
In a third aspect, an embodiment of the present application provides an apparatus for solving a shortest disjoint path pair in a WDM network, where the apparatus for solving a shortest disjoint path pair in a WDM network includes a processor, a memory, and a program for solving a shortest disjoint path pair in a WDM network stored on the memory and executable by the processor, where the program for solving a shortest disjoint path pair in the WDM network implements the steps of the method for solving a shortest disjoint path pair in the WDM network when executed by the processor.
In a fourth aspect, an embodiment of the present application provides a computer readable storage medium, where a program for finding a shortest disjoint path pair in a WDM network is stored, where the program for finding a shortest disjoint path pair in the WDM network, when executed by a processor, implements the steps of the method for finding a shortest disjoint path pair in the WDM network.
The technical scheme provided by the embodiment of the application has the beneficial effects that:
the search result of the traditional path finding algorithm is improved, and for searching of disjoint path pairs, the success rate of searching of the disjoint path pairs is improved by adopting a mode of searching the paths pair by pair instead of searching the paths pair by pair, so that the success rate of service and the utilization rate of network topology are improved.
Drawings
FIG. 1 is a flow chart of one embodiment of a method for finding shortest disjoint pairs in a WDM network in accordance with the present application;
FIGS. 2-6 are flow diagrams of one embodiment of a method for finding shortest disjoint pairs in a WDM network according to the present application;
FIG. 7 is a schematic diagram of functional blocks of an embodiment of a system for shortest disjoint path pairs in a WDM network in accordance with the present application;
fig. 8 is a schematic hardware structure of an apparatus for finding a shortest disjoint path pair in a WDM network according to an embodiment of the present application.
Detailed Description
In order that those skilled in the art will better understand the present application, a technical solution in the embodiments of the present application will be clearly and completely described below with reference to the accompanying drawings in which it is apparent that the described embodiments are only some embodiments of the present application, not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the application without making any inventive effort, are intended to be within the scope of the application.
First, some technical terms in the present application are explained so as to facilitate understanding of the present application by those skilled in the art.
For the purpose of making the objects, technical solutions and advantages of the present application more apparent, the embodiments of the present application will be described in further detail with reference to the accompanying drawings.
In a first aspect, an embodiment of the present application provides a method for finding a shortest disjoint path pair in a WDM network.
In one embodiment, referring to fig. 1, fig. 1 is a flowchart illustrating an embodiment of a method for finding shortest disjoint pairs in a WDM network according to the present application. As shown in fig. 1, the method for finding the shortest disjoint path pair in the WDM network includes:
s1, constructing an undirected weighted graph of a wavelength division multiplexing WDM network, and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
step S2, when any intermediate node has a connection relationship with a side branch node outside the first shortest path, defining the intermediate node as a first node, and defining a corresponding side branch node as a second node;
S3, after the weights and the directions of all edges on the first shortest path are reversed, all the first nodes are split into a pair of in nodes and out nodes which are sequentially arranged along the path direction; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes;
s4, splitting edges between the second nodes and the corresponding first nodes into first edges and second edges with unchanged weights, wherein the first edges point to the in nodes from the second nodes, and the second edges point to the second nodes from the out nodes so as to obtain updated weight graphs and obtain second shortest paths;
and S5, comparing the two shortest paths to remove edges with opposite weights and directions, and obtaining a shortest disjoint path pair.
In this embodiment, the search result of the conventional path-finding algorithm is improved, for searching of the disjoint path pairs, by adopting a mode of searching the paths pair by pair instead of searching the paths pair by pair, the success rate of searching of the disjoint path pairs is improved, two shortest paths can be searched at a time, the search efficiency is improved, meanwhile, each of the two shortest paths is slightly longer than a single shortest path obtained by searching in a single search by the conventional path-finding algorithm, the path lengths of the two shortest paths are shorter than those of the two shortest paths obtained by searching in two searches by the conventional path-finding algorithm, and by balancing two factors of the path lengths and the path number, the path planning is more reasonable, the topology resource is utilized more fully, the situation that the disjoint path pairs cannot be obtained by adopting the conventional path-finding algorithm can be solved, and the success rate of the service is improved from all the above aspects.
Further, in an embodiment, the method further comprises:
after each shortest disjoint path pair is obtained, the found shortest disjoint path pair is shielded in the WDM network, and the shortest disjoint path pair is found again.
In this embodiment, after a pair of shortest disjoint path pairs is obtained by searching each time, the pair of paths is shielded, and the path searching process of the shortest disjoint path pairs is repeated again until a plurality of pairs of shortest disjoint path pairs are obtained, so as to improve the success rate of the service and the utilization rate of the network topology.
In a specific embodiment, first, given an undirected weighted (weighted positive) graph, a Dijkstra algorithm or other shortest path finding algorithm is used to find a shortest path i from a source node to a destination node in the graph.
Then, a new graph is constructed. Specifically, the weight of the edge passing through by the shortest path I is taken as the opposite number, the direction is from the destination node to the source node, the original source node on the shortest path I becomes the destination node, and the destination node becomes the source node. Dividing the intermediate nodes (i.e. nodes except the source and destination nodes) on the shortest path I into an in node and an out node, adding an edge with the weight value of 0 pointing to the out node from the in node into the same intermediate node, adding an edge which keeps the same weight value as the splitting weight value before splitting and points to the in from the out node between adjacent intermediate nodes, splitting only the intermediate nodes with connection relation with the side support nodes outside the first shortest path during splitting, and splitting all the intermediate nodes, wherein the two splitting modes can be selected according to actual requirements without influencing the final path finding result. Dividing other undirected edges which are not on the shortest path I and are connected with the middle point in the step (2) into two directed edges, taking the weight of the edges, wherein the directions are respectively from an out node to the other end of the edge and from the other end of the edge to an in node.
In the new graph, the Dijkstra algorithm is used again to find a shortest path ii from the source node to the sink node in the graph.
Comparing the shortest path I with the shortest path II, removing the overlapped edges (namely the edges with opposite weights and directions) passing through the shortest path I and the shortest path II, and combining to obtain two new paths.
The two paths obtained at this time are disjoint and the sum of their weights is the smallest, being the first pair of shortest disjoint paths.
Forbidden the edge passed by the first pair of shortest paths in the original graph, and repeating the path searching step to obtain a second pair of shortest disjoint paths
The edges of the first two pairs of shortest paths are forbidden in the original graph, and the path searching step is repeated to obtain a third pair of shortest disjoint paths
Sequentially iterating, prohibiting the edges of the front k-1 pair of disjoint shortest paths from passing through in the original graph, and repeating the path searching step to obtain the kth pair of disjoint shortest paths, wherein k is a positive integer not less than 2.
In summary, aiming at disjoint path searching among a plurality of band protection services, based on the improvement of the traditional path searching algorithm, a mode of searching the disjoint paths pair by pair instead of searching the disjoint paths pair by pair is adopted for searching the disjoint paths, so that the success rate of the disjoint path searching is improved, the shortest path combination of the disjoint paths pair in the topology can be searched in part of special scenes, the disjoint path pair in the topology can be found to the maximum extent, the problem of incomplete path searching is solved, and the utilization rate of topology resources is improved.
Further, in an embodiment, the comparing the two shortest paths specifically includes the following steps:
And combining each pair of in nodes and out nodes on the second shortest path into an intermediate node, and comparing the weight and the direction of edges between all adjacent two intermediate nodes in the two shortest paths.
In this embodiment, when splitting the node to be split into the in node and the out node, an edge with a weight of 0 is configured between the in node and the out node corresponding to the same node to be split, and the weight of the edge between the adjacent node to be split and the intermediate node (the intermediate node may be a common intermediate node having no connection relationship with a side node outside the first shortest path or may be a node to be split having a connection relationship with a side node outside the first shortest path) is unchanged, so that each pair of the in node and the out node may be combined to be regarded as an intermediate node when comparing the first shortest path with the second shortest path in the later stage.
Further, in an embodiment, the step of removing the edges with opposite weights and opposite directions to obtain a shortest disjoint path pair includes the following steps:
and removing the edges with opposite weights and directions in the second shortest path by combining the first shortest path to obtain a shortest disjoint path pair.
In this embodiment, after each pair of in node and out node on the second shortest path is regarded as one intermediate node, if the weight and direction of the edge between two adjacent intermediate nodes on the second shortest path are opposite to those of the edge between two adjacent intermediate nodes on the first shortest path, the edge is removed on the second shortest path, and finally a shortest disjoint path pair can be obtained.
In one implementation, given an undirected weighted (weighted positive) graph as shown in fig. 2, all circles filled with english letters in the graph are nodes. The Dijkstra algorithm is used to find a shortest path i from the source node to the sink node in fig. 2, namely: s- & gt a- & gt b- & gt c- & gt t, wherein the single path is the global shortest path.
Firstly, the weight of the edge passing through by the shortest path I is taken as the opposite number, the direction points to the original point from the destination point in sequence, namely, the undirected edge in the original image is replaced to be the directed edge (t-c-b-a-s, and the weight of each edge is-1).
When any intermediate node has a connection relationship with a side branch node outside the first shortest path, the intermediate node is defined as a first node, and the corresponding side branch node is defined as a second node. In other embodiments, if no connection exists between the intermediate node and the side branch node, a conventional path-finding algorithm is subsequently used for path finding.
As shown in fig. 3, the first node on the shortest path I is divided into two nodes in and out, an edge pointing from the in node to the out node is added in the middle node, the weight of the edge is 0, and edges with unchanged weight and direction are added between the middle nodes. Other intermediate nodes except the first node can be split into two nodes in and out, the two splitting methods are adjusted according to actual scenes and requirements, the final path finding result is not affected, for convenience of explanation, all the intermediate nodes are split as examples, namely, three points a, b and c in fig. 2 are replaced by a in→aout、bin→bout、cin→cout respectively, other undirected edges which are not on the shortest path I and are connected with the points a, b and c in fig. 2 are split into two directed edges, the weight values of the edges are taken, and the directions are respectively as follows: g- > a in、aout→g;f→cin、cout - > f.
As shown in fig. 4, in the new fig. 3, the Dijkstra algorithm is used again to find a shortest path ii from the source to the sink in the figure, i.e. s→d→e→f→c in→cout→bin→bout→ain→aout →g→h→i→t.
As shown in fig. 5, the directional paths i and ii are compared, and the sides of the two paths with opposite weights and opposite directions, i.e., the sides between a and b, and between b and c in the figure, are removed.
As shown in fig. 6, the processed paths I and ii are finally recombined to obtain a pair of shortest disjoint paths: s- & gt d- & gt e- & gt f- & gt c- & gt t and s- & gt a- & gt g- & gt h- & gt i- & gt t.
In fig. 6, the edge passing by the first pair of shortest paths is forbidden, a Dijkstra algorithm is used to find a shortest path III (s- > m- > p- > l- > t) and a shortest path IV (s- > j- > k- > l- > p- > m- > n- > o- > t) from the source node to the destination node before and after the re-composition, paths III and IV are compared, paths with the same weight and opposite directions in the two paths are removed, namely paths between m and p, p and l in the graph, and finally new directed edges are re-combined to obtain a second pair of shortest disjoint paths: s- & gt j- & gt k- & gt l- & gt t and s- & gt m- & gt n- & gt o- & gt t.
Further disable the edges traversed by the first two pairs of shortest paths in fig. 6, and according to the same idea, obtain a third pair of shortest disjoint shortest paths: s- & gt w- & gt x- & gt y- & gt z- & gt t and s- & gt q- & gt r- & gt u- & gt v- & gt t.
So far, all three pairs of shortest disjoint paths in the original network topology are obtained, and route paths can be distributed for three 1+1 mutually exclusive group services.
In a second aspect, the embodiment of the application also provides a system for solving the shortest disjoint path pair in the WDM network.
In one embodiment, referring to fig. 7, fig. 7 is a schematic functional block diagram of an embodiment of a system for finding shortest disjoint pairs in a WDM network according to the present application. As shown in fig. 7, the system for finding the shortest disjoint path pair in the WDM network includes:
the first path finding module is used for constructing an undirected weighted graph of the wavelength division multiplexing WDM network and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
The second path finding module is used for defining any intermediate node as a first node and defining a corresponding side branch node as a second node when the intermediate node and the side branch node outside the first shortest path have a connection relation; the method is also used for splitting all the first nodes into a pair of in nodes and out nodes which are sequentially arranged along the path direction after the weights and the directions of all the edges on the first shortest path are reversed; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node so as to obtain an updated weighted graph and obtain a second shortest path;
and the third path searching module is used for comparing the two shortest paths so as to remove the edges with opposite weight and direction and obtain a shortest disjoint path pair.
In this embodiment, the search result of the conventional path-finding algorithm is improved, for searching of the disjoint path pairs, by adopting a mode of searching the paths pair by pair instead of searching the paths pair by pair, the success rate of searching of the disjoint path pairs is improved, two shortest paths can be searched at a time, the search efficiency is improved, meanwhile, each of the two shortest paths is slightly longer than a single shortest path obtained by searching in a single search by the conventional path-finding algorithm, the path lengths of the two shortest paths are shorter than those of the two shortest paths obtained by searching in two searches by the conventional path-finding algorithm, and by balancing two factors of the path lengths and the path number, the path planning is more reasonable, the topology resource is utilized more fully, the situation that the disjoint path pairs cannot be obtained by adopting the conventional path-finding algorithm can be solved, and the success rate of the service is improved from all the above aspects.
The function implementation of each module in the system for solving the shortest disjoint path pair in the WDM network corresponds to each step in the method embodiment for solving the shortest disjoint path pair in the WDM network, and the function and implementation process of the function implementation are not described in detail herein.
In a third aspect, an embodiment of the present application provides a device for obtaining a shortest disjoint path pair in a WDM network, where the device for obtaining a shortest disjoint path pair in the WDM network may be a device with a data processing function, such as a personal computer (personal computer, PC), a notebook computer, or a server.
Referring to fig. 8, fig. 8 is a schematic hardware structure of an apparatus for finding a shortest disjoint path pair in a WDM network according to an embodiment of the present application. In an embodiment of the present application, a device for finding a shortest disjoint path pair in a WDM network may include a processor, a memory, a communication interface, and a communication bus.
The communication bus may be of any type for implementing the processor, memory, and communication interface interconnections.
The communication interfaces include input/output (I/O) interfaces, physical interfaces, logical interfaces, and the like for implementing device interconnections within the devices that find the shortest disjoint path pairs in the WDM network, and interfaces for implementing the interconnection of the devices that find the shortest disjoint path pairs in the WDM network with other devices (e.g., other computing devices or user devices). The physical interface may be an ethernet interface, a fiber optic interface, an ATM interface, etc.; the user device may be a Display, a Keyboard (Keyboard), or the like.
The memory may be various types of storage media such as random access memory (randomaccess memory, RAM), read-only memory (ROM), nonvolatile RAM (non-volatileRAM, NVRAM), flash memory, optical memory, hard disk, programmable ROM (PROM), erasable PROM (erasable PROM, EPROM), electrically erasable PROM (ELECTRICALLY ERASABLE PROM, EEPROM), and the like.
The processor may be a general-purpose processor, and the general-purpose processor may call a program for finding a shortest disjoint path pair in the WDM network stored in the memory, and execute the method for finding a shortest disjoint path pair in the WDM network provided by the embodiment of the present application. For example, the general purpose processor may be a central processing unit (central processing unit, CPU). The method for performing the procedure for finding the shortest disjoint path pair in the WDM network when the procedure for finding the shortest disjoint path pair in the WDM network is called out can refer to various embodiments of the method for finding the shortest disjoint path pair in the WDM network of the present application, which are not described herein.
Those skilled in the art will appreciate that the hardware configuration shown in fig. 8 is not limiting of the application and may include more or fewer components than shown, or may combine certain components, or a different arrangement of components.
In a fourth aspect, embodiments of the present application also provide a readable storage medium.
The readable storage medium of the present application stores thereon a program for finding a shortest disjoint path pair in a WDM network, wherein the program for finding a shortest disjoint path pair in the WDM network, when executed by a processor, implements the steps of the method for finding a shortest disjoint path pair in a WDM network as described above.
The method implemented when the program for finding the shortest disjoint path pair in the WDM network is executed may refer to various embodiments of the method for finding the shortest disjoint path pair in the WDM network of the present application, which are not described herein.
It should be noted that, the foregoing reference numerals of the embodiments of the present application are merely for describing the embodiments, and do not represent the advantages and disadvantages of the embodiments.
From the above description of the embodiments, it will be clear to those skilled in the art that the above-described embodiment method may be implemented by means of software plus a necessary general hardware platform, but of course may also be implemented by means of hardware, but in many cases the former is a preferred embodiment. Based on such understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art in the form of a software product stored in a storage medium (e.g. ROM/RAM, magnetic disk, optical disk) as described above, comprising several instructions for causing a terminal device to perform the method according to the embodiments of the present application.
The terms "comprising" and "having" and any variations thereof in the description and claims of the application and in the foregoing drawings are intended to cover non-exclusive inclusions. For example, a process, method, system, article, or apparatus that comprises a list of steps or elements is not limited to only those listed steps or elements but may include other steps or elements not listed or inherent to such process, method, article, or apparatus. The terms "first," "second," and "third," etc. are used for distinguishing between different objects and not necessarily for describing a sequential or chronological order, and are not limited to the fact that "first," "second," and "third" are not identical.
In describing embodiments of the present application, "exemplary," "such as," or "for example," etc., are used to indicate by way of example, illustration, or description. Any embodiment or design described herein as "exemplary," "such as" or "for example" is not necessarily to be construed as preferred or advantageous over other embodiments or designs. Rather, the use of words such as "exemplary," "such as" or "for example," etc., is intended to present related concepts in a concrete fashion.
In the description of the embodiments of the present application, unless otherwise indicated, "/" means or, for example, a/B may represent a or B; the text "and/or" is merely an association relation describing the associated object, and indicates that three relations may exist, for example, a and/or B may indicate: the three cases where a exists alone, a and B exist together, and B exists alone, and furthermore, in the description of the embodiments of the present application, "plural" means two or more than two.
In some of the processes described in the embodiments of the present application, a plurality of operations or steps occurring in a particular order are included, but it should be understood that the operations or steps may be performed out of the order in which they occur in the embodiments of the present application or in parallel, the sequence numbers of the operations merely serve to distinguish between the various operations, and the sequence numbers themselves do not represent any order of execution. In addition, the processes may include more or fewer operations, and the operations or steps may be performed in sequence or in parallel, and the operations or steps may be combined.
The foregoing description is only of the preferred embodiments of the present application, and is not intended to limit the scope of the application, but rather is intended to cover any equivalents of the structures or equivalent processes disclosed herein or in the alternative, which may be employed directly or indirectly in other related arts.
Claims (10)
1. A method for finding a shortest disjoint path pair in a WDM network, the method comprising:
Constructing an undirected weighted graph of the WDM network and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
when any intermediate node has a connection relation with a side branch node outside the first shortest path, the intermediate node is defined as a first node, and the corresponding side branch node is defined as a second node;
After the weights and the directions of all edges on the first shortest path are reversed, all the first nodes are split into a pair of in nodes and out nodes which are sequentially arranged along the path direction; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node so as to obtain an updated weighted graph and obtain a second shortest path;
And comparing the two shortest paths, and removing the edges with opposite weights and directions to obtain a shortest disjoint path pair.
2. A method of finding a shortest disjoint pair of paths in a WDM network as claimed in claim 1, said method further comprising:
and after each shortest disjoint path pair is obtained, shielding the found shortest disjoint path pair in the undirected weighted graph, and searching the shortest disjoint path pair again.
3. A method for finding a shortest disjoint pair of paths in a WDM network according to claim 1, wherein said comparing said two shortest paths comprises the steps of:
And combining each pair of in nodes and out nodes on the second shortest path into an intermediate node, and comparing the weight and the direction of edges between all adjacent two intermediate nodes in the two shortest paths.
4. A method for finding a shortest disjoint path pair in a WDM network according to claim 3, wherein said removing edges having opposite weights and directions results in a shortest disjoint path pair comprising the steps of:
and removing the edges with opposite weights and directions in the second shortest path by combining the first shortest path to obtain a shortest disjoint path pair.
5. A system for shortest disjoint path pairs in a WDM network, comprising:
the first path finding module is used for constructing an undirected weighted graph of the wavelength division multiplexing WDM network and acquiring a first shortest path; the first shortest path comprises a source node, an intermediate node and a sink node;
The second path finding module is used for defining any intermediate node as a first node and defining a corresponding side branch node as a second node when the intermediate node and the side branch node outside the first shortest path have a connection relation; the method is also used for splitting all the first nodes into a pair of in nodes and out nodes which are sequentially arranged along the path direction after the weights and the directions of all the edges on the first shortest path are reversed; adding an edge with a weight value of 0 from an in node to an out node in the same first node, and adding an edge with a constant weight value and direction between adjacent first nodes; splitting an edge between a second node and a corresponding first node into a first edge and a second edge with unchanged weight, wherein the first edge points to an in node from the second node, and the second edge points to the second node from an out node so as to obtain an updated weighted graph and obtain a second shortest path;
and the third path searching module is used for comparing the two shortest paths so as to remove the edges with opposite weight and direction and obtain a shortest disjoint path pair.
6. A system for shortest disjoint pairs of paths in a WDM network according to claim 5, further comprising:
And the control module is used for shielding the searched shortest disjoint path pair in the WDM network after the third path searching module obtains the shortest disjoint path pair, and controlling the three path searching modules to search the shortest disjoint path pair again.
7. A system for finding pairs of shortest disjoint paths in a WDM network according to claim 5, wherein said third routing module combines each pair of in-nodes and out-nodes on the second shortest path into an intermediate node when comparing said two shortest paths, and compares the weights and directions of edges between all adjacent two intermediate nodes in said two shortest paths.
8. The system for finding a shortest disjoint path pair in a WDM network of claim 7, wherein said third routing module removes edges having opposite weights and directions to obtain a shortest disjoint path pair, and removes edges having opposite weights and directions in a second shortest path in combination with the first shortest path to obtain a shortest disjoint path pair.
9. An apparatus for shortest disjoint path pair in a WDM network, characterized in that the apparatus for shortest disjoint path pair in a WDM network comprises a processor, a memory, and a program for shortest disjoint path pair in a WDM network stored on the memory and executable by the processor, wherein the program for shortest disjoint path pair in a WDM network implements the steps of the method for shortest disjoint path pair in a WDM network according to any one of claims 1 to 4 when executed by the processor.
10. A computer readable storage medium, wherein a program for finding the shortest disjoint path pair in a WDM network is stored on the computer readable storage medium, wherein the program for finding the shortest disjoint path pair in the WDM network, when executed by a processor, implements the steps of the method for finding the shortest disjoint path pair in a WDM network as claimed in any one of claims 1 to 4.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410209908.7A CN117978320A (en) | 2024-02-26 | 2024-02-26 | Method and system for solving shortest disjoint path pair in WDM network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410209908.7A CN117978320A (en) | 2024-02-26 | 2024-02-26 | Method and system for solving shortest disjoint path pair in WDM network |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN117978320A true CN117978320A (en) | 2024-05-03 |
Family
ID=90845682
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410209908.7A Pending CN117978320A (en) | 2024-02-26 | 2024-02-26 | Method and system for solving shortest disjoint path pair in WDM network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117978320A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118409862A (en) * | 2024-05-09 | 2024-07-30 | 苏州工业园区服务外包职业学院(苏州市服务外包人才培养实训中心) | Method, device and equipment for constructing one-to-many disjoint paths of partition exchange graph |
-
2024
- 2024-02-26 CN CN202410209908.7A patent/CN117978320A/en active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118409862A (en) * | 2024-05-09 | 2024-07-30 | 苏州工业园区服务外包职业学院(苏州市服务外包人才培养实训中心) | Method, device and equipment for constructing one-to-many disjoint paths of partition exchange graph |
| CN118409862B (en) * | 2024-05-09 | 2025-02-11 | 苏州工业园区服务外包职业学院(苏州市服务外包人才培养实训中心) | Method, device and equipment for constructing one-to-many disjoint paths of partition exchange graph |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zhang et al. | Enhancing network robustness via shielding | |
| Becker et al. | Near-optimal approximate shortest paths and transshipment in distributed and streaming models | |
| Clímaco et al. | Multicriteria path and tree problems: discussion on exact algorithms and applications | |
| Hochbaum et al. | Simplifications and speedups of the pseudoflow algorithm | |
| Feldmann et al. | Fast hybrid network algorithms for shortest paths in sparse graphs | |
| Duarte et al. | Improved heuristics for the regenerator location problem | |
| US8843902B2 (en) | Program flow route constructor | |
| Vasko et al. | A simple methodology that efficiently generates all optimal spanning trees for the cable-trench problem | |
| CN117978320A (en) | Method and system for solving shortest disjoint path pair in WDM network | |
| Housni | An efficient algorithm for enumerating all minimal paths of a graph | |
| Lopez-Pajares et al. | The disjoint multipath challenge: Multiple disjoint paths guaranteeing scalability | |
| CN114298431A (en) | A network path selection method, device, device and storage medium | |
| Chen et al. | Polynomial-time data reduction for the subset interconnection design problem | |
| Mumey et al. | Parity balancing path flow decomposition and routing | |
| Cruz et al. | A heuristic for widest edge-disjoint path pair lexicographic optimization | |
| Gomes et al. | Protected shortest path visiting specified nodes | |
| US8881117B2 (en) | Structural analyser | |
| D’Andrea et al. | Dynamically maintaining shortest path trees under batches of updates | |
| CN115134293B (en) | Telecommunication route recommendation method, device and server | |
| Zhang et al. | Computing bipath multicommodity flows with constraint programming–based branch-and-price-and-cut | |
| JP7400833B2 (en) | Topology design device, topology design method, and program | |
| Migov | Parallel methods for network reliability calculation and cumulative updating of network reliability bounds | |
| Cheng et al. | Efficient survivable mapping algorithm for logical topology in IP-over-WDM optical networks against node failure | |
| Bökler et al. | Exact minimum weight spanners via column generation | |
| Baskakov et al. | Modeling of the Multiple Paths Finding Algorithm for Software-Defined Network |
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 |