GATE CSE 2015 | Set 3 | Question: 28

Question

Consider a network connecting two systems located $8000$ $\text{Km}$ apart. The bandwidth of the network is $500 \times 10^6$ $\text{bits}$ per second. The propagation speed of the media is $4 \times 10^6$ $\text{meters}$ per second. It needs to design a Go-Back-$N$ sliding window protocol for this network. The average packet size is $10^7$ $\text{bits}$. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then, the minimum size in bits of the sequence number field has to be ______.

Comments

full capacity means 100% efficiency

---

👍

---

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

Answer 1

Answer = 8 bits.

In order to achieve full utilization, sender has to keep on sending frames till
the acknowledgement arrives for the first frame.

Time taken for acknowledgement to arrive is $2$ times propagation delay $+$ transmission time for a frame.

One way propagation delay $=\dfrac{8000\times 10^3}{(4\times 10^6)}= 2s$

Time taken to transmit one frame $=\dfrac{10^7}{(500\times 10^6)}=0.02s$

 So, RTT $=2\times 2 + 0.02 = 4.02s$

No. of frames that can be transmitted in $4.02$ secs $=\dfrac{4.02}{0.02}=201$

Being Go-Back-N protocol this means $W_S = 201$ and $W_R=1.$ So, total number of sequence numbers required $ = 201+1=202.$

Hence, minimum number of bits required for sequence numbers till $202$ is $\lceil \log_2 202 \rceil = 8.$ 

Comments

Is using link in full capacity same as 100%.efficiency or link capacity then we have to take Bandwidth and propagation delay product .pls help

---

@AGNIDEB MUKHERJEE Yes, using link in full capacity is same as 100%.efficiency, i.e fully utilizing the channel.

---

Thanks 👍

Answer 2

Isn't the minimum sequence number $\geq$ SWS+RWS.
So we are getting $201$ for the sender window and since we are using $\text{GBN}$
we should add $1$ as the RWS.

So total sequence number $\geq 201+1 =202.$

Answer will still remain 8 though

Comments

can you help me in calculation part?  here how the sender window size is 201? 

---

correct

---

@Doley

sender window size is 1+2a where a = propagation delay/ transmission delay.

1+2(2/0.02) = 201

Answer 3

Given $T_{processing}=0,Transmission_{ack}=0$

My total RTT here is $T_{data}+T_{prop}+T_{prop}=T_t+2*T_p$

My useful time will only be $N*T_{data}$ where $T_{data}$ will be transmission time for one frame.

so my efficiency

$\frac{N*T_{data}}{RTT}=\frac{T_{data}*N}{T_{data}+2*T_{prop}}=\frac{N}{1+2*\frac{T_p}{T_t}}=\frac{N}{1+2a}$

so, my efficiency would be 100% only if I send 1+2a packets into network in RTT time.

This 1+2a comes to be 201.

Now, this is the sender's window size. Receiver window size would be 1. So, the total you would need 202 distinct sequence numbers for frames and this requires $\lceil log_2202 \rceil = 8$ bits

Answer 4

to know  the minimum size in bits of the sequence number field when the The network is to be used to its full capacity we need to send until RTT time.

propagation speed is given by which we can find propagation time ...
to travel 4x10^6 meters its take 1 second
so for 8x10^6 meters it will take 2 second which is our propagation time

now our RTT will be  2*PT=2*2=4 second 

now we can find that in 4 second how much data we can transfer using Bandwidth. 
in 1 second we transferring 500x10^6 bits
so in 4 second  we will transfer 500x10^6 bits*4=200x10^7 bits 
now we can find the total no packets to be transfer (window size) =200x10^7 bits/10^7=200 packets
to represent 200 we need 8 bits which is our answer
 

Comments

We have to consider Ws as number of packets send in $T_{t}+2T_{p}$ time and not $2T_{p}$ alone.(as given network is used to full capacity)

ie, in 2*2+0.02 =4.02s --> 4.02*500*$10^{7}$= 201 x $10^{7}$ bits

Number of packets =$\frac{201 * 10^{7}bits }{10^{7}bits (length of packet)}$=201

Total sequence numbers required=Ws(201)+Wr(1)= 202

Number of bits for sequence number =8

Answer 5

Can we not use the formula for Utilization here it is fully utilized so 1=N/1+2a that way N=201 no of bits required in go back n for window size is 2^k-1=201..k-8 bits

Comments

we can use..as N = SEQUENCE NO

---

even my doubt also same ..why can't we use full utilization formula at that case no.of available sequence numbers is 202.

if this is wrong what is the difference between full utilization of network and full capacity ?

please clarify this

Answer 6

Given, L =  10^7 bits , B = 500 * 10^ 6  SO , Tt = L / B = 0.02 sec

d = 8000 km ,V = 4*10^6 m/sec SO, Tp = d / v = 2 sec

a = Tp / Tt = 2 / 0.02 = 100

The network is to be used to its full capacity so η = 100 %

Go-back-N protocol, So η = w/(1+2a) where w = 2^n-1
w = 1+2*a

⇒ 2^n - 1 = 201
⇒ 2^n = 202 ⇒ n = 8