Token Bucket

Question

For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 mega byte and the maximum output rate is 20 mega bytes per second. Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second. The token bucket is currently 25% full and the machine needs to send 12 mega bytes of data. If the system is initially idle for 2 seconds, then the minimum time required to transmit the data is ____________ seconds.

Comments

Any options?

---

no it's an optionless question

---

Oh okay. I just wanted to get an idea of how far/close my answer is to the actual one. I have not encountered such type of problem before so don't know how to solve it. Is there any solution given?

---

No, but a guy in fb group said that answer is 1.175secs.

Answer 1

Is it 1.1 sec.

Comments

Please post your solution

---

Capacity of token bucket-=1 MB

Maximum output Rate=20 MBps

Input rate of token= 10 MBps

Currently 25% full

Data to be send=12 MB

Sender idle for 2 sec,it means tokens are arriving in the bucket during that period but sender is not sending any data packet.

So, After 2 sec bucket will be full.

And sender will send at 20 MBps(Peak rate) for=Capacity of bucket/(Output rate-Input rate)=1MB/(20MB-10MB)=0.1 sec.

So,in 0.1 sec we have sent 2 MB at peak rate 20 MBps.

After that token bucket will be empty and remaining data will be output at rate of 10 MBps (input rate) which will take 1 sec.

Total time to send data=1+0.1=1.1 sec.

---

correct me if I am wrong, but it says that system is idle for 2 seconds, doesn't it mean that even the host isn't getting any data?

---

Token is different from Data in token bucket.

It is like counter which we keep incrementing and when any data comes we decrement the counter by the data value sent.

so,in the idle period even host is not generating any data token bucket receive new tokens.

We start sending data after 2 sec,and at that time token bucket will be full.

---

How is the fact that the bucket is 25% full, utilized in the answer?

Answer 2

1.175 sec

Capacity = 1MB

Initially 25% filled so 0.25 MB of data will be transmitted immediately in no time. So the token bucket becomes empty now.
Now remains 12MB-0.25MB= 11.75MB data

But tokens arrive at a rate of 10MBps
So 10MB data transmitted in 1 sec
Therefore 11.75MB of data will be transmitted in 1.175 sec.

 

Answer 3

Initially token bucket has 25% capacity = 25%(1)= 0.25MB

And the host machine is idle for 2 seconds , so in 2 sec in general tokens arrive here at 10Mb/sec .so it can fill a max capacity of 20MB in 2sec , but here bucket capacity is just 1MB , so now the token bucket is full.

So , now after 2 sec host machine starts data transfer ,so it will use tokens the EQ becomes 1+10t=20t, on solving you will get t=0.1 means for 0.1 sec it will transfer data at max bandwidth of 20MB. So, in 0.1 sec 20(0.1)=2MB data transfer has been completed , remaining 10 MB has to be transferred , as the rate of token arrival is 10MB /sec , so to generate 10MB tokens one second is required, and without any due the data will be transferred as o/p rate is more than i/p rate .

So total 0.1+1=1.1 sec required to transfer the 12MB data