GATE IT 2006 | Question: 64

Question

Suppose that it takes $1$ unit of time to transmit a packet (of fixed size) on a communication link. The link layer uses a window flow control protocol with a window size of $N$ packets. Each packet causes an ack or a nak to be generated by the receiver, and ack/nak transmission times are negligible. Further, the round trip time on the link is equal to $N$ units. Consider time $i > N$. If only acks have been received till time i(no naks), then the goodput evaluated at the transmitter at time i(in packets per unit time) is

• A. $1- \dfrac{  N}{i}$
   
• B. $\dfrac{i}{(N + i)}$
   
• C. $1$
   
• D. $1 - e^{\left(\frac{i}{N}\right)}$

Comments

$\text{Hint}$

$1^{st}$ $ACK$ @ $N+1$
$2^{nd}$ $ACK$ @ $N+2$
$3^{rd}$ $ACK$ @ $N+3$​​​​​​​
...
$i^{th}$ $ACK$ @ $i-N$

$Goodput = \dfrac{\text{#packets successfully transmitted}}{\text{Total #packets transmitted}}$

---

The hint is great, but there will be a small correction:

$(i-N)^{th} ACK $ @ $i ( = N +(i-N))$ 

instead of : $i^{th} ACK$ @ $i-N$

---

here RTT =2Tp

---

RTT is given as N units and window size=N then how it can be 2Tp as 1 unit of time is required for transmitting 1 packet so total transmission time of window will become N there is no scope left for any other delays.

---

The question seems to be somewhat incorrect because RTT is given as N units and window size=N, as 1 unit of time is required for transmitting 1 packet so total transmission time of window will become N units there is no scope left for any other time consumption so how the RTT can be N units.

---

Why 1st ACK @ N+1?

Since RTT is given as N units so it should be relieved within N units. Not only 1st RTT of whole window is N so all ACK's should arrive in N units. But that doesn't seems to be possible.

---

GO to the Root of Concept: Video Explanation with timestamp: Sliding Window PYQs| GATE 2009 Q57, 58| 2006 Q46, 64| 2003, 2014, 2015, 2004, 2016, 2007| With NOTES

---

OPTION_A

This is a tricky question (or rather, a poorly framed one).
There are two possible interpretations of RTT (refer to this).
In this question, the RTT is calculated excluding the packet transmission time, which is the less common interpretation.

THANKS TO @Sachin Mittal 1(no one could have explained better)

---

https://youtube.com/clip/UgkxL6ye3c6zT0fDOKFuu0HqZ9GWUJhXMhJl?si=fMWY5jz-fzuyRYeU.    Sachin sir answer...

---

https://gateoverflow.in/3608/gate-it-2006-question-64

---

is this in DDL lectures of sachine sir vedio ? or in TCP lectures @DIVYANSH_SRIVASTAVA

Answer 1

In computer networks, goodput is the application level throughput, i.e. the number of useful information bits delivered by the network to a certain destination per unit of time. (From wikipedia).

So, successful delivery of packet can be assured if $\text{ACK}$ has been received for it.

So till time $'i'$ we would have transmitted $'i'$ packets but only $(i-N)$ can be acknowledged as minimum time for a packet to get Acknowledged is $N$ (since $\text{RTT}$ is $N$ which is equal to the window size, there is no waiting time
for the sender).

So, successfully delivered packets $=(i-N)$

Time for transmission $=i$

Goodput $=\dfrac{\text{Successfully delivered data}}{\text{Time}}$

$=\dfrac{(i-N)}{i}$

$= 1- \dfrac{ N}{i}$

Therefore (A)

Comments

At time N we recive ack for -------> 1st packet

At time N+1 we recive ack for -------> 2nd packet

At time N+2 we recive ack for -------> 3rd packet

.

.

.

at time i we recieve ack for -------> i - N + 1 th packet
 

so throughput should be = $\frac{i - N + 1}{i}$

 

why we are idle after transmitting N packets? becuase as we recieve 1st ACK the timer is at N or we can say sender will recieve its first ACK immediatly after sending $N$th packet

---

@RahulVerma3 correction: At time i we receive ack for ----> i-N+1 th packet not N-i+1 th because i>N given in question. 

---

RTT = Tp(Packet) + Tp(Ack) = N
TTT = Tt(Packet) + RTT = 1 + N

So we will receive 1st Ack at 1 + N time not N

Answer 2

I tried to make it easier by taking an example that how it is actually working. 

 

Comments

just in case if anyone thinking about the accumulative

acknowledgements.

 

"Each packet causes an ack or a nak to be generated by the receiver"

 

---

The first acknowledgement will arrive at the time when 5th frame is being sent not at 6th time, beacuse no. Of frame sent = round trip time..

---

@ash_khola

here round trip time has different meaning, i think here it is $R.T.T=2*T_{prop}$. So $1st$ ACK will arrive at $t=6$ according to the diagram in the solution. 

Answer 3

At T = N + 1 1st ack arrives judging this pattern and some manipulation we can get to the answer :)

Answer 4

1 unit of time —  packet.

N units of time — N packets.

i units of time — i packets.

 

If only acks have been received till time i (no naks)

It means till time i, i packets are ACKed?

No.

Whatever i is, ACKed packets would always be (i - N) because it takes N units of time to receive an ACK for a packet (because N is the RTT). So from total packets (ie i packets) ACKed packets are (i - N).

 

So, Goodput = $\frac{i-N}{i}$

=> $\frac{i}{i} - \frac{N}{i}$

=> $1 - \frac{N}{i}$

 

Option A

Answer 5

Goodput is the application level throughtout, i.e., the no. of useful information bits delivered by the network to a certain destination per unit of time.
So, successful delivery of packet can be assured if ack has been received for it.
So till time 'i' we would have transmitted 'i' packets but only (i - N) can be acknowledged as minimum time for a packet to get acknowledged is N (since RTT is N which is equal to the window size, there is no waiting for the sender).
So, successfully delivered packets = (i - N)
Time for transmission = i
Goodput = Successfully delivered data/Time
= (i - N)/i
= 1 - N/i

Answer 6

 

The image explains

everything clearly