El algoritmo genérico de velocidad de celdas (GCRA) es un algoritmo de programación de tipo depósito con fugas para el programador de red que se utiliza en redes de modo de transferencia asíncrono (ATM). [1] [2] Se utiliza para medir la sincronización de celdas en canales virtuales (VC) y/o rutas virtuales (VP) en relación con los límites de ancho de banda y 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 dados por el contrato de tráfico pueden volver a cronometrarse (retrasarse) en la modelación del tráfico , o pueden descartarse (descartarse) o reducirse en prioridad (degradarse) en la vigilancia del tráfico . Las celdas no conformes cuya prioridad se reduce pueden luego descartarse, en preferencia a celdas de mayor prioridad, por componentes descendentes en 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 ellas, a pesar de que sean celdas excedentes en lo que respecta al contrato: consulte control de prioridad.
El GCRA se proporciona como referencia para verificar el tráfico en las conexiones de la red, es decir, el control de uso/parámetros de red (UPC/NPC) en las interfaces usuario-red (UNI) o interfaces entre redes o interfaces red-red (INI/NNI). [3] También se proporciona como referencia para la temporización de las celdas transmitidas (ATM PDU Data_Requests) en una red ATM por una tarjeta de interfaz de red (NIC) en un host, es decir, en el lado del usuario de la UNI. [3] Esto garantiza que las celdas no sean descartadas por UPC/NCP en la red, es decir, en el lado de la red de la UNI. Sin embargo, como el GCRA solo se proporciona como referencia, los proveedores de red y los usuarios pueden usar cualquier otro algoritmo que brinde el mismo resultado.
El GCRA está descrito por el Foro ATM en su Interfaz Usuario-Red (UNI) [1] y por la 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 maneras equivalentes: como un algoritmo de programación virtual y como un algoritmo de contenedor con fugas de estado continuo (figura 1).
La descripción en términos del algoritmo del cubo con fugas puede ser la más fácil de entender de las dos desde una perspectiva conceptual, ya que se basa en una analogía simple de un cubo con una fuga: consulte la figura 1 en la página del cubo con fugas . Sin embargo, ha habido confusión en la literatura sobre la aplicación de la analogía del cubo con fugas para producir un algoritmo, que se ha trasladado al GCRA. El GCRA debe considerarse como una versión del cubo con fugas como medidor en lugar del cubo con fugas como cola .
Sin embargo, si bien comprender esta descripción de cubo con fugas puede tener sus ventajas, no necesariamente da como resultado el mejor código (el más rápido) si se implementa directamente. Esto se evidencia por la cantidad relativa de acciones que se deben realizar en los diagramas de flujo para las dos descripciones (figura 1).
La descripción en términos del algoritmo de cubo con fugas de estado continuo la proporciona la UIT-T de la siguiente manera: "El cubo con fugas de estado continuo puede considerarse como un cubo de capacidad finita cuyo contenido de valor real se drena a una tasa continua de 1 unidad de contenido por unidad de tiempo y cuyo contenido se incrementa en el incremento T para cada celda conforme... Si en 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 es no 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 balde 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 del balde 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 balde actual se almacena entonces 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 se ajusta, entonces, si se ajusta porque llegó tarde, es decir, el balde vacío ( X' <= 0), X se establece en T ; si fue temprano, pero no demasiado temprano, ( τ >= X' > 0), X se establece en X' + T .
De esta manera, el diagrama de flujo imita directamente la analogía del cubo con fugas (usado como medidor), con X y X' actuando como el análogo del cubo.
El algoritmo de programación virtual, si bien no está tan obviamente relacionado con una analogía tan accesible como la del cubo con fugas, brinda una comprensión más clara de lo que hace el GCRA y de cómo implementarlo mejor. Como resultado, la implementación directa de esta versión puede generar un código más compacto y, por lo tanto, más rápido que una implementación directa de la descripción del cubo con fugas.
La descripción en términos del algoritmo de programación virtual la proporciona la UIT-T de la siguiente manera: "El algoritmo de programación virtual actualiza un Tiempo de llegada teórico (TAT), que es el tiempo de llegada 'nominal' de la celda asumiendo que las celdas se envían igualmente espaciadas en un intervalo de emisión de T correspondiente a la tasa de celdas Λ [= 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 celdas, 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 es no conforme". [2] Si la celda es no conforme , el TAT se deja sin cambios. Si la celda es conforme y llegó antes de su TAT (equivalente a que el contenedor no esté vacío pero sea menor que el valor límite), entonces el TAT de la siguiente celda 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 contenedor 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 fluctuaciones: véase balde con fugas: tolerancia a la variación del retraso . Otra forma de verlo es que TAT representa cuándo se vaciará el balde la próxima vez, por lo que un tiempo τ antes de eso es cuando el balde se llena exactamente hasta el valor límite. Por lo tanto, en cualquier punto de vista, si llega más de τ antes de TAT , es demasiado pronto para cumplir.
A diferencia de las implementaciones del algoritmo de token bucket , el GCRA no simula el proceso de actualización del depósito (la fuga o la adición regular de tokens). En cambio, cada vez que llega una celda, calcula la cantidad de fuga que habrá tenido el depósito desde que se calculó su nivel por última vez o cuándo se vaciará el depósito nuevamente (= TAT ). Esto esencialmente reemplaza 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 contenedor (o de TAT ) no implica ninguna multiplicación o división. Como resultado, el cálculo se puede realizar rápidamente en software, y aunque se realizan más acciones cuando llega una celda que las que realiza el contenedor de tokens, en términos de la carga en un procesador que realiza la tarea, la falta de un proceso de actualización independiente lo compensa con creces. Además, como no hay simulación de la actualización del contenedor, no hay carga de procesador en absoluto cuando la conexión está inactiva.
Sin embargo, si el GCRA se utilizara para limitar un ancho de banda, en lugar de una tasa de paquetes/fotogramas, en un protocolo con paquetes de longitud variable (PDU de capa de enlace), implicaría una multiplicación: básicamente, el valor añadido al cubo (o a TAT) para cada paquete conforme tendría que ser proporcional a la longitud del paquete: mientras que, con el GCRA tal como se describe, el agua en el cubo tiene unidades de tiempo, para los paquetes de longitud variable tendría que tener unidades que sean el producto de la longitud del paquete y el tiempo. Por lo tanto, la aplicación del GCRA para limitar el ancho de banda de los paquetes de longitud variable sin acceso a un multiplicador de hardware rápido (como en un FPGA ) puede no ser práctica. Sin embargo, siempre se puede utilizar para limitar la tasa de paquetes o celdas, siempre que se ignoren sus longitudes.
Se pueden aplicar múltiples implementaciones de GCRA simultáneamente a un VC o un VP, en una función de control de tráfico o modelado de tráfico de contenedores con fugas duales, por ejemplo, aplicada a un VC de tasa de bits variable (VBR). Esto puede limitar las celdas ATM en este VC de VBR a una tasa de celdas sostenida (SCR) y un tamaño de ráfaga máximo (MBS). Al mismo tiempo, la función de control de tráfico de contenedores con fugas duales puede limitar la tasa de celdas en las ráfagas a una tasa de celdas máxima (PCR) y una tolerancia máxima de variación de retardo de celda (CDVt): consulte Contrato de tráfico n.º Parámetros de tráfico .
Esto puede entenderse mejor cuando la transmisión en un VC VBR 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 requieren una cantidad de celdas, MBS, para transportarlos; sin embargo, la descripción del tráfico VBR y el uso del contenedor con doble fuga no se limitan a tales situaciones. En este caso, la tasa de celdas 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 que es más pequeño que el intervalo de mensajes IMT, con brechas entre las instancias del mensaje.
En el contenedor con fugas dual, se aplica un contenedor 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: consulte contenedor con fugas#Tamaño máximo de ráfaga . El segundo contenedor 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: consulte contenedor con fugas#Tolerancia de variación de retardo . Luego, se permite el paso de celdas en el PCR, con una fluctuación de τ PCR , hasta un número máximo de celdas MBS. Luego, se permitirá el paso de la siguiente ráfaga de celdas MBS comenzando con MBS x 1/SCR después de la primera.
Si las células llegan en una ráfaga a una tasa mayor que 1/PCR (las células MBS llegan en menos de (MBS - 1)/PCR - τ PCR ), o llegan más de células MBS a la PCR, o ráfagas de células MBS llegan más cerca que IMT entre sí, el doble depósito con fugas detectará esto y retrasará (modelará) o descartará o despriorizará (vigilará) suficientes células para hacer que la conexión se ajuste.
La figura 3 muestra el algoritmo de referencia para el control de SCR y PCR para flujos de células con 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 reciben el mismo tratamiento. En el Anexo A de I.371 también se ofrecen algoritmos de referencia similares donde las células de prioridad alta y baja reciben un tratamiento diferente. [2]