Metriche e prestazioni di rete per i servizi multimediali

Per sapere se una rete è in grado di sostenere uno streaming o una videochiamata bisogna saper misurare e calcolare le sue prestazioni: quanti bit al secondo trasporta, quanto ritardo introduce, quanti pacchetti si perdono. Questa nota definisce queste metriche con precisione e le usa per fare i conti che compaiono nei quiz (svolti in Esercizio - Ritardi, throughput e BDP (domande ed esercizi del corso), Esercizio - Canale binario simmetrico e codici di canale (domande ed esercizi del corso) e Esercizio - Stima della banda con il comando ping (dispensa del corso)). Richiami più generali sono in 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 →, Modello ISO-OSI e pila TCP-IPUna comunicazione tra due calcolatori è un problema troppo vario (segnali, errori, accesso al mezzo, instradamento, controllo di flusso, rappresentazione dei dati) per un solo protocollo, quindi si divide in strati (layer). Il modello ISO/OSI ha 7 livelli (fisico, collegamento, rete, trasporto, sessione, presentazione, applicazione); la pila TCP/IP riunisce gli ultimi tre in un solo livello applicazione, quindi ne ha 5. Ogni livello offre un servizio a quello sopra e parla solo con il livello pari dell'altro nodo tramite PDU; scendendo si aggiunge un'intestazione (PCI): incapsulamento. Indirizzi: MAC (collegamento, locale), IP (rete, globale).Modello ISO-OSI e pila TCP-IP → e nella nota sul modello a strati del modulo HTTP, Modello ISO-OSI, data plane e control plane, architetture client-server e publish-subscribeIl modello ISO/OSI (7 livelli) e la pila TCP/IP (4 livelli) dividono la comunicazione in strati; ogni livello riceve una SDU dal livello superiore, aggiunge la sua intestazione e produce una PDU; il confine fra due livelli adiacenti e' il SAP, identificato da un indirizzo (EtherType per Ethernet, numero di protocollo per IP, numero di porta per TCP e UDP) e per un programma C il SAP del trasporto e' l'API delle socket; il data plane inoltra i pacchetti seguendo le tabelle, il control plane le costruisce con i protocolli di instradamento; client/server funziona come una chiamata di funzione (richiesta e risposta), peer-to-peer mette tutti i nodi alla pari, publish/subscribe funziona come un interrupt: un broker inoltra gli eventi agli iscritti, con disaccoppiamento nello spazio, nel tempo e nella sincronizzazione.Modello ISO-OSI, data plane e control plane, architetture client-server e publish-subscribe →.

1. Architettura a strati

Una rete deve risolvere problemi molto diversi: generare segnali fisici dai bit e recuperare i bit dai segnali; gestire i disturbi del canale; assicurare comunicazioni corrette tra due host vicini (single hop); trovare un percorso attraverso più host; gestire messaggi incompleti o persi; offrire servizi di alto livello (e-mail, web, streaming, cloud gaming). Per dominare la complessità le reti sono organizzate come pile di livelli (layers). È un'idea comune in informatica (tipi di dato astratti, sistemi operativi con kernel e servizi, database con livello fisico, logico e vista): si offrono servizi nascondendo i dettagli dell'implementazione.

Livello, servizio, protocollo, interfaccia.

• Un livello ha l'obiettivo di fornire un insieme di servizi ai livelli superiori nascondendo la complessità della sua implementazione; resta definito dai servizi che offre al livello superiore.
• Un servizio è un insieme di primitive offerte al livello superiore: dice che cosa il livello può fare, non come. Si espleta tramite l'interfaccia tra il fornitore (livello inferiore) e l'utente (livello superiore).
• Un protocollo è un insieme di regole che definiscono formato e semantica dei pacchetti scambiati dalle entità pari (peer) dello stesso livello su host diversi.
• Un protocollo si può cambiare, purché servizi e interfacce restino identici (esempio: HTTP/3 usa QUIC su UDP al posto di TCP, mantenendo servizi simili ai livelli superiori).

Esempio: il livello fisico (L1) fa la modulazione (crea un segnale elettromagnetico, ottico o acustico dai bit) e la demodulazione (stima i bit dal segnale) e nasconde ai livelli superiori il canale analogico: offre un servizio di canale digitale per bit. I protocolli superiori non devono sapere se il mezzo è fibra o radio e non cambiano se il livello fisico cambia.

La definizione dei servizi di un livello è in parte arbitraria (esistono più modelli: ISO/OSI e TCP/IP), ma l'idea è che un livello tratti problemi omogenei.

