Lezione 11 · Canale 1 · lunedì 19 ottobre 2026

Checksum, CRC e ritardo di trasferimento

FCI · Reti

Rilevare un errore con bit aggiuntivi

Per proteggere una stringa di bit se ne calcola un'altra, più corta, che dipende da essa: è l'overhead. Le due stringhe viaggiano insieme. Chi riceve rifà lo stesso calcolo e confronta il risultato con ciò che è arrivato. Se non coincide, c'è stato un errore. Il controllo dice che qualcosa è cambiato, non quale bit. I metodi sono due: l'Internet checksum, facile da calcolare in software, e il CRC, basato sulla divisione fra polinomi.

Internet checksum

La stringa da proteggere è una sequenza di parole di 16 bit, $b_0, b_1, \dots, b_{m-1}$ , ciascuna letta come un intero. Il checksum è una parola $b_m$ , anch'essa di 16 bit, scelta in modo che la somma di tutte le parole, checksum compresa, valga 0 modulo $2^{16}-1$ :

\begin{aligned} S&=b_0+b_1+\dots+b_{m-1}\pmod{2^{16}-1}\\ b_m&=-S\pmod{2^{16}-1} \end{aligned}

Il numero di parole si chiama $m$ e la somma $S$ perché più avanti $L$ indica i bit di testo di un pacchetto e $x$ la variabile dei polinomi.

Sommare modulo 15 significa contare e ripartire da 0 quando si arriva a 15. È il modulo delle parole di 4 bit, $2^4-1=15$ , cioè il valore di $1111$ : $8+4+2+1$ .

Esempio. Con $b_0=1100=12$ e $b_1=1010=10$ :

\begin{aligned} S&=12+10=22\equiv 7\pmod{15}\\ b_2&=-7\equiv 8\pmod{15} \end{aligned}

Quindi $S=0111$ e $b_2=1000$ . Il checksum si ottiene invertendo ogni bit di $S$ : $1111-S$ trasforma ogni 1 in 0 e ogni 0 in 1, e $1111=15$ , quindi $15-S=-S$ modulo 15.

In binario la somma si fa con il riporto. Si ha $1100+1010=10110$ e il riporto uscito a sinistra si riaggiunge a destra: $0110+1=0111$ . Il passaggio è lecito perché togliere $2^4=16$ e aggiungere 1 equivale a togliere 15.

Contare modulo 15

S

b_{0}

b_{1}

b_{2}

conteggiomodulo 15

conteggio modulo 15

b_{0}

b_{1}

Sommare modulo 15 è contare ripartendo da 0 a ogni multiplo di 15. Il checksum

b_{2}

è quanto manca alla somma per arrivare al multiplo successivo, dove il conto torna a 0.

Controllo in ricezione. Chi riceve somma tutte le parole, checksum compresa: $0111+1000=1111$ , cioè $15\equiv 0$ . Con parole di 16 bit il risultato corretto è fatto di soli 1. Un risultato diverso segnala un errore, senza dire in quale parola. Soli 1 non provano però che non ci siano errori.

Lo usano IP, TCP e UDP. Nell'intestazione IP le righe si leggono come parole da 16 bit e il checksum ne occupa una, quindi l'overhead è di 16 bit.

CRC: le stringhe come polinomi

Una stringa di $K$ bit si legge come i coefficienti, 0 o 1, di un polinomio di grado al più $K-1$ . Il bit più a destra è il coefficiente di $x^0$ :

P(x)=a_{K-1}x^{K-1}+\dots+a_1x+a_0

Per esempio $1100$ è $P(x)=x^3+x^2$ .

I coefficienti si sommano modulo 2, dove $1+1=0$ . Quindi somma e sottrazione coincidono e sono uno XOR sui bit: due termini uguali si cancellano.

(x^7+x^6+1)+(x^6+x^5)=x^7+x^5+1

Moltiplicare per $x^z$ sposta la stringa a sinistra di $z$ posizioni, cioè aggiunge $z$ zeri in coda.

