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

Testo (esempio del corso). Sette misure successive di RTT, $\text{rtt}_i=30,\ 80,\ 40,\ 130,\ 50,\ 70,\ 90$ ms. Si calcolano la stima levigata $\text{SRTT}_i$ e la deviazione media $\text{MAD}_i$ con le medie mobili esponenziali di Jacobson, $\alpha=1/8$ e $\rho=1/4$, partendo da valori iniziali nulli; poi il timeout di ritrasmissione $\text{RTO}$. In più: confronto con l'inizializzazione dell'RFC 6298 e caso con ritrasmissioni (algoritmo di Karn e raddoppio del timeout).

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

Le formule

Dopo la misura $i$-esima ($\text{rtt}_i$ = tempo tra la trasmissione di un segmento e il ricevimento del suo ACK): $$\text{SRTT}_i=(1-\alpha)\,\text{SRTT}_{i-1}+\alpha\,\text{rtt}_i,\qquad \text{MAD}_i=(1-\rho)\,\text{MAD}_{i-1}+\rho\,\left|\text{rtt}_i-\text{SRTT}_{i-1}\right|,$$ $$\text{RTO}_i=\text{SRTT}_i+4\,\text{MAD}_i$$ ($\text{RTO}_i$ è il timeout da usare per i segmenti trasmessi dopo la misura $i$). Nota l'ordine: la deviazione si aggiorna con la stima levigata precedente $\text{SRTT}_{i-1}$.

Perché due medie e il fattore 4: la media esponenziale pesa di più i campioni recenti (si adatta ai cambi di carico) con costo di una moltiplicazione, e $\alpha=1/8$, $\rho=1/4$ sono potenze di due, quindi si fanno con scorrimenti di bit (dividere per $2^k$ è uno scorrimento a destra di $k$ posizioni, Aritmetica binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.Aritmetica binaria →). Il fattore $4$ non è casuale: per RTT gaussiani $\text{MAD}=0{,}797\,\sigma$, quindi $4\,\text{MAD}\simeq3{,}19\,\sigma$ e un campione supera $\text{SRTT}+4\,\text{MAD}$ con probabilità $1-\Phi(3{,}19)\approx0{,}0007$ (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) →; dimostrazione della costante nella teoria). Il timeout storico $\text{RTO}=2\cdot\text{RTT}$ scade troppo presto se il RTT ha varianza alta (carico elevato): aggiungere un multiplo della deviazione media rende il timeout robusto.

Come si ottiene un campione

Il TCP ha un solo temporizzatore di misura alla volta (un timer per connessione, non per segmento), con la granularità del clock $G$ del sistema operativo. Esempio delle slide: parte il segmento $1$ e il timer si avvia; torna l'ACK $2$ dopo $3$ tick, misura $\text{rtt}_1=3G$ e il timer si ferma. Si manda il segmento $2$, il timer riparte; i segmenti $3$ e $4$ non vengono misurati perché il timer è già attivo; torna l'ACK $5$ dopo $2$ tick, $\text{rtt}_2=2G$. Questo spiega perché le misure sono poche (una per finestra al massimo). L'estensione timestamp (marca temporale nell'intestazione, ripetuta dal ricevitore negli ACK) permette di misurare con più precisione.

Tabella con valori iniziali nulli ($\text{SRTT}_0=\text{MAD}_0=0$)

Passaggi della prima riga: $\text{SRTT}_1=\tfrac78\cdot0+\tfrac18\cdot30=3{,}75$; $\text{MAD}_1=\tfrac34\cdot0+\tfrac14\cdot|30-0|=7{,}5$. Seconda riga: $\text{MAD}_2=\tfrac34\cdot7{,}5+\tfrac14\cdot|80-3{,}75|=5{,}625+19{,}0625=24{,}69$; $\text{SRTT}_2=\tfrac78\cdot3{,}75+\tfrac18\cdot80=3{,}28+10=13{,}28$.

Che cosa mostra la tabella.

