Cubo con fugas

El algoritmo del cubo con fugas se basa en la analogía de un cubo con una fuga constante que se desbordará si la velocidad media de vertido supera la velocidad de la fuga o si se vierte más agua de la que el cubo puede contener de una sola vez. Se puede utilizar para determinar si una secuencia de eventos discretos se ajusta a límites definidos en sus tasas o frecuencias medias y máximas, por ejemplo, para limitar las acciones asociadas a estos eventos a dichas tasas o retrasarlas hasta que se ajusten a ellas. También se puede utilizar para comprobar la conformidad o limitar la acción a una tasa media, es decir, para eliminar cualquier variación respecto a la media.

Se utiliza en redes informáticas de conmutación de paquetes y redes de telecomunicaciones tanto en el control de tráfico , la conformación del tráfico como en la programación de transmisiones de datos , en forma de paquetes , ^{[ a ]} con límites definidos en el ancho de banda y la variabilidad (una medida de las variaciones en el flujo de tráfico ).

Se recomienda una versión del algoritmo de cubo con fugas, el algoritmo genérico de tasa de celda , para redes de modo de transferencia asíncrona (ATM) ^{[ 1 ]} en UPC y NPC en interfaces usuario-red , interfaces entre redes o interfaces red a red para proteger una red de niveles de tráfico excesivos en las conexiones que la atraviesan. El algoritmo genérico de tasa de celda, o uno equivalente, también puede utilizarse para dar forma a las transmisiones de una tarjeta de interfaz de red en una red ATM.

Al menos algunas implementaciones del algoritmo del cubo con fugas son una imagen especular del algoritmo del cubo de tokens y, dados parámetros equivalentes, determinarán exactamente la misma secuencia de eventos para ajustarse o no a los mismos límites.

En la literatura se describen dos métodos diferentes para aplicar esta analogía del cubo con fugas. ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]} Estos métodos presentan lo que parecen ser dos algoritmos distintos, ambos denominados algoritmo del cubo con fugas y, por lo general, sin hacer referencia al otro método. Esto ha generado confusión sobre qué es el algoritmo del cubo con fugas y cuáles son sus propiedades.

En una versión, el cubo es un contador o variable separado del flujo de tráfico o del cronograma de eventos. ^{[ 2 ] [ 4 ] [ 5 ]} Este contador se usa solo para verificar que el tráfico o los eventos se ajusten a los límites: El contador se incrementa a medida que cada paquete llega al punto donde se realiza la verificación o cuando ocurre un evento, lo que es equivalente a la forma en que se agrega agua intermitentemente al cubo. El contador también se decrementa a una tasa fija, equivalente a la forma en que el agua se escapa del cubo. Como resultado, el valor en el contador representa el nivel de agua en el cubo. Si el contador permanece por debajo de un valor límite especificado cuando llega un paquete o ocurre un evento, es decir, el cubo no se desborda, eso indica su conformidad con los límites de ancho de banda y ráfaga o los límites de tasa promedio y pico de eventos. Esta versión se denomina aquí cubo con fugas como medidor .

En la segunda versión, el cubo es una cola en el flujo de tráfico. ^{[ 3 ]} Esta cola se utiliza para controlar directamente ese flujo: los paquetes se introducen en la cola a medida que llegan, equivalente a añadir agua al cubo. Estos paquetes se eliminan de la cola ( primero en llegar, primero en ser atendido ), normalmente a una tasa fija, por ejemplo, para su posterior transmisión, equivalente a que el agua se escape del cubo. Esta configuración impone conformidad en lugar de comprobarla, y cuando la salida se atiende a una tasa fija (y donde todos los paquetes tienen la misma longitud), el flujo de tráfico resultante está necesariamente exento de fluctuaciones o jitter . Así pues, en esta versión, el tráfico mismo es el análogo del agua que pasa por el cubo. Esta versión se denomina aquí cubo con fugas como cola .

