Go-Back-N e Selective Repeat

Che cosa viaggia e che cosa si conosce

Un protocollo ARQ usa informazioni che viaggiano nelle unità e informazioni che i due estremi conoscono in anticipo.

• Nella trama viaggiano il CRC, per rivelare gli errori, e il numero di sequenza $S_{\text{last}}$.
• Nel riscontro viaggia $R_{\text{next}}$, il numero della prossima trama attesa, che conferma anche tutte le precedenti.
• Non viaggiano il timer, la finestra $W_s$ e le regole di ritrasmissione: i due estremi devono usare lo stesso protocollo.

Nello stop and wait i numeri sono di un bit e si alternano. Il Go-Back-N non aggiunge campi alle trame. Il trasmettitore tiene un timer per trama e $S_{\text{last}}$, la più vecchia non riscontrata, da cui riparte. Il ricevitore tiene $R_{\text{next}}$, che ora è un numero progressivo.

Numerazione e finestra del Go-Back-N

Con $m$ bit i numeri di sequenza sono $M=2^m$, da $0$ a $M-1$, e poi si riparte da $0$. Un numero identifica quindi una trama solo rispetto allo stato del protocollo. Con $m=2$ sono 00, 01, 10, 11.

Se $W_s=M=4$ e si perdono tutti i riscontri, allo scadere del timeout A ritrasmette la 0. B ha già ricevuto 0, 1, 2, 3 e si aspetta di nuovo la 0: per lui è una trama nuova, e non può distinguerla dalla ripetizione. Con $W_s=3$, dopo 0, 1, 2 B si aspetta la 3, quindi riconosce la 0 come duplicata e la scarta.

Finestra e numerazione con due bit

$W_s=4$: B si aspetta la 0

ABaccettata0123timeout0

$W_s=3$: B si aspetta la 3

ABscartata012timeout0

La finestra del Go-Back-N è quindi al più di $M-1$ trame, una in meno dei numeri disponibili:

$$W_s\le M-1=2^m-1$$

Selective Repeat

Dopo un errore il Go-Back-N ripete anche trame arrivate bene. Il Selective Repeat ripete solo quelle perse. Il trasmettitore resta uguale. Cambia il ricevitore, che ha una finestra di ricezione di ampiezza $W_r$: accetta le trame corrette con numero da $R_{\text{next}}$ a $R_{\text{next}}+W_r-1$, anche fuori sequenza. Quelle fuori sequenza le conserva in un buffer e le consegna in ordine quando arriva la mancante.

Il ricevitore segnala il buco con un NAK, un riscontro negativo con il numero della trama mancante, e poi manda ACK con lo stesso $R_{\text{next}}$ finché il buco resta. Il trasmettitore ritrasmette la trama non riscontrata più vecchia appena riceve il NAK, o allo scadere del suo timer. Quando la trama arriva, $R_{\text{next}}$ salta oltre quelle conservate e un solo ACK le conferma tutte.

Selective Repeat con la trama 2 persa

AB013452NAK 2ACK 6B conserva 3, 4, 5

Anche qui i numeri possono confondersi. Se tutti i riscontri si perdono, A ritrasmette la 0 e B ha già spostato in avanti la finestra di ricezione: se la 0 ci ricade, la accetta come nuova. Con $m=2$ la finestra di B dopo ogni trama ricevuta è:

B ha ricevuto	$W_s=W_r=3$	$W_s=W_r=2$
niente	$\{0,1,2\}$	$\{0,1\}$
0	$\{1,2,3\}$	$\{1,2\}$
0, 1	$\{2,3,0\}$	$\{2,3\}$
0, 1, 2	$\{3,0,1\}$	–

Con $W_s=W_r=3$ la 0 ritrasmessa ricade in $\{3,0,1\}$ ed è accettata. Con $W_s=W_r=2$ è fuori da $\{2,3\}$ ed è scartata. In generale, dopo $W_s$ trame la finestra di ricezione va da $W_s$ a $W_s+W_r-1$, e la 0 resta fuori se questo estremo è minore di $M$:

$$W_s+W_r\le M$$

Con $W_r=1$ è la regola del Go-Back-N. Con $m=2$ vanno bene $W_s=W_r=2$ e $W_s=3$, $W_r=1$.

Efficienza dei tre protocolli

Sia $P_f$ la probabilità di errore su una trama. Il numero medio di trasmissioni per trama è $1/(1-P_f)$: con $P_f=0$ vale 1 e non si ritrasmette mai, con $P_f\to1$ cresce senza limite.

