Packet switching, ritardi e throughput

Internet come rete di reti

Nel packet switching i dati sono divisi in pacchetti, che attraversano i nodi con il meccanismo store and forward: il nodo riceve il pacchetto intero e solo dopo lo inoltra sul collegamento successivo. Nessuna risorsa è riservata in anticipo, e le risorse sono condivise a richiesta (multiplazione statistica). Quando le richieste superano ciò che il collegamento offre, i pacchetti aspettano nei nodi.

Internet è una rete di reti. Ogni rete è un Internet Service Provider (ISP) e gli ISP sono organizzati in livelli:

• Livello 1: grandi ISP con copertura nazionale o internazionale (Verizon, Sprint, AT&T). Sono collegati direttamente fra loro e comunicano alla pari (peer).
• Livello 2: ISP più piccoli, clienti di un ISP di livello 1, da cui ottengono la connettività con il resto della rete. Possono non essere collegati direttamente fra loro; per un collegamento diretto si usa un Internet Exchange Point.
• ISP locali (livello 3): danno accesso agli utenti finali e sono clienti di un ISP di livello 2.

Un pacchetto sale dall'ISP locale ai livelli superiori, può attraversare due ISP di livello 1 alla pari e poi scende fino alla destinazione. Il percorso cambia con il destinatario.

Riservare risorse lungo un percorso che attraversa tante reti eterogenee, di dimensioni e paesi diversi, è complesso. Il trasferimento a pacchetto è più semplice da realizzare, a prezzo di code e ritardi.

I quattro ritardi

Un pacchetto che passa da un nodo al collegamento successivo subisce quattro ritardi, uno dopo l'altro:

Quattro cause di ritardo

ABR1R2$R$, $d$

$$d_{\text{link}}=d_{\text{elab}}+d_{\text{queue}}+d_{\text{trasm}}+d_{\text{prop}}$$

• Elaborazione $d_{\text{elab}}$: il nodo legge l'intestazione, controlla errori sui bit e sceglie il collegamento di uscita (instradamento). È spesso piccolo e dipende dalla CPU del router.
• Accodamento $d_{\text{queue}}$: se due pacchetti devono uscire sullo stesso collegamento, parte per primo quello arrivato per primo; a parità di arrivo e senza priorità l'ordine è casuale. Ogni pacchetto attende la trasmissione di quelli che lo precedono, e pacchetti di lunghezze diverse producono attese diverse. Dipende dal traffico concorrente, quindi non si conosce a priori.
• Trasmissione $d_{\text{trasm}}$: tempo per immettere sul collegamento tutti i bit del pacchetto. Dipende dalla lunghezza $L$ del pacchetto (in bit) e dal bitrate $R$ del collegamento (in bit/s): dietro un pacchetto lungo si aspetta di più.
• Propagazione $d_{\text{prop}}$: tempo che il segnale impiega a percorrere il mezzo fisico, di lunghezza $d$, con velocità di propagazione $s$. La luce nel vuoto viaggia a circa $3\times10^8$ m/s, su un collegamento fisico a circa $2\times10^8$ m/s, cioè $1/s=5\ \mu\text{s}/\text{km}$.

$$\begin{aligned} d_{\text{trasm}}&=\frac{L}{R}\\ d_{\text{prop}}&=\frac{d}{s} \end{aligned}$$

$s$ e $R$ sono grandezze diverse: $R$ dice quanto in fretta i bit escono dal nodo, $s$ quanto in fretta il segnale viaggia. Con elaborazione e accodamento trascurabili, il ritardo del collegamento è $L/R+d/s$.

Una colonna di auto

Dieci auto fra due caselli, tempo in minuti

tempoCasello 1Casello 210 auto arrivate

$v$ (km/h)

100

servizio per auto (s)

12

Quali ritardi si possono ridurre