El cubo con fugas como medidor es exactamente equivalente a (una imagen especular de) el algoritmo del cubo de tokens ; es decir, el proceso de añadir agua al cubo con fugas refleja exactamente el de extraer tokens del cubo de tokens cuando llega un paquete conforme, el proceso de fuga de agua del cubo con fugas refleja exactamente el de añadir tokens al cubo de tokens de forma regular, y la prueba de que el cubo con fugas no se desborde es un reflejo de la prueba de que el cubo de tokens contenga suficientes tokens y no se desborde . Por lo tanto, dados parámetros equivalentes, ambos algoritmos verán el mismo tráfico como conforme o no conforme. El cubo con fugas como cola puede considerarse un caso especial del cubo con fugas como medidor. ^{[ 6 ]}

A Jonathan S. Turner se le atribuye ^{[ 7 ]} la descripción original del algoritmo de la cubeta con fugas y lo describe de la siguiente manera: "Un contador asociado a cada usuario que transmite en una conexión se incrementa cada vez que el usuario envía un paquete y se decrementa periódicamente. Si el contador supera un umbral al incrementarse, la red descarta el paquete. El usuario especifica la tasa a la que se decrementa el contador (esto determina el ancho de banda promedio) y el valor del umbral (una medida de la variabilidad)". ^{[ 2 ]} La cubeta (análoga al contador) se utiliza, en este caso, como un medidor para comprobar la conformidad de los paquetes, en lugar de como una cola para controlarlos directamente.

Otra descripción de lo que es esencialmente la misma versión del algoritmo de medición, el algoritmo genérico de tasa de celda , la proporciona la UIT-T en la recomendación I.371 y en la especificación UNI del ATM Forum . ^{[ 4 ] [ 5 ]} La descripción, en la que el término celda es equivalente a paquete en la descripción de Turner ^{[ 2 ],} la proporciona la UIT-T de la siguiente manera: "El cubo con fugas de estado continuo puede considerarse como un cubo de capacidad finita cuyo contenido de valor real se drena a una tasa continua de 1 unidad de contenido por unidad de tiempo y cuyo contenido aumenta en el incremento T para cada celda conforme... Si a la llegada de una celda el contenido del cubo es menor o igual al valor límite τ , entonces la celda es conforme; de ​​lo contrario, la celda no es conforme. La capacidad del cubo (el límite superior del contador) es ( T + τ )". ^{[ 5 ]} Estas especificaciones también establecen que, debido a su capacidad finita, si el contenido del cubo en el momento en que se prueba la conformidad es mayor que el valor límite, y por lo tanto la celda no es conforme, entonces el cubo se deja sin cambios; es decir, simplemente no se agrega agua si esto haría que el cubo se desbordara.

David E. McDysan y Darrel L. Spohn ofrecen un comentario sobre la descripción proporcionada por el Foro ITU-T/ATM. En él, afirman: «En la analogía del cubo con fugas, las celdas [ATM] no fluyen realmente a través del cubo; solo lo hace la verificación de admisión conforme». ^{[ 6 ]} Sin embargo, de forma poco común en las descripciones de la literatura, McDysan y Spohn también se refieren al algoritmo del cubo con fugas como una cola, y añaden: «Nótese que una implementación de la conformación del tráfico consiste en hacer que las celdas fluyan realmente a través del cubo». ^{[ 6 ]}

Al describir el funcionamiento de la versión del algoritmo de la UIT-T, McDysan y Spohn invocan una "noción comúnmente empleada en la teoría de colas de un gremlin ficticio ". ^{[ 6 ]} Este gremlin inspecciona el nivel en el cubo y toma medidas si el nivel está por encima del valor límite τ : en la vigilancia del tráfico , abre una trampilla, lo que hace que el paquete que llega se descarte y evita que su agua entre en el cubo; en la conformación del tráfico , empuja una solapa, lo que retrasa el paquete que llega y evita que entregue su agua, hasta que el nivel de agua en el cubo cae por debajo de τ .

