Modello analitico del tasso di invio di TCP

Il modello analitico del corso risponde a una domanda: dato il tasso di perdita $p$ dei pacchetti e il tempo di andata e ritorno RTT, quanti segmenti al secondo invia in media, a regime, un flusso TCP? Il risultato è una formula chiusa, usata negli esercizi per calcolare il throughput di un percorso (Esercizio - throughput TCP di tre flussi con la formula del modello). Si basa sul comportamento di TCP Reno (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 →); i simboli sono quelli di 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 →. Per la fonte si fa riferimento al corso Internet, UniPD.

Ipotesi

• Tempo a round. Il tempo è organizzato in round (rounds) di durata RTT secondi ciascuno. In ogni round il mittente trasmette $W$ pacchetti (la finestra di congestione, che varia nel tempo). L'RTT è costante e indipendente da $W$.
• Ritardo degli ACK. $b$ è il parametro degli ACK ritardati: un ACK ogni $b$ pacchetti, di solito $b=2$. Se in un round sono trasmessi $W$ pacchetti, nel round successivo arrivano $W/b$ ACK; in CA ogni ACK fa crescere la finestra di $1/W$, quindi la finestra cresce di $1$ ogni $b$ round (di $1/b$ per round).
• Solo congestion avoidance. TCP opera sempre in CA (lo slow start è trascurato: flusso lungo).
• Perdite. Ogni pacchetto è perso con probabilità $p$. Gli errori in round diversi sono statisticamente indipendenti; nello stesso round sono correlati: se un pacchetto è perso, sono persi anche tutti quelli che lo seguono nel round.
• Pacchetti tutti della stessa dimensione: si contano pacchetti, non byte.
• Traffico pesante (heavy traffic): il mittente ha sempre dati da inviare. In un primo momento la finestra non è limitata dal ricevente ($W_{\max}$ infinito).

L'analisi si fa in due passi: (1) le perdite sono segnalate solo da $K=3$ dupACK (i timeout sono trascurati); (2) le perdite sono segnalate da tre dupACK e da timeout (importante quando $p$ cresce).

Definizione (tasso di invio). Se $N_t$ è il numero di pacchetti trasmessi nell'intervallo $[0,t]$, il tasso di invio nell'intervallo è $N_t/t$ e il tasso di invio a lungo termine (a regime) è $$B=\lim_{t\to\infty}\frac{N_t}{t}\quad[\text{pacchetti/s}].$$

Si noti che è il tasso di invio, non di arrivo: conta anche ciò che viene perso. Per avere il tasso di arrivo (goodput) si dovrebbe moltiplicare per la frazione di pacchetti non persi, $1-p$, che per $p$ piccolo è quasi $1$.

Passo 1: perdite segnalate solo da tre dupACK

I cicli TDP

Si guarda la finestra quando le perdite sono rilevate da tre dupACK: a ogni evento la finestra viene dimezzata. L'evoluzione è a dente di sega: si chiama TDP (triple duplicate period) il periodo tra due dimezzamenti consecutivi. Dopo il dimezzamento, la finestra riparte da $W_{i-1}/2$ e cresce di 1 ogni $b$ round fino a una nuova perdita.

Per il $i$-esimo TDP si definiscono:

• $A_i$: la durata del TDP, in secondi;
• $W_i$: la finestra alla fine del TDP, in pacchetti;
• $Y_i$: il numero di pacchetti inviati nel TDP.

Poiché $W_i$ dipende da $W_{i-1}$ ($W_i$ è una catena di Markov con "ricompense" $Y_i$), la sequenza $(Y_i,A_i)$ è un processo di rinnovo con ricompensa (renewal reward process). Per la teoria di questi processi il tasso medio è il rapporto tra ricompensa media e durata media del ciclo:

Formula (tasso a lungo termine). $$B=\frac{E[Y]}{E[A]}.$$

