Esercizio - Frammentazione di un pacchetto su tre collegamenti

Testo. Si consideri la connessione in catena $A\to R_1\to R_2\to B$ formata da tre collegamenti:

1. Esprimere in forma parametrica il tempo necessario per trasmettere un pacchetto di lunghezza $h+D$ bit da $A$ a $B$.
2. Supporre che il pacchetto sia diviso in due frammenti. Esprimere in forma parametrica il tempo per inviare tutti i frammenti da $A$ a $B$, con $C_2\le C_1\le C_3$.
3. Qual è il numero di frammenti che dà il tempo totale di trasmissione più breve?

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 →.

Modello e simboli

Router store-and-forward senza elaborazione né accodamento da altro traffico. $h$ è l'intestazione e $D$ il carico utile in bit. Quando si frammenta, ogni frammento porta una propria intestazione $h$ (è l'ipotesi standard: ogni pezzo deve poter essere instradato e ricomposto), quindi un frammento di $K$ è lungo $L_K=h+\dfrac DK$ bit. Il tempo di trasmissione di un frammento sul collegamento $i$ è $a_i=\dfrac{L_K}{C_i}$.

(1) Un solo pacchetto

Il pacchetto viene ricevuto per intero ad ogni nodo e poi ritrasmesso: si sommano le tre trasmissioni e le tre propagazioni, $$T_1=\frac{h+D}{C_1}+\frac{h+D}{C_2}+\frac{h+D}{C_3}+t_1+t_2+t_3=(h+D)\left(\frac1{C_1}+\frac1{C_2}+\frac1{C_3}\right)+t_1+t_2+t_3.$$

(2) Due frammenti

Sia $L=h+D/2$ e $a_i=L/C_i$. Per le ipotesi $C_2\le C_1\le C_3$ si ha $a_1\le a_2$ e $a_3\le a_2$: il collegamento 2 è il collo di bottiglia (il più lento), che serve i frammenti uno dopo l'altro. Seguiamo i due frammenti:

• Frammento 1. Fine tx su $C_1$ a $a_1$, arriva a $R_1$ a $a_1+t_1$; viene trasmesso su $C_2$ fino a $a_1+t_1+a_2$, poi arriva a $R_2$ e così via.
• Frammento 2. Finisce su $C_1$ a $2a_1$ e arriva a $R_1$ a $2a_1+t_1$. Poiché $a_1\le a_2$, a quel tempo ($2a_1+t_1\le a_1+t_1+a_2$) il collegamento 2 sta ancora trasmettendo il frammento 1: il frammento 2 aspetta e parte subito dopo, a $a_1+t_1+a_2$, finendo a $a_1+t_1+2a_2$.
• A $R_2$ il frammento 2 arriva a $a_1+t_1+2a_2+t_2$; il collegamento 3 ha già finito il frammento 1 (a $a_1+t_1+a_2+t_2+a_3\le$ quel valore perché $a_3\le a_2$), quindi non c'è attesa: lo trasmette in $a_3$ e dopo $t_3$ è in $B$.

Il tempo totale è quello dell'ultimo frammento: $$T_2=a_1+t_1+2a_2+t_2+a_3+t_3=\left(h+\frac D2\right)\left(\frac1{C_1}+\frac2{C_2}+\frac1{C_3}\right)+t_1+t_2+t_3.$$ Il collo di bottiglia viene "pagato" due volte (una per frammento); gli altri due collegamenti una volta.

(3) Numero ottimo di frammenti

