The Gateway to Computer Science Excellence
+33 votes
3.9k views

Let us consider a statistical time division multiplexing of packets. The number of sources is $10$. In a time unit, a source transmits a packet of $1000$ bits. The number of sources sending data for the first $20$ time units is $6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5$ respectively. The output capacity of multiplexer is $5000$ bits per time unit. Then the average number of backlogged of packets per time unit during the given period is

  1. $5$
  2. $4.45$
  3. $3.45$
  4. $0$
in Computer Networks by Boss (16.3k points)
edited by | 3.9k views
+1
Is this in syllabus?
+1
Yes! it is a part of MAC sublayer
+2

TDMA is a  channel-access scheme is based on a multiplexing method, that allows several data streams or signals to share the same communication channel or physical medium.

 Multiplexing is provided by the physical layer .

+1
some necessary information before solving this question:

. In case of tdm we create a combine frame which will contain time slot from each data source and we send this combined frame to the destination but here the problem is that if some source is not sending the data then also we have to reserve slots for it. Due to which bandwidth required is very high we can resolve this issue in statistical tdm here any data can be send in the slot time and there is no empty space also it may be required to send some data in next frame so backlog It in next frame.
0
The capacity of single communication line that is used to carry the various transmission should be greater than the total speed of input lines in synchronous time division multiplexing. Can someone explain why??
0
Sir this topic is in syllabus or not?
0

this is not in syllabus

0
Can you tell us what all things are not in the syllabus of CN?

2 Answers

+54 votes
Best answer

Answer is B.

Here, we can send at max $5$ packets per Time unit $\dfrac{5000}{1000}$.

So, whatever which is not sent is backlog.

So,

First Time Unit $\Rightarrow 6,$

Backlog in First time unit $\Rightarrow 6-5\Rightarrow 1$ This one gets added to next Time units load

Second time unit $\Rightarrow 9 + 1$ (One from Previous Time Unit)

Backlog in Second time Unit $=10-5\Rightarrow 5$ (This one gets added to next Time Units load.)

Total Backlog this way  $=1+5+3+5+2+0+0+0+0+1+0+5
+7+7+10+8+9+6+10+10=89$

Avg Backlog $=\dfrac{89}{20}=4.45$

The average number of backlogged of packets per time unit during the given period is $4.45$.

by Boss (41.5k points)
edited by
0
Option B rt?
0
How do you get 89? Can you please provide few more steps of your calculation?
+1
can u provide some resource, from where u got this concept ? @Akash kanase ?
0
Please help me how @Akash has calculated backlog 89?

Is @Rojarshi Ans is correct?
0

@Brij Mohan Gupta 

calculated backlog =  6+9+7+6+10+7+8+6+9 = 68

so Average number of backlogged packets per time unit is 68 / 20 = 3.4

0
Thanks @Bikram
+3

@Bikram sir

Backlog = 1+5+3+5+2+0+0+0+0+1+0+5+7+7+10+8+9+6+10+10=89

Avg Backlog=89/20=4.45 (Option b)

Can you point out why this is wrong? I have followed the above approach as mentioned by Akash sir.

0
@VS

Both answer are correct, another answer have good description, that's why i selected that .

Though i edit this answer, previously it was wrong ..now i edit and make it correct.
0
@VS

Total Backlogs  = ( 6+9+7+6+10+7+8+6+9) = 68

you check once again please .. you can see another answer to understand!
+5
@Bikram sir
Now I have a serious confusion here.
How to calculate the backlogs?

Approach 1 : if input =6 then backlog=6 (since nothing is transmitted here)

Approach 2: If input=6 then backlog=1( 6-5,since 5 packets are transmitted and the remaining 1 packet is added as the load for next input i.e. next input= 9+1=10)

Using first approach Total backlogs are 68
Using Second =89.

Stallings uses second approach
http://spinlab.wpi.edu/courses/ece2305_2014/statistical_multiplexing_stallings.pdf
Page 4
0

VS 

yes, you are correct , this answer is correct according to a standard book ( Stallings ).

Since this approach is followed by a book it should be followed by us to calculate avg number of backlogs.

And this question is directly given in stallings too ..

While in another approach by @rajarshi , i did not found any standard resource to follow it..hence i selected this answer.

0
@Bikram sir

Thanks a lot :)
+6

As per William Stalling 
“We have said that the data rate of the output of a statistical multiplexer is less than the sum of the data rates of the inputs. This is allowable because it is anticipated that the average amount of input is less than the capacity of the multiplexed line. The difficulty with this approach is that, while the average aggregate input may be less than the multiplexed line capacity, there may be peak periods when the input exceeds capacity. The solution to this problem is to include a buffer in the multiplexer to hold temporary excess input


