Preventing traffic flooding to the root of a multi-point to multi-point label-switched path tree with no receivers

• US 9,369,297 B2
• Filed: 07/25/2014
• Issued: 06/14/2016
• Est. Priority Date: 04/23/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Boers, Arjen
• Primary Examiner(s): Cho, Un C
• Assistant Examiner(s): COSTIN, JEREMY M
• Application Number:
  US14/341,536
• Publication Number:
  US 20140334308A1
• Time in Patent Office: 690 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• 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]

Abstract

A method is provided for pruning an MP2MP tree. The method includes, in a first node of an MP2MP LSP tree, determining whether the first node has only a single replication branch for the MP2MP LSP tree, the single replication branch representing a downstream path to only a second node of the plurality of nodes. In response to determining that the first node has only a single replication branch for the MP2MP LSP tree, sending a message to the second node indicating that the second node should refrain from sending upstream traffic towards the first node, and in response to determining that the first node does not have only a single replication branch for the MP2MP LSP tree, refraining from sending a message to the second node indicating that the second node should refrain from sending upstream traffic of the MP2MP LSP tree towards the first node.

Claims

1. A method comprising:

at a first node of a multipoint-to-multipoint (MP2MP) label switched path (LSP) tree, the MP2MP LSP tree including a plurality of nodes, receiving, from a second node, a first Label Mapping packet, the second node being a first leaf node to join the MP2MP LSP tree;

determining whether the first node has only a single replication branch for the MP2MP LSP tree;

in response to determining that the first node has only the single replication branch for the MP2MP LSP tree, sending, by the first node, a first Label Withdraw packet to the second node;

sending, by the first node, a second Label Mapping Packet upstream towards a third node;

in response to the third node determining that it has only a single replication branch for the MP2MP LSP tree, receiving, from the third node, a second Label Withdraw packet;

in response to subsequent downstream nodes joining the MP2MP LSP tree, receiving subsequent Label Mapping Packets from each of the subsequent downstream nodes resulting in the first node having more than one replication branch;

in response to receiving the subsequent Label Mapping Packets, sending additional Label Mapping Packets to each of the subsequent downstream nodes; and

updating a Forwarding Information Base (FIB) of the first node to reflect all paths that exist due to addition of the first node and the subsequent downstream nodes to the MP2MP LSP tree.

2. The method of claim 1, further comprising sending, by the first node, a third Label Mapping Packet to the second node for use by the second node in upstream communications.

3. The method of claim 1, wherein, the first node sends the second Label Mapping Packet upstream towards the third node before the first node sends the first Label Withdraw Packet to the second node.

4. The method of claim 1, wherein the first node sends the first Label Withdraw Packet to the second node after receiving the second Label Withdraw Packet from the third node.

5. The method of claim 2, further comprising accessing a tree table to determine a location of the second node before sending the third Label Mapping Packet to the second node for use by the second node in upstream communications.

6. The method of claim 1, wherein subsequent to sending the first Label Withdraw packet to the second node, further comprising storing a reference to the second node as a downstream node in a tree table of the first node.

7. The method of claim 1, wherein determining the first node has only the single replication branch for the MP2MP LSP tree is performed in response to receiving, at the first node, a request for label mapping.

8. A first node comprising:

a plurality of network interfaces; and

a controller, the controller configured to;

receive from a second node connected to a first one of the plurality of network interfaces, a first Label Mapping packet, the second node being a first leaf node to join a multipoint-to-multipoint (MP2MP) label switched path (LSP) tree;

determine whether the first node has only a single replication branch for the MP2MP LSP tree;

in response to determining that the first node has only the single replication branch for the MP2MP LSP tree, send a first Label Withdraw packet to the second node via the first one of the plurality of network interfaces;

send a second Label Mapping Packet upstream towards a third node connected to a second one of the plurality of network interfaces;

in response to the third node determining that it has only a single replication branch for the MP2MP LSP tree, receive, from the third node, a second Label Withdraw packet;

in response to subsequent downstream nodes joining the MP2MP LSP tree, receive over the plurality of network interfaces subsequent Label Mapping Packets from each of the subsequent downstream nodes resulting in the first node having more than one replication branch;

in response to receiving the subsequent Label Mapping Packets, send additional Label Mapping Packets to each of the subsequent downstream nodes over the plurality of network interfaces; and

update a Forwarding Information Base (FIB) of the first node to reflect all paths that exist due to addition of the first node and the subsequent downstream nodes to the MP2MP LSP tree.

9. The first node of claim 8, the controller further configured to send a third Label Mapping Packet to the second node for use by the second node in upstream communications.

10. The first node of claim 8, the controller further configured to send the second Label Mapping Packet upstream towards the third node before the first node sends the first Label Withdraw Packet to the second node.

11. The first node of claim 8, the controller further configured to send the first Label Withdraw Packet to the second node after receiving the second Label Withdraw Packet from the third node.

12. The first node of claim 9, the controller further configured to access a tree table to determine a location of the second node before sending the third Label Mapping Packet to the second node for use by the second node in upstream communications.

13. The first node of claim 8, wherein subsequent to sending the first Label Withdraw packet to the second node, the controller is further configured to store a reference to the second node as a downstream node in a tree table.

14. The first node of claim 8, wherein determining the first node has only the single replication branch for the MP2MP LSP tree is performed in response to the first node receiving a request for label mapping.

15. A non-transitory computer-readable storage medium having a computer readable program code embodied therein, the computer-readable program code when executed by at least one processor causes the at least one processor within a first node to:

receive from a second node, a first Label Mapping packet, the second node being a first leaf node to join a multipoint-to-multipoint (MP2MP) label switched path (LSP) tree;

determine whether the first node has only a single replication branch for the MP2MP LSP tree;

in response to determining that the first node has only the single replication branch for the MP2MP LSP tree, send a first Label Withdraw packet to the second node;

send a second Label Mapping Packet upstream towards a third node;

in response to the third node determining that it has only a single replication branch for the MP2MP LSP tree, receive, from the third node, a second Label Withdraw packet;

in response to subsequent downstream nodes joining the MP2MP LSP tree, receive subsequent Label Mapping Packets from each of the subsequent downstream nodes resulting in the first node having more than one replication branch;

in response to receiving the subsequent Label Mapping Packets, send additional Label Mapping Packets to each of the subsequent downstream nodes; and

update a Forwarding Information Base (FIB) of the first node to reflect all paths that exist due to addition of the first node and the subsequent downstream nodes to the MP2MP LSP tree.

16. The non-transitory computer-readable storage medium of claim 15, when executed by the at least one processor, further causes the at least one processor to send a third Label Mapping Packet to the second node for use by the second node in upstream communications.

17. The non-transitory computer-readable storage medium of claim 15, when executed by the at least one processor, further causes the at least one processor to send the second Label Mapping Packet upstream towards the third node before the first node sends the first Label Withdraw Packet to the second node.

18. The non-transitory computer-readable storage medium of claim 15, when executed by the at least one processor, further causes the at least one processor to send the first Label Withdraw Packet to the second node after receiving the second Label Withdraw Packet from the third node.

19. The non-transitory computer-readable storage medium of claim 16, when executed by the at least one processor, further causes the at least one processor to access a tree table to determine a location of the second node before sending the third Label Mapping Packet to the second node for use by the second node in upstream communications.

20. The non-transitory computer-readable storage medium of claim 15, wherein subsequent to sending the first Label Withdraw packet to the second node, the at least one processor is further caused to store a reference to the second node as a downstream node in a tree table.