Esercizio - throughput TCP di tre flussi con la formula del modello

Testo. Rete con cinque host $A,\dots,E$ e tre router. Collegamenti: $L_1$ ($A$-router 1), $L_2$ ($B$-router 1), $L_3$ (router 1-router 2), $L_4$ ($C$-router 2), $L_7$ (router 2-router 3), $L_5$ ($D$-router 3), $L_6$ ($E$-router 3). Flussi TCP: $A\to E$, $B\to D$, $C\to A$.

I RTT dei collegamenti sono variabili gaussiane indipendenti con media $\text{RTT}_n$ e deviazione standard $\sigma_n$. Su $L_6$ c'è un livello MAC IEEE 802.11 e un ARQ stop-and-wait di collegamento con $M=3$ tentativi per pacchetto; pacchetto di collegamento $=$ intestazione di $36$ byte $+$ segmento TCP. Altri dati: ritardo ACK $b=2$; $W_{max}=200$ segmenti; intestazione IP $20$ B, TCP $40$ B; segmento TCP di $1500$ B; intestazione applicativa $25$ B.

• Q1.1 Throughput TCP end-to-end del flusso $A\to E$ (flussi attivi uno alla volta). Q1.2 Throughput a livello applicativo.
• Q2 Throughput di $A\to E$ con $M=8$ (valore tipico del Wi-Fi).
• Q3 Throughput di $C\to A$. Q4 Throughput di $B\to D$.
• Q5 Throughput dei tre flussi attivi insieme, se i router assegnano al flusso $i$ la frazione $\xi_i$ del collegamento ($\xi_1=0{,}2$, $\xi_2=0{,}2$, $\xi_3=0{,}6$).
• Q6.1 RTT massimo di $L_4$ perché $C\to A$ sfrutti tutta la velocità disponibile. Q6.2 Che cosa succede agli altri flussi se cambia il RTT di $L_4$.

