Table lookup mechanism for address resolution

• US 7,593,953 B1
• Filed: 11/17/2000
• Issued: 09/22/2009
• Est. Priority Date: 11/18/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Malalur, Govind
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/714,273
• Time in Patent Office: 3,231 Days
• Field of Search: 707/7, 707/3, 707100-102, 707/104.1, 707/5, 707/2, 707/127, 707/129, 707/1
• US Class Current: 1/1
• 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. A method of performing a table look-up in a network device comprising the steps of:

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

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

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

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

2. The method as claimed in claim 1 wherein said step of indexing said index portion to said bucket portion is the step of linearly indexing said index portion to said bucket portion.

3. The method as claimed in claim 1 wherein said step of indexing said index portion to said bucket portion is the step of XOR indexing said index portion to said bucket portion.

4. The method as claimed in claim 1 further comprising the step of sorting said bucket portion.

5. The method as claimed in claim 1 further comprising the step of binary sorting said bucket portion.

6. The method as claimed in claim 1 wherein the step of parsing said data packet into an index portion and a corresponding bucket portion further comprises the step of 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.

7. The method as claimed in claim 1 further comprising the step of 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.

8. An address table look-up indexing device comprising:

a receiver portion of a port of a network device that receives an incoming data packet;

a data parser that parses said data packet into an index portion and a corresponding bucket portion;

an indexer that directly indexes said index portion to said bucket portion; and

an address lookup device that accesses an address look-up table using said corresponding bucket portion.

9. The device as claimed in claim 8 wherein said indexer linearly indexes said index portion to said bucket portion.

10. The device as claimed in claim 8 wherein said indexer XOR indexes said index portion to said bucket portion.

11. The device as claimed in claim 8 further comprising a sorter that sorts said bucket portion.

12. The device as claimed in claim 11 wherein said sorter binary sorts said bucket portion.

13. The device as claimed in claim 11 wherein said data parser parses said index portions into groups such that each said index portion in a group is the same as other index portions in said group.

14. The device as claimed in claim 8 further comprising a storage mechanism that stores information regarding said data packet 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.

15. A network switch comprising:

multiple ports used for receiving and exporting data, each of said multiple ports being connected to one another through a communications medium;

multiple Address Resolution Logic (ARL) devices, each of said multiple ARL devices being connected to one of said multiple ports, each of said multiple ports having a corresponding ARL device, each of said multiple ARL devices comprising;

a parser that parses data into an index portion and a corresponding bucket portion;

an indexer that directly indexes said index portion to a corresponding bucket portion;

a look-up device that accesses table entries in a look-up table using said bucket portion.