Hispanopedia Wiki
Articulo de referencia

Cubo de fichas

El algoritmo de cubo de tokens se utiliza en redes de conmutación de paquetes y telecomunicaciones . Permite comprobar que las transmisiones de datos , en forma de paquetes , se...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo de cubo de tokens se utiliza en redes de conmutación de paquetes y telecomunicaciones . Permite comprobar que las transmisiones de datos , en forma de paquetes , se ajustan a los límites definidos de ancho de banda y variabilidad (una medida de la irregularidad o las variaciones en el flujo de tráfico ). También puede utilizarse como algoritmo de planificación para determinar la sincronización de las transmisiones que cumplan con los límites establecidos para el ancho de banda y la variabilidad: véase planificador de red .

Descripción general

El algoritmo de cubo de tokens se basa en la analogía de un cubo 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 comprueba que un paquete cumple con los límites definidos, se inspecciona el cubo para ver si contiene suficientes tokens en ese momento. Si es así, se extrae la cantidad apropiada de tokens, por ejemplo, equivalente a la longitud del paquete en bytes, y el paquete se transmite. El paquete no cumple con los límites si no hay suficientes tokens en el cubo, y el contenido del cubo no se modifica. Los paquetes que no cumplen con los límites pueden tratarse de diversas maneras:

  • Pueden ser descartados.
  • Podrán ponerse en cola para su posterior transmisión cuando se hayan acumulado suficientes tokens en el depósito.
  • Pueden transmitirse, pero marcadas como no conformes, y posiblemente descartarse posteriormente si la red se sobrecarga.

Un flujo conforme puede contener tráfico con una tasa promedio igual a la tasa a la que se agregan tokens al depósito, y tener una variabilidad determinada por la profundidad del depósito. Esta variabilidad puede expresarse en términos de una tolerancia de fluctuación , es decir, cuánto antes podría un paquete cumplir con los requisitos (por ejemplo, llegar o ser transmitido) de lo que se esperaría 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 tráfico que el nivel promedio podría cumplir con los requisitos en un período finito.

Algoritmo

El algoritmo de cubo de tokens se puede entender conceptualmente de la siguiente manera:

  • Se agrega un token al cubo cada1/r{\displaystyle 1/r}artículos de segunda clase.
  • El cubo puede contener como máximob{\displaystyle b}fichas. Si llega una ficha 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 depósito, se eliminan n tokens del depósito y el paquete se envía a la red.
    • if fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.

Variations

Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every 1/r{\displaystyle 1/r} seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = (r∗S)/1000{\displaystyle (r*S)/1000}.

Properties

Average rate

Over the long run the output of conformant packets is limited by the token rate, r{\displaystyle r}.

Burst size

Let M{\displaystyle M} be the maximum possible transmission rate in bytes/second.

