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

GATE-2005
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
Explanation:
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
Explanation:
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
Explanation:
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

GATE-2006
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)



Explanation:
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.

GATE-2009
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
Explanation:
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

GATE-2007
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)
Explanation:
Given,
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]

2 comments:

  1. 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
    timeout
    9 (9 sent)


    Total = 16

    ReplyDelete