Commutazione a pacchetto e ritardi

Riassunto

La commutazione di pacchetto è una modalità connectionless che utilizza la multiplazione statistica delle risorse: in condizioni di basso fattore di attività, molti più utenti possono condividere un collegamento rispetto alla commutazione di circuito. I costi sono l'overhead dell'intestazione, i ritardi dovuti allo store and forward, l'accodamento e le possibili perdite di pacchetti. Un esempio confronta le due tecniche: con utenti attivi solo il 10% del tempo e una capacità di 1 Mbit/s, la commutazione di pacchetto può servire 35 utenti con bassa probabilità di congestione, mentre la commutazione di circuito ne servirebbe solo dieci. Il ritardo in una rete è composto da trasmissione, propagazione, elaborazione e accodamento. L'accodamento cresce molto quando il carico relativo si avvicina a uno, come previsto dalla teoria delle code M/M/1. Esercizi su collegamenti punto-punto e percorsi multi-hop illustrano il concetto di collo di bottiglia e l'effetto dello store and forward sui pacchetti consecutivi.

Concetti chiave

• Commutazione di circuito — modalità in cui gli utenti instaurano una connessione e ottengono risorse dedicate prima dello scambio; la multiplazione è statica.
• Commutazione di pacchetto — modalità connectionless in cui l'informazione è suddivisa in pacchetti inviati senza instaurare una connessione.
• Multiplazione statistica — condivisione delle risorse senza preallocarle: gli utenti competono quando trasmettono.
• Fattore di attività — percentuale del tempo in cui una sorgente on-off è nello stato ON e trasmette.
• Pacchetto — unità d'informazione con header (intestazione) e payload (contenuto).
• Store and forward — modalità in cui un commutatore riceve e immagazzina l'intero pacchetto prima di inoltrarlo, perché l'intestazione contiene le informazioni per il prossimo salto.
• Accodamento — attesa di un pacchetto in un buffer quando il collegamento in uscita è occupato.
• Congestione — condizione in cui il carico offerto supera la capacità del servente; la coda tende a crescere causando ritardi elevati e possibili perdite.
• Packet loss — perdita di pacchetti, che avviene quando il buffer si riempie (buffer overflow).
• Capacità — bit rate che la scheda di rete può trasmettere, misurato in bit al secondo.
• Tempo di trasmissione — tempo per trasferire sul collegamento tutti i bit di un pacchetto.
• Tempo di propagazione — tempo per il segnale di percorrere la distanza fisica del collegamento.
• Tempo di elaborazione — tempo per esaminare il pacchetto e consultare la tabella d'inoltro.
• Tempo di accodamento (queuing delay) — attesa prima di poter iniziare la trasmissione.
• Collo di bottiglia — collegamento meno capacitivo di un percorso.
• Overprovisioning — aumento della capacità oltre il necessario per ridurre il carico relativo.
• Coda M/M/1 — modello teorico di coda con arrivi poissoniani, disciplina FIFO, un servente e buffer infinito.

Sviluppo

Confronto tra commutazione di circuito e commutazione di pacchetto

Nella commutazione di circuito gli utenti instaurano una connessione prima di scambiare informazioni: ciò può essere inefficiente quando il tempo d'instaurazione è confrontabile con la durata dello scambio. La commutazione di pacchetto è invece connectionless: l'utente invia i dati senza prenotare prima una connessione.

Multiplazione statistica

Con la multiplazione statistica le risorse non sono preallocate agli utenti, che competono per usarle quando devono trasmettere. Questo funziona particolarmente bene se il fattore di attività è basso, cioè se ogni utente è attivo solo per una piccola parte del tempo: quando un utente prova a trasmettere, è probabile che la rete sia libera. La sorgente non invia i bit come uno stream continuo, ma raggruppa l'informazione in pacchetti.

Struttura dei pacchetti e store and forward

Un pacchetto ha due parti: header e payload. Il contenuto dell'utente si trova nel payload; l'header contiene informazioni di sistema che servono alla rete per la consegna e per altri servizi. Come in un pacco spedito, il contenuto è il messaggio, mentre involucro e indirizzo aiutano il sistema a consegnarlo e proteggerlo.

