Esercizio - Slotted ALOHA e ALOHA con N trasmettitori

Testo (scheda "Data link layer", esercizio 3). Con un approccio simile al problema precedente si risolva questa situazione più generale. La rete contiene $N$ trasmettitori potenziali e un solo ricevitore. Il tempo è a slot e in ogni slot tutti i nodi decidono individualmente se trasmettere, con probabilità $p$, indipendentemente. Se $N\to\infty$ e $p$ è scelta in modo ottimo si ottiene una dimostrazione alternativa che il massimo throughput normalizzato dello slotted ALOHA è $1/e$. Analogamente, togliendo l'ipotesi di tempo a slot, si ottiene che il massimo throughput normalizzato dell'ALOHA è $1/(2e)$.

Teoria usata: 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 →, 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 →, Calcolo dei limiti di successioniGli strumenti per calcolare i limiti senza la definizione: algebra dei limiti, permanenza del segno, carabinieri, infinitesima per limitata, algebra degli infiniti, reciproco, confronto per le divergenti e forme indeterminate.Calcolo dei limiti di successioni →, Limiti notevoli e gerarchia degli infinitiI limiti di base per sciogliere le forme indeterminate delle successioni: potenze, polinomi, il numero e, esponenziali, la gerarchia logaritmi < potenze < esponenziali < fattoriale < n^n e la razionalizzazione.Limiti notevoli e gerarchia degli infiniti →.

1. Slotted ALOHA

Con un solo ricevitore, se due nodi trasmettono nello stesso slot c'è collisione. Quindi uno slot ha successo se e solo se esattamente un nodo trasmette. Con $N$ nodi indipendenti (ognuno trasmette con probabilità $p$, uno trasmette e gli altri $N-1$ no, e il nodo che trasmette può essere uno qualunque degli $N$ nodi: Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →): $$S(p)=N\,p\,(1-p)^{N-1}.$$ Massimo. Si deriva rispetto a $p$ (con $N$ fisso): $$\frac{dS}{dp}=N(1-p)^{N-1}-N(N-1)p(1-p)^{N-2}=N(1-p)^{N-2}\big[(1-p)-(N-1)p\big]=N(1-p)^{N-2}\,(1-Np).$$ Il fattore $(1-p)^{N-2}=0$ per $p=1$ dà un minimo (si scarta: $S(1)=0$ per $N\ge2$), e $1-Np=0$ dà $$\boxed{p^*=\frac1N}.$$ È una soglia naturale: in media trasmette un nodo per slot ($Np^*=1$). Throughput massimo: $$S(p^*)=N\cdot\frac1N\Big(1-\frac1N\Big)^{N-1}=\Big(1-\frac1N\Big)^{N-1}.$$ Per $N\to\infty$ si usa il limite notevole $\big(1+\frac xN\big)^N\to e^x$, con $x=-1$: $\big(1-\frac1N\big)^{N}\to e^{-1}$ e il fattore mancante $\big(1-\frac1N\big)^{-1}\to1$: $$\lim_{N\to\infty}S(p^*)=\frac1e\simeq0{,}368.$$ Valori: $N=2$: $S=0{,}5$; $N=4$: $0{,}422$; $N=10$: $0{,}387$; $N=100$: $0{,}370$; $N=1000$: $0{,}3681$.

2. ALOHA puro (senza slot)

Senza slot un pacchetto di durata $t_P$ ha successo se nessun altro nodo cerca di trasmettere né prima né dopo: l'intervallo di vulnerabilità è $2t_P$, cioè due "finestre" di durata $t_P$ (si divide idealmente il tempo in finestre di durata $t_P$ e ogni nodo decide, in ciascuna finestra, di iniziare con probabilità $p$). Il nodo che trasmette ha successo se gli altri $N-1$ non iniziano in nessuna delle due finestre: $(1-p)^{2(N-1)}$. Quindi $$S(p)=N\,p\,(1-p)^{2N-2}.$$ Derivando: $\frac{dS}{dp}=N(1-p)^{2N-3}\big[(1-p)-(2N-2)p\big]=N(1-p)^{2N-3}\big[1-(2N-1)p\big]$, che si annulla per $$p^*=\frac1{2N-1}.$$ Throughput: $$S(p^*)=\frac N{2N-1}\Big(1-\frac1{2N-1}\Big)^{2N-2}.$$ Per $N\to\infty$: $\frac N{2N-1}\to\frac12$ e $\big(1-\frac1{2N-1}\big)^{2N-2}\to e^{-1}$ (esponente $\sim2N-1$ al denominatore), quindi $$\lim_{N\to\infty}S(p^*)=\frac1{2e}\simeq0{,}184.$$ Valori: $N=2$: $0{,}296$; $N=10$: $0{,}199$; $N=100$: $0{,}185$. Sono gli stessi limiti ottenuti con $S=Ge^{-G}$ e $S=Ge^{-2G}$ (con $G=Np$ traffico offerto e $\lim_{N\to\infty}(1-p)^{N}=e^{-Np}$).

Perché i due metodi coincidono. Nel limite $N\to\infty$, $p\to0$ con $Np=G$ fissato, $(1-p)^{N-1}\to e^{-G}$ e $S\to Ge^{-G}$ (slotted) e, con $2N-2$ al posto di $N-1$, $S\to Ge^{-2G}$ (puro): la $p$ ottima corrisponde a $G=1$ e $G=1/2$ rispettivamente, in accordo con la derivazione basata sulla probabilità di Poisson di zero arrivi.