GATE2003-84

Question

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 send and receive 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 50 μs. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 $\mu$s. What is the maximum achievable throughput in this communication?

• A. $7.69 \times 10^6$ Bps

• B. $11.11 \times 10^6$ Bps

• C. $12.33 \times 10^6$ Bps

• D. $15.00 \times 10^6$ Bps

Comments

Isn't answer should be 88.88 X 10⁶ bps?

---

Ur Rght

option c is correct

since the solution is 

Throughput=total size/total time

                =1500*4/(60+2*170)*10^-6 

               =6000/400*10^-6

              =15*10^6 Bytes/sec

---

in the options they have used bps(small b which bits/sec) so what should we consider it in exam bytes or bits /sec

---

What happen when half duplex is given.

---

In case of half duplex the acknowledgements would need to be sent on a different channel. That will not affect throughput in this case since ack is considered to be negligible.

---

@anirudh @saurabh rai

I think all 5 packet reach to receiver within 250 microseconds so in another 200 microseconds ack trevel alone so there is no effect in throughput even in half duplex.

---

if they ask us to consider ack also and the link is half duplex

how this effects answer?

---

@ Yashaswini Vanaja   and @ Prashant.

 

 Wiki says  " For the highest possible throughput, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time(RTT). "   https://en.wikipedia.org/wiki/Sliding_window_protocol

So that means  though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following  Sliding Window protocol which has independent acknowledgements.

 

so you have to use RTT here and RTT = 2 * prop time + Transmission Time = 2 * 200 + 50 = 450 

 If it is half duplex  answer will be half of this answer  .

For throughput .

2*bandwidth*Tp = for full duplex link 

bandwith*tp = for half duplex 

---

Throughput in half Duplex = ( Throughput in Full duplex / 2 )

So channel type (means half duplex or full duplex) will just affect capacity or Throughput.. It does Not effect transmission time nor bandwidth.

---

@Bikram sir according to you

If I calculate the throughout it is 4MB/sec

Please correct me if I am wrong

---

what is the correct answer of this question/

---

The correct answer is 88.88 X 10⁶ bps(bit per sec) or 11.11X10⁶ Bps(Bytes per sec).

The correct Option is,(B) 11.11X10⁶ Bps

---

Answer should be 7.69 * 10⁶

Answer 1

We need the maximum throughput, and for that we need to send as much data
as possible to fully utilize the bandwidth.

so, maximum packets that can be sent $=1 + 2a = 9$ (after calculation) for $100\%$ efficiency.

But we have a window size of 5 only, so we can send only $5$ packets at max.

Efficiency $=\dfrac{5}{9}$

Now, $\dfrac{A}{Q},$ Bandwidth of the channel $(BW) =\dfrac{L}{T_t}$
$=\dfrac{1000}{(50\times 10^{-6})}$

$= 20\times 10^{6} \text{bytes/sec}.$

So, max. throughput achievable $=\text{Efficiency$\times $BW}$

$=\dfrac{5}{9}\times 20\times 10^{6}= 11.11\times 10^{6} \text{bytes/sec}.$

Comments

This seems to me a more sensible answer than the currently accepted one.

---

can u plzz tell me ahat will b throughput for half duplex ??

---

Is the sliding window protocol is even possible for half duplex?

---

well explained concept.....thnks

---

best way of explaination....great job :)

---

@ saurabh rai 

Throughput 

2*bandwidth*Tp=for full duplex link

bandwith*tp=for half duplex 

---

@Bikram sir

 if capacity of link is asked in question then it will be

2*bandwidth*Tp=for full duplex link

bandwith*tp=for half duplex

---

Yes, you are correct

Capacity = 2*bandwidth*Tp  for Full duplex link  and bandwith *tp=for half duplex link.... this is correct .

 Here we need to found Throughput ..  we consider capacity = throughput 

Maximum throughput is generally same as digital bandwidth capacity.

the term capacity is used many places in different way..throughput is one of them https://en.wikipedia.org/wiki/Computer_data_storage#Capacity

---

can u plzz tell me ahat will b throughput for half duplex ?

The value of Throughput in Half duplex is Half of the value we found in Full duplex.

Throughput in half Duplex = ( Throughput in Full duplex / 2 )

---

perfect

---

What will be the change in the calculation part, if it is given the half duplex link?

---

Anwer should be 7.69 $\times$ 10⁶ bps

Total time = 50 + 200(till this time all packet will come one link i.e. 50 $\times$ 4) + 200 for Ack till 4th paket + 200 for 5th packet = 650 micro sec

since TT given for one packet.

Throughput = $\frac{5 \times 1000}{650 \times 10^{6}} = 7.69 \times 10^{6} Bps$

