Der Leaky-Bucket-Algorithmus (undichter Eimer) ist ein Verfahren zur Verkehrsformung, das einen konstanten, gleichmäßigen Abfluss erzwingt. Ankommende Daten laufen in einen Puffer (den Eimer) und werden mit fest vorgegebener Rate abgelassen — unabhängig davon, wie unregelmäßig sie ankommen. Ist der Eimer voll, werden weitere Pakete verworfen oder blockiert. Das Bild: Ein Eimer mit kleinem Loch am Boden läuft immer mit derselben Geschwindigkeit aus, egal wie viel Wasser (Verkehr) man hineingießt.
So funktioniert der Algorithmus
Der Eimer entspricht einer Warteschlange mit begrenzter Kapazität. Neue Pakete werden am oberen Ende eingefüllt; ein Ablaufmechanismus entnimmt unten mit fester Rate ein Paket nach dem anderen (Leak Rate) und gibt es auf die Leitung. Drei Fälle sind möglich: Der Eimer ist leer — die Leitung läuft unter der Maximalrate (kein Stau); es ist Füllstand vorhanden — Pakete werden mit exakt der Abflussrate gesendet; der Eimer ist voll — weitere Pakete passen nicht hinein und werden verworfen (oder der Sender wird per Backpressure gestoppt). Dadurch entsteht ein perfekt geglätteter Datenstrom ohne Bursts, dafür kann der Algorithmus keine kurzen Datenschübe durchreichen, selbst wenn die Leitung frei wäre.
Leaky-Bucket vs. Token-Bucket
- Leaky-Bucket: starrer, konstanter Ausgangsstrom; ein ankommender Burst wird auf die Abflussrate gedrosselt. Gut für Echtzeitanwendungen, die gleichmäßige Latenz brauchen (Sprache, Video-Streaming).
- Token-Bucket: erlaubt Bursts bis zur Bucket-Größe; im Leerlauf angesammelte Token können später sofort genutzt werden. Flexibler für Internet-Verkehr mit Stoßcharakter (Web, Dateitransfer).
- Gemeinsam: Beide begrenzen die mittlere Rate und brauchen einen Puffer; beide sind Grundbausteine von Traffic Shaping und QoS-Metern.
Einsatzgebiete
- ATM-Netze nutzten das Leaky-Bucket-Modell zur Verkehrscharakterisierung (Generic Cell Rate Algorithm).
- Streaming-Server modellieren mit dem Leaky-Bucket-Puffermodell die Puffergröße für ruckelfreie Wiedergabe (Microsoft Media Foundation).
- Rate Limiter in API-Gateways und Netzwerkgeräten erzwingen mit ihm eine harte Obergrenze pro Sekunde.
Verwandte Grundlagen: Token-Bucket · Traffic Shaping · Quality of Service · Router.