Esercizio - Finestra scorrevole e buffer del ricevitore

Testo. Collegamento punto-punto con bitrate al PHY $R=1$ Mbit/s e ritardo di propagazione $\tau_p=25$ ms. Il DLL usa ARQ a finestra scorrevole e controllo di flusso a finestra scorrevole. Un file di $12\,500$ byte è trasferito tra i due nodi in pacchetti da $1250$ byte, con intestazione trascurabile. Il ricevitore ha un buffer DLL di dimensione $Q_B=2500$ byte.

1. Tempo totale di trasferimento (dalla trasmissione del primo bit alla ricezione dell'ultimo), senza errori.
2. Massimo throughput effettivo ottenuto nel trasferimento del file.
3. Che ritardo si avrebbe senza il DLL (cioè senza ARQ e controllo di flusso)?
4. Come cambiano i risultati se la finestra fosse più grande del BDP?

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 →, 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 →.

Dati

• Pacchetto: $F=1250\cdot8=10\,000$ bit; numero di pacchetti $n=\dfrac{12\,500}{1250}=10$ (file $=100\,000$ bit).
• Tempo di trasmissione: $t_F=\dfrac{F}{R}=\dfrac{10^4}{10^6}=10$ ms.
• Ciclo (ACK trascurabile): $RTT=t_F+2\tau_p=10+50=60$ ms.
• Finestra imposta dal buffer: il ricevitore non può avere più di $Q_B/F=2500/1250=2$ pacchetti non ancora consegnati: la finestra del mittente è $N=2$ pacchetti.
• BDP (con l'RTT come ritardo): $R\cdot RTT=10^6\cdot0{,}06=60\,000$ bit $=6$ pacchetti. La finestra minima per trasmettere in continuo è $N\ge t_G/t_F=60/10=6$.

Poiché $N=2<6$ la finestra è troppo piccola: il mittente trasmette $2$ pacchetti e si ferma ad aspettare l'ACK. Unità: $R\cdot RTT=10^6\ \text{bit/s}\cdot0{,}06\ \text{s}=60\,000$ bit, e dividendo per i $10\,000$ bit di un pacchetto si hanno i $6$ pacchetti della capacità del tubo.

Punto 1: tempo totale con $N=2$

Sia $s_k$ l'istante di inizio della trasmissione del pacchetto $k$. L'ACK di $k$ arriva a $s_k+RTT=s_k+60$ ms. Il pacchetto $k+2$ può partire solo quando è libera la finestra (arrivato l'ACK di $k$) e quando il pacchetto $k+1$ ha finito di essere trasmesso: $$s_{k+2}=\max\left(s_{k+1}+t_F,\ s_k+RTT\right).$$

La trasmissione procede quindi a raffiche di due pacchetti ogni $60$ ms (due pacchetti $=20$ ms di trasmissione, poi $40$ ms di attesa). L'ultimo pacchetto parte a $250$ ms, finisce di essere trasmesso a $260$ ms e arriva a $260+25=285$ ms: $$T_{tot}=285\ \text{ms}.$$

Punto 2: throughput effettivo

$$S=\frac{\text{bit del file}}{T_{tot}}=\frac{100\,000}{0{,}285}\approx351\ \text{kbit/s}\ (\approx350\ \text{kbit/s}).$$ Controllo: in ogni ciclo da $60$ ms si trasmettono $N\cdot F=20\,000$ bit, cioè $333$ kbit/s a regime; il valore finale è un po' maggiore perché l'ultimo ciclo non aspetta l'ACK.

Punto 3: senza DLL

Senza ARQ né controllo di flusso il mittente trasmette in continuo, con tutti i pacchetti uno dietro l'altro: $$T=n\,t_F+\tau_p=10\cdot10+25=125\ \text{ms}.$$ (Il buffer del ricevitore farebbe perdere i pacchetti in eccesso, ma nell'esercizio si calcola solo il tempo.)

Punto 4: finestra maggiore del BDP

Con $N\ge6$ pacchetti (finestra $\ge$ BDP) il mittente non si ferma mai: la trasmissione è continua, come senza DLL. Il tempo è $125$ ms e il throughput effettivo $$S=\frac{100\,000}{0{,}125}=800\ \text{kbit/s}.$$ $800$ kbit/s è inferiore a $R=1$ Mbit/s per via della propagazione non trascurabile ($25$ ms su $125$): lo stesso valore si ottiene con $N=6$, e una finestra più grande non migliora ancora, perché è già continuo.

Valori intermedi: con la stessa regola $s_{k+N}=\max(s_{k+N-1}+t_F,\ s_k+RTT)$ il tempo cala con $N$ finché la finestra non copre il tubo, poi si ferma a $n\,t_F+\tau_p=125$ ms.

Confronto con la soluzione ufficiale

Ufficiale: $\approx285$ ms; $\approx350$ kbit/s; $125$ ms; per finestra maggiore del BDP $125$ ms e $800$ kbit/s. Coincide ($351$ kbit/s è arrotondato a $350$ dalla soluzione).

Errori comuni

• Confondere le unità del buffer: $Q_B$ è in byte e il pacchetto pure, quindi la finestra è $2500/1250=2$ pacchetti (non $2500$ bit divisi per byte).
• Ignorare il buffer e usare subito la finestra del BDP ($6$ pacchetti): nel controllo di flusso a finestra è il buffer del ricevitore a fissare la finestra.
• Calcolare $285$ ms come $5$ cicli da $60$ ms più qualcosa: l'ultimo ciclo è più corto ($250+10+25$).
• Dividere i bit per il tempo senza chiarire se si include la propagazione: qui il throughput effettivo è $\text{bit del file}/T_{tot}$.

(Verificato con Python: $t_F=10$ ms, $RTT=60$ ms, BDP $=60\,000$ bit $=6$ pacchetti; istanti di partenza $0,10,60,70,\dots,250$ ms; $T_{tot}=285$ ms, $350{,}9$ kbit/s; senza DLL $125$ ms, $800$ kbit/s.)