Method and apparatus for rapidly restoring a communication network

• US 5,146,452 A
• Filed: 10/26/1990
• Issued: 09/08/1992
• Est. Priority Date: 10/26/1990
• Status: Expired due to Term

• Current Assignee: Alcatel Network Systems India Limited (Nokia Corporation)
• Original Assignee: Alcatel Network Systems India Limited (Nokia Corporation)
• Inventors: Pekarske, Robert J.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US07/604,846
• Time in Patent Office: 683 Days
• Field of Search: 370/16, 370/94.1, 370/13, 370/13.1, 370/85.12, 370/85.15, 371/8.1, 371/11.1, 371/11.2, 379/2, 379/221, 379/273, 379/274
• US Class Current: 370/228
• CPC Class Codes: H04J 3/085 for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04Q 3/0016 Arrangements providing connection between exchanges
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

The present invention provides an approach to reconnect a communications network such as a DS3 telephone-type network when a span of DS3 channels is rendered inoperative, such as by cutting, within the 1.5 second time frame necessary to prevent disablement of local offices. This is accomplished by preplanning a restoration connection for each possible operating link failure in each span using spare capacity. A dedicated (DS3) communication loop is used to inform all nodes in the network substantially simultaneously to implement their portion of a plan associated with the failed span. After the restoration occurs for a given failed span, the concept can be extended to start planning for further failures or can be designed to restore further failures on a real time basis.

Claims

1. The method of re-establishing communication between a given pair of nodes of a network having an arbitrary number of uniquely identified nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and many of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each working and spare circuit having a network unique identifier and each node being connected in a communication loop with all other nodes in the network, said method comprising the steps of:

a) monitoring the spare circuit node interconnection structure of the network and initiating a preneed alternate multinode connection plan between said pair of nodes whenever there is a change in network capacity affecting previously planned alternate circuit interconnections between said nodes;

b) establishing the route for at least one multinode alternate communication path between said pair of nodes as part of said preneed plan by,

1) a predetermined one SENDER, of said pair of nodes sending separate path search requests out over spare channels, other than those directly connecting said pair nodes, to other network nodes for each working channel between said pair of nodes needing protection, directed utimately to the other, CHOOSER, of said pair of nodes, each of the separate search requests having a unique "signature" identifier,

2) each node, other than the CHOOSER node, receiving a search request forwarding same on at least one further spare channel while incrementing a "hop" count associated with the request to indicate the number of nodes the search has traversed,

3) each node receiving multiple search requests having the same "signature" selecting only the one of said multiple having the lowest "hop" count for forwarding to other nodes,

4) the CHOOSER node selecting the search request having the lowest "hop" count for each "signature" and returning information to the SENDER as to the internode route and specific spare channels used for each search request,

5) storing information gathered as a result of the sending of the search requests as a preneed plan in each of said SENDER and CHOOSER nodes for use in the event of a loss of direct communications between said pair of nodes; and

c) implementing said preneed plan upon detection of a loss of direct communications between said pair of nodes.

2. The method of restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and many of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being normally connected in a communication circuit with all other nodes in the network, said method comprising the steps of:

a) monitoring the spare circuit node interconnection structure of the network and initiating a preneed alternate interconnection plan between said pair of nodes whenever there is a change in network capacity affecting previously planned alternate circuit interconnections between said nodes;

b) establishing the preneed alternate route for each working circuit to be protected as part of said plan by,

1) sending out search requests on spare circuits connected to nodes other than said pair of nodes by one of said pair of nodes and addressed to the other of said pair of nodes,

2) marking the search request at each hop on the way to its destination with the route taken and incrementing the request as to the number of hops required to reach the other of said pair of nodes,

3) selecting a route from those requests received at the other of said pair of nodes based on an arbitrary logical basis,

4) communicating the selected route to the one of said pair initiating the search request,

5) storing the selected route in the preneed plan, and

6) repeating steps 1 to 5 for each remaining working circuit to be protected using routes other than those already selected for the present preneed plan;

c) monitoring active traffic signals between said pair of node for a loss of communications therebetween; and

d) implementing said preneed plan upon detection of a loss of direct communications between said pair of nodes.

3. The method of restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate with all other nodes in the network, said method comprising the steps of:

a) establishing a set of preneed alternate routes for a span of working circuits between said given a pair of nodes to be protected as part of a preneed plan by,

1) sending out search requests on spare circuits connected to nodes other than said pair of nodes by one of said pair of nodes and addressed to the other of said pair of nodes,

2) selecting a route from those search requests received at the other of said pair of nodes,

3) storing the selected route as part of the preneed plan in at least one of said pair of nodes, and

