flow control
What is flow control?
Flow control is a technique used to regulate data transfer between computers or other nodes in a network. Flow control ensures that the transmitting device does not send more data to the receiving device than it can handle. If a device receives more data than it can process or store in memory at any given time, the data is lost and needs to be retransmitted.
The purpose of flow control is to throttle the amount of data transmitted to avoid overwhelming the receiver's resources. This is accomplished through a series of messages that the receiver transmits to the sender to acknowledge if frames have been received. The sender uses these messages to determine when to transmit more data. If the sender does not receive an acknowledgement (ACK), it concludes that there has been a problem with the transmission and retransmits the data.
Flow control is implemented in different ways, depending on how the sender and receiver handle messages and track data frames. There are two basic approaches to flow control: stop and wait and sliding window. The stop-and-wait approach is the simplest to implement, but it is not as efficient as sliding window, which delivers better network performance and utilizes network resources more effectively.
Stop-and-wait flow control
In the stop-and-wait approach, the sender segments the data into frames and then transmits one frame at a time to the receiver, which responds to each frame with an ACK message. This process occurs through the following steps:
- The sender transmits a data frame to the receiver.
- The sender waits for the receiver to respond.
- Upon receiving the frame, the receiver transmits an ACK to the sender.
- Upon receiving the ACK, the sender sends the next frame to the receiver and waits for the next ACK. If the sender does not receive an ACK within a defined time limit, known as a timeout, the sender retransmits the same frame.
- The process continues until the sender has finished transmitting all the data to the receiver.
Figure 1 illustrates how this exchange works. In this case, the sender starts by transmitting Frame 0 and then waiting for the ACK. When Frame 0 reaches its destination, the receiver sends ACK 0 to the sender.
After receiving ACK 0, the sender transmits Frame 1 and waits for ACK 1. When that arrives, the sender transmits Frame 2 and waits again. This time, however, the sender does not receive ACK 2 before the timeout occurs, so it retransmits Frame 2. The frame now arrives at its destination, so the receiver sends ACK 2. When the sender receives ACK 2, it transmits Frame 3, which is also acknowledged by the receiver.
Stop and wait belongs to a category of error control mechanisms called automatic repeat requests (ARQs), which rely on the use of ACKs to determine if a data transmission was successful or if retransmission is needed. Other ARQs include Go-Back-N ARQ and Selective Repeat ARQ, both of which use the sliding window protocol.
Stop and wait is simpler to implement than sliding window. It is also fairly reliable because the sender receives an ACK for each frame successfully transmitted to the receiver. These qualities, however, also make data communications much slower, which can be exacerbated by long distances and heavy traffic. The stop-and-wait approach also tends to underutilize network resources.
Sliding window flow control
The sliding window approach addresses many of the issues that come with stop and wait because the sender can transmit multiple frames at once without having to wait for an ACK for each frame. However, this approach also comes with additional complexity.
When first connecting, the sender and receiver establish a window that determines the maximum number of frames the sender can transmit at a time. During the transmission, the sender and receiver must carefully track which frames have been sent and received to ensure that all the data reaches its destination and is reassembled in the correct order.
Sliding window flow control can be implemented using one of two approaches: Go-Back-N and Selective Repeat. With the Go-Back-N approach, the sender can send one or more frames but never more frames than the window allows. As the receiver acknowledges the frames, the sender moves to the next batch, or window, of frames that can now be sent. If there is a problem with a transmitted frame, the sender retransmits all the frames in the current window.
Figure 2 shows an example of how Go-Back-N works. In this case, the window consists of only three frames -- initially, Frames 0 through 2. The sender begins by transmitting Frame 0 to the receiver. Upon receiving Frame 0, the receiver sends an ACK that specifies the next frame to send (Frame 1), rather than specifying the frame that has just been received.
When the sender receives ACK 1, it moves the window over by one position, dropping Frame 0 and adding Frame 3. The sender then transmits Frames 1, 2 and 3, which represent the window's entire contents. The sender does not necessarily need to send Frame 0 first, followed by Frames 1 through 3. This is illustrated in Figure 2 to demonstrate how the process works.
Upon receiving the three frames, the receiver sends a cumulative ACK that specifies the next frame to send, which is Frame 4. The ACK indicates that the receiver now has all the preceding frames (0 through 3).
When the sender receives ACK 4, it adjusts the window so that it now includes Frames 4 through 6 and then transmits those frames. This time, however, Frame 4 gets lost in the transmission, while Frames 5 and 6 reach their destination. Upon receiving Frame 5, the receiver detects that Frame 4 is missing and sends a negative acknowledgement (NAK) that specifies Frame 4. At the same time, the receiver discards Frames 5 and 6.
When the sender receives the NAK, it retransmits Frames 4 through 6 and waits for the ACK. The frames arrive with no errors the second time around, so the receiver returns an ACK indicating that the sender can now transmit Frame 7. The sender adjusts the window accordingly and transmits the next set of frames, starting with Frame 7.
The Selective Repeat approach is similar to Go-Back-N. The primary difference is that Selective Repeat does not retransmit the entire window if there is an error, only the individual frame in dispute. Selective Repeat does not support cumulative ACK messages like Go-Back-N, so each ACK is specific to the frame that was just received, which is what enables the sender to identify the precise frame that needs to be retransmitted.
Figure 3 illustrates an example of the Selective Repeat process. After transmitting Frame 0, the sender receives an ACK, so it transmits Frames 1 through 3 and receives an ACK for each one. The sender then transmits Frames 4 through 6. When Frames 5 and 6 arrive at the receiver, but not Frame 4, the receiver sends ACK 5 and ACK 6, along with NAK 4. The sender responds to the NAK by retransmitting Frame 4. Upon receiving Frame 4, the receiver sends an ACK. The sender then adjusts the window and transmits the next three frames, starting with Frame 7.
Both Selective Repeat and Go-Back-N are more efficient than the stop-and-wait approach, but there are important differences between the two sliding window approaches. The Go-Back-N approach can consume more bandwidth because all the frames in a window are retransmitted if an error occurs. However, it is not as complex to implement as Selective Repeat and does not require the same amount of system resources. Selective Repeat comes with greater management overhead because the frames must be tracked and sorted throughout the data transmission.
Learn about 12 common network protocols and their functions.