Token-Bucket-Algorithmus

Der Token-Bucket-Algorithmus ist ein Konzept der Informatik aus dem Bereich des Traffic-Shapings. Es wird damit die Menge der übertragenen Daten geregelt. Dabei wird die durchschnittliche Datenrate begrenzt. Ein ähnlicher Algorithmus ist der Leaky-Bucket-Algorithmus.

Aufgabe

Unter Traffic-Shaping versteht man eine Programmlogik, die den Datenfluss einer Schnittstelle beeinflusst, um Grenzwerte einzuhalten; z. B. durchschnittliche, minimale oder maximale Datenmenge je Zeiteinheit.

Der Token-Bucket-Algorithmus gewährleistet, dass der Datenfluss langfristig einen bestimmten Durchschnitt nicht überschreitet, erlaubt aber kurzfristige Datenschübe (sog. Bursts) wenn der Datenfluss ungleichmäßig ist.

Funktionsweise

Dem Datenstrom werden regelmäßig bestimmte Kontingente zugeteilt, die ausgenutzt oder bis zu einer gewissen Grenze angesammelt werden können. Um die Sache anschaulicher zu machen, stellt man sich die Zuteilung bildhaft in Form von "Wertmarken" (englisch Token) vor, die in regelmäßigen Abständen in einen metaphorischen "Eimer" (englisch Bucket) geworfen werden. Jede Wertmarke steht für ein bestimmtes Datenkontingent, das übertragen werden darf. Wenn der Eimer voll ist, werden keine Wertmarken zugeteilt.

Wenn ein Datenpaket übertragen werden soll, werden entsprechend dem Gegenwert der Datenmenge im Paket Wertmarken aus dem Eimer entnommen.

Was passiert, wenn nicht genug Wertmarken im Eimer sind, hängt von der Umsetzung ab. Entweder wird das Datenpaket in eine Warteschlange gesetzt, bis sich durch die regelmäßige Zuteilung genug Wertmarken angesammelt haben, oder es wird verworfen. Eine weitere Möglichkeit ist, das Datenpaket trotzdem sofort zu versenden, es aber als "nicht-konform" zu markieren, so dass es auf seinem weiteren Weg verworfen werden kann, falls es zu Engpässen kommen sollte.

Wenn über einen Zeitraum hinweg weniger Daten übertragen als Wertmarken zugeteilt werden, sammeln sich diese im Eimer an. Dadurch entsteht ein Guthaben, das es ermöglicht, kurzfristig größere Datenmengen zu übertragen. Langfristig ist die Übertragungsrate aber durch die Rate der Wertmarkenzuteilung begrenzt.

Die Größe (Kapazität) des Eimers bestimmt das maximale Guthaben, das sich ansammeln kann. Dadurch wird verhindert, dass die durchschnittliche Datenrate über einen zu langen Zeitraum überschritten wird.

Weblinks

• Animation (FH Köln)