Stima del timeout di ritrasmissione (RTO)

Perché serve una stima

TCP usa un timer di ritrasmissione, il retransmission timeout (RTO), per garantire la consegna dei dati quando manca il feedback del ricevente (gli ACK): se l'ACK di un segmento non arriva entro RTO, il segmento è considerato perso e viene ritrasmesso (TCP - connessione, affidabilità e controllo di flussoTCP (Transmission Control Protocol) è il protocollo di trasporto con connessione e affidabile: trasforma il servizio senza connessione e inaffidabile di IP in un flusso di byte ordinato, senza errori né duplicati. La connessione si apre con l'handshake a tre vie (SYN, SYN+ACK, ACK) e si chiude con tre o quattro segmenti (FIN). I byte sono numerati: il numero di sequenza è quello del primo byte del segmento, il numero di ACK (cumulativo) è il prossimo byte atteso. Il mittente può inviare $\min(\text{rwnd},\text{cwnd})$ byte non ancora confermati; rwnd (finestra del ricevitore, in un campo di 16 bit) è il controllo di flusso. L'errore si gestisce con checksum, ACK, timeout di ritrasmissione (RTO) e ritrasmissione rapida dopo tre ACK duplicati. Per usare tutto il canale la finestra deve valere almeno il prodotto banda-ritardo (BDP); il throughput massimo è $\text{MSS}\cdot W_{\max}/\text{RTT}$.TCP - connessione, affidabilità e controllo di flusso →). Il valore giusto dipende dalla rete e cambia nel tempo, quindi non si può fissare una volta per tutte:

• RTO troppo piccolo rispetto all'RTT: scatta quando l'ACK sta ancora arrivando, e si ritrasmette senza motivo (timeout spurio), caricando la rete e, come si vede in 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 →, riducendo la finestra senza ragione;
• RTO troppo grande: dopo una perdita vera si resta fermi a lungo, con perdita di throughput.

Per questo l'RTO si stima in linea (online) dalle misure di tempo di andata e ritorno (RTT) dei segmenti. Si definiscono due variabili (come in RFC 6298):

