Esercizio - Due collegamenti con switch, file da 1250 MB e ARQ stop-and-wait

Testo. Due host comunicano tramite uno switch, su una catena di due collegamenti: $R_1=100$ Mbit/s e $R_2=200$ Mbit/s, con propagazione di $500\ \mu$s per collegamento. Lo switch fa commutazione di pacchetto a datagramma (store-and-forward), senza ritardo di elaborazione. Un file di $1250$ Mbyte è trasferito in pacchetti da $10$ kbit con intestazione trascurabile. Calcolare il tempo totale di trasferimento (dalla trasmissione del primo bit alla ricezione dell'ultimo) nei casi:

1. pacchetti trasmessi senza controllo d'errore;
2. con ARQ S&W su ciascun collegamento (nessun errore);
3. con ARQ S&W end-to-end (nessun errore);
4. come cambiano i risultati se $R_2=50$ Mbit/s.

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 →; richiami sugli ARQ in 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 →.

Dati e grandezze di base

• Dimensione del file: $1250\ \text{MB}=1250\cdot8\cdot10^6=10^{10}$ bit. Pacchetti da $L=10\,000$ bit: $K=\dfrac{10^{10}}{10^4}=10^6$ pacchetti.
• Tempi di trasmissione di un pacchetto: $T_1=\dfrac{L}{R_1}=\dfrac{10^4}{10^8}=0{,}1$ ms; $T_2=\dfrac{L}{R_2}=\dfrac{10^4}{2\cdot10^8}=0{,}05$ ms.
• Propagazione: $\tau_1=\tau_2=\tau=0{,}5$ ms.
• Ipotesi sugli ACK: nessun dato sulla lunghezza dell'ACK, quindi si trascura il suo tempo di trasmissione ($t_A\approx0$): l'ACK impiega solo la propagazione di ritorno.

Caso 1: nessun controllo d'errore

Senza ARQ A trasmette un pacchetto dietro l'altro senza fermarsi. Il collegamento 1 è il collo di bottiglia ($T_1>T_2$): A emette un pacchetto ogni $T_1=0{,}1$ ms e lo switch, che impiega solo $0{,}05$ ms a ritrasmetterlo, è sempre libero quando ne arriva uno nuovo (nessuna coda). L'ultimo pacchetto parte da A a $(K-1)T_1$, finisce a $KT_1$, e fa poi gli ultimi due salti: $$T_{tot}=K\,T_1+\tau_1+T_2+\tau_2=10^6\cdot0{,}1\text{ ms}+0{,}5+0{,}05+0{,}5\text{ ms}=100{,}00105\ \text{s}\approx100\ \text{s}.$$ Il termine dominante è $K\,T_1$: è il tempo per far uscire tutti i bit dal collegamento più lento.

Caso 2: S&W su ciascun collegamento (punto-punto)

Modello. Su ogni collegamento il trasmettitore manda un pacchetto e aspetta l'ACK del nodo vicino prima del successivo. Il ciclo su un collegamento dura $$RTT_1=T_1+2\tau_1=0{,}1+1=1{,}1\ \text{ms},\qquad RTT_2=T_2+2\tau_2=0{,}05+1=1{,}05\ \text{ms}.$$ Nel $RTT_1$ A manda un pacchetto; lo switch impiega $RTT_2=1{,}05$ ms a consegnare il suo (compreso l'ACK da B), un po' meno del tempo con cui A glielo fornisce. Quindi lo switch è sempre pronto e il ritmo è dettato dal collegamento più lento, il primo: A manda un pacchetto ogni $RTT_1$.

