GATE2006-44

Question

Station $A$ uses $32$ $\text{byte}$ packets to transmit messages to Station $B$ using a sliding window protocol. The round trip delay between A and $B$ is $80$ $\text{milliseconds}$ and the bottleneck bandwidth on the path between $A$ and $B$ is $128$ $\text{kbps}$ . What is the optimal window size that $A$ should use?

• A. $20$
• B. $40$
• C. $160$
• D. $320$

Comments

can any one give me how utilization is n/(1+2a) , where a is : propagation delay / transmission delay )

---

Round Trip propagation delay = 80ms
propagation delay=80ms/2=40ms
Frame size = 32*8 bits
Bandwidth = 128kbps
Transmission Time = 32*8/(128) ms = 2 ms

Let n be the window size.

UtiliZation = n/(1+2a) where a = Propagation time / transmission time
a=40/2=20
= n/(1+2*20)
=n/41
For maximum utilization: n = 41 which is close to option (B

---

Sir, this was a numerical type question. And there are two possibilites for the answer:

1. We take the transmission time which is 2ms and answer come out 41.

2. We ignore transmission time, and answer comes out 40.

Which one is correct (marks were provided for which answer) and which possibilty should we choose for solving such types of question?

Regards

---

Any one please clear this 40 or 41?And why not 41?

---

ans is 40 , and RTT = 2 * propagation delay is taken here .

---

@ Bikram sir here T_t is not very less to T_p, that why are you ignoring transmission time? And if this question was NAT type, than 40 or 41 matters a lot. 

---

Yes even I have same doubt why not 41 and why we ignoring transmit time? Our we should choose answer which is closest? And what if question is numerical type:(

---

For future visitors, I've written an answer below using bandwidth delay product which is not ambiguous. You can refer that.

Answer 1

Round trip delay $= 80\ ms$.

Quoting from Wikipedia

the round-trip delay time (RTD) or 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 acknowledgment
of that signal to be received.

Now, in many books including standard ones, they have used $\text{RTT}$ to mean just
the $2\text{-way}$ propagation delay by considering the signal/packet as of the smallest
possible quantity so that its transmission time is negligible.
The given question is following the first definition as given by Wikipedia which is clear from
 the choice.

During this time the first $\text{ACK}$ arrives and so sender can continue sending frames.
So, for maximum utilization sender should have used the full bandwidth during this time.
i.e., it should have sent $128\text{ kbps}\times 80\ ms$ amount of data and a packet
being of size $32\text{ byte}$.

we get no. of packets $=\dfrac{128 \times 80}{32 \times 8} = 40.$

Comments

what would be the exact value 40 or 41??

---

Sender sends first frame in tx=32x8/(128x10^3)=2ms time, after 2 x tp = 80ms time, 1st ACK arrives, during these 80 ms, additional 80/2 = 40 packets can be sent; so shouldn't the answer be 41?

---

+1

---

@mysticprince There is no additional. In the time before ACK arrives we can sent just 40 packets including the initial one. 41 is wrong.

---

@Arjun sir, Ack returns after 80ms, initial transmission took 2 ms, so its 82ms window, why can't we have 41 packets? In your answer you haven't taken into consideration that 1 packet is transmitted before, transmitting packets, in the wait-for-ack gap. What do you say?

---

what is this "before"?  ACK returns after 80ms and the total no. of packets that can be transmitted is whatever is possible to transmit in this interval.

---

I don't know what was I thinking, when I wrote that one! :D I meant, that after the first packet is fully transmitted, there's this additional 80ms, when you usually wait in Stop-n-wait.

---

Question same but full duplex then what is answer @arjun sir

---

So,Sir RTT $= T_t + 2T_p$ ???

---

Here propagation delay is 40ms means 20 frames are present in medium when first bit of 1 frame received by the receiver. receiver take some time(1 transmission time) to receive first packet, after receiving first packet it sent ACK that take negligible transmission time.

In this time sender put one more packet in the medium at this point total 20+1 packet had been send by the sender. ACK first bit take 40ms in this time sender put 40 more frames. It means that when sender receive first frame ACK it had been send 41 frames. is this correct sequence @arjun sir

---

arjun sir- formula is 1+2a= 1+2*Tp/Tt and it evaluates to 41. why 40 :( ?

in numerical type question what will be the answer 40 or 41?

---

but in many problems we consider thr transmission delay alsoand there is nothing like we need to negect tt in the question we get tt as 2 msec if we consider that we get 41

---

here Tt is 2ms and Tp is 39ms, We ignore Tt when Tt<<<Tp but this is not the case here
now apply N=1+2(Tp/Tt)=40 is the anser

---

I also think that answer should be 41,but 40 is the closest match. Because maximum size if sender window=Number of frames in RTT+1. Here +1 indicates that after 1 PT receiver will get first bit of first frame and by the time first framer is completely received by receiver sender can transmit 1 more frames.

---

how 39 ? i got tp=40

---

Use this: rtt = tt + 2tp

---

@Arjun sir, why aren't we counting the first packet sent?

During this time the first ACK arrives and so sender can continue sending frames...

Before the starting of 80 ms of RTT, we already have sent the first packet. After sending that first packet, we start counting the RTT time(i.e. 80ms). And for max efficiency, sender should keep sending during this 80ms, in this time we can send 40 packets. So, in total we sent 40 + 1 (initial) packets. 

Where am I wrong?

---

Why we are not using formula (1+2a) here ??

---

Arjun sir,in order to send the acknowledgement by the receiver it has to completely accepts that packet..i.c it has to accept the last bit of that packet so in the sender end it has to transmits the last bit of that packet for which it takes one transmission time and then that last bit has to be propagate to the receiver end for which it takes one propagation time and then the receiver sends the acknowledgement for which it takes one propagation time more (considering transmission time for the acknowledgement is negligible)...so here during that two propagation time sender can send atmost 40 packets and during the first transmission the sender already send one packet so in total the sender can send atmost 41 packets at max...

                Sir if the above cocept is correct then the ans should be 41 (if numerical ans type questio come).the same above cocept is used to solve the problem which has been asked in gate 07 (the distance between two stations  M and N is L km.....)..where they mention the solution is option C...
          Sir whether i am correct or not ...verify it please...

Answer 2

Answer: B

Round Trip Time $= 80ms$
Frame size $=32\times 8\text{ bits}$
Bandwidth $=128\text{ kbps}$
Transmission Time $=\dfrac{32\times 8}{128}\ ms = 2\ ms$
Let $n$ be the window size.

Utilization $=\dfrac{n}{1+2a}$

where $\large a = \dfrac{\text{Propagation Time}}{\text{Transmission Time}}$

$ =\dfrac{n}{1+\dfrac{2 \times 40}{2}}$

For maximum utilization: $n = 41$ which is close to option (B).

Comments

@Rajarshi Value of a will be = 80/2 = 40

Utilization = $\frac{n}{1+2*40} = \frac{n}{81}$
n = 81 instead of 41.

Please correct it.

---

you are doing mistake actual formula is

utilization = n* tp/ (tp+ 2tp)

80 is rtt= 2Tp

---

@sv_jan5 , no

Here R.T.T. = 80

a = P.T. / T.T.

& 2a = 2*p.T. / T.T.  = R.t.t. /  T.T.  {since RTT = 2PT}

so, 2a  =  80/2 = 40

---

Ok I got it!
It is written in the answer that "propagation time or Round trip time" this is a bit confusing. as P.T = RTT/2

---

yes, that's an error.

---

Here the bandwidth mentioned as 128kilo bytes per second....so dont we need to write in the denominator as 128×8....

---

k.eswar prasanth No! 128 Kbps means 128 * 10^3 bits per second. 

 

if it's 128Mbps it would be 128*10^6 bits per second. 

There's no multiplying by 8 

Answer 3

RTT is 80 ms , irrespective of what T(p) & T(t) values are .

The acknowledgment is reaching at 80th ms and not 82nd ms (If calcualated T(t) values and added to twice of T(p) = 40 )

Here T(t) + 2 T(p) = 80 ms

 

So 128 kb  == 1 sec
      128 bits == 1 ms
       1ms == 128 bits
        80 ms == 80 * 128 bits

So no of frame required = ( 80 * 128 ) / 256
                                   = 40 frames (Window Size)

Answer 4

ans b)

Comments

can any one explain it.?please ...

---

@harsha RTT=80 therfore TP=40  as RTT=2TP

TT= L/B   L= 32*8 = 256 and BW= 128 therfore TT=2

window size = (1+2tp/tt)

1+2(40/2) = 41 which is very close to B)

Answer 5

Here, we can use the concept of bandwidth delay product.

What is bandwidth delay product?

"It's the amount of data that left the sender before the first acknowledgement was received by the sender. That is, bandwidth * round trip time = the desired window size under perfect conditions. If the round trip time is measured from the last packet and the sender's outbound bandwidth is perfectly stable and fully used, then the measured window size exactly calculates the number of packets (data and ACKs together) in transit. If you want only one direction, divide the quantity by two."

Further reading: http://www.kehlet.cx/articles/99.html, https://learningnetwork.cisco.com/thread/125627

The bandwidth delay product is given by:  $BW \times RTT$, which in this case is $128 \,\text{kbps} \times 80 \times 10^{-3} \text{s}$, which comes as $10240$ bits.

Therefore, number of packets can be given by $\frac{10240}{32 \times 8} = 40$ packets, which does not have any off by one error.

Answer 6

It is already mentioned in the question that bottleneck bandwidth is used and initial bandwidth is not given ie. no use to calculate TT.

So, no. of packets = (128×80)/(32×8) = 40.      Ans.

Answer 7

I m trying to tell all of u with some example lets forget 40 or 41 here probelm is not prpblem os what should be logic , so if calculate max window size we try to calculate max pkt we can send in time of 1st pkt reach at destination so according to this rtt includes both transmisson time as well as propogation time . Here rtt is given so we have not to think extra propagation time all r included in it so if u calculate u will find ans