4) repeating steps 2 and 3 for each remaining working circuits to be protected using routes other than those already selected for the preneed plan; and

b) implementing said preneed plan upon detection of a loss of direct communications between said pair of nodes.

4. A node to be used in a network of communicating identically constructed nodes having a number of spans interconnecting said nodes, each said span having working circuit channels between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuit channels between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate with all other nodes in the network for the purpose of establishing alternate traffic routes in the event of loss of a span between a given pair of nodes where the given pair of nodes may be set to SENDER and CHOOSER states for the purpose of a specific preneed alternate route plan and all other nodes may be set to TANDEM states, the SENDER and CHOOSER state nodes sending search requests, search request replies, confirmations and confirmation replies therebetween indirectly using the nodes in the TANDEM states as part of the preplanning actions, comprising, in combination:

plan database storage means;

means for detecting when said node is in the TANDEM state;

means for receiving search requests on a spare circuit channels;

means for logically selecting outgoing spare circuit channels to adjacent nodes and replicating thereon an updated version of a received search request for a given working channel to be protected;

means for propagating search request replies to the sender back along the same spare channel as the search request orginally traversed;

means for receiving and for propagating confirmation messages to the CHOOSER;

means for recording in its plan database storage means plan connections to be made when said node is notified of the failure of a given working circuit channel between said SENDER and CHOOSER nodes in accordance with information retrieved from received and propagated confirmation messages;

means for propagating confirmation replies back to the SENDER; and

means for responding to a received plan activation request for a given channel by checking the stored plan in said plan database storage means to see and executing the associated connection operation if that channel is referenced.

5. A node to be used in a network of communicating identically constructed nodes having a number of spans interconnecting said nodes, each said span having working circuit channels between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuit channels between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate, on a broadcast link, with all other nodes in the network for the purpose of establishing alternate traffic routes in the event of loss of a span between a given pair of nodes where the given pair of nodes may be set to SENDER and CHOOSER states for the purpose of establishing a specific preneed alternate route plan and all other nodes may be set to TANDEM states, the SENDER and CHOOSER state nodes sending search requests, search request replies, confirmations and confirmation replies therebetween indirectly using the nodes in the TANDEM states as part of the preplanning actions, comprising, in combination:

plan database storage means for storing preneed alternate connection data necessary to promptly implement switching traffic from failed communication channels to operable spare circuit channels;

broadcast link input and output ports;

first monitoring means for initiating an update of alternate connection data stored in said plan database storage means whenever a predetermined change is detected in the spare circuit capacity of the network to which the node is connected;

second monitoring means for toggling said node between a PLAN state and a NOPLAN state as a function of whether or not the stored plan has been updated in accordance with predetermined changes in the current spare capacity of the network to which the node is connected; and

means for activating alternate connection operations as set forth in the plan database storage means when said node is placed in a SENDER state because of a present working circuit channel failure and node is not in a NOPLAN state.

6. A method of restoring protected circuit traffic communications between a pair of nodes, between which commincations have been broken, in a network having an arbitrary number of nodes and arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and many of said spans having spare circuits between nodes capable of but, not designated for, the transmission of actual communications traffic, said method comprising the steps of:

a) designating one of each pair of nodes terminating each span a SENDER node for an instance of failure of that specific span and designating the other as a CHOOSER node for each span in the network in accordance with a predetermined algorithm, all other nodes in the network for a specific span failure being designated as TANDEM nodes;

b) storing a preneed alternate connection plan in each node using spare circuit capacity, said alternate connection plan at each node containing data for switching actions of that node whether acting as a SENDER, CHOOSER or TANDEM node for each of a plurality of given working circuit failures occurring between SENDER and CHOOSER;

c) updating the preneed alternate connection plan at each affected node when there is a change in network spare circuit capacity;

d) activating the switching of network traffic to spare circuits in accordance with the preneed plans stored in the nodes upon detection of the failure of protected traffic circuits.

7. The method of claim 6 where the communications broken include traffic circuits and network managerial circuits comprising the additional steps of:

providing for priority assignments of circuits to be protected in instances where there are less spare circuits available than there are circuits in a span to be protected; and

switching managerial and traffic circuits to spares circuits in the priority orders listed in the plan until all available spares circuits are used.

8. The method of claim 7 comprising the additional steps of:

storing any network broadcast indication of added spare circuit network capacity since the last preneed alternate connection plan update was performed for a given node; and

switching a given node to a real time restoration mode when (1) said given node is a SENDER node and (2) there is a stored indication of additional spare circuit capacity and (3) all spare circuits listed in the preneed plan have been activated and (4) there are still broken communication circuits to be switched.

9. An apparatus for restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate with all other nodes in the network, each node in the apparatus comprising, in combination:

