Accesso al mezzo - ALOHA, CSMA e protocolli deterministici

Le basi (modello di collisione, ipotesi di lavoro, metriche throughput e ritardo, dominio di collisione) sono in 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 →; qui si studiano i protocolli del sottolivello MAC: chi parla e quando, in un canale condiviso. La regola di fondo è parlare uno per volta, nella stessa zona di collisione.

Vedi anche Protocolli di accesso multiplo - ALOHA e CSMAQuando più stazioni condividono lo stesso mezzo serve un protocollo di accesso (MAC) che decida chi trasmette. Accesso casuale: ALOHA puro (si trasmette subito, tempo vulnerabile $2t_F$), slotted ALOHA (si parte solo a inizio slot, vulnerabile $t_F$), CSMA (si ascolta prima di parlare, vulnerabile $\tau_p$) con le varianti 1-persistent, non persistent e p-persistent, CSMA/CD (rileva la collisione mentre trasmette: serve $t_F\ge2\tau_p$, quindi un frame minimo) e CSMA/CA del Wi-Fi (IFS, finestra di contesa con backoff esponenziale, ACK, RTS/CTS e NAV). Accesso controllato: prenotazione, polling, token. Canalizzazione: FDMA, TDMA, OFDMA, CDMA, SDMA.Protocolli di accesso multiplo - ALOHA e CSMA →, 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 → (Internet) e 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 → (Ing. Elettronica).

Tipi di accesso

Anche l'accesso casuale ha regole comuni: si parla di contesa (contention) come decisione di chi accede al canale: è casuale, il vincitore cambia ogni volta.

Collisioni e backoff

Con accesso deterministico o a richiesta non ci sono collisioni e quindi $t_{retx}=0$. Con l'accesso casuale sì, e dopo una collisione non si può ritrasmettere subito: la collisione è causata da almeno due nodi che trasmettono insieme; poiché seguono le stesse regole, se ritrasmettessero subito collidrebbero di nuovo. Bisogna aspettare un tempo di backoff $\tau_B$ casuale: la contesa si può vedere come la scelta del $\tau_B$ più basso.

Accesso deterministico

Ipotesi. $N_u$ utenti, ognuno con traffico di Poisson di intensità $\lambda$ pkt/s (Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →): il traffico totale è ancora di Poisson (somma di Poisson indipendenti) con tasso $N_u\lambda$. Pacchetti tutti lunghi $L$ bit, bitrate $R_b$: $t_P=L/R_b$. Arrivi Markov e servizio deterministico: si usa la coda M/D/1 (Sistemi a coda M-G-1 e formula di LittleMisure di un sistema a coda: occupazione $x=q+z$, tempi $s=w+y$, traffico offerto $G=\frac\lambda\mu$, fattore di carico $\rho=\frac\lambda{m\mu}$, throughput $\eta$ e throughput normalizzato $S=\frac\eta\mu$. Il sistema senza blocco è stabile se $\rho<1$ e allora $\eta=\lambda$, altrimenti $\eta=m\mu$. La formula di Little $E[x]=\lambda E[s]$ vale sempre (anche per la sola coda, $E[q]=\lambda E[w]$, e per il servizio, $E[z]=\lambda E[y]$). Per arrivi di Poisson e servizio generale (M/G/1) la formula di Pollaczek-Khinchin dà $E[w]=\frac{\lambda E[y^2]}{2(1-\rho)}$: con servizio esponenziale si ritrova l'M/M/1, con servizio costante (M/D/1) l'attesa si dimezza, $E[w]=\frac{\rho}{2\mu(1-\rho)}$.Sistemi a coda M-G-1 e formula di Little →). Il ritardo è $t_{delay}=s+\tau_P=w+t_P+\tau_P$ (attesa in coda $w$, trasmissione $t_P$, propagazione).

TDMA ed FDMA

