Il capitolo 12 ha descritto come il controllo di congestione del TCP modifica la finestra di trasmissione: Slow Start, Congestion Avoidance, Fast Retransmit, Fast Recovery. Questo capitolo affronta la domanda successiva, quella quantitativa: quanto velocemente una connessione TCP trasferisce dati, e quanto tempo impiega a completare un trasferimento. Le slide del corso introducono tre indici distinti, che è importante non confondere.
Il throughput è la quantità complessiva di informazioni inviate per unità di tempo. È l'indice che guarda al lato del trasmettitore: conta tutto ciò che parte, ritrasmissioni comprese. Il goodput è la quantità di informazioni utili inviate con successo per unità di tempo, escludendo ritrasmissioni e duplicazioni: è l'indice che guarda al lato del ricevitore, cioè ciò che l'applicazione realmente ottiene. Vale sempre goodput ≤ throughput, e la differenza è esattamente il prezzo pagato per l'affidabilità. La latenza è invece il tempo totale necessario a un client per ricevere i dati richiesti: non è un rate ma un tempo, e per una connessione TCP si misura dall'istante in cui il client avvia la connessione all'istante in cui ha ricevuto l'intero file.
Le slide osservano che le prestazioni del TCP sono influenzate principalmente da tre fattori: la dinamica della finestra di trasmissione W(t), gli eventi che causano ritardo o perdita dei segmenti, e gli ACK duplicati o mancanti che ne derivano. I modelli analitici si costruiscono a diversi livelli di complessità; questo capitolo segue le slide e presenta i due modelli semplici e approssimati che il corso usa come strumenti di calcolo: il modello del throughput, che considera l'effetto della congestione, e il modello della latenza, che la trascura.
Il primo modello approssima la dinamica della finestra di congestione con un andamento periodico. Le ipotesi sono cinque, e vanno imparate a memoria perché ogni formula del capitolo ne discende:
CW << AW;W(t) = WL;Con queste ipotesi la finestra segue il classico dente di sega. Durante l'i-esimo RTT vengono inviati Wi segmenti. Al termine dell'RTT, se tutti gli ACK sono stati ricevuti correttamente, la finestra cresce di un segmento: Wi+1 = Wi + 1, finché non raggiunge WL. Quando la finestra ha praticamente raggiunto WL, si verifica la perdita periodica e immediatamente dopo la finestra si dimezza: W = WL/2. Da lì ricomincia la crescita lineare. Il periodo del dente di sega è quindi
T = (WL/2) · RTT
perché servono WL/2 incrementi di un segmento per RTT per tornare da WL/2 a WL.
Il modello periodico sostituisce la complessità reale (perdite aleatorie, RTT variabile, fasi di recupero) con un ciclo regolare: crescita lineare, perdita al picco, dimezzamento. Tutte le formule del throughput nascono dal fatto che in un periodo si perde esattamente un segmento, quindi il numero di segmenti inviati per periodo è 1/p.
Il valore di picco WL non è un dato del problema: va ricavato dalla probabilità di perdita p. Il ragionamento delle slide conta i segmenti inviati in un periodo in due modi diversi e li uguaglia.
Il primo modo è diretto: se p è la percentuale di segmenti persi e in ogni periodo T si perde un segmento, allora il numero di segmenti inviati in ogni periodo è
segmenti per periodo = 1/p
Il secondo modo conta gli stessi segmenti dalla crescita della finestra. Trascurando la discretizzazione dovuta ai singoli segmenti, la quantità di dati trasmessi in un periodo è l'area sotto la curva W(t). Il dente di sega è un triangolo di base WL/2 (in RTT) e altezza WL − WL/2 = WL/2 (in segmenti): l'area vale
area = ½ · (base) · (altezza) = ½ · (WL/2) · (WL/2) = WL²/8
Attenzione: l'area va calcolata sul triangolo completo, che ha base WL/2 e altezza WL/2, ma le slide la esprimono come 3WL²/8 perché la contano come area del trapezio sotto il dente di sega (rettangolo di base WL/2 e altezza WL/2, più triangolo superiore di base WL/2 e altezza WL/2): WL²/4 + WL²/8 = 3WL²/8. Le due letture coincidono perché il triangolo completo del dente di sega ha area WL²/8 e il rettangolo sottostante WL²/4: in totale 3WL²/8.
Uguagliando i due conteggi:
1/p = 3WL²/8 ⇒ WL = √(8/(3p))
La finestra massima cresce quindi come l'inverso della radice quadrata della probabilità di perdita: per dimezzare la perdita la finestra di picco cresce solo di un fattore √2. È una relazione che spiega perché le reti a bassa perdita siano così preziose per i trasferimenti lunghi.
3WL²/8 segmenti per periodo.Il throughput medio nel periodo T è il rapporto tra il numero di byte trasmessi nel periodo e la durata del periodo stesso. I byte trasmessi sono (1/p) · MSS; la durata è T = (WL/2) · RTT. Sostituendo WL = √(8/(3p)) e semplificando si ottiene la formula centrale del capitolo:
S̄ = (MSS/RTT) · √(3/(2p))
espressa in bit al secondo. Espressa in numero medio di segmenti per RTT, la stessa formula diventa
S̄′ = √(3/(2p))
La forma a segmenti per RTT è quella che si usa nei calcoli a mano, perché evita di portarsi dietro MSS e RTT fino alla fine. Il risultato ha una lettura fisica importante: il throughput medio del TCP in Congestion Avoidance è inversamente proporzionale alla radice quadrata della probabilità di perdita. Ridurre la perdita di un fattore 4 raddoppia il throughput; ridurla di un fattore 100 lo decuplica. È la legge che governa i trasferimenti lunghi su Internet.
La formula vale sotto le ipotesi del modello periodico: sorgente satura, perdita periodica, TCP sempre in Congestion Avoidance, CW << AW. Se la finestra annunciata AW limita la finestra di congestione, o se le perdite non sono periodiche, la formula va corretta come mostrato nelle sezioni 6 e 7.
Le slide riportano anche la simulazione di W(t) per TCP Reno, che mostra come il dente di sega reale sia irregolare: i picchi non sono tutti uguali, perché le perdite non avvengono esattamente allo stesso valore di finestra. Il modello periodico è appunto una approssimazione di questa dinamica, e la sua utilità sta nel produrre formule chiuse che si possono valutare con una calcolatrice.
Finora si è assunto che la destinazione risponda con un ACK per ogni segmento ricevuto. Molte implementazioni usano invece gli ACK ritardati (delayed ACK): la destinazione risponde con un ACK ogni b segmenti ricevuti, tipicamente b = 2. Il parametro b entra nel modello in due punti.
Primo: la crescita della finestra rallenta. Al termine dell'i-esimo RTT, se tutti gli ACK sono stati ricevuti correttamente, la finestra cresce di 1/b segmenti: Wi+1 = Wi + 1/b. La finestra aumenta di un intero segmento ogni b finestre trasmesse, cioè ogni b RTT. La risalita da WL/2 a WL richiede quindi b·WL/2 RTT, e il periodo diventa
T = (b·WL/2) · RTT
Secondo: il conteggio per area cambia. Il triangolo del dente di sega ha ora base b·WL/2 e altezza WL/2, quindi l'area totale sotto la curva è 3bWL²/8. Uguagliando a 1/p:
WL = √(8/(3bp))
e il throughput medio diventa
S̄ = (MSS/RTT) · √(3/(2bp))
Gli ACK ritardati riducono il throughput di un fattore √b rispetto al caso b = 1: con b = 2 il throughput medio è circa il 71% di quello con ACK immediati, a parità di perdita. È il prezzo della riduzione del carico di ACK sulla rete.
Il modello finora ha assunto CW << AW, cioè che la finestra di congestione sia sempre il collo di bottiglia. Quando la finestra annunciata AW è piccola, la storia cambia: la perdita periodica avviene dopo che si è raggiunta la AW annunciata dalla destinazione, e il dente di sega si deforma.
L'andamento periodico di W(t) è ora composto da due fasi: una fase di crescita da AW/2 fino a AW, seguita da una fase costante in cui la finestra resta pari a AW per un certo numero k di RTT, finché non subentra la perdita. La durata del periodo è
T = (b·AW/2 + k) · RTT
Il numero k di RTT a finestra costante si ricava dal fatto che in un periodo si perdono 1/p segmenti. L'area sotto la curva è la somma del triangolo di risalita (area 3bAW²/8) e del rettangolo di altezza AW e larghezza k (area k·AW):
1/p = 3bAW²/8 + k·AW ⇒ k = 1/(p·AW) − 3bAW/8
Il throughput medio diventa
S̄ = (MSS/RTT) · (1/p) / (b·AW/2 + k)
La lettura è importante: quando AW limita la finestra, il throughput medio è più basso di quello del modello senza AW, perché la finestra non può mai superare AW e il dente di sega è "schiacciato". Nei compiti, il confronto tra WL (o Wmax) e AW decide quale formula usare: se WL ≤ AW la finestra annunciata non ha effetto; se WL > AW va applicata la correzione con k.
(bAW/2 + k) · RTT; il valore di k si ricava dal vincolo di un segmento perso per periodo.Il modello periodico assume perdite a intervalli regolari. Nella realtà ogni segmento può essere perso con probabilità p, in modo indipendente per ogni segmento e per ogni fase di Congestion Avoidance. Le slide mostrano che, se p << 1, ciascuna fase di Congestion Avoidance può essere modellata come un periodo con parametri equivalenti: ogni ciclo del dente di sega ha il proprio picco WL,k e la propria durata Tk, ma la struttura è la stessa del caso periodico.
La giustificazione è probabilistica. In una fase di Congestion Avoidance che parte da WL/2, la probabilità che un dato segmento sia il primo a essere perso dipende dalla posizione del segmento nella fase; per p piccolo, la distribuzione del picco WL,k è concentrata attorno al valore medio √(8/(3p)) del caso periodico. Le formule del throughput medio restano quindi valide in media, e i compiti le applicano direttamente anche quando il testo parla di "perdite aleatorie" o "perdite puntuali periodiche": la differenza è concettuale, non di calcolo.
Nei testi d'esame la dicitura "perdite puntuali periodiche ogni N segmenti" significa p = 1/N, e la dicitura "perdite aleatorie con probabilità p" significa usare lo stesso p nelle stesse formule. Il modello periodico è l'unico strumento di calcolo richiesto: la distinzione serve a riconoscere quando le ipotesi sono rispettate.
Il secondo modello delle slide valuta la latenza di una connessione TCP: il tempo che intercorre tra l'istante ti in cui il client fa partire la connessione e l'istante tf in cui il client ha ricevuto il file completo,
D = tf − ti
Le ipotesi del modello di latenza sono diverse da quelle del modello di throughput, e vanno tenute distinte:
CW << AW);La notazione è: S = 8·MSS (dimensione di un segmento in bit), F = N·S (dimensione del file in bit, N segmenti), C la bit rate da server a client, S/C il tempo di trasmissione di un segmento, RTT il round-trip time.
La latenza è minima quando la finestra di trasmissione non limita il flusso dei dati. In quel caso il tempo si compone di tre parti:
DMIN = 2·RTT + F/C
Questo è il lower bound per la latenza TCP: nessuna connessione può trasferire un file più velocemente, perché il handshake e la richiesta richiedono due RTT prima che il primo byte di dati possa partire.
Il primo caso concreto di latenza considera un server che usa sempre una finestra di dimensione fissa W. Quando la richiesta del client arriva, il server trasmette W segmenti; successivamente trasmette un segmento per ogni ACK ricevuto. Il comportamento dipende dal confronto tra il tempo di trasmissione della finestra W·S/C e il tempo S/C + RTT necessario a ricevere l'ACK del primo segmento della finestra. Si distinguono tre casi.
Il server riceve l'ACK del primo segmento della finestra corrente prima di aver terminato la trasmissione della finestra stessa. I segmenti sono trasmessi di continuo finché l'intero file è stato trasferito: il flusso dati non è mai interrotto e la latenza è minima,
D = DMIN = 2·RTT + F/C
È la finestra di trasmissione ideale: l'ACK del primo segmento arriva esattamente quando la trasmissione della finestra termina. Il canale è saturato senza interruzioni e senza accodamento: anche qui D = DMIN. La condizione si risolve in W = 1 + RTT·C/S, che è il prodotto banda×ritardo espresso in segmenti (più uno).
Il server riceve l'ACK del primo segmento dopo aver terminato la trasmissione della finestra. Una volta inviata una finestra, il server si ferma ad aspettare gli ACK, poi trasmette un'altra finestra. Il numero di finestre necessarie a trasferire l'intero file è
K = ⌈F/(W·S)⌉
Nell'intervallo tra una coppia di finestre consecutive il server è in attesa degli ACK: si ferma K−1 volte, e il tempo di attesa per ciascun turno è
TW = RTT − (W−1)·S/C
perché l'ACK del primo segmento arriva dopo S/C + RTT, ma il server ha già trasmesso W−1 segmenti dopo di esso, impiegando (W−1)·S/C. La latenza vale quindi
D = 2·RTT + F/C + (K−1)·TW = DMIN + (K−1)·(S/C + RTT − W·S/C)
La latenza cresce rispetto a DMIN quando servono più finestre (K > 1) e quando RTT >> S/C con W non abbastanza grande; tende a DMIN quando W·S/C tende a S/C + RTT; coincide con DMIN quando K = 1, cioè una singola finestra è sufficiente.
(K−1)·TW.Il caso realistico considera l'evoluzione della finestra secondo le fasi di Slow Start e Congestion Avoidance, fino al raggiungimento del minimo tra AW e la finestra ideale WID. Superato il valore della finestra ideale (il prodotto banda×ritardo), la capacità del canale è satura: il server trasferisce sempre la stessa quantità di dati al client per ciascun RTT, indipendentemente dal valore della finestra di congestione.
La latenza si ottiene sommando il numero di RTT necessari per ciascuna fase:
D = (1 + kSS + kCA + kAW/ID) · RTT
dove l'1 iniziale è l'RTT di apertura della connessione, kSS gli RTT di Slow Start, kCA gli RTT di Congestion Avoidance e kAW/ID gli RTT della fase finale a finestra costante pari a min(AW, WID).
Durante la Slow Start vengono trasmessi NSS segmenti. Numerando gli RTT della fase a partire da i = 0 e assumendo W = 1 nel primo RTT, nell'i-esimo RTT vengono trasmessi Wi = 2i segmenti. La fase dura
kSS = log2(SSThr)
RTT, e il numero di segmenti trasmessi è NSS = 2kSS − 1. Se la fase partisse con W = 2 (come nei compiti che fissano la finestra iniziale a 2 MSS), si avrebbe kSS = log2(SSThr) − 1 e NSS = 2kSS+1 − 2.
Numerando gli RTT della fase a partire da j = 0 e assumendo W = SSThr nel primo RTT, nel j-esimo RTT vengono trasmessi Wj = SSThr + j segmenti. La fase dura
kCA = min(AW, WID) − SSThr
RTT, e il numero di segmenti trasmessi è la somma aritmetica
NCA = kCA·SSThr + (kCA−1)·kCA/2
che i compiti ricordano con la formula ∑j=0kCA−1 j = (kCA−1)·kCA/2.
Raggiunto il valore min(AW, WID), vengono trasmessi esattamente min(AW, WID) segmenti per RTT. Restano da trasmettere NAW/ID = N − NSS − NCA segmenti, che richiedono
kAW/ID = ⌈NAW/ID / min(AW, WID)⌉
RTT. Può capitare che kAW/ID = 0 se l'intero file viene trasferito prima di raggiungere la finestra min(AW, WID), o che anche kCA = 0 se il file viene trasferito prima di raggiungere SSThr: le fasi si "saltano" e la formula resta valida con i termini nulli.
min(AW, WID); da lì la finestra resta costante e il canale è saturo.Il quesito di latenza dei compiti chiede quasi sempre: calcolare WID (prodotto banda×ritardo in byte e in MSS), poi il tempo totale di trasferimento con la formula D = (1 + kSS + kCA + kAW/ID) · RTT. Attenzione a due trappole ricorrenti: la finestra iniziale di Slow Start (1 o 2 MSS cambia kSS e NSS), e il fatto che WID può essere raggiunto durante la Slow Start, nel qual caso la fase di CA non esiste e si passa direttamente alla fase finale.
Il throughput è la quantità complessiva di informazioni inviate per unità di tempo, ritrasmissioni incluse. Il goodput è la quantità di informazioni utili ricevute con successo per unità di tempo, ritrasmissioni e duplicazioni escluse: vale sempre goodput ≤ throughput. La latenza non è un rate ma un tempo: l'intervallo fra l'avvio della connessione e la ricezione completa del file.
1) Sorgente satura (ha sempre dati da trasmettere); 2) segmenti tutti di dimensione MSS; 3) buffer grandi, CW << AW; 4) rete stabile: RTT costante, perdita periodica con percentuale p, perdita quando W = WL; 5) TCP sempre in Congestion Avoidance. Da queste ipotesi discendono tutte le formule del capitolo.
Si contano i segmenti inviati in un periodo in due modi: come 1/p (un segmento perso per periodo) e come area sotto il dente di sega, 3WL²/8. Uguagliando: 1/p = 3WL²/8, da cui WL = √(8/(3p)). Con ACK ritardati (b) l'area diventa 3bWL²/8 e WL = √(8/(3bp)).
S̄ = (MSS/RTT) · √(3/(2p)) in bit/s, oppure S̄′ = √(3/(2p)) in segmenti per RTT. Con ACK ritardati: S̄ = (MSS/RTT) · √(3/(2bp)). La lettura è che il throughput è inversamente proporzionale alla radice quadrata della probabilità di perdita: ridurre p di un fattore 4 raddoppia il throughput.
La perdita avviene dopo che la finestra ha raggiunto AW: il dente di sega ha una fase di crescita da AW/2 ad AW e una fase costante di k RTT a AW. Il periodo è T = (bAW/2 + k) · RTT con k = 1/(pAW) − 3bAW/8, e il throughput medio è S̄ = (MSS/RTT) · (1/p)/(bAW/2 + k). Se WL ≤ AW la correzione non serve.
Perché se p << 1 ogni fase di Congestion Avoidance può essere modellata come un periodo con parametri equivalenti: la distribuzione del picco WL,k è concentrata attorno al valore medio del caso periodico. Le formule restano valide in media, e i compiti applicano lo stesso p sia per "perdite puntuali periodiche ogni N segmenti" (p = 1/N) sia per "perdite aleatorie".
È DMIN = 2 RTT + F/C: un RTT per il 3-way handshake, un secondo RTT per completarlo, inviare la richiesta e ricevere il primo bit del file, poi il tempo di trasmissione del file F/C. È un lower bound: nessuna connessione può fare meglio, perché i primi due RTT non trasportano dati utili.
Quando W·S/C ≥ S/C + RTT: il server riceve l'ACK del primo segmento prima di aver finito di trasmettere la finestra, quindi il flusso non si interrompe mai. Il caso limite W·S/C = S/C + RTT è la finestra ideale. Se invece W·S/C < S/C + RTT, servono K = ⌈F/(WS)⌉ finestre con K−1 attese di TW = RTT − (W−1)S/C ciascuna.
Si sommano gli RTT delle fasi: D = (1 + kSS + kCA + kAW/ID) · RTT. Slow Start: kSS = log2(SSThr) (partendo da 1) e NSS = 2kSS − 1. Congestion Avoidance: kCA = min(AW, WID) − SSThr e NCA = kCA·SSThr + (kCA−1)kCA/2. Fase finale: kAW/ID = ⌈(N − NSS − NCA)/min(AW, WID)⌉.
Perché è la quantità di dati che può essere "in volo" sul percorso: WID = C · RTT bit. Con una finestra più piccola il canale resta inattivo tra una finestra e l'ACK della precedente (sottoutilizzazione); con una finestra più grande i dati eccedenti si accodano nei router. A W = WID il canale è saturo senza interruzioni né accodamento.