Algoritmo di backoff esponenziale binario

In telecomunicazioni l'algoritmo di backoff esponenziale è un algoritmo utilizzato nel protocollo di accesso multiplo CSMA/CD per decidere il tempo di subentro in trasmissione su mezzo condiviso da parte di una o più stazioni (host) trasmittenti una volta che è stata riscontrata una collisione. L'algoritmo si applica in seguito alla ricezione della sequenza di jamming che definisce il messaggio di interruzione della trasmissione del pacchetto.

Come è ben noto Ethernet utilizza il protocollo CSMA/CD, cioè il canale sul quale vengono trasmessi i frame viene condiviso da più stazioni (Multiple Access) che sono in grado di vedere quando il canale è libero o meno (rilevamento della portante o Carrier Sense) e di rilevare le collisioni (Collision Detection). La caratteristica principale del protocollo CSMA/CD è che una volta rilevata una collisione, si attende un intervallo casuale prima di ritrasmettere, questo intervallo viene calcolato ogni volta tramite l'algoritmo di backoff esponenziale.

L'algoritmo

1. Si calcola il tempo $T_{p}$ di propagazione di andata e ritorno nel caso peggiore (2τ).
2. Per la prima collisione, i due host coinvolti nell'errore di trasmissione scelgono a caso tra 0 e 1. L'host che sceglie 0 non ritrasmette, mentre quello che sceglie 1 ritrasmette.
3. Qualora entrambi gli host scelgano lo stesso numero, si verifica una nuova collisione e quindi si divide il tempo in intervalli $P$ che durano $T_{p}$.
4. Alla collisione i-esima (con $1\leq i\leq 10$):
   1. si sceglie casualmente un numero $N$, tale che $0\leq N<2^{i}-1$.
   2. si attendono $N\cdot P$ intervalli prima di ritentare la trasmissione.
5. Per i tentativi successivi i rimane costante a 10.
6. Se ci si trova alla $16$-esima collisione viene comunicato un errore in trasmissione.

Tutte le trasmissioni vengono effettuate a intervalli di 2τ (Round Trip Delay).

Come si può notare dall'algoritmo, $N$ cresce esponenzialmente con il numero di collisioni avvenute, questo garantisce che il tempo di ritrasmissione sia minimo se le stazioni a collidere sono poche e che invece sia molto alto in caso le collisioni siano molte cioè ci siano molte stazioni a trasmettere. La scelta dell'esponente massimo 16 (limite di back-off) è stata fatta studiando il tempo che un frame può impiegare a propagarsi in un cavo di lunghezza massima e decidendo un periodo ragionevole di attesa prima di comunicare un errore di rete.

L'algoritmo in pseudo-codice

if tentativo=1 // primo tentativo di ritrasmissione del frame
then
   max:=2
otherwise
   if tentativo < limite_di_backoff
   then max:=max x2
wait(2t x random(0,max-1))