Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA

Il problema

In molte reti i nodi condividono lo stesso mezzo (un canale radio, un bus: Sistemi di telecomunicazioni e modello ISO-OSIUn servizio di telecomunicazioni porta informazione da una sorgente a una destinazione lontana attraverso trasmettitore, canale e ricevitore. Le comunicazioni si classificano per destinatari (unicast, broadcast, multicast) e per direzione (simplex, half-duplex, full-duplex); le reti hanno una topologia (stella, mesh, albero, anello, bus) e usano commutazione di circuito o di pacchetto. Le funzioni di rete sono divise in strati: nel modello ISO-OSI sono 7 e questo corso studia quasi solo lo strato fisico.Sistemi di telecomunicazioni e modello ISO-OSI →). Se due trasmettono insieme i segnali si sommano e nessuno è decodificabile: c'è una collisionedue o più nodi trasmettono insieme e i segnali si sommano: i pacchetti vanno persi. Il sottostrato MACmedium access control: sottostrato che decide chi usa il mezzo condiviso e quando (medium access control) del livello di collegamento dati decide chi trasmette e quando. Due famiglie:

• accesso deterministico: le risorse sono assegnate in anticipo, nessuna collisione (FDMAaccesso a divisione di frequenza: a ogni utente una sottobanda, TDMAaccesso a divisione di tempo: ogni utente trasmette nel proprio slot, polling, token);
• accesso aleatorio: i nodi trasmettono quando hanno dati, e si gestiscono le collisioni (ALOHA, CSMAcarrier sense multiple access: si ascolta il canale prima di trasmettere).

