Retroceso exponencial

Busque backoff en Wikcionario, el diccionario libre.

El retroceso exponencial es un algoritmo que utiliza la retroalimentación para disminuir de forma multiplicativa la velocidad de algún proceso, con el fin de encontrar gradualmente una velocidad aceptable. Estos algoritmos se utilizan en una amplia gama de sistemas y procesos, siendo especialmente notables las redes de radio y las redes informáticas .

Un algoritmo de retroceso exponencial es una forma de sistema de control de bucle cerrado que reduce la velocidad de un proceso controlado en respuesta a eventos adversos. Por ejemplo, si una aplicación de teléfono inteligente no puede conectarse a su servidor, podría intentarlo nuevamente 1 segundo después, luego, si falla nuevamente, 2 segundos después, luego 4, etc. Cada vez que la pausa se multiplica por una cantidad fija (en este caso 2). En este caso, el evento adverso es no poder conectarse al servidor. Otros ejemplos de eventos adversos incluyen colisiones de tráfico de red , una respuesta de error de un servicio o una solicitud explícita para reducir la velocidad (es decir, retroceso ).

La reducción de la tasa se puede modelar como una función exponencial :

${\displaystyle t=b^{c}}$

o

${\displaystyle f={\frac {1}{b^{c}}}}$

Aquí, t es el retraso de tiempo aplicado entre acciones, b es el factor multiplicativo o base , c es el número de eventos adversos observados y f es la frecuencia (o tasa) del proceso (es decir, el número de acciones por unidad de tiempo). El valor de c se incrementa cada vez que se observa un evento adverso, lo que genera un aumento exponencial del retraso y, por lo tanto, una tasa inversamente proporcional. Un algoritmo de retroceso exponencial donde b = 2 se denomina algoritmo de retroceso exponencial binario .

Cuando la tasa se ha reducido en respuesta a un evento adverso, por lo general no permanece en ese nivel reducido para siempre. Si no se observan eventos adversos durante un período de tiempo, a menudo denominado tiempo de recuperación o período de enfriamiento , la tasa puede aumentarse nuevamente. El período de tiempo que debe transcurrir antes de intentar aumentar la tasa nuevamente puede, en sí mismo, determinarse mediante un algoritmo de retroceso exponencial. Por lo general, la recuperación de la tasa ocurre más lentamente que la reducción de la tasa debido al retroceso y, a menudo, requiere un ajuste cuidadoso para evitar la oscilación de la tasa. ^[1] El comportamiento de recuperación exacto es específico de la implementación y puede estar informado por cualquier número de factores ambientales.

El mecanismo por el cual se logra en la práctica la reducción de la velocidad en un sistema puede ser más complejo que un simple retraso de tiempo. En algunos casos, el valor t puede hacer referencia a un límite superior del retraso de tiempo, en lugar de un valor de retraso de tiempo específico. El nombre de retraso exponencial hace referencia a la característica de crecimiento exponencial del retraso, en lugar de a una relación numérica exacta entre los recuentos de eventos adversos y los tiempos de retraso.

El retroceso exponencial se utiliza comúnmente como parte de los mecanismos de limitación de velocidad en sistemas informáticos como los servicios web , para ayudar a hacer cumplir la distribución justa del acceso a los recursos y evitar la congestión de la red . Cada vez que un servicio informa a un cliente que está enviando solicitudes con demasiada frecuencia, el cliente reduce su velocidad en un factor predeterminado, hasta que la tasa de solicitudes del cliente alcanza un equilibrio aceptable. El servicio puede hacer cumplir la limitación de velocidad al negarse a responder a las solicitudes cuando el cliente las envía con demasiada frecuencia, de modo que los clientes con mal comportamiento no puedan exceder sus recursos asignados.

