Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

(1)

RETI DI CALCOLATORI E APPLICAZIONI TELEMATICHE

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

© 1999 Pier Luca Montessoro (si veda la nota a pagina 2) 2 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 devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

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)

(2)

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

(3)

Delimitazione della trama con caratteri speciali

byte di dato delimitatore

di inizio della trama

byte stuffing

DLE STX 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 dopo il quinto 1

• 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

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 scarta il pacchetto

in ricezione

NO SÌ

(4)

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

• 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 Mbyte

in transito

(5)

Protocolli “sliding window”

• Ogni frame spedito è numerato, da 0 a 2

ⁿ

-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

3 4

7

il limite superiore viene fatto avanzare quando si riceve un frame e si invia il riscontro

la dimensione della finestra è fissa 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)

(6)

HDLC

dati con bit stuffing 8 bit

01111110address control data checksum 01111110

8 bit 8 bit ≥⁰ 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:

→ C0

_h

diventa DB

_h

DC

_h

• 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

(7)