Communication system and method providing optimal restoration of failed paths

• US 5,835,482 A
• Filed: 09/18/1996
• Issued: 11/10/1998
• Est. Priority Date: 09/22/1995
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MCI Communications Corporation (Verizon Communications Inc.)
• Inventors: Allen, John David
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/715,323
• Time in Patent Office: 783 Days
• Field of Search: 370/16, 370/16.1, 370/54, 370/60, 370/60.1, 370/94.3, 370/216, 370/217, 370/218, 370/225, 370/351, 370/400, 371/8.2, 371/11.2, 379/16, 379/221, 340/825.01, 340/827, 455/8, 395/182.02
• US Class Current: 370/225
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

To restore partial outages within a communication network having numerous switching nodes and links interconnecting the nodes, a three-stage distributed restoration protocol is activated to use spare links to bypass failed links and restore normal network connectivity. The three-stage protocol detects and resolves contention for spare resources among separate restoration processes and is therefore particularly advantageous in the event of multiple simultaneous network failures. A conservative flooding approach is used during the first forward signalling stage. Data elements added to the forward signals convey the likelihood that the path will be needed for restoration. The second reverse signalling stage uses reverse signals with attached contention data to detect contention among separate processes for spare resources and to alert the respective processes. The final path implementation stage involves reviewing the reverse signals and using the attached contention data to make informed choices of restoration paths that result in the highest degree of overall network restoration. The present invention, including node logic and specific signal structures and multiple-pass signalling, allows for shared awareness among diverse restoration processes so that they may work collectively to best utilize available spare resources.

Claims

1. In a telecommunications network having a plurality of nodes interconnected by a plurality of spans each having working and spare links, a method of restoring traffic disrupted by at least one failed link, comprising the steps of:

(a) designating one of a pair of nodes bracketing said one failed link a sender node and an other of said pair of nodes a chooser node, and nodes interconnecting said sender and chooser nodes via said plurality of spans tandem nodes;

(b) transmitting restoration signals from said sender node to said chooser node along said interconnected tandem nodes, each of said restoration signals including data identifying said sender and chooser nodes, index data and probability data indicative of the likelihood that the path traversed by said each restoration signal is to be used for restoring the disrupted traffic;

(c) adding to said each restoration signal contention data as said each restoration data traverses along each one of said tandem nodes;

(d) after receiving said restoration signals for a predetermined time period, said chooser node transmitting reverse restoration signals to backtrack the restoration paths traversed by said received restoration signals, said reverse restoration signals each including particular contention and probability of use data derived from the data carried by a corresponding restoration signal received by said chooser node; and

(e) upon receipt of an expected number of said reverse restoration signals, said sender node reviewing the respective contention and probability of use data attached to each of said received reverse restoration signals to select an optimal restoration path for restoring the disrupted traffic.

2. The method of claim 1, further comprising the step of:

appending contention data relating to each tandem node to each reverse restoration signal passing through said each tandem node, said each tandem node generating and sending an update message to any other sender node of other sender and chooser pairs not bracketing said one failed link.

3. The method of claim 1, further comprising the step of:

effecting said sender node to

i) assess the number of failed links in said telecommunications network before said sender node transmits restoration signals to said chooser node;

ii) identify a span, and ports and spare links within said identified span, to which restoration signals may be transmitted;

iii) limit the number of restoration signals to be transmitted along spare links in said span to the number of failed links assessed;

iv) select a port and a spare link in said span for transmitting each restoration signal;

v) repeat steps (ii) to (iv) for each span connected to said sender node.

4. The method of claim 1, wherein said step (b) further comprises the step of:

providing said probability data to said each restoration signal by adding a FAILED field and a FLOODED field to said each restoration signal, said FAILED and FLOODED fields together providing an indication of the likelihood that a prospective path traversed by said each restoration signal will actually be needed for restoring the disrupted traffic.

5. The method of claim 1, upon receipt of a restoration signal at a port of a span connected to said each tandem node, said each tandem node

updating a contention metric associated with said port to indicate the probability that said port is to be used for restoration of the disrupted traffic;

maintaining a record of restoration signals dispatched along each span connected to said each tandem node for said pair of sender and chooser nodes; and

selecting the port with the lowest contention metric as an output port for forwarding said received restoration signal to nodes downstream of said each tandem node.

6. The method of claim 5, said each tandem node further curtailing further forwarding of restoration signals to a particular span if the number of restoration signals dispatched along said particular span connected to said each tandem node already equals to the number of failed links assessed;

storing the curtailed restoration signals in a holding store; and

updating the count of the number of restoration signals sent out along each span for each pair of sender and chooser nodes.

