Esercizio - throughput di stop-and-wait, go-back-N e selective repeat (esercizi del corso, cap. 4)

---

Teoria usata: Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico → (sezione sull'ARQ). Versione per Ing. Elettronica, con lo stesso esercizio e altri casi: Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →.

Il modello e i dati

Il trasmettitore manda pacchetti (PDU) e il ricevitore risponde con una conferma. I tempi sono:

• $t_P=200$ ms: tempo per trasmettere un pacchetto;
• $t_A=10$ ms: tempo per trasmettere la conferma (ACK/NACK);
• $\tau_P=525$ ms: ritardo di propagazione in un verso. Il segnale va e torna: l'andata e ritorno vale $2\tau_P=1050$ ms.

La probabilità che un pacchetto arrivi errato è $p=10^{-2}$. Il throughput normalizzato $S$ è la frazione di tempo in cui il canale trasporta pacchetti nuovi e corretti; il bit-rate utile è $S\,R_b$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$ (ogni trasmissione riesce con probabilità $1-p$).

Stop-and-wait

Si invia un pacchetto e si aspetta la conferma prima di inviare il successivo. Un ciclo dura $$t_P+t_A+2\tau_P=200+10+1050=1260\ \text{ms}$$ (trasmissione del pacchetto, ritardo di andata e ritorno, conferma). Di questi, il tempo utile è $t_P=200$ ms e solo se il pacchetto è corretto (probabilità $1-p$): $$S_{SW}=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}=\frac{200\cdot0{,}99}{1260}=\frac{198}{1260}=0{,}157.$$ Il canale è usato per circa il $16\%$ del tempo: lo stop-and-wait aspetta quasi sempre la conferma.

Go-back-N

Il trasmettitore invia pacchetti di seguito, con una finestra di $N$ pacchetti in volo, senza aspettare ogni conferma. Perché il canale non resti mai inattivo, la finestra deve coprire il tempo che la conferma di un pacchetto impiega a tornare: il numero di pacchetti trasmessi mentre il primo viaggia andata e ritorno è $$N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil=\left\lceil\frac{1050}{210}\right\rceil=\lceil5\rceil=5\quad\Longrightarrow\quad N=6.$$ Se un pacchetto è errato, il ricevitore scarta anche i successivi e il trasmettitore li rimanda tutti: ogni errore costa $N-1$ trasmissioni inutili in più oltre al ripetere il pacchetto. Il numero medio di trasmissioni per pacchetto utile è $\frac{1+(N-1)p}{1-p}$ e ogni trasmissione occupa $t_P+t_A$: $$S_{GBN}=\frac{(1-p)\,t_P}{\left[(N-1)p+1\right](t_P+t_A)}=\frac{0{,}99\cdot200}{(5\cdot0{,}01+1)\cdot210}=\frac{198}{1{,}05\cdot210}=\frac{198}{220{,}5}=0{,}898.$$

Selective repeat

Come GBN, ma il ricevitore conserva i pacchetti corretti arrivati dopo uno errato e il trasmettitore rimanda solo quello errato. Resta il tempo della conferma e il fatto che con probabilità $p$ il pacchetto va ripetuto: $$S_{SR}=(1-p)\,\frac{t_P}{t_P+t_A}=0{,}99\cdot\frac{200}{210}=0{,}943.$$ È il massimo ottenibile con l'ARQ: con $p\to0$ e $t_A\to0$ vale $1$.

Riepilogo ($p=10^{-2}$): $S_{SW}=0{,}157$, $S_{GBN}=0{,}898$, $S_{SR}=0{,}943$. Verificato con Python: $0{,}1571$, $0{,}8980$, $0{,}9429$.

Osservazione sulla soluzione del corso. La soluzione riporta $S_{SW}=0{,}16$, ma per GBN e SR dà $0{,}63$ e $0{,}66$. Con i dati dell'esercizio ($t_P=200$ ms, $t_A=10$ ms, $p=10^{-2}$) le stesse formule danno $0{,}898$ e $0{,}943$: i valori $0{,}63$ e $0{,}66$ non sono coerenti con questi dati (per esempio $S_{SR}=0{,}66$ richiederebbe $p\approx0{,}3$, e con $p=0{,}3$ lo stop-and-wait scenderebbe a $0{,}11$, non $0{,}16$). Il valore $N=6$ e le formule della soluzione sono invece uguali alle mie.

Come cambia con $p$ e con il ritardo

Con $p$ grande il go-back-N crolla (ogni errore ritrasmette $N=6$ pacchetti), il selective repeat resta vicino a $1-p$. Col ritardo di propagazione cresce lo svantaggio dello stop-and-wait; il go-back-N perde poco perché la finestra si allarga con il ritardo (curve a $p=10^{-2}$, $t_P=200$ ms, $t_A=10$ ms):

Errori comuni

• Usare $\tau_P$ al posto di $2\tau_P$ nel ciclo dello stop-and-wait e nella finestra: il ritardo si paga all'andata e al ritorno.
• Calcolare la finestra come $N=\frac{2\tau_P}{t_P+t_A}$ senza il $+1$: la finestra contiene il pacchetto più i $\lceil\frac{2\tau_P}{t_P+t_A}\rceil$ che riempiono l'attesa, $N=6$ qui.
• Dimenticare il fattore $\frac{t_P}{t_P+t_A}$ in GBN e SR: la conferma occupa $t_A$.
• Scambiare GBN e SR: il GBN ha $(N-1)p+1$ al denominatore e perde molto per $p$ grande.