2. Pacchettizzazione

L'applicazione produce dati a una certa velocità (non necessariamente costante) e li offre al livello sottostante (L4), che li suddivide in unità più piccole aggiungendo informazioni di controllo (header); L4 offre i pacchetti a L3, che decide il percorso sorgente-destinazione; ogni livello può spezzare le unità di dati e aggiungere altre intestazioni. A destinazione si fa il processo inverso e i dati dell'applicazione vengono ricostruiti.

Il flusso di bit $s_b(n)$ è diviso in blocchi (source data blocks); un pacchetto è formato da header (dati di controllo: identificativo del blocco, sorgente, destinatario, ecc.) e payload. Ogni livello ha il suo protocollo che definisce sintassi e semantica dell'header, e il pacchetto di un livello è il payload del livello inferiore: $\text{Payload}_N=\text{Intestazione}_N+\text{Payload}_{N-1}$ nei termini del modello a strati.

Vantaggi della trasmissione a pacchetti rispetto a un blocco unico:

1. Efficienza: i pacchetti possono seguire percorsi diversi e la rete si usa meglio;
2. Affidabilità: in caso di errore si ritrasmettono solo i pacchetti danneggiati, non il messaggio intero;
3. Scalabilità: si gestiscono più dispositivi e più traffico senza cambiare l'infrastruttura;
4. Multiplexing statistico: più flussi condividono dinamicamente le stesse risorse (Commutazione di circuito e di pacchettoUn nodo di commutazione (switch) può collegare ingresso e uscita in tre modi. Commutazione di circuito: si stabilisce prima un collegamento fisico dedicato (rete telefonica), tempo di consegna $T=3Nt_p+Nt_s+M/R$. Commutazione di pacchetto a datagramma: il messaggio è diviso in $K$ pacchetti con intestazione, ognuno è instradato indipendentemente con store-and-forward, $T=Nt_p+(N+K-1)\frac{M/K+H}{R}$, con $K_{ott}=\sqrt{(N-1)M/H}$. A circuito virtuale: tre fasi (setup, dati, chiusura), connessione logica dedicata ma senza risorse dedicate, identificatore locale che cambia a ogni salto.Commutazione di circuito e di pacchetto →).

L'applicazione multimediale in linea di principio non dovrebbe conoscere la pacchettizzazione, ma può dare indicazioni: nei video compressi moderni (H.264, HEVC, AV1) la pacchettizzazione segue spesso le unità codificate (ogni immagine in uno o più pacchetti, e in ogni pacchetto dati di una sola immagine). In ricezione la de-pacchettizzazione estrae i dati utili e, grazie alle informazioni di controllo, ricostruisce il bitstream (ordinamento, rilevazione e correzione degli errori).

3. PDU, SDU, overhead ed efficienza

Due entità dello stesso livello si scambiano PDU (protocol data unit). Per esempio una PDU di un'applicazione di comunicazione video (L5) può essere un frame intra. La PDU è virtualmente inviata all'entità pari, ma praticamente viene passata al livello inferiore, che la tratta come SDU (service data unit) e vi aggiunge le proprie informazioni di controllo PCI (protocol control information, cioè header) per formare la propria PDU. Per esempio L4 aggiunge i numeri di porta, L3 gli indirizzi IP.

$$\mathrm{PDU}_n=\mathrm{PCI}_n+\mathrm{SDU}_n,\qquad \mathrm{SDU}_n=\mathrm{PDU}_{n+1}.$$

L'overhead è costituito dai dati di controllo, che si aggiungono al carico utile. Il throughput massimo che il livello $n$ offre al superiore è $$S_{n+1}=S_n\cdot\frac{|\mathrm{SDU}_n|}{|\mathrm{PDU}_n|}=S_n\cdot\frac{|\mathrm{SDU}_n|}{|\mathrm{PCI}_n|+|\mathrm{SDU}_n|}.$$ Si definisce l'efficienza del protocollo di livello $n$ $$\eta=\frac{S_{n+1}}{S_n}=\frac{|\mathrm{SDU}_n|}{|\mathrm{PDU}_n|}=\frac1{1+\frac{|\mathrm{PCI}_n|}{|\mathrm{SDU}_n|}}\in(0,1].$$ Aumenta con le dimensioni della SDU e diminuisce con quelle dell'header (per questo conviene avere SDU grandi e header piccoli). Esistono però altri vincoli che impediscono di avere SDU troppo grandi o header troppo piccoli: un pacchetto lungo ha più probabilità di essere errato (vedi PER), occupa il link più a lungo (ritardo di trasmissione), ecc.

