SELECTING A PATH FOR A PACKET

• US 20100046515A1
• Filed: 10/28/2009
• Published: 02/25/2010
• Est. Priority Date: 06/27/2003
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Wong, Jimmy S.
• Granted Patent: US 7,983,270 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5617 Virtual LANs; Emulation of LANs
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities

Abstract

Various example embodiments are disclosed. According to an example embodiment, a network device may include a memory management unit. The memory management unit may be configured to populate a count field based on a number of equal cost paths for each Internet Protocol (IP) route for a packet, randomly choose one of the equal cost paths for the packet, and send the packet out of the network device, the packet including route information for the chosen equal cost path.

Claims

1. A network device comprising:

a memory management unit configured to;

populate a count field based on a number of equal cost paths for each Internet Protocol (IP) route for a packet;

randomly choose one of the equal cost paths for the packet; and

send the packet out of the network device, the packet including route information for the chosen equal cost path.

2. The network device of claim 1, wherein the memory management unit is configured to randomly choose one of the equal cost paths based on determining that the packet is a multicast packet.

3. The network device of claim 1, wherein the memory management unit is further configured to:

randomly choose one of the equal cost paths for a copy of the packet; and

send the copy of the packet out of the network device, the copy of the packet including route information for the equal cost path chosen for the copy of the packet.

4. The network device of claim 1, wherein the memory management unit is further configured to:

determine a copy count value that represents a number of copies that have been generated to duplicate the packet,

wherein the packet, upon being sent out of the network device, includes the route information for the chosen equal cost path and the copy count value.

5. The network device of claim 1, wherein the memory management unit is further configured to populate the count field from a Layer 3 (L3) routing table.

6. The network device of claim 1, wherein the memory management unit is configured to populate the count field by:

determining that an IP destination address of the packet is included in a Layer 3 (L3) routing table;

obtaining a pointer from a Longest Prefix Match (LPM) table for the IP destination address of the packet; and

obtaining the route information from the L3 routing table based on the pointer.

7. The network device of claim 1, further comprising:

at least one data port interface coupled to the memory management unit,

wherein the memory management unit is configured to send the packet out of the network device via the at least one data port interface.

8. The network device of claim 1, wherein:

the memory management unit is further configured to;

determine a copy count value that represents a number of copies that have been generated to duplicate the packet; and

send the packet out of the network device via a data port interface, the packet including the route information for the chosen equal cost path and the copy count value; and

the network device further includes the data port interface coupled to the memory management unit, the data port interface being configured to modify a Virtual Local Area Network (VLAN) identifier of the packet based on the copy count value.

9. A method comprising:

populating, by a memory management unit, a count field based on a number of equal cost paths for each Internet Protocol (IP) route for a packet;

randomly choosing one of the equal cost paths for the packet; and

sending the packet out of a network device, the packet including route information for the chosen equal cost path.

10. The method of claim 9, further comprising:

determining that the packet is a multicast packet,

wherein the randomly choosing one of the equal cost paths includes randomly choosing one of the equal cost paths based on determining that the packet is the multicast packet.

11. The method of claim 9, further comprising:

randomly choosing one of the equal cost paths for a copy of the packet; and

sending the copy of the packet out of the network device, the copy of the packet including route information for the equal cost path chosen for the copy of the packet.

12. The method of claim 9, further comprising:

determining a copy count value that represents a number of copies that have been generated to duplicate the packet,

wherein the packet, upon being sent out of the network device, includes the route information for the chosen equal cost path and the copy count value.

13. The method of claim 9, further comprising populating the count field from a Layer 3 (L3) routing table.

14. The method of claim 9, wherein the memory management unit is configured to populate the count field by:

determining that an IP destination address of the packet is included in a Layer 3 (L3) routing table;

obtaining a pointer from a Longest Prefix Match (LPM) table for the IP destination address of the packet; and

obtaining the route information from the L3 routing table based on the pointer.

15. The method of claim 9, further comprising:

at least one data port interface coupled to the memory management unit,

wherein the memory management unit is configured to send the packet out of the network device via the at least one data port interface.

16. The method of claim 9, wherein:

the memory management unit is further configured to;

determine a copy count value that represents a number of copies that have been generated to duplicate the packet; and

send the packet out of the network device via a data port interface, the packet including the route information for the chosen equal cost path and the copy count value; and

the network device further includes the data port interface coupled to the memory management unit, the data port interface being configured to modify a Virtual Local Area Network (VLAN) identifier of the packet based on the copy count value.

17. An apparatus comprising:

means for populating a count field based on a number of equal cost paths for each Internet Protocol (IP) route for a packet;

means for randomly choosing one of the equal cost paths for the packet; and

means for sending the packet out of the network device, the packet including route information for the chosen equal cost path.

18. The apparatus of claim 17, further comprising:

means for determining that the packet is a multicast packet,

wherein the means for randomly choosing one of the equal cost paths includes means for randomly choosing one of the equal cost paths based on the determining that the packet is a multicast packet.

19. The apparatus of claim 17, further comprising:

means for randomly choosing one of the equal cost paths for a copy of the packet; and

means for sending the copy of the packet out of the network device, the copy of the packet including route information for the equal cost path chosen for the copy of the packet.

20. The apparatus of claim 17, further comprising:

means for determining a copy count value that represents a number of copies that have been generated to duplicate the packet,

wherein the packet, upon being sent out of the network device, includes the route information for the chosen equal cost path and the copy count value.