Multicast packet replication

• US 7,263,099 B1
• Filed: 08/14/2002
• Issued: 08/28/2007
• Est. Priority Date: 08/14/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Woo, Hsien-Chung, Hui, Lawrence, Ferguson, Dennis C
• Primary Examiner(s): Sam; Phirin
• Application Number:
  US10/219,799
• Time in Patent Office: 1,840 Days
• Field of Search: None
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• 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

Abstract

Techniques are described to replicate multicast packets in accordance with a hierarchical data structure. For example, upon receiving a multicast packet, a packet-forwarding engine may communicate the packet to packet-forwarding engines corresponding to starting nodes of the hierarchical data structure. The packet-forwarding engines corresponding to starting nodes of the hierarchical data structure may replicate the multicast packet for local interface cards, and forward the replicated packets to the network. Furthermore, the packet-forwarding engines may replicate the packet for packet-forwarding engines corresponding to downstream nodes. In this manner, the packet replication process is distributed throughout the router decreasing the complexity of necessary replication hardware. Furthermore, the packet replication process is highly scalable resulting in a latency of one fabric hop when the number of packet-forwarding engines doubles. Also, when the hierarchical data structure has more than one starting node, the packet replication process is less susceptible to a single point failure.

Claims

1. A method comprising:

identifying a set of interfaces of a network router from a first multicast list of a plurality of multicast lists;

identifying packet replicators associated with the identified interfaces, wherein the packet replicators are distributed across multiple ones of the interfaces;

generating a hierarchical data structure that represents a hierarchical relationship of packet replicators distributed across the multiple interfaces in the network router by determining a starting entry of the first multicast list based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists, populating a base node of the hierarchical data structure with one of the packet replicators associated with the determined starting entry of the first multicast list, and populating the hierarchical data structure with the respective packet replicators associated with ascending entries of the first multicast list; and

replicating a multicast packet in the packet replicators according to the hierarchical data structure.

2. The method of claim 1, wherein determining the starting entry includes:

determining the number of entries in the first multicast list; and

dividing the index number of the first multicast list by the number of entries in the first multicast list and using the remainder of the division as the starting entry.

3. The method of claim 1, wherein the hierarchical data structure is a binary tree structure.

4. The method of claim 1, wherein replicating the multicast packet according to the hierarchical relationship comprises:

receiving a multicast packet; and

generating copies of the multicast packet for packet replicators corresponding to downstream nodes of the hierarchical data structure.

5. The method of claim 1, further comprising associating the hierarchical relationship with the first multicast list.

6. The method of claim 5, wherein the first multicast list includes the interfaces involved in a multicast session, and the packet replicators include packet forwarding engines serving the interfaces.

7. The method of claim 5, further comprising:

associating a source/destination address pair of the multicast packet with the first multicast list;

accessing the hierarchical data structure associated with the first multicast list; and

communicating the multicast packet to the packet replicator corresponding to the base node of the hierarchical data structure.

8. The method of claim 1, further comprising:

receiving the first multicast list identifying the interfaces involved in a multicast session;

deriving from the first multicast list a list of packet replicators involved in the multicast session.

9. The method of claim 8, further comprising each packet replicator identifying from the first multicast list interfaces served by the respective packet replicator.

10. The method of claim 9, further comprising:

receiving, in one of the packet replicators, a multicast packet; and

generating copies of the multicast packet for the interfaces served by the respective packet replicator.

11. The method of claim 1, wherein the hierarchical data structure has at least two base nodes.

12. The method of claim 1, wherein the packet replicator includes a packet-forwarding engine (PFE).

13. The method of claim 1, wherein the interfaces are interface cards of the network router.

14. A device comprising:

a set of router interfaces;

a set of packet replicators, wherein the packet replicators are distributed across multiple ones of the router interfaces; and

a hierarchical data structure that represents a hierarchical relationship of the packet replicators distributed across the multiple interfaces in the device, wherein the hierarchical data structure is generated by determining a starting entry of a first multicast list of a plurality of multicast lists based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists, populating a base node of the hierarchical data structure with one of the packet replicators associated with the determined starting entry of the first multicast list, and populating the hierarchical data structure with the respective packet replicators associated with ascending entries of the first multicast list,

further wherein each of the packet replicators replicates a multicast packets according to the hierarchical data structure.

15. The device of claim 14, wherein each of the packet replicators stores a copy of the hierarchical data structure that defines the hierarchical relationship, and accesses the hierarchical data structure to identify one or more packet replicators for forwarding of the replicated packets.

16. The device of claim 14, wherein the hierarchical data structure has at least two base nodes.

17. The device of claim 14, wherein the first multicast list is a list of interfaces involved in a multicast session.

18. The device of claim 14, wherein the first multicast list is a list of packet replicators involved in a multicast session.

19. The device of claim 18, further comprising a switch for communication of the packets between the packet replicators.

20. The device of claim 14, wherein the packet replicators include packet forwarding engines that serve the interfaces.

21. The device of claim 14, wherein the interfaces include interface cards coupled to packet forwarding engines via interface card concentrators.