Esempio. Il livello $n+1$ crea PDU da 1200 byte; il livello $n$ ha throughput $S_n=100$ Mbit/s e un header di 60 byte. $|\mathrm{PDU}_n|=1260$ byte, $\eta=\frac{1200}{1260}=0{,}952$, quindi $S_{n+1}=100\cdot\frac{1200}{1260}\approx95{,}24$ Mbit/s (se il livello $n+1$ produce dati abbastanza in fretta e il link non è condiviso).

4. Bit-rate, throughput e goodput

Sono tre concetti simili: una velocità di trasferimento tra due entità pari; la differenza sta nel livello considerato.

Unità: $1\ \text{kbit/s}=10^3$ bit/s, $1\ \text{Mbit/s}=10^6$, $1\ \text{Gbit/s}=10^9$ (non si usano le potenze di 2); byte/s: $1\ \text{kB/s}=8$ kbit/s.

Il bit-rate è la velocità "grezza" con cui i bit attraversano un singolo hop, senza garanzie di affidabilità (i bit possono essere alterati o persi). Dipende da banda in Hz, modulazione e rapporto segnale-rumore.

Vincolo fondamentale: $S\le R_0$. Gli strati superiori non possono essere più veloci dei sottostanti perché: (1) parte della capacità è occupata dai segnali di controllo (overhead); (2) il link può essere congestionato o condiviso da più flussi; (3) i protocolli (specie di L2) possono imporre tempi di inattività (un host non deve trasmettere contemporaneamente a un altro). Nei sistemi reali (Wi-Fi, 5G) il throughput è spesso molto inferiore al bit-rate nominale. In generale: bit-rate $\ge$ throughput $\ge$ goodput.

Il throughput è il rapporto tra quantità di dati e tempo impiegato, quindi dipende dall'intervallo di tempo considerato. Sia $b_n(t)$ il numero cumulativo di bit trasmessi fino a $t$ visto dal livello $n$:

• medio su un intervallo $T$: $s_n(t;T)=\dfrac{b_n(t)-b_n(t-T)}T$;
• istantaneo ($T\to0$): $s_n(t)=\dfrac{db_n(t)}{dt}$ (la derivata di $b_n$);
• di lungo termine (asintotico): $S_n=\lim_{t\to\infty,\,T\to\infty}s_n(t;T)$.

Il throughput di lungo termine a livello applicazione è il goodput.

Esempio (collegamento punto-punto, traffico periodico). Bit-rate PHY $R_0=100$ Mbit/s. L'applicazione genera una PDU da 1200 byte ogni $T=10$ ms; i livelli inferiori portano la PDU a 1260 byte a livello PHY.

• Traffico offerto al PHY: $S=\frac{1260\cdot8}{10^{-2}}=1{,}008$ Mbit/s. È minore del bit-rate: può essere sostenuto, quindi è il throughput di lungo termine del PHY.
• Throughput istantaneo: periodico con periodo 10 ms; la PDU occupa il link per $\frac{1260\cdot8}{10^8}\approx0{,}1$ ms, durante i quali $s(t)=R_0=100$ Mbit/s, e per il resto dei 10 ms (9,9 ms) è zero.
• Goodput APP: $G=S_{\text{PHY}}\cdot\frac{|\mathrm{PDU}_{\text{APP}}|}{|\mathrm{HDR}_{\text{tot}}|+|\mathrm{PDU}_{\text{APP}}|}=1{,}008\cdot\frac{1200}{1260}=960$ kbit/s; oppure, visto che il traffico è sostenuto completamente, $G=\frac{1200\cdot8}{10^{-2}}=960$ kbit/s. Si noti $G\ll R_0$ perché l'applicazione produce poco.
• Overhead del livello APP (frazione del traffico PHY che non è utile all'APP): $\frac{60}{1260}\approx4{,}76\%$ (nota: è $\frac{M-L}{M}$, con $M$ PDU del PHY e $L$ dell'APP).

5. Ritardi

5.1 Ritardo nodale, punto-punto, end-to-end, RTT

