Il livello Trasporto.

Bibliografia:
Computer Networking. Cap. 3. Autori: James F. Kurose (University of Massachusetts, Amherst) Keith W. Ross (Polytechnic Institute of NYU).

Tecniche Automatic Retransmission reQuest

La tecnica Stop and Wait in un Protocollo di trasporto affidabile

L'ultima versione del protocollo di trasporto, vista nella sezione precedente, è corretta e funzionante, ma è molto difficile che qualcuno sia soddisfatto delle sue prestazioni, anche in considerazione dell'alta velocità delle moderne reti. L'inefficienza è provocata dalla tecnica stop-and-wait.

Il protocollo è affidabile grazie agli elementi fondamentali di cui si serve: il Checksum, i numeri di sequenza, i timer, e le conferme positive e negative, ma il meccanismo di stop-and-wait introduce dei tempi di inattività del mittente. Si considerino due sistemi terminali separati da una grande distanza. Si assuma che il tempo di propagazione del segnale lungo il canale che li collega sia di 15 ms. La capacità del canale sia di 1 Gb/s. Con un pacchetto di lunghezza 1KB il tempo necessario alla trasmissione è

t = (8000 bit) / 10⁹ bit/s = 8µs.

Con l'adozione della tecnica stop and wait, se il mittente spedisce il pacchetto al tempo t = 0, dopo t = 8 µs l'ultimo bit del pacchetto trasmesso entra nel canale. Il pacchetto viaggia lungo il canale, impiegando 15 ms per raggiungere il ricevitore. Al tempo t = 15.008 ms l'ultimo bit del pacchetto viene acquisito dal ricevitore. Ammettendo che il ricevitore invii immediatamente il pacchetto ACK e che questo sia della stessa lunghezza di un pacchetto dati, l'ultimo bit del pacchetto ACK entra nel sistema terminale al lato del trasmettitore a t=30.016 ms. In questo intervallo di tempo di 30.016 ms, il mittente è stato impegnato (per la trasmissione del pacchetto dati e per la ricezione del pacchetto ACK) solo 0.016 ms. Se si definisce l'utilizzazione del canale come la frazione del tempo che il mittente impiega per trasmettere, da questo esempio, risulta che il coefficiente di utilizzazione del canale è 0.008/30.016 = 0.0002. Cioè il mittente usa solo lo 0.02% del tempo per trasmettere. In modo equivalente si può dire che il mittente ha inviato 1KB (8000 bit) in 30.016 ms che corrisponde ad un flusso di (8000/0.030016 =) 266Mb/s = 33KB/s. Si ha un chiaro sottoutilizzo della capacità di 1 Gb/s del canale. Il ritardo di un pacchetto non dipende solo dal tempo di propagazione del segnale, ma anche dai ritardi trascorsi nelle code dei sistemi intermedi e per l'instradamento del pacchetto.

Allo scopo di migliorare le prestazioni del protocollo, la tecnica stop and wait può essere modificata per consentire al trasmettitore di inviare più di un pacchetto senza aspettare le conferme. La rappresentazione dei pacchetti in transito sul canale dal trasmettitore al ricevitore assomiglia ad un nastro trasportatore, per cui questa variante della tecnica è denominata pipelining. Le conseguenze di questa tecnica in un protocollo affidabile sono:

Il numero di bit riservati a contenere i numeri di sequenza deve essere aumentato, perchè ci sono più pacchetti trasmessi, ognuno con un proprio numero di sequenza, e ciascuno di questi richiede la conferma.
Il mittente e il ricevitore potrebbero avere la necessità di memorizzare, in un buffer, uno o più pacchetti. Come minimo il mittente deve avere la capacità di memorizzare i pacchetti trasmessi per i quali aspetta la conferma, in modo che in assenza di questa potrà ritrasmetterli. Anche il ricevitore ha la stessa necessità di memorizzare i pacchetti, ma per motivi che saranno chiariti in seguito.
Le decisioni sulla scelta del numero di bit riservati a rappresentare il numero di sequenza e il calcolo della dimensione del buffer dipende dal modo in cui il protocollo gestisce gli errori o la perdita di pacchetti

