Trasferimento affidabile dei dati

Per realizzare un trasferimento affidabile dei dati, è necessario implementare un canale sicuro al cui interno non vengano perse o corrotte informazioni.

Tuttavia, un canale fisico che possa svolgere tale funzione risulta essere irrealizzabile. Per tale motivo, la complessità del protocollo di trasferimento dati affidabile (RDT - Reliable Data Transfer) dipende fortemente dalle caratteristiche del canale inaffidabile utilizzato.

Inoltre, è necessario puntualizzare che il mittente e il destinatario non conoscono lo stato l’uno dell’altro (es: se la ricezione sia andata a buon fine), a meno che non gli venga comunicato tramite un ulteriore messaggio.

Il protocollo RDT presenta delle interfacce per il suo utilizzo:

• rdt_sent(data): il quale viene chiamato dal livello di applicazione e il cui argomento corrisponde ai dati da inoltrare al destinatario
• udt_send(): dove UDT è acronimo di Unreliable Data Transfer, il quale viene chiamato dal protocollo RDT sul mittente per trasferire il pacchetto sul canale inaffidabile
• rdt_rcv(): il quale viene chiamato alla ricezione del pacchetto dal destinatario
• deliver_data(): il quale viene chiamato dal protocollo RDT sul destinatario per inoltrare al livello di applicazione i dati ricevuti

Poiché i dispositivi comunicanti non sono a conoscenza dello stato altrui, il protocollo RDT si basa su un trasferimento dei dati unidirezionale, dunque come se uno solo dei due sia il mittente ed uno solo sia il destinatario (sebbene in realtà sia bidirezionale). Per rappresentare le operazioni e le decisioni effettuate dal protocollo, utilizzeremo le macchine a stati finiti (FSM - Finite State Machine) e in particolare la seguente notazione:

Protocollo RDT 1.0 e 2.0

Protocollo RDT 1.0 e 2.0

All’interno del protocollo RDT 1.0, viene assunto che il canale sottostante utilizzato per il trasferimento sia perfettamente affidabile, implicando che il mittente invii i dati nel canale e il ricevitore li legga direttamente, senza alcuna operazione aggiuntiva

Nel protocollo RDT 2.0, invece, viene assunto che il canale sottostante possa invertire alcuni bit nel pacchetto inviato. Analogamente al protocollo UDP, viene utilizzato un checksum per rilevare la presenza di errori. Nel caso in cui venga rilevato uno di quest’ultimi, il destinatario comunicherà al mittente l’esito dell’operazione:

• Acknowledgements (ACK), dove il destinatario dice esplicitamente al mittente che il pacchetto è stato ricevuto senza problemi .
• Negative acknowledgements (NAK), dove il destinatario dice esplicitamente al mittente che il pacchetto ricevuto presenta degli errori. Successivamente all’invio di un pacchetto, il mittente rimane in attesa della risposta del destinatario (meccanismo stop and wait)

Se la risposta ricevuta è un ACK, il mittente torna il stato di attesa del prossimo pacchetto da parte del livello applicativo.

Se invece la risposta è un NAK, il mittente rinvia il pacchetto generante l’errore e rimane in attesa della risposta del destinatario, ripetendo nuovamente tale processo nel caso in cui si riceva nuovamente un NAK.

Tuttavia, la versione 2.0 del protocollo RDT presenta un difetto fatale: se la risposta ACK/NAK è corrotta, il mittente non è più a conoscenza di cosa sia accaduto al destinatario. Inoltre, non è sufficiente ritrasmettere il pacchetto per risolvere tale difetto, poiché il destinatario potrebbe ricevere due pacchetti duplicati ed inoltrarli al livello di applicazione.

Link to original

Protocollo RDT 2.1 e 2.2

Protocollo RDT 2.1

Per risolvere il difetto fatale della versione 2.0, il protocollo RDT 2.1:

• Viene controllato se la risposta ACK/NAK sia corrotta. Nel caso in cui lo sia, il pacchetto viene rinviato.
• Il destinatario non è a conoscenza della possibile corruzione del pacchetto ACK/-NAK
• Viene aggiunto un numero di sequenza al pacchetto inviato. In particolare, sono necessari i numeri di sequenza 0 ed 1 affinché il protocollo stop and wait possa funzionare correttamente:
  • Assieme alla risposta di ACK, il destinatario invia un numero di riscontro, il quale, per convenzione, indica sempre il numero di sequenza del prossimo pacchetto atteso dal destinatario.
  • Se il destinatario ha ricevuto correttamente il pacchetto 0, invia un riscontro con valore 1 (dunque il prossimo pacchetto atteso è il pacchetto 1)
  • Analogamente, se il destinatario ha ricevuto correttamente il pacchetto 1, invia un riscontro con valore 0 (dunque il prossimo pacchetto atteso è il pacchetto 0)
• Se il pacchetto ricevuto dal destinatario è un duplicato, esso viene automaticamente scartato senza essere inviato al livello di applicazione

Mittente:

Destinatario:

Protocollo RDT 2.2

In aggiunta alle modifiche della versione 2.1, il protocollo RDT 2.2 elimina la necessità di una risposta NAK: il ricevitore invia come numero di riscontro il numero di sequenza dell’ultimo pacchetto correttamente. In tal modo, un ACK duplicato al mittente comporta la stessa azione di un NAK, ossia la ritrasmissione del pacchetto corrente.

Link to original

Protocollo RDT 3.0

Oltre all’assunzione di possibili bit invertiti, il protocollo RDT 3.0 assume la possibilità di una perdita di pacchetti, sia dati che ACK. Per risolvere tale problematica, il mittente attende un lasso di tempo:

• Il destinatario deve specificare il numero di sequenza del pacchetto per il quale sta inviando un ACK
• Se non viene ricevuto alcun ACK allo scadere del lasso di tempo, il pacchetto dati (che indicheremo con pkt) viene ritrasmesso
• Se pkt o ACK arrivano successivamente allo scadere del tempo, il pacchetto verrà ritrasmesso, implicando che la trasmissione verrà duplicata (problema già gestito dai numeri di sequenza) La FSM associata al mittente corrisponde a:

Attenzione:

Tuttavia, in cambio dei notevoli benefici del meccanismo stop and wait, le prestazioni del protocollo RDT 3.0 risultano essere infime, limitando le prestazioni dell’infrastruttura sottostante, ossia il canale.

In particolare, la percentuale di utilizzo Umit della comunicazione da parte del mittente, ossia la frazione di tempo in cui il mittente è impegnato nell’invio corrisponde a:

$U_{mit}=\frac{D_t}{RTT+D_t}$

dove $D_t$ è il delay di trasmissione (dunque $D_t=\frac{L}{R}$ con L la lunghezza del pacchetto e R il transmission rate del link).

Esempio

Considerando un link avente un rate pari a R = 1 Gb/s, una lunghezza di pacchetto pari a L = 8000 b e un ritardo di propagazione sia pari a 15 ms, la percentuale di utilizzo del mittente corrisponde a: $D_t=\frac{8\cdot 10^{3}b}{10^{9}b/s}=8\mu s$ $U_{mit}=\frac{8\mu s}{30ms+8\mu s}=27\cdot 10^{-5}=0.027\%$

Link to original