Flow Control

What is Flow Control?

Sometimes the receiver's processor is slow and cannot process the data at the speed the sender is sending. If the queue(buffer) of the receiver is full then it starts discarding the signals. Flow control methods are used to assure that the sender sends the signal only if the receiver is in a condition to receive it.

Types of delays

Transmission Delay

It is the time taken to transfer a packet from the host to the outgoing link.

T_{t =}   L / B

L is the size of the packet.

B is the Bandwidth of the Bandwidth of the transmission medium.

For example, if bandwidth is 1 bps (every second 1 bit can be transmitted onto the transmission medium) and data size is 20 bits then what is the transmission delay? If in one second, 1 bit can be transmitted. To transmit 20 bits, 20 seconds would be required.

Note: Data is always is powers of 2 and Bandwidth is always in powers of 10. This is because Bandwidth is dependent on frequency and frequency is measured in decimal. Data is measured in bits.

Propagation Delay

It is the time taken by the signal to reach from one end of the link to the other end of the link.

T_{p =}   Distance / Velocity

Queuing Delay

When the packet is received at the destination it will not be processed immediately. All the packets will sit in a queue. This is called queuing delay. When the receiver has processing time, the packets will be taken one by one from the queue.

Processing Delay

It is the time taken to process the signal.

Both queuing delay and processing delay doesn’t have any formula because they depend upon the speed of the processor of the receiver.

Total Time

T_t + T_p + T_queue + T_processing

Flow Control Methods

Stop & Wait

It is the simplest flow control mechanism. The sender sends one packet and then stops and waits until the receiver confirms that it can send the next one.

Total time is

T_{t Data} + T_{p Data} + T_queue + T_processing + T_{t Acknowledgement} + T_{p Acknowledgement}

T_{t Data} Transmission time for data

T_{p Data} Propagation time for data

T_{t Acknowledgement} Transmission time for acknowledgement

T_{p Acknowledgement} Propagation time for acknowledgement

T_{p Data} is the same as T_{p Acknowledgement}

Total time is T_{t Data} + T_queue + T_processing + T_{t Acknowledgement} + 2T_p

Size of acknowledgement << Size of data

Hence, we can ignore T_{t Acknowledgement}

Total time is T_{t Data} + T_queue + T_processing + 2T_p

Queuing delay (T_queue) and processing delay (T_processing) are also negligible.

Total time is T_{t Data} + 2T_p

We stop and wait for "2T_p" Hence, this is inefficiency.

Throughput: Number of bits we are able to send per second. Sometimes throughput is also called effective bandwidth or bandwidth utilization.

Throughput = L / (T_{t Data} + 2T_p)

Disadvantages of stop and wait

• Efficiency is not very high and decreases with certain factors. It is good for LAN but not WAN.

• The problem arises when a data packet is lost. The sender will think that the receiver has received the data but is busy. The receiver keeps waiting for the sender to send the data. Hence both the sender and the receiver go into a deadlock. A solution to this is a time-out timer. Within this time if the receiver doesn't get an acknowledgement then it considers that data is lost and retransmits the data. This is called the stop-and-wait automatic repeat request.

• Acknowledgement can be lost or duplicate packet problems. If the acknowledgement is lost then after the time-out timer the sender retransmits the data packet and the receiver thinks that it is a different data packet. Hence, the receiver accepts the duplicate packet as a new data packet. To solve this we have a sequence number on the data which helps to identify data uniquely.

  Miminum swquence number required to avoid duplicate packet problem is

  W_S + W_R

  W_S = Sender window size

  W_R = Receiver window size

• To solve the delayed acknowledgement problem we number the acknowledgements. Acknowledgements have a number of the data byte expected next.

Sliding Window

Pipelining

T_{t Data} sec = 1 packet is sent

1 sec = 1 / T_{t Data} packet is sent

T_{t Data} + 2T_p   sec = (T_{t Data} + 2T_p ) / T_{t Data} packet is sent = 1 + 2a packets

Hence, we could have transmitted 1 + 2a packets in T_{t Data} + 2T_p   sec.

To increase efficiency, we have to increase the number of packets sent. Instead of sending 1 packet and waiting for the acknowledgement, we send a window of packets.

