The Gateway to Computer Science Excellence

+22 votes

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

0

Excerpt from 2014-1 Question Paper

Consider a selective repeat sliding window protocol that uses a frame size of **1 KB** to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is

+96 votes

Best answer

$\eta_{SR} = \dfrac{N}{1+2a}$

$B = 1.5 \text{ Mbps}$

$T_p = 50 \text{ ms}$

$L = 1 \text{ KB} = 1024 \times 8 \text{ bits}$

$\eta_{SR} = 60\%$

$\therefore 0.6 = \dfrac{N}{1+2a}$

$\implies N = 0.6 (1+2a)$

$a =\dfrac{T_p}{T_t} = \dfrac{T_p}{L} . B = \dfrac{50\times 10^{-3} \times 1.5 \times 10^6}{1024 \times 8} = 9.155$

$\therefore N = 0.6 \times (1 + 2 \times 9.155) = 11.58$

$w_s + w_R \leq \text{ASN}$

$\implies 2N \leq \text{ASN}$

$\implies 2\times 11.58 \leq \text{ASN}$

$\implies \text{ASN} \geq \lceil 23.172 \rceil$

$\implies \text {ASN} \geq 24$

$\therefore \text{Minimum number of bits required for sequence number field} = \lceil \log_2 24 \rceil = 5.$

$B = 1.5 \text{ Mbps}$

$T_p = 50 \text{ ms}$

$L = 1 \text{ KB} = 1024 \times 8 \text{ bits}$

$\eta_{SR} = 60\%$

$\therefore 0.6 = \dfrac{N}{1+2a}$

$\implies N = 0.6 (1+2a)$

$a =\dfrac{T_p}{T_t} = \dfrac{T_p}{L} . B = \dfrac{50\times 10^{-3} \times 1.5 \times 10^6}{1024 \times 8} = 9.155$

$\therefore N = 0.6 \times (1 + 2 \times 9.155) = 11.58$

$w_s + w_R \leq \text{ASN}$

$\implies 2N \leq \text{ASN}$

$\implies 2\times 11.58 \leq \text{ASN}$

$\implies \text{ASN} \geq \lceil 23.172 \rceil$

$\implies \text {ASN} \geq 24$

$\therefore \text{Minimum number of bits required for sequence number field} = \lceil \log_2 24 \rceil = 5.$

0

@Vikrant suppose this question is asking in GBN then wil we multiply 2? As i also get value of N = 11.58

And I took log of 11.58 which is 4

and also what happen in simple stop wait protocol I think in stop wait answer is 4.. plzz help in this

And I took log of 11.58 which is 4

and also what happen in simple stop wait protocol I think in stop wait answer is 4.. plzz help in this

+6

@aman.anand

In GBN, receiver window size is 1. So the equation will be N+1 <= Available Sequence Numbers

In GBN, receiver window size is 1. So the equation will be N+1 <= Available Sequence Numbers

+34 votes

A frame is $1\text{ KB}$ and takes $\dfrac{8\times 10^3}{1.5\times 10^6}\ s = 5.33\ ms$

to reach the destination. ( $8$ is used to convert byte to bits)

Adding the propagation delay of $50\ ms,$ the total time will be $50 + 5.33 = 55.33\ ms$

Now, we need the $\text{ACK}$ to reach back also, so the time between a packet is sent

and an $\text{ACK}$ is received $= 55.33 + 50\text{(transmission time of ACK neglected)}$

$= 105.33\ ms$

The channel band width is $1.5\text{ Mbps},$ so in $1\ ms,\ 1.5K$ bits can be transferred

and so in $105.33\ ms,\ 157.995 K$ bits can be transferred.

To, ensure $60\%$ utilization, amount of bits to be transferred in

$1\ ms = 157.995\times 0.6 = 94.797\ Kb =\dfrac{ 94.797}{(8\times 1000)}$ frames

$= 11.849\text{ frames}\approx 12\text{ frames}.$

(we bounded up to ensure at least $60\%$ utilization)

So, we need a minimum window size of $12.$

Now, in selective repeat protocol, the window size must be less than half the

sequence number space.

http://stackoverflow.com/questions/3999065/why-is-window-size-less-than-or -equal-to-half-the-sequence-number-in-sr-protocol

So, this means sequence number space must be larger than $2\times 12 = 24.$

To have a sequence number space of $24,$ sequence bits must be at least $\log_{2} 24 = 5$

0

"The channel band width is 1.5 Mbps, so in 1 ms, 1.5 K bits can be transferred and so in 105.33 ms, 157.995 K bits can be transferred."

sir here 157.995 k bits are the maximum bits which we can transfer right ?? as we have discussed here https://gateoverflow.in/1267/gate2007_69?show=42108#c42108

