Path restoration of networks

• US 6,377,543 B1
• Filed: 10/20/1997
• Issued: 04/23/2002
• Est. Priority Date: 08/13/1997
• Status: Expired due to Term

• Current Assignee: Telecommunications Research Laboratories
• Original Assignee: Telecommunications Research Laboratories
• Inventors: Doherty, Lance, Iraschko, Rainer R., Grover, Wayne D.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US08/954,247
• Time in Patent Office: 1,646 Days
• Field of Search: 370/216, 370/217, 370/218, 370/221, 370/225, 370/227, 370/228, 370/238, 370/248, 370/254, 370/351, 370/357, 370/400, 370/255, 709/238, 709/239, 340/825.01, 340/825.02, 340/825.03, 340/827
• US Class Current: 370/227
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0659 by isolating or reconfiguring faulty entities
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

A distributed method for creating telecommunications paths in a network, particularly after a span failure. The network includes plural distinct nodes interconnected by plural distinct spans, each span having working links and spare links. Each node has a digital cross-connect switch for making and breaking connections between adjacent spans forming span pairs at a node. At least one of the end nodes of a path to be created broadcasts statelets. Each intermediate node between the end nodes broadcasts incoming statelets in a manner that favours use of restoration paths that eliminate the fewest other paths. Statelets that have traversed spans with greater spare capacity, considering the number of statelets competing to be broadcast along the spans, are preferentially broadcast.

Claims

1. A method of establishing a connected telecommunications path through a telecommunications network, in which the telecommunications network includes plural nodes interconnected by plural spans, each node having a digital cross-connect switch for making and breaking connections between links in adjacent spans forming span paths through the node and a controller for controlling transmission, reception and content of statelets arriving at or transmitted from the node, in which each statelet contains plural fields, the method comprising the steps of:

broadcasting statelets from plural source nodes along successive spare links to successive tandem nodes in the network;

preferentially broadcasting from each tandem node at which statelets arrive those statelets which, by comparison with other statelets competing to be broadcast at the tandem node, have traversed spans with higher spare capacity;

continuing to broadcast statelets from tandem nodes at least until a statelet arrives at a destination node; and

creating a communications path through the nodes traversed by the statelet upon arrival of the statelet at the destination node.

2. The method of claim 1 in which each statelet contains a field defining the destination node for the statelet.

3. The method of claim 2 further comprising:

monitoring, at each tandem node, and for each span to which the tandem node is connected, how many statelets are competing to be broadcast along the span and how many spare links in the span are available for broadcasting statelets; and

updating an interference field in each statelet transmitted from each tandem node according to a measure relating how many statelets are competing to be broadcast along the span upon which the statelet is to be transmitted and how many spare links in the span are available for broadcasting statelets.

4. The method of claim 3 in which the measure is the difference between how many spare links in the span are available for broadcasting statelets and how many statelets are competing to be broadcast along the span.

5. The method of claim 3 further comprising the step of favouring use of spare links terminating at an end node of a failed working path by any statelet for which the destination node of the statelet is an end node of the failed working path.

6. The method of claim 5 in which favouring use of spare links comprises:

defining a local protection area comprising nodes adjacent to an end node of a failed working path; and

updating a field in statelets traversing the local protection area in a manner that decreases the likelihood that the statelets will be broadcast from subsequent nodes if the destination node of the statelets is not the end node of the failed working path.

7. The method of claim 6 in which creating a communications path comprises:

upon receipt of a statelet at a destination node, transmitting a reverse linking statelet from the destination node along the nodes traversed by the statelet.

8. The method of claim 2 further comprising the step of favouring use of spare links terminating at an end node of a failed working path by any statelet for which the destination node of the statelet is an end node of the failed working path.

9. The method of claim 8 in which favouring use of spare links comprises:

broadcasting statelets from first and second end nodes of a failed working path along respective paths until a statelet initiated by the first end node meets, at a tandem node, a statelet initiated by the second end node; and

propagating the statelet initiated by the first end node along the path followed by the statelet initiated by the second end node until the statelet reaches the second end node.

10. The method of claim 9 further comprising confirming the existence of a connected path between the first and second end nodes.

11. The method of claim 2 in which broadcast of statelets is initiated upon receipt by a node in the network of a signal indicating that a failure has occurred on one of the spans of the network.

12. The method of claim 11 in which each source node attempts to broadcast as many statelets, each corresponding to a different index family, as there are lost links in the failed span.

13. The method of claim 2 in which each statelet broadcast by a source node has an index field whose value is uniquely associated with the source and destination node of the statelet and the span on which the statelet is transmitted from the source node.

14. The method of claim 13 in which each tandem node transmits on each span only one statelet having a specific combination of index field, source node and destination node.

15. The method of claim 14 in which each tandem node attempts to broadcast each statelet arriving at the tandem node on as many spans as possible.

16. The method of claim 2 in which each statelet contains a repeat field and the method further comprises the steps of:

each tandem node incrementing the value of the repeat field of a statelet upon arrival of the statelet at the tandem node; and

preventing broadcast of statelets having a repeat field value greater than a pre-determined value.

17. The method of claim 2 in which each statelet contains a route field and the method further comprises the steps of:

