Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA

Questa nota calcola il throughput e il ritardo dei protocolli descritti in 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 →, con 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 →. La stessa analisi, nella versione del corso di comunicazioni, è 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 →. Servono la probabilità di Poisson con $k=0$ (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 →), la distribuzione geometrica (Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →) e l'esponenziale (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 →).

Simboli

L'ipotesi del modello è che l'insieme dei frame nuovi e di quelli ritrasmessi dopo una collisione formi ancora un processo di Poisson di tasso $\lambda'$ (Somma di Poisson indipendenti e processo di PoissonSe X ~ Po(λ) e Y ~ Po(μ) sono indipendenti, X + Y ~ Po(λ + μ). Un processo di Poisson di intensità λ (eventi per unità di tempo) è una famiglia {Xₜ} in cui Xₜ ~ Po(λt) conta gli eventi in [0, t], gli incrementi X_{t+τ} − Xₜ ~ Po(λτ) dipendono solo dalla lunghezza τ dell'intervallo, e incrementi su intervalli disgiunti sono indipendenti. Quindi il numero di eventi in un intervallo non dipende da quanti ne sono avvenuti prima; la probabilità di nessun evento in un tempo τ è e^{−λτ}.Somma di Poisson indipendenti e processo di Poisson →). È un'approssimazione, ma rende i conti trattabili.

ALOHA puro

Si definiscono tre metriche:

Definizione (metriche del protocollo ad accesso casuale).

