Static information storage and retrieval – Addressing – Counting
Reexamination Certificate
2000-11-28
2002-09-10
Le, Vu A. (Department: 2876)
Static information storage and retrieval
Addressing
Counting
C365S049130
Reexamination Certificate
active
06449214
ABSTRACT:
BACKGROUND INFORMATION
1. Field of the Invention
The present invention relates to the field of integrated circuits, and particularly to statistics memories.
2. Description of Related Art
Electronic devices in many instances are used to maintain an accurate count of an event. Whether an electronic device counts the number of packets that transit a router in the Internet or an electronic device that monitors the number of cars of a certain make that drive past an observation point on the side of a highway, similar principles of counting apply. When an event occurs, the counter increments by one. In some instances for example, the counter records the weight of the vehicles, the counter is typically increase by a number larger than one.
In order for this counter to be stored within the electronic device, the counter is placed within some electronic storage medium. Since this medium cannot be infinite in size, a size is wisely chosen that will suit the needs of the event being counted. Three factors need consideration when determining the size of the storage for a single counter: first, the highest rate possible that the event could occur; second, the amount by which the counter could be incremented; third, the rate at which the counter is copied to a location elsewhere and can then be reset to zero.
A common shortcoming that results when determining the appropriate size of a counter is that one needs to consider the worst possible case and then size the counter to hold that worst case. For example, in a device that counted the makes of cars, if it is determined that the maximum rate of cars that can pass the device is 1000 cars per hour and that the counts will be recorded once a day, then the maximum value that a counter will have to hold is 24000-1000 cars per hour * 24 hours. But since it is desirable to have an individual counter per make of car, what size should a counter be selected? In the worst case, every car could be the same make, perhaps due to a large Mercedes convention taking place. To ensure that no make counters overflow, each counter needs to hold 24000. In such instance, the number of individual makes of cars is increased, and the wastage of counters becomes greater and greater. If during one day, only Hondas and Toyotas that used the road, each may have a count of 12000 while all the other counters remained at zero. Since every counter was sized to accept 24000, this is obviously quite wasteful.
A more realistic example of this is for packets being counted each time the packets are forwarded by an Internet router. Packet classification steps within the router group many packets into logical grouping commonly referred to as flows. Numbers of packets received and the number of bytes within the received packets are then counted against these flows. In the same way that the counters in the example above had to be sufficiently large to handle the case where all cars were the same make, the counters in the Internet router needs to be large enough to handle the case where a significant portion of the packets belong to the same logical grouping. As is the case in the car example above, the resulting counter design is quite wasteful in order to cover the worst-case counter size scenario.
FIG. 1
shows a conventional architectural diagram of a statistics memory
10
coupled to a statistics logic or microprocessor
11
. In this illustration, the statistics memory
10
has a length of 512K (524,288) entries, with each counter having a worst case of 42 bits in width, totaling 21 Mbits in the size of the statistics memory
10
. Such crude approach in designing a statistics memory fails to optimally utilize the memory capacity, requires a larger die size, and increases the manufacturing costs.
Accordingly, it is desirable to have a statistics memory design that significantly reduces the wastefulness of in storing counter contents.
SUMMARY OF THE INVENTION
The present invention overcomes the foregoing limitations by using small counters for the events that occur infrequently, and larger counters for the events that happened often. In one embodiment, a binary CAM is provided to reduce the storage space required for statistics counters by learning which events requires larger counters as events are recorded. A CAM is a memory that stores data in association with a specified key. When data is stored in a CAM, data and an associated key are given to the CAM. When the data is desired, the CAM is presented with the key and the CAM will use the key to find its associated data. If the key has not been stored in the CAM before the request, no match is found and no data is returned.
Advantageously, in commercial applications that require accurate storage of a large number of mutually exclusive counters, the present invention significantly reduces the memory storage requirements of counters, resulting in allocating much less space to each of the counters. If some of the counters exceed their storage space, the excess counter information is stored in a CAM entry that is associated with the counter's address. The present invention also minimizes or eliminates off-chip delays by the usage of internal or embedded memories on an integrated circuit.
REFERENCES:
patent: 5179549 (1993-01-01), Joos et al.
patent: 6304903 (2001-10-01), Ward
patent: 2002/0010793 (2002-01-01), Noll et al.
Carr David W.
Funnekotter Edward D.
Fernandez & Associates LLP
Le Vu A.
Silicon Access Networks
LandOfFree
Statistics counter overflow content addressable memory (CAM)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Statistics counter overflow content addressable memory (CAM)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistics counter overflow content addressable memory (CAM)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2867354