Con lo stesso ragionamento, con $K$ frammenti il collegamento 2 trasmette $K$ frammenti consecutivi mentre gli altri due collegamenti trasmettono ciascuno un frammento in più della fila (il primo sul collegamento 1 prima del collo di bottiglia, l'ultimo sul collegamento 3 dopo). Il perché: dato che $a_1\le a_2$, il frammento $k$ arriva a $R_1$ (a $k\,a_1+t_1$) quando il collegamento 2 sta ancora trasmettendo il precedente, quindi il collegamento 2 lavora senza pause da $a_1+t_1$ fino a $a_1+t_1+K a_2$. Dato che $a_3\le a_2$, il collegamento 3 smaltisce ogni frammento prima che arrivi il successivo e l'ultimo frammento paga solo la propria trasmissione $a_3$. Sommando, il tempo di arrivo dell'ultimo frammento è $a_1+t_1+Ka_2+t_2+a_3+t_3$, cioè: $$T(K)=\left(h+\frac DK\right)\left(\frac1{C_1}+\frac K{C_2}+\frac1{C_3}\right)+t_1+t_2+t_3.$$ Sviluppando: $$T(K)=h\left(\frac1{C_1}+\frac1{C_3}\right)+\frac{hK}{C_2}+\frac D{K}\left(\frac1{C_1}+\frac1{C_3}\right)+\frac D{C_2}+t_1+t_2+t_3.$$ Il termine $D\left(\frac1{C_1}+\frac1{C_3}\right)/K$ decresce con $K$ (frammenti più piccoli attraversano più in fretta i collegamenti non critici), mentre $hK/C_2$ cresce (ogni frammento in più ripaga un'intestazione sul collo di bottiglia). Si pone a zero la derivata (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 →; la derivata di $D S/K$ rispetto a $K$ è $-DS/K^2$, con $S=\frac1{C_1}+\frac1{C_3}$ costante, per la regola della potenzala derivata di K elevato a n è n per K elevato a n-1, qui con n uguale a -1Regole di derivazione →; la derivata di $hK/C_2$ è $h/C_2$, e le costanti $hS$, $D/C_2$, $\sum t_i$ spariscono): $$\frac{dT}{dK}=\frac h{C_2}-\frac D{K^2}\left(\frac1{C_1}+\frac1{C_3}\right)=0\ \Longrightarrow\ \boxed{K_{opt}=\sqrt{\frac Dh\,C_2\left(\frac1{C_1}+\frac1{C_3}\right)}}.$$ Passaggio algebrico: $\frac h{C_2}=\frac{DS}{K^2}\Rightarrow K^2=\frac{D}{h}C_2S\Rightarrow K=\sqrt{\frac Dh C_2 S}$ (si prende la radice positiva, perché $K>0$). È davvero un minimo: la derivata seconda $\frac{d^2T}{dK^2}=\frac{2DS}{K^3}$ è positiva per $K>0$, quindi $T$ è convessa (Funzioni convesse, concave e punti di flessof è convessa se ogni corda sta sopra il grafico (concava se sta sotto). Una funzione convessa è continua e ha derivate destra e sinistra in ogni punto interno. Per f derivabile: convessa ⇔ grafico sopra ogni tangente ⇔ f' crescente ⇔ (se esiste) f'' ≥ 0. f'' > 0 ⇒ strettamente convessa, non viceversa (x⁴). Flesso: punto in cui f passa da convessa a concava; lì, se esiste, f''(x0) = 0, ma non basta (x⁴ in 0).Funzioni convesse, concave e punti di flesso →) e il punto stazionario è il minimo.

La curva vale per $K$ reale; solo i valori interi hanno senso fisico, e il minimo intero è $K=5$ (la curva è molto piatta attorno al minimo: $T(4)=9{,}794$ e $T(5)=9{,}784$ ms differiscono di $0{,}01$ ms). Poiché $C_2\le C_1$ e $C_2\le C_3$, vale $C_2\left(\frac1{C_1}+\frac1{C_3}\right)\le2$, quindi $K_{opt}\le\sqrt{2D/h}$; se i tre collegamenti hanno la stessa capacità $K_{opt}=\sqrt{2D/h}$ (e la formula coincide con quella di Esercizio - Commutazione di pacchetto e numero ottimo di pacchetti con $N=3$). Il numero intero migliore è quello tra i due vicini a $K_{opt}$ con $T$ minore. La formula vale finché il collegamento 2 resta il collo di bottiglia, cioè sempre, perché $a_i\propto L_K/C_i$ conserva l'ordine dei collegamenti.

Esempio numerico

$C_1=10$ Mbps, $C_2=2$ Mbps, $C_3=20$ Mbps (rispetta $C_2\le C_1\le C_3$), $h=160$ bit, $D=12\,000$ bit, $t_1=t_2=t_3=1$ ms.

• $T_1=12\,160\left(\frac1{10^7}+\frac1{2\cdot10^6}+\frac1{2\cdot10^7}\right)+3\ \text{ms}=12\,160\cdot6{,}5\cdot10^{-7}+3\ \text{ms}=7{,}904+3=10{,}904$ ms.
• Due frammenti: $L=6160$ bit, $a_1=0{,}616$ ms, $a_2=3{,}08$ ms, $a_3=0{,}308$ ms:

(formula: $0{,}616+2\cdot3{,}08+0{,}308+3=10{,}084$ ms).

• $K_{opt}=\sqrt{\frac{12\,000}{160}\cdot2\cdot\left(\frac1{10}+\frac1{20}\right)}=\sqrt{75\cdot0{,}3}=4{,}74$. Confronto:

Il minimo è $K=5$ ($9{,}784$ ms), seguito da $K=4$ ($9{,}794$ ms): coerente con $K_{opt}=4{,}74$. La frammentazione fa guadagnare circa il $10\%$ rispetto a un solo pacchetto.

Confronto con la soluzione ufficiale

Per questo esercizio le slide delle soluzioni non riportano un risultato (la serie delle soluzioni salta dal 4 al 6), quindi non c'è un numero da confrontare. I risultati sono stati controllati con una simulazione store-and-forward (tempi di fine trasmissione e arrivo di ogni frammento su ogni collegamento), che coincide con le formule per tutti i $K$ provati.

Errori comuni

• Dimenticare che ogni frammento ha la propria intestazione $h$: senza $h$ il tempo decrescerebbe sempre con $K$ e non esisterebbe un ottimo.
• Pagare il collo di bottiglia una sola volta (o tutti i collegamenti $K$ volte): solo il collegamento più lento viene "pagato" $K$ volte, gli altri una sola.
• Usare $C_2$ come collo di bottiglia quando l'ordine delle capacità è diverso: la formula di $T(K)$ vale solo se il collegamento più lento è il 2.

(Verificato con Python: $T_1=10{,}904$ ms; $T(2)=10{,}084$ ms (formula e simulazione); $K_{opt}=4{,}74$; minimo intero $K=5$ con $T=9{,}784$ ms.)