Then Tmax={b/(M−r) if r<M∞ otherwise {\displaystyle T_{\text{max}}={\begin{cases}b/(Mr)&{\text{ si }}r<M\\\infty &{\text{ en caso contrario }}\end{cases}}} is the maximum burst time, that is the time for which the rate M{\displaystyle M} is fully utilized.

The maximum burst size is thus Bmax=Tmax∗M{\displaystyle B_{\text{max}}=T_{\text{max}}*M}

Uses

The token bucket can be used in either traffic shaping or traffic policing. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts to prevent transmissions being discarded by traffic management functions in the network.

The token bucket algorithm is also used in controlling database IO flow.[1] In it, limitation applies to neither IOPS nor the bandwidth but rather to a linear combination of both. By defining tokens to be the normalized sum of IO request weight and its length, the algorithm makes sure that the time derivative of the aforementioned function stays below the needed threshold.

Comparison to leaky bucket

The token bucket algorithm is directly comparable to one of the two versions of the leaky bucket algorithm described in the literature.[2][3][4][5] This comparable version of the leaky bucket is described on the relevant Wikipedia page as the leaky bucket algorithm as a meter. This is a mirror image of the token bucket, in that conforming packets add fluid, equivalent to the tokens removed by a conforming packet in the token bucket algorithm, to a finite capacity bucket, from which this fluid then drains away at a constant rate, equivalent to the process in which tokens are added at a fixed rate.

Sin embargo, existe otra versión del algoritmo de cubo con fugas, [ 3 ] descrita en la página correspondiente de Wikipedia como el algoritmo de cubo con fugas como cola . Este es un caso especial del cubo con fugas como medidor, que se puede describir mediante los paquetes conformes que pasan a través del cubo. Por lo tanto, el cubo con fugas como cola solo es aplicable a la conformación del tráfico y, en general, no permite que el flujo de paquetes de salida sea en ráfagas, es decir, no tiene fluctuaciones. Por consiguiente, es significativamente diferente del algoritmo de cubo de tokens.

Estas dos versiones del algoritmo de la cubeta con fugas se han descrito en la literatura con el mismo nombre. Esto ha generado considerable confusión sobre las propiedades de dicho algoritmo y su comparación con el algoritmo de la cubeta de tokens. Sin embargo, fundamentalmente, ambos algoritmos son iguales y, si se implementan correctamente y se les proporcionan los mismos parámetros, clasificarán exactamente los mismos paquetes como conformes y no conformes.

Cubo de tokens jerárquico

El cubo de tokens 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 tasa de descarga / subida de cada cliente para que el cliente limitado no pueda saturar el ancho de banda total.

Tres clientes compartiendo el mismo ancho de banda de salida.

Conceptualmente, HTB es un número arbitrario de cubetas de tokens organizadas jerárquicamente. 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 límite superior . 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 se refiere al ancho de banda garantizado disponible para una clase determinada, y ceil (abreviatura de ceiling) indica el ancho de banda máximo que esa clase puede consumir. Cuando una clase solicita un ancho de banda superior al garantizado, puede tomar prestado ancho de banda de su clase padre siempre que no se alcancen ambos ceils. Hierarchical Token Bucket implementa un mecanismo de colas 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 de tráfico específicas, así como indicar la proporción de distribución del ancho de banda cuando hay ancho de banda adicional disponible (hasta ceil).

Al elegir el ancho de banda para una clase de nivel superior, la gestión del tráfico solo resulta útil en el cuello de botella entre la LAN e Internet. Normalmente, esto ocurre en entornos de red domésticos y de oficina, donde toda la LAN se conecta mediante una conexión DSL o T1 .

Véase también

Referencias

  1. ↑ "Implementación de un nuevo algoritmo de planificación de E/S para cargas de trabajo mixtas de lectura/escritura" . 3 de agosto de 2022. Consultado el 4 de agosto de 2022 .
  2. ↑ Turner, J., Nuevas direcciones en las comunicaciones (¿o hacia dónde nos dirigimos en la era de la información?) . IEEE Communications Magazine 24 (10): 8–15. ISSN 0163-6804 , 1986. 
  3. 1 2 Andrew S. Tanenbaum, Redes de computadoras, cuarta edición , ISBN 0-13-166836-6, Prentice Hall PTR, 2003, página 401.
  4. ↑ ATM Forum, Interfaz de red de usuario (UNI), v. 3.1, ISBN 0-13-393828-X, Prentice Hall PTR, 1995.
  5. ↑ UIT-T, Control de tráfico y control de congestión en ISDN B , Recomendación I.371, Unión Internacional de Telecomunicaciones, 2004, Anexo A, página 87.
  6. ↑ "Página principal de Linux HTB" . Consultado el 30 de noviembre de 2013 .

Lecturas adicionales

  • John Evans, Clarence Filsfils (2007). Implementación de QoS IP y MPLS para redes multiservicio: teoría y práctica . Morgan Kaufmann. ISBN 978-0-12-370549-5.
  • Ferguson P., Huston G. (1998). Calidad de servicio: Ofreciendo QoS en Internet y en redes corporativas . John Wiley & Sons, Inc. ISBN 0-471-24358-2.