Livello di collegamento - LLC, MAC e ipotesi di lavoro

Qui comincia la seconda parte del capitolo: il passaggio dal livello fisico (il canale "domato" dalla Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale → e dai codici di Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →) al livello 2, cioè al livello di collegamento (Introduzione alle reti di telecomunicazioneUn servizio di telecomunicazione porta informazione da un trasmettitore a un ricevitore attraverso un canale. Le comunicazioni si classificano per destinatari (unicast, broadcast, multicast, anycast, multi-point) e per direzione (unidirezionali, bidirezionali; canali half-duplex e full-duplex); la rete è un grafo (nodi e archi) con topologie stella, mesh, albero, anello, bus, e una parte di accesso e una di core. Le risorse si danno con la commutazione di circuito (riservate) o di pacchetto (condivise, datagramma o circuito virtuale). Il controllo è diviso in livelli con protocolli, primitive, PDU/SDU/PCI e incapsulamento $PDU_N=PCI_N+SDU_N$; il modello ISO/OSI ha 7 livelli.Introduzione alle reti di telecomunicazione →: pila ISO/OSI). Le due note successive studiano come si gestiscono gli errori (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 →) e l'accesso condiviso al canale (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 →); questa fissa linguaggio e ipotesi.

Vedi anche Livello di collegamento e framingIl livello di collegamento (DLL) consegna un frame da un nodo a un nodo adiacente su un collegamento. Servizi: framing, accesso al mezzo (MAC) con indirizzi MAC a 48 bit, controllo di flusso, rilevazione e correzione degli errori. Si divide in DLC (framing, controllo di errore e di flusso) e MAC (accesso al mezzo condiviso). Il framing delimita i frame con un flag: nei protocolli a byte (flag di 8 bit, ESC) si usa il byte stuffing, in quelli a bit (flag 01111110) il bit stuffing, che inserisce uno 0 dopo ogni cinque 1 consecutivi.Livello di collegamento e framing →, 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 → e Introduzione alla teoria delle codeUn sistema a coda (QS) è fatto da un processo di arrivi (di Poisson, tasso $\lambda$), una coda e uno o più servitori con tasso di servizio $\mu$. Carico offerto $G=\lambda/\mu$, fattore di carico $\rho=\lambda/(m\mu)$: il sistema è stabile solo se $\rho<1$, e allora il throughput è $\lambda$ (altrimenti è $m\mu$). Legge di Little: $E[x]=\lambda E[s]$, valida per qualsiasi disciplina. Coda M/M/1: $E[x]=\frac{\rho}{1-\rho}$, $E[s]=\frac{1/\mu}{1-\rho}$, $E[w]=\frac{\rho/\mu}{1-\rho}$. Con servizio deterministico (M/D/1, caso particolare di Pollaczek-Khinchin): $E[w]=\frac{\rho}{2\mu(1-\rho)}$. Il ritardo cresce senza limite quando $\rho\to1$.Introduzione alla teoria delle code →.

Il ruolo del livello 2

Il livello 2 vede un canale fisico con errori residui e passa ai livelli superiori un canale arbitrariamente affidabile. Ci si chiede: perché non basta il teorema di Shannon, applicato al livello 1? Perché

• alcuni errori di modulazione si correggono con la codifica di canale, ma si vuole correggerli tutti;
• bisogna regolare l'accesso al canale quando è condiviso.

Per questo il livello 2 ha due sottolivelli:

L'LLC e in particolare l'ARQ sono un argomento di confine tra i livelli 1 e 2 (coinvolgono la codifica di canale, che si può mettere dove si vuole); l'ARQ non è nemmeno una funzione esclusiva dell'LLC (è opzionale e la usano anche altri livelli).

Perché serve il MAC: SNR contro SINR