Teoria usata: Modello analitico del tasso di invio di TCPIl modello analitico del corso calcola il tasso di invio a regime B (segmenti al secondo) di un flusso TCP Reno in funzione della probabilità di perdita p, dell'RTT, del parametro di ACK ritardato b e del timeout T0. Il tempo è diviso in round di durata RTT; il ciclo della finestra tra due perdite segnalate da tre dupACK (TDP) ha media E[W] = (2-3b)/(3b) + sqrt(((3b-2)/(3b))^2 + 8(1-p)/(3bp)) e il tasso è B = E[Y]/E[A] (pacchetti inviati diviso durata di un TDP). Per p piccolo si ottiene la formula della radice quadrata B = (1/RTT) sqrt(3/(2bp)) (circa 1,22/(RTT sqrt p) per b = 1 e 0,87/(RTT sqrt p) per b = 2). Con i timeout si aggiungono la probabilità Q che una perdita finisca in timeout, E[R] = 1/(1-p) pacchetti e E[Z^TO] = T0 f(p)/(1-p) secondi di attesa: B = (E[Y] + Q E[R])/(E[A] + Q E[Z^TO]). Con la finestra massima Wmax il tasso non supera Wmax/RTT.Modello analitico del tasso di invio di TCP →, Stima del timeout di ritrasmissione (RTO)TCP ritrasmette un segmento se il suo ACK non arriva entro il timeout di ritrasmissione (RTO), che deve seguire il tempo di andata e ritorno (RTT) della rete: troppo corto provoca ritrasmissioni inutili, troppo lungo rallenta il recupero. L'RTT si misura con un solo timer per connessione (granularità G del clock). Si mantengono una media mobile esponenziale SRTT_i = (1-α)SRTT_{i-1} + α·rtt_i con α = 1/8 e la deviazione media MAD_i = (1-ρ)MAD_{i-1} + ρ|rtt_i - SRTT_{i-1}| con ρ = 1/4 (in RFC 6298 RTTVAR, β = 1/4); RTO = SRTT + 4·MAD, con minimo di 1 s. L'algoritmo di Karn ignora le misure dei segmenti ritrasmessi (non si sa a quale trasmissione si riferisce l'ACK) e a ogni timeout consecutivo il valore raddoppia fino a 64 volte T0. Per un RTT gaussiano la deviazione media vale MAD = σ·sqrt(2/π) ≈ 0,797σ.Stima del timeout di ritrasmissione (RTO) →, TCP - controllo di congestioneLa congestione nasce quando collegamenti veloci alimentano un collegamento lento: le code dei router si riempiono, i pacchetti si perdono o ritardano e, nel caso peggiore, la rete collassa (quasi solo ritrasmissioni). TCP controlla la propria finestra di congestione cwnd con il feedback delle perdite (timeout o tre ACK duplicati): slow start (cwnd raddoppia a ogni RTT) fino alla soglia ssthresh, poi congestion avoidance (+1 MSS per RTT); a ogni perdita ssthresh = W/2. Le varianti si distinguono per come reagiscono ai tre dupACK: Tahoe riparte da cwnd = 1 dopo la ritrasmissione rapida; Reno usa il fast recovery (ssthresh = cwnd/2, cwnd = ssthresh + 3, +1 per ogni altro dupACK); NewReno gestisce gli ACK parziali e recupera più perdite nella stessa finestra; SACK riscontra i blocchi ricevuti e ritrasmette solo quello che manca.TCP - controllo di congestione →, 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 →. Richiami di probabilità: Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi → (perdite su collegamenti diversi), Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale → (errori sui bit, tentativi dell'ARQ), Distribuzione gaussiana (normale)N(μ, σ²) ha densità e^(−(x−μ)²/(2σ²)) / √(2πσ²), a campana centrata in μ con larghezza σ; media μ, varianza σ²; si standardizza con Z = (X − μ)/σ ~ N(0, 1) e si calcola P(X ≤ x) = Φ((x − μ)/σ), con Φ(−z) = 1 − Φ(z); aX + b è ancora gaussiana, N(aμ + b, a²σ²).Distribuzione gaussiana (normale) → e Somma di variabili aleatorie indipendentiSe X e Y sono indipendenti, la legge di Z = X + Y è la convoluzione: p_Z(n) = Σ_k p_X(k) p_Y(n − k) nel discreto, f_Z(z) = ∫ f_X(z − y) f_Y(y) dy nel continuo. Casi notevoli: Bin(n,p) + Bin(m,p) = Bin(n+m,p), Poi(λ) + Poi(μ) = Poi(λ+μ), Geo + Geo con densità (n−1)p²(1−p)^(n−2), Exp(λ) + Exp(λ) = Γ(2,λ), gaussiane indipendenti sommano medie e varianze.Somma di variabili aleatorie indipendenti → (RTT dei collegamenti), Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →.

Lo strumento: la formula del tasso di invio

Il tasso di invio di un flusso TCP in segmenti al secondo, a partire da probabilità di perdita $p$, RTT, ritardo ACK $b$ e timeout $T_0$, è nella versione del corso $$B\simeq\min\left\{\frac{W_{max}}{\text{RTT}},\ \frac1{\text{RTT}\sqrt{\frac{2bp}3}+T_0\min\left\{1,3\sqrt{\frac{3bp}8}\right\}p\,(1+2p+4p^2)}\right\}\ \ [\text{seg/s}],$$ dove il primo termine nel minimo è il limite della finestra massima, il secondo il modello (che con $p\to0$ tende a infinito). Il throughput in bit/s si ottiene moltiplicando per la dimensione del carico utile TCP in bit (non del segmento intero).

Costruzione dei parametri per un cammino:

1. $\text{RTT}$ del cammino $=$ somma dei RTT dei collegamenti attraversati.
2. $p$ del cammino: un segmento arriva se non è perso su nessun collegamento, e le perdite sono indipendenti: $p=1-\prod_n(1-p_n)$. Il perché: l'evento «arriva» è l'intersezione degli eventi «non perso sul collegamento $n$», che essendo indipendenti hanno probabilità uguale al prodotto $\prod_n(1-p_n)$; la perdita è il complementare, $1$ meno quel prodotto.
3. Il timeout: la varianza di somme di variabili indipendenti si somma (somma di gaussiane indipendenti è gaussiana, con medie e varianze che si sommano), $\sigma^2=\sum\sigma_n^2$; per una variabile gaussiana la deviazione media assoluta (MAD) vale $\text{MAD}=\sigma\sqrt{2/\pi}\approx0{,}797\,\sigma$ (si ricava da $\text{MAD}=2\int_0^{\infty}\frac y{\sigma\sqrt{2\pi}}e^{-y^2/2\sigma^2}dy$, con la sostituzione $u=y^2/2\sigma^2$). Il timeout è $\text{RTO}=\text{RTT}+4\,\text{MAD}$ e, come nell'RFC 6298, $T_0=\max\{\text{RTO},1\ \text{s}\}$.

Q1.1: flusso $A\to E$, throughput TCP

Carico utile. $1500-20-40=1440$ B $=11\,520$ bit.

Cammino. $A$-$L_1$-$L_3$-$L_7$-$L_6$-$E$: $\text{RTT}_{AE}=2+10+10+5=27$ ms.

Perdite su $L_6$ (il tratto Wi-Fi). Il pacchetto di collegamento è lungo $L=(36+1500)\cdot8=12\,288$ bit. Una trasmissione fallisce se almeno un bit è errato: $$\tilde p_6=1-(1-P_{bit})^{L}=1-(1-4\cdot10^{-5})^{12\,288}=0{,}3883.$$ Il passaggio: la trasmissione riesce se tutti i $L$ bit sono corretti, ognuno con probabilità $1-P_{bit}$ e indipendentemente, quindi con probabilità $(1-P_{bit})^L$; il fallimento è il complementare. Numericamente, $(1-P_{bit})^L=e^{L\ln(1-P_{bit})}\simeq e^{-LP_{bit}}=e^{-0{,}4915}=0{,}6117$ (si usa $\ln(1-x)\simeq-x$, Mac-Laurin), e $1-0{,}6117=0{,}3883$. L'ARQ ritenta fino a $M=3$ volte: il pacchetto va perso solo se falliscono tutti i tentativi, che sono indipendenti, quindi $p_6=\tilde p_6^{\,M}=0{,}3883^3=0{,}0586$ (nelle slide $0{,}0585$ per arrotondamento).

Perdita end-to-end. $$p_{AE}=1-(1-p_1)(1-p_3)(1-p_7)(1-p_6)=1-1\cdot1\cdot(1-2\cdot10^{-4})(1-0{,}05855)=0{,}0587.$$ Domina $L_6$, come atteso.

Timeout. $\sigma_{AE}^2=0{,}1^2+2^2+1^2+0{,}5^2=5{,}26$ ms$^2$ (la varianza dei RTT di $L_1,L_3,L_7,L_6$), quindi $\sigma_{AE}=2{,}293$ ms; $\text{MAD}=0{,}797\cdot2{,}293=1{,}830$ ms; $\text{RTO}=27+4\cdot1{,}830=34{,}32$ ms. Poiché $34{,}32$ ms $<1$ s, $T_0=1$ s: il minimo di un secondo domina.

Tasso di invio. Il limite della finestra è $200/0{,}027=7407$ seg/s, molto più alto del modello. Termini del denominatore:

• $\text{RTT}\sqrt{2bp/3}=0{,}027\sqrt{\tfrac{2\cdot2\cdot0{,}0587}{3}}=0{,}027\cdot0{,}2799=0{,}007556$ s;
• $\min\{1,3\sqrt{3bp/8}\}=\min\{1,3\sqrt{0{,}0440}\}=\min\{1,0{,}6297\}=0{,}6297$;
• $T_0\cdot0{,}6297\cdot p\,(1+2p+4p^2)=1\cdot0{,}6297\cdot0{,}0587\cdot1{,}1313=0{,}04184$ s.

Denominatore $=0{,}04940$ s, quindi $$B=\frac1{0{,}04940}=20{,}2435\ \text{seg/s},\qquad\eta_{AE}=B\cdot11\,520=\boxed{233{,}2\ \text{kbit/s}}.$$ Poche decine di segmenti al secondo: con $p\approx6\%$ il TCP spende quasi tutto il tempo a recuperare dopo timeout da $1$ s. Le unità: $B$ è in segmenti/s e il payload in bit/segmento, quindi $20{,}2435\cdot11\,520=233\,205$ bit/s.

Il grafico mostra lo stesso modello per tutte le $p$ (RTT $27$ ms): la curva parte dal tetto della finestra massima ($W_{max}/\text{RTT}=7407$ seg/s, cioè $85{,}3$ Mbit/s) e cala come $1/\sqrt p$ finché i timeout non prendono il sopravvento; i due punti sono i casi $M=3$ ($p=5{,}87\%$) e $M=8$ ($p=0{,}0717\%$) del testo.

Q1.2: throughput a livello applicativo

L'applicazione vede solo i dati senza la sua intestazione di $25$ B: $1440-25=1415$ B $=11\,320$ bit per segmento. $$\eta^{APP}_{AE}=B\cdot11\,320=20{,}2435\cdot11\,320=\boxed{229{,}2\ \text{kbit/s}}.$$

Q2: $A\to E$ con $M=8$ tentativi

Cambia solo $p_6=\tilde p_6^{\,8}=0{,}3883^8=5{,}169\cdot10^{-4}$ (tanti tentativi rendono il collegamento molto più affidabile). Quindi $$p_{AE}^{new}=1-(1-2\cdot10^{-4})(1-5{,}169\cdot10^{-4})=7{,}168\cdot10^{-4}.$$ RTO, RTT, $T_0=1$ s restano invariati. Denominatore: $0{,}027\sqrt{2\cdot2\cdot7{,}168\cdot10^{-4}/3}=8{,}35\cdot10^{-4}$ s; $\min\{1,3\sqrt{3bp/8}\}=0{,}0696$; termine di timeout $=1\cdot0{,}0696\cdot7{,}168\cdot10^{-4}\cdot1{,}0014=5{,}0\cdot10^{-5}$ s. Somma $=8{,}85\cdot10^{-4}$ s, $B=1130{,}4$ seg/s (sotto il limite $7407$): $$\eta_{AE}^{new}=1130{,}4\cdot11\,520=\boxed{13{,}022\ \text{Mbit/s}}.$$ Cento volte meno probabilità di perdita: il throughput è circa $56$ volte più alto.

Q3: flusso $C\to A$

Cammino $C$-$L_4$-$L_3$-$L_1$-$A$ senza errori: $p_{CA}=0$. Con $p=0$ il termine del modello tende a $+\infty$ e resta il limite della finestra: $B=W_{max}/\text{RTT}_{CA}$. Il RTT è $\text{RTT}_{CA}=\text{RTT}_4+\text{RTT}_3+\text{RTT}_1=2{,}5+10+2=14{,}5$ ms, quindi $$B=\frac{200}{0{,}0145}=13\,793\ \text{seg/s},\qquad \eta=13\,793\cdot11\,520=158{,}9\ \text{Mbit/s}.$$ Ma il flusso non può superare la velocità del collegamento più lento del cammino: $\min\{B_1,B_3,B_4\}=B_3=100$ Mbit/s (figura). Quindi $$\boxed{\eta_{CA}=\min\{158{,}9,\ 100\}=100\ \text{Mbit/s}}.$$

Q4: flusso $B\to D$

Cammino $L_2,L_3,L_7,L_5$: $\text{RTT}_{BD}=2+10+10+3=25$ ms; $\sigma^2_{BD}=0{,}1^2+2^2+1^2+0{,}2^2=5{,}05$ ms$^2$, $\sigma_{BD}=2{,}247$ ms, $\text{MAD}=1{,}793$ ms, $\text{RTO}=25+4\cdot1{,}793=32{,}17$ ms $\Rightarrow T_0=1$ s. Perdita: $p_{BD}=1-(1-10^{-12})(1-0)(1-10^{-12})(1-2\cdot10^{-4})\approx p_7=2\cdot10^{-4}$. Formula: $0{,}025\sqrt{2\cdot2\cdot2\cdot10^{-4}/3}=4{,}08\cdot10^{-4}$ s; $\min\{1,3\sqrt{3bp/8}\}=0{,}0367$; timeout $=0{,}0367\cdot2\cdot10^{-4}\cdot1{,}0004=7{,}4\cdot10^{-6}$ s. Somma $=4{,}16\cdot10^{-4}$ s, $B=2406{,}2$ seg/s ($<200/0{,}025=8000$): $$\eta_{BD}=2406{,}2\cdot11\,520=\boxed{27{,}72\ \text{Mbit/s}}.$$

Q5: i tre flussi contemporaneamente

I tre flussi attraversano tutti $L_3$ (da $100$ Mbit/s), che è il collo di bottiglia comune. Il router assegna al flusso $i$ la frazione $\xi_i$: $$b_1=100\cdot0{,}2=20,\quad b_2=100\cdot0{,}2=20,\quad b_3=100\cdot0{,}6=60\ \text{Mbit/s}.$$ Il throughput di ogni flusso è il minimo tra quello che il TCP otterrebbe da solo e la quota assegnata: $$\eta_{AE}=\min\{13{,}022,\ 20\}=13{,}022,\qquad\eta_{BD}=\min\{27{,}72,\ 20\}=20,\qquad\eta_{CA}=\min\{158{,}9,\ 60\}=60\ \text{Mbit/s}.$$ $A\to E$ resta limitato dalle perdite (usa meno della sua quota); $B\to D$ e $C\to A$ sono limitati dalla quota.

Q6: RTT massimo di $L_4$

Q6.1. Per sfruttare i $60$ Mbit/s assegnati a $C\to A$ serve $\frac{W_{max}}{\text{RTT}_{CA}}\cdot11\,520\ge60\cdot10^6$, cioè $\text{RTT}_{CA}\le\frac{200\cdot11\,520}{60\cdot10^6}=38{,}4$ ms. Poiché $\text{RTT}_{CA}=\text{RTT}_4+\text{RTT}_3+\text{RTT}_1$: $$\text{RTT}_4\le38{,}4-(10+2)=\boxed{26{,}4\ \text{ms}}.$$

Q6.2. $L_4$ è usato solo dal flusso $C\to A$: gli altri flussi non cambiano. (Se lo usassero anche altri, i loro throughput andrebbero ricalcolati.)

(Tutti i numeri sono stati ricalcolati con Python: $20{,}2435$ seg/s, $233{,}205$ kbit/s, $229{,}156$ kbit/s, $1130{,}39$ seg/s e $13{,}0221$ Mbit/s, $2406{,}16$ seg/s e $27{,}719$ Mbit/s, $26{,}4$ ms.)

Confronto con la soluzione ufficiale e anomalie

• Q1, Q2, Q4, Q5 (parte $A\to E$, $B\to D$), Q6: i risultati coincidono con le slide.
• Q3, RTT del cammino: le slide scrivono "$\text{RTT}_{CA}=\text{RTT}_1+\text{RTT}_3+\text{RTT}_4=6{,}5$ ms" e ne ricavano $30\,769$ seg/s e $354{,}5$ Mbit/s. Con i valori della tabella la somma è $14{,}5$ ms ($6{,}5$ corrisponderebbe a $\text{RTT}_3=2$ ms invece di $10$). Che $14{,}5$ sia il valore coerente lo conferma Q6.1 delle stesse slide, che usa $\text{RTT}_1+\text{RTT}_3=12$ ms e ottiene $26{,}4$ ms. Il risultato finale non cambia, perché in entrambi i casi il limite è il collo di bottiglia $L_3$ ($100$ Mbit/s) e in Q5 la quota $60$ Mbit/s.
• Velocità di $L_3$: la figura dice $100$ Mbit/s, la tabella $200$; le slide usano $100$ (Q3, Q5). Con $200$, in Q3 si avrebbe $158{,}9$ Mbit/s.
• Q5, flusso $A\to E$: la slide scrive "$13{,}221$ Mbit/s": è un refuso per $13{,}0221$ Mbit/s (Q2).
• Fattore $p(1+2p+4p^2)$. Le slide del corso usano questo fattore nell'approssimazione del modello; nel lavoro originale da cui il modello è tratto compare $p(1+32p^2)$. Con il fattore originale i risultati sarebbero Q1 $20{,}56$ seg/s ($236{,}9$ kbit/s invece di $233{,}2$), Q2 $13{,}023$ Mbit/s, Q4 $27{,}719$ Mbit/s. La differenza è sensibile solo con perdite elevate ($p\approx6\%$); i risultati da riportare all'esame sono quelli del corso.

Errori comuni

• Moltiplicare i segmenti al secondo per $1500$ B invece del carico utile ($1440$ B), o per $1415$ B per il throughput TCP: il carico utile TCP esclude IP e TCP, quello applicativo anche l'intestazione dell'applicazione.
• Dimenticare il tetto di un secondo del timeout: $T_0=\max\{\text{RTO},1\ \text{s}\}$.
• Sommare le deviazioni standard invece delle varianze.
• Usare $p_6=\tilde p_6$ invece di $\tilde p_6^{\,M}$: l'ARQ riduce l'errore residuo.
• Dimenticare il limite del collo di bottiglia con $p=0$: il TCP non può superare la velocità del collegamento più lento.