Shortest minimum regeneration path search in networks

Patent metadata

Field	Value
Publication number	US-9967053-B2
Application number	US-201615169235-A
Country	US
Kind code	B2
Filing date	May 31, 2016
Priority date	May 31, 2016
Publication date	May 8, 2018
Grant date	May 8, 2018

Abstract

Methods and systems are provided for determining a shortest minimum regeneration path in an optical network. The method includes creating a virtual node at a source node, the source node communicatively coupled to a destination node through a plurality of nodes and links. The method includes traversing the virtual nodes, wherein traversing the virtual nodes comprises selecting an unvisited virtual node at a node; identifying a candidate virtual node from the unvisited virtual node; determining whether the candidate virtual node exceeds a maximum permitted weight; determining whether the candidate virtual node violates a shortest minimum regeneration path condition; and creating the new virtual node from the candidate virtual node if the candidate virtual node does not exceed the maximum permitted weight and if the candidate virtual node does not violate the shortest minimum regeneration path condition.

First claim

What is claimed is:

1. A method for determining a shortest minimum regeneration path in an optical network, the method comprising:
creating a virtual node at a source node, the source node communicatively coupled to a destination node through a plurality of nodes and links;
traversing the virtual nodes, wherein traversing the virtual nodes comprises:
selecting an unvisited virtual node at a node;
identifying a candidate virtual node from the unvisited virtual node, the candidate virtual node representing a new virtual node at the node and a neighboring node;
determining whether the candidate virtual node exceeds a maximum permitted weight;
determining whether the candidate virtual node violates a shortest minimum regeneration path condition, the shortest minimum regeneration path condition identifying virtual nodes that could not be part of the shortest minimum regeneration path;
creating the new virtual node from the candidate virtual node if the candidate virtual node does not exceed the maximum permitted weight and if the candidate virtual node does not violate the shortest minimum regeneration path condition; and
marking the unvisited virtual node as visited; and

identifying a shortest minimum regeneration path between the source node and the destination node from the virtual nodes.

2. The method of claim 1 , wherein creating the new virtual node comprises:
setting a distance value for the new virtual node to a combined weight of links in a path from the source node to the new virtual node;
setting a regeneration value for the new virtual node to a total number of regenerations in the path to the new virtual node;
setting a distance since last regeneration value for the new virtual node to a combined weight of links between the new virtual node and a prior virtual node at which a regeneration occurred.

3. The method of claim 1 , wherein the candidate virtual node exceeds a maximum permitted weight if a combined weight of links between the new virtual node and a prior virtual node at which a regeneration occurred exceeds a predetermined maximum permitted weight.

4. The method of claim 1 , wherein determining whether the candidate virtual node violates the shortest minimum regeneration path condition comprises comparing one of a distance value, a regeneration value, and a distance since last regeneration value to an existing virtual node at the node.

5. The method of claim 4 , wherein the virtual node violates the shortest minimum regeneration condition if the distance value is greater than or equal to the existing virtual node, the distance since last regeneration for the candidate virtual node is greater than the existing virtual node, and the regeneration value for the candidate virtual node is equal to the existing virtual node.

6. The method of claim 4 , wherein the virtual node violates the shortest minimum regeneration condition if the distance value is greater than the existing virtual node and the regeneration value for the candidate virtual node is greater than the existing virtual node.

7. The method of claim 4 , wherein the virtual node violates the shortest minimum regeneration condition if the regeneration value is great than the existing virtual node, and the distance since last regeneration value is greater than or equal to the existing virtual node.

8. The method of claim 4 , wherein the virtual node violates the shortest minimum regeneration condition if the regeneration value of the candidate virtual node is greater than one plus the regeneration value of the existing virtual node.

9. The method of claim 1 , wherein identifying the shortest minimum regeneration path comprises:
selecting a virtual node at the destination node with a lowest regeneration value and a lowest distance value; and
following the links from the virtual node with the lowest regeneration value and the lowest distance value to the source node.

10. The method of claim 1 , wherein selecting an unvisited virtual node from the virtual nodes comprises selecting a virtual node with a lowest regeneration value and distance value.

11. A control system for identifying the shortest minimum regeneration path, the control system comprising a processor having access to memory media storing instructions executable by the processor to:
create a virtual node at a source node, the source node communicatively coupled to a destination node through a plurality of nodes and links;
select an unvisited virtual node at a node;
identify a candidate virtual node from the unvisited virtual node, the candidate virtual node representing a new virtual node at the node and a neighboring node;
determine whether the candidate virtual node exceeds a maximum permitted weight;
determine whether the candidate virtual node violates a shortest minimum regeneration path condition, the shortest minimum regeneration path condition identifying virtual nodes that could not be part of the shortest minimum regeneration path;
create the new virtual node from the candidate virtual node if the candidate virtual node does not exceed the maximum permitted weight and if the candidate virtual node does not violate the shortest minimum regeneration path condition;
mark the unvisited virtual node as visited; and
identify a shortest minimum regeneration path between the source node and the destination node from the virtual nodes.

12. The control system of claim 11 , wherein the memory media further comprises instructions to:
set a distance value for the new virtual node to a combined weight of links in a path from the source node to the new virtual node;
set a regeneration value for the new virtual node to a total number of regenerations in the path to the new virtual node;
set a distance since last regeneration value for the new virtual node to a combined weight of links between the new virtual node and a prior virtual node at which a regeneration occurred.

13. The control system of claim 11 , wherein the candidate virtual node exceeds a maximum permitted weight if a combined weight of links between the new virtual node and a prior virtual node at which a regeneration occurred exceeds a predetermined maximum permitted weight.

14. The control system of claim 11 , wherein determining whether the candidate virtual node violates the shortest minimum regeneration path condition comprises comparing one of a distance value, a regeneration value, and a distance since last regeneration value to an existing virtual node at the node.

15. The control system of claim 14 , wherein the virtual node violates the shortest minimum regeneration condition if the distance value is greater than or equal to the existing virtual node, the distance since last regeneration for the candidate virtual node is greater than the existing virtual node, and the regeneration value for the candidate virtual node is equal to the existing virtual node.

16. The control system of claim 14 , wherein the virtual node violates the shortest minimum regeneration condition if the distance value is greater than the existing virtual node and the regeneration value for the candidate virtual node is greater than the existing virtual node.

17. The control system of claim 14 , wherein the virtual node violates the shortest minimum regeneration condition if the regeneration value is great than the existing virtual node, and the distance since last regeneration value is greater than or equal to the existing virtual node.

18. The control system of claim 14 , wherein the virtual node violates the shortest minimum regeneration condition if the regen

Assignees

• Fujitsu Ltd

Inventors

• Kim Inwoong
• Wang Xi
• Zhang Qiong
• Palacharla Paparao
• Ikeuchi Tadashi

Classifications

• H04J2203/0023

  Routing/path finding · CPC title

• H04J2203/0094

  Virtual Concatenation · CPC title

• H04J2203/0055

  Network design, dimensioning, topology or optimisation · CPC title

• H04J14/0267 Primary

  Optical signaling or routing · CPC title

• H04J2203/0098

  Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management · CPC title