Una ventaja de utilizar un algoritmo de reducción exponencial, en lugar de un límite de velocidad fijo, es que los límites de velocidad se pueden alcanzar de forma dinámica sin proporcionar ninguna información previa al cliente. En caso de que los recursos se vean limitados inesperadamente, por ejemplo, debido a una gran carga o una interrupción del servicio, las solicitudes de reducción y las respuestas de error del servicio pueden reducir automáticamente la tasa de solicitudes de los clientes. Esto puede ayudar a mantener un cierto nivel de disponibilidad en lugar de sobrecargar el servicio. Además, se puede priorizar la calidad del servicio para determinados clientes en función de su importancia individual, por ejemplo, reduciendo la reducción de las llamadas de emergencia en una red telefónica durante períodos de alta carga.

En una versión simple del algoritmo, los mensajes se retrasan durante un tiempo predeterminado (no aleatorio). Por ejemplo, en el protocolo SIP sobre un transporte no confiable (como UDP ), el cliente retransmite las solicitudes en un intervalo que comienza en T1 segundos (normalmente,500 ms , que es la estimación del tiempo de ida y vuelta ) y se duplica después de cada retransmisión hasta que alcanza T2 segundos (que es el valor predeterminado).4 s ). Esto da como resultado intervalos de retransmisión de500 ms ,1 segundo ,2 segundos ,4 segundos ,4 segundos ,4 s , etc. ^[2]

Los algoritmos de retroceso exponencial se pueden utilizar para evitar colisiones en la red. En una red punto a multipunto o multiplexada , varios remitentes se comunican a través de un único canal compartido. Si dos remitentes intentan transmitir un mensaje al mismo tiempo, o se comunican entre sí, se produce una colisión y los mensajes se dañan o se pierden. Cada remitente puede entonces retroceder antes de intentar retransmitir el mismo mensaje nuevamente.

Un algoritmo de retroceso exponencial determinista no es adecuado para este caso de uso, ya que cada remitente se retrasaría durante el mismo período de tiempo, lo que los llevaría a retransmitir simultáneamente y causar otra colisión. En cambio, para evitar colisiones, el tiempo entre retransmisiones es aleatorio y el algoritmo de retroceso exponencial establece el rango de valores de retraso que son posibles. El retraso de tiempo generalmente se mide en ranuras , que son períodos de tiempo de longitud fija (o porciones ) en la red. En un algoritmo de retroceso exponencial binario (es decir, uno donde b = 2 ), después de c colisiones, cada retransmisión se retrasa por un número aleatorio de ranuras de tiempo entre 0 y 2 ^c − 1. Después de la primera colisión, cada remitente esperará 0 o 1 ranuras de tiempo. Después de la segunda colisión, los remitentes esperarán entre 0 y 3 ranuras de tiempo ( inclusive ). Después de la tercera colisión, los remitentes esperarán entre 0 y 7 ranuras de tiempo (inclusive), y así sucesivamente. A medida que aumenta el número de intentos de retransmisión, el número de posibilidades de retraso aumenta exponencialmente . Esto disminuye la probabilidad de una colisión, pero aumenta la latencia promedio.

El retroceso exponencial se utiliza durante la retransmisión de tramas en redes de acceso múltiple con detección de portadora y prevención de colisiones (CSMA/CA) y de acceso múltiple con detección de portadora y detección de colisiones (CSMA/CD), donde este algoritmo es parte del método de acceso al canal utilizado para enviar datos en estas redes. En las redes Ethernet , el algoritmo se utiliza comúnmente para programar retransmisiones después de las colisiones. La retransmisión se retrasa por una cantidad de tiempo derivada del tiempo de ranura (por ejemplo, el tiempo que lleva enviar 512 bits; es decir, 512 tiempos de bit ) y la cantidad de intentos de retransmisión.

Este ejemplo es del protocolo Ethernet , ^[3] donde un host emisor puede saber cuándo se ha producido una colisión (es decir, otro host ha intentado transmitir), cuando está enviando una trama. Si ambos hosts intentaran volver a transmitir tan pronto como se produjo una colisión, habría otra colisión y el patrón continuaría para siempre. Los hosts deben elegir un valor aleatorio dentro de un rango aceptable para garantizar que esta situación no suceda. Por lo tanto, se utiliza un algoritmo de retroceso exponencial. El valor 51,2 μs se utiliza como ejemplo aquí porque es el tiempo de ranura para unaLínea Ethernet de 10 Mbit/s . Sin embargo,En la práctica, 51,2 μs podrían sustituirse por cualquier valor positivo.