Perché: dopo $n$ cicli sono stati inviati $N=\sum_{i=1}^nY_i$ pacchetti in un tempo $t=\sum_{i=1}^nA_i$. Dividendo numeratore e denominatore per $n$, $\frac Nt=\frac{\frac1n\sum Y_i}{\frac1n\sum A_i}$, e per la legge dei grandi numeriSe X₁, X₂, ... sono i.i.d. con media μ, la media campionaria X̄ₙ = (X₁ + ... + Xₙ)/n converge a μ: in probabilità (legge debole, dimostrata con Chebyshev se la varianza è finita: P(|X̄ₙ − μ| > ε) ≤ σ²/(nε²)) e quasi certamente (legge forte). Metodo Monte Carlo: ∫ g = E[g(U)] si stima con la media di g(U₁), ..., g(Uₙ) per uniformi indipendenti.Legge dei grandi numeri e metodo Monte Carlo → le due medie campionarie tendono a $E[Y]$ e $E[A]$ per $n\to\infty$, da cui il rapporto dei valori medi.

Basta quindi studiare le statistiche di un solo TDP: $E[Y]$ e $E[A]$.

La geometria di un TDP

Nel $i$-esimo TDP:

• $\alpha_i$ è la posizione del primo pacchetto perso (contando i pacchetti inviati da inizio TDP, partendo da 1);
• $X_i$ è il round in cui avviene la perdita, il round semi-ultimo; il round successivo, il $X_i+1$-esimo, è l'ultimo, in cui si inviano $\beta_i$ pacchetti;
• dopo il pacchetto perso il mittente non lo sa ancora: invia altri pacchetti prima di accorgersi della perdita.

Relazione tra le finestre. La finestra cresce di 1 ogni $b$ round per $X_i$ round, partendo da $W_{i-1}/2$; poiché è la finestra del round semi-ultimo, $$W_i=\frac{W_{i-1}}{2}+\frac{X_i}{b}-1.\tag{1}$$

Esempio (dalla figura del corso). $W_{i-1}/2=3$, $b=2$, $X_i=10$ round: la finestra vale $3,3,4,4,5,5,6,6,7,7$ e $W_i=3+10/2-1=7$ ✓.

