Data structure-less distributed fabric multicast

• US 8,325,726 B2
• Filed: 02/09/2010
• Issued: 12/04/2012
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Baban, Alex, Frailong, Jean-Marc, Kompella, Kireeti, Kumar, Nitin, Wania, Jamsheed, Attarwala, Murtuza
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Tsegaye, Saba
• Application Number:
  US12/702,718
• Publication Number:
  US 20110194557A1
• Time in Patent Office: 1,029 Days
• Field of Search: 370/270, 370/271, 370/312, 370/389, 370/390, 370/432
• US Class Current: 370/390
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation

Abstract

A network device receives a packet with a multicast nexthop identifier, and creates a mask that includes addresses of egress packet forwarding engines, of the network device, to which to provide the packet. The network device divides the mask into two portions, generates two copies of the packet, provides a first portion of the mask in a first copy of the packet, and provides a second portion of the mask in a second copy of the packet. The network device also forwards the first copy of the packet to an address of a first egress packet forwarding engine provided in the first portion of the mask, and forwards the second copy of the packet to an address of a second egress packet forwarding engine provided in the second portion of the mask.

Claims

1. A method implemented by a network device, the method comprising:

receiving, by an ingress packet forwarding engine of the network device, a packet with a multicast nexthop identifier;

creating, by the ingress packet forwarding engine, a mask that includes addresses of egress packet forwarding engines to which to provide the packet;

dividing, by the ingress packet forwarding engine, the mask into two portions;

generating, by the ingress packet forwarding engine, two copies of the packet;

providing, by the ingress packet forwarding engine, a first portion of the mask in a first copy of the packet; and

forwarding, by the ingress packet forwarding engine, the first copy of the packet to an address of an egress packet forwarding engine provided in the first portion of the mask.

2. The method of claim 1, where forwarding the first copy of the packet comprises:

selecting the address of the egress packet forwarding engine from the first portion of the mask;

removing the address of the egress packet forwarding engine from the first portion of the mask prior to forwarding the first copy of the packet; and

forwarding the first copy of the packet, with the address of the egress packet forwarding engine removed from the first portion of the mask, to the address of the egress packet forwarding engine.

3. The method of claim 1, further comprising:

providing a second portion of the mask in a second copy of the packet; and

forwarding the second copy of the packet to an address of another egress packet forwarding engine provided in the second portion of the mask.

4. The method of claim 3, where forwarding the second copy of the packet comprises:

selecting the address of the other egress packet forwarding engine from the second portion of the mask;

removing the address of the other egress packet forwarding engine from the second portion of the mask prior to forwarding the second copy of the packet; and

forwarding the second copy of the packet, with the address of the other egress packet forwarding engine removed from the second portion of the mask, to the address of the other egress packet forwarding engine.

5. The method of claim 1, where the mask includes indices identifying egress packet forwarding engines to which to provide the packet.

6. The method of claim 5, where one or more bits of the mask are allocated to each of the indices.

7. The method of claim 1, where the network device comprises one or more of:

a gateway,

a router,

a switch,

a firewall,

a network interface card (NIC),

a hub,

a bridge,

a proxy server, or

an optical add-drop multiplexer (OADM).

8. A method implemented by a network device, the method comprising:

receiving, by a packet forwarding engine of the network device, a packet with a mask that includes addresses of other packet forwarding engines to which to provide the packet;

determining, by the packet forwarding engine, that the mask is divisible;

dividing, by the packet forwarding engine, the mask into two portions;

generating, by the packet forwarding engine, two copies of the packet;

providing, by the packet forwarding engine, a first portion of the mask in a first copy of the packet; and

forwarding, by the packet forwarding engine, the first copy of the packet to an address of one of the other packet forwarding engines provided in the first portion of the mask.

9. The method of claim 8, further comprising:

removing the mask from the packet when the mask includes a single address of a particular packet forwarding engine; and

forwarding the packet to the address of the particular packet forwarding engine.

10. The method of claim 8, where forwarding the first copy of the packet comprises:

selecting the address of the one of the other packet forwarding engines from the first portion of the mask;

removing the address of the one of the other packet forwarding engines from the first portion of the mask prior to forwarding the first copy of the packet; and

forwarding the first copy of the packet, with the address of the one of other packet forwarding engines removed from the first portion of the mask, to the address of the one of the other packet forwarding engines.

11. The method of claim 8, further comprising:

providing a second portion of the mask in a second copy of the packet; and

forwarding the second copy of the packet to an address of another one of the other packet forwarding engines provided in the second portion of the mask.

12. The method of claim 11, where forwarding the second copy of the packet comprises:

selecting the address of the other one of the other packet forwarding engines from the second portion of the mask;

removing the address of the other one of the other packet forwarding engines from the second portion of the mask prior to forwarding the second copy of the packet; and

forwarding the second copy of the packet, with the address of the other one of the other packet forwarding engines removed from the second portion of the mask, to the address of the other one of the other packet forwarding engines.

13. The method of claim 8, where the network device comprises one or more of:

a gateway,

a router,

a switch,

a firewall,

a network interface card (NIC),

a hub,

a bridge,

a proxy server, or

an optical add-drop multiplexer (OADM).

14. A network device, comprising:

a memory to store a plurality of instructions; and

a processor to execute instructions in the memory to;

receive a packet with a multicast nexthop identifier,

create a mask that includes addresses of egress packet forwarding engines, of the network device, to which to provide the packet,

divide the mask into two portions,

generate two copies of the packet,

provide a first portion of the mask in a first copy of the packet,

provide a second portion of the mask in a second copy of the packet,

forward the first copy of the packet to an address of a first egress packet forwarding engine provided in the first portion of the mask, and

forward the second copy of the packet to an address of a second egress packet forwarding engine provided in the second portion of the mask.

15. The network device of claim 14, where, when forwarding the first copy of the packet, the processor is further to execute instructions in the memory to:

select the address of the first egress packet forwarding engine from the first portion of the mask,

remove the address of the first egress packet forwarding engine from the first portion of the mask prior to forwarding the first copy of the packet, and

forward the first copy of the packet, with the address of the first egress packet forwarding engine removed from the first portion of the mask, to the address of the first egress packet forwarding engine.

16. The network device of claim 14, where, when forwarding the second copy of the packet the processor is further to execute instructions in the memory to:

select the address of the second egress packet forwarding engine from the second portion of the mask,

remove the address of the second egress packet forwarding engine from the second portion of the mask prior to forwarding the second copy of the packet, and

forward the second copy of the packet, with the address of the second egress packet forwarding engine removed from the second portion of the mask, to the address of the second egress packet forwarding engine.

17. The network device of claim 14, where the mask includes indices identifying egress packet forwarding engines to which to provide the packet, and where one or more bits of the mask are allocated to each of the indices.

18. The network device of claim 14, where the network device comprises one or more of:

a gateway,

a router,

a switch,

a firewall,

a network interface card (NIC),

a hub,

a bridge,

a proxy server, or

an optical add-drop multiplexer (OADM).

19. A network device, comprising:

a memory to store a plurality of instructions; and

a processor to execute instructions in the memory to;

receive a packet with a mask that includes addresses of packet forwarding engines to which to provide the packet,

determine that the mask is divisible,

divide the mask into two portions,

generate two copies of the packet,

provide a first portion of the mask in a first copy of the packet,

provide a second portion of the mask in a second copy of the packet,

forward the first copy of the packet to an address of one of the packet forwarding engines provided in the first portion of the mask, and

forward the second copy of the packet to an address of another one of the packet forwarding engines provided in the second portion of the mask.

20. The network device of claim 19, where the processor is further to execute instructions in the memory to:

remove the mask from the packet when the mask includes a single address of a particular packet forwarding engine, and

forward the packet to the single address of the particular packet forwarding engine.

21. The network device of claim 19, where, when forwarding the first copy of the packet the processor is further to execute instructions in the memory to:

select the address of the one of the packet forwarding engines from the first portion of the mask,

remove the address of the one of the packet forwarding engines from the first portion of the mask prior to forwarding the first copy of the packet, and

forward the first copy of the packet, with the address of the one of packet forwarding engines removed from the first portion of the mask, to the address of the one of the packet forwarding engines.

22. The network device of claim 19, where, when forwarding the second copy of the packet, the processor is further to execute instructions in the memory to:

select the address of the other one of the packet forwarding engines from the second portion of the mask,

remove the address of the other one of the packet forwarding engines from the second portion of the mask prior to forwarding the second copy of the packet, and

forward the second copy of the packet, with the address of the other one of the packet forwarding engines removed from the second portion of the mask, to the address of the other one of the packet forwarding engines.

23. The network device of claim 19, where the mask includes indices identifying egress packet forwarding engines to which to provide the packet.

24. The network device of claim 23, where one or more bits of the mask are allocated to each of the indices.

25. The network device of claim 19, where the network device comprises one or more of:

a gateway,

a router,

a switch,

a firewall,

a network interface card (NIC),

a hub,

a bridge,

a proxy server, or

an optical add-drop multiplexer (OADM).