cerca
La verità sul go-back-n
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

La verità sul go-back-n

 :: La verità sul go-back-n ::

Breve introduzione

Il protocollo TCP ha il concetto di connessione, ovvero i due host che vogliono scambiarsi dei files devono mettersi d'accordo su ciò. Inoltre, a differenza di UDP, prevede un controllo d'errore, ovvero se c'è qualche pacchetto o frammento rovinato, va reinviato. L'host destinatario risponde ad ogni pacchetto ricevuto con un messaggio ACK che si riferisce al segmento che si attende di ricevere in seguito. Questo vuol dire che se mi arriva il segmento 2, rispondo dicendo che mi attendo il segmento 3, e il mittente capisce che il 2 gli è arrivato. In caso un segmento arrivi danneggiato (il ricevente se ne accorge tramite il CRC) allora il ricevente invia un messaggio NACK relativo a quel segmento.

Sistemi per il reinvio di segmenti

Ci sono fondamentalmente 2 scuole di pensiero riguardo al reinvio di segmenti. La prima si chiama idle RQ, la seconda continuous RQ. Entrambe utilizzano un timer: ad ogni segmento inviato, faccio partire un timer, e se entro la scadenza del timer non mi arriva una risposta, reinvio quel segmento.

Idle RQ

Mando un segmento, e attendo l'ACK. Poi mando il secondo segmento, e attendo l'ACK del secondo. Funziona, ma è estremamente lento, perché nei tempi in cui il mittente attende l'ACK, non manda niente: la linea rimane vuota.

Continuous RQ

Qui invece la questione cambia: invio tanti pacchetti di fila, senza bisogno di attendere l'ACK. In questo modo ho sempre la banda piena. Il numero di pacchetti che posso inviare senza bisogno di ricevere l'ACK si chiama finestra . Inviati tutti i pacchetti della mia finestra, attendo tutti gli ACK, e poi comincio ad inviare una nuova finestra. Qui il gioco sta quindi nel capire quando spostare la finestra, di quanto, e che fare in caso di errore.

Supponiamo che la finestra abbia dimensione 4. Il mittente, che chiamo M, invia 4 segmenti di fila senza curarsi di quello che succede. Il ricevente si chiama R. Quando riceve il segmento 1 (comincio a contare da 1 e non da 0 per comodità) invia l'ACK di 1 (che come ho detto sopra conterrà un messaggio che dice: mi attendo il segmento 2). Quando riceve il segmento 2, invia l'ACK di 2 e così via fino all'ACK di 4.

Che cosa fa M allora? Non appena riceve ACK 1 sposta a destra di uno la finestra. Quindi, se prima la finestra conteneva i segmenti 1 - 2 - 3 - 4, ora la finestra contiene 2 - 3 - 4 - 5. Quando arriva ACK 2, sposta la finestra di un altro segmento: 3 - 4 - 5 - 6.

Selective Repeat

Supponiamo che a R arrivino tutti i 4 segmenti TRANNE il segmento 2: invierà l'ACK di tutti quanti ma non del 2. R manterrà in memoria TUTTI i segmenti e si ricorderà che il 2 non è arrivato. Alla fine della trasmissione M reinvia il 2 e fa avanzare la finestra.

Il vantaggio è che la rete viene usata in modo ottimale, ma il problema è che il ricevente deve mantenere in memoria tutti i segmenti, e può essere costoso in termini di memoria sulla scheda di rete o robe simili.

go-back-n

I problemi di trasmissione possono essere di diversi tipi: 1) non arriva l'ACK perché si perde; 2) il frame arriva corrotto e R risponde con NACK (il contrario di ACK).

Nel caso 1, occorre vedere quale dei 4 ACK che mi aspetto non arriva. Se non arriva l'ACK del primo, ma l'ACK del secondo, o nel caso peggiore solo l'ACK del 4°, la procedura go-back-n assume che tutti i segmenti precedenti siano stati ricevuti con successo. Perché? Perché si è stabilito che dopo aver ricevuto un segmento danneggiato, il ricevente risponda con NACK e non invii più nessun tipo di messaggio. Ma se arriva l'ACK del 4 segmento, vuol dire che sono tutti arrivati bene, anche se gli ACK sono arrivati male, altrimenti in caso di errore il destinatario non avrebbe mai potuto inviare l'ACK del 4 perché si sarebbe fermato prima.

Che cosa succede alla finestra? Mi arriva solo l'ACK del 4 segmento. Io so che il 4 segmento è l'ultimo della mia finestra, e che la finestra è lunga 4 => sposto a destra la finestra di 4 elementi. Se mi arriva solo l'ACK del 3 , allora sposto la finestra di 3 e così via.

In caso di timer scaduto, ovvero attendo un ACK e non mi arriva, riparto da quel segmento il cui timer è scaduto. Se arriva un NACK, riparto dal segmento il cui NACK è arrivato in poi. Quindi la finestra e la lista di ritrasmissione (cioè i segmenti che devo tenere in memoria perché potrei doverli reinviare a breve) sono gestite dinamicamente in questo modo.

La dimensione della finestra in generale non è statica. Viene negoziata tra 2 hosts in modo tale che il mittente possa inviare tanti segmenti quanti ne posso inviare nel tempo in cui un segmento ci mette a lasciare il mittente ed arrivare al destinatario. Il parametro che ho in mano in genere si chiama RTT, cioè Round Trip Time, ovvero tempo di andata & ritorno. Una volta ottenuto questo tempo, faccio in modo di inviare tanti segmenti quanti ne servono per tenere occupata la linea per questo RTT.

Ciò vuol dire che se RTT è 10 secondi, allora per 10 secondi invio pacchetti, così che quando ho finito di mandare l'ultimo pacchetto dovrebbe arrivare subito l'ACK del primo.


Torna alla pagina di Sistemi per l'elaborazione delle informazioni