Method and apparatus for automatic protection switching

• US 6,728,205 B1
• Filed: 02/04/1998
• Issued: 04/27/2004
• Est. Priority Date: 02/19/1997
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Medard, Muriel, Barry, Richard A., Finn, Steven G.
• Primary Examiner(s): Jung, Min
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/018,354
• Time in Patent Office: 2,274 Days
• Field of Search: 370/217, 370/216, 370/241, 370/224, 370/249, 370/256, 370/248, 370/258, 370/400, 370/406, 370/408, 370/410, 370/242, 370/244, 370/221, 370/351, 370/389, 370/392, 370/254, 345/440, 716/10, 709/220, 709/200, 709/221, 709/223, 709/224, 709/225, 709/226, 709/229, 709/238, 709/239, 714/1, 714/2, 714/776, 714/712, 714/716
• US Class Current: 370/217
• 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/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A Bi-directional Link Self-healing Network (BLSN) for implementing bi-directional link automatic protection switching (APS) for an arbitrary edge or node redundant network and a technique for implementing APS recovery in response to an edge or node failure in a network is described. The BLSN technique does not require permanent allocation of spare capacity for each connection and allows sharing of capacity among many network connections by allocating capacity for use only in the event of a failure. The described technique allows loopback protection to be performed over node or edge redundant networks and operates such that the remains connected after the failure of a node or an edge in the network. The technique makes use of connected directed subgraphs of the network. Also described are techniques for generating the directed subgraphs on node and edge redundant networks having an arbitrary network topology.

Claims

1. An apparatus for implementing bi-directional link automatic protection switching for an arbitrary node or edge redundant network comprising:

a. means for representing a network as an undirected graph having a predetermined number of nodes and a predetermined number of edges;

b. means for generating at least one bi-directional link self-healing network (BLSN) subgraph for a node redundant network;

c. means for generating at least one BLSN subgraph for a network which can be represented as an edge redundant graph;

d. means for routing traffic connection requests over the BLSN subgraphs to provide automatic protection switching;

e. means for detecting a failure in the network;

f. means, responsive to said means for detecting a failure, for implementing automatic protection switching wherein in response to detection of an edge failure by said means for detecting, said means for implementing automatic protection switching implements automatic protection switching for an edge failure and in response to detecting a node failure by said means for detecting, said means for implementing automatic protection switching implements automatic protection switching for a node failure.

2. The apparatus of claim 1 wherein said means for generating at least one BLSN subgraph for a node redundant network which can be represented as a node redundant graph comprises:

(1) means for selecting a first edge from an undirected graph having a plurality of nodes and a plurality of edges with each of the edges having a predetermined length capacity;

(2) means for selecting a first cycle which includes the first edge;

(3) means for assigning node values to each node in the first cycle in accordance with a predetermined criteria to define a directed subgraph having a second plurality of nodes and a second plurality of arcs;

(4) means for determining whether the subgraph includes all nodes to be connected;

(5) means for selecting a path having a starting node and an ending node already included in the cycle but which includes at least one intermediate node not already included in the cycle or any path on which no values are already assigned in response to the means for determining whether the subgraph includes all nodes to be connected determines that the subgraph does not include all nodes to be connected;

(6) means for assigning node values to each of the at least one intermediate nodes in the path selected by the means for selecting a path, wherein the node values are assigned in accordance with a predetermined criteria to define a new directed subgraph having a third plurality of nodes and a third plurality of arcs.

3. The apparatus of claim 1 wherein said means for generating at least one BLSN subgraph for an edge redundant network which can be represented as an edge redundant graph comprises:

(1) means for selecting a cycle on a subgraph;

(2) means for selecting a direction for the cycle;

(3) means for determining whether some nodes are not yet reached by any path or cycle;

(4) means for choosing a next path or a next cycle in response to some nodes not yet being reached by any path or cycle; and

(5) means for selecting a direction for the path or cycle selected by the means for choosing a next path or a next cycle.

4. The apparatus of claim 1 wherein said means for implementing automatic protection switching comprises:

(1) means for identifying a failed edge between a first node and second node in an edge redundant network;

(2) means for identifying a first arc between the first node and the second node, the first arc existing in a first subgraph;

(3) means for identifying a second arc between the first node and the second node, the second arc having a direction which is different than the direction of the first arc and the second arc existing in a second subgraph; and

(4) means for generating a pair of looping arcs such that signals which arrive for transmission on the first arc in the first subgraph are looped back to a first one of the first and second nodes along the second arc in the second subgraph.

5. A method for generating one or more Bi-directional Link Self-healing Network subgraphs comprising the steps of:

(a) representing a network as an undirected graph having nodes andedges;

(b) identifying bi-directional capacity of each edge in the undirected graph;

(c) generating a bi-directional subgraph;

(d) generating two directed subgraphs which can provide loopback recovery for selected nodes in the undirected graph; and

(e) reducing capacity on each edge used in the subgraphs by sharing capacity among multiple connections to provide a remaining network.

6. The method of claim 5 further comprising in the steps of:

(f) determining if network requirements are satisfied;

(g) in response to the network requirements not being satisfied, performing the step of determining if the remaining network has redundant portions.

7. The method of claim 6 wherein in response to the remaining network having redundant portions performing the steps of:

(h) generating a next subgraph from the remaining network; and

(i) repeating steps (d)-(f) until a first one of the following conditions is met;

(1) network requirements are satisfied; and

(2) the remaining network does not have any redundant portions.

8. A method for generating a directed subgraph from a network which can be represented as an edge redundant graph comprising the steps of:

(a) selecting a cycle on a subgraph;

