El token bucket es un algoritmo utilizado en redes de telecomunicaciones y de conmutación de paquetes . Puede utilizarse para comprobar que las transmisiones de datos , en forma de paquetes , se ajustan a límites definidos de ancho de banda y ráfagas (una medida de la desigualdad o variaciones en el flujo de tráfico ). También se puede utilizar como algoritmo de programació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: ver programador de red .
El algoritmo del depósito de tokens se basa en una analogía de un depósito de capacidad fija en el que los tokens , que normalmente representan una unidad de bytes o un único paquete de tamaño predeterminado, se agregan a una velocidad fija. Cuando se debe verificar que un paquete cumpla con los límites definidos, se inspecciona el depósito para ver si contiene suficientes tokens en ese momento. Si es así, se elimina ("cobra" el número apropiado de tokens, por ejemplo equivalente a la longitud del paquete en bytes), y el paquete se pasa, por ejemplo, para su transmisión. El paquete no se ajusta si no hay suficientes tokens en el depósito y el contenido del depósito no se modifica. Los paquetes no conformes se pueden tratar de varias maneras:
Por lo tanto, un flujo conforme puede contener tráfico con una tasa promedio hasta la tasa a la que se agregan tokens al depósito, y tener una ráfaga determinada por la profundidad del depósito. Esta ráfaga puede expresarse en términos de tolerancia a la fluctuación, es decir, cuánto antes podría adaptarse un paquete (por ejemplo, llegar o transmitirse) de lo que se esperaría del límite de la velocidad promedio, o una tolerancia de ráfaga o tamaño máximo de ráfaga, es decir cuánto más que el nivel promedio de tráfico podría conformarse en un período finito.
El algoritmo del depósito de tokens se puede entender conceptualmente de la siguiente manera:
Los implementadores de este algoritmo en plataformas que carecen de la resolución de reloj necesaria para agregar un solo token al depósito cada segundo pueden considerar una formulación alternativa. Dada la capacidad de actualizar el depósito de tokens cada S milisegundos, la cantidad de tokens que se agregarán cada S milisegundos = .
A largo plazo, la salida de paquetes conformes está limitada por la tasa del token .
Sea la velocidad de transmisión máxima posible en bytes/segundo.
Entonces está el tiempo máximo de ráfaga, es decir, el tiempo durante el cual la velocidad se utiliza por completo.
El tamaño máximo de ráfaga es, por tanto,
El depósito de tokens se puede utilizar para dar forma al tráfico o para controlar el tráfico . En la vigilancia del tráfico, los paquetes no conformes pueden descartarse (eliminarse) o reducirse su prioridad (para que las funciones de gestión del tráfico descendente se descarten si hay congestión). En el modelado del tráfico, los paquetes se retrasan hasta que se ajusten. La vigilancia del tráfico y la configuración del tráfico se utilizan habitualmente para proteger la red contra un tráfico excesivo o con ráfagas excesivas; consulte gestión del ancho de banda y prevención de congestión . La configuración del tráfico se utiliza comúnmente en las interfaces de red de los hosts para evitar que las funciones de gestión del tráfico de la red descarten las transmisiones.
El algoritmo del depósito de tokens también se utiliza para controlar el flujo de E/S de la base de datos. [1] En él, la limitación no se aplica ni a IOPS ni al ancho de banda, sino a una combinación lineal de ambos. Al definir los tokens como la suma normalizada del peso de la solicitud de IO y su longitud, el algoritmo se asegura de que la derivada temporal de la función antes mencionada se mantenga por debajo del umbral necesario.
El algoritmo del depósito de tokens es directamente comparable a una de las dos versiones del algoritmo del depósito con fugas descritas en la literatura. [2] [3] [4] [5] Esta versión comparable del balde con fugas se describe en la página correspondiente de Wikipedia como el algoritmo del balde con fugas como un medidor . Esta es una imagen especular del cubo de fichas, en el sentido de que los paquetes conformes añaden fluido, equivalente a las fichas eliminadas por un paquete conforme en el algoritmo del cubo de fichas, a un cubo de capacidad finita, del cual este fluido luego se drena a una velocidad constante. equivalente al proceso en el que se añaden tokens a una tasa fija.
Sin embargo, existe otra versión del algoritmo del depósito con fugas, [3] descrito en la página correspondiente de Wikipedia como algoritmo del depósito con fugas como cola . Este es un caso especial del balde con fugas como medidor, que puede describirse por los paquetes conformes que pasan a través del balde. Por lo tanto, el depósito con fugas como cola es aplicable sólo a la conformación del tráfico y, en general, no permite que el flujo de paquetes de salida esté en ráfagas, es decir, que esté libre de fluctuaciones. Por lo tanto, es significativamente diferente del algoritmo del depósito de tokens.
Estas dos versiones del algoritmo del cubo con fugas se han descrito en la literatura con el mismo nombre. Esto ha generado una confusión considerable sobre las propiedades de ese algoritmo y su comparación con el algoritmo del depósito de tokens. Sin embargo, fundamentalmente, los dos algoritmos son iguales y, si se implementan correctamente y se les dan los mismos parámetros, verán exactamente los mismos paquetes como conformes y no conformes.
El depósito de tokens jerárquico (HTB) es un reemplazo más rápido para la disciplina de colas basadas en clases (CBQ) en Linux . [6] Es útil para limitar la tasa de descarga / carga de cada cliente para que el cliente limitado no pueda saturar el ancho de banda total.
Conceptualmente, HTB es un número arbitrario de depósitos de tokens organizados en una jerarquía. La disciplina de cola de salida principal ( qdisc ) en cualquier dispositivo se conoce como qdisc raíz. La qdisc raíz contendrá una clase. Esta única clase de HTB se configurará con dos parámetros, una tarifa y un techo . Estos valores deben ser los mismos para la clase de nivel superior y representarán el ancho de banda total disponible en el enlace.
En HTB, tasa significa el ancho de banda garantizado disponible para una clase determinada y techo (abreviatura de techo) indica el ancho de banda máximo que esa clase puede consumir. Cuando una clase solicita un ancho de banda superior al garantizado, puede pedir prestado ancho de banda a su padre siempre que no se alcancen ambos límites. Hierarchical Token Bucket implementa un mecanismo de cola con clase para el sistema de control de tráfico de Linux y proporciona velocidad y techo para permitir al usuario controlar el ancho de banda absoluto para clases particulares de tráfico, así como indicar la relación de distribución del ancho de banda cuando hay ancho de banda adicional disponible ( hasta el techo).
A la hora de elegir el ancho de banda para una clase de nivel superior, el modelado del tráfico sólo ayuda en el cuello de botella entre la LAN e Internet. Normalmente, este es el caso en entornos de red domésticos y de oficina, donde una LAN completa recibe servicio mediante una conexión DSL o T1 .