Pacchetti inviati. Il pacchetto perso è il numero $\alpha_i$; dopo di esso partono altri $W_i-1$ pacchetti prima che la perdita sia rilevata. (Infatti se il pacchetto perso è il $k$-esimo del round semi-ultimo, i $k-1$ precedenti sono riscontrati e permettono di inviare $\beta_i=k-1$ pacchetti nell'ultimo round; più i $W_i-k$ pacchetti del round semi-ultimo successivi a quello perso: in tutto $(W_i-k)+(k-1)=W_i-1$.) Quindi $$Y_i=\alpha_i+W_i-1.\tag{2}$$

Primo calcolo di $E[Y]$: la posizione del primo errore

Gli errori sono indipendenti con probabilità $p$ per pacchetto: la posizione del primo errore è geometrica, $$P[\alpha=k]=(1-p)^{k-1}p,\qquad k=1,2,3,\dots$$ (è la distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →: $k-1$ pacchetti riusciti, ciascuno con probabilità $1-p$, e il $k$-esimo perso) e il suo valore medioIl 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 →, ponendo $q=1-p$, $$E[\alpha]=\sum_{k=1}^{\infty}q^{k-1}(1-q)\,k=\sum_{k=1}^\infty k\,q^{k-1}-\sum_{k=1}^\infty k\,q^{k}=\sum_{k=0}^\infty q^{k}=\frac1{1-q}=\frac1p.$$ Passaggi: si distribuisce $(1-q)$; nella seconda somma si pone $j=k+1$, cioè $\sum_{k\ge1}k\,q^k=\sum_{j\ge2}(j-1)\,q^{j-1}$; sottraendo termine a termine ciò che resta è $\sum_{j\ge1}q^{j-1}=\sum_{k\ge0}q^k$ perché $k\,q^{k-1}-(k-1)q^{k-1}=q^{k-1}$. L'ultima è la serie 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 → di ragione $q<1$, che vale $\frac1{1-q}$. Dalla (2), prendendo il valore atteso:

Formula (primo calcolo). $$E[Y]=E[\alpha]-1+E[W]=\frac{1-p}{p}+E[W].\tag{3}$$

(In media passano $1/p$ pacchetti prima di un errore: con $p=0{,}01$, $100$ pacchetti.)

Secondo calcolo di $E[Y]$: la somma sulla finestra

Il numero di pacchetti si può anche contare dalla forma del TDP: durante i primi $X_i$ round la finestra assume i valori $W_{i-1}/2+k$, ciascuno per $b$ round (la finestra cresce di $1$ ogni $b$ round), con $k=0,\dots,X_i/b-1$, cioè $X_i/b$ valori distinti; poi nell'ultimo round se ne inviano $\beta_i$: $$Y_i=\sum_{k=0}^{X_i/b-1}\left(\frac{W_{i-1}}{2}+k\right)b+\beta_i=\frac{W_{i-1}}{2}\,X_i+\frac{X_i}{2}\left(\frac{X_i}{b}-1\right)+\beta_i.$$ (Il primo termine è la somma di $X_i/b$ termini uguali a $b\,W_{i-1}/2$, cioè $\frac{X_i}{b}\cdot b\cdot\frac{W_{i-1}}2=\frac{W_{i-1}}2X_i$; il secondo è $b$ per la somma dei primi numeri naturali $0+1+\dots+N$ (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →), $\tfrac{N(N+1)}2$ con $N=X_i/b-1$, quindi $b\cdot\frac12\bigl(\frac{X_i}b-1\bigr)\frac{X_i}b=\frac{X_i}{2}\bigl(\frac{X_i}b-1\bigr)$.) Dalla (1), $X_i/b-1=W_i-W_{i-1}/2$, quindi $$Y_i=\frac{W_{i-1}}2X_i+\frac{X_i}2\Bigl(W_i-\frac{W_{i-1}}2\Bigr)+\beta_i=\frac{X_i}{2}\left(\frac{W_{i-1}}{2}+W_i\right)+\beta_i,\tag{4}$$ dove i termini in $W_{i-1}$ si sono raccolti: $\frac{W_{i-1}}2X_i-\frac{X_i}2\frac{W_{i-1}}2=\frac{X_i}2\cdot\frac{W_{i-1}}2$.

Esempio (stessa figura). $W_{i-1}/2=3$, $W_i=7$, $X_i=10$: $\tfrac{10}{2}(3+7)=50$ pacchetti, più $\beta_i$; direttamente: $2\cdot(3+4+5+6+7)=50$ ✓.

Si assume che $X_i$ e $W_i$ siano indipendenti e stazionari ($E[X_i]=E[X]$, $E[W_i]=E[W]$): allora, poiché $E[W_{i-1}]/2+E[W_i]=\frac12E[W]+E[W]=\frac32E[W]$, $$E[Y]=\frac{E[X]}{2}\cdot\frac32E[W]+E[\beta].\tag{5}$$ Il numero di pacchetti dell'ultimo round $\beta_i$ si assume uniforme su $\{0,\dots,W_i-1\}$, da cui $E[\beta]=E[W]/2$ (l'appendice dell'articolo mostra che è una buona approssimazione).

Valore medio di $X$. Dalla (1) con la stazionarietà: $E[W]=E[W]/2+E[X]/b-1$, cioè $$E[X]=\frac b2E[W]+b.\tag{6}$$

L'equazione per $E[W]$

Si uguagliano i due risultati per $E[Y]$, (3) e (5), con $x=E[W]$, la (6) e $E[\beta]=x/2$ (si noti che $\frac{E[X]}2\cdot\frac32x=\bigl(\frac b2x+b\bigr)\frac{3x}4$): $$\frac{1-p}{p}+x=\left(\frac b2x+b\right)\frac{3x}{4}+\frac x2 \ \Longrightarrow\ \frac{3b}{8}x^2+\left(\frac{3b}{4}-\frac12\right)x-\frac{1-p}{p}=0,$$ dove si è sviluppato il prodotto, $\bigl(\frac b2x+b\bigr)\frac{3x}4=\frac{3b}8x^2+\frac{3b}4x$, e si è portato tutto a sinistra ($x-\frac x2=\frac x2$ cambia il coefficiente di $x$ in $\frac{3b}4+\frac12-1=\frac{3b}4-\frac12$). Moltiplicando per $8$: $$3b\,x^2+2(3b-2)\,x-\frac{8(1-p)}{p}=0.$$ È un'equazione di secondo grado con $a=3b$ positivo e termine noto negativo: ha una radice positiva e una negativa, e la finestra media è la positiva, $x=\frac{-(3b-2)+\sqrt{(3b-2)^2+24b(1-p)/p}}{3b}$. Dividendo per $3b$ dentro e fuori dalla radice ($24b/(3b)^2=8/(3b)$):

Formula (finestra media). $$E[W]=\frac{2-3b}{3b}+\sqrt{\left(\frac{3b-2}{3b}\right)^2+\frac{8(1-p)}{3bp}}\ \xrightarrow{\,p\to0\,}\ \sqrt{\frac{8}{3bp}}.$$

Esempio. $b=2$, $p=0{,}01$: $E[W]=-\tfrac23+\sqrt{\tfrac49+\tfrac{4\cdot0{,}99}{3\cdot0{,}01}}=-0{,}667+\sqrt{0{,}444+132}=10{,}84$ pacchetti (l'approssimazione $\sqrt{8/(3\cdot2\cdot0{,}01)}=11{,}55$ dà una stima un po' alta, perché trascura il termine costante).

Con la (6) e per $p\to0$: $E[X]\simeq\tfrac b2\sqrt{\tfrac8{3bp}}=\sqrt{\tfrac{b^2}4\cdot\tfrac8{3bp}}=\sqrt{\tfrac{2b}{3p}}$ (per $b=2$, $p=0{,}01$: $E[X]=12{,}84$ da formula esatta, contro $\sqrt{4/0{,}03}=11{,}55$).

La durata e la formula della radice quadrata

La durata del TDP è il numero di round per la durata di un round; round numerati da $1$ a $X_i+1$, quindi

Formula (durata media). $$E[A]=(E[X]+1)\,\text{RTT}\simeq\text{RTT}\sqrt{\frac{2b}{3p}}.$$

Il tasso di invio, solo con TD, è dunque $$B=\frac{E[Y]}{E[A]}=\frac{\frac{1-p}{p}+E[W]}{\text{RTT}\left(\frac b2E[W]+b+1\right)}.$$ Per $p\to0$ il numeratore è dominato da $1/p$ (anche $E[W]\sim1/\sqrt p$ è trascurabile): $B\simeq\dfrac{1/p}{\text{RTT}\sqrt{2b/(3p)}}$. Portando $1/p=\sqrt{1/p^2}$ sotto la radice: $\dfrac{1}{\text{RTT}}\sqrt{\dfrac{1/p^2}{2b/(3p)}}=\dfrac1{\text{RTT}}\sqrt{\dfrac{3p}{2b\,p^2}}=\dfrac1{\text{RTT}}\sqrt{\dfrac3{2bp}}$. Si ottiene la formula della radice quadrata:

Formula (radice quadrata). $$B(p,b,\text{RTT})=\frac1{\text{RTT}}\sqrt{\frac{3}{2bp}}+o\!\left(\frac1{\sqrt p}\right).\tag{7}$$

Per $b=1$ il coefficiente è $\sqrt{3/2}=1{,}22$, cioè $B\approx1{,}22/(\text{RTT}\sqrt p)$; per $b=2$ è $\sqrt{3/4}=0{,}87$: $B\approx0{,}87/(\text{RTT}\sqrt p)$ (si è usato $\sqrt{3/(2bp)}=\sqrt{3/(2b)}\cdot\frac1{\sqrt p}$).

Esempio. $b=2$, $\text{RTT}=100$ ms, $p=10^{-4}$: $B=\frac1{0{,}1}\sqrt{\frac3{4\cdot10^{-4}}}=10\cdot86{,}6=866$ segmenti/s. Dimezzare l'RTT raddoppia $B$; ridurre $p$ di un fattore $100$ moltiplica $B$ per $10$. Con $p=10^{-2}$ la (7) dà $86{,}6$ seg/s, mentre la formula esatta senza arrotondare ($E[Y]/E[A]$) dà $79{,}4$: per $p$ grande la radice quadrata sovrastima.

Passo 2: anche i timeout

Non tutte le perdite sono rilevate da tre dupACK: se la finestra è piccola non ci sono abbastanza pacchetti dopo quello perso per generare tre dupACK, e scatta un timeout. Al timeout $W=1$ e si ritrasmette il primo pacchetto non riscontrato; se scade ancora un timeout subito dopo il precedente, il timer raddoppia (e continua a raddoppiare fino a $64\,T_0$), dove $T_0$ è la durata del primo timeout.

Il ciclo di trasmissione $i$ (non più il singolo TDP) si divide in due parti: una sequenza di $m_i$ TDP (ciascuno già analizzato) e un sottociclo di timeout. Il ciclo è un processo di rinnovo con ricompensa:

• $M_i=\sum_{j=1}^{m_i}Y_{ij}+R_i$ pacchetti inviati, con $R_i$ i pacchetti inviati nel sottociclo di timeout;
• $S_i=\sum_{j=1}^{m_i}A_{ij}+Z_i^{TO}$ secondi, con $Z_i^{TO}$ la durata del sottociclo di timeout.

Allora $B=E[M]/E[S]$, con $E[M]=E[m]E[Y]+E[R]$ e $E[S]=E[m]E[A]+E[Z^{TO}]$. Chiamando $Q=1/E[m]$ e dividendo per $E[m]$:

Formula (tasso con timeout, forma generale). $$B=\frac{E[Y]+Q\,E[R]}{E[A]+Q\,E[Z^{TO}]}.\tag{8}$$

$Q=1/E[m]$ è la probabilità che una indicazione di perdita alla fine di un TDP sia un timeout: in un ciclo ci sono $m_i-1$ eventi TD e un solo timeout, quindi $m$ è geometrica con parametro $Q$. Restano da calcolare $Q$, $E[R]$, $E[Z^{TO}]$; $E[Y]$ e $E[A]$ sono già noti.

La probabilità $Q$

Sia $w$ la finestra nel round semi-ultimo. TCP può inviare $w$ pacchetti; i primi $k$ arrivano, il $(k+1)$-esimo è il primo perso (e tutti i seguenti nel round lo sono). I $k$ pacchetti riscontrati permettono di inviare $k$ pacchetti nell'ultimo round, e ogni pacchetto di questo che arriva produce un dupACK. Si ha TD se i dupACK sono almeno 3, timeout altrimenti. Due probabilità:

• $A(w,k)=\dfrac{(1-p)^kp}{1-(1-p)^w}$: probabilità che i primi $k$ pacchetti del round semi-ultimo siano corretti (e il $(k+1)$-esimo no), dato che il round contiene un errore (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →): il numeratore è la probabilità di «$k$ riusciti poi un perso»; il denominatore $1-(1-p)^w$ è la probabilità che ci sia almeno un errore in $w$ pacchetti (complementare di «tutti corretti»), cioè la somma di $(1-p)^kp$ per $k=0,\dots,w-1$, e fa sì che le $A(w,k)$ sommino a $1$;
• $C(n,m)$: probabilità che i primi $m$ pacchetti dell'ultimo round siano corretti avendone inviati $n$, cioè $(1-p)^mp$ per $m<n$ e $(1-p)^n$ per $m=n$.

Si ha timeout se $k\le2$ (non possono arrivare 3 dupACK) oppure se $k\ge3$ ma meno di $3$ dei $k$ pacchetti dell'ultimo round arrivano, quindi $$\hat Q(w)=\sum_{k=0}^{2}A(w,k)+\sum_{k=3}^{w-1}A(w,k)\sum_{m=0}^{2}C(k,m).$$ Svolgendo le somme geometriche (con $\sum_{k=0}^{n-1}x^k=\frac{1-x^n}{1-x}$) si ottiene la forma chiusa (verificata numericamente: per $w=10$, $p=0{,}01$ entrambe danno $0{,}3311$):

Formula (probabilità di timeout). $$\hat Q(w)=\min\left\{1,\ \frac{1-(1-p)^3}{1-(1-p)^w}\Big[1+(1-p)^3\big(1-(1-p)^{w-3}\big)\Big]\right\}\ \xrightarrow{\,p\to0\,}\ \min\left\{1,\frac3w\right\}.$$

Il limite $p\to0$: per Mac-LaurinTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli → $(1-p)^n\simeq1-np$, quindi $1-(1-p)^3\simeq3p$, $1-(1-p)^w\simeq wp$ e la parentesi quadra tende a $1+1\cdot(1-1)=1$: resta $\frac{3p}{wp}=\frac3w$.

Esempio. $w=10$, $p=0{,}01$: $\hat Q=0{,}331$ (contro l'approssimazione $3/w=0{,}30$). Con $w\le3$ è $\hat Q=1$ (con finestra di 3 pacchetti o meno un solo pacchetto perso non può produrre tre dupACK: sempre timeout). Poiché $w$ non è costante si usa $Q\simeq\hat Q(E[W])$.

Pacchetti e durata nel sottociclo di timeout

$E[R]$. In ogni timeout si ritrasmette un pacchetto; se è perso (probabilità $p$) segue un altro timeout. Il numero $R$ di pacchetti del sottociclo è quindi geometrico, $P[R=i]=p^{i-1}(1-p)$, e $$E[R]=\frac1{1-p}.$$

$E[Z^{TO}]$. La durata di $i$ timeout consecutivi è, con il raddoppio ($T_0,2T_0,4T_0,\dots$) fino a $64T_0$: $$L_i=\begin{cases}(2^i-1)\,T_0 & i=1,\dots,6\\ \big(63+64(i-6)\big)\,T_0 & i\ge7.\end{cases}$$ (per $i\le6$ è $T_0(1+2+\dots+2^{i-1})=(2^i-1)T_0$, somma di una progressione geometrica; dal settimo in poi ogni timeout in più dura $64T_0$). I valori sono $1,3,7,15,31,63,127,191,\dots$ volte $T_0$. Mediando su $R$: $$E[Z^{TO}]=\sum_{i\ge1}L_i\,P[R=i]=T_0\,\frac{f(p)}{1-p},\qquad f(p)=1+p+2p^2+4p^3+8p^4+16p^5+32p^6.$$ Un modo più breve per ritrovarlo: il $j$-esimo timeout del sottociclo avviene solo se i $j-1$ precedenti sono falliti, con probabilità $p^{j-1}$, e dura $\min\{2^{j-1},64\}\,T_0$. Quindi $$E[Z^{TO}]=T_0\Bigl[1+2p+4p^2+8p^3+16p^4+32p^5+64p^6\bigl(1+p+p^2+\dots\bigr)\Bigr],$$ e la parentesi finale è la serie geometrica $\frac1{1-p}$. Moltiplicando e dividendo per $1-p$, il numeratore diventa $(1+2p+4p^2+8p^3+16p^4+32p^5)(1-p)+64p^6$; svolgendo il prodotto ogni coefficiente intermedio si dimezza ($2p-p=p$, $4p^2-2p^2=2p^2$, ... $-32p^6+64p^6=32p^6$) e si ottiene proprio $f(p)$. (Controllo con $p=0{,}1$: la somma numerica dà $1{,}249991$, come $f(0{,}1)/0{,}9=1{,}249991$.)

Il modello completo

Sostituendo in (8), con $E[A]=\text{RTT}(E[X]+1)=\text{RTT}\left(\tfrac b2E[W]+b+1\right)$:

Formula (modello completo, "full model"). $$B(p,b,\text{RTT},T_0)=\frac{\dfrac{1-p}{p}+E[W]+\hat Q(E[W])\dfrac1{1-p}}{\text{RTT}\left(\dfrac b2E[W]+b+1\right)+\hat Q(E[W])\,\dfrac{T_0\,f(p)}{1-p}}.\tag{9}$$

Il modello approssimato

Per $p$ piccolo, con $E[W]\simeq\sqrt{8/(3bp)}$ e $\hat Q\simeq\min\{1,3/E[W]\}=\min\{1,3\sqrt{3bp/8}\}$, il numeratore è $\simeq1/p$, il tempo del TDP è $\simeq\text{RTT}\sqrt{2b/(3p)}$. Nel secondo membro del denominatore $\frac{f(p)}{1-p}=1+2p+4p^2+8p^3+\dots$ (i coefficienti sono le somme parziali di quelli di $f$: $1,2,4,8,\dots$) si tiene il polinomio fino a $4p^2$. Moltiplicando numeratore e denominatore per $p$ il numeratore diventa $1$, $\text{RTT}\,p\sqrt{2b/(3p)}=\text{RTT}\sqrt{2bp/3}$ e $\hat Q\,T_0\,p\,\frac{f(p)}{1-p}$ resta come termine dei timeout; si ottiene:

Formula (modello approssimato). $$B\simeq\frac1{\text{RTT}\sqrt{\dfrac{2bp}3}+T_0\min\left\{1,\,3\sqrt{\dfrac{3bp}8}\right\}p\,(1+2p+4p^2)}\quad[\text{seg/s}].\tag{10}$$

Il fattore $p\,(1+2p+4p^2)$ è quello usato nelle slide del corso e negli esercizi. Nel lavoro originale compare invece $p\,(1+32p^2)$: le due forme approssimano lo stesso polinomio $f(p)$ e per $p$ piccolo danno risultati quasi uguali (per l'esempio sotto $20{,}24$ contro $20{,}56$ seg/s). Se la finestra non può superare $W_{\max}$ (limite del ricevitore o del buffer) il tasso non supera $W_{\max}/\text{RTT}$:

Formula (tetto della finestra). $$B^{W_{\max}}=\min\left\{\frac{W_{\max}}{\text{RTT}},\ B(p,b,\text{RTT},T_0)\right\}\quad[\text{pacchetti/s}].\tag{11}$$

Per avere il throughput in bit/s si moltiplica per la dimensione del payload in bit.

Quanto bene approssimano le formule

Confronto numerico per $b=2$, $\text{RTT}=100$ ms, $T_0=1$ s (seg/s; calcolato con Python):

Per $p\lesssim10^{-3}$ le formule coincidono entro circa il $5\%$ ($10^{-4}$: $866$ contro $857$). Per $p\gtrsim10^{-2}$ la radice quadrata sovrastima di molto, perché ignora i timeout: con $p=0{,}1$ è $27{,}4$ contro $7{,}1$ del modello completo. L'approssimato (10) resta entro circa il $12\%$ dal completo per $p\le3\cdot10^{-2}$ ($29{,}1$ contro $25{,}9$ a $p=3\cdot10^{-2}$) e coincide quasi del tutto a $p=0{,}1$.

Sul grafico (scala logaritmica in $p$, $\text{RTT}=100$ ms, $T_0=1$ s, $b=2$): la radice quadrata $B\propto p^{-1/2}$ ha pendenza $-1/2$ in scala log-log, e si stacca dalle altre per $p>10^{-3}$; l'approssimato (tratteggio) e il completo restano vicini.

Per visualizzare la forma di un TDP, il grafico seguente mostra la finestra round per round dell'esempio della figura del corso ($W_{i-1}/2=3$, $b=2$, $X_i=10$): $3,3,4,4,5,5,6,6,7,7$, cioè $W(r)=3+\lfloor (r-1)/b\rfloor$; subito dopo la perdita la finestra viene dimezzata.

Esempio completo

Percorso con $\text{RTT}=27$ ms, $b=2$, $T_0=1$ s (nel corso $T_0=\max\{\text{RTO},1\text{ s}\}$: 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) →), $W_{\max}=200$ segmenti, payload TCP di $1440$ byte e probabilità di perdita complessiva del percorso $p=0{,}058740$ (con la formula $p=1-\prod(1-p_n)$ sui collegamenti attraversati, dove l'errore sul collegamento radio domina). Passi:

1. Tetto. $W_{\max}/\text{RTT}=200/0{,}027=7407$ seg/s (al massimo $W_{\max}$ segmenti per ogni RTT di $27$ ms): molto più alto di quello che segue, quindi non è il limite.
2. Primo termine del denominatore. Con $b=2$, $2bp/3=4\cdot0{,}05874/3=0{,}07832$, la cui radice è $0{,}27986$. $\text{RTT}\sqrt{2bp/3}=0{,}027\cdot0{,}27986=0{,}007556$ s (RTT in secondi).
3. Termine dei timeout. Qui $3bp/8=6\cdot0{,}05874/8=0{,}044055$, con radice $0{,}20989$ e triplo $0{,}6297$: $\min\{1,\,3\sqrt{3bp/8}\}=\min\{1,\,0{,}6297\}=0{,}6297$ (è la stima di $\hat Q$: circa il $63\%$ delle perdite finisce in timeout); $p\,(1+2p+4p^2)=0{,}05874\cdot1{,}13128=0{,}066451$; il prodotto con $T_0=1$ è $0{,}6297\cdot0{,}066451=0{,}041843$ s.
4. Tasso. $B=\dfrac1{0{,}007556+0{,}041843}=\dfrac1{0{,}049399}=20{,}2435$ seg/s, minore del tetto: è il valore valido.
5. Throughput in bit/s. $20{,}2435\cdot1440\cdot8=233{,}2$ kbit/s (il payload va espresso in bit: $1440$ byte $\times8=11\,520$ bit per segmento).

Per confronto, con gli stessi dati: la radice quadrata (7) darebbe $1/(0{,}027\cdot0{,}27986)=132{,}3$ seg/s, una sovrastima enorme perché ignora i timeout; il modello completo (9) dà $E[W]=4{,}003$, $\hat Q=0{,}8096$, numeratore $16{,}024+4{,}003+0{,}860=20{,}888$, denominatore $0{,}189+0{,}917=1{,}106$, quindi $B=18{,}88$ seg/s ($\simeq7\%$ in meno dell'approssimato). Con il fattore $p\,(1+32p^2)$ dell'articolo originale si avrebbe $20{,}56$ seg/s.

L'applicazione a più flussi che condividono un collegamento è in Esercizio - throughput TCP di tre flussi con la formula del modello.

Limiti del modello

• Vale per il comportamento stazionario di un flusso lungo in congestion avoidance: lo slow start (flussi brevi) non è modellato.
• L'RTT è supposto costante e indipendente dalla finestra: in realtà le code lo allungano.
• Le perdite sono supposte con probabilità $p$ fissa e indipendente tra round, con correlazione nel round (disciplina drop-tail): le perdite reali sono più irregolari.
• Alcune approssimazioni ($X_i$ e $W_i$ indipendenti, $\beta_i$ uniforme, $E[W]\to\sqrt{8/(3bp)}$) valgono per $p$ piccolo.
• Le varianti come SACK recuperano meglio da perdite multiple e hanno throughput maggiore di quello previsto per Reno.