Wednesday, December 26, 2012

GATE questions on Computer Networks - Sliding Window Protocol

Previous GATE questions with solutions on Computer Networks (Sliding Window Protocol) - CS/IT

1.The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is
a) 2n            b) 2n-1                    c) 2n-1                   d)2n-2

Ans: Option b
Selective Reject (or Selective Repeat) protocol is one of the automatic repeat-request (ARQ) techniques used for communications. 
In SR protocol the window size of the receiver and sender must be (N+1)/2, where N is the maximum sequence number.
If N is the maximum available sequence numbers then, the window size of both sender and receiver must be N/2.
If n is the number of bits in the frame sequence field then, the window size of both sender and receiver must be  2n-1.

GATE 2003
2.Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The sender and receiver window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50ms. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200ms. What i the maximum achievable throughput in this communication?
a)7.69x106bps         b) 11.11 x106bps               c)13.33 x106bps                 d)15.00 x106bps

Ans: Option b
Throughput =1 window/ RTT
RTT = Round Trip Time = Transmission Time + 2 x propagation time
                                          = 50ms + 2 x  200ms = 450ms

Since the size of window = 5 packets and 1 packet contains 1000 bytes the total size of the packet in bytes is 5 x 1000 = 50000bytes

Therefore, Throughput = 5000 bytes/ 450 x10-6 s = 11.11 x106bps 

GATE - 2006
3.Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip time delay between A and B is 80ms and the bottleneck bandwidth on the path A and B is 128kbps. What is the optimal window size that A should use?
a) 20          b) 40            c)160        d)320

Ans: Option b
Since we have to find the optimal window size, we are indirectly said that maximum throughput should be achieved. Hence the maximum throughput that we can achieve is 128kbps.
RTT = 80ms
Packet size = 32 x 8 bits

We know, Throughput =1 window/ RTT
Therefore optimal window size = Throughput x RTT 
                                              = 128x103 x 80x10-3
                                              = 128 x 80 bits
Therefore, optimal window size in terms of packets = (128 x 80) / (32 x 8) = 40

4.Station A needs to send a message consisting of 9 packets to station B using a sliding window (window size 3) and go back-n error control strategy. All packets are ready and immediately available for transmission. If every 5th packet that A transmits gets lost (but no acks from B ever get lost) then what is the number of packets that A will transmit for sending the message to B?
a) 12         b) 14       c) 16             d) 18

Ans: Option a (There are lot of confusions regarding the answer. Even if the answer is given as option a in the answer key, according to me answer should be 13)

Sender continues to send number of frames specified by the window size even without receiving an acknowledgement (ACK) packet from the receiver.
Note that the receiver in GBN strategy never receives  a frame which is out of order. That is, say 1st frame is received by the receiver, but 2nd frame is lost, and then it receives 3rd frame. Even if the 3rd frame is received and is correct, the receiver will discard the 3rd frame because it didn't receive the 2nd packet. 
The receiver process keeps track of the sequence number of the next frame it expects to receive, and sends that number with every ACK it sends. The receiver will ignore any frame that does not have the exact sequence number it expects. Once the sender has sent all of the frames in its window, it will detect that all of the frames since the lost frame are outstanding, and will go back to sequence number of the last ACK it received from the receiver process and fill its window starting with that frame and continue the process over again.

5.Frames of 1000 bits are sent over a 106 bps duplex link between 2 hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

I. What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames. 
a) l = 2            b) l = 3         c) l = 4         d) l = 5

II. Suppose that the sliding window protocol is used with the sender window size of 2l where l is the number of bits identified in the earlier part and acknowledgments are always piggybacked. After sending 2l frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)
(a) 16ms   (b) 18ms   (c) 20ms   (d) 22ms

I Ans: option d
Since duplex, link can deliver only 106/2bps

We know, Throughput =1 window/ RTT
Therefore optimal window size = Throughput x RTT 
                                              = (106/2) x 50 x10-3
Therefore, optimal window size in terms of packets = (25x103)/1000 = 25

Since we have 25 frames to send we require minimum 5 bits to represent the sequence numbers distinctly.

II Ans: option b
Explanation: From previous question we got l=5
Therefore Window Size = 2l frames = 32 frames

Transmission time for 1 frame = Size of a frame / Bandwidth
                                           = 1000 / 10= 1ms

Total time taken for 32 frames = 32ms
The sender cannot receive acknowledgement before 50ms.
After sending 32 frames, the minimum time the sender will have to wait before starting transmission of the next frame = 50 – 32 = 18ms

6. The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:
(a) log2 [(2LtR + 2K)/K]
(b) log2 [(2LtR)/K]
(c) log2 [(2LtR + K)/K]
(d) log2 [(2LtR + K)/2K]

Ans: option (c)
Bandwidth = R bps, Frame Size = K bits, distance between stations = L kms

