Go-Back-N

GBN consente al mittente di spedire quanti pacchetti vuole, con il limite però che il buffer non può superare una certa soglia di pacchetti per cui si attende gli ACK.
Pasted image 20230921125526.png
L’immagine sopra offre una descrizione della finestra del mittente che utilizza GBN.

  • base: più piccolo numero di sequenza di un pacchetto inviato ma che non ha ricevuto ACK
  • nextseqnum: più piccolo numero di sequenza di un pacchetto che può essere inviato, ma che non è stato inviato (prossimo pacchetto da inviare)
  • N: grandezza della finestra (buffer mittente)

Si delineano 4 intervalli:

  1. [0, base - 1]: pacchetti inviati per cui è stato ricevuto ACK
  2. [base, nextseqnum - 1]: pacchetti inviati per cui non è stato ricevuto ACK
  3. [nextseqnum, base + N - 1]: pacchetti non ancora inviati
  4. I numeri di sequenza maggiori o uguali a base + N non possono essere usati

La finestra che va da [base, N - 1] scorre lungo i numeri di sequenza.
N viene detta ampiezza della finestra.
GBN viene detto protocollo a finestra scorrevole.
In pratica, il numero di sequenza di un pacchetto, viene scritto in un campo a dimensione fissa dell'intestazione del pacchetto. Detto il numero di bit di tale campo l'intervallo di possibili numeri di sequenza è .
La finestra è limitata per consentire il servizio del controllo della congestione (che verrà affrontato più avanti).
Presentiamo di seguito la macchina a stati finiti di GBN che risulta essere una estensione della macchina del mittente.
Pasted image 20230927123331.png

  • All'inizio base = 1 e nextseqnum = 1.
  • Quando arriva la richiesta di inviare dei pacchetti dall'alto, viene chiamata rdt_send(data), qui GBN controlla che nextseqnum (il numero di sequenza del pacchetto da inviare) sia inferiore a base + N (dove N è la dimensione della finestra), in tal caso il pacchetto con numero nextseqnum viene creato (make_pkt(...)) e inviato. Dopo aver inviato il pacchetto viene fatto un altro controllo if(base == nextseqnum), ovvero si controlla se il pacchetto appena inviato è il primo pacchetto per cui non è stato ricevuto ACK, in tal caso si fa partire il timer e si incrementa il numero di sequenza (prossimo pacchetto). Nel caso in cui il pacchetto da inviare è maggiore della dimensione della finestra (la finestra è piena), il pacchetto viene rifiutato (refuse_data()), cioè non viene inviato.
  • GBN riceve ACK relativi ai pacchetti che invia. Gli ACK di GBN sono detti cumulativi. Ovvero la ricezione di ACK per il pacchetto , indica che tutti i pacchetti con numero di sequenza inferiore a sono stati ricevuti. (Torneremo a breve sull'argomento quando esamineremo la macchina del destinatario).
  • Il timer utilizzato su GBN è unico. Quando un pacchetto viene spedito viene avviato il timer. Se entro un lasso di tempo stabilito dall'avvio del timer, non si riceve alcun ACK, si verifica il timeout e ciò indica che i pacchetti da base a nextseqnum devono essere ritrasmessi.
    Infatti se guardiamo lo stato in basso della macchina in figura, vediamo che, quando viene ricevuto un pacchetto e questo pacchetto non è corrotto, il valore della base diventa quello del pacchetto di ACK appena ricevuto incrementato di 1, ovvero grazie a questo ACK con un certo numero di sequenza, sappiamo che il pacchetto relativo a questo ACK e quelli numero di sequenza inferiore, sono arrivati correttamente, per cui adesso si attendono gli ACK per i pacchetti successivi al numero di sequenza dell'ACK appena ricevuto: base = getacknum(rcvpkt) + 1. Poi si controlla se base == nextseqnum, ovvero se l'ACK appena ricevuto corrisponde con l'ultimo pacchetto inviato, se è vero, il timer può fermarsi, poiché il mittente ha ricevuto ACK per tutti i pacchetti inviati, se è falso, vuol dire che il mittente deve resettare il timer e continuare a trasmettere pacchetti.
  • Infine c'è lo stato relativo al timeout, un evento interno: quando scade il timer, esso viene resettato e vengono inviati nuovamente i pacchetti per cui non è estato ricevuto ACK, ovvero da base a nextseqnum - 1.

Per comprendere meglio:

  • supponiamo che il timer sia di 3 secondi
  • nessun pacchetto è stato inviato, base = 1
  • il mittente spedisce con nextseqnum = 1, base == nextseqnum, avvio del timer, nextseqnum + 1 e spedizione del pacchetto
  • il mittente spedisce poi , base = 1 (perché non è ancora arrivato l'ACK relativo a ), il timer non viene resettato
  • il mittente spedisce poi , base = 1 (non sono ancora arrivati gli ACK per e ), il timer non viene resettato
  • scadenza del timer: non sono arrivati gli ACK per i pacchetti , e : devono essere ritrasmessi
GBN sul destinatario
...

Pasted image 20230927131054.png

  • All'inizio: expectedseqnum = 1
  • Il destinatario di GBN, riceve un pacchetto, se esso non è corrotto e ha il numero di sequenza del pacchetto che si sta attendendo (rdt_rcv(rcv_pkt) && notcorrupt(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum) allora vengono estratti i dati e consegnati al livello superiore, dopo si invia l'ACK e si incrementa la variabile expecetedseqnum.
  • In tutti gli altri casi (default: pacchetto corrotto, o smarrito) viene inviato ACK per l'ultimo pacchetto che si è ricevuto correttamente.

Notiamo che, trattandosi di pacchetti consegnati uno per volta, se il pacchetto è stato ricevuto e consegnato, sono stati consegnati tutti quelli precedenti. Si noti infatti che GBN scarta i pacchetti fuori sequenza, GBN ricevente accetta solo pacchetti con corretto numero di sequenza, ovvero con il numero di sequenza che il ricevente si aspetta che abbia. Il motivo è che il mittente tiene conto della sua finestra di invio in maniera ordinata, non può avere pacchetti sparsi per la sua finestra, poi l'altro motivo è la semplicità: se arriva un pacchetto fuori sequenza, diciamo e il ricevente deve inviare ACK per un altro numero di sequenza, diciamo , il ricevente dovrebbe salvare il pacchetto con numero di sequenza per spedire l'ACK quando è il momento del numero di sequenza .

GBN in funzione
...

Pasted image 20230927131949.png
La figura sopra mostra come lavora GBN con una finestra di 4 pacchetti.
A causa di questo limite il mittente invia i pacchetti da 0 a 3, dopo di che deve attendere conferma per uno di questi 4 pacchetti inviati. Quando giungono gli ACK0 e ACK1, la finestra scorre in avanti e può trasmettere due nuovi pacchetti (4 e 5).
Lato ricevente il pacchetto 2 viene perso, dunque i pacchetti 3 e 4, giungono in un ordine inaspettato per il ricevente, che prontamente li rifiuta.