!
Tag: Flow Control in Computer
Networks
Stop and Wait ARQ | Go back N |
SR Protocol
!Computer Networks
Flow Control Protocols-
In computer networking, there are various flow control
protocols-
Sliding Window Protocol-
Sliding window protocol allows the sender to send
multiple frames before needing the
acknowledgements.
It is more efficient.
Advertisements
Learn more
Read More- Sliding Window Protocol
Implementations-
Various implementations of sliding window protocol are-
1. Stop and Wait ARQ
2. Go back N
3. Selective Repeat
In this article, we will compare these sliding window
protocols.
Advertisements
Learn more
Comparison Table-
Selective
Stop and Wait ARQ Go back N Remarks
Repeat
Go back N and Selective Repeat gives better
Efficiency 1 / (1+2a) N / (1+2a) N / (1+2a)
efficiency than Stop and Wait ARQ.
Sender Window Size = 1 Buffer requirement in Selective Repeat is very
large.
Receiver Window Size = 1
If the system does not have lots of memory,
Advertisements then it is better to choose Go back N.
Ads by Advertisements
Send feedback
Sender Window Sender Window
Why this ad?
Size = N Size = N
Window Size Receiver Window Receiver Window
Size = 1 Size = N
Minimum number
Selective Repeat requires large number of bits
of sequence 2 N+1 2xN
in sequence number field.
numbers required
Retransmissions Only the lost
The entire window Selective Repeat is far better than Go back N in
required if a packet Only the lost packet is retransmitted packet is
is retransmitted terms of retransmissions required.
is lost retransmitted
Bandwidth
requirement is high
because even if a
single packet is
lost, entire window Bandwidth
Bandwidth Selective Repeat is better than Go back N in
Bandwidth requirement is Low has to be requirement is
Requirement terms of bandwidth requirement.
retransmitted. moderate
Thus, if error rate
is high, it wastes a
lot of bandwidth.
High due to
searching and
Go back N is better than Selective Repeat in
CPU usage Low Moderate sorting required at
terms of CPU usage.
sender and
receiver side
Complex as it
Level of difficulty in requires extra Go back N is better than Selective Repeat in
Low Moderate
Implementation logic and sorting terms of implementation difficulty.
and searching
Uses cumulative
acknowledgements
Uses independent Sending cumulative acknowledgements reduces
(but may use
Acknowledgements Uses independent acknowledgement for each packet acknowledgement the traffic in the network but if it is lost, then the
independent
for each packet ACKs for all the corresponding packets are lost.
acknowledgements
as well)
Type of Go back N and Selective Repeat are better in
Half duplex Full duplex Full duplex
Transmission terms of channel usage.
Conclusions-
Advertisements
Go back N is more often used than other
protocols.
SR protocol is less used because of its
complexity.
Stop and Wait ARQ is less used because of its
low efficiency.
Depending on the context and resources
availability, Go back N or Selective Repeat is
employed.
Selective Repeat and Stop and Wait ARQ are
similar in terms of retransmissions.
Go back N and Selective Repeat are similar in
terms of efficiency if sender window sizes are
same.
SR protocol may be considered as a combination
of advantages of Stop and Wait ARQ and Go back
N.
SR protocol is superior to other protocols but
because of its complexity, it is less used.
Important Notes-
Note-01:
Advertisements
Protocols at data link layer like HDLC (Low level
protocols) use Go back N.
This is because-
1. Bandwidth is high
2. CPU is very busy doing routing job
3. Error rate is low since out of order packets are not
possible in wired medium
Advertisements
Note-02:
Protocols at transport layer like TCP (High level
protocols) use selective repeat.
Advertisements
PRACTICE PROBLEMS BASED
ON SLIDING WINDOW
PROTOCOLS-
Problem-01:
If the bandwidth between the sender and receiver is
sufficient, CPU and buffers are moderate, then which
flow control protocol would you suggest to use?
Advertisements
Learn
more
Replay
Solution-
The suggested protocol would be Go back N.
Advertisements
Problem-02:
If the bandwidth between the sender and receiver is
moderate, CPU and buffers are sufficient, then which
flow control protocol would you suggest to use?
Advertisements
···
Solution-
The suggested protocol would be Selective Repeat.
To gain better understanding about sliding window
protocols comparison,
Watch this Video Lecture
Next Article- Miscellaneous Problems On Flow
Control Protocols
Get more notes and other study material of Computer
Networks.
Watch video lectures by visiting our YouTube channel
LearnVidFun.
Flow Control Protocols | Practice
Problems
!Computer Networks
Flow Control Protocols-
In computer networking, there are various flow control
protocols-
Stop and Wait Protocol
Stop and Wait ARQ
Go back N Protocol
Selective Repeat Protocol
In this article, we will discuss practice problems based
on these flow control protocols.
PRACTICE PROBLEMS BASED
ON FLOW CONTROL
PROTOCOLS-
Problem-01:
In what protocols is it possible for the sender to receive
an acknowledgement for a packet that falls outside its
current window?
1. Stop and Wait
2. Selective Repeat
3. Go back N
4. All of the above
Solution-
Delayed Acknowledgements fall outside the
current window.
They may occur in any of the flow control
protocols and received by the sender.
Thus, correct option is (D).
Problem-02:
On a wireless link, the probability of packet error is 0.2.
A stop and wait protocol is used to transfer data across
the link. The channel condition is assumed to be
independent from transmission to transmission. What is
the average number of transmission attempts required
to transfer 100 packets?
1. 100
2. 125
3. 150
4. 200
Solution-
Method-01:
Given-
Probability of packet error = 0.2
We have to transfer 100 packets
Now,
When we transfer 100 packets, number of packets
in which error will occur = 0.2 x 100 = 20.
Then, these 20 packets will have to be
retransmitted.
When we retransmit 20 packets, number of
packets in which error will occur = 0.2 x 20 = 4.
Then, these 4 packets will have to be
retransmitted.
When we retransmit 4 packets, number of packets
in which error will occur = 0.2 x 4 = 0.8 ≅ 1.
Then, this 1 packet will have to be retransmitted.
From here, average number of transmission attempts
required = 100 + 20 + 4 + 1 = 125.
Thus, Option (B) is correct.
Method-02:
REMEMBER
If there are n packets to be transmitted and p
is the probability of packet error, then-
Number of transmission attempts required
= n + np + np2 + np3 + …… + ∞
= n / (1-p)
Substituting the given values, we get-
Average number of transmission attempts required =
100 / (1-0.2) = 125.
Thus, Option (B) is correct.
Problem-03:
Compute the fraction of the bandwidth that is wasted on
overhead (headers and retransmissions) for a protocol
on a heavily loaded 50 Kbps satellite channel with data
frames consisting of 40 bits header and 3960 data bits.
Assume that the signal propagation time from the earth
to the satellite is 270 msec. ACK frames never occur.
NAK frames are 40 bits. The error rate for data frames
is 1% and the error rate for NAK frames is negligible.
1. 1.21 %
2. 2.12 %
3. 1.99 %
4. 1.71 %
Solution-
Consider 100 frames are being sent. Then, we have-
Useful Data Sent-
Since each frame contains 3960 data bits, so while
sending 100 frames,
Useful data sent
= 100 x 3960 bits
= 396000 bits
Useless Data Sent / Overhead-
In general, overhead is due to headers, retransmissions
and negative acknowledgements.
Now,
The error rate for data frames is 1%, therefore out
of 100 sent frames, error occurs in one frame.
This causes the negative acknowledgement to
follow which causes the retransmission.
So, we have-
Overhead due to headers = 100 x 40 bits = 400
bits.
Overhead due to negative acknowledgement = 40
bits.
Overhead due to retransmission = 40 bits header
+ 3960 data bits = 4000 bits.
From here,
Total overhead
= 400 bits + 40 bits + 4000 bits
= 8040 bits
Calculating Efficiency-
Efficiency (η) = Useful data sent / Total data sent
Here,
Useful data sent = 396000 bits
Total data sent = Useful data sent + Overhead =
396000 bits + 8040 bits = 404040 bits
Substituting the values, we get-
Efficiency (η)
= 396000 bits / 404040 bits
= 0.9801
Advertisements
···
Calculating Bandwidth Utilization-
Bandwidth Utilization
Advertisements
···
= Efficiency x Bandwidth
= 0.9801 x 50 Kbps
= 49.005 Kbps
Calculating Bandwidth Wasted-
Bandwidth wasted
Advertisements
···
= Bandwidth – Bandwidth Utilization
= 50 Kbps – 49.005 Kbps
= 0.995 Kbps
x Learn More
Calculating Fraction of Bandwidth
Wasted-
Ad : (0:07) 0:07
Advertisement:
Fraction of bandwidth wasted
