Token bucket

El algoritmo token bucket se basa en una analogía de un cubo de capacidad fija en el que los tokens, normalmente representando una unidad de bytes o un único paquete de tamaño predeterminado, son añadidos a un ritmo fijo. Cuando se debe verificar que un paquete se ajusta (es conforme) a los límites definidos, se inspecciona el cubo para ver si contiene suficientes tokens en ese momento. Si es así, el número apropiado de tokens, por ejemplo equivalente a la longitud del paquete en bytes, se eliminan ("se consumen"), y el paquete se pasa, por ejemplo, para su transmisión. El paquete no es conforme si no hay suficientes tokens en el cubo, y el contenido del cubo no se modifica. Los paquetes no conformes se pueden tratar de varias maneras:

• Pueden ser borrados.
• Pueden ser puestos en cola para su posterior transmisión cuando se hayan acumulado suficientes tokens en el cubo.
• Pueden ser transmitidos, pero marcarse como no conformes, posiblemente para ser borrados posteriormente si la red está sobrecargada.

Por lo tanto, un flujo conforme puede contener tráfico con un ritmo promedio hasta el ritmo al que se añaden tokens al cubo, y tiene una ráfaga determinada por la profundidad del cubo.

El algoritmo token bucket se puede entender conceptualmente de la siguiente manera:

• Se añade un token al cubo cada ${\displaystyle 1/r}$ segundos.
• El cubo puede contener como máximo ${\displaystyle b}$ tokens. Si llega un token cuando el cubo está lleno, se descarta.
• Cuando llega un paquete (PDU de capa de red) de n bytes,
  • si hay al menos n tokens en el cubo, se eliminan n tokens del cubo y el paquete se envía a la red.
  • si hay menos de n tokens disponibles, no se eliminan tokens del cubo y se considera que el paquete no es conforme.

• Leaky bucket
• Traffic shaping

• John Evans, Clarence Filsfils (2007). Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice. Morgan Kaufmann. ISBN 0-12-370549-5.
• Ferguson P., Huston G. (1998). Quality of Service: Delivering QoS on the Internet and in Corporate Networks. John Wiley & Sons, Inc. ISBN 0-471-24358-2.