Static information storage and retrieval – Floating gate – Multiple values
Reexamination Certificate
2001-10-24
2003-12-16
Elms, Richard (Department: 2824)
Static information storage and retrieval
Floating gate
Multiple values
C365S049130, C365S236000, C365S239000, C711S108000
Reexamination Certificate
active
06665210
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to data storage and retrieval and in particular to the storage and retrieval of items of data consisting of associated value pairs.
2. Description of the Related Art
A typical computer network may consist of several end-user computer terminals which are interconnected via one or more central computer systems. Data is known to be transferred around such a network in the form of blocks, commonly called packets. Communication between various parts of the network may be achieved using a value known as a circuit ID. Each circuit ID is specific to the connection between two particular parts of the network. A packet which is to be sent between those particular parts has the corresponding circuit ID encapsulated within it. The circuit ID has an associated value termed the information value, and the circuit ID and information are stored together as an item of data id a memory of the network. To send data between the two particular parts, the network hardware has to extract the circuit ID from the packet and retrieve from the network memory the associated information value. The packet is then routed, encrypted or otherwise operated on as dictated by the information value.
Asynchronous transfer mode (ATM) protocols utilised in computer network communications operate along the lines described above. Data is transferred around an ATM network in short packets called cells, each of which includes a circuit ID in 24-bit binary form. Thus, 2
24
(over 26 million) different IDs are feasible. As a consequence, processors within an ATM network must be able to retrieve one of a potentially large number of information values for routing etc. the cell whilst still keeping pace with the arrival of new cells for processing.
It is possible to store data in a random access memory (RAM) device with as many storage locations as the maximum feasible number of data items. For instance, in the case of an ATM network, this would mean a 2
24
storage location RAM. However, by current standards, this constitutes a very large RAM and may be difficult to fit on to a single integrated circuit, which is preferable. In addition, an ATM network will typically have only a small proportion of the total number of possible circuit IDs active at any one time, which means utilisation may be poor. Furthermore, an increase in the bit form of the circuit ID, for example in the case of the ATM network ID to 28- or 32-bit form, would necessitate an even larger RAM.
Rather than using a large RAM for storing data, typical networks, like an ATM network, tend to use so-called content addressable memories (CAMs). CAMs are capable of storing items of data consisting of pairs of values, such as an identifier value and an information value. Data can be retrieved from a CAM by presenting an identifier value and the associated information value is returned. A key feature of the CAM is that the total number of possible identifier values may greatly exceed the available storage locations, and not all possible identifier values can be stored simultaneously in the device.
A CAM device for an ATM network can be constructed by having a number of storage locations, each storing an identifier value and information value pair, and a comparator for comparing the stored identifier value and the input identifier value. Several thousand such cells are required for an ATM network, which means that a CAM can only realistically be implemented in custom integrated circuits. In addition, to insert a new value into a CAM requires searching for a location which does not contain a valid data pair. This can be time consuming.
A modification on the basic form of CAM is the hash table CAM. This is a device having a number of storage locations (indexed by a number i) each of which contains a pair of values, such as an identifier value and an associated information value, or may be empty. Each pair of values is stored using a hash function which generates an index value i from the identifier value, and the pair of values are stored in the location with the index *value i. The hash function reduces the range of identifier values to a smaller range of index values. This reduces the memory size requirements, and makes it practically feasible to build the CAM on a single integrated circuit.
The problem with a hash table CAM is that because the hash function reduces the large set of input values to a smaller set of index values, necessarily there will be two or more input values which map on to the same index value. This is called a collision and means that these two input values cannot be stored in the table at the same time.
Collision avoidance mechanisms have been implemented in software. The input value is initially processed by the hash table to produce an index value i. If the location corresponding to that i index value is already full, an adjacent range of i values, i.e. i+k, i+2k etc., is tried each in turn sequentially until an empty location is found. Such collision avoidance mechanisms have also been implemented in hardware. Although this is the simplest form of collision avoidance mechanism, it is highly inefficient when k is fixed. Alternatively, k may be derived from the input value via a so-called “hash function”. This is more efficient, but usually involves arithmetic operations such as multiplication and division which are costly to build into hardware.
The present invention seeks to provide an improved memory device.
SUMMARY OF THE INVENTION
The invention provides a memory device for storing items of data, each item consisting of an identifier value and an information value, which device comprises an array of storage locations each identified by a unique index value, counting means for providing numbers from a number sequence and processing means for generating an index value for each item of data as a function of the identifier value of the item of data and a number from the number sequence wherein the item of data is stored in the location corresponding to the generated index value or, if that location is already occupied, in an alternative location corresponding to the index value generated as a function of the identifier value of the item of data and a subsequent number from the number sequence.
The device according to the invention enables the use of random functions for the generation of the index value. This leads to more efficient utilisation of the device. With known simple counting based generation methods, the likelihood of not finding an unoccupied location within the permitted number of attempts to locate data is high because if a location is already occupied, the probability is that the alternative location is also occupied. However, generation of the index value using a random function means that the alternative location is unlikely to be occupied. Thus, more data may be located before any item of data cannot be located within the maximum number of permitted attempts.
REFERENCES:
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5623545 (1997-04-01), Childs et al.
patent: 6044077 (2000-03-01), Luijten et al.
Le Toan
nCipher Corporation Limited
Young Law Firm P.C.
LandOfFree
Data storage and retrieval does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data storage and retrieval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data storage and retrieval will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3140986