Token-Bucket-Algorithmus

Der Token-Bucket-Algorithmus ist ein Algorithmus zur Verkehrsformung in paketvermittelten Datennetzen. Er reguliert durch Netzwerk-Scheduler die mittlere Datenrate und maximale Burst-Größe.

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.

Siehe auch

• Leaky-Bucket-Algorithmus

Literatur

• Panos Lekkas: Network Processors. Architectures – Protocols and Platforms, McGraw Hill Professional, 2003, ISBN 978-0-07-140986-5.
• Ralf Steinmetz: Multimedia-Technologie. Grundlagen – Komponenten und Systeme, 2. Auflage, Springer Verlag, Berlin / Heidelberg 1999, ISBN 978-3-662-08882-1.
• Christoph Meinel, Harald Sack: Internetworking. Technische Grundlagen und Anwendungen. Springer-Verlag, Berlin/ Heidelberg 2012, ISBN 978-3-540-92940-6.

Weblinks

• Animation (FH Köln)
• Token Bucket Algorithmus (abgerufen am 29. September 2017)
• Leaky-Bucket & Token-Bucket-Algorithmus (abgerufen am 29. September 2017)