Requisito previo: conceptos básicos de CSMA/CD , detección de colisiones en CSMA/CD
El algoritmo de retroceso es un mecanismo de resolución de colisiones que se utiliza en los protocolos MAC de acceso aleatorio (CSMA/CD). Este algoritmo se usa generalmente en Ethernet para programar retransmisiones después de colisiones.
Si se produce una colisión entre 2 estaciones, pueden reiniciar la transmisión tan pronto como puedan después de la colisión. Esto siempre conducirá a otra colisión y formará un bucle infinito de colisiones que conducirá a un interbloqueo. Para evitar tal escenario, se utiliza un algoritmo de retroceso.
Consideremos un escenario de 2 estaciones A y B transmitiendo algunos datos:
Después de una colisión, el tiempo se divide en intervalos discretos ( T slot ) cuya longitud es igual a 2t, donde t es el máximo retardo de propagación en la red.
Las estaciones involucradas en la colisión eligen aleatoriamente un número entero del conjunto K, es decir, {0, 1}. Este conjunto se denomina ventana de contención. Si las fuentes vuelven a chocar porque eligieron el mismo número entero, el tamaño de la ventana de contención se duplica y se convierte en {0, 1, 2, 3}. Ahora, las fuentes involucradas en la segunda colisión eligen aleatoriamente un número entero del conjunto {0, 1, 2, 3} y esperan esa cantidad de intervalos de tiempo antes de volver a intentarlo. Antes de intentar transmitir, escuchan el canal y transmiten solo si el canal está inactivo. Esto hace que la fuente que eligió el número entero más pequeño en la ventana de contención logre transmitir su trama.
Entonces, el algoritmo de retroceso define un tiempo de espera para las estaciones involucradas en la colisión , es decir, cuánto tiempo debe esperar la estación para volver a transmitir.
Waiting time = back–off time Let n = collision number or re-transmission serial number. Then, Waiting time = K * Tslot where K = [0, 2n – 1 ]
Ejemplo –
Caso-1:
Suponga que 2 estaciones A y B comienzan a transmitir datos (Paquete 1) al mismo tiempo y luego ocurre una colisión. Entonces, el número de colisión n para ambos datos (Paquete 1) = 1. Ahora, ambas estaciones eligen aleatoriamente un número entero del conjunto K, es decir, {0, 1}.
- Cuando tanto A como B eligen K = 0
–> Tiempo de espera para A = 0 * Intervalo T = 0
Tiempo de espera para B = 0 * Intervalo T = 0Por lo tanto, ambas estaciones transmitirán al mismo tiempo y, por lo tanto, se producirá una colisión.
- Cuando A elige K = 0 y B elige K = 1
–> Tiempo de espera para A = 0 * Intervalo T = 0
Tiempo de espera para B = 1 * Intervalo T = Intervalo TPor lo tanto, A transmite el paquete y B espera el intervalo de tiempo T para transmitir y, por lo tanto, A gana.
- Cuando A elige K = 1 y B elige K = 0
–> Tiempo de espera para A = 1 * T slot = T slot
Tiempo de espera para B = 0 * T slot = 0Por lo tanto, B transmite el paquete y A espera el intervalo de tiempo T para transmitir y, por lo tanto, B gana.
- Cuando tanto A como B eligen K = 1
–> Tiempo de espera para A = 1 * Intervalo T = Intervalo T Tiempo de
espera para B = 1 * Intervalo T = Intervalo TPor lo tanto, ambos esperarán el mismo intervalo de tiempo T y luego transmitirán. Por lo tanto, se produce la colisión.
Probability that A wins = 1/4 Probability that B wins = 1/4 Probability of collision = 2/4
Caso-2:
Suponga que A gana en el Caso 1 y transmite sus datos (Paquete 1). Ahora, tan pronto como B transmite su paquete 1, A transmite su paquete 2. Por lo tanto, se produce una colisión. Ahora la colisión no. n se convierte en 1 para el paquete 2 de A y se convierte en 2 para el paquete 1 de B.
Para el paquete 2 de A, K = {0, 1}
Para el paquete 1 de B, K = {0, 1, 2, 3}
Probability that A wins = 5/8 Probability that B wins = 1/8 Probability of collision = 2/8
Entonces, la probabilidad de colisión disminuye en comparación con el Caso 1.
Ventaja –
- La probabilidad de colisión disminuye exponencialmente.
Desventajas –
- Efecto captura: Estación que gana unas sigue ganando.
- Funciona solo para 2 estaciones o hosts.
Pregunta de práctica GATE –