Method and apparatus for automatic protection switching

• US 6,047,331 A
• Filed: 02/19/1997
• Issued: 04/04/2000
• Est. Priority Date: 02/19/1997
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Barry, Richard A., Gallager, Robert G., Medard, Muriel, Finn, Steven G.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US08/803,169
• Time in Patent Office: 1,140 Days
• Field of Search: 364/DIG. 1 MS File, 364/DIG. 2 MS File, 395/200.3, 395/200.48, 395/200.5, 395/200.51, 395/200.52, 395/200.53, 395/200.69, 395/200.82, 395/200.81, 370/216, 359/118, 359/168
• US Class Current: 709/239
• 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: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• 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 method and apparatus for generating first and second tree topologies for any source node in a network which can be represented as a node or an edge redundant graph, such that any node in the graph remains connected to the source node via at least one tree even after the failure of a node or an edge. This technique provides a recovery mechanism upon detection of a failure in a network.

Claims

1. A method of establishing at least a pair of paths between a source node and a destination node in a network including a plurality of nodes, the method comprising the steps of:

(a) selecting a source node;

(b) selecting a cycle around the source node, wherein the cycle includes a source node a first plurality of nodes;

(c) assigning a first source node value to the source node;

(d) assigning a second different source node value to the source node;

(e) assigning a node value to each of the first plurality of nodes wherein the node value assigned to each node decreases in a first direction around the cycle;

(f) constructing a first set of arcs each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than the node value of the downstream node; and

(g) constructing a second set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than the node value of the downstream node.

2. The method of claim 1 further comprising the steps of:

determining if the first plurality of nodes in the cycle includes each of the plurality of nodes in the network;

in response to the first plurality of nodes in the cycle not including each of the plurality of nodes in the network then performing the steps of;

(1) selecting a first path having a starting node, an ending node and at least one intermediate node wherein the starting node corresponds to one of the first plurality of nodes in the cycle, the ending node corresponds to a second different one of the first plurality of nodes in the cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the cycle and wherein the value of the starting node is greater than the value of the ending node; and

(2) assigning a node value to each of the at least one intermediate nodes wherein the node values assigned to each of the at least one intermediate nodes do not increase when traversing the first path in a direction from the starting node to the ending node.

3. The method of claim 2 wherein the step of assigning a node value to each of the at least one intermediate nodes comprises the step of:

assigning the intermediate node immediately prior to the ending node a value which is greater than the maximum of;

(i) the second value of the source node; and

(ii) the value of any node included in the cycle and the path and already assigned a value which is smaller than the value of the starting node.

4. The method of claim 3 further comprising the steps of:

constructing a first set of arcs on the first path, each of the arcs linking an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than the node value of the downstream node; and

constructing a second set of arcs on the first path, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than the node value of the downstream node.

5. The method of claim 4 wherein:

the first source node value is greater than the second source node value; and

a first one of the starting node and ending node corresponds to the source node and wherein in response to the source node corresponding to the starting node, the starting node is provided having the first source node value and in response to the ending node corresponding to the source node, the ending node is provided having the second source node value.

6. A method of establishing at least a pair of paths between a source node and a destination node in a network including a plurality of nodes, the method comprising the steps of:

(a) selecting a source node;

(b) selecting a first cycle around the source node, wherein the first cycle includes a first plurality of nodes;

(c) assigning first and second source values to the source node;

(d) assigning first and second node values to each of the first plurality of nodes wherein first ones of the first and second node values assigned to each node do not increase in value in a first direction around the first cycle and second ones of the first and second node values assigned to each node do not increase in value in the first direction around the first cycle and wherein for each node the first node value is greater than the second node value;

(e) constructing a first set of arcs, each of the arcs linking an upstream node and a downstream node in the first cycle, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

(f) constructing a second set of arcs, each of the arcs connecting an upstream node and a downstream node in the first cycle, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

7. The method of claim 6 further comprising the steps of:

