Sistemi e Tecnologie della
Comunicazione
Lezione 10: data link layer: definizione, framing, codici di correzione degli errori
1
Il data link layer




Il Data Link Layer (anche livello di collegamento dati, o piu’
semplicemente: livello 2) ha la funzione principale di fornire allo
strato di rete servizi per il recapito di dati al nodo direttamente
adiacente sulla rete
Il compito del data link layer e’ quindi quello di organizzare il
trasferimento dei dati tra due apparati adiacenti, e di fornire una
interfaccia definita per consentire allo strato di rete di accedere ai
servizi offerti
Apparati adiacenti significa connessi da un “tubo” che trasmette i bit
da una parte e li riceve dall’altra, nell’ordine di trasmissione
Il data link layer utilizzera’ i servizi dello strato fisico per il recapito
dei dati al suo processo paritario sul calcolatore ricevente, ma
logicamente la comunicazione avverra’ direttamente con il processo
di data link layer remoto

come sia fatto il “tubo” non e’ argomento che riguardi il data link layer,
ma lo strato fisico: non importa se ci sia un cavo, una fibra, una
sequenza di mezzi differenti con interposti ripetitori, convertitori
elettrico/ottici, modem, multiplexer, antenne o altro
2
Il data link layer (cont.)


Per realizzare le sue funzioni il data link layer riceve i dati dallo strato
di rete (pacchetti), li organizza in trame (frame) eventualmente
spezzando in piu’ frame il blocco di dati ricevuto dal livello 3,
aggiunge ad ogni frame una intestazione ed una coda (header e
trailer), e passa il tutto allo strato fisico per la trasmissione
In ricezione il data link layer riceve i dati dallo strato fisico, effettua i
controlli necessari, elimina header e trailer, ricombina i frame e passa
i dati ricevuti allo strato di rete
3
Servizi del DLL

Lo strato di data link fornisce allo strato di rete i servizi




trasmissione dati senza riscontro e senza connessione
trasmissione dati affidabile senza connessione
trasmissione affidabile con connessione
La classe di servizio non affidabile senza connessione e’
adatta su linee di elevata qualita’




il controllo sugli errori e la ritrasmissione di frame errati comporta
una inefficienza in termini di numero di bit trasmessi rispetto ai
dati, con riduzione del tasso utile ed aumento della probabilita’ di
errore
il controllo puo’ essere demandato ai livelli superiori a vantaggio
della efficienza del livello di data link
generalmente questi servizi sono utilizzati su rete locale
come detto piu’ volte, servizi non affidabili sono utilizzati anche
per il traffico voce e video
4
Servizi del DLL (cont.)

La classe di servizio affidabile con connessione e’ adatta
su linee piu’ frequentemente soggette ad errori




demandare il controllo e la ritrasmissione ai livelli superiori (che
generalmente trasmettono pacchetti costituiti da piu’ frame) in
caso di elevata probabilita’ di errore potrebbe causare la
ritrasmissione di molti pacchetti, mentre al livello due puo’ essere
sufficiente la ritrasmissione del singolo frame
tipicamente utilizzata su linee a grande distanza (connessioni
WAN), anche se la fibra ottica riduce notevolmente questo
problema
Il data link layer deve quindi poter offrire le diverse classi
di servizio, per soddisfare le diverse esigenze
I servizi vengono implementati attraverso una serie di
regole di comunicazione (protocolli) tra i livelli di data link
dei calcolatori adiacenti
5
Problematiche del livello 2

Per poter svolgere le sue funzioni il data link layer
dovra’ curare i seguenti aspetti:




framing: l’organizzazione del flusso di bit in frame, con
controllo per la sincronizzazione, inserimento e
rimozione di header e trailer
frammentazione e riordinamento dei frame in ricezione
gestione degli errori: devono essere utilizzati codici di
correzione degli errori o codici di identificazione degli
errori e va gestita la ritrasmissione dei frame errati
controllo di flusso: si deve impedire ad un
trasmettitore veloce di sovraccaricare un ricevitore
lento
6
Framing

Il DDL organizza le trasmissioni di dati in blocchi (frame)
per realizzare un controllo sugli errori trasmissivi





