GATE CSE 2016 Set 1 | Question: 54

Question

For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to sustain output at a rate of $10$ $\text{megabytes}$ per $\text{second}$. The token bucket is currently full and the machine needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.

Comments

Sir in this situation

10t + 1 = 12

And t = 1.1 sec

Confusion::- at t =1.1 sec the capacity of token bucket is 12mb

And question is asking about data transmission time  from bucket not the capacity. I think it is slightly greater than 1.1 sec

---

Fact is in this problem Ans is not depending on Output rate at all
Only depends on Token rate and size of Bucket

---

My Solution  (please check and correct me if  i am wrong)

https://gateoverflow.in/39720/gate-cse-2016-set-1-question-54?show=420464#a420464

Good Explanation by @Pranavpurkar

https://gateoverflow.in/39720/gate-cse-2016-set-1-question-54?show=374049#c374049

Answer 1

Initially token Bucket full  and has 1 MB of tokens

$Max Rate = (capacity + tokenRate * time) /time$

$20 MBps = (1 MB + 10MBps *t)/t$

$\therefore t = 0.1s$

 

In this 0.1 sec $20 MBps*0.1s = 2 MB$ data is sent

(1MB already available tokens + 1 MB generated in 0.1s)

 

 Now remaining 10 MB data will be sent at token generation rate.  

Why?

because there are no available tokens in the bucket at 0.1s.

so to generate 10 MB of tokens 1 sec is needed ( Token generation rate given)

$\therefore total = 1s+0.1s = 1.1s$

 

Answer 2

Can’t it be like this?

Capacity= 1MB , 

Max o/p rate = 20MBps ,

incoming rate = 10MBps

initially the bucket is full (i.e 1MB)

and it will get out at the Max o/p rate  so ,

20MB →  1s

1MB → (1/20)s   i.e  0.05 s

Now, the remaining data is  (12 – 1) MB = 11 MB

this data will be out at the incoming rate which is 10MBps  so,

10MB → 1s

1MB → (1/10)s  i.e  0.1 s 

Then  11MB → 11* (0.1)s  i.e  1.1 s

Thus the total time to transfer 12MB data is  =   (1.1 + 0.05) s   =   1.15 s

which is in the range from  1.10 to 1.19 

 

Answer 3

we know that input flow == out flow in bucket algo which is C+PS=MS , but here we will only calculate input flow which is C+PS  for s seconds and we will equate it to data size we want to send …because see initial 1 mb will go very fast in very small time(not even in seconds) and here everything is in seconds ...and after 1st mb of data  data will move at input rate

note: we want minimum time i.e., (jis speed se aaya usi speed se chla jae to minimum , isse zada b lg skta hai but ye minimum h) which means its fastest we can send data in such a scenario

C+PS==M

C = CAPACITY =1MB

P= TOKEN RATE = 10MBPS

S= BURSTY TRAFFIC COMING FOR S SECONDS 

M = message size = 12MB

c+ps=m

1+10s=12

10s=11

s=1.1sec(approx)

 

Answer 4

The question is about the token bucket algorithm, which is a method used for network congestion control. In this case, the host machine has a token bucket with a capacity of 1 megabyte. The maximum output rate (data transmission rate) of the machine is 20 megabytes per second. Tokens are added to the bucket at a rate that can sustain an output of 10 megabytes per second. The bucket is currently full and there are 12 megabytes of data that need to be sent.

The token bucket algorithm works by adding tokens to the bucket at a fixed rate. The bucket has a certain capacity and can't hold more tokens than its capacity. When a packet (or in this case a portion of the data) needs to be sent, it can be sent only if there are enough tokens in the bucket to "pay" for it. The tokens are then removed from the bucket.

In this scenario, the token bucket is full (1 MB), and the machine can send data at a maximum rate of 20 MB/s. So, initially, the machine can send data at this maximum rate until the token bucket is empty.

The rate at which the token bucket is emptied is the difference between the maximum output rate and the token arrival rate, which is (20-10) MBps = 10 MBps. The time taken to empty the token bucket of 1 MB at this rate is 1/10 = 0.1 seconds.

In this 0.1 seconds, the amount of data sent is 0.1 * 20 = 2 MB. This is because the machine is sending data at its maximum output rate during this time.

After the token bucket is emptied, the machine can only send data at the rate of token arrival, which is 10 MBps. The remaining data to be sent is (12-2) = 10 MB.

The time to send this remaining data is 10/10 = 1 second.

So, the total time taken to send all 12 MB of data is 0.1 + 1 = 1.1 seconds