Frammentazione e architetture a strati

Internet come rete di reti

Internet è formata da molte reti gestite da ISP (Internet Service Provider), dalla periferia verso il centro: reti di accesso, ISP regionali e nazionali, reti intercontinentali e reti di estensione globale. Fra gli operatori valgono due relazioni.

• Customer-provider: un cliente chiede a un fornitore un servizio di transito. Al margine della rete un host chiede al proprio ISP un transito che si chiama accesso.
• Peering: due operatori pari si collegano direttamente quando la connessione conviene a entrambi.

Un IXP (Internet Exchange Point) è un punto di interconnessione fra reti: fa da scorciatoia e riduce i salti necessari per raggiungere una destinazione. Una CDN (Content Distribution Network) è un'infrastruttura in genere privata che avvicina i contenuti agli utenti, collegandosi alle reti di accesso o agli IXP, dove si concentrano molti operatori.

Frammentare un pacchetto

Un pacchetto ha un'intestazione di $h$ bit e un campo dati di $D$ bit. La frammentazione divide il campo dati in parti: ogni parte, un frammento, ripete l'intestazione.

Il guadagno è nel tempo. Un router in store and forward deve ricevere un frammento, non l'intero pacchetto, prima di ritrasmetterlo, e le trasmissioni sui diversi collegamenti si sovrappongono. Il costo è l'overhead, perché ogni frammento porta una nuova intestazione. Si cerca il numero di frammenti che minimizza il ritardo.

Esercizio 5. Un host A manda un pacchetto a un server B attraverso due router R1 e R2, su tre collegamenti in serie. Il collegamento $i$ ha capacità $C_i$ e ritardo di propagazione $\tau_i$.

Pacchetto intero. Su ogni collegamento servono la trasmissione del pacchetto, lungo $L$ bit, e la propagazione. Il ritardo end-to-end, con $L=h+D$, è

$$T_{e2e}=\sum_{i=1}^{3}\left(\frac{L}{C_i}+\tau_i\right)$$

$n$ frammenti. Il campo dati si divide in $n$ parti uguali, quindi ogni frammento è lungo $L=h+D/n$. Il primo arriva dopo $T_{e2e}$, calcolato con questa lunghezza. Gli altri $n-1$ arrivano uno dopo l'altro, a distanza pari al tempo di trasmissione sul collo di bottiglia:

$$T_{TOT}=T_{e2e}+(n-1)\frac{L}{C_{\text{bottleneck}}}$$

Il collo di bottiglia è $C_2$, perché si assume $C_2\le C_1\le C_3$:

$$\begin{aligned} T_{TOT}(n)&=\sum_{i=1}^{3}\left(\frac{h+D/n}{C_i}+\tau_i\right)\\ &\quad+(n-1)\frac{h+D/n}{C_2} \end{aligned}$$

Il numero di frammenti che minimizza il ritardo

La trasmissione di un frammento sul secondo collegamento compare $n$ volte, una nella somma e $n-1$ nel secondo termine: $n\,(h+D/n)/C_2=nh/C_2+D/C_2$. I termini che non dipendono da $n$ si raccolgono in una costante $K$:

$$\begin{aligned} T_{TOT}(n)&=\frac{D}{n}\left(\frac{1}{C_1}+\frac{1}{C_3}\right)+\frac{nh}{C_2}+K\\ K&=\tau_1+\tau_2+\tau_3+\frac{D}{C_2}\\ &\quad+h\left(\frac{1}{C_1}+\frac{1}{C_3}\right) \end{aligned}$$

Il primo termine diminuisce al crescere di $n$: è il guadagno dello store and forward. Il secondo cresce: è il tempo che le $n$ intestazioni occupano sul collo di bottiglia. Il ritardo prima scende e poi risale, quindi il punto con derivata nulla è il minimo:

$$\frac{dT_{TOT}}{dn}=-\frac{D}{n^2}\left(\frac{1}{C_1}+\frac{1}{C_3}\right)+\frac{h}{C_2}=0$$ $$n^*=\sqrt{\frac{C_2}{h}\left(\frac{D}{C_1}+\frac{D}{C_3}\right)}$$

Esempio numerico. Con $C_1=C_3=1$ Mbit/s, $C_2=900$ kbit/s, $\tau_1=\tau_2=\tau_3=3$ ms, $h=400$ bit e $D=10\,000$ bit si ha $n^*\approx 6{,}71$. Il numero di frammenti è intero: con 7 il ritardo è circa $26{,}88$ ms, con 6 circa $26{,}91$ ms, quindi si sceglie 7. Se $D/n$ non è intero, l'ultimo frammento è un po' più piccolo degli altri.

Frammenti sul percorso dell'esempio, tempi in ms

tempoAR1R2B$T_{TOT}$

$n$

7

Ritardo totale in funzione di $n$, in ms

$n^{\ast }$$n$$T_{TOT}$

• $T_{TOT}(n)$
• limite con $h$ trascurabile

$h$ (bit)

400

Intestazione trascurabile

Se $h$ si trascura, il pacchetto è lungo $D$ e

$$\begin{aligned} T_{TOT}(n)&=\sum_{i=1}^{3}\left(\frac{D/n}{C_i}+\tau_i\right)\\ &\quad+(n-1)\frac{D}{nC_2} \end{aligned}$$

