Esercizio - ALOHA puro e slotted

Testo. Si considerino i seguenti sistemi ALOHA.

1. Un gruppo di $N$ utenti condivide un canale ALOHA puro da $56$ kbit/s. Ogni utente genera pacchetti secondo un processo di Poisson, uno da $1000$ bit ogni $100$ s, anche se il precedente non è ancora stato trasmesso. Qual è il massimo valore di $N$?
2. Diecimila stazioni di prenotazione aerea si contendono un unico canale ALOHA slotted. In media ogni stazione fa $18$ richieste all'ora. Uno slot dura $125\ \mu$s. Qual è, approssimativamente, il carico totale del canale?

Teoria usata: 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 → (dove le formule sono ricavate), 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 →.

Idea di fondo

In ALOHA le stazioni trasmettono senza coordinarsi, quindi alcuni pacchetti collidono e vanno ritrasmessi. Il canale non può mai essere usato al 100%: esiste un throughput massimo (normalizzato alla capacità del canale), che dipende solo dal tipo di ALOHA. Se $G$ è il traffico offerto al canale (in pacchetti per tempo di trasmissione di un pacchetto, comprese le ritrasmissioni) e $S$ il throughput utile (sempre in pacchetti per tempo di pacchetto), valgono

$$S_{puro}=G\,e^{-2G},\qquad S_{slotted}=G\,e^{-G}.$$

Il primo ha massimo in $G=\tfrac12$: $S_{max}=\tfrac1{2e}\approx0{,}184$. Il secondo ha massimo in $G=1$: $S_{max}=\tfrac1e\approx0{,}368$. Il fattore $2$ nell'esponente del puro viene dal tempo di vulnerabilità: $2T_{fr}$ per l'ALOHA puro, $T_{fr}$ per lo slotted (un pacchetto sopravvive solo se nessun altro viene iniziato in quella finestra).

Da dove vengono le formule e i massimi. Gli arrivi sono di Poisson di tasso $\lambda$, quindi la probabilità che in un intervallo lungo $T$ non arrivi nessun pacchetto è $e^{-\lambda T}$ (formula 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 →). Con $G=\lambda T_{fr}$ e finestra $2T_{fr}$ si ha $P_S=e^{-2G}$, e il throughput è il traffico offerto per la probabilità di successo, $S=G\,P_S$. Per il massimo si deriva col prodotto: $\frac{d}{dG}\left(Ge^{-2G}\right)=e^{-2G}-2Ge^{-2G}=e^{-2G}(1-2G)=0$, da cui $G=\tfrac12$ e $S_{max}=\tfrac12e^{-1}=0{,}184$ (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 →, 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 →). Per lo slotted $\frac{d}{dG}\left(Ge^{-G}\right)=e^{-G}(1-G)=0$ dà $G=1$ e $S_{max}=e^{-1}=0{,}368$.

(1) $N$ massimo con ALOHA puro

Traffico di un utente. Un pacchetto da $1000$ bit ogni $100$ s significa $$s=\frac{1000\ \text{bit}}{100\ \text{s}}=10\ \text{bit/s}.$$ Non serve conoscere altro sul processo di Poisson: conta solo la quantità media di bit generati. Infatti la somma di $N$ processi di Poisson indipendenti è ancora un processo di Poisson, con tasso uguale alla somma dei tassi (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 →): il canale vede un unico flusso, di $N\cdot s$ bit/s in media.

Capacità utile del canale. Il canale ha capacità $C=56$ kbit/s, ma l'ALOHA puro ne sfrutta al massimo il $18\%$ circa, perché il resto va perso in collisioni e ritrasmissioni. Quindi il traffico utile massimo sostenibile è $$C_{max}=S_{max}\cdot C\approx0{,}18\cdot56\,000=10\,080\ \text{bit/s}.$$ Il prodotto ha senso perché $S$ è normalizzato alla capacità: $S=1$ vorrebbe dire canale pieno di bit utili ($56\,000$ bit/s), $S_{max}=0{,}18$ al più $0{,}18\cdot56\,000$ bit/s utili.

Condizione. Il traffico totale generato deve stare sotto $C_{max}$: $$N\cdot s\le C_{max}\ \Longrightarrow\ N\le\frac{10\,080}{10}=1008.$$

Il massimo è $N=1008$ utenti. Ogni utente genera pochissimo (10 bit/s contro 56 000), ma l'ALOHA puro regge solo poco più di mille utenti perché la capacità efficace è circa un quinto di quella nominale.

(2) Carico del canale con ALOHA slotted

Richieste al secondo di una stazione. $$\lambda_1=\frac{18}{3600\ \text{s}}=0{,}005\ \text{s}^{-1}=\frac1{200}\ \text{s}^{-1}.$$

Richieste al secondo di tutte le stazioni. $$\lambda=10\,000\cdot0{,}005=50\ \text{s}^{-1}.$$

Carico per slot. Il carico $G$ è il numero medio di richieste che arrivano in uno slot (tasso di arrivo per durata dello slot, un numero puro: $\text{s}^{-1}\cdot\text{s}$). Uno slot dura $125\ \mu\text{s}=1{,}25\cdot10^{-4}$ s, quindi $$G=\lambda\cdot T_{slot}=50\cdot125\cdot10^{-6}=6{,}25\cdot10^{-3}=\frac1{160}\ \text{richieste/slot}.$$

Il canale è quasi scarico: $G\approx0{,}006\ll1$. Con questo carico quasi tutte le richieste passano al primo tentativo: $S=Ge^{-G}=0{,}00625\cdot e^{-0{,}00625}=0{,}00625\cdot0{,}99377=0{,}00621$, praticamente uguale a $G$ (collisioni rarissime: la probabilità di trovare un altro pacchetto nello stesso slot è $1-e^{-G}=0{,}0062$, circa lo $0{,}6\%$). Siamo molto a sinistra del massimo $G=1$: il canale è sfruttato appena allo $0{,}6\%$.

Confronto con la soluzione ufficiale

• (1) Ufficiale: $N=1008$. Coincide, perché la soluzione usa $\eta_{puro}\approx0{,}18$ arrotondato. Con il valore esatto $\tfrac1{2e}=0{,}18394$ si ottiene $C_{max}=10\,300{,}6$ bit/s e $N\le1030$ (arrotondando per difetto): la differenza è solo di arrotondamento, e all'esame va usato il valore indicato nel corso ($0{,}18$).
• (2) Ufficiale: $\tfrac1{160}$ richieste per slot. Coincide.

Errori comuni

• Confrontare $N\cdot s$ con $56$ kbit/s invece che con $0{,}18\cdot56$ kbit/s: si trova $N=5600$, che sovraccaricherebbe il canale.
• Confondere ALOHA puro ($S_{max}=0{,}18$) e slotted ($S_{max}=0{,}37$): usare lo slotted per la domanda (1) darebbe $N\approx2060$.
• Lasciare le richieste "all'ora" senza convertirle in secondi: $18/\text{ora}$ è $0{,}005/\text{s}$, non $18/\text{s}$.
• Dimenticare che il carico si esprime per slot: $50$ richieste/s sono $50\cdot125\ \mu\text{s}$, non $50$.

(Verificato con Python: $\tfrac1{2e}=0{,}18394$, $0{,}18\cdot56\,000/10=1008$, esatto $1030$; $\lambda=50\ \text{s}^{-1}$, $G=0{,}00625=1/160$.)