Esercizio 33throughput di stop-and-wait, go-back-N e selective repeat (esercizio del corso)

---

Teoria usata: 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 →.

Stop-and-wait

Ogni pacchetto occupa $t_P$ utile, ma il ciclo dura $t_P+t_A+2\tau_P=200+10+1050=1260$ ms (pacchetto, conferma, e andata e ritorno di $525$ ms ciascuna): $$S_{SW}=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}=\frac{200\cdot0{,}99}{1260}=0{,}157.$$ Il canale è usato solo il $16\%$ del tempo: il trasmettitore attende quasi sempre.

Go-back-N

La finestra deve coprire il ciclo di conferma: $\frac{2\tau_P}{t_P+t_A}=\frac{1050}{210}=5$, quindi $N-1=5$ e $N=6$ pacchetti. Ogni errore costa $N=6$ trasmissioni: $$S_{GBN}=\frac{(1-p)\,t_P}{\left[1+(N-1)p\right](t_P+t_A)}=\frac{0{,}99\cdot200}{(1+5\cdot0{,}01)\cdot210}=\frac{198}{220{,}5}=0{,}898.$$

Selective repeat

Si ritrasmette solo il pacchetto errato; resta l'overhead della conferma: $$S_{SR}=(1-p)\frac{t_P}{t_P+t_A}=0{,}99\cdot\frac{200}{210}=0{,}943.$$

Quindi, con $p=10^{-2}$: $S_{SW}=0{,}157$, $S_{GBN}=0{,}898$, $S_{SR}=0{,}943$ (il bit-rate utile è $S\cdot R_b$).

Altri valori

• $p=0{,}3$ (stessi tempi): SW $\frac{200\cdot0{,}7}{1260}=0{,}111$; GBN $\frac{0{,}7\cdot200}{(1+5\cdot0{,}3)\cdot210}=\frac{140}{525}=0{,}267$; SR $0{,}7\cdot\frac{200}{210}=0{,}667$. Con errori frequenti il GBN crolla (ogni errore ritrasmette $6$ pacchetti) e il SR resta vicino a $1-p$.
• $\tau_P=5$ ms ($p=10^{-2}$): $2\tau_P=10$ ms. SW: $\frac{198}{200+10+10}=0{,}9$. GBN: $\frac{10}{210}=0{,}048\to N-1=1$, $N=2$: $\frac{198}{(1+0{,}01)\cdot210}=0{,}933$. SR: $0{,}943$. Con ritardo di propagazione piccolo, SW, GBN e SR sono quasi uguali (SW perde solo il tempo del ciclo).

(Verificato con Python: SW $0{,}1571$, GBN $0{,}8980$ ($N=6$), SR $0{,}9429$; per $p=0{,}3$: $0{,}1111$, $0{,}2667$, $0{,}6667$. La soluzione a mano dell'eserciziario riporta $0{,}66$ e $0{,}63$ per SR e GBN a $p=10^{-2}$: sono i valori di $p\approx0{,}3$ per SR; con $p=10^{-2}$ i valori giusti sono $0{,}943$ e $0{,}898$.)

Errori comuni

• Usare $\tau_P$ invece di $2\tau_P$ nel ciclo dello stop-and-wait e nella finestra.
• Dimenticare $\frac{t_P}{t_P+t_A}$ (la conferma occupa tempo) in GBN e SR.
• Calcolare $N$ senza il $+1$: la finestra contiene $N=1+\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$ pacchetti.
• Scambiare GBN e SR: il GBN ha $1+(N-1)p$ a denominatore.