Esercizio - Commutazione di pacchetto e numero ottimo di pacchetti

Testo. Calcolare il tempo di consegna di un messaggio dall'host A all'host B con in mezzo uno switch che implementa la commutazione di pacchetto con approccio a datagramma (store-and-forward). Il messaggio è diviso in $K$ pacchetti. Si trascurano accodamento ed elaborazione. Tutti i collegamenti sono uguali (stessa lunghezza, stesso bitrate). Calcolare il valore ottimo di $K$ che minimizza il tempo di consegna del messaggio.

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 →; per la derivata e il minimo Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione → e Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →.

Simboli

• $N$: numero di collegamenti da A a B (hop); $N-1$ switch intermedi. Nell'esercizio $N=2$, ma si ricava la formula generale.
• $t_p$: propagazione di un collegamento; $R$: bitrate di ogni collegamento.
• $M$: lunghezza del messaggio in bit; $K$: numero di pacchetti.
• $H$: lunghezza dell'intestazione di ciascun pacchetto in bit (indirizzi di sorgente e destinazione, necessari nel datagramma: ogni pacchetto è instradato da solo).
• Lunghezza di un pacchetto: $L=\dfrac MK+H$; tempo di trasmissione di un pacchetto su un collegamento: $t_{tx}=\dfrac{M/K+H}{R}$.

Ricavo del tempo di consegna

Sul primo collegamento A trasmette i $K$ pacchetti uno dopo l'altro: la trasmissione dell'ultimo termina a $K\,t_{tx}$. Poi quest'ultimo pacchetto deve ancora attraversare i collegamenti restanti: su ciascuno viene ricevuto per intero (store), poi ritrasmesso (forward, $t_{tx}$) e poi si propaga ($t_p$). Il primo collegamento aggiunge anche la sua propagazione, quindi: $$T=K\,t_{tx}+N\,t_p+(N-1)\,t_{tx}=N\,t_p+(N+K-1)\,t_{tx}.$$ Uno sguardo al diagramma temporale aiuta a vedere perché non serve ritrasmettere per intero ogni pacchetto: appena lo switch finisce di ricevere il pacchetto 1 comincia a trasmetterlo verso B mentre A sta già trasmettendo il pacchetto 2 (pipeline). I collegamenti lavorano in parallelo su pacchetti diversi: il tempo non è $K\cdot N\cdot t_{tx}$ ma $(N+K-1)\,t_{tx}$, perché il pacchetto che chiude la sequenza paga $N$ trasmissioni (una per hop) e gli altri $K-1$ si "nascondono" dietro di lui. In forma completa: $$\boxed{T(K)=N\,t_p+(N+K-1)\,\frac{M/K+H}{R}}$$

Perché esiste un $K$ ottimo

Sviluppando il prodotto: $$(N+K-1)\left(\frac MK+H\right)=\frac{(N-1)M}{K}+M+(N-1)H+KH.$$ Quindi $$T(K)=N\,t_p+\frac1R\left[\underbrace{\frac{(N-1)M}{K}}_{\text{decresce con }K}+\underbrace{K\,H}_{\text{cresce con }K}+M+(N-1)H\right].$$ Dividere in più pacchetti accorcia il tempo perché gli hop lavorano in parallelo (primo termine); ma ogni pacchetto in più porta un'intestazione in più (secondo termine). Il minimo si trova derivando rispetto a $K$ e ponendo la derivata uguale a zero: $$\frac{dT}{dK}=\frac1R\left[-\frac{(N-1)M}{K^2}+H\right]=0\ \Longrightarrow\ \boxed{K_{opt}=\sqrt{\frac MH\,(N-1)}}.$$ Passo per passo: i termini $N\,t_p$, $M$ e $(N-1)H$ non contengono $K$ e la loro derivata è $0$; $\frac{d}{dK}\frac{(N-1)M}{K}=-\frac{(N-1)M}{K^2}$ (potenza $K^{-1}$) e $\frac{d}{dK}(KH)=H$. Porre la derivata a zero significa $H=\frac{(N-1)M}{K^2}$, cioè $K^2=\frac{(N-1)M}{H}$, e si prende la radice positiva. La derivata seconda $\frac{2(N-1)M}{RK^3}$ è positiva per $K>0$, quindi è un minimo. Se il numero risultante non è intero si confrontano i due interi vicini.

Caso del testo ($N=2$): $K_{opt}=\sqrt{M/H}$.

Esempio numerico

$M=10^6$ bit, $H=100$ bit, $N=3$ hop, $R=10$ Mbps, $t_p=1$ ms. Allora $K_{opt}=\sqrt{10^6\cdot2/100}=141{,}4$ e

Controllo di $K=141$ passo per passo: dimensione del pacchetto $M/K+H=10^6/141+100=7092+100=7192$ bit; tempo di trasmissione $7192/(10^{7})=0{,}7192$ ms; numero di tempi $N+K-1=3+141-1=143$; $T=N\,t_p+143\cdot0{,}7192=3+102{,}85=105{,}85$ ms.

Il minimo cade tra $141$ e $142$ (i due valori differiscono per meno di un microsecondo, $105{,}848$ ms), ed è molto piatto: scegliere $K$ da $100$ a $200$ perde meno del $0{,}2\%$. Con $K=1$ (nessuna segmentazione) il messaggio dovrebbe essere ritrasmesso per intero a ogni hop: $303$ ms.

Confronto con la soluzione ufficiale

Ufficiale: $T_{tx}=N\,t_p+(N+K-1)\dfrac{H+M/K}{R}$ e $K_{opt}=\sqrt{\dfrac MH(N-1)}$: coincidono esattamente. La soluzione ufficiale cita anche il tempo di commutazione $t_s$ tra i simboli ma poi lo omette nella formula: qui si trascura, come da testo (elaborazione trascurabile). Nel testo c'è un solo switch ($N=2$ collegamenti), dove $K_{opt}=\sqrt{M/H}$.

Errori comuni

• Moltiplicare $K\cdot N\cdot t_{tx}$: ignora la pipeline tra gli hop.
• Dimenticare l'intestazione $H$ in ogni pacchetto: senza $H$, $T$ decresce sempre con $K$ e non c'è un ottimo.
• Confondere $N$ (collegamenti) con il numero di switch ($N-1$): il fattore nella formula di $K_{opt}$ è $N-1$.
• Arrotondare $K_{opt}$ senza confrontare i due interi vicini quando $K_{opt}$ è piccolo.

(Verificato con Python: con $M=10^6$, $H=100$, $N=3$, $R=10$ Mbps, $t_p=1$ ms: $K_{opt}=141{,}42$, $T(141)=105{,}848$ ms, $T(142)=105{,}848$ ms, minimo intero $K=141$.)