Il pipelining suggerisce due varianti alla tecnica Stop and wait: Go-Back-N e Selective Repeat.

Go Back N

Vedi simulazione

La tecnica Go-Back-N (GBN) consente al mittente di inviare fino ad un massimo di N pacchetti e restare in attesa delle conferme. Il numero N di pacchetti che possono rimanere in attesa di conferma è determinato dal numero di bit assegnato al campo contatore nel pacchetto.

Il mittente usa una variabile, la si indichi con base, per mantenere il numero di sequenza del più vecchio pacchetto non confermato e la variabile nextseqnum per mantenere il numero di sequenza del prossimo pacchetto da trasmettere, allora si individuano quattro intervalli dei numeri di sequenza:

I numeri di sequenza nell'intervallo [0, base-1] corrispondono ai pacchetti trasmessi e confermati.
L'intervallo [base, nextseqnum-1] corrisponde ai pacchetti trasmessi ma non confermati.
I numeri di sequenza nell'intervallo [nextseqnum, base+N-1] possono essere assegnati ai prossimi pacchetti che trovano posto nel buffer di trasmissione.
Infine i numeri di sequenza maggiori o uguali di base+N non si possono usare fino a quando non giunge la conferma di un pacchetto presente nel buffer di trasmissione (il pacchetto con numero di sequenza base che, essendo confermato, viene eliminato e lascia posto ad un nuovo pacchetto).

Il range dei numeri dei pacchetti trasmessi e non ancora confermati è detto finestra di dimensione N sul range dei numeri di sequenza. Mentre la comunicazione avanza, la finestra scorre sullo spazio dei numeri di sequenza. Il protocollo adesso viene denominato a finestra scorrevole. I numeri di sequenza vengono inseriti nell'intestazione del pacchetto all'interno di un campo di dimensione prefissata. Se k è il numero di bit riservati al numero di sequenza, il range è [0, 2^k-1]. Tutte le operazioni aritmetiche sono svolte in modulo 2^k. (cioè in questa aritmetica dopo 2^k-1 c'è 0).

Comportamento del trasmettitore:
Prima di avviare la trasmissione, il mittente crea due variabili e assegna i valori iniziali:

base = 1
nextseqnum = 1

La dimensione N della finestra si suppone predefinita.
Gli eventi che devono essere gestiti dal protocollo sono i seguenti:

il livello applicazione consegna al protocollo di trasporto un messaggio da consegnare al ricevitore, il protocollo svolge le seguenti azioni:

        se (nextseqnum < base+N) {
          calcola il checksum e lo inserisce nell'header del pacchetto.
          inserisce il valore di nextseqnum  nell'header del pacchetto.
          completa il pacchetto con il messaggio da consegnare
          se (base == nextseqnum) cioè se la finestra è vuota, avvia il timer
          nextseqnum++
        } else {
          se la finestra è piena) rifiuta il messaggio
        }

si verifica il timeout

        ritrasmette il pachetto con numero di sequenza base,
        ritrasmette il pachetto con numero di sequenza base+1,
        …
        ritrasmette il pachetto con numero di sequenza nextseqnum-1

viene ricevuto un pacchetto ACK, cioè un pacchetto di conferma.

        controlla il checksum. Risulta che il pacchetto è integro.
        aggiorna la variabile base = (numero del pacchetto confermato)+1
        se (base == nextseqnum)
          ferma il timer
        else
          avvia il timer

viene ricevuto un pacchetto

        controlla il checksum risulta che il pacchetto ha subito degli errori.
        scarta il pacchetto.

Comportamento del ricevitore:
il ricevitore, dopo aver aperto la connessione, crea una variabile e le assegna il valore iniziale.

    numeroSeqAtteso = 1

