Token bucket

Token bucket es un algoritmo usado en redes de computadoras de paquetes conmutados y redes de telecomunicaciones. Se puede usar para verificar que las transmisiones de datos, en forma de paquetes, se ajusten a límites definidos en el ancho de banda y la ráfaga (una medida de la irregularidad o variaciones en el flujo de tráfico). También se puede utilizar como un algoritmo de planificación para determinar el tiempo de las transmisiones que cumplirán con los límites establecidos para el ancho de banda y la ráfaga: véase planificador de red.

Visión general

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.

Algoritmo

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

• Se añade un token al cubo cada $1/r$ segundos.
• El cubo puede contener como máximo $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.

Véase también

• Leaky bucket
• Traffic shaping

Otras lecturas

• 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. 

• Datos: Q386456