each tandem node updating the route field of a statelet upon arrival of the statelet at the tandem node to include the identification of the tandem node, whereby the statelet contains a record of the nodes traversed by the statelet; and

preventing broadcast of each statelet to any tandem node previously traversed by the respective statelet.

18. The method of claim 17 further comprising the steps of:

identifying any communications paths having a length of one span; and

preventing any statelet from being broadcast along a communications path having a length of one span.

19. The method of claim 2 in which creating a communications path comprises:

upon receipt of a statelet at a destination node, transmitting a reverse linking statelet from the destination node along the nodes traversed by the statelet.

20. The method of claim 19 in which each statelet broadcast by a source node has an index field whose value is uniquely associated with the source and destination node of the statelet and the span on which the statelet is transmitted from the source node.

21. The method of claim 20 further comprising:

cancelling transmission of a reverse linking statelet from a destination node if a reverse linking statelet having a given index field value arriving at a tandem node has traversed spans with lower spare capacity than another statelet with the given index field value competing to be broadcast from the tandem node.

22. The method of claim 19 in which each statelet contains a route field and the method further comprises the step of:

each tandem node updating the route field of a statelet upon arrival of the statelet at the tandem node to include the identification of the tandem node, whereby the statelet contains a record of the nodes traversed by the statelet.

23. A method of establishing a communications path in a telecommunications network, in which the network is formed by plural nodes interconnected by plural spans, each span containing working and spare links, each node having a cross-connect switch for connecting links in spans terminating at the node and a controller for controlling propagation and content of statelets arriving at or transmitted from the node, the method comprising the steps of:

propagating statelets through the network, in which each statelet comprises fields designating a source node for the statelet, a destination node for the statelet, a statelet index, and a measure of the spare capacity of spans traversed by the statelet;

updating each statelet transmitted from a node on a span, except at the destination node for that statelet, to alter the measure of spare capacity according to the spare capacity of the span on which the statelet is to be transmitted, in which the measure of spare capacity takes into account how many statelets are competing to be broadcast along the span and how many spare links in the span are available for broadcasting statelets; and

creating a communications path through the nodes traversed by a statelet upon arrival of a statelet at the destination node of the statelet.

24. The method of claim 23 in which the measure of spare capacity is the difference between how many spare links in the span are available for broadcasting statelets and how many statelets are competing to be broadcast along the span.

25. The method of claim 24 in which propagation of statelets is initiated upon receipt by a node in the network of a signal indicating that a working path in the network has failed.

26. The method of claim 25 further comprising the step of favouring use of spare links terminating at an end node of a failed working path by any statelet for which the destination node of the statelet is an end node of the failed working path.

27. The method of claim 26 in which favouring use of spare links comprises:

defining a local protection area comprising nodes adjacent to an end node of a failed working path; and

updating a field in statelets traversing the local protection area in a manner that decreases the likelihood that the statelets will be broadcast from subsequent nodes if the destination node of the statelets is not the end node of the failed working path.

28. The method of claim 26 in which favouring use of spare links comprises:

broadcasting statelets from first and second end nodes of a failed working path along respective paths until a statelet initiated by the first end node meets, at a tandem node, a statelet initiated by the second end node; and

propagating the statelet initiated by the first end node along the path followed by the statelet initiated by the second end node until the statelet reaches the second end node.

29. The method of claim 28 further comprising confirming the existence of a connected path between the first and second end nodes.

30. The method of claim 26 in which each source node attempts to broadcast as many statelets, each corresponding to a different index family, as there are lost working paths.

31. The method of claim 30 in which each statelet broadcast by a source node has an index field whose value is uniquely associated with the source and destination node of the statelet and the span on which the statelet is transmitted from the source node.

32. The method of claim 31 in which each tandem node transmits on each span only one statelet having a specific combination of index field, source node and destination node.

33. The method of claim 32 in which each tandem node attempts to broadcast each statelet arriving at the tandem node on as many spans as possible.

34. The method of claim 33 in which each statelet contains a route field and the method further comprises the steps of:

each tandem node updating the route field of a statelet upon arrival of the statelet at the tandem node to include the identification of the tandem node, whereby the statelet contains a record of the nodes traversed by the statelet; and

preventing broadcast of each statelet to any tandem node previously traversed by the respective statelet.

35. The method of claim 34 further comprising the steps of:

identifying any communications paths having a length of one span; and

preventing any statelet from being broadcast along a communications path having a length of one span.

36. The method of claim 35 in which creating a communications path comprises:

upon receipt of a statelet at a destination node, transmitting a reverse linking statelet from the destination node along the nodes traversed by the statelet.

37. The method of claim 36 further comprising:

cancelling transmission of a reverse linking statelet from a destination node if a reverse linking statelet having a given index field value arriving at a tandem node has traversed spans with lower spare capacity than another statelet with the given index field value competing to be broadcast from the tandem node.

38. The method of claim 37 in which each statelet contains a repeat field and the method further comprises the steps of:

each tandem node incrementing the value of the repeat field of a statelet upon arrival of the statelet at the tandem node; and

preventing broadcast of statelets having a repeat field value greater than a pre-determined value.