Methods and apparatus for minimizing duplicate traffic during point to multipoint tree switching in a network

• US 7,899,049 B2
• Filed: 08/01/2006
• Issued: 03/01/2011
• Est. Priority Date: 08/01/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Raj, Alex E., Thomas, Robert H.
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): KHIRODHAR, MAHARISHI V
• Application Number:
  US11/497,952
• Publication Number:
  US 20080031130A1
• Time in Patent Office: 1,673 Days
• Field of Search: 370/408, 370/389, 370/256, 370/395.1, 370/396, 370/400, 370/406, 370/242, 370/216, 370/395.52, 370/390, 370/432, 709/238, 709/242, 709/252
• US Class Current: 370/390
• 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/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/502 Frame based

Abstract

A method, apparatus and computer program product for minimizing or preventing duplicate traffic during point to multipoint tree switching in a network. In its operation, embodiments disclosed herein utilize control plane trigger mechanisms to handle the receipt of duplicate traffic by network entities after the occurrence of a network failure event. Generally, the control plane trigger mechanism prevents a network entity from processing multicast traffic from both old and new upstream data paths resulting from typical network convergence procedures. The methods and apparatus describe herein apply to standard rerouting procedures as well as fast rerouting procedures for multicast traffic in a network.

Claims

1. A method for minimizing duplicate traffic during point to multipoint (P2MP) tree switching in a network including a P2MP tree with a source node, the method comprising:

receiving multicast data traffic transmitted from a first router over a primary network path to a second router, wherein the primary network path supports multicast label switching of multicast data traffic; and

in response to detecting a failure in the network, receiving the multicast data traffic over a backup label switched path on a secondary network path between the first router and the second router in lieu of receiving the multicast data traffic over the primary network path and minimizing duplicate traffic by initiating a multicast rerouting procedure, the multicast rerouting procedure comprising;

transmitting a new multicast switching label via the secondary network path to an upstream router, the secondary network path including the upstream router between the first router and the second router;

and, upon receiving an acknowledgement notification from the upstream router indicating that the upstream router is a merge point in the P2MP tree, configuring the second router to receive multicast data traffic addressed to the new multicast switching label and transmitted from the upstream router over the secondary network path in lieu of receiving multicast data traffic from the backup label switched path prior to the PSMP tree reaching a convergent state after the failure.

2. A method as in claim 1 wherein initiating the multicast rerouting procedure by transmitting the multicast new switching label via the secondary network path to the upstream router comprises:

initiating the multicast rerouting procedure by implementing a reverse path forwarding procedure.

3. A method as in claim 1 wherein initiating the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprises:

determining whether the upstream router is receiving multicast data traffic, and when the upstream router is receiving multicast data traffic;

adding the new multicast switching label to a routing table at the upstream router, and

transmitting the acknowledgement notification to the second router via the secondary network path.

4. A method as in claim 1 wherein initiating the multicast rerouting procedure by transmitting new multicast switching label via the secondary network path to the upstream router comprises:

determining whether an upstream node on the secondary network path is receiving multicast data traffic, and in response to a determination the upstream node is not receiving multicast data traffic;

transmitting a respective switching label to a next upstream router via the secondary network path in response to a determination the upstream node is not receiving multicast data traffic; and

propagating the acknowledgement notification from the upstream router receiving multicast data traffic to the second router via the secondary network path.

5. A method as in claim 1 wherein initiating the multicast rerouting procedure further comprises:

determining whether the upstream router is the source node of the P2MP tree, and in response to a determination the upstream router is not the source node of the P2MP tree, transmitting a respective switching label to a next upstream router via the secondary network path until the source node of the P2MP tree is reached; and

propagating the acknowledgement notification from the source node of the P2MP tree to the second router via the secondary network path.

6. A method as in claim 1 wherein the configuring the second router to receive multicast data traffic from the secondary network path comprises:

removing, from the second router, a primary switching label that the second router normally uses for receiving multicast data traffic via the primary network path; and

receiving, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.

7. A method as in claim 1 further comprising:

configuring the backup label switched path between the first router and the second router;

in response to detecting the failure in the network, initiating transmission of the multicast data traffic over the backup label switched path between the first router and the second router in lieu of transmitting the multicast data traffic over the primary network path.

8. A method as in claim 7 wherein the configuring the second router to receive multicast data traffic addressed to the new multicast switching label comprises:

removing, from the second router, a backup path switching label that the second router normally uses for receiving multicast data traffic via the backup label switched path;

receiving, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.

9. A tangible computer readable medium having computer readable code thereon for providing a method for minimizing duplicate traffic during point to multipoint (P2MP) tree switching in a network including a P2MP tree with a source node, the tangible computer readable medium comprising:

instructions operable on a processor to receive multicast data traffic transmitted from a first router over a primary network path to a second router, wherein the primary network path supports multicast label switching of multicast data traffic;

instructions operable on the processor to, in response to a detection of a failure in the network, receive the multicast data traffic over a backup label switched path on a secondary network path between the first router and the second router in lieu of receiving the multicast data traffic over the primary network path and minimize duplicate traffic via an initiation of a multicast rerouting procedure, wherein the instructions to minimize duplicate traffic via the initiation of the multicast rerouting procedure comprise;

instructions operable on the processor to transmit a new multicast switching label via the secondary network path to an upstream router, the secondary network path including the upstream router between the first router and the second router; and

instructions operable on the processor to configure the second router, upon receipt of an acknowledgement notification from the upstream router via the secondary network path indicating that the upstream router is a merge point in the P2MP tree, to receive multicast data traffic addressed to the new multicast switching label from the upstream router prior to the PSMP tree being in a convergent state after the failure instead of to receive multicast data traffic from the backup label switched path.