• SRTT (smoothed RTT): la stima "levigata" dell'RTT;
• RTTVAR (variazione dell'RTT): una stima della sua variabilità, nelle slide del corso chiamata MAD (mean absolute deviation, deviazione media assoluta).

Come si misura l'RTT

Un orologio di sistema parte all'avvio del sistema e scatta ogni $G$ secondi, la granularità del clock, che dipende dal sistema operativo; $G$ è il tempo di risoluzione con cui TCP stima l'RTO. C'è una sola misura di RTT attiva alla volta (un timer per sessione, non per pacchetto), e il timer di misura si accende e si spegne secondo l'andamento delle trasmissioni.

Esempio (dalle slide). Il timer parte alla trasmissione del pacchetto $1$ e si ferma quando arriva $\text{ACK}\,2$: tra i due eventi passano $3$ tick del clock, $\text{RTT}_1=3G$. Alla trasmissione del pacchetto $2$ il timer riparte; poiché è già attivo, i pacchetti $3$ e $4$ non vengono cronometrati; il timer si ferma con $\text{ACK}\,5$ e la seconda misura è $\text{RTT}_2=2G$.

Per misure più accurate si usa l'opzione timestamp di TCP: il mittente scrive in ogni segmento l'istante corrente nell'intestazione, e il ricevente lo riporta (echo) negli ACK; così ogni ACK porta con sé il proprio istante di partenza. Il timestamp serve anche a distinguere pacchetti con lo stesso numero di sequenza quando i 32 bit del numero di sequenza si esauriscono e ricominciano (wraparound): tempo di giro dei $2^{32}$ byte, in funzione del bitrate:

Esempio. A $10$ Mbit/s: i numeri di sequenza contano byte, quindi i $2^{32}$ numeri sono $2^{32}$ byte $=2^{32}\cdot8$ bit (il fattore $8$ converte in bit); divisi per il bitrate $C=10^7$ bit/s danno $2^{32}\cdot8/10^7=3436$ s, e $3436/60=57{,}3$ min. Un segmento rimasto in rete più di quel tempo potrebbe essere confuso con uno nuovo con lo stesso numero. ($2^{32}=4\,294\,967\,296$: Sistemi di numerazione posizionaliNotazione posizionale in base b; conversioni tra base 10, 2, 8 e 16 per interi (divisioni successive) e per parti frazionarie (moltiplicazioni successive); numeri periodici in binario.Sistemi di numerazione posizionali →.)

La media levigata (algoritmo di Jacobson)

L'algoritmo originale è di Jacobson (1988), poi sostituito dalle RFC 2988 e 6298. Con $\text{rtt}_i$ la misura dell'$i$-esimo campione e $\text{SRTT}_i$ la stima dopo $i$ campioni, si usa una media mobile esponenziale pesata (EWMA):

Formula (SRTT). $$\text{SRTT}_i=(1-\alpha)\,\text{SRTT}_{i-1}+\alpha\cdot\text{rtt}_i,\qquad\alpha=\frac18.$$

Il campione nuovo pesa $1/8$, la stima precedente $7/8$: i campioni vecchi pesano sempre meno (di un fattore $7/8$ a ogni passo), il rumore di singoli campioni è smorzato. Il nome "esponenziale" viene dal fatto che il peso del campione di $k$ passi fa è $\alpha(1-\alpha)^k$.

Perché: si sostituisce la formula in se stessa. $\text{SRTT}_i=\alpha\,\text{rtt}_i+(1-\alpha)\bigl[\alpha\,\text{rtt}_{i-1}+(1-\alpha)\text{SRTT}_{i-2}\bigr]=\alpha\,\text{rtt}_i+\alpha(1-\alpha)\,\text{rtt}_{i-1}+(1-\alpha)^2\text{SRTT}_{i-2}$ e così via, fino a $$\text{SRTT}_i=\alpha\sum_{k=0}^{i-1}(1-\alpha)^k\,\text{rtt}_{i-k}+(1-\alpha)^i\,\text{SRTT}_0.$$ I pesi dei campioni sommano a $\alpha\,\frac{1-(1-\alpha)^i}{1-(1-\alpha)}=1-(1-\alpha)^i$ (somma geometricaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica → finita) e il resto, $(1-\alpha)^i$, è il peso del valore iniziale: con $i=7$ vale $(7/8)^7=0{,}393$, e per questo partire da $\text{SRTT}_0=0$ sottostima così tanto (vedi sotto). Il grafico mostra i pesi $\alpha(1-\alpha)^k$ con $\alpha=1/8$.

Esempio. $\text{SRTT}_{i-1}=80$ ms, $\text{rtt}_i=120$ ms: $\text{SRTT}_i=\tfrac78\cdot80+\tfrac18\cdot120=70+15=85$ ms.

Algoritmo di Karn: i segmenti ritrasmessi

Se un segmento è stato ritrasmesso, l'ACK che arriva riscontra la prima, la seconda, ..., o la $n$-esima trasmissione? Non si può sapere, quindi non si può calcolare $\text{rtt}_i$ in modo corretto.

Regola (algoritmo di Karn). Si ignora la misura di RTT di un segmento che è stato ritrasmesso (non si aggiorna SRTT). Per il pacchetto successivo si usa l'ultimo RTO calcolato, e si riprende la stima solo dopo una trasmissione riuscita senza ritrasmissione. Inoltre a ogni timeout consecutivo l'RTO raddoppia (backoff esponenziale) fino a un massimo di $64\,T_0$.

Esempio. $\text{SRTT}=80$ ms e $\text{MAD}=10$ ms, cioè $\text{RTO}=80+4\cdot10=120$ ms (si trascura il minimo di 1 s per chiarezza). Il segmento inviato a $t=0$ non è riscontrato entro $120$ ms: si ritrasmette e RTO diventa $240$ ms. Un ACK arriva a $t=130$ ms: appartiene alla trasmissione originale (RTT $130$ ms) o alla ritrasmissione (RTT $10$ ms)? Non si sa.

• Se si prendesse $\text{rtt}=10$: $\text{SRTT}=\tfrac78\cdot80+\tfrac18\cdot10=71{,}25$, $\text{MAD}=0{,}75\cdot10+0{,}25\cdot|10-80|=25$, $\text{RTO}=71{,}25+100=171{,}25$ ms: un campione sbagliato: SRTT scende da $80$ a $71$ ms proprio quando la rete si è rivelata più lenta, e MAD cresce in modo spurio.
• Con Karn si scarta il campione, l'RTO resta quello raddoppiato ($240$ ms) e si ricalcola solo con il primo campione "pulito": per esempio $\text{rtt}=90$ dà $\text{SRTT}=81{,}25$, $\text{MAD}=0{,}75\cdot10+0{,}25\cdot10=10$, $\text{RTO}=121{,}25$ ms.

Se i timeout continuano, l'RTO vale $T_0,2T_0,4T_0,\dots$, con massimo $64\,T_0$ (con $T_0=120$ ms: $120,240,480,960,1920,3840,7680$ ms); la durata complessiva dei timeout consecutivi entra nel modello del tasso di invio (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 →).

La variabilità: deviazione media

Per decidere quanto margine lasciare sopra la media serve una misura della dispersione. La vera deviazione standard $\sigma=\sqrt{\tfrac1N\sum_n(\text{RTT}_n-\bar{\text{RTT}})^2}$ è costosa da calcolare in linea (radici, somme di quadrati). Si usa invece la deviazione media assoluta (mean absolute difference, MAD), economica da calcolare, ancora con una media mobile:

Formula (MAD). $$\text{MAD}_i=(1-\rho)\,\text{MAD}_{i-1}+\rho\,\big|\text{rtt}_i-\text{SRTT}_{i-1}\big|,\qquad\rho=\frac14.$$

Nella RFC 6298 la stessa quantità si chiama RTTVAR, con coefficiente $\beta=1/4$; la differenza è nel punto di partenza (vedi sotto).

Il calcolo di RTO

Una prima regola (RFC 739) imponeva $\text{RTO}_i=2\cdot\text{RTT}_{i-1}$, cioè concedeva due tempi di andata e ritorno prima di scadere. Se l'RTT ha una varianza alta (rete carica), questo metodo scade troppo presto.

Esempio. Con la serie di RTT $30,80,40,130,50,70,90$ ms (sotto), la regola $2\cdot\text{RTT}_{i-1}$ dà timeout spurio sul campione $2$ ($80>2\cdot30=60$) e sul campione $4$ ($130>2\cdot40=80$): in entrambi i casi il nuovo RTT supera il doppio del precedente, quindi l'ACK arriva dopo la scadenza del timer.

La soluzione di Jacobson è usare la media più un multiplo della deviazione media:

Formula (RTO). $$\text{RTO}_i=\text{SRTT}_i+4\cdot\text{MAD}_i,\qquad T_0=\max\{\text{RTO},\,1\text{ s}\}.$$

Perché il fattore $4$: se gli RTT sono gaussiani (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) →) vale $\text{MAD}\simeq0{,}797\,\sigma$ (ultima sezione), quindi $\text{SRTT}+4\,\text{MAD}\simeq\text{SRTT}+3{,}19\,\sigma$. La probabilità che un RTT superi la media di più di $3{,}19\sigma$ è $1-\Phi(3{,}19)\approx0{,}0007$: il timeout scatta a vuoto in meno di una misura su mille. Con un fattore minore (es. $2\,\text{MAD}\simeq1{,}6\sigma$) i timeout spuri sarebbero circa il $5{,}5\%$.

