Frammentazione dei pacchetti ed effetto pipeline

Un messaggio, uno o più pacchetti

Un messaggio di $X$ bit può viaggiare in un unico pacchetto o diviso in $P$ frammenti, ciascuno con la propria intestazione. Dividerlo sembra solo un costo, perché le intestazioni si ripetono. Ma un pacchetto solo occupa un'interfaccia alla volta, mentre i frammenti possono trovarsi insieme su interfacce diverse: questa sovrapposizione è l'effetto pipeline. Il ritardo di trasferimento è il bilancio fra i due effetti, e per questo la dimensione dell'unità informativa di uno strato, fissata da uno standard, non è indifferente.

Notazione:

• $H$ è l'intestazione, in bit e uguale in ogni pacchetto; $L$ sono i bit di testo di un pacchetto, che è quindi lungo $H+L$. Con testi uguali i frammenti sono $P=X/L$.
• $N$ è il numero di interfacce attraversate, $C_i$ il bit rate dell'interfaccia $i$ e $d_{\text{prop},i}$ il suo ritardo di propagazione.
• $D_{\text{PAC}}$ è il ritardo di trasferimento di un pacchetto, $D_{\text{MES}}$ quello del messaggio: dall'emissione del primo bit alla ricezione dell'ultimo.

La rete è scarica, senza altro traffico che faccia attendere i pacchetti nei nodi ($d_{\text{mem}}=0$), e l'elaborazione nei nodi è trascurabile ($d_{\text{elab}}=0$). Un nodo ritrasmette un pacchetto solo quando l'ha ricevuto per intero.

Tre interfacce da A a B

AN1N2B$C_1$, $d_{\text{prop},1}$$C_2$, $d_{\text{prop},2}$$C_3$, $d_{\text{prop},3}$

Un pacchetto intero

Su ogni interfaccia il pacchetto paga la trasmissione e poi la propagazione. I contributi delle interfacce si sommano, perché ogni nodo aspetta il pacchetto intero:

$$D_{\text{PAC}}=\sum_{i=1}^{N}\Bigl(\frac{H+L}{C_i}+d_{\text{prop},i}\Bigr)$$

Con lo stesso $C$ e lo stesso $d_{\text{prop}}$ su tutte le interfacce:

$$\begin{aligned} D_{\text{PAC}}&=N\,\frac{H+L}{C}+d_{\text{prop,AB}}\\ d_{\text{prop,AB}}&=N\,d_{\text{prop}} \end{aligned}$$

Il messaggio in un solo pacchetto ha $L=X$.

Due frammenti

Con $P=2$ si ha $L=X/2$ e ogni frammento è lungo $H+X/2$. Il secondo porta un'intestazione in più, ma $D_{\text{MES}}$ non è la somma di due ritardi di pacchetto: mentre il primo frammento è sull'interfaccia 2, il secondo è già sulla 1.

Si legge il ritardo sul diagramma spazio-tempo, nel caso in cui $C_2$ è più lento di $C_1$ e di $C_3$. Tre tratti:

• il primo frammento da solo sull'interfaccia 1: $(H+L)/C_1+d_{\text{prop},1}$;
• tutti i frammenti sull'interfaccia 2, la più lenta, dove si susseguono senza pause: $P\,(H+L)/C_2+d_{\text{prop},2}$;
• l'ultimo frammento da solo sull'interfaccia 3: $(H+L)/C_3+d_{\text{prop},3}$.

I frammenti arrivano in N1 più in fretta di quanto l'interfaccia 2 riesca a trasmetterli, quindi aspettano in N1 e la occupano di seguito. L'interfaccia 3 è più veloce e trova libero ogni frammento che arriva. Le trasmissioni sovrapposte si contano una volta sola. Moltiplicare per $P$ il ritardo di un frammento, come se i frammenti si susseguissero lungo tutto il percorso, sarebbe sbagliato.

Il messaggio in P frammenti

tempoAN1N2B$D_{\text{MES}}$

$P$

2

Con $L=X/P$ e le tre interfacce:

$$\begin{aligned} D_{\text{MES}}(P)&=\Bigl(H+\frac XP\Bigr)\Bigl(\frac1{C_1}+\frac P{C_2}+\frac1{C_3}\Bigr)\\ &\quad+\sum_{i=1}^{3}d_{\text{prop},i} \end{aligned}$$

Per $P=1$ ritorna $D_{\text{PAC}}$.

Interfacce uguali: contare gli intervalli

Con $N=3$ interfacce uguali e senza propagazione, ogni frammento dura $(H+X/3)/C$ su ogni interfaccia. Il messaggio intero impiega $3(H+X)/C$. Diviso in tre frammenti, il diagramma non contiene $3\cdot 3=9$ intervalli ma 5: il secondo frammento viaggia insieme al primo, il terzo insieme al secondo, e quelle trasmissioni si contano una volta.

Tre interfacce uguali, senza propagazione

tempoAN1N2B$D_{\text{MES}}$

$P$

3

La regola vale per $N$ e $P$ qualsiasi: il primo frammento percorre tutte le $N$ interfacce; ognuno dei $P-1$ restanti viaggia insieme al precedente, un'interfaccia più indietro, e solo sull'ultima interfaccia aggiunge un intervallo. Con la propagazione uguale su ogni interfaccia:

$$\begin{aligned} D_{\text{MES}}&=(N+P-1)\,\frac{H+L}{C}+d_{\text{prop,AB}}\\ L&=\frac XP \end{aligned}$$

Con cinque nodi intermedi le interfacce sono $N=6$. Due frammenti occupano $6+2-1=7$ intervalli, non $12$; tre frammenti ne occupano $8$. Il parallelismo c'è solo nel tratto intermedio: se le interfacce crescono più dei frammenti, quel tratto pesa sempre meno sul totale, ma il guadagno resta.

Quanti frammenti

Sviluppando il prodotto di $D_{\text{MES}}(P)$ solo due termini dipendono da $P$:

$$\begin{aligned} D_{\text{MES}}(P)&=\frac{H\,P}{C_2}+\frac XP\Bigl(\frac1{C_1}+\frac1{C_3}\Bigr)\\ &\quad+H\Bigl(\frac1{C_1}+\frac1{C_3}\Bigr)+\frac X{C_2}+\sum_{i=1}^{3}d_{\text{prop},i} \end{aligned}$$

Il primo cresce con $P$: sono le intestazioni in più sull'interfaccia più lenta. Il secondo decresce: il primo e l'ultimo frammento, che viaggiano da soli, diventano più brevi. Ogni frammento in più aggiunge $H$ bit: in tutto se ne trasmettono $X+P\,H$. Quindi $D_{\text{MES}}$ scende finché prevale la pipeline e poi risale per il peso delle intestazioni.

Il minimo, con $P$ trattato come numero reale, si trova annullando la derivata:

$$\begin{aligned} \frac{dD_{\text{MES}}}{dP}&=\frac H{C_2}-\frac X{P^2}\Bigl(\frac1{C_1}+\frac1{C_3}\Bigr)=0\\ P^*&=\sqrt{\frac{X\,C_2}{H}\Bigl(\frac1{C_1}+\frac1{C_3}\Bigr)} \end{aligned}$$

I frammenti sono un numero intero, quindi si confrontano gli interi vicini a $P^*$.

Esempio. Sia $C_1=C_3=1$ Mb/s $=1000$ kb/s, $C_2=900$ kb/s, $d_{\text{prop},i}=1,\,2,\,3$ ms, $H=400$ bit e $X=10\,000$ bit. Con i bit rate in kb/s i tempi escono in ms. Sostituendo nella formula, il messaggio intero dà $D_{\text{MES}}\approx 38{,}36$ ms; con due frammenti il ritardo scende a $28{,}8$ ms, nonostante la seconda intestazione.

$$P^*=\sqrt{\frac{10\,000\cdot 900}{400}\cdot\frac{2}{1000}}=\sqrt{45}\approx 6{,}71$$

Per $P=6$ si ha $23{,}91$ ms e per $P=7$ si ha $23{,}88$ ms: il valore intero migliore è 7.

Il ritardo al variare dei frammenti

$P^{\ast }$$P$$D_{\text{MES}}$ (ms)

• $D_{\text{MES}}(P)$

$H$ (bit)

400