Lezione 17Livello di collegamento, ARQ e accesso deterministico (TDMA e FDMA)

Appunti di riferimento: tlc_17 e slide TLC10 (ARQ).

Argomenti trattati

1. Ruolo del livello 2: canale con errori residui che diventa affidabile; sottolivelli LLC e MAC; perché serve il MAC (SINR contro SNR, interferenza e violazione di Shannon).
2. ARQ in astratto: ACK, NACK, timeout; ipotesi di lavoro: pacchetti di $L$ bit, probabilità $p$ i.i.d., coda sempre piena, $t_P$, $t_A$, $\tau_P$, $t_{RTT}$, timeout stringente, ACK sempre corretti, ritrasmissioni illimitate; $E[\#tx]=\frac1{1-p}$.
3. Metriche: throughput come frazione di tempo d'aria e ritardo fino alla ricezione corretta.
4. Stop-and-Wait, Go-Back-N, Selective Repeat: funzionamento (slide animate con $N=3$), throughput $\frac{t_P(1-p)}{t_{RTT}}$, $\frac{1-p}{(N-1)p+1}$, $1-p$; buffer; efficienza.
5. Modello di collisione, dominio di collisione, metriche del MAC.
6. Tipi di accesso: deterministico, a richiesta, casuale; collisioni e backoff.
7. Accesso deterministico: ipotesi con $N_u$ utenti, M/D/1; TDMA e FDMA, SDMA e CDMA (DS-CDMA, frequency hopping).
8. Prestazioni: stabilità $N_u\lambda t_P<1$; ritardo del TDMA ($w=w_1+w_2$, attesa dell'autobus più M/D/1) e dell'FDMA; confronto: FDMA peggiore di $t_P(N_u/2-1)$.

Teoria

• 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 → — punti 1-3 e 5
• 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 → — punti 2-4
• 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 → — punti 6-8

Esercizi

• Esercizio - Throughput di SR-ARQ e stabilità della coda ARQ
• Esercizio - Pacchetti su BSC, stabilità e traffico offerto

Lezione precedente: Lezione 16 · Codici lineari, sindrome, capacità di canale e teorema di Shannon · Lezione successiva: Lezione 18 · Esercizi su codici e capacità