La differenza operativa fondamentale rispetto a un commutatore di circuito è il paradigma store and forward. Il commutatore di pacchetto deve ricevere il pacchetto per intero prima di inoltrarlo, perché deve leggere nell'intestazione le informazioni sul prossimo salto. Il pacchetto viene quindi trattato come un'unità che viaggia tutta insieme.

Costi e limiti della commutazione di pacchetto

Lo store and forward aggiunge un ritardo a ogni salto: in una rete multi-hop il pacchetto deve essere trasmesso su ciascun collegamento. A questo si aggiungono l'overhead dell'header e l'accodamento. Se il collegamento in uscita è occupato, il pacchetto attende in un buffer; l'attesa aggiunge un ritardo e, se il buffer si riempie, può verificarsi un overflow e quindi una perdita di pacchetti.

Le prestazioni diventano probabilistiche e non deterministiche: non si può conoscere in anticipo il ritardo o la banda che un utente otterrà. Si possono descrivere il comportamento medio e altri aspetti in termini probabilistici. Il commutatore usa una tabella che associa destinazioni e interfacce di uscita; un protocollo, da trattare più avanti, ha il compito di compilarla.

Esempio: confronto quantitativo tra le due tecniche

$N$ utenti condividono un collegamento d'accesso a Internet da 1 Mbit/s. Ogni sorgente è on-off: quando è nello stato ON trasmette a 100 kbit/s ed è ON per il 10% del tempo. Un flusso di questo tipo è paragonabile a quello di una videochiamata a qualità medio-bassa.

Con la commutazione di circuito si assegnano canali da 100 kbit/s, perché canali più grandi sprecherebbero capacità e canali più piccoli non soddisferebbero il bit rate richiesto. Il collegamento da 1 Mbit/s si suddivide quindi in dieci canali: solo dieci utenti possono essere serviti, mentre gli altri vengono bloccati o rifiutati.

Con la commutazione di pacchetto, la situazione critica si verifica quando almeno undici utenti sono ON simultaneamente: il traffico offerto, $11\times 100$ kbit/s $=1{,}1$ Mbit/s, supera allora la capacità di 1 Mbit/s. La coda può crescere e, se il buffer si riempie, le prestazioni peggiorano e si verificano perdite. Interessa quindi la probabilità di questo evento.

Probabilità degli utenti attivi

Si assume che gli stati dei diversi utenti siano indipendenti. Per avere esattamente $K$ utenti ON, una combinazione specifica richiede che $K$ utenti siano ON e i restanti $N-K$ siano OFF. La probabilità di tale combinazione è il prodotto delle probabilità dei singoli stati. Poiché esistono più combinazioni di $K$ utenti scelti tra $N$, si moltiplica per il coefficiente binomiale.

La probabilità che vi sia congestione è la somma delle probabilità associate a tutti i valori da $K=11$ fino a $N$. Per $N=35$ vale circa $0{,}0004$, cioè $0{,}4$ per mille: la probabilità è trascurabile, e con la commutazione di pacchetto tutti i 35 utenti possono usufruire del servizio con alta probabilità, mentre con la commutazione di circuito solo dieci ottengono un canale. Il fattore di attività è $p=0{,}1$.

Quando conviene ciascuna commutazione

La multiplazione statistica è particolarmente efficace quando $N$ è grande e il fattore di attività è piccolo: in tali condizioni è probabile che la risorsa sia libera quando una sorgente deve trasmettere. La commutazione di circuito può invece essere poco efficiente per scambi brevi, perché il tempo d'instaurazione pesa rispetto alla durata del trasferimento.

La scelta dipende dal servizio. Per la telefonia la commutazione di circuito può essere adatta; per la comunicazione tra macchine, per esempio tra molti sensori che inviano pochi bit di temperatura, dedicare un canale a ciascun sensore sarebbe problematico, mentre la multiplazione statistica può essere conveniente.

