Method of validating data in circular buffers

Details Method of validating data in circular buffers Method of validating data in circular buffers

2001-09-13

2003-06-10

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C710S056000, C710S057000, C714S719000

Reexamination Certificate

active

06578105

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to digital communications, and more particularly to a method of managing a circular buffer.
BACKGROUND OF THE INVENTION
Circular buffers are used in many applications where, for example, data may arrive at a varying rate and need to be read out at a constant rate. A particular application of circular buffers is in ATM circuit emulation services, where cells carrying constant bit rate data arrive at varying times determined by CDV (Cell Delay Variation), and the data contained in the cells has to be read out onto a TDM bus at a constant rate.
In a circular buffer, it is of course possible for the incoming data to get too far ahead of the reading of the outgoing data for the size of the buffer, in which case unread data will be overwritten by new data and an “overrun” will occur. Similarly, if the new data arrives at an insufficient rate to replenish the data in the buffer, the read-pointer will re-read old data, and in this case an “underrun” occurs. It is important to be able to identify buffer underruns and overruns.
Mitel Corporation makes a SAR (Segmentation and Reassembly) device sold under product number MT90500 for creating TDM data streams from incoming ATM cells, which are written into circular buffers (one for each TDM channel). A single-bit flag in the data circular buffer is used to indicate whether the data in a memory location has been read. This bit is cleared upon data writes and is set (written to ‘1’) after the data is read, to indicate that the data has been read.
Additionally, the MT90500 and other devices overwrite the circular buffer data itself with FFh (or some other pre-specified pattern) to indicate that the data has been read.
U.S. Pat. No. 5,584,038 discloses a method of using wrap bits in a circular buffer to indicate whether a queue of the circular buffer has been traversed.
U.S. Pat. No. 5,978,868 discloses a system for generating buffer status flags by comparing read and write pointers and determining direction of progression of a read-pointer with respect to a write pointer.
An object of the present invention is to permit the identification of read underruns without the need for semaphore flags.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method of managing a circular buffer, comprising writing data into said circular buffer at an address pointed to by a write pointer, and writing into said address a first number that increments modulo a predetermined number each time said circular buffer is traversed by the write pointer.
The number is preferably in the form of a most significant bits (MSB) extension of the write pointer. It typically consists of two extra bits, which permit four distinct rotations 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, etc. These two extra bits are written into the circular buffer alongside the circular buffer data. The two extra bits are called “turns”. The number could also consist of a single bit.
A similar number is incremented each time the read pointer traverses the circular buffer. When data is read from the circular buffer, the number associated with the read pointer is compared to the number associated with the data in the buffer. This enables the validity of the data to be checked (i.e., to determine whether or not an underrun has occurred). Typically, the number associated with the read pointer is also in the form of an extension to the read pointer, typically two extra most significant bits.
This technique permits the system to distinguish between a short-duration underrun and a long-duration underrun or between an overrun and an underrun by the magnitude of the difference in the “turns” bits associated with the data in the buffer address being read and the read pointer.
In another aspect the invention provides a circular buffer comprising a plurality of address locations for storing data; a write pointer for pointing to an address in said circular buffer where incoming data is to be written; a read pointer for pointing to an address in said circular buffer from which data is to be read out; and each of said buffer addresses including a register portion storing a first number associated with said write pointer, said first number incrementing modulo a predetermined number each time said circular buffer is traversed by the write pointer.


REFERENCES:
patent: 4692893 (1987-09-01), Casper
patent: 4821171 (1989-04-01), Calamari
patent: 4916658 (1990-04-01), Lee et al.
patent: 4942553 (1990-07-01), Dalrymple et al.
patent: 5438575 (1995-08-01), Bertrand
patent: 5696768 (1997-12-01), Harriman et al.
patent: 5884101 (1999-03-01), Wu
patent: 6337893 (2002-01-01), Pontius
patent: 6408409 (2002-06-01), Williams et al.
patent: 94/11800 (1994-05-01), None
MT90500, Multi-Channel ATM AAL1 SAR.

Affiliated with

Also associated with

Rating

Method of validating data in circular buffers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of validating data in circular buffers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of validating data in circular buffers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3145863