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 tasa promedio a la que se vierte el agua excede la tasa a la que gotea el balde o si hay 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 a estos eventos a estas tasas o retrasarlas hasta que se ajusten a las tasas. También se puede utilizar para verificar la conformidad o limitar a una tasa promedio solamente, es decir, eliminar cualquier variación del promedio.
Se utiliza en la conmutación de paquetes de redes informáticas y de telecomunicaciones redes, tanto en el tráfico policiales y conformación de tráfico de las transmisiones de datos , en forma de paquetes , [nota 1] a límites definidos en ancho de banda y explosividad (una medida de la irregularidad o variaciones en el flujo de tráfico ). También se puede utilizar como un algoritmo de programación para determinar la sincronización de las transmisiones que cumplirán con los límites establecidos para el ancho de banda y la ráfaga aplicada por la red: consulte el programador de la red . [1] [2] [3] [4] Se recomienda una versión del balde con fugas, el algoritmo genérico de velocidad de celda , para redes de modo de transferencia asíncrona (ATM) [5] en Control de parámetros de red / uso 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 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 de una tarjeta de interfaz de red en una red ATM (es decir, en el lado del usuario de la interfaz usuario-red), por ejemplo, a niveles por debajo de los niveles establecidos para Uso / Control de parámetros de red en la red para evitar que se tomen medidas para limitar aún más esa conexión. El algoritmo de cubeta con fugas también se utiliza en contadores de cubetas con fugas, por ejemplo, para detectar cuándo la tasa promedio o máxima de eventos aleatorios o estocásticos o procesos estocásticos , como fallas o fallas, exceden los límites definidos.
Al menos algunas implementaciones del depósito con fugas son una imagen reflejada del algoritmo Token Bucket y, dados los parámetros equivalentes, determinarán exactamente la misma secuencia de eventos para ajustarse o no a los mismos límites. Sin embargo, hay al menos dos descripciones diferentes del balde con fugas que pueden y han causado confusión. [1] [2] [6]
Descripción general
En la literatura se describen dos métodos diferentes de aplicar esta analogía del balde con fugas. [1] [2] [3] [4] Estos dan lo que parecen ser dos algoritmos diferentes, los cuales se conocen como el algoritmo del balde con fugas y generalmente sin referencia al otro método. Esto ha generado confusión sobre qué es el algoritmo de cubeta con fugas y cuáles son sus propiedades.
En una versión de la aplicación de la analogía, el análogo del cubo es un contador o variable, separado del flujo de tráfico o la programación de eventos. [1] [3] [4] 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 ocurre un evento, que es equivalente a la forma en que se agrega agua de forma intermitente al balde. El contador también se reduce a una tasa fija, 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 cubo análogo. Si el contador permanece por debajo de un valor límite especificado cuando llega un paquete o ocurre 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 tasa promedio y pico. Entonces, en esta versión, el análogo del agua es transportado por los paquetes o los eventos, agregado al balde cuando llegan o ocurren, y luego se escapa. Esta versión se conoce aquí como el cubo con fugas como medidor .
En la segunda versión, el análogo del cubo es una cola en el flujo de tráfico. [2] Esta cola se usa para controlar directamente ese flujo: los paquetes se ingresan en la cola a medida que llegan, equivalente al agua que se agrega al balde. A continuación, estos paquetes se retiran de la cola (por orden de llegada ), normalmente a una velocidad fija, por ejemplo, para su transmisión, equivalente a una fuga de agua del cubo. Como resultado, la velocidad a la que se atiende la cola controla directamente la velocidad de transmisión del tráfico. Por lo tanto, impone conformidad en lugar de verificarla, y cuando la cola recibe servicio a una tasa fija (y donde los paquetes tienen todos la misma longitud), el flujo de tráfico resultante está necesariamente desprovisto de ráfagas o fluctuaciones. Entonces, en esta versión, el tráfico en sí es el análogo del agua que pasa por el cubo. No está claro cómo esta versión de aplicar la analogía podría usarse para verificar las tasas de eventos discretos. Esta versión se conoce aquí como el depósito con fugas como cola .
El balde con fugas como medidor es exactamente equivalente a (una imagen reflejada de) el algoritmo del balde de fichas , es decir, el proceso de agregar agua al balde con fugas refleja exactamente el de retirar las fichas del balde de fichas cuando llega un paquete conforme, el proceso de la fuga de agua del balde con fugas refleja exactamente la de agregar regularmente tokens al balde de tokens, y la prueba de que el balde con fugas no se desbordará es un espejo de la prueba de que el balde de tokens contiene suficientes tokens y no se `` desbordará ''. Por lo tanto, dados los parámetros equivalentes, los dos algoritmos verán el mismo tráfico como conforme o no conforme. El balde con fugas como cola puede verse como un caso especial del balde con fugas como medidor. [6]
Como un metro
A Jonathan S. Turner se le atribuye [7] la descripción original del algoritmo del 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 contador supera un umbral al incrementarse, la red descarta el paquete. El usuario especifica la velocidad a la que se reduce el contador (esto determina el ancho de banda medio) y el valor del umbral (una medida de ráfaga) ". [1] 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 , está dada por el UIT-T en la recomendación I.371 y en la Especificación UNI del Foro ATM . [3] [4] La descripción, en la que el término celda es equivalente a paquete en la descripción de Turner [1], viene dada por el UIT-T de la siguiente manera: "La cubeta con fugas de estado continuo puede verse como una cubeta de capacidad finita cuyo el contenido de valor real se drena a una tasa continua de 1 unidad de contenido por unidad de tiempo y cuyo contenido se incrementa en el incremento T para cada celda conforme ... 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 + τ ) ". [4] Estas especificaciones también establecen que, debido a su capacidad finita, si el contenido de la cubeta 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, la cubeta no se modifica. ; es decir, el agua simplemente no se agrega si haría que el balde se desborde.
David E. McDysan y Darrel L. Spohn comentan la descripción dada por el Foro UIT-T / ATM. En esto, afirman "En la analogía de la cubeta con fugas, las células [ATM] no fluyen realmente a través de la cubeta; solo lo hace la verificació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 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 cubo". [6]
Al describir el funcionamiento de la versión del algoritmo del UIT-T, McDysan y Spohn invocan una "noción comúnmente empleada en la teoría de las 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 vigilancia (figura 2), abre una trampilla, lo que hace que el paquete que llega se caiga y detiene el agua. de entrar en el balde; al dar forma (figura 3), empuja hacia arriba una solapa, lo que retrasa la llegada del paquete e impide que entregue su agua, hasta que el nivel del agua en el balde desciende por debajo de τ .
La diferencia entre las descripciones dadas por Turner y el Foro UIT-T / ATM es que el de Turner es específico para la vigilancia del tráfico , mientras que el Foro UIT-T / ATM es aplicable tanto a la vigilancia del tráfico como a la configuración del tráfico. Además, Turner no establece que el contenido del contador solo debería verse afectado por los paquetes conformes, y solo debería incrementarse cuando esto no provoque que exceda un límite, es decir, Turner no declara explícitamente que la capacidad del depósito o el valor máximo del contador es finito. Para que la descripción de Turner esté claramente alineada con ITU-T, la declaración "Si el contador excede un umbral al ser incrementado, la red descarta el paquete" tendría que cambiarse a algo como "Si el contador excedería un umbral [equivalente al profundidad del cubo, T + τ , en la descripción UIT-T] al incrementarse, la red descarta el paquete y el contador no se incrementa ", es decir, solo se incrementa cuando es menor o igual al valor límite, τ , o al menos T menos que la profundidad del cucharón en la descripción del UIT-T.
Si bien la descripción proporcionada por Turner no establece que el contador solo debería verse afectado por los paquetes conformes, se da en términos de una función de control de tráfico, donde el exceso de celo en limitar una conexión que contiene paquetes no conformes puede no ser un problema. De hecho, en algunos contextos, como las transmisiones de tasa de bits variable (VBR), la pérdida de cualquier paquete puede corromper la totalidad de un mensaje de capa superior, por ejemplo, una PDU de capa de red OSI. En cuyo caso, descartar todos los siguientes paquetes de esa PDU dañada arroja una carga de red innecesaria. Sin embargo, sería completamente inaceptable en la configuración del tráfico que un paquete que no pasa la prueba de conformidad afecte el tiempo antes de que ocurra la conformidad, es decir, si el acto de probar la conformidad de un paquete posterior cambiaría el tiempo que tiene un paquete que actualmente espera cumplir. esperar. Esto es exactamente lo que sucedería si el agua de los paquetes no conformes se añadiera al balde, ya que cualquier paquete no conforme posterior elevaría el nivel del agua y, por lo tanto, haría que un paquete que espera para ajustarse espere más tiempo.
Ni Turner ni el UIT-T abordan el tema de los paquetes de longitud variable. Sin embargo, la descripción según ITU-T es para las células ATM, que son paquetes de longitud fija, y Turner no excluye específicamente los paquetes de longitud variable. Por lo tanto, en ambos casos, si la cantidad en la que se incrementa el contenido del depósito o el contador para un paquete conforme es proporcional a la longitud del paquete, ambos tendrán en cuenta la longitud y permitirán que el algoritmo limite el ancho de banda del tráfico explícitamente en lugar de limitar la tasa de paquetes. Por ejemplo, los paquetes más cortos agregarían menos al contenedor y, por lo tanto, podrían llegar a intervalos más pequeños; mientras que los paquetes más largos agregarían más y, por lo tanto, tendrían que estar separados por intervalos proporcionalmente más grandes para adaptarse.
Concepto de funcionamiento
Una descripción del concepto de funcionamiento del algoritmo de cubeta con fugas como un medidor que se puede utilizar en la vigilancia del tráfico o en la configuración del tráfico, se puede establecer de la siguiente manera:
- Un segmento de capacidad fija, asociado con cada conexión virtual o usuario, tiene fugas a una tasa fija.
- Si el balde está vacío, deja de gotear.
- Para que un paquete se ajuste, debe 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 exceda su capacidad, el paquete no se ajusta y el agua del balde no se modifica.
Usos
La cubeta con goteo como un metro se puede utilizar en cualquiera de conformación de tráfico o políticas de tráfico . Por ejemplo, en las redes ATM, en la forma del 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 las 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 (descartarse) o reducir su prioridad (para que las funciones de gestión de tráfico descendentes caigan si hay congestión). En la configuración del tráfico, las células se retrasan hasta que se ajustan. La vigilancia del tráfico y la configuración del tráfico se utilizan comúnmente en UPC / NPC para proteger la red contra el tráfico excesivo o con ráfagas excesivas, consulte la gestión del ancho de banda y la prevención de la congestión . El modelado del tráfico se usa 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 administración del tráfico en la red. (Consulte programación (informática) y programador de red ).
El algoritmo del balde con fugas como medidor también se puede utilizar en un contador de baldes con fugas para medir la tasa de procesos estocásticos o aleatorios . Se puede usar un contador de cubos con fugas para detectar cuándo la tasa promedio o máxima de eventos aumenta por encima de un nivel de fondo aceptable, es decir, cuando el cubo se desborda. [8] Sin embargo, los eventos que no causan un desbordamiento, es decir, tienen tasas suficientemente bajas y están bien distribuidos en el tiempo, pueden ignorarse. Por ejemplo, un contador de baldes con fugas de este tipo se puede utilizar para detectar cuando hay una explosión repentina de errores de memoria corregibles o cuando ha habido un aumento gradual, pero significativo, en la tasa promedio, lo que puede indicar una falla inminente, [9] etc.
El uso del algoritmo del balde con fugas en un contador de baldes con fugas es similar al de la gestión del tráfico, ya que se utiliza como medidor. Esencialmente, los eventos reemplazan los paquetes en la descripción, y cada evento provoca que se agregue una cantidad de agua al balde. Si el depósito se desbordara como resultado del evento, 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, [1] 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 superado el umbral, es posible que no vuelva a su estado anterior hasta ha pasado 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.
Parámetros
En el caso del algoritmo de cubeta con fugas como medidor, los límites del tráfico pueden ser un ancho de banda y una ráfaga de la salida. [3] [4] [nota 2]
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 un paquete o velocidad de cuadros, un byte o velocidad de bits , o como un intervalo de emisión entre los paquetes. Un límite de la ráfaga puede especificarse como una tolerancia a la variación de la fluctuación o el 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 varias instancias del algoritmo de depósito con fugas, cada una de las cuales puede requerir un ancho de banda y un límite de ráfagas: consulte Controlador de depósito con fugas dual .
Intervalo de emisión
La velocidad a la que el depósito gotea determinará el límite de ancho de banda, que Turner [1] denomina velocidad media y la inversa de la cual se denomina intervalo de emisión en el UIT-T. Es más fácil explicar cuál es este intervalo cuando los paquetes tienen una longitud fija. Por tanto, la primera parte de esta descripción asume esto, y las implicaciones de las longitudes variables de los paquetes se consideran por separado.
Considere un depósito que se llena exactamente hasta el tope por el tráfico anterior, es decir, cuando ya se ha producido la máxima ráfaga permitida, es decir, el número máximo de paquetes o células acaba de llegar en el tiempo mínimo para que todavía se ajusten al ancho de banda y límites de jitter. El intervalo mínimo antes de que el siguiente paquete pueda ajustarse 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 cumple 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 a la que pueden ajustarse los paquetes es con este intervalo entre cada paquete.
Turner [1] 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 cuanto a cuál es la tasa y el intervalo promedio. Dado que los paquetes pueden llegar a cualquier tasa más baja, este es 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 con intervalos más pequeños y, por lo tanto, con una velocidad mayor que ésta. 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 tanto, debido a esta ambigüedad, el término intervalo de emisión se utiliza en lo sucesivo. 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 cubo es proporcional a la longitud del paquete, la velocidad máxima a la que pueden ajustarse varía de acuerdo con su longitud: la cantidad que el cubo debe haber goteado por completo para que un paquete se ajuste es el cantidad que agregará el paquete, y si esto es proporcional a la longitud del paquete, también lo es el intervalo entre este y el paquete anterior que llenó el depósito. Por 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.
Tolerancia de variación de retardo
Es más fácil explicar cuál es esta tolerancia cuando los paquetes tienen una longitud fija. Por tanto, la primera parte de esta descripción asume esto, y las implicaciones de las longitudes variables de los paquetes se consideran por separado.
El UIT-T define un valor límite, τ , que es menor que la capacidad del balde en T (la cantidad en la que se incrementa el contenido del balde para cada celda conforme), de modo que la capacidad del balde es 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 tiene una fuga de 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 llena completamente el balde agregando su agua T , y el balde ahora está τ por debajo de su capacidad. Entonces, cuando llega el siguiente paquete, el cubo solo tiene que haber sido drenado por T - τ para que esto se ajuste. Por lo que el intervalo entre estos dos paquetes puede ser tanto como τ menor que T .
Esto se extiende a varios paquetes en una secuencia: Imagine lo siguiente: el depósito comienza nuevamente vacío, por lo que el primer paquete que llegue debe cumplir. Entonces, el depósito se llena exactamente después de que varios paquetes conformes, N , hayan llegado en el tiempo mínimo posible para que se ajusten. Para que el último paquete (el N- ésimo) se adapte, el balde debe haber filtrado suficiente agua de los N - 1 paquetes anteriores (( N - 1) * T segundos de valor) para que esté exactamente en el valor límite τ en este momento. Por lo tanto, el agua que se filtra es ( N - 1) T - τ , que debido a que la fuga es de una unidad por segundo, tomó exactamente ( N - 1) T - τ segundos en filtrarse. Por lo tanto, el tiempo más corto en el que todos los N paquetes pueden llegar y conformarse es ( N - 1) T - τ segundos, que es exactamente τ menos que el tiempo que habría tomado si los paquetes hubieran estado llegando exactamente al intervalo de emisión.
Sin embargo, los paquetes solo pueden llegar con intervalos inferiores a T cuando el paquete anterior no llena el depósito. Si es así, entonces el balde debe haberse drenado por la cantidad total T antes de que el siguiente paquete se ajuste. Así que una vez que esta tolerancia se ha utilizado por los paquetes que llegan a menos de T , cuadros subsiguientes deben llegar a intervalos de no menos de t . Sin embargo, pueden llegar a intervalos mayores, cuando no llenen el balde. Cuando esto ha sucedido, los paquetes pueden, nuevamente, llegar con intervalos menores que T hasta que la tolerancia se agote nuevamente. Sin embargo, dado que el balde deja de gotear cuando está vacío, siempre hay un límite ( τ ) a la cantidad de tolerancia que pueden acumular estos intervalos mayores que T , sin embargo, pueden ser mucho mayores que T o, sin embargo, muchos de ellos. existen.
Dado que el valor límite τ define cuánto antes puede llegar un paquete de lo que se esperaría, es el límite de la diferencia entre los retrasos máximos y mínimos desde la fuente hasta el punto donde se realiza la prueba de conformidad (asumiendo que los paquetes se generan sin jitter). De ahí el uso del término tolerancia de variación de retardo de celda (CDVt) para este parámetro en ATM.
Por ejemplo, una posible fuente de variación del retardo es cuando se multiplexan varias conexiones (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 de la salida, todos los paquetes que llegan se pueden transmitir eventualmente. Sin embargo, si sus llegadas son independientes, por ejemplo, porque llegan a diferentes entradas del conmutador, entonces pueden llegar varias o casi al mismo tiempo. Dado que la salida solo puede transmitir un paquete a la vez, los otros deben estar en cola en un búfer hasta que sea su turno para ser transmitidos. Este búfer introduce un retraso adicional entre un paquete que 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. Una situación similar puede ocurrir 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 dado es proporcional a su longitud, τ no puede verse como un límite de cuán lleno puede estar el cubo cuando llega un paquete, ya que esto varía según el tamaño del paquete. . Sin embargo, el tiempo que se tarda en pasar de este nivel al vacío sigue siendo cuánto antes puede llegar un paquete de lo esperado, 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 retardo de transferencia hasta el punto en el que se está aplicando la prueba de conformidad lo que se puede tolerar y, por lo tanto, la tolerancia en la variación máxima del retardo.
Tamaño máximo de ráfaga
El valor límite o la 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 depósito sobre la capacidad requerida para un solo paquete. Por lo tanto, MBS es también una medida de ráfagas o fluctuaciones, y es posible especificar la ráfaga como un 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 esto.
Una ráfaga o grupo de paquetes pueden llegar a un ritmo mayor que el determinado por la emisión intervalo 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 lleguen uno tras otro. Sin embargo, como 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 mayor, pero menor que la tasa de línea del capa física, en ese caso el Peak Cell Rate (PCR). El MBS puede ser entonces 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í, llegue significativamente antes de lo que lo haría si las celdas fueran enviadas al SCR: duración de transmisión = (MBS-1) / PCR en lugar de (MBS-1) / SCR. Esta ráfaga en el PCR coloca una carga significativamente mayor en los recursos compartidos, por ejemplo, los búferes de salida de conmutación, que la transmisión en el SCR y, por lo tanto, es más probable que provoque desbordamientos de búfer y congestión de la red. Sin embargo, coloca una carga menor en estos recursos que la que se transmitiría en el SCR con un valor límite, τ SCR , que permite que las células MBS se transmitan y lleguen una tras otra a la velocidad de la 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 desde vacío, el primer paquete en llegar agregará T , pero si, para 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 depósito 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 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 máxima tolerancia a la fluctuación de fase, τ ; y el tiempo necesario para transmitir / recibir un paquete, δ , como sigue: [3]
Del mismo modo, el valor mínimo de la tolerancia a la fluctuación de fase τ que da un MBS específico se puede calcular a partir del MBS de la siguiente manera: [3]
En el caso de ATM, donde técnicamente MBS solo se relaciona con la tolerancia de 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 la PCR T PCR , y el intervalo de emisión, T , es el intervalo de emisión para el SCR T SCR . Cuando MBS sea el número de células necesarias para transportar un paquete segmentado, el valor límite en lo anterior, τ , debería ser el del SCR τ SCR . Sin embargo, en el UNI o en un NNI, donde las células en la PCR se habrán sometido a una 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 hay 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.
Comparación con el algoritmo token bucket
El algoritmo de depósito con fugas a veces se contrasta con el algoritmo de depósito de tokens . Sin embargo, el concepto de operación anterior para el balde con fugas como medidor puede compararse directamente con el algoritmo del balde de fichas, cuya descripción se da en ese artículo de la siguiente manera:
- Se agrega un token al depósito cada 1 / r segundos.
- El cubo puede contener como máximo b fichas. Si llega una ficha cuando el depósito está lleno, se descarta.
- Cuando llega un paquete ( PDU de capa de red ) [ sic ] [nota 1] de "n" bytes, se eliminan n tokens del depósito y el paquete se envía a la red.
- Si hay menos de n tokens disponibles, no se eliminan tokens del depósito y el paquete se considera no conforme.
Esto se puede comparar con el concepto de funcionamiento, repetido desde arriba:
- Un segmento de capacidad fija, asociado con cada conexión virtual o usuario, tiene fugas a una tasa fija.
- Si el balde está vacío, deja de gotear.
- Para que un paquete se ajuste, debe 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 exceda su capacidad, el paquete no se ajusta y el agua del balde no se modifica.
Como se puede ver, estas dos descripciones son esencialmente imágenes espejo una de la otra: una agrega algo al cubo de forma regular y quita algo para que los paquetes se ajusten hasta un límite de cero; el otro quita regularmente y agrega 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 tasa fija es una implementación del contenedor con fugas o del contenedor de tokens? De manera similar, ¿qué algoritmo se usa en una implementación que elimina el agua de un paquete conforme y agrega agua a una tasa fija? De hecho, ambos son efectivamente lo mismo, es decir, implementaciones tanto del depósito con fugas como del depósito de fichas, ya que son el mismo algoritmo básico descrito de manera diferente. Esto explica por qué, dados los parámetros equivalentes, los dos algoritmos verán exactamente los mismos paquetes como conformes o no conformes. Por tanto, las diferencias en las propiedades y el rendimiento de las implementaciones de los algoritmos de depósito con fugas y token resultan 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 cubeta con fugas, cuando se usa como medidor, puede permitir un flujo de paquetes de salida conforme con fluctuación o ráfagas, se puede usar en la vigilancia del tráfico, así como en la conformación, y se puede implementar para paquetes de longitud variable.
Como una cola
El depósito con fugas como cola es esencialmente una forma de describir una cola o búfer FIFO simple que recibe servicio a una velocidad fija para eliminar las explosiones o la fluctuación. 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 la cola; de lo contrario, se descarta. Con cada tic del reloj se transmite un paquete (a menos que la cola esté vacía) ". [2] Por lo tanto, una implementación del depósito con fugas como una cola es siempre una forma de función de configuración del tráfico.
Como puede verse, esta implementación está restringida porque los paquetes solo se transmiten a una velocidad fija. Para subrayar esto, Tanenbaum también afirma que "El algoritmo de cubeta con fugas impone un patrón de salida rígido a la tasa promedio, sin importar cuán ráfagas sea el tráfico [de entrada]". [10] Sin embargo, esta afirmación solo es estrictamente cierta siempre que la cola no se vacíe: si la tasa de llegada promedio es menor que la tasa de tic del reloj, o si la entrada es lo suficientemente ráfaga como para que las pérdidas traigan la tasa de resto por debajo de la frecuencia de tic 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 se vacíe), habrá espacios en el flujo de salida.
Una restricción adicional es que el depósito con fugas como función de modelado de tráfico de cola solo transmite paquetes en los ticks; por 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 hacia adelante. Considerando que, cuando se utiliza un medidor de cubeta con fugas para controlar la transmisión en curso, un paquete se transmite tan pronto como se ajusta, es decir, en relación con el anterior o, si ya cumple, su hora de llegada; no según algún reloj local arbitrario. De manera perversa, en el contexto del retardo de transferencia, esta imposición de una fase fija que puede, con el tiempo, diferir de la de un flujo de paquetes de entrada de otro modo conforme, constituye una variación de retardo y, por tanto, una fluctuación. La fluctuación de fase provocada de esta manera en particular solo se pudo observar cuando la demora se mide como el tiempo de tránsito entre dos puntos de medición separados, uno a cada lado del cubo con fugas como 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 un extremo a otro el que determina la latencia de los datos recibidos. Por lo tanto, el depósito con fugas como cola no es adecuado para las transmisiones en tiempo real que configuran el tráfico.
Limitar los paquetes de longitud variable utilizando el algoritmo de cubeta con fugas como una 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 "recuento de bytes" para paquetes de longitud variable de la siguiente manera: "En cada tic, se inicializa un contador en n. Si el primer paquete de la cola tiene menos bytes que el valor actual del contador, se transmite, y el contador se reduce en ese número 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 siguiente tick, momento en el que el recuento de bytes residuales se restablece [an] y el flujo puede continuar ". [2] 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 variables de extremo a extremo y en la inadecuación para la configuración del tráfico en tiempo real.
Usos
El depósito con fugas como cola solo se puede utilizar para configurar el tráfico a un ancho de banda especificado 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 configurar el tráfico en las interfaces de red de los hosts.
Parámetros
En el caso del algoritmo de depósito con fugas como una cola, el único límite definido para este algoritmo es el ancho de banda de su salida. [10] [nota 2]
El límite de ancho de banda para la conexión se puede especificar en un contrato de tráfico . Un límite de ancho de banda puede especificarse como un paquete o velocidad de cuadros, un byte o velocidad de bits , o como un intervalo de emisión entre los paquetes.
Ineficacia
La implementación del depósito con fugas como una cola no utiliza los recursos de red disponibles de manera eficiente. Debido a que transmite paquetes solo a intervalos fijos, habrá muchos casos en los que el volumen de tráfico sea muy bajo y no se estén utilizando grandes porciones de recursos de red (ancho de banda en particular). Por lo tanto, no existe ningún mecanismo en la implementación del depósito con fugas como una cola para permitir que los flujos individuales aumenten a la velocidad del puerto, consumiendo efectivamente los recursos de la red en momentos en que no habría contención de recursos en la red. Sin embargo, las implementaciones de la cubeta de fichas y la cubeta con fugas como un medidor permiten que los flujos de tráfico de salida tengan características de ráfagas.
Comparación entre las dos versiones
El análisis de las dos versiones del algoritmo del balde 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, al que se le da servicio utilizando un depósito con fugas como medidor. Imagine también que el cubo de este medidor tiene una profundidad igual a la cantidad agregada 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. Esta agua luego se escapa 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 contenedor de tokens con la misma profundidad, donde se agregan suficientes tokens para un paquete (si el contenedor no está lleno) en los intervalos de emisión. Esta implementación luego recibirá paquetes con un patrón de llegada en ráfagas (limitado por la profundidad de la cola) y los transmitirá a intervalos que son siempre múltiplos exactos (integrales) del intervalo de emisión.
Sin embargo, la implementación del cubo con fugas como medidor (o cubo simbólico) en una función de configuración del tráfico descrita anteriormente es un equivalente exacto a la descripción del cubo con fugas como una cola: [2] 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 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 marca. Por lo tanto, para paquetes de longitud fija, la implementación del depósito con fugas como una cola es un caso especial de una función de modelado de tráfico que utiliza un depósito con fugas (o depósito de fichas) 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 una cola para paquetes de longitud variable también se puede describir como equivalente a un caso especial del cubo con fugas como un metro. La implementación sugerida [2] 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 retraso, en lugar del depósito, y la función que da servicio a la cola, en este caso, se da explícitamente como un depósito de tokens: se reduce para los paquetes conformes y se incrementa a una tasa fija. Por lo tanto, como la cubeta con fugas como medidor y la cubeta con fichas son equivalentes, la cubeta con fugas como una cola para paquetes de longitud variable también es un caso especial de una función de modelado de tráfico que usa una cubeta con fugas (o cubeta con fichas) como medidor.
Hay una consecuencia interesante de ver el depósito con fugas como una cola para longitudes de paquetes variables como una implementación específica del depósito de fichas o depósito con fugas como un medidor en la configuración del tráfico. Esto es que la cubeta del medidor tiene una profundidad, n, y, como siempre es el caso con la cubeta 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 tanto, es posible cuantificar la ráfaga de la salida de este cubo con fugas de "recuento de bytes" como un metro, a menos que todos los paquetes tengan la longitud máxima cuando no tenga sentido. Sin embargo, esta capacidad para definir una ráfaga para la salida está en contradicción directa con la afirmación de que el depósito con fugas (como una cola) necesariamente da una salida con una tasa rígida, sin importar cuán ráfaga sea la entrada.
Ver también
- Algoritmo genérico de velocidad de celda
- UPC y NPC
- Contrato de tráfico
- Cubo de tokens
- Cola fluida
Notas
- ^ a b En la gestión del tráfico, el depósito con fugas se aplica normalmente al equivalente de las PDU de capa de enlace de datos de capa 2 del modelo ISO - OSI , por ejemplo, células ATM y tramas Ethernet , que se denominan tramas . Se puede argumentar entonces que la descripción de este algoritmo debería darse en términos de tramas, no de paquetes , que son, en el modelo de capa ISO-OSI 7, PDU de capa de red de capa 3 . Sin embargo, el término paquete se usa comúnmente de manera genérica en las descripciones de este algoritmo en la literatura, y esta convención también se aplica aquí. Sin embargo, no pretende implicar que el algoritmo de depósito con fugas se aplique exclusivamente a las PDU de capa de red.
- ^ a b Las funciones de modelado de tráfico incluyen una cola que es necesariamente de tamaño finito. Por lo tanto, si el flujo de entrada excede algún nivel de ráfaga que depende de la longitud de la cola o excede constantemente el límite de ancho de banda que se impone al flujo de salida, la cola se desbordará y los paquetes (normalmente) se descartarán: consulte Condición de desbordamiento de la configuración del tráfico. . Por lo tanto, se puede considerar que las funciones de modelado del tráfico aplican la vigilancia del tráfico a la conexión de entrada y el modelado del tráfico a la salida. Por lo tanto, deben tomar un parámetro para el límite de estallido en la entrada adicional a ese o aquellos para el balde con fugas. Sin embargo, este límite de ráfagas de entrada puede establecerse por defecto en un valor que no se espera que afecte al tráfico normal (se supone que la cola es lo suficientemente profunda para todas las circunstancias normales) y no siempre se especifica explícitamente.
Referencias
- ^ a b c d e f g h i Turner, J., Nuevas direcciones en las comunicaciones (¿o hacia dónde llegar a la era de la información?) . Revista de comunicaciones IEEE 24 (10): 8–15. ISSN 0163-6804 , 1986.
- ^ a b c d e f g h Andrew S. Tanenbaum, Redes informáticas, cuarta edición , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003., página 401.
- ^ a b c d e f g Foro ATM, La interfaz de red de usuario (UNI), v. 3.1, ISBN 0-13-393828-X , Prentice Hall PTR, 1995.
- ^ a b c d e f UIT-T, Control de tráfico y control de congestión en B ISDN , Recomendación I.371, Unión Internacional de Telecomunicaciones, 2004, Anexo A, página 87.
- ^ UIT-T, Control de tráfico y control de congestión en B ISDN , Recomendación I.371, Unión Internacional de Telecomunicaciones, 2004, página 17
- ^ a b c d e McDysan, David E. y Spohn, Darrel L., ATM: teoría y aplicación , ISBN 0-07-060362-6 , serie McGraw-Hill sobre comunicaciones informáticas, 1995, páginas 358–9.
- ^ Andrew S. Tanenbaum, Redes informáticas, cuarta edición , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003, página 400.
- ^ a b http://encyclopedia2.thefreedictionary.com/leaky+bucket+counter .
- ^ Intel, Intel Server Board S5400SF: Especificación técnica del producto , septiembre de 2007, http://download.intel.com/support/motherboards/server/s5400sf/sb/s5400sf_tps_rev2_01.pdf .
- ^ a b c Andrew S. Tanenbaum, Redes informáticas, cuarta edición , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003, página 402.