8.7k views

Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Let $I$ be the minimum number of bits $(I)$ that will be required to represent the sequence numbers distinctly assuming that no time gap needs to be given between transmission of two frames.

Suppose that the sliding window protocol is used with the sender window size of $2^{I}$, where $I$ is the numbers of bits as mentioned earlier and acknowledgements are always piggy backed. After sending $2^I$ 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)

1. $16ms$
2. $18ms$
3. $20ms$
4. $22ms$

edited | 8.7k views
+11

In this question , RTT is calculated as :

RTT = Propagation time for frame + Transmission time for frame + Propagation time for ACK + Transmission time for ACK

Why ?

That is because in question it says

After  sending 2I frames , what is the minimum time the sender will have to wait before starting transmission of the next frame?

that means after the transmission time of those 2I frames , how much time it should wait to start transmitting again , which means we need that time until ACK arrives.

So, we just have to find the time when ACK arrives and  that's why RTT value counts Transmission time for ack here in this particular question.

0

@Arjun Veteran the no. of frames at max in the channel could be 24 not 25 i think

0
Since propagation time is 25ms, but we are still sending 32 packets, assuming half duplex connection, clearly the receiver can start transmitting piggybacked acknowledgement, only after 32ms. The receiver has to acknowledge all the 32 packets it received, and thus it will need 32transmissiins and one propagation.

Therefore wont the wait time be imcreased to 32+25=57ms?
0
RTT value includes transmission time of acknowledgement so to get waiting time exclude transmission time from it
0
What will be the efficiency? 32/52 = 61 % ?! Can someone check this?

Bandwidth won't be halved in full duplex. http://superuser.com/questions/335979/does-1-gbit-s-port-in-full-duplex-mean-1-gbit-s-send-and-1-gbit-s-receive

Propagation time is given as $25$ ms.
Bandwidth $= 10^6$ bps.
So, to fully utilize the channel, we must send $10^6$ bits into the channel in a second, which will be $1000$ frames per second as each frame is $1000$ bits. Now, since the propagation time is $25$ ms, to fully pack the link we need to send at least $1000 \ ^*25 \ ^* 110^{-3}= 25$ frames. So, we need $⌈log_2 \ 25⌉ = 5$ bits.

$I = 5$, so $2^I = 32$ frames are sent.

Now, we need to get RTT (which is the time between which a frame is sent and its ACK is received), to determine the waiting time.
Transmission time (for a frame of size $1000$ bits) $= 1000/10^6 = 1$ ms.
So, transmission time for $32$ frames $= 32$ ms.
RTT $=$ Propagation time for frame $+$ Transmission time for frame $+$ Propagation time for ACK $+$ Transmission time for ACK

$= 25$ ms $+ 1$ ms $+ 25$ ms $+ 1$ ms (ACK is piggy backed and assuming frame size for piggy backing is also $1000$ bits)
$= 52$ ms
So, waiting time $= 52 - 32 = 20$ ms. (For the $32$ ms, the sender was transmitting and not waiting)
Correct Answer: $C$
by Veteran (424k points)
edited
+1

In question it is mentioned that the ACKs are piggybacked, so the RTT will be 50 instead of 52.

Hence the answer will be 50-32=18.

0

In the solution of the second part on calculating RTT, you have chosen propagation time as 25 ms (given).
Similarly while solving the first part, RTT = (2^(no. of bits) * frame_size) / bandwidth (formulae)
Since propagation time is 25 ms, then RTT should be 50 ms.
We cannot match any option using RTT as 50 ms, but logically this should be the case.
Please correct me, if I am wrong...

+6
RTT is the time until which the ACK arrives. Just imagine what all happens from the moment a frame is send until ACK comes back and do the calculation. If you use formula given somewhere without understanding how you can get negative marks for free.
+1

@Arjun Sir,

"Frames are to be transmitted into this link to maximally pack them in transit (within the link)"

what is actually the meaning? i cannot understand. how is it different from link utilization? plz help sir...

