Equalizing FIFO buffer with adaptive watermark

Details Equalizing FIFO buffer with adaptive watermark Equalizing FIFO buffer with adaptive watermark

2000-03-27

2003-11-04

Gaffin, Jeffrey (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S056000, C710S033000, C710S035000

Reexamination Certificate

active

06643719

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to First-in, First-out (FIFO) devices and queuing schemes for data communication systems using frames of data.
BACKGROUND OF THE INVENTION
Frame Relay (FR) networks route FR frames, using a plurality of frame-relay frame handlers, from one terminal equipment station to another. The FR frame structure is defined by American National Standards Institute (ANSI) Standard T1.618. Based on the High-level Data Link Control (HDLC) protocol, frame relay frames are delimited by one or more flags. To avoid data being incorrectly interpreted as a flag, frames of data are “stuffed” prior to transmission using a zero bit insertion algorithm. More specifically, data in FR frames are transported using the following standard HDLC framing:
<flag><data><crc><flag>
where
<flag> is the bit sequence 01111110,
<data> is the frame payload (not restricted to just exactly byte sized data—the data may for example be 25 bits long).
<crc> is the 16 bit cyclic redundant check (CRC) character of the <data> section.
Should the bit sequence 01111110 appear in the data stream, it would be incorrectly interpreted as a flag sequence. To overcome this, every time the sequence 11111 appears in the data, an extra ‘0’ is inserted (‘stuffed’) into the data stream, i.e., it is replaced with 111110. On reception the converse occurs—the sequence 111110 is replaced with 11111 (‘de-stuffed’) after the flag detection logic. Consequently, the 8 bit sequence 01111110 in the data would be transmitted as a 9 bit sequence 011111010.
This bit stuffing has significant impact on the rate which data can be transmitted. Take for example two different data frames of 256 bytes. One contains all zeros, and the other contains all 1's. The frame containing all zeroes will have no bit stuffing applied (as the sequence 11111 will not occur, except maybe in the CRC), and the entire frame will be (256 * 8)+32=2080 bits. The frame containing all 1's will have an extra 0 inserted every 5 data bits, and the entire frame will therefore be (256 * 8)+((256 * 8)/5)+32=2489 bits. Given the line bit rate is fixed, the all 1's frame will take almost 20% longer to transmit.
For in-line frame relay equipment, the data is received on one port and transmitted on another. In such equipment, when the frames are simply transferred from the receiver to the transmitter (i.e., in plaintext bypass conditions), this variability in the effective transmission rate has no major impact. In other words, for a given item of data, the level of bit stuffing on the receiver and transmitter will match. However, when the data is modified, the level of bit stuffing for the receiver and transmitter may be different. For example, when data is encrypted, the encrypted data is essentially random (The data bits 0/1 distribution is statistically identical to the head/tail results from tossing a coin many times). This has the effect that with the above-mentioned, illustrative 256 byte frame, when encrypted, has generally between 30 & 40 stuffing bits inserted (i.e., 2110 to 2120 bits in the total frame size), regardless of the number of stuffing bits that were present in the unencrypted data.
Although frame relay (and most other systems using HDLC framing) do not support payloads that are not exact bytes in size, the HDLC standard is designed to cope with this possibility. Therefore, the flag bit-stuffing mechanism operates on every bit in the data stream, not just at the byte boundaries.
Commercially available products, such as the product identified by the trademark “DC2K-FR” and manufactured by Racal-Airtech Limited, a U.K. company, “destuff” each frame (i.e., removes the zero bits added by the stuffing process), transform it (e.g., by encryption—when required) and re-stuff it before transmitting. Since the data being re-stuffed has been transformed, it may have very different statistical characteristics to the original frame, and a different number of bits may be added by the restuffing process than were removed during the destuffing process, causing the unit's input and output data rates to be different.
In these commercially available products, an “equalizing” First-in First-out device (FIFO) is used to minimise the loss and corruption of frames due to this effect. In the equalizing FIFO, the next byte to be retrieved is the byte that has been in the queue for the longest time. The equalizing FIFO used is fairly large, having to cope with potentially very different input and output data rates. Encrypted data is essentially random, whereas the input data that is destuffed can be highly formatted (Word documents, for example, have a large number of 1's in their binary image, requiring a relatively large amount of de-stuffing).
With respect to the above referenced DC2K-FR encryption unit, the equalizing FIFO is used in the following manner. The length of the FIFO used is 512 bytes, and a “watermark” typically, for example, is set at 90 bytes to allow for an underrun (where data transmitted has less stuffing than that received) of up to 90 bytes, or an overrun (where data received has less stuffing than that transmitted) of up to 512−90=422 bytes. The frames coming into the encryption unit are not passed out of the encryption unit until either at least 90 bytes of the frame have been received by the equalizing FIFO, or the entire frame has been received, causing a (non-cumulative) latency in data output. Other features of this design (the encryption algorithm for example) also cause some degree of latency, giving rise to a total latency of approximately 15 plus minimum (90 bytes or length of frame in bytes).
As implemented in this prior art design, the watermark is calculated to avoid an underrun for a given maximum size data frame. For example, to allow a 1500 byte frame, the watermark would need to be set to at least 275 bytes. More specifically, this watermark value can be calculated as follows. The worst case situation is for this 1500 byte frame, as received by the FIFO, to have all ones, which will lead to the frame being bit stuffed at the rate one stuffing bit per 5 data bits (20%), giving a total frame length of 1800 bytes (=1500 * 1.2) on the receive side of the FIFO. On encrypted data, the stuffing rate is around 1 bit per 60 data bits (1.7%), giving a total frame length of 1525 bytes (=1500 * 1.017) on the transmit side. The watermark in the FIFO must be set so that the frame will have finished being received before it has finished being retransmitted; hence, the watermark must be at least 275 (1800-1525) bytes. This approach has a number of problems, as described below:
1. The system ends up with an artificially large latency on all but small frames.
2. The amount of FIFO space available to handle overrun conditions is reduced.
3. There is no mechanism to handle larger highly stuffed frames.
SUMMARY OF THE INVENTION
The invention is directed toward a method of buffering received frames of data bits comprising the steps of inputting the data bits into a first-in first-out buffer at a first data rate; outputting the data bits from the buffer at a second data rate when a complete frame of the data bits has been received by the buffer or the amount of the data bits received by the buffer reaches a watermark, detecting when the buffer has an underrun condition or an overrun condition, wherein the improvement is characterised by the following steps of increasing the watermark by a first predetermined amount when the underrun condition is detected; and decreasing the watermark by a second predetermined amount when the overrun condition is detected.
The invention is also directed to a frame processing device for processing received frames of data bits comprising means for receiving the data bits with a first data rate; data manipulation means being operable for changing the amount of the data bits; means for transmitting the data bits with a second data rate; first-in first-out (FIFO) buffer means for c

Affiliated with

Also associated with

Rating

Equalizing FIFO buffer with adaptive watermark does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Equalizing FIFO buffer with adaptive watermark, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equalizing FIFO buffer with adaptive watermark will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3141693