10. A tangible computer readable medium as in claim 9 wherein the instructions operable on the processor to minimize duplicate traffic via the initiation of the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprise:

instructions operable on the processor to execute a reverse path forwarding procedure.

11. A tangible computer readable medium as in claim 9 wherein the instructions operable on the processor to minimize duplicate traffic via the initiation of the multicast rerouting procedure further comprise:

instructions operable on the processor to add, in response to a determination the upstream router receives multicast data traffic, the new multicast switching label to a routing table at the upstream router; and

instructions operable on the processor to transmit the acknowledgement notification to the second router via the secondary network path.

12. A tangible computer readable medium as in claim 9 wherein the instructions operable on the processor to minimize duplicate traffic via the initiation of the multicast rerouting procedure further comprise:

instructions operable on the processor to transmit, in response to a determination an upstream node on the secondary network path does not receive multicast data traffic, a respective switching label to a next upstream router via the secondary network path;

instructions operable on the processor to propagate the acknowledgement notification from the upstream router, which is in receipt of multicast data traffic, to the second router via the secondary network path.

13. A tangible computer readable medium as in claim 9 wherein the instructions operable on the processor to minimize duplicate traffic via the initiation of the multicast rerouting procedure further comprise:

instructions operable on the processor to transmit a respective switching label to a next upstream router via the secondary network path in response to a determination the upstream router is not the source node of the P2MP tree; and

instructions operable on the processor to propagate the acknowledgement notification from the source node of the P2MP tree to the second router via the secondary network path.

14. A tangible computer readable medium as in claim 9 wherein the instructions operable on the processor to configure the second router to receive multicast data traffic addressed to the new multicast switching label comprises:

instructions operable on the processor to remove, from the second router, a primary switching label that the second router uses to receive the multicast data traffic via the primary network path;

instructions operable on the processor to receive, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.

15. A tangible computer readable medium as in claim 9 further comprising:

instructions operable on the processor to configure the backup label switched path on the secondary network path between the first router and the second router;

instructions operable on the processor to initiate, in response to the detection of the failure in the network, transmission of the multicast data traffic over the backup label switched path between the first router and the second router in lieu of transmission of the multicast data traffic over the primary network path.

16. A tangible computer readable medium as in claim 15 wherein the instructions operable on the processor to configure the second router to receive multicast data traffic from the secondary network path comprise:

instructions operable on the processor to remove, from the second router, a backup label switched path switching label that the second router normally uses for receiving multicast data traffic via the backup label switched path;

instructions operable on the processor to receive, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.

17. A network device comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with a network manager application that when performed on the processor duplicate traffic during point to multipoint (P2MP) tree switching in a network including a P2MP tree with a source node by performing the operations of;

receiving multicast data traffic transmitted from a first router over a primary network path to a second router, wherein the network path supports multicast label switching of multicast data traffic;

in response to detecting a failure in the network, receiving the multicast data traffic over a backup label switched path on a secondary network path between the first router and the second router in lieu of receiving the multicast data traffic over the primary network path and minimizing duplicate traffic by initiating a multicast rerouting procedure, the multicast rerouting procedure comprising;

transmitting a new multicast switching label via the secondary network path to an upstream router, the secondary network path including the upstream router between the first router and the second router; and

upon receiving an acknowledgement notification from the upstream router indicating that the upstream router is a merge point in the P2MP tree, configuring the second router to receive multicast data traffic addressed to the new multicast switching label from the upstream router over the secondary network path prior to the PSMP tree being in a convergent state after the failure and in lieu of receiving multicast data traffic over the backup label switched path.

18. A network device as in claim 17 wherein initiating the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprises:

initiating the multicast rerouting procedure by implementing a reverse path forwarding procedure.

19. A network device as in claim 17 wherein initiating the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprises:

adding the new multicast switching label to a routing table at the upstream router in response to determining the upstream router receives multicast data traffic; and

transmitting the acknowledgement notification to the second router via the secondary network path.

20. A network device as in claim 17 wherein initiating the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprises:

transmitting at an upstream node a respective switching label to a next upstream router via the secondary network path in response to determining the upstream node is not receiving multicast data traffic, wherein the upstream node and the next upstream router are on the secondary network path between the upstream router and the second router; and

propagating the acknowledgement notification from the upstream router receiving multicast data traffic to the second router via the secondary network path.

21. A network device as in claim 17 wherein initiating the multicast rerouting procedure by transmitting the new multicast switching label via the secondary network path to the upstream router comprises:

transmitting a respective switching label to a next upstream router via the secondary network path in response to determining an upstream node is not the source node of the P2MP tree;

propagating the acknowledgement notification from the source node of the P2MP tree to the second router via the secondary network path.

22. A network device as in claim 17 wherein configuring the second router to receive multicast data traffic from the secondary network path comprises:

removing, from the second router, a primary switching label that the second router normally uses for receiving multicast data traffic via the primary network path; and

receiving, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.

23. A network device as in claim 17 further comprising:

configuring the backup label switched path between the first router and the second router, the backup label switched path to tunnel the multicast data traffic to the second router;

in response to detecting the failure in the network, initiating transmission of the multicast data traffic over the backup label switched path between the first router and the second router in lieu of transmitting the multicast data traffic over the primary network path.

24. A network device as in claim 23 wherein the configuring the second router to receive multicast data traffic addressed to the new multicast switching label and transmitted from the upstream router over the secondary network path comprises:

removing, from the second router, a backup label switched path switching label that the second router uses for receiving multicast data traffic via the backup label switched path;

receiving, at the second router, multicast data traffic in accordance with the new multicast switching label used for the secondary network path.