Method for finding protected path in mesh networks
View Patent ↗A method of finding a primary communication path in a mesh network, which would be at once a protected path having a fully guaranteed segmented node or node-link protection. The method comprises defining a required protection type and further selecting each specific path segment of the desired communication path based on initial user's requirements and topology information of the network. Each specific node path segment N for the communication path is selected upon ensuring that it can be protected in the network by a node backup path satisfying the initial user's requirements. Each specific link path segment L for the communication path is chosen if it can be protected in the network by a link backup path satisfying the initial user's requirements and if the node path segment N to which segment L leads cannot be protected by a suitable node backup path.
1. A method for routing data packets in a mesh network, comprising:
selecting a fully protected communication path between a source node and a destination node in the mesh network, said communication path being assembled from path segments each presenting either a node path segment N or a link path segment L and each being protected with a backup path in said network, wherein each node path segment N comprises a node, a link incoming to said node and a link outgoing from said node, while each link path segment L comprises a single link outgoing from one associated node and incoming to another associated node,
defining a required protection type for said communication path, being either a node protection, or a node-link protection,
finding a primary path being said fully protected communication path, by selecting each specific path segment for said primary path according to initial user's requirements and topology information on the network, and by using the following rules:
a) for any of said protection types, selecting a specific node path segment N for the primary path upon ensuring that said specific node path segment N can be protected in the network by a node backup path satisfying said initial user's requirements,
b) if the node protection is defined, selecting for the primary path only a single specific link path segment L comprising a link incoming to said destination node, upon ensuring that said single specific link path segment L can be protected in the network by a link backup path satisfying said initial user's requirements,
c) if the node-link protection is defined, selecting for the primary path a specific link path segment L only if it is impossible to select a node path segment N there-instead, upon ensuring that said specific link path segment L can be protected in the network by a link backup path satisfying said initial user's requirements; and
routing the data packets along thus selected fully protected communication path between the source node and the destination node.
2. The method according to claim 1 , further comprising finding, in a single phase, the primary path being said fully protected communication path.
3. The method according to claim 1 , wherein the communication path is a Label Switched Path (LSP), the mesh network is a Multiprotocol Label Switching (MPLS) network, and said protection is a guaranteed Fast Reroute (FRR) segment protection.
4. The method according to claim 1 , wherein the initial user's requirements include at least the source node, the destination node, the required protection type and quality of service (QoS) requirements comprising at least bandwidth requirements of the communication path.
5. The method according to claim 4 , wherein the initial user's requirements include at least one additional requirement from the following non-exhaustive list: the maximal metric allowed for the path, class of service (CoS), path bidirectionality, loop-free constraint.
6. The method according to claim 1 , wherein the topology information is represented as a weighted directed topology graph of nodes and interconnecting links, wherein each node and link is associated with resources and/or topology constraints, including information concerning available node backup paths and link backup paths.
7. The method according to claim 6 , comprising: a step of introducing intra-node connectivity and transforming said topology graph into a transformed graph, by adding to the topology graph fictitious intra-node links, the step comprises adding a fictitious intra-node link with a zero metric into the node of a node path segment to interconnect the incoming link and the outgoing link of said node segment, if there is a node backup path for said path segment in the topology graph.
8. The method according to claim 7 , wherein the step of introducing intra-node connectivity further comprises an additional operation of adding to the topology graph further fictitious intra-node links with non-zero metric, wherein a fictitious intra-node link with a non-zero metrics is added to the node of a node segment to interconnect the incoming link and the outgoing link of said node segment, if there is no node backup path for said node path segment in the topology graph, while there is a link backup path for the incoming link of said node path segment.
9. The method according to claim 1 , further comprising applying a computation algorithm for finding, in said network, an optimal path based on a predetermined criterion.
10. A software product comprising computer implementable instructions and/or data for carrying out the method according to claim 1 , stored on an appropriate computer readable non-transitory storage medium so that the software is capable of enabling operations of said method, when used in a computer.