From: Ronny Jonathan (rjonathan@xxxxxxxxxx)
Date: Tue Jul 16 2002 - 12:34:38 GMT-3
Hi Group,
After some reading and self study on QOS, I found that most of QOS technique
(CAR, Traffic Shaping, and FRTS) are using "token bucket" algorithm.
I might be wrong but this is my understanding of how the algorithm work.
They used concepts like Normal Burst (Bc), Exceed Burst (Be)
Actual Debt, and Compounded Debt.
Actual Debt is the total number of "token" borrowed, while
Compounded Debt is the sum of Actual Debt.
Example FRTS w/ parameters of:
CIR = 32000 bps
AR = 64000 bps
Tc = 0.125
Bc = 4000 bits -> Bucket will get 4000 token every interval
Be = 32000 bits
Assuming arrival rate is 1 packet of 8000 bits ( 1000 bytes) per interval
(Tc):
1. When packet #1 arrived at t=0, the number of token in the bucket (Bc) is
4000.
IOS need 8000 token to send the packet, so it need to borrow 4000 token
to
be able to send pkt #1.
Hence at the 1st interval: Actual Debt = 4000, Compounded Debt = 4000.
Because Be > Compounded Debt , it send packet #1
2. When packet #2 arrived at t=0.125, the number of token in the bucket (Bc)
is 4000
IOS need 8000 token to send the packet, so it need to borrow 4000 token
to
be able to send pkt #2.
Hence at the 2nd interval: Actual Debt = 4000 + 4000 = 8000,
Compounded Debt = Compounded Debt at 1st interval + Actual Debt at 2nd
interval = 4000 + 8000 =12000
3. This continue until Be > Compounded Debt.
When Be > Compounded Debt, IOS enqueue the packet.
Because no packet transmitted, IOS doesn't need to borrow token, and the
available Bc
can be used to pay the actual debt.
Hence
Actual Debt = Actual Debt from previous interval - Bc
Compounded Debt = 0
The detail is in the excel spreadsheet attached. Hope this help. Thanks.
[GroupStudy.com removed an attachment of type application/vnd]
This archive was generated by hypermail 2.1.4 : Sat Sep 07 2002 - 19:36:32 GMT-3