Method and apparatus for fast distributed restoration of a communication network

• US 6,549,513 B1
• Filed: 10/12/1999
• Issued: 04/15/2003
• Est. Priority Date: 10/12/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Darabpour, Manouchehr, Chao, Tzu-Lien Tim
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): SCHULTZ, WILLIAM C
• Application Number:
  US09/416,545
• Time in Patent Office: 1,281 Days
• Field of Search: 370/221, 370/216, 370/217, 370/218, 370/222, 370/223, 370/225, 370/226, 370/227, 370/228
• US Class Current: 370/227
• 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

Abstract

A method for distributed managing of restoration paths within a communication network having nodes connected by links; comprising the steps of: (a) establishing a spare link catalog identifying unassigned links connecting each selected node with an adjacent node; (b) sending a probe message from each node to each adjacent node over an unassigned link; (c) evaluating the probe message at each adjacent node according to predetermined criteria; (d) forwarding the probe message to subsequent adjacent nodes, or discarding the probe message, as determined by the evaluating; (e) appending message content to the probe message indicating the path sequence traversed by the probe message proceeding through the network; (f) evaluating the forwarded probe message at each said subsequent node according to the predetermined criteria; (g) repeating steps (d) through (f) for each forwarded probe message until it is discarded or is received by the probe message originating node; (h) the probe message originating node noting each message receipt of its own probe message, each such message receipt including a recital of a restoration path in the path sequence; and (i) recording each message receipt in a restoration path register in a data store at a plurality of selected storage nodes.

Claims

1. A method for distributed restoration in an optical mesh having a plurality of nodes, comprising the steps of:

at periodic intervals, updating a spare link database, wherein the spare link database includes information relating to spare links between each node and adjacent nodes in the optical mesh network and availability of the spare links for restoration;

at periodic intervals, updating a restoration route database for each node in the optical mesh network, wherein the step of updating a restoration route database comprises the steps of;

transmitting a probe message by each node to be forward through the optical network, wherein the probe message includes an indentification of a source node and a maximum number of hops allowed in a restoration path; and

receiving the probe message by the source node, wherein the probe message includes a node list comprised of a node identification appended by each successive forwarding node that can be used as a complete restoration route and number of spare links along the restoration route, wherein the node list includes less than or equal to the maximum number of hops allowed in the restoration path; and

in response to detection of a fault in a working link, selecting a restoration route from the restoration route database and establishing the restoration route in the optical network.

2. The method in claim 1 for distributed restoration in an optical mesh network, wherein the step of, at periodic intervals, updating a spare link database, wherein the spare link database includes information relating to spare links between each node and adjacent nodes in the optical mesh network and availability of the spare links for restoration, comprises:

transmitting idle messages by each node to adjacent nodes, wherein the idle message identifies the originating node of the message, a port identification of a port connecting a spare link with the adjacent node, and state of the port;

receiving by each node idle messages from adjacent nodes; and

updating a spare link database stored at each node, wherein the spare link database at each node includes information relating to spare links connecting each node to its adjacent nodes and availability of the spare links for restoration.

3. The method in claim 1 for distributed restoration in an optical mesh network, wherein the step of, transmitting a probe message by each node to be forwarded through the optical network, wherein the probe message includes an identification of a source node and a maximum number of hops allowed in a restoration path, comprises:

transmitting a probe message from each node to each adjacent node connected by a spare link, wherein the probe message includes an identification of a source node and a maximum number of hops allowed in a restoration path.

4. The method in claim 3 for distributed restoration in an optical mesh network, wherein the step of, at periodic intervals, updating a restoration route database for each node in the optical mesh network, further comprises the steps of:

receiving a probe message by a node in the optical network, that is not the source node, from an adjacent node;

determining a hop count for the probe message and discarding the message if the hop count exceeds the maximum number of hops allowed in a restoration path;

determining spare links available for restoration to a subsequent adjacent node;

appending an identification of the node to a node list in the probe message and number of spare links available for restoration between the node and the subsequent adjacent node; and

transmitting the probe message to the subsequent adjacent node.

5. The method in claim 4 for distributed restoration in an optical mesh network, wherein the step of, at periodic intervals, updating a restoration route database for each node in the optical mesh network, further comprises the steps of:

in response to receiving the probe message by the source node, updating a restoration route database stored at the source node with the restoration route derived from the node list and the number of spare links available for restoration between each node along the restoration route.

6. The method of claim 5 for distributed restoration in an optical mesh network, wherein the step of, in response to detection of a fault in a working link, selecting a restoration route from the restoration route database and establishing the restoration route in the optical network, comprises the steps of:

detecting a failure in a working link between a first node and a second node in the optical network;

designating one node of the first node and the second node as a sender node, and the other node as a receiver node;

selecting a restoration route from the restoration route database stored at the sender node according to predetermined route selection criterion;

creating a connection message by the sender node, wherein the connection message provides information relating to the nodes in the selected restoration route and the working link with a failure; and

transmitting the connection message to an adjacent node in the selected restoration route.

7. The method of claim 6 for distributed restoration in an optical mesh network, wherein the step of, selecting a restoration route from the restoration route database stored at the sender node according to predetermined route selection criterion, further comprises the steps of:

selecting a restoration route from the restoration route database having a fewest number of hops.

8. A node in a mesh network that is connected to one or more adjacent nodes, comprising:

a spare link catalog stored in the node that includes a list of any spare links between the node and one or more adjacent nodes and availability of such spare links for restoration, wherein the node periodically updates the spare link catalog by transmitting and receiving idle messages between the one or more adjacent nodes;

a restoration route register stored in the node that includes a list of restoration routes, wherein the node periodically updates the restoration route register by transmitting a probe message to the one or more adjacent nodes and receiving the returned probe message having a node identification appended by each successive forwarding node; and

wherein the node selects one of the restoration routes stored in the restoration route register in response to a failure in a working link connected to an adjacent node and transmits a connection message with information on the selected restoration route to an adjacent node in the selected restoration route.

9. The node in claim 8, wherein the spare link catalog further includes an identification of the one or more adjacent nodes, port identification for any spare links at the node and the one or more adjacent nodes, and status of such spare links.

10. The node in claim 9, wherein the restoration route register further includes a number of spare links available along the restoration routes and identification of working links that each restoration route can be used to protect in the event of a failure on such working links.

11. The node in claim 10, wherein the node selects the restoration route stored in the restoration route register with the least number of hops in response to a failure in a working link.