Strato di collegamento: framing e controllo degli errori

Lo strato di collegamento

Lo strato di collegamento (data link, strato 2) porta i pacchetti lungo un solo collegamento, fra due nodi adiacenti. I nodi sono host e router; il collegamento è cablato o wireless, punto a punto o condiviso. Un pacchetto attraversa più collegamenti e su ciascuno può essere gestito da un protocollo diverso: Ethernet sul primo, un protocollo di rete geografica nel tratto intermedio, PPP sull'ultimo. Non tutti i dispositivi hanno lo strato 2: un amplificatore di segnale opera solo a livello fisico.

AR1R2BEthernetWANPPP

L'unità di dati dello strato 2 è il frame. I servizi che lo strato può offrire sono:

• Framing: incapsula il pacchetto in un frame e ne delimita inizio e fine.
• Accesso al mezzo: su un collegamento condiviso, come il Wi-Fi o la rete cellulare, il sottostrato MAC (Medium Access Control) regola chi trasmette.
• Rivelazione e correzione degli errori: il trasmettitore aggiunge bit di controllo dell'errore al frame e il ricevente li usa per rivelare gli errori ed eventualmente correggerli.
• Controllo di flusso: regola la velocità di emissione, perché il ricevente riesca a elaborare i frame.
• Consegna affidabile: ritrasmette i frame errati. Serve dove gli errori sono frequenti, come nel wireless, e può essere svolta anche dallo strato di trasporto.
• Half duplex o full duplex: in half duplex si trasmette e si riceve alternandosi, in full duplex contemporaneamente.

Ogni protocollo ne offre solo alcuni: Ethernet, per esempio, non offre la consegna affidabile.

Lo strato 2 è realizzato nella scheda di rete (NIC, Network Interface Card), insieme allo strato fisico: una combinazione di hardware, software e firmware.

Il frame

Il framing forma la PDU dello strato 2, il frame, incapsulando la PDU dello strato superiore, il pacchetto, che diventa la SDU del frame. Le entità di strato 2 dei due nodi comunicano logicamente; fisicamente il frame passa allo strato 1, che lo trasmette sul mezzo come sequenza di bit.

Lo strato 2 aggiunge al pacchetto le proprie informazioni di controllo, la PCI (Protocol Control Information):

$$\text{Frame}=\text{PCI}_{\text{i}}+\text{SDU}+\text{PCI}_{\text{f}}$$

La PCI può stare all'inizio (intestazione, header), alla fine (suffisso, trailer) o in entrambe le posizioni, secondo il protocollo.

Se i frame hanno lunghezza fissa, concordata in anticipo, il ricevente sa dove finiscono. Se la lunghezza è variabile, deve poterne riconoscere l'inizio e la fine: è la funzione di delimitazione.

Delimitare con un flag

Si pone all'inizio e alla fine di ogni frame una sequenza fissa di bit, il flag. Una configurazione possibile è il byte

$$\text{FLAG}=01111110$$

Un flag apre il frame, il successivo lo chiude. Resta un problema: la SDU è una sequenza qualsiasi di bit e può contenere proprio il byte del flag, che il ricevente scambierebbe per un delimitatore. Lo strato 2 deve quindi modificare i dati con una di due tecniche, alternative: ogni protocollo ne adotta una sola.

Bit stuffing

Nei dati, dopo ogni sequenza di cinque 1 consecutivi, il trasmettitore inserisce uno 0, qualunque sia il bit successivo:

$$11111\longrightarrow 111110$$

Così nei dati non compaiono mai sei 1 di seguito, e il flag resta riconoscibile. Il ricevente conta gli 1 consecutivi (destuffing). Dopo cinque 1 guarda il bit seguente: se è un 1 la sequenza fa parte di un flag, se è uno 0 è un bit inserito e lo elimina.

Esempio, con i quattro 0 inseriti sottolineati. Cinque 1 seguiti da uno 0 ricevono comunque lo 0; in undici 1 di fila gli 0 inseriti sono due, dopo il quinto 1 e dopo il decimo.

$$\begin{aligned} \text{originale}&:\ \mathtt{1011111111111011\ 0111110011111100}\\ \text{trasmessa}&:\ \mathtt{1011111\underline{0}11111\underline{0}1011\ 011111\underline{0}0011111\underline{0}100} \end{aligned}$$

