RETI DI CALCOLATORI
E APPLICAZIONI TELEMATICHE
Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria
Università degli Studi di Udine
Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.
Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.
Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.
L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).
In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.
In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non
Nota di Copyright
Lezione 15
Il livello data-link (I parte):
protocolli per collegamenti punto-punto
Lezione 15: indice degli argomenti
• Scopi del livello data-link, servizi forniti al livello di rete
• Impacchettamento
• Controllo degli errori
• Controllo di flusso
• Esempi di protocollo: HDLC, SLIP, PPP
Scopi del livello data-link
• Comunicazione sufficientemente
affidabile ed efficiente tra nodi adiacenti
• Nelle reti locali anche gestione della condivisione del mezzo trasmissivo
• Servizi offerti al livello network:
• senza connessione e senza riscontro
• senza connessione ma con riscontro
• con connessione e con riscontro
Servizi
senza connessione e senza riscontro
• Utili se il mezzo trasmissivo è affidabile
• Tipicamente usato nelle LAN
• Introduce ritardi minimi
→ adatto a servizi real-time (es.
audio/video)
Servizi
senza connessione ma con riscontro
• Utili se il mezzo trasmissivo è poco affidabile
• Tipicamente usato nelle reti wireless
• Un messaggio di riscontro che viene
perso può provocare la ricezione multipla
di un pacchetto
Servizi
con connessione e con riscontro
• Prevede la numerazione e il controllo del corretto ricevimento di tutti i pacchetti
• Garantisce che ogni pacchetto venga ricevuto una ed una sola volta
• Garantisce che tutti i pacchetti vengano
ricevuti nello stesso ordine con cui sono
stati trasmessi
Funzionalità del livello data-link
• Impacchettamento (“framing”)
• permette di delimitare i pacchetti
trasportati dal flusso di bit al livello fisico
• prevede l’inserimento di checksum per il controllo degli errori
• Controllo di flusso
• permette di adattare la velocità del
trasmettitore alla velocità del ricevitore
Impacchettamento
Delimitazione della trama con conteggio dei byte
frame 1
lunghezza del frame in byte
frame 2
5 11 12 13 14 15 3 16 17 18 4 19 20 21 22 frame 3
frame 1 frame 2 (errato)
5 11 12 13 14 15 7 16 17 18 4 19 20 21 22
errore di trasmissione byte di dato erroneamente considerato di conteggio
Delimitazione della trama con caratteri speciali
• Si utilizzano i codici ASCII:
• DLE (Data Link Escape)
• STX (Start of TeXt)
• ETX (End of TeXt)
• DLE-STX = inizio, DLE-ETX = fine
• E se compaiono nei dati?
• “byte stuffing” (riempimento di caratteri): i caratteri DLE nei dati vengono raddoppiati in trasmissione e ripristinati in ricezione
Delimitazione della trama con caratteri speciali
byte di dato delimitatore
di inizio della trama
byte stuffing
DLESTX 137 234 DLE DLE 79 DLE ETX
delimitatore di fine della
trama
137 234 DLE 79
dati da trasmettere
dati trasmessi
Delimitazione della trama con riempimento di bit (“bit stuffing”)
• Adatta per ogni tipo di dato e con un numero arbitrario di bit per carattere
• Delimitarore (“flag byte”): 01111110
• Se il livello data link trova 11111 nei
dati da trasmettere aggiunge un bit a 0
• Quando il ricevitore trova 5 bit a 1 seguiti
da uno 0 rimuove il bit a 0
Delimitazione della trama con riempimento di bit (“bit stuffing”)
011011111111111111110010
dati da trasmettere
011011111011111011111010010
dati trasmessi
bit stuffing
Controllo e correzione degli errori
Controllo e correzione degli errori
dati in trasmissione
FCS
dati FCS
Frame Check
Sequence = f (dati)
Controllo e correzione degli errori
f (dati)
dati FCS
FCS
= ?
i dati ricevuti sono corretti se possibile si correggono
i bit errati, altrimenti si in ricezione
NO SÌ
Controllo e correzione degli errori
• I codici di Hamming permettono la correzione
• adatti se non è conveniente la ritrasmissione
• I codici polinomiali o codici a ridondanza ciclica (CRC) si limitano a rilevare gli
errori
• richiedono meno bit aggiuntivi ai bit di dato
Controllo di flusso
Controllo di flusso
• Nei collegamenti punto-punto si basa sull’autorizzazione, esplicita o implicita data dal ricevitore al trasmettitore per inviare i dati
• Richiede protocolli con cui trasmettitore e ricevitore si scambiano le informazioni di controllo
• Bisogna considerare la possibilità di
perdita delle informazioni di controllo
Un semplice protocollo stop-and-wait
• Il nodo A trasmette un pacchetto e si mette in attesa del riscontro da B
• Se il traffico è bidirezionale, il riscontro può viaggiare nell’intestazione di uno dei pacchetti in arrivo da B ad A
(piggybacking)
Un semplice protocollo stop-and-wait
• Problema 1: se il riscontro non arriva?
• A ritrasmette il pacchetto
• Problema 2: se il riscontro non arriva
perché andato perso, ma il pacchetto era arrivato correttamente?
• A ritrasmette il pacchetto e B lo riceve una seconda volta
→ duplicazione dei pacchetti
Un semplice protocollo stop-and-wait
• Problema 3: quanto costa aspettare il riscontro?
• Esempio: collegamento in fibra ottica a 1 Gb/s tra San Francisco e New York
3 Mbyte3 Mbyte in in transitotransito
Protocolli “sliding window”
• Ogni frame spedito è numerato, da 0 a
2
n-1 (numero progressivo su n bit)
Protocolli “sliding window”
• Il trasmettitore mantiene una finestra di trasmissione
• numeri d’ordine dei pacchetti che può spedire
• permette di spedire frame prima di aver ricevuto i riscontri dei frame precedenti
• i frame appartenenti alla finestra vengono memorizzati per eventuali ritrasmissioni
Protocolli “sliding window”
• Il ricevitore mantiene una finestra di ricezione
• numeri d’ordine dei pacchetti che può ricevere
• consente di riconoscere e scartare frame duplicati a causa di riscontri andati
perduti
• permette di accettare frame non ordinati (a causa di frame persi o di
ritrasmissioni)
Protocolli “sliding window”
1 2 5
6
0
3 4
7 il limite superiore viene fatto avanzare quando si spedisce un frame
il limite inferiore viene fatto avanzare quando si riceve un riscontro
trasmettitore
1 2 5
6
0
7 il limite superiore viene fatto avanzare quando si riceve un frame e si invia il riscontro
ricevitore
Esempi di protocolli
HDLC
• High-Level Data Link Control
• Derivato da SDLC (Synchronous Data Link Control) di IBM
• Orientato al bit, con bit stuffing
• Contiene anche l’indirizzo del
destinatario, per linee con terminali
multipli (punto-multipunto)
HDLC
dati con bit stuffing
8 bit
01111110address control data checksum 01111110
8 bit 8 bit ≥ 0 16 bit 8 bit
SLIP
• Serial Line Internet Protocol
• Inventato per spedire pacchetti IP su linea telefonica via modem
• Delimitatore dei pacchetti: byte C0
h• Rimpiazzamento dei caratteri nei dati:
→ C0h diventa DBh DCh
• Molte limitazioni, tra cui la mancanza di
gestione degli errori
PPP
• Point-to-Point Protocol
• Miglioramenti rispetto a SLIP:
• rilevamento degli errori
• protocollo di controllo del collegamento
• supporto di più protocolli del livello rete
• Formato della trama simile ad HDLC, ma
orientato al byte
PPP
dati con rimpiazzamento di caratteri
1 byte
flag
01111110
payload (dati) address
11111111
control
00000011
checksum
2 o 4 byte 1 byte
protocol
1 byte 1 byte 1 o 2 byte variabile
flag
01111110
payload (dati)
variabile
Lezione 15: riepilogo
• Scopi del livello data-link, servizi forniti al livello di rete
• Impacchettamento
• Byte stuffing, bit stuffing
• Controllo degli errori
• Controllo di flusso
• Protocolli sliding window
• Esempi di protocollo: HDLC, SLIP, PPP
Bibliografia
• “Reti di Computer”
• Capitolo 3
• Libro “Reti locali: dal cablaggio all’internetworking”
contenuto nel CD-ROM omonimo
• Parte del capitolo 13
