Techniques for determining local repair paths using CSPF

1. A method comprising:

identifying, by a network device, for a connection having a first path traversing a plurality of nodes from an ingress node to an egress node, a start node and an end node from the plurality of nodes, wherein the end node is downstream to the start node in the first path; and

determining, by the network device, a second path from the start node to the end node;

wherein the determining comprises:

identifying a first list of nodes comprising nodes in the first path that are upstream from the start node; and

performing processing to ensure that the second path does not traverse a path from a first node in the first list to a second node in the first list wherein the second node is downstream from the first node in the first path;

wherein performing processing comprises:

determining if a first candidate node identified for inclusion in the second path is included in a second list of nodes;

rejecting the first candidate node as a node for the second path upon determining that the first candidate node is included in the second list of nodes; and

including the first candidate node as a node in the second path upon determining that the first candidate node is not included in the second list of nodes.

2. The method of claim 1 wherein determining the second path comprises determining the second path using a constraint shortest path first (CSPF) technique.

3. The method of claim 1 wherein performing processing further comprises, upon determining that the first candidate node is not included in the second list of nodes:

determining if the first candidate node is included in the first list;

if the first candidate node is included in the first list, identifying a set of nodes in the first list that are downstream from the first candidate node in the first path; and

updating the second list to include the set of nodes.

4. The method of claim 3 wherein performing processing further comprises:

determining if a second candidate node identified for inclusion in the second path is included in the updated second list of nodes;

rejecting the second candidate node as a node for the second path upon determining that the second candidate node is included in the updated second list of nodes; and

including the second candidate node as a node in the second path upon determining that the second candidate node is not included in the updated second list of nodes.

5. The method of claim 1 wherein the end node is at least two nodes downstream from the start node in the first path.

6. The method of claim 1 further comprising signaling a local repair connection using the second path.

7. The method of claim 1 wherein the second list of nodes comprises at least one node selected from the first list of nodes and inserted into the second list of nodes.

8. A system comprising:

a memory configured to store information for a first path traversing a plurality of nodes from an ingress node to an egress node; and

a processing module configured to:

identify, for a second path, a start node from the plurality of nodes and an end node from the plurality of nodes, wherein the end node is downstream to the start node in the first path;

identify a first list of nodes comprising nodes in the first path that are upstream from the start node; and

perform processing to ensure that the second path does not traverse a path from a first node in the first list to a second node in the first list wherein the second node is downstream from the first node in the first path, the processing comprising:

determining if a first candidate node identified for inclusion in the second path is included in a second list of nodes;

rejecting the first candidate node as a node for the second path upon determining that the first candidate node is included in the second list of nodes; and

including the first candidate node as a node in the second path upon determining that the first candidate node is not included in the second list of nodes.

9. The system of claim 8 wherein the processing module is configured to determine the second path using a constraint shortest path first (CSPF) technique.

10. The system of claim 8 wherein the processing module, upon determining that the first candidate node is not included in the second list of nodes, is configured to:

determine if the first candidate node is included in the first list;

if the first candidate node is included in the first list, identify a set of nodes in the first list that are downstream from the first candidate node in the first path; and

update the second list to include the set of nodes.

11. The system of claim 10 wherein the processing module is configured to:

determine if a second candidate node identified for inclusion in the second path is included in the updated second list of nodes;

reject the second candidate node as a node for the second path upon determining that the second candidate node is included in the updated second list of nodes; and

include the second candidate node as a node in the second path upon determining that the second candidate node is not included in the updated second list of nodes.

12. The system of claim 8 wherein the end node is at least two nodes downstream from the start node in the first path.

13. The system of claim 8 wherein the processing module is configured to signal a local repair connection using the second path.

14. The system of claim 8 wherein the second list of nodes comprises at least one node selected from the first list of nodes and inserted into the second list of nodes.

15. A computer-readable memory storing a plurality of instructions for controlling a processor to determine a local repair path for a connection, the connection having a first path traversing a plurality of nodes from an ingress node to an egress node, the plurality of instructions comprising:

