GATE IT 2006 | Question: 67

Question

A link of capacity $100$ $\text{Mbps}$ is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is $10$ $\text{Mbps}$, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of on-time to off-time, is $1: 2$. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is $S1$. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is $S2$. The values of $S1$ and $S2$ are, respectively,

• A. $10$ $\text{and}$ $30$
• B. $12$ $\text{and}$ $25$
• C. $5$ $\text{and}$ $33$
• D. $15$ $\text{and}$ $22$

Comments

@Tuhin Dutta ji what is not clear to you @Vicky Bajoria ji has already given very good explanation.

---

What topic is this que from ?

---

This question is based on Statistical Multiplexing / Traffic Engineering / On-Off Traffic Sources, 

which belonged to the older Computer Networks syllabus.
 

Out of syllabus now.

Answer 1

Since there is no buffer and constraint given is there should not be any data lost, and no wastage of capacity as well.

Since data should not be lost, we calculate for the extreme case when all sources are on (that is transmitting).

$10\ Mbps\times \text{n-station} \leqslant 100 Mbps$

$\implies \text{n-station}= 10.$

In the next part of the question it is given that the link is provided with large buffer and we are asked to find out the maximum number of stations.

For this we'll calculate the expected value of bandwidth usage (if more data comes we store in buffer and due to expectation, the buffer will be emptied soon or in other words buffer space will never run out):

$E =\dfrac{1}{3}\times 10 +\dfrac{1}{3}\times 10+\ldots \text{n-station times}\leqslant 100\ Mbps$
[ total time is $(1+2)=3$ then on time is $1$ so $\dfrac{1}{3}$ of BW]

$\Rightarrow \dfrac{1}{3}\times 10\times \text{n-station}\leqslant 100\ Mbps$

$\Rightarrow \text{n-station} =30$

So, option (A) is answer.

Comments

HitechGa think of it like this:

the given link is time multiplexed between those sources. Now using this approach u will see that the bandwidth is being divided between sources and there will be no collision too.

---

in part one ans. there will be time when capacity won't be fully utilized(ex. 9 are on and 1 is off then only 90mbps is being used) then how can it be the ans?(edit: i have now assumed that by "capacity is not wasted" they mean that "there is some point in time when it's fully utilized" and not that "it's fully utilized for all the time" cause full capacity utilization isnt possible without the sources being synchronized and sources r synchronized only in part two of the question and not one)

correct me if i am wrong

---

why we haven't applied duty cycle for S1?

Answer 2

Part 1(for S1)

Suppose there are three slot 1,2 and 3

Every station can send traffic only during one slot and in remaining two slots it will not send traffic(bcz on off duty cycle is 1:2)

Here we have to find minimum number of station that can generate traffic so that we have maximum utilization with no loss of data.

Any station can generate traffic during any slot But there is no buffer it means the traffic generated by stations during slot 1 will also be on link during slot2 and slot 3 also traffic generated by stations during slot 2 will also be on link during slot 3

But we have to find out minimum number of stations which will be possible when all stations generate traffic during same slot.

Traffic generated by n stations= Bandwidth

10*n=100

So n=10 stations

Alternate method for part 1(for S1)

Let n1,n2 and n3 be the no of stations that generate traffic during slot 1, slot 2 and slot 3 respectively.

Any station can generate traffic during any slot But there is no buffer it means the traffic generated by stations during slot 1 will also be on link during slot 2 and slot 3 also traffic generated by stations during slot 2 will also be on link during slot 3.

Traffic generated during slot 1 =n₁*10

Traffic generated during slot 2 =n₂*10

Total Traffic during slot 3 =n₃*10 + n₁*10 + n₂*10.

Total traffic=100 Mbps

n₃*10 + n₁*10 + n₂*10 =100

n₃ + n₁ + n₂  =10

Part 2(For S2)

Suppose there are three slot 1,2 and 3

Every station can send traffic only during one slot and in remaining two slots it will not send traffic(bcz on off duty cycle is 1:2)

The stations who generate traffic during slot 1 their data during slot 2 and and during slot 3 can be stored in buffer.

The stations who generate traffic during slot 2 their data during slot 3 can be stored in buffer.

So lets's find how many maximum   stations can send data during slot 1 so that we will have maximum utilization with no loss of data.

Let n station generate traffic during slot 1 as each station generate 10 Mbps.

So n station generate 10*n Mbps it must be equal to.100Mbps (for maximum utilization and no loss of data)

10n=100

So n=10 during slot 1.

It is also true for other slots also.

So Total Stations=10(slot1)+10(slot2)+10(slot3)=30.

Correct me if you think my approach is wrong.

Comments

@akb 

you have just assumed 3 slots right ? any reason behind it ? if not

So Total Stations=10(slot1)+10(slot2)+10(slot3)=30.

then if u assume 4 slots answer will be 40

if 5 then 50 and so on 

---

"The duty cycle, which is the ratio of on-time to off-time, is 1: 2"
Because of this I have assumed 3 slots(1in which it will be on and in another two it will be off)

---

@akb

if on off duty part was not ther in the question. Just assuming that always traffic is 10Mbps

then the minimum would be 10 only....right ?

what would the max be.....i think any number .......correct me

Answer 3

I will try to explain the S2 part only in the simplest way possible!

Given that Duty Cycle =ontime/offtime =½

=> on/off=1/2
=>  on=1/2 times of off