La diferencia entre las descripciones proporcionadas por Turner y el Foro ITU-T/ATM radica en que la de Turner se centra específicamente en la regulación del tráfico, mientras que la del Foro ITU-T/ATM es aplicable tanto a la regulación como a la conformación del tráfico. Además, Turner no indica que el contenido del contador solo deba verse afectado por paquetes conformes, ni que solo deba incrementarse cuando esto no provoque que se supere un límite; es decir, Turner no afirma explícitamente que la capacidad del depósito o el valor máximo del contador sean finitos. ^{[ b ]}

El modelo de cubo con fugas como cola es esencialmente una forma de describir un búfer FIFO o cola simple que se atiende a una tasa fija para eliminar la fluctuación o el jitter. Andrew S. Tanenbaum lo describe en (una versión anterior de) su libro Redes de computadoras como: "El cubo con fugas consiste en una cola finita. Cuando llega un paquete, si hay espacio en la cola, se agrega a ella; de lo contrario, se descarta. En cada ciclo de reloj, se transmite un paquete (a menos que la cola esté vacía)". ^{[ 3 ]} Por lo tanto, una implementación del cubo con fugas como cola es siempre una forma de función de modelado de tráfico.

Como se puede observar, esta implementación está restringida, ya que los paquetes solo se transmiten a una velocidad fija. Para subrayar esto, Tanenbaum también afirma que "El algoritmo del cubo con fugas impone un patrón de salida rígido a la velocidad promedio, sin importar cuán irregular sea el tráfico [de entrada]". ^{[ 10 ]} Sin embargo, esta afirmación solo es estrictamente cierta mientras la cola no se vacíe: si la tasa de llegada promedio es menor que la frecuencia de los ciclos de reloj, o si la entrada es suficientemente irregular como para que las pérdidas hagan que la tasa del resto sea inferior a la frecuencia de los ciclos de reloj (es decir, las brechas en el flujo de entrada son lo suficientemente largas y la cola es lo suficientemente pequeña como para que pueda vaciarse), habrá brechas en el flujo de salida.

El parámetro ajustable para este algoritmo es el ancho de banda de su salida. ^{[ 10 ] [ c ]} El límite de ancho de banda para la conexión puede especificarse en un contrato de tráfico . Un límite de ancho de banda puede especificarse como una tasa de paquetes o tramas , una tasa de bytes o bits , o como un intervalo de emisión entre los paquetes.

Limitar paquetes de longitud variable usando el algoritmo de cubo con fugas como cola es significativamente más complicado que para paquetes de longitud fija. Tanenbaum ofrece una descripción de un cubo con fugas de "conteo de bytes" para paquetes de longitud variable de la siguiente manera: "En cada ciclo, un contador se inicializa a n. Si el primer paquete en la cola tiene menos bytes que el valor actual del contador, se transmite y el contador se decrementa en esa cantidad de bytes. También se pueden enviar paquetes adicionales, siempre que el contador sea lo suficientemente alto. Cuando el contador cae por debajo de la longitud del siguiente paquete en la cola, la transmisión se detiene hasta el siguiente ciclo, momento en el cual el conteo de bytes residual se restablece [a n] y el flujo puede continuar". ^{[ 3 ]} Al igual que con la versión para paquetes de longitud fija, esta implementación tiene un fuerte efecto en la fase de las transmisiones, lo que resulta en retrasos de extremo a extremo variables y no es adecuada para la conformación de tráfico en tiempo real.

El algoritmo de cubo con fugas, como cola, solo puede utilizarse para dar forma al tráfico a un ancho de banda específico sin fluctuaciones en la salida. ^{[ 10 ]} Puede utilizarse dentro de la red, por ejemplo, como parte de la gestión del ancho de banda, pero es más apropiado para dar forma al tráfico en las interfaces de red de los hosts. El algoritmo de cubo con fugas se utiliza en el módulo ngx_http_limit_req_module de Nginx para limitar el número de solicitudes concurrentes originadas desde una única dirección IP . ^{[ 11 ]}

