El retroceso exponencial es un algoritmo que utiliza la retroalimentación para disminuir multiplicativamente la tasa de algún proceso, con el fin de encontrar gradualmente una tasa aceptable.
Algoritmo de retroceso exponencial binario
En una variedad de redes de computadoras , el retroceso exponencial binario o el retroceso exponencial binario truncado se refiere a un algoritmo utilizado para espaciar las retransmisiones repetidas del mismo bloque de datos , a menudo para evitar la congestión de la red .
Algunos ejemplos son la retransmisión de tramas en redes de acceso múltiple con detección de portadora con prevención de colisiones (CSMA / CA) y acceso múltiple con detección de colisión (CSMA / CD), donde este algoritmo es parte del método de acceso al canal utilizado para enviar datos en estas redes. redes. En las redes Ethernet , el algoritmo se usa comúnmente para programar retransmisiones después de colisiones. La retransmisión se retrasa por una cantidad de tiempo derivada del tiempo del intervalo (por ejemplo, el tiempo que se tarda en enviar 512 bits, es decir, 512 bits ) y el número de intentos de retransmisión.
Después de c colisiones, se elige un número aleatorio de intervalos de tiempo entre 0 y 2 c - 1 . Después de la primera colisión, cada remitente esperará 0 o 1 franja horaria. Después de la segunda colisión, los remitentes esperarán entre 0 y 3 intervalos de tiempo ( inclusive ). Después de la tercera colisión, los remitentes esperarán entre 0 y 7 intervalos 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 .
El 'truncado' simplemente significa que después de un cierto número de aumentos, la exponenciación se detiene; es decir, el tiempo de espera de retransmisión alcanza un límite y, a partir de entonces, no aumenta más. Por ejemplo, si el límite máximo se establece en i = 10 (como en el estándar IEEE 802.3 CSMA / CD [1] ), entonces el retardo máximo es de 1023 intervalos de tiempo. Esto es útil porque estos retrasos hacen que otras estaciones que están enviando colisionen también. Existe la posibilidad de que, en una red ocupada, cientos de personas queden atrapadas en un solo conjunto de colisión. [2]
Ejemplo de algoritmo de retroceso exponencial
Este ejemplo es del protocolo Ethernet , [3] donde un host de envío puede saber cuándo ha ocurrido una colisión (es decir, otro host ha intentado transmitir), cuándo está enviando una trama. Si ambos hosts intentaran retransmitir tan pronto como ocurriera 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 asegurarse de que esta situación no ocurra. Por tanto, se utiliza un algoritmo de retroceso exponencial. El valor '51 .2 μs 'se utiliza aquí como ejemplo porque es el tiempo de ranura para una línea Ethernet de 10 Mbit / s (consulte Tiempo de ranura ). Sin embargo, en la práctica, 51,2 μs podrían sustituirse por cualquier valor positivo.
- Cuando ocurre una colisión por primera vez, envíe una "señal de interferencia" para evitar que se envíen más datos.
- Vuelva a enviar un fotograma después de 0 segundos o 51,2 μs, elegido al azar.
- Si eso falla, vuelva a enviar la trama después de 0 s, 51,2 μs, 102,4 μs o 153,6 μs.
- Si eso aún no funciona, vuelva a enviar el fotograma después de k · 51,2 μs , donde k es un número entero aleatorio entre 0 y 2 3 - 1 .
- En general, después del c- ésimo intento fallido, vuelva a enviar la trama después de k · 51,2 μs , donde k es un número entero aleatorio entre 0 y 2 c - 1 .
Retroceso esperado
Dada una distribución uniforme de los tiempos de espera , el tiempo de espera esperado es la media de las posibilidades. Es decir, después de c colisiones, el número de ranuras de retroceso está en [0, 1, ..., N ] , donde N = 2 c - 1 y el tiempo de retroceso esperado (en ranuras) es
Por ejemplo, el tiempo de retroceso esperado para la tercera colisión ( c = 3 ), primero se podría calcular el tiempo de retroceso máximo, N :
y luego calcule la media de las posibilidades de tiempo de espera:
- .
que es, por ejemplo, E (3) = 3,5 ranuras.
Ver también
Referencias
- ^ "Estándar IEEE 802.3-2015" . IEEE . Consultado el 13 de marzo de 2018 . (compra)
- ^ Redes de computadoras, 5ª edición, p. 303 , Tanenbaum
- ^ Redes de computadoras , Peterson y Davie
- Este artículo incorpora material de dominio público del documento de la Administración de Servicios Generales : "Norma Federal 1037C" .