Distributed generation of hierarchical multicast forwarding structures

• US 9,838,327 B1
• Filed: 12/08/2014
• Issued: 12/05/2017
• Est. Priority Date: 12/08/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ghosh, Kaushik
• Primary Examiner(s): Nguyen, Thai
• Application Number:
  US14/563,785
• Time in Patent Office: 1,093 Days
• CPC Class Codes: F02B 37/12 Control of the pumps
• CPC Class Codes: F02D 2041/001 for engines with variable valve actuation
• CPC Class Codes: F02D 41/0007 for control of turbo-charged or super-charged engines control of the pumps per se F02B37/12
• CPC Class Codes: F04D 17/10 for compressing or evacuating
• CPC Class Codes: F04D 27/0223 Control schemes therefor
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 61/5069 for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04N 7/15 Conference systems
• CPC Class Codes: Y02T 10/12 Improving ICE efficiencies

Abstract

In general, techniques are described in which packet replicators of a network device cooperate to generate a distributed hierarchical forwarding structure that the packet replicators then use to replicate and forward multicast packets to multiple output interfaces. For example, packet forwarding engines (PFEs) of a router each receive a new list of interfaces for a multicast packet stream. The PFEs individually construct a hierarchical forwarding structure based on the interface list. The hierarchical forwarding structure specifies interrelationships among the PFEs, which occupy nodes within the hierarchy. Each child PFE determines from the hierarchical forwarding structure the identity of a parent PFE and issues a token, constituting forwarding state for the distributed hierarchical forwarding structure, to the parent PFE. The parent PFE uses the token to identify packets of the multicast traffic to the child PFE during replication and forwarding of multicast packets proceeding according to the hierarchical forwarding structure.

Claims

1. A method comprising:

sending, by a first packet replicator of a plurality of packet replicators within a network device to a second packet replicator of the plurality of packet replicators and according to first local forwarding state stored by the first packet replicator for a multicast replication tree for replicating data units of multicast packets among the plurality of packet replicators, a data unit of a multicast packet;

sending, by the first packet replicator to the second packet replicator, a tear-down message directing the second packet replicator to delete local forwarding state for the multicast replication tree; and

deleting, by the second packet replicator in response to receiving the tear-down message, second local forwarding state stored by the second packet replicator for the multicast replication tree.

2. The method of claim 1, wherein sending the tear-down message comprises sending, by the first packet replicator to the second packet replicator in response to determining the second packet replicator is a child packet replicator of the first packet replicator according to the first local forwarding state, the tear-down message.

3. The method of claim 1, wherein the plurality packet replicators are interconnected by one of an internal crossbar fabric and an internal switching fabric of the network device, the method further comprising:

receiving, by the first packet replicator, a fabric token from the second packet replicator, the fabric token identifying the second local forwarding state.

4. The method of claim 3, wherein sending the data unit of the multicast packet comprising sending, by the first packet replicator to the second packet replicator, the data unit of the multicast packet and the fabric token.

5. The method of claim 4, further comprising:

sending, by the second packet replicator in response to identifying the second local forwarding state using the fabric token and via an outbound interface, the multicast packet.

6. The method of claim 1, wherein the multicast replication tree comprises a first multicast replication tree for a multicast group, the method further comprising:

receiving, by the first packet replicator from a control unit of the network device, an interface list for the multicast group identifying a plurality of outbound interfaces of the network device by which the network device is to output multicast packets for the multicast group; and

generating, by the first packet replicator in response to receiving the interface list, local forwarding state for a second multicast replication tree for the interface list.

7. The method of claim 6, further comprising:

sending, by the first packet replicator to the second packet replicator after receiving a ready message from each egress packet replicator of the plurality of packet replicators for the second multicast replication tree, a data unit for a subsequent multicast packet,

wherein the ready message from each egress packet replicator indicates the egress packet replicator is ready to replicate data units for multicast packets according to the second multicast replication tree for the interface list.

8. The method of claim 1, further comprising:

sending, by the second packet replicator to a third packet replicator in response to receiving the tear-down message, the tear-down message.

9. The method of claim 1, wherein each of the plurality of packet replicators comprises a packet forwarding engine.

10. A router comprising:

a plurality of packet replicators, a first packet replicator of the plurality of packet replicators configured to send, to a second packet replicator of the plurality of packet replicators and according to first local forwarding state stored by the first packet replicator for a multicast replication tree for replicating data units of multicast packets among the plurality of packet replicators, a data unit of a multicast packet,

wherein the first packet replicator is further configured to send, to the second packet replicator, a tear-down message to direct the second packet replicator to delete local forwarding state for the multicast replication tree, and

wherein the second packet replicator is configured to delete, in response to receiving the tear-down message, second local forwarding state stored by the second packet replicator for the multicast replication tree.

11. The router of claim 10, wherein to send the tear-down message the first packet replicator is configured to send, to the second packet replicator in response to determining the second packet replicator is a child packet replicator of the first packet replicator according to the first local forwarding state, the tear-down message.

12. The router of claim 10, further comprising:

a switching fabric interconnecting the plurality packet replicators,

wherein the first packet replicator is further configured to receive a fabric token from the second packet replicator, the fabric token identifying the second local forwarding state.

13. The router of claim 12, wherein to send the data unit of the multicast packet the first packet replicator is further configured to send, to the second packet replicator, the data unit of the multicast packet and the fabric token.

14. The router of claim 13, where the second packet replicator is further configured to send, in response to identifying the second local forwarding state using the fabric token and via an outbound interface, the multicast packet.

15. The router of claim 10, further comprising:

a control unit,

wherein the multicast replication tree comprises a first multicast replication tree for a multicast group,

wherein the first packet replicator is further configured to receive, from the control unit, an interface list for the multicast group identifying a plurality of outbound interfaces of the network device by which the router is to output multicast packets for the multicast group, and

wherein the first packet replicator is further configured to generate, in response to receiving the interface list, local forwarding state for a second multicast replication tree for the interface list.

16. The router of claim 15,

wherein the first packet replicator is further configured to send, to the second packet replicator after receiving a ready message from each egress packet replicator of the plurality of packet replicators for the second multicast replication tree, a data unit for a subsequent multicast packet, and

wherein the ready message from each egress packet replicator indicates the egress packet replicator is ready to replicate data units for multicast packets according to the second multicast replication tree for the interface list.

17. The router of claim 10, further comprising:

wherein the second packet replicator is further configured to send, to a third packet replicator in response to receiving the tear-down message, the tear-down message.

18. The router of claim 10, wherein each of the plurality of packet replicators comprises a packet forwarding engine.

19. A non-transitory computer-readable medium comprising instructions for causing respective processing circuitry of a plurality of packet replicators within a network device to:

send, by a first packet replicator of the plurality of packet replicators to a second packet replicator of the plurality of packet replicators and according to first local forwarding state stored by the first packet replicator for a multicast replication tree for replicating data units of multicast packets among the plurality of packet replicators, a data unit of a multicast packet;

send, by the first packet replicator to the second packet replicator, a tear-down message that directs the second packet replicator to delete local forwarding state for the multicast replication tree; and

delete, by the second packet replicator in response to receiving the tear-down message, second local forwarding state stored by the second packet replicator for the multicast replication tree.

20. The non-transitory computer-readable medium of claim 19, wherein to send the tear-down message the instructions cause the respective processing circuitry of the plurality of packet replicators to send, by the first packet replicator to the second packet replicator in response to determining the second packet replicator is a child packet replicator of the first packet replicator according to the first local forwarding state, the tear-down message.