CRC e trasferimento affidabile

I servizi del livello di collegamento

Il livello di collegamento offre al livello di rete quattro servizi. Il framing trasforma il datagramma, la SDU, nel frame, la PDU del livello, con un'intestazione e, in Ethernet, un trailer. Il duplexing usa il collegamento in una direzione (half-duplex) o in due (full-duplex). Gli errori si rivelano o correggono con parità, codici di Hamming, checksum e CRC, e si recuperano con la consegna affidabile.

Stringhe e polinomi

Il CRC (Cyclic Redundancy Check, codice a ridondanza ciclica) è il codice usato per esempio in Internet. Tratta una stringa binaria come un polinomio e calcola in algebra modulo 2.

Modulo $m$ significa prendere il resto della divisione per $m$: $12\bmod5=2$. Con $m=2$ i coefficienti valgono 0 o 1, e somma e sottrazione coincidono: sono lo XOR bit a bit.

Una stringa di $k$ bit corrisponde a un polinomio $P(x)$ di grado al più $k-1$, i cui coefficienti, dal grado più alto a $x^0$, sono i bit. Per esempio $1010$ è $x^3+x$.

Polinomio generatore e parola di codice

Trasmettitore e ricevitore conoscono un polinomio generatore $G(x)$ di grado $z$, cioè una stringa di $z+1$ bit. Il trasmettitore divide $x^zP(x)$ per $G(x)$ e ottiene un quoziente $Q(x)$ e un resto $R(x)$ di grado minore di $z$:

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

La parola di codice è $T(x)=x^zP(x)+R(x)$. Modulo 2 somma e sottrazione sono uguali, quindi sommare $R(x)$ due volte lo cancella:

$$\begin{aligned} T(x)&=x^zP(x)+R(x)\\ &=Q(x)G(x) \end{aligned}$$

Ogni parola di codice è divisibile per $G(x)$. Il ricevitore divide per $G(x)$ ciò che riceve: con resto diverso da 0 c'è un errore; con resto 0 la stringa è una parola di codice, ma non è detto che sia quella trasmessa, perché un errore potrebbe averla trasformata in un'altra.

Moltiplicare per $x^z$ aggiunge $z$ zeri in coda al messaggio. Il resto, di grado al più $z-1$, si scrive su $z$ bit e occupa il posto di quegli zeri: la parola trasmessa è il messaggio seguito dal resto. La divisione si esegue durante la trasmissione con un circuito efficiente, in tempi dell'ordine dei nanosecondi.

Esempi di divisione e codifica

Con $G(x)=x^3+x+1$, cioè $1011$ e $z=3$, si divide $x^6+x^5$. A ogni passo si sceglie la potenza di $x$ che porta $G(x)$ al grado del dividendo e si somma (XOR):

• $x^3G(x)=x^6+x^4+x^3$ dà $x^5+x^4+x^3$;
• $x^2G(x)=x^5+x^3+x^2$ dà $x^4+x^2$;
• $xG(x)=x^4+x^2+x$ dà $x$.

Il quoziente è $x^3+x^2+x$ e il resto è $x$: ci si ferma quando il grado scende sotto $z$.

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

Per il messaggio $1100$, cioè $P(x)=x^3+x^2$, con lo stesso generatore, si ha $x^3P(x)=x^6+x^5$ e il resto è $x$. Su tre bit è $010$, quindi la parola trasmessa è $1100010$, cioè $T(x)=x^6+x^5+x=(x^3+x^2+x)(x^3+x+1)$.

Il trasferimento dati affidabile

Dopo aver rivelato un errore si può scartare il frame, provare a correggerlo, con il rischio di correggere male, o recuperarlo con un trasferimento dati affidabile (RDT, reliable data transfer). Il collegamento può introdurre errori sui bit, perdite, duplicati e frame fuori sequenza: l'RDT consegna i dati senza errori, una sola volta e nell'ordine di invio.

Il recupero può essere end-to-end, fra i sistemi terminali, o hop-by-hop, su ogni collegamento. Il primo spetta al livello di trasporto: lo offre TCP, e per questo HTTP viaggia su TCP. Il secondo è un servizio del livello di collegamento.

Il recupero end-to-end serve comunque, perché chi progetta un'applicazione non conosce i collegamenti attraversati. Quello sul collegamento conviene dove gli errori sono frequenti, come sul primo tratto wireless: si corregge subito, mentre end-to-end passano decine di millisecondi. Ethernet non lo realizza, una cella 5G sì: ripeterlo a più livelli costa prestazioni.

Stop and wait

