Shortest path routing systems and methods for networks with non-fully meshed vertices
Shortest path routing systems and methods are presented for networks with non-fully meshed vertices or nodes. The systems and methods may include a shortest path routing method in a network with non-fully meshed vertices, a network with non-fully meshed vertices, and a system for implementing the shortest path routing methods. The shortest path routing systems and methods include modifications to the Dijkstra algorithm to more accurately model a network, such as an optical or photonic network. In an exemplary embodiment, the Dijkstra algorithm is modified to represent degrees at a site with an ingress vertex (e.g., a demultiplexer) and an egress vertex (e.g., a multiplexer). In another exemplary embodiment, in addition to representing degrees as ingress and egress vertices, the Dijkstra algorithm is modified to maintain knowledge of previously visited degrees to prevent revisiting a same degree in determining a shortest path.
1. A shortest path routing method in a network with non-fully meshed vertices, comprising:
using a controller coupled to a plurality of interconnected network elements, the controller configured to perform steps of;
defining vertices for each degree in the network at each node in the network, the vertices at each degree comprising an ingress vertex and an egress vertex, wherein at least one node in the network comprises degrees which are not fully-meshed internally such that some of the degrees are not connected to one another directly internally at the at least one node and have no interconnectivity for signals between them; and
implementing a Dijkstra algorithm in a constrained manner to determine a shortest, bidirectional path through the network between two degrees in the network;
wherein each degree in the network, except for the degrees which are not fully-meshed, is configured to receive an ingress signal from an edge and transmit an egress signal to another degree at a same node for transmission to another edge; and
wherein the each degree in the network is configured to receive an input signal from the edge and transmit an output signal to the edge, the edge comprising a bidirectional link.
2. The shortest path routing method of claim 1 , wherein the constrained manner comprises maintaining each visited degree such that a same degree is not revisited in the Dijkstra algorithm.
3. The shortest path routing method of claim 1 , further comprising:
defining a transmit port to a receive port and a receive port to a transmit port as edges for each link in the network;
wherein the constrained manner comprises maintaining a set of each visited degree based on the edges and implementing the Dijkstra algorithm to exclude each edge and associated vertices based on the set such that a same degree is not revisited in the Dijkstra algorithm.
4. The shortest path routing method of claim 1 , wherein the ingress vertex comprises a demultiplexer and the egress vertex comprises a multiplexer.
5. The shortest path routing method of claim 4 , wherein the network comprises an optical network, and the method further comprising:
implementing the Dijkstra algorithm in the constrained manner to find a first path through the network between two degrees in the network; and
utilizing opposite vertices at each degree in the first path to define a second path through the network between two vertices in the network, the first path comprising a path from a demultiplexer at a first degree of the two degrees to a multiplexer at a second degree of the two degrees, and the second path comprising a path from a multiplexer at the first degree to a demultiplexer at the second degree.
6. A network, comprising:
a plurality of interconnected network elements, each of the plurality of network elements comprising one or more degrees, wherein at least one network element comprises degrees which are not fully-meshed internally such that some of the degrees are not connected to one another directly internally at the at least one network element and have no interconnectivity for signals between them; and
a controller configured to determine a shortest path between any of the plurality of network elements, the controller configured to:
define an ingress vertex and an egress vertex for each degree of the one or more degrees; and
implement a Dijkstra algorithm in a constrained manner to determine a shortest path through the network between two degrees in the network;
wherein each degree in the network, except for the degrees which are not fully-meshed, is configured to receive an ingress signal from an edge and transmit an egress signal to another degree at a same node for transmission to another edge; and
wherein the each degree in the network is configured to receive an input signal from the edge and transmit an output signal to the edge, the edge comprising a bidirectional link.
7. The network of claim 6 , wherein the constrained manner comprises the controller maintaining each visited degree such that a same degree is not revisited in the Dijkstra algorithm.
8. The network of claim 6 , wherein the controller is further configured to:
define a transmit port to a receive port and a receive port to a transmit port as edges for each link in the network;
wherein the constrained manner comprises the controller maintaining a set of each visited degree based on the edges and implementing the Dijkstra algorithm to exclude each edge and associated vertices based on the set such that a same degree is not revisited in the Dijkstra algorithm.
9. The network of claim 6 , wherein the ingress vertex comprises a demultiplexer and the egress vertex comprises a multiplexer.
10. The network of claim 9 , wherein the network comprises an optical network, and the controller further configured to:
implement the Dijkstra algorithm in the constrained manner to find a first path through the network between two degrees in the network; and
utilize opposite vertices at each degree in the first path to define a second path through the network between two vertices in the network, the first path comprising a path from a demultiplexer at a first degree of the two degrees to a multiplexer at a second degree of the two degrees, and the second path comprising a path from a multiplexer at the first degree to a demultiplexer at the second degree.
11. A system, comprising:
a data store;
a network interface;
a processor, wherein the data store, the network interface, and the processor are communicatively coupled; and
wherein the processor is configured to:
maintain a network topology of a network, the network topology comprising vertices and edges;
define an ingress vertex and an egress vertex for each degree in the network at each node in the network, wherein at least one node in the network comprises degrees which are not fully-meshed internally such that some of the degrees are not connected to one another directly internally at the at least one node and are inaccessible to one another and have no interconnectivity for signals between them; and
implement a Dijkstra algorithm in a constrained manner to determine a shortest path through the network between an ingress vertex at a first degree in the network and an egress vertex at a second degree in the network;
wherein each degree in the network, except for the degrees which are not fully-meshed, is configured to receive an ingress signal from an edge and transmit an egress signal to another degree at a same node for transmission to another edge; and
wherein the each degree in the network is configured to receive an input signal from the edge and transmit an output signal to the edge, the edge comprising a bidirectional link.
12. The system of claim 11 , wherein the network topology comprises a non-fully meshed topology in at least one node of the network.
13. The system of claim 12 , wherein the system comprises a controller module in a network element.
14. The system of claim 12 , wherein the system comprises a network planning system or a network management system.
15. The system of claim 12 , wherein the constrained manner comprises maintaining each visited degree such that a same degree is not revisited in the Dijkstra algorithm.