Tecniche ARQ - stop-and-wait, go-back-N e selective repeat

L'idea e il modello

Con la ritrasmissione automaticail ricevitore controlla ogni pacchetto e ne chiede la ripetizione se è errato (ARQ, automatic repeat request) il ricevitore verifica con un codice a rivelazione di errore (un controllo di parità o un CRCcontrollo di ridondanza ciclica: codice che rivela gli errori, calcolato sui bit del pacchetto, Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →) se il pacchetto è corretto e risponde con una conferma ACKconferma positiva: il pacchetto è arrivato corretto (corretto) o NACKconferma negativa: il pacchetto è errato (errato); il trasmettitore ritrasmette i pacchetti errati. È il compito del livello di collegamento dati (LLClogical link control: parte del livello di collegamento dati che controlla errori e flusso, Sistemi di telecomunicazioni e modello ISO-OSIUn servizio di telecomunicazioni porta informazione da una sorgente a una destinazione lontana attraverso trasmettitore, canale e ricevitore. Le comunicazioni si classificano per destinatari (unicast, broadcast, multicast) e per direzione (simplex, half-duplex, full-duplex); le reti hanno una topologia (stella, mesh, albero, anello, bus) e usano commutazione di circuito o di pacchetto. Le funzioni di rete sono divise in strati: nel modello ISO-OSI sono 7 e questo corso studia quasi solo lo strato fisico.Sistemi di telecomunicazioni e modello ISO-OSI →). Si assume il canale di ritornocanale su cui viaggiano le conferme, dal ricevitore al trasmettitore affidabile e si indica:

• $L$ la lunghezza del pacchetto in bit e $P_{bit}$ la probabilità di errore sul bit: il pacchetto è sbagliato se almeno un bit è sbagliato, $$p=1-(1-P_{bit})^L\approx LP_{bit}\quad(LP_{bit}\ll1);$$
• $t_P=\frac L{R_b}$ il tempo di pacchettotempo per trasmettere tutti i bit del pacchetto: $L$ diviso il bit-rate (di trasmissione), $t_A$ quello della conferma, $\tau_P$ il ritardo di propagazionetempo che il segnale impiega ad andare dal trasmettitore al ricevitore (andata); il tempo di andata e ritorno è $2\tau_P$.

Ogni pacchetto va trasmesso, in media, $\frac1{1-p}$ volte (distribuzione geometricanumero di prove fino al primo successo, ciascuna con la stessa probabilità: con probabilità $(1-p)p^{j-1}$ servono $j$ trasmissioni, media $\sum_jj(1-p)p^{j-1}=\frac1{1-p}$). L'efficienzafrazione di tempo in cui il canale trasmette pacchetti nuovi e corretti (throughput normalizzato) $S$ è la frazione di tempo in cui il canale trasmette pacchetti nuovi e corretti: il bit-rate utile è $S\,R_b$ (per i bit di dati, tolta l'intestazione).

Stop-and-wait (SW-ARQ)

Il trasmettitore invia un pacchetto e aspetta l'ACK prima di inviare il successivo. Il ciclo dura $t_P+2\tau_P+t_A$ (pacchetto, andata e ritorno, conferma) ma solo $t_P$ è "utile", e solo con probabilità $1-p$: $$\boxed{S_{SW}=\frac{t_P\,(1-p)}{t_P+t_A+2\tau_P}.}$$ È semplice ma inefficiente quando $2\tau_P$ è grande rispetto a $t_P$ (canale lungo: il trasmettitore resta fermo ad aspettare).

Go-back-N (GBN-ARQ)

Il trasmettitore invia pacchetti in modo continuo senza aspettare l'ACK, con una finestranumero massimo di pacchetti trasmessi e non ancora confermati di $N$ pacchetti in volo. Se il pacchetto $j$ è errato, il ricevitore scarta anche i successivi e il trasmettitore ritorna indietro e ritrasmette il pacchetto errato e tutti i successivi già inviati. Per tenere occupato il canale la finestra deve coprire il ciclo di conferma: $$N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil\ \ (N\text{ pacchetti: quello e }N-1\text{ in volo}).$$ Ogni errore costa $N$ trasmissioni (il pacchetto sbagliato più $N-1$ ritrasmessi inutilmente) e ogni pacchetto subisce in media $\frac p{1-p}$ errori prima del successo: il numero medio di trasmissioni per pacchetto utile è $1+\frac{Np}{1-p}=\frac{1+(N-1)p}{1-p}$ e l'efficienza è il suo inverso, moltiplicato per $\frac{t_P}{t_P+t_A}$: $$\boxed{S_{GBN}=\frac{(1-p)\,t_P}{\left[1+(N-1)p\right](t_P+t_A)}.}$$

Selective repeat (SR-ARQ)

Come GBN ma il ricevitore memorizza i pacchetti corretti arrivati dopo uno errato (ha un buffermemoria in cui il ricevitore conserva i pacchetti arrivati fuori ordine) e il trasmettitore ritrasmette solo quello errato; il ricevitore riordina. Si spreca soltanto l'overheadtempo aggiunto oltre ai dati utili, qui quello dell'ACK dell'ACK e i pacchetti sbagliati: $$\boxed{S_{SR}=(1-p)\,\frac{t_P}{t_P+t_A}}$$ (è il massimo ottenibile con ARQ: $\to1-p$ per $t_A\to0$).

Esempio numerico (eserciziario, verificato)

$\tau_P=525$ ms, $t_P=200$ ms, $t_A=10$ ms, $p=10^{-2}$:

• SW: $S=\frac{0{,}2\cdot0{,}99}{0{,}2+0{,}01+1{,}05}=0{,}157$;
• GBN: $\frac{2\tau_P}{t_P+t_A}=\frac{1{,}05}{0{,}21}=5\Rightarrow N=6$; $S=\frac{0{,}99\cdot0{,}2}{(1+5\cdot0{,}01)\cdot0{,}21}=0{,}898$;
• SR: $S=0{,}99\cdot\frac{0{,}2}{0{,}21}=0{,}943$.

(Il canale lungo penalizza lo SW: $16\%$ contro $90$-$94\%$.) Dipendenza da $p$ (stessi tempi):

Con $p$ grande GBN crolla (ogni errore ritrasmette $N$ pacchetti) e SR resta vicino a $1-p$. Altri esempi: LANlocal area network: rete locale su breve distanza ($t_P=1$ ms, $t_A=50\ \mu$s, $\tau_P=5\ \mu$s, $p=10^{-2}$): SW $0{,}934$, GBN $0{,}934$ ($N=2$), SR $0{,}943$ (differenze piccole: il ritardo è trascurabile). Satellite geostazionarioin orbita a circa 36000 km sopra l'equatore: ritardo di andata di circa 270 ms ($t_P=10$ ms, $t_A=0{,}5$ ms, $\tau_P=270$ ms, $p=10^{-2}$): SW $0{,}018$, GBN $0{,}62$ ($N=53$), SR $0{,}943$: lo stop-and-wait è inutilizzabile.

Errori comuni

• Calcolare $p$ come $P_{bit}$: $p=1-(1-P_{bit})^L$ ($\approx LP_{bit}$).
• Dimenticare il ritardo di andata e ritorno $2\tau_P$ (non $\tau_P$) in SW e nella finestra di GBN.
• Usare per GBN la formula dello SW o dimenticare $\frac{t_P}{t_P+t_A}$ (l'overhead dell'ACK).
• Scambiare GBN e SR: GBN ritrasmette tutti i successivi (efficienza minore con $p$ grande), SR solo l'errato.