Per confrontarli si usa il throughput normalizzatofrazione di tempo in cui il canale trasporta pacchetti utili ricevuti correttamente $S$: la frazione di tempo in cui il canale trasporta pacchetti utili ricevuti correttamente, $0\le S\le1$, in funzione del traffico offerto normalizzatonumero medio di trasmissioni, nuove e ripetute, per ogni tempo di pacchetto $G$ (numero medio di pacchetti trasmessi, nuovi più ritrasmessi, per tempo di pacchetto $t_P$). Con $t_P=\frac L{R_b}$ ($L$ bit per pacchetto, compresa l'intestazione) il numero di pacchetti ricevuti correttamente per secondo è $\frac S{t_P}$ e il bit-rate utile è $S\,R_b\cdot\frac{L_{dati}}L$.

Accesso deterministico

FDMA (frequency division multiple access): la banda totale $B$ è divisa tra $N$ utenti in $N$ sottobande di larghezza $\frac BN$ (più eventuali bande di guardia). Ogni utente ha un canale permanente di bit-rate $\approx\frac{R_b}N$.

TDMA (time division multiple access): il tempo è diviso in trame di durata $T_f$, ciascuna con $N$ slotintervallo di tempo della trama assegnato a un utente; l'utente $i$ trasmette solo nel suo slot, a tutto il bit-rate $R_b$. Se ogni slot contiene un intervallo di guardia (e preambolo) $t_g$ oltre ai $t_u$ di dati, l'efficienza è $\eta=\frac{t_u}{t_u+t_g}$ e il bit-rate medio per utente $$R_{utente}=\frac{R_b}{N}\,\eta.$$ Se i dati sono protetti da un codice a blocco $(n,k)$ (Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →) il rate utile è ancora ridotto di $\frac kn$: per $R_b=10$ Gbit/s, $N=20$ utenti e codice $(63,45)$, $R_{utile}=\frac{10^{10}}{20}\cdot\frac{45}{63}=357$ Mbit/s (Esercizio 27 · TDMA, codice a blocco (63,45) e PAM a quattro livelli (tema d'esame luglio 2021)).

Pro e contro. Nessuna collisione e ritardo prevedibile, ma risorse sprecate se un utente non ha dati, sincronismo necessario, difficile da adattare a un numero variabile di utenti o a traffico a raffiche.

Accesso aleatorio: ALOHA

ALOHA puro. Ogni nodo trasmette un pacchetto appena lo ha. Se riceve conferma bene; altrimenti (collisione) attende un tempo casuale (backoffattesa casuale prima di ritrasmettere, per non ricollidere, per esempio esponenziale) e ritrasmette. Un pacchetto di durata $t_P$ ha successo se nessun altro inizia una trasmissione nell'intervallo $\left(-t_P,t_P\right)$ attorno al suo inizio (finestra di vulnerabilitàintervallo in cui un'altra trasmissione provoca la collisione $2t_P$). Con traffico offerto di Poissonarrivi indipendenti con un tasso medio costante: il numero di arrivi in un intervallo segue la legge di Poisson di intensità $G$ (pacchetti per $t_P$) la probabilità di nessun altro arrivo in $2t_P$ è $e^{-2G}$, quindi $$\boxed{S_{ALOHA}=G\,e^{-2G},\qquad S_{max}=\frac1{2e}=0{,}184\ \text{per }G=\tfrac12.}$$

Slotted ALOHA. Il tempo è diviso in slot di durata $t_P$ e le trasmissioni cominciano solo all'inizio di uno slot: la finestra di vulnerabilità si riduce a $t_P$ (si collide solo con chi usa lo stesso slot): $$\boxed{S_{slotted}=G\,e^{-G},\qquad S_{max}=\frac1e=0{,}368\ \text{per }G=1.}$$ Con $N$ nodi che trasmettono in ogni slot con probabilità $q$probabilità con cui ogni nodo trasmette in uno slot ($G=Nq$), il successo è $S=Nq(1-q)^{N-1}$, che tende a $Ge^{-G}$ per $N$ grande; per $N=15$ il massimo ($q=\frac1N$) è $(1-\frac1N)^{N-1}=0{,}380$.

Per $G>1$ il sistema è instabile senza controllo: troppi pacchetti, più collisioni, più ritrasmissioni, e $S\to0$. Il backoff casuale serve a ridurre le collisioni ripetute. Valori (verificati con simulazione, $2\cdot10^6$ slot o $4\cdot10^5$ pacchetti): puro: $G=0{,}25$: $S=0{,}152$; $G=0{,}5$: $0{,}184$; $G=1$: $0{,}135$; slotted: $G=0{,}5$: $0{,}303$; $G=1,5$: $0{,}335$.

Esempio (tema d'esame gennaio 2021). $N=15$ sensori, pacchetti di $1000$ bit più $3$ byte di intestazione ($L=1024$ bit), $R_b=2$ Mbit/s: $t_P=512\ \mu$s. Con slotted ALOHA il massimo di pacchetti ricevuti è $\frac{1/e}{t_P}=718{,}5$ pacchetti/s, cioè $47{,}9$ pacchetti/s per sensore ($49$ kbit/s), contro i $130{,}2$ pacchetti/s per sensore ($133$ kbit/s) di un TDMA ideale (Esercizio 29 · rete di sensori con slotted ALOHA (tema d'esame gennaio 2021)).

CSMA

Nel CSMA (carrier sense multiple access) il nodo ascolta il canale prima di trasmettere: se lo sente occupato non trasmette. Collisioni restano possibili solo perché il segnale impiega un tempo $\tau_P$ritardo di propagazione: tempo che il segnale impiega a percorrere il mezzo (propagazione) ad arrivare: due nodi che iniziano entro $\tau_P$ l'uno dall'altro non si accorgono. Si definisce $a=\frac{\tau_P}{t_P}$ (ritardo normalizzato); il CSMA funziona bene se $a\ll1$. Varianti:

• 1-persistent: se il canale è occupato aspetta e trasmette appena si libera (causa collisioni se in attesa ci sono più nodi);
• non persistentese il canale è occupato attende un tempo casuale e riascolta, senza restare in ascolto: se è occupato attende un tempo casuale e riascolta; per $a$ piccolo $$S_{np}=\frac{G\,e^{-aG}}{G(1+2a)+e^{-aG}};$$
• CSMA/CDcollision detection: si interrompe la trasmissione appena si rileva una collisione (collision detection): si ascolta anche durante la trasmissione e la si interrompe appena si rileva una collisione (Ethernet su cavo coassiale); CSMA/CA (collision avoidance): nelle reti radio, dove non si può ascoltare mentre si trasmette, si ricorre a backoff e conferme (Wi-Fi).

Il massimo di $S_{np}$ (calcolo numerico) è $0{,}815$ per $a=0{,}01$ (in $G\approx9{,}5$) e $0{,}515$ per $a=0{,}1$: l'accesso con ascolto è molto più efficiente dell'ALOHA se il ritardo di propagazione è piccolo rispetto alla durata del pacchetto, e peggiora quando $a$ cresce (reti satellitari: $a$ grande, l'ascolto non serve).

Errori comuni

• Applicare $Ge^{-G}$ all'ALOHA puro (la finestra è $2t_P$: $Ge^{-2G}$).
• Dimenticare che $G$ conta tutte le trasmissioni (nuove e ritrasmesse), non solo i pacchetti nuovi.
• Prendere $S_{max}=\frac1e$ come numero di pacchetti/s: va diviso per $t_P=\frac L{R_b}$ (con $L$ che comprende l'intestazione).
• Usare un throughput normalizzato come bit-rate senza moltiplicare per $R_b$ e per la frazione di bit di dati.