gli eventi che deve trattare il ricevitore sono:

riceve un pacchetto

       controlla il checksum. risulta che il pacchetto è integro.
       controlla se il numero di sequenza del pacchetto ricevuto è uguale al numero di sequenza atteso.
       estrae il messaggio e lo consegna al livello applicazione
       numeroSeqAtteso++
       invia un pacchetto di conferma

riceve un pacchetto errato o fuori sequenza

       ripete la conferma inviando un ACK contenente il campo numero di sequenza = numeroSeqAtteso

Il protocollo deve essere in grado di rispondere a tre tipi di eventi:

Invocazione dai livelli superiori. un processo del livello applicazione richiama send(), il mittente controlla se la finestra è piena, cioè se ci sono N pacchetti trasmessi che aspettano la conferma. Se la finestra non è piena il pacchetto viene creato e spedito, e vengono anche aggiornate le appropriate variabili. Se la finestra è piena il mittente fornisce un'indicazione al livello superiore il cui significato dovrebbe essere che l'operazione non può essere eseguita al momento, e bisognerà riprovare. In una situazione reale il mittente dovrebbe regolare l'accesso al buffer tramite un meccanismo di sincronizzazione (problema del produttore e del consumatore), che dovrebbe consentire al processo del livello applicazione di essere informato quando la finestra non è piena.
Ricezione di un ACK. La conferma di un pacchetto con numero di sequenza n rappresenta una conferma cumulativa, indica cioè che tutti i pacchetti con numero di sequenza minore di n sono stati ricevuti correttamente.
Timeout. Il nome "Go-Back-N", dato alla tecnica, deriva dal comportamento del mittente in presenza di pacchetti persi o di pacchetti in ritardo. Come nella tecnica stop-and-wait, si usa un timer per segnalare lo stato "pacchetto o conferma persa". Quando si verifica un timeout, il mittente ritrasmette tutti i pacchetti in attesa di conferma. Un solo timer è stato avviato al momento della spedizione del più vecchio pacchetto trasmesso, quando viene ricevuto un ACK ma il buffer contiene ancora pacchetti in attesa di conferma il timer viene riavviato, se il buffer è vuoto il timer viene fermato.

Con la tecnica GBN, le azioni svolte dal mittente e dal ricevitore sono: se il ricevitore acquisisce correttamente un pacchetto con numero di sequenza n ed è in ordine, cioè l'ultimo messaggio consegnato al livello superiore era contenuto in un pacchetto con numero di sequenza n-1, il ricevitore invia un ACK per il pacchetto n e consegna il messaggio contenuto nel pacchetto al livello superiore. In ogni altro caso il ricevitore scarta il pacchetto e ritrasmette un ACK per il pacchetto più recentemente ricevuto in ordine. Notare che, poichè i pacchetti vengono consegnati uno alla volta al livello superiore, se è stato ricevuto e consegnato il pacchetto k, significa che tutti i pacchetti con numero di sequenza minore di k sono stati consegnati (conferma cumulativa).

Nel protocollo che adotta la tecnica GBN il ricevitore scarta i pacchetti fuori ordine. Un pacchetto ricevuto correttamente, ma non in ordine, viene scartato. Questo comportamento sembra inefficiente, ma la ragione è che il ricevitore deve consegnare i messaggi in ordine al livello superiore. Se il ricevitore è in attesa del pacchetto n ma riceve il pacchetto n+1, deve memorizzare il pacchetto n+1 e consegnarlo al livello superiore solo dopo aver ricevuto e consegnato il pacchetto n. Ma, come conseguenza della regola di trasmissione del mittente, se il pacchetto n si perde, verranno ritrasmessi entrambi. In questo modo la gestione del buffer del ricevitore, non richiede che i pacchetti vengano ordinati. Così, mentre il mittente deve ricordare i limiti superiore ed inferiore della sua finestra e la posizione di nextseqnum all'interno della finestra, la sola informazione che il ricevitore deve mantenere è il numero di sequenza del prossimo pacchetto (in ordine). Questo valore viene mantenuto in una variabile denominata, ad esempio, numeroSeqAtteso. In particolare, il destinatario non deve riservare spazio per il buffer di ricezione in cui conservare i pacchetti fuori ordine, in attesa di quelli precedenti. Naturalmente c'è lo svantaggio che se viene scartato un pacchetto corretto e la ritrasmissione del pacchetto ha esito negativo, sarà richiesta un'ulteriore ritrasmissione.