+15
Consider dropping a bucket of water from a roof top. We say that the water is fully packed in transit if when the first drop touches the ground there is still a drop coming from the bucket.
+1
@Arjun sir

@arjun sir

Since the ack packets are piggybacked doesn't it mean there need not be any transmission time for the ack packets

The reason being that the receiver already has packets ready (the transmission time for these packets get interleaved with the time required by the sender's packets to arrive) so as soon as the packet from the sender arrives the ack gets piggybacked on the outgoing frame

Am I right??
+1
That will be interesting to do in practice. But even assuming receiver is continuously sending packets, to attach 'ACK' to a transmitted frame is not possible - or there is no practical way I know of. But who knows this can be done by some smarter way- thats a research problem :). As of now, to attach 'ACK', frame must be with the receiver and hence it can be transmitted only after getting attached.
+1

Hello Arjun sir, question says "After sending 2l frames ........" . What efffect does this statement has on our solution?  Why are we considering Transmission time of frame in our solution? No other question has confused me as much as this question. Please guide your disciple.

+6
@Priya That is so easy. Thsi question and most other questions for GATE are framed in such a way that those who knows what they learn are able to answer. IIT profs usually make sure those who knows only formula are not able to answer.

Here, the question- especially the second part is pretty clear. The sender sends $2^I$ frames and after this -- means after the transimission time of those $2^I$ frames -- how much time it should wait to start transmitting again -- which means time until ACK arrives. So, we just have to find the time when ACK arrives and subtract the transmission time of $2^I$ frames.
0
@arjun sir shouldnt be 52-31 ??
0
Nice explanation
–1
@Arjun Sir, why isn't is 52-31? Why are you considering the transmission time of a frame in 2nd part? the 32 frames have already been transmitted right!!
0
@arjun sir

Gate key says 18ms. so what we have to consider rtt=50 or 52?
0
How you got the GATE key? It was not published before 2012.
+1

@Arjun Sir, why are you counting 25 + 1 + 25  +1

i.e why are we counting transmission time for frame as 1ms in RTT, when you have already calculated 32ms fas total time for transmitting

0
thank you for explaining so so well.it has cleared a lots of things. :)
+3
Although Answer is Correct by @Arjun Sir But explanation is incorrect.

RTT will be count after sending atleast 1 frame, so after 1st frame sent

RTT= time to reach one frame at destination + one frame transmission time(ack. is piggybacked ) + time to reach ack. frame at sender         (ignore frame processing time at the receiver and sender side)

RTT= 25 + 1 + 25 =51 ms

there is still 31 frames to send at the sender side so waiting time will start after sending these 31 frames

waiting time = 51 - 31 = 20 ms
+1

RTT will be count after sending atleast 1 frame,

Who told this?

+1
No one but this isn't logical?

why we would count Round Trip Time of a packet without sending it.
+1
That depends on how RTT is defined. Does sending start from the first bit being sent or the last bit?
0
and if RTT is not defined we do not bother about first bit or last bit, we consider only packets.
+1
Round trip time(RTT) is the length of time it takes for a signal to be sent plus the length of time it takes for an acknowledgement of that signal to be received. This time therefore consists of the propagation times between the two point of signal.
0

Arjun I think it's worth mentioning that maximal window size is dependent upon transmission time.If it was less than 1 ms pipeline wouldn't have been fully utilized in transit.

+34

So, the sender will take 1ms time to place the first frame onto the link. This frame1 will take 25ms to reach the receiver. Assuming processing time to be negligible, the receiver starts transmitting ACK frame for frame 1. Since ACK are piggybacked, the same data frame is used for sending ACK so, in this case, $T_{ACK}=1\,ms$. This ACK will take another 25ms to reach the sender. Assuming processing time to be nil, total time elapsed from sending of frame 1 to receive its ACK=1+25+1+25=52ms.

Now, since the sender is sending all 32 frames without waiting for the acknowledgement ( means no gap between frames), the sender would be done sending all frames at 32ms.