• TDMA (Time Division Multiple Access): ogni utente ha il suo turno, e conviene imporre che il turno sia uno slot $=t_P$: trasmette esattamente un pacchetto (se ne ha uno al suo turno), usando tutta la capacità per $t_P$ secondi, poi tocca a un altro.
• FDMA (Frequency Division Multiple Access): tutti trasmettono contemporaneamente su sottocanali diversi: ognuno ha $1/N_u$ della capacità, dividendo la banda in $N_u$ sottobande di ugual larghezza. Il bitrate non è più $R_b$ ma $R_b/N_u$ e anche il tempo di pacchetto cambia: $t_P'=N_ut_P$.

Altre tecniche deterministiche: SDMA (antenne direttive creano sottoregioni, cioè domini di collisione diversi) e CDMA (Code Division, usato nel 3G: in teoria si trasmette nello stesso tempo e alla stessa frequenza, ma in modo ortogonale; analogia: persone che parlano lingue diverse nella stessa stanza). Nel DS-CDMA (Direct Sequence) a ogni utente è assegnato un codice personale (per esempio utente 1: $0\to01100$, $1\to10011$; utente 2: $0\to00101$, $1\to11010$) e il tempo di bit $T_b$ è diviso in $n_{chip}$ piccole fette, i chip, di durata $T_c=T_b/n_{chip}$; i due messaggi sovrapposti si possono ancora separare (più o meno). In alternativa, nel frequency hopping si usa una banda larga ma solo una frazione per volta, saltando con uno schema pseudo-casuale. Hanno il vantaggio di essere robuste al rumore, ma ISI più seria, problemi di sincronizzazione ecc., e usano una banda più larga (wideband CDMA) anche se in realtà se ne usa solo una frazione.

Prestazioni del TDMA

Si analizza come una coda; la prima cosa da fare è la stabilità: tasso di arrivo $<$ tasso di servizio, $N_u\lambda<\frac1{t_P}$: $$\boxed{N_u\lambda t_P<1}.$$ Se stabile il throughput normalizzato vale $S=N_u\lambda t_P=\rho$; se instabile $S=1$. Valgono le considerazioni sulle code: instabile $\Rightarrow$ ritardi illimitati; stabile $\Rightarrow$ quel che entra, esce.

