Leaky-Bucket-Algorithmus
Der Leaky-Bucket-Algorithmus ist eine Methode zur Zwischenspeicherung einer variablen Anzahl von Anfragen und deren Organisation zur Ausgabe von Paketen mit einer festgelegten Rate in einem ATM-Netzwerk (Asynchronous Transfer Mode).
Der Leaky-Bucket-Algorithmus wird verwendet, um Traffic Policing und Traffic Shaping in Ethernet- und zellularen Datennetzen (Mobilfunk) zu implementieren. Der Algorithmus eignet sich auch zur Steuerung von Internet-Verbindungen mit gebührenpflichtiger Bandbreite.
Der Algorithmus funktioniert ähnlich wie ein undichter Eimer (Leaky Bucket), der Wasser hält: Der Leaky Bucket nimmt Daten auf und sammelt sie bis zu einer maximalen Kapazität. Die Daten im Eimer werden nur mit einer festgelegten Rate und Paketgröße aus dem Eimer freigegeben. Wenn der Eimer keine Daten mehr enthält, hört das Auslaufen auf. Wenn eingehende Daten den Eimer überfüllen würden, wird das Paket als nicht konform betrachtet und nicht zum Eimer hinzugefügt. Daten werden dem Eimer wieder hinzugefügt, wenn Speicherplatz für konforme Pakete verfügbar wird.
Der Leaky-Bucket-Algorithmus kann außerdem sowohl allmählich ansteigende als auch dramatische Speicherfehlererhöhungen erkennen, indem er vergleicht, wie die Durchschnitts- und Spitzendatenraten festgelegte akzeptable Hintergrundmengen überschreiten.
Der Leaky-Bucket-Algorithmus lässt sich mit einer FIFO-Warteschlange relativ einfach realisieren.
In einem breiteren Kontext ist der Leaky Bucket eine Analogie zur Beschreibung der Funktionsweise von Ein- und Ausgängen in einer Vielzahl von Geschäfts- und Technologiesystemen.
