El algoritmo genérico de velocidad de celda (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 asincrónica (ATM). [1] [2] Se utiliza para medir la sincronización de las células en canales virtuales (VC) o rutas virtuales (VP) frente a 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 células. Las celdas que no se ajusten a los límites establecidos por el contrato de tráfico pueden ser reprogramadas (retrasadas) en la configuración del tráfico , o pueden ser eliminadas (desechadas) o reducidas en prioridad (degradadas) en la vigilancia del tráfico . Las células no conformes cuya prioridad se reduce pueden ser descartadas, con preferencia a células de mayor prioridad, por los componentes descendentes de la red que están experimentando congestión. Alternativamente podrán llegar a su destino (terminación VC o VP) si hay capacidad suficiente para ellas, a pesar de ser células sobrantes para el contrato: ver control de prioridad.
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 entre interfaces entre redes o interfaces red-red (INI/NNI). ). [3] También se proporciona como referencia para la sincronización de las células transmitidas (ATM PDU Data_Requests) en 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 garantiza que UPC/NCP no descarte las células en la red, es decir, en el lado de red de la UNI. Sin embargo, como el GCRA sólo se proporciona como referencia, los proveedores y usuarios de la red pueden utilizar cualquier otro algoritmo que dé el mismo resultado.
El GCRA es descrito por el Foro ATM en su Interfaz de Red de Usuario (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 maneras equivalentes: como un algoritmo de programación virtual y como un algoritmo de depósito con fugas de estado continuo (figura 1).
La descripción en términos del algoritmo del balde 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 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 cubo con fugas para producir un algoritmo, que ha pasado 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 existen posibles ventajas al comprender esta descripción del depósito con fugas, no necesariamente da como resultado el mejor código (el 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 del cubo con fugas de estado continuo 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 contenido de valor real se drena a una velocidad 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; en caso 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 del cubo 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 cubo 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 actual del segmento se almacena luego 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 cubo está vacío ( X' <= 0), X se establece en T ; si fue temprano, pero no demasiado temprano, ( τ >= X' > 0), X se establece en X' + T .
Por lo tanto, el diagrama de flujo imita directamente la analogía del balde con fugas (usado como medidor), con X y X' actuando como el análogo del balde.
El algoritmo de programación virtual, aunque no está tan obviamente relacionado con una analogía tan fácilmente accesible como el cubo con fugas, ofrece una comprensión más clara de lo que hace la GCRA y cuál es la mejor manera de implementarlo. Como resultado, la implementación directa de esta versión puede dar como resultado 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 la proporciona el 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 célula suponiendo que las células se envían equiespaciadas. en 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; en caso contrario, la celda no es conforme". [2] Si la celda no es conforme, entonces TAT no se modifica. Si la celda se ajusta y llegó antes de su TAT (equivalente a que el depósito 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 que se acumule crédito cuando hay un espacio en la transmisión (equivalente a que el cubo quede menos que vacío).
Esta versión del algoritmo funciona porque τ define cuánto antes puede llegar una celda de lo que lo haría si no hubiera fluctuación: ver cubo con fugas: tolerancia a la variación del retraso . Otra forma de verlo es que TAT representa cuándo se vaciará el depósito a continuación, por lo que un tiempo τ antes de eso es cuando el depósito se llena exactamente hasta el valor límite. Entonces, desde cualquier punto de vista, si llega más de τ antes de TAT , es demasiado pronto para ajustarse.
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 filtración o la adición de tokens con regularidad). Más bien, cada vez que llega una celda, calcula la cantidad por la cual el cubo se habrá filtrado desde la última vez que se calculó su nivel o cuándo se vaciará el cubo la próxima vez (= TAT ). Básicamente, se trata de reemplazar el proceso de filtración con un reloj (en tiempo real), que probablemente ya tengan la mayoría de las implementaciones de hardware.
Esta sustitución del proceso por un RTC es posible porque las células ATM tienen una longitud fija (53 bytes), por lo que T es siempre una constante y el cálculo del nuevo nivel del depósito (o de TAT ) no implica ninguna multiplicación o división. Como resultado, el cálculo se puede realizar rápidamente en el software y, si bien cuando llega una celda se toman más acciones que las que realiza 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 esto lo compensa con creces. Además, debido a que no hay simulación de la actualización del depósito, no hay ninguna carga del procesador cuando la conexión está inactiva.
Sin embargo, si el GCRA se utilizara para limitar 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 paquetes de longitud variable tendría que tener unidades que sean el producto de longitud y tiempo del paquete. Por lo tanto, aplicar GCRA para limitar el ancho de banda de paquetes de longitud variable sin acceso a un multiplicador de hardware rápido (como en una FPGA ) puede no ser práctico. Sin embargo, siempre se puede utilizar para limitar la velocidad de paquetes o células, 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 configuración de tráfico de cubo 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 de ráfaga máximo (MBS). Al mismo tiempo, la función de vigilancia de tráfico de cubeta con fugas dual puede limitar la tasa de celdas en las ráfagas a una tasa de celda pico (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 se puede entender 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 toman una cantidad de celdas, MBS, para llevarlos; sin embargo, la descripción del tráfico VBR y el uso del cubo con fugas duales no se limitan a tales situaciones. En este caso, la velocidad celular promedio durante el intervalo de IMT es la 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 del mensaje IMT, con espacios entre instancias del mensaje.
En el depósito con fugas dual, se aplica un depósito al tráfico con un intervalo de emisión de 1/SCR y un valor límite τ SCR que proporciona un MBS que es el número de celdas en el mensaje: consulte depósito con fugas#Tamaño máximo de ráfaga . El segundo depósito 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 depósito con fugas#Tolerancia de variación de retardo . Luego se permite el paso de las células en la PCR, con una fluctuación de τ PCR , hasta un número máximo de células MBS. La siguiente ráfaga de celdas MBS se permitirá iniciando 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 cubo doble con fugas detectará esto y retrasará (configurará) o eliminará o quitará prioridad (vigilará) 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 flujos de células con valores 1 (bajo) y 0 (alto) de prioridad de pérdida de células (CLP), es decir, donde las células con ambos valores de prioridad se tratan de la misma manera. En el anexo A a I.371 también se proporcionan algoritmos de referencia similares en los que las células de alta y baja prioridad se tratan de forma diferente. [2]