Prefix search method

• US 7,130,847 B2
• Filed: 07/28/2003
• Issued: 10/31/2006
• 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): Pham, Khanh B.
• Application Number:
  US10/628,312
• Publication Number:
  US 20040111402A1
• Time in Patent Office: 1,191 Days
• Field of Search: 707/3, 707/6, 707/7, 707/100, 707/101, 370/408, 370/413, 709/238
• US Class Current: 707/706
• 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 SDRAMs 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. A method of prefix search comprising:

applying prefix search keys to an input queue;

distributing the prefix search keys from the input queue to plural prefix search engines over a network from the input queue as the engines become idle;

at each search engine, reading data from a prefix search data tree structure stored in memory and, in a comparator, performing prefix search comparisons of search keys and data from the prefix search tree data structure to determine, in a forward pass of the tree data structure toward a leaf, memory addresses of nodes of the tree data structure to read the data from memory and obtain prefix search results; and

forwarding results of prefix searches of the plural prefix search engines over the network to an output queue in an order independent of the order in the input queue.

2. A method as claimed in claim 1 wherein the results of the prefix searches are ordered in the output queue in the same order that the corresponding prefix search keys arrived at the input queue.

3. A method as claimed in claim 1 further comprising:

addressing a memory unit from each search engine over integrated circuit pins shared with another search engine; and

reading the data in bursts over integrated circuit data pins dedicated to the search engine from the address locations in the memory unit.

4. A method as claimed in claim 3 further comprising storing a prefix search tree data structure across plural banks of memory units and accessing the tree structure in successive read cycles.

5. A method as claimed in claim 1 further comprising storing a prefix search tree data structure across plural banks of memory units and accessing the tree structure in successive read cycles.

6. A method as claimed in claim 5 wherein duplicate copies of internal nodes of the tree structure are stored in each of plural banks.

7. A method as claimed in claim 6 wherein leaf nodes are interleaved across plural banks.

8. A method as claimed in claim 1 wherein the determined memory address is the address of the next tree node.

9. A method as claimed in claim 8 wherein the determined memory address is determined from a comparison of plural stored keys with the search key.

10. A method of prefix search comprising:

distributing prefix search keys to plural prefix search engines; and

at each search engine, reading data from a prefix search data tree structure stored in memory and, in a comparator, performing prefix search comparisons of search keys and data from the prefix search tree data structure to determine, in a forward pass of the tree data structure toward a leaf, memory addresses of nodes of the tree data structure to read the data from memory and obtain prefix search results, the step of reading data further comprising;

addressing a memory unit from each search engine over integrated circuit pins shared with another search engine; and

reading the data in bursts over integrated circuit data pins dedicated to the search engine from the address locations in the memory unit.

11. A method as claimed in claim 10 further comprising storing a prefix search tree data structure across plural banks of memory units and accessing the tree structure in successive read cycles.

12. A method of prefix search comprising:

distributing prefix search keys to plural prefix search engines; and

at each search engine, reading data from a prefix search data tree structure stored in memory and, in a comparator, performing prefix search comparisons of search keys and data from the prefix search tree data structure to determine, in a forward pass of the tree data structure toward a leaf, memory addresses of nodes of the tree data structure to read the data from memory and obtain prefix search results, the method further comprising storing a prefix search tree data structure across plural banks of memory units, duplicate copies of internal nodes of the tree structure being stored in each of plural banks, and accessing the tree structure in successive read cycles.

13. A method as claimed in claim 12 wherein leaf nodes are interleaved across plural banks.