per trasportare i bit il Data Link Layer utilizza i servizi dello strato
fisico
lo strato fisico non puo’ garantire il trasferimento privo di errori,
che dovranno essere gestiti dal DLL
per fare cio’ il DLL organizza i bit in frame, ed effettua i controlli
per ogni frame
La struttura del frame deve consentire al ricevente di
identificarne i limiti (sincronizzazione), quindi si devono
adottare regole per delimitarlo
Esistono diverse tecniche:



conteggio dei caratteri
byte di flag e byte stuffing
bit(s) di flag e bit stuffing
7
Framing a conteggio di caratteri



Il conteggio dei caratteri prevede l’utilizzo di un frame costituito da
caratteri, ed un campo iniziale per specificare il numero dei caratteri
di cui e’ costituito il frame
In ricezione si legge nel campo iniziale la lunghezza del frame, e si
identifica cosi’ il primo carattere appartenente al frame successivo
Questo algoritmo e’ molto debole, in quanto in caso di errore non si
riesce piu’ a riagganciare la sincronizzazione
8
Frame con byte di flag





Il problema della sincronizzazione puo’ essere risolto utilizzando un
carattere speciale per indicare l’inizio (e la fine) del frame (flag)
In questo modo la perdita di sincronia si recupera semplicemente
aspettando il carattere di inizio del frame
Si presenta il problema di gestire l’eventualita’ che il carattere di flag
compaia nel campo dei dati: la soluzione e’ quella di utilizzare un
carattere di escape da inserire prima del byte di flag nel campo dati,
in modo da indicare al ricevente che quel carattere fa parte dei dati e
non della struttura di controllo
In ricezione il carattere di escape verra’ rimosso dal campo dati
Va pero’ considerato che anche il carattere di escape puo’ capitare
casualmente nel campo dati: per evitare che venga erroneamente
rimosso un carattere di escape facente parte dei dati, anche il
carattere di escape verra’ preceduto dal carattere di escape stesso, in
modo da identificarlo in ricezione come parte dei dati allo stesso
modo dell’eventuale carattere di flag
9
Frame con byte di flag (cont.)

In molti protocolli si utilizza la coppia di caratteri DLE-STX (Data Link
Escape – Start of Text) per delimitare l’inizio del frame, e la coppia
DLE-ETX (End of Text) per delimitarne la fine; ogni volta che il
carattere DLE compare nel campo dati viene raddoppiato.
10
Framing con bit stuffing

L’utilizzo di protocolli basati sulla lunghezza del carattere a livello di
data link non sempre e’ auspicabile






non tutti i codici sono concordi sulla lunghezza del carattere (7/8 bit
ASCII, 16 bit UNICODE, …)
non sempre e’ adatto un frame costituito da un numero intero di caratteri
(vedi ad esempio SONET)
Per ovviare a questo si utilizza una tecnica che prevede per indicare
l’inizio e la fine del frame una sequenza predefinita di bit (solitamente
01111110)
Ogni qualvolta la sequenza di flag compare nel campo dati, e’
sufficiente inserire in modo opportuno un bit che ne altera la
sequenza; per la sequenza vista, si inserisce un bit 0 dopo cinque bit
1 consecutivi
In ricezione ogni volta che si riceve una sequenza di 5 bit 1 seguiti da
un bit 0, lo zero viene eliminato
Anche in questo caso l’operazione di stuffing rende inequivocabile la
sequenza di inizio e fine del frame, e quindi rende possibile la
risincronizzazione
11
Esempio di bit stuffing
12
Tecniche multiple

Va infine considerato che molti protocolli
aumentano le informazioni di framing utilizzando
piu’ di una tecnica assieme



tipicamente si abbina il conteggio dei caratteri ad una
delle due tecniche di byte o bit stuffing
In ricezione si semplifica il controllo in quanto il
delimitatore di fine si cerca solo nella posizione
indicata come fine del frame dal contatore
Va osservato come la ridondanza non permetta
comunque di rinunciare allo stuffing, che resta
indispensabile per la risincronizzazione del frame
13
Frammentazione





