title: Algoritmo di backoff esponenziale binario
text: # 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
  
  * Si calcola il tempo $T_{p}$ di propagazione di andata e ritorno nel caso peggiore (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.
  * 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}$.
  * Alla collisione i-esima (con $1\leq i\leq 10$):
     * si sceglie casualmente un numero $N$, tale che $0\leq N<2^{i}-1$.
     * si attendono $N\cdot P$ intervalli prima di ritentare la trasmissione.
  * Per i tentativi successivi i rimane costante a 10.
  * 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.
  
  