Introduzione alle reti telematiche/Protocolli a finestra

I protocolli a finestra sono dei protocolli, utilizzati in vari livelli nella gerarchia OSI, che servono per recuperare gli errori:

• FEC: si tenta di correggere l'errore;
• ARQ: viene richiesta la ritrasmissione dei dati.

FEC

Il FEC è utile per esempio nelle applicazioni real-time dove la ritrasmissione arriverebbe troppo tardi, o nel caso di una sonda lontana dalla Terra dove la ritrasmissione richiederebbe troppo tempo. Il FEC non garantisce però che l'informazione venga ricostruita in maniera corretta.

Esempi di protezione dagli errori

• bit di parità: rileva ma non corregge errori singoli, non rileva due errori;
• codice a ripetizione: i bit vengono mandati più volte e poi viene scelta la sequenza ricevuta il maggior numero di volte → molta affidabilità ma spreco di banda;
• parità di riga e colonna: rileva e corregge errori singoli.

I codici di protezione dagli errori si inseriscono tipicamente nelle intestazioni dei pacchetti. Può venire protetta la PCI, la SDU o l'intera PDU; è importante proteggere almeno l'intestazione. I codici CRC sono dei codici di protezione dagli errori che vengono calcolati in modo molto veloce.

I bit di parità:

• nel FEC vengono usati anche per correggere l'errore;
• nell'ARQ si limitano a rilevare l'errore.

ARQ

Nell'ARQ oltre ai bit di parità si introducono nella PCI anche dei bit di numerazione che permettono di ricostruire la sequenza di pacchetti.

Stop and wait

1. inizializzazione: il trasmettitore e il ricevitore si sincronizzano per avere lo stesso valore;
2. il trasmettitore, dopo averne fatto una copia, invia la PDU al ricevitore con numero d'ordine pari al suo valore;
3. il ricevitore quando riceve la PDU:
   1. ne verifica l'integrità attraverso i codici di controllo;
   2. verifica di aver ricevuto il pacchetto con il corretto numero d'ordine;
   3. se la PDU è corretta, rispedisce indietro una PCI detta ACK per confermare la ricezione e per richiedere il pacchetto con numero d'ordine successivo, incrementando il proprio valore interno;
   4. se la PDU è quella attesa, inoltra l'informazione all'applicativo utente;
4. il trasmettitore quando riceve la PDU:
   1. verifica l'integrità della PCI;
   2. verifica il numero d'ordine;
   3. invia il pacchetto con numero d'ordine successivo, incrementando il proprio valore interno.

Se il trasmettitore non riceve l'ACK entro un tempo prestabilito, ripete la trasmissione.

Piggybacking

Nel caso di flussi di informazione bidirezionali, la PDU di riscontro viene anche sfruttata per l'invio di altri dati.

Criticità

È difficile trovare il giusto valore del timeout, che deve essere idealmente di poco superiore all'RRT:

• se è troppo breve, il trasmettitore invia molti pacchetti duplicati;
• se è troppo lungo, in caso di pacchetto perso si spreca molto tempo.

Si riducono le possibilità di malfunzionamento usando:

• un maggior numero di bit per la numerazione;
• un tempo di vita massimo per le PDU e gli ACK, oltre il quale il pacchetto si "suicida".

Alternating bit protocol

La numerazione delle PDU è indispensabile, perché il trasmettitore deve capire precisamente qual è l'ultimo pacchetto che è arrivato al ricevitore. Se però si trasmettono tanti pacchetti, i numeri d'ordine diventerebbero molto grandi.

L'alternating bit protocol cerca di ovviare al problema prevedendo un unico bit per la numerazione, e alterna bit 0 e bit 1.

Su una rete non sequenziale questo protocollo non è affidabile, perché ogni pacchetto può essere instradato in una strada diversa più o meno lunga, e può verificarsi la perdita di pacchetti in determinati casi dovuti ad ACK vaganti:

Numerazione modulo 4

I pacchetti sono nominati da 0 a 3. Anche aumentando il numero di bit in un canale non sequenziale il protocollo potrebbe addirittura entrare in un loop:

Prestazioni

In generale le prestazioni sono limitate a causa dei tempi di attesa degli ACK.

Selective repeat

Il selective repeat cerca di ottimizzare le prestazioni dello stop and wait: il trasmettitore è in grado di gestire l'invio consecutivo di pacchetti senza dover aspettare ogni volta l'ACK:

Trasmissione

Si definisce finestra di trasmissione W_T il numero massimo di PDU che il trasmettitore è autorizzato ad inviare in sequenza senza aver ricevuto riscontro (ACK).

Tutti i pacchetti all'interno della finestra di trasmissione W_T, dopo essere stati memorizzati, vengono inviati consecutivamente dal trasmettitore.

La finestra di trasmissione non può essere maggiore dell'intervallo finito di valori che può assumere il numero d'ordine.

Ricezione

Si definisce finestra di ricezione W_R il numero massimo di PDU fuori sequenza che il ricevitore è disposto a tollerare, oltre il quale la PDU viene scartata:

Il ricevitore quando riceve una PDU:

1. ne controlla la correttezza e il numero di sequenza;
2. se la PDU non è corretta o non rientra nella finestra di ricezione la ignora, altrimenti:

1. invia la conferma di ricezione (ACK);
2. se la PDU è la prima della sequenza la consegna ai livelli superiori, altrimenti attende le precedenti.

