CSMA

Nei protocolli ALOHA visti, i nodi prendono la decisione di trasmettere indipendentemente dall'attività degli altri nodi collegati al canale broadcast. In particolare un nodo non presta attenzione al fatto che vi sia un altro nodo che sta già trasmettendo, o nello scenario in cui nodo stia già trasmettendo, che un altro nodo ha cominciato a trasmettere interferendo con la sua trasmissione. CSMA introduce due features:

  1. rilevamento della portante un nodo ascolta il canale prima di trasmettere. Se il canale sta già trasmettendo un frame, il nodo aspetta finché il canale è libero per un intervallo di tempo e quindi inizia la trasmissione
  2. rilevamento della collisione il nodo che sta trasmettendo rimane contemporaneamente in ascolto nel canale. Se osserva che un altro nodo sta trasmettendo un frame che interferisce col suo, arresta la propria trasmissione, aspetta un intervallo di tempo casuale e poi ripete il processo.

La prima domanda che ci si può chiedere è:

  • perché se tutti i nodi eseguono il rilevamento della portante, si verificano collisioni?
    Questo lo si può meglio comprendere con un diagramma spazio temporale:
    Pasted image 20230420164815.png
    La linea orizzontale in cima, in cui ci sono le etichette A, B, C, D, rappresentano i nodi che partecipano al collegamento broadcast (nello spazio).
    B effettuando il rilevamento della portante, verifica che nessun nodo sta trasmettendo, quindi all'instante inizia a trasmettere, la sua trasmissione si muove in entrambe le direzioni (destra e sinistra) poiché deve raggiungere tutti gli altri nodi.
    Ad un certo punto D sfruttando il rilevamento della portante, vede che nessun nodo sta trasmettendo, poiché non gli è ancora arrivato nulla da nessun nodo (in particolare non gli sono arrivati i frame di B), così comincia a trasmettere, ad un certo punto il suo frame collide con quello inviato da B. In questo caso non c'è rilevamento della collisione e i nodi continuano a trasmettere i loro frame. I frame in questo caso vengono corrotti: la collisione provoca interferenze nel canale di comunicazione, e i segnali trasmessi si sovrappongono, generando un segnale risultate corrotto e non decifrabile correttamente.

A questo punto entra in gioco, ed è utile il rilevamento, della collisione.

Con rilevamento della collisione (CSMA/CD):
Pasted image 20230420165752.png
la figura mostra lo stesso scenario precedente, tuttavia in questo caso, poco dopo il rilevamento delle collisioni i nodi interrompono la trasmissione. La possibilità di poter interrompere la trasmissione quando si rilevano delle collisioni migliora il protocollo, evitando di trasmettere dei frame danneggiati dalle interferenze.

Prima di analizzare CSMA/CD riassumiamo le sue operazioni dal punto di vista di una scheda di rete collegata ad un canale broadcast:

  1. La scheda ottiene direttamente un datagramma dal livello di rete, prepara un frame a livello di collegamento e lo sistema in un suo buffer;
  2. quando riscontra che il canale è libero (cioè, non vi è energia di segnale che entri nella scheda del canale), inizia la trasmissione del frame. Se il canale risulta occupato, resta in attesa sino al momento in cui non rileva più il segnale e solo allora inizia l'invio del frame;
  3. durante la trasmissione verifica la presenza di eventuali segnali provenienti da altre schede di rete sul canale broadcast;
  4. la scheda di rete, se trasmette l'intero frame senza rilevare energia di segnale proveniente da altre schede, ha finito il suo lavoro; altrimenti, se riscontra energia di segnale durante la trasmissione, la interrompe immediatamente;
  5. dopo aver annullato la trasmissione, la scheda di rete aspetta un tempo casuale e ritorna al passo 2.
    Attendere per un periodo di tempo casuale è necessario, poiché se si attendesse lo stesso periodo di tempo, la collisione si verificherebbe di continuo.
    Qual è l'intervallo opportuno per questa attesa casuale (detto anche tempo di backoff):
  • se l'intervallo è grande il numero di nodi che collidono è piccolo, ma c'è il rischio che il canale risulti inutilizzato per diverso tempo;
  • se l'intervallo è grande il numero di nodi che collidono è grande e che i nodi continuino a collidere.
    Idealmente occorrerebbe un numero piccolo quando il numero di nodi che collidono è piccolo e un numero grande quando il numero di nodi che collidono è grande.
    L'algoritmo di binary exponential backoff (attesa binaria esponenziale), usato anche in Ethernet, risolve il problema in maniera elegante:
  • quando un nodo riscontra l'n-esima collisione durante la trasmissione di un dato frame, stabilisce casualmente un valore , quindi risulta che più grande è il numero di collisioni, più largo sarà l'intervallo da cui viene estratto .
    In Ethernet, l'intervallo di tempo che un nodo deve aspettare è pari a quello necessario per inviare volte 512 bit e il valore massimo che n può assumere è 10.

Esempio
...

Supponiamo che la scheda di rete tenti per la prima volta di inviare un frame e che mentre lo trasmette rilevi una collisione. Allora sceglierà dall'insieme , ogni elemento con pari probabilità. Se la scheda sceglie 0, allora tenta immediatamente una nuova trasmissione, al rilevamento di una collisione. Se sceglie 1 allora la scheda aspetta il tempo necessario per inviare 512 bit (0,01 microsecondi per Ethernet a 100 Mpbs) prima di ritentare la trasmissione. Dopo una seconda collisione, è scelto con uguale probabilità fra . Dopo tre collisioni l'insieme sarà e via via aumenterà.

Efficienza di CSMA/CD
...

Quando un solo nodo ha un frame da inviare può trasmettere alla massima velocità del canale.
Se invece i nodi sono numerosi l'effettiva velocità di trasmissione sul canale può risultare notevolmente inferiore.

Definiamo efficienza di CSMA/CD la frazione di tempo media durante la quale i frame sono trasferiti sul canale senza collisioni in presenza di un alto numero di nodi attivi, con un elevata quantità di frame da inviare.

Indichiamo con:

  • = tempo massimo che occorre al segnale per propagarsi fra una coppia di schede di rete
  • = tempo necessario per trasmettere un frame della maggiore dimensione possibile (circa 1,2 ms in Ethernet a 10 Mbps)
    avremo la semplice approssimazione (= efficienza CSMA/CD):
    Dalla formula si evince che:
  • quando tende a 0, l'efficienza tende a 1;
  • al crescere di l'efficienza tende a 1.
    Nel momento in cui un frame si appropria del canale può trattenerlo per un periodo di tempo estremamente lungo, di conseguenza il canale svolge lavoro produttivo per la maggior parte del tempo.