El algoritmo del cubo con fugas se basa en una analogía de cómo un cubo con una fuga constante se desbordará si la velocidad media a la que se vierte el agua en él supera la velocidad a la que el cubo pierde agua o si se vierte más agua de la que puede contener el cubo de una sola vez. Se puede utilizar para determinar si una secuencia de eventos discretos se ajusta a límites definidos en sus frecuencias o tasas medias y máximas, por ejemplo, para limitar las acciones asociadas con estos eventos a estas tasas o retrasarlas hasta que se ajusten a ellas. También se puede utilizar para comprobar la conformidad o limitar a una tasa media únicamente, es decir, eliminar cualquier variación con respecto a la media.
Se utiliza en redes de ordenadores con conmutación de paquetes y redes de telecomunicaciones tanto para el control del tráfico , la modelación del tráfico y la programación de transmisiones de datos , en forma de paquetes , [nota 1] con límites definidos de ancho de banda y ráfagas (una medida de las variaciones en el flujo de tráfico ).
Se recomienda una versión del contenedor con fugas, el algoritmo de velocidad de celda genérico , para redes de modo de transferencia asíncrono (ATM) [1] en UPC y NPC en interfaces de usuario-red o interfaces entre redes o interfaces de red a red para proteger una red de niveles de tráfico excesivos en conexiones enrutadas a través de ella. El algoritmo de velocidad de celda genérico, o un equivalente, también se puede utilizar para dar forma a las transmisiones de una tarjeta de interfaz de red en una red ATM.
Al menos algunas implementaciones del cubo con fugas son una imagen reflejada del algoritmo del cubo de fichas y, dados parámetros equivalentes, determinarán exactamente la misma secuencia de eventos para cumplir o no con los mismos límites.
En la literatura se describen dos métodos diferentes de aplicación de esta analogía del cubo con fugas. [2] [3] [4] [5] Estos dan como resultado lo que parecen ser dos algoritmos diferentes, ambos denominados algoritmo del cubo con fugas y generalmente 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 independiente del flujo de tráfico o del cronograma de eventos. [2] [4] [5] Este contador se utiliza únicamente para comprobar que el tráfico o los eventos se ajustan a los límites: el contador se incrementa a medida que cada paquete llega al punto en el que se está realizando la comprobación o se produce un evento, lo que equivale a la forma en que se añade agua de forma intermitente al cubo. El contador también se decrementa a una tasa fija, equivalente a la forma en que el agua se filtra del cubo. Como resultado, el valor del 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 se produce un evento, es decir, el cubo no se desborda, eso indica su conformidad con los límites de ancho de banda y ráfagas o los límites de eventos de tasa media y máxima. Esta versión se denomina aquí el 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, lo que equivale a que se añada agua al cubo. A continuación, estos paquetes se eliminan de la cola ( por orden de llegada ), normalmente a una velocidad fija, por ejemplo, para la transmisión posterior, lo que equivale 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 velocidad fija (y donde todos los paquetes tienen la misma longitud), el flujo de tráfico resultante está necesariamente libre de ráfagas o fluctuaciones. Por tanto, en esta versión, el tráfico en sí 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 reflejada de) el algoritmo del cubo de fichas , es decir, el proceso de añadir agua al cubo con fugas refleja exactamente el de retirar fichas del cubo de fichas cuando llega un paquete conforme, el proceso de fuga de agua del cubo con fugas refleja exactamente el de añadir fichas regularmente al cubo de fichas, y la prueba de que el cubo con fugas no se desbordará es un espejo de la prueba de que el cubo de fichas contiene suficientes fichas y no se desbordará . Por lo tanto, dados parámetros equivalentes, los dos algoritmos verán el mismo tráfico como conforme o no conforme. El cubo con fugas como cola puede verse como un caso especial del cubo con fugas como medidor. [6]
Jonathan S. Turner [7] es reconocido por la descripción original del algoritmo del cubo con fugas y lo describe de la siguiente manera: "Un contador asociado con 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 excede un umbral al ser incrementado, la red descarta el paquete. El usuario especifica la velocidad a la que se decrementa el contador (esto determina el ancho de banda promedio) y el valor del umbral (una medida de la ráfaga)". [2] El cubo (análogo al contador) se usa, en este caso, como un medidor para probar 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 de contador del algoritmo, el algoritmo de velocidad de celda genérica , es dada por la UIT-T en la recomendación I.371 y en la Especificación UNI del Foro ATM . [4] [5] La descripción, en la que el término celda es equivalente a paquete en la descripción de Turner [2] es dada por la UIT-T de la siguiente manera: "El contenedor con fugas de estado continuo puede ser visto como un contenedor 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 se incrementa por el incremento T para cada celda conforme... Si en la llegada de una celda el contenido del contenedor es menor o igual al valor límite τ , entonces la celda es conforme; de lo contrario, la celda es no conforme. La capacidad del contenedor (el límite superior del contador) es ( T + τ )". [5] Estas especificaciones también establecen que, debido a su capacidad finita, si el contenido del balde 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 balde se deja sin cambios; es decir, simplemente no se agrega agua si esto haría que el balde se desborde.
David E. McDysan y Darrel L. Spohn ofrecen un comentario sobre la descripción dada por el Foro ITU-T/ATM. En él, afirman: "En la analogía del cubo con fugas, las células [ATM] en realidad no fluyen a través del cubo; sólo lo hace la comprobación de admisión conforme". [6] Sin embargo, de manera 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: "Obsérvese que una implementación de la modelación del tráfico es hacer que las células fluyan 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 duende ficticio ". [6] Este duende inspecciona el nivel en el balde 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 balde; en la modelación del tráfico , empuja hacia arriba una solapa, que retrasa el paquete que llega y evita que entre su agua, hasta que el nivel de agua en el balde cae por debajo de τ .
La diferencia entre las descripciones dadas por Turner y las del Foro ITU-T/ATM es que la de Turner es específica para el control del tráfico, mientras que la descripción del Foro ITU-T/ATM es aplicable tanto al control del tráfico como a la conformación del tráfico. Además, Turner no afirma que el contenido del contador sólo deba verse afectado por los paquetes conformes y que sólo deba incrementarse cuando esto no haga que supere un límite, es decir, Turner no afirma explícitamente que la capacidad del contenedor o el valor máximo del contador sean finitos. [nota 2]
Una descripción del concepto de funcionamiento del algoritmo del cubo con fugas como un medidor que se puede utilizar tanto en la vigilancia del tráfico como en la modelación del tráfico puede describirse como un cubo de capacidad fija, asociado con cada conexión virtual o usuario. El cubo pierde agua a una velocidad fija. Si el cubo está vacío, deja de perder agua. Para que un paquete se ajuste a las normas, tiene que ser posible añadir una cantidad específica de agua al cubo. La cantidad específica añadida por un paquete conforme puede ser la misma para todos los paquetes o puede ser proporcional a la longitud del paquete. Si esta cantidad de agua hiciera que el cubo se desbordara, entonces el paquete no se ajusta a las normas y el agua del cubo no cambia.
El cubo con fugas como medidor se puede utilizar tanto en la modelación del tráfico como en la vigilancia del tráfico . Por ejemplo, en las redes ATM, en forma de algoritmo de velocidad de celda genérico, se utiliza para comparar el ancho de banda y la ráfaga de tráfico en un canal virtual (VC) o ruta virtual (VP) con los límites especificados en la velocidad a la que pueden llegar las celdas y la fluctuación máxima, o variación en los intervalos entre llegadas, para el VC o VP. En la vigilancia del tráfico, las celdas que no se ajustan a estos límites (celdas no conformes) pueden descartarse o pueden reducirse en prioridad para que las funciones de gestión del tráfico descendente las descarten si hay congestión. En la modelación del tráfico, las celdas se retrasan hasta que se ajustan. La vigilancia del tráfico y la modelación del tráfico se utilizan comúnmente en UPC y NPC para proteger la red contra el tráfico excesivo o excesivamente en ráfagas. (Véase gestión del ancho de banda y prevención de la congestión ). La modelación del tráfico se utiliza comúnmente en las interfaces de red en los hosts para evitar que las transmisiones excedan los límites de ancho de banda o fluctuación y sean descartadas por las funciones de gestión del tráfico en la red. (Véase programación (informática) y programador de red ).
El algoritmo de balde con fugas como medidor también se puede utilizar en un contador de balde con fugas para medir la tasa de procesos aleatorios (estocásticos) . Un contador de balde con fugas se puede utilizar para indicar, mediante su desbordamiento, cuándo la tasa promedio o pico de eventos aumenta por encima de un nivel de fondo aceptable. [8] Por ejemplo, un contador de balde con fugas de este tipo se puede utilizar para detectar cuándo hay una ráfaga repentina de errores de memoria corregibles o cuando ha habido un aumento gradual, pero significativo, en la tasa promedio, lo que puede indicar un fallo de corrección inminente. [9]
El uso del algoritmo de balde con fugas en un contador de baldes con fugas es similar al de la gestión del tráfico, en el sentido de que se utiliza como un medidor. Básicamente, los eventos reemplazan los paquetes en la descripción, y cada evento hace que se agregue una cantidad de agua al balde. Si el balde se desbordara como resultado del evento, entonces el evento debería desencadenar la acción asociada con un evento fuera de límites. Algunas implementaciones [8] parecen ser paralelas a la descripción de Turner [2] , en el sentido de que no hay un límite explícito en el valor máximo que puede tomar el contador, lo que implica que una vez que el contador ha excedido el umbral, puede no volver a su estado anterior hasta que haya transcurrido un período significativamente mayor que el equivalente del intervalo de emisión, que puede aumentarse por lo que de otro modo serían eventos conformes. Sin embargo, otras implementaciones pueden no incrementar el contador mientras está desbordado, lo que le permite determinar correctamente si los siguientes eventos son conformes o no.
En el caso del algoritmo de balde con fugas como medidor, los límites del tráfico pueden ser el ancho de banda y la ráfaga de la salida. [4] [5] [nota 3] El límite de ancho de banda y el límite de ráfagas para la conexión pueden especificarse en un contrato de tráfico . Un límite de ancho de banda puede especificarse como una tasa de paquetes, una tasa de bits o como un intervalo de emisión entre los paquetes. Un límite de ráfagas puede especificarse como una tolerancia de variación de retardo o como un tamaño máximo de ráfaga (MBS).
Se pueden aplicar varios conjuntos de parámetros de contrato simultáneamente a una conexión utilizando múltiples instancias del algoritmo de depósito con fugas, cada una de las cuales puede tomar un ancho de banda y un límite de ráfagas: consulte Algoritmo de velocidad de celda genérico § Controlador de depósito con fugas dual .
La tasa a la que se producen fugas en el contenedor determinará el límite de ancho de banda, al que Turner [2] denomina tasa promedio y cuya inversa la ITU-T denomina intervalo de emisión. Es más fácil explicar qué es este intervalo cuando los paquetes tienen una longitud fija. Por lo tanto, la primera parte de esta descripción asume esto y las implicaciones de las longitudes de paquete variables se consideran por separado.
Consideremos un contenedor que se llena exactamente hasta arriba con el tráfico precedente, es decir, cuando ya se ha producido la máxima cantidad de ráfagas permitidas, es decir, la cantidad máxima de paquetes o celdas acaba de llegar en el tiempo mínimo necesario para que sigan cumpliendo con los límites de ancho de banda y fluctuación. El intervalo mínimo antes de que el próximo paquete pueda cumplir con los límites es entonces el tiempo que tarda el contenedor en filtrar exactamente la cantidad de agua entregada por un paquete, y si se prueba un paquete y cumple con los límites en ese momento, esto llenará exactamente el contenedor una vez más. Por lo tanto, una vez que el contenedor está lleno, la tasa máxima a la que los paquetes pueden cumplir con los límites es con este intervalo entre cada paquete.
Turner [2] se refiere a esta tasa como el promedio, lo que implica que su inverso es el intervalo promedio. Sin embargo, existe cierta ambigüedad en lo que son la tasa promedio y el intervalo. Dado que los paquetes pueden llegar a cualquier tasa inferior, se trata de un límite superior, en lugar de un valor fijo, por lo que, en el mejor de los casos, podría llamarse el máximo para la tasa promedio. Además, durante el tiempo en que se produce la máxima ráfaga, los paquetes pueden llegar a intervalos más pequeños y, por lo tanto, a una tasa mayor que esta. Por lo tanto, para cualquier período menor que infinito, la tasa promedio real puede ser (pero no necesariamente) mayor que esta y el intervalo promedio puede ser (pero no necesariamente) menor que el intervalo de emisión. Por lo tanto, debido a esta ambigüedad, en lo sucesivo se utiliza el término intervalo de emisión. Sin embargo, sigue siendo cierto que el valor mínimo que puede tomar el intervalo promedio de largo plazo tiende a ser el intervalo de emisión.
En el caso de los paquetes de longitud variable, en los que la cantidad añadida al contenedor es proporcional a la longitud del paquete, la velocidad máxima a la que pueden ajustarse varía según su longitud: la cantidad que el contenedor debe haber perdido desde que está lleno para que un paquete se ajuste es la cantidad que el paquete añadirá y, si esta es proporcional a la longitud del paquete, también lo es el intervalo entre este y el paquete anterior que llenó el contenedor. Por lo tanto, no es posible especificar un intervalo de emisión específico para los paquetes de longitud variable, y el límite de ancho de banda debe especificarse explícitamente, en bits o bytes por segundo.
Es más fácil explicar la tolerancia a la variación del retardo en el caso en que los paquetes tienen una longitud fija. Por lo tanto, la primera parte de esta descripción asume esto y las implicaciones de las longitudes de paquete variables se consideran por separado.
La UIT-T define un valor límite, τ , que es menor que la capacidad del contenedor en T (la cantidad en la que se incrementa el contenido del contenedor para cada celda conforme), de modo que la capacidad del contenedor es T + τ . Este valor límite especifica cuánto antes puede llegar un paquete de lo que se esperaría normalmente si los paquetes llegaran con exactamente el intervalo de emisión entre ellos.
Imaginemos la siguiente situación: un cubo pierde una unidad de agua por segundo, por lo que el valor límite, τ, y la cantidad de agua añadida por un paquete, T , están en realidad en unidades de segundos. Este cubo empieza vacío, por lo que cuando llega un paquete al cubo, no lo llena del todo añadiendo su agua T , y el cubo está ahora τ por debajo de su capacidad. Por lo que cuando llega el siguiente paquete, el cubo solo tiene que haberse vaciado en T – τ para que esto sea conforme. Por lo que el intervalo entre estos dos paquetes puede ser tanto como τ menos que T.
Esto se extiende a múltiples paquetes en una secuencia: Imagine lo siguiente: el cubo comienza nuevamente vacío, por lo que el primer paquete que llega claramente se ajusta. El cubo luego se llena exactamente después de que una cantidad de paquetes conformes, N , hayan llegado en el mínimo tiempo posible para que se ajusten. Para que el último paquete (el N º) se ajuste, el cubo debe haber perdido suficiente agua de los N – 1 paquetes anteriores (( N – 1) × T segundos) para que esté exactamente en el valor límite τ en este momento. Por lo tanto, el agua filtrada es ( N – 1) × T – τ , que debido a que la fuga es de una unidad por segundo, tomó exactamente ( N – 1) × T – τ segundos para filtrarse. Por lo tanto, el tiempo más corto en el que todos los N paquetes pueden llegar y ajustarse es ( N – 1) × T – τ segundos, que es exactamente τ menos que el tiempo que habría tomado si los paquetes hubieran estado llegando exactamente en el intervalo de emisión.
Sin embargo, los paquetes solo pueden llegar con intervalos menores que T cuando el contenedor no está lleno por el paquete anterior. Si está lleno, entonces el contenedor debe haberse vaciado por la cantidad completa T antes de que el siguiente paquete se ajuste. Entonces, una vez que este espacio del contenedor ha sido utilizado por paquetes que llegan en menos de T , los marcos posteriores deben llegar en intervalos no menores que T. Sin embargo, pueden llegar en intervalos mayores, cuando el contenedor no se llenará con ellos. Dado que el contenedor deja de tener fugas cuando está vacío, siempre hay un límite ( τ ) a cuánta tolerancia se puede acumular por estos intervalos mayores que T .
Dado que el valor límite τ define cuánto antes puede llegar un paquete de lo esperado, es el límite de la diferencia entre los retrasos máximo y mínimo desde la fuente hasta el punto donde se realiza la prueba de conformidad (suponiendo que los paquetes se generan sin fluctuaciones). De ahí el uso del término tolerancia a la variación del retraso de celda (CDVt) para este parámetro en ATM.
Como ejemplo, una posible fuente de variación de retardo es cuando se multiplexan juntos varios flujos de paquetes en la salida de un conmutador. Suponiendo que la suma de los anchos de banda de estas conexiones es menor que la capacidad de la salida, todos los paquetes que llegan pueden transmitirse eventualmente. Sin embargo, si sus llegadas son independientes, por ejemplo, porque llegan a diferentes entradas del conmutador, entonces varios pueden llegar al mismo tiempo o casi al mismo tiempo. Como la salida solo puede transmitir un paquete a la vez, los demás deben ponerse en cola en un búfer hasta que sea su turno para ser transmitidos. Este búfer introduce entonces un retraso adicional entre la llegada de un paquete a una entrada y su transmisión por la salida, y este retraso varía, dependiendo de cuántos otros paquetes ya estén en cola en el búfer. Una situación similar puede ocurrir en la salida de un host (en el controlador de interfaz de red ) cuando varios paquetes tienen tiempos de liberación iguales o similares, y este retraso generalmente se puede modelar como un retraso en un búfer de salida virtual.
En el caso de paquetes de longitud variable, donde la cantidad de agua añadida por un paquete determinado es proporcional a su longitud, τ no puede considerarse un límite de lo lleno que puede estar el balde cuando llega un paquete, ya que esto varía según el tamaño del paquete. Sin embargo, el tiempo que tarda en vaciarse desde este nivel hasta que se vacía sigue siendo el tiempo que tarda un paquete en llegar antes de lo esperado cuando se transmiten en el límite de ancho de banda. Por lo tanto, sigue siendo la variación máxima en el retraso de transferencia hasta el punto en el que se aplica la prueba de conformidad lo que se puede tolerar y, por lo tanto, la tolerancia en la variación máxima del retraso.
El valor límite o tolerancia de variación de retardo también controla cuántos paquetes pueden llegar en una ráfaga, determinada por el exceso de profundidad del contenedor sobre la capacidad requerida para un solo paquete. Por lo tanto, MBS también es una medida de ráfaga o fluctuación, y es posible especificar la ráfaga como un MBS y derivar el valor límite τ de esto o especificarlo como una fluctuación o tolerancia de variación de retardo o valor límite, y derivar el MBS de esto.
Una ráfaga o un grupo de paquetes puede llegar a una velocidad mayor que la determinada por el intervalo de emisión T. Esta puede ser la velocidad de línea de la conexión de la capa física cuando los paquetes en la ráfaga llegarán uno tras otro. Sin embargo, como en ATM, la tolerancia se puede aplicar a una velocidad menor, en ese caso, la tasa de celdas sostenible (SCR), y la ráfaga de paquetes (celdas) puede llegar a una velocidad mayor, pero menor que la velocidad de línea de la capa física, en ese caso, la tasa de celdas máxima (PCR). La MBS puede ser entonces la cantidad de celdas necesarias para transportar un paquete de capa superior (consulte Segmentación y reensamblaje ), donde los paquetes se transmiten con un ancho de banda máximo determinado por la SCR y las celdas dentro de los paquetes se transmiten en la PCR; lo que permite que la última celda del paquete, y el paquete en sí, lleguen significativamente antes de lo que llegarían si las celdas se enviaran en la SCR: duración de la transmisión = (MBS-1)/PCR en lugar de (MBS-1)/SCR. Esta ráfaga en el PCR impone una carga significativamente mayor en los recursos compartidos, por ejemplo, los buffers de salida del conmutador, que la transmisión en el SCR, y por lo tanto es más probable que resulte en desbordamientos de buffer y congestión de la red. Sin embargo, impone una carga menor en estos recursos que la que generaría la transmisión en el SCR con un valor límite, τ SCR , que permite que las celdas MBS se transmitan y lleguen consecutivamente a la velocidad de línea.
Si el valor límite es lo suficientemente grande, entonces varios paquetes pueden llegar en una ráfaga y aún así cumplir con los requisitos: si el contenedor comienza desde vacío, el primer paquete que llegue agregará T , pero si, para cuando llegue el siguiente paquete, el contenido está por debajo de τ , este también cumplirá con los requisitos. Suponiendo que cada paquete tarda δ en llegar, entonces si τ (expresado como el tiempo que tarda el contenedor en vaciarse desde el valor límite) es igual o mayor que el intervalo de emisión menos el tiempo mínimo entre llegadas, T – δ , el segundo paquete cumplirá con los requisitos incluso si llega como una ráfaga con el primero. De manera similar, si τ es igual o mayor que ( T – δ ) × 2, entonces pueden llegar 3 paquetes en una ráfaga, etc.
El tamaño máximo de esta ráfaga, M , se puede calcular a partir del intervalo de emisión, T ; la tolerancia máxima de fluctuación, τ ; y el tiempo necesario para transmitir/recibir un paquete, δ , de la siguiente manera: [4]
De igual manera, el valor mínimo de tolerancia a la fluctuación τ que da un MBS específico se puede calcular a partir del MBS de la siguiente manera: [4]
En el caso de ATM, donde técnicamente MBS solo se relaciona con la tolerancia del SCR, en la ecuación anterior el tiempo que tarda cada paquete en llegar, δ , es el intervalo de emisión para celdas en el PCR T PCR , y el intervalo de emisión, T , es el intervalo de emisión para el SCR T SCR . Donde MBS debe ser el número de celdas requeridas para transportar un paquete segmentado, el valor límite en lo anterior, τ , debe ser el del SCR τ SCR . Sin embargo, en la UNI o una NNI, donde las celdas en el PCR habrán estado sujetas a variación de retardo, debe ser el valor límite para el SCR más el del PCR τ SCR + τ PCR .
En el caso de los paquetes de longitud variable, el tamaño máximo de ráfaga dependerá de la longitud de los paquetes de la ráfaga y no existe un valor único para el tamaño máximo de ráfaga. Sin embargo, es posible especificar la longitud total de la ráfaga en bytes, a partir de la tasa de bytes del flujo de entrada, la tasa de bytes equivalente de la fuga y la profundidad del depósito.
El algoritmo del cubo con fugas se contrasta a veces con el algoritmo del cubo con fichas . Sin embargo, el concepto de funcionamiento anterior para el cubo con fugas como medidor se puede comparar directamente con el algoritmo del cubo con fichas, cuya descripción se da en ese artículo de la siguiente manera:
Esto se puede comparar con el concepto de operación, repetido anteriormente:
Como se puede ver, estas dos descripciones son esencialmente imágenes especulares una de la otra: una añade algo al contenedor de forma regular y quita algo para los paquetes conformes hasta un límite de cero; la otra quita de forma regular y añade para los paquetes conformes hasta un límite de la capacidad del contenedor. Por tanto, ¿una implementación que añade tokens para un paquete conforme y los elimina a una tasa fija es una implementación del contenedor con fugas o del contenedor con tokens? De forma similar, ¿qué algoritmo se utiliza en una implementación que elimina agua para un paquete conforme y añade agua a una tasa fija? De hecho, ambos son efectivamente lo mismo, es decir, implementaciones tanto del contenedor con fugas como del contenedor con tokens, ya que son el mismo algoritmo básico descrito de forma diferente. Esto explica por qué, dados parámetros equivalentes, los dos algoritmos verán exactamente los mismos paquetes como conformes o no conformes. Las diferencias en las propiedades y el rendimiento de las implementaciones de los algoritmos de contenedor con fugas y de contenedor con tokens resultan entonces enteramente de las diferencias en las implementaciones, es decir, no se derivan de diferencias en los algoritmos subyacentes.
Los puntos a tener en cuenta son que el algoritmo de cubo con fugas, cuando se utiliza como medidor, puede permitir un flujo de paquetes de salida conforme con fluctuaciones o ráfagas, se puede utilizar en el control y modelado del tráfico, y se puede implementar para paquetes de longitud variable.
El cubo con fugas como cola es esencialmente una forma de describir un buffer o cola FIFO simple que se atiende a una tasa fija para eliminar las ráfagas o fluctuaciones. Andrew S. Tanenbaum lo describe en (una versión anterior de) su libro Computer Networks como "El cubo con fugas consiste en una cola finita. Cuando llega un paquete, si hay espacio en la cola, se agrega a la cola; de lo contrario, se descarta. En cada tic del 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 ver, esta implementación está restringida en el sentido de que los paquetes solo se transmiten a una tasa fija. Para subrayar esto, Tanenbaum también afirma que "el algoritmo de depósito con fugas impone un patrón de salida rígido a la tasa promedio, sin importar cuán intermitente 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 promedio de llegada es menor que la tasa de ticks del reloj, o si la entrada es lo suficientemente intermitente como para que las pérdidas lleven la tasa del resto por debajo de la tasa de ticks del reloj (es decir, los espacios en el flujo de entrada son lo suficientemente largos y la cola es lo suficientemente pequeña como para que pueda vaciarse), habrá espacios en el flujo de salida.
Una restricción adicional es que el cubo con fugas como una función de modelado de tráfico de cola solo transmite paquetes en los ticks; por lo tanto, si se utiliza dentro de una red, equivalente a UPC y NPC , también impone una fase fija en la transmisión posterior de paquetes. Mientras que, cuando se utiliza un medidor de cubo con fugas para controlar la transmisión posterior, un paquete se transmite tan pronto como se ajusta, es decir, en relación con el anterior o, si ya se ajusta, su tiempo de llegada; no de acuerdo con algún reloj local arbitrario. Perversamente, en el contexto del retraso de transferencia, esta imposición de una fase fija que puede, con el tiempo, diferir de la de un flujo de paquetes de entrada que de otro modo se ajustaría, constituye una variación de retraso y, por lo tanto, una fluctuación. La fluctuación causada de esta manera particular solo podría observarse donde el retraso se mide como el tiempo de tránsito entre dos puntos de medición separados, uno a cada lado del cubo con fugas como una función de modelado de cola. Sin embargo, en el contexto de las transmisiones de datos en tiempo real, es este retraso de extremo a extremo el que determina la latencia de los datos recibidos. Por lo tanto, el cubo con fugas como cola no es adecuado para la configuración del tráfico en transmisiones en tiempo real.
Limitar los paquetes de longitud variable utilizando el algoritmo de depósito con fugas como cola es significativamente más complicado que para los paquetes de longitud fija. Tanenbaum ofrece una descripción de un depósito con fugas de "conteo de bytes" para paquetes de longitud variable de la siguiente manera: "En cada tic, se inicializa un contador 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 tic, momento en el que el recuento 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 demoras variables de extremo a extremo y en la falta de idoneidad para la modelación del tráfico en tiempo real.
El contenedor con fugas como cola solo se puede utilizar para dar forma al tráfico a un ancho de banda específico sin fluctuaciones en la salida. [10] Se puede utilizar 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 contenedor con fugas se utiliza en el módulo ngx_http_limit_conn_module de Nginx para limitar la cantidad de conexiones simultáneas que se originan desde una única dirección IP . [11]
En el caso del algoritmo de depósito con fugas como cola, el único límite definido para este algoritmo es el ancho de banda de su salida. [10] [nota 3]
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 cuadros, una tasa de bytes o bits , o como un intervalo de emisión entre los paquetes.
La implementación del depósito con fugas como cola no utiliza los recursos de red disponibles de manera eficiente. Debido a que transmite paquetes solo a intervalos fijos, habrá muchas instancias en las que el volumen de tráfico sea muy bajo y no se utilicen grandes porciones de los recursos de red (en particular, el ancho de banda). Por lo tanto, no existe ningún mecanismo en la implementación del depósito con fugas como cola que permita que los flujos individuales alcancen la velocidad del puerto, consumiendo efectivamente recursos de red en momentos en los que no habría contención de recursos en la red. Sin embargo, las implementaciones del depósito de tokens y del depósito con fugas como medidor permiten que los flujos de tráfico de salida tengan características de ráfagas.
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.
Imagine una función de modelado de tráfico para paquetes de longitud fija que se implementa utilizando una cola de longitud fija, formando un elemento de retardo, que se atiende utilizando un cubo con fugas como medidor. Imagine también que el cubo en este medidor tiene una profundidad igual a la cantidad añadida por un paquete, es decir, tiene un valor límite, τ , de cero. Sin embargo, la prueba de conformidad solo se realiza en intervalos del intervalo de emisión, cuando se transmite el paquete en la cabeza de la cola y se añade su agua. Esta agua se filtra durante el siguiente intervalo de emisión (o se elimina justo antes de realizar la siguiente prueba de conformidad), lo que permite que el siguiente paquete se ajuste en ese momento o en algún intervalo de emisión posterior. La función de servicio también se puede ver 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á entonces paquetes con un patrón de llegada en ráfagas (limitado por la profundidad de la cola) y los transmitirá en intervalos que siempre son múltiplos exactos (enteros) del intervalo de emisión.
Sin embargo, la implementación del cubo con fugas como un medidor (o cubo de fichas) en una función de modelado de tráfico descrita anteriormente es un equivalente exacto a la descripción del cubo con fugas como una 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 da servicio a la cola, y la fuga es tal que el intervalo de emisión es el mismo que el intervalo de tic. Por lo tanto, para paquetes de longitud fija, la implementación del cubo con fugas como una cola es un caso especial de una función de modelado de tráfico que utiliza un cubo con fugas (o cubo de fichas) como un 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 contenedor con fugas como cola para longitudes de paquetes variables también puede describirse como equivalente a un caso especial del contenedor con fugas como medidor. La implementación sugerida [3] puede, al igual que la implementación de longitud fija, verse como una función de modelado de tráfico en la que la cola es un elemento de retardo, en lugar del contenedor, y la función que da servicio a la cola se da, en este caso, explícitamente como un contenedor de tokens: se decrementa para los paquetes conformes y se incrementa a una tasa fija. Por lo tanto, como el contenedor con fugas como medidor y el contenedor de tokens son equivalentes, el contenedor con fugas como cola para longitudes de paquetes variables también es un caso especial de una función de modelado de tráfico que utiliza un contenedor con fugas (o contenedor de tokens) como medidor.
Hay una consecuencia interesante de considerar el cubo con fugas como una cola para longitudes de paquetes variables como una implementación específica del cubo de tokens o cubo con fugas como un medidor en la conformación del tráfico. Esto es que el cubo del medidor tiene una profundidad, n, y, como siempre es el caso 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 ya no tiene sentido. Sin embargo, esta capacidad de definir una ráfaga para la salida está en contradicción directa con la afirmación de que el cubo con fugas (como una cola) necesariamente da una salida con una tasa rígida, sin importar cuán ráfaga sea la entrada.