L'ultimo pacchetto parte quando A riceve l'ACK del penultimo, cioè a $(K-1)RTT_1$, e poi fa i due salti senza altre attese (l'ACK dell'ultimo non conta: il tempo si ferma alla ricezione dell'ultimo bit): $$T_{tot}=(K-1)\,RTT_1+T_1+\tau_1+T_2+\tau_2=(10^6-1)\cdot1{,}1\text{ ms}+1{,}15\text{ ms}=1100{,}00005\ \text{s}\approx1100\ \text{s}.$$

Caso 3: S&W end-to-end

Modello. L'ARQ è tra A e B: A manda un pacchetto e aspetta l'ACK che arriva da B, dopo aver attraversato i due collegamenti in entrambi i versi. Il ciclo dura il tempo di andata di un pacchetto più il ritorno dell'ACK: $$RTT_{e2e}=T_1+\tau_1+T_2+\tau_2+\tau_2+\tau_1=0{,}1+0{,}5+0{,}05+0{,}5+0{,}5+0{,}5=2{,}15\ \text{ms}.$$ $$T_{tot}=(K-1)\,RTT_{e2e}+T_1+\tau_1+T_2+\tau_2=(10^6-1)\cdot2{,}15\text{ ms}+1{,}15\text{ ms}=2149{,}999\ \text{s}\approx2150\ \text{s}.$$ Il tempo è quasi doppio rispetto al caso 2: un solo pacchetto alla volta nell'intera rete, mentre con l'ARQ punto-punto i due collegamenti lavorano in parallelo su pacchetti diversi (pipeline).

Controllo con la formula dell'utilizzazione dello stop-and-wait, $\rho=t_F/t_G$ (teoria in 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 →): il collegamento 1 trasmette per $T_1=0{,}1$ ms su ogni ciclo di $1{,}1$ ms nel caso 2 ($\rho=0{,}0909$) e di $2{,}15$ ms nel caso 3 ($\rho=0{,}0465$). Il tempo senza ARQ, $K\,T_1=100$ s, diviso per $\rho$ dà $100/0{,}0909=1100$ s e $100/0{,}0465=2150$ s: gli stessi risultati.

Caso 4: $R_2=50$ Mbit/s

Ora $T_2=\dfrac{10^4}{5\cdot10^7}=0{,}2$ ms: il collegamento 2 diventa il più lento ($T_2>T_1$).

• Senza ARQ: i pacchetti arrivano allo switch ogni $0{,}1$ ms ma escono ogni $0{,}2$ ms: lo switch accumula coda. Il collo di bottiglia ora è il secondo collegamento: il primo pacchetto lascia lo switch a $T_1+\tau_1+T_2$, poi uno ogni $T_2$ fino all'ultimo (al peggio come se la coda fosse sempre piena): $$T_{tot}=T_1+\tau_1+K\,T_2+\tau_2=0{,}1+0{,}5+10^6\cdot0{,}2+0{,}5\ \text{ms}=200{,}0011\ \text{s}\approx200\ \text{s}.$$
• S&W punto-punto: $RTT_1=1{,}1$ ms, $RTT_2=T_2+2\tau_2=0{,}2+1=1{,}2$ ms. Ora $RTT_2>RTT_1$: lo switch ci mette di più a consegnare un pacchetto di quanto A impieghi a mandarglielo, quindi i pacchetti si accodano nello switch e il ritmo è dettato dal secondo collegamento: un pacchetto ogni $RTT_2$. Il primo pacchetto arriva allo switch a $T_1+\tau_1$ e poi ne esce uno ogni $RTT_2$: $$T_{tot}=T_1+\tau_1+(K-1)\,RTT_2+T_2+\tau_2=0{,}6+(10^6-1)\cdot1{,}2+0{,}7\ \text{ms}=1200{,}0001\ \text{s}\approx1200\ \text{s}.$$
• S&W end-to-end: $RTT_{e2e}=0{,}1+0{,}5+0{,}2+0{,}5+0{,}5+0{,}5=2{,}3$ ms: $$T_{tot}=(K-1)\cdot2{,}3\text{ ms}+1{,}3\text{ ms}=2299{,}999\ \text{s}\approx2300\ \text{s}.$$

Riepilogo:

Confronto con la soluzione ufficiale

Ufficiale (con $R_2=200$): $\approx100$ s, $\approx1100$ s, $\approx2150$ s; con $R_2=50$: $\approx200$ s, $\approx1200$ s, $\approx2300$ s. Coincide in tutti i casi, nello stesso modello (ACK di dimensione trascurabile). Le formule dei tempi ufficiali, viste nelle note a mano della soluzione, sono quelle usate qui: $KT_1+\tau_1+T_2+\tau_2$; $(K-1)RTT_1+T_1+\tau_1+T_2+\tau_2$; $(K-1)RTT_{e2e}+\dots$; per $R_2=50$ il caso punto-punto diventa $T_1+\tau_1+(K-1)RTT_2+T_2+\tau_2$.

Errori comuni

• Confondere $1250$ Mbyte con $1250$ Mbit: dimenticare il fattore $8$ dà $K=1{,}25\cdot10^5$ invece di $10^6$.
• Usare $RTT_2$ nel caso 2 con $R_2=200$: il ritmo lo decide il massimo tra $RTT_1$ e $RTT_2$.
• Dimenticare il "$-1$" in $(K-1)RTT$: l'ultimo pacchetto non aspetta il proprio ACK (qui l'effetto è trascurabile, ma conta con pochi pacchetti).
• Non distinguere ARQ punto-punto da end-to-end: nel secondo caso c'è un solo pacchetto in rete, nel primo due.

(Verificato con Python: $K=10^6$; $T_1=0{,}1$ ms, $T_2=0{,}05$ ms; $100{,}00105$ s, $1100{,}00005$ s, $2149{,}999$ s; con $R_2=50$: $200{,}0011$ s, $1200{,}0001$ s, $2299{,}999$ s.)