Der Token-Bucket-Algorithmus (Token-Eimer) ist das verbreitetste Verfahren zur Verkehrsformung und Ratenbegrenzung in Netzwerken. Er erlaubt eine garantierte Durchschnittsrate, gestattet aber kurzzeitige Bursts bis zu einer konfigurierbaren Obergrenze. Er steckt im Traffic Shaping und im Rate Limiting von Routern, Firewalls und API-Gateways.
So funktioniert der Algorithmus
Ein Bucket (Eimer) fasst eine begrenzte Anzahl Token. Token werden mit fester Rate r aufgefüllt — in der Regel ein Token pro Zeiteinheit, bei Netzwerken entsprechend einer Datenrate in Bit pro Sekunde. Will ein Gerät ein Paket senden, muss es ein Token aus dem Bucket entnehmen; ist keins vorhanden, wird das Paket zurückgestellt (Shaping) oder verworfen (Policing). Ist der Bucket voll, werden neu erzeugte Token verworfen. Die Bucket-Größe b bestimmt dabei den erlaubten Burst: Ein großer Bucket erlaubt kurze Datenschübe bis zu seiner Füllmenge, während die langfristige Rate durch die Auffüllrate r begrenzt bleibt. Genau diese Kombination — Mittelrate r plus Burstgröße b — beschreibt auch der RFC-2216-Verkehrsspezifikationstyp der IETF.
Eigenschaften im Vergleich
- Erlaubt Bursts: Solange Token vorhanden sind, darf schneller gesendet werden als die Mittelrate — ideal für Web- und Dateitransfers.
- Keine künstliche Verzögerung im Leerlauf: Ist der Bucket voll, können sofort Daten fließen.
- Kein starrer Abfluss wie beim Leaky-Bucket, sondern ein Kreditrahmen, der sich bei Inaktivität ansammelt.
- Einfach parallelisierbar: Jede Instanz eines verteilten Dienstes kann ihren eigenen Bucket führen.
Typische Anwendungen
- QoS-Shaper auf Routern: Cisco-Terminologie CIR/Bc/Tc bildet den Token-Bucket direkt ab (Bc = Token, die pro Tc aufgefüllt werden).
- API-Gateways (z. B. Nginx, Kong, AWS API Gateway) begrenzen Anfragen pro Sekunde mit Token-Buckets pro Client oder API-Key.
- Firewalls und Traffic-Policer an ISP-Grenzen setzen das Verfahren als Messgerät (Meter) ein.
Verwandte Grundlagen: Traffic Shaping · Leaky-Bucket · Rate Limiting · Congestion Window.