Modello del collegamento e parametri

Si considera un router R1 collegato a un router R2. La scheda di rete (NIC) di R1 trasmette sul mezzo fisico verso il router successivo. Il bit rate della NIC, indicato con $C$, dipende dall'hardware e deve essere supportato dal mezzo trasmissivo.

Il mezzo è caratterizzato dalla lunghezza fisica $D$ e dal materiale. Il materiale influenza sia la banda passante sia la velocità di propagazione $V$ dell'onda elettromagnetica. Il pacchetto ha lunghezza $L$ misurata in bit; anche l'occupazione del buffer $B$ è misurata in bit. La lunghezza del pacchetto non va confusa con una distanza in metri.

Componenti del ritardo

Il ritardo è composto da quattro termini: tempo di trasmissione, tempo di propagazione, tempo di accodamento e tempo di elaborazione. I ritardi si indicano con $T$, per distinguerli dalla distanza $D$.

Tempo di trasmissione

La NIC trasferisce i bit dalla memoria al canale uno alla volta, convertendo l'informazione binaria in un segnale che si propaga sul mezzo. Durante la trasmissione, una parte del pacchetto può già essere sul canale mentre il resto è ancora nella memoria della scheda. Il tempo necessario a trasmettere tutti i bit è $L/C$.

Come un gruppo di automobili che entra in autostrada attraverso un casello, ogni automobile corrisponde a un bit e la capacità indica quante automobili (o bit) il casello riesce a far passare nell'unità di tempo. Le automobili già entrate proseguono il viaggio mentre le successive sono ancora al casello.

Tempo di propagazione

Una volta sul canale, il segnale impiega tempo per raggiungere il ricevitore. Il tempo dipende dalla distanza e dalla velocità di propagazione nel mezzo: un collegamento più lungo comporta un ritardo maggiore. In alcune reti satellitari a orbita bassa (LEO), il percorso e la propagazione nel vuoto possono contribuire a ritardi competitivi rispetto a collegamenti in fibra.

Tempo di elaborazione

La scheda o il router esamina il pacchetto in ingresso: estrae l'header, individua informazioni come l'indirizzo di destinazione, consulta la tabella e sposta il pacchetto verso l'interfaccia d'uscita. Queste operazioni richiedono un tempo non nullo, che si considera trascurabile rispetto a ritardi di propagazione di diversi millisecondi. Nelle funzioni di rete virtualizzate, eseguite in macchine virtuali o container, il processamento può invece diventare un collo di bottiglia.

Il parsing è l'interpretazione dell'header per estrarne i campi rilevanti, per esempio gli indirizzi sorgente e destinazione, come in un modulo da compilare con caselle quali nome, cognome e matricola.

Tempo di accodamento

Il buffer contiene i pacchetti in attesa di essere trasmessi sul link, oltre all'eventuale pacchetto già in trasmissione. Se un nuovo pacchetto trova un pacchetto in corso e tre pacchetti davanti a sé, deve aspettare che termini la trasmissione in corso e che siano trasmessi quelli in coda.

Non si può conoscere in anticipo la situazione esatta che il pacchetto troverà al suo arrivo: dipende dal numero e dalla lunghezza dei pacchetti in coda e dalla parte ancora da trasmettere del pacchetto in servizio. Si può interrogare il dispositivo e ottenere una fotografia istantanea dello stato, ma non conoscere in anticipo lo stato nell'istante di arrivo.

Carico e modello M/M/1

La teoria delle code permette di stimare parametri come il tempo medio di accodamento. Il modello M/M/1 assume, come ipotesi semplificative, arrivi modellati con un processo di Poisson, coda FIFO e buffer infinito. Il buffer infinito è un'idealizzazione teorica che esclude le perdite.

Il carico relativo $\rho$ confronta il traffico medio offerto con la capacità del servente. Con carico basso il tempo medio di accodamento è prossimo a zero; aumentando il carico, il ritardo cresce; quando $\rho$ si avvicina a uno, il ritardo medio tende a diventare infinito. Come nel traffico stradale, le code possono nascere anche senza incidenti, quando il numero di automobili che attraversa un tratto si avvicina alla capacità della strada.

