Esercizio - Cinque pacchetti da A e trasferimento TCP di 50 KB con finestra persa

Testo (simulazione d'esame 1, esercizio 1). Rete a commutazione di pacchetto a datagramma (store-and-forward), con code indipendenti per ogni interfaccia di uscita dei router R1 e R2.

1. A $t=0$ la coda di A contiene cinque pacchetti diretti a B, B, D, D, C (in questo ordine), con canale libero. Pacchetti di $L=1250$ byte: calcolare l'istante di arrivo a destinazione di ciascuno.
2. Tra A e C c'è una connessione TCP, $\text{MSS}=1250$ byte; apertura e ACK di lunghezza trascurabile, intestazioni trascurabili; $\text{cwnd}=1250$ B all'inizio, $\text{ssthresh}=10\,000$ B, $\text{rwnd}=1$ MB. Calcolare RTT e prodotto banda-ritardo (BDP).
3. Il tempo di apertura della connessione (pacchetti scambiati), con i dati che partono appena possibile.
4. Il tempo totale per trasferire $M=50$ KB (dall'apertura alla ricezione dell'ultimo ACK).
5. Lo stesso calcolo se tutti i segmenti in volo della quarta finestra vanno persi (i fuori sequenza vengono scartati), con timeout pari a $3$ RTT.

Teoria usata: Commutazione di circuito e di pacchettoUn nodo di commutazione (switch) può collegare ingresso e uscita in tre modi. Commutazione di circuito: si stabilisce prima un collegamento fisico dedicato (rete telefonica), tempo di consegna $T=3Nt_p+Nt_s+M/R$. Commutazione di pacchetto a datagramma: il messaggio è diviso in $K$ pacchetti con intestazione, ognuno è instradato indipendentemente con store-and-forward, $T=Nt_p+(N+K-1)\frac{M/K+H}{R}$, con $K_{ott}=\sqrt{(N-1)M/H}$. A circuito virtuale: tre fasi (setup, dati, chiusura), connessione logica dedicata ma senza risorse dedicate, identificatore locale che cambia a ogni salto.Commutazione di circuito e di pacchetto →, Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →, 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 →, 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 →.

Domanda 1: i cinque pacchetti

Un pacchetto da $L=1250$ B $=10\,000$ bit impiega $T=L/C$ per essere trasmesso su un collegamento:

Regola: un pacchetto può uscire da un nodo solo quando è arrivato per intero (store-and-forward), parte a $\max(\text{pronto},\text{collegamento libero})$, finisce dopo $T$ e arriva al nodo successivo dopo $\tau$ in più. Percorsi: B: $C_1,C_2,C_3$; D: $C_1,C_5$; C: $C_1,C_2,C_4$.

Uscita da A. I pacchetti $p_1\ldots p_5$ (B, B, D, D, C) escono uno dopo l'altro ogni $0{,}5$ ms e arrivano a R1 dopo $6$ ms:

In R1. Le code sono due, una per interfaccia di uscita:

• $C_2$ (verso R2, $T=1$ ms): $p_1$ parte a $6{,}5$, finisce a $7{,}5$; $p_2$ è arrivato a $7{,}0$ ma aspetta fino a $7{,}5$, finisce a $8{,}5$; $p_5$ arriva a $8{,}5$, trova il collegamento appena libero, parte a $8{,}5$ e finisce a $9{,}5$. Arrivi in R2 (con $+4$ ms): $p_1$ a $11{,}5$, $p_2$ a $12{,}5$, $p_5$ a $13{,}5$.
• $C_5$ (verso D, $T=2$ ms): $p_3$ parte a $7{,}5$, finisce a $9{,}5$, arriva a D a $9{,}5+1=\mathbf{10{,}5}$; $p_4$ aspetta fino a $9{,}5$, finisce a $11{,}5$, arriva a $\mathbf{12{,}5}$.

In R2.

• $C_3$ (verso B, $T=2$ ms): $p_1$ parte a $11{,}5$, finisce a $13{,}5$, arriva a B a $13{,}5+4=\mathbf{17{,}5}$; $p_2$ (pronto a $12{,}5$) parte a $13{,}5$, finisce a $15{,}5$, arriva a $\mathbf{19{,}5}$.
• $C_4$ (verso C, $T=5$ ms): $p_5$ pronto a $13{,}5$, finisce a $18{,}5$, arriva a C a $18{,}5+10=\mathbf{28{,}5}$.

Domanda 2: RTT e BDP

Il cammino A→C usa $C_1,C_2,C_4$. Il collegamento più lento è $C_4$ ($2$ Mbit/s): è il collo di bottiglia, e il suo tempo di trasmissione $T_b=10\,000/2\,\text{Mbit/s}=5$ ms è l'intervallo minimo fra due segmenti consecutivi in arrivo.

• Andata di un segmento da $1250$ B: $T_1+\tau_1+T_2+\tau_2+T_4+\tau_4=0{,}5+6+1+4+5+10=26{,}5$ ms.
• Ritorno dell'ACK (lunghezza trascurabile, quindi solo propagazione): $\tau_4+\tau_2+\tau_1=10+4+6=20$ ms.

$$\text{RTT}=26{,}5+20=\mathbf{46{,}5\ \text{ms}}.$$

$$\text{BDP}=C_{\text{bottleneck}}\cdot\text{RTT}=2\ \text{Mbit/s}\cdot46{,}5\ \text{ms}=93\ \text{kbit}=\mathbf{9{,}3}\ \text{MSS}.$$

Significato: per tenere sempre occupato il collo di bottiglia servono almeno $9{,}3$ segmenti in volo, quindi $\text{swnd}^*=\lceil9{,}3\rceil=10$ MSS. Con $\text{rwnd}=1$ MB $\gg\text{cwnd}$ la finestra di invio è $\text{swnd}=\min(\text{cwnd},\text{rwnd})=\text{cwnd}$.

Domanda 3: apertura della connessione

I segmenti di apertura hanno lunghezza trascurabile: contano solo le propagazioni, $\tau_1+\tau_2+\tau_4=20$ ms in un verso.

1. SYN da A a C: $20$ ms.
2. SYN+ACK da C ad A: altri $20$ ms (a $t=40$ ms A considera aperta la connessione).
3. ACK da A a C, con il primo segmento di dati sullo stesso pacchetto (piggyback): parte a $40$ ms e, come ogni segmento da $1250$ B, arriva dopo $26{,}5$ ms.

Quindi la connessione risulta aperta anche in C a $40+26{,}5=66{,}5$ ms, quando arriva l'ACK con il primo dato: è il valore della soluzione ufficiale ($T_{\text{setup}}=66{,}5$ ms). I due segmenti di controllo da soli occupano $2\cdot20=40$ ms: è l'istante in cui A comincia a trasmettere i dati, ed è il $40$ ms che compare nel calcolo del tempo totale.

Domanda 4: trasferimento di 50 KB

Numero di segmenti. Si usa $K=50\,000/1250=40$ segmenti.

Crescita della finestra. Si parte da $\text{cwnd}=1$ MSS e $\text{ssthresh}=10\,000$ B $=8$ MSS: in slow start la finestra raddoppia ogni RTT ($1,2,4,8$); a $8$ si raggiunge ssthresh e inizia la congestion avoidance con $+1$ MSS per RTT ($9,10,\dots$). Segmenti inviati nelle prime finestre:

Totale $1+2+4+8+9=24$ segmenti (le prime quattro finestre sono una somma geometrica1 + 2 + 4 + ... + 2^k = 2^(k+1) − 1, perché ogni termine è il doppio del precedenteSerie notevoli - geometrica, telescopica, armonica →: $1+2+4+8=2^4-1=15$, più $9$). Rimangono $40-24=16$ segmenti.

Flusso continuo. Alla sesta finestra $\text{swnd}=10\ge\text{BDP}=9{,}3$: il collo di bottiglia non resta mai vuoto e i $16$ segmenti restanti escono uno ogni $T_b=5$ ms.

Tempo totale. L'ACK dell'ultimo segmento arriva a

$$T_{\text{TOT}}=\underbrace{40}_{\text{SYN, SYN+ACK}}+5\,\text{RTT}+(16-1)\,T_b+\text{RTT}=40+232{,}5+75+46{,}5=\mathbf{394\ \text{ms}}.$$

Spiegazione dei termini: le prime $5$ finestre occupano $5$ RTT, poi il primo dei $16$ segmenti parte a $40+5\,\text{RTT}$ e l'ultimo $15\,T_b$ dopo; da quando l'ultimo parte a quando ne arriva l'ACK passa un RTT (il suo $T_b$ è già dentro l'RTT).