(b) selecting a direction for the cycle;

(c) determining whether some nodes are not yet reached by any path or cycle;

(d) in response to some nodes not yet being reached by any path or cycle choosing a next path or a next cycle; and

(e) selecting a direction for the path or cycle selected in step (d).

9. The method of claim 8 further comprising the steps of repeating steps (c)-(e) until all nodes are reached by a path or cycle.

10. A method for generating a directed subgraph in a network which can be represented as node redundant graph comprising the steps of:

(a) selecting a first edge from an undirected graph having a plurality of nodes and a plurality of edges with each of the edges having a predetermined length capacity;

(b) selecting a first cycle which includes the first edge;

(c) assigning node values to each node in the first cycle in accordance with a predetermined criteria to define a directed subgraph having a second plurality of nodes and a second plurality of arcs;

(d) determining whether the directed subgraph includes all nodes to be connected; and

(e) in response to the directed subgraph not including all nodes to be connected, performing the steps of;

(1) selecting a path having a starting node and an ending node already included in the directed subgraph but which includes at least one node not already included in the directed subgraph; and

(2) assigning node values to each of the at least one intermediate nodes in the path in accordance with a predetermined criteria to define a new directed subgraph having a further plurality of nodes and a further plurality of arcs.

11. The method of claim 10 wherein in response to determining that the directed subgraph includes all nodes to be connected performing the steps of:

accepting the directed subgraph and defining a reverse subgraph; and

reducing the capacity of each of the edges remaining in the undirected graph.

12. The method of claim 11 further comprising the steps of repeating steps (d) and (e) until a first one of:

the directed subgraph includes all nodes to be connected; and

the undirected graph does not have any redundant portions.

13. A method for routing traffic on a Bi-directional Link Self-healing Network (BLSN) subgraph comprising the steps of:

(a) selecting a connection to be routed in accordance with a predetermined criteria;

(b) determining if there exists a tree on any subgraph which can route the selected connection; and

(c) in response to the existing a tree on a subgraph which can route the selected connection, performing the steps of;

(1) routing the connection over the selected tree;

(2) marking all intermediate nodes to indicate that the nodes are utilized in the selected circuit for the selected tree; and

(3) deleting edges of the tree from the list of available edges in the subgraph.

14. The method of claim 13 wherein in response to determining that there does not exist a tree on any subgraph which can route the selected connection, then performing the steps of:

(1) indicating that the selected connection is blocked; and

(2) determining whether there are any connections remaining which has not been either routed or blocked.

15. The method of claim 14 wherein in response to determining that there are connections remaining which have not been either routed or blocked then performing the steps of:

selecting another connection to be routed; and

repeating steps (b) and (g) until there are no connections remaining which have not been either routed or blocked.

16. A method for recovering from a single link failure or a single node failure using help messages, the method comprising the steps of:

detecting, at a node, a first one of a link failure and a node failure;

broadcasting, from the node, a help message on all outbound arcs of the node, wherein the outbound arcs include outbound arcs on a primary subgraph and a secondary subgraph;

receiving data on an inbound arc of a secondary subgraph at a node;

in response to the receiving data on an inbound arc of the secondary subgraph at the node, determining whether outbound arcs of the secondary subgraph at the node are idle; and

in response to the outbound arcs of the secondary subgraph at the node being idle, broadcasting the data received on the inbound arc on all outbound arcs of the secondary subgraph at the node.

17. A method for recovering from a failure without a help message comprising the steps of:

(a) detecting a failure at a node;

(b) selecting a circuit to be checked;

(c) determining if the selected circuit is routed over the failed link; and

(d) in response to the selected circuit being routed over the failed link performing the steps of;

(1) defining a graph over which the circuit was routed;

(2) initiating loopback on the failed link on an undirected subgraph;

(3) determining if the node on the other side of the failed link is an intermediate node;

(i) in response to the node on the other side of the failed link corresponding to an intermediate node performing the steps of setting a flag in a failure message to indicate whether the node is or is not an intermediate node; and

(4) sending a failure message on all operational outbound links on a secondary graph from the node detecting the failure.

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

(e) determining if all circuits have been checked;

(f) in response to all circuits not having been checked, then performing the step of selecting the next circuit to be checked; and

(g) repeating steps (c) and (d) until all circuits have been checked.

19. A method for restoring a connection between a pair of nodes comprising the steps of:

(a) receiving a help message at a node on an arc;

(b) determining if the help message is new;

(c) determining if the help message originated at the node;

(d) in response to the help message being new and not originating at the node, forwarding a help message on all operational outgoing arcs of the node;

(e) determining whether the node has any failed links;

(f) in response to the node having a failed link, determining if a circuit referred to in the help message uses the failed link; and

(g) in response to the failed link under consideration being used on the circuit for which the node received the help message, performing the step of looping back on the failed link at the node to provide a signal path restoring the connection.

20. The method of claim 19 wherein the first node is a first one of a plurality of nodes and the method further comprises the steps of repeating steps (a)-(g) for each of the plurality of nodes.

21. The method of claim 20 wherein the help message includes an indicator which identifies a circuit.

22. The method of claim 21 wherein the step of looping back on the failed link at the node includes the steps of:

identifying a failed edge between the node and a second node;

identifying a first arc between the node and the second node, the first arc existing in a first subgraph corresponding to the subgraph over which the circuit is routed;

identifying a second arc between the first node and the second node, the second arc having a direction which is different than the direction of the first arc and the second arc existing in a second subgraph; and

generating a looping arc such that signals which arrive for transmission on the first arc in the first subgraph are looped back to a first one of the first and second nodes along the second arc in the second subgraph.