Flow control is a technique for assuring that a transmitting station does not overwhelm a receiving station with data. The receiver will typically allocate a data buffer with some maximum length. When data are received, it must do a certain amount of processing before it can clear the buffer and be prepared to receive more data. In the absence of flow control, the receiver’s buffer may overflow while it is processing old data.
While discussing the flow control techniques, we will assume that all frames that are transmitted are received successfully.
The simplest form of flow control, known as stop-and-wait flow control, works as follows. A source entity transmits a frame. After reception, the destination entity indicates its willingness to accept another frame by sending back an acknowledgement to the frame just received. The source must wait until it receives the acknowledgement before sending the next frame. The destination can thus stop the flow of data by simply withholding acknowledgement.
This protocol can be implemented on a half-duplex line and both the stations can have only one buffer.
To send n packets, approximate time required is
T0 = n(2tprop + tframe)
tprop = propagation time from the sender to the receiver or from the receiver to the sender
tframe = transmission time of a frame.
The utilization or efficiency can be expressed as
U = n x tframe / n(2tprop + tframe)
U = 1/(1+2a), where a=tprop/tframe
For a LAN, typical value of a = 0.01, which gives U in the range 0.83 to 0.98. But for satellite communication, where the value of ‘a’ is relatively very high, the utilization will be very poor and this scheme is not suitable.
For such cases, a more elaborate procedure is necessary to improve the utilization. Sliding-window protocol is one such universally accepted protocol.
The key idea behind sliding-window protocol is to allow transmission of a maximum number of frames before receiving an acknowledgement from the receiver. Assume that we have two stations A and B, connected via a full-duplex link. Station B allocates buffer space for n frames instead of 1 in previous protocol. Thus B can accept n frames, and A is allowed to send n frames without waiting for an acknowledgement. To keep track of which frames have been acknowledged, each is labeled with a sequence number. B acknowledges a frame by sending an acknowledgement that includes the sequence number of the next frame expected. This acknowledgement also implicitly announces that B is prepared to receive the next n frames beginning with number specified. This scheme can also be used to acknowledge multiple frames. For example, B could receive frames 2, 3 & 4, but withhold acknowledgement until frame 4 has arrived. by then returning an acknowledgement with sequence number 5, B acknowledges frames 2, 3 & 4 at one time. A maintains a list of sequence numbers that it is allowed to send and B maintains a list of sequence numbers that it is prepared to receive. Each of these lists can be thought of as a window of frames. The operation is referred to as sliding-window flow control.
An important restriction needs to be noted. Since the sequence number to be used, occupies a field in the frame, it is clearly of bounded size. For a k-bit field, the sequence number can range from 0 to 2k-1. Accordingly frames are numbered modulo 2k, i.e., after sequence number 2k-1 the next number is zero. The figure below depicts the sliding-window process.
In the above figure, we have assumed the use of a 3-bit sequence number so that frames are numbered sequentially from 0 thru’ 7, and then the same numbers are reused for subsequent frames. The shaded rectangle represents the window of frames that may be transmitted. The figure indicates that the sender may transmit 7 frames beginning with frame 6. Each time a frame is sent, the shaded portion will shrink. Each time a new acknowledgement is received, the shaded portion will grow.
An example is shown in figure below. The example assumes a 3-bit sequence number field and a maximum window size of 7.
Initially, A and B have windows indicating that A may transmit 7 frames, beginning with frame 0 (F0). After transmitting 3 frames (F0, F1, F2) without acknowledgement, A has shrunk its window to 4 frames. The window indicates that A may transmit 4 frames beginning with frame number 3. B then transmits an ACK3, which means B has received all frames up through frame #2, and is ready to receive frame #3. In fact, B is prepared to receive 7 frames beginning with frame #3. With this acknowledgement A is back up to permission to transmit 7 frames, still beginning with frame 3. A proceeds to transmit frames 3, 4, 5 & 6. B returns an ACk4, which acknowledges frame 3 and allows the transmission of frames 4 thru’ 2. But by the time that this acknowledgement reaches A, it has already transmitted frames 4, 5 & 6. The result is that A may only open its window to permit the transmission of 4 frames beginning with frame 7.
The mechanism so far described, does indeed provide a form of flow control. The receiver must only be able to accommodate n frames beyond the one it has last acknowledged. to supplement this, most protocols also allow a station to complete the flow of frames from the other side by sending a Receive-Not-Ready (RNR) message, which acknowledges former frames but forbids transfer of future frames. Thus RNR 5 means B has received all frames through number 4, but is unable to accept any more. At some subsequent point, the station must send a normal acknowledgement to re-open the window.
It can be shown that the utilization U is 1 when the window size n > 2a+1, and U = n/(2a+1), when n < 2a+1.
A window size from 3 to 7 have been found adequate for most situations.
In situations where both the stations are sending frames, acknowledgement can be sent along with data, without using separate frames for acknowledgements. this technique is known as piggy-backing which helps in reducing congestion.
Introduction to Communications
Data Transmission Modes, Types of Data Transmission & Data Transmission Techniques
How to move your Email accounts from one hosting provider to another without losing any mails?
How to resolve the issue of receiving same email message multiple times when using Outlook?
Self Referential Data Structure in C - create a singly linked list
Mosquito Demystified - interesting facts about mosquitoes
Elements of the C Language - Identifiers, Keywords, Data types and Data objects
Moving Email accounts from one cPanel server to another
How to pass Structure as a parameter to a function in C?
Rajeev Kumar is the primary author of How2Lab. He is a B.Tech. from IIT Kanpur with several years of experience in IT education and Software development. He has taught a wide spectrum of people including fresh young talents, students of premier engineering colleges & management institutes, and IT professionals.
Rajeev has founded Computer Solutions & Web Services Worldwide. He has hands-on experience of building variety of websites and business applications, that include - SaaS based erp & e-commerce systems, and cloud deployed operations management software for health-care, manufacturing and other industries.