LOOP DETECTION AND REPAIR IN A MULTICAST TREE

• US 20150124587A1
• Filed: 07/11/2014
• Published: 05/07/2015
• Est. Priority Date: 11/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Pani, Ayaskant
• Granted Patent: US 9,698,994 B2
• Time in Patent Office: Days
• US Class Current: 370/221
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 45/563 Software download or update
• CPC Class Codes: H04L 49/604 Hybrid IP/Ethernet switches
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses

Abstract

Systems, methods and transitory computer-readable storage media for detecting one or more loops in a multicast tree. The method includes calculating a multicast tree radius for a first multicast tree, the multicast tree radius representing a maximum number of hops from a root node to a furthest edge node in the first multicast tree, forwarding, by the root node, a first packet to each edge node within the first multicast tree, the first packet having a time-to-live (TTL) value equal to twice the first multicast tree radius, receiving, at the root node, a copy of the forwarded first packet, and determining an existence of a loop in the first multicast tree based at least upon receiving the copy of the forwarded first packet.

Claims

1. A method comprising:

calculating a multicast tree radius for a first multicast tree, the multicast tree radius representing a maximum number of hops from a root node to a furthest edge node in the first multicast tree;

forwarding, by the root node, a first packet to each edge node within the first multicast tree, the first packet having a time-to-live (TTL) value equal to twice the first multicast tree radius;

receiving, at the root node, a copy of the forwarded first packet; and

determining an existence of a loop in the first multicast tree based at least upon receiving the copy of the forwarded first packet.

2. The method of claim 1, wherein determining the existence of a loop in the first multicast tree further comprises receiving a notification from a particular edge node in the first multicast tree, the notification indicating that the particular edge node detected the TTL value of the first packet equal to zero.

3. The method of claim 1, further comprising:

forwarding, by the root node, a second packet to each edge node within a second multicast tree, the second packet having a TTL value equal to twice a second multicast tree radius, the second packet having a signature different from the first packet; and

determining an existence of a loop in the second multicast tree by receiving, at the root node, a copy of the forwarded second packet.

4. The method of claim 3, wherein determining the existence of a loop in the first multicast tree occurs simultaneously with determining the existence of the loop within the second multicast tree.

5. The method of claim 1, further comprising forwarding, by the root node, a label switched path (LSP) packet indicating the existence of at least one loop within the first multicast tree.

6. The method of claim 2, wherein the particular edge node is isolated from the first multicast tree upon detection of the loop.

7. The method of claim 6, wherein upon detection of the loop, further comprising reconverging all remaining edge nodes with the root node after the particular edge node is isolated from the first multicast tree.

8. A system comprising:

at least one edge node; and

a root node in communication with the at least one edge node, the root node and the at least one edge node forming a first multicast tree, the root node configured to;

calculate a multicast tree radius for the first multicast tree, the multicast tree radius representing a maximum number of hops from the root node to a furthest edge node in the first multicast tree;

forward a first packet to each edge node within the first multicast tree, the first packet having a time-to-live (TTL) value equal to twice the multicast tree radius for the first multicast tree;

receive a copy of the forwarded first packet; and

determine an existence of a loop in the first multicast tree based at least upon receiving the copy of the forwarded first packet.

9. The system of claim 8, wherein the root node further determines the existence of a loop in the first multicast tree by being configured to receive a notification from a particular edge node in the first multicast tree, the notification indicating that the particular edge node detected the TTL value of the first packet equal to zero.

10. The system of claim 9, wherein the root node is further configured to:

forward a second packet to each edge node within a second multicast tree, the second packet having a TTL value equal to twice the second multicast tree radius, the second packet having a signature different from the first packet; and

determine an existence of a loop in the second multicast tree by receiving a copy of the forwarded second packet.

11. The system of claim 10, wherein determining the existence of a loop in the first multicast tree occurs simultaneously with determining the existence of the loop within the second multicast tree.

12. The system of claim 8, wherein the root node is further configured to forward a label switched path (LSP) packet indicating the existence of at least one loop within the first multicast tree.

13. The system of claim 9, wherein the particular edge node is isolated from the first multicast tree upon detection of the loop.

14. The system of claim 13, wherein the root node is further configured to reconverge all remaining edge nodes with the root node after the particular edge node is isolated from the first multicast tree.

15. The system of claim 8, wherein each edge node that receives the first packet, forwards the first packet to at least one other node in the multicast tree.

16. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:

calculating a multicast tree radius for a first multicast tree, the multicast tree radius representing a maximum number of hops from a root node to a furthest edge node in the first multicast tree;

forwarding a first packet to each edge node within the first multicast tree, the first packet having a time-to-live (TTL) value equal to twice the first multicast tree radius;

receiving a copy of the forwarded first packet; and

determining an existence of a loop in the first multicast tree based at least upon receiving the copy of the forwarded first packet.

17. The non-transitory computer-readable storage medium of claim 16, storing additional instructions which, when executed by the processor, result in operations further comprising determining the existence of a loop in the first multicast tree by receiving a notification from a particular edge node in the first multicast tree, the notification indicating that the particular edge node detected the TTL value of the first packet being equal to zero.

18. The non-transitory computer-readable storage medium of claim 17, storing additional instructions which, when executed by the processor, result in operations further comprising:

forwarding a second packet to each edge node within a second multicast tree, the second packet having a TTL value equal to twice the second multicast tree radius, the second packet having a signature different from the first packet; and

determining an existence of a loop in the second multicast tree by receiving a copy of the forwarded second packet.

19. The non-transitory computer-readable storage medium of claim 18, wherein determining the existence of a loop in the first multicast tree occurs simultaneously with determining the existence of the loop within the second multicast tree.

20. The non-transitory computer-readable storage medium of claim 17, storing additional instructions which, when executed by the processor, result in operations further comprising, upon detection of the loop, reconverging all remaining edge nodes with the root node after the particular edge node is isolated from the first multicast tree.