Reti di Calcolatori
a.a. 2005/06
Lezione 8
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Fisico
Reti di Calcolatori
Andrea Frosini
2
Schema generale della trasmissione
Nei livelli Network, Data Link e Fisico esistono tre distinte entità indipendenti
(hardware o software) che comunicano tra loro scambiandosi messaggi tramite le
opportune interfacce
1. L’entità di livello Network passa un pacchetto all’entità di livello Data Link
2. L’entità Data Link prepara un frame aggiungendo una testata ed una coda
contenenti informazioni di controllo
3. L’entità Data Link calcola il checksum del frame e lo inserisce in un opportuno
campo nella testata o nella coda del frame
4. L’entità Data Link passa il frame all’entità del livello Fisico
5. L’entità Fisico invia il frame per mezzo del canale di comunicazione
Reti di Calcolatori
Andrea Frosini
3
Schema generale della ricezione
1. L’entità Fisico riceve una sequenza di bit dal canale di comunicazione e la
passa all’entità Data Link
2. L’entità Data Link estrae il frame dalla sequenza di bit
3. L’entità Data Link calcola il checksum del frame e lo controlla con il checksum
nell’opportuno campo nella testata o nella coda del frame
4. L’entità Data Link:
• se il frame ha errori, adotta una opportuna procedura (ad esempio scarta il
frame ed eventualmente trasmette un ack negativo)
• se il frame è corretto, estrae il pacchetto dal frame rimovendo la testata e la
coda e lo passa all’entità Network
Reti di Calcolatori
Andrea Frosini
4
Gestione sequenza di trasmissione e flusso I
Oltre alla costruzione dei frame ed alla rilevazione/correzione degli errori, il livello
Data Link può gestire
• il flusso dei frame (per evitare che il calcolatore ricevente sia sovraccaricato)
• la sequenza di trasmissione dei frame (soprattutto per evitare che frame duplicati
siano passati al livello Network ricevente)
Questi due obiettivi sono spesso ottenuti utilizzando un singolo protocollo
Reti di Calcolatori
Andrea Frosini
5
Gestione sequenza di trasmissione e flusso II
Le funzioni effettivamente svolte dal livello Data Link dipendono in realtà dal tipo di
servizio offerto:
• affidabile: controllo che i frame arrivino tutti, senza errori e senza duplicazioni
• non affidabile: controllo che i frame arrivati non contengano errori (quelli con errori
vengono semplicemente scartati; questo di solito è “gratis” perché implementato in
hardware)
Si assume che il livello Data Link non ha mai necessità di spezzare un pacchetto del
livello Network in più frame
In pratica, i protocolli affidabili del livello Data Link sono anche connection-oriented e
garantiscono che i pacchetti raggiungono il livello Network della macchina
destinazione nello stesso ordine in cui sono stati trasmessi dal livello Network al
livello Data Link della macchina sorgente
Reti di Calcolatori
Andrea Frosini
6
Acknowledgement
L’acknowledgement (ack) o conferma è un messaggio inviato dal ricevente al
trasmittente per informarlo che
• un frame è arrivato correttamente (positive ack)
• un frame è arrivato con errori (negative ack)
I messaggi di ack possono essere inviati come
• singoli frame (frame ack)
• all’interno di opportuni campi della testata dei frame normali (frame dati)
Il meccanismo di acknowledgement dei frame fallisce in caso di scomparsa di frame
Reti di Calcolatori
Andrea Frosini
7
Scomparsa di frame
Problema 1: un frame di dati è trasmesso ma scompare completamente; il ricevente
non invia nulla perché non deve dare alcuna conferma; il trasmittente aspetta una
conferma (negativa o positiva) che non arriverà mai
Soluzione: il trasmittente stabilisce, per ciascun frame dati, un termine utile entro il
quale deve arrivare il relativo ack. Se l’ack non arriva in questo periodo di tempo, il
frame dati viene ritrasmesso
Problema 2: un frame di ack scompare del tutto; il trasmittente, dopo aver aspettato
invano la conferma, invia un secondo frame di dati identico al precedente; il
destinatario riceve un frame dati duplicato
Soluzione: il trasmittente inserisce un numero di sequenza all’interno di ciascun frame
dati; il ricevente scarta tutti i frame aventi lo stesso numero di sequenza di quello
precedentemente ricevuto
Reti di Calcolatori
Andrea Frosini
8
Gestione del flusso
Il meccanismo degli acknowledgement è utile anche per il controllo del flusso di
trasmissione
Una strategia per il controllo del flusso consiste nell’attesa di una autorizzazione
esplicita del destinatario all’invio di nuovi frame
Questa comunicazione può essere inserita all’interno di un frame ack che conferma
la corretta ricezione di un frame dati precedente
Reti di Calcolatori
Andrea Frosini
9
Schema di un frame
Nell’analisi dei protocolli di trasmissione e flusso del livello Data Link è utile far
riferimento ad un frame convenzionale diviso in due campi (header e info):
Kind
Seq
Ack
Info
Chk
Nel campo header si possono individuare altri sottocampi:
Kind: Serve a distinguere il tipo di frame (contiene dati, di controllo, ecc.)
Seq: Contiene il numero progressivo del frame
Ack: Contiene informazioni legate all'acknowledgement
Chk: contiene il checksum del frame
Il campo info contiene un pacchetto di livello network completo (comprendente le
informazioni di controllo di tale livello)
Reti di Calcolatori
Andrea Frosini
10
Protocolli unidirezionali
Prendiamo in considerazione alcuni schemi di protocolli del livello Data Link per il
controllo di trasmissione e flusso su un canale simplex:
• Protocollo utopia
• Protocollo simplex stop-and-wait
• Protocollo PAR
Reti di Calcolatori
Andrea Frosini
11
Protocollo utopia
Il protocollo utopia è il più semplice possibile. Si assumono le ipotesi non realistiche:
• i dati sono spediti in una sola direzione
• il livello Network trasmittente è sempre pronto ad inviare dati
• il livello Network ricevente è sempre pronto a ricevere dati
• il livello Data Link ha a disposizione buffer di dimensione infinita
• il tempo necessario per analizzare i frame è trascurabile
• il canale di comunicazione (ossia il livello Fisico) è esente da errori e non perde
alcun frame
Reti di Calcolatori
Andrea Frosini
12
Protocollo utopia – Trasmissione
La procedura logica eseguita dall’entità del livello Data Link trasmittente è il seguente
loop infinito:
while (true) {
receive_network(packet);
(riceve dati dal livello Network)
frame = build_frame(packet);
(costruisce il frame di dati)
send_physical(frame);
(passa il frame al livello Fisico)
}
Viene utilizzato il campo info del frame, non vengono utilizzati i campi di controllo
kind, ack, seq e chk
Reti di Calcolatori
Andrea Frosini
13
Protocollo utopia – Ricezione
La procedura logica eseguita dall’entità del livello Data Link ricevente è il seguente
loop infinito:
while (true) {
wait_data_physical(buffer);
(riceve frame dal livello Fisico)
packet = extract_packet(frame);
(estrae il pacchetto di dati)
send_network(packet);
(passa i dati al livello Network)
}
Notare che il canale di comunicazione deve essere wire-like: due bit spediti uno dopo
l’altro devono essere ricevuti nello stesso ordine
Reti di Calcolatori
Andrea Frosini
14
Protocollo utopia – Svantaggi
La assunzione meno realistica del protocollo utopia:
• il livello Network ricevente è in grado di accettare pacchetti a qualunque velocità
o equivalentemente:
• il livello Data Link ricevente ha a disposizione un buffer per i frame ricevuti di
dimensione infinita
Un protocollo più evoluto del protocollo utopia è in grado di controllare il tasso di
trasmissione dei frame per evitare il sovraccarico del ricevente
Reti di Calcolatori
Andrea Frosini
15
Ritardo fissato in trasmissione
Per risolvere il problema della congestione del ricevente si può introdurre un
ritardo fissato tra l’invio di un frame ed il successivo
Questo approccio è conveniente solo in casi molto particolari (ad esempio, reti di
comunicazioni sincrone con ricevente ben dimensionato)
In generale è da scartare:
• l’intervallo temporale tra la ricezione di un frame e la sua trasmissione a livello
Network può variare considerevolmente
• se il progettista della rete imposta il ritardo di trasmissione dei frame sul caso
peggiore, la rete di comunicazione è sotto-utilizzata
Reti di Calcolatori
Andrea Frosini
16
Protocollo simplex stop-and-wait
Rendiamo ora le assunzioni iniziali un po’ più veritiere:
• i dati sono spediti in una sola direzione (ma i frame devono poter viaggiare in
entrambe le direzioni!)
• il canale di comunicazione (ossia il livello Fisico) è esente da errori e non perde
alcun frame
Il più semplice protocollo simplex stop-and-wait è basato sull’invio di un frame ack
ogni volta che un pacchetto è stato trasmesso con successo all’entità Network
ricevente
Il canale di comunicazione deve essere half-duplex o full-duplex
Reti di Calcolatori
Andrea Frosini
17
Protocollo simplex stop-and-wait – Trasmissione
La procedura logica eseguita dall’entità del livello Data Link trasmittente:
while (true) {
receive_network(packet);
frame = build_frame(packet);
send_physical(frame);
wait_data_physical(buffer);
(attesa del frame ack vuoto)
}
Reti di Calcolatori
Andrea Frosini
18
Protocollo simplex stop-and-wait – Ricezione
La procedura logica eseguita dall’entità del livello Data Link ricevente:
while (true) {
wait_data_physical(buffer);
packet = extract_packet(frame);
send_network(packet);
frame = build_frameack();
(costruzione del frame ack vuoto)
send_physical(frame);
(invio del frame ack vuoto)
}
Reti di Calcolatori
Andrea Frosini
19
Protocollo simplex stop-and-wait con rumore I
La assunzione meno realistica del protocollo simplex stop-and-wait è che ogni frame
trasmesso venga ricevuto correttamente poiché nessun canale di comunicazione
reale è del tutto privo di errori
L’uso di un timer (da parte dell’entità trasmittente) e di checksum insieme al protocollo
simplex stop-and-wait sembra essere sufficiente:
• quando il trasmittente invia un frame, fa partire un timer
• se non arriva il relativo frame ack entro la scadenza del timer, il trasmittente invia
nuovamente il frame
• il ricevente invia un frame ack solo quando riceve un frame senza errori
Reti di Calcolatori
Andrea Frosini
20
Protocollo simplex stop-and-wait con rumore II
Lo svantaggio principale del protocollo simplex stop-and-wait unito con l’uso del timer
è che l’entità Data Link ricevente non è in grado di gestire i pacchetti duplicati
Infatti, tutti i pacchetti duplicati vengono trasmessi al livello Network:
• Il trasmittente invia un frame dati
• Il destinatario riceve il frame dati correttamente, ed invia il frame ack
• Il trasmittente non riceve il frame ack
• Scaduto il timer, il trasmittente invia per la seconda volta il frame dati
• Il destinatario riceve il frame dati correttamente, ed invia il frame ack
• Il trasmittente riceve il frame ack
Lo stesso pacchetto è stato passato al livello Network ricevente due volte
Reti di Calcolatori
Andrea Frosini
21
Protocollo PAR
E’ necessario aggiungere al protocollo simplex stop-and-wait con timer la capacità
del livello Data Link destinatario di distinguere frame dati già ricevuti in precedenza
Ciò che si ottiene è un protocollo PAR (Positive Acknowledgement with
Retransmission), anche chiamato protocollo ARQ (Automatic Repeat Request)
Il metodo più semplice per distinguere i frame dati consiste nel memorizzare nel
campo seq della testata del frame un numero di sequenza, incrementato
automaticamente dal livello Data Link trasmittente per ciascun diverso frame dati
Quando il destinatario riceve un frame dati con lo stesso numero di sequenza del
frame ricevuto in precedenza, riconosce un frame duplicato e lo scarta
Reti di Calcolatori
Andrea Frosini
22
Protocollo PAR – Numeri di sequenza
Quanti bit devono essere riservati nella testata del frame per il campo seq?
Nel caso di protocolli di tipo PAR, un frame dati è inviato solo dopo la ricezione del
frame ack relativo al frame dati inviato prima
Se dunque il livello Data Link ha ricevuto un certo frame con numero di sequenza m,
il prossimo frame dati che riceverà potrà solo essere:
m+1 in caso di ricezione corretta del frame ack, oppure
m in caso di perdita del frame ack
Sono sufficienti due soli numeri di sequenza, quindi seq può essere costituito da un
singolo bit
Reti di Calcolatori
Andrea Frosini
23
Protocollo PAR – Trasmissione I
La procedura logica eseguita dall’entità del livello Data Link trasmittente:
seq = 0; receive_network(packet);
while (true) {
frame = build_frame(packet,seq);
send_physical(frame);
timed_wait_data_physical(buffer); (resetta il timer e attende)
if (frame_arrival)
{
frame = extract_frame(buffer);
if (checksum(frame) && frame.ack == seq){
receive_network(packet); seq = 1 - seq; }
}
}
Reti di Calcolatori
Andrea Frosini
24
Protocollo PAR – Trasmissione II
Commenti:
• il valore di seq viene cambiato solo quando il giusto ack è arrivato
• il tempo di attesa della procedura timed_wait_data_physical() è finito. Una
volta scaduto si attua nuovamente l’invio del frame
• una volta che il giusto frame è arrivato si accetta un nuovo frame dal livello
superiore (Network) e si invia ponendo l’header seq modificato
• tale protocollo potrà essere reso più efficiente utilizzando un numero di bit maggiore
per seq (come vedremo)
Reti di Calcolatori
Andrea Frosini
25
Protocollo PAR – Ricezione I
La procedura logica eseguita dall’entità del livello Data Link ricevente:
seq = 0;
while (true) {
wait_data_physical(buffer);
frame = extract_frame(buffer);
if (checksum(frame)) {
if (frame.seq == seq)
{
packet = extract_packet(frame);
send_network(packet); seq = 1 - seq;}
frame = build_frameack(1 - seq); (qui seq NON cambia)
send_physical(frame);}
}
Reti di Calcolatori
Andrea Frosini
26
Protocollo PAR – Ricezione II
Il mittente etichetta i frame dati con la sequenza ...0,1,0,1..., ma passa
all'etichetta e frame successivi solo quando arriva un ack;
finché ciò non succede, continua a ritrasmettere lo stesso frame
Il ricevente invia un ack di conferma per tutti i frame dati privi di errori,
ma consegna al livello network solo quelli giusti, e cioè etichettati secondo la
sequenza ...0,1,0,1.…
Quando un frame con etichetta sbagliata arriva a destinazione lo ignora e chiede il
successivo
Reti di Calcolatori
Andrea Frosini
27
Protocollo PAR – Normale funzionamento
host1
host2
1
ack
1
0
0
ack
1
Reti di Calcolatori
Andrea Frosini
28
Protocollo PAR – Errore su frame dati
host1
host2
timeout
1
1
ack
1
1
0
Reti di Calcolatori
Andrea Frosini
29
Protocollo PAR – Errore su frame ack
host1
host2
timeout
1
ack
1
non passato al
livello Network
1
ack
1
1
0
Reti di Calcolatori
Andrea Frosini
30
Protocollo PAR – Lunghezza del timer
La scelta dell’intervallo a cui impostare il timer per la ritrasmissione è critica:
• se il valore del timer è troppo lungo, il protocollo è inefficiente perché ogni frame ack
perso provoca lunghi “stalli”
• se il valore del timer è troppo corto, il mittente può ritrasmettere un frame dati
mentre il frame ack atteso sta per essere correttamente ricevuto
L’ultimo scenario è particolarmente disastroso se l’entità Data Link trasmittente non ha
modo di associare ciascun frame ack al numero di sequenza del relativo frame dati
Perciò il campo ack del frame ack contiene il numero di sequenza (0 o 1 nel nostro
caso) del frame dati a cui l’acknowledgement si riferisce
Reti di Calcolatori
Andrea Frosini
31
Protocollo PAR (ack anonimo!) – Timeout troppo corto
associazioni
fatte da host1
timeout
host1
host2
1
ack
1
ack
1
non passato al
livello Network
1
0
1
Perdita di
ack
1
0
!!!
0
Reti di Calcolatori
Andrea Frosini
32
Protocollo PAR (ack anonimo) – No ack su frame duplicati
Cosa accade nel caso di ack anonimo se
non inviamo ack per frame duplicati?
Completa la trasmissione utilizzando:
host1
host2
ack
personaggi:
0
Reti di Calcolatori
1
timeout
oggetti da utilizzare:
Andrea Frosini
33