Section 4.6. Link-Level Flow Control

4.6. Link-Level Flow Control

Communication systems must use flow-control techniques on their transmission links to guarantee that a transmitter does not overwhelm a receiver with data. Several protocols guarantee the control of link flows. Two widely used flow-control protocols are stop and wait and sliding window .

4.6.1. Stop-and-Wait Flow Control

The stop-and-wait protocol is the simplest and the least expensive technique for link-overflow control. The idea behind this protocol is that the transmitter waits for an acknowledgement after transmitting one frame (see Figure 4.10). The essence of this protocol is that if the acknowledgment is not received by the transmitter after a certain agreed period of time, the transmitter retransmits the original frame.

Figure 4.10. A simple timing chart of a stop-and-wait flow control of data links

In this figure, we assume two consecutive frames i and i + 1. Frame i is ready to enter the link and is transmitted at t = 0. Let t _f be the time required to enter all the bits of a frame and t _p the propagation time of the frame between the transmitter (T) and the receiver (R). It takes as long as t = t _f + t _p to transmit a frame. At the arrival of a frame i , the receiver processes the frame for as long as t _r and generates an acknowledgment. For the same reason, the acknowledgment packet takes t = t _a + t _p to be received by the transmitter if t _a is assumed to be the time required to enter all the bits of an acknowledgment frame, and it takes t _r for processing it at the receiver. Therefore, the total time to transmit a frame, including acknowledgment processes,

Equation 4.11

Note here that with this technique, the receiver can stop or slow down the flow of data by withholding or delaying acknowledgment. Practically, t _r and t _a are negligible compared to other components of the equation. Thus, this equation can be approximated as

Equation 4.12

In this equation, t _f = /r , where is the length of frame in bits; r is the data rate; and t _p = d/… , where d is the length of transmission line, and … is speed of transmission. For wireless and wired transmissions, … = 3 x 10 ⁸ m/s where except for fiber- optic links, … 2.2 x 10 ⁸ m/s, owing to the fact that light travels zigzag over links, and thus overall speed is lower. Therefore, the link efficiency is defined as

Equation 4.13

4.6.2. Sliding-Window Flow Control

The shortcoming of the stop-and-wait protocol is that only one frame at a time is allowed for transmission. This flow control can be significantly improved by letting multiple frames travel on a transmission link. However, allowing a sequence of frames to be in transit at the same time requires a more sophisticated protocol for the control of data overflow on links. The well-known sliding-window protocol is one technique that efficiently controls the flow of frames.

Figure 4.11 shows an example of sliding-window flow control. With this protocol, a transmitter (T) and a receiver (R) agree to form identical-size sequences of frames. Let the size of a sequence be ‰ . Thus, a transmitter allocates buffer space for ‰ frames, and the receiver can accept up to ‰ frames. In this figure, ‰ = 5. The transmitter can then send up to ‰ = 5 frames without waiting for any acknowledgment frames. Each frame in a sequence is labeled by a unique sequence number. For every k frames forming a sequence, the transmitter attaches a sequence-number field to each frame. Therefore, as many as 2 ^k sequence numbers exist.

Figure 4.11. Timing chart of a sliding-window flow control for two sequences of frames

First, a transmitter opens a window of size ‰ = 5, as the figure shows. The receiver also opens a window of size ‰ to indicate how many frames it can expect. In the first attempt, let's say that frames 1, 2, and 3 as part of sequence i are transmitted. The transmitter then shrinks its window to ‰ = 2 but keeps the copy of these frames in its buffer just in case any of the frames is not received by the receiver. At the receipt of these three frames, the receiver shrinks its expected window to ‰ = 2 and acknowledges the receipt of frames by sending an acknowledgment ACK1,2,3 frame to the transmitter.

At the release of ACK1,2,3, the receiver changes its expected window size back to ‰ = 5. This acknowledgment also carries information about the sequence number of the next frame expected and informs that the receiver is prepared to receive the next ‰ frames. At the receipt of ACK1,2,3, the transmitter maximizes its window back to ‰ = 5, discards the copies of frames 1, 2, and 3, and continues the procedure. In this protocol, the window is imagined to be sliding on coming frames. Similarly, we can derive an expression for this protocol as we did for the stop-and-wait protocol. For the transmission of a frame as the integral portion of ‰ frames sequence, the total time, including all the acknowledgment processes, is obtained using Equation (4.11), with averaging over ‰ and inclusion of ‰t _f as

Equation 4.14

Practically, t _r and t _a are negligible; thus, this equation can be approximated by

Equation 4.15

Therefore, link efficiency is expressed as

Equation 4.16

Link efficiency provides a network designer with a good understanding of the link utilization for network management purposes.