Path-based restoration mesh networks

• US 6,324,162 B1
• Filed: 06/03/1998
• Issued: 11/27/2001
• Est. Priority Date: 06/03/1998
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Chaudhuri, Sid
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US09/089,823
• Time in Patent Office: 1,273 Days
• Field of Search: 370/216-218, 370/221, 370/225, 370/228, 370/242, 370/244-245, 370/248, 340/825.01, 340/825.06, 340/825.16, 709/239, 709/242, 714/1-2, 714/4, 714/25
• US Class Current: 370/225
• CPC Class Codes: H04B 1/745 using by-passing or self-healing methods
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

Restoration of service in a mesh network (10) upon the failure of a working channel (16) on a link (14_I) connecting a pair of nodes (12A and 12D) is accomplished by first attempting to route traffic on an restoration channel (18) in the same link when such a channel is available. If such “localized” restoration can not be accomplished, then the end-point (traffic originating and/or terminating) nodes that are connected by a path that includes the link having the failed working channel then implements a precomputed path. Each pre-computed path identifies a collection of channels in a series of links that connect the end-point nodes (and any intermediate nodes) so as to bypass traffic around the link having the failed working channel. The pre-computed path information is typically pre-stored in the end-point nodes to enable the end-point nodes to effect rapid restoration in the event localized restoration in not achievable.

Claims

1. A method for restoring service in a mesh network formed of a plurality of nodes at least two of which serve as end points for traffic traversing the network, the nodes connected to each other by links, each link having at least one working channel for carrying traffic between a pair of nodes and a restoration channel, and each pair of end-point nodes connected through a working path by connecting a set of channels in a series of links, the method comprising the steps of:

(a) monitoring each link to detect a failure of a working channel and, upon detecting a failure,

(b) determining if said each link with a failed working channel has at least one available restoration channel able to carry traffic, and if so, then routing traffic on said available restoration channel;

but if no restoration channel is available in said each link with the failed working channel, then restoring traffic by the steps of

(1) checking the availability of, and selecting a restoration channel in the same link according to a pre-determined priority of failed channels;

(2) sending a request from a first node connected at a first end of the link having a failed channel to a second node at an opposite end over the available channel to verify that said available channel is to be used for routing failed traffic in both directions;

(3) effecting a switching operation at each of the first and second nodes to switch traffic from the failed channel to the available restoration channel, then

(c) implementing, at each pair of end-point nodes linked by said working path having the failed channel in a link in said path, a pre-computed path associated with said link having said failed channel, said pre-computed path associated with said link and identifying a collection of restoration channels in pre-selected links that collectively provide a route between said pair of end-point nodes, and

(d) routing traffic in said network over said pre-computed path between each said pair of end-point nodes that would otherwise pass traffic over the link having the failed working channel.

2. The method according to claim 1 wherein the routing step includes the steps of:

identifying the pre-computed path to each pair of end-point nodes that would otherwise pass traffic over the link having the failed working channel; and

effecting switching of traffic onto the pre-computed path.

3. The method according to claim 1 wherein the monitoring step includes the steps of:

monitoring each link for a restoration trigger including Loss of Signal, Loss of Frame and Signal Degrade and

communicating that condition to each node connected to said each link.

4. The method according to claim 1 wherein the step of routing traffic over the pre-computed path comprises the steps of:

originating a request to effect automatic switching at a first endpoint node to route traffic on an available restoration channel able to carry traffic;

passing the automatic switching request from the first end-point node to a first intermediate node that receives the request on a working channel in the pre-computed path and thereafter passes the request without action to a subsequent node when the restoration channel identified by the pre-computed path is a channel of an original path traversing that first intermediate node;

otherwise,

bridging, at the first intermediate node, an incoming channel to an outgoing channel in response to a request on the working channel when the outgoing channel is not a part of the original path;

but

connecting an incoming channel at an intermediate node to an outgoing restoration channel in response to a request on a restoration channel when no channel is part of the original path.

5. The restoration method according to claim 4 further including the steps of:

(a) determining, after implementation of each pre-computed path, whether there exist any paths in failure, and if so;

(b) communicating to a restoration path control system, the paths still in failure;

(c) determining if the cause of the paths still in failure is a node failure, and if not then if the cause is multiple links in failure;

(d) determining additional pre-computed paths or computing additional restoration paths avoiding failed links and nodes, each corresponding to a node in failure or multiple links in failure;