El análisis de las dos versiones del algoritmo del cubo con fugas muestra que la versión como cola es un caso especial de la versión como medidor.

Imaginemos una función de modelado de tráfico para paquetes de longitud fija, implementada mediante una cola de longitud fija que forma un elemento de retardo, el cual se gestiona utilizando un medidor con un cubo con fugas. Imaginemos también que el cubo de este medidor tiene una profundidad igual a la cantidad añadida por un paquete, es decir, un valor límite, τ , de cero. Sin embargo, la prueba de conformidad solo se realiza a intervalos del intervalo de emisión, cuando se transmite el paquete al inicio de la cola y se añade su agua. Esta agua se filtra durante el siguiente intervalo de emisión (o se retira justo antes de realizar la siguiente prueba de conformidad), lo que permite que el siguiente paquete cumpla con la conformidad en ese momento o en algún intervalo de emisión posterior. La función de servicio también puede visualizarse en términos de un cubo de tokens con la misma profundidad, donde se añaden suficientes tokens para un paquete (si el cubo no está lleno) en los intervalos de emisión. Esta implementación recibirá paquetes con un patrón de llegada en ráfagas (limitado por la profundidad de la cola) y los transmitirá a intervalos que siempre son múltiplos exactos (enteros) del intervalo de emisión.

Sin embargo, la implementación del cubo con fugas como medidor (o cubo de tokens) en una función de modelado de tráfico descrita anteriormente es un equivalente exacto a la descripción del cubo con fugas como cola: ^{[ 3 ]} el elemento de retardo de la versión del medidor es el cubo de la versión de la cola; el cubo de la versión del medidor es el proceso que atiende la cola, y la fuga es tal que el intervalo de emisión es el mismo que el intervalo de tick. Por lo tanto, para paquetes de longitud fija, la implementación del cubo con fugas como cola es un caso especial de una función de modelado de tráfico que utiliza un cubo con fugas (o cubo de tokens) como medidor en el que el valor límite, τ , es cero y el proceso de prueba de conformidad se realiza a la tasa más baja posible.

El cubo con fugas como cola para longitudes de paquete variables también puede describirse como equivalente a un caso especial del cubo con fugas como medidor. La implementación sugerida ^{[ 3 ]} puede considerarse, al igual que la implementación de longitud fija, como una función de modelado de tráfico en la que la cola es un elemento de retardo, en lugar del cubo, y la función que atiende la cola se define explícitamente como un cubo de tokens: se decrementa para los paquetes conformes y se incrementa a una tasa fija. Por lo tanto, dado que el cubo con fugas como medidor y el cubo de tokens son equivalentes, el cubo con fugas como cola para longitudes de paquete variables también es un caso especial de una función de modelado de tráfico que utiliza un cubo con fugas (o un cubo de tokens) como medidor.

Existe una consecuencia interesante al considerar el cubo con fugas como una cola para longitudes de paquetes variables, como una implementación específica del cubo de tokens o el cubo con fugas como medidor en la conformación del tráfico. Esto se debe a que el cubo del medidor tiene una profundidad, n , y, como siempre ocurre con el cubo de tokens, esta profundidad determina la ráfaga del tráfico de salida (quizás en relación con el número promedio o mínimo de tokens requeridos por los paquetes). Por lo tanto, es posible cuantificar la ráfaga de la salida de este cubo con fugas de conteo de bytes como un medidor, a menos que todos los paquetes tengan la longitud máxima, en cuyo caso resulta inútil. Sin embargo, esta capacidad de definir una ráfaga para la salida contradice directamente la afirmación de que el cubo con fugas (como una cola) necesariamente proporciona una salida con una tasa rígida, independientemente de la ráfaga de la entrada.

• Cola fluida
• Algoritmo genérico de tasa celular
• Contrato de tráfico
• UPC y NPC