Ritardo medio del TDMA. $m_{delay}=m_w+t_P+\tau_P$ ($m_{retx}=0$). Il punto difficile è $m_w$: non è quello della M/D/1 perché il servizio non è "instancabile" (restless): dal punto di vista dei pacchetti nella coda di un utente, una volta servito un pacchetto il servitore smette e va a servire altre code: durante il servizio si percepisce un tempo $t_P$, ma in coda si vede avanzare la coda ogni $N_ut_P$ secondi. Si divide $w=w_1+w_2$ (per un pacchetto accodato all'utente $1$):

• $w_1$: tempo prima che sia il turno dell'utente $1$, come aspettare un autobus che passa ogni $N_ut_P$ secondi: in media $m_{w_1}=\dfrac{N_ut_P}{2}$;
• $w_2$: da quel momento si è in una coda con servitore attivo e tempo di servizio $T=N_ut_P$: si prende il tempo di attesa della M/D/1, $m_{w_2}=\dfrac{\rho T}{2(1-\rho)}=\dfrac{\rho N_ut_P}{2(1-\rho)}$, con $\rho=N_u\lambda t_P$ (traffico dell'utente: arrivi $\lambda$, servizio $N_ut_P$, quindi $\lambda\cdot N_ut_P=\rho$).

Sommando, e osservando $\frac12+\frac\rho{2(1-\rho)}=\frac1{2(1-\rho)}$: $$\boxed{m_{delay}^{TDMA}=\frac{N_ut_P}2+\frac{\rho N_ut_P}{2(1-\rho)}+t_P+\tau_P=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P}.$$

Prestazioni dell'FDMA

Stabilità: tasso di arrivo $\lambda<$ tasso di servizio $\frac1{N_ut_P}$, cioè sempre $N_u\lambda t_P<1$; throughput normalizzato (se stabile) $S=N_u\lambda t_P=\rho$. Attenzione: nonostante le somiglianze con il TDMA il significato è diverso: nel TDMA si ha una coda con arrivi $N_u\lambda$ e servizio $1/t_P$; nell'FDMA si hanno $N_u$ code separate, ciascuna con arrivi $\lambda$ e servizio $1/(N_ut_P)$. Il ritardo è facile: ora ogni utente è una semplice M/D/1 con tempo di servizio $T=N_ut_P$: $$m_s=\frac{T(2-\rho)}{2(1-\rho)}=\frac{N_ut_P(2-\rho)}{2(1-\rho)},\qquad m_{delay}^{FDMA}=m_s+\tau_P.$$ (Il tempo di sistema M/D/1 è $T+\frac{\rho T}{2(1-\rho)}=\frac{T(2-\rho)}{2(1-\rho)}$.)

TDMA contro FDMA

Riscrivendo $\frac{2-\rho}{2(1-\rho)}=\frac1{2(1-\rho)}+\frac12$: $$m_{delay}^{FDMA}=\frac{N_ut_P}{2(1-\rho)}+\frac{N_ut_P}2+\tau_P,\qquad m_{delay}^{TDMA}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P.$$ Quindi $m_{delay}^{TDMA}<m_{delay}^{FDMA}$ se $t_P<\frac{N_ut_P}2$, cioè $N_u>2$ (e un accesso "multiplo" ha $N_u\ge2$): l'FDMA è peggiore, anche se di poco (un servitore veloce contro tanti lenti). La differenza è $t_P(N_u/2-1)$.

Esempio. $R_b=1$ Mbit/s, $L=1000$ bit ($t_P=1$ ms), $N_u=10$ utenti con $\lambda=50$ pkt/s: $\rho=10\cdot50\cdot10^{-3}=0{,}5$ (stabile). TDMA: $m_{delay}=\frac{10}{2\cdot0{,}5}+1=11$ ms (più $\tau_P$); FDMA: $10+5=15$ ms: la differenza è $4=1\cdot(10/2-1)$ ms.

Accesso casuale: l'ALOHA

Tutti gli schemi di questo tipo hanno un antenato comune, il protocollo ALOHA (Abramson, università delle Hawaii, circa 1970): problema, un solo satellite condiviso per comunicare; idea: trasmettere e basta, e se si collide, riprovare (dopo un backoff casuale). Implica: (1) ogni pacchetto riceve un ACK; (2) se non lo riceve si assume una collisione, e si ritrasmette dopo un backoff.

Ipotesi di lavoro.

1. Arrivi di Poisson con tasso globale $\lambda$ (ha il ruolo di $N_u\lambda$): lo studio vale solo per $N_u\gg1$ (arrivi individuali infinitesimi) e $\lambda_{ind}\ll1$; si denota con $\lambda$ il prodotto, finito. Pacchetti tutti di $L$ bit, bitrate $R_b$, $t_P=L/R_b$ (possibile solo senza collisioni). Il numero di pacchetti che arrivano in $\Delta t$ è di Poisson: $P[k\text{ pacchetti in }\Delta t]=e^{-\lambda\Delta t}\frac{(\lambda\Delta t)^k}{k!}$ (Distribuzione di PoissonPoi(λ) conta eventi rari: P(X = k) = e^(−λ) λ^k / k! per k = 0, 1, 2, …, con media e varianza entrambe uguali a λ; approssima la binomiale Bin(n, p) quando n è grande e p piccolo, con λ = np.Distribuzione di Poisson →).
2. Backoff esponenziale: per trattabilità $\tau_B\sim\mathrm{Exp}(\beta)$, $p_{\tau_B}(a)=\beta e^{-\beta a}$, $E[\tau_B]=m_{\tau_B}=1/\beta$ (Distribuzioni uniforme continua ed esponenzialeU(a, b) ha densità costante 1/(b − a) su [a, b], media (a + b)/2 e varianza (b − a)²/12; Exp(λ) ha densità λe^(−λx) per x ≥ 0, FdD 1 − e^(−λx), P(X > t) = e^(−λt), media 1/λ, varianza 1/λ², ed è l'unica legge continua senza memoria (versione continua della geometrica).Distribuzioni uniforme continua ed esponenziale →).
3. Si trascura il tempo di attesa in coda $w$: l'analisi vale solo se il tasso di arrivo di ogni singolo nodo è molto basso. Quindi $m_{delay}=m_{retx}+t_P+\tau_P$. (Anticipazione: tutti i sistemi derivati da ALOHA funzionano bene solo se poco carichi: un forte accodamento significherebbe troppe collisioni e il sistema non funzionerebbe.)

Il processo totale è di Poisson. Con le ritrasmissioni il processo globale di arrivi al canale ha tasso $\lambda_{tot}=\lambda+\lambda_{retx}$, superiore a $\lambda$. Lo si assume ancora di Poisson (e lo è, ma solo se $\tau_B$ è esponenziale e grande). Intuizione: gli arrivi sono già senza memoria (interarrivi esponenziali); le ritrasmissioni accadono dopo un tempo esponenziale, ma c'è memoria, perché sono causate proprio dalla collisione; a meno che non avvengano dopo un tempo così lungo che la memoria è "svanita": alla fine è solo un "pettine di Dirac" più denso (frecce rosse in più nelle slide). Altra intuizione: con $n$ utenti in collisione $\lambda_{retx}=n\beta$ è Poisson (somma di $n$ processi di tasso $\beta$); i due addendi di $\lambda_{tot}$ non sono indipendenti (requisito della somma), ma l'analisi funziona solo se $\beta\ll1$ (backoff medio $1/\beta$ lungo, memoria "svanita"). Il libro dà una giustificazione alternativa: $n$ deve essere indipendente dal processo di arrivo di tasso $\lambda$. In pratica si tratta il processo totale come di Poisson con il suo tasso $\lambda_{tot}$.

Intervallo di vulnerabilità e probabilità di successo

Si prenda la trasmissione di un utente $1$ nell'intervallo $[0,t_P]$. Un altro pacchetto collide con lui se la sua trasmissione si sovrappone, in parte, a $[0,t_P]$: cioè se inizia in $(-t_P,\,t_P)$ (se iniziasse prima di $-t_P$ finirebbe prima di $0$; se iniziasse dopo $t_P$ comincerebbe quando il nostro è finito).

Definizione (intervallo di vulnerabilità). L'intervallo in cui altre trasmissioni causano collisione. Per l'ALOHA ha durata $2t_P$.

Osservazioni: bisogna usare $\lambda_{tot}$ e non $\lambda$ (le ritrasmissioni collidono anch'esse); in realtà bisognerebbe contare solo gli arrivi degli altri utenti, tasso $(N_u-1)\lambda_{tot}/N_u\simeq\lambda_{tot}$ perché $N_u\gg1$. Per semplicità si trascura il ritardo di propagazione (qui non cambia nulla; con il carrier sense conterà).

L'evento "collisione" è "almeno un arrivo nell'intervallo di vulnerabilità"; la probabilità di successo è quella di zero arrivi di Poisson (tasso $\lambda_{tot}$) in $\Delta t=2t_P$: $$P_{success}=P[k=0\text{ arrivi in }2t_P]=e^{-2\lambda_{tot}t_P}.$$

Throughput

Riciclando la terminologia dei sistemi a coda (sistema con $m=1$ servitore, $\mu=1/t_P$): fattore di carico $\rho=\lambda/(m\mu)$; traffico offerto $G=\lambda/\mu$; throughput normalizzato (se stabile) $S=\lambda/\mu=\rho$ (tutto ciò che entra esce). Per ALOHA si distingue: $$S=\lambda t_P\ (\text{throughput, se stabile}),\qquad G=\lambda_{tot}t_P\ (\text{traffico offerto, contando gli errori di ALOHA}).$$ Relazione tra $S$ e $G$. Di $S$ solo la frazione $P_{success}$ esce al primo tentativo: $SP_{success}$ passa, $S(1-P_{success})$ collide e rientra come ritrasmissione; di questa $S(1-P_{success})P_{success}$ passa, $S(1-P_{success})^2$ collide, e così via. A regime, se stabile, ciò che passa è la somma geometrica (ragione $1-P_{success}<1$) $SP_{success}\cdot\frac1{1-(1-P_{success})}=S$ ✓, mentre il traffico offerto è $S+S(1-P_{success})+S(1-P_{success})^2+\dots=\frac S{P_{success}}$: $G=S/P_{success}$, cioè $$S=P_{success}\,G\qquad(\text{approssimazione al primo ordine: successo medio = arrivi complessivi}\times P_{success}).$$ Con $P_{success}=e^{-2G}$ ($G=\lambda_{tot}t_P$):

Formula (throughput dell'ALOHA puro). $$\boxed{S=G\,e^{-2G}}.$$

La relazione dà $S$ come funzione semplice di $G$, ma l'inversa ($G$ da $S$) è molto difficile.

Il massimo. $\frac{dS}{dG}=e^{-2G}-2Ge^{-2G}=e^{-2G}(1-2G)=0$, poiché $e^{-2G}\ne0$: $G=\frac12$, e $$S_{max}=\frac12e^{-1}=\frac1{2e}\simeq0{,}184.$$ Si usa al massimo il $18\,\%$ della capacità, e in $G=0{,}5$ il canale è libero il $50\,\%$ del tempo (attenzione al paradosso: trasmettere di più peggiora le cose, perché aumentano le ritrasmissioni, già il $32\,\%$ del totale, e $S$ cala). Nella parte iniziale ($G\to0$): $e^{-2G}\to1$, $P_{success}\to1$, $S\simeq G$: se si tiene $G$ basso non si collide mai e ciò che si invia passa.

Esempio. $G=0{,}1$: $P_{success}=e^{-0{,}2}=0{,}819$, $S=0{,}082$; $G=0{,}5$: $S=0{,}184$; $G=2$: $P_{success}=e^{-4}=0{,}018$, $S=0{,}037$ (canale sommerso dalle collisioni).

Slotted ALOHA

(Roberts, 1972.) Si immagina un sistema perfettamente sincronizzato con l'asse dei tempi diviso in slot di durata $t_P$, e si aggiunge la regola che i pacchetti si possono trasmettere solo all'inizio di uno slot (un pacchetto che arriva a metà slot aspetta l'inizio del successivo). Il vantaggio: due trasmissioni si sovrappongono o del tutto o per niente. Un altro pacchetto che arriva durante lo slot dell'utente $1$ (cioè in $[0,t_P]$ se si prende lo slot $[0,t_P]$) deve aspettare l'inizio dello slot successivo, mentre quelli arrivati nello slot precedente partono all'istante $0$: sono i soli a coincidere (perfettamente) con la trasmissione dell'utente $1$, perché tutti iniziano agli istanti multipli di $t_P$. Un pacchetto che arriva a metà slot e parte all'istante $t_P$ non collide, perché il nostro è appena finito. Quindi l'unico intervallo in cui un arrivo provoca collisione è lo slot precedente, di durata $t_P$: l'intervallo di vulnerabilità si riduce a $t_P$ (la metà di quello di ALOHA). Rifacendo i calcoli con matematica analoga: $$P_{success}=e^{-\lambda_{tot}t_P}=e^{-G},\qquad\boxed{S=G\,e^{-G}},\qquad S_{max}=\frac1e\simeq0{,}368\ \text{ in }G=1.$$ Con una modifica teorica banale $S_{max}$ raddoppia, anche se non sempre è facile da implementare (richiede sincronizzazione), ed è comunque lontano dal $100\,\%$. Per l'ALOHA il caso è analogo con $S$ scalato di $2$ (e $G\to2G$).

Esempio. $G=1$ (canale pienamente "offerto"): $P_{success}=e^{-1}=0{,}368$, $S=0{,}368$: il $63\,\%$ dei tentativi collide; con $G=1$ lo slotted ALOHA dà il $37\,\%$, mentre l'ALOHA puro darebbe $S=e^{-2}=0{,}135$.

Come ricavare $G$ da $S$ (esercizi difficili)

Dato $S=Ge^{-G}$ (per slotted ALOHA; per ALOHA puro si scala di $2$), trovare $G$ richiede la soluzione di un'equazione trascendente. Trucchi:

1. metodi numerici (provare qualche numero): per $S=0{,}2$ si trovano $G=0{,}259$ e $G=2{,}543$;
2. sviluppo di Taylor $e^{-G}=1-G+\frac{G^2}{2!}-\dots$, quindi $S\simeq G-G^2$ (Formula di Taylor con resto di PeanoUna funzione derivabile n volte in x0 si scrive, vicino a x0, come un polinomio di grado al più n (il polinomio di Taylor, costruito con le derivate in x0) più un errore o((x-x0)^n); il polinomio è unico. Per x0 = 0 si chiama sviluppo di Mac-Laurin.Formula di Taylor con resto di Peano →): per $S=0{,}2$ dà $G=\frac{1-\sqrt{1-4S}}2=0{,}276$ (esatto $0{,}259$);
3. osservare che il sistema deve lavorare a $G$ bassi, dove una buona approssimazione è $S\simeq G$ (che vale anche perché Taylor vale per $G\to0$; più le condizioni di stabilità che seguono).

Stabilità dell'ALOHA

L'equazione $S=P_{success}G$ vale solo per un sistema stabile ed è un'approssimazione del primo ordine; vale per ogni approccio tipo ALOHA, con o senza slot. Se si fissa $S$ e si risolve in $G$ si trovano due soluzioni, $G_1<G_2$ (a sinistra e a destra del massimo). Che significa? Corrisponde a chiedersi cosa succede se si parte da queste soluzioni in media, ma si ha una piccola oscillazione:

• $G_1$ (ramo crescente della curva) è un punto stabile: attrattore delle piccole oscillazioni (se $G$ cresce un po', $S$ cresce, il canale smaltisce di più, $G$ torna indietro);
• $G_2$ (ramo decrescente) è instabile: tende a respingerle. In particolare appena $S$ è un po' più basso, il punto di lavoro si sposta verso destra ($G_2$ aumenta, perché si devono ritrasmettere più pacchetti), e sul ramo decrescente $S$ cala ancora: in pochissimo tempo $S$ raggiunge $0$.

È una instabilità peggiore di quella delle code classiche: là instabile significava throughput $=\mu$; qui significa throughput zero (solo ritrasmissioni, nessuna uscita). Conclusione: ALOHA è intrinsecamente instabile. Il massimo throughput è solo un limite superiore: non si può lavorare in cima alla collina (ogni oscillazione minima porterebbe a $S=0$), né a destra; bisogna stare un po' a sinistra, con un margine dal massimo, e con un'oscillazione abbastanza grande si supera comunque il massimo; perfino partendo da sinistra, aspettando un tempo infinito l'instabilità prima o poi scatta. Ma in pratica si usa (l'instabilità può comparire dopo un tempo lunghissimo), a bassi carichi offerti.

Ritardo dell'ALOHA

Vale per ogni approccio tipo ALOHA (con o senza slot, con piccoli aggiustamenti). Poiché si trascura $w$, $m_{delay}=m_{retx}+t_P+\tau_P$, con $m_{retx}=E[n_{retx}]\cdot t_{retx}$ e $E[n_{retx}]=\frac1{P_{success}}-1$ (come per l'ARQ: 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 →). Ogni ritrasmissione costa un round-trip (si scopre la collisione dal timeout) più un backoff medio $m_{\tau_B}$: $$m_{delay}=\Big(\frac1{P_{success}}-1\Big)\big(t_P+t_A+2\tau_P+m_{\tau_B}\big)+t_P+\tau_P,\quad m_{\tau_B}=\frac1\beta.$$ ALOHA: $P_{success}=e^{-2G}$: $$m_{delay}^{ALOHA}=(e^{2G}-1)\Big(t_P+t_A+2\tau_P+\frac1\beta\Big)+t_P+\tau_P.$$ Slotted ALOHA: $P_{success}=e^{-G}$ e il tempo di pacchetto si aumenta del $50\,\%$, perché si può trasmettere solo all'inizio di uno slot (attesa media $t_P/2$ prima dell'inizio, come l'attesa dell'autobus del TDMA): $$m_{delay}^{slotted}=(e^{G}-1)\Big(\frac32t_P+t_A+2\tau_P+\frac1\beta\Big)+\frac32t_P+\tau_P.$$ Esempio. $t_P=1$ ms, $t_A=0{,}1$ ms, $\tau_P=0{,}05$ ms, backoff medio $1/\beta=5$ ms, $G=0{,}25$: ALOHA: $(e^{0{,}5}-1)(1+0{,}1+0{,}1+5)+1+0{,}05=0{,}6487\cdot6{,}2+1{,}05=5{,}07$ ms; slotted: $(e^{0{,}25}-1)(1{,}5+0{,}1+0{,}1+5)+1{,}5+0{,}05=0{,}2840\cdot6{,}7+1{,}55=3{,}45$ ms. A basso carico lo slotted è più veloce anche con lo slot di attesa.

I grafici delle slide mostrano il ritardo normalizzato in funzione del throughput: curve a "naso" (due rami: a $S$ dato esistono due valori di $G$, uno stabile e uno instabile, e per $S\to S_{max}$ il ritardo esplode). Il ramo corretto è quello in basso.

Carrier sense: CSMA

Il carrier sense è "ascoltare" la portante di una trasmissione in corso: un trucco semplice che migliora molto l'ALOHA (su cui si basano Ethernet e Wi-Fi). Analogia: ALOHA è "prova a parlare sperando di non collidere"; meglio ascoltare prima che nessun altro stia parlando. In pratica, prima di trasmettere si verifica la presenza di potenza di portante: se il canale è sentito occupato non si trasmette, per non causare collisioni (ALOHA, per definizione, non lo fa).

Problema risolto? Non del tutto: sentire il canale libero significa soltanto che era libero $\tau_P$ secondi fa (come vedere la luce di stelle che si sono spente: si vede il passato). L'intervallo di vulnerabilità cambia: ora è $\tau_P$. Ascoltare prima di parlare non evita del tutto le collisioni, ma le riduce molto se $\tau_P\ll t_P$, vero per distanze terrestri; non lo è per esempio per canali sottomarini o spaziali (dove può essere $\tau_P>t_P$ e il carrier sense non si fa). Si ottiene il CSMA (Carrier Sense Multiple Access): si modificano di conseguenza tutti i passaggi (vulnerabilità, successo, ritardo).

Formula (CSMA non persistente, completamento). Con $a=\tau_P/t_P$ e traffico offerto $G$ (se $\tau_P=0$, $S=G/(1+G)\to1$ per $G\to\infty$): $$S=\frac{G\,e^{-aG}}{G(1+2a)+e^{-aG}}.$$ (È la formula standard, usata per i grafici delle slide: non è dedotta nel corso. Per $a=0{,}01$ il massimo è $S\simeq0{,}815$ in $G\simeq9{,}5$; per $a=0{,}1$, $S\simeq0{,}515$ in $G\simeq2{,}6$; per $a=1$, $S\simeq0{,}144$: peggio dello slotted ALOHA.)

Collision detection: CSMA/CD

Poiché non si evitano tutte le collisioni, se ne limitano i danni: le collisioni si scoprono solo quando manca l'ACK, dopo che i pacchetti si sono sovrapposti per intero, sprecando tempo; meglio fermarsi prima. CSMA/CD (Ethernet): si ascolta il canale anche mentre si trasmette e, a una collisione, si invia un segnale speciale di jamming (un segnale ad alta potenza: come urlare "fermi tutti, stiamo collidendo!"). Senza il jamming la collisione verrebbe notata solo molto più tardi.

Collision avoidance: CSMA/CA

CSMA/CD funziona benissimo ma non può funzionare sul wireless: richiede di ascoltare il canale non solo prima ma anche durante la trasmissione, impossibile su un mezzo radio, per natura half duplex. Si usa il CSMA/CA (base del Wi-Fi), meno efficace: si scambiano pacchetti brevi RTS (Request-to-Send) e CTS (Clear-to-Send), poi DATI e ACK (handshake a quattro vie): apparentemente rimanda il problema, delegandolo a pacchetti più piccoli (le collisioni, se capitano, riguardano RTS brevi invece del pacchetto di dati).

Persistenza

Serve un'ultima miglioria per arrivare a efficienza unitaria ($S\to100\,\%$): la persistenza. Il carrier sense fa aspettare quando il canale è occupato; e quando si libera? Se due utenti stanno aspettando, rischiano di collidere (entrambi trasmettono appena "libero"). Tre opzioni:

• 1-persistente: si trasmette appena il canale si libera (molto aggressivo, rischia di collidere);
• non persistente: grazie al CSMA si è evitato di collidere; cosa sarebbe successo altrimenti? Un backoff. Quindi: se il canale è occupato si aspetta un intero tempo di backoff (riprova più tardi) senza seguire la fine della trasmissione; può essere troppo conservativo, perché fa aspettare anche quando nessun altro attende;
• $p$-persistente: via di mezzo, con probabilità $p$ si trasmette (come 1-persistente) e con probabilità $1-p$ si rimanda (come non persistente).

È un compromesso ingegneristico, e con una scelta per tentativi di $p$ si può arrivare a un throughput del $100\,\%$.

Errori comuni

• Usare $\lambda$ invece di $\lambda_{tot}$ nella probabilità di successo ($G=\lambda_{tot}t_P$): le ritrasmissioni collidono come le trasmissioni nuove.
• Dire che ALOHA ha throughput massimo $1/e$ (è lo slotted: $1/e=0{,}368$; l'ALOHA puro $1/(2e)=0{,}184$) o confondere i punti di massimo ($G=1/2$ e $G=1$).
• Trascurare la stabilità: oltre il massimo il throughput di ALOHA tende a $0$, non a $S_{max}$.
• Usare la M/D/1 per il TDMA senza il termine $N_ut_P/2$ di attesa del turno.
• Dire che FDMA "è più veloce perché trasmette sempre": ogni utente ha un servitore $N_u$ volte più lento.

Collegamenti

Esercizi: Esercizio - Rete a maglia di 4 nodi half-duplex - accesso deterministico e casuale, Esercizio - Slotted ALOHA e ALOHA con N trasmettitori, e le simulazioni d'esame che usano TDMA/FDMA, come l'Esercizio - Quattro domande brevi su capacità, TDMA e FDMA, entropia e codice lineare (simulazione d'esame 2013). Per la parte di ritrasmissione: Tecniche ARQ e loro prestazioniARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore risponde a ogni pacchetto con ACK (corretto) o NACK (errato), e il trasmettitore ritrasmette. Con probabilità di pacchetto errato $p$, $t_{RTT}=t_P+t_A+2\tau_P$ e coda sempre piena, il throughput massimo (frazione di tempo d'aria) è: Stop-and-Wait $S=\frac{t_P(1-p)}{t_{RTT}}$; Go-Back-N con $N=t_{RTT}/t_P$ $S=\frac{1-p}{(N-1)p+1}$; Selective Repeat $S=1-p$. Il ritardo medio è $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$ (a coda vuota). Sono solo valori massimi: la coda ARQ è stabile solo se $\lambda$ è minore della velocità di servizio, $\lambda<1/m_y$; altrimenti il throughput è $\min(\lambda,\mu)$. L'efficienza (payload) è $\eta=S,L_D/L$.Tecniche ARQ e loro prestazioni →.