• Elaborazione: spesso trascurabile, e negli esercizi si trascura se è detto.
• Accodamento: è trascurabile se non ci sono altri pacchetti in transito. Per scaricare un file si può scegliere un momento di poco traffico; per un servizio interattivo o un video in diretta no.
• Trasmissione: si riduce aumentando $R$. Ridurre $L$ la riduce a sua volta, ma si trasmettono meno dati.
• Propagazione: si riduce accorciando il percorso. Per questo la vicinanza del server conta nei servizi a bassa latenza, come i videogiochi.

Traffico, code e perdita di pacchetti

Siano $a$ il numero medio di pacchetti che arrivano al nodo al secondo, ciascuno di $L$ bit, e $R$ il bitrate del collegamento in uscita. L'intensità di traffico è

$$\frac{La}{R}$$

• con $La/R$ vicino a 0 il ritardo di accodamento è molto limitato;
• con $La/R$ che tende a 1 cresce in modo non lineare, senza limite;
• con $La/R>1$ arriva più lavoro di quanto il collegamento ne smaltisca e il ritardo medio è infinito.

Gli arrivi sono casuali: anche con tassi medi uguali in ingresso e in uscita si formano code.

Esempio: molti utenti sullo stesso access point Wi-Fi generano traffico che lo congestiona. Passare a un altro access point cambia la distanza (propagazione) e il numero di utenti che lo condividono (accodamento): non risolve il problema se la causa è la quantità di traffico.

La coda di un router ha memoria finita. Il pacchetto che arriva a coda piena viene scartato: è la perdita di pacchetti. In IP la rete di norma non la recupera, e quando serve ci pensa un livello superiore. La tolleranza dipende dall'applicazione: una piccola perdita lascia comprensibile un messaggio vocale o un video, mentre un file o un testo si corrompono.

Coda e perdita a tassi costanti

$t$ (s)pacchetti

• pacchetti in coda
• pacchetti persi, in totale

$a$ (pacchetti/s)

500

$R/L$ (pacchetti/s)

350

capienza della coda (pacchetti)

50

Throughput e collo di bottiglia

Il throughput è il bitrate al quale i bit passano dal mittente al ricevente, istantaneo o medio su un periodo. Descrive il trasferimento effettivo lungo tutto il percorso, non il bitrate di una singola linea.

Come l'acqua in tubi di sezione diversa, il flusso è limitato dal tratto più stretto: il throughput è il bitrate più basso lungo il percorso, il collo di bottiglia. Non è la media dei bitrate. Una fibra veloce a un estremo non basta se l'altro estremo è lento.

Connessioni che condividono un collegamento

S1S2S3R1R2C1C2C3$R_s$$R_s$$R_s$$R$$R_c$$R_c$$R_c$

Con un server a bitrate $R_s$ e un client a bitrate $R_c$ il throughput è $\min(R_s,R_c)$. Se $N$ connessioni condividono un collegamento di bitrate $R$ a parti uguali, ciascuna ne ottiene $R/N$. Con $N=10$:

$$\text{throughput}=\min\left(R_c,\,R_s,\,\frac{R}{10}\right)$$

• $R=R_s=R_c=10$ Mbit/s: $\min(10,\,10,\,1)=1$ Mbit/s.
• $R=10$ Mbit/s, $R_s=5$ Mbit/s, $R_c=500$ kbit/s: $\min(0{,}5,\,5,\,1)=0{,}5$ Mbit/s.

Nel primo caso il collo di bottiglia è il collegamento condiviso, nel secondo è il collegamento del client. In pratica il collo di bottiglia è spesso $R_c$ o $R_s$.

Throughput di una connessione al crescere delle connessioni

$N$Mbit/s

• throughput $\min (R_c,R_s,R/N)$
• quota del collegamento condiviso $R/N$
• limite degli estremi $\min (R_s,R_c)$

$R_s$ (Mbit/s)

5

$R_c$ (Mbit/s)

2

$R$ (Mbit/s)

10