Reti di Calcolatori
a.a. 2005/06
Lezione 6
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Fisico
Reti di Calcolatori
Andrea Frosini
2
Il livello data link - Generalità
Scopo: offrire una comunicazione affidabile ed efficiente tra due macchine adiacenti
Problemi: comportandosi come un “tubo digitale” (cioè i bit partono e arrivano nello
stesso ordine), si deve tener conto di:
- errori e disturbi occasionali
- il data rate finito del canale
- il ritardo nella propagazione
Compiti:
- Offrire servizi al livello network con un’interfaccia ben definita;
- Determinare come i bit del livello fisico sono raggruppati in frame (framing)
- Gestire gli errori di trasmissione
- Regolare il flusso della trasmissione fra sorgente e destinatario
Reti di Calcolatori
Andrea Frosini
3
Il livello data link - Servizi
Il livello Data Link offre come servizi il trasferimento dei dati dal livello Network della
macchina di origine al livello Network della macchina di destinazione
Il livello Data Link generalmente offre uno dei seguenti tipi di servizi:
• Servizio connectionless non affidabile
• Servizio connectionless affidabile
• Servizio connection-oriented affidabile
I servizi del livello Data Link devono essere accessibili tramite una interfaccia ben
definita ed ordinata
Il livello dialoga idealmente con l’entità di pari livello sulla macchina adiacente
utilizzando un determinato protocollo
Reti di Calcolatori
Andrea Frosini
4
Il servizio connectionless non affidabile
Caratteristiche:
• non si stabilisce alcuna connessione
• ogni frame è inviato indipendentemente dagli altri
• non vi è conferma di ricezione dei frame
• i frame persi non sono recuperati
Questo servizio può essere utilizzato per canali con tasso d’errore molto basso. In
pratica, il livello Data Link della maggior parte delle LAN adotta questo tipo di servizio
Reti di Calcolatori
Andrea Frosini
5
Il servizio connectionless affidabile
Caratteristiche:
• non si stabilisce alcuna connessione
• ogni frame è inviato indipendentemente dagli altri
• vi è conferma di ricezione dei frame
• se la conferma non arriva, il mittente può rispedire il frame (quindi bisogna anche
gestire i frame duplicati)
Questo tipo di servizio è molto utile con canali con alto tasso d’errore (ad esempio,
reti wireless)
Reti di Calcolatori
Andrea Frosini
6
Il servizio connection-oriented affidabile
Caratteristiche:
• si stabilisce una connessione prima dell’invio di tutti i frame corrispondenti alla
sequenza di bit da inviare
• si chiude la connessione al termine dell’invio di tutti i frame
• vi è conferma di ricezione di ciascun frame
• garantisce che ciascun frame sia ricevuto una sola volta e nell’ordine giusto
A livello Data Link, questo servizio è in genere utilizzato dai router di una
communication subnet
Reti di Calcolatori
Andrea Frosini
7
Livello Data Link — Trasmissione
Quando il livello Network richiede la trasmissione di un certo pacchetto o flusso di
dati, il livello Data Link:
• incapsula il flusso di bit del livello Network in unità chiamate frame
• calcola il valore di una apposita funzione (checksum) per ciascun frame
• inserisce il checksum nel frame
• invoca il servizio di livello 1 (Fisico) per inviare il frame al calcolatore adiacente
Reti di Calcolatori
Andrea Frosini
8
Livello Data Link — Ricezione
In ricezione, il livello Data Link:
• riceve una sequenza di bit dal livello 1 (Fisico)
• ricostruisce dalla sequenza di bit i vari frame
• per ciascun frame:
– estrae il valore del checksum
– ricalcola il valore del checksum
– se i due valori coincidono, accetta il frame
– se i due valori differiscono, scarta il frame
Reti di Calcolatori
Andrea Frosini
9
Framing
Framing: operazione di frammentazione del flusso di bit proveniente dal livello Network
E’ ben più difficile di quanto appaia a prima vista, perché il livello 1 (Fisico) non
garantisce che il numero di bit trasmessi coincida con il numero di bit effettivamente
ricevuti
Invece il livello Data Link ha necessità di identificare ciascun frame senza possibilità
d’errore
Esistono cinque diverse strategie per il framing:
Temporizzazione
Conteggio dei caratteri
Caratteri di inizio e fine
Bit di inizio e fine
Violazioni della codifica dei bit del livello Fisico
Reti di Calcolatori
Andrea Frosini
10
Temporizzazione
In linea teorica, il modo più semplice per delimitare l’inizio e la fine di ciascun frame
consiste nell’inserire un ritardo temporale tra l’invio di un frame e l’altro
L’entità di pari livello del calcolatore ricevente potrebbe utilizzare l’assenza di ricezione
per determinare la fine di un frame: ogni bit ricevuto da quel momento in poi farà parte
del frame successivo
In pratica questa strategia non può essere applicata perché i mezzi trasmissivi
raramente forniscono garanzie sui tempi di trasmissione dei bit.
In altri termini, il livello Fisico non offre alcuna garanzia sulla temporizzazione dei propri
servizi offerti al livello Data Link
Eccezione: reti sincrone (SONET/SDH)
Reti di Calcolatori
Andrea Frosini
11
Conteggio dei caratteri I
Ciascun frame ha una testata (header).
Un particolare campo di questa testata memorizza il numero di caratteri presenti nel
frame.
Questo contatore permette di stabilire quando termina il frame nel flusso di bit
proveniente dal livello Fisico
frame 1
5 caratteri
Reti di Calcolatori
frame 2
4 caratteri
Andrea Frosini
12
Conteggio dei caratteri II
Il difetto di questo sistema è la sua fragilità nei confronti degli errori di trasmissione
Se il valore di un contatore viene alterato nella trasmissione non è più possibile
stabilire il punto in cui termina il frame
Ancor peggio, non è possibile stabilire dove inizia il nuovo frame, e quindi non è
possibile leggere alcun frame successivo
Chiedere al trasmittente di ritrasmettere il frame cattivo è inutile perché il ricevente
non sa quanti caratteri del flusso già ricevuto deve scartare
Questo metodo è praticamente abbandonato (eccetto che in combinazione con altri
metodi di framing)
Reti di Calcolatori
Andrea Frosini
13
Caratteri di inizio e fine I
Ciascun frame è considerato come una sequenza di caratteri ad 8 bit, ed è
delimitato da una sequenza di caratteri ASCII:
• l’inizio del frame è indicato dai caratteri DLE STX (DLE=Data Link Escape, STX
= Start of Text)
• la fine del frame è indicata dai caratteri DLE ETX (ETX = End of Text)
In caso di errore di trasmissione di un frame, per trovare l’inizio del frame
successivo si monitorizza il flusso di bit in arrivo cercando la sequenza di bit
corrispondente ai caratteri DLE STX
DLE, STX e ETX rappresentano ciascuno un singolo carattere ASCII (8 bit)
Reti di Calcolatori
Andrea Frosini
14
Caratteri di inizio e fine II
Si ha un problema quando le sequenze di caratteri DLE STX e DLE ETX
occorrono casualmente anche all’interno del frame
Si adotta perciò una tecnica chiamata character stuffing: ogni occorrenza del
carattere DLE all’interno del frame è preceduta da un altro carattere DLE
In questo modo, ogni carattere DLE isolato precede immediatamente un carattere
di controllo del frame
In protocolli più recenti, questa tecnica viene utilizzata con un singolo carattere di
inizio e fine (FLAG); le occorrenze di FLAG all’interno del frame vengono fatte
precedere da un altro carattere ESC (escape)
Le occorrenze di ESC all’interno del frame sono sempre raddoppiate, così ogni
carattere ESC isolato è seguito da FLAG e questa sequenza non rappresenta un
carattere di controllo del frame (importante per flussi di dati non ASCII)
Reti di Calcolatori
Andrea Frosini
15
Caratteri di inizio e fine III
La sequenza
FLAG X ESC FLAG Y ESC ESC FLAG
codifica un frame il cui contenuto è
X FLAG Y ESC
Svantaggi di questo metodo:
• si fonda sulla rappresentazione di ciascun carattere con 8 bit, mentre, ad
esempio, se si trasmette in UNICODE necessitiamo di 16 bit per carattere
• la scelta dei caratteri di controllo (DLE, STX e ETX oppure FLAG e ESC) è legata
alla codifica dei caratteri (tipicamente ASCII), ed il metodo può avere un overhead
(caratteri in più del necessario sono utilizzati) elevato se viene utilizzata una
codifica differente
• il numero di bit del frame deve essere un multiplo di 8
Reti di Calcolatori
Andrea Frosini
16
Bit di inizio e fine
Ciascun frame è delimitato da una sequenza particolare di bit detta flag byte.
Esempio di flag byte: 01111110
Per evitare ambiguità con le sequenze di bit identiche all’interno del frame si adotta il
bit stuffing:
• in trasmissione, ad ogni sequenza di cinque bit “1” consecutivi si appende un bit “0”
• in ricezione, per ogni sequenza di cinque bit “1” consecutivi si scarta il bit “0”
seguente
001111110010 => 01111110001111101001001111110
Per sincronizzarsi dopo un errore è sufficiente attendere due flag byte consecutivi
Reti di Calcolatori
Andrea Frosini
17
Violazione della codifica dei bit del livello Fisico I
Questo metodo può essere adottato soltanto se il livello Fisico codifica ciascun bit di
dati con una certa ridondanza
Ad esempio: Manchester encoding (IEEE 802.3)
• il bit di dati “1” è rappresentato con i due bit fisici low/high
• il bit di dati “0” è rappresentato con i due bit fisici high/low
Questa codifica ridondante dimezza la capacità del mezzo trasmissivo!
Reti di Calcolatori
Andrea Frosini
18
Violazione della codifica dei bit del livello Fisico II
Le coppie di bit fisici high/high e low/low sono disponibili per codificare l’inizio e la
fine di ciascun frame
Questo metodo può essere considerato simile al metodo basato sul flag byte, ma le
sequenze di bit delimitatori non possono mai presentarsi all’interno del frame
Il metodo si basa su di una particolare modalità di funzionamento del mezzo
trasmissivo:
questa caratteristica è definita dal livello Fisico, non dal livello Data Link
E’ possibile utilizzare il metodo solo se il livello Fisico offre primitive che consentano
di impostare i bit fisici della trasmissione
Reti di Calcolatori
Andrea Frosini
19
Combinazione di più metodi di framing
Spesso si utilizza il metodo di conteggio dei caratteri con uno degli altri metodi
per aumentarne l’efficienza e la robustezza
Ad esempio, combinando il metodo di conteggio dei caratteri con l’uso dei
caratteri di inizio e fine:
• in trasmissione, il frame viene delimitato dalle sequenze DLE STX e DLE ETX, e
la lunghezza del frame viene scritta nella testata
• in ricezione, il frame viene ricostruito velocemente sulla base della lunghezza
riportata nella testata, e si controlla che il frame termini correttamente con la
sequenza di caratteri DLE ETX
• in caso di errore, il flusso di caratteri viene analizzato per cercare la successiva
sequenza DLE STX
Reti di Calcolatori
Andrea Frosini
20
Gestione degli errori di trasmissione
Gli errori di trasmissione sono dovuti a
• rumore di fondo del mezzo trasmissivo
• disturbi naturali (es. fulmini)
• interferenze con dispositivi elettrici
• guasti transienti
E’ compito del livello Data Link gestire gli errori del mezzo trasmissivo (per quanto
possibile)
Reti di Calcolatori
Andrea Frosini
21
Burst di errori
In molti casi la distribuzione degli errori non è uniforme:
la probabilità che un certo bit sia errato è maggiore se uno dei bit vicini è errato
Gli errori tendono a concentrarsi in burst
Esempio: reti wireless basate su onde radio
rilevazione e correzione degli errori sono più difficili
il numero di frame con errore è minore
Reti di Calcolatori
Andrea Frosini
22
Rilevazione e correzione dell’errore
Per gestire l’errore il livello Data Link può adottare due approcci:
• Rilevazione dell’errore: è possibile solo determinare l’esistenza di bit erronei
all’interno di un frame, includendo meno informazione aggiuntiva possibile
• Correzione dell’errore: è possibile determinare l’errore e ricostruire il contenuto del
frame originario mandando sufficiente informazione aggiuntiva
Nel secondo caso il frame dovrà essere codificato in modo più ridondante, e dunque
meno efficiente. Tale caso è conveniente con canali con elevato tasso d’errore (ad
es. wireless)
Reti di Calcolatori
Andrea Frosini
23
Codici
Un frame (a parte i delimitatori) consiste di n = m + r bit, dove:
- m bit costituiscono il messaggio vero e proprio
- r bit sono ridondanti, e sono detti reduntant bit (o check bit)
Una sequenza di n bit fatta in tal modo, e tale che gli m bit del messaggio sono in
accordo con gli r bit di controllo si dice codeword, o parola di codice
Date due qualunque parole di codice,
ad es. 1000 1001 e 1011 0001
è possibile determinare il numero di bit che in esse differiscono (3 nell'esempio)
tramite un semplice XOR fatto bit a bit
Tale numero si dice la distanza di Hamming delle due codeword (dH) e può essere
vista come il numero di bit da cambiare per passare da una parola all’altra
Reti di Calcolatori
Andrea Frosini
24
Distanza di Hamming di un codice I
Un codice è un algoritmo che dati m bit di dati produce r bit di controllo
Ogni frame con n = m + r bit può contenere 2m messaggi differenti
Il numero di parole di codice è però strettamente minore di 2n, perché alcune sequenze
di n bit devono essere non valide (sono quelle che segnalano un errore)
Si definisce la distanza di Hamming di un codice C la minima distanza esistente tra due
parole del codice:
dH ( C ) = min dH ( u, v )
con u,v  C e u  v
Reti di Calcolatori
Andrea Frosini
25
Distanza di Hamming di un codice II
Se un codice deve rilevare d errori, la sua distanza di Hamming deve essere
almeno pari a d+1
Se la distanza fosse minore, un burst di d errori potrebbe trasformare una parola di
codice in un’altra parola di codice: l’errore non sarebbe rilevato
Se un codice deve correggere d errori, la sua distanza di Hamming deve essere
almeno pari a 2d+1 (!!!)
Un burst di d errori al peggio trasforma una parola di codice in una sequenza di bit a
distanza al più d dalla parola di codice corretta e a distanza almeno d+1 da tutte le
altre parole di codice
Reti di Calcolatori
Andrea Frosini
26
Bit di parità
Un semplice codice per la rilevazione di 1 errore è costituito dal bit di parità
Data la sequenza di m bit che costituiscono il messaggio, si aggiunge un bit di
controllo (r = 1) in modo tale che la somma di tutti i bit “1” della parola di codice sia
pari (o dispari)
Ad esempio (m = 7):
00101101
10101100
Il codice a bit di parità ha distanza di Hamming pari a 2 (non ci sono parole che
differiscono per un solo bit)
Reti di Calcolatori
Andrea Frosini
27
Correzione di 2 errori (non efficiente)
Il seguente codice ha distanza di Hamming pari a 5:
C = { 0000000000, 0000011111, 1111100000, 1111111111 }
Consente di rilevare 4 errori e di correggere 2 errori
Poiché ha solo 4 parole di codice, ciascuna parola di codice “rappresenta” 2 bit di
dati: n = 10, r = 8, m = 2
E’ molto inefficiente: solo il 20% dei bit trasmessi è realmente significativo, gli altri
sono ridondanti
Reti di Calcolatori
Andrea Frosini
28
Correzione di d errori (non efficiente)
In generale possiamo dire che:
un modo semplice per creare codici per la correzione di d errori consiste nel
replicare l’informazione
Dato un messaggio di m bit si costruisce una parola di codice con 2d copie di
ciascuno dei bit del messaggio (r = 2d · m)
La distanza di Hamming del codice è 2d+1, quindi può correggere d errori
Il codice non è efficiente: solo 1 / (2d+1) bit sono significativi
Reti di Calcolatori
Andrea Frosini
29
Numero minimo dei bit di controllo
Sia C un codice che corregge 1 errore con parole di codice con n bit, m bit di
messaggio e r bit di controllo
Ciascuna parola di codice ha n sequenze di bit illegali a distanza 1, costruite
invertendo un bit della parola di codice
Ciascuno dei 2m messaggi richiede n+1 sequenze di bit: (n+1) · 2m
m


2n
2r - r - 1
Es. se m = 128 , allora r  8
Reti di Calcolatori
Andrea Frosini
30