Il ricevente elimina i quattro 0 e ricostruisce la sequenza originale.

Byte stuffing

Si lavora un byte alla volta, con un secondo byte speciale, il control escape, usato dal protocollo PPP:

$$\text{ESC}=01111101$$

Il trasmettitore legge la SDU byte per byte. Se trova un byte uguale a FLAG o a ESC, gli antepone un ESC:

$$\begin{gathered} \text{FLAG}\longrightarrow\text{ESC}\,\text{FLAG}\\ \text{ESC}\longrightarrow\text{ESC}\,\text{ESC} \end{gathered}$$

Solo dopo aggiunge il flag iniziale e quello finale. Il ricevente applica tre regole:

• due ESC consecutivi: ne elimina uno;
• un ESC seguito da un FLAG: elimina l'ESC e tiene il FLAG come dato;
• un FLAG senza ESC davanti: è un delimitatore.

Confronto

Esercizio: una SDU di 6 byte, cioè 48 bit, con due byte speciali, uguali a FLAG o a ESC.

• Byte stuffing: due ESC davanti ai byte speciali e due flag. Il frame ha 10 byte, cioè 80 bit; le aggiunte sono 4 byte su 6, il 66,7%.
• Bit stuffing: ogni byte speciale contiene cinque 1 consecutivi e riceve uno 0; si aggiungono poi i due flag. Il frame ha $48+2+16=66$ bit; le aggiunte sono 18 bit su 48, il 37,5%.

Il bit stuffing aggiunge meno bit: uno 0 costa 1 bit, un ESC ne costa 8. Il byte stuffing richiede meno elaborazione: 6 letture, una per byte, contro 48 bit. Quale conviene dipende da che cosa si privilegia.

Gli errori sui bit

Un errore è un bit flip: un bit trasmesso come 0 viene ricevuto come 1, o viceversa, perché il segnale è alterato da un'interferenza o attenuato lungo il mezzo. Nella fibra ottica i flip sono rari, nel wireless più frequenti.

Due meccanismi per trattarli:

• FEC (Forward Error Correction): si aggiunge in anticipo ridondanza ai dati, così che il ricevente riveli l'errore e, se il codice è abbastanza potente, lo corregga senza chiedere altro.
• ARQ (Automatic Repeat Request), o error detection and retransmission: il ricevente rivela l'errore e il frame viene ritrasmesso.

Nella FEC un codificatore trasforma l'informazione d'utente in una parola di codice (codeword), che viene trasmessa al posto dell'originale. Il ricevente controlla se il blocco ricevuto è una parola di codice: se non lo è, lo considera in errore. Il prezzo è la ridondanza (overhead), cioè i bit di controllo aggiunti al blocco di dati d'utente. Il canale può anche trasformare la parola di codice trasmessa in un'altra parola di codice: allora l'errore non è rivelato.

informazione d'utenteCodificatorecodewordCanaleblocco ricevutoControllo della codewordvalido o in errore

Controllo di parità singola

È il codice più semplice. Ai $k$ bit informativi $b_1,\dots,b_k$ si aggiunge un solo bit, in fondo, scelto in modo che il numero totale di 1 sia pari:

$$b_{k+1}=\Bigl(\sum_{i=1}^{k}b_i\Bigr)\bmod 2$$

La codeword è $(b_1,\dots,b_k,b_{k+1})$. Il ricevente conta gli 1 della codeword, non dei dati: se sono pari accetta, se sono dispari segnala un errore.

• Un errore che cambia un numero dispari di bit è sempre rivelato.
• Un errore che cambia un numero pari di bit lascia pari il numero di 1 e non è rivelato.
• Non si sa quale bit sia errato: l'errore non si può correggere. Può colpire anche il bit di parità.

Esempio con $k=7$, dati $(0,1,0,1,1,0,0)$. Ci sono tre 1, quindi $b_8=1$ e la codeword è $(0,1,0,1,1,0,0,1)$, con quattro 1.

• Errore sul bit 3: $(0,1,1,1,1,0,0,1)$ ha cinque 1, dispari. Errore rivelato.
• Errore sui bit 3 e 5: $(0,1,1,1,0,0,0,1)$ ha quattro 1, pari. Errore non rivelato, anche se due bit sono sbagliati.