Answer 2

I think options are given in bytes per sec instead of bits per sec.

Transmission time $=50 \text{ micro sec}$
Propagation time $=200\text{ micro sec}$

RTT$= 50+2\times 200=450 \text{ microsec}$

(Receiver can send an $\text{ACK}$ as soon as the first packet is received)

Total number of bits transmitted before first $\text{ACK}$ is received,
$=1000\times 5\times 8\text{ bits}=40000\text{ bits}$

After first $\text{ACK}$ is received, the same cycle of action repeats.

So, Throughput$=\left(\dfrac{40000}{450}\right)\times10^{6} \text{ bits}$

$= 88.88\times 10^{6} \text{bits per sec}$

$=11.11\times 10^{6}\text{ bytes per sec}$

Comments

Must be a typo in question. Bytes per second must be Bps.

---

@parul You took RTT=250+2*200=450.It shud be 650 ryt as per the calculation?

---

It should be 50+2*200 = 450.

---

Maybe i have mistakenly added 250 instead of 50. But now answer is correctly edited.

---

Okay. :)

But why taking transmission time of only a single packet? Host A can send one window, i.e. 5 packets in one RTT. So shudnt v consider transmission time of all 5 packets instead of one?

---

The receiver can send an ACK when it receives the first packet, or after all packets or sometime in between. There is no fixed rule for it. So, we can assume the best case. 

http://courses.cs.washington.edu/courses/cse461/07wi/lectures/l10.pdf

---

because after transmitting first packet when packet will travel from sender to receiver (Propagation time), other packets will transmit in that time gap. In other words, the sender will transmit rest of 4 packets when 1st packet will be travelling from sender to receiver. Means in overall 50+2*200 ms, sender will have transmitted all the 5 packets. Do you understand? if not let me know. And yes this is only my explanation so may be wrong.

 

---

That approach is not correct, in fact completely wrong. It is just assuming the time for the receiver to get the packets. But unless ACK is received back, sender can't resume sending. And that is why we need RTT.

---

In the best case we assume the receiver sends the request after receiving first packet??

Ack will be received at sender after 200 ms time. In mean time all remaining 4 packets are received at receiver that's why we take 5000 bytes in throughput??

If in Meantime only 2 packets are received at receiver and other 2 packets are still travelling over the link or out of remaining 2 packets only 1 packet is travelling and sender has 1 packet to send then what will be the throughput in both case??

---

here we have full duplex link. so, why did we take propagation time as twice..shouldn't be 200 only? please correct me if i m wrong. i am really confuse here.

---

My doubt is why ack is send after transmiiting the 5 packets , acc to me in sliding window protocol ack can be send  after transmiting any number of packets , so why we are taking 5 packets ,,,      plzzzzzzzzzzzzzzzz zz.  Clear this

---

what would be the answer if the link was given half duplex? @arjun sir

---

It is mentioned in the question that the sender and receiver window size is 5 packets.and therefore we send five packets in one attempt.

---

Even though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following selective repeat protocol which has independent acknowledgements.

---

 Parul Agarwal How u get bandwidth 10^6??? transmission time=packet size/bandwidth , bandwidth=1000/50^-6 = 20*10^6  byte per sec. correct me if u find something wrong

 

---

@rinky that is not bw .... actually the formula is like (data size /total time ) where datasize=4000 bits nd total time =450 micro sec. no bandwith is here....

---

$\text{Throughput} =\frac{\text{window size}}{RTT}$

$\text{window size}=5 \times 1000 $B
$RTT=T_t+2\times T_p=50+2\times200=450$micro seconds

$\text{Throughput} =\frac{5000B}{450ms}=11.11\times10^{6}$Bps

---

@Arjun sir

The link is given full duplex in the question. Then why we are taking propagation time twice?shouldnot the RTT be 50+ 200=250microsec?

i am not clear in this part when duplex links are given.also tell what would have happened if the link was half duplex?

---

@Bikram sir

The link is given full duplex in the question. Then why we are taking propagation time twice?shouldnot the RTT be 50+ 200=250microsec?

i am not clear in this part when duplex links are given.also tell what would have happened if the link was half duplex?

---

@ VS

RTT = 2 * Propagation delay + Transmission Time ......  ( By definition of RTT )

here Transmission time =50 micro sec
Propagation time =200 micro sec

so RTT = 2 * 200 +50 = 450 micro sec

 see this  https://gateoverflow.in/30319/rtt

---

@Bikram sir

https://cs.stackexchange.com/questions/21324/sliding-window-protocol-calculation-of-sequence-number-bits

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).

Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

---

@ VS 

