641:(short for ceiling) indicates the maximum bandwidth that class is allowed to consume. When a class requests a bandwidth more than guaranteed, it may borrow bandwidth from its parent as long as both ceils are not reached. Hierarchical Token Bucket implements a classful queuing mechanism for the Linux traffic control system, and provides rate and ceil to allow the user to control the absolute bandwidth to particular classes of traffic as well as indicate the ratio of distribution of bandwidth when extra bandwidth become available (up to ceil).
610:
574:. This is a special case of the leaky bucket as a meter, which can be described by the conforming packets passing through the bucket. The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.
524:. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see
567:. This is a mirror image of the token bucket, in that conforming packets add fluid, equivalent to the tokens removed by a conforming packet in the token bucket algorithm, to a finite capacity bucket, from which this fluid then drains away at a constant rate, equivalent to the process in which tokens are added at a fixed rate.
577:
These two versions of the leaky bucket algorithm have both been described in the literature under the same name. This has led to considerable confusion over the properties of that algorithm and its comparison with the token bucket algorithm. However, fundamentally, the two algorithms are the same,
102:
A conforming flow can thus contain traffic with an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket. This burstiness may be expressed in terms of either a jitter tolerance, i.e. how much sooner a packet might conform
87:
of predetermined size, are added at a fixed rate. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e.g. equivalent to the length of the packet in bytes, are
438:
88:
removed ("cashed in"), and the packet is passed, e.g., for transmission. The packet does not conform if there are insufficient tokens in the bucket, and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:
644:
When choosing the bandwidth for a top-level class, traffic shaping only helps at the bottleneck between the LAN and the
Internet. Typically, this is the case in home and office network environments, where an entire LAN is serviced by a DSL or
103:(e.g. arrive or be transmitted) than would be expected from the limit on the average rate, or a burst tolerance or maximum burst size, i.e. how much more than the average level of traffic might conform in some finite period.
345:
507:
238:
seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds =
276:
236:
141:
458:
337:
309:
164:
543:
The token bucket algorithm is also used in controlling database IO flow. In it, limitation applies to neither IOPS nor the bandwidth but rather to a
688:
622:) on any device is known as the root qdisc. The root qdisc will contain one class. This single HTB class will be set with two parameters, a
563:
algorithm described in the literature. This comparable version of the leaky bucket is described on the relevant
Knowledge page as the
578:
and will, if implemented correctly and given the same parameters, see exactly the same packets as conforming and nonconforming.
860:
98:
They may be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.
817:
210:
Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every
547:
of both. By defining tokens to be the normalized sum of IO request weight and its length, the algorithm makes sure that the
618:
Conceptually, HTB is an arbitrary number of token buckets arranged in a hierarchy. The primary egress queuing discipline (
433:{\displaystyle T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}}
630:. These values should be the same for the top-level class, and will represent the total available bandwidth on the link.
836:
758:
741:
521:
466:
59:
to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see
570:
There is, however, another version of the leaky bucket algorithm, described on the relevant
Knowledge page as the
855:
533:
52:
95:
They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket.
80:
32:
367:
668:
717:
241:
195:
tokens are available, no tokens are removed from the bucket, and the packet is considered to be
44:
646:
587:
529:
525:
56:
8:
540:
to prevent transmissions being discarded by traffic management functions in the network.
213:
118:
591:
544:
443:
322:
294:
170:
149:
48:
774:, Recommendation I.371, International Telecommunication Union, 2004, Annex A, page 87.
571:
564:
832:
813:
754:
737:
713:
60:
36:
559:
The token bucket algorithm is directly comparable to one of the two versions of the
663:
548:
517:
291:
Over the long run the output of conformant packets is limited by the token rate,
28:
537:
84:
40:
849:
658:
829:
Quality of
Service: Delivering QoS on the Internet and in Corporate Networks
560:
689:"Implementing a New IO Scheduler Algorithm for Mixed Read/Write Workloads"
188:
tokens are removed from the bucket, and the packet is sent to the network.
810:
Deploying IP and MPLS QoS for
Multiservice Networks: Theory and Practice
710:
New directions in communications (or which way to the information age?)
784:
111:
The token bucket algorithm can be conceptually understood as follows:
606:
rate so that the limited client cannot saturate the total bandwidth.
24:
586:
The hierarchical token bucket (HTB) is a faster replacement for the
166:
tokens. If a token arrives when the bucket is full, it is discarded.
599:
609:
551:
of the aforementioned function stays below the needed threshold.
72:
637:
means the guaranteed bandwidth available for a given class and
603:
440:
is the maximum burst time, that is the time for which the rate
76:
807:
595:
426:
339:
be the maximum possible transmission rate in bytes/second.
826:
753:
ATM Forum, The User
Network Interface (UNI), v. 3.1,
469:
446:
348:
325:
297:
244:
216:
152:
121:
83:, normally representing a unit of bytes or a single
613:Three clients sharing the same outbound bandwidth.
501:
452:
432:
331:
303:
270:
230:
158:
135:
51:(a measure of the unevenness or variations in the
847:
772:Traffic control and congestion control in B ISDN
728:
726:
502:{\displaystyle B_{\text{max}}=T_{\text{max}}*M}
712:. IEEE Communications Magazine 24 (10): 8–15.
681:
16:Scheduling algorithm for network transmissions
723:
554:
581:
598:. It is useful for limiting each client's
532:. Traffic shaping is commonly used in the
71:The token bucket algorithm is based on an
764:
777:
747:
608:
516:The token bucket can be used in either
848:
808:John Evans, Clarence Filsfils (2007).
744:, Prentice Hall PTR, 2003., page 401.
702:
115:A token is added to the bucket every
13:
801:
413:
14:
872:
734:Computer Networks, Fourth Edition
572:leaky bucket algorithm as a queue
565:leaky bucket algorithm as a meter
146:The bucket can hold at the most
55:flow). It can also be used as a
827:Ferguson P., Huston G. (1998).
463:The maximum burst size is thus
286:
43:, conform to defined limits on
35:. It can be used to check that
831:. John Wiley & Sons, Inc.
390:
378:
257:
245:
1:
861:Network scheduling algorithms
674:
314:
281:
205:
169:When a packet (network layer
106:
7:
652:
66:
33:telecommunications networks
10:
877:
761:, Prentice Hall PTR, 1995.
555:Comparison to leaky bucket
271:{\displaystyle (r*S)/1000}
184:tokens are in the bucket,
582:Hierarchical token bucket
511:
614:
503:
454:
434:
333:
305:
272:
232:
160:
137:
785:"Linux HTB Home Page"
732:Andrew S. Tanenbaum,
612:
504:
455:
435:
420: otherwise
334:
306:
273:
233:
161:
138:
588:class-based queueing
530:congestion avoidance
526:bandwidth management
467:
444:
346:
323:
295:
242:
214:
150:
119:
92:They may be dropped.
75:of a fixed capacity
57:scheduling algorithm
856:Network performance
812:. Morgan Kaufmann.
669:Counting semaphores
460:is fully utilized.
231:{\displaystyle 1/r}
136:{\displaystyle 1/r}
615:
592:queuing discipline
545:linear combination
534:network interfaces
499:
450:
430:
425:
329:
301:
268:
228:
156:
133:
37:data transmissions
819:978-0-12-370549-5
490:
477:
453:{\displaystyle M}
421:
398:
356:
332:{\displaystyle M}
304:{\displaystyle r}
159:{\displaystyle b}
61:network scheduler
39:, in the form of
868:
842:
823:
795:
794:
792:
791:
781:
775:
768:
762:
751:
745:
730:
721:
706:
700:
699:
697:
696:
685:
522:traffic policing
508:
506:
505:
500:
492:
491:
488:
479:
478:
475:
459:
457:
456:
451:
439:
437:
436:
431:
429:
428:
422:
419:
399:
396:
377:
358:
357:
354:
338:
336:
335:
330:
310:
308:
307:
302:
277:
275:
274:
269:
264:
237:
235:
234:
229:
224:
165:
163:
162:
157:
142:
140:
139:
134:
129:
876:
875:
871:
870:
869:
867:
866:
865:
846:
845:
839:
820:
804:
802:Further reading
799:
798:
789:
787:
783:
782:
778:
769:
765:
752:
748:
731:
724:
707:
703:
694:
692:
691:. 3 August 2022
687:
686:
682:
677:
664:Traffic shaping
655:
617:
584:
557:
549:time derivative
518:traffic shaping
514:
487:
483:
474:
470:
468:
465:
464:
445:
442:
441:
424:
423:
418:
416:
410:
409:
395:
393:
373:
363:
362:
353:
349:
347:
344:
343:
324:
321:
320:
317:
296:
293:
292:
289:
284:
260:
243:
240:
239:
220:
215:
212:
211:
208:
177:bytes arrives,
151:
148:
147:
125:
120:
117:
116:
109:
69:
29:packet-switched
17:
12:
11:
5:
874:
864:
863:
858:
844:
843:
837:
824:
818:
803:
800:
797:
796:
776:
763:
746:
722:
701:
679:
678:
676:
673:
672:
671:
666:
661:
654:
651:
583:
580:
556:
553:
513:
510:
498:
495:
486:
482:
473:
449:
427:
417:
415:
412:
411:
408:
405:
402:
397: if
394:
392:
389:
386:
383:
380:
376:
372:
369:
368:
366:
361:
352:
328:
316:
313:
300:
288:
285:
283:
280:
267:
263:
259:
256:
253:
250:
247:
227:
223:
219:
207:
204:
203:
202:
201:
200:
197:non-conformant
191:if fewer than
189:
167:
155:
144:
132:
128:
124:
108:
105:
100:
99:
96:
93:
68:
65:
15:
9:
6:
4:
3:
2:
873:
862:
859:
857:
854:
853:
851:
840:
838:0-471-24358-2
834:
830:
825:
821:
815:
811:
806:
805:
786:
780:
773:
767:
760:
759:0-13-393828-X
756:
750:
743:
742:0-13-166836-6
739:
735:
729:
727:
719:
715:
711:
705:
690:
684:
680:
670:
667:
665:
662:
660:
659:Rate limiting
657:
656:
650:
648:
642:
640:
636:
631:
629:
625:
621:
611:
607:
605:
601:
597:
593:
589:
579:
575:
573:
568:
566:
562:
552:
550:
546:
541:
539:
535:
531:
527:
523:
519:
509:
496:
493:
484:
480:
471:
461:
447:
406:
403:
400:
387:
384:
381:
374:
370:
364:
359:
350:
340:
326:
312:
298:
279:
265:
261:
254:
251:
248:
225:
221:
217:
198:
194:
190:
187:
183:
179:
178:
176:
172:
168:
153:
145:
130:
126:
122:
114:
113:
112:
104:
97:
94:
91:
90:
89:
86:
82:
78:
74:
64:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
828:
809:
788:. Retrieved
779:
771:
766:
749:
733:
709:
708:Turner, J.,
704:
693:. Retrieved
683:
649:connection.
643:
638:
634:
632:
627:
623:
619:
616:
585:
576:
569:
561:leaky bucket
558:
542:
515:
462:
341:
318:
290:
287:Average rate
209:
196:
192:
185:
181:
180:if at least
174:
110:
101:
70:
21:token bucket
20:
18:
79:into which
850:Categories
790:2013-11-30
695:2022-08-04
675:References
315:Burst size
282:Properties
206:Variations
49:burstiness
718:0163-6804
494:∗
414:∞
385:−
252:∗
107:Algorithm
45:bandwidth
25:algorithm
653:See also
633:In HTB,
600:download
143:seconds.
67:Overview
27:used in
770:ITU-T,
720:, 1986.
73:analogy
53:traffic
41:packets
835:
816:
757:
740:
716:
626:and a
604:upload
590:(CBQ)
85:packet
81:tokens
77:bucket
23:is an
620:qdisc
596:Linux
538:hosts
342:Then
173:) of
833:ISBN
814:ISBN
755:ISBN
738:ISBN
714:ISSN
639:ceil
635:rate
628:ceil
624:rate
528:and
512:Uses
404:<
319:Let
266:1000
47:and
31:and
19:The
594:in
536:in
520:or
489:max
476:max
355:max
171:PDU
852::
736:,
725:^
647:T1
311:.
278:.
63:.
841:.
822:.
793:.
698:.
602:/
497:M
485:T
481:=
472:B
448:M
407:M
401:r
391:)
388:r
382:M
379:(
375:/
371:b
365:{
360:=
351:T
327:M
299:r
262:/
258:)
255:S
249:r
246:(
226:r
222:/
218:1
199:.
193:n
186:n
182:n
175:n
154:b
131:r
127:/
123:1
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.