# GATE2009-57, ISRO2016-75

20.9k views

Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

What is the minimum number of bits $(I)$ that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.

1. $I=2$
2. $I=3$
3. $I=4$
4. $I=5$

edited
0
Downvoting won't ace you rather explain question.
0
can someone plz explain the second part of the question..mainly in this part" no time gap needs to be given between transmission of two frames" .how it has been used in the question
0
Here they are not given the gbn or sr
then which one to consider..
And they ask for half duplex
How to approach for that
0
I think its similar to gbn protocol where they have mentioned window size which requires sequence no. ,but direct formula wont work here for gate questions.Here the catch is ACKs are always piggybacked which is given in the second part of the question.Now is Acks are piggybacked ,

Sender transmits one packet in 1 ms and receiver in 1 ms.Useful time = 2 ms

Total time from sending one packet from source to destination and back with piggybacked acks will take = 2 ms (total transmission time)+25 ms (sender to receiver propagation time)+25 ms (receiver to sender propagation time for Piggybacked Ack,which contains data as well as ack) = 52 ms

So,2 packets are sent in 52 ms timeframe from two sides,sender first packet reaches receiver in 26 ms after which receiver starts sending its data with ack of the sender added to it.By normal given book formula it is 52 packets we can pack,here its also same but both sender and receiver are packing 52 together 26 from sender,26 from receiver. Efficiency is also better here than normal case.
0
what is dulex mean here ?

what is the answer in both the cases

i used ceil of 1+2a .what is wrong with this approach ?
3

sushmita

why we are not considering 1+2a here directly ?pls explain

0

Link for $2^{nd}$ part  -> https://gateoverflow.in/43470/gate2009-58

0

@set2018 duplex can be full duplex half duplex any of them but assume full duplex by default

64

## The below SWS = 51 packets when the word mentioned is TRANSMIT or Transmitted.

2

### those packets are not in transit because at least one packet has reached the destination, processed and ACKED

brilliant answer by you.  really transit word  was playing a key role.

if nothing is mentioned about piggybacking in this question then we should not talk about it.

1

@iarnav sir it was really a brilliant explaination..

can you please also explain..that when we have to divide/ multiply the Bandwidth by 2, in cases of full or half duplex links

1
Thank you very much for this clarity.
1
I got the difference between transit and transmit but what is the difference between maximal and maximum in here....what would be the effect in answer if we have maximum in place of macimum?
0
Amazing answer, thank you. One question though, why do we need sequence numbers anyway? What purpose do they serve in this specific question.
0

@iarnav

not 51 frame only 50

total frame = RTT/TT

50 ms /1 ms= 50 frame

anyway thank you for sharing good information

0

@mohan123

No, the SWS is equal to the no. of frames transmitted in Transmission Time + Round Trip Time.

0
It's 50 not 51
0
it will be 51 only , "1 packet is put into link even before(or at the same moment) the start of propagation time (because that packet only going to start propagation time countdown)"
0

@dr_Jackal 51 is max frame  send

but in question mention pt=25ms ,  then rtt =50ms

50*ms*10^6=50000bit

frame size 1000 then 50000/1000=50

refer this

1 vote

simply:

L = 1000 bits (frame size)

Tp = 25 ms  (propagation delay)

B = 10^6 bps  (Bandwidth)

Tt = L/B = 1000/1000000 = 1 ms for 1 frame

in question given there is no any gap between two frames

so , i frame travel from sender to receiver there are 25 frames comes on link for fully utilize the link

Here 25 frames on link ,

so no. of required bits = ceil(log25)) = 5

correct option (C)

Actually, the question is asking the bits needed or frames needed so as to pack the link. We don't need to think more beyond this.

Now, $1$st bit will take $25$ms to reach other host. So, to fill the link we need frames occupying the link all this while which is $25$ms. Since $1$ frame is being transmitted in $1$ms, a host need to fire at least $25$ frames at once to keep the link fully occupied.  Therefore, $5$ bits needed.

Here transmission time Tt = L/B = 1000/10^6 = 1 ms

i.e  to transmit 1 frame we need 1 ms.

Now we are given that propagation time Tp=25 ms i.e in Tp time we can send 1*25 = 25 frames only.

Therefore no of bits required for sequence no = ceil( log2(25) ) = 5 bits.

A possible ans:

Every 1 ms we hv a new frame on the line. (BW 10^6 bps and frame size 1000 b).

See it as the first bit of the frame, the first bit touches the other end at 25 ms delay.

How many frames have we pushed on the line during this 25 ms as we were pushing 1 frame each 1 ms?

25 frames on the line at a time.

To identify 25 frames, we need 5 bits.

L=1000b,B=1000000b/s

Tt = L/B = 1ms

Tp = 25 ms

a  = Tp/Tt

For maximising the efficiency,no of frames that must be transmitted is 1+2a

thus no. of frames is 51

so no of bits required to represent 51 is 5(ans).

I think this the correct way. Please check if incorrect

Since, it is duplex link Therefore PIGGYBACKING is used.

Formula to be used here is
$\eta = \frac{w*2tx}{2tx + 2tp}$
where n = 1 here

Since in Piggybacking with frame ack. is also sent so txa should not be ignored here and txa=tx in piggybacking.

Therefore, Useful time = 2tx and total time is 2tx+2tp.

Use this formula you will get the answer.

maximally pack them in transit

Bits will only stay  in transit for max 25ms, because that's the propagation delay.

In $1$ second —> $10^6$ bits are passed through the link at max.

In $25 ms$ —> $25m * 10^6$ bits are passed through the link at max.

=> In $25 ms$ —> $25 * 10^3$ bits are passed through the link at max.

=> In $25ms$ —> $25 packets$ are passed through the link at max..

To uniquely identify 25 packets., we need 5 bits.

Option D

## Related questions

1
3.9k views
In which one of the following page replacement policies, Belady's anomaly may occur? FIFO Optimal LRU MRU
Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be the minimum number of ... wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time) $16ms$ $18ms$ $20ms$ $22ms$
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes
Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error? $G(x)$ contains more than two terms $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length $1+x$ is a factor of $G(x)$ $G(x)$ has an odd number of terms.