Costruire la parola di codice

Chi trasmette e chi riceve concordano un polinomio generatore $G(x)$ , di grado $z$ , con coefficienti di $x^z$ e di $x^0$ uguali a 1. Fa parte del protocollo. Si divide $x^zP(x)$ per $G(x)$ , con le regole modulo 2:

x^zP(x)=Q(x)G(x)+R(x),\qquad \deg R<z

Il quoziente $Q(x)$ non serve. Il resto $R(x)$ ha al più $z$ coefficienti e si scrive con $z$ bit, completando con zeri a sinistra. La parola trasmessa è

T(x)=x^zP(x)+R(x)

cioè i dati seguiti dai $z$ bit del resto. Poiché somma e sottrazione coincidono, $T(x)=x^zP(x)-R(x)=Q(x)G(x)$ : ogni parola di codice è divisibile per $G(x)$ .

Chi riceve divide per $G(x)$ ciò che arriva.

Resto diverso da 0: errore rilevato, senza sapere dove.
Resto 0: la parola è ritenuta corretta. Alcune configurazioni di errori danno però resto 0 e sfuggono: per questo $G(x)$ non si sceglie a caso.

Esempio di calcolo

Si proteggono i bit $1100$ , cioè $P(x)=x^3+x^2$ , con generatore $G(x)=x^3+x+1$ , cioè $1011$ , e $z=3$ . Si aggiungono tre zeri: $x^3P(x)=x^6+x^5$ , cioè $1100000$ . Si procede da sinistra: se la cifra di testa è 1 si sottrae $1011$ con uno XOR, se è 0 non si sottrae niente; poi si abbassa la cifra successiva. Quando non restano cifre da abbassare, gli ultimi tre bit sono il resto:

\begin{array}{ccccccc} 1&1&0&0&0&0&0\\ 1&0&1&1&&&\\ \hline &1&1&1&0&&\\ &1&0&1&1&&\\ \hline &&1&0&1&0&\\ &&1&0&1&1&\\ \hline &&&0&0&1&0 \end{array}

Il resto è $010$ , cioè $R(x)=x$ , e il quoziente è $x^3+x^2+x$ . La parola trasmessa è $T(x)=x^6+x^5+x$ , cioè $1100010$ : gli ultimi tre zeri sono sostituiti dal resto. Si verifica che $T(x)$ è un multiplo di $G(x)$ :

(x^3+x+1)(x^3+x^2+x)=x^6+x^5+x

Chi riceve $1100010$ e divide per $1011$ ottiene resto $000$ .

La divisione sui bit usa solo XOR e scorrimenti di una posizione. Per questo una macchina la esegue in fretta, con un registro a scorrimento (shift register).

Il grado $z$ decide l'overhead: $z$ bit. Per esempio $G(x)=x^{16}+x^{12}+x^5+1$ ha grado 16 e dà 16 bit. Generatori standard di grado 16 e 32 definiscono CRC16 e CRC32. La loro forma è scelta per rilevare errori di tipo particolare.

Ritardo con un'interfaccia più lenta

Si riprende il ritardo di trasferimento di un messaggio diviso in pacchetti.

Il messaggio è di $X$ bit, in $n$ pacchetti; ciascuno porta $L=X/n$ bit di testo e $H$ bit di intestazione.
Le interfacce attraversate sono $N$ ; la propagazione su ognuna dura $d_{\text{prop}}$ .
$D_{\text{MES}}$ è il ritardo del messaggio, dal primo bit emesso all'ultimo ricevuto.

La rete è scarica e l'elaborazione nei nodi è nulla. Un nodo ritrasmette un pacchetto quando l'ha ricevuto per intero. Con tutte le interfacce a capacità $C$ , il primo pacchetto le attraversa tutte e ognuno degli altri $n-1$ aggiunge un solo intervallo, perché viaggia insieme al precedente su un'altra interfaccia (effetto pipeline):

D_{\text{MES}}=N\,d_{\text{prop}}+(N+n-1)\frac{H+L}{C}

Ora un'interfaccia ha capacità $C/2$ e le altre $C$ . Con quattro nodi intermedi le interfacce sono $N=5$ .

Cinque interfacce, una più lenta

AN1N2N3N4B

C

C

C /2

C

C

Il percorso ha una sola interfaccia a

C /2

: è il collo di bottiglia, che limita il trasferimento dell'intero percorso.

Su un'interfaccia a capacità $C$ un pacchetto impiega $(H+L)/C$ , su quella lenta $2(H+L)/C$ . L'interfaccia lenta trasmette i pacchetti uno dopo l'altro, senza pause, perché ogni pacchetto è già pronto quando l'interfaccia si libera: occupa $n$ volte il tempo di un pacchetto. Su ognuna delle altre $N-1$ interfacce conta un solo pacchetto, perché gli altri vi passano mentre l'interfaccia lenta è occupata:

\begin{aligned} D_{\text{MES}}&=N\,d_{\text{prop}}+(N-1)\frac{H+L}{C}\\ &\quad+n\,\frac{H+L}{C/2} \end{aligned}

Dove sta l'interfaccia lenta non conta. Il primo pacchetto la raggiunge dopo aver attraversato quelle che la precedono, e l'ultimo attraversa quelle che la seguono, sempre una per volta. Nel diagramma le interfacce sono numerate da A verso B, la propagazione è trascurata e il tempo è in unità $(H+L)/C$ : un pacchetto occupa 1 sulle interfacce a capacità $C$ e 2 su quella lenta.

Tre pacchetti, un'interfaccia lenta

tempoAN1N2N3N4B

D_{MES}

Interfaccia lenta3

L'interfaccia lenta resta occupata dai tre pacchetti di seguito. Spostandola,

D_{MES}

resta di 10 unità.

Con $N=5$ , $n=3$ e $L=X/3$ la trasmissione occupa $4+3\cdot 2=10$ unità:

D_{\text{MES}}=5\,d_{\text{prop}}+10\,\frac{H+X/3}{C}

Con tutte le interfacce a $C$ sarebbero $N+n-1=7$ unità. L'interfaccia lenta aggiunge un'unità per ogni pacchetto, cioè tre.

La regola vale in generale: si contano tutti gli $n$ pacchetti sull'interfaccia più lenta e un solo pacchetto su ciascuna delle altre.

Collo di bottiglia e throughput

L'interfaccia più lenta è il collo di bottiglia. Il throughput è il bit rate da un estremo all'altro della rete ed è condizionato dal collegamento più lento. Si può contare anche in pacchetti al secondo: gli $n$ pacchetti arrivano in $D_{\text{MES}}$ , quindi

\text{throughput}=\frac{n}{D_{\text{MES}}}

Nell'esempio sono 3 pacchetti in $D_{\text{MES}}$ . Il denominatore dipende dal collo di bottiglia: se l'interfaccia lenta rallenta, $D_{\text{MES}}$ cresce e il throughput cala; se accelera, il throughput cresce.

Formulario

Internet checksum, modulo $2^{16}-1$

\begin{aligned} S&=\sum_{i=0}^{m-1}b_i\\ b_m&\equiv-S \end{aligned}

Controllo: somma di tutte le parole

\sum_{i=0}^{m}b_i\equiv0

Divisione CRC

x^zP(x)=Q(x)G(x)+R(x)

Parola di codice

T(x)=x^zP(x)+R(x)

Interfacce tutte a $C$

\begin{aligned} D_{\text{MES}}&=N\,d_{\text{prop}}\\ &\quad+(N+n-1)\frac{H+L}{C} \end{aligned}

Un'interfaccia a $C/2$

\begin{aligned} D_{\text{MES}}&=N\,d_{\text{prop}}\\ &\quad+(N-1)\frac{H+L}{C}\\ &\quad+n\,\frac{H+L}{C/2} \end{aligned}

Throughput in pacchetti al secondo

\frac{n}{D_{\text{MES}}}