• Il ritardo punto-punto (o nodale) $d_{p2p}$ è il tempo tra l'inizio della trasmissione di un pacchetto in un nodo e la sua ricezione completa nel nodo successivo.
• Il ritardo end-to-end $d_{e2e}$ è il tempo tra l'inizio della trasmissione nel primo nodo e la ricezione completa alla destinazione finale: la somma dei ritardi nodali lungo il percorso: $d_{e2e}=\sum_{i=1}^Kd_{\text{nodal},i}$; con $K$ link identici $d_{e2e}=K\,d_{p2p}$.
• Il RTT (round-trip time) tra A e B è la somma dei ritardi end-to-end da A a B e da B ad A; spesso si approssima $\mathrm{RTT}\approx2\,d_{e2e}$.

Il ritardo nodale ha quattro componenti: $$d_{\text{nodal}}=d_{\text{proc}}+d_{\text{queue}}+d_{\text{trans}}+d_{\text{prop}}.$$

1. Processing $d_{\text{proc}}$: controllo d'errore e scelta del link di uscita (instradamento). Tipicamente costante e spesso trascurabile (nei router moderni è fatto in hardware dedicato: ASIC, SmartNIC, DPU). Non confondere con gli algoritmi di routing.
2. Accodamento $d_{\text{queue}}$: tempo che un messaggio passa in un buffer in attesa di essere elaborato. Dipende dal traffico complessivo sul nodo; buffer troppo pieni causano perdita di pacchetti. Si controlla in parte con priorità, schedulazione, controllo di ammissione (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 →).
3. Trasmissione (o di forwarding, di inoltro) $d_{\text{trans}}$: tempo tra la ricezione del primo e dell'ultimo bit del messaggio, cioè il tempo per "mettere" tutti i bit sul link: $$\boxed{d_{\text{trans}}=\frac LR}$$ con $L$ lunghezza del pacchetto (bit) e $R$ bit-rate del link. Esempio: 100 Mbit su un link da 100 Mbit/s: $d_{\text{trans}}=1$ s. Si può ridurre aumentando $R$. Si può calcolare anche a livelli superiori se il sistema lavora al massimo (sempre dati pronti): $d_{\text{trans}}=\frac{|\mathrm{PDU}_{\text{MAC}}|}{S_{\text{MAC}}}$.
4. Propagazione $d_{\text{prop}}$: tempo per la propagazione fisica del segnale dalla sorgente alla destinazione: $$\boxed{d_{\text{prop}}=\frac xc}$$ con $x$ distanza e $c$ velocità di propagazione nel mezzo (circa $2\cdot10^8$ m/s in cavo e fibra, circa i due terzi della luce nel vuoto). Spesso è trascurabile, tranne nelle comunicazioni a lungo raggio (satelliti, transoceaniche: migliaia di km $\to$ decine di ms) e con link ad alto bit-rate. Non si può ridurre (dipende da grandezze che non si possono cambiare). $c$ e $R$ sono grandezze molto diverse: $c$ è una velocità in m/s, $R$ in bit/s.

Esempio. Pacchetto da $L=1000$ bit su un link da 1 Gbit/s lungo 1 km: $d_{\text{trans}}=\frac{1000}{10^9}=1\ \mu\text{s}$, $d_{\text{prop}}=\frac{1\ \text{km}}{2\cdot10^5\ \text{km/s}}=5\ \mu\text{s}$: qui la propagazione domina.

Il ritardo minimo corrisponde a code vuote e processing trascurabile: $d_{p2p,\min}=d_{\text{prop}}+d_{\text{trans}}$.

5.2 Jitter

Il jitter è la varianza (nelle slide; nella pratica si usa spesso la deviazione standard) del ritardo. Il ritardo è un fenomeno aleatorio: conta il valore medio, ma anche lo scostamento dalla media. È critico per cloud gaming, videoconferenza, VR/AR, teleoperazione. Nello streaming un ritardo costante non è un grosso problema; ma se all'improvviso il ritardo cresce, la riproduzione deve fermarsi: freezing, che riduce molto la qualità percepita. Il jitter si contrasta con un buffer di riproduzione (playout buffer): più è grande, più jitter si assorbe, ma ha un costo (memoria e ritardo di avvio). Un jitter elevato richiede lunghi ritardi di riproduzione e produce code più lunghe in media.

6. Prodotto banda-ritardo (BDP)

Se il mittente vuole essere sicuro che il pacchetto $m$ sia stato ricevuto, deve attendere l'ACK; se non arriva entro un timeout si suppone che il pacchetto sia perso e si ritrasmette. Quindi non può scartare $m$ prima di aver ricevuto l'ACK: i pacchetti trasmessi e non ancora confermati restano nel buffer di trasmissione. Quanti sono? Dipende dal BDP (bandwidth-delay product).

