Esercizio - Collegamento Terra-Luna, RTT, BDP ed efficienza

Testo. Un collegamento satellitare punto-punto con bitrate $R=100$ Mbps collega la Terra a una colonia lunare. La distanza Terra-Luna è circa $385\,000$ km e i dati viaggiano alla velocità della luce ($c=3\cdot10^8$ m/s). Calcolare:

1. l'RTT minimo del collegamento;
2. l'RTT se il centro di controllo sulla Terra invia alla base lunare un'immagine da $25$ MB;
3. il BDP (usando come ritardo l'RTT del punto precedente);
4. l'utilizzazione (efficienza) del collegamento se il centro invia un'altra immagine da $25$ MB solo dopo aver ricevuto l'ACK dalla Luna;
5. l'efficienza se il centro invia l'immagine successiva senza aspettare l'ACK.

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 → (efficienza dello stop-and-wait).

Dati e conversioni

• $d=385\,000$ km $=3{,}85\cdot10^8$ m, $c=3\cdot10^8$ m/s, $R=100$ Mbit/s $=10^8$ bit/s.
• Il testo parla di MB (megabyte) per i dati e di Mbps (megabit al secondo) per il bitrate: prima di dividere bisogna portare tutto in bit. $25$ MB $=25\cdot8=200$ Mbit.

(1) RTT minimo

L'RTT è la somma del ritardo dell'andata (pacchetto di dati) e di quello del ritorno (ACK). Ritardi di elaborazione e di accodamento sono trascurabili (nessun router in mezzo), quindi per ciascuna delle due direzioni restano trasmissione e propagazione: $$RTT=(t_{tx}+t_{prop})+(t_{tx,ACK}+t_{prop})=2t_{prop}+t_{tx}+t_{tx,ACK}.$$ Il minimo si ha con il pacchetto più piccolo possibile (1 bit) e un ACK di dimensione trascurabile, quindi $t_{tx}=1\text{ bit}/R=10$ ns, cioè zero rispetto ai secondi della propagazione: $$t_{prop}=\frac dc=\frac{3{,}85\cdot10^8}{3\cdot10^8}=1{,}2833\ \text{s},\qquad RTT_{min}\simeq2t_{prop}=\mathbf{2{,}57\ s}.$$ È la fisica: nessun protocollo può scendere sotto questo valore (la luce impiega $1{,}28$ s per arrivare sulla Luna).

(2) RTT con l'immagine da 25 MB

Ora la trasmissione dell'immagine non è più trascurabile: bisogna "versare" $200$ Mbit sul collegamento. $$t_{tx}=\frac{25\ \text{MB}}{R}=\frac{200\ \text{Mbit}}{100\ \text{Mbit/s}}=2\ \text{s}.$$ L'ACK è piccolo e la sua trasmissione si trascura, quindi $$RTT=2t_{prop}+t_{tx}=2{,}5667+2=\mathbf{4{,}57\ s}.$$

(3) BDP

Il bandwidth-delay product è il numero di bit che "riempiono" il collegamento nel tempo scelto come ritardo; qui il ritardo richiesto è l'RTT di (2): $$BDP=RTT\cdot R=4{,}5667\cdot100\ \text{Mbit/s}=456{,}7\ \text{Mbit}=\frac{456{,}7}{8}=\mathbf{57{,}1\ MB}.$$ Quindi mentre il primo bit va e torna come ACK, la sorgente potrebbe trasmettere $57$ MB.

(4) Efficienza se si attende l'ACK (stop-and-wait)

L'efficienza è il rapporto tra quanto si invia davvero e quanto si sarebbe potuto inviare nello stesso tempo (la "capacità" del collegamento, cioè il BDP): $$\eta=\frac{\text{dati inviati}}{BDP}=\frac{25\ \text{MB}}{57{,}08\ \text{MB}}=0{,}438.$$ Lo stesso numero si ottiene come tempo utile su tempo totale: $\eta=t_{tx}/RTT=2/4{,}567=0{,}438$. Il collegamento trasmette per $2$ s ogni $4{,}57$ s, il resto del tempo è attesa dell'ACK. È la formula dello stop-and-wait con propagazione normalizzata $a=t_{prop}/t_{tx}=1{,}2833/2=0{,}642$: $\eta=\dfrac1{1+2a}=\dfrac1{1+1{,}283}=0{,}438$, la stessa cosa perché $t_{tx}/(t_{tx}+2t_{prop})$ diviso per $t_{tx}$ dà $1/(1+2a)$.

Il grafico mostra che per avere un'efficienza alta con stop-and-wait servono messaggi enormi: sul collegamento Terra-Luna conviene non aspettare l'ACK (finestra scorrevole).

(5) Efficienza senza attendere l'ACK

Se l'immagine successiva parte subito dopo la precedente, il collegamento non resta mai vuoto per aspettare l'ACK: l'unica "attesa" è il ritardo end-to-end del singolo invio, $t_{prop}+t_{tx}$, perché il primo bit deve arrivare e l'ultimo deve essere trasmesso. Il numero di bit che il collegamento può contenere in quel ritardo è $$BDP'=(t_{prop}+t_{tx})\cdot R=(1{,}2833+2)\cdot100\ \text{Mbit/s}=328{,}3\ \text{Mbit}=41{,}04\ \text{MB},$$ $$\eta=\frac{25\ \text{MB}}{41{,}04\ \text{MB}}=0{,}609.$$ Lo stesso rapporto è $t_{tx}/(t_{tx}+t_{prop})=2/3{,}283=0{,}609$. Non arriva a $1$ perché con una sola immagine il collegamento resta comunque "vuoto" per il tempo di propagazione dopo l'ultimo bit trasmesso.

Confronto con la soluzione ufficiale

Ufficiale: RTT$_{min}=2{,}57$ s, RTT $=4{,}57$ s, BDP $=457$ Mbit, $\eta=43\%$, $\eta=60\%$. I primi tre valori coincidono. Per le efficienze la soluzione manoscritta usa gli stessi rapporti ($25/57$ e $25/41$ MB) ma tronca invece di arrotondare: $43{,}8\%\to43\%$ e $60{,}9\%\to60\%$. Con l'arrotondamento si ha $44\%$ e $61\%$: la differenza è solo di arrotondamento, il metodo è lo stesso. Nel manoscritto la conversione $25$ MB $\to200$ Mbit è scritta come $25\cdot8$.

Errori comuni

• Dividere $25$ MB per $100$ Mbps senza convertire i byte in bit: darebbe $0{,}25$ s invece di $2$ s.
• Dimenticare che l'RTT contiene due propagazioni ($2t_{prop}$) e scrivere $t_{prop}+t_{tx}$.
• Usare la distanza in km con $c$ in m/s (fattore $1000$ di errore).
• Confondere BDP in bit con BDP in byte nel calcolo di $\eta$ (numeratore e denominatore devono avere la stessa unità).

(Verificato con Python: $t_{prop}=1{,}2833$ s; $RTT_{min}=2{,}5667$ s; $t_{tx}=2$ s; $RTT=4{,}5667$ s; $BDP=456{,}67$ Mbit $=57{,}08$ MB; $\eta_4=0{,}438$; $BDP'=328{,}33$ Mbit; $\eta_5=0{,}609$.)