Spesso lo strato di rete utilizza pacchetti di dimensione
inadatta allo strato di data link
In questa condizione, il livello 2 spezza il pacchetto in piu’
frammenti, e tratta ciascun frammento
indipendentemente (applica a ciascuno header, trailer e
limiti del frame)
Per poter consegnare in ricezione allo strato di rete il
pacchetto originario il livello 2 dovra’ occuparsi di
ricombinare i frammenti nell’ordine corretto
Sara’ quindi necessario numerare i frame in un apposito
campo dell’header per poterli riordinare
Vedremo piu’ approfonditamente come questo venga
fatto nella analisi del controllo di flusso e di errore
14
Controllo degli errori


Come gia’ visto, lo strato fisico non puo’ garantire una
consegna di bit senza errori
Lo strato di data link deve quindi operare algoritmi per
assicurarsi che i frame inviati vengano ricevuti






tutti
senza errori
senza duplicati
nell’ordine corretto
Solitamente si utilizza una forma di riscontro che il
ricevente manda al mittente per confermare la corretta
ricezione dei frame
Questo viene fatto tramite l’invio di pacchetti appositi di
acknowledge positivo (ACK) o negativo (NACK)
15
Problematiche del controllo degli errori




Il controllo deve prevedere un meccanismo per
correggere o identificare gli errori di trasmissione
La perdita completa di un frame, o la perdita di un ACK,
lascia il trasmittente in attesa dell’ACK, quindi si dovranno
inserire timer per la ritrasmissione automatica di frame
La perdita di un ACK comporta la ritrasmissione di un
frame gia’ ricevuto correttamente, quindi si deve
identificare questa eventualita’ e scartare il duplicato,
tramite ad esempio la numerazione dei frame
I meccanismi adottati per questa funzione sono differenti
e dipendono dal protocollo utilizzato; ne vedremo alcuni
tra i piu’ comuni
16
Controllo di flusso





Puo’ capitare che una sorgente sia in grado di trasmettere
ad un tasso piu’ alto della capacita’ di ricevere a
destinazione
Senza controllo, questo implica che la destinazione
inizierebbe a scartare frame trasmessi correttamente per
mancanza di risorse (tempo di processamento, buffer)
Il protocollo deve poter gestire questa situazione e
prevedere meccanismi per rallentare la trasmissione
Tipicamente il protocollo prevedera’ dei frame di controllo
con cui il ricevente puo’ inibire e riabilitare la trasmissione
di frame, cioe’ il protocollo stabilisce quando il
trasmittente puo’ inviare frame
Vedremo diverse tecniche, che si differenziano per
complessita’ ed efficienza di utilizzo della linea
17
Controllare gli errori?

Perche’ occuparsi degli errori trasmissivi? Vediamo un esempio pratico:


Una linea ISDN a 64 Kbps viene ritenuta idonea a fornire servizio se il numero di
frame errati non riconosciuti e’ inferiore ad uno al giorno
Ipotizzando di utilizzare frame di 1000 bit, e di trasmettere a piena banda, si ha:
86400 s/giorno * 64000 bps
 5.53  106 frame/gior no
1000 bit/frame
1
PFE 
 1.8  10  7 max prob. di frame errato
6
5.53  10

Ora, ipotizzando un BER di una parte su milione, si ha:
PBE  10 6  PB  1  10 6
PF   PB 
1000

 0.999  PFE  1  PF   0.001
cioe’ senza controllo di errori il tasso di frame errati e’ 5000 volte superiore a
quello richiesto, quindi e’ necessario operare per identificare e correggere gli errori
trasmissivi
18
Errori di trasmissione

Esistono due strategie per gestire errori di trasmissione
del livello fisico:

utilizzare codifiche a correzione di errore (forward error
correction): la codifica utilizzata e’ in grado di identificare i bit
errati nel frame e di correggerli in ricezione


utilizzata tipicamente su linee ad alto tasso di errore, per le quali
l’overhead della codifica e’ conveniente rispetto alla ritrasmissione del
frame che ha elevate probabilita’ di essere ancora errato
utilizzare codifiche ad identificazione di errore: la codifica e’ in
grado di capire se c’e’ stato un errore durante la trasmissione; in
conseguenza dell’errore il protocollo chiedera’ la ritrasmissione del
frame, o non fara’ nulla, aspettando lo scadere del timer in
trasmissione

