Method and apparatus for automatic protection switching

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 36

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.

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.

Claim 43

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.

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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.