Protocolli di accesso multiplo - ALOHA e CSMA

Il problema: un mezzo, molte stazioni

Sul livello di collegamento (Livello di collegamento e framingIl livello di collegamento (DLL) consegna un frame da un nodo a un nodo adiacente su un collegamento. Servizi: framing, accesso al mezzo (MAC) con indirizzi MAC a 48 bit, controllo di flusso, rilevazione e correzione degli errori. Si divide in DLC (framing, controllo di errore e di flusso) e MAC (accesso al mezzo condiviso). Il framing delimita i frame con un flag: nei protocolli a byte (flag di 8 bit, ESC) si usa il byte stuffing, in quelli a bit (flag 01111110) il bit stuffing, che inserisce uno 0 dopo ogni cinque 1 consecutivi.Livello di collegamento e framing →) i problemi si dividono in due famiglie. Il controllo del collegamento dati (Data Link Control, DLC: framing, controllo d'errore con Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →, controllo di flusso) vale sia per i collegamenti punto-punto sia per quelli condivisi. Il controllo dell'accesso al mezzo (Medium Access Control, MAC) serve solo quando il mezzo è condiviso (di solito broadcast, cioè tutti sentono tutti): decide quando una stazione può trasmettere un frame.

Il MAC consegna la PDU del livello LLC tra stazione sorgente e stazione destinazione e offre un servizio con riscontro. La PDU del MAC contiene:

I protocolli MAC si dividono in tre famiglie:

• accesso casuale (random access): ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA;
• accesso controllato (controlled access): prenotazione, polling, passaggio del testimone (token passing);
• canalizzazione (channelization): FDMA, TDMA, OFDMA, CDMA, SDMA.

Le prestazioni dei protocolli casuali (throughput, ritardo) sono calcolate in Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA →, che usa gli strumenti di Introduzione alla teoria delle codeUn sistema a coda (QS) è fatto da un processo di arrivi (di Poisson, tasso $\lambda$), una coda e uno o più servitori con tasso di servizio $\mu$. Carico offerto $G=\lambda/\mu$, fattore di carico $\rho=\lambda/(m\mu)$: il sistema è stabile solo se $\rho<1$, e allora il throughput è $\lambda$ (altrimenti è $m\mu$). Legge di Little: $E[x]=\lambda E[s]$, valida per qualsiasi disciplina. Coda M/M/1: $E[x]=\frac{\rho}{1-\rho}$, $E[s]=\frac{1/\mu}{1-\rho}$, $E[w]=\frac{\rho/\mu}{1-\rho}$. Con servizio deterministico (M/D/1, caso particolare di Pollaczek-Khinchin): $E[w]=\frac{\rho}{2\mu(1-\rho)}$. Il ritardo cresce senza limite quando $\rho\to1$.Introduzione alla teoria delle code →. Qui si descrivono gli algoritmi. La stessa famiglia di protocolli, vista dal corso di comunicazioni con il confronto FDMA/TDMA, è in Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMAQuando più nodi condividono un mezzo serve un protocollo di accesso (MAC). Accesso deterministico: FDMA (una banda per utente) e TDMA (uno slot per utente in una trama): nessuna collisione, a ogni utente $\frac{R_b}N$ meno le perdite di sincronismo. Accesso aleatorio: ALOHA puro ($S=Ge^{-2G}$, massimo $\frac1{2e}=0{,}184$ in $G=0{,}5$), slotted ALOHA ($S=Ge^{-G}$, massimo $\frac1e=0{,}368$ in $G=1$), CSMA (si ascolta prima di trasmettere: nel non persistente $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, con $a=\frac{\tau_P}{t_P}$ piccolo si arriva a $\approx0{,}8$-$0{,}9$).Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA →; il riscontro con ACK e timeout è lo stop-and-wait di Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →.

Accesso casuale: lo scopo

Nei metodi ad accesso casuale (o a contesa) nessuna stazione è superiore alle altre: chi ha dati da inviare usa una procedura per decidere se trasmettere oppure no, e non c'è un istante prestabilito per trasmettere. Le stazioni competono per il canale (processo di contesa). Se due stazioni trasmettono nello stesso momento c'è una collisione e i frame coinvolti sono persi con alta probabilità.

Ogni protocollo risponde a quattro domande:

1. quando può una stazione accedere al mezzo?
2. che cosa fa se il mezzo è occupato?
3. come si stabilisce il successo o il fallimento di una trasmissione?
4. che cosa fa se c'è un conflitto di accesso?

ALOHA puro (pure ALOHA)

Progettato all'inizio degli anni '70 per collegare calcolatori su isole diverse dell'arcipelago delle Hawaii (non c'erano cavi): è il protocollo di ALOHAnet, la prima rete dati a pacchetti senza fili (Storia e struttura di InternetInternet nasce da ARPANET (1969), una rete a commutazione di pacchetto finanziata dal Dipartimento della Difesa USA. Con TCP/IP (1972-77) i controlli d'errore passano dai nodi della rete ai calcolatori agli estremi (end host): è questo che la rende scalabile. DNS (1983), WWW (1989), apertura commerciale (1995). Oggi è una rete di reti: ISP locali, regionali e nazionali, collegati tra loro direttamente (peering) o tramite punti di interscambio (NAP/IXP, per esempio il MIX di Milano); IANA coordina indirizzi e DNS root, IETF/IRTF/IAB/ISOC definiscono standard e ricerca.Storia e struttura di Internet →).

Definizione (algoritmo dell'ALOHA puro).

1. Quando accedere: appena si ha qualcosa da trasmettere.
2. Mezzo occupato? Si trasmette comunque, senza guardare.
3. Esito: si usa uno schema ACK/NACK con timeout. Se l'ACK non arriva entro il timeout, si deduce una collisione.
4. Conflitto: si attende un tempo casuale (backoff) e si ritrasmette; si ripete finché non va a buon fine.

Il backoff è casuale per un motivo preciso: due stazioni che hanno avuto una collisione, se aspettassero lo stesso tempo, ritrasmetterebbero di nuovo insieme e si scontrerebbero all'infinito.

Basta un solo bit di un frame che coesiste sul canale con un solo bit di un altro frame per distruggerli entrambi: l'ALOHA puro non ha nessuna regola che limiti la sovrapposizione.

Definizione (tempo vulnerabile dell'ALOHA puro). Se la stazione B comincia a trasmettere un frame al tempo $t$ (il frame dura $t_F$), il frame non subisce collisione solo se nessun altro frame (nuovo o ritrasmesso) parte da $t_F$ secondi prima a $t_F$ secondi dopo il suo inizio. Il tempo vulnerabile (vulnerable time) è quindi $$T_{vuln}=2\,t_F.$$

Perché due $t_F$: un frame $A$ iniziato prima di $t-t_F$ è già finito quando B parte, quindi non disturba; ma un frame iniziato in $[t-t_F,t]$ è ancora in corso quando B comincia, e uno iniziato in $[t,t+t_F]$ si sovrappone alla coda di B. L'intervallo critico è lungo $t_F+t_F$.

Esempio. Frame da $1000$ bit su un canale a $1$ Mbit/s: $t_F=1$ ms. Se B parte a $t=10$ ms, qualsiasi altro frame che parta tra $9$ ms e $11$ ms lo distrugge: $T_{vuln}=2$ ms. Nell'esempio delle slide quattro stazioni inviano due frame ciascuna e solo due frame (quelli delle stazioni 1 e 3) sopravvivono, perché tutti gli altri si sovrappongono almeno in parte a un altro.

ALOHA a slot (slotted ALOHA)

Definizione (algoritmo dello slotted ALOHA). Il tempo è diviso in slot di durata $t_F$ e le stazioni sono costrette a iniziare la trasmissione solo all'inizio di uno slot. Un frame generato a metà slot aspetta l'inizio del successivo (attesa media $t_F/2$). Per il resto l'algoritmo è quello dell'ALOHA puro (ACK, timeout, backoff casuale).

Poiché tutti partono solo a inizio slot, due frame si sovrappongono o del tutto o per niente: la collisione avviene solo se due frame sono pronti nello stesso slot. Il tempo vulnerabile si dimezza: $$T_{vuln}=t_F.$$

Il prezzo è la sincronizzazione: tutte le stazioni devono conoscere l'inizio degli slot.

I due protocolli a confronto sulle slide: il throughput massimo normalizzato dell'ALOHA puro è circa $0{,}18$, quello dello slotted ALOHA circa $0{,}37$ ($1/e$), cioè il doppio (Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA → dà la dimostrazione).

CSMA: ascoltare prima di parlare

Definizione (CSMA). Carrier Sense Multiple Access: ogni stazione ascolta il mezzo prima di trasmettere (listen before talk) e trasmette solo se lo trova libero.

La probabilità di collisione diminuisce, ma non si annulla, per colpa del ritardo di propagazione $\tau_p$: una stazione può sentire il canale libero solo perché il primo bit trasmesso da un'altra stazione non l'ha ancora raggiunta.

Definizione (tempo vulnerabile del CSMA). È il tempo di propagazione (massimo) $\tau_p$ da un estremo all'altro del mezzo: $$T_{vuln}=\tau_p.$$

Perché: se una stazione inizia a trasmettere e un'altra tenta di farlo entro $\tau_p$, l'altra non ha ancora sentito niente e c'è collisione. Ma quando il primo bit del frame ha raggiunto l'estremo opposto, tutte le stazioni lo hanno sentito e si astengono.

Esempio. Bus di $2$ km con propagazione $2\cdot10^8$ m/s: $\tau_p=2000/(2\cdot10^8)=10^{-5}$ s $=10\ \mu$s. Frame da $1000$ bit a $10$ Mbit/s: $t_F=1000/(10^{7})=10^{-4}$ s $=100\ \mu$s. Il tempo vulnerabile è $10\ \mu$s, cioè un decimo del frame ($\tau_p/t_F=0{,}1$); per l'ALOHA puro sarebbe $2t_F=200\ \mu$s, venti volte di più ($200/10=20$). Se invece $\tau_p$ fosse paragonabile a $t_F$ (satellite, rete molto veloce), l'ascolto servirebbe a poco: la differenza tra CSMA e ALOHA sparisce (Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA →).

Le varianti: che cosa fare se il canale è occupato

Nel dettaglio del p-persistent, se il canale è libero:

1. con probabilità $p$ si invia il frame;
2. con probabilità $q=1-p$ si aspetta l'inizio dello slot successivo e si riascolta il canale:
   • se è ancora libero si torna al punto 1;
   • se è occupato, ci si comporta come dopo una collisione e si applica la procedura di backoff (per esempio il backoff esponenziale binario, definito nel dettaglio in LAN - Ethernet e Wi-FiUna LAN copre un'area limitata ed è definita dalla famiglia IEEE 802.x (802.3 Ethernet, 802.11 Wi-Fi), che divide il livello di collegamento in LLC e MAC. Ethernet è senza connessione, senza controllo di flusso e senza ACK; usa CSMA/CD 1-persistent; il frame va da 64 a 1518 byte (indirizzi di 6 byte, tipo/lunghezza, dati 46-1500, CRC di 4) e il minimo di 64 B deriva da $t_F\ge2\tau_p$. Dal 10 Mbit/s a coassiale fino al 10 Gbit/s su fibra, con switch full-duplex che eliminano le collisioni. Il Wi-Fi (802.11) usa CSMA/CA, ha i modi BSS (con access point) e ad hoc, EBSS con sistema di distribuzione; adatta il bitrate all'SNR; ha problemi del terminale nascosto e del terminale esposto, risolti in parte da RTS/CTS e NAV.LAN - Ethernet e Wi-Fi →: l'intervallo da cui si estrae l'attesa raddoppia a ogni collisione); allo scadere del timer di backoff si torna al punto 1.

La logica dei tre valori: $p=1$ è il caso 1-persistent; con $p$ piccolo si riduce la probabilità che più stazioni in attesa partano insieme, ma si spreca qualche slot di canale libero.

CSMA non persistente (quello del Wi-Fi). Diagramma di flusso: si monitora il canale; se è libero si trasmette il frame; se non arriva l'ACK si fa un backoff casuale e, finché restano tentativi, si ricomincia; se il canale è occupato si fa subito un backoff casuale e si riascolta. Il livello di collegamento usa quindi una politica di ritrasmissione stop-and-wait (Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →).

CSMA/CD (Ethernet)

Definizione (CSMA/CD). Carrier Sense Multiple Access with Collision Detection: al CSMA aggiunge la rilevazione delle collisioni mentre si trasmette. La stazione controlla il mezzo durante la trasmissione del frame:

• se il livello di energia sul canale è coerente con la trasmissione del proprio frame, va tutto bene;
• se è anormale (più alto), c'è una collisione: la trasmissione viene interrotta e si invia un breve segnale di disturbo (jamming) per avvertire tutte le altre stazioni.

Algoritmo: monitora il canale; se è libero trasmette il frame; se c'è collisione invia il segnale di jam e, se restano tentativi, fa un backoff casuale e riprova; altrimenti termina. Anche qui il livello di collegamento usa una politica stop-and-wait. Vantaggio sul CSMA: appena si capisce che un frame è perso, si smette di sprecare il canale con il resto di un frame destinato a perdersi.

Durata minima della trasmissione

Perché la rilevazione funzioni, la stazione deve accorgersi della collisione prima di aver finito di trasmettere il frame. Se avesse già inviato l'ultimo bit quando la collisione le arriva, crederebbe di aver avuto successo e non ritrasmetterebbe mai quel frame (nessun livello inferiore lo scoprirebbe).

Caso peggiore. La stazione A inizia a trasmettere a $t=0$. Un'altra stazione B, all'altro estremo del mezzo, inizia un istante prima che il segnale di A la raggiunga, cioè a $t\approx\tau_p$. La collisione avviene vicino a B, ma il suo effetto torna indietro fino ad A in altri $\tau_p$: A se ne accorge a $t\approx2\tau_p$. B invece è sicura di aver conquistato il canale solo dopo $2\tau_p$.

Formula (durata minima del frame in CSMA/CD). Per essere sicuri che una trasmissione sia andata a buon fine bisogna che $$t_F\ \ge\ 2\,\tau_p,\qquad t_F=\frac FR\ \Longrightarrow\ F\ \ge\ 2\,\tau_p\,R.$$

La seconda relazione si ottiene sostituendo $t_F=F/R$ (lunghezza del frame in bit diviso bitrate) nella prima e moltiplicando entrambi i membri per $R>0$: la disuguaglianza non cambia verso. Il significato è che il frame deve contenere almeno tanti bit quanti ne entrano sul mezzo nel tempo di andata e ritorno, $2\tau_p R$ (il prodotto banda-ritardo di Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →).

Esempio (valori delle slide). $R=10$ Mbit/s e $\tau_p=25{,}6\ \mu$s (si tratta del ritardo massimo, comprensivo dei ripetitori): $t_F\ge2\tau_p=2\cdot25{,}6=51{,}2\ \mu$s, quindi $F_{min}=10\cdot10^{6}\ \text{bit/s}\cdot51{,}2\cdot10^{-6}\ \text{s}=512$ bit $=512/8=64$ B. È proprio la lunghezza minima del frame Ethernet (LAN - Ethernet e Wi-FiUna LAN copre un'area limitata ed è definita dalla famiglia IEEE 802.x (802.3 Ethernet, 802.11 Wi-Fi), che divide il livello di collegamento in LLC e MAC. Ethernet è senza connessione, senza controllo di flusso e senza ACK; usa CSMA/CD 1-persistent; il frame va da 64 a 1518 byte (indirizzi di 6 byte, tipo/lunghezza, dati 46-1500, CRC di 4) e il minimo di 64 B deriva da $t_F\ge2\tau_p$. Dal 10 Mbit/s a coassiale fino al 10 Gbit/s su fibra, con switch full-duplex che eliminano le collisioni. Il Wi-Fi (802.11) usa CSMA/CA, ha i modi BSS (con access point) e ad hoc, EBSS con sistema di distribuzione; adatta il bitrate all'SNR; ha problemi del terminale nascosto e del terminale esposto, risolti in parte da RTS/CTS e NAV.LAN - Ethernet e Wi-Fi →). Nelle slide l'ultimo passaggio riporta $52{,}1\ \mu$s: è un refuso, il valore che dà $64$ B è $51{,}2\ \mu$s.

Prestazioni e dimensione della rete. Si confronta $\tilde\tau_p=\tau_p/t_F$ ($=a$):

• $R=10$ Mbit/s, $F=10$ kbit, $d=200$ m su cavo: $t_F=10^4/10^7=1$ ms, $\tau_p=200/(2\cdot10^8)=1\ \mu$s, quindi $\tilde\tau_p=0{,}001$: la propagazione è trascurabile, la collisione è rarissima.
• Stessa rete a $R=10$ Gbit/s: $t_F=1\ \mu$s e $\tilde\tau_p=1$: ora propagazione e trasmissione si equivalgono, e il CSMA/CD è molto meno efficiente (e il vincolo $t_F\ge2\tau_p$ non sarebbe rispettato).
• Se «si comprime» il mezzo condiviso in una scatola (hub o switch, pochi cm), $\tau_p$ diventa piccolissimo e si ottiene una mini-LAN dove il problema scompare.

Nel confronto grafico delle slide, $\tilde\tau_p=0{,}01$ è già abbastanza lontano dal caso ideale. Per l'esercizio sulla velocità massima oltre la quale le collisioni non si rilevano vedi Esercizio - Bitrate oltre il quale CSMA-CD non rileva le collisioni.

CSMA/CA (Wi-Fi)

Definizione (CSMA/CA). Carrier Sense Multiple Access with Collision Avoidance: inventato per le reti senza fili, dove non si può rilevare una collisione durante la trasmissione (la propria trasmissione sovrasta ciò che si riceve). Non si rileva, si evita.

Gli ingredienti sono quattro: IFS, finestra di contesa (CW), ACK, e opzionalmente RTS/CTS.

Spazio tra i frame (IFS, Interframe Space). Quando il canale è libero la stazione non trasmette subito: aspetta un tempo detto IFS. Il frame dati parte dopo che il canale è stato sentito libero per $DIFS$ secondi (costante del protocollo; nello standard $DIFS=SIFS+2$ slot). Gli IFS servono anche per dare priorità: chi ha un IFS più corto passa avanti. Si usano $SIFS<PIFS<DIFS$, con $SIFS=16\ \mu$s fisso nell'802.11 (concede la separazione minima: propagazione di andata e ritorno più elaborazione locale del MAC).

Handshake a due vie. Il frame dati parte solo dopo $DIFS$ di canale libero; il ricevitore risponde con un ACK esplicito dopo un tempo $SIFS$. Poiché $SIFS<DIFS$, l'ACK ha priorità su qualsiasi nuovo frame (nessuno riesce a inserirsi prima). Il livello di collegamento usa una ritrasmissione stop-and-wait: se il frame fallisce lo ritrasmette fino al successo o al numero massimo di tentativi.

Finestra di contesa e backoff. Se il canale è occupato (o dopo un fallimento) si aspetta un tempo casuale, secondo questo meccanismo:

• si definisce la finestra di contesa $CW$, espressa in slot di trasmissione (durata costante $T_{slot}$);
• quando si trova il canale occupato si sceglie un contatore di backoff $b$ intero uniforme in $[0,CW-1]$ (ciascuno dei $CW$ valori ha probabilità $1/CW$: Bernoulli, binomiale e uniforme discretaBernoulli Be(p): un solo tentativo, vale 1 con probabilità p; binomiale Bin(n, p): numero di successi in n prove indipendenti, P(X = k) = C(n,k) p^k (1−p)^(n−k), media np e varianza np(1−p); uniforme discreta: n valori equiprobabili.Bernoulli, binomiale e uniforme discreta →); il tempo di backoff è $t_b=b\,T_{slot}$;
• si parte da $CW_{min}=15$ e $CW$ raddoppia a ogni fallimento del frame ($CW_{n+1}=\min\{2\,CW_n,\,CW_{max}\}$), fino a $CW_{max}=1023$ (nell'802.11 $T_{slot}=9\ \mu$s; nello standard i valori sono $15,31,63,\dots,1023$, cioè potenze di due meno uno);
• il canale si ascolta alla fine di ogni slot: finché è libero il contatore scende di uno; quando è occupato il conto alla rovescia si congela e riparte quando il canale torna libero;
• si può trasmettere quando il contatore arriva a $0$.

Esempio. Al primo tentativo $CW=15$ e $T_{slot}=9\ \mu$s: se si estrae $b=7$ la stazione aspetta $7\cdot9=63\ \mu$s di canale libero. Se il canale diventa occupato dopo $4$ slot liberi, il contatore resta fermo a $3$ finché la trasmissione altrui non finisce, poi riprende e a $0$ si trasmette. Chi ha estratto il contatore più basso vince la contesa: è il motivo per cui le stazioni che hanno aspettato di più (contatore congelato) tendono ad andare per prime la volta successiva.

Perché la finestra raddoppia. Due stazioni in contesa estraggono lo stesso valore, e quindi collidono, con probabilità $\sum_b\frac1{CW}\cdot\frac1{CW}=\frac1{CW}$ (le due estrazioni sono indipendenti: Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →): circa $1/15=6{,}7\,\%$ con $CW=15$ (lo standard estrae tra $0$ e $CW$, cioè $16$ valori, e dà $1/16=6{,}25\,\%$: stesso ordine di grandezza). Dopo un fallimento $CW=31$ e la probabilità scende a circa $1/31\approx3{,}2\,\%$: più stazioni sono in contesa, più serve una finestra larga, e il raddoppio la allarga solo quando c'è stata una collisione. L'attesa media di un'estrazione è $(CW-1)/2$ slot: con $CW=15$ sono $7$ slot $=7\cdot9=63\ \mu$s.

Anche con tutte queste precauzioni una collisione può ancora distruggere i dati (due stazioni estraggono lo stesso $b$), e i dati possono anche corrompersi durante la trasmissione. L'ACK positivo e il timeout garantiscono al mittente che il ricevitore ha ricevuto il frame.

RTS/CTS e NAV (opzionali). Per ridurre le collisioni dovute a stazioni che non si sentono tra loro (LAN - Ethernet e Wi-FiUna LAN copre un'area limitata ed è definita dalla famiglia IEEE 802.x (802.3 Ethernet, 802.11 Wi-Fi), che divide il livello di collegamento in LLC e MAC. Ethernet è senza connessione, senza controllo di flusso e senza ACK; usa CSMA/CD 1-persistent; il frame va da 64 a 1518 byte (indirizzi di 6 byte, tipo/lunghezza, dati 46-1500, CRC di 4) e il minimo di 64 B deriva da $t_F\ge2\tau_p$. Dal 10 Mbit/s a coassiale fino al 10 Gbit/s su fibra, con switch full-duplex che eliminano le collisioni. Il Wi-Fi (802.11) usa CSMA/CA, ha i modi BSS (con access point) e ad hoc, EBSS con sistema di distribuzione; adatta il bitrate all'SNR; ha problemi del terminale nascosto e del terminale esposto, risolti in parte da RTS/CTS e NAV.LAN - Ethernet e Wi-Fi →, terminale nascosto):

1. la stazione che ha conquistato il canale invia un frame di controllo RTS (Request To Send) al destinatario;
2. dopo un intervallo $SIFS$ solo la destinazione risponde con un CTS (Clear To Send), a tutti: «sono pronto a ricevere»;
3. dopo un altro $SIFS$ la sorgente invia i dati; dopo $SIFS$ arriva l'ACK;
4. tutte le altre stazioni che sentono RTS o CTS impostano un timer, il NAV (Network Allocation Vector), che indica quanto tempo deve passare prima che possano riascoltare il canale; prima di sentire il canale ogni stazione controlla se il suo NAV è scaduto.

Il NAV è un ascolto «virtuale» del canale: anche una stazione che non sente la trasmissione dei dati sa che il canale è occupato.

Riepilogo dei protocolli ad accesso casuale

Accesso controllato

Qui le stazioni non competono: un meccanismo decide chi può trasmettere, e non ci sono collisioni.

Prenotazione (reservation). Il tempo è diviso in intervalli; in ogni intervallo un frame di prenotazione precede i frame dati. Con $N$ stazioni ci sono esattamente $N$ minislot, uno per stazione. Una stazione che ha dati prenota nel suo minislot; quelle che hanno prenotato inviano i dati dopo il frame di prenotazione.

Polling (usato, per esempio, in Bluetooth). Una stazione è primaria e le altre secondarie (topologia a stella, Tipi di rete e topologieLe reti si classificano per estensione (BAN, WLAN, LAN, MAN, WAN, WSN), per mezzo trasmissivo (aria, fibra, rame, luce visibile) e per topologia: bus (mezzo condiviso, collisioni), stella (nodo centrale, collo di bottiglia), anello (ogni nodo inoltra al successivo), maglia (collegamento diretto tra ogni coppia: $n(n-1)/2$ collegamenti). La scelta dipende da affidabilità, scalabilità, protocollo e mezzo fisico.Tipi di rete e topologie →): tutti gli scambi passano dal dispositivo primario, che controlla il collegamento e decide chi usa il canale e quando; è sempre il primario a iniziare e usa le funzioni poll e select per evitare collisioni. Difetto: se la stazione primaria si guasta, cade il sistema.

• Select (il primario ha qualcosa da inviare): il primario avvisa il secondario della trasmissione in arrivo con un frame SEL che contiene l'indirizzo del secondario, e aspetta un ACK che confermi che è pronto; poi invia i dati e il secondario risponde con un ACK.
• Poll (il primario vuole ricevere): chiede a ogni dispositivo se ha qualcosa da inviare; il secondario interrogato risponde con un NAK (niente da dire) oppure con i dati; con i dati il primario legge il frame e restituisce un ACK. Il walk time è il tempo per passare il controllo da una stazione alla successiva nel ciclo di polling.

Passaggio del testimone (token passing). Le stazioni sono organizzate in un anello logico, in cui ognuna ha un predecessore e un successore. Un pacchetto speciale, il token, circola sull'anello: possedere il token dà il diritto di accedere al canale. Una stazione con dati da inviare aspetta il token dal predecessore, lo trattiene e invia i dati, e a fine trasmissione lo rilascia passandolo al successore; una stazione senza dati passa subito il token. La gestione del token richiede di limitare il tempo di possesso (altrimenti una stazione monopolizza la rete) e di controllare che non sia perso o distrutto.

Canalizzazione

Il canale viene diviso tra le stazioni in modo fisso, per frequenza, tempo, codice o spazio.

Le prestazioni di TDMA e FDMA come sistemi a coda sono in Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA →.

Esercizi collegati

Esercizio - ALOHA puro e slotted, Esercizio - Bitrate oltre il quale CSMA-CD non rileva le collisioni, Esercizio - Scelta del protocollo MAC su bus di 5 km, Esercizio - Collisione tra due stazioni CSMA 1-persistente e, per il bridge in una LAN Ethernet, Esercizio - Traffico massimo con bridge in una LAN 10Base-T.