Domanda 5: quarta finestra persa, timeout di 3 RTT

Le finestre $1,2,4$ passano senza problemi ($7$ segmenti consegnati). La quarta finestra ($8$ segmenti) parte a $40+3\,\text{RTT}$ ed è persa per intero. Dopo $\text{RTO}=3\,\text{RTT}=139{,}5$ ms scatta il timeout (misurato dall'inizio dell'invio della finestra persa):

• $\text{ssthresh}=\text{cwnd}/2=8/2=4$ MSS e $\text{cwnd}=1$ MSS (riparte la slow start);
• finestre dopo il timeout: $1,2,4$ (si arriva a ssthresh), poi in congestion avoidance $5,6,7,8$.

Segmenti ancora da consegnare: $40-7=33=1+2+4+5+6+7+8$, quindi servono esattamente $7$ finestre. Tutte restano sotto il BDP ($\le8<9{,}3$ MSS): il collo di bottiglia non si satura e ogni finestra dura un RTT. Nell'ultima finestra ($8$ segmenti) i segmenti escono a distanza $T_b$, quindi l'ultimo parte $7\,T_b$ dopo il primo, e il suo ACK torna dopo un RTT.

$$T_{\text{TOT}}=40+3\,\text{RTT}+\text{RTO}+7\,\text{RTT}+(8-1)\,T_b=40+139{,}5+139{,}5+325{,}5+35=\mathbf{679{,}5\ \text{ms}}.$$

