Esercizio - Cinque pacchetti da A e B e TCP da 18,75 KB su collegamenti da 100 a 1000 kbps

Testo (tema d'esame, sessione di giugno, esercizio 1). Rete a commutazione di pacchetto a datagramma (store-and-forward), code indipendenti per ogni interfaccia di uscita.

1. A $t=0$ la coda del server A ha tre pacchetti diretti a C, C, E (E per ultimo); quella del server B ha due pacchetti diretti a D e F (F per ultimo). Pacchetti da $L=250$ B, trasmissioni che partono a $t=0$ in tutti i nodi. Calcolare l'arrivo dei soli tre pacchetti di A.
2. Tra A e D c'è una connessione TCP ($\text{MSS}=125$ B, apertura e ACK trascurabili, intestazioni trascurabili, $\text{cwnd}=125$ B, $\text{ssthresh}=500$ B, $\text{rwnd}=1000$ B). Calcolare RTT e BDP.
3. Tempo totale per trasferire $M=18{,}75$ kB (dall'apertura all'ultimo ACK).
4. Lo stesso con $\text{rwnd}=1$ MB, se tutti i pacchetti in volo della quinta finestra sono persi e il timeout è $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 pacchetti di A (con il traffico di B)

$L=250$ B $=2000$ bit; tempi di trasmissione:

Percorsi: A→C: $C_1,C_3,C_4$; A→E: $C_1,C_3,C_6,C_7$; B→D: $C_2,C_3,C_5$; B→F: $C_2,C_3,C_6,C_8$. I due flussi si incontrano su $C_3$ (R1→R2) e, per i pacchetti verso E e F, su $C_6$ (R2→R3).

Uscita dagli host e arrivo in R1.

Coda su $C_3$ ($T=8$ ms). Si servono per ordine di arrivo in R1: $A_1$ ($18$), $B_1$ ($20$), $B_2$ ($25$), $A_2$ ($28$), $A_3$ ($38$).

In R2.

• $A_1$ (verso C) su $C_4$ ($T=2$): $36\to38$, arriva a C a $38+50=\mathbf{88}$ ms.
• $A_2$ (verso C): $60\to62$, arriva a $62+50=\mathbf{112}$ ms.
• $A_3$ (verso E) e $B_2$ (verso F) usano $C_6$ ($T=20$): $B_2$ arriva in R2 a $52$ e parte subito ($52\to72$); $A_3$ arriva a $68$ ma $C_6$ è occupato fino a $72$: parte a $72$, finisce a $92$, arriva in R3 a $92+5=97$.
• In R3, $A_3$ su $C_7$ ($T=10$): $97\to107$, arriva a E a $107+1=\mathbf{108}$ ms.

(Il pacchetto $A_3$ arriva prima del secondo per C perché passa per un tratto diverso.)

Domanda 2: RTT e BDP

Cammino A→D: $C_1,C_3,C_5$. Il collo di bottiglia è $C_5$ ($100$ kbit/s). Un segmento da $125$ B $=1000$ bit:

• Andata: $5+8+4+10+10+10=47$ ms.
• Ritorno dell'ACK (trascurabile): $\tau_5+\tau_3+\tau_1=10+10+8=28$ ms.

$$\text{RTT}=47+28=\mathbf{75\ \text{ms}},\qquad\text{BDP}=100\ \text{kbit/s}\cdot75\ \text{ms}=\mathbf{7{,}5\ \text{kbit}}=7{,}5\ \text{MSS}.$$

Quindi $\text{swnd}^*=8$ MSS e il tempo di trasmissione del collo di bottiglia è $T_b=10$ ms.

Passaggi e unità: kbit/s $\times$ ms $=$ bit ($10^3$ bit/s $\cdot10^{-3}$ s), quindi $\text{BDP}=100\cdot75=7500$ bit $=7{,}5$ segmenti da $1000$ bit. Il flusso è continuo se $\text{swnd}\cdot T_b\ge\text{RTT}$, cioè $\text{swnd}\ge75/10=7{,}5$: si arrotonda per eccesso a $8$, perché con $7$ segmenti la finestra occupa il collegamento $70$ ms su $75$ e lo lascia fermo $5$ ms a ogni giro.

Domanda 3: $18{,}75$ kB con $\text{rwnd}=1000$ B

$K=18\,750/125=150$ segmenti; $\text{ssthresh}=500/125=4$ MSS; $\text{rwnd}=1000/125=8$ MSS.

Apertura. SYN e SYN+ACK solo propagazione: $\tau_1+\tau_3+\tau_5=28$ ms ciascuno, quindi i dati partono a $56$ ms (con l'ACK finale).

Finestre. Slow start: $1,2,4$ (si raggiunge $\text{ssthresh}=4$); congestion avoidance: $5,6,7,8$ (la finestra si ferma a $8$ per il limite di $\text{rwnd}$).

Nelle prime sei finestre si inviano $1+2+4+5+6+7=25$ segmenti (le prime tre 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=2^3-1=7$). Dalla settima $\text{swnd}=8\ge\text{swnd}^*=8$: flusso continuo per i $150-25=125$ segmenti restanti.

$$T_{\text{TCP}}=56+6\,\text{RTT}+(125-1)\,T_b+\text{RTT}=56+450+1240+75=\mathbf{1821\ \text{ms}}=1{,}821\ \text{s}.$$

Lettura dei termini: $56$ ms è l'handshake ($28$ ms per il SYN e $28$ per il SYN+ACK, solo propagazione); $6\,\text{RTT}$ sono le prime sei finestre, ciascuna lunga un RTT perché $\text{swnd}\cdot T_b<\text{RTT}$ (ad esempio $7\cdot10=70<75$ ms) e il mittente aspetta l'ACK del primo segmento; i $125$ segmenti rimanenti partono in flusso continuo uno ogni $T_b$, il primo all'inizio della settima finestra e l'ultimo $124\,T_b$ dopo; l'ultimo $\text{RTT}$ è il ritorno dell'ACK dell'ultimo segmento (la sua trasmissione è già compresa nell'RTT).

Domanda 4: quinta finestra persa, $\text{rwnd}=1$ MB

Con $\text{rwnd}$ grande la finestra non è mai limitata dal ricevitore: $1,2,4$ (slow start), poi $5,6,7,\dots$ in congestion avoidance.

• Le prime quattro finestre ($1,2,4,5$) portano $12$ segmenti a destinazione.
• La quinta finestra ($6$ segmenti) parte a $56+4\,\text{RTT}=356$ ms ed è persa per intero.
• Dopo $\text{RTO}=3\,\text{RTT}=225$ ms (misurati dall'inizio dell'invio della finestra persa) scatta il timeout: $\text{ssthresh}=\text{cwnd}/2=6/2=3$ MSS, $\text{cwnd}=1$.

Dopo il timeout: finestre $1,2,3$ (si raggiunge ssthresh), poi $4,5,6,7$ (congestion avoidance), con $1+2+3+4+5+6+7=28$ segmenti in $7$ finestre. I segmenti ancora da inviare erano $150-12=138$, ne restano $138-28=110$. Dall'ottava finestra $\text{swnd}=8\ge\text{swnd}^*$: flusso continuo.

$$T_{\text{TCP}}=56+4\,\text{RTT}+\text{RTO}+7\,\text{RTT}+(110-1)\,T_b+\text{RTT}=56+300+225+525+1090+75=\mathbf{2271\ \text{ms}}.$$

Lettura dei termini: $56$ ms handshake; $4\,\text{RTT}$ le prime quattro finestre ($1,2,4,5$) che vanno a buon fine; $\text{RTO}=225$ ms l'attesa del timeout, contata dall'invio della quinta finestra persa; $7\,\text{RTT}$ le sette finestre $1,\dots,7$ dopo il timeout (somma $1+\dots+7=28$, con la formula di Gauss $\frac{7\cdot8}2$, SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →); $(110-1)\,T_b$ la parte in flusso continuo; $\text{RTT}$ finale per l'ultimo ACK.

Il grafico mostra le due finestre di invio nei round (linea continua: domanda 3; tratteggiata: domanda 4): la finestra persa (6 segmenti) resta in attesa fino al timeout, poi si riparte da $1$ con $\text{ssthresh}=3$, e la linea orizzontale è $\text{swnd}^*=8$, la soglia del flusso continuo.

Confronto con la soluzione ufficiale

Tutto coincide.

Errori comuni

• Mettere in coda $A_3$ dietro $B_2$ su $C_3$ in ordine di partenza dagli host: l'ordine di servizio è per arrivo in R1 ($B_2$ arriva a $25$, $A_2$ a $28$).
• Dimenticare che $B_2$ occupa $C_6$ fino a $72$ ms e ritarda $A_3$ di $4$ ms.
• Alla domanda 3 non fermare la finestra a $8$ MSS: con $\text{rwnd}=1000$ B non si va oltre.
• Alla domanda 4 prendere $\text{ssthresh}=4/2$: la finestra al momento della perdita è $6$, quindi $\text{ssthresh}=3$.
• Contare ancora la quinta finestra tra i segmenti consegnati.

(Verificato con Python: simulatore a eventi per la domanda 1 e simulatore TCP a finestra intera per le domande 3-4; $1821$ e $2271$ ms.)