Salta al contenuto
Note per Studenti Esercizio 33 · throughput di stop-and-wait, go-back-N e selective repeat (esercizio del corso)

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

In questa pagina 5

Testo (eserciziario di un corso UniPD equivalente, esercizio sull'ARQ). Calcolare il throughput per SW-ARQ, GBN-ARQ e SR-ARQ per una trasmissione con τP=525\tau_P=525 ms, tP=200t_P=200 ms, tA=10t_A=10 ms e probabilità di errore sulla PDU p=10−2p=10^{-2}. Si calcoli poi come cambiano i valori per p=0,3p=0{,}3 e per un collegamento con τP=5\tau_P=5 ms.

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 tPt_P utile, ma il ciclo dura tP+tA+2τP=200+10+1050=1260t_P+t_A+2\tau_P=200+10+1050=1260 ms (pacchetto, conferma, e andata e ritorno di 525525 ms ciascuna): SSW=tP(1−p)tP+tA+2τP=200⋅0,991260=0,157.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%16\% del tempo: il trasmettitore attende quasi sempre.

Go-back-N

La finestra deve coprire il ciclo di conferma: 2τPtP+tA=1050210=5\frac{2\tau_P}{t_P+t_A}=\frac{1050}{210}=5, quindi N−1=5N-1=5 e N=6N=6 pacchetti. Ogni errore costa N=6N=6 trasmissioni: SGBN=(1−p) tP[1+(N−1)p](tP+tA)=0,99⋅200(1+5⋅0,01)⋅210=198220,5=0,898.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: SSR=(1−p)tPtP+tA=0,99⋅200210=0,943.S_{SR}=(1-p)\frac{t_P}{t_P+t_A}=0{,}99\cdot\frac{200}{210}=0{,}943.

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

Grafico interattivo: Throughput in funzione della probabilità di errore p sulla PDU (τ_P = 525 ms, t_P = 200 ms, t_A = 10 ms, N = 6): per p = 10⁻² vale 0,157 (SW), 0,898 (GBN) e 0,943 (SR); per p = 0,3 il GBN crolla a 0,267 (ogni errore ritrasmette 6 pacchetti), il SR resta a 0,667 e lo stop-and-wait a 0,111

Altri valori

  • p=0,3p=0{,}3 (stessi tempi): SW 200⋅0,71260=0,111\frac{200\cdot0{,}7}{1260}=0{,}111; GBN 0,7⋅200(1+5⋅0,3)⋅210=140525=0,267\frac{0{,}7\cdot200}{(1+5\cdot0{,}3)\cdot210}=\frac{140}{525}=0{,}267; SR 0,7⋅200210=0,6670{,}7\cdot\frac{200}{210}=0{,}667. Con errori frequenti il GBN crolla (ogni errore ritrasmette 66 pacchetti) e il SR resta vicino a 1−p1-p.
  • τP=5\tau_P=5 ms (p=10−2p=10^{-2}): 2τP=102\tau_P=10 ms. SW: 198200+10+10=0,9\frac{198}{200+10+10}=0{,}9. GBN: 10210=0,048→N−1=1\frac{10}{210}=0{,}048\to N-1=1, N=2N=2: 198(1+0,01)⋅210=0,933\frac{198}{(1+0{,}01)\cdot210}=0{,}933. SR: 0,9430{,}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,15710{,}1571, GBN 0,89800{,}8980 (N=6N=6), SR 0,94290{,}9429; per p=0,3p=0{,}3: 0,11110{,}1111, 0,26670{,}2667, 0,66670{,}6667. La soluzione a mano dell'eserciziario riporta 0,660{,}66 e 0,630{,}63 per SR e GBN a p=10−2p=10^{-2}: sono i valori di p≈0,3p\approx0{,}3 per SR; con p=10−2p=10^{-2} i valori giusti sono 0,9430{,}943 e 0,8980{,}898.)

Errori comuni

  • Usare τP\tau_P invece di 2τP2\tau_P nel ciclo dello stop-and-wait e nella finestra.
  • Dimenticare tPtP+tA\frac{t_P}{t_P+t_A} (la conferma occupa tempo) in GBN e SR.
  • Calcolare NN senza il +1+1: la finestra contiene N=1+⌈2τPtP+tA⌉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)p1+(N-1)p a denominatore.

Versione ripasso

Testo. Collegamento con τP=525\tau_P=525 ms, tP=200t_P=200 ms, tA=10t_A=10 ms e probabilità di errore sulla PDU p=10−2p=10^{-2}. Richiesti: throughput di stop-and-wait, go-back-N e selective repeat; poi gli stessi con p=0,3p=0{,}3 e con τP=5\tau_P=5 ms.

Stop-and-wait (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 →)

  • Ciclo tP+tA+2τP=1260t_P+t_A+2\tau_P=1260 ms. S=tP(1−p)1260=1981260=0,157S=\frac{t_P(1-p)}{1260}=\frac{198}{1260}=0{,}157.

Go-back-N

  • 2τPtP+tA=5\frac{2\tau_P}{t_P+t_A}=5, quindi N−1=5N-1=5 e N=6N=6.
  • S=(1−p)tP[1+(N−1)p](tP+tA)=198220,5=0,898S=\frac{(1-p)t_P}{[1+(N-1)p](t_P+t_A)}=\frac{198}{220{,}5}=0{,}898.

Selective repeat

  • S=(1−p)tPtP+tA=0,943S=(1-p)\frac{t_P}{t_P+t_A}=0{,}943.

Altri valori

  • Con p=0,3p=0{,}3: stop-and-wait 0,1110{,}111, GBN 0,2670{,}267, SR 0,6670{,}667. Il GBN crolla perché ogni errore ritrasmette 66 pacchetti.
  • Con τP=5\tau_P=5 ms (p=10−2p=10^{-2}): stop-and-wait 0,90{,}9; GBN con N=2N=2, S=0,933S=0{,}933; SR 0,9430{,}943. Con ritardo piccolo i tre protocolli sono vicini.

Errori tipici

  • Usare τP\tau_P invece di 2τP2\tau_P nel ciclo dello stop-and-wait e nella finestra.
  • Dimenticare il fattore tPtP+tA\frac{t_P}{t_P+t_A} in GBN e SR.
  • Calcolare NN senza il termine +1+1 rispetto a N−1N-1.
  • Scambiare GBN e SR: il GBN ha 1+(N−1)p1+(N-1)p a denominatore.

Teoria collegata