Selecting a path for a packet
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.
1. A network device comprising:
a memory management unit comprising:
a longest prefix match (LPM) table configured to store, for each of a plurality of Internet Protocol (IP) addresses, a count field based on a number of equal cost paths for each Internet Protocol IP address and a pointer to a route information table; and
the route information table configured to store the equal cost paths for each of the IP addresses;
the network device being configured to:
find a destination IP address of a packet in the route information table;
after finding the destination IP address in the route information table, find a longest prefix match for the destination IP address in the LPM table and a pointer to the route information table based on the longest prefix match;
randomly choose one of the equal cost paths stored in the route information table based on the pointer associated with the longest prefix match; 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 network device 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 network device 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 network device is further configured to:
determine a copy count value that represents a number of copies of the packet that have been generated,
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 network device is configured to populate the count field based on the number of equal cost paths stored in the route information table for each IP address.
6. The network device of claim 1 , further comprising:
at least one data port interface coupled to the memory management unit,
wherein the network device is configured to send the packet out of the network device via the at least one data port interface.
7. The network device of claim 1 , wherein the network device is further configured to:
determine a copy count value that represents a number of copies of the packet that have been generated; 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;
wherein 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.
8. A method comprising:
finding a destination Internet Protocol (IP) address of a packet in a route information table of a memory management unit;
after finding the destination IP address in the route information table, finding a longest prefix match for the destination IP address in a longest prefix match (LPM) table of the memory management unit and a pointer to the route information table based on the longest prefix match;
randomly choosing one of the equal cost paths packet stored in the route information table based on the pointer associated with the longest prefix match; and
sending the packet out of a network device which includes the memory management unit, the packet including route information for the chosen equal cost path.
9. The method of claim 8 , 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 a multicast packet.
10. The method of claim 8 , 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.
11. The method of claim 8 , 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.
12. The method of claim 8 , further comprising populating the count field from a Layer 3 (L 3 ) routing table.
13. The method of claim 8 , further comprising:
determining a copy count value that represents a number of copies that have been generated to duplicate the packet; and
sending 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
modifying a Virtual Local Area Network (VLAN) identifier of the packet based on the copy count value.
14. An apparatus comprising:
means for finding a destination Internet Protocol (IP) address of a packet in a route information table of a memory management unit;
means for finding a longest prefix match for the destination IP address in a longest prefix match (LPM) table of the memory management unit and a pointer to the route information table based on the longest prefix match, after finding the destination IP address in the route information table;
means for randomly choosing one of the equal cost paths stored in the route information table based on the pointer associated with the longest prefix match; and
means for sending the packet out of a network device which includes the memory management unit, the packet including route information for the chosen equal cost path.
15. The apparatus of claim 14 , 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.
16. The apparatus of claim 14 , 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.
17. The apparatus of claim 14 , further comprising:
means for determining a copy count value that represents a number of copies of the packet that have been generated,
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.
18. The network device of claim 1 , wherein the network device is configured to randomly choose one of the equal cost paths by hashing from the destination IP address to one of the equal cost paths for the longest prefix match.