Prefix search circuitry and method

• US 6,430,527 B1
• Filed: 08/26/1998
• Issued: 08/06/2002
• Est. Priority Date: 05/06/1998
• Status: Expired due to Term

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Avici Systems Inc.
• Inventors: Dally, William J., Carvey, Philip P., Dennison, Larry R., Mann, William F., Waters, Gregory M.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): PHAM, KHANH B
• Application Number:
  US09/140,030
• Time in Patent Office: 1,441 Days
• Field of Search: 370/389, 370/413, 370/408, 707/3, 707/6, 707/7, 709/238
• US Class Current: 703/3
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• 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/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Prefix searches for directing internet data packets are performed in a prefix search integrated circuit. The integrated circuit includes an array of search engines, each of which accesses a prefix search tree data structure to process a prefix search. An SDRAM is dedicated to each search engine, and SDRAMs share address and control pins to plural search engines on the IC chip. Internal nodes of the tree data structure are duplicated across banks of the SDRALMs to increase bandwidth, and leaf nodes are stored across the SDRAM banks to reduce storage requirements. Within each search engine, data stored in a data register from an SDRAM is compared to a prefix search key stored in a key register. Based on that comparison, an address is calculated to access further tree structure data from the SDRAM. Packet descriptors containing search keys are forwarded to the search engines from an input queue and the search results are forwarded to an output queue, the same packet order being maintained in the two queues.

Claims

1. Prefix search circuitry comprising, in an integrated circuit, a plurality of prefix search engines, each performing a prefix search of a prefix search tree data structure based on a prefix search key, each prefix search engine comprising:

a comparator that compares a search key with data from the prefix search tree data structure; and

an address calculator which calculates, in a forward pass of the tree data structure toward a leaf, memory addresses of nodes of the tree data structure based on the comparator output to read data of the prefix search data structure from memory.

2. Prefix search circuitry as claimed in claim 1 further comprising, in the integrated circuit:

an input queue for receiving input packet descriptors;

an output queue; and

a network for distributing prefix search keys from the input packet descriptors to the plurality of prefix search engines as the engines become idle and for forwarding the results of prefix searches of the plural prefix search engines to the output queue in an order independent of the order in the input queue.

3. Prefix search circuitry as claimed in claim 2 wherein the results of the prefix searches are ordered in the output queue in the same order that the corresponding input packet descriptors arrived at the input queue.

4. Prefix search circuitry as claimed in claim 2 wherein the network comprises a bus.

5. Prefix search circuitry as claimed in claim 1 further comprising an array of memory units, each unit dedicated to a search engine within the integrated circuit.

6. Prefix search circuitry as claimed in claim 5 wherein each search engine reads data in bursts over integrated circuit data pins dedicated to the search engine and each search engine addresses a memory unit over integrated circuit pins shared with another search engine.

7. Prefix search circuitry as claimed in claim 6 wherein each memory unit is a synchronous dynamic random access memory (SDRAM).

8. Prefix search circuitry as claimed in claim 6 wherein each memory unit comprises plural banks of memory cells and a prefix search tree data structure is stored across the plural banks to provide access to the tree structure in successive read cycles.

9. Prefix search circuitry as claimed in claim 1 further comprising an array of memory units, each having plural banks of memory cells, and a prefix search tree data structure stored across the plural banks to provide access to the tree structure in successive read cycles.

10. Prefix search circuitry as claimed in claim 9 wherein duplicate copies of internal nodes of the tree structure are stored in each of plural banks.

11. Prefix search circuitry as claimed in claim 10 wherein leaf nodes are interleaved across plural banks.

12. Prefix search circuitry as claimed in claim 1 wherein each prefix search engine comprises a data register which receives data of the tree structure from memory and a search key register, the comparator comparing a search key in the search key register with data from the data register.

13. Prefix search circuitry as claimed in claim 1 wherein the address calculator selects the address of the next tree node based on the comparator output.

14. Prefix search circuitry as claimed in claim 13 wherein the address calculator selects an address as a result of a comparison of plural stored keys with the search key.

15. A prefix search engine comprising:

a data register which receives data of a tree structure from memory;

a search key register;

a comparator which compares a search key in the search key register with data from the data register; and

an address calculator which calculates, in a forward pass of the tree data structure toward a leaf, memory addresses of nodes of the tree data structure based on the comparator output to read the data from memory into the data register.

16. A prefix search engine as claimed in claim 15 wherein the address calculator selects the address of the next tree node based on the comparator output.

17. A prefix search engine as claimed in claim 16 wherein the address calculator selects an address as a result of a comparison of plural stored keys with the search key.