El token bucket es un algoritmo utilizado en redes de conmutación de paquetes y de telecomunicaciones . Se puede utilizar para comprobar que las transmisiones de datos , en forma de paquetes , se ajustan a los límites definidos de ancho de banda y ráfagas (una medida de la irregularidad o las variaciones en el flujo de tráfico ). También se puede utilizar como un algoritmo de programación para determinar el momento de las transmisiones que cumplirán con los límites establecidos para el ancho de banda y las ráfagas: consulte planificador de red .
El algoritmo de depósito de tokens se basa en una analogía de un depósito de capacidad fija en el que se añaden tokens , que normalmente representan una unidad de bytes o un único paquete de tamaño predeterminado, a una tasa fija. Cuando se debe comprobar si un paquete cumple los límites definidos, se inspecciona el depósito para ver si contiene suficientes tokens en ese momento. Si es así, se elimina ("se cobra") la cantidad adecuada 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 cumple los requisitos 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 formas:
Un flujo conforme puede contener tráfico con una tasa promedio hasta la tasa a la que se agregan tokens al contenedor, y tener una ráfaga determinada por la profundidad del contenedor. Esta ráfaga puede expresarse en términos de una tolerancia de fluctuación, es decir, cuánto antes un paquete podría cumplir con la norma (por ejemplo, llegar o transmitirse) de lo que se esperaría a partir del límite de la tasa 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 cumplir con la norma en un período finito.
El algoritmo del token bucket 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 segundos 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 deben agregar cada S milisegundos = .
A largo plazo, la salida de paquetes conformes está limitada por la tasa de 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 tasa se utiliza completamente.
El tamaño máximo de ráfaga es por lo tanto
El token bucket se puede utilizar tanto en la modelación del tráfico como en la vigilancia del tráfico . En la vigilancia del tráfico, los paquetes no conformes se pueden descartar (eliminar) o se puede reducir su prioridad (para que las funciones de gestión del tráfico descendente los descarten si hay congestión). En la modelación del tráfico, los paquetes se retrasan hasta que se ajustan. La vigilancia del tráfico y la modelación del tráfico se utilizan habitualmente para proteger la red contra el tráfico excesivo o excesivamente en ráfagas, consulte gestión del ancho de banda y prevención de la congestión . La modelación del tráfico se utiliza habitualmente en las interfaces de red de los hosts para evitar que las funciones de gestión del tráfico descarten transmisiones en la red.
El algoritmo de token bucket 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 las E/S por segundo 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 E/S 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 cubo de fichas es directamente comparable a una de las dos versiones del algoritmo del cubo con fugas descritas en la literatura. [2] [3] [4] [5] Esta versión comparable del cubo con fugas se describe en la página de Wikipedia pertinente como el algoritmo del cubo con fugas como un medidor . Esta es una imagen reflejada del cubo de fichas, en la que los paquetes conformes agregan fluido, equivalente a los tokens eliminados 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 tasa constante, equivalente al proceso en el que los tokens se agregan a una tasa fija.
Sin embargo, existe otra versión del algoritmo del cubo con fugas, [3] descrita en la página de Wikipedia correspondiente como el algoritmo del cubo con fugas como cola . Este es un caso especial del cubo con fugas como medidor, que puede describirse por los paquetes conformes que pasan a través del cubo. Por lo tanto, el cubo con fugas como cola solo es aplicable a la modelación del tráfico y, en general, no permite que el flujo de paquetes de salida sea a ráfagas, es decir, que no tenga fluctuaciones. Por lo tanto, es significativamente diferente del algoritmo del cubo con tokens.
Estas dos versiones del algoritmo del cubo con fugas se han descrito en la literatura con el mismo nombre, lo que ha provocado una considerable confusión sobre las propiedades de ese algoritmo y su comparación con el algoritmo del cubo con fichas. Sin embargo, en esencia, los dos algoritmos son iguales y, si se implementan correctamente y se les dan los mismos parámetros, considerarán exactamente los mismos paquetes como conformes y no conformes.
El token bucket jerárquico (HTB) es un reemplazo más rápido para la disciplina de cola basada en clases (CBQ) en Linux . [6] Es útil para limitar la velocidad de carga / descarga de cada cliente de modo que el cliente limitado no pueda saturar el ancho de banda total.
En términos conceptuales, HTB es una cantidad arbitraria de tokens dispuestos 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 HTB se configurará con dos parámetros, una tasa y un ceil . 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, rate significa el ancho de banda garantizado disponible para una clase determinada y ceil (abreviatura de ceiling) indica el ancho de banda máximo que se permite que consuma esa clase. Cuando una clase solicita un ancho de banda mayor que el garantizado, puede pedir prestado ancho de banda a su padre siempre que no se alcancen ambos topes. Hierarchical Token Bucket implementa un mecanismo de cola con clases para el sistema de control de tráfico de Linux y proporciona rate y ceil para permitir al usuario controlar el ancho de banda absoluto para clases particulares de tráfico, así como indicar la proporción de distribución del ancho de banda cuando hay ancho de banda adicional disponible (hasta el tope).
Al elegir el ancho de banda para una clase de nivel superior, la modelación del tráfico solo ayuda en el cuello de botella entre la LAN e Internet. Por lo general, este es el caso en entornos de redes domésticas y de oficina, donde una LAN completa recibe servicio de una conexión DSL o T1 .