determining if the first plurality of nodes in the first cycle includes each of the plurality of nodes in the network;

in response to the first plurality of nodes in the first cycle not including each of the plurality of nodes in the network then performing the steps of;

(1) selecting a first one of a path or a second cycle;

(2) in response to the selection of a path performing the steps of;

(a) selecting a first path having a starting node, an ending node and at least one intermediate node wherein the starting node corresponds to one of the first plurality of nodes in the cycle, the ending node corresponds to a second different one of the first plurality of nodes in the cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the cycle and wherein the first value of the starting node is greater than the first value of the ending node; and

(b) assigning first and second node values to each of the at least one intermediate nodes wherein first ones of the node values assigned to each of the at least one intermediate nodes do not increase in value when traversing the path in a direction from the starting node to the ending node and wherein second ones of the node values assigned to each of the at least one intermediate nodes do not increase in value when traversing the path in a direction from the starting node to the ending node and wherein for each intermediate node the first node value is greater than the second node value;

(3) in response to the selection of a cycle performing the steps of;

(a) selecting a second cycle having a second source node and at least one intermediate node wherein the second source node corresponds to one of the first plurality of nodes in the first cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the first cycle; and

(b) assigning a node value to each of the at least one intermediate nodes wherein first ones of the first and second node values assigned to each of the at least one intermediate nodes do not increase in value in a first direction around the second cycle and second ones of the first and second node values assigned to each node do not increase in value in the first direction around the second cycle and wherein for each intermediate node the first node value is greater than the second node value.

8. The method of claim 7 wherein the step of assigning a node value to each of the at least one intermediate nodes comprises the step of:

assigning the intermediate node adjacent a first one of the end node and the starting node a value which is not less than the maximum of a first one of;

(i) a first one of;

the first value of all of the nodes included in the first cycle and the path having a value which is smaller than the first value of the first node in the path; and

the second value of all of the nodes included in the first cycle and the first path having a value which is smaller than the first value of the first node in the first path;

(ii) a first one of;

the first value of all of the nodes included in the first cycle and the second cycle having a value which is smaller than the value of the second source node in the second cycle; and

the second value of all of the nodes included in the first cycle and the second cycle having a value which is smaller than the first value of the second source node in the second cycle.

9. The method of claim 8 further comprising the steps of:

in response to the selection of a path performing the steps of;

constructing a first set of arcs on the first path, each of the arcs linking an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

constructing a second set of arcs on the first path, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

10. The method of claim 9 wherein:

the first source node value is greater than the second source node value; and

a first one of the starting and ending nodes corresponds to the source node and wherein in response to the source node corresponding to the starting node, the starting node is provided having the first source node value and in response to the ending node corresponding to the source node, the ending node is provided having the second source node value.

11. The method of claim 8 further comprising the steps of:

in response to the selection of a second cycle performing the steps of;

constructing a first set of arcs on the second cycle, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

constructing a second set of arcs on the second cycle, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

12. The method of claim 11 wherein:

the first source node value is greater than the second source node value; and

a first one of the starting and ending nodes corresponds to the source node and wherein in response to the source node corresponding to the starting node, the starting node is provided having the first source node value and in response to the ending node corresponding to the source node, the ending node is provided having the second source node value.

13. A computer program product comprising:

a computer useable medium having computer readable program code to select a source node from a plurality of nodes;

a computer useable medium having computer readable program code to select a cycle around the source node, wherein the cycle includes a first plurality of nodes;

a computer useable medium having computer readable program code to assign a first source value to the source node;

a computer useable medium having computer readable program code to assign a second different source value to the source node;

a computer useable medium having computer readable program code to assign a node value to each of the first plurality of nodes wherein the node value assigned to each node decreases in the first direction around the cycle;

a computer useable medium having computer readable program code to construct a first set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than the node value of the downstream node; and

a computer useable medium having computer readable program code to construct a second set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than the node value of the downstream node.

