Data processing: database and file management or data structures – Database design – Data structure types
Patent
1998-02-24
2000-04-18
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 6, 707 7, 707 9, G06F 1700
Patent
active
060526831
ABSTRACT:
An apparatus for performing an address lookup to find a longest matching prefix for an N-bit input address in a packet data communication system that includes a memory (e.g. RAM) for storing a table containing a predefined portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix. A binary search algorithm is used for selecting a specific prefix value from the prefix search list to structure the N-bit input address to form a search value. A search algorithm (e.g. a content addressable memory) is used for performing an associative search on the search value to find the longest matching prefix. The two types of memories (RAM and CAM) each provide specific functions. The RAM is used as a lookup table to provide an N/x-bit (0<x<N) binary decoding tree, and the CAM is used to provide an associative search of network addresses that are stored in logical bins that have a specific network prefix. By using the binary search algorithm that is guided by the lookup table data, the CAM can be probed to find the longest matching prefix.
REFERENCES:
patent: 5229936 (1993-07-01), Decker et al.
patent: 5281967 (1994-01-01), Jung
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5488608 (1996-01-01), Flammer, III
patent: 5525982 (1996-06-01), Cheng et al.
patent: 5561421 (1996-10-01), Smith et al.
patent: 5794177 (1998-08-01), Carus et al.
patent: 5890103 (1999-03-01), Carus
Degermark, Mikael et al., Smalls Forwarding Tables for Fast Routing Lookups, Department of Computer Science and Electrical Engineering, Lule.ang. University of Technology, S-971 87 Lule.ang., Sweden, no date.
Waldvogel, Marcel et al., Scalabe High Speed IP Routing Lookups, Computer Engineering and Networks Laboratory, ETH Zurich, Switzerland; Computer and Communications Research Center, Washington University in St. Louis, USA, no date.
Black Thomas G.
Jung David
Nortel Networks Corporation
Wood Max R.
LandOfFree
Address lookup in packet data communication networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Address lookup in packet data communication networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address lookup in packet data communication networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2344876