Equal and weighted cost multipath load balancing in a network device

• US 20040264374A1
• Filed: 06/24/2004
• Published: 12/30/2004
• 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: Dull, Jeff, Chen, Yih-Chuan S., Yu, Song-huo
• Granted Patent: US 7,697,432 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• 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
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A method of mediating the flow of datagrams to a destination in a network is disclosed. The method includes the steps of receiving a datagram at a port of a network device, evaluating a destination address for the datagram based on fields in the incoming packet, searching a longest prefix match (LPM) table using the destination address as a LPM key, determining an address table index and an offset based on entries found in the search of the longest prefix match table, searching an address table using the address table index and the offset as an address key to determine an egress port number of the network device and forwarding the packet based upon at least the egress port number.

Claims

1. A method of mediating the flow of datagrams to a destination in a network, said method comprising:

receiving a datagram at a port of a network device;

evaluating a destination address for the datagram based on fields in the incoming datagram;

searching a longest prefix match (LPM) table using the destination address as a LPM key;

determining an address table index and an offset based on entries found in the search of the longest prefix match table;

searching an address table using the address table index and the offset as an address key to determine an egress port number of the network device; and

forwarding the datagram based upon at least the egress port number.

2. A method as recited in claim 1, wherein the step of evaluating a destination address for the packet comprises determining whether the address table contains an entry for a destination IP address contained in the datagram.

3. A method as recited in claim 1, wherein the step of forwarding the packet comprises obtaining an interface number from the searching of the address table and using the interface number to search an interface table to get a router MAC address and a VLAN tag for the packet.

4. A method as recited in claim 1, wherein the step of determining the address table index and the offset comprises obtaining a count value from the searching of the LPM table and using the count value to determine the offset.

5. A method as recited in claim 4, wherein the step of using the count value to determine the offset comprises determining a modulo of the count value and using the modulo to determine the offset.

6. A method as recited in claim 4, wherein the method further comprises updating entries in the address and LPM tables, such that the count value is equal to a number of entries in the address table that represent paths to a same IP destination address.

7. A method as recited in claim 6, wherein the method is performed such that the step of forwarding the datagram comprises forwarding the datagram along the paths to the same IP destination address such that each path of the paths is utilized approximately equally.

8. A network device for mediating the flow of datagrams to a destination in a network, said method comprising:

receiving means for receiving a datagram at a port of a network device;

evaluating means for evaluating a destination address for the datagram based on fields in the incoming datagram;

first searching means for searching a longest prefix match (LPM) table using the destination address as a LPM key;

determining means for determining an address table index and an offset based on entries found in the search of the longest prefix match table;

second searching means for searching an address table using the address table index and the offset as an address key to determine an egress port number of the network device; and

forwarding means forwarding the datagram based upon at least the egress port number.

9. A network device as recited in claim 8, wherein the evaluating means comprises second determining means for determining whether the address table contains an entry for a destination IP address contained in the datagram.

10. A network device as recited in claim 8, wherein the forwarding means comprises obtaining means for obtaining an interface number from results obtained from the second searching means and third searching means for searching an address interface table using the interface number to get a router MAC address and a VLAN tag for the datagram.

11. A network device as recited in claim 8, wherein the forwarding means comprises obtaining means for obtaining a count value from the searching of the LPM table and the second searching means is configured to use the count value to determine the offset.

12. A network device as recited in claim 11, wherein the second searching means is configured to determine a modulo of the count value and to use the modulo to determine the offset.

13. A network device as recited in claim 11, wherein the network device further comprises updating means for updating entries in the address and LPM tables, such that the count value is equal to a number of entries in the address table that represent paths to a same IP destination address.

14. A network device for handling data datagrams, comprising:

at least one data port interface, said at least one data port interface supporting a plurality of data ports transmitting and receiving data;

a plurality of lookup tables to determine an egress port based on a destination address contained in a datagram received at one of the plurality of data ports;

wherein the plurality of lookup tables comprises a longest prefix match (LPM) table and an address table and wherein the at least one data port interface is configured to search the LPM table to obtain an entry in the address table containing at least an egress port number of the network device, such that each entry in the address table for the destination address is utilized approximately equally.

15. A network device as recited in claim 14, wherein the plurality of lookup tables further comprises an address interface table and wherein the at least one data port interface is configured to search the address interface table to get a router MAC address and a VLAN tag for the datagram.

16. A network device as recited in claim 14, wherein each entry in the LPM table contains a count filed containing a count value, where the count value is equal to a number of respective entries in the address table for the same destination address.

17. A network device as recited in claim 14, wherein the at least one data port interface is configured to update the address table based on changes in destination addresses and update entries in the LPM table to reflect the changes to the address table.