Una coppia trasmettitore-ricevitore TX$_1\to$RC$_1$ sceglie la velocità $R_1<C_1=B_1\log_2(1+\mathrm{SNR}_1)$ (il teorema di Shannon dice allora che va tutto bene, ma solo se la capacità è calcolata bene). Se nello stesso posto c'è un'altra coppia TX$_2\to$RC$_2$ che trasmette, TX$_2$ interferisce su RC$_1$: il rapporto giusto non è l'SNR ma la SINR (Signal to Interference plus Noise Ratio), più bassa: $$\mathrm{SINR}_1=\frac{P_{tx1}/a_{ch1}}{P_{tx2}/a_{ch2}+N_0B}\ \le\ \mathrm{SNR}_1=\frac{P_{tx1}/a_{ch1}}{N_0B}.$$ Poiché ingegneristicamente si fissa $R<B\log_2(1+\mathrm{SNR})$ di poco, passare alla SINR viola Shannon: la comunicazione non è più affidabile. Una soluzione è impedire a un altro trasmettitore di interferire: ecco il ruolo del MAC.

Esempio. Con $\mathrm{SNR}=20$ dB ($100$), la capacità vale $\log_2(101)=6{,}66$ bit/s/Hz. Se l'interferente arriva a $10$ dB sopra il rumore (potenza $10N_0B$), $\mathrm{SINR}=\frac{100}{10+1}=9{,}1$ ($9{,}6$ dB) e la capacità scende a $\log_2(10{,}1)=3{,}34$ bit/s/Hz: una velocità scelta a $6{,}5$ bit/s/Hz ora supera la capacità.

Il ruolo di MAC e LLC si riassume così: il MAC stabilisce chi può parlare (e lo si può stabilire in buona parte in anticipo: come quando una persona fa da relatore, o si alza la mano); l'LLC risolve i problemi non prevedibili in anticipo, per esempio con l'ARQ che chiede una ritrasmissione se il messaggio è ancora in errore (serve un'altra comunicazione di ritorno). Idea di base dell'ARQ: dopo ogni messaggio il ricevitore deve confermare: manda un pacchetto di controllo, senza dati, detto ACK (acknowledgment), che conferma la ricezione corretta; oppure un NACK (negative acknowledgment), che fa partire una ritrasmissione.

Ipotesi di lavoro del livello 2

Per studiare le prestazioni si fissano ipotesi semplici (da non applicare ciecamente: le formule vanno usate sapendo quando valgono).

1. Pacchetti uguali e probabilità $p$. Tutti i dati del livello 2 viaggiano in pacchetti di $L$ bit (a volte $L=L_D+L_O$: payload più overhead di incapsulamento e controllo). Ogni pacchetto è sbagliato con probabilità $p$, in modo indipendente da un pacchetto all'altro. Per esempio, su un BSC senza memoria (Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →) il pacchetto è giusto se tutti gli $L$ bit lo sono, con probabilità $(1-P_{bit})^L$: $$p=1-(1-P_{bit})^L\simeq L\,P_{bit}\qquad(P_{bit}\ll1),$$ perché $(1-P_{bit})^L=1-LP_{bit}+o(P_{bit})$ (Binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton →, Formula di Taylor con resto di PeanoUna funzione derivabile n volte in x0 si scrive, vicino a x0, come un polinomio di grado al più n (il polinomio di Taylor, costruito con le derivate in x0) più un errore o((x-x0)^n); il polinomio è unico. Per x0 = 0 si chiama sviluppo di Mac-Laurin.Formula di Taylor con resto di Peano →). La probabilità di $h$ errori sul pacchetto è $\binom Lh P_{bit}^h(1-P_{bit})^{L-h}$ (Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →). I casi reali sono infiniti (può esserci una codifica in più; oppure $P_{bit}$ piccolissima ma ulteriori errori da interferenza, collisioni: $p=p_{coll}$): al livello 2 non importa l'origine di $p$, si sa solo che c'è e la si gestisce.

Esempio. $P_{bit}=10^{-6}$, $L=4192$ bit: $p=1-(1-10^{-6})^{4192}=4{,}18\cdot10^{-3}$ ($0{,}418\,\%$), contro l'approssimazione $LP_{bit}=4{,}19\cdot10^{-3}$.

2. Coda sempre piena. Il sistema funziona come un sistema a coda (Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →): i pacchetti sono i clienti, e per stimare quanto si può servire si assume la coda sempre piena (backlogged queue, heavy traffic: "c'è sempre qualcosa da trasmettere"): si ottengono i valori massimi raggiungibili.

3. Velocità costante: tempo di pacchetto. La trasmissione avviene a bitrate costante $R_b$ (quindi il servizio è deterministico): si definisce il tempo di pacchetto $t_P=L/R_b$. Per gli ACK/NACK (più corti, lunghezza $L_A$): $t_A=L_A/R_b$. Normalmente $t_A<t_P$, ma non c'è una regola: a volte $t_A$ è trascurabile, altre volte si assume $t_A=t_P$.

4. Ritardo di propagazione e round-trip. Si include il ritardo di propagazione $\tau_P$ (simmetrico nei due versi; un eventuale ritardo di elaborazione $\tau_{proc}$ si trascura o si somma a $\tau_P$). Il tempo per "andare e tornare", dall'istante di inizio trasmissione al momento in cui il trasmettitore sa se è andata bene, è il tempo di round-trip $$t_{RTT}=t_P+t_A+2\tau_P.$$ (Prima si trasmette il pacchetto, $t_P$; poi il ricevitore lo riceve dopo $\tau_P$ e invia l'ACK, $t_A$; che torna dopo altri $\tau_P$.)