Il modello è teorico e basato su ipotesi forti, ma suggerisce di far lavorare la rete con carico offerto molto inferiore alla sua capacità.

Ridurre il carico relativo: overprovisioning

Per ridurre il rapporto tra traffico offerto e capacità si può aumentare la capacità oppure ridurre il traffico offerto. Aumentare il denominatore è l'approccio più comune: si installa capacità in eccesso rispetto al traffico previsto. Questa strategia, chiamata overprovisioning, è efficace ma costosa.

Ridurre la dimensione dei pacchetti è un intervento poco efficace se aumenta l'overhead. Agire sul fattore di attività richiede tecniche più sofisticate, trattate in corsi avanzati.

Esercizio 1: trasmissione e propagazione

Un collegamento punto-punto è lungo 500 km, ha un data rate di 100 kbit/s e un ritardo di propagazione di 5 microsecondi per chilometro. Il pacchetto è lungo 2000 bit. Il tempo tra la trasmissione del primo bit e la ricezione dell'ultimo è la somma del tempo necessario a trasmettere l'intero pacchetto e di quello necessario all'ultimo bit per propagarsi.

La «velocità» espressa in kbit/s indica il data rate, mentre il ritardo espresso in microsecondi per chilometro va moltiplicato per la lunghezza del collegamento:

• tempo di trasmissione: $T_{\text{trasmissione}} = \dfrac{2000\ \text{bit}}{100\ \text{kbit/s}} = 20$ ms;
• tempo di propagazione: $T_{\text{propagazione}} = 500\ \text{km}\cdot 5\ \mu\text{s/km} = 2500\ \mu\text{s} = 2{,}5$ ms;
• tempo totale: $20\ \text{ms} + 2{,}5\ \text{ms} = 22{,}5$ ms.

Esercizio 2: round trip time

Un pacchetto di 10.000 bit viene inviato da A a B su un collegamento lungo 100 km, poi viene ricevuto interamente e rimandato ad A. La velocità del segnale è 200.000 km/s. Poiché B opera in store and forward, il pacchetto deve essere ricevuto interamente prima di iniziare la trasmissione di ritorno. Il tempo richiesto è quindi formato da due tempi di propagazione e due tempi di trasmissione.

Con data rate di 100 kbit/s, in una direzione il tempo di propagazione è $\dfrac{100\ \text{km}}{200.000\ \text{km/s}} = 0{,}5$ ms e quello di trasmissione è $\dfrac{10.000\ \text{bit}}{100\ \text{kbit/s}} = 100$ ms; il round trip time è $2\cdot 0{,}5 + 2\cdot 100 = 201$ ms.

Ripetendo il calcolo a 10 Gbit/s, il tempo di trasmissione in una direzione è $10.000\ \text{bit}/(10\ \text{Gbit/s}) = 1\ \mu\text{s}$ e il round trip time è $2\cdot 0{,}5\ \text{ms} + 2\cdot 1\ \mu\text{s} = 1{,}002$ ms, dominato dalla propagazione.

Esercizio multi-hop: due pacchetti e collo di bottiglia

Si considera il percorso R1 → R2 → R3 → A, con due pacchetti di 512 bit inizialmente in coda a R1. I ritardi di propagazione sono $\tau_1=\tau$, $\tau_2=2\tau$ e $\tau_3=\tau$, con $\tau=1$ ms. Le capacità sono $C_1=C$, $C_2=2C$ e $C_3=4C$, con $C_1=128$ kbit/s. I tempi di trasmissione sono quindi $4$ ms, $2$ ms e $1$ ms.

Nel diagramma spazio-tempo, a ogni salto del primo pacchetto si sommano un tempo di trasmissione e uno di propagazione, con attesa store and forward prima dell'inoltro. Il primo pacchetto arriva interamente a destinazione dopo $(1+4)+(2+2)+(1+1)=11$ ms.