Data packet size =1000 Bytes given
No of packets= 5  ( as sender and receiver window size is given )
so Total Data size =    1000 * 5 = 5000 Bytes

Propagation delay=200 micro sec ( given )
Transmission time= 50 micro sec/packet  ( given ) 
So for 5 packet Tp is = 250 micro sec

Total time for 5 packet=   Propagation time + Transmission time = 200+250=450 micro sec

= 450/10⁶ seconds 

Throughput  =  total data size / total time
=  ( 5000 / 450 ) × 10⁶
=11.11×10⁶ Bytes per seconds

 

PS : here i did not use RTT formula .

---

But @ VS , my above approach is NOT correct .. why ?

i am quoting Arjun Suresh here " That approach is not correct, in fact completely wrong. It is just assuming the time for the receiver to get the packets. But unless ACK is received back, sender can't resume sending. And that is why we need RTT. "

 

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender

 

Even though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following  Sliding Window protocol which has independent acknowledgements.

Another quote from wiki " For the highest possible throughput, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time(RTT). "   https://en.wikipedia.org/wiki/Sliding_window_protocol

so you have to use RTT here and RTT = 2 * prop time + Transmission Time = 2 * 200 + 50 = 450 

Yes it is full duplex here also if it is half duplex we also use RTT .

Hope , now your doubt gets clear !!

 

---

@Bikram sir First of all thanks a lot for your instant replies! I am really short of words to express my gratitude towards you.

Why RTT is not taken as

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

 = 50+200+200+50 (ACK is piggy backed and assuming frame size for piggy backing is also 1000 Bytes)
 

Throughput =10 mbps(no options matching)

Ref::https://gateoverflow.in/43470/gate2009-58

---

@ VS 

First of all there is No Standard definition of RTT . 

The definition of RTT depends upon how question is framed !

what i think is RTT =Propagation time for frame + Transmission time for frame + Propagation time for ACK + Transmission time for ACK

as what Arjun said in that answer.. actually RTT  means  the time between  a frame is sent and its ACK is received . Theoretically this is correct definition.

 

but see this question sys it is Full Duplex, which means the transmission of data in two directions simultaneously .

RTT is  taken in this question as  ( 2 * Prop time + Transmission time ) means Propagation time from sender to receiver + Propagation time from receiver to sender + Transmission time from any one direction

because propagation time always consider for each link and here Transmission time is overlapped hence consider only one time.

Hope this clears your doubts.

---

@Bikram sir

Thanks for all the pain that you are taking to clear my stupid doubts:)

But, I am saying it is really confusing as to what to take as RTT in each question

Here it is, RTT =  ( 2 * Prop time + Transmission time ) given full duplex link.

In this ::

 https://gateoverflow.in/43470/gate2009-58

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

Again full duplex link.

How can we assume whatever we feel like in gate exam,where we cannot afford to spend more than 5 min at max in a question?

---

@VS

As i said, there is no standard definition of  RTT , it depends upon question.

 
like RTT = 2 * Tp ,( by not including Transmission time )  also possible. For long distance network like Satellite , we ignore the Transmission time as we don't know how long that receiver is.

And also in both questions there is simultaneous data transmission and sliding window is used . 

Actual meaning of RTT is : RTT  is the time between  a frame is sent and its ACK is received.

Now depends upon question , we use formula.

This is actual how RTT value is calculated :

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

now generally we don't consider Transmission time for ack as it is piggybacked . thts why RTT formula becomes 2 * Tp + Tt

but in this question, https://gateoverflow.in/43470/gate2009-58 we have to add that Transmission time ack just because in question it says 

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

 

-- means after the transmission time of those 2^I 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.

Hope , somehow i clear your doubt ..this is good question from your side. And i only see in this 2009 question RTT is counted like this way ..almost everywhere we use RTT formula straightforward way like RTT = 2 * Tp + Tt ...

 

 

 

---

@Bikram sir

Thanks a ton for all the efforts you put in for clearing the doubts of students !!

As far as I can conclude on all the discussions about RTT ::

RTT=2*PT (for long distance n/w eg satellite)(Simplex +Half+ Full duplex) //TT of data and ack ignored

RTT=TT+2*PT (Most of the cases)(Simplex + Half+Full duplex) // TT of ack ignored

RTT=2*(TT+PT) (Simplex +Half+ Full duplex) //When waiting time of sender is asked

Anything wrong above ?

---

@ VS 

Yes, it is correct, you can also include Half Duplex . 

What do you think in case of half duplex those 3 cases of RTT value would be ?

---

Although the link is full duplex, but we are utilizing it as half duplex beacuse data is sent from only A to B which is explicitly mentioned in question.thats why things will not change when the same case will be taken with half duplex.

