Esercizio - Trasferimento di 1,5 MB con handshake, stop-and-wait e limite di pacchetti per RTT

Testo. Collegamento punto-punto tra l'host A e l'host B con bitrate $R=10$ Mbps e $RTT_{min}=80$ ms. Calcolare il tempo totale per trasferire $1{,}5$ MB di dati nei casi seguenti:

1. i dati sono divisi in pacchetti da $1$ KB e i pacchetti si inviano in modo continuo, dopo un "handshake" iniziale di $2\cdot RTT_{min}$;
2. come al punto 1 ma, dopo ogni pacchetto, il trasmettitore attende un RTT prima di inviare il successivo; calcolare anche l'efficienza del collegamento;
3. il collegamento permette una trasmissione infinitamente veloce ma limita il throughput in modo che si possano inviare solo $20$ pacchetti per RTT; calcolare l'efficienza.

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

• $R=10$ Mbit/s; $1$ KB $=1000$ byte $=8000$ bit; $1{,}5$ MB $=1\,500\,000$ byte, quindi $N=1500$ pacchetti.
• Tempo di trasmissione di un pacchetto: $t_{tx}=\dfrac{8000}{10^7}=0{,}8$ ms.
• $RTT_{min}=2t_{prop}+t_{tx}(1\text{ bit})\simeq2t_{prop}$, quindi $t_{prop}=RTT_{min}/2=40$ ms.
• RTT "vero" per un pacchetto da $1$ KB (ACK trascurabile): $RTT=2t_{prop}+t_{tx}=80{,}8$ ms.

(1) Invio continuo

Si paga prima l'handshake, $2\cdot RTT_{min}=160$ ms. Poi i pacchetti partono uno dietro l'altro: il trasmettitore è occupato per $1500\cdot t_{tx}=1{,}2$ s. L'ultimo bit dell'ultimo pacchetto viene messo sul filo alla fine di questi $1{,}2$ s e arriva a B dopo altri $t_{prop}=40$ ms.

Non serve calcolare la propagazione di ogni pacchetto: i pacchetti arrivano a B a distanza di $t_{tx}$ l'uno dall'altro (trasmissione e propagazione avvengono "in parallelo" su pacchetti diversi), quindi basta aggiungere la propagazione una volta sola: $$T_1=2RTT_{min}+N\,t_{tx}+t_{prop}=0{,}16+1{,}2+0{,}04=\mathbf{1{,}40\ s}.$$

(2) Un pacchetto per RTT (stop-and-wait)

Dopo l'handshake si invia il pacchetto 1, si attende l'ACK (un RTT dall'inizio della trasmissione), poi si invia il pacchetto 2, e così via. I primi $N-1=1499$ pacchetti occupano ciascuno un intero ciclo di durata $RTT=80{,}8$ ms. L'ultimo pacchetto non deve attendere l'ACK: bastano la sua trasmissione e la propagazione fino a B. $$T_2=2RTT_{min}+(N-1)\,RTT+t_{tx}+t_{prop}=0{,}16+1499\cdot0{,}0808+0{,}0008+0{,}04=\mathbf{121{,}32\ s}.$$ Efficienza. Il BDP calcolato sull'RTT è $RTT\cdot R=0{,}0808\cdot10^7=808$ kbit: in un ciclo il collegamento potrebbe trasportare $808$ kbit ma ne trasporta $8$ kbit ($1$ KB): $$\eta=\frac{8\ \text{kbit}}{808\ \text{kbit}}=\frac{t_{tx}}{RTT}=0{,}0099\simeq\mathbf{1\%}.$$ Il throughput sperimentato è $8000/0{,}0808\simeq99$ kbps, cioè circa $100$ kbps su un collegamento da $10$ Mbps.

(3) Gruppi di 20 pacchetti per RTT

Ora si inviano finestre di $20$ pacchetti e poi si aspetta. Inviare $20$ pacchetti richiede $20\,t_{tx}=16$ ms, cioè molto meno dell'RTT ($80{,}8$ ms): il collegamento resta fermo per il tempo restante, per cui il ciclo dura ancora un RTT. Le finestre sono $1500/20=75$; le prime $74$ occupano un ciclo di $RTT$ ciascuna, l'ultima solo il tempo di trasmettere i suoi $20$ pacchetti più la propagazione: $$T_3=2RTT_{min}+(75-1)\,RTT+20\,t_{tx}+t_{prop}=0{,}16+74\cdot0{,}0808+0{,}016+0{,}04=\mathbf{6{,}195\ s}.$$ Efficienza: in un ciclo si inviano $20$ KB sui $808$ kbit possibili, $$\eta=\frac{160\ \text{kbit}}{808\ \text{kbit}}=0{,}198\simeq\mathbf{20\%},$$ con throughput $160\,000/0{,}0808\simeq1{,}98$ Mbps $\simeq2$ Mbps. È proporzionale alla dimensione della finestra: $20$ volte meglio di stop-and-wait. In generale, con $W$ pacchetti per RTT, $\eta=W\,t_{tx}/RTT$ finché $W\,t_{tx}<RTT$; il collegamento è sempre occupato quando $W\ge RTT/t_{tx}=80{,}8/0{,}8=101$ pacchetti, che è il prodotto banda-ritardo in pacchetti.

Confronto con la soluzione ufficiale

Ufficiale: $1{,}40$ s; $121{,}32$ s con $\eta=1\%$ e throughput $100$ kbps; $6{,}195$ s con $\eta=20\%$ e throughput $2$ Mbps. Tutto coincide. Una nota sul punto 3: il testo dice "trasmissione infinitamente veloce", ma la soluzione usa comunque $t_{tx}=0{,}8$ ms per pacchetto (finestra da $16$ ms) e un ciclo di $80{,}8$ ms. Se si prendesse alla lettera $t_{tx}=0$ si avrebbe $RTT=80$ ms e $T=0{,}16+74\cdot0{,}08+0{,}04=6{,}12$ s, che non è il numero ufficiale. Il $6{,}195$ s si riproduce solo con la lettura della soluzione.

Errori comuni

• Sommare la propagazione a ogni pacchetto nel caso (1): con invio continuo si paga una sola volta.
• Nel caso (2) contare $N$ RTT invece di $N-1$ più la parte finale dell'ultimo pacchetto.
• Usare $1$ KB $=1024$ byte: qui $1$ KB $=1000$ byte, altrimenti non si ottengono $1500$ pacchetti e $0{,}8$ ms.
• Dimenticare di convertire $RTT_{min}=80$ ms in $t_{prop}=40$ ms per il ritardo di sola andata.

(Verificato con Python: $t_{tx}=0{,}8$ ms; $RTT=80{,}8$ ms; $T_1=1{,}400$ s; $T_2=121{,}320$ s; $BDP=808$ kbit; $\eta_2=0{,}0099$; $T_3=6{,}1952$ s; $\eta_3=0{,}198$; $T_3$ con $t_{tx}=0$: $6{,}12$ s.)