Il secondo pacchetto parte da R1 appena termina la trasmissione del primo sul primo link; la trasmissione procede senza soluzione di continuità finché ci sono pacchetti da inviare. In questo esempio il primo link è il meno capace, quindi il secondo pacchetto arriva 4 ms dopo il primo, per un tempo complessivo di 15 ms. Se la capacità dei link fosse disposta in ordine opposto, il tempo complessivo resterebbe uguale, ma si creerebbe un riaccodamento al link collo di bottiglia.

Formule e dimostrazioni

Confronto tra capacità e utenti serviti

$N_{\text{canali}}=\frac{C_{\text{tot}}}{R_{\text{utente}}}=\frac{1\ \text{Mbit/s}}{100\ \text{kbit/s}}=10$

$C_{\text{tot}}$ è la capacità totale del collegamento; $R_{\text{utente}}$ è il bit rate richiesto da un utente attivo.

Probabilità di utenti ON e congestione

$P(X=K)=\binom{N}{K}p^K(1-p)^{N-K}$

$N$ è il numero totale di utenti; $K$ è il numero di utenti ON; $p=0{,}1$ è la probabilità che un utente sia ON; $1-p$ è la probabilità che sia OFF. L'indipendenza degli stati permette di moltiplicare le probabilità per una combinazione specifica. Il coefficiente binomiale $\binom{N}{K}$ conta le possibili scelte dei $K$ utenti attivi.

$P(X>10)=P(X\geq 11)=\sum_{K=11}^{N}\binom{N}{K}p^K(1-p)^{N-K}$

$X$ è il numero di utenti simultaneamente ON. La soglia di congestione è almeno undici utenti attivi, perché ciascuno offre 100 kbit/s e la capacità totale è 1 Mbit/s. Per $N=35$ risulta $P(X\geq 11)\approx 0{,}0004$.

Ritardo di nodo e singole componenti

$T=T_{\text{trasmissione}}+T_{\text{propagazione}}+T_{\text{accodamento}}+T_{\text{elaborazione}}$

I quattro termini rappresentano il tempo per trasmettere il pacchetto, il tempo di propagazione, l'attesa in coda e il processamento.

$T_{\text{trasmissione}}=\frac{L}{C}, \qquad T_{\text{propagazione}}=\frac{D}{V}$

$L$ è la lunghezza del pacchetto in bit; $C$ è la capacità in bit/s; $D$ è la lunghezza fisica del collegamento; $V$ è la velocità di propagazione del segnale nel mezzo.

Carico relativo:

$\rho=\frac{A L}{C}$

$A$ è il numero medio di pacchetti in arrivo al secondo; $L$ è la lunghezza media di un pacchetto in bit; $C$ è la capacità del servente in bit/s. Il tempo medio di accodamento cresce rapidamente quando $\rho$ si avvicina a uno.

Round trip time

$RTT=2T_{\text{propagazione}}+2T_{\text{trasmissione}}=2\frac{D}{V}+2\frac{L}{C}$

$D$ è la distanza tra $A$ e $B$; $V$ è la velocità del segnale; $L$ è la lunghezza del pacchetto; $C$ è il data rate. Per $D=100$ km, $V=200.000$ km/s, $L=10.000$ bit e $C=100$ kbit/s si ottiene $RTT=201$ ms.

Percorso multi-hop e pacchetti consecutivi

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

$\tau_i$ è il ritardo di propagazione del link $i$; $C_i$ è la sua capacità; $L$ è la lunghezza del pacchetto. Per i valori dell'esercizio:

$T_1=(1+4)+(2+2)+(1+1)\ \text{ms}=11\ \text{ms}$

Arrivo del secondo pacchetto nel caso descritto:

$T_2=T_1+\frac{L}{C_{\text{bottleneck}}}=11\ \text{ms}+4\ \text{ms}=15\ \text{ms}$

$C_{\text{bottleneck}}$ è la capacità del link meno capace; nell'esempio è $C_1=128$ kbit/s, quindi $L/C_1=4$ ms.