Il ricevitore accetta tutti i pacchetti della finestra di ricezione, anche se arrivano completamente fuori sequenza. Tutti i pacchetti ricevuti al di fuori della finestra di ricezione vengono scartati. Ad esempio, se la finestra di ricezione è pari a 2, e l'ultimo pacchetto ricevuto è il pacchetto n-esimo:

• se arriva per primo il pacchetto n+1-esimo, tutto ok e la finestra di ricezione trasla;
• se arriva per primo il pacchetto n+2-esimo, il ricevitore lo accetta e rimane in attesa del pacchetto n+1-esimo;
• se arriva per primo il pacchetto n+3-esimo (o successivo), il ricevitore lo scarta.

ACK

Il ricevitore, quando riesce a completare una certa sequenza, invia un ACK che informa dell'ultimo pacchetto ricevuto in sequenza, quindi invia la sequenza ai livelli superiori.

Esistono 3 tipi di ACK:

• ACK individuale (o selettivo): ACK(n) significa "ho ricevuto il pacchetto n":

svantaggio: per ogni pacchetto ricevuto si deve mandare un ACK → molto traffico nella rete;

• ACK cumulativo: ACK(n) significa "ho ricevuto tutto fino a n escluso":

svantaggio: se viene perso solo uno dei primi pacchetti della finestra, il trasmettitore ritrasmette oltre al pacchetto perso anche gli altri pacchetti successivi nella sequenza che in realtà sono già stati ricevuti;

• ACK negativo (NAK): NAK(n) significa "ritrasmetti il pacchetto n":

vantaggio: è utile quando la finestra è molto ampia, o la probabilità di perdita di un pacchetto non è troppo alta.

Trasmettitore e ricevitore si devono accordare preventivamente sulla semantica degli ACK.

Il timeout è unico per la finestra di trasmissione: se scade il timeout prima dell'arrivo di tutte conferme, il trasmettitore ripete la trasmissione delle PDU non ancora confermate.

Il trasmettitore si accorge della perdita di pacchetti con la ricezione di ACK duplicati. Quando il pacchetto i-esimo va perso o è in ritardo, il ricevitore continua ad avvisare che l'ultimo pacchetto ricevuto è stato il pacchetto i−1-esimo. Quando il trasmettitore riceve due volte lo stesso ACK, si accorge che c'è stato o un ritardo o una perdita del pacchetto. Se ritrasmettesse subito il pacchetto, ciò sarebbe svantaggioso nel caso in cui il pacchetto sia solamente in ritardo e arrivi subito dopo perché aumenta inutilmente il traffico in rete → conviene ritrasmettere il pacchetto solo dopo un certo numero, maggiore di 2, di ACK duplicati (il TCP per esempio ne prevede 3). Il selective repeat è efficace perché quando finalmente arriva il pacchetto i-esimo, il ricevitore può mandare subito un ACK e comunicare al trasmettitore il pacchetto fino a quale è arrivato a ricevere tra quelli successivi al pacchetto i-esimo: il trasmettitore così non deve ritrasmettere tutti i pacchetti successivi dall'i+1-esimo in poi.

La numerazione delle PDU è ciclica: dati k bit, giunti all'ultimo numero rappresentabile (2^k) si ritorna allo 0. Per evitare ambiguità:

$W_{\mathrm {T} }+W_{\mathrm {R} }\leq 2^{k}$

Se questa condizione non viene rispettata potrebbero verificarsi degli errori. Ad esempio, se W_T = 3, W_R = 2, k = 2:

Prestazioni

In assenza di pacchetti persi, il throughput si calcola come:

$\min {\left\{{\frac {\text{finestra trasmissione (bit)}}{\text{RTT (s)}}},\,{\text{velocit}}{\grave {\text{a}}}{\text{ di linea}}\right\}}$

Pertanto accorciando la distanza tra il ricevitore e il trasmettitore, ovvero riducendo il RTT, si possono ottenere prestazioni migliori, anche se aumenta il throughput, cioè il traffico sulla rete.

Go back N

Nel selective repeat, la finestra di trasmissione e la finestra di ricezione sono entrambe maggiori di 1 e di solito di pari dimensione. Invece, nel go back N la finestra di ricezione W_R ha sempre dimensione pari a 1 → il ricevitore può ricevere solamente pacchetti in sequenza, perché tutti i pacchetti fuori sequenza vengono scartati.

Fissata una finestra di trasmissione W_T:

1. configurazione vietata: la finestra di trasmissione non trasla finché tutti i pacchetti sono stati ricevuti;
2. nessuno dei pacchetti trasmessi è stato ricevuto;
3. è stato ricevuto il pacchetto 1, ma la sua ACK è andata persa;
4. tutti i pacchetti sono stati ricevuti, ma tutte le ACK sono andate perse;
5. configurazione vietata: il ricevitore aspetta un pacchetto che il trasmettitore non è abilitato a trasmettere.

Rispetto allo stop and wait, nel go back N il trasmettitore diventa più complesso perché sono necessari degli algoritmi per la gestione dei pacchetti. Al lato ricevitore:

• ACK individuali: la gestione è molto semplice: se un pacchetto viene perso, è solo il trasmettitore a dover accorgersi di non avere ricevuto il suo ACK;
• ACK cumulativi: siccome l'ACK viene mandato dopo la ricezione non di un singolo pacchetto ma di un gruppo di pacchetti, è necessario un clock che stabilisca il timeout quando l'attesa di uno dei pacchetti diventa troppo lunga.

Il go back N si comporta come il selective repeat in termini di velocità di trasmissione (throughput) e di occupazione del canale.