1. Cuando ocurre una colisión por primera vez, envía una señal de interferencia para evitar que se envíen más datos.
2. Reenviar un marco después de 0 segundos o51,2 μs , elegido al azar.
3. Si eso falla, vuelva a enviar el marco después de cualquiera de los dos.0 segundos ,51,2 μs ,102,4 μs , o153,6 μs .
4. Si esto sigue fallando, vuelva a enviar el marco después de k ·51,2 μs , donde k es un entero aleatorio entre 0 y 2 ³ − 1 .
5. En caso de fallos posteriores, después del c -ésimo intento fallido, vuelva a enviar el marco después de k ·51,2 μs , donde k es un entero aleatorio entre 0 y 2 ^c − 1 .

En un artículo seminal publicado en AFIPS 1970, ^[4] Norman Abramson presentó la idea de múltiples “usuarios”, en diferentes islas, que comparten un único canal de radio (es decir, una única frecuencia) para acceder a la computadora principal de la Universidad de Hawai sin ninguna sincronización horaria. Las colisiones de paquetes en el receptor de la computadora principal son tratadas por los remitentes después de un tiempo de espera como errores detectados. Cada remitente que no reciba un acuse de recibo positivo de la computadora principal retransmitiría su paquete “perdido”. Abramson supuso que la secuencia de paquetes transmitidos al canal compartido es un proceso de Poisson a una tasa G , que es la suma de la tasa S de llegadas de nuevos paquetes a los remitentes y la tasa de paquetes retransmitidos al canal. Suponiendo un estado estable, demostró que la tasa de rendimiento del canal tiene un valor máximo de 1/(2 e ) = 0,184 en teoría.$Estilo de visualización S=Ge^{-2G}}$

Larry Roberts consideró un canal ALOHA con ranuras de tiempo, en el que cada ranura de tiempo es lo suficientemente larga para un tiempo de transmisión de paquetes. (Un canal satelital que utiliza el protocolo TDMA tiene ranuras de tiempo). Utilizando el mismo proceso de Poisson y supuestos de estado estable que Abramson, Larry Roberts demostró que la tasa máxima de rendimiento es 1/ e = 0,368 en teoría. ^[5] Roberts fue el director del programa del proyecto de investigación ARPANET . Inspirado por la idea de ALOHA con ranuras, Roberts inició un nuevo proyecto de Sistema Satelital ARPANET (ASS) para incluir enlaces satelitales en ARPANET.

Los resultados de simulación de Abramson, sus colegas y otros mostraron que un canal ALOHA, con o sin ranuras, es inestable y a veces entra en colapso por congestión . El tiempo hasta el colapso por congestión dependía de la tasa de llegada de nuevos paquetes, así como de otros factores desconocidos. En 1971, Larry Roberts pidió al profesor Leonard Kleinrock y a su estudiante de doctorado, Simon Lam , de la UCLA que se unieran al proyecto del Sistema Satelital de ARPANET . Simon Lam trabajaría en la estabilidad, la evaluación del rendimiento y el control adaptativo del ALOHA con ranuras para la investigación de su tesis doctoral. El primer artículo del que fue coautor con Kleinrock fue ARPANET Satellite System (ASS) Note 12, difundido al grupo ASS en agosto de 1972. ^[6] En este artículo, se utilizó una ranura elegida aleatoriamente en un intervalo de K ranuras para la retransmisión. Un nuevo resultado del modelo es que aumentar K aumenta el rendimiento del canal, que converge a 1/ e a medida que K aumenta hasta el infinito. Este modelo mantuvo los supuestos de llegadas de Poisson y estado estable, y no fue pensado para comprender el comportamiento estadístico y el colapso de la congestión.

