3.3) Gestione sequenza di trasmissione e flusso |
Dopo aver trovato il modo di delineare l'inizio e la fine dei frame e di gestire gli errori di trasmissione, bisogna trovare la maniera di informare opportunamente il mittente se i frame spediti sono anche arrivati, e senza errori, dall'altra parte:
Per saperlo si introduce il concetto di acknowledgement, che è un messaggio inviato dal destinatario al mittente per informarlo che:
Nel seguito, ove necessario per evitare ambiguità, col
termine frame dati indicheremo
un frame che trasporta informazioni generate nel colloquio fra
le peer entity; col termine frame di
ack indicheremo un frame il cui solo scopo è
trasportare un acknowledgement.
Introducendo l'uso degli ack sorgono però alcuni problemi,
fra cui:
| Problema 1 | un frame può anche sparire del tutto, per cui il mittente rimane bloccato in attesa di un ack che non arriverà mai; |
| Soluzione 1 | il mittente stabilisce un time-out per la ricezione dell'ack. Se questo non arriva in tempo, il frame si ritrasmette. |
| Problema 2 | se sparisce l'ack, il destinatario può trovarsi due (o più) copie dello stesso frame; |
| Soluzione 2 | il mittente inserisce un numero di sequenza all'interno di ogni frame dati. |
Un altro aspetto importante, che richiede anch'esso un feedback
dal destinatario al mittente, è il controllo del flusso,
onde impedire che il mittente spedisca dati più velocemente
di quanto il destinatario sia in grado di gestirli. Spesso si
usano meccanismi basati sull'esplicita autorizzazione, data da
parte del destinatario al mittente, di inviare un ben preciso
numero di frame.
Vedremo ora le caratteristiche di diversi protocolli, di complessità
crescente, per il livello data link.
Prima però dobbiamo fare alcune assunzioni:
Nei nostri esempi, la struttura di un frame è questa:
I campi del frame hanno le seguenti funzioni:
| kind | servirà a distinguere il tipo di frame (contiene dati, è solo di controllo, ecc.) |
| seq | contiene il numero progressivo del frame |
| ack | contiene informazioni legate all'acknowledgement |
| info | contiene un pacchetto di livello network completo (comprendente quindi le informazioni di controllo di tale livello). |
Naturalmente, i vari algoritmi useranno via via un numero maggiore
di tali informazioni.
3.3.1) Protocollo 1: Heaven |
Questo protocollo, per canale simplex, è molto semplice ed è basato sulle ipotesi (non realistiche) che:
Il protocollo consiste di due procedure, relative rispettivamente
al mittente e al destinatario.
Mittente (loop infinito):
1) attende un pacchetto dal livello network; 2) costruisce un frame dati; 3) passa il frame al livello fisico; 4) torna ad 1). |
Destinatario (loop infinito):
1) attende evento:
* arriva frame da livello fisico:
2) estrae pacchetto;
3) lo passa al livello network;
4) torna ad 1).
|
3.3.2) Protocollo 2: Simplex Stop and Wait |
Rilasciamo l'ipotesi (poco realistica) che
esista un buffer infinito nel ricevitore. Tutte le altre rimangono,
incluso il fatto che il traffico dati viaggia in una sola direzione.
La novità è che il mittente deve essere opportunamente
rallentato. Ciò però non si può fare con
ritardi prefissati: sarebbe troppo gravoso, perché questi
dovrebbero essere calibrati sul caso pessimo, che non sempre si
verificherà.
La soluzione consiste nell'invio, da parte del destinatario, di
una esplicita autorizzazione all'invio del prossimo frame. Questo
tipo di protocolli, nei quali il mittente attende un OK dal destinatario,
si chiamano stop and wait.
Mittente (loop infinito):
1) attende un pacchetto dal livello network;
2) costruisce un frame dati;
3) passa il frame al livello fisico;
4) attende evento:
* arriva frame di ack (vuoto):
5) torna ad 1).
|
Destinatario (loop infinito):
1) attende evento:
* arriva frame dati da livello fisico:
2) estrae il pacchetto;
3) consegna il pacchetto al livello network;
4) invia un frame di ack (vuoto) al mittente;
5) torna ad 1).
|
Si noti che, sebbene il traffico dati viaggi in una sola direzione,
i frame viaggiano in entrambe, dunque ci vuole un canale almeno
half-duplex (c'è alternanza stretta nelle due direzioni).
3.3.3) Protocollo 3: simplex per canale rumoroso |
Assumiamo ora che il canale possa fare errori.
I frame (dati o di ack) possono essere danneggiati o persi completamente.
Se un frame arriva danneggiato, l'HW di controllo del checksum
se ne accorge e informa il SW di livello data link; se il frame
si perde del tutto, ovviamente, la cosa non si rileva.
L'aggiunta di un timer al protocollo 2) può bastare? Cioé,
è adeguato uno schema quale il seguente?
Questo semplice schema in realtà non basta, infatti può verificarsi la seguente sequenza di eventi:
E' necessario che il destinatario possa riconoscere gli eventuali
doppioni. Ciò si ottiene sfruttando il campo seq
dell'header, dove il mittente mette il numero di sequenza del
frame dati inviato.
Notiamo che basta un bit per il numero di sequenza, poiché
l'unica ambiguità in ricezione è tra un frame ed
il suo immediato successore (siano ancora in stop and wait): infatti,
fino a che un frame non viene confermato, è sempre lui
ad essere ritrasmesso, altrimenti è il suo successore.
Dunque, sia mittente che destinatario useranno, come valori per i numeri di sequenza, la successione
...01010101...
Il mittente trasmette i frame dati alternando zero ed uno nel
campo seq; passa a trasmettere il prossimo frame solo quando riceve
l'ack di quello precedente.
Il destinatario invia un frame di ack per tutti quelli ricevuti
senza errori, ma passa al livello network solo quelli con il numero
di sequenza atteso.
Per quanto riguarda le possibilità che i frame dati arrivino
rovinati o non arrivino affatto, un meccanismo basato su timer
va bene, bisogna però che esso sia regolato in modo da
permettere sicuramente l'arrivo dell'ack, pena la ritrasmissione
errata di un duplicato del frame, che può creare grossi
guai (vedremo in seguito).
Protocolli come questo, in cui il mittente aspetta un ack di conferma
prima di trasmettere il prossimo frame, si chiamano PAR
(Positive Ack with Retransmission) o ARQ
(Automatic Repeat Request).
Mittente (loop infinito; [seq] rappresenta il campo seq di un frame):
0) n_seq = 0;
1) n_seq = 1 - n_seq;
2) attende un pacchetto dal livello network;
3) costruisce frame dati e copia n_seq in [seq];
4) passa il frame dati al livello fisico;
5) resetta il timer;
6) attende un evento:
* timer scaduto: torna a 4)
* arriva frame di ack (vuoto) non valido: torna a 4)
* arriva frame di ack (vuoto) valido: torna ad 1)
|
Destinatario (loop infinito; [seq] rappresenta il campo seq di un frame):
0) n_exp = 1;
1) attende evento;
* arriva frame dati valido da livello fisico:
2) se ([seq] == n_exp)
2.1) estrae pacchetto
2.2) lo consegna al livello network
2.3) n_exp = 1 - n_exp
3) invia frame di ack (vuoto)
4) torna ad 1)
* arriva frame non valido: torna ad 1)
|
In sintesi:
...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.
...0,1,0,1....
I disegni seguenti illustrano varie eventualità che possono verificarsi durante il dialogo secondo il protocollo 3. I numeri ai lati delle figure indicano i numeri di sequenza che, rispettivamente:
In assenza di errori il funzionamento è il seguente:
Nel caso in cui un frame dati si perda o si danneggi, la situazione
è la seguente:
Nel caso in cui invece si perda o si danneggi un frame di ack,
la situazione è la seguente:
Un problema importante è legato, come abbiamo già
accennato, alla lunghezza del timeout. Se esso è troppo
breve, può succedere questo:
Nell'esempio, i frame dati (x+1) e (x+2) si perdono (nel senso
che non vengono consegnati al livello network) e nessuno se ne
accorge.
D'altronde, se cambiamo il protocollo mandando un frame di ack
solo per i frame dati che non sono duplicati, ci si può
bloccare:
