Esercizio - Rete a maglia di 4 nodi half-duplex - accesso deterministico e casuale

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (scheda "Data link layer", esercizio 2). Una rete cablata ha $4$ nodi half-duplex collegati a maglia completa. Ogni nodo ha costantemente pacchetti da inviare agli altri $3$, tenuti in $3$ code separate (code backlogged). Il tempo è a slot e i nodi sono sincronizzati in modo che in ogni slot ogni nodo possa trasmettere o ricevere, non entrambi. I pacchetti sono tutti lunghi $1000$ bit, la velocità di ogni cavo è $1$ Mbit/s, quindi uno slot dura $1$ ms. Quale throughput massimo si ottiene con: a. un accesso deterministico, in cui è deciso in anticipo chi trasmette e a chi? b. un accesso casuale, in cui ogni nodo trasmette con probabilità $p$ indipendentemente dagli altri e sceglie la destinazione a caso?

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 →, 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 →, 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 del modello. $L=1000$ bit, $R_b=1$ Mbit/s, $t_P=1$ ms. Un nodo che sta trasmettendo non riceve (half-duplex): se un pacchetto è inviato a un nodo che in quello slot trasmette, il pacchetto non è ricevuto. Se due nodi trasmettono allo stesso nodo, c'è collisione e entrambi i pacchetti sono persi. Trasmissioni a nodi diversi (per esempio $A\to B$ e $C\to D$) non si disturbano (a maglia ogni coppia ha il suo cavo).

a. Accesso deterministico

Si decide in anticipo chi trasmette e a chi. Con $4$ nodi half-duplex, in ogni slot al massimo $2$ nodi trasmettono e gli altri $2$ ricevono: per esempio $A\to B$ e $C\to D$. Non si può fare meglio, perché ogni pacchetto occupa un trasmettitore e un ricevitore e ogni nodo fa una sola delle due cose: con $4$ nodi, al più $4/2=2$ trasmissioni per slot. Il massimo è quindi $S=2$ pacchetti per slot: $$\text{throughput}=2\ \text{pacchetti}/\text{slot}\Rightarrow\frac{2\cdot1000\ \text{bit}}{1\ \text{ms}}=2\ \text{Mbit/s}.$$ (Basta ruotare gli accoppiamenti slot dopo slot: $\{A\to B,C\to D\}$, $\{A\to C,B\to D\}$, $\{A\to D,B\to C\}$ e poi le direzioni opposte, perché ogni nodo deve servire tutte e $3$ le sue code.)

b. Accesso casuale

Ogni nodo, in ogni slot: con probabilità $p$ trasmette (e sceglie a caso uno degli altri $3$, ognuno con probabilità $p/3$); con probabilità $1-p$ ascolta.

Un primo tentativo (lungo). Si potrebbero enumerare tutti i casi con la formula delle probabilità totali: per esempio nessun nodo trasmette con probabilità $(1-p)^4$ (throughput $0$); $A,B,C$ ascoltano e solo $D$ trasmette con probabilità $(1-p)^3p$ (throughput $1$ pacchetto: nessuno disturba $D$, e il destinatario è in ascolto). Ma i casi sono tanti.

Un modo più rapido: si ragiona su un nodo ricevente. Si consideri il nodo $A$. Quando riceve correttamente un pacchetto?

1. $A$ deve essere in ascolto: probabilità $1-p$;
2. uno solo degli altri $3$ nodi deve trasmettere ad $A$. Ogni altro nodo trasmette ad $A$ con probabilità $p/3$ (trasmette con probabilità $p$ e sceglie $A$ tra i $3$ possibili destinatari con probabilità $1/3$). Ci sono $3$ modi di scegliere quale nodo è l'unico mittente, quindi il fattore è $3\cdot\frac p3$;
3. i due nodi rimasti non devono trasmettere ad $A$: ognuno con probabilità $1-\frac p3$ (possono tranquillamente trasmettere ad altri), quindi $\big(1-\frac p3\big)^2$.

Dunque la probabilità che $A$ riceva correttamente un pacchetto in uno slot è $$P_A=(1-p)\cdot3\cdot\frac p3\cdot\Big(1-\frac p3\Big)^2=p(1-p)\Big(1-\frac p3\Big)^2.$$ I $4$ nodi sono equivalenti, quindi il throughput totale (pacchetti correttamente ricevuti per slot) è $$S(p)=4\,p\,(1-p)\Big(1-\frac p3\Big)^2.$$ (Controllo sul caso $p=1$: $S=0$, tutti trasmettono e nessuno ascolta; $p=0$: $S=0$.)

Massimizzazione. Si pone $\frac{dS}{dp}=0$. Con $f(p)=p(1-p)(1-p/3)^2$: $$f'(p)=(1-2p)\Big(1-\frac p3\Big)^2+p(1-p)\cdot2\Big(1-\frac p3\Big)\Big(-\frac13\Big)=\Big(1-\frac p3\Big)\Big[(1-2p)\Big(1-\frac p3\Big)-\frac23p(1-p)\Big].$$ Il fattore $1-\frac p3=0$ darebbe $p=3$ (impossibile, $p\le1$). Resta $$(1-2p)\Big(1-\frac p3\Big)-\frac23p(1-p)=1-\frac p3-2p+\frac23p^2-\frac23p+\frac23p^2=1-3p+\frac43p^2=0,$$ cioè, moltiplicando per $3$: $4p^2-9p+3=0$, $p=\dfrac{9\pm\sqrt{81-48}}{8}=\dfrac{9\pm\sqrt{33}}8$. La radice con $+$ è $>1$ ($1{,}84$), da scartare: $$p^*=\frac{9-\sqrt{33}}8=0{,}4069,\qquad S(p^*)=4\cdot0{,}4069\cdot0{,}5931\cdot(0{,}8644)^2=0{,}7212.$$ (Le slide scrivono la radice come $(9-\sqrt{33})/4$, ma il valore numerico $p^*=0{,}4069$ è quello di $(9-\sqrt{33})/8$.)

Throughput massimo: $$\text{throughput}=0{,}7212\ \text{pacchetti/slot}\cdot\frac{1000\ \text{bit}}{1\ \text{ms}}=721{,}2\ \text{kbit/s}.$$

Confronto

Con l'accesso deterministico si arriva a $2$ Mbit/s, con quello casuale a $0{,}72$ Mbit/s: il casuale usa il $36\,\%$ del massimo ($0{,}7212/2$). Il prezzo dell'accesso casuale è la perdita per collisioni e per i pacchetti spediti a nodi che stanno trasmettendo (half-duplex).