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 wikitesto]

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

Come si può notare dall'algoritmo, 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