• Il Selective Repeat ripete solo la trama errata: il tempo per trama è $t_f/(1-P_f)$ e l'efficienza dipende solo da $P_f$.
• Il Go-Back-N a ogni errore ripete una finestra, quindi dipende anche da $W_s$.
• Lo stop and wait lascia il canale vuoto mentre aspetta il riscontro, quindi cala con il prodotto banda-ritardo $L$, in trame.

Con $n_f$ bit per trama, $n_a$ per l'ACK, $n_o$ di intestazione e bit rate $R$, il prodotto banda-ritardo in trame è, per la finestra che riempie il ciclo:

$$L=\frac{2(t_{\text{prop}}+t_{\text{proc}})\,R}{n_f}=W_s-1$$ $$\begin{gathered} \eta_{\text{SR}}=\left(1-\frac{n_o}{n_f}\right)(1-P_f)\\ \eta_{\text{GBN}}=\frac{(1-n_o/n_f)(1-P_f)}{1+(W_s-1)P_f}\\ \eta_{\text{SW}}=\frac{(1-n_o/n_f)(1-P_f)}{1+n_a/n_f+L} \end{gathered}$$

Con $P_f\approx0$ Selective Repeat e Go-Back-N coincidono; con $P_f\to1$ coincidono Go-Back-N e stop and wait, se $n_a\ll n_f$. Un esempio con $n_f=10\,000$ bit, $n_a=n_o=200$ bit, $R=1$ Mbit/s e $2t_{\text{prop}}=100$ ms, cioè $L=10$ e $W_s=11$, per diversi tassi d'errore sul bit $p$, con $1-P_f=(1-p)^{n_f}\simeq e^{-n_f p}$:

$p$	$0$	$10^{-6}$	$10^{-5}$	$10^{-4}$
stop and wait	8,9 %	8,8 %	8,0 %	3,3 %
Go-Back-N	98 %	88,2 %	45,4 %	4,9 %
Selective Repeat	98 %	97 %	89 %	36 %

Senza errori Go-Back-N e Selective Repeat arrivano al 98 %: il resto lo toglie l'intestazione.

Efficienza e tasso d'errore sul bit

${\log }_{10}p$

• Selective Repeat
• Go-Back-N con $W_s=L+1$
• stop and wait

$L$

10

Dal collegamento al TCP

Regolando i riscontri si regola anche il flusso: se il ricevitore li manda più tardi o meno spesso, il trasmettitore rallenta. Il TCP, protocollo di strato 4 sopra IP, usa questi meccanismi da estremo a estremo, con un funzionamento simile al Selective Repeat. Il tempo di andata e ritorno su tutta la rete non si misura in anticipo: il TCP lo stima con i pacchetti inviati e raffina la stima a ogni pacchetto, e su di essa dimensiona la finestra di trasmissione. Integra il controllo di flusso e numera i byte dei segmenti, non le trame.

Esercizio: Go-Back-N con 1000 pacchetti

Il ritardo di propagazione è $t_{\text{prop}}=24\,t_f$, l'ACK dura $t_{\text{ack}}=t_f$, la finestra è $W_s=100$, il timeout dura quanto la trasmissione di una finestra, $100\,t_f$, e il file ha 1000 pacchetti. Il ciclo è

$$t_0=t_f+t_{\text{ack}}+2t_{\text{prop}}=50\,t_f$$

Quanti pacchetti si trasmettono inutilmente in quattro casi?

• Primo pacchetto errato. B scarta i 99 successivi, anche se corretti, perché manca il primo, e non manda riscontri: la finestra non scorre. Dopo $100\,t_f$ scade il timeout e A riparte dal pacchetto 1. I pacchetti inutili sono 100, l'errato e i 99 scartati. Poi la finestra scorre senza pause.
• Primo e centesimo errati. Stesso risultato: l'errore del primo fa già scartare il resto della finestra.
• Riscontro del primo perso. Il riscontro del secondo è cumulativo e conferma anche il primo prima del timeout. Non si ritrasmette niente.
• Riscontri del primo e del centesimo persi. Come prima: un riscontro perso nella finestra non costa niente se ne arriva uno successivo.

Pacchetti consegnati in ordine

Evento

Primo pacchetto erratoRiscontro del primo perso

$t/t_f$consegnati

• senza errori
• con l'evento scelto

$W_s$

100

I riscontri consecutivi che si possono perdere sono al più 49. Il riscontro del pacchetto $k$ torna a $t_0+(k-1)\,t_f$: quello del cinquantesimo torna a $99\,t_f$, prima del timeout di $100\,t_f$ del primo, e conferma tutti i precedenti.