Propagation delay = t seconds per km
                          = Lt seconds

We knowThroughput =1 window/ RTT

Since link utilization is maximum => Throughput = R

RTT = (2 x propagation delay) + Transmission Time
      = 2Lt + (K/R)

1 window in terms of bits = Throughput x RTT
                                      = R {2Lt + (K/R)} = 2LtR + K

1 window in terms of frames = [2LtR + K ]/K

Sequence numbers required: 2[2LtR + K ]/K    
{where n is the number of bits for the sequence number field}
Therefore n = log2 [(2LtR + K)/K]


  1. The answer of the question no.4 of gate 2006 to count the number of times the frames are being transmitted is wrongly solved by you. It's answer should be 16.
    1-2-3 4-5lost-6 (go back to 5)till timeout
    7-5-6 7lost-8-9 (go back to 7)till timeout
    7-8-9lost (after timeout of 9 again send 9th)
    total No. of frames transmitted is 16.

    1. yes answer should be 16 only

    2. i have a doubt what if using gb4 and every 3rd packet lost and you have to send 10 packets then total no of transmission?

  2. Answer of question 4 should be 16, because as every 5th frame is lost. So receiver will never send any ack for that. But Sender will keep sending the frame available frame in the window.
    3 2 1 (1sent)
    4 3 2 (2 sent)
    5 4 3 (3 sent)
    6 5 4 (4 sent)
    7 6 5 (5 sent) --- 5th lost -- no ack
    7 6 5 (6 sent) - no ack until receiver gets 5th
    7 6 5 (7 sent) - no ack until receiver gets 5th
    sender can no longer send anything now...timeout for 5th
    7 6 5 (5 sent)
    8 7 6 (6 sent)
    9 8 7 (7 sent) -lost
    9 8 7 (8 sent) no ack
    9 8 7 (9 sent) - no ack
    timeout for 7
    9 8 7 (7 sent)
    9 8 (8 sent)
    9 (9 sent) - lost
    9 (9 sent)

    Total = 16

    1. i have a doubt what if using gb4 and every 3rd packet lost and you have to send 10 packets then total no of transmission?

  3. IN Q.4 , they might consider window size 3 , n according to that ans is 12.

  4. hello sir! Thank you for posting this..... But i have a confusion in question 2..... window size is 5 so transmission time should be 5*50 is it 50 ms

  5. in question 4 gate2006 ans 12 is correct b'coz window will not shift untill it get 6th pkts ack so after lost the pkts it will re transmit 5&6 not 5,6,7. window never slide untill all three pkts reach successfully
    so transmitted sequence will be like (1,2,3),(4,5,6) 5 lost re transmit (5,6) (7,8,9) lost 9 re transmit (9)

  6. in q.2 1ms=1/1000 sec
    but u did 1ms=1/1000000 sec

  7. in answer 6 window size should be 2^n -1
    and answer will be option (a)

  8. Replies
    1. i have a doubt what if using gb4 and every 3rd packet lost and you have to send 10 packets then total no of transmission?

  9. Q4
    5+2 transfers for first probe, after all transfers the timeout is detected,the 5th packet is sent again,and 6th on 7th the collision is detected the time out is after 2 more packets are sent ,this repeats till all 9 packets, and the acknowledgement for 1st pack comes at the start of 4th packet,not the third,

  10. This comment has been removed by the author.

  11. Question no 4 right ans is 16 packets


  12. If 5 bits are used for sequence number then what is the sender window size in selective repeat scheme

  13. Since we have 25 frames to send we require minimum 5 bits to represent the sequence numbers distinctly.

    Why 5 bits. Could anyone explain it?

  14. Because 25 can be represented in binary form in 5 bits, i.e 11001. Any number less than that can be represented in less than or equal to 5 bits. Hence 5 bits are needed.

  15. In sliding window protocol total 8 packets are needed to send and if every 4th packet is lost then find the number of transmission is needed by the sender

  16. Consider a scenario where 2 hosts transmit to each other using
    Go-Back-N ARQ with 2 bits for sequence numbers.
    1. What is the maximum window size that can be used?
    2. Now assume that Host A has 6 frames to send to Host B. If the 2nd
    frame out of the 6 frames is lost, sketch the sequence of transmission and
    acknowledgements between the 2 hosts. Assume that each frame is 1 unit long,
    time-out is 4 time units, and propagation times are negligible.

  17. Question no 6 in simpler way..

    efficiency = window size/(1+2*a) where a=Tp/Tt { Tp = propagation time, Tt = Transmission time}

    So now, Tp = L*t and Tt = k/R

    therefore a=L*t*R/k

    For max utilization window size = 1+2*a

    putting the value of a

    window size = (2*L*t*R + k)/k

    so no. of bits required in sequence no. field is log2((2*L*t*R+k)/k)