Definizione (BDP). Numero di bit (o pacchetti) che possono essere contemporaneamente "in transito" nella connessione: anche il numero di bit ricevuti (a regime) in un tempo pari al RTT. $$\mathrm{BDP}_{\text{bit}}=S\cdot\mathrm{RTT},\qquad\mathrm{BDP}_{\text{pkt}}=\frac{\mathrm{BDP}_{\text{bit}}}{|\mathrm{PDU}|}.$$

Si considera il throughput a regime. Nell'esempio delle slide, tra l'invio del primo pacchetto e la ricezione del suo ACK ne vengono trasmessi 8. Il BDP è importante nelle Long Fat Networks (alta capacità e alta latenza: dorsali transcontinentali, data center interconnessi, satelliti).

Connessioni multi-hop. Il bit-rate da considerare è il minimo tra tutti i collegamenti. Ragione: se la sorgente produce un pacchetto di $L$ bit ogni $T_0$ s, il primo link con $R_1<\frac L{T_0}$ non riesce a trasmettere a ritmo $T_0$ e deve attendere $T_1=\frac L{R_1}>T_0$ prima del pacchetto successivo; i link a valle non possono aumentare la frequenza di arrivo. Perciò il link a bit-rate minimo determina il periodo dei pacchetti, e quindi quanti ne sono "in volo".

Se il buffer di trasmissione è più piccolo del BDP non si riesce a trasmettere in modo continuo:

Esempio (buffer più piccolo del BDP). Buffer di trasmissione 300 kbit, RTT 10 ms, $R=100$ Mbit/s, ritardi di processing e propagazione trascurabili; protocollo di ritrasmissione Go-Back-N (Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →): se l'ACK non arriva entro il RTT si torna a trasmettere dal primo pacchetto non confermato. Il BDP è $100\cdot10^6\cdot10^{-2}=1$ Mbit, maggiore del buffer. Trasmettere 300 kbit richiede $\frac{300\cdot10^3}{100\cdot10^6}=3$ ms; poi il trasmettitore aspetta altri 7 ms (non può sapere se il primo pacchetto è arrivato). Throughput di lungo periodo: 300 kbit ogni 10 ms $=30$ Mbit/s (un terzo del bit-rate). Se invece non si garantisce la ritrasmissione, si può usare tutto il throughput del canale.

Esempio svolto (10 link identici). $k=10$ link, ciascuno di $x=10$ km; pacchetti PHY da $L=10$ kbit; $R=100$ Mbit/s; $c=2\cdot10^8$ m/s; processing trascurabile. Ritardo di propagazione di un hop: $\frac{10^4}{2\cdot10^8}=5\cdot10^{-5}$ s $=50\ \mu$s. Ritardo di trasmissione: $\frac{10^4}{10^8}=100\ \mu$s. Ritardo punto-punto minimo: $150\ \mu$s. End-to-end minimo: $k\cdot150=1500\ \mu$s. $\mathrm{BDP}_{\text{bit}}=R\cdot2d_{e2e}=10^8\cdot2\cdot1{,}5\cdot10^{-3}=300$ kbit $=30$ pacchetti.

Il resto delle varianti (un link più lento, un link più lungo, satellite) è in Esercizio - Ritardi, throughput e BDP (domande ed esercizi del corso).

7. Affidabilità: errori su bit e sui pacchetti

I pacchetti ricevuti possono essere affetti da errori: uno o più bit diversi da quelli inviati (cause tipiche: basso SNR, interferenze, fading). Indici:

• probabilità di errore su bit (bit error rate, BER);
• probabilità di perdita di un pacchetto: un pacchetto può non arrivare mai, o troppo tardi per essere utile; cause: congestione (un nodo riceve più pacchetti di quanti ne può memorizzare) ed errori (un pacchetto riconosciuto errato può essere scartato);
• ordine di ricezione: alcune tecnologie garantiscono l'ordine, ma allora un pacchetto in ritardo ritarda tutti i successivi; per certi servizi conviene trascurare un pacchetto che non può arrivare entro la scadenza.

7.1 Il canale binario simmetrico (BSC)

