Lezione 20Esercizi sul livello di collegamento

Appunti di riferimento: tlc_20 (soluzioni dei tre esercizi della scheda "Data link layer").

Argomenti trattati

1. ARQ e stabilità: pacchetti di $4192$ bit a $2$ Mbit/s con $P_{bit}=10^{-6}$; $p=0{,}418\,\%$, $\mu\simeq475$ pkt/s; con $\lambda=100$ pkt/s throughput $=\lambda$ (stabile), con $\lambda=1000$ pkt/s sistema instabile e throughput $1-p$. Il throughput $\min(\lambda,\mu)$ e il servizio medio $m_y$ di SW, GBN e SR (con il trucco $\lambda_T=\lambda/P_{success}$).
2. Rete a maglia di $4$ nodi half-duplex: accesso deterministico ($2$ Mbit/s) contro casuale ($S(p)=4p(1-p)(1-p/3)^2$, $p^*=0{,}4069$, $721$ kbit/s).
3. $N$ trasmettitori e un ricevitore: $S=Np(1-p)^{N-1}$, $p^*=\frac1N$, limite $\frac1e$ (slotted); senza slot $S=Np(1-p)^{2N-2}$, $p^*=\frac1{2N-1}$, limite $\frac1{2e}$.

Teoria

• 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 →
• 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 →
• 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 →

Esercizi

• Esercizio - Throughput di SR-ARQ e stabilità della coda ARQ
• Esercizio - Rete a maglia di 4 nodi half-duplex - accesso deterministico e casuale
• Esercizio - Slotted ALOHA e ALOHA con N trasmettitori
• Esercizio - Pacchetti su BSC, stabilità e traffico offerto — esempio numerico degli appunti di Bressanone

Lezione precedente: Lezione 19 · ALOHA, CSMA e persistenza