means if a station is off for 2 times then it will be on for half of (2 times)= 1 time

So we can say that in a time duration of 3 slots for one slot station will be on and the remaining two slots the station will be off!

We have been told that we have a Buffer of infinite Capacity!

Also we know that link has a max capacity of 100Mbps!

In computer science we always assume the worst case!

Since our link has a max capacity of 100Mbps so at max during a particular time instant(say t=0) all the 10 stations of group1 got on and now all started transmitting at same time at there max capacity of 10Mbps each,So since our link capacity is 100Mbps so Group1 can contain at max 10 stations.

Now assume the data which group1 stations produced got stored in the buffer!

Now at the end of slot1 ,Group1 will become silent for slo2,slot3{they will not produce any data till end of Slot3} Since as i mentioned above bcoz of that duty cycle.

Now Suppose Group2 started transmitting ,similarly group2 will also contain at max 10 stations as i already mentioned the reason above.Now in the slot2 when group2 stations were transmitting ,assume again the data of group2 got stored in the buffer again.
Now group 2 will remain silent for the next two time slots.{slot3,4}

Now Suppose Group3 started transmitting ,similarly group3 will also contain at max 10 stations as i already mentioned the reason above.Now in the slot3 when group3 stations were transmitting ,assume again the data of group3 got stored in the buffer again.
Now group3 will remain silent for the next two time slots.{slot4,5}

So till now we got 30 stations,all the data has been stored onto the buffer till this point.

Now at this point{end of slot3} if you assume (just a hypothetical scenario) one more station (say of group4),now this would create a problem bcoz now at the end of slot3 the stations of group1 will become active and since group1 already contains 10 members so no more extra stations can be afforded,bcoz then we will be exceeding the limit of 10stations{10*10Mbps=100Mbps(the max cap of out link)}
As the moment group1 stations gets activated they will again try to send the data{and in worst case all the 10 Stations of group1 can try to send the data at 10Mbps/station)

So even if we have a infinite size buffer, we can afford a max of 30 Stations in whatever worstcase we assume,as stated in the question that no data loss should occur and also capacity must not exceed!

Comments

Nice explanation!

---

Nicely Explained !

Answer 4

Here is a slightly different approach to the problem.

Here think of the pipes bringing water to the backet as the sources, and each source can be on or off. When they are on, they are bringing in data (water) with a rate of 10Mbps, and when they are closed there won't be any data(water) coming out of them. Also, each the duty cycle ratio is given as 1:2. Also let's assume there is a hole at the bottom of the bucket which allows data to flow out at a maximum rate of 100Mbps.

Case-1: There is no buffer

This means the storage capacity of the bucket is 0. Means whatever water is being added to the bucket needs to go out at the same time as the bucket can't store any data inside it. So if data is coming at a rate that is higher than what the bucket can dispose off, the data will start getting spilled(Data Loss). 

Let's assume that there are x pipes. In the worst case, all the x pipes will be on simultaneously and hence all of them will be adding data at a rate of 10*x Mbps. In the worst case, that should be less than or equal to 100Mbps.

Hence 10*x = 100
=> x=10.

 

 

Case-2: There is a buffer that is large enough.

This means that the data being brought in doesn't need to be discarded immediately and the bucket can store some data. In such case,

                If we consider the span of a second, the pipes will be on for 1/3 of  a second, and for that time they will be bringing in data with a rate of 10Mbps. So, effectively, in every 1 second, a pipe is bringing 10/3Mb into the container.

In this case, we don't care about the overflow, but we need to ensure that 100Mbps outlet can be utilized properly.

 

So, if there are x pipes , in this case, total generated per second must be equal to the outlet rate. Hence,

(10/3)*x = 100/3

=>x = 30.

 

Any suggestions are cross questions are appreciated
 

Comments

even better explaination 😊

---

(10/3)*x = 100/3
this should be like (10/3)*x=100 right?? edit

Answer 5

Bandwidth is given as = 100 Mbps.

 

for calculating S1 : We have no buffer. Buffer role is to have all the bits that are currently in the queue and are needed to be sent but because of the bandwidth utilization is complete the bits can’t be send as of right now.

 Since no buffer is there and each source have a data transfer rate = 10 Mbps, a total of 10 sources can send the data without any hassle.

 

for calculating S2 : For this case we are given we will need a buffer to store outstanding bits in the queue.

But how many such bits can be stored ?

We can calculate it by using the duty cycle ratio i.e 1:2

meaning if 1 source is on than 2 sources are off (or buffered up)

 

so, from S1 we had 10 sources at max we can send. But now since there is a buffer available we can queue up sources.

And from duty cycle,

for 1 source On → 2 sources need to be off

therefore for 10 sources on → 20 sources need to be off

and the total equals 10 on and 20 off = 30 sources.

 

therefore a minimum of 10 sources and a max of 30 sources can send data is the answer.

Answer 6

First, we have to find a minimum no of Sources so, We have 100mbs link capacity, and for having 10mbps for each source, no of sources should be 10 if there is no buffer provided so no data can be stored,

In the second situation, we have buffers, so suppose a source is transmitting and the link is full, then it can be stored in a buffer and can be transmitted later. As the duty cycle ratio is 1:2 and for not wasting any link’s bandwidth, the no of sources should be 30. according to duty cycle if we consider 3 sources per 10mbps then , one of the source will always be transmitting in any situation.