• La stima levigata sale molto lentamente: dopo sette misure $\text{SRTT}_7=44{,}3$ ms, ma la media vera dei sette RTT è $70$ ms. È l'effetto dell'inizializzazione a $0$: la memoria dello zero iniziale pesa ancora $(7/8)^7\approx39\%$. Il perché: srotolando la formula, $\text{SRTT}_7=\alpha\sum_{k=0}^{6}(1-\alpha)^k\,\text{rtt}_{7-k}+(1-\alpha)^7\text{SRTT}_0$; i pesi dei sette campioni sommano a $1-(7/8)^7=0{,}607$ (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, $0{,}393$, va al valore iniziale nullo. Per questo $\text{SRTT}_7=0{,}607\cdot73{,}0=44{,}3$, dove $73{,}0$ è la media dei sette campioni pesata con i pesi normalizzati (più peso ai recenti), invece dei $70$ ms della media semplice.
• La deviazione $\text{MAD}$, invece, è alta e sovrastimata ($42{,}6$ ms): la differenza $|\text{rtt}_i-\text{SRTT}_{i-1}|$ misura la distanza da una stima ancora troppo bassa. Per questo, nei primi campioni, il timeout è comunque ragionevole (maggiore dei RTT osservati: $219{,}8$ ms contro $130$ ms al massimo) pur con $\text{SRTT}$ errato.
• Confronto con i valori "veri" dei sette campioni: media $70$ ms, deviazione standard $31{,}6$ ms (popolazione) o $34{,}2$ ms (campionaria), deviazione media assoluta $25{,}7$ ms. La slide riporta "avg $=70$ ms, stdev $=36{,}64$ ms" per l'intera serie, di cui mostra solo sette righe.

(Verificato con Python: i valori coincidono con le slide a meno dell'ultimo decimale; le slide troncano alcune cifre: $24{,}68$, $25{,}19$, $39{,}37$ per $24{,}69$, $25{,}20$, $39{,}38$.)

Nel grafico i punti uniti dalla linea tratteggiata sono gli rtt misurati, la linea in basso è $\text{SRTT}$ e quella in alto è $\text{RTO}$; $\text{RTO}_i$ vale per il campione $i+1$ ed è più piccolo del campione che segue solo due volte ($33{,}75<80$ e $117{,}4<130$).

Con l'inizializzazione dell'RFC 6298

La procedura standard, che evita il difetto dello zero iniziale:

• prima misura $R$: $\text{SRTT}=R$, $\text{RTTVAR}=R/2$;
• misure successive: $\text{RTTVAR}\leftarrow\tfrac34\text{RTTVAR}+\tfrac14|\text{SRTT}-R'|$, poi $\text{SRTT}\leftarrow\tfrac78\text{SRTT}+\tfrac18R'$ (stessi pesi $\rho=1/4$ e $\alpha=1/8$, stesso ordine);
• $\text{RTO}=\text{SRTT}+\max\{G,\,4\,\text{RTTVAR}\}$, e comunque non meno di $1$ s.

La stima $\text{SRTT}_7=56{,}1$ ms è più vicina alla media ($70$ ms) di quella con zero iniziale ($44{,}3$ ms), e i timeout sono più bassi ($174{,}9$ contro $214{,}7$ ms) perché non c'è la deviazione gonfiata. Con il minimo di $1$ s previsto dall'RFC tutti i valori in tabella (sono tutti sotto $1$ s) verrebbero portati a $\text{RTO}=1$ s: il minimo domina, come negli esercizi sul modello di throughput (Esercizio - throughput TCP di tre flussi con la formula del modello).

Ritrasmissioni: algoritmo di Karn e raddoppio del timeout

Problema. Se un segmento è stato ritrasmesso, l'ACK che arriva è relativo alla prima, alla seconda o alla $n$-esima trasmissione? Non si può sapere: misurando dalla prima trasmissione il campione sarebbe troppo alto, dalla ultima forse troppo basso.

Algoritmo di Karn. (1) I campioni di RTT dei segmenti ritrasmessi non si usano per aggiornare $\text{SRTT}$ e la deviazione. (2) Alla scadenza del timer, l'$\text{RTO}$ viene raddoppiato (exponential backoff) e il raddoppio resta in vigore finché non arriva un campione valido, preso da un segmento mai ritrasmesso; a quel punto si ricalcola $\text{RTO}=\text{SRTT}+4\,\text{RTTVAR}$.

Esempio. Si parta dopo le prime cinque misure con l'inizializzazione RFC 6298: $\text{SRTT}=48{,}58$ ms, $\text{RTTVAR}=28{,}44$ ms, $\text{RTO}=162{,}35$ ms (senza minimo di $1$ s per leggere i numeri).

Che cosa sarebbe successo senza Karn: se il campione fosse misurato dalla prima trasmissione, sarebbe $162{,}35+324{,}7+55=542{,}05$ ms: $\text{SRTT}=110{,}27$, $\text{RTTVAR}=144{,}70$, $\text{RTO}=689{,}1$ ms, cioè un timeout quasi quattro volte troppo grande per una rete con RTT di circa $50$ ms. Se invece fosse misurato dall'ultima trasmissione ($55$ ms) ma l'ACK fosse in realtà della prima (arrivata in ritardo), $\text{SRTT}=49{,}4$ e $\text{RTO}=141{,}1$ ms: più basso del RTT reale, con rischio di scadenze premature e ritrasmissioni inutili.

Con il minimo di $1$ s i timeout successivi alla perdita sarebbero $1$ s, $2$ s, $4$ s (l'RFC fissa un massimo di almeno $60$ s).

(Tutti i numeri sono ricalcolati con Python.)

Confronto con la soluzione ufficiale

La tabella con valori nulli coincide con quella della slide (a parte i troncamenti di cui sopra). La slide dà la formula per il timeout nella forma $\text{RTO}_i=\text{RTT}_{i-1}+4\,\text{MAD}_{i-1}$ (con il RTT medio al posto di $\text{SRTT}$); qui si usa $\text{SRTT}_i+4\,\text{MAD}_i$, equivalente. L'esempio con l'inizializzazione RFC e quello di Karn non sono nelle slide: sono ricavati dalle stesse regole.

Errori comuni

• Aggiornare la deviazione con $\text{SRTT}_i$ già aggiornato invece di $\text{SRTT}_{i-1}$.
• Misurare il RTT di un segmento ritrasmesso: viola l'algoritmo di Karn.
• Dimenticare di togliere il raddoppio del timeout alla prima misura valida successiva.
• Dimenticare il minimo di $1$ s (e che con valori iniziali nulli le prime stime sono molto basse).