(e) downloading said additional paths to each pair of end point nodes whose connecting path contains a link still in failure; and

(f) effecting a routing operation on the said additional paths.

6. The method according to claim 1 further including the steps of:

(a) determining when a failed working channel on a link is returned to service; and

(b) switching traffic back onto the link returned to service.

7. The method according to claim 1 wherein each pre-computed path is determined by the method comprising the steps of:

(a) determining a set of all available restoration channels except those in a successive one of the links and

(b) establishing the pre-computed path P for a successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said successive working channel in said successive link;

(c) removing from the set of available restoration channels the channels comprising said pre-computed path for said successive working channel in said successive link;

(d) establishing a pre-computed path for a next successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said next successive working channel in said successive link;

(e) removing from the set of available restoration channels the channels comprising said pre-computed path for said next one successive working channel in said successive link;

(f) repeating steps (d) and (e) for each next successive working channel in said successive link until pre-computed paths are established for all the working channels in said successive link;

(g) repeating steps (b)-(f) for all of the links.

8. The method according to claim 7 wherein the originating request is communicated on an unused portion of an overhead data block in the traffic traversing the network.

9. A method for restoring service in a mesh network formed of a plurality of nodes at least two of which serve as end points for traffic traversing the network, the nodes connected to each other by links, each link having at least one working channel for carrying traffic between a pair of nodes and a restoration channel, and each pair of end-point nodes connected by a working path formed of at least one working channel in one link, the method comprising the steps of:

(a) monitoring each link to detect a failure of a working channel and, upon detecting a failure,

(b) determining if said each link with a failed working channel has at least one available restoration channel able to carry traffic, and if so, then routing traffic on said available restoration channel;

but if no restoration channel is available on said restoration channel in said each link with the failed working channel, then

(c) implementing, at each pair of end-point nodes linked by said working path having the failed channel in a link in said path, a pre-computed path associated with said link having said failed channel, said pre-computed path associated with a said link and identifying a collection of restoration channels in pre-selected links that collectively provide a route between said pair of end-point nodes, and

(d) routing traffic in said network over said pre-computed path between each said pair of end-point nodes that would otherwise pass traffic over the link having the failed working channel by the steps of;

(1) originating a request to effect automatic switching at a first end point node to route traffic on an available restoration channel able to carry traffic;

(2) passing the automatic switching request from the first endpoint node to a first intermediate node in the pre-computed path that receives the request on a working channel and thereafter passes the request without action to a subsequent node when the restoration channel identified by the pre-computed path is a path of an original path traversing that first intermediate node;

otherwise,

(3) bridging, at the first intermediate node an incoming channel to an outgoing channel in response to a request on the working channel when outgoing channel is not a part of the original path;

but

(4) connecting an incoming channel at an intermediate node to an outgoing restoration channel in response to a request on a restoration channel when no channel is part of the original path.

10. The method according to claim 9 wherein the routing step includes the steps of:

identifying the pre-computed path to each pair of end-point nodes that would otherwise pass traffic over the link having the failed working channel; and

effecting switching of traffic onto the pre-computed path.

11. The method according to claim 9 wherein the monitoring step includes the steps of:

monitoring each link for a restoration trigger including Loss of Signal, Loss of Frame and Signal Degrade; and

communicating that condition to each node connected to said each link.

12. The method according to claim 9 wherein the step of determining and routing on an available channel on the same link comprises the steps of:

(a) checking the availability of, and selecting a restoration channel in the same link according to a pre-determined priority of failed channels;

(b) sending a request from a first node connected to a first end of the link having a failed channel to a second node at an opposite end over the available channel to verify that same said available channel is to be used for routing failed traffic in both directions; and

(c) effecting a switching operation at each of the first and second nodes to switch traffic from the failed channel to the available restoration channel.

13. The restoration method according to claim 9 further including the steps of:

(a) determining, after implementation of each pre-computed path, whether there exist any links in failure, and if so;

(b) communicating to a restoration path control system, the links still in failure;

(c) determining additional pre-computed paths, each corresponding to a link still in failure; and

(d) downloading said additional pre-computed paths to each pair of end point nodes whose connecting path contains a link still in failure.

14. The method according to claim 9 further including the steps of:

(a) determining when a failed working channel on a link is returned to service; and

(b) switching traffic back onto the link returned to service.

