# GATE2015-3-28

29 votes
5.6k views
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 ______.

edited
1
GETTING CONFUSE WITH ITS DUPLEX NATURE :

what should i consider about this channel as a FULL DUPLEX or HALF DUPLEX ?

because on considering as half duplex (i m getting 7 bits) and on considering as full duplex (i m getting 8 bits).
0
In question, it is mentioned that Network is to be used to its full capacity. So we take FULL DUPLEX.

## 7 Answers

42 votes

Best answer

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 time $=\dfrac{8000\times 10^3}{(4\times 10^6)}= 2\text{ secs}$

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

So, RTT $=2\times 2 = 4$

No of frames that can be transmitted in $4$ secs $=\dfrac{4}{0.02}=200$

Hence, minimum number of bits required for sequence numbers till $200$ is $8$ (as $2^8 = 256$ )

edited
46
I think it should be seq no for 201 packets not just 200

as 200 packets in RTT plus 1st packet too

although answer will be same 8 bits

but might be useful in some boundary cases of some other ques on the same concept
91
Actually u are partially correct.

Ws = (Tt + 2Tp) = 201 packets

Wr = 1 (GBN)

No. of seq. nos. req = Ws + Wr = 201 + 1 = 202.

Obv. the answer will still be the same = 8 bits.
0
can you explain how to find 201 packet after calculating the value of Tt and Tp.??
1
You can find out the window size of the sender from the efficieny formula of the GBN. Just equate efficiency to 1 since we need full capacity and substitute the values of Tt and Tp and solve for N. That will be the number of packets(window size of the sender).
0
Can anyone explain why sender have to wait till the acknowledgement in order to fully utilize channel ,ACC to me to fully utilize capacity which = 2*500*10^6, the no of packets = 100 of sender from there the no of bits =7 .can anyone solve my doubt?
0

The answers provided by @Ayush Upadhyayaseem correct. The selected answer is not completely right.

Let there be m bits in sequence number.

We have 2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

Go back n protocol:

Here, W$_{s}$ = 1+2a; W$_{r}$=1

2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

2$^{m}$ $\geq$ 1+2a + 1

m $\geq$ $\left \lceil log (2+2a) \right \rceil$

For this question, we have

2$^{m}$ $\geq$ 1 + 2a + 1

2$^{m}$ $\geq$ 2 + 2a

2$^{m}$ $\geq$ 202

m $\geq$ 8

35 votes

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

edited
0

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

0
correct
0

@Doley

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

1+2(2/0.02) = 201

15 votes
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
8 votes

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

4
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
5 votes
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
1
we can use..as N = SEQUENCE NO
2
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
2 votes
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
–1 vote
Answer is 8 bits.
1
how it is 8
1

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.

(we can ignore transmission delay at receiver as it is negligible)

One way propagation time = 8000x10^3 / (4x10^6)

= 2 secs

Time taken to transmit one frame = 10^7/(500x10^6)

=0.02 secs

No of frames that can be transmitted in 4 secs  = 4/0.02

=200

Hence minimum number of bits required for sequence numbers till 200 is 8 (as 2^8 = 256)

4
So, total number of frames that can be sent = 200 + 1 =201.

Please confirm.
Answer:

## Related questions

30 votes
5 answers
1
5.7k views
In the network $200.10.11.144/27$, the $fourth$ octet (in decimal) of the last $IP$ address of the network which can be assigned to a host is _____.
65 votes
9 answers
2
13.4k views
Two hosts are connected via a packet switch with $10^7$ bits per second links. Each link has a propagation delay of $20$ microseconds. The switch begins forwarding a packet $35$ microseconds after it receives the same. If $10000$ bits of data are to be ... time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is ______.
29 votes
5 answers
3
11k views
Consider a selective repeat sliding window protocol that uses a frame size of $1$ $\text{KB}$ to send data on a $1.5$ $\text{Mbps}$ link with a one-way latency of $50$ $\text{msec}$. To achieve a link utilization of $60\%$, the minimum number of bits required to represent the sequence number field is ________.
28 votes
2 answers
4
4.4k views
Consider the following C program: #include<stdio.h> int f1(void); int f2(void); int f3(void); int x=10; int main() { int x=1; x += f1() + f2 () + f3() + f2(); printf("%d", x); return 0; } int f1() { int x = 25; x++; return x;} int f2() { static int x = 50; x++; return x;} int f3() { x *= 10; return x;} The output of the program is ______.