TABLE LOOKUP MECHANISM FOR ADDRESS RESOLUTION

• US 20100014516A1
• Filed: 08/05/2009
• Published: 01/21/2010
• Est. Priority Date: 11/18/1999
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Malalur, Govind
• Granted Patent: US 8,086,571 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A table lookup indexing system for the transmission of data packets in a network switch. Data is received in an input port and is divided into two parts, an index portion and a bucket portion. The index portion selects a particular bucket and the combination of the index portion and bucket portion selects a specific entry in the table.

Claims

1. (canceled)

2. An apparatus for performing a table look-up in a network device comprising:

means for receiving a data packet through an input port of the network device;

means for parsing said data packet into an index portion and a corresponding bucket portion;

means for indexing, directly, said index portion to said corresponding bucket portion; and

means for accessing address table information stored in an address look-up table using said bucket portion.

3. The apparatus of claim 2 wherein said means for indexing said index portion to said bucket portion comprises means for linearly indexing said index portion to said bucket portion.

4. The apparatus of claim 2 wherein said means for indexing said index portion to said bucket portion comprises means for XOR indexing said index portion to said bucket portion.

5. The apparatus of claim 2 and further comprising means for sorting said bucket portion.

6. The apparatus of claim 2 and further comprising means for binary sorting said bucket portion.

7. The apparatus of claim 2 wherein said means for parsing said data packet into an index portion and a corresponding bucket portion further comprises means for parsing said index portion so that said index portion will recur when other data is parsed into said index portion and said corresponding bucket portion.

8. The apparatus of claim 2 and further comprising means for storing information regarding said data in said address look-up table as address table information when no address table information is available using said bucket portion to access address table information.

9. A method comprising:

receiving data including a MAC address at a port of a network switch having multiple ports;

parsing the MAC address into an index portion and a bucket portion;

indexing the index portion to the bucket portion; and

accessing an entry in a look-up table based on the bucket portion to determine which port of the multiple ports the data should be sent for output.

10. The method of claim 9 and further comprising storing information regarding said data in said address look-up table as address table information when no address table information is available using said bucket portion to access address table information.

11. The method of claim 9 and further comprising:

determining that there is no entry in the look-up table based on the bucket portion;

sending the MAC address to multiple ports on the network switch, when there is no entry in the look-up table based on the bucket portion;

receiving a message from a responding port of the network switch indicating that the responding port is the port for outputting data corresponding to the bucket portion; and

adding an entry in the look-up table indicating that the responding port corresponds to the bucket portion.

12. An apparatus comprising:

means for receiving data including a MAC address at a port of a network switch having multiple ports;

means for parsing the MAC address into an index portion and a bucket portion;

means for indexing the index portion to the bucket portion; and

means for accessing an entry in a look-up table based on the bucket portion to determine which port of the multiple ports the data should be sent for output.

13. The apparatus of claim 12 and further comprising means for storing information regarding said data in said address look-up table as address table information when no address table information is available using said bucket portion to access address table information.

14. The apparatus of claim 12 and further comprising:

means for determining that there is no entry in the look-up table based on the bucket portion;

means for sending the MAC address to multiple ports on the network switch, when there is no entry in the look-up table based on the bucket portion;

means for receiving a message from a responding port of the network switch indicating that the responding port is the port for outputting data corresponding to the bucket portion; and

means for adding an entry in the look-up table indicating that the responding port corresponds to the bucket portion.