utilizzata tipicamente su linee a basso tasso di errore, nelle quali la
ritrasmissione del frame errato risulta piu’ conveniente dell’overhead
di una codifica a correzione di errore
19
Codeword e distanza di Hamming



Un messaggio da inviare e’ costituito da m bit di dati, a cui si
aggiungono r bit di ridondanza finalizzata alla rilevazione o correzione
di errore
La quantita’ di bit trasmessi e’ costituita da n = m+r bit. Chiamiamo
codeword l’insieme di n bit trasmessi
Date due codeword, si definisce distanza di Hamming tra le codeword
il numero di bit corrispondenti che differiscono, cioe’ il numero di “1”
nel risultato dell’OR esclusivo tra le codeword; ad esempio le due
codeword
10001001
10110001
00111000
hanno distanza di Hamming pari a 3
20
Correzione e rivelazione di errori basati sulla
distanza di Hamming




L’idea e’ che per trasformare una codeword in
un’altra codeword a distanza d, sono necessari d
errori sul bit
Normalmente i codici ammettono tutte le possibili
2 m combinazioni di bit sui dati, ma non tutte le 2 r
combinazioni sui bit di controllo
Dato l’algoritmo che determina gli r bit di
controllo associati alle possibili combinazioni degli
m bit di dati, esisteranno codeword valide e
codeword invalide
La distanza minima tra le codeword valide e’
detta distanza di Hamming della codifica
21
Correzione e rivelazione di errori basati
sulla distanza di Hamming (cont.)



Ogni errore di bit trasformera’ la codeword trasmessa (valida) in una
codeword differente
Per poter rivelare d errori, il codice dovra’ avere una distanza di
Hamming pari a d+1 (in questo modo d errori non potranno mai
trasformare una codeword valida in un’ altra codeword valida)
L’esempio piu’ semplice e’ il bit di parita’: questo e’ un codice a
distanza due, che permette di identificare l’errore di singolo bit




dato un set di m bit, la codeword e’ costituita da m+1 bit dove l’ultimo
bit e’ determinato dalla parita’
la codeword valida piu’ vicina si trova cambiando un bit dei dati, ma
questo obbliga a cambiare anche il bit di parita’, quindi la distanza del
codice e’ 2
un errore di singolo bit provoca sempre la trasformazione di una
codeword valida in una non valida (vìola la parita’)
Naturalmente questi codici in generale non sono in grado di rivelare
errori di d+1 bit (o superiori) in trasmissione
22
Correzione e rivelazione di errori basati
sulla distanza di Hamming (cont.)








La stessa tecnica viene utilizzata anche per la correzione degli errori
Per poter identificare e correggere d errori, serve una codifica a distanza
2d+1
In questo modo d errori trasformeranno una codeword valida in una
codeword invalida, ma tale che la codeword valida trasmessa sia quella a
distanza minima, quindi identificabile
Ad esempio, supponiamo che le codeword valide siano 0000000000
0000011111 1111100000 e 1111111111.
La distanza del codice e’ 5
Supponiamo di trasmettere 0000000000, e di avere 2 errori in trasmissione,
ad esempio riceviamo 1100000000.
Il ricevente sa che la codeword ricevuta e’ invalida, ed identifica la codeword
trasmessa come quella piu’ vicina alla codeword ricevuta, cioe’ ricostruisce il
dato corretto
In caso di errori di piu’ bit, la codifica commettera’ un errore di
interpretazione (proseguendo nell’esempio, se in trasmissione e’ stata
trasmessa la codeword 1111100000 e si sono verificati 3 bit di errore,
ricevendo 1111101011, il ricevente correggera’ il dato ricevuto in
1111111111) commettendo un errore di identificazione
23
Metodo di Hamming per un codice di
correzione di un bit



Per realizzare la correzione di 1 bit di errore dobbiamo realizzare un
codice a distanza 3. Dato m, quanto deve essere r?
Si puo’ vedere la cosa nel seguente modo: per ciascun insieme di dati
dovremo avere una codeword valida ed n codeword invalide,
ottenute cambiando ad uno ad uno un bit della codeword valida
Si ha pertanto:
 n  1 2 m