Para comprender la estabilidad, Lam creó un modelo de cadena de Markov de tiempo discreto para analizar el comportamiento estadístico de ALOHA con ranuras en el capítulo 5 de su disertación. ^[7] El modelo tiene tres parámetros: N , s y p . N es el número total de usuarios. En cualquier momento, cada usuario puede estar inactivo o bloqueado. Cada usuario tiene como máximo un paquete para transmitir en el siguiente intervalo de tiempo. Un usuario inactivo genera un nuevo paquete con probabilidad s y lo transmite en el siguiente intervalo de tiempo inmediatamente. Un usuario bloqueado transmite su paquete atrasado con probabilidad p , donde 1/ p = ( K +1)/2 para mantener el intervalo de retransmisión promedio igual. Los resultados de retardo de rendimiento de los dos métodos de retransmisión se compararon mediante simulaciones exhaustivas y se encontró que eran esencialmente los mismos. ^[8]

El modelo de Lam proporciona respuestas matemáticamente rigurosas a las cuestiones de estabilidad de ALOHA con ranuras, así como un algoritmo eficiente para calcular el rendimiento de retardo de procesamiento para cualquier sistema estable. Hay 3 resultados clave, que se muestran a continuación, del modelo de cadena de Markov de Lam en el Capítulo 5 de su disertación (también publicada conjuntamente con el profesor Len Kleinrock, en IEEE Transactions on Communications. ^[9] )

1. El modelo ALOHA con ranuras y llegadas de Poisson (es decir, N infinito ) es inherentemente inestable, porque no existe una distribución de probabilidad estacionaria. (Alcanzar el estado estable fue un supuesto clave utilizado en los modelos de Abramson y Roberts).
2. Para ALOHA ranurado con una N finita y una K finita , el modelo de cadena de Markov se puede utilizar para determinar si el sistema es estable o inestable para una tasa de entrada dada ( N × s ) y, si es estable, calcular su retraso de paquete promedio y la tasa de rendimiento del canal.
3. Al aumentar K se incrementa el número máximo de usuarios que puede alojar un canal ALOHA ranurado estable. ^[10]

Para un número finito ( N  ×  s ), un canal inestable para el valor K actual se puede hacer estable aumentando K a un valor suficientemente grande, al que se denominará su K ( N , s ). ^[11]

Lam utilizó la teoría de decisión de Markov y desarrolló políticas de control óptimas para ALOHA con ranuras, pero estas políticas requieren que todos los usuarios bloqueados conozcan el estado actual (número de usuarios bloqueados) de la cadena de Markov. En 1973, Lam decidió que en lugar de utilizar un protocolo complejo para que los usuarios estimaran el estado del sistema, crearía un algoritmo simple para que cada usuario utilizara su propia información local, es decir, el número de colisiones que su paquete atrasado ha encontrado. ^[13] Aplicando el corolario anterior, Lam inventó la siguiente clase de algoritmos de retroceso adaptativos (llamados RCP heurístico).

Un algoritmo RCP heurístico consta de los siguientes pasos: (1) Sea m el número de colisiones previas sufridas por un paquete en un usuario como la información de retroalimentación en su bucle de control. Para un nuevo paquete, K (0) se inicializa a 1. (2) El intervalo de retransmisión del paquete K ( m ) aumenta a medida que m aumenta (hasta que el canal se vuelve estable como lo implica el Corolario anterior). Para la implementación, con K (0)=1, a medida que m aumenta, K ( m ) se puede aumentar por multiplicación (o por adición).

El retroceso exponencial binario (BEB), utilizado en Ethernet varios años más tarde, es un caso especial de RCP heurístico con .${\displaystyle K(m)=2^{m}}$

BEB es muy fácil de implementar. Sin embargo, no es óptimo para muchas aplicaciones porque BEB utiliza 2 como único multiplicador, lo que no proporciona flexibilidad para la optimización. En particular, para un sistema con una gran cantidad de usuarios, BEB aumenta K ( m ) demasiado lentamente. Por otro lado, para un sistema con una pequeña cantidad de usuarios, una K bastante pequeña es suficiente para que el sistema sea estable y no sea necesario un retroceso.

