Hybrid flow control

Details Hybrid flow control Hybrid flow control

1998-12-07

2001-06-19

Teska, Kevin J. (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Emulation

Of peripheral device

C703S020000, C709S233000, C709S234000, C710S033000, C712S201000, C370S414000, C340S870030

Reexamination Certificate

active

06249756

ABSTRACT:

BACKGROUND OF THE INVENTION
Data transfer systems such as networks and I/O busses always have latency due to the finite time of signal propagation over physical media. Accordingly, receive buffers must include capacity to handle data that is in transit when a full or BUSY signal is generated indicating that the receive buffer is full. As the distance between transmitting nodes and the receive buffer increases the required latency capacity of the buffer must also increase. Prior art flow control systems generally use either a high/low watermark system or a credit based system.
A typical high/low watermark flow control system is depicted in
FIGS. 1 and 2
.
FIG. 1
depicts a receive FIFO and
FIG. 2
is simplified state graph of the operation of the FIFO. If the receive FIFO transmits a busy signal at time t0 and the transit time to the transmitting module is t1 then the transmitting module will continue transmitting until t3=t0+t1. Thus, the “Round trip depth” is all the data that was in transit at t0 plus the data that was transmitted between t0 and t3. Additional data will also be transmitted due to logic delays in generating and responding to the BUSY signal.
The prior art flow control protocol uses FIFO high and low watermarks to control the state of a receive link. If the FIFO is above the high watermark the link is busy, and BUSY command symbols are transmitted. If the FIFO is below the low watermark the link is ready, and READY command symbols are transmitted.
At system start-up the receive FIFO is empty and below the low watermark. In this flow control state (FCS), the receiver is ready and the READY command signals are transmitted regularly as required. When receive data arrive, they are pushed into the FIFO, and their availability is reported to the output side. When output is unblocked, the receive data is pulled from the FIFO as soon as available. If the output path is blocked or running at a lower transfer rate, data will accumulate in the FIFO.
When the accumulated data reaches the high watermark, the state of the link changes from inbound READY to inbound BUSY. This state change causes the keep alive protocol to send a BUSY signal to stop the flow of data. If there is insufficient space above the high watermark (less than a round trip delay) or the BUSY command is corrupted, receive data may overflow the FIFO. This flow control relies on the buffer space above the high watermark to prevent FIFO overflow by compensating for the delayed response to the BUSY. When sufficient data has been pulled from the FIFO to bring it below the low watermark, the state will return to inbound ready causing the keep alive protocol to send a READY command symbol to restart the flow of data. The storage below the low watermark is used to prevent data underflow.
The FIFO can be sized to support a desired link length by computing the round trip propagation delay of the link. The four link delay components are:
1. Local Node logic Delay (LND) (300 to 450 ns)
2. Outbound physical media delay (PMD) (5 ns/meter)
3. Remote Node logic Delay (RND) (300 to 450 ns)
4. Inbound physical media delay (PMD) (5 ns/meter)
On short links (less than 30 to 50 meters) the propagation delay is dominated by logic delay in the local and remote nodes. The longer links are dominated by delay in the physical media. To provide full link performance the FIFO must be sized
20
to have a full link round trip delay of characters above the high water-mark and the same amount below the low watermark. The table of
FIG. 3
lists a few link lengths and the required FIFO depth. The prior art flow control protocol requires equal amounts of storage above and below the watermarks. For long links, the storage required exceeds the on-chip storage available in current ASIC technology.
Prior credit based flow control protocols issue fixed credits to sending nodes. However, these systems have major start-up and lost-credit problems. At start-up the receive FIFO remains empty until a transmitting node receives a credit and sets up its credit management protocol. If a credit is lost, the transmitting node will wait for a credit and the receiving node will wait for a transmission. The complexity of initialization and error recovery to recover lost credits are major drawbacks of a credit based system.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, a hybrid flow control system utilizes aspects of the high/low watermark and credit based systems to reduce FIFO size in systems with high latency due to increased link transfer latency. Additionally, control overhead is minimized.
According to a further aspect of the invention, a receive FIFO has in input into which received bytes are pushed and an output from which bytes are pulled. First and second numbers are designated as a low watermark and a high watermark, with the high watermark being greater than the low watermark. When the number of bytes stored in the FIFO is less than the low watermark the FIFO indicates it is READY to receive bytes. When the number of bytes stored exceeds the high watermark the FIFO asserts a BUSY signal to stop the transmission of bytes. The difference between the high watermark and total capacity of the FIFO is sufficient to accommodate data already in transmission over the physical links between the senders and the receive FIFO.
Subsequent to the assertion of the BUSY signal, the number of bytes pulled from the FIFO are counted. When the number counted exceeds a selected number, N, a credit of N bytes is transmitted to the sender. Thus, even though the number of bytes stored may be greater than the low watermark, the transmission of another N bytes is authorized.
It is important to maintain the flow of data to prevent under-running the FIFO. By issuing credits even when the byte count is greater than the low watermark, the byte count in the receive FIFO is kept higher than the high watermark. Thus, if there is an interruption in the receipt of bytes the FIFO will be able to continue to supply the receiving node with data for a longer length of time than would be possible with a prior art high/low watermark system.
According to a still further aspect of the invention, a hybrid flow control protocol provides for a variable credit. Subsequent to the assertion of the BUSY signal, a counter is incremented for every byte pulled and decrement for every byte pushed into the receive FIFO. When the count is greater than a predetermined number the READY signal is asserted until the count is equal to zero. Thus, the number of bytes that can be received is variable, depending on the difference between the rate at which bytes are being received and the rate at which bytes are being pulled.
According to a further aspect of the invention, if the rate of pulling bytes is at least equal to the rate of receiving bytes, subsequent to the assertion of BUSY the READY signal is asserted as long as bytes are being pulled from the receive FIFO.
Other features and advantages of the invention will be apparent in view of the following detailed description and appended claims.


REFERENCES:
patent: 5208810 (1993-05-01), Park
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5557751 (1996-09-01), Banman et al.
patent: 5574849 (1996-11-01), Sonnier et al.
patent: 5675579 (1997-10-01), Watson et al.
patent: 5694121 (1997-12-01), Krause et al.
patent: 5710549 (1998-01-01), Horst et al.
patent: 5867501 (1999-02-01), Horst et al.

Affiliated with

Also associated with

Rating

Hybrid flow control does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hybrid flow control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid flow control will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2519896