Range check cell and a method for the use thereof

Details Range check cell and a method for the use thereof Range check cell and a method for the use thereof

2001-07-18

2004-07-20

Coby, Frantz (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C365S049130, C365S185250

Reexamination Certificate

active

06766317

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a range check cell and a method for the use thereof in determining the range match of incoming data values in a database. The invention particularly relates to a range check cell which stores the Upper Limit and Lower Limit of a specified range and facilitates a range match on an incoming data value within one content addressable memory (CAM) operation.
The present invention relates to intelligent range check cells for use in coprocessors using the classless Inter domain routing protocol, which is a subset of the Internet protocol. More particularly, the present invention relates to intelligent range check cells, which can be used as building blocks for a database management system to enable matching of input data to a user determined range of stored data in the system. The present invention also relates to a method for retrieving data, from a plural range of stored data, which matches or is similar to input retrieval data.
BACKGROUND OF THE INVENTION
In the field of information technology, the ability to store, obtain, process, retrieve and transfer data speedily and accurately is critical. Data can include voice, images, pictures, words or any combination thereof.
The necessity for faster and accurate transfer and retrieval of data has increased with the use of the Internet data communication. Data communication over the Internet is performed in accordance with a specific protocol. Each protocol specifies how the data is sent from the source point to the destination point.
The IP protocol governs the data and voice communication over the Internet. The CIDR protocol, which is a subset of the IP protocol, governs addressing over the Internet. Under the CIDR protocol, the correct destination address is the one that is associated with the longest prefix. Each Internet address in the CIDR protocol is associated with an IP address and a sub-net mask value. In each router, the routing tables are constructed out of prefix information and are searched using the destination address to determine the exit port of the router. According to the CIDR protocol, a sub-net mask value could only include a series of consecutive “1s” followed by “0s.” “1” represents that the corresponding bit in the associated IP address is used to determine the final physical address of the destination.
A transfer of information between two points begins by the user sending a packet of information to the receiver. Depending upon the location of the receiver, the information may have to travel through several networks before it reaches the receiver. It therefore, becomes very important that the information travels accurately through the shortest possible route from the sender to the receiver. It becomes all the more difficult since different destinations may have portions of their address in common with each other.
As the number of networks and destinations which are interconnected increases by the day, it is highly important that routers in each network are able to route the information as fast as possible to the final destination. The current technology takes a long time to determine the correct address in a router to route the information. For example, a 16 bit address could require up to 15 clock cycles to be determined in the currently available technology. In networks incorporating a wider address such as 128 bits, it would take more time to accurately determine the address of the final destination.
In computing or in everyday use of computers, it becomes essential to access databases to recover specific information of value. The need for speed of data recovery by the user is closely allied to the need for accuracy of results. One solution in the art to ensure speed and accuracy in the field of data recovery is to convert the applied data into a specific code and to match the applied code entry by entry with the data stored in the database. This process however, is in computing terms quite long drawn. This process works by matching the applied data with the data stored in the database in the form of a range.
The known solutions to the range match problem fall in two categories:
1. Sequential memory based: These solutions typically expand the range field and hence require either a huge memory or multiple accesses to the table.
2. CAM based: These solutions try to split the range search into multiple prefix searches and use a ternary CAM to do these searches. Hence multiple entries are required for each range value and multiple searches are also required.
Thus there is a need for a search cell capable of searching a database in the shortest possible time without compromising on the accuracy of the results.
The applicants' own co-pending application Ser. No. 09/865,241 filed on May 24, 2001 overcomes many of the problems associated with the prior art and discloses a novel search cell for use as a building block of a database and which is capable of performing hierarchical searches in the database as well as a method thereof. The novel search cell of the co-pending application includes a plurality of Logic Content addressable Memory Cells (LCAMS) arranged in rows and columns. Each LCAM cell includes a first and second memory cells, a first comparator coupled to the first and second memory cells for comparing the content of the first memory cell with one bit of a test information. To search for a second data type entry, the search cell searches for the longest prefix entry belonging to the first data type by comparing test information with the entries stored in the first storage unit. Once the longest prefix entry is determined, a corresponding entry in the second storage unit is output as the output of the search cell. The contents of said U.S. patent application are deemed to have been incorporated herein by reference.
Content addressable memory cells are well known in the art and are used to compare a search word with a set of stored words. An indication of whether or not the search word matches the stored words is produced for each stored word. A distinguishing characteristic of a CAM is that each stored word is uniquely identified on the basis of the content of the word itself, rather than by its address within the memory array.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory elements constitute a stored word. During a match operation, a search word of input data is applied to all the rows, and an indication is produced for each row as to whether or not the search word matches the word stored therein.
An important use for a CAM is to facilitate searches on a conventional indexed random access memory (RAM). The CAM stores a series of “tags” which represent address locations in the RAM. Match operations are performed on the CAM in order to detect the locations of data stored in the RAM. When match data is presented to the CAM, the CAM responds with a “tag” representing the address location in RAM containing the desired data. This address location is then driven to the RAM's address lines in order to access the data.
A conventional content addressable memory has a plurality of word data memories respectively having memory cells, the number of which corresponds to a number of bits of a word. The memory cells are respectively activated by word lines, thereby the data stored in the memory cells are read out respectively via bit lines. Such data read out from the memory cells via the bit lines are respectively supplied to a plurality of match detection-circuits.
Each of the match detection circuits detects whether data on one of the bit lines matches data from a corresponding one of the memory cells, i.e., when a circuit operation signal line which is common to the entire words is in an active state. Each of the match detection circuits activates its corresponding one of match signal lines when the data on the entire bit lines match the data from the memory cells.
When retrieving data in the content addressable memory, t

Affiliated with

Also associated with

Rating

Range check cell and a method for the use thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Range check cell and a method for the use thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Range check cell and a method for the use thereof will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3212702