Para ilustrar un ejemplo de un RCP multiplicativo que utiliza varios multiplicadores, véase la fila inferior de la Tabla 6.3 en la página 214 del Capítulo 6 de la disertación de Lam, o la fila inferior de la Tabla III en la página 902 del artículo de Lam-Kleinrock. En este ejemplo:

1. Se transmite un nuevo paquete inmediatamente, m = 0, K (0) = 1
2. Para un paquete con 1 colisión previa, K (1) = K (0)  ×  10 = 10 (el multiplicador salta directamente a K ^* = 10, que se encontró que era el valor K óptimo en estado estable para este sistema en particular (ALOHA con ranura para un canal satelital).
3. Para un paquete con 2 colisiones previas, K (2) = K (1)  ×  10 = 100 (una colisión más, K salta 10 veces).
4. K (3) = K (2) × 2 = 200
5. K ( m )= K ( m −1) para m ≥4

Para este ejemplo, K = 200 es suficiente para un sistema ALOHA con ranuras estable con N igual a aproximadamente 400, lo que se desprende del resultado 3 anterior. No es necesario aumentar K más.

La variante "truncada" del algoritmo introduce un límite en c . Esto simplemente significa que después de un cierto número de aumentos, la exponenciación se detiene. Sin un límite en c , el retraso entre transmisiones puede volverse indeseablemente largo si un remitente observa repetidamente eventos adversos, por ejemplo, debido a una degradación en el servicio de red. En un sistema aleatorio, esto puede ocurrir por casualidad, lo que lleva a una latencia impredecible; los retrasos más largos debido a aumentos ilimitados en c son exponencialmente menos probables, pero son efectivamente inevitables en una red concurrida debido a la ley de números verdaderamente grandes . Limitar c ayuda a reducir la posibilidad de latencias de transmisión inesperadamente largas y mejora los tiempos de recuperación después de una interrupción transitoria.

Por ejemplo, si el techo se establece en i = 10 en un algoritmo de retroceso exponencial binario truncado (como en el estándar IEEE 802.3 CSMA/CD ^[14] ), entonces el retraso máximo es 1023 veces el intervalo, es decir, 2 ^{· 10} − 1 .

La selección de un límite de retroceso adecuado para un sistema implica lograr un equilibrio entre la probabilidad de colisión y la latencia. Al aumentar el límite, se produce una reducción exponencial de la probabilidad de colisión en cada intento de transmisión. Al mismo tiempo, aumentar el límite también aumenta exponencialmente el rango de posibles tiempos de latencia para una transmisión, lo que conduce a un rendimiento menos determinista y a un aumento de la latencia promedio. El valor límite óptimo para un sistema es específico tanto de la implementación como del entorno. ^[15]

Dada una distribución uniforme de tiempos de retardo, el tiempo de retardo esperado es la media de las posibilidades. Después de c colisiones en un algoritmo de retardo exponencial binario, el retraso se elige aleatoriamente de [0, 1, ..., N ] ranuras, donde N = 2 ^c − 1 , y el tiempo de retardo esperado (en ranuras) es

${\displaystyle \operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}.}$

Por ejemplo, el tiempo de retroceso esperado para la tercera colisión ( c = 3 ), se podría calcular primero el tiempo de retroceso máximo, N :

$Estilo de visualización N=2^{c}-1}$

$Estilo de visualización N=2^{3}-1=8-1}$

${\estilo de visualización N=7,}$

y luego calcular la media de las posibilidades de tiempo de retroceso:

${\displaystyle \operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2^{c}-1}{2}}}$.

que es, para el ejemplo, E (3) = 3,5 ranuras.

• Teoría del control
• Cadena de Markov
• Proceso de decisión de Markov

• Tanenbaum, Andrew; Wetherall, David (2010). Redes informáticas (5.ª ed.). Pearson. ISBN 978-0132126953.

 Este artículo incorpora material de dominio público de la Norma Federal 1037C. Administración de Servicios Generales . Archivado desde el original el 22 de enero de 2022.