Reti di calcolatori:Protocolli a finestra

Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 3. Protocolli a finestra.

2. OSI	Reti di calcolatori	4. Livello 1 OSI

Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

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

• FEC (Forward Error Correction): si tenta di correggere l'errore;
• ARQ (Automatic Retransmission reQuest): 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

• 9 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;
• 10 parità di riga e colonna: rileva e corregge errori singoli.

11 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.

12 I bit di parità:

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

ARQ

13 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

58 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.

Alternating bit protocol

33 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.

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

44 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

49 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:

---

49 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".

Prestazioni

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

Go back N

50 Il go back N cerca di ottimizzare le prestazioni dello stop and wait: nel tempo che il trasmettitore attende l'ACK del primo pacchetto, continua a inviare i pacchetti successivi:

Finestre

Finestra di trasmissione

51 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).

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

Finestra di ricezione

52 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 buttata via:

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.

59 Fissata una finestra di trasmissione W_T, seguono le possibili posizioni di una finestra di ricezione W_R unitaria:

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

---

55 Il trasmettitore invia fino a W_T PDU, dopo aver fatto la copia di ognuna. 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.

56 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;
2. se la PDU è la prima della sequenza la consegna ai livelli superiori, altrimenti attende le precedenti.

ACK

57 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.

62 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.

Selective repeat

63-64 Nel selective repeat, il ricevitore può richiedere selettivamente le PDU che non ha ricevuto. A differenza del go back N, la finestra di trasmissione e quella di ricezione sono entrambe maggiori di 1 e di solito di pari dimensione. 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.

65 Il trasmettitore ha un unico clock per le W_T PDU, e quando scade il timeout reinvia tutte le PDU di cui non ha ricevuto la conferma.

67 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.

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 al 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.

61 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}$

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

Prestazioni

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

72 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\}}$

73 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.

2. OSI	Reti di calcolatori	4. Livello 1 OSI