Lo stop and wait è il più semplice dei protocolli ARQ (Automatic Repeat Request). Il trasmettitore A invia un frame protetto da un codice di rivelazione e aspetta. Se B verifica che è una parola di codice lo accetta e invia un riscontro positivo, l'ACK: A può proseguire. Se il frame si perde B non risponde e A resterebbe bloccato, quindi A fa partire un timeout a ogni trasmissione, l'RTO (retransmission timeout): se scade senza ACK ritrasmette.

Se l'ACK si perde o arriva tardi, A ritrasmette un frame che B ha già accettato. Per riconoscerlo ogni frame ha un numero di sequenza: B scarta la copia, senza consegnarla al livello superiore, e invia di nuovo l'ACK, che sblocca A. Anche l'ACK è numerato, con il numero atteso, cioè quello del prossimo frame. C'è al più un frame «in volo», quindi bastano 0 e 1: se B riceve 0, 1 e di nuovo 0, sa che comincia un nuovo ciclo.

La macchina a stati descrive la logica con l'ultimo numero di sequenza e quello atteso, e parte da $(0,0)$. Senza errori percorre il ciclo $(0,0)\to(0,1)\to(1,1)\to(1,0)\to(0,0)$, un passo per ogni frame corretto con il numero atteso e uno per il suo ACK. Un frame errato, o con un altro numero, lascia lo stato com'è e B invia di nuovo l'ACK del numero atteso.

Un frame con un ritardo eccezionale può arrivare quando B attende di nuovo lo 0 e venire accettato come nuovo. Numeri di sequenza più ampi riducono il rischio, ma costano memoria e bit di intestazione, cioè overhead.

Perdite, duplicati e ritardi

Caso

Frame persoACK persoRitardo eccezionale

AB0ACK 11ACK 01ACK 0RTO

Efficienza dello stop and wait

L'efficienza $\eta$ è il rapporto fra il tempo utile e il tempo totale. Il tempo utile è quello in cui si trasmette il frame, $L/C$, con $L$ la lunghezza del frame in bit e $C$ la capacità in bit/s. Il tempo totale va dall'inizio della trasmissione alla ricezione dell'ACK: trasmissione, due propagazioni $T_P$ e trasmissione dell'ACK, di $L_H$ bit.

$$\eta=\frac{L/C}{L/C+2T_P+L_H/C}$$

Moltiplicando numeratore e denominatore per $C/L$:

$$\eta=\frac{1}{1+\dfrac{2CT_P}{L}+\dfrac{L_H}{L}}$$

L'ACK è breve rispetto ai dati, quindi $L_H/L$ si trascura. Con $\mathrm{RTT}=2T_P$, il tempo di andata e ritorno:

$$\eta\simeq\frac{1}{1+\dfrac{C\,\mathrm{RTT}}{L}}$$

Il prodotto $C\,\mathrm{RTT}$, in bit, è il prodotto banda-ritardo. Il collegamento è come un tubo: la capacità è la sezione, il ritardo la lunghezza, e il prodotto dice quanti bit ci entrano. Lo stop and wait ne manda un frame per volta: se il prodotto supera molto $L$, il tubo resta quasi vuoto.

Con $C=1$ Mbit/s, frame di 10 000 bit di cui 200 di intestazione, che non contano come utili, e ACK di 200 bit, un RTT di 1 ms, 10 ms, 100 ms e 1 s dà $C\,\mathrm{RTT}=10^3$, $10^4$, $10^5$ e $10^6$ bit e $\eta\simeq88\,\%$, $49\,\%$, $9\,\%$ e $1\,\%$. Con $C=1$ Gbit/s, come un accesso in fibra, il prodotto è mille volte più grande e $\eta$ vale 1 %, 0,1 %, 0,01 % e 0,001 %.

Protocolli con pipeline

Lo stop and wait si ferma dopo ogni frame, quindi il tempo utile è un solo tempo di trasmissione. Frame più lunghi non bastano: non li sceglie chi trasmette e sono più esposti agli errori. Si lasciano invece più frame in volo, non ancora riscontrati: sono i protocolli con pipeline: Go-Back-N, che invia $N$ frame prima di attendere, e Selective Repeat.

Il tempo utile diventa $N\,L/C$, quindi l'efficienza è $N$ volte quella dello stop and wait, ma non supera il 100 %:

$$\eta_{\text{pipe}}=\min\left(1,\ \frac{N}{1+C\,\mathrm{RTT}/L}\right)$$

Per arrivare al 100 % servono almeno

$$N_{\text{min}}=\left\lceil1+\frac{C\,\mathrm{RTT}}{L}\right\rceil$$

frame.

Efficienza di una pipeline

$N=1$$N_{\text{min}}$$N$

• ${\eta }_{\text{pipe}}$

$C\mathrm{RTT}/L$

4