and if i will divide 157.995k by frame size i.e, 157.995k / 8 * k then i will get number of frames when channel utilization is maximum ? right

+4

sir why have you taken propogation delay as 50 ms......in forouzan book,it was given **latency = propogation time +transmission time.****why it is not propogation time + trnasmission time =50 ms**

0

There is no "propagation" there rt? Delay is for the packet to reach the sender. I took propagation delay same as propagation time.

0

Sir how in 5.33 ms packet can reach at destination. I think this is the transmission time.

Please clear me.

Please clear me.

+3

@Arjun Sir,

I could not understand what do u mean by **"There is no "propagation" there rt?"**

How packets are moving between source and destination without propagation.. Please clarify. What I am missing here

0

@Arjun Sir, plz reply i am also having the same doubt, why u are adding transmission time with one way latency given, as it implicitly include transmission time as given in forouzan book and image is shared above?

+1

Yog If there was no propagation delay then the frame would have taken 5.33ms(because of the bandwidth).

but there is a delay of 50 ms in the propagation hence 5.33+50 = 55.33ms.

**In telecommunications a link is a communications channel that connects two or more devices**(wiki)

You guys are confusing bandwidth with transmission.

Transmission time is limited with the transmitting device(node) and not the link connecting them

0

@Arjun Sir .... Is it the correct thinking about this question

TT - Transmission time , PT - Propagation time

Since link utilization is given as 60% then

$\implies$ $\frac{60}{100} = \frac{TT}{TT + 2PT}$

$\implies$$6TT + 12PT = 10TT$

$\implies$$TT = 3PT$ this becomes transmision time according to given data

Now total time $= TT + 2PT$

$= 3PT + 2PT$

$= 5PT$

$\implies$ $5*50 ms = 250 ms$

Bits transmitted in 250 ms = $\frac{250 * 10^{-3} * 1.5 * 10 ^ {6} }{1024 * 8}$

= 45.77

= 46

Number of sequence bits = log(46) = 6

Hance 6 bits should be used.

Please correct me sir if I am thinking wrong

TT - Transmission time , PT - Propagation time

Since link utilization is given as 60% then

$\implies$ $\frac{60}{100} = \frac{TT}{TT + 2PT}$

$\implies$$6TT + 12PT = 10TT$

$\implies$$TT = 3PT$ this becomes transmision time according to given data

Now total time $= TT + 2PT$

$= 3PT + 2PT$

$= 5PT$

$\implies$ $5*50 ms = 250 ms$

Bits transmitted in 250 ms = $\frac{250 * 10^{-3} * 1.5 * 10 ^ {6} }{1024 * 8}$

= 45.77

= 46

Number of sequence bits = log(46) = 6

Hance 6 bits should be used.

Please correct me sir if I am thinking wrong

0

sir i feel this is correct but then how do i find logic to correct answer. please guide if u understood it

0

@Arjun sir

why you 11.849 as 12 but not 11..by considering 12 efficency will be greater than 60 % but we want 60%

+5 votes

Transmission delay = Frame Size/bandwidth

= (1*8*10^3)/(1.5 * 10^6)=5.33ms

Propagation delay = 50ms

Efficiency = Window Size/(1+2a) = .6

a = Propagation delay/Transmission delay

So, window size = 11.856(approx)

min sequence number = 2*window size = 23.712

bits required in Min sequence number = log_{2}(23.712)

Answer is 4.56

Ceil(4.56) = 5

+1 vote

Bandwidth delay product = Bandwidth x RTT

$\rightarrow 1.5\times 10^6 \times 2\times 50\times 10^{-3}=1.5\times 10^5$ bits.

$Utilization=\frac{N\times packet\ size}{Bandwidth\ delay\ product}$

$\rightarrow 0.6=\frac{N\times 8\times 1000}{1.5\times 10^5}\rightarrow6\times 15=N\times 8$

$\rightarrow N=\frac{45}{4}=11.25 \approx12.$

In selective repeat, $N\leq\frac{2^n}{2}\rightarrow12\leq\frac{2^n}{2}\rightarrow2^n\geq24\rightarrow n\geq log_2(24)$ or $n \geq 5$.

$\rightarrow 1.5\times 10^6 \times 2\times 50\times 10^{-3}=1.5\times 10^5$ bits.

$Utilization=\frac{N\times packet\ size}{Bandwidth\ delay\ product}$

$\rightarrow 0.6=\frac{N\times 8\times 1000}{1.5\times 10^5}\rightarrow6\times 15=N\times 8$

$\rightarrow N=\frac{45}{4}=11.25 \approx12.$

In selective repeat, $N\leq\frac{2^n}{2}\rightarrow12\leq\frac{2^n}{2}\rightarrow2^n\geq24\rightarrow n\geq log_2(24)$ or $n \geq 5$.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,523 answers

195,602 comments

101,286 users