Algoritmo de Recuo Binário Exponencial

Em vários artigos do Vovó Viu a Rede eu já falei de uma atitude comum a muitos dos protocolos: quando há uma colisão, as máquinas que tentaram enviar esperam um tempo aleatório para tentar novamente. A única coisa que ainda não tinha ficado clara é como se define este tempo aleatório.

Até agora.

A este trabalho de definir um tempo de espera aleatório foi dado o feioso nome de recuo binário exponencial. Apesar do nome feio, a explicação é simples. Para entender isso, vamos a mais uma das minhas metáforas.

***

Imagine um destes programas de debates, com um monte de gente querendo falar. Quando dois começassem a falar juntos, ambos parariam e ambos jogariam uma moeda. Quem tirasse cara esperaria um minuto para começar a falar, quem tirasse coroa esperaria dois minutos.

Claro que acontecia muitas vezes o azar de os dois tirarem o mesmo lado da moeda. Quando isso acontecia, eles trocavam as moedas por dados: cada um jogava um dado e cada um esperava o número de minutos que tivesse caído nos dados. Se novamente eles dessem o azar de tirar o mesmo número nos dados, partiriam para jogar dois dados ao mesmo tempo. Se, azar dos azares, eles novamente tirassem números iguais, seria a vez de jogar naquelas roletas de cassino.

Veja que a cada vez que uma colisão acontecia em seqüência, o sorteio era feito de maneira que as chances de haver uma colisão eram cada vez menores. É exatamente isso que faz o recuo binário exponencial.

***

Quando há uma colisão, o protocolo inicialmente sorteia dois intervalos de tempo entre os transmissores que colidiram. Se por acaso houver uma nova colisão, o protocolo sorteia quatro intervalos. Em caso de nova colisão, o número de intervalos sorteados sobe para oito, e daí em diante, sempre em potências de dois, com o limite máximo de 1024 espaços.

Colocando em termos mais claros ainda: o número de intervalos de tempo a serem sorteados entre os transmissores que colidiram é igual a dois elevado ao número de colisões seguidas.

***

Este procedimento é eficiente tanto em momentos de baixo tráfego quanto de alto, pois ele vai se adaptando gradualmente.

Se não houvesse esse aumento gradual, em momentos de pico ninguém transmitiria. Veja só: imagine que uma rede tem 50 máquinas interligadas, todas ávidas por um espaço para transmitir. Haveria uma colisão atrás da outra, sem parar, sempre havendo sorteios entre elas para tentarem pegar o primeiro intervalo de tempo ou o segundo.

Para que uma máquina conseguisse transmitir, seria necessário que só ela recebesse um intervalo e todas as outras recebessem o outro, o que é muito improvável. Com o aumento gradual de intervalos a serem sorteados, as chances de que duas máquinas recebam o mesmo diminuem bastante.

Em uma situação inversa, no caso de poucas máquinas querendo transmitir, o sorteio de poucos intervalos já é suficiente para resolver o problema das colisões. Se sempre fossem sorteados um número muito grande intervalos, haveria um desperdício muito grande de tempo, gerando retardos desnecessários.

Imagine no exemplo do programa de debates, aí de cima: duas pessoas tentam falar ao mesmo tempo e partem direto para a roleta de cassino, e a primeira tem que esperar 20 minutos e a outra 45, e enquanto isso não aparece mais ninguém querendo falar. Não tem cabimento.

***

Este é, então, o algoritmo de recuo binário exponencial. Simples, mas eficiente.

Veja mais sobre alguns protocolos que usam este algoritmo:
Protocolo MACA
Protocolos CSMA que permitem colisão
Protocolo Aloha