Il minimo di $1$ s (RFC 6298, nel corso $T_0=\max\{\text{RTO},1\text{ s}\}$) rende l'RTO molto più lungo della stima per RTT di pochi millisecondi. Nelle slide la formula è scritta in termini di $\text{RTT}_{i-1}$ e $\text{MAD}_{i-1}$; negli esercizi si usa la media dell'RTT del percorso più $4$ volte la deviazione media.

Esempio numerico: sette misure

Misure (slide del corso): $30,80,40,130,50,70,90$ ms. Nel corso la stima parte da $\text{SRTT}_0=\text{MAD}_0=0$. Con $\alpha=1/8$ e $\rho=1/4$:

Passaggi del primo e del secondo campione: $\text{SRTT}_1=\tfrac78\cdot0+\tfrac18\cdot30=3{,}75$; $\text{MAD}_1=0{,}75\cdot0+0{,}25\cdot|30-0|=7{,}5$. $\text{SRTT}_2=\tfrac78\cdot3{,}75+\tfrac18\cdot80=3{,}28+10=13{,}28$; $\text{MAD}_2=0{,}75\cdot7{,}5+0{,}25\cdot|80-3{,}75|=5{,}625+19{,}06=24{,}69$ (le slide riportano $24{,}68$, per arrotondamento).