a) first means for establishing a set of preneed alternate routes for a span of working circuits between said given pair of noded to be protected as part of a preneed plan, said first means, including,

1) means for sending out search request on spare circuits connected to nodes other than said pair of nodes by one of said pair of nodes and addressed to the other of said pair of nodes,

2) means for selecting a route from those search requests received at the other of said pair of nodes,

3) means for storing the selected route as part of the preneed plan in at least one of said pair of nodes, and

4) means for repeating the operations of paragraphs 2 and 3 for each remaining working circuits to be protected using routes other than those already selected for the preneed plan; and

b) second means for implementing said preneed plan upon detection of a loss of direct communications between said pair of nodes.

10. A method of restoring protected circuit traffic communications between any given pair of nodes, between which communications may be broken, in a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and many of said spans having spare circuits between nodes capable of but, not designated for, the transmission of actual communications traffic, each node in the network being capable of operating in a SENDER, CHOOSER or TANDEM mode wherein said given pair of nodes for a specific span comprises a SENDER at one end and a CHOOSER at the other and all other nodes in the network operate in the TANDEM mode, said method comprising the steps of:

a) each SENDER node, as part of a preneed plan, making a network request for permission to setup a set of alternate connection in stored memory where the requests are granted in accordance with a predetermined algorithm;

b) a SENDER, upon receiving permission to plan, sending out search request on spare circuits connected to TANDEM nodes and addressed to the CHOOSER node of said pair of nodes;

c) each TANDEM node logically forwarding received search requests toward said CHOOSER after storing information as to identify of circuit to be protected, the identity of the spare circuit upon which the request was received and the identity of any outgoing spare circuit upon which the search request was forwarded;

d) each TANDEM node reserving each outgoing spare circuit from use by other search request;

e) the CHOOSER node selecting from between any search requests for the same protected circuits, recording in memory its portion of the plan, and returning a reply back to the SENDER along the same route that the request traversed to reach the sender;

f) each TANDEM node releasing spare circuits previously reserved when it first received a search request for a specific working circuit to be protected upon other than the spare circuit upon which the reply is received;

g) the SENDER storing in memory the spare circuit from which the reply is received and that the working circuit associated therewith is now protected; and

h) a SENDER, having a preneed plan completed, activating said plan upon detecting that at least one protected working circuit between itself and the associated CHOOSER has failed.

11. The method of restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and many of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being normally connected in a communication circuit with all other nodes in the network, said method comprising the steps of:

a) monitoring the spare circuit node interconnection structure of the network and initiating a preneed alternate interconnection plan between said given pair of nodes whenever there is a change in network capacity affecting previously planned alternate circuit interconnections between said nodes;

b) establishing a preneed alternate route for each interconnected given pair of nodes to be protected as part of said plan;

c) monitoring active traffic signals between said pair of nodes for a loss of communications therebetween; and

d) implementing said preneed plan upon direction of a loss of direct communications between said pair of nodes.

12. The method of restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate with all other nodes in the network, said method comprising the steps of:

a) establishing a set of preneed alternate interconnecting routes for a span of working circuit between said given pair of nodes to be protected as part of a preneed plan;

b) implementing said preneed plan upon detection of loss of direct communications between said pair of nodes.

13. An apparatus for restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each said span having working circuits between nodes designated for transmitting actual communications traffic and at least some of said spans having spare circuits between nodes capable of, but not designated for, transmitting actual communications traffic, each node being able to managerially communicate with all other nodes in the network, each node in the apparatus comprising, in combination:

a) first means for establishing at least one preneed alternate interconnecting route for a span of working circuits between said given pair of nodes to be protected as part of a preneed plan; and

b) second means for implementing said preneed plan upon detection of a loss of direct communications between said pair of nodes.

14. Apparatus for restoring communications between any given pair of nodes of a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting said nodes, each node being able to managerially comminicate with at least adjacent nodes in the network, each node in the apparatus comprising, in combination:

a) first means for establishing at least one preneed alternate interconnecting route for each span of working circuits between said apparatus and each adjacent node having a span to be protected as part of a preneed plan; and

b) second means for implementing said preneed plan upon detection of a loss of direct communications between said apparatus and an adjacent node covered by the preneed plan.

15. The method of communicating between intelligent nodes in a DS3 type traffic signal communication network comprising the steps of:

interconnecting all nodes using spare capacity DS3 channels to form a communications loop;

transmitting idle format signals around the loop as an indication of loop integrity;

intermixing control signal bits with said idle format signals to provide broadcast communications with all nodes connected to loop in the form of continuously circulating messages; and

detecting the control signal bits of the circulating messages at each node.