Flow Control

In computer networks, flow control is defined as-

A set of procedures which are used for restricting the amount of data that a sender can send to the receiver.

The flow control protocols which are classified as-

Stop and Wait Protocol

 It is the simplest flow control protocol.

 Sender sends one data packet and then waits for its acknowledgement.

 Sender sends the next packet only after it receives the acknowledgement for the previous packet.
 It works under the following assumptions-
o Communication channel is perfect.
o No error occurs during transmission.

How it Works?

The working of a stop and wait protocol may be explained as-

 Sender sends only one data packet to the receiver.

 Sender stops and waits for the acknowledgement for the sent packet from the receiver.
 Receiver receives and processes the data packet.
 Receiver sends an acknowledgement to the sender.
 After receiving the acknowledgement, sender sends the next data packet to the receiver.

These steps are illustrated below-

Analysis-

Now, let us analyze in depth how the transmission is actually carried out-

 Sender puts the data packet on the transmission link.

 Data packet propagates towards the receiver’s end.
 Data packet reaches the receiver and waits in its buffer.
 Receiver processes the data packet.
 Receiver puts the acknowledgement on the transmission link.
 Acknowledgement propagates towards the sender’s end.
 Acknowledgement reaches the sender and waits in its buffer.
 Sender processes the acknowledgement.

These steps are illustrated below-

Total Time-

Total time taken in sending one data packet

= (Transmission delay + Propagation delay + Queuing delay + Processing delay) packet + (Transmission delay + Propagation delay + Queuing delay
+ Processing delay)ACK

Assume-

 Queuing delay and processing delay to be zero at both sender and receiver side.
 Transmission time for the acknowledgement to be zero since it’s size is very small.

Under the above assumptions,

Total time taken in sending one data packet = (Transmission delay + Propagation delay)packet + (Propagation delay)ACK

We know,

 Propagation delay depends on the distance and speed.

 So, it would be same for both data packet and acknowledgement.

So, we have-

Total time taken in sending one data packet = (Transmission delay)packet + 2 x Propagation delay
Efficiency-

Efficiency of any flow control protocol is given by-

Efficiency (η) = Useful Time / Total Time

where-

 Useful time = Transmission delay of data packet = (Transmission delay)packet

 Useless time = Time for which sender is forced to wait and do nothing = 2 x Propagation delay
 Total time = Useful time + Useless time

Thus,
Factors Affecting Efficiency-

We know,

Efficiency (η) = (Transmission delay)packet / { (Transmission delay)packet + 2 x Propagation delay }

Dividing numerator and denominator by (Transmission delay)packet, we get-

From here, we can observe-

 Efficiency (η) ∝ 1 / Distance between sender and receiver

 Efficiency (η) ∝ 1 / Bandwidth
 Efficiency (η) ∝ Transmission speed
 Efficiency (η) ∝ Length of data packet
Throughput-

 Number of bits that can be sent through the channel per second is called as its throughput.

Round Trip Time-

Round Trip Time = 2 x Propagation delay

Advantages-

The advantages of stop and wait protocol are-

 It is very simple to implement.

 The incoming packet from receiver is always an acknowledgement.

Limitations-

The limitations of stop and wait protocol are-

Point-01:

It is extremely inefficient because-

 It makes the transmission process extremely slow.

 It does not use the bandwidth entirely as each single packet and acknowledgement uses the entire time to traverse the link.
Point-02:

If the data packet sent by the sender gets lost, then-

 Sender will keep waiting for the acknowledgement for infinite time.
 Receiver will keep waiting for the data packet for infinite time.

Point-03:

If acknowledgement sent by the receiver gets lost, then-

 Sender will keep waiting for the acknowledgement for infinite time.
 Receiver will keep waiting for another data packet for infinite time.

Important Notes-

Note-01:

Efficiency may also be referred by the following names-

 Line Utilization /Link Utilization/Sender Utilization/Utilization of Sender

Note-02:

Throughput may also be referred by the following names-

 Bandwidth Utilization /Effective Bandwidth /Maximum data rate possible /Maximum achievable throughput

Note-03:
Stop and Wait protocol performs better for LANs than WANs.

This is because-

 Efficiency of the protocol is inversely proportional to the distance between sender and receiver.
 So, the protocol performs better where the distance between sender and receiver is less.
 The distance is less in LANs as compared to WANs.

The main problem faced by the Stop and Wait protocol is the occurrence of deadlock due to-

 Loss of data packet

 Loss of acknowledgement

Stop and Wait ARQ-

Stop and Wait ARQ assumes-

 The communication channel is noisy.

 Errors may get introduced in the data during the transmission.

How it works?

 Stop and wait ARQ works similar to stop and wait protocol.
 It provides a solution to all the limitations of stop and wait protocol.
 Stop and wait ARQ includes the following three extra elements.
Thus, we can say-

Stop and Wait ARQ

= Stop and Wait Protocol + Time Out Timer + Sequence Numbers for Data Packets and Acknowledgements

Number of Sequence Numbers Required-

NOTE:

For any sliding window protocol to work without any problem, the following condition must be satisfied-

Available Sequence Numbers >= Sender Window Size + Receiver Window Size