I valori veri dei sette campioni sono media $=70$ ms, deviazione standard $\sigma=\sqrt{7000/7}=31{,}6$ ms (con $N-1$ al denominatore: $34{,}2$ ms; le slide riportano $36{,}64$ ms per l'intera serie, di cui si vedono solo sette righe) e deviazione media assoluta $\frac1N\sum_n|\text{rtt}_n-70|=25{,}7$ ms. Si nota che partire da $0$ sottostima pesantemente: dopo sette campioni $\text{SRTT}=44{,}3$ ms contro una media di $70$; la stima converge lentamente (il peso di $\text{SRTT}_0=0$ si smorza solo di $7/8$ a passo: $(7/8)^7=39\%$ dopo sette passi). Il margine $4\,\text{MAD}$ compensa in parte, ma l'RTO calcolato prima di un campione è inferiore al campione successivo due volte (dopo il primo, $33{,}75$ contro $80$, e dopo il terzo, $117{,}4$ contro $130$): in questi casi il timeout scatterebbe a vuoto.

RFC 6298. Alla prima misura $R$ si pone $\text{SRTT}=R$ e $\text{RTTVAR}=R/2$; poi per ogni campione si aggiorna prima $\text{RTTVAR}=(1-\beta)\text{RTTVAR}+\beta|\text{SRTT}-R|$ e poi $\text{SRTT}=(1-\alpha)\text{SRTT}+\alpha R$, con $\text{RTO}=\text{SRTT}+\max\{G,\,4\,\text{RTTVAR}\}$. Con le stesse misure:

Inizializzare con il primo campione evita il lungo "avvio" della stima: dopo sette campioni $\text{SRTT}=56{,}1$ ms (invece di $44{,}3$), più vicino alla media vera.

Nel grafico (partenza da zero): i punti uniti dalla linea tratteggiata sono gli $\text{rtt}$ misurati; la linea in basso è $\text{SRTT}$, ancora lontana dalla media di $70$ ms (linea tratteggiata orizzontale); la linea in alto è $\text{RTO}=\text{SRTT}+4\,\text{MAD}$. Il valore $\text{RTO}_i$ vale per il campione $i+1$, e solo due volte è più piccolo del campione che segue ($33{,}75<80$ e $117{,}4<130$): sono i due casi di timeout a vuoto.

Esercizio: Esercizio - SRTT, deviazione media e RTO da sette misure di RTT.

Deviazione media e deviazione standard per variabili gaussiane

Se gli RTT sono gaussiani (ipotesi usata negli esercizi), MAD e deviazione standard $\sigma$ sono legate da una costante. Sia $X$ una gaussianaN(μ, σ²) 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) → con media $\mu$ e deviazione standard $\sigma$ e $Y=X-\mu$ (gaussiana di media $0$). La MAD è il valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → $E|Y|$ del valore assoluto, cioè l'integrale di $|y|$ per la densità: $$\text{MAD}=\int_{-\infty}^{+\infty}|y|\,\frac1{\sigma\sqrt{2\pi}}e^{-y^2/(2\sigma^2)}dy=2\int_0^{+\infty}y\,\frac1{\sigma\sqrt{2\pi}}e^{-y^2/(2\sigma^2)}dy,$$ perché la funzione integranda ($|y|$ per la densità, entrambe pari) è pari e quindi l'integrale su $(-\infty,0)$ è uguale a quello su $(0,\infty)$; su $y>0$ si toglie il modulo. Con la sostituzioneSe nell'integranda c'è g(f(x))·f'(x), la sostituzione y = f(x), dy = f'(x)dx trasforma l'integrale in ∫g(y)dy = G(y) + k, poi si torna a x: G(f(x)) + k. Negli integrali definiti cambiano anche gli estremi (da c, d a f(c), f(d)). Si può usare anche al contrario, con x = f⁻¹(y). È il primo metodo a cui pensare; dà la tabella degli integrali "immediati per sostituzione".Integrazione per sostituzione → $u=y^2/(2\sigma^2)$, per cui $du=\frac{2y}{2\sigma^2}dy=y\,dy/\sigma^2$, cioè $y\,dy=\sigma^2du$ (gli estremi restano $0\to0$ e $+\infty\to+\infty$ e $e^{-y^2/(2\sigma^2)}=e^{-u}$): $$\text{MAD}=\frac{2\sigma^2}{\sigma\sqrt{2\pi}}\int_0^{+\infty}e^{-u}du=\frac{2\sigma}{\sqrt{2\pi}}\cdot1=\sigma\sqrt{\frac2\pi},$$ dove $\int_0^{+\infty}e^{-u}du=[-e^{-u}]_0^{+\infty}=0-(-1)=1$ (Integrali immediatiTabella degli integrali immediati, ottenuti leggendo al contrario le derivate delle funzioni elementari: potenze, 1/x, esponenziali, seno e coseno, tangente, arcoseno, arcotangente, funzioni iperboliche e loro inverse. Per gli integrali non ci sono regole come per le derivate, solo metodi: linearità, sostituzione, per parti.Integrali immediati →) e $\frac{2}{\sqrt{2\pi}}=\sqrt{\frac4{2\pi}}=\sqrt{\frac2\pi}$.

Proprietà (MAD di una gaussiana). $\text{MAD}=\sigma\sqrt{2/\pi}\approx0{,}797\,\sigma$.

Esempio. Un percorso formato da collegamenti con RTT indipendenti: il RTT medio totale è la somma dei medi e la varianza è la somma delle varianze (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 →: la somma di gaussiane indipendenti è ancora gaussiana). Con $\sigma_n=0{,}1;\,2;\,1;\,0{,}5$ ms: $\sigma^2_{\text{tot}}=0{,}01+4+1+0{,}25=5{,}26$ ms$^2$, $\sigma=2{,}293$ ms; $\text{MAD}=0{,}7979\cdot2{,}293=1{,}829$ ms. Con $\text{RTT}=27$ ms (la media): $\text{RTO}=\text{SRTT}+4\,\text{MAD}=27+4\cdot1{,}829=34{,}3$ ms, e quindi $T_0=\max\{34{,}3\text{ ms},1\text{ s}\}=1$ s: è il valore che si usa nel modello del tasso di invio (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 →). La verifica numerica con $400\,000$ campioni gaussiani dà $E|Y|=0{,}7985\,\sigma$.