edited by
41,696 views
100 votes
100 votes
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}$.
edited by

21 Answers

Best answer
131 votes
131 votes

Initially token bucket is full.

 Rate at which it is emptying is $(20-10)$ MBps.

Time taken to empty token bucket of $1$ MB is $\frac{1}{10}$  i.e  $0.1$ sec.

Data send in this time is $0.1*20=2$ MB (rate at which bucket is emptying is different from rate at which data is send) .

Data left to send is $12-2=10$ MB .

Now bucket is empty and rate of token arriving is less than that of going out so effective data speed will be $10$MBps.

Time to send remaining $10$MB will be $1$ sec. So total time is $1+0.1$=$1.1 $sec

edited by
76 votes
76 votes

Short answer

The total time to transmit data in Token Bucket algorithm is the sum of two times -

  1. T1 = Time to transmit data with max. transmission rate as long as the bucket is not empty.
  2. T2 = Time to transmit the remaining data after the bucket is empty. During this time, data can only be sent at the rate at which the tokens are generated.

[If size of data is less than or equal to the bucket capacity then all data will be transmitted before the bucket becomes empty. Therefore, only the first component gives the answer in this case.]

Calculating T1 -
This is simple, but can be a bit tricky for some people like me. Since, the bucket's capacity is 1 MB, and the effective rate of token removal is 20 - 10 = 10 MBps, therefore the bucket will be emptied in 1 MB /10 MBps = 0.1 s. But, this does not mean that 1 MB data is transmitted in 0.1 s. During this time, data is transmitted at the rate of 20 MBps, not at the effective rate of 10 MBps. So, data sent is 20 MBps x 0.1 s = 2 MB.