Stop and wait ARQ is a one bit sliding window protocol where-

 Sender window size = 1

 Receiver window size = 1
Thus, in stop and wait ARQ,

Minimum number of sequence numbers required

= Sender Window Size + Receiver Window Size

=1+1

=2

Thus,

 Minimum number of sequence numbers required in Stop and Wait ARQ = 2.

 The two sequence numbers used are 0 and 1.

How Stop and Wait ARQ Solves All Problems?

1. Problem of Lost Data Packet-

 Time out timer helps to solve the problem of lost data packet.
 After sending a data packet to the receiver, sender starts the time out timer.
 If the data packet gets acknowledged before the timer expires, sender stops the time out timer.
 If the timer goes off before receiving the acknowledgement, sender retransmits the same data packet.
 After retransmission, sender resets the timer.
 This prevents the occurrence of deadlock.
2. Problem of Lost Acknowledgement-

 Sequence number on data packets help to solve the problem of delayed acknowledgement.
 Consider the acknowledgement sent by the receiver gets lost.
 Then, sender retransmits the same data packet after its timer goes off.
 This prevents the occurrence of deadlock.
 The sequence number on the data packet helps the receiver to identify the duplicate data packet.
 Receiver discards the duplicate packet and re-sends the same acknowledgement.
Role of Sequence Number on Data Packets

Consider the above example-

Step-01:

 Sender sends a data packet with sequence number-0 to the receiver.

Step-02:

 Receiver receives the data packet correctly.

 Receiver now expects data packet with sequence number-1.
 Receiver sends the acknowledgement ACK-1.

Step-03:

 Acknowledgement ACK-1 sent by the receiver gets lost on the way.

Step-04:

 Sender receives no acknowledgement and time out occurs.

 Sender retransmits the same data packet with sequence number-0.
 This will be a duplicate packet for the receiver.

Step-05:

 Receiver receives the data packet and discovers it is the duplicate packet.
 It expects the data packet with sequence number-1 but receiving the data packet with sequence number-0.
 It discards the duplicate data packet and re-sends acknowledgement ACK-1.
 ACK-1 requests the sender to send a data packet with sequence number-1.
 This avoids the inconsistency of data.

Conclusion-

 Had the sequence numbers not been allotted to the data packets, receiver would have accepted the duplicate data packet thinking of it
as the new data packet.
 This is how sequence numbers allotted to the data packets prove to be useful for identifying the duplicate data packets and discarding
them.
3. Problem of Delayed Acknowledgement-

 Sequence number on acknowledgements help to solve the problem of delayed acknowledgement.

Role of Sequence Number on Acknowledgements

Consider the above example-

Step-01:

 Sender sends a data packet with sequence number-0 to the receiver.

Step-02:

 Receiver receives the data packet correctly.

 Receiver now expects data packet with sequence number-1.
 Receiver sends the acknowledgement ACK-1.

Step-03:

 Acknowledgement ACK-1 sent by the receiver gets delayed in reaching the sender.

Step-04:

 Sender receives no acknowledgement and time out occurs.

 Sender retransmits the same data packet with sequence number-0.
 This will be a duplicate packet for the receiver.

Step-05:

 Receiver receives the data packet and discovers it is the duplicate packet.
 It expects the data packet with sequence number-1 but receiving the data packet with sequence number-0.
 It discards the duplicate data packet and re-sends acknowledgement ACK-1.
 ACK-1 requests the sender to send a data packet with sequence number-1.

Step-06:

 Two acknowledgements ACK1 reaches the sender.

 When first acknowledgement ACK1 reaches the sender, sender sends the next data packet with sequence number 1.
 When second acknowledgement ACK1 reaches the sender, sender rejects the duplicate acknowledgement.
 This is because it has already sent the data packet with sequence number-1 and now sender expects the acknowledgement with
sequence number 0 from the receiver.

Conclusion-

 Had the sequence numbers not been allotted to the acknowledgements, sender would have accepted the duplicate acknowledgement
thinking of it as the new acknowledgement for the latest data packet sent by it.
 This is how sequence numbers allotted to the acknowledgements prove to be useful for identifying duplicate acknowledgements and
discarding them.

4. Problem of Damaged Packet-

 If receiver receives a corrupted data packet from the sender, it sends a negative acknowledgement (NAK) to the sender.
 NAK requests the sender to send the data packet again.
Stop and Wait Protocol Vs Stop and Wait ARQ-

The following comparison table states the differences between the two protocols-

Stop and Wait Protocol Stop and Wait ARQ

It assumes that the communication channel is perfect and noise

It assumes that the communication channel is imperfect and noisy.
free.

Data packet sent by the sender can never get corrupt. Data packet sent by the sender may get corrupt.

A negative acknowledgement is sent by the receiver if the data

There is no concept of negative acknowledgements.
packet is found to be corrupt.

There is no concept of time out timer. Sender starts the time out timer after sending the data packet.
Data packets and acknowledgements are numbered using
There is no concept of sequence numbers.
sequence numbers.

Limitation of Stop and Wait ARQ-

The major limitation of Stop and Wait ARQ is its very less efficiency.