“When the input exceeds the output, backlog develops that must be buffered.” 

Source: William Stalling 8th Edition page number 260 & 261

B is correct 

0
+1

@Arjun @Bikram @srestha @Dixith Reddy @Akash Kanase @Milicevic3306 @Ishrat Jahan @Radha mohan

How exactly TDM works for Access Control? I have read that, it is similar to Round-Robin method where every Station gets a slot to transmit a data packet. Is it really, we do multiplexing (i.e. take data packets from each station (which is ready to transmit) into a single frame and sent over the channel in a single time slot).

Correct me, if i am wrong.

+11 votes
Answer: C

In statistical TDM, the bandwidth is divided into slots each for a source if the source requires. There is no dedicated slot for each source in the bandwidth.
STDM does not reserve a time slot for each terminal, rather it assigns a slot when the terminal is requiring data to be sent or received.

Multiplexer bandwidth = 5000bits = 5 packets can be send in a time unit.

If x number of source want to transmit in a particular time unit then MBW will be divided among x sources. Therefore,

if [x <= 5] {
    all x sources can successfully transmit their 1000bits because [x*1000]<=[5000]
} else {
    all sources cannot transmit their complete 1000 bits and there will be backlog of x (incompletely transmitted) packets.
}

So,

6 [Backlog], 9 [Backlog], 3 [-], 7 [Backlog], 2 [-], 2 [-], 2 [-], 3 [-], 4 [-], 6 [Backlog], 1 [-], 10 [Backlog], 7 [Backlog], 5 [-], 8 [Backlog], 3 [-], 6 [Backlog], 2 [-], 9 [Backlog], 5 [-]

Average number of backlogged packets per time unit during the given period is = [6+9+7+6+10+7+8+6+9]/20 = 3.4
by Boss (33.8k points)
+2
Should not be backlog of x-5 packets ?
0
Arjun Sir, who is correct?
0
Please clarify @Arjun sir
0
@arjun sir :  Here since all station can send simultenously but multiplexer output capacity is 5000 bits per second  so for just first 5 sources if they transmit the packet wont be blogged , but if anyone after that does than all the packet would be blogged ryt ?

hence we have the above calc right ?
+5

The backlog is calculated as the difference between the available packets and those that can be transmitted in unit time. Here (Input - Output).

0
From which book this image is taken?? Can u please share the book if available in pdf
0

anchitjindal07  

This is  William Stallings book, see this  http://spinlab.wpi.edu/courses/ece2305_2014/statistical_multiplexing_stallings.pdf

above snap is taken from this link, page 4.

0

Bikram  Sir ...Please tell me if i m wrong..

In this question we don't know that out of the 10 sources..S1 S2 S3 .....S10....which are transmitting in which time slot.

so if in first time slot (6 sources) say S1 S5 S9 S2 S3 S7 are transmitting  and due to condition of 5000 b suppose S7 is Backlogged  

.it is possible that in the next time slot (9 sources) S7 may never come.

Hence we should not add the backlogged packet for next time slot ...and ans would be 3.45.

Thanks :)

0

gari  

is there any standard source to mention this technique ?

you can see that Stallings snap where backlog concept is discussed ..

+1
No sir i haven't found any source for this technique ....i just thought about it......because in the question it's not given that in a particular time slot which are the sources that are transmitting....

I feel my interpretation is somewhat correct..but i haven't found any proof for it . :)
0

@gari

No, i think your assumption is not correct.

yes it is not given  which source is transmitting in which particular time slot . But without this information we can solve this problem too..

How you assume that " it is possible that in the next time slot (9 sources) S7 may never come. " ?

This is mention in Stallings  " there may be peak periods when the input exceeds capacity. The solution to this problem is to include a buffer in the multiplexer to hold temporary excess input  "

so it means " When the input exceeds the output, the backlog which are develops that must be buffered.” so it need to use buffer to hold S7 in your example .

About source :

only 2 books distinguish between normal TDM and statistical TDM, stalling and forouzan . And forouzan didn't mention anything about backlog .

What Stallings says is to use buffer when exceeds so we must follow it as it is mention in a standard source. We should not make any assumption about which we are not sure , is not it ?

0

Thanks a lot @ Bikram sir for your efforts :) yes sir u are correct .....we should not make any assumptions about this and follow standard book.

sir do we know the official answer for this question ?

+1
@gari

This is Gate 2007 paper and that time no official answer key posted .  And this question also match with that Stallings link, just check yourself the value given in question and value given in that snap , answer is B and it is correct.
0
Thanks sir :)

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
50,647 questions
56,508 answers
195,519 comments
100,952 users