22. A method comprising:

identifying a set of interfaces of a network router involved in a one-to-many communication session from a first list of a plurality of lists;

identifying packet replicators associated with the identified interfaces, wherein the packet replicators are distributed across multiple ones of the interfaces;

generating a data structure that represents a hierarchical relationship of packet replicators distributed across the multiple interfaces in the network router by determining a starting entry of the first list based on at least an index number of the first list from a data structure that maintains the plurality of lists, populating a base node of the hierarchical data structure with one of the packet replicators associated with the determined starting entry of the first list, and populating the hierarchical data structure with the respective packet replicators associated with ascending entries of the first list; and

replicating a one-to-many communication packet using the packet replicators associated with the interfaces in accordance with the hierarchical data structure.

23. The method of claim 22, wherein each of the packet replicators generates the hierarchical data structure, and forwards replicated packets to other packet replicators according to the hierarchical data structure.

24. The method of claim 22, wherein each of the packet replicators downloads the hierarchical data structure from a routing engine.

25. The method of claim 22, wherein the packet replicators include packet forwarding engines that serve the interfaces.

26. The method of claim 22, further comprising:

generating a list of packet replicators associated with the interfaces identified in the first multicast list; and

generating the hierarchical data structure based on the list of packet replicators.

27. The method of claim 22 wherein the one-to-many communication session is one of a multicast session and a broadcasting session.

28. A method comprising:

receiving a first multicast list of a plurality of multicast lists that identifies interface cards involved in a multicast session;

deriving a list of packet-forwarding engines involved in the multicast session from the first multicast list, wherein each of the packet-forwarding engines is associated with one or more of the interface cards; and

generating a hierarchical data structure based on the packet-forwarding engine list by determining a starting entry of the packet-forwarding engine list based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists, populating a base node of the hierarchical data structure with one of the packet-forwarding engines associated with the determined starting entry, and populating the hierarchical data structure with the respective packet-forwarding engines associated with ascending entries of the packet-forwarding engine list;

replicating multicast packets within the packet-forwarding engines in accordance with the hierarchical data structure.

29. A method comprising:

receiving a first multicast list of a plurality of multicast lists;

determining a starting entry of the first multicast list based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists;

populating a base node of a hierarchical data structure with one of a plurality of packet replicators corresponding to the determined starting entry of the first multicast list;

populating the hierarchical data structure horizontally with ascending entries of the first multicast list; and

replicating packets using packet replicators associated with the router interfaces according to the hierarchical data structure.

30. The method of claim 29, further comprising:

determining the index number of the first multicast list from the data structure that maintains the plurality of multicast lists;

determining the number of entries in the first multicast list; and

dividing the index number of the first multicast list by the number of entries in the first multicast list and using the remainder of the division as the starting entry.

31. The method of claim 29, wherein the hierarchical data structure has two or more base nodes.

32. A system comprising:

a source host that sends a multicast packet;

a plurality of destination hosts that receive a copy of the multicast packet; and

a router that replicates the multicast packets using packet replicators distributed across multiple interfaces in the router according to a hierarchical data structure, wherein the hierarchical data structure is generated by determining a starting entry of a first multicast list of a plurality of multicast lists based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists, populating a base node of the hierarchical data structure with one of the packet replicators associated with the determined starting entry of the first multicast list, and populating the hierarchical data structure with the respective packet replicators associated with ascending entries of the first multicast list.

33. A computer-readable medium comprising instructions to cause a processor to:

identify a set of interfaces of a network router from a first multicast list of a plurality of multicast lists;

identify packet replicators associated with the identified interfaces, wherein the packet replicators are distributed across multiple ones of the interfaces;

generate a hierarchical data structure that represents a hierarchical relationship of packet replicators distributed across the multiple interfaces in the network router by determining a starting entry of the first multicast list based on at least an index number of the first multicast list from a data structure that maintains the plurality of multicast lists, populating a base node of the hierarchical data structure with one of the packet replicators associated with the determined starting entry of the first multicast list, and populating the hierarchical data structure with the respective packet replicators associated with ascending entries of the first multicast list; and

replicate a multicast packets in the packet replicators according to the hierarchical data structure.

34. The computer-readable medium of claim 33, wherein the instructions cause the processor to generate copies of the multicast packet for one or more of the packet replicators corresponding to downstream nodes of the hierarchical data structure.

35. The computer-readable medium of claim 33, further comprising instructions to cause the processor to associate the hierarchical data structure with the first multicast list.

36. The computer-readable medium of claim 35, further comprising instructions to cause the processor to:

associate a source/destination address pair of the multicast packet with the first multicast list;

access the hierarchical data structure associated with the first multicast list; and

communicate the multicast packet to one of the packet replicators corresponding to a base node of the hierarchical data structure.

37. The computer-readable medium of claim 33, further comprising instructions to cause the processor to derive a list of packet replicators involved in a multicast session from the first multicast list.

38. The computer-readable medium of claim 33, wherein the packet replicators include packet forwarding engines associated with the interfaces.