Il più semplice modello di canale punto-punto a errori su bit è il BSC: accetta in ingresso una sequenza di bit e restituisce una sequenza dello stesso numero di bit (niente inserzioni né cancellazioni); ogni bit viene invertito con probabilità $\varepsilon$, uguale se si trasmette 0 o 1 (da cui "simmetrico"); errori indipendenti e identicamente distribuiti (i.i.d.). Rimando a Canale binario simmetrico, codifica di Gray e probabilità di bitIl canale numerico equivalente a modulatore, canale e demodulatore è un canale binario simmetrico senza memoria (BSC): ogni bit è sbagliato con probabilità $P_{bit}$, indipendentemente dagli altri. Per una modulazione $M$-aria con $n=\log_2M$ bit per simbolo, la probabilità di errore sul simbolo è $P[E]=1-(1-P_{bit})^n\approx nP_{bit}$ e $P_{bit}\le P[E]$. Il legame inverso passa dalla distanza di Hamming tra le parole di bit: $P_{bit}=\sum_k\sum_{j\ne k}p_kP_{j|k}\frac{d_H(\mathbf c_j,\mathbf c_k)}{\log_2M}$. Con la codifica di Gray (simboli adiacenti differiscono per un solo bit) e SNR non troppo basso gli errori più probabili, verso i vicini, sbagliano un solo bit, quindi $P_{bit}\approx\frac{P[E]}{\log_2M}$.Canale binario simmetrico, codifica di Gray e probabilità di bit →.

PER. Un pacchetto di $L$ bit è ricevuto correttamente se e solo se tutti i suoi bit sono corretti. Un bit è corretto con probabilità $1-\varepsilon$; con errori indipendenti il pacchetto è corretto con probabilità $(1-\varepsilon)^L$. Quindi il packet error rate (frazione di pacchetti con uno o più errori, equivalente alla probabilità che un pacchetto abbia almeno un errore) è $$\boxed{\mathrm{PER}=1-(1-\varepsilon)^L\approx L\varepsilon\ \ (\text{se }L\varepsilon\ll1)}.$$ Probabilità di $\ell$ bit errati su $L$: ci sono $\binom L\ell$ modi di scegliere gli $\ell$ errori, ciascuno con probabilità $\varepsilon^\ell(1-\varepsilon)^{L-\ell}$: $$P(\ell)=\binom L\ell\,\varepsilon^\ell\,(1-\varepsilon)^{L-\ell}.$$ Un messaggio di $N$ pacchetti è ricevuto senza errori con probabilità $(1-\mathrm{PER})^N$.