5. Timeout. Non basta dire "il pacchetto è errato con probabilità $p$": ci sono tre esiti possibili: ricevere ACK, ricevere NACK, non ricevere niente. Il terzo si evita con un timeout $t_O$ (una scadenza): scaduto il quale si assume come NACK. Molto spesso $t_O=t_{RTT}$: timeout stringente.

6. ACK e NACK sempre corretti. Sono corti e si possono proteggere con codici forti. Se invece potessero sbagliare, si aumenta in pratica il valore di $p$ (più o meno, dipende dall'errore).

7. Ritrasmissioni illimitate finché non arriva un ACK. Numero medio di ritrasmissioni: se si fanno esattamente $j$ ritrasmissioni, cioè $j$ fallimenti seguiti da un successo, con probabilità $(1-p)p^j$: $$E[\#retx]=\sum_{j=0}^{\infty}j\,(1-p)p^j=(1-p)\,p\sum_{j=1}^{\infty}jp^{j-1}=(1-p)\,p\,\frac1{(1-p)^2}=\frac p{1-p}.$$ (Si è usata $\sum_{j\ge1}jp^{j-1}=\frac d{dp}\frac1{1-p}=\frac1{(1-p)^2}$, Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →: stessa serie di una variabile geometrica, Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →.) Poiché $\#tx=1+\#retx$ (tentativi $=1$ in più delle ritrasmissioni): $$E[\#tx]=1+\frac p{1-p}=\frac1{1-p}=\frac1{P_{success}},\qquad P_{success}=1-p.$$

Esempio. $p=0{,}1$: in media $0{,}111$ ritrasmissioni e $1{,}111$ tentativi per pacchetto; $p=0{,}5$: $1$ ritrasmissione e $2$ tentativi.

Metriche di prestazione

Si valutano throughput e ritardo.

• Ritardo (medio): il tempo trascorso dall'inizio della trasmissione fino alla sua ricezione corretta, calcolato lato ricevitore ($t_{delay}=s+\tau_P$, con $s$ tempo medio di sistema; è un'altra differenza rispetto alla teoria delle code).
• Throughput: non è quello della teoria delle code: (1) si contano solo i pacchetti corretti; (2) ci sono ritrasmissioni, mentre nei sistemi a coda i clienti uscivano sempre dal sistema (non tornano indietro).

Esempio (FEC). Un sistema senza ritrasmissioni, in cui i pacchetti sbagliati sono persi: throughput $=1-p$, ritardo $=t_P+\tau_P$. Con ARQ il ritardo è invece complicato (vedi 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 →) e il throughput si calcola come frazione di tempo d'aria: $$S=\frac{t_P}{m_{t_T}},\qquad m_{t_T}=\text{tempo medio totale speso per un pacchetto}.$$

Richiamo di teoria delle code

Per $m$ servitori e arrivi a tasso $\lambda$ (Poisson, Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →), con tempo di servizio medio $m_y$ e tasso di servizio $\mu=1/m_y$: il sistema è stabile se la distribuzione di $X(t)$ (numero di clienti nel sistema, $X=Z+q$, in servizio più in coda) ammette limite stazionario non degenere indipendente da $X(0)$. La condizione (Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, condizione di Loynes) è $\lambda<m\mu$. Il throughput assoluto è $\lambda$ se il sistema è stabile ("quel che entra, esce") e $m\mu$ se è instabile; normalizzato $S=\eta/\mu\le m$. Con $m=1$ si definiscono il fattore di carico $\rho=\lambda/\mu$ e il traffico offerto $G=\lambda/\mu$: se stabile $S=\rho=G$. Il ritardo totale è $m_{delay}=m_w+t_P+\tau_P+m_{retx}$ (attesa in coda, trasmissione, propagazione, ritrasmissioni).

Esempio (appunti del corso, Bressanone). $\lambda=50$ pkt/s, $R_b=1$ Mbit/s, $L=10\,000$ bit: $t_P=10$ ms, $\mu=R_b/L=100$ pkt/s; $\lambda<\mu$: stabile, $\rho=G=0{,}5$, throughput $50$ pkt/s ($0{,}5$ Mbit/s). Con $\lambda=150$ pkt/s sarebbe instabile e il throughput si fermerebbe a $\mu=100$ pkt/s ($S=1$).

Il modello di collisione

Si considerino $2$ trasmissioni coesistenti. Se due pacchetti si sovrappongono nel tempo di trasmissione, anche per una parte piccolissima, entrambi si considerano persi: non importa quanto sia piccola la sovrapposizione. (Nei disegni si pone $\tau_P=0$ senza perdere generalità: includerlo non cambia il ragionamento.) Si riformula allora la condizione di Shannon $R<C$:

• se un pacchetto è indisturbato (l'unico trasmesso) per tutti i suoi $t_P$ secondi, è sicuramente senza errori (da interferenza);
• altrimenti c'è una collisione, il pacchetto è in errore, e si gestisce con le ritrasmissioni.

Questo permette di astrarre dai dettagli fisici (modulazione, codifica, ...). Il modello è conservativo (pessimistico) per due motivi: si perde il pacchetto anche per una sovrapposizione minima, mentre con la codifica di canale si potrebbe sperare di recuperarlo; e quando Shannon non vale ($R>C$) non è detto che vada tutto male, anche se sotto collisione la capacità di solito diventa piccolissima. Si assume infine di aver preso contromisure per rivelare questi problemi (per esempio con la codifica di canale).

Il livello MAC in sintesi

Il MAC è (probabilmente) la parte più importante del livello 2 e decide chi può parlare. Regola di fondo: parlare uno per volta, almeno nella stessa zona, detta dominio di collisione (la regione geografica in cui ognuno sente tutti gli altri, quindi una collisione disturba tutti). Metriche: throughput (come nelle code, più le ritrasmissioni) e ritardo medio del pacchetto $m_{delay}$ (tempo medio dalla prima trasmissione del pacchetto alla sua ricezione corretta). Il tipo di accesso (deterministico, a richiesta, casuale), il backoff e le prestazioni sono in 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 →.

Errori comuni

• Usare le formule dell'ARQ senza controllare la stabilità ($\lambda<\mu$): sono valori massimi in heavy traffic. È la trappola dell'Esercizio - Throughput di SR-ARQ e stabilità della coda ARQ.
• Usare $p=LP_{bit}$ quando $LP_{bit}$ non è piccolo.
• Confondere il throughput delle code con quello del livello 2 (conta solo ciò che arriva corretto) e il ritardo (misurato lato ricevitore, fino alla ricezione corretta).
• Dimenticare che $t_{RTT}$ include $t_A$ e due ritardi di propagazione.