search
Log In
75 votes
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$
in Computer Networks
edited by
20.9k views
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
Please explain me
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

This question is purely wordplay! The most important words are transit and maximal. 

There's a night and day difference in the meaning of words - TRANSMIT and TRANSIT.

Informally Transit is - When you order a package from say China and destination is say Delhi the tracking shows - 

China - Shenzhen - Kolkata  . . . . . . . .  Delhi.

Currently your package is stuck at customs in Kolkata and not reached the destination Delhi (your home). So you can say your package is in transit or according to question your frame is in transit and not delivered to your home or receiver, but in this question we are sending many frames per second and to be precise, here 1000 frames are in transit per second or Sender should send 1000 frames per second to utilize the link fully and in question they are asking - 

Maximal (not maximum) frames should be in transit i.e the maximum frames should be on the way from Sender to Receiver or simply put before the first frame reaches the destination, how many frames sender can put on the link, that we need to find. 

That's why it's only one way (Tp i.e the time which is in the hands of the acting Sender to bombard the channel/link with as many packets he can send, but B/W is 10^6 bps and Sender can only send data in bundles of 1000 bits because frame size is 1000 bits. So, 10^6 divided by 1000 gives you 1000 frames per second, but sender has allocated a fixed time for this Transmission which is the Tp time of 25 millisecond.) and there's no concept of RTT because of word transit.

So, Sender can send 1000 frames per second. So in 25 seconds sender can send 25000 frames, but sender doesn't have 25 seconds, sender has 25 milliseconds. So Sender can only send for 25 milliseconds thus - 25000*10^-3 will give you 25 frames per millisecond and that makes sense because when you calculate Tt it's 1ms i.e Sender takes 1 ms to put one frame on the link and thus in 25ms it can put 25 frames, thus verified, things are fine! So SWS in transit maximally can hold 25 frames and thus log(25) ceil = 5 bits.

More information ---- When you take the word TRANSMIT AND TRANSIT AS SAME, which indeed is wrong!

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

The reason we are getting N (SWS) = 51 packets and then 6 bits for sequence # field is wrong because we are calculating MAXIMUM packets (TRANSMITTED TO R (not sure of being successfully transmitted because no ACK, but trasmit nonetheless from S to R AND NOT IN TRANSIT to R) that S can send which includes the RTT of 2*25ms = 50ms and then you say it's 1 + 50 = 51 packets, but those are MAXIMUM packets and not maximal and on top of that those packets are not in transit because at least one packet has reached the destination, processed and ACKED. Considering 1ms for piggybacking, that's something different.

My main intention was to tell "the words TRANSIT and MAXIMAL" even the link is full duplex restricts us to find max # of transmissions in only one side like a half duplex kind of!

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 

https://gateoverflow.in/1820/gate2006-44  

16 Answers

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)

0 votes
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.
0 votes

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.

 

0 votes

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.

0 votes
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).
0 votes

I think this the correct way. Please check if incorrect

0 votes
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.
0 votes

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

Answer:

Related questions

16 votes
4 answers
1
3.9k views
In which one of the following page replacement policies, Belady's anomaly may occur? FIFO Optimal LRU MRU
asked Sep 22, 2014 in Operating System Kathleen 3.9k views
56 votes
6 answers
2
12.6k views
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$
asked Apr 23, 2016 in Computer Networks jothee 12.6k views
20 votes
6 answers
3
5.3k views
$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
asked Sep 22, 2014 in Theory of Computation Kathleen 5.3k views
36 votes
6 answers
4
11.3k views
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.
asked Sep 22, 2014 in Computer Networks Kathleen 11.3k views
...