So, at 52ms, the sender would start sending the next window of frames.

My sender has to wait= 52-32=20ms.

0
Nicely explained.
+1
Very nice Ayush
0
very nice explaination
0

@Arjun sir,

If sender is sending for complete RTT * BW ..then waiting time will be zero right?

As till the ack comes sender continously trasmitting onto the link and that will be the CASE for 100% efficiency right ?

i.e RTT*BW  = Ws * Length of frame

here we considered in RTT(Tt +2TP) time we can send RTT*BW data   ..accordingly we have done things

-----------------------------------------------------------------

But my doubt is if again 3rd question was What is capacity of the link then wht should be answer RTT * BW or 2TP* BW ?

0

key here is- and acknowledgements are always piggy backed

0
Is this link half duplex ?

Given, propagation time =25 ms.

Time required to transmit 1 frame = 1000 bits (frame size)/ 106 bps(bandwidth) = 1 ms

To fully utilize the channel, we need to transmit frames for propagation time(25 ms), 25 frames.

therefore, minimum no. of bits required for numbering 25 frames is = log 2(25) = 5 bits.

We need to calculate minimum waiting time after sending 2 frames (32 frames) to initiate transmission of next frame, for that we need to understand for what time sender is in busy mode and for what time sender is in waiting mode.

Sender is in busy mode during transmission of all the 32 frames, that means, for 32 ms.

after transmission sender is in waiting mode which is

= ( time required to get the ack for 1st frame ) - ( time for which sender is busy)

= (1+25+1+25) - (32) = 20 ms.

1+25+1+25 = transmission time for 1st frame + propagation time for frame + transmission time for ack as it is piggy backed + propagation time for ack

by Junior (757 points)
+2
In question it is mentioned that the ACKs are piggybacked, so the RTT will be 50 instead of 52.

Hence the answer will be 50-32=18.
0
0
So why sender will wait after 32 ms? He can go on sending more data without waiting any further?

This might help.

by (123 points)
+1
But the question says that acknowledgement is piggybacked.
Since I = 5 from previous question

Window size of sender = 2^5 = 32

Scenario 1 :

For 1st frame out of these 32 frames :

Tx = 1 ms , Tp = 25 ms and so Tx(ack) = 1ms (duplex so receiver is also sending some data and putting ack of received frame in it .i.e. piggybacking) , Tp(ack) = 25 ms

We are getting ack for first frame in time = 1 + 25 + 1 + 25 = 52 ms

After this time this first frame can be discarded from window and window can be slided to transmit frame number 33.

Scenario 2 :

1 frame takes 1ms to transmit

since window size is 32 we can transmit 32 frames on cable without waiting for ack of first frame.

which takes 32*1ms = 32ms

After sending for 32ms sender will sit idle till ack of 1st frame is not received.

Conclusion :  52ms - 32ms = 20ms is the time for which sender is waiting before transmiting next frame (frame 33).
by Active (2k points)
Size of sliding window = 2^5 = 32
Transmission time for a frame = 1ms
Total time taken for 32 frames = 32ms
The sender cannot receive acknoledgement before round trip time which is 50ms
After sending 32 frames, the minimum time the sender will have to wait before starting transmission of the next frame = 50 – 32 = 18
1------------25------32(last frame)----------50(first ack receive) so waiting time is (50-32) = 18ms(using pipelining)
Please any one correct me if I am wrong..
by Active (2.3k points)
edited
0

Hope it will make you clear.

This question would've been a lot easier, if they asked the maximum waiting time.
It'd simply be, $T_{p} + T_{t} + T_{p} = 51ms$

But they asked the minimum waiting time.
It'll be the total time for 1 packet - time for which the sender is busy.
= ($T_{t} + T_{p} + T_{t} + T_{p}) - 32 * T_{t}$
= 52ms - 32ms
= 20ms.

Option C

PS: The green coloured line depicts the total time for 1 packet.

by Active (1.9k points)
edited