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.

---

RTT is 80ms and not 82ms. This 80ms already includes transmission time for first packet + propagation time of first packet to reach receiver + propagation time of ACK receiver sends after receiving first packet.

---

@rfzahid I think now i am satisfied ...thanks bro I have been searching since long time but not get what i wanted .....whenever RTT given Then use  2a formula else use 1+2a........because some people take RTT =2Tp thats why this confusion arises....But actually  RTT  should be Tx+2Tp........let me know if i am wrong.........thanku very much

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 choices.

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{ bytes},$ we get

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

Comments

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

---

For those who are getting confused whether why the answer to this is not 41

See what efficiency is $\eta=\frac{useful\,time}{Total\,Time}$

Now, this Total time is the time when the sender receives the ACK for the first packet sent and then it can start sending the packets in the next window(After receiving ACK only window will slide).

Now here they have only given you RTT=80ms.(So, this is the total time right from the moment sender started sending the first packet to the moment when the sender received it's first ack.

Now, Useful time=$N \times T_t$

Where N=Optimal Window Size for efficiency required $\eta$

and $T_t=$TIme required to transmit one 32 byte frame->$2ms$

We need optimal window size so $\eta=1$

By Definition given above

$1=\frac{N \times 2}{80} \Rightarrow N=40$

---

40 shouldn't be a correct answer.

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

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 6

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 7

L = 32 Byte = 32*8 = 256 bits

B/w= 128 Kbps

Tt= L/B =2 ms

tp= RTT/2 = 40 ms

optimum window size = 1+2a

= 1+2*40/2 = 41 

Answer 8

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