• Traffico offerto $G$: numero medio di frame (nuovi e ritrasmessi) che arrivano in un tempo di servizio, $G=\dfrac{\lambda'}{\mu}=\lambda't_F$.
• Probabilità di successo $P_S$: probabilità che una trasmissione abbia successo, $P_S=\dfrac{\lambda}{\lambda'}=\dfrac{\text{arrivi nuovi/s}}{\text{arrivi totali/s (nuovi + ritrasmessi)}}$.
• Throughput $S$: numero medio di frame trasmessi con successo in un tempo di frame, $S=GP_S=\lambda t_F$.

L'ultima uguaglianza ha un senso fisico: a regime tutti i frame nuovi alla fine passano, quindi i frame consegnati con successo al secondo sono $\lambda$, e normalizzati sul tempo di frame danno $\lambda t_F$ ($=S$, il traffico utile della teoria delle code).

Throughput

Un frame trasmesso all'istante $t$ ha successo se nessun altro frame (nuovo o ritrasmesso) arriva durante il periodo vulnerabile $[t-t_F,\,t+t_F]$ di durata $2t_F$: un frame partito prima di $t-t_F$ è già finito prima che inizi il nostro, uno partito dopo $t+t_F$ comincia quando il nostro è finito; ogni altro frame lo sovrappone almeno in parte. Il numero di arrivi in un intervallo di durata $T$ è di Poisson con media $\lambda'T$, e la probabilità di zero arrivi (formula di Poisson con $k=0$, $\frac{(\lambda'T)^0}{0!}e^{-\lambda'T}=e^{-\lambda'T}$) è $e^{-\lambda'T}$. I due mezzi intervalli sono disgiunti, quindi gli arrivi in ciascuno sono indipendenti e le probabilità si moltiplicano (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 →): $$P_S=P[N(t-t_F,t)=0,\ N(t,t+t_F)=0]=e^{-\lambda't_F}\cdot e^{-\lambda't_F}=e^{-\lambda'\,2t_F}=e^{-2G},$$ dove si è usato $G=\lambda't_F$.

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

Il massimo si trova derivando (Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →). Per la regola del prodotto (Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →) e la derivata dell'esponenziale composto $\frac{d}{dG}e^{-2G}=-2e^{-2G}$: $$\frac{d(Ge^{-2G})}{dG}=1\cdot e^{-2G}+G\cdot(-2)e^{-2G}=e^{-2G}(1-2G)=0\ \Rightarrow\ G=\frac12,$$ perché $e^{-2G}$ non si annulla mai. La derivata è positiva per $G<\frac12$ e negativa dopo, quindi è un massimo, e vale $$S_{max}=\frac12e^{-1}=\frac1{2e}\simeq0{,}184.$$

Esempio. Con $G=0{,}5$: $P_S=e^{-1}=0{,}368$ e $S=0{,}5\cdot0{,}368=0{,}184$, il canale è sfruttato al $18{,}4\,\%$: su un canale a $1$ Mbit/s si consegnano al massimo $184$ kbit/s utili ($0{,}184\cdot1$ Mbit/s). Con $G=0{,}1$ (carico basso) $P_S=e^{-0{,}2}=0{,}819$ e $S=0{,}1\cdot0{,}819=0{,}082$: quasi tutto ciò che arriva passa, ma il $18\,\%$ dei tentativi ($1-e^{-0{,}2}=0{,}181$) si scontra. Con $G=2$ (carico alto) $P_S=e^{-4}=0{,}018$ e $S=2\cdot0{,}018=0{,}037$: il canale è sommerso da collisioni.

Ritardo

Il numero medio di trasmissioni necessarie per consegnare un frame: ogni trasmissione ha probabilità di successo $P_S$, quindi $n$ è geometrico (le prime $n-1$ falliscono, l'ultima riesce): $$E[n_{tx}]=\sum_{n=1}^{+\infty}n(1-P_S)^{n-1}P_S=\frac1{P_S},\qquad E[n_{retx}]=E[n_{tx}]-1=\frac{1-P_S}{P_S}=e^{2G}-1.\qquad(*1)$$ La somma è il valore atteso di una variabile geometrica (Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →): posto $q=1-P_S$, si usa $\sum_{n\ge1}nq^{n-1}=\frac{d}{dq}\frac1{1-q}=\frac1{(1-q)^2}=\frac1{P_S^2}$ (Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →), e moltiplicando per $P_S$ resta $1/P_S$. Per l'ALOHA puro $1/P_S=e^{2G}$. Il ritardo totale è la trasmissione riuscita ($t_F+\tau_p$) più, per ogni ritrasmissione, la trasmissione fallita ($t_F$), l'attesa del NACK o del timeout (round-trip di propagazione $2\tau_p$) e il backoff medio $E[t_b]$:

Formula (ritardo medio dell'ALOHA puro). $$E[T]=t_F+\tau_p+E[n_{retx}](t_F+2\tau_p+E[t_b])=t_F+\tau_p+(e^{2G}-1)(t_F+2\tau_p+E[t_b]).$$

Esempio. $t_F=1$ ms, $\tau_p=0{,}1$ ms, $E[t_b]=5$ ms.

(il termine $t_F+2\tau_p+E[t_b]=1+0{,}2+5=6{,}2$ ms; la parte fissa è $t_F+\tau_p=1{,}1$ ms; per $G=0{,}25$, per esempio, $E[n_{retx}]=e^{0{,}5}-1=0{,}649$ e $E[T]=1{,}1+0{,}649\cdot6{,}2=5{,}12$ ms). Il ritardo cresce in fretta all'aumentare del carico, già prima del massimo di throughput.

Slotted ALOHA

Il periodo vulnerabile è un solo $t_F$ (il frame non soffre collisione se nessun altro frame è stato generato nello slot precedente il suo inizio): $$P_S=P[N(t-t_F,t)=0]=e^{-\lambda't_F}=e^{-G}.$$

Formula (throughput dello slotted ALOHA). $$S=G\,P_S=G\,e^{-G},\qquad\frac{dS}{dG}=e^{-G}(1-G)=0\ \Rightarrow\ G=1,\quad S_{max}=\frac1e\simeq0{,}37.$$

Derivata col prodotto, come sopra: $\frac{d}{dG}(Ge^{-G})=e^{-G}-Ge^{-G}=e^{-G}(1-G)$. Il valore massimo raddoppia rispetto all'ALOHA puro ($\frac1e=2\cdot\frac1{2e}$), e si ottiene per un carico offerto doppio ($G=1$ contro $G=\frac12$).

Ritardo. Rispetto all'ALOHA puro, ogni (ri)trasmissione aspetta in media mezzo slot, $E[W]=t_F/2$, prima di partire a inizio slot: $$E[T]=E[W]+t_F+\tau_p+\frac{1-P_S}{P_S}\big(E[W]+t_F+2\tau_p+E[t_b]\big)=\frac{3t_F}2+\tau_p+(e^{G}-1)\Big(\frac{3t_F}2+2\tau_p+E[t_b]\Big).$$

Esempio. Gli stessi dati dell'ALOHA puro: $G=0{,}1$ dà $E[T]=1{,}5+0{,}1+0{,}105\cdot(1{,}5+0{,}2+5)=2{,}30$ ms (contro $2{,}47$ ms dell'ALOHA puro); $G=0{,}5$ dà $5{,}95$ ms (contro $11{,}75$); $G=1$ dà $13{,}1$ ms. A basso carico lo slotted ha un ritardo maggiore per via dell'attesa dello slot, ma poi cresce molto più lentamente: conta il numero di collisioni. Per esempio per $G=0{,}5$: parte fissa $\frac{3t_F}{2}+\tau_p=1{,}5+0{,}1=1{,}6$ ms, ritrasmissioni $e^{0{,}5}-1=0{,}649$, costo di ciascuna $1{,}5+0{,}2+5=6{,}7$ ms, quindi $E[T]=1{,}6+0{,}649\cdot6{,}7=5{,}95$ ms.

Attenzione: il confronto è a parità di $G$, non di $S$; a parità di throughput utile (per esempio $S=0{,}18$) lo slotted ha un carico $G$ più basso e quindi un vantaggio ancora maggiore.

Dopo il massimo il throughput diminuisce all'aumentare del carico: troppi frame si distruggono a vicenda e ne vengono ritrasmessi ancora di più.

Stabilità: i due punti di funzionamento

Il carico offerto $G$ non è un dato: dipende anche dalle ritrasmissioni. A regime il throughput deve uguagliare il tasso di arrivo normalizzato $\lambda t_F$: i punti di funzionamento sono le intersezioni della curva $S(G)$ con la retta orizzontale $S=\lambda t_F$.

Se $\lambda t_F<S_{max}$ ci sono due intersezioni, $G_1<G_2$:

• in $G_1$ (carico basso) il punto è stabile: se $G$ sale un po', $S>\lambda t_F$ (il sistema smaltisce più frame di quelli che arrivano) e il carico torna giù; è un punto che richiama il sistema;
• in $G_2$ (carico alto) il punto è instabile: oltre $G_2$ il throughput $S$ è inferiore al tasso di arrivo, la coda dei frame da (ri)trasmettere cresce e il carico continua a salire: è la regione di instabilità, in cui il throughput tende a $0$.

Esempio (slotted ALOHA). Con $\lambda t_F=0{,}12$ frame per slot: $Ge^{-G}=0{,}12$ ha le due soluzioni $G_1=0{,}138$ e $G_2=3{,}32$. L'equazione non si risolve con formule elementari; si trova per tentativi o per iterazione. Ramo basso: $G=0{,}12e^{G}$ partendo da $G=0{,}12$ dà $0{,}135,\ 0{,}1374,\ 0{,}1377\to0{,}138$. Ramo alto: $G=\ln(G/0{,}12)$ partendo da $3$ dà $3{,}22,\ 3{,}29,\ 3{,}31\to3{,}32$. Il sistema vive in $G_1$: $P_S=e^{-0{,}138}=0{,}871$ (il $12{,}9\,\%$ dei tentativi si scontra). Un picco di traffico che lo spinga oltre $G_2=3{,}32$ lo manda in blocco. Se $\lambda t_F>1/e=0{,}368$ non esiste nessuna intersezione: il sistema non è mai stabile.

CSMA (non persistente)

Si analizza con il tempo diviso in cicli: ogni ciclo è un periodo di occupazione (busy period, $B$, c'è attività sul canale) seguito da un periodo di inattività (idle period, $I$, il canale è libero). Si definisce il ritardo di propagazione normalizzato $$a=\tilde\tau_p=\frac{\tau_p}{t_F}.$$

Periodo di inattività. I frame (nuovi e ritrasmessi) arrivano con processo di Poisson di tasso $\lambda'$, quindi il tempo tra due arrivi, cioè la durata del periodo di inattività, è esponenziale di parametro $\lambda'$ (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 →) e vale in media $$m_I=\int_0^\infty\tau\lambda'e^{-\lambda'\tau}d\tau=\frac1{\lambda'}=\frac{t_F}{G}\qquad(\text{da }G=\lambda't_F\Rightarrow1/\lambda'=t_F/G).$$

Periodo di occupazione utile. Un periodo di occupazione è riuscito (BP-S) se in esso passa un solo frame, in collisione (BP-C) se ne passano più di uno. Un periodo che inizia in $t$ ha successo se nessun altro frame arriva nel tempo vulnerabile $\tau_p$: $$P_{BP-S}=P[N(t,t+\tau_p)=0]=e^{-\lambda'\tau_p}=e^{-Ga},\qquad P_{BP-C}=1-e^{-Ga}.$$ La parte utile $U$ del periodo vale $t_F$ se riuscito e $0$ se in collisione, quindi $$m_U=t_FP_{BP-S}+0\cdot P_{BP-C}=t_Fe^{-Ga}.$$

Periodo riuscito. Dura il frame più la sua propagazione: $m_{BP-S}=t_F+\tau_p$.

Periodo in collisione. Sia $Y$ il tempo tra la partenza del primo e quella dell'ultimo frame del periodo: $Y\in[0,\tau_p]$ perché dopo $\tau_p$ tutte le stazioni hanno sentito la trasmissione e non partono più. Il periodo dura $Y+t_F+\tau_p$. La distribuzione di $Y$ è la probabilità che nell'intervallo $[t+y,t+\tau_p]$ (lungo $\tau_p-y$) non arrivi nessun frame: $$P_Y(y)=P[Y\le y]=e^{-\lambda'(\tau_p-y)},\ 0\le y\le\tau_p,\qquad p_Y(y)=\lambda'e^{-\lambda'(\tau_p-y)},$$ $$E[Y]=\int_0^{\tau_p}y\,p_Y(y)\,dy=\tau_p-\frac{1-e^{-\lambda'\tau_p}}{\lambda'}=t_F\left(a-\frac{1-e^{-aG}}G\right).$$ Il calcolo dell'integrale: per parti (Integrazione per parti∫ f·g' dx = f·g − ∫ f'·g dx (regola del prodotto letta al contrario). Si usa per log x, arcsin x, arctan x (scritti come "funzione per 1"), per sin²x, cos²x, sinh²x, cosh²x (integrale circolare: l'integrale di partenza ricompare e si porta a sinistra) e per prodotti come x^n·e^(αx), x^n·sin(βx), e^(αx)·sin(βx).Integrazione per parti →), con $u=y$ e $dv=\lambda'e^{-\lambda'(\tau_p-y)}dy$ (quindi $v=e^{-\lambda'(\tau_p-y)}$), $$\int_0^{\tau_p}y\,\lambda'e^{-\lambda'(\tau_p-y)}dy=\Big[y\,e^{-\lambda'(\tau_p-y)}\Big]_0^{\tau_p}-\int_0^{\tau_p}e^{-\lambda'(\tau_p-y)}dy=\tau_p-\frac{1-e^{-\lambda'\tau_p}}{\lambda'}.$$ Nell'ultimo passaggio si sostituiscono $\tau_p=at_F$ e $\lambda'=G/t_F$, per cui $\lambda'\tau_p=aG$ e $1/\lambda'=t_F/G$.

Durata media del periodo di occupazione. Mediando tra i due casi: $$m_B=m_{BP-S}P_{BP-S}+\big(E[Y|BP\text{-}C]+t_F+\tau_p\big)P_{BP-C}=(t_F+\tau_p)\cdot1+E[Y]\,,$$ perché $E[Y|BP\text{-}C]P_{BP-C}=E[Y]$ (valore medio non condizionato) e $P_{BP-S}+P_{BP-C}=1$. Quindi $$m_B=t_F+\tau_p+E[Y]=t_F\left(1+a+a-\frac{1-e^{-aG}}G\right)=t_F\left(1+2a-\frac{1-e^{-aG}}G\right).$$

Formula (throughput del CSMA non persistente). Il throughput è il tempo utile medio per ciclo diviso la durata media del ciclo $m_B+m_I$: $$S=\frac{m_U}{m_B+m_I}=\frac{t_Fe^{-aG}}{t_F\left(1+2a-\frac{1-e^{-aG}}G\right)+\frac{t_F}G}=\frac{G\,e^{-aG}}{G(1+2a)+e^{-aG}}.$$

Passaggio al risultato: nel denominatore si raccoglie $t_F$ e le due frazioni con $G$ si sommano, $-\frac{1-e^{-aG}}G+\frac1G=\frac{e^{-aG}}G$, quindi il denominatore vale $t_F\left(1+2a+\frac{e^{-aG}}G\right)$; si semplifica $t_F$ e si moltiplicano numeratore e denominatore per $G$.

Casi estremi: con $a\to0$ (propagazione trascurabile) $S=\frac G{G+1}\to1$ per $G$ grande: il CSMA riempie il canale. Con $a$ grande la propagazione si fa sentire e $S$ cala, come per l'ALOHA.

Esempio. $a=0{,}1$, $G=1$: $1+2a=1{,}2$ e $e^{-aG}=e^{-0{,}1}=0{,}9048$, quindi $S=\dfrac{e^{-0{,}1}}{1\cdot1{,}2+e^{-0{,}1}}=\dfrac{0{,}9048}{2{,}1048}=0{,}430$. Con $a=0{,}01$: $S=0{,}493$; con $a=1$: $S=0{,}109$.

Il massimo del CSMA (calcolato numericamente) dipende da $a$:

Per $a=1$ il CSMA ha un picco $0{,}14$, inferiore a quello dello slotted ALOHA ($0{,}37$), e per $a=10$ crolla a $0{,}018$, inferiore anche all'ALOHA puro ($0{,}18$). Il confronto con lo slotted ALOHA dipende quindi da $a$:

• ritardo di propagazione piccolo rispetto a $t_F$ (per esempio $a=0{,}01$): il CSMA va meglio dello slotted ALOHA;
• ritardo di propagazione grande (per esempio $a=1$): lo slotted ALOHA va meglio, perché con una propagazione lunga l'ascolto dà un'informazione vecchia e quindi inutile.

Ritardo del CSMA

Il ritardo totale ha tre parti: il tempo per trasmettere i pacchetti (con tutti i fallimenti da collisione), la propagazione e l'attesa che il canale diventi libero durante l'ascolto.

In un ciclo ci sono $m_B-\tau_p$ secondi in cui il canale può essere trovato occupato, quindi $$P_{busy}=\frac{m_B-\tau_p}{m_B+m_I}=\frac{G(1+a)-(1-e^{-aG})}{G(1+2a)+e^{-aG}}.$$ (Si ottiene dividendo per $t_F$ e moltiplicando per $G$ numeratore e denominatore: $m_B-\tau_p=t_F\left(1+a-\frac{1-e^{-aG}}G\right)$.) Quando il canale è occupato (o dopo una collisione) si aspetta un backoff $t_b$ esponenziale di parametro $\beta$, $E[t_b]=1/\beta$. Il numero di volte che il canale è trovato occupato prima di trovarlo libero è geometrico (Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →) con probabilità $P_{busy}$ di «insuccesso»: $P[i\text{ attese}]=P_{busy}^{\,i}(1-P_{busy})$, e ogni attesa dura in media $E[t_b]$. Quindi l'attesa media prima di trasmettere è $$E[W]=\sum_{i=0}^{+\infty}i\,E[t_b]\,P_{busy}^{\,i}(1-P_{busy})=\frac1\beta\cdot\frac{P_{busy}}{1-P_{busy}}.$$ Il numero medio di ritrasmissioni è (da $(*1)$ con $P_S=S/G$): $$E[n_{retx}]=\frac{1-P_S}{P_S}=\frac{G}{S}-1.$$

Formula (ritardo medio del CSMA non persistente). $$E[T]=E[W]+t_F+\tau_p+\left(\frac GS-1\right)\big(E[W]+t_F+2\tau_p+E[t_b]\big).$$

Il primo gruppo è l'ultima trasmissione (andata a buon fine): attesa del canale libero, trasmissione e propagazione. Ogni ritrasmissione costa: attesa del canale libero, trasmissione, andata e ritorno di propagazione (per accorgersi del fallimento), backoff.

Esempio. $t_F=1$ ms, $\tau_p=0{,}1$ ms ($a=0{,}1$), $E[t_b]=5$ ms, $G=1$. Passo per passo:

• $S=0{,}430$ (calcolato sopra);
• $m_B=t_F\left(1+0{,}2-(1-e^{-0{,}1})\right)=1{,}2-0{,}0952=1{,}105$ ms e $m_I=t_F/G=1$ ms;
• $P_{busy}=(m_B-\tau_p)/(m_B+m_I)=1{,}005/2{,}105=0{,}477$;
• $E[W]=5\cdot0{,}477/(1-0{,}477)=5\cdot0{,}477/0{,}523=4{,}57$ ms;
• ritrasmissioni medie $G/S-1=1/0{,}430-1=1{,}33$;
• $E[T]=4{,}57+1+0{,}1+1{,}33\cdot(4{,}57+1+0{,}2+5)=5{,}67+1{,}33\cdot10{,}77\approx19{,}9$ ms (senza arrotondamenti intermedi $19{,}947$; con i valori arrotondati qui sopra si ottiene $19{,}99$).

La figura delle slide mette in relazione $E[T]/t_F$ con $S$ per CSMA e slotted ALOHA: per $a=0{,}01$ il CSMA ha ritardo minore a parità di throughput; per $a=1$ vale il contrario. Le curve tornano indietro perché a ogni $S$ corrispondono due valori di $G$ (il ramo instabile).

TDMA (coda M/D/1)

Definizione (TDMA). L'asse del tempo è diviso in slot di uguale durata, preassegnati agli $N_u$ utenti; ogni utente può trasmettere liberamente nel suo slot, in cui dispone dell'intero bitrate $R$. L'assegnazione segue uno schema periodico (la trama TDMA: $1,2,\dots,N_u$). Il tempo di trasmissione del pacchetto coincide con la durata dello slot: $t_F=F/R$.

Throughput. Ogni utente ha arrivi di Poisson di tasso $\lambda$; il tasso totale è $\lambda_t=N_u\lambda$. Se la coda di ogni utente è stabile: $$S=G=\rho=\frac{\lambda_t}\mu=\frac{N_u\lambda}{\mu}=N_u\lambda t_F.$$ Il TDMA non ha collisioni: il throughput è uguale al carico finché $\rho<1$, e $S\le1$ (non c'è picco né calo).

Ritardo. Per un utente fissato: dopo aver trasmesso deve aspettare $N_u-1$ slot prima del turno successivo, quindi serve in modo costante un pacchetto per trama: $$E[y]=\frac1\mu=N_ut_F\ \Rightarrow\ \mu=\frac1{N_ut_F}\ \text{pacchetti/s}.$$ L'attesa in coda è quella di una M/G/1 con servizio costante (formula di Pollaczek-Khinchin, 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 →): $$E[w]=\frac{\rho}{2\mu(1-\rho)}=\frac{S\,N_ut_F}{2(1-S)}.$$ Qui il tempo di servizio è costante, quindi vale la formula della M/D/1 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 → con $1/\mu=N_ut_F$. Il ritardo $E[T]$ ha quattro contributi:

1. attesa dello slot: quando arriva un pacchetto, il suo istante di arrivo cade a caso nella trama di durata $N_ut_F$ (uniforme: 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 →), quindi si aspetta in media mezza trama, $\dfrac{N_ut_F}2$, prima che il turno torni all'utente;
2. attesa in coda $E[w]=\dfrac{SN_ut_F}{2(1-S)}$, dovuta ai pacchetti già presenti;
3. il tempo di trasmissione $t_F$;
4. la propagazione finale $\tau_p$.

Formula (ritardo medio del TDMA). $$E[T]=\frac{N_ut_F}2+\frac{SN_ut_F}{2(1-S)}+t_F+\tau_p=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right).$$

Esempio. $N_u=10$ utenti, $t_F=1$ ms, $a\approx0$, carico $S=0{,}5$: attesa dello slot $N_u/2=5$, attesa in coda $\dfrac{10\cdot0{,}5}{2\cdot(1-0{,}5)}=\dfrac{5}{1}=5$, trasmissione $1$, quindi $E[T]/t_F=5+5+1=11$, cioè $E[T]=11$ ms. A basso carico ($S=0{,}1$) $E[T]/t_F=5+\dfrac{10\cdot0{,}1}{2\cdot0{,}9}+1=5+0{,}56+1=6{,}56$; con $S=0{,}9$ la coda pesa $\dfrac{10\cdot0{,}9}{2\cdot0{,}1}=45$ e si arriva a $5+45+1=51$.

FDMA (coda M/G/1)

Definizione (FDMA). La banda disponibile è divisa in sottobande disgiunte, assegnate ciascuna a un utente. Il sistema ha un bitrate totale $R$, diviso in parti uguali tra i $N_u$ utenti: ognuno ha $R/N_u$ bit/s. Il tasso di servizio di un utente è $$\mu=\frac{R/N_u}{F}=\frac R{FN_u}\quad[\text{pacchetti/s}].$$

Il tempo di trasmissione di un pacchetto in FDMA è quindi $N_ut_F$ (il pacchetto di $F$ bit passa a $R/N_u$ bit/s: $F/(R/N_u)=N_uF/R=N_ut_F$, cioè su una banda $N_u$ volte più stretta). Rispetto alle slide sulla divisione di frequenza si veda anche 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 →.

Throughput (per il singolo utente, a regime): $$S=G=\rho=\frac\lambda\mu=\lambda N_u\frac FR=\lambda N_ut_F.$$ È la stessa espressione del TDMA: a parità di carico offerto, throughput uguale.

Ritardo. Per una M/G/1 con servizio costante il numero medio di pacchetti nel sistema è $E[x]=\rho+\frac{\rho^2}{2(1-\rho)}$ e, con Little, il tempo di sistema è $$E[s]=\frac{E[x]}\lambda=\frac{S+\frac{S^2}{2(1-S)}}{\lambda},$$ cioè somma di tempo di coda e di servizio. Con $\lambda=S/(N_ut_F)$ (da $S=\lambda N_ut_F$) il fattore $1/\lambda=N_ut_F/S$ moltiplica ogni termine: $$E[s]=\frac{N_ut_F}{S}\left(S+\frac{S^2}{2(1-S)}\right)=N_ut_F+\frac{N_ut_F\,S}{2(1-S)}.$$ Aggiungendo la propagazione $\tau_p$:

Formula (ritardo medio dell'FDMA). $$E[T]=N_ut_F+\frac{N_ut_FS}{2(1-S)}+\tau_p=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right).$$

TDMA contro FDMA

Confrontando le due formule, il ritardo normalizzato $\tilde T=E[T]/t_F$ differisce di una costante: $$E[\tilde T]_{FDMA}=E[\tilde T]_{TDMA}+\frac{N_u}2-1.$$

Perché: l'attesa in coda è la stessa (stesso $\rho=S$ e stesso servizio costante di durata $N_ut_F$); cambia il modo di servire il pacchetto. Sottraendo membro a membro, $\big(N_u+\ldots\big)-\big(\frac{N_u}2+\ldots+1\big)=\frac{N_u}2-1$. In FDMA il pacchetto occupa $N_ut_F$ per essere trasmesso; in TDMA aspetta in media $N_ut_F/2$ per lo slot e poi si trasmette in $t_F$, con totale $N_ut_F/2+t_F$. Il TDMA è quindi più veloce di $t_F(N_u/2-1)$ (per $N_u=2$ i due sono uguali), e la differenza cresce linearmente col numero di utenti.

Con $N_u=100$ la differenza sale a $49$ tempi di frame: per esempio a $S=0{,}5$ il TDMA ha $E[T]/t_F=101$ e l'FDMA $150$; a basso carico il ritardo è dominato dal termine $N_u/2$ o $N_u$, cioè dal numero di utenti, non dal carico.

Nessuno dei due ha un throughput che decresce: sono protocolli a divisione fissa (nessuna collisione, ma risorse riservate anche a chi non trasmette). Gli ALOHA e il CSMA hanno invece ritardi minimi molto bassi quando il canale è poco usato, ma throughput massimo limitato dalle collisioni.

Confronto riassuntivo

Gli algoritmi sono in 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 →; per il caso dell'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 →), $a$ è molto piccolo, dove il CSMA è l'ideale. Esercizio numerico sull'ALOHA: Esercizio - ALOHA puro e slotted.