instructions that cause the processor to identify a start node and an end node from the plurality of nodes, wherein the end node is downstream to the start node in the first path; and

instructions that cause the processor to determine a second path from the start node to the end node;

wherein the instructions that cause the processor to determine the second path comprise:

instructions that cause the processor to identify a first list of nodes comprising nodes in the first path that are upstream from the start node; and

instructions that cause the processor to perform processing to ensure that the second path does not traverse a path from a first node in the first list to a second node in the first list wherein the second node is downstream from the first node in the first path;

wherein the instructions that cause the processor to perform processing to ensure that the second path does not traverse a path from a first node in the first list to a second node in the first list comprise:

instructions that cause the processor to determine if a first candidate node identified for inclusion in the second path is included in a second list of nodes;

instructions that cause the processor to reject the first candidate node as a node for the second path upon determining that the first candidate node is included in the second list of nodes; and

instructions that cause the processor to include the first candidate node as a node in the second path upon determining that the first candidate node is not included in the second list of nodes.

16. The computer-readable memory of claim 15 wherein the instructions that cause the processor to determine the second path comprise instructions that cause the processor to determine the second path using a constraint shortest path first (CSPF) technique.

17. The computer-readable memory of claim 15 wherein the instructions that cause the processor to perform processing comprise instructions that cause the processor to, upon determining that the first candidate node is not included in the second list of nodes:

determine if the first candidate node is included in the first list;

if the first candidate node is included in the first list, identify a set of nodes in the first list that are downstream from the first candidate node in the first path; and

update the second list to include the set of nodes.

18. The computer-readable memory of claim 17 wherein the instructions that cause the processor to perform processing further comprise:

instructions that cause the processor to determine if a second candidate node identified for inclusion in the second path is included in the updated second list of nodes;

instructions that cause the processor to reject the second candidate node as a node for the second path upon determining that the second candidate node is included in the updated second list of nodes; and

instructions that cause the processor to include the second candidate node as a node in the second path upon determining that the second candidate node is not included in the updated second list of nodes.

19. The computer-readable memory of claim 15 wherein the end node is at least two nodes downstream from the start node in the first path.

20. The computer-readable memory of claim 15 wherein the plurality of instructions further comprises instructions that cause the processor to signal a local repair connection using the second path.

21. The computer-readable memory of claim 15 wherein the second list of nodes comprises at least one node selected from the first list of nodes and inserted into the second list of nodes.

22. A method comprising:

determining, by a network device, a second path from a start node to an end node, wherein the start and end nodes are from a plurality of nodes traversed by a first path and the end node is downstream from the start node in the first path; and

wherein the determining comprises:

identifying a first node included in the second path, wherein the first node is in the first path and is upstream from the start node in the first path; and

performing processing to ensure that the second path does not traverse a path from the first node to a second node in the plurality of nodes wherein the second node is upstream from the start node in the first path and the second node is downstream from the first node in the first path, the processing comprising:

determining if a first candidate node identified for inclusion in the second path is included in a second list of nodes;

rejecting the first candidate node as a node for the second path upon determining that the first candidate node is included in the second list of nodes; and

including the first candidate node as a node in the second path upon determining that the first candidate node is not included in the second list of nodes.

23. A system comprising:

a memory configured to store information for a first path traversing a plurality of nodes; and

a processing module configured to:

determine, for a second path, a start node and an end node, wherein the start and end nodes are from the plurality of nodes and the end node is downstream from the start node in the first path;

identify a first node included in the second path, wherein the first node is in the first path and is upstream from the start node in the first path; and

perform processing to ensure that the second path does not traverse a path from the first node to a second node in the plurality of nodes wherein the second node is upstream from the start node in the first path and the second node is downstream from the first node in the first path, the processing comprising:

determining if a first candidate node identified for inclusion in the second path is included in a second list of nodes;

rejecting the first candidate node as a node for the second path upon determining that the first candidate node is included in the second list of nodes; and

including the first candidate node as a node in the second path upon determining that the first candidate node is not included in the second list of nodes.