Esercizio - Quattro pacchetti, UDP e ARQ GBN o stop-and-wait su ogni collegamento o end-to-end

Testo (simulazione d'esame 3, esercizio 1). Rete a commutazione di pacchetto a datagramma (store-and-forward), code indipendenti per ogni interfaccia di uscita.

1. A $t=0$ la coda di A contiene tre pacchetti diretti a C, C, D (D per ultimo); la coda di E ha un pacchetto diretto a B. Pacchetti da $L=1250$ B: calcolare gli istanti di arrivo e il throughput medio.

Da qui in avanti si trascura ogni altro traffico, si trasmette un messaggio di $M=125$ KB in pacchetti da $L=1250$ B da A a C, senza intestazioni e con ACK di lunghezza trascurabile; si calcola il tempo totale (dal primo byte all'ultimo ACK) quando:

2. si usa UDP (solo ricezione dell'ultimo pacchetto, niente ACK);
3. GBN su ogni collegamento con finestra $N=8$;
4. GBN end-to-end con $N=8$;
5. GBN end-to-end con $N=16$;
6. stop-and-wait su ogni collegamento;
7. stop-and-wait end-to-end;
8. GBN ($N=8$) sul primo collegamento, GBN ($N=8$) sul secondo, stop-and-wait sul terzo.

Teoria usata: Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →, Commutazione di circuito e di pacchettoUn nodo di commutazione (switch) può collegare ingresso e uscita in tre modi. Commutazione di circuito: si stabilisce prima un collegamento fisico dedicato (rete telefonica), tempo di consegna $T=3Nt_p+Nt_s+M/R$. Commutazione di pacchetto a datagramma: il messaggio è diviso in $K$ pacchetti con intestazione, ognuno è instradato indipendentemente con store-and-forward, $T=Nt_p+(N+K-1)\frac{M/K+H}{R}$, con $K_{ott}=\sqrt{(N-1)M/H}$. A circuito virtuale: tre fasi (setup, dati, chiusura), connessione logica dedicata ma senza risorse dedicate, identificatore locale che cambia a ogni salto.Commutazione di circuito e di pacchetto →, Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →, 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 →. Un esercizio molto simile, con altri valori: Esercizio - Go-Back-N su ogni collegamento con finestre 15 e 6 e confronto con stop-and-wait.

Domanda 1: arrivi e throughput

$L=10\,000$ bit. Tempi di trasmissione $T=L/C$ (ms):

Percorsi: C: $C_1,C_2,C_4$; D: $C_1,C_5,C_6$; B (da E): $C_7,C_2,C_3$. Si incrociano solo su $C_2$.

• A: $C_{(1)}$ esce a $0{,}667$, $C_{(2)}$ a $1{,}333$, $D$ a $2{,}0$; in R1 (con $+1$ ms) $1{,}667$; $2{,}333$; $3{,}0$.
• E: il pacchetto per B esce a $1{,}0$ e arriva in R1 a $2{,}0$.

Coda su $C_2$ ($T=1{,}25$): ordine di arrivo $C_{(1)}$ ($1{,}667$), $B$ ($2{,}0$), $C_{(2)}$ ($2{,}333$).

Il pacchetto D non incontra traffico: da R1 va su $C_5$ ($0{,}5$ ms, parte a $3{,}0$, finisce a $3{,}5$), $+7$ ms $\to10{,}5$ in R3, poi $C_6$: $+0{,}1+5$: arriva a $\mathbf{15{,}6}$ ms.

Arrivi in ordine di tempo: $9{,}42$, $11{,}27$, $11{,}92$, $15{,}6$ ms (ufficiale: $9{,}41$; $11{,}26$; $11{,}91$; $15{,}6$, con $T_1$ troncato a $0{,}66$ ms).

Throughput medio. Quattro pacchetti da $10$ kbit in $15{,}6$ ms: $40\,000/15{,}6\cdot10^{-3}\approx2{,}56$ Mbit/s (bit consegnati diviso tempo fino all'ultimo arrivo).

Grandezze per le domande 2-8

Cammino A→C: $C_1$ ($T=0{,}667$, $\tau=1$), $C_2$ ($T=1{,}25$, $\tau=5$), $C_4$ ($T=0{,}5$, $\tau=1$). Numero di pacchetti: $K=125\,000/1250=100$. Il collo di bottiglia è $C_2$ ($T_b=1{,}25$ ms). Ritardo di ritorno di un ACK sull'intero cammino: $\tau_4+\tau_2+\tau_1=7$ ms.

Tempo di un RTT per collegamento, $T+2\tau$:

• $\text{RTT}_1=0{,}667+2=2{,}667$ ms;
• $\text{RTT}_2=1{,}25+10=11{,}25$ ms;
• $\text{RTT}_4=0{,}5+2=2{,}5$ ms.

Primo pacchetto: $T_1+\tau_1+T_2+\tau_2+T_4+\tau_4=0{,}667+1+1{,}25+5+0{,}5+1=9{,}417$ ms. Il tempo "fino all'ultimo ACK" è contato come fa la soluzione ufficiale: ricezione dell'ultimo pacchetto in C più il ritorno di $7$ ms.

RTT end-to-end (pacchetto singolo, ACK trascurabile): $\text{RTT}_{e2e}=9{,}417+7=16{,}417$ ms.

Domanda 2: UDP

Non ci sono ACK né attese: i pacchetti escono alla velocità del collo di bottiglia. L'ultimo (il centesimo) arriva a

$$T_{\text{UDP}}=9{,}417+(100-1)\cdot1{,}25=\mathbf{133{,}17\ \text{ms}}.$$

Domanda 3: GBN su ogni collegamento, $N=8$

Ogni collegamento esegue il proprio GBN: può avere $8$ pacchetti non riscontrati. Un collegamento è continuo se $N\,T\ge\text{RTT}_{\text{collegamento}}$:

• $C_1$: $8\cdot0{,}667=5{,}33\ge2{,}667$: sì;
• $C_2$: $8\cdot1{,}25=10<11{,}25$: no, ogni finestra da $8$ pacchetti dura $\text{RTT}_2=11{,}25$ ms invece di $10$ ms;
• $C_4$: $8\cdot0{,}5=4\ge2{,}5$: sì.

Il collo di bottiglia vero è quindi $C_2$ con $8$ pacchetti ogni $11{,}25$ ms. $100=12\cdot8+4$: $12$ finestre complete e una da $4$ pacchetti:

$$T=T_1+\tau_1+12\,\text{RTT}_2+4\,T_2+\tau_2+T_4+\tau_4+\underbrace{(\tau_4+\tau_2+\tau_1)}_{7}=1{,}667+135+5+5+1{,}5+7=\mathbf{155{,}17\ \text{ms}}.$$

Il primo pacchetto arriva in R1 a $T_1+\tau_1=1{,}667$; $C_2$ trasmette $12$ finestre complete da $11{,}25$ ms; l'ultima finestra ha $4$ pacchetti ($4\,T_2$), poi propagazione e ultimo collegamento; infine il ritorno dell'ACK.

Domanda 4: GBN end-to-end, $N=8$

Ora la finestra copre l'intero cammino e l'ACK torna dalla destinazione. Con $N\,T_b=8\cdot1{,}25=10<\text{RTT}_{e2e}=16{,}417$ ms il flusso non è continuo: $8$ pacchetti ogni $\text{RTT}_{e2e}$.

$$T=12\,\text{RTT}_{e2e}+T_1+\tau_1+4\,T_2+\tau_2+T_4+\tau_4+7=197{,}00+1{,}667+5+5+1{,}5+7=\mathbf{217{,}17\ \text{ms}}$$

(ufficiale $217{,}08$: differenza di arrotondamento con $T_1=0{,}66$ ms).

Domanda 5: GBN end-to-end, $N=16$

$16\cdot1{,}25=20\ge16{,}417$: flusso continuo. Il collo di bottiglia lavora senza pause:

$$T=T_1+\tau_1+100\,T_2+\tau_2+T_4+\tau_4+7=1{,}667+125+5+1{,}5+7=\mathbf{140{,}17\ \text{ms}}.$$

Il grafico mostra come cambia $T(N)$ per il GBN end-to-end al variare della finestra (stessa regola: $\lceil100/N\rceil$ finestre, l'ultima più corta): $N=1$ è lo stop-and-wait end-to-end ($1641{,}67$ ms, domanda 7), $N=8$ dà $217{,}17$ ms (domanda 4), da $N=\lceil16{,}417/1{,}25\rceil=14$ in poi vale $140{,}17$ ms come per $N=16$ (domanda 5).

Domanda 6: stop-and-wait su ogni collegamento

Ogni collegamento manda un pacchetto, aspetta l'ACK ($T+2\tau$), poi il successivo. Il più lento è $C_2$ con $\text{RTT}_2=11{,}25$ ms a pacchetto ($C_1$ e $C_4$ sono più veloci: $2{,}667$ e $2{,}5$ ms):

$$T=T_1+\tau_1+(100-1)\,\text{RTT}_2+T_2+\tau_2+T_4+\tau_4+7=1{,}667+1113{,}75+6{,}25+1{,}5+7=\mathbf{1130{,}17\ \text{ms}}.$$

Domanda 7: stop-and-wait end-to-end

Un solo pacchetto in volo sull'intero cammino: $100$ round trip da $\text{RTT}_{e2e}=16{,}417$ ms:

$$T=100\cdot16{,}417=\mathbf{1641{,}67\ \text{ms}}.$$

Domanda 8: GBN, GBN e stop-and-wait

• primo collegamento GBN ($8$): continuo ($5{,}33\ge2{,}667$);
• secondo collegamento GBN ($8$): $8$ pacchetti ogni $11{,}25$ ms, cioè $1{,}41$ ms a pacchetto;
• terzo collegamento stop-and-wait: $\text{RTT}_4=T_4+2\tau_4=2{,}5$ ms a pacchetto, più lento del secondo ($1{,}41$ ms): è il collo di bottiglia.

I pacchetti si accodano in R2 e $C_4$ ne serve uno ogni $2{,}5$ ms. Il primo arriva a R2 a $T_1+\tau_1+T_2+\tau_2=7{,}917$ ms:

$$T=T_1+\tau_1+T_2+\tau_2+(100-1)\,\text{RTT}_4+T_4+\tau_4+7=7{,}917+247{,}5+1{,}5+7=\mathbf{263{,}92\ \text{ms}}.$$

Confronto con la soluzione ufficiale

Le differenze di un centesimo sono arrotondamenti ($T_1=0{,}667$ nei miei calcoli, $0{,}66$ nei suoi). Nella soluzione ufficiale la cifra del risultato finale della domanda 8 è poco leggibile; la formula ($T_1+\tau_1+T_2+\tau_2+(K-1)\text{RTT}_4+T_4+\tau_4+7$) è identica.

Errori comuni

• Applicare la finestra del GBN a ogni collegamento ma calcolare $\text{RTT}_{e2e}$ (o viceversa): "su ogni collegamento" usa $T+2\tau$ del singolo collegamento, "end-to-end" il tempo di tutto il cammino.
• Verificare il flusso continuo solo sul collo di bottiglia: con GBN per collegamento va controllata la condizione $N\,T\ge T+2\tau$ su ciascun collegamento.
• Dimenticare il ritorno finale dell'ACK ($7$ ms) quando si chiede "fino all'ultimo ACK".
• Contare $12{,}5$ finestre: $100=12\cdot8+4$, l'ultima è da $4$ pacchetti e non dura un RTT intero.

(Verificato con Python: simulatore a eventi per la domanda 1 e simulatore ARQ per collegamento ed end-to-end per le domande 2-8.)