Esempio. $L=1000$ bit, $\varepsilon=10^{-6}$: $\mathrm{PER}=1-(1-10^{-6})^{1000}\approx0{,}0999\%\approx10^{-3}$ (non l'1%: sbagliare di un fattore 10 è tipico dei quiz). Un messaggio di 750 pacchetti arriva intatto con probabilità $(1-10^{-3})^{750}\approx47{,}2\%$.

7.2 Rilevazione e correzione degli errori, codifica di canale

Una tecnica di rilevazione (error detection, ED) riconosce se un pacchetto ha errori; una di correzione (error correction, EC) rileva e corregge. Entrambe aggiungono bit di ridondanza: sono codifica di canale (channel coding), da distinguere dalla codifica di sorgente (la compressione). Quest'ultima toglie ridondanza "non controllata" dei segnali; la codifica di canale aggiunge ridondanza "controllata" per rilevare o correggere errori.

Due famiglie: codici a blocchi (un blocco di $k$ simboli in ingresso produce un blocco di $n>k$ simboli) e codici convoluzionali (un flusso di simboli, $n$ simboli in uscita ogni $k$ in ingresso, con memoria: l'uscita dipende anche dal passato). Rapporto di codifica $R=\frac kn<1$; overhead (frazione di simboli che non portano informazione) $\frac{n-k}n$.

Controllo di parità. Blocchi di $k=7$ bit; si aggiunge il bit $b_8=\sum_{i=1}^7b_i$ (somma modulo 2): il blocco codificato ha sempre un numero pari di 1. In ricezione, se la somma degli 8 bit è $\ne0$ c'è almeno un errore. Con $n=k+1$, $R=\frac k{k+1}$: un errore singolo è rivelato, ma due errori no (un numero dispari di errori è sempre rivelato, un numero pari mai). L'overhead è $\frac1{k+1}$: aumentare $k$ riduce l'overhead ma anche la capacità di rilevazione.

Codice di Hamming (nelle slide "(4,7)": $k=4$ dati, $n=7$; si usa più spesso la scrittura (7,4)). Tre bit di parità, ciascuno controlla un sottoinsieme dei bit: il bit 5 controlla le posizioni $\{1,2,4,5\}$, il 6 le $\{1,3,4,6\}$, il 7 le $\{2,3,4,7\}$. Per $x=0110$: $b_5=0\oplus1\oplus0=1$, $b_6=0\oplus1\oplus0=1$, $b_7=1\oplus1\oplus0=0$, quindi $y=0110\,110$. Se si riceve $\hat y=0010\,110$ (errore sul bit 2):

• controllo $\{1,2,4,5\}$: somma $0+0+0+1=1$: non OK;
• controllo $\{1,3,4,6\}$: $0+1+0+1=0$: OK;
• controllo $\{2,3,4,7\}$: $0+1+0+0=1$: non OK.

Il bit sbagliato sta nell'intersezione dei due insiemi che falliscono: $\{1,2,4,5\}\cap\{2,3,4,7\}=\{2,4\}$; non può essere il 4 perché il secondo controllo (che contiene il 4) è OK; quindi è il bit 2: lo si corregge. Perché funziona: ogni posizione ha un'impronta diversa nei tre controlli (1: $\{A,B\}$, 2: $\{A,C\}$, 3: $\{B,C\}$, 4: $\{A,B,C\}$, 5: $\{A\}$, 6: $\{B\}$, 7: $\{C\}$) e quindi l'insieme dei controlli falliti individua la posizione errata (distanza minima 3: ho verificato in Python che i 16 codeword stanno a distanza $\ge3$ e che ogni errore singolo si corregge). Il codice corregge tutti gli errori singoli oppure rileva tutti gli errori singoli e doppi; con tre o più errori può sbagliare. Qui $R=\frac47$. Rimando a 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 → e Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →.

Burst e interleaving. Con un codice (7,4) si corregge un errore ogni sette bit. Ma alcuni fenomeni fisici concentrano gli errori nel tempo: burst (errori a raffica; per esempio 10 bit errati su 70, tutti consecutivi): il codice (7,4) fallirebbe pur con un errore su sette in media. L'interleaving distribuisce gli errori consecutivi su più blocchi: prima della trasmissione si scrivono i bit nelle righe di una matrice e si leggono le colonne; in ricezione si fa l'operazione inversa.

Esempio. 21 bit numerati $1,\dots,21$, scritti per righe in una matrice $3\times7$ (righe: $1..7$, $8..14$, $15..21$) e letti per colonne: si trasmette $1,8,15,2,9,16,3,10,17,\dots$ Un burst di 3 errori consecutivi colpisce $1,8,15$ (o altre terne): sono uno per riga. Dopo il de-interleaving, ciascuna riga (cioè ciascun blocco del codice (7,4)) ha un solo errore, correggibile. Senza interleaving i tre errori consecutivi sarebbero tutti nello stesso blocco: non correggibili.

Compromessi della codifica di canale.

• Bit-rate: aumentando $R=\frac kn$ si riduce l'overhead ma anche la capacità di ED ed EC.
• Complessità: codici più sofisticati migliorano ED/EC ma costano calcolo e memoria: i turbo codici (convoluzionali) hanno alta capacità di correzione; i codici LDPC (a blocchi con $k$ molto grande) prestazioni simili con costo in memoria alto ma non computazionale; Reed-Solomon e in generale i codici ciclici (CRC) sono efficienti in hardware, meno performanti. Stato dell'arte: LDPC per il payload ad alta velocità (5G, Wi-Fi), codici polar per canali di controllo e pacchetti brevi, Reed-Solomon per errori a burst (link ottici, storage).
• Ritardo: l'interleaving migliora la robustezza ai burst ma aggiunge ritardo; anche i codici convoluzionali richiedono latenza aggiuntiva.

7.3 Perdite per congestione

I pacchetti da inoltrare su un link occupato si accodano nel buffer di uscita del nodo, che ha capacità finita: quando è pieno c'è buffer overflow e bisogna scegliere cosa scartare. Politiche: drop tail (si scartano i nuovi arrivi a buffer pieno); early dropping casuale (sopra una soglia critica, per esempio 2/3 della capacità, si scartano pacchetti in coda a caso). Un pacchetto scartato può essere ritrasmesso dal nodo precedente, dalla sorgente o mai (dipende dai protocolli).

Packet loss rate $P_{\text{LOSS}}$: frazione complessiva dei pacchetti trasmessi non consegnati, per qualsiasi motivo (errori o overflow). I termini "tasso o probabilità di errore, perdita, scarto di pacchetti" (packet error / drop / loss rate) si usano spesso come sinonimi. Packet delivery ratio $\mathrm{PDR}=1-P_{\text{LOSS}}$: frazione consegnata con successo.

Il PDR può essere diverso ai vari livelli, secondo i meccanismi di recupero: un L2 con un PHY inaffidabile può ridurre il $P_{\text{LOSS}}$ visto da L3 con rilevazione e correzione d'errore, ritrasmissioni e interleaving.

8. Misurare le prestazioni: il comando ping

Il comando ping usa il protocollo ICMP (direttamente su IP, senza trasporto) per inviare pacchetti di $L$ bit a una destinazione che risponde con pacchetti della stessa dimensione; misura il RTT di ciascuno (Protocollo ICMPIPv4 non ha meccanismi per segnalare o correggere gli errori né per interrogare host e router: li fornisce l'ICMP (Internet Control Message Protocol), un protocollo di rete i cui messaggi viaggiano dentro datagrammi IP con campo Protocol $=1$. I messaggi sono di errore (destination unreachable, tipo 3; time exceeded, tipo 11; redirect, tipo 5; parameter problem, tipo 12), sempre inviati alla sorgente originale e con l'intestazione IP più i primi 8 byte del datagramma che ha causato l'errore, oppure di interrogazione (echo request 8 e reply 0, timestamp 13-14). ICMP segnala ma non corregge. Con l'echo si fanno ping (RTT) e scoperta dell'MTU (bit D, codice 4, payload massimo $1500-20-8=1472$ byte); con time exceeded e port unreachable si fa traceroute ($n+1$ messaggi con TTL crescente). Attacchi: smurf e redirect.Protocollo ICMP →). Ripetendo $K$ volte per ogni $L$, il RTT osservato è la somma dei ritardi su tutti i link di andata e ritorno ($n$ link in totale): $d_i=d_{i,\text{queue}}+d_{i,\text{proc}}+d_{i,\text{prop}}+\frac L{S_i}$, per cui $$\mathrm{RTT}(L,k)=\Bigl(\sum_{i=1}^n\frac1{S_i}\Bigr)L+\sum_iq_i(k)+\sum_i\tau_i=aL+Q(k)+T,$$ con $a=\sum_i\frac1{S_i}$ coefficiente di $L$, $Q(k)=\sum_iq_i(k)$ somma dei ritardi di accodamento (variabile con la ripetizione $k$) e $T=\sum_i\tau_i$ ritardi di propagazione (costanti; il processing è trascurato). Il RTT cresce con $L$, ma l'accodamento $Q(k)$ maschera la relazione. Per eliminarlo si prende il minimo tra le $K$ misure a $L$ costante: prima o poi un pacchetto trova tutte le code vuote, quindi $\mathrm{RTT}_{\min}(L)=\min_k\mathrm{RTT}(L,k)\approx aL+T$ è una retta. Dalla pendenza $a$ (per esempio con i minimi quadrati) si stima il throughput:

• se tutti gli $n$ link (andata e ritorno) hanno lo stesso throughput $S$: $a=\frac nS$, quindi $S=\frac na$;
• se c'è un collo di bottiglia molto più lento degli altri, uguale in andata e in ritorno: $a\approx\frac2{S_{\text{bn}}}$, quindi $S_{\text{bn}}\approx\frac2a$.

Un esempio numerico è in Esercizio - Stima della banda con il comando ping (dispensa del corso).

Domande d'esame

1. Qual è la differenza tra bit-rate, throughput e goodput? Traccia: sono tutte velocità di trasferimento; cambia il livello: bit-rate = velocità nominale del livello fisico (tra nodi adiacenti), throughput = velocità effettivamente osservata a un livello tra 2 e 4 (sempre $\le$ bit-rate per overhead, condivisione, attese dei protocolli), goodput = throughput a lungo termine utile all'applicazione. Vale bit-rate $\ge$ throughput $\ge$ goodput.

2. Quali sono le componenti del ritardo punto-punto e quali si possono ridurre? Traccia: processing, accodamento, trasmissione $\frac LR$, propagazione $\frac xc$; la trasmissione si riduce aumentando il bit-rate, l'accodamento con priorità e controllo del traffico, il processing con instradamento efficiente; la propagazione no.

3. Un pacchetto di 2000 bit viaggia su un BSC con $\varepsilon=10^{-5}$: qual è il PER? Traccia: $1-(1-10^{-5})^{2000}\approx0{,}0198\approx2\%$.