Multimedia-Technik: Token Bucket / Leaky Bucket

(Prof. Dr. C. Vogt, Nachrichtentechnik, FH Köln)

Die Animation des Token-Bucket- und des Leaky-Bucket-Algorithmus stammt aus dem Softwarepraktikum des Studiengangs Technische Informatik (Information Engineering) im Sommersemester 2007.
Sie wurde von den Studenten Edmond Chouaffe, Wouter Dijkstra, Andreas Novák und Saroosh Yousaf angefertigt.

Zweck der Algorithmen

In verteilten Multimediasystemen werden Audio- und Videoströme über Datennetze übertragen. Damit das Netz nicht überlastet wird, muss man sicherstellen, dass der Datenverkehr auf den Strömen bestimmte Grenzen nicht überschreitet. Verfahren, die den Verkehr entsprechend begrenzen, nennt man Traffic-Shaping-Algorithmen. Hierzu gehören der Token-Bucket- und der Leaky-Bucket-Algorithmus.

Token Bucket

Beim Token-Bucket-Verfahren fließen Marken (Token) mit einer bestimmten Rate r in einen Eimer (Bucket). Der Eimer kann höchstens b Marken aufnehmen; ist er voll, so gehen nachfolgende Token verloren. Um ein Datenpaket der Größe n im Netz zu verschicken, müssen n Marken aus dem Eimer genommen werden. Stehen sie nicht zur Verfügung, so wird das Paket so lange verzögert, bis der Eimer n Marken enthält. Die Füllrate r des Eimers begrenzt also die Langzeitdatenrate des Stroms, seine Kapazität b begrenzt die Größe von Bursts, also von Datenmengen, die "auf einen Schlag" übertragen werden.

Leaky Bucket

Beim Leaky-Bucket-Verfahren fließt der Strom selbst in den Eimer und darf diesen höchstens mit der Rate r verlassen. Der Eimer kann höchstens b Bytes aufnehmen; ist er voll, so gehen folgende Pakete verloren. Die Füllrate r des Eimers begrenzt also die Datenrate des Stroms. Bursts am Ausgang des Eimers sind hier nicht möglich. Ein Burst an seinem Eingang wird durch das Zwischenspeichern der Daten im Eimer "geglättet"; die maximale Größe eines solchen Bursts ist b.

Die Animation

Java-Applets animieren die Funktionsweise der Algorithmen. Sie bieten verschiedene Benutzungsmöglichkeiten:

• Automatischer Ablauf eines vorgegebenen Stroms. Dabei Illustration der Fälle, dass der Eimer überläuft und leerläuft.
  
  
• Einstellung der Werte r und b durch den Benutzer; ebenso Einstellung ob regelmäßige oder unregelmäßige Ankunft der Pakete und ob gleiche oder unterschiedliche Paketgrößen.
  
  
• Erzeugung des Stroms durch den Benutzer: Klicken mit der Maus lässt ein neues Paket eintreffen.

Mehr Informationen findet man im Benutzerhandbuch.

© 3.7.2007 Prof. Dr. Carsten Vogt - Kommentare sind willkommen.