Per $n\to\infty$ i termini $D/(nC_i)$ tendono a $0$ e $(n-1)/n$ tende a $1$. Con $\tau_{tot}=\tau_1+\tau_2+\tau_3$:

$$\lim_{n\to\infty}T_{TOT}(n)=\tau_{tot}+\frac{D}{C_{\text{bottleneck}}}$$

È il ritardo della commutazione di circuito con un circuito di capacità $C_{\text{bottleneck}}$: la propagazione lungo il percorso più il tempo per trasmettere il messaggio a quella capacità. Frammenti sempre più piccoli riducono lo store and forward fino a farlo sparire, quindi la commutazione di pacchetto raggiunge le prestazioni di quella di circuito. Il risultato vale solo se l'intestazione è trascurabile.

Esercizio 4: pacchetti verso due destinazioni

Al tempo $t=0$ la coda d'uscita di R1 contiene quattro pacchetti da $L=512$ bit: i primi due sono diretti ad A, gli altri due a B. Si cerca l'istante $t_k$ in cui il pacchetto $k$ è ricevuto per intero a destinazione.

Capacità in kbit/s, ritardi in ms

R1R2AB$C_1=256$, ${\tau }_1=1$$C_2=512$, ${\tau }_2=2$$C_3=64$, ${\tau }_3=4$

Capacità e ritardi sono potenze di 2, quindi conviene un'unità di tempo comune: la trasmissione più breve, quella su $C_2$, dura $512/512\,000$ s $=1$ ms. Gli altri tempi di trasmissione $T_{TX_i}=L/C_i$ ne sono multipli:

$$T_{TX_1}=2\ \text{ms},\quad T_{TX_2}=1\ \text{ms},\quad T_{TX_3}=8\ \text{ms}$$

Fino a R2. R1 trasmette senza pause: il pacchetto $k$ finisce di uscire a $2k$ ms e, dopo $\tau_1=1$ ms, R2 lo ha ricevuto per intero a $2k+1$ ms. Per i quattro pacchetti sono 3, 5, 7 e 9 ms. Solo allora R2 può ritrasmetterli.

Verso A. Per questa comunicazione il collo di bottiglia è $C_1$. R2 ritrasmette un pacchetto in 1 ms e i pacchetti arrivano a distanza di 2 ms, quindi non si forma coda.

Verso B. Qui il collo di bottiglia è $C_3$. Il pacchetto 3 è ricevuto a 7 ms e viene trasmesso da 7 a 15 ms. Il pacchetto 4 è ricevuto a 9 ms, ma R2 sta ancora trasmettendo il 3: aspetta in coda fino a 15 ms e viene trasmesso da 15 a 23 ms. Il pacchetto 4 arriva quindi $L/C_3=8$ ms dopo il 3.

Pacchetti 3 e 4 verso B, tempi in ms

tempoR1R2B27 ms

Gli istanti di arrivo sono la somma dell'istante in cui R2 inizia a trasmettere, della trasmissione e della propagazione:

$$\begin{aligned} t_1&=3+1+2=6\ \text{ms}\\ t_2&=5+1+2=8\ \text{ms}\\ t_3&=7+8+4=19\ \text{ms}\\ t_4&=15+8+4=27\ \text{ms} \end{aligned}$$

Ogni comunicazione ha il suo collo di bottiglia: $C_1$ da R1 ad A, $C_3$ da R1 a B. Due comunicazioni diverse possono averne di diversi.

Architettura a strati

Un'architettura a strati impila gli strati e li numera dal basso verso l'alto. Ogni strato svolge funzioni e offre servizi secondo standard. Come li realizza non interessa agli altri strati, che sono indipendenti: chi chiede un servizio di scrittura di biglietti d'auguri a mano vuole il biglietto scritto come promesso, non importa con quale mano.

Lo strato $i$ è fornitore di servizi per lo strato $i+1$ e cliente dello strato $i-1$, e comunica solo con gli strati adiacenti.

L'architettura del corso ha cinque strati, il modello classico sette. Dall'alto: applicazione (5), trasporto (4), rete (3), collegamento (2) e fisico (1). Seguono i tre strati più alti.

Applicazione. Per vedere una pagina web serve un browser, un processo client, che invia una richiesta a un processo server su un'altra macchina. Il server risponde con la pagina. Per l'applicazione esistono solo due processi che si scambiano messaggi: se il percorso attraversa cento router, fibre o collegamenti wireless non conta. È la logica di ogni applicazione client-server.

Trasporto. I due processi girano su macchine fisicamente separate, quindi non possono usare le chiamate fra processi di un sistema operativo. Lo strato di trasporto crea l'illusione che siano collegati da un cavo diretto, un collegamento logico: il processo, cliente, gli affida il messaggio e il trasporto, fornitore, lo consegna. Le socket sono le estremità di questo collegamento: interfacce logiche fra il processo applicativo e lo strato sottostante.

Rete. Il collegamento logico si appoggia a un'infrastruttura fisica: gli host sono collegati da una sequenza di reti locali e di router, i commutatori di pacchetto. Lo strato di rete offre il servizio di consegna end-to-end: salto dopo salto ogni router passa il messaggio al successivo, fino all'host di destinazione. Come lo fa non riguarda il trasporto.