El algoritmo genérico de velocidad de celda (GCRA) es un algoritmo de programación de tipo cubo con fugas para el programador de red que se utiliza en las redes del modo de transferencia asíncrona (ATM). [1] [2] Se utiliza para medir el tiempo de las celdas en canales virtuales (VC) y / o Rutas virtuales (VP) contra el ancho de banda y los límites de fluctuación contenidos en un contrato de tráfico para el VC o VP al que pertenecen las celdas. Las celdas que no se ajustan a los límites establecidos por el contrato de tráfico pueden volver a programarse (retrasarse) en la configuración del tráfico., o puede ser eliminado (descartado) o reducido en prioridad (degradado) en la vigilancia del tráfico . Las células no conformes que tienen una prioridad reducida pueden ser descartadas, con preferencia a las células de mayor prioridad, por los componentes descendentes de la red que están experimentando congestión. Alternativamente pueden llegar a su destino (terminación de VC o VP) si hay suficiente capacidad para ellos, a pesar de que sean celdas en exceso en lo que al contrato se refiere: ver control de prioridades .
El GCRA se proporciona como referencia para comprobar el tráfico en las conexiones de la red, es decir, el control de parámetros de uso / red (UPC / NPC) en las interfaces usuario-red (UNI) o interfaces entre redes o interfaces red-red (INI / NNI ). [3] También se da como referencia para la temporización de las células transmitidas (Solicitudes de datos de PDU ATM) a una red ATM mediante una tarjeta de interfaz de red (NIC) en un host, es decir, en el lado del usuario de la UNI. [3] Esto asegura que las células no sean descartadas por UPC / NCP en la red, es decir, en el lado de la red de la UNI. Sin embargo, dado que el GCRA solo se proporciona como referencia, los proveedores de red y los usuarios pueden utilizar cualquier otro algoritmo que dé el mismo resultado.
Descripción del GCRA
El GCRA está descrito por el Foro ATM en su interfaz usuario-red (UNI) [1] y por el UIT-T en la recomendación I.371 Control de tráfico y control de congestión en B-ISDN . [2] Ambas fuentes describen el GCRA de dos formas equivalentes: como un algoritmo de programación virtual y como un algoritmo de balde con fugas de estado continuo (figura 1).
Descripción del balde con fugas
La descripción en términos del algoritmo del balde con fugas puede ser el más fácil de entender de los dos desde una perspectiva conceptual, ya que se basa en una analogía simple de un balde con una fuga: consulte la figura 1 en la página del balde con fugas . Sin embargo, ha habido confusión en la literatura sobre la aplicación de la analogía del balde con fugas para producir un algoritmo, que ha pasado al GCRA. El GCRA debe considerarse como una versión del balde con fugas como un medidor en lugar del balde con fugas como una cola .
Sin embargo, aunque existen posibles ventajas en la comprensión de esta descripción de depósito con fugas, no necesariamente da como resultado el mejor código (más rápido) si se implementa directamente. Esto se evidencia por el número relativo de acciones a realizar en los diagramas de flujo para las dos descripciones (figura 1).
La descripción en términos del algoritmo de cubeta con fugas de estado continuo la proporciona el UIT-T de la siguiente manera: "La cubeta con fugas de estado continuo se puede considerar como una cubeta de capacidad finita cuyo contenido en 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 al valor límite τ , entonces la celda es conforme; de lo contrario, la celda no es conforme. La capacidad del cubo (el límite superior del contador) es ( T + τ ) ". [2] Vale la pena señalar que debido a que la fuga es una unidad de contenido por unidad de tiempo, el incremento para cada celda T y el valor límite τ están en unidades de tiempo.
Considerando el diagrama de flujo del algoritmo de cubeta con fugas de estado continuo, en el que T es el intervalo de emisión y τ es el valor límite: lo que sucede cuando llega una celda es que el estado de la cubeta se calcula a partir de su estado cuando llegó la última celda conforme. , X , y cuánto se ha filtrado en el intervalo, t a - LCT . Este valor de cubo actual se almacena en X ' y se compara con el valor límite τ . Si el valor en X ' no es mayor que τ , la celda no llegó demasiado pronto y, por lo tanto, se ajusta a los parámetros del contrato; si el valor en X ' es mayor que τ , entonces no se ajusta. Si cumple, entonces, si cumple porque llegó tarde, es decir, el cubo está vacío ( X ' <= 0), X se establece en T ; si era temprano, pero no demasiado pronto, ( τ > = X ' > 0), X se establece en X' + T .
Por lo tanto, el diagrama de flujo imita la analogía del balde con fugas (usado como medidor) directamente, con X y X ' actuando como el análogo del balde.
Descripción de la programación virtual
El algoritmo de programación virtual, aunque no está tan obviamente relacionado con una analogía de tan fácil acceso como el balde con fugas, proporciona una comprensión más clara de lo que hace el GCRA y cómo se puede implementar mejor. Como resultado, la implementación directa de esta versión puede resultar en un código más compacto y, por lo tanto, más rápido que una implementación directa de la descripción del depósito con fugas.
La descripción en términos del algoritmo de programación virtual viene dada por el UIT-T de la siguiente manera: "El algoritmo de programación virtual actualiza una hora de llegada teórica (TAT), que es la hora de llegada 'nominal' de la celda, asumiendo que las celdas se envían a distancias iguales a un intervalo de emisión de T correspondiente a la tasa de celda Λ [= 1 / T ] cuando la fuente está activa. Si el tiempo de llegada real de una celda no es 'demasiado temprano' en relación con el TAT y la tolerancia τ asociada a la tasa de celda , es decir, si el tiempo de llegada real es posterior a su tiempo de llegada teórico menos el valor límite (t a > TAT - τ ), entonces la celda es conforme; de lo contrario, la celda no es conforme ". [2] Si la celda no cumple , TAT se deja sin cambios. Si la célula es conforme, y llegó antes de su TAT (equivalente a la cubeta no estar vacío, pero es menor que el valor límite), a continuación de la siguiente celda TAT es simplemente TAT + T . Sin embargo, si una celda llega después de su TAT , entonces el TAT para la siguiente celda se calcula a partir del tiempo de llegada de esta celda, no de su TAT . Esto evita la acumulación de crédito cuando hay una brecha en la transmisión (equivalente a que el cubo se quede menos que vacío).
Esta versión del algoritmo funciona porque τ define cuánto antes puede llegar una celda de lo que llegaría si no hubiera jitter: ver depósito con fugas: tolerancia a la variación de retardo . Otra forma de verlo es que TAT representa la próxima vez que se vacíe el balde, por lo que un tiempo τ antes de eso es cuando el balde se llena exactamente hasta el valor límite. Entonces, en cualquier punto de vista, si llega más de τ antes de TAT , es demasiado pronto para ajustarse.
Comparación con el depósito de tokens
El GCRA, a diferencia de las implementaciones del algoritmo del depósito de tokens , no simula el proceso de actualización del depósito (la fuga o la adición de tokens con regularidad). Más bien, cada vez que llega una celda, calcula la cantidad por la cual se habrá filtrado el balde desde la última vez que se calculó su nivel o la próxima vez que se vaciará el balde (= TAT ). Básicamente, esto está reemplazando el proceso de fuga con un reloj (en tiempo real), que es probable que ya tengan la mayoría de las implementaciones de hardware.
Esta sustitución del proceso por un RTC es posible porque las celdas ATM tienen una longitud fija (53 bytes), por lo que T es siempre una constante, y el cálculo del nuevo nivel de cubeta (o de TAT ) no implica ninguna multiplicación o división. Como resultado, el cálculo se puede hacer rápidamente en el software, y aunque se toman más acciones cuando llega una celda que las que toma el depósito de tokens, en términos de la carga en un procesador que realiza la tarea, la falta de un proceso de actualización separado más que compensa esto. Además, debido a que no hay simulación de la actualización del depósito, no hay carga del procesador en absoluto cuando la conexión está inactiva.
Sin embargo, si la GCRA se usara para limitar a un ancho de banda, en lugar de una velocidad de paquete / cuadro, en un protocolo con paquetes de longitud variable (PDU de capa de enlace), implicaría una multiplicación: básicamente el valor agregado al depósito (o a TAT) para cada paquete conforme tendría que ser proporcional a la longitud del paquete: mientras que, con el GCRA como se describe, el agua en el balde tiene unidades de tiempo, para los paquetes de longitud variable tendría que tener unidades que sean el producto de longitud y tiempo del paquete. Por lo tanto, aplicar el GCRA para limitar el ancho de banda de paquetes de longitud variable sin acceso a un multiplicador de hardware rápido (como en un FPGA ) puede no ser práctico. Sin embargo, siempre se puede utilizar para limitar el paquete o la velocidad de la celda, siempre que se ignoren sus longitudes.
Controlador de cucharón con fugas dual
Se pueden aplicar múltiples implementaciones del GCRA simultáneamente a un VC o un VP, en una función de control de tráfico o conformación de tráfico de cubeta con fugas dual , por ejemplo, aplicada a un VC de velocidad de bits variable (VBR). Esto puede limitar las celdas ATM en este VBR VC a una velocidad de celda sostenida (SCR) y un tamaño máximo de ráfaga (MBS). Al mismo tiempo, la función de vigilancia de tráfico de cubeta con fugas dobles puede limitar la tasa de celdas en las ráfagas a una Tasa de celda máxima (PCR) y una tolerancia máxima de variación de retardo de celda (CDVt): consulte Contrato de tráfico # Parámetros de tráfico .
Esto puede entenderse mejor cuando la transmisión en un VBR VC se realiza en forma de mensajes de longitud fija (CPCS-PDU), que se transmiten con un intervalo fijo o el tiempo entre mensajes (IMT) y toman un número de celdas, MBS, para llevarlos; sin embargo, la descripción del tráfico VBR y el uso del balde con fugas dobles no se limitan a tales situaciones. En este caso, la tasa de celda promedio durante el intervalo de IMT es el SCR (= MBS / IMT). Los mensajes individuales se pueden transmitir en un PCR, que puede ser cualquier valor entre el ancho de banda para el enlace físico (1 / δ ) y el SCR. Esto permite que el mensaje se transmita en un período menor que el intervalo de mensaje IMT, con espacios entre instancias del mensaje.
En el depósito con fugas dobles, se aplica un depósito al tráfico con un intervalo de emisión de 1 / SCR y un valor límite τ SCR que da un MBS que es el número de celdas en el mensaje: ver depósito con fugas # Tamaño máximo de ráfaga . El segundo cubo tiene un intervalo de emisión de 1 / PCR y un valor límite τ PCR que permite el CDV hasta ese punto en la ruta de la conexión: ver cubo con fugas # Tolerancia de variación de retardo . A continuación, se permite el paso de las células en la PCR, con fluctuación de τ PCR , hasta un número máximo de células MBS. La siguiente ráfaga de células MBS se permitirá a través del inicio de MBS x 1 / SCR después de la primera.
Si las células llegan en una ráfaga a una velocidad superior a 1 / PCR (las células MBS llegan en menos de (MBS - 1) / PCR - τ PCR ), o llegan más células MBS a la PCR, o llegan ráfagas de células MBS más cerca que IMT, el depósito con fugas dual detectará esto y retrasará (modelará) o eliminará o eliminará la prioridad (vigilancia) suficientes celdas para que la conexión se ajuste.
La Figura 3 muestra el algoritmo de referencia para el control de SCR y PCR para los flujos de células de los valores de Prioridad de pérdida de células (CLP) 1 (bajo) y 0 (alto), es decir, donde las células con ambos valores de prioridad se tratan de la misma manera. En el anexo A a I.371 se dan también algoritmos de referencia similares en los que las células de alta y baja prioridad se tratan de forma diferente. [2]
Ver también
- Modo de Transferencia Asíncrona
- Cubo agujereado
- UPC y NPC
- NNI
- Contrato de tráfico
- Control de admisión de conexión
- Conformación del tráfico
- Vigilancia de tráfico (comunicaciones)
- Cubo de tokens
Referencias
- ^ a b 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 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.
- ^ a b 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