14. The computer program product of claim 13 further comprising:

a computer useable medium having computer readable program code to determine if the first plurality of nodes in the cycle includes each of the plurality of nodes in the network;

a computer useable medium having computer readable program code to select a first path having a starting node, an ending node and at least one intermediate node wherein the starting node corresponds to one of the first plurality of nodes in the cycle, the ending node corresponds to a second different one of the first plurality of nodes in the cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the cycle and wherein the value of the starting node is greater than the value of the ending node; and

a computer useable medium having computer readable program code to assign a node value to each of the at least one intermediate nodes wherein the node values assigned to each of the at least one intermediate nodes do not increase when traversing the path in a direction from the starting node to the ending node.

15. The computer program product of claim 14 wherein the computer readable program code means to assign a node value to each of the at least one intermediate nodes comprises:

a computer useable medium having computer readable program code to assign the intermediate node immediately prior to the end node a value which is not less than the maximum of;

(i) the second value of the source node and (ii) the value of any node included in the cycle and the path and already assigned a value which is smaller than the value of the starting node.

16. The computer program product of claim 15 further comprising:

a computer useable medium having computer readable program code to construct a first set of arcs on the first path, each of the arcs linking an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than the node value of the downstream node; and

a computer useable medium having computer readable program code to construct a second set of arcs on the first path, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than the node value of the downstream node.

17. A computer program product comprising:

a computer useable medium having computer readable program code to select a source node from a plurality of nodes to be included in a network;

a computer useable medium having computer readable program code to select a first cycle around the source node, wherein the first cycle includes a first plurality of nodes;

a computer useable medium having computer readable program code to assign first and second source node values to the source node;

a computer useable medium having computer readable program code to assign first and second node values to each of the first plurality of nodes wherein first ones of the first and second node values assigned to each node do not increase in value in a first direction around the first cycle and second ones of the first and second node values assigned to each node do not increase in value in the first direction around the first cycle and wherein for each node the first node value is greater than the second node value;

a computer useable medium having computer readable program code to construct a first set of arcs, each of the arcs linking an upstream node and a downstream node in the first cycle, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

a computer useable medium having computer readable program code to construct a second set of arcs, each of the arcs connecting an upstream node and a downstream node in the first cycle, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

18. The computer program product of claim 17 further comprising the steps of:

a computer useable medium having computer readable program code to determine if the first plurality of nodes in the first cycle includes each of the plurality of nodes to be included in the network;

a computer useable medium having computer readable program code to select a first one of a path and a cycle, the computer readable program code to select comprising;

a computer useable medium having computer readable program code to select a first path in having a starting node, an ending node and at least one intermediate node wherein the starting node corresponds to one of the first plurality of nodes in the cycle, the ending node corresponds to a second different one of the first plurality of nodes in the cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the cycle and wherein the first value of the starting node is greater than the first value of the ending node;

a computer useable medium having computer readable program code to assign first and second node values to each of the at least one intermediate nodes wherein first ones of the node values assigned to each of the at least one intermediate nodes do not increase in value when traversing the path in a direction from the starting node to the ending node and wherein second ones of the node values assigned to each of the at least one intermediate nodes do not increase in value when traversing the path in a direction from the starting node to the ending node and wherein for each intermediate node the first node value is greater than the second node value;

a computer useable medium having computer readable program code to select a second cycle having a second source node and at least one intermediate node wherein the second source node corresponds to one of the first plurality of nodes in the first cycle and each of the at least one intermediate nodes correspond to nodes not included in the first plurality of nodes in the first cycle; and

a computer useable medium having computer readable program code to assign first and second node values to each of the at least one intermediate nodes wherein first ones of the first and second node values assigned to each of the at least one intermediate nodes do not increase in value in a first direction around the second cycle and second ones of the first and second node values assigned to each node do not increase in value in the first direction around the second cycle and wherein for each intermediate node the first node value is greater than the second node value.

