12,958 views

The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be the channel capacity. Assuming that the processing delay is negligible, the $\text{minimum}$ number of bits for the sequence number field in a frame for maximum utilization, when the $\text{sliding window protocol}$ is used, is:

1. $\lceil \log_2 \frac{2LtR +2K}{K} \rceil$

2. $\lceil \log_2 \frac{2LtR}{K} \rceil$

3. $\lceil \log_2 \frac{2LtR +K}{K} \rceil$

4. $\lceil \log_2 \frac{2LtR +2K}{2K} \rceil$

Can anybody answer, when to use capacity mentioned as capacity and not as bandwidth??

Ps: Knowing that would we have easily solved this question!

See according to option dude. If none matches with capacity then it's definitely bandwidth. I don't think they would put both options with ambiguous terminologies
Number of packets sent is inversely proportional to the Throughput

Hence

it is 1/1+2a

We can send $\dfrac{\text{RTT}}{\text{Transmission Time}}$ number of packets

for maximum utilization of the channel, as in this time, we get the first $\text{ACK}$ back and till that time, we can continue sending packets.

So, $\dfrac{\text{Transmission Time + 2$\times $Propagation Time}}{\text{Transmission Time}}$ number of packets should be sent.

Therefore, bits required for the sequence number field:

$\left \lceil \log_2 \left(\frac{\dfrac{K}{R}+\large 2Lt}{\dfrac{K}{R}}\right) \right\rceil = \left\lceil \log_2\left(\dfrac{K+2LtR}{{K}}\right) \right\rceil$

Edit : here it is asked for general sliding window protocol not GBN nor SR .

In general sliding window protocol:

Sequence number bit $=\log \text{(sender window size)}$

Thanks @subhanshu even I interpreted it same way as you mentioned your comment made me sure that I was thinking in right way!!

Let there be m bits in sequence number.

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

Case 1) Sliding window protocol:

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

(we do not have any buffer at the receiver end. The receiver simply sends a cumulative acknowledgement.)

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

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

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

Case 2) 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$

Case 3) Selective repeat:

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

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

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

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

Someone please let me know if this is right. :)

R is channel capacity is given not the bandwith

where channel capacity =2*BW *tp

please clear this doubt

for maximum utilization $\eta = 1$,

\begin{align*} \eta &= SWS \times \frac{\text{Transmission Time}}{\text{Transmission Time + 2\times$Propagation Time}} \\ \\ 1 &= SWS \times \frac{\text{Transmission Time}}{\text{Transmission Time + 2$\timesPropagation Time}} \\ \end{align*}

so, $\dfrac{\text{Transmission Time + 2$\times$Propagation Time}}{\text{Transmission Time}} =\text{SWS}$

gives the number of packets that are sent. It means that it is the Sender's Window Size.

But we also know that,

$\text{available sequence numbers} \ \geq \text{ SWS + RWS}$

so, to get the minimum number of bits needed to represent the sequence numbers - we should consider what protocols are in use.

if GBN ARQ:

\begin{align*} \substack{\large\text{# bits required to rep.} \\ \large\text{ sequence numbers}} &= \lceil \log_2{(SWS + RWS)} \rceil \\ &= \left \lceil \log_2{\left(\frac{\frac{K}{R} + 2Lt} {\dfrac{K}{R}}+1 \right)} \right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 2LtR}{K}\right)} \right \rceil \end{align*}

if Selective Repeat ARQ :

\begin{align*} \substack{\large\text{# bits required to rep.} \\ \large\text{ sequence numbers}} &= \lceil \log_2{(2\times SWS)} \rceil \\ &= \left \lceil \log_2{\left(2\times \frac{\frac{K}{R} + 2Lt}{\frac{K}{R}}\right)} \right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 4LtR}{K}\right)} \right \rceil \end{align*}

When we are talking about only sliding window protocol, we only care about sender's window.
If it is explicitely mentioned about GBN or SR then only focus on reciever's window.
(Sliding window protocol is a theoretical concept, implemented using either GBN or SR protocol)

So C is the ans.
Maximum Sender window is = Number of frames in 2*BD+1.

Now using above if you find maximum sender window.You will get the same answer as given.C should not be correct option.Because if question is saying maximum utilization then there is always 1 frame we need to add to 2*BD
Sequence number bit =log(sender window size)

because Question mention minimum number of bits for the sequence number but we can take only SWS not RWS WHY ?

Because of we can only transmit in GBN So, take only SWS not include RWS.

$Answer$ C

$a = \frac{Tp}{Tt}$

$\text{For maximum utilisation,}$

$\frac{W_{s}}{1+2a} = 100$%

$log(1+2a)$ is the answer

$Tt = \frac{K}{R}$

$Tp = t\times L$

$log(1+2a) = log(1+2\frac{t\times L}{\frac{K}{R}})$

$log(1+2a) = log(\frac{2LtR+K}{K})$

by

Ws(window size of sender)=1+2a  where a=Tp/Tt

minimum sequence number possible= 1+2a

min. num of bit for sequence number = ⌈log(1+2a)⌉ ************************** Equation 1

Tp/Tt=Lt/(K/R)

1+2a=(K+2LtR)/K

put value of 1+2a in eq 1

@bikram sir, this method is correct, isn't it?
Is Tp not L/t.....i mean Tp=distance/velocity......!!

Given t is not velocity.

Delay per km is given as t sec. So total delay in L km is L * t sec.

1
28,784 views