Velocidad de obturación exponencial

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 11 de septiembre de 2019; las comprobaciones requieren 3 ediciones .

El retroceso exponencial es un algoritmo que utiliza retroalimentación para disminuir multiplicativamente la frecuencia de algún proceso para encontrar gradualmente una frecuencia aceptable.

Obturador Exponencial Binario / Obturador Exponencial Truncado

En muchas redes informáticas, el término retroceso exponencial binario o retroceso exponencial binario truncado se refiere a un algoritmo para reducir las transmisiones repetidas del mismo bloque de datos, a menudo como parte de las medidas para evitar la congestión de la red.

Algunos ejemplos son el reenvío de tramas de datos en redes de acceso múltiple con detección de portadora y prevención de colisiones (CSMA/CA) y acceso múltiple con detección de portadora y detección de colisión (CSMA/CD), donde este algoritmo es parte del método de acceso al canal utilizado para enviar datos a través de estas redes. En las redes Ethernet , este algoritmo se usa típicamente para programar retransmisiones después de colisiones. El reenvío se retrasa una cantidad de tiempo que depende del intervalo de tiempo y el número de intentos de reenvío.

Después de c colisiones, se elige un número aleatorio de intervalos de tiempo entre 0 y 2 s −1. Después de la primera colisión, cada remitente esperará 0 o 1 espacio de tiempo. 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 reenvío, el número de opciones de retraso crece exponencialmente.

La palabra "truncado" significa que después de un cierto número de incrementos, el crecimiento exponencial se detiene, es decir, el tiempo de espera de retransmisión alcanza un techo y después de eso ya no crece. Por ejemplo, si el límite máximo se establece en i = 10 (como en el estándar IEEE 802.3 CSMA/CD [1] ), el retraso máximo es de 1023 intervalos de tiempo.

Dado que estos retrasos provocan colisiones con otras estaciones que envían datos, existe la posibilidad de que en una red ocupada, cientos de personas queden atrapadas en un solo conjunto de colisiones. Debido a la existencia de tal posibilidad, el proceso termina después de 16 intentos de transmisión.

Un ejemplo de un algoritmo de remojo exponencial

Este ejemplo está tomado de la descripción del protocolo Ethernet [2] , donde el remitente tiene la oportunidad de saber al momento de enviar la trama que ha ocurrido una colisión (es decir, otro host intentó enviar datos). Si ambos hosts intentaran reenviar los datos tan pronto como se produjera la colisión, se produciría la siguiente colisión y esta secuencia continuaría para siempre. Los hosts deben elegir un valor aleatorio dentro de un rango aceptable para garantizar que esta situación no ocurra, por lo que se utiliza el algoritmo de absorción exponencial. Aquí se usa el número 51,2 µs como ejemplo, pero este es el intervalo de tiempo para un enlace Ethernet de 10 Mbit/s (consulte Tiempo de intervalo ) . Pero en la práctica, 51,2 µs pueden sustituirse por cualquier otro valor positivo.

Cuando ocurra la primera colisión, envíe una "Señal de congestión" para evitar que se envíen más datos.
Reenvía la trama después de un retraso de 0 o 51,2 µs, elegido al azar.
Si el envío falla, vuelva a enviar la trama después de un retraso de 0, 51,2 µs, 102,4 µs o 153,6 µs.
Si esto falla, vuelva a enviar la trama después de un retraso 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 envío fallido, vuelva a enviar la trama después de un retraso de k · 51,2 µs, donde k es un número entero aleatorio entre 0 y 2 s −1.

Exposición esperada

Si se proporciona una distribución uniforme de los tiempos de inmersión, la expectativa del tiempo de inmersión es el promedio de todos los valores posibles. Es decir, después de c colisiones, el número de intervalos de recuperación está en el intervalo [0, 1, …, N ] donde N = 2 s −1, y el tiempo de recuperación esperado (en intervalos) es

{\frac{1}{N+1}}\sum_{{i=0}}^{{N}}i

Por ejemplo, la velocidad de obturación esperada para la tercera colisión ( c = 3) se puede calcular primero para el tiempo máximo de obturación N :

N=2^{c}-1

N=2^{3}-1=8-1

N=7

... y luego calcule el valor promedio entre todas las opciones de exposición:

\nombre del operador {E}(c)={\frac {1}{N+1}}\sum_{{i=0}}^{{N}}i

\operatorname {E}(3)={\frac {1}{7+1}}\sum_{{i=0}}^{{7}}i={\frac {1}{8}}( 0+1+2+3+4+5+6+7)={\frac{28}{8))

\nombre del operador {E}(3)=3.5

… obteniendo 3.5 como el número esperado de ranuras de absorción después de tres colisiones.

La derivación anterior es en gran medida innecesaria cuando te das cuenta de que el promedio de enteros sucesivos es igual al promedio de los números más pequeños y más grandes del conjunto. Esto significa que el promedio de un conjunto A de enteros consecutivos a 0 , a 1 , a 2 , … a m es simplemente el promedio de a 0 y a m o ( a 0 + a m )/2.

En la aplicación al problema anterior de encontrar el tiempo de exposición esperado, la fórmula se simplifica:

\nombre del operador {E}(c)={\frac {2^{c}-1}{2}}

... o, en un caso particular, interpretado como la mitad del tiempo de retardo máximo posible.

También tenga en cuenta que el gran total es un número triangular , como igual a...

{\frac{(2^{c}-1)2^{c}}{2}}={\frac{N(N+1)}{2}}

…que cancela con un denominador más allá de la suma, dejando solo…

{\ fracción {N}{2}}={\ fracción {2^{c}-1}{2}}

Enlaces

↑ Estándar IEEE 802.3-2008 . IEEE. Consultado: 22 de septiembre de 2010.
↑ Redes informáticas , Peterson y Davie