Technique for breaking loops in a communications network

• US 7,969,898 B1
• Filed: 03/09/2007
• Issued: 06/28/2011
• Est. Priority Date: 03/09/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vaithilingam, Prabhu, Raj, Alex, Thomas, Robert H., Charny, Anna
• Primary Examiner(s): Hoang; Thai D
• Application Number:
  US11/716,055
• Time in Patent Office: 1,572 Days
• Field of Search: 370/225, 370241-252
• US Class Current: 370/248
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• 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/18 Loop-free operations
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A technique for breaking a loop caused by looping alternate paths associated with a prefix in a communications network. One or more non-looping alternate paths associated with the prefix that exclude a first node in the communications network are identified. One or more alternate paths from nodes in the loop that are associated with the prefix are identified. An identified path that intersects with an identified non-looping path is established as an alternate path associated with the prefix at a node in the loop.

Claims

1. A method for breaking a loop formed from looping alternate paths associated with a prefix, the method comprising:

identifying, with a processor at a first node, at least one non-looping alternate path associated with the prefix in response to detection of the loop at the first node, the at least one non-looping alternate path being for a second node and excluding the first node, the first and second nodes being in a communications network, the prefix being for routing of network traffic in the communications network;

transmitting a loop break message from the first node to a third node in response to identifying the at least one non-looping alternate path for the second node at the first node, the third node being in the loop, the loop break message comprising the at least one non-looping alternate path for the second node and an identity of each node in the loop; and

setting a non-routed path associated with the prefix at the third node that intersects the at least one non-looping alternate path as a replacement alternate path for the third node in response to receipt of the loop break message at the third node.

2. The method of claim 1 wherein transmitting the loop break message comprises transmitting the loop break message to all nodes in the loop.

3. The method of claim 1 further comprising forwarding the loop break message at each node in the loop to a next one of the nodes in the loop until a last node in the loop is reached.

4. The method of claim 1 wherein the non-routed path is neither a normal routed path for the third node nor an alternate path for the third node.

5. An apparatus that breaks a loop of looping alternate paths associated with a prefix, the apparatus comprising:

a memory; and

a processor configured to execute instructions stored in the memory, the memory comprising;

instructions executable with the processor to receive a loop break message from a first node in a communications network in response to detection of the loop at the first node, the loop break message comprising at least one non-looping alternate path associated with the prefix and an identity of each node in the loop, the at least one non-looping alternate path being for a second node, wherein the at least one non-looping alternate path is non-looping due to an exclusion of the first node, the apparatus is in the loop, and the second node is outside of the loop; and

instructions executable with the processor to set a non-routed path that intersects the at least one non-looping alternate path of the second node as a replacement alternate path of the apparatus, the replacement alternate path being associated with the prefix in the memory.

6. The apparatus of claim 5, wherein the prefix is an Internet Protocol (IP) address.

7. The apparatus of claim 5, further comprising instructions executable with the processor to select the non-routed path that intersects the at least one non-looping alternate path from a plurality of non-routed paths.

8. The apparatus of claim 5, wherein the non-routed path is neither a normal routed path for the third node nor an alternate path for the third node.

9. The apparatus of claim 5, further comprising instructions executable with the processor to notify nodes neighboring the apparatus of the replacement alternate path.

10. The apparatus of claim 5, further comprising instructions executable with the processor to forward the loop break message to the first node in response to the apparatus being a last node in the loop to receive the loop break message.

11. A first node in a communications network, the first node comprising:

a network interface in communication with the communications network; and

a supervisor engine configured to;

detect a loop of looping alternate paths from alternative path information received over the network interface from a plurality of nodes in the communications network;

identify at least one non-looping alternate path associated with the prefix from the alternative path information in response to detection of the loop, the at least one non-looping alternate path being for a second node in the communications network and being non-looping due to a failure to include the first node;

transmit a loop break message from the first node to a third node in response to detection of the loop at the first node, the third node being in the loop, the loop break message comprising the at least one non-looping alternate path and an identity of each node in the loop;

receive the loop break message from a last node in the loop; and

determine whether the loop is broken from the loop break message.

12. The first node of claim 11 wherein the loop break message includes an indicator of whether the loop is broken.

13. The first node of claim 11 wherein the loop break message includes a replacement alternative path for at least one node in the loop to indicate the loop is broken, and the replacement alternative path intersects one of the at least one non-looping alternate path.

14. A first node in a communications network, the first node comprising:

a network interface that communicates with the communications network; and

a supervisor engine comprising circuitry configured to;

detect a loop of looping alternate paths from alternate path information received over the network interface from a plurality of nodes in the communications network;

identify at least one non-looping alternate path associated with the prefix from the alternate path information in response to detection of the loop, the at least one non-looping alternate path being for a second node in the communications network and being non-looping due to a failure to include the first node;

transmit a loop break message from the first node to a third node over the network interface in response to identification of the at least one non-looping alternate path, the third node being in the loop, the loop break message comprising an identity of each node in the loop;

receive a non-routed path associated with the prefix from the third node over the network interface in response to receipt of the loop break message by the third node;

determine the non-routed path intersects the at least one non-looping alternate path; and

notify the third node to set the non-routed path to a replacement alternate path for the third node.