Esercizio - Sei pacchetti con traffico concorrente e TCP con rwnd limitata

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

1. A $t=0$ la coda di A contiene quattro pacchetti diretti a E, E, D, D; quella di B due pacchetti diretti a C, C. Lunghezze $L_C=400$ kbit, $L_D=100$ kbit, $L_E=200$ kbit. Calcolare l'istante di arrivo di ogni pacchetto.
2. Tra A e C c'è una connessione TCP, $\text{MSS}=1250$ B, apertura e ACK trascurabili, intestazioni trascurabili; $\text{cwnd}=1250$ B, $\text{ssthresh}=10\,000$ B, $\text{rwnd}=1$ MB. Calcolare la finestra di invio $\text{swnd}^*$ che permette un flusso continuo tra A e C.
3. Tempo totale per trasferire $M=50$ KB (dall'apertura alla ricezione dell'ultimo byte).
4. Lo stesso con $\text{rwnd}=5$ KB.
5. Lo stesso con $\text{rwnd}=5$ KB se tutti i pacchetti in volo della settima finestra vanno persi (fuori sequenza scartati), con timeout di $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: sei pacchetti con lunghezze diverse

Percorsi: E: $C_1,C_2,C_3,C_5$; D: $C_1,C_2,C_3,C_4$; C (pacchetti di B): $C_6,C_2,C_7$. Tempi di trasmissione $T=L/C$ in ms:

Uscita dai due host. A manda $E_1,E_2,D_1,D_2$ uno dietro l'altro; B manda $C_1,C_2$:

• $E_1$: $C_1$ $0\to10$, in R1 a $16$; $E_2$: $10\to20$, in R1 a $26$; $D_1$: $20\to25$, in R1 a $31$; $D_2$: $25\to30$, in R1 a $36$.
• $C_1$ (di B, per distinguerlo lo chiamo $B_1$): $C_6$ $0\to16$, in R1 a $18$; $B_2$: $16\to32$, in R1 a $34$.

Coda su $C_2$ (R1 → R2). Si servono i pacchetti per ordine di arrivo in R1: $E_1$ ($16$), $B_1$ ($18$), $E_2$ ($26$), $D_1$ ($31$), $B_2$ ($34$), $D_2$ ($36$).

In R2. I pacchetti per C ($B_1$, $B_2$) vanno su $C_7$ ($2$ Mbit/s, $T=200$ ms): $B_1$ da $42$ a $242$, arriva a C a $242+12=\mathbf{254}$; $B_2$, pronto a $70$, aspetta fino a $242$, finisce a $442$ e arriva a $\mathbf{454}$ ms. I pacchetti per R3 vanno su $C_3$ (coda FIFO per arrivo in R2: $E_1$ $26$, $E_2$ $50$, $D_1$ $54$, $D_2$ $74$):

In R3. $E_1$ su $C_5$: $48\to64$, arriva a E a $64+2=\mathbf{66}$; $E_2$: $72\to88$, arriva a $\mathbf{90}$. $D_1$ su $C_4$: $82\to90$, arriva a D a $\mathbf{92}$; $D_2$: $92\to100$, arriva a $\mathbf{102}$.

Domanda 2: finestra per un flusso continuo

Il cammino A→C usa $C_1,C_2,C_7$. Il collo di bottiglia è $C_7$ ($2$ Mbit/s): con $\text{MSS}=1250$ B $=10$ kbit, $T_b=10\,000/2\cdot10^6=5$ ms.

• Andata di un segmento: $T_1+\tau_1+T_2+\tau_2+T_7+\tau_7=0{,}5+6+0{,}4+2+5+12=25{,}9$ ms.
• Ritorno dell'ACK: $\tau_7+\tau_2+\tau_1=12+2+6=20$ ms.

$$\text{RTT}=25{,}9+20=45{,}9\ \text{ms},\qquad\text{swnd}^*\ge\frac{\text{RTT}}{T_b}=\frac{45{,}9}{5}=9{,}18\ \Rightarrow\ \text{swnd}^*=\mathbf{10\ \text{MSS}}.$$

Equivalente: $\text{BDP}=2\ \text{Mbit/s}\cdot45{,}9\ \text{ms}=91{,}8$ kbit $=9{,}18$ MSS.

Domanda 3: 50 KB con $\text{rwnd}=1$ MB

$K=50\,000/1250=40$ segmenti. L'apertura (SYN e SYN+ACK, solo propagazione $20$ ms ciascuno) dura $40$ ms; l'ACK finale porta il primo dato.

Finestre: $1,2,4,8$ (slow start fino a $\text{ssthresh}=8$ MSS), poi $9,10,\dots$ in congestion avoidance:

Inviati $24$ (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=15$, più $9$); rimangono $16$. Dalla sesta finestra $\text{swnd}=10=\text{swnd}^*$: flusso continuo, un segmento ogni $T_b=5$ ms. L'ultimo byte arriva quando l'ultimo segmento ha attraversato tutti i collegamenti (non serve aspettare l'ACK):

$$T_{\text{TOT}}=40+5\,\text{RTT}+(16-1)\,T_b+\underbrace{(T_1+\tau_1+T_2+\tau_2+T_7+\tau_7)}_{25{,}9}=40+229{,}5+75+25{,}9=\mathbf{370{,}4\ \text{ms}}.$$ Lettura dei termini: $40$ ms l'apertura; $5\,\text{RTT}$ le prime cinque finestre ($1,2,4,8,9$); $15\,T_b$ la distanza tra il primo e l'ultimo dei $16$ segmenti in flusso continuo; $25{,}9$ ms il viaggio dell'ultimo segmento fino a C (si chiede l'ultimo byte, quindi niente ritorno dell'ACK).

Domanda 4: $\text{rwnd}=5$ KB

$\text{rwnd}=5000/1250=4$ MSS. La finestra di invio è $\text{swnd}=\min(\text{cwnd},\text{rwnd})$, quindi si ferma a $4$: finestre $1,2,4,4,4,\dots$ Poiché $4\,T_b=20$ ms $<\text{RTT}=45{,}9$ ms, il mittente invia $4$ segmenti, poi aspetta: ogni finestra dura un RTT.

• Nelle prime due finestre: $1+2=3$ segmenti; rimangono $40-3=37$.
• $37=9\cdot4+1$: $9$ finestre complete da $4$ e una finale da $1$ segmento.

$$T_{\text{TOT}}=40+2\,\text{RTT}+9\,\text{RTT}+25{,}9=40+11\cdot45{,}9+25{,}9=\mathbf{570{,}8\ \text{ms}}.$$

Domanda 5: settima finestra persa

Con $\text{rwnd}=4$ le finestre sono $1,2,4,4,4,4$ (sei finestre, $1+2+4\cdot4=19$ segmenti consegnati) e poi la settima ($4$ segmenti, inviata a $40+6\,\text{RTT}$) è persa. Dopo $\text{RTO}=3\,\text{RTT}$ scatta il timeout:

• $\text{ssthresh}=\text{swnd}/2=4/2=2$ MSS, $\text{cwnd}=1$ MSS;
• finestre dopo il timeout: $1,2$ (si raggiunge ssthresh), $3$ (congestion avoidance), poi $4$ (limite di rwnd): $1+2+3=6$ segmenti nelle prime $3$ finestre.

Rimangono $40-19=21$ segmenti; dopo le tre finestre da $1,2,3$ ne restano $15=3\cdot4+3$: $3$ finestre da $4$ e una da $3$.

$$T_{\text{TOT}}=40+6\,\text{RTT}+\text{RTO}+3\,\text{RTT}+3\,\text{RTT}+\bigl(25{,}9+2\,T_b\bigr).$$

L'ultima finestra ha $3$ segmenti: l'ultimo esce $2\,T_b$ dopo il primo. Numericamente $40+275{,}4+137{,}7+137{,}7+137{,}7+35{,}9=\mathbf{764{,}4\ \text{ms}}$ (i tre blocchi da $137{,}7=3\,\text{RTT}$ sono, nell'ordine, il timeout, le finestre $1,2,3$ e le tre finestre da $4$).

Confronto con la soluzione ufficiale

Tutto coincide. L'ufficiale usa il tempo "fino all'ultimo byte" (non all'ultimo ACK): aggiungendo $20$ ms di ritorno dell'ACK si avrebbero $390{,}4$, $590{,}8$ e $784{,}4$ ms.

Errori comuni

• Servire $C_2$ in ordine di partenza dagli host invece che di arrivo in R1: $B_1$ ($18$) passa prima di $E_2$ ($26$).
• Usare $T=L/C$ con la stessa $L$ per tutti i pacchetti: qui $L_C,L_D,L_E$ sono diverse.
• Dimenticare che $B_2$ resta in coda in R2 per $C_7$ fino a $242$ ms.
• Con $\text{rwnd}$ piccola, continuare a raddoppiare la finestra oltre $\text{rwnd}$.
• Dopo il timeout calcolare $\text{ssthresh}$ da una $\text{cwnd}$ non limitata da rwnd: si usa la finestra effettivamente in volo ($4$ MSS), quindi $\text{ssthresh}=2$.

(Verificato con Python: simulatore a eventi per la domanda 1; simulatore TCP a finestra intera per le domande 3-5, riportato all'istante dell'ultimo byte.)