The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+48 votes
11.4k views

Frames of $1000$ $\text{bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $25$ $\text{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$
asked in Computer Networks by Veteran (59.7k points)
edited by | 11.4k views
–3
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 ?
+1

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 

+8

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!

+1

 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.

10 Answers

+82 votes
Best answer

Bandwidth won't be halved in full duplex.
http://superuser.com/questions/335979/does-1-gbit-s-port-in-full-duplex-mean-1-gbit-s-send-and-1-gbit-s-receive

Propagation time is given as $25\ ms$. 

Bandwidth $=10^6\ bps$. 

So, to fully utilize the channel, we must send $10^6$ bits into the channel in a second,
which will be $1000$ frames per second as each frame is $1000$ bits.

Now, since the propagation time is $25\ ms,$ to fully pack the link we need to send
at least $1000\times 25\times 10^{-3}=25$ frames.

So, we need $\lceil\log_{2} 25\rceil=5\text{ bits}.$

answered by Veteran (367k points)
edited by
0

Hemant Parihar Doesn't "maximally pack the packets" and 100% efficiency mean the same???  RTT in this example is 52. Why we are considering during propagation time of data from sender only.. Sender can send frames even after receiver starts sending acknowlegement. Why are not considering that time, when we have to maximally pack the frames.. Kindly explain 

0

Can we send data when ack is coming in reverse direction in half duplex link?

 @sushmita Do not you think if this will happen then it will become full duplex link ?

+1

Can anyone guide me where am I heading wrong?

0
Becoz transmission is possible from a to b and b to a also so  sir capacity of full duplex =2*propogation delay * bandwidth =2*25*(10^-3)*10^6 i.e = 50*10^3= 50 frames for identifying log(50)base 2 = 6 bits are required.

Please correct me if i am wrong
0
@sushmita the derivation of that formula is like

in Tt sec -> 1 pkt is transmitted, then in 1 sec -> 1/Tt packet is transmitted

Now as Arjun sir said Ack will be piggybacked, here the general formula is

Optimal win size = (Tt + RTT) * 1/ Tt (Packets per second * seconds gives total packets)

Now as sir said Tp will not be considered as they are piggybacked but now the Tt will be considered from receiver. so it becomes

optimal win size= (Tt(during sending) + Tp(traveling from S to D ) + Tt of Ack) * 1/Tt

you will get the answer.

Don't blindly follow 1+2a it is straightforward case. Many manipulation can be done in RTT.

But after reading the question it is very difficult to think given full duplex ack is not considered.
+1

I feel the question just uses the concept of bandwidth delay product. We don't need to bring in all the concepts of stop and wait or sliding window here.

bandwidth is 106bps which means per second 106 bits are put onto the channel.

So in 1ms 103 bits are transmitted on the channel.

At t=0ms a bunch of 103 bits starts to get transmitted which is finally on the channel at t=1ms.

At t=1ms 2nd bunch of 103 bits is transmitted and is finally on the channel at t=2ms and the previous 103 bits has traveled by some distance.

At t=2ms 3rd bunch of 103 bits is transmitted and is finally on the channel at t=3ms and the 2nd 103 bits has traveled by some distance and the first has traveled a further more.

This continues till t=25ms when the first bunch  just reaches the destination ( as 25ms is the propagation delay) and 25th bunch just got transmitted on the channel.

At this instant the channel is filled with 25*103bits = 25 frames.

So to represent 25 frames we need 5 bits.

 

0

MiNiPanda

Channel utilization = 2*Tp *bandwidth

                                = 50 x 103 bits

total data send =  50 x 103 bits

Frame size = 1000 bits

 No of frames we sent   =   50 x 103 bits /  1000 bits 

                                         = 50 frames

we you tell me where I'm wrong ??

0
My question is I understood your logic clearly but If in xam in the question paper they didn't mention anything about full-duplex and half-duplex....

and "6 bits" is also there in the options

then I have serious doubt in it  :3
+2

@Magma

yes right but I read in one of the previous comments that duplex by default means full duplex, also Sir took it as full duplex.

But now there might be this confusion that why aren't we considering the frames being piggybacked from the other end. They are also present in the channel. In that way a total of around 50 packets will be there at the same time in the channel. But the sequence no. wrt to End A and End B are different. A can send at most 25 frames to fill up the channel which requires 5 bits and same for the receiver. They individually require 5 bits.

 

+1

Oh yes  MiNiPanda :p

great

+27 votes

BW both the sides will be 106​ ​bps for a full-duplex channel/wire/link.

We are actually only considering transit to one side while transmission of the packets to fully pack them in the link(106 bps). So, instead of the general approach of taking 1+2a packets, here we are taking 1+a packets since we are only considering the time of 1 Tp, we need to keep the link full for 1 Tp.

So, Min. no. of packets required = 1 + a = 1 + 25/1 = 26 packets.

Min. no. of bits required = log2​(26) = 5 bits.

So, 5 bits are enough to pack one side of the link while the frames are in transit.

Actually, both the hosts will send data packets and acknowledgements, but for both the sides, 5 bits are enough individually to fully pack 106​ bits from both the sides(full-duplex). Here, to keep things simple, I have only discussed considering one sender and one receiver only.  

For optimal case, when we also consider the time of the acknowledgement coming back, that time also packets can be kept on transmitting in the channel,

So, Min. no. of packets required = 1 + 2a = 1 + 2*25/1 = 51 (doesn't matter if the ack. is piggybacked or not).

and Min. no. of bits req = log2​(51) = 6 if we want this kind of link utilization.

Again, here also for simplicity, only considered one sender and one receiver.

But in reality both the hosts will act as source and destination simultaneously. Obviously, the acknowledgements will be piggybacked in such a practical case.

answered by Active (3.3k points)
edited by
+15 votes

When the link is duplex do we have to take Bandwidth  = B/2 ?

My solution:

answered by Boss (13.6k points)
reshown by
+4
I have a doubt in your approach.Why did you half the given bandwidth?
As mentioned in solution why should we half the given bandwidth when it is duplex?

Thank you in advance.
0
No , i case of duplex link bandwidth wont be divided by 2
+8 votes

Answer (D).

Given, propagation time =25 ms.

Time required to transmit 1 frame = 1000 bits (frame size)/ 10^6 bps(bandwidth) = 1 ms

To fully utilize the channel, we need to transmit frames for propagation time(25 ms), 25 frames.

therefore, minimum no. of bits required for numbering 25 frames is = log2 (25) = 5 bits.

answered by Junior (735 points)
edited by
0
I just have 1 question if it would have not been given that the channel is duplex. Then

"To fully utilize the channel, we need to transmit frames for propagation time(25 ms)"

wil change to

"To fully utilize the channel, we need to transmit frames for round trip time which is 2*propagation time=(50ms) ??
+4 votes

Duplex simply means both sender and receiver can send and receive the signals which is bydefault as we know.

Tx = 1ms (1 frame data put on cable) 

Tp = 25ms (25 frame data can be put on cable in this time if we fully utilize the link).

Total time : 1 + 25 = 26 ms (from frist bit of of first frame put on cable to last bit of frame reached to receiver)

So to fully utilize the link we must use the link for 26 ms (26 frames need to transmit)

frames numbered as 0,1,2,3,...25 thus we need 26 different sequence numbers

therefore bits rewuired for sequence number = ceil(log 26) = 5

answered by Active (2k points)
+2 votes

For Half Duplex, Capacity of the channel = BW * Tp
So we get capacity = $10^6$ b/s * 25 * 10 ^ -3 s
                               = 25 * $10^3 bits$

so a channel can contain 25 * $10^3 bits$ but we are sending only frames of 1000 bits
Therefore, the total no. of frames we are sending with its full channel capacity = 25 * 1000/1000 = 25 frames.
For this much frames the seq.numbers nedded are 25.
And Seq.no.bits required are $Ceil(\log_{2}25)$ = 5 bits

answered by Junior (643 points)
edited by
+2 votes

5 bits

answered by Boss (24.2k points)
0
according to me , the question doesnot asking about how many maximum packet we could sent it is asking how many maximum packet we can send while transit(meaning during transmission only) and significance of giving duplex here is together ack also came we can get data parallely
0
why RTT = PT in full duplex?
+1 vote
Propagation time is given as 25 ms.

Bandwidth = 106 bps.

So, to fully utilize the channel, we must send 106 bits into the channel in a second, which will be 1000 frames per second as each frame is 1000 bits. Now, since the propagation time is 25 ms, to fully pack the link we need to send at least 1000 * 25 * 10-3 = 25 frames. Since, to represent 25 frames we need 25 distinct index numbers. Thus, minimum no. of bits required to do this will be 5 (2^5=32) as 4 will not be enough (2^4=16, not enough to represent 25 distinct no.)
answered by
0
@Arjun  Sir ,why we are not considering the other tp for acknowledgement. in this time, we can sent more 25 packets.
+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)

answered by (367 points)
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.
answered ago by Junior (511 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,962 questions
49,517 answers
162,468 comments
65,759 users