Lezione 19ALOHA, CSMA e persistenza

Appunti di riferimento: tlc_19 e slide TLC11 (grafici di throughput e ritardo).

Argomenti trattati

1. Accesso casuale e ALOHA (Hawaii, 1970): trasmettere e, se si collide, riprovare dopo un backoff casuale; ipotesi di lavoro: arrivi di Poisson con tasso globale $\lambda$ per $N_u\gg1$, backoff esponenziale $\mathrm{Exp}(\beta)$, processo totale $\lambda_{tot}=\lambda+\lambda_{retx}$ ancora di Poisson, attesa in coda trascurata.
2. Intervallo di vulnerabilità ($2t_P$) e probabilità di successo $P_{success}=e^{-2\lambda_{tot}t_P}$.
3. Traffico offerto e throughput: $G=\lambda_{tot}t_P$, $S=\lambda t_P$, $S=P_{success}G$, $S=Ge^{-2G}$; massimo $\frac1{2e}\simeq0{,}184$ in $G=\frac12$; discussione (si usa il $18\,\%$ del canale).
4. Slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, massimo $\frac1e\simeq0{,}368$ in $G=1$; come ricavare $G$ da $S$ (numerico, Taylor, $S\simeq G$).
5. Stabilità: due soluzioni $G_1$ (stabile) e $G_2$ (instabile); ALOHA intrinsecamente instabile, throughput che va a $0$; margine dal massimo.
6. Ritardo: $m_{delay}=\big(\frac1{P_{success}}-1\big)(t_P+t_A+2\tau_P+\frac1\beta)+t_P+\tau_P$; slotted con $\frac32t_P$.
7. Carrier sense (CSMA): vulnerabilità $\tau_P$, CSMA/CD (jamming, Ethernet), CSMA/CA (RTS/CTS, Wi-Fi); persistenza: 1-persistente, non persistente, $p$-persistente.
8. Curve di throughput di ALOHA, slotted ALOHA e CSMA non persistente in funzione di $G$ e di $\tau_P$.

Teoria

• Accesso al mezzo - ALOHA, CSMA e protocolli deterministiciQuando più nodi condividono il canale serve un protocollo di accesso (MAC): deterministico (TDMA, FDMA, SDMA, CDMA), a richiesta (polling, token) o casuale (ALOHA, CSMA). Con $N_u$ utenti, arrivi di Poisson $\lambda$ ciascuno e pacchetti da $t_P=L/R_b$: TDMA stabile se $N_u\lambda t_P<1$, $m_{delay}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P$; FDMA ha ritardo maggiore di $t_P(N_u/2-1)$. ALOHA puro: intervallo di vulnerabilità $2t_P$, $S=Ge^{-2G}$, $S_{max}=1/(2e)\simeq0{,}18$ per $G=1/2$; slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, $S_{max}=1/e\simeq0{,}37$. ALOHA è intrinsecamente instabile (oltre il massimo il throughput va a $0$). Il carrier sense riduce la vulnerabilità a $\tau_P$ (CSMA), CD interrompe le collisioni, CA (RTS/CTS) è per il wireless; la persistenza (1-, non-, $p$-persistente) può portare il throughput verso il $100,%$.Accesso al mezzo - ALOHA, CSMA e protocolli deterministici →
• Livello di collegamento - LLC, MAC e ipotesi di lavoroIl livello di collegamento vede un canale fisico con errori residui e deve offrire ai livelli superiori un canale affidabile; ha due sottolivelli: LLC (correzione residua, ARQ con ACK/NACK) e MAC (chi trasmette, perché con più trasmettitori il rapporto giusto è la SINR e non l'SNR e la capacità cala). Per analizzarlo si usano ipotesi standard: pacchetti di $L$ bit, probabilità $p$ di pacchetto errato (i.i.d., $p=1-(1-P_{bit})^L\simeq LP_{bit}$), coda sempre piena (heavy traffic), tempo di pacchetto $t_P=L/R_b$, $t_{RTT}=t_P+t_A+2\tau_P$, timeout stringente, ACK/NACK senza errori, ritrasmissioni illimitate ($E[#tx]=1/(1-p)$). Le metriche sono throughput (frazione di tempo d'aria) e ritardo (fino alla ricezione corretta). Una collisione è la sovrapposizione, anche minima, di due pacchetti.Livello di collegamento - LLC, MAC e ipotesi di lavoro →

Esercizi

• Esercizio - Slotted ALOHA e ALOHA con N trasmettitori
• Esercizio - Rete a maglia di 4 nodi half-duplex - accesso deterministico e casuale

Lezione precedente: Lezione 18 · Esercizi su codici e capacità · Lezione successiva: Lezione 20 · Esercizi sul livello di collegamento