Algoritmo di backoff esponenziale binario

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

Commento: Questa voce manca completamente di fonti

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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.

1. Si calcola il tempo ${\displaystyle 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 ${\displaystyle P}$ che durano ${\displaystyle T_{p}}$.
4. Alla collisione i-esima (con ${\displaystyle 1\leq i\leq 10}$):
   1. si sceglie casualmente un numero ${\displaystyle N}$, tale che ${\displaystyle 0\leq N<2^{i}-1}$.
   2. si attendono ${\displaystyle 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 ${\displaystyle 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, ${\displaystyle 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.

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))

Portale Telematica: accedi alle voci di Wikipedia che parlano di reti, telecomunicazioni e protocolli di rete