7. The method of claim 6, each of said tandem nodes, upon receipt of each reverse restoration signal, further

correlating the restoration path of said reverse restoration signal with a corresponding restoration signal that had traversed through said each tandem node;

transmitting said reverse restoration signal to the span from which said corresponding restoration signal had reached said each tandem node;

generating a copy of said reverse restoration signal for each curtailed restoration signal stored in said holding store, a percentage of probability of use being allocated for each said copy; and

transmitting any copy of said reverse restoration signal along the restoration path associated with the curtailed restoration signal.

8. The method of claim 1, wherein said each restoration signal includes a chooser ID and each node of said network includes a node ID, further comprising the step of:

determining said chooser node to have been reached by said each restoration signal if the chooser ID of said each restoration signal is the same as the node ID of the node in receipt of said each restoration signal.

9. The method of claim 1, in receipt of said each restoration signal, said chooser node further

updating the port in the span from which said each restoration signal is received by said chooser node;

extracting sender, chooser and index data carried by said each received restoration signal;

recording the sender, chooser and index data for said each received restoration signal in a table store; and

converting the sender, chooser and index data of said each received restoration signal into a unique identifier for a candidate restoration path.

10. The method of claim 9, said chooser node further

determining if a candidate restoration path is already in said table store;

keeping a count of the number of times restoration signals from a candidate restoration path is received by said chooser node;

retrieving from said table store the restoration signal having the lowest hop count;

calculating a probability of use metric for the restoration path of said retrieved restoration signal; and

designating said restoration path with the probability of use metric as the chosen restoration path.

11. The method of claim 10, further comprising the steps of:

transmitting from said chooser node a reverse restoration signal including said probability of use metric to said chosen restoration path from a best available port of the span from which said retrieved restoration signal was received.

12. The method of claim 11, wherein said step (e) further comprises the step of:

transmitting an update signal to tandem nodes not along said optimal restoration path for updating the availability of the spans and ports associated with those tandem nodes to prevent contention problems.

13. The method of claim 1, each of said tandem nodes, upon receipt of each reverse restoration signal, further

correlating the restoration path of said reverse restoration signal with a corresponding restoration signal that had traversed through said each tandem node;

and

transmitting said reverse restoration signal to the span from which said corresponding restoration signal had reached said each tandem node.

14. The method of claim 1, further comprising the step of:

said sender node collecting all reverse restoration signals for selecting an optimal restoration path based on the lowest probability of use, the lowest hop count or the shortest implemented restoration path length.

15. A method of restoring communications in a telecommunications network having a plurality of nodes interconnected by a plurality of spans each having working and spare links, at least one of said links having failed, comprising the steps of:

(a) designating one of a pair of nodes bracketing said one failed link a sender node and an other of said pair of nodes a chooser node, and nodes interconnecting said sender and chooser nodes via said plurality of spans tandem nodes;

(b) said sender node

i) assessing the number of failed links;

ii) identifying a span and spare ports within said span for flooding restoration signals;

iii) limiting the number of restoration signals to be transmitted along spare links in said span to the number of failed links assessed;

iv) selecting an output port for each restoration signal to be sent;

v) repeating steps ii to iv for each span connected to said sender node;

vi) transmitting at least one restoration signal to said chooser node through each output port of said each span, each of said restoration signals including data identifying said sender and chooser nodes, and probability data indicative of the likelihood that the path traversed by said one restoration signal is to be used for restoring the communications carried by said one failed link;

(c) each of said tandem nodes, upon receipt of a restoration signal at a port of a span connected thereto,

updating a contention metric associated with said port to indicate the probability that said port is to be used for restoration of the disrupted traffic;

maintaining a record of restoration signals dispatched along each span connected to said each tandem node for said pair of sender and chooser nodes;

selecting the port with the lowest contention metric as an output port for forwarding received restoration signals to nodes downstream from said each tandem node;

(d) said chooser node, after receiving restoration signals for a predetermined period of time,

choosing from among the received restoration signals one having a corresponding restoration path;

calculating a probability of use metric for said chosen restoration path;

transmitting a reverse restoration signal including a probability of use metric to said chosen restoration path, said reverse restoration signal including particular contention and probability of use data derived from data carried by said chosen restoration signal;

(e) said sender node, upon receipt of an expected number of said reverse restoration signal, reviewing the respective contention and probability of use data attached to each of said received reverse restoration signals to select an optimal restoration path for restoring the communications carried by said failed link.