The window is the buffer used to hold the packets. The way the window is moving, it is actually sliding. Hence, it is called the sliding window protocol.

For maximum utilization, the sender window size should be (1 + 2a).

The sequence number is stored in the header field. A larger sequence number means space taken up by the header will also be high. Hence to decrease the header size, the sequence number should be as less as possible.

W_s = min ( 1+2a, 2^N)

W_s is the Sender window size

N is the number of bits in the sequence number field

2^N is the Number of sequence numbers possible with N bits

Sliding window protocol is a theoretical concept. It is practically implemented as:

• Go Back N (GBN)

• Selective Repeat (SR)

Go Back N

W_s is N and W_R is N

W_s means the Sender window size

W_R means the Receiver window size

If a time-out occurs at any point on the sender side, we go back to N and retransmit the entire window again. We go back to N from the point where the last packet was being transmitted and not from the lost one. Hence, it is called Go Back N.

GBN uses cumulative acknowledgement. The receiver side has an acknowledgement timer. For all the packets received during this time one acknowledgement is sent. The acknowledgement timer should not be too large otherwise on the other side there will be a timeout.

Time-out timer (sender side) > Acknowledgement timer (receiver side)

Selective Repeat (SR)

Here, only the erroneous or lost frames are retransmitted, while the good frames are received and buffered.

W_S > 1 and W_R = W_S

The Comparison

Access Control

When we have a broadcast channel, only one station should send the data. If more than one station is sending the data then there should be no collisions inside the channel.

Access Control Methods

Time Division Multiplexing

The timeline is divided into slots and each slot is allocated to each station in a Round Robin manner.

How much time to give to each station?

The last bit transmitted by it should get out of the link

Total time = T_t + T_p

Disadvantage: The station might not use the slot allocated to it completely as it might not have nay data to send.

Polling

• A poll is conducted in which all the stations willing to send data participate.

• The polling algorithm chooses one of the stations to send the data.

• The chosen station sends the data to the destination.

• After the chosen station has sent the data, the cycle repeats.

Total time is T_t + T_p+ T_poll

Advantage: No slots wasted

Disadvantage:

• Not a fair sharing

• Starvation may occur

• Extra polling time required

CSMA/CD

Carrier Sensing

• Any station that is willing to transmit the data senses the carrier.

• If it finds the carrier free, it starts transmitting its data packet otherwise not.

Multiple Access: Many stations are trying to access the channel (Broadcast channel)

Collision Detection: The sender should be able to detect if it's packet got involved in a collision and retransmit.

How can the sender detect if the collision signal coming back is because of it's own packet?

If the data packet is long enough and while the sender is till transmitting the data the collision signal comes.

T_t >= 2T_P

L >= 2T_P B

Back Off Algorithm is used to assign waiting time to the stations.

Refer to the resources for:

Token Passing

Aloha

The Comparison

Error Control

When many packets are sent to the receiver, the buffer might get filled up and the remaining packets are discarded. Another reason for errors is that we will receive the packet but a few bits will be corrupted. This can happen due to some external disturbance while the packet is being transmitted.

Error Detection	Error correction
Here, we only know that the packet got corrupted but we don't know which bits got corrupted. We cannot self-correct it and hence ask for retransmission.	Here, we know where the error is in the packet and hence we can self-correct it.

Error control Methods

• Cyclic Redundancy Check

• Checksum

• Parity check

• Hamming Distance

Hamming Distance (d)

Hamming distance between two points is the number of bits that are different at the same position. Let "d" be the hamming distance between 2 points "a" and "b".

d = a XOR b

To detect x bit error we need, d = x + 1

To correct x bit error we need, d = 2x + 1

Comparison

Where they take place

• Transport layer: Flow control and Error control

• Data link layer: Access control, flow control and error control

Flow control vs Access control

We first apply access control methods to get access to the channel link followed by the flow control methods to stop the receiver from overflowing.

Resources

• CS50 - YouTube channel

• The Bits and Bytes of Computer Networking - Google

• Computer Networking Full Course - Kunal Kushwaha

• Computer Network - Ravindra Babu Ravula Sir

• Computer Networking Course - Network Engineering [CompTIA Network+ Exam Prep] - FreeCodeCamp