codeword necessarie
2 n combinazio ni possibili
 n  1  2 m  2 n  2  mr 
 m  r  1 2 m  2 m 2 r  r  2 r  m  1

Questa relazione definisce il limite inferiore di r
Ad esempio, per trasmettere la codifica ASCII a 7 bit dovremo
utilizzare 4 bit di ridondanza
24
Metodo di Hamming per un codice di
correzione di un bit (cont.)




Hamming ha ideato un modo efficiente per realizzare questa codifica
Numeriamo i bit della codifica partendo da sinistra, iniziando da 1
I bit di ridondanza stanno nelle posizioni 1, 2, 4, … (quelle che
rappresentano le potenze di 2)
I bit dei dati occupano le altre posizioni; ciascuna posizione puo’
essere espressa come somma di potenze di due:



7 = 1+2+4
10 = 2+8
Ciascun bit di ridondanza viene valutato per definire la parita’ (pari o
dispari) dell’insieme dei bit la cui posizione e’ tale da avere il numero
di posizione di quel bit di ridondanza nella sua scomposizione



il bit 1 definira’ la parita’ dei bit 1, 3, 5, 7, ..
il bit 2 definira’ la parita’ dei bit 2, 3, 6, 7, 10, 11, 14, 15, …
il bit 4 definira’ la parita’ dei bit 4, 5, 6, 7, 12, 13, 14, 15, …
25
Metodo di Hamming per un codice di
correzione di un bit (cont.)



Ogni bit di dati contribuisce alla parita’ dei bit di controllo tali che la somma
delle posizioni di questi bit di controllo eguaglia la posizione del bit in
questione, in quanto questi sono i bit le cui posizioni fanno parte della
scomposizione in potenze di due della posizione del bit stesso
In ricezione si calcolano i bit di parita’ sulla base dei dati ricevuti, e si
confrontano con i valori ricevuti; sommando le posizioni dei bit di controllo
risultati errati, si ottiene la posizione del bit errato (si otterra’ zero se non c’e’
stato errore)
Ad esempio, supponiamo di trasmettere il carattere H, la cui codifica ASCII e’
1001000. La codifica di Hamming (pari) per H e’ 00110010000 (in azzurro i
bit di ridondanza)
Se in ricezione otteniamo 00110110000 (con un errore di trasmissione, nel
bit in posizione 6) e proviamo a ricalcolare la parita’, otteniamo:
bit 1: 0+1+0+1+0+0 = 0 giusto (bit in pos. 1, 3, 5, 7, 9, 11)

bit 2: 0+1+1+1+0+0 = 1 errato (bit in pos. 2, 3, 6, 7, 10, 11)

bit 4: 1+0+1+1 = 1 errato (bit in pos. 4, 5, 6, 7)

bit 8: 0+0+0+0 = 0 giusto (bit in pos. 8, 9, 10, 11)
quindi il bit errato sara’ in posizione 2+4 = 6


Questo vale anche per identificare un eventuale errore sul bit di controllo,
che risultera’ essere l’unico errato
26
Tecnica per correzione di errori a grappolo







Spesso gli errori su una linea di trasmissione dati si presentano a
grappoli (burst)
Ad esempio, un evento di rumore impulsivo provoca l’errore di un
certo numero di bit consecutivi
Benche’ la codifica Hamming permetta di correggere solo errori
singoli, si usa un trucco per identificare e correggere gli errori a
grappolo fino ad una lunghezza massima
Una sequenza di K codeword consecutive viene rappresentata in
righe, ma i bit vengono trasmessi per colonna
Un evento di errore burst di lunghezza non superiore a K provochera’
la trasmissione errata di non piu’ di K bit consecutivi (nell’ordine di
trasmissione)
Poiche’ i bit sono trasmessi in colonne, risulteranno errati non piu’ di
un bit per ciascuna codeword
In questa condizione gli errori burst di lunghezza non maggiore di K
potranno essere corretti in ricezione
27
Esempio di codifica di Hamming
28