Patent ID: 8599681

Claim:
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 such that the second path does not traverse a path from a first node in the plurality of nodes to a second node in the plurality of nodes wherein the first node and second nodes are upstream from the start node in the first path and the second node is downstream from the first node in the first path; wherein determining the second path comprises: identifying a first list of nodes comprising one or more nodes in the first path that are upstream from the start node; maintaining a second list of nodes comprising one or more nodes in the first path to be excluded from inclusion in the second path; identifying a first candidate node for inclusion in the second path; determining if the first candidate node is in the second list of nodes; not including the first candidate node in the second path upon determining that the first candidate node is in the second list of nodes; and including the first candidate node in the second path upon determining that the first candidate node is not in the second list of nodes.