16. The method of claim 15, wherein said probability data of said each restoration signal sent out by said sender node comprises a FAILED data field and a FLOODED data field which together provides a ratio for indicating the likelihood that a prospective path traversed by said each restoration signal will actually be needed for restoring the communications carried by said failed link.

17. The method of claim 15, wherein said step (c) further comprises the steps of:

said tandem node curtailing further forwarding of restoration signals to a particular span if the number of restoration signals dispatched along said particular span connected to said tandem node already equals to the number of failed links assessed; and

storing the curtailed restoration signals in a holding store.

18. The method of claim 15, further comprising the step of:

appending contention data relating to each tandem node to each reverse restoration signal passing through said each tandem node, said each tandem node generating and sending an update message to any other sender node of other sender and chooser pairs not bracketing said one failed link.

19. The method of claim 15, wherein said each restoration signal includes a chooser ID and each node of said network includes a node ID, further comprising the step of:

determining said chooser node to have been reached by said each restoration signal if the chooser ID of said each restoration signal is the same as the node ID of the node in receipt of said each restoration signal.

20. In a telecommunications network having a plurality of nodes interconnected by a plurality of spans each having working and spare links, a system for restoring traffic disrupted by at least one failed link, one of a pair of nodes bracketing said one failed link being designated a sender node and an other of said pair of nodes being designated a chooser node, and nodes interconnecting said sender and chooser nodes via said plurality of spans being designated tandem nodes, said system comprising:

processor switch means in said sender node for flooding restoration signals to said chooser node along said interconnected tandem nodes, each of said restoration signals including data identifying said sender and chooser nodes, index data and probability data indicative of the likelihood that the path traversed by said each restoration signal is to be used for restoring the disrupted traffic;

processor switch means in each of said tandem nodes for adding to said each restoration signal contention data as said each restoration data traverses along said each tandem node; and

processor switch means in said chooser node for receiving said restoration signals, after receiving said restoration signals for a predetermined time period, said chooser node processor switch means transmitting reverse restoration signals to backtrack the restoration paths traversed by said received restoration signals, said reverse restoration signals each including particular contention and probability of use data derived from the data carried by a corresponding restoration signal received by said chooser node;

upon receipt of an expected number of said reverse restoration signals, said sender node processor switch means reviewing the respective contention and probability of use data attached to each of said received reverse restoration signals to select an optimal restoration path for restoring the disrupted traffic.

21. The system of claim 20, wherein the processor switch means of said each tandem node further appends contention data relating to each tandem node to each reverse restoration signal passing through said each tandem node, and generates and sends an update message to any other sender node of other sender and chooser pairs not bracketing said one failed link.

22. The system of claim 20, wherein said processor switch means of said sender node further

i) assesses the number of failed links in said telecommunications network before transmitting restoration signals to said chooser node;

ii) identifies a span, and ports and spare links within said identified span, to which restoration signals may be transmitted;

iii) limits the number of restoration signals to be transmitted along spare links in said span to the number of failed links assessed;

iv) selects a port and a spare link in said span for transmitting each restoration signal; and

v) repeats steps (ii) to (iv) for each span connected to said sender node.

23. The system of claim 20, wherein said probability data is provided to said each restoration signal as a FAILED field and a FLOODED field, said FAILED and FLOODED fields together providing an indication of the likelihood that a prospective path traversed by said each restoration signal will actually be needed for restoring the disrupted traffic.

24. The system of claim 20, wherein said each tandem node is connected to at least one span having a plurality of ports, and wherein upon receipt of a restoration signal at a port of said one span, said each tandem node processor switch means

updates a contention metric associated with said port to indicate the probability that said port is to be used for restoration of the disrupted traffic;

maintains a record of restoration signals dispatched along each span connected to said each tandem node for said pair of sender and chooser nodes; and

selects the port with the lowest contention metric as an output port for forwarding said received restoration signal to nodes downstream thereof.

25. The system of claim 20, wherein said each tandem node processor switch means further comprises a holding store, the processor switch means of said each tandem node curtailing further forwarding of restoration signals to a particular span if the number of restoration signals dispatched along said particular span connected to said each tandem node already equals to the number of failed links assessed, storing the curtailed restoration signals in said holding store, and updating the count of the number of restoration signals sent out along each span for each pair of sender and chooser nodes.

26. The system of claim 20, wherein the processor means of said each tandem node along said optimal restoration path transmits an update signal to other tandem nodes for updating the availability of the spans and ports associated with said each tandem node to prevent contention problems.

27. The system of claim 20, wherein said sender node processor switch means collects all reverse restoration signals from said each tandem nodes for selecting said optimal restoration path based on the lowest probability of use, the lowest hop count or the shortest implemented restoration path length.