Lettura dei termini: $40$ ms sono SYN e SYN+ACK; $3\,\text{RTT}$ le finestre $1,2,4$ riuscite; $\text{RTO}=3\,\text{RTT}=139{,}5$ ms l'attesa del timeout della quarta finestra; $7\,\text{RTT}$ le sette finestre dopo il timeout ($33$ segmenti, $1+2+4+5+6+7+8$), di cui l'ultima è anche l'ultima a spedire; $(8-1)\,T_b$ la serializzazione dei suoi $8$ segmenti al collo di bottiglia ($T_b=5$ ms); l'ultimo ACK è già nell'ultimo RTT (tutte le finestre restano sotto il BDP $9{,}3$, quindi ciascuna dura un RTT).

Confronto con la soluzione ufficiale

Discrepanza sulla domanda 5. La soluzione ufficiale scrive la stessa formula ($T_{\text{setup}}+3\,\text{RTT}+\text{RTO}+7\,\text{RTT}+(8-1)T_b$) ma riporta $640$ ms; con i suoi stessi termini ($40+139{,}5+139{,}5+325{,}5+35$) la somma è $679{,}5$ ms. Ho verificato il risultato con un simulatore a eventi (finestra intera, ACK cumulativi, timeout a $3\,\text{RTT}$ dall'inizio della finestra persa): $679{,}5$ ms. Sembra un errore di somma nella soluzione.

Errori comuni

• Dare a $p_5$ (C) una coda dietro $p_2$: sul collegamento $C_2$ i due pacchetti non si sovrappongono, perché $p_2$ finisce proprio a $8{,}5$ ms.
• Usare $C_3$ o $C_5$ come collo di bottiglia: il cammino A→C passa per $C_1,C_2,C_4$.
• Calcolare il BDP in MSS senza arrotondare per eccesso: $9{,}3$ MSS richiedono $\text{swnd}^*=10$.
• Dimenticare che dopo il timeout $\text{ssthresh}=\text{cwnd}/2$ e non $\text{ssthresh}/2$.
• Contare come consegnati i segmenti della finestra persa.

(Verificato con Python: simulatore a eventi per i pacchetti e per TCP; $394$ ms e $679{,}5$ ms.)