Here, because of the relative nature of the formula used to calculate the time to empty the bucket, some people get confused. To clear the confusion, consider this simple problem.
Q. Two cars A and B start moving at the same time in the same direction at the speeds of 20 kmph and 10 kmph respectively. If B has a head start of 1 km, then what is the distance traveled by A to overtake B.
Ans:- Since both cars start moving at the same time, A must travel the same amount of time as B. So, the answer is simply the product of this time and A's speed, i.e., 20 kmph.
Now, one way to calculate this time is to use the concept of relative speeds. If B is put to rest (i.e, B's speed is decreased by 10 kmph), then A's speed also decreases by the same amount, thus resulting in a relative speed of 20 - 10 = 10 kmph. Since, B is at rest, therefore to overtake B, A only needs to cover the head start distance of 1 km. Therefore, time taken by A to overtake B = 1 km / 10 kmph = 0.1 hr. Clearly, this does not mean that A travels only 1 km. Since, A's actual speed is 20 kmph, therefore distance covered by A = 20 kmph x 0.1 hr = 2 km.

Calculating T2 -
This is straightforward. Since, the remaining data is 12 - 2 = 10 MB, and the rate of transmission of this data is equal to the rate of token arrival, i.e., 10 MBps, therefore time taken to transmit 10 MB = 10 MB / 10 MBps = 1 s.

Therefore, total time = T1 + T2 = 0.1 s + 1 s = 1.1 s

Long Answer

The concept is simple -

  • Tokens are produced by the system at a fixed rate, and stored in a bucket having fixed capacity.
  • Whenever a packet is transmitted, some tokens are removed from the bucket. How many are removed ? It depends. If all packets are of same size, then one token per packet is OK. Otherwise, one token per byte is deleted. By default, it is one token per byte.
  • Transmission can be performed ONLY IF tokens are available in the bucket. If bucket is empty, then packets are queued until sufficient tokens are available.

the rate at which tokens are removed from the bucket is ALWAYS equal to the rate at which the packets are transmitted by the system.

Now comes the central question. "Why are the tokens STORED in a bucket ?" To understand this, consider what would happen if we don't store them !! If tokens are not stored, then the system will always transmit the packets at the same rate at which the tokens are produced. And, this is nothing but the "Leaky Bucket" algorithm, where the packet transmission rate is always fixed.

The "Token Bucket" algorithm with a zero bucket capacity is nothing but the "Leaky Bucket" algorithm.

If the tokens are stored, however, then the system is not limited to the token generation/arrival rate, and can transmit the packets at the maximum transmission rate. The max. transmission rate is generally greater than the token arrival rate.

As long as the bucket contains tokens, they can be removed at the max. possible rate, and so, the system transmits the data at max. transmission rate. But, since the rate of token removal is greater than the rate of token arrival, the bucket eventually becomes empty. After that, the tokens can be removed only at the rate at which they are produced. Therefore, when the bucket becomes empty, the system transmits data at the rate of token arrival.

On pg. no. 409 of the book "Computer Networks" (5th edition) by Tanenbaum, it is clearly stated that -

The host can send full throttle at the maximum transmission rate for a short while until it has drained the bucket...

When it (no. of tokens in the bucket) reaches zero, new packets can be sent only at the rate at which the buffer is filling; there can be no more bursts until the bucket has recovered...

edited by
30 votes
30 votes

Reffer: Token-Bucket .

  • Token bucket has a capacity of 1 mega byte (maximum capacity $C$ )

Here  one byte is considered as one token

$\Rightarrow C=1 \text{M tokens}$

  • output rate is 20 mega bytes per second ($M=20\text{MBps}$)
  • Tokens arrive at a rate to sustain output at a rate of 10 mega bytes per second

$20-R=10$

$\Rightarrow$ Input Rate  $R=10\text{MBps}$

Unlike Leaky Bucket , idle hosts can capture and save up $ c \leq C $ tokens in order to send larger bursts later.

When we begin transfer  the tokens present in token buckt is transmitted at once to the network

ie. if initally capacity of token bucket is 'c'  then c tokens will be instantly be present in the network.

Time to Empty the token bucket

$c$: is the inital capacity of token bucket
$R$: every sec we are getting R tokens
$M$ : evey seconds M tokens are produced


INPUT FLOW : Then the number of packets that are ready to  enter the network during a time interval 't' is $c+Rt$

OUTPUT FLOW : Then the number of packets that are ready to  enter the network during a time interval 't' is $Mt$

INPUT FLOW = OUTPUT FLOW

$\Rightarrow c+Rt = Mt$

$\begin{align*} t&= \frac{c}{M-R} \\ &=\frac{1}{20-10} \\ &=0.1\text{sec} \end{align*}$

  • Given that Token bucket is full ($c=C$)

Now , We have got  two cases  

  • To transfer 1M tokens , Will it be instantly  with t=0
  • Or to transfer 1M tokens , we take 10/ 20-10 = 0.1sec ?

To transfer 1M  (inital token) tokens , Will it be instantly  with t=0

Consider the equation

INPUTFLOW = c+Rt


This means that 
" c tokens (initally contained in token bucket  ) are transmitted without any delays "

Unlike Leaky bucket ,  token buckets can keep on reserving token if the sender is idle .Once it is ready to send the packets . Packets will take the token and will be transmitted to the network. $\Rightarrow c $ And then we are adding the $R$ tokens produced in $'t'$ time to finnaly get the INPUTFLOW

$\Rightarrow 1 \text{MB}$ is transmitted instantly . Now we are left with 11 MB to transmit

To trnasfer remaining 11 MB

at $t=0$ we begin transmitting 11 MB data.

at $t=0.1$sec :  1MB  (1 MB transfered)

at $t=0.2$sec :  1MB  (2 MB transfered)

..
..

at $t=1.1$ sec : 1MB (11 MB transfered )

Therefore to transfer 12MB it takes 1.1sec + 0 sec = 1.1 sec

Transfer 1M (inital token) tokens , we take  = 0.1sec

( if it take 0.1 sec for 1MB i could argue that it will take 1.2ssec for 12MB )

then during 0.1sec .   01 *10MBps = 1M tokens are fulled up .

t=0s : begin to transfer  12 MB data.

t=0.1s : 1MB

t=0.2s : 1MB  (2 MB transfered)

t=0.3s : 1MB  (3 MB transfered)
..
..

t=1.2s : 1MB  (12 MB transfered)

Therefore to transfer 12MB it takes 1.2sec



Question does clearly mention about this part . Hence it is common practice to always follw the best case .
Therefore the answer would be 1.1 sec
 


Reference

edited by
13 votes
13 votes

Tokens arrive at 10MB/sec, i.e 1 MB in 0.10 sec
Tokens output at 20MB/sec, i.e 1 MB in 0.05 sec

Initially we have 1 MB in token bucket. Lets see what happens using timeline.
Please pay attention. This may seem confusing, understand what happens in between 0 - 0.1 sec

T=0.00,  Bucket contains 1 MB, Output = 0 MB
T=0.05,  Bucket contains 0.5 MB, Output = 1 MB
Since initially bucket is full with 1MB, it will take 0.05 sec to empty it, but during that 0.05 sec we will also get an input of 0.5 MB
T=0.10,  Bucket contains 0.5 MB, Output = 2 MB
At 0.1 sec, the previous 0.5 MB present in bucket + new 0.5 MB data will output, making a total output of 2 MB.
Here onwards everything is streamlined, we will output only when we get data, i.e evey 0.1 sec
T=0.15,  Bucket = 0.5 MB, Output = 2.5 MB
​​​​​​​T=0.20,  Bucket = 0.5 MB, Output = 3 MB

T=0.25,  Bucket = 0.5 MB, Output = 3.5 MB
​​​​​​​T=0.30,  Bucket = 0.5 MB, Output = 4 MB

T=0.35,  Bucket = 0.5 MB, Output = 4.5 MB
​​​​​​​T=0.40,  Bucket = 0.5 MB, Output = 5 MB

T=0.45,  Bucket = 0.5 MB, Output = 5.5 MB
​​​​​​​T=0.50,  Bucket = 0.5 MB, Output = 6 MB

T=0.55,  Bucket = 0.5 MB, Output = 6.5 MB
​​​​​​​T=0.60,  Bucket = 0.5 MB, Output = 7 MB

T=0.65,  Bucket = 0.5 MB, Output = 7.5 MB
​​​​​​​T=0.70,  Bucket = 0.5 MB, Output = 8 MB

T=0.75,  Bucket = 0.5 MB, Output = 8.5 MB
​​​​​​​T=0.80,  Bucket = 0.5 MB, Output = 9 MB

T=0.85,  Bucket = 0.5 MB, Output = 9.5 MB
​​​​​​​T=0.90,  Bucket = 0.5 MB, Output = 10 MB

T=0.95,  Bucket = 0.5 MB, Output = 10.5 MB
​​​​​​​T=1.00,  Bucket = 0.5 MB, Output = 11 MB

T=1.05,  Bucket = 0.5 MB, Output = 11.5 MB
​​​​​​​T=1.10,  Bucket = 0.0 MB, Output = 12 MB


​​​​​​​Hence, It will take 1.1 sec to transmit 12 MB data.

Answer:

Related questions

58 votes
58 votes
11 answers
2
Sandeep Singh asked Feb 12, 2016
26,091 views
A sender uses the Stop-and-Wait $\text{ARQ}$ protocol for reliable transmission of frames. Frames are of size $1000$ bytes and the transmission rate at the sender is $80\...
34 votes
34 votes
6 answers
3
Sandeep Singh asked Feb 12, 2016
18,002 views
Which one of the following protocols is NOT used to resolve one form of address to another one?$\textsf{DNS}$$\textsf{ARP}$$\textsf{DHCP}$$\textsf{RARP}$