if, in this question it is given that data is sending from both side A to B and also from B to A then it will differ from the half duplex link.

---

@Bikram sir

Edited above.

@reena_kandari

if, in this question it is given that data is sending from both side A to B and also from B to A then also it will not differ from the half duplex link.

Because TTdata+PTdata is taken for sure in RTT, Now about PTack.

PTack is included even if the data is going from B to A because Receiver can send an ack only upon receiving a frame.

https://gateoverflow.in/69139/full-duplex

---

@VS  and @Reena

yes, both half duplex and full duplex give same result for all 3 cases of RTT .
 data is sending from both side A to B and also from B to A then it will Not differ from the half duplex link.

In half duplex  link from A to B first data transmitted then from B to A.

In Full duplex both from A to B and B to A , data is transmitted at same time ..

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

should be same for both the cases .

---

@Bikram SIr,@Vs

RTT does not include transmission time.It is totally dependent upon the cable/link we are using.RTT=2*PT(always).

Ref:-  https://en.wikipedia.org/wiki/Round-trip_delay_time

Now the maximum sender window size= (2*Bandwidth*Delay)+1.    //or we can say that maximum sender window size is the number of frames it can send it in (TransmissionTime+round trip time),So as window is 5 ,it means entire 5 frames can be send  in  TT+RTT=50+400 =450.

This concept is well explained in Tanenbaum book.

---

@Bikram Sir, it is given in the question that:-

Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time.

 thats why we are considering RTT as TT of data + PT of data (A to B) + PT of ack(B to A).

Secondly, We are getting 450 msec as RTT, I think it is because, it is given in the question that 

The send and receive window sizes are 5 packets each

which shows that they are using Select and Repeat ARQ, and in This ARQ the receiver can send cumulative ack for all the data packets. i.e. I think sender is sending all five packets in one go itself and then waiting for ack to come in, That;s why it require TT of data, and in this TT it sends all 5 packets, and PT of ACk(B to A) in this time Sender is waiting for cumulative ack.

That's why the time is 50 + 2*200 = 450, ryt sir,

---

@ Shubhanshu 

For your first doubt, yes your assumption is correct. 

Read my above comments, we discussed this issues..

----

For your 2nd doubt :

The send and receive window sizes are 5 packets each

Yes, your reasoning is correct..

though the connection is full duplex, next window will be sent only after acknowledgement will be received by sender because it is following  Sliding Window protocol which has independent acknowledgements.

So the main point is : Sender is waiting for cumulative ack.

---

@Bikram Sir, I have a doubt in the line which I have written 

That;s why it require TT of data, and in this TT it sends all 5 packets,

if it is sending 5 packets then TT should be 5*TT of each packet as given in the question

the transmission time for such a packet is 50 μs

if it is so then we should get (5* 50 + 2*200 ) micro seconds but why isn't so???

---

@Shubhanshu 

This is very simple concept. What i have learnt from taenenbaum is that 

Maximum sender window is the number of frames that will be sent in TT+2PT or TT+RTT

So 5 frames can be sent in 50+2*400 =450.

 

You can read this from tanenbaum for clarification

---

Ok so whatever be the window size means what ever no of packet we sent it will always TT+2PT

---

Yes. Maximum sender window size =Number of frames in 2*bandwidth +1 = Number of frames in TT+RTT because in one RTT is same as 2*BD and one TT is time for one frame so all are same

---

@rahul

the definition of RTT is not 2*PT , Its only in tanenbaum, but other books quote it differently.

Please check this once.

---

which other books?

---

@rahul

Just read discussions between us in above comments...

RTT have no worldwide standard definition..in Kurose you can check it may be different there..

in above discussions we discuss what actually RTT is and in which cases what value of RTT should we use !

---

can't we follow the approach, throughput=bytes sent(5*50) / total bytes that can be sent(5*50+RTT*Bandwidth )   in the way it has been followed in the solution to

GATE2008-IT-64

by Danish

I am confused where we are supposed to add the Transmission time for all sent packets or single packet to compute the efficiency , Please help me in that

---

@Bikram Sir,

One doubt. If the transmission would have happened both A->B and B->A at the same time in this full duplex,then answer would be 22.22×10^6bytes/sec.

Answer 3

5000 bytes are being sent in 200 + 50×5 us.so troughput =5000/450  ×10^6 =》11.11×10^6 option b.

Answer 4

In this question we need not to add acknowledgement time of last packet because here for throughput they are assuming that this tramsmission is continuous for indefinite time(It is a real system based question)

so Tt=250 micro sec

  Tp=200 microsecond

  N= 5000 bytes

so throughput= 5000/450 microsec = b option