Il livello data-link (I parte): protocolli per collegamenti punto-a-punto

© 1999 Pier Luca Montessoro (si veda la nota a pagina 2) 1

RETI DI CALCOLATORIE APPLICAZIONI TELEMATICHE

Prof. PIER LUCA MONTESSORO

Facoltà di IngegneriaUniversità degli Studi di Udine


Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sulcopyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alleslides (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 Ministerodell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine dilucro. In tal caso non è richiesta alcuna autorizzazione.Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni susupporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se nonesplicitamente autorizzata per iscritto, a priori, da parte degli autori.L’informazione contenuta in queste slide è ritenuta essere accurata alla data dellapubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzatain progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamentisenza preavviso. L’autore non assume alcuna responsabilità per il contenuto di questeslide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità,aggiornamento dell’informazione).In ogni caso non può essere dichiarata conformità all’informazione contenuta in questeslide.In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide nondevono 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 allivello di rete

• Impacchettamento

• Controllo degli errori• Controllo di flusso• Esempi di protocollo: HDLC, SLIP, PPP


Scopi del livello data-link

• Comunicazione sufficientementeaffidabile ed efficiente tra nodi adiacenti

• Nelle reti locali anche gestione dellacondivisione del mezzo trasmissivo

• Servizi offerti al livello network:• senza connessione e senza riscontro

• senza connessione ma con riscontro• con connessione e con riscontro


Servizisenza 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)


Servizisenza connessione ma con riscontro

• Utili se il mezzo trasmissivo è pocoaffidabile

• Tipicamente usato nelle reti wireless

• Un messaggio di riscontro che vieneperso può provocare la ricezione multipladi un pacchetto


Servizicon connessione e con riscontro

• Prevede la numerazione e il controllo delcorretto ricevimento di tutti i pacchetti

• Garantisce che ogni pacchetto vengaricevuto una ed una sola volta

• Garantisce che tutti i pacchetti venganoricevuti nello stesso ordine con cui sonostati 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 ilcontrollo degli errori

• Controllo di flusso• permette di adattare la velocità del

trasmettitore alla velocità del ricevitore


Impacchettamento


Delimitazione della trama conconteggio 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 erroneamenteconsiderato di conteggio


Delimitazione della trama concaratteri 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): icaratteri DLE nei dati vengono raddoppiatiin trasmissione e ripristinati in ricezione


Delimitazione della trama concaratteri speciali

byte di datodelimitatoredi inizio della

tramabyte stuffing

DLESTX 137 DLE DLE DLE ETX234 79

delimitatoredi fine della

trama

137 DLE234 79dati da trasmettere

dati trasmessi


Delimitazione della trama conriempimento di bit (“bit stuffing”)

• Adatta per ogni tipo di dato e con unnumero arbitrario di bit per carattere

• Delimitarore (“flag byte”): 01111110

• Se il livello data link trova 11111 neidati da trasmettere aggiunge un bit a 0

• Quando il ricevitore trova 5 bit a 1 seguitida uno 0 rimuove il bit a 0


Delimitazione della trama conriempimento di bit (“bit stuffing”)

011011111111111111110010dati da trasmettere

011011111011111011111010010dati trasmessi

bit stuffing


Controllo e correzione degli errori



dati

in trasmissione

FCS

dati FCS

Frame CheckSequence = f (dati)



f (dati)

dati FCS

FCS

= ?

i dati ricevutisono corretti

se possibile si correggonoi bit errati, altrimenti siscarta il pacchetto

in ricezione

NO SÌ



• I codici di Hamming permettono lacorrezione• adatti se non è conveniente la

ritrasmissione

• I codici polinomiali o codici a ridondanzaciclica (CRC) si limitano a rilevare glierrori• richiedono meno bit aggiuntivi ai bit di

dato


Controllo di flusso


Controllo di flusso

• Nei collegamenti punto-punto si basasull’autorizzazione, esplicita o implicitadata dal ricevitore al trasmettitore perinviare i dati

• Richiede protocolli con cui trasmettitore ericevitore si scambiano le informazioni dicontrollo

• Bisogna considerare la possibilità diperdita delle informazioni di controllo


Un semplice protocollo stop-and-wait

• Il nodo A trasmette un pacchetto e simette in attesa del riscontro da B

• Se il traffico è bidirezionale, il riscontropuò viaggiare nell’intestazione di uno deipacchetti in arrivo da B ad A(piggybacking)



• Problema 1: se il riscontro non arriva?• A ritrasmette il pacchetto

• Problema 2: se il riscontro non arrivaperché andato perso, ma il pacchetto eraarrivato correttamente?• A ritrasmette il pacchetto e B lo riceve

una seconda volta

→ duplicazione dei pacchetti



• Problema 3: quanto costa aspettare ilriscontro?• Esempio: collegamento in fibra ottica a 1

Gb/s tra San Francisco e New York

3 3 MbyteMbytein in transitotransito


Protocolli “sliding window”

• Ogni frame spedito è numerato, da 0 a2n-1 (numero progressivo su n bit)



• Il trasmettitore mantiene una finestra ditrasmissione• 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



• Il ricevitore mantiene una finestra diricezione• numeri d’ordine dei pacchetti che può

ricevere• consente di riconoscere e scartare frame

duplicati a causa di riscontri andatiperduti

• permette di accettare frame non ordinati(a causa di frame persi o diritrasmissioni)



1

25

6

0

34

7 il limite superiore viene fatto avanzarequando si spedisce un frame

il limite inferiore viene fatto avanzarequando si riceve un riscontro

trasmettitore

1

25

6

0

34

7 il limite superiore viene fatto avanzarequando si riceve un frame e si invia ilriscontro

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 terminalimultipli (punto-multipunto)


HDLC

dati con bit stuffing

8 bit

01111110 dataaddress control checksum 01111110

8 bit 8 bit 16 bit 8 bit≥ 0


SLIP

• Serial Line Internet Protocol• Inventato per spedire pacchetti IP su

linea telefonica via modem

• Delimitatore dei pacchetti: byte C0h

• Rimpiazzamento dei caratteri nei dati:→ C0h diventa DBh DCh

• Molte limitazioni, tra cui la mancanza digestione 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, maorientato al byte


PPP

dati con rimpiazzamento di caratteri

1 byte

flag01111110

payload(dati)

address11111111

control00000011

checksum

2 o 4 byte 1 byte

protocol

1 byte 1 byte 1 o 2 byte variabile

flag01111110

payload(dati)

variabile


Lezione 15: riepilogo

• Scopi del livello data-link, servizi forniti allivello 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 cablaggioall’internetworking”

contenuto nel CD-ROM omonimo• Parte del capitolo 13


Come contattare il prof. Montessoro

E-mail: [email protected]: 0432 558286

Fax: 0432 558251URL: www.uniud.it/~montessoro

Il livello data-link (I parte): protocolli per collegamenti punto-a-punto

Documents

Transcript of Il livello data-link (I parte): protocolli per collegamenti punto-a-punto