El balde con fugas es un algoritmo basado en una analogía de cómo un balde con una fuga constante se desbordará si la velocidad promedio a la que se vierte agua excede la velocidad a la que el balde gotea o si se vierte más agua que la capacidad del balde. vertido todo a la vez. Puede usarse para determinar si alguna secuencia de eventos discretos se ajusta a límites definidos en sus tasas o frecuencias promedio y pico, por ejemplo, para limitar las acciones asociadas con estos eventos a estas tasas o retrasarlas hasta que se ajusten a las tasas. También se puede utilizar para verificar la conformidad o limitarla a una tasa promedio únicamente, es decir, eliminar cualquier variación del promedio.
Se utiliza en redes informáticas de conmutación de paquetes y redes de telecomunicaciones tanto para la vigilancia del tráfico como para la configuración del tráfico y la programación de transmisiones de datos , en forma de paquetes , [nota 1] hasta 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 cubo con fugas, el algoritmo genérico de velocidad de celda , para redes de modo de transferencia asincrónica (ATM) [1] en UPC y NPC en interfaces usuario-red o interfaces entre redes o interfaces de red a red para proteger una red contra niveles excesivos de tráfico en las conexiones enrutadas a través de ella. El algoritmo genérico de velocidad de celda, o un equivalente, también se puede utilizar para dar forma a las transmisiones mediante una tarjeta de interfaz de red en una red ATM.
Al menos algunas implementaciones del depósito con fugas son una imagen reflejada del algoritmo del depósito 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 dan lo que parecen ser dos algoritmos diferentes, ambos conocidos como algoritmo del cubo con fugas y generalmente sin 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 depósito es un contador o variable independiente del flujo de tráfico o del calendario 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 donde se está realizando la comprobación o se produce un evento, que es equivalente a la forma en que se agrega agua intermitentemente al balde. El contador también disminuye a un ritmo fijo, equivalente a la forma en que el agua se escapa del balde. Como resultado, el valor en el contador representa el nivel del agua en el balde. Si el contador permanece por debajo de un valor límite especificado cuando llega un paquete o se produce un evento, es decir, el depósito 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 velocidad promedio y máxima. Esta versión se denomina aquí cubo con fugas como medidor .
En la segunda versión, el depósito es una cola en el flujo de tráfico. [3] Esta cola se utiliza para controlar directamente ese flujo: los paquetes se ingresan en la cola a medida que llegan, lo que equivale a agregar agua al balde. Luego, estos paquetes se eliminan de la cola ( por orden de llegada ), normalmente a un ritmo fijo, por ejemplo, para su transmisión posterior, equivalente a una fuga de agua del cubo. Esta configuración impone la conformidad en lugar de verificarla, 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 necesariamente carece de ráfagas o fluctuaciones. Entonces, en esta versión, el tráfico en sí es análogo al agua que pasa a través del balde. Esta versión se denomina aquí depósito con fugas como cola .
El balde con fugas como medidor es exactamente equivalente a (una imagen especular de) el algoritmo del balde de fichas , es decir, el proceso de agregar agua al balde con fugas refleja exactamente el de retirar fichas del balde de fichas cuando llega un paquete conforme, el proceso de la fuga de agua del balde que gotea refleja exactamente la de agregar fichas regularmente al balde de fichas, y la prueba de que el balde con fugas no se desbordará es un espejo de la prueba de que el balde de fichas contiene suficientes fichas y no se desbordará . Por lo tanto, dados parámetros equivalentes, los dos algoritmos considerará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 contador. [6]
A Jonathan S. Turner se le atribuye [7] la descripción original del algoritmo de depósito 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 reduce periódicamente. Si el ". [2] El cubo (análogo al contador) se utiliza, 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 medidor del algoritmo, el algoritmo genérico de velocidad de celda , la proporciona el 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 célula equivale a paquete en la descripción de Turner [2], la proporciona el UIT-T de la siguiente manera: "El cubo con fugas de estado continuo puede verse como un cubo de capacidad finita cuyo el contenido de valor real se drena a un ritmo continuo de 1 unidad de contenido por unidad de tiempo y cuyo contenido se incrementa en el incremento T para cada celda conformante... Si a la llegada de una celda el contenido del cubo es menor o igual a el 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 depósito 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 depósito no se modifica. ; es decir, simplemente no se agrega agua si eso haría que el balde se desborde.
David E. McDysan y Darrel L. Spohn comentan la descripción proporcionada por el Foro ITU-T/ATM. En esto, afirman: "En la analogía del cubo con fugas, las celdas [del cajero automático] en realidad no fluyen a través del cubo; sólo lo hace la verificación de la admisión conforme". [6] Sin embargo, poco común en las descripciones de la literatura, McDysan y Spohn también se refieren al algoritmo del depósito con fugas como una cola y continúan: "Tenga en cuenta que una implementación de la configuración del tráfico es hacer que las células fluyan a través del depósito". [6]
Al describir el funcionamiento de la versión del algoritmo del ITU-T, McDysan y Spohn invocan una "noción comúnmente empleada en la teoría de colas de un gremlin ficticio ". [6] Este duende inspecciona el nivel en el cubo y toma medidas si el nivel está por encima del valor límite τ : en la vigilancia de tráfico , abre una trampilla, lo que hace que el paquete que llega se caiga y evita que el agua entre en el balde; en la conformación del tráfico , empuja hacia arriba una aleta, lo que retrasa el paquete que llega y le impide entregar su agua, hasta que el nivel del agua en el cubo cae por debajo de τ .
La diferencia entre las descripciones dadas por Turner y el Foro ITU-T/ATM es que la de Turner es específica de la vigilancia del tráfico, mientras que la descripción del Foro ITU-T/ATM es aplicable tanto a la vigilancia del tráfico como a la configuración del tráfico. Además, Turner no afirma que el contenido del contador sólo deba verse afectado por los paquetes conformes, y sólo debe incrementarse cuando esto no cause que exceda un límite, es decir, Turner no establece explícitamente que la capacidad del depósito o el valor máximo del contador es finito. [nota 2]
Una descripción del concepto de funcionamiento del algoritmo del depósito con fugas como un medidor que se puede utilizar en la vigilancia del tráfico o en la configuración del tráfico puede describirse como un depósito de capacidad fija, asociado con cada conexión virtual o usuario. El balde gotea a un ritmo fijo. Si el balde está vacío, deja de gotear. Para que un paquete se ajuste, tiene que ser posible agregar una cantidad específica de agua al balde. La cantidad específica agregada 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 hace que el balde se desborde, entonces el paquete no se adapta y el agua del balde no cambia.
El cubo con fugas como medidor se puede utilizar tanto para controlar el tráfico como para controlar el tráfico . Por ejemplo, en las redes ATM, en forma de algoritmo genérico de velocidad de celda, se utiliza para comparar el ancho de banda y la ráfaga del tráfico en un canal virtual (VC) o ruta virtual (VP) con los límites especificados en la velocidad a la que pueden llegar células 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 células que no se ajustan a estos límites (células no conformes) pueden descartarse o reducirse su prioridad para que las funciones de gestión del tráfico descendente se eliminen si hay congestión. En la conformación del tráfico, las células se retrasan hasta que se adaptan. La vigilancia del tráfico y la configuración del tráfico se utilizan comúnmente en UPC y NPC para proteger la red contra el tráfico excesivo o con ráfagas excesivas. (Consulte administración del ancho de banda y prevención de congestión ). La configuración del tráfico se usa comúnmente en las interfaces de red de los hosts para evitar que las transmisiones excedan el ancho de banda o los límites de fluctuación y sean descartadas por las funciones de administración del tráfico en la red. (Ver programación (informática) y programador de red ).
El algoritmo del cubo con fugas como medidor también se puede utilizar en un contador de cubos con fugas para medir la tasa de procesos aleatorios (estocásticos) . Se puede utilizar un contador de cubeta con fugas para indicar, mediante su desbordamiento, cuándo la tasa promedio o máxima de eventos aumenta por encima de algún nivel de fondo aceptable. [8] Por ejemplo, un contador de cubos con fugas se puede utilizar para detectar cuándo hay una repentina ráfaga de errores de memoria corregibles o cuando ha habido un aumento gradual, pero significativo, en la tasa promedio, lo que puede indicar una falla de corrección inminente. . [9]
El uso del algoritmo de depósito con fugas en un contador de depósitos con fugas es similar al de la gestión del tráfico, en el sentido de que se utiliza como medidor. Básicamente, los eventos reemplazan a los paquetes en la descripción, y cada evento provoca que se agregue una cantidad de agua al balde. Si el depósito se desborda 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 existe 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, no puede volver a su estado anterior hasta ha transcurrido un período significativamente mayor que el equivalente del intervalo de emisión, que puede verse incrementado por lo que de otro modo serían eventos conformes. Sin embargo, es posible que otras implementaciones no incrementen el contador mientras está desbordado, lo que le permite determinar correctamente si los siguientes eventos se ajustan o no.
En el caso del algoritmo de cubo 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 se puede especificar como una tasa de paquetes, una tasa de bits o como un intervalo de emisión entre los paquetes. Se puede especificar un límite de ráfaga como una tolerancia de variación del retardo o como un tamaño máximo de ráfaga (MBS).
Se pueden aplicar múltiples 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áfaga: consulte Algoritmo genérico de velocidad de celda § Controlador de depósito con fugas dual .
La velocidad a la que se fuga el cubo determinará el límite de ancho de banda, que Turner [2] denomina velocidad promedio y el ITU-T denomina a su inversa intervalo de emisión. Es más fácil explicar cuál es este intervalo en el que los paquetes tienen una longitud fija. Por lo tanto, la primera parte de esta descripción asume esto y las implicaciones de longitudes de paquetes variables se consideran por separado.
Considere un depósito que está exactamente lleno hasta el tope con el tráfico anterior, es decir, cuando ya se ha producido la ráfaga máxima permitida, es decir, el número máximo de paquetes o células acaba de llegar en el tiempo mínimo para que aún se ajusten al ancho de banda y límites de fluctuación. El intervalo mínimo antes de que el siguiente paquete pueda adaptarse es el tiempo que tarda el balde en filtrar exactamente la cantidad de agua entregada por un paquete, y si un paquete se prueba y se ajusta en ese momento, esto llenará exactamente el balde una vez más. . Por lo tanto, una vez que se llena el depósito, la velocidad máxima que los paquetes pueden ajustarse es con este intervalo entre cada paquete.
Turner [2] se refiere a esta tasa como promedio, lo que implica que su inverso es el intervalo promedio. Sin embargo, existe cierta ambigüedad en cuanto a cuál es la tasa promedio y el intervalo. Dado que los paquetes pueden llegar a cualquier velocidad inferior, este es un límite superior, en lugar de un valor fijo, por lo que, en el mejor de los casos, podría denominarse máximo para la velocidad promedio. Además, durante el tiempo que se produce la máxima ráfaga, los paquetes pueden llegar a intervalos más pequeños y, por tanto, a una velocidad mayor. Entonces, para cualquier período menor que infinito, la tasa promedio real puede ser (pero no necesariamente) mayor que esto 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 medio a largo plazo tiende a ser el intervalo de emisión.
Para paquetes de longitud variable, donde la cantidad agregada al depósito 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 depósito debe haber filtrado desde que está lleno para que un paquete se ajuste es la cantidad que agregará el paquete, y si esto es proporcional a la longitud del paquete, también lo será el intervalo entre este y el paquete anterior que llenó el depósito. Por lo tanto, no es posible especificar un intervalo de emisión específico para 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 longitudes de paquetes variables se consideran por separado.
El ITU-T define un valor límite, τ , que es menor que la capacidad del depósito en T (la cantidad en la que se incrementa el contenido del depósito para cada celda conforme), de modo que la capacidad del depósito sea T + τ . Este valor límite especifica cuánto antes puede llegar un paquete de lo que normalmente se esperaría si los paquetes llegaran exactamente con el intervalo de emisión entre ellos.
Imagine la siguiente situación: un balde pierde 1 unidad de agua por segundo, por lo que el valor límite, τ y la cantidad de agua agregada por un paquete, T , están efectivamente en unidades de segundos. Este balde comienza vacío, por lo que cuando un paquete llega al balde, no lo llena completamente agregando su agua T , y el balde ahora está τ por debajo de su capacidad. Entonces, cuando llegue el siguiente paquete, el depósito solo tiene que haberse drenado en T – τ para que se ajuste. Entonces , el intervalo entre estos dos paquetes puede ser hasta τ menor que T.
Esto se extiende a varios paquetes en una secuencia: Imagine lo siguiente: el depósito nuevamente comienza vacío, por lo que el primer paquete que llega claramente se ajusta. Luego, el depósito 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 (el N.ésimo ) paquete se ajuste, el balde debe haber filtrado 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 que se filtró es ( N – 1) × T – τ , lo cual, debido a que la fuga es de una unidad por segundo, tardó exactamente ( N – 1) × T – τ segundos en fugarse. Por lo tanto, el tiempo más corto en el que todos los N paquetes pueden llegar y adaptarse es ( N – 1) × T – τ segundos, que es exactamente τ menos que el tiempo que habría tomado si los paquetes hubieran llegado exactamente en el intervalo de emisión.
Sin embargo, los paquetes solo pueden llegar con intervalos menores que T cuando el paquete anterior no llena el depósito. Si está lleno, entonces el cubo debe haberse drenado en su totalidad T antes de que se conforme el siguiente paquete. Entonces , una vez que los paquetes que llegan a menos de T han utilizado este espacio del depósito , las tramas posteriores deben llegar a intervalos no menores a T. Sin embargo, pueden llegar a intervalos mayores, cuando no llenarán el cubo. Dado que el balde deja de tener fugas cuando está vacío, siempre hay un límite ( τ ) en cuanto a la tolerancia que se puede acumular con 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 (asumiendo que los paquetes se generan sin fluctuaciones). De ahí el uso del término tolerancia de variación del retardo de celda (CDVt) para este parámetro en ATM.
Por ejemplo, una posible fuente de variación del retardo es cuando varias conexiones (flujos de paquetes) se multiplexan juntas en la salida de un conmutador. Suponiendo que la suma de los anchos de banda de estas conexiones sea menor que la de salida, todos los paquetes que lleguen podrán transmitirse, eventualmente. Sin embargo, si sus llegadas son independientes, por ejemplo porque llegan a diferentes entradas del interruptor, entonces varios pueden llegar al mismo tiempo o casi al mismo tiempo. Dado que la salida sólo puede transmitir un paquete a la vez, los demás deben ponerse en cola en un búfer hasta que sea su turno de transmitirse. Luego, este búfer introduce un retraso adicional entre que un paquete llega a una entrada y es transmitido por la salida, y este retraso varía dependiendo de cuántos otros paquetes ya están en cola en el búfer. Puede ocurrir una situación similar en la salida de un host (en la NIC) 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.
Para paquetes de longitud variable, donde la cantidad de agua agregada por un paquete determinado es proporcional a su longitud, τ no puede verse como un límite de qué tan lleno 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 lleva pasar de este nivel a vaciarse sigue siendo cuánto antes de lo esperado puede llegar un paquete, cuando los paquetes 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 la que puede tolerarse y, por tanto, la tolerancia en la variación del retraso máximo.
El valor límite o tolerancia a la variación del retraso también controla cuántos paquetes pueden llegar en una ráfaga, determinado por el exceso de profundidad del depósito 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 MBS y derivar el valor límite τ de esto o especificarlo como un valor límite/tolerancia de variación de fluctuación/retardo, y derivar el MBS de este.
Una ráfaga o 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 de la ráfaga llegarán uno tras otro. Sin embargo, al igual que en ATM, la tolerancia se puede aplicar a una tasa más baja, en ese caso la Tasa de Celda Sostenible (SCR), y la ráfaga de paquetes (celdas) puede llegar a una tasa más alta, pero menor que la tasa de línea del capa física, en ese caso, la Peak Cell Rate (PCR). El MBS puede entonces ser el número de células necesarias para transportar un paquete de capa superior (ver segmentación y reensamblaje ), donde los paquetes se transmiten con un ancho de banda máximo determinado por el SCR y las células dentro de los paquetes se transmiten en el PCR; permitiendo así que la última celda del paquete, y el paquete en sí, lleguen significativamente antes de lo que lo harían si las celdas se enviaran en el 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 a los recursos compartidos, por ejemplo, buffers de salida de conmutación, que la transmisión en el SCR y, por lo tanto, es más probable que produzca desbordamientos de buffer y congestión de la red. Sin embargo, supone una carga menor para estos recursos que la transmisión en el SCR con un valor límite, τ SCR , que permite que las células MBS se transmitan y lleguen consecutivas 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: si el depósito comienza vacío, el primer paquete en llegar agregará T , pero si, cuando llegue el siguiente paquete, el contenido es por debajo de τ , esto también se ajustará. Suponiendo que cada paquete tarda δ en llegar, entonces si τ (expresado como el tiempo que tarda el cubo en vaciarse del valor límite) es igual o mayor que el intervalo de emisión menos el tiempo mínimo entre llegadas, T – δ , el segundo paquete se conformará 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 a la fluctuación de fase, τ ; y el tiempo necesario para transmitir/recibir un paquete, δ , como sigue: [4]
Asimismo, el valor mínimo de tolerancia a la fluctuación de fase τ 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 SCR, en la ecuación anterior, el tiempo que tarda cada paquete en llegar, δ , es el intervalo de emisión para las células en el PCR T PCR , y el intervalo de emisión, T , es el intervalo de emisión del SCR T SCR . Cuando MBS debe ser el número de células necesarias para transportar un paquete segmentado, el valor límite anterior, τ , debe ser el de SCR τ SCR . Sin embargo, en la UNI o una NNI, donde las células de la PCR habrán estado sujetas a variación de retardo, debería ser el valor límite para la SCR más el de la PCR τ SCR + τ PCR .
Para paquetes de longitud variable, el tamaño máximo de ráfaga dependerá de las longitudes de los paquetes en 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 depósito con fugas a veces se contrasta con el algoritmo del depósito de tokens . Sin embargo, el concepto anterior de funcionamiento del cubo con fugas como medidor puede compararse directamente con el algoritmo del cubo de tokens, 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 puede verse, estas dos descripciones son esencialmente imágenes especulares entre sí: una agrega algo al depósito de forma regular y quita algo para conformar paquetes hasta un límite de cero; el otro quita periódicamente y añade para conformar paquetes hasta un límite de la capacidad del cubo. Entonces, ¿una implementación que agrega tokens para un paquete conforme y los elimina a una velocidad fija es una implementación del depósito con fugas o del depósito de tokens? De manera similar, ¿qué algoritmo se utiliza en una implementación que elimina agua de un paquete conforme y agrega agua a una velocidad fija? De hecho, ambos son efectivamente iguales, es decir, implementaciones tanto del depósito con fugas como del depósito de tokens, ya que son el mismo algoritmo básico descrito de manera 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 con fugas y de depósito de tokens resultan, por tanto, enteramente de las diferencias en las implementaciones, es decir, no surgen de diferencias en los algoritmos subyacentes.
Los puntos a tener en cuenta son que el algoritmo de depósito con fugas, cuando se utiliza como medidor, puede permitir un flujo de paquetes de salida conforme con fluctuación o ráfagas, se puede utilizar en la vigilancia del tráfico y en la configuración, y se puede implementar para paquetes de longitud variable.
El depósito con fugas como cola es esencialmente una forma de describir un búfer o cola FIFO simple que recibe servicio a una velocidad fija para eliminar ráfagas o fluctuaciones. Andrew S. Tanenbaum , en (una versión anterior de) su libro Computer Networks, da una descripción del mismo como "El cubo con fugas consiste en una cola finita. Cuando llega un paquete, si hay espacio en la cola, se agrega a él". 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 depósito con fugas como cola es siempre una forma de función de configuración del tráfico.
Como puede verse, esta implementación está restringida en el sentido de que los paquetes sólo 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 intenso sea el tráfico [de entrada]". [10] Sin embargo, esta afirmación sólo es estrictamente cierta siempre y cuando la cola no quede vacía: si la tasa de llegada promedio es menor que la tasa de tics del reloj, o si la entrada está lo suficientemente ráfaga como para que las pérdidas aceleren la tasa de El resto por debajo de la velocidad 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 quedar vacía), habrá espacios en el flujo de salida.
Una restricción adicional es que el depósito con fugas como función de configuración del 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 de paquetes. Considerando que, cuando se utiliza un medidor de cubeta con fugas para controlar la transmisión, un paquete se transmite tan pronto como se ajusta, es decir, en relación con el anterior o, si ya se ajusta, con su hora de llegada; no según algún reloj local arbitrario. Perversamente, en el contexto del retraso de transferencia, esta imposición de una fase fija que, con el tiempo, puede diferir de la de un flujo de paquetes de entrada que de otro modo se ajustaría, constituye una variación del retraso y, por tanto, una fluctuación. La fluctuación causada de esta manera particular solo se puede observar cuando 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 configuración de la 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 el tráfico que da forma a las 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 lo es para los paquetes de longitud fija. Tanenbaum da una descripción de un depósito con fugas de "recuento de bytes" para paquetes de longitud variable de la siguiente manera: "En cada tic, un contador se inicializa en n. Si el primer paquete en la cola tiene menos bytes que el valor actual del contador, se transmite y el contador disminuye 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 que el contador cae por debajo de la longitud del siguiente paquete en la cola. siguiente tic, momento en el cual el recuento de bytes residuales 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 transmisiones, lo que resulta en retrasos variables de extremo a extremo e inadecuada para la configuración del tráfico en tiempo real.
El depósito con fugas como cola solo se puede utilizar para configurar el tráfico a un ancho de banda específico sin fluctuaciones en la salida. [10] Puede usarse dentro de la red, por ejemplo, como parte de la gestión del ancho de banda, pero es más apropiado para la configuración del tráfico en las interfaces de red de los hosts. El algoritmo Leaky Bucket se utiliza en el módulo ngx_http_limit_conn_module de Nginx para limitar el número 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 se puede especificar 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 sólo a intervalos fijos, habrá muchos casos en los que el volumen de tráfico será muy bajo y grandes porciones de los recursos de la red (en particular el ancho de banda) no se utilizarán. Por lo tanto, no existe ningún mecanismo en la implementación del depósito con fugas como cola para permitir que los flujos individuales alcancen la velocidad del puerto, consumiendo efectivamente recursos de la red en momentos en 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 depósito con fugas muestra que la versión como cola es un caso especial de la versión como medidor.
Imagine una función de configuración del 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. Imaginemos también que el cubo de 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 a intervalos del intervalo de emisión, cuando se transmite el paquete al principio de la cola y se agrega su agua. Luego, esta agua se escapa durante el siguiente intervalo de emisión (o se elimina justo antes de realizar la siguiente prueba de conformidad), permitiendo 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 depósito de tokens con la misma profundidad, donde se agregan suficientes tokens para un paquete (si el depósito no está lleno) en los intervalos de emisión. Luego, 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 (integrales) del intervalo de emisión.
Sin embargo, la implementación del depósito con fugas como un medidor (o depósito de tokens) en una función de configuración del tráfico descrita anteriormente es un equivalente exacto a la descripción del depósito con fugas como una cola: [3] el elemento de retraso de la versión del medidor es el depósito de la versión de la cola; el cubo de la versión con 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 depósito con fugas como cola es un caso especial de una función de conformación del tráfico que utiliza un depósito con fugas (o depósito de tokens) como medidor en el que el valor límite, τ , es cero y el proceso de conformidad de las pruebas se realiza al ritmo más bajo posible.
El cubo con fugas como cola para paquetes de longitud variable también puede describirse como equivalente a un caso especial del cubo con fugas como un medidor. La implementación sugerida [3] puede, al igual que la implementación de longitud fija, verse como una función de configuración del tráfico en la que la cola es un elemento de retraso, en lugar del depósito, y la función que da servicio a la cola, en este caso, se proporciona explícitamente como un depósito de tokens: se reduce para los paquetes conformes y se incrementa a una velocidad fija. Por lo tanto, como el depósito con fugas como medidor y el depósito de tokens son equivalentes, el depósito con fugas como cola para longitudes de paquetes variables también es un caso especial de una función de configuración del tráfico que utiliza un depósito con fugas (o depósito de tokens) como medidor.
Hay una consecuencia interesante de ver el depósito con fugas como una cola para paquetes de longitudes variables como una implementación específica del depósito de tokens o el depósito con fugas como un medidor en la configuración del tráfico. Esto es que el depósito del medidor tiene una profundidad, n, y, como siempre es el caso con el depósito 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 el paquetes). Por lo tanto, es posible cuantificar la ráfaga de la salida de este depósito con fugas de "conteo de bytes" como un metro, a menos que todos los paquetes tengan la longitud máxima cuando 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.
