Algoritmo di backoff esponenziale binario

Da Wikipedia, l'enciclopedia libera.

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 trasmittenti una volta che è stata riscontrata una collisione.

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). Una 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[modifica | modifica sorgente]

  1. Si calcola il tempo T_p di propagazione di andata e ritorno nel caso peggiore (2t).
  2. Si divide il tempo in intervalli P che durano T_p.
  3. Alla collisione i-esima (con 1\leq i\leq 16):
    1. si sceglie casualmente un numero N, tale che 0\leq N < 2^i.
    2. si attendono N\cdot P intervalli prima di ritentare la trasmissione.
  4. Se ci si trova alla 16-esima collisione viene comunicato un errore in trasmissione.

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 è 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.

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