19. The computer program product of claim 18 wherein the computer useable medium having computer readable program code to assign first and second node values to each of the at least one intermediate nodes comprises:

a computer useable medium having computer readable program code to assign the intermediate node adjacent to a first one of the end node and the starting node a value which is not less than the maximum of a first one of;

(i) a first one of;

the first value of all of the nodes included in the first cycle and the path having a value which is smaller than the first value of the first node in the path; and

the second value of all of the nodes included in the first cycle and path having a value which is smaller than the first value of the first node in the path;

(ii) a first one of;

the first value of all of the nodes included in the first cycle and the second cycle having a value which is smaller than the value of the second source in the second cycle; and

the second value of all of the nodes included in the first cycle and the second cycle having a value which is smaller than the first value of the second node in the second cycle.

20. The computer program product of claim 19 further comprising:

a computer useable medium having computer readable program code to construct a first set of arcs on the first path, each of the arcs linking an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

a computer useable medium having computer readable program code to construct a second set of arcs on the first path, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

21. The computer program product of claim 19 further comprising:

a computer useable medium having computer readable program code to select a first set of arcs along the path between the starting node and the ending node wherein a value of each of the nodes decrease along the direction of the arc; and

a computer useable medium having computer readable program code to select a second set of arcs along the path between the starting node and the ending node wherein a value of each of the nodes increases along the direction of the arcs.

22. The computer program product of claim 19 further comprising:

a computer useable medium having computer readable program code to construct a first set of arcs on the second cycle, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than a node value of the downstream node; and

a computer useable medium having computer readable program code to construct a second set of arcs on the second cycle, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than a node value of the downstream node.

23. The computer program product of claim 19 further comprising:

a computer useable medium having computer useable program code to select a first set of arcs along the path between the starting node and the ending node wherein the value of each of the nodes decrease along the direction of the arc; and

a computer useable medium having computer useable program code to select a second set of arcs along the path between the starting node and the ending node wherein a value of each of the nodes increases along the direction of the arcs.

24. A network comprising:

a plurality of nodes each of the nodes comprising;

means for exchanging network topology information with each of the plurality of nodes;

means for computing a plurality of directed trees wherein at least two of the plurality of directed trees are redundant after failure of a first one of a node and a link; and

means for transmitting the plurality of directed trees computed in each of the nodes to first ones of the plurality of nodes.

25. The network of claim 24 wherein said means for computing a plurality of directed trees includes means for computing a plurality of directed spanning trees.

26. A network comprising:

a plurality of nodes each of the nodes coupled by a link and each of the nodes comprising;

means for transmitting network topology information to a first one of the plurality of nodes;

means for providing traffic information to the first one of the plurality of nodes and wherein the first one of the plurality of nodes comprises;

means for computing a plurality of trees for each of the plurality of nodes and transmitting the tree information from the first one of the plurality of nodes to the remainder of the plurality of nodes wherein at least two of the plurality of directed trees are redundant after failure of a first one of a node and a link.

27. The network of claim 26 wherein said means for computing a plurality of directed trees includes means for computing a plurality of directed spanning trees.

28. A method for generating two directed trees for automatic protection switching comprising the steps of:

selecting a source node having first and second source node values;

selecting a first cycle around the source node, the first cycle including a plurality of nodes;

ordering the plurality of nodes in decreasing order in a first direction around the cycle and in increasing order in a second opposite direction around the cycle;

constructing two sets of arcs;

selecting a first one of a path and a cycle which includes a node not already included in the first cycle; and

ordering any node not already ordered such that a value assigned to each node does not increase in the value when traversing the cycle in the first direction and does not decrease in value when traversing the cycle in the second direction.

29. The method of claim 28 further comprising the steps of:

connecting the arcs included in the first set of arcs to provide a first tree topology; and

connecting the arcs included in the second set of arcs to provide a second different tree topology.

30. A method of providing a network having a plurality of nodes with a logical tree topology, the method comprising the steps of:

(a) selecting a first cycle containing a first plurality of nodes with a first one of the first plurality of nodes corresponding to a first source node;

(b) determining if the first cycle includes all nodes to be included in the network;

(c) in response to the first cycle not including all nodes to be included in the network, then performing the steps of;

(i) selecting a first starting node from the plurality of nodes in the first cycle;

(ii) assigning a first starting node value to the first starting node;

(iii) selecting a first ending node from the plurality of nodes in the first cycle;

(iv) assigning a first ending node value to the first ending node;

(v) selecting a first path between the first starting node and the first ending node which includes at least one intermediate node not included in the first cycle;

(vi) assigning a node value to each of the at least one intermediate nodes.

31. The method of claim 30 further comprising the steps of:

(vii) determining if the first cycle and first path include all of the nodes to be included in the network;

(viii) in response to the first cycle and first path not including all nodes to be included in the network, then performing the steps of;

(a) selecting a next starting node from the plurality of nodes in a first one of the first cycle and first path;

(b) selecting a first ending node from the plurality of nodes in a first one of the first cycle and first path;

(c) selecting a next path between the first starting node and the first ending node which includes at least one node not included in the first cycle and first path; and

(d) repeating steps (a)-(c) until each of the plurality of nodes in the network are included in at least one of a path or a cycle.

32. The method of claim 31 wherein in response to the cycle selected in step (a) including all nodes to be included in the network, the method comprises the steps of:

assigning a first and second source node values to the first source node; and

ordering the nodes in a predetermined order.

33. A network comprising:

a plurality of nodes;

a first plurality of links each of said first plurality of links having a first end coupled to a first one of the plurality of nodes and a second end coupled to a second different one of the plurality of nodes such that the nodes and first plurality of links form a first tree topology; and

a second plurality of links each of said second plurality of links having a first end coupled to a first one of the plurality of nodes and a second end coupled to a second different one of the plurality of nodes such that the nodes and links form a second tree topology and wherein in response to failure of any of the nodes or first or second plurality of links, each of said plurality of nodes remain mutually connected through at least one of said first and second tree topologies.

34. The network of claim 33 wherein at least one of the plurality of nodes comprises an automatic switch protection processor for automatically logically connecting each of the nodes to a first one of the first and second tree topologies.

35. A network planning system comprising:

means for selecting a source node;

means for selecting a cycle around the source node, wherein the cycle includes a source node a first plurality of nodes;

means for assigning a first source node value to the source node;

means for assigning a second different source node value to the source node;

means for assigning a node value to each of the first plurality of nodes wherein the node value assigned to each node decreases in a first direction around the cycle;

means for constructing a first set of arcs each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not less than the node value of the downstream node; and

means for constructing a second set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is not greater than the node value of the downstream node.

36. The network planning system of claim 35 wherein said means for assigning a node value to each of the first plurality of nodes wherein the node value assigned to each node decreases in a first direction around the cycle further comprises means for assigning a second node value to each of the first plurality of nodes wherein the second node value assigned to each node increases in a second opposite direction around the cycle.

37. The network planning system of claim 35 further comprising:

means for receiving network topology information; and

means for connecting the first set of arcs to provide a first logical tree topology and for connecting the second set of arcs to provide a second logical tree topology.

38. A method of generating two directed trees for automatic protection switching in an optical network, the method comprising the steps of:

identifying a source node;

selecting a first cycle containing the source node;

determining if the cycle includes all nodes in a graph;

in response to the cycle not containing all the nodes in a graph, selecting a first path that starts on some node in the first cycle;

determining if the first cycle and first path do not include all the nodes of the graph;

in response to the cycle and path not including all the nodes in the graph, constructing another path starting on some node already included in one of the first cycle and first path and passing through one or more nodes not included in one of the first cycle and first path and ending on another node included in one of the first cycle and first path; and

ordering the nodes in accordance with a predetermined criteria.