15. The method according to claim 9 wherein each pre-computed path is determined by the method comprising the steps of:

(a) determining a set of all available restoration channels except those in a successive one of the links and

(b) establishing the pre-computed path P for a successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said successive working channel in said successive link;

(c) removing from the set of available restoration channels the channels comprising said pre-computed path for said successive working channel in said successive link;

(d) establishing a pre-computed path for a next successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said next successive working channel in said successive link;

(e) removing from the set of available restoration channels the channels comprising said pre-computed path for said next successive working channel in said successive link;

(f) repeating steps (d) and (e) for each next successive working channel in said successive link until pre-computed paths are established for all the working channels in said successive link;

(g) repeating steps (b)-(f) for all of the links.

16. The method according to claim 9 wherein the originating request is communicated on an unused portion of an overhead data block in the traffic traversing the network.

17. A method for restoring service in a mesh network formed of a plurality of nodes at least two of which serve as end points for traffic traversing the network, the nodes connected to each other by links, each link having at least one working channel for carrying traffic between a pair of nodes and a restoration channel, and each pair of end-point nodes connected by a working path formed of at least one working channel in one link, the method comprising the steps of:

(a) monitoring each link to detect a failure of a working channel and, upon detecting a failure,

(b) determining if said each link with a failed working channel has at least one available restoration channel able to carry traffic, and if so, then routing traffic on said available restoration channel;

but if no restoration channel is available within the each link with the failed working channel, then

(c) implementing, at each pair of end-point nodes linked by said working path having the failed channel in a link in said path, a pre-computed path associated with said link having said failed channel, said pre-computed path associated with a said link and identifying a collection of restoration channels in pre-selected links that collectively provide a route between said pair of end-point nodes, each pre-computed path established by the steps of;

(1) determining a set of all available restoration channels except those in a successive one of the links and

(2) establishing the pre-computed path P for a successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said successive working channel in said successive link;

(3) removing from the set of available restoration channels the channels comprising said precomputed path for said successive working channel in said successive link;

(4) establishing a pre-computed path for a next successive one of n working channels in a successive one of the links from a collection of available restoration channels, which yields a shortest path between said two end-point bypassing said next successive working channel in said successive link;

(5) removing from the set of available restoration channels the channels comprising said pre-computed path for said next one successive working channel in said successive link;

(6) repeating steps (4) and (5) for each next successive working channel in said successive link until pre-computed paths are established for all the working channels in said successive link;

7 repeating steps (2) through (6) for all of the links and

routing traffic in said network over said pre-computed path between each said pair of end-point nodes that would otherwise pass traffic over the link having the failed working channel.

18. The method according to claim 17 wherein the routing step includes the steps of:

identifying the pre-computed path to each pair of endpoint nodes that would otherwise pass traffic over the link having the failed working channel; and

effecting switching of traffic onto the pre-computed path.

19. The method according to claim 17 wherein the monitoring step includes monitoring each link for a restoration trigger including Loss of Signal, Loss of Frame and Signal Degrade and communicating that condition to each node connected to said each link.

20. The method according to claim 17 wherein the step of routing traffic over the pre-computed path comprises the steps of:

originating a request to effect automatic switching at a first endpoint node to route traffic on an available restoration channel able to carry traffic;

passing the automatic switching request from the first end-point node to a first intermediate node in the pre-computed path that receives the request on a working channel and thereafter passes the request without action to a subsequent node when the restoration channel identified by the pre-computed path is a path of an original path traversing that first intermediate node;

otherwise,

bridging, at the first intermediate node an incoming channel to an outgoing channel in response to a request on the working channel when outgoing channel is not a part of the original path;

but

connecting an incoming channel at an intermediate node to an outgoing restoration channel in response to a request on a restoration channel when no channel is part of the original path.

21. The restoration method according to claim 17 further including the steps of:

(a) determining, after implementation of each pre-computed path, whether there exist any links in failure, and if so;

(b) communicating to a restoration path control system, the links still in failure;

(c) determining additional pre-computed paths, each corresponding to a link still in failure; and

(d) downloading said additional pre-computed paths to each pair of end point nodes whose connecting path contains a link still in failure.

22. The method according to claim 17 further including the steps of:

(a) determining when a failed working channel on a link is returned to service; and

(b) switching traffic back onto the link returned to service.

23. The method according to claim 20 wherein the originating request is communicated on an unused portion of an overhead data block in the traffic traversing the network.