Ripetizione selettiva

GBN sembra risolvere i problemi che ci portiamo dietro da protocolli stop-and-wait. Tuttavia anche l'efficienza di GBN potrebbe essere migliorata. Se la larghezza della finestra del mittente è ampia, esso può spedire un elevato numero di pacchetti. Inoltre se la distanza tra gli host comunicanti è estesa c'è da aspettarsi un certo ritardo. Queste condizioni combinate possono portare all'invio di un elevato numero di pacchetti, che viaggiano su un lungo percorso. Se un solo pacchetto si perde o è corrotto, il mittente è costretto a ritrasmettere numerosi pacchetti.

Un protocollo a ripetizione selettiva evita la ritrasmissione di pacchetti che è inutile ritrasmettere, per esempio quei pacchetti che in GBN il ricevente rifiuta. Questa tecnica costringe il ricevente a inviare ACK per pacchetti specifici sia per quelli che giungono in ordine, sia per quelli che giungono fuori sequenza. Il mittente conserverà i pacchetti ricevuti in modo corretto in un buffer finché non sono stati ricevuti tutti i pacchetti con numero di sequenza inferiore.
Pasted image 20230927132341.png
In figura abbiamo:

  • sopra, la finestra dei pacchetti inviati dal mittente
  • mentre sotto, la finestra dei pacchetti ricevuti dal destinatario
Finestre del mittente
...
  1. Quando si ricevono dati dall'alto, il mittente di SR (selective repeat), controlla il successivo numero di sequenza disponibile per il pacchetto. Se è all'interno della finestra del mittente, i dati vengono impacchettati e inviati; altrimenti sono salvati nei buffer o restituiti al livello superiore per una successiva ritrasmissione come in GBN.
  2. Gestione del timeout: il contatore utilizzato è sempre un timer logico, tuttavia a questo punto deve essere utilizzato un timer per ogni pacchetto, dato che verranno rispediti solo i pacchetti effettivamente corrotti/persi.
  3. Gestione di ACK non ricevuti: se si riceve ACK, il mittente di SR etichetta il pacchetto come ricevuto, ammesso che sia nella finestra. Se il numero di sequenza del pacchetto è uguale a send_base, la base della finestra si muove verso il pacchetto che non ha ricevuto ACK con il più piccolo numero di sequenza (al prossimo pacchetto giallo in figura). Se la finestra si sposta e ci sono pacchetti non ancora trasmessi con numero di sequenza che rientra nella finestra, allora essi vengono trasmessi.
Finestra del destinatario
...
  1. Se il pacchetto con numero di sequenza nell'intervallo [rcv_base, rcv_base + N - 1] viene ricevuto correttamente, allora il pacchetto ricevuto ricade all'interno della finestra del ricevente e al mittente viene restituito un ACK selettivo. Se il pacchetto non era già stato ricevuto veniva salvato nel buffer del ricevente. Se presenta un numero di sequenza uguale alla base della finestra di ricezione (rcv_base), allora questo pacchetto e tutti i pacchetti nel buffer vengono consegnati al livello superiore (partendo da rcv_base). Si veda esempio alla fine di questa lista.
  2. Se viene ricevuto pacchetto con numero di sequenza nell'intervallo [rcv_base - N, rcv_base - 1], ovvero se si riceve un pacchetto già ricevuto (verde in figura), allora si deve inviare un ACK anche se il pacchetto è già stato ricevuto.
  3. Altrimenti: si ignora il pacchetto
Nota

Il pacchetto di ACK viene inviato anche se è già stato ricevuto lo stesso pacchetto da parte del destinatario, perché le finestre del mittente e del ricevente potrebbero non essere allineate. Infatti il ricevente sa di aver ricevuto per la seconda volta lo stesso pacchetto, ma magari il mittente no.

Esempio
...

Pasted image 20230927134734.png

La sincronizzazione delle finestre è fondamentale quando si ha a che fare con dei numeri di sequenza finiti, quando i numeri di sequenza sono saturi essi ricominciano da capo.
Immaginiamo il seguente scenario:

  • Finestra grande 4, ovvero con numeri di sequenza che vanno da 0 a 3
  • Il mittente e il ricevente non possono vedere cosa succede dall'altra parte

Pasted image 20230927135308.png

Caso (a)
...
  1. In verde, il destinatario riceve i pacchetti con numero di sequenza e allora invia gli ACK per quei pacchetti. Quegli ACK si perdono.
  2. Il timer del mittente (blu) scade e allora il mittente ritrasmette. Abbiamo detto che i numeri di sequenza si resettano. Quando il mittente rispedisce i pacchetti con numero di sequenza come fa il destinatario a sapere se si tratta di nuovi dati, o dei pacchetti per cui ha già inviato gli ACK (che si sono persi)?
Caso (b)
...
  1. In verde, il destinatario invia gli ACK per i pacchetti ricevuti, con numeri di sequenza . Gli ACK questa volta non si perdono e arrivano al mittente.
  2. Il mittente (blu) riceve prima l'ACK per quanto riguarda il pacchetto 0, la sua finestra scorre e invia il pacchetto con numero di sequenza 3. Tale pacchetto si perde. Poi il mittente riceve ACK per il pacchetto 1 e la sua finestra scorre e invia i pacchetto 0 (sequenza resettata).
  3. Il pacchetto col numero di sequenza 3 si è perso e il destinatario non ha modo di sapere se si tratta di una ritrasmissione o nuovi dati.

Dato che si possono riutilizzare i numeri di sequenza, si deve prestare attenzione alla duplicazione dei pacchetti. L'approccio utilizzato nella pratica è assicurarsi che prima di riutilizzare i numeri di sequenza ci si deve assicurare che il pacchetto non possa più essere in giro per la rete. Tale lasso di tempo nelle reti TCP ad alta velocità è stimato essere 3 minuti.