Prefix search circuitry and method

Details Prefix search circuitry and method Prefix search circuitry and method

2006-10-18

2010-02-23

Pham, Khanh B (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C370S389000, C370S408000, C370S413000

Reexamination Certificate

active

07668890

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.

REFERENCES:
patent: 5729228 (1998-03-01), Franaszek et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 5983223 (1999-11-01), Perlman
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6081522 (2000-06-01), Hendel et al.
patent: 6147996 (2000-11-01), Laor et al.
patent: 7023807 (2006-04-01), Michels et al.
patent: 2003/0058864 (2003-03-01), Michels et al.
Perlman, Radia, “Interconnections, Bridges and Routers,” Addison Wesley, 1992, pp. 233-239.
Cormen, Leiserson and Rivest, “Introduction to Algorithms,” 1990, pp. 381-399.
Lampson, B., et al., “IP Lookups using Multiway and Multicolumn Search,” 26 pp., May 1998.
Doreinger, et al., “Routing on Longest-Matching Prefixes,” IEEE/ACM Transactions on Networking, vol. 4, No. 1, Feb. 1996, pp. 86-97.
Zitterbart, et al., “Efficient Routing Table Lookup for IPv6”, High-Performance Communications Systems, Jun. 1997, The Fourth IEEE Workshop, pp. 1-9.
Computer Dictionary, Microsoft Press, Redmond, Washington, 1997, p. 456.

Affiliated with

Also associated with

Rating

Prefix search circuitry and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Prefix search circuitry and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix search circuitry and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4229219