La figura mostra le operazioni della tecnica Go Back N per il caso di una finestra di larghezza quattro pacchetti. Come conseguenza della limitazione di questa larghezza della finestra, il mittente invia i pacchetti da 0 a 3 e passa in attesa che uno o più pacchetti vengano confermati. Per ogni successivo ACK che viene ricevuto (ad esempio, ACK0 ed ACK1), la finestra del trasmettitore scorre e il mittente può trasmettere un altro pacchetto (ad esempio (pkt4 e pkt5). Al ricevitore non giunge il pacchetto 2 e quindi i pacchetti 3, 4, e 5 risultando fuori ordine saranno scartati. L'implementazione della tecnica Go Back N dovrebbe essere realizzata con procedure richiamate al verificarsi di certi eventi. Nella programmazione orientata agli eventi, le procedure vengono richiamate o da altre procedure o generando una interruzione. Nel mittente, gli eventi da trattare dovrebbero essere

una richiesta di servizio proveniente da un processo del livello applicazione che richiama send(),
una interruzione generata dal timer, e
una richiesta di servizio generata dal livello rete quando giunge un pacchetto.

Selective Repeat (SR)

Il protocollo Go Back N consente al trasmettitore di riempire la coda dei pacchetti uscenti riducendo l'inutilizzazione del canale osservata con la tecnica stop-and-wait. Comunque anche il protocollo Go Back N non garantisce buone prestazioni. In particolare, quando è elevata sia la larghezza della finestra che la velocità di trasmissione, la coda può contenere molti pacchetti. Un solo pacchetto intermedio errato provoca la ritrasmissione di tutti i pacchetti che lo seguono, molti dei quali introducono un traffico inutile se erano stati ricevuti senza errore. Come analogia si pensi che, dopo aver dettato un messaggio, la parola numero 1000 non viene capita: il trasmettitore deve ripetere tutte le 1000 parole.

La tecnica selective-repeat evita le ritrasmissioni inutili, il mittente deve ritrasmettere solo i pacchetti per i quali sospetta che possa essersi verificato un errore in ricezione. Alcuni pacchetti, cioè, o sono stati persi o sono stati alterati dal rumore. Questa ritrasmissione richiede che il ricevitore confermi singolarmente i pacchetti ricevuti senza errore. Anche per questa tecnica si usa una finestra di larghezza N, per limitare le dimensioni del buffer dei pacchetti trasmessi, in attesa di conferma. Ma a differenza della tecnica Go Back N il mittente può ricevere una conferma per qualsiasi pacchetto trasmesso.

Il ricevitore conferma qualsiasi pacchetto, anche se fuori ordine. I pacchetti fuori ordine resteranno in un buffer di memoria fino a quando saranno stati ricevuti tutti i pacchetti mancanti, cioè con numero di sequenza inferiore, a quel punto tutti i pacchetti possono essere consegnati in ordine al livello superiore.

Azioni del trasmettitore con la tecnica Selective Repeat

Dati ricevuti dal livello applicazione. Quando il processo di livello Trasporto dal lato del trasmettitore riceve dati dal processo del livello superiore controlla il prossimo numero di sequenza disponibile. Se il numero rientra nella finestra di trasmissione il dato viene inserito nel pacchetto e inviato, altrimenti viene memorizzato, oppure si chiede al livello superiore di attendere.
Timeout. Ogni volta che viene inviato un pacchetto, il trasmettitore imposta un timer per quel pacchetto. Al verificarsi del timeout, verrà ritrasmesso il pacchetto corrispondente. La generazione di un timer associato ad ogni pacchetto inviato richiede un particolare utilizzo software del solo timer hardware disponibile.
ACK ricevuto. Quando il trasmettitore riceve un ACK controlla che il numero del pacchetto sia interno alla finestra e marca il pacchetto come ricevuto. Se il numero di sequenza del pacchetto confermato è uguale a sendbase, la base della finestra è traslata sul prossimo pacchetto non confermato con il più piccolo numero di sequenza. Dopo aver spostato la finestra, se si trovano pacchetti in attesa di trasmissione con numero di sequenza interno alla finestra, questi pacchetti vengono trasmessi.

Azioni del Ricevitore con la tecnica Selective Repeat

Pacchetto ricevuto correttamente con numero di sequenza contenuto in [rcvbase, rcvbase+N-1]. In questo caso il pacchetto ricevuto rientra nella finestra del ricevitore e il ricevitore invia un pacchetto di conferma selettiva al trasmettitore. Se il pacchetto non era già stato ricevuto viene memorizzato. Se il numero di sequenza del pacchetto è uguale alla base della finestra del ricevitore (rcvbase), allora questo pacchetto e tutti quelli precedentemente memorizzati e con numerazione progressiva (a iniziare da rcvbase) vengono consegnati al livello superiore. La finestra del ricevitore scorre della quantità di pacchetti consegnati. Ad esempio, se il pacchetto con numero di sequenza rcvbase=2 viene ricevuto, questo e i pacchetti rcvbase+1 e rcvbase+2 possono essere consegnati al livello superiore.
Pacchetto ricevuto correttamente con numero di sequenza in [rcvbase-N, rcvbase-1]. In questo caso deve essere inviata una conferma, anche se il ricevitore aveva già confermato questo pacchetto.
In ogni altro caso, ignora il pacchetto.

La figura mostra un esempio di comunicazione con la tecnica selective repeat in cui si verifica la perdita del pacchetto 2. Notare che il ricevitore memorizza i pacchetti 3, 4, e 5, e li consegna tutti insieme solo dopo aver ricevuto correttamente il pacchetto 2.

È importante notare che il ricevitore, piuttosto che ignorarli, ripete la conferma dei pacchetti già ricevuti, il cui numero di conferma è inferiore alla base della finestra. Questa ripetizione è necessaria. Infatti se mancasse la conferma del pacchetto sendbase, dal ricevitore al trasmettitore, il mittente ripeterebbe quel pacchetto sendbase, anche se il ricevitore l'ha già acquisito. Se il ricevitore non confermasse questo pacchetto, la finestra del trasmettitore non traslerebbe mai. Questo è un aspetto importante del protocollo SR: Il mittente e il destinatario non hanno sempre la stessa visione di ciò che è stato ricevuto correttamente. e di ciò che non lo è. Le finestre del trasmettitore e del ricevitore non coincidono quasi mai.

La mancanza di sincronizzazione tra le finestre del mittente e del ricevitore ha importanti conseguenze sulla scelta dell'intervallo dei numeri di sequenza. Si esamini cosa succede se la numerazione dei pacchetti è modulo 4 (0, 1, 2 e 3), cioè vengono usati 2 bit per numerare i pacchetti, e la finestra ha larghezza 3. Si supponga che vengano trasmessi i pacchetti 0, 1 e 2. Il ricevitore li acquisisce correttamente e invia la conferma. A questo punto la finestra del ricevitore è stata traslata sui successivi tre pacchetti a cui corrispondono i numeri di sequenza 3, 0, 1. Si ipotizzino due casi. Nel primo caso si suppone che si perda l'ACK dei primi tre pacchetti e il trasmettitore, al timeout, ripete questi tre pacchetti. In questo modo il ricevitore crede erroneamente che il pacchetto 0 sia nuovo e lo colloca di seguito ai precedenti.

Nel secondo caso la conferma dei primi tre pacchetti giunge correttamente. Il trasmettitore trasla la finestra e invia i successivi tre pacchetti con numero di sequenza 3, 0 e 1. La possibilità che si vuole prendere in considerazione è che il pacchetto con numero di sequenza 3 si perde nella rete ma il pacchetto con numero di sequenza 0 viene consegnato correttamente. Non è la ripetizione del pacchetto numero 0, ma è un nuovo pacchetto.

Il ricevitore e il trasmettitore non vedono le loro rispettive azioni, possono solo osservare i messaggi che entrano ed escono dal canale. Le due situazioni ipotizzate sono identiche, Non c'è modo di distinguere la ritrasmissione del primo pacchetto dalla trasmissione del quinto pacchetto. Risulta chiaro che una finestra che ha larghezza minore di 1 rispetto all'intervallo dei numeri di sequenza crea questi problemi. Si può dimostrare che la condizione da rispettare è che la larghezza della finestra sia minore o uguale della metà dell'intervallo dei numeri di sequenza.

Se si pensa al canale come un filo che collega il trasmettitore e il ricevitore è chiaro che il canale non può riordinare i pacchetti, ma il canale non è un filo, è una rete, i cui i sistemi intermedi memorizzano i pacchetti e, a seconda del traffico, potrebbero consegnarli in qualsiasi momento, anche se le finestre dal lato del mittente e quella dal lato del ricevitore non contengono il numero di sequenza di questo pacchetto. Siccome i numeri di sequenza dei pacchetti sono ciclici, il trasmettitore non deve riusare un numero di sequenza se non ha la certezza che ogni pacchetto precedente, con lo stesso numero di sequenza, non sia più nella rete. Per questa ragione un pacchetto ha una "vita" definita come il massimo tempo che può permanere nella rete, prima di essere eliminato.

Riepilogo

Meccanismo	Uso, Commenti
Checksum	Usato per riconosce la presenza di bit errati in un pacchetto trasmesso.
Timer	Usato per fissare un massimo tempo di attesa della conferma prima di ritrasmettere il pachetto. La ritrasmissione è richiesta perchè dopo tale intervallo di tempo, si ritiene che il pacchetto, o la conferma, si è perso nel canale. Il timeout si può verificare anche se il pacchetto non si perde, ma subisce un grande ritardo oppure se si perde la conferma del pacchetto. In questo caso al ricevitore giungono pacchetti duplicati.
Numeri di sequenza	Usati per assegnare una numerazione progressiva ai pacchetti che viaggiano dal mittente al destinatario. Un salto di numerazione nella sequenza dei pacchetti ricevuti permette al destinatario di rilevare un pacchetto perso. I pacchetti con numero di sequenza duplicato permettono al destinatario di accorgersi di aver ricevuto una copia di un pacchetto precedentemente acquisito.
Conferma	Usata dal ricevitore per infomare il mittente che uno o più pacchetti sono stati ricevuti correttamente I pacchetti di conferma portano il numero di sequenza dei pacchetti ricevuti correttamente. Le conferme possono essere singole o cumulative, a seconda della tecnica ARQ usata.
Conferme negative	Usate dal ricevitore per informare il mittente che un pacchetto è stato ricevuto con errori. I pacchetti di conferma negativa portano anche il numero del pacchetto che &egarve; stato ricevuto con errori.
Finestra	La velocità di generazione di pacchetti può essere limitata imponendo al trasmettitore di inviare solo i pacchetti che hanno un numero di sequenza contenuto in un prestabilito intervallo. La larghezza della finestra dipende dalla capacità del ricevitore di acquisire, memorizzare e consegnare pacchetti.