Fast data base research and learning apparatus

• US 6,490,279 B1
• Filed: 07/23/1998
• Issued: 12/03/2002
• Est. Priority Date: 07/23/1998
• Status: Expired due to Fees

• Current Assignee: Advanced Communication Concepts Incorporated
• Original Assignee: Advanced Communication Device Incorporated
• Inventors: Wang, Ying, Chen, Honglu, Tsui, Tak-Lap
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/121,586
• Time in Patent Office: 1,594 Days
• Field of Search: 370/356, 370/363, 370/364, 370/365, 370/368, 370/382, 370/389, 370/392, 370/397, 370/399, 370/400-404, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/419, 370/428, 370/429, 370/235-235, 370/475, 395/200-800, 709/230, 709/238, 707/6, 711/150, 711/157, 711/168, 711/169, 711/211, 711/216
• US Class Current: 370/392
• CPC Class Codes: H04L 12/56 Packet switching systems

Abstract

This invention discloses an improved address table apparatus that includes an address bus for receiving input data packets and for hashing a designated bucket number and extracting a key from each of the data packets. The address table apparatus further includes a plurality of memory banks connected to the address bus wherein each memory bank includes a plurality of memory buckets for storing a designation address (DA) and a port number in each of the buckets. The address table apparatus further includes a comparand bus connected to the address bus for receiving the key therefrom. The address table apparatus further includes a plurality of comparators each corresponding to one of the memory banks for receiving the designation address (DA) and the port number from the designated bucket from a corresponding memory bank. The comparators further connected to the comparand bus for receiving and comparing the key to the address from the designated bucket in each of the memory banks. The address table apparatus further includes a result bus connected to the comparators for displaying an output port number from one of the comparators if the key extracted from one the data packets matching the designation address (DA) from one of the designated buckets.

Claims

1. An address table apparatus comprising:

an address bus for receiving input data packets and for hashing a designated bucket number and extracting a key from each of said data packets;

a plurality of memory banks connected directly to said address bus wherein each memory bank includes a plurality of memory buckets for storing a destination address (DA) and a port number for each of said packets in each of said buckets having a bucket number corresponding to a bucket number hashed from said each of said data packets;

a comparand bus connected to said address bus for receiving said key therefrom;

a plurality of comparators each corresponding to one of said memory banks for directly connected to and receiving said destination address (DA) and said port number from said designated bucket from a corresponding memory bank, said comparators further connected directly to said comparand bus for receiving and comparing said key to said address from said designated bucket in each of said memory banks; and

a result bus connected directly to said comparators for displaying an output port number from one of said comparators if said key extracted from one said data packets matching said destination address (DA) from one of said designated buckets.

2. The address table apparatus of claim 1 wherein:

said address bus, said comparand bus, said result bus, and

said memory banks are disposed on a semiconductor chip.

3. The address table apparatus of claim 2 wherein:

said address bus and said comparand bus having a bus-width equal to or more than 1024 bits.

4. The address table apparatus of claim 1 further comprising:

a command queue for receiving and temporarily storing a plurality of lookup/learning commands therein; and

a command parser for processing said lookup/learning commands for generating said data packets for inputting to said data bus.

5. The address table apparatus of claim 4 further comprising:

a result queue for receiving and temporarily storing said port number from said result bus.

6. A method for performing a lookup operation over an address table comprising:

(a) receiving input data packets from an input address bus for hashing a designated bucket number and extracting a key from each of said data packets;

(b) reading a destination address (DA) and a port number from a memory bucket corresponding to said designated bucket number from each of a plurality of memory banks each having a plurality of said memory buckets for storing a destination address (DA) and a port number in each of said memory buckets;

(c) employing a plurality of comparators for receiving said destination address (DA) and said port number and for comparing said key to said address from said designated bucket in each of said memory banks; and

(d) displaying an output port number from one of said comparators if said key extracted from one said data packets matching said destination address (DA) from one of said buckets corresponding to said designated bucket number.

7. The method for performing a lookup operation over an address table of claim 6 further comprising:

(e) displaying an unknown key if said key extracted from one said data packets does not match any of said destination addresses (DA) from all of said buckets corresponding to said designated bucket number.

8. A method for performing a learning operation over an address table comprising:

(a) receiving an input data packet from an input address bus for hashing a key into a designated bucket number;

(b) finding an empty memory bucket among a plurality of memory buckets corresponding to said designated bucket number from a plurality of memory banks wherein each of said memory banks configured for having a plurality of memory buckets; and

(c) storing said key and said data packet in said empty memory bucket found in one of said memory banks and returning a learning success message if an empty memory bucket is found and returning a bucket overflow message if no empty memory bucket is found in said step (b).

9. The method for performing a learning operation over an address table of claim 8 further comprising:

(d) returning a bucket overflow message when none of the memory buckets corresponding to said designated bucket number from said plurality of memory banks is empty.

10. The method for performing a learning operation over an address table of claim 8 wherein:

said step (c) of storing data of said data packet in said empty memory bucket is a step of storing a destination address and port number in said empty memory bucket.

11. An address table apparatus comprising:

a command queue for receiving and temporarily storing a plurality of lookup/learning commands therein;

a command parser for receiving from said command queue and for processing said lookup/learning commands for generating a lookup command or a learning command;

a lookup logic for receiving and processing said lookup command for generating a designated bucket number and a lookup key number;

an address table having a plurality of memory banks connected to said lookup logic wherein each of said memory banks includes a plurality of memory buckets for storing a lookup address and a lookup output data in each of said buckets;

a comparand bus connected directly to said lookup logic for receiving said lookup key therefrom;

a plurality of comparators each corresponding to one of said memory banks for receiving said lookup address and said lookup data from a memory corresponding to said designated bucket number of a corresponding memory bank, said comparators further connected to said comparand bus for receiving and comparing said lookup key to said lookup address from each of said memory buckets corresponding to said designated bucket number; and

a result queue connected to said comparators for receiving and temporary storing a lookup output data from one of said comparators if said lookup key matching said lookup address from one of said memory buckets.

12. The address table apparatus of claim 11 further comprising:

a learning logic for receiving and processing said learning command for generating a designated bucket number and a memory-bucket storage data;

said learning logic further having an empty memory bucket means for searching an empty memory bucket from a plurality of memory buckets corresponding to said designated bucket number in each of said memory banks; and

said learning logic further having a data-storing means for determining an empty memory bucket is found and for storing said memory-bucket storage data into said empty memory bucket.

13. The address table apparatus of claim 12 wherein:

said command queue, said command parser, said lookup logic, said learning logic, said comparand bus, said result queue, and said address table are disposed on a semiconductor chip.

14. The address table apparatus of claim 13 further comprising:

an address bus for passing said lookup command and said learning command to said address table; and

said address bus and said comparand bus having a bus-width equal to or more than 1024 bits.

15. The address table apparatus of claim 11 further comprising:

a cascaded address table apparatus provided for receiving a command from said address table apparatus for pipelined operation.