Commutazione di circuito e di pacchetto

Il problema

Una rete non può collegare con un cavo ogni coppia di nodi (in una maglia servono $n(n-1)/2$ collegamenti, cioè tante quante le coppie di nodi, $\binom n2$: Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →; si veda Tipi di rete e topologieLe reti si classificano per estensione (BAN, WLAN, LAN, MAN, WAN, WSN), per mezzo trasmissivo (aria, fibra, rame, luce visibile) e per topologia: bus (mezzo condiviso, collisioni), stella (nodo centrale, collo di bottiglia), anello (ogni nodo inoltra al successivo), maglia (collegamento diretto tra ogni coppia: $n(n-1)/2$ collegamenti). La scelta dipende da affidabilità, scalabilità, protocollo e mezzo fisico.Tipi di rete e topologie →). I nodi intermedi, gli switch (o router), devono quindi commutare: mettere in comunicazione un collegamento in ingresso con uno in uscita. Il paradigma di commutazione (switching) è la regola con cui lo si fa. Ce ne sono tre: circuito, pacchetto (con due varianti: circuito virtuale e datagramma) e, storicamente, messaggio (l'intero messaggio viene ricevuto e poi inoltrato: è il caso limite del pacchetto con un solo pacchetto).

Commutazione di circuito (circuit switching, CS)

Definizione (rete a commutazione di circuito). Si crea una connessione fisica tra due nodi prima della comunicazione: una volta stabilita, una linea (un circuito) è riservata ai due interlocutori per tutta la durata. Esempio: la vecchia rete telefonica.

Fasi: setup (la richiesta attraversa i nodi riservando risorse; torna la conferma), trasferimento (i dati viaggiano sul circuito riservato, senza intestazioni di indirizzo né code), chiusura.

Formula (tempo di consegna in CS). Con $N$ collegamenti (hop) tra trasmettitore e ricevitore, tempo di propagazione $t_p$ per collegamento, tempo di commutazione $t_s$ per nodo, messaggio di $M$ bit e bitrate $R$: $$T_{CS}=3\,N\,t_p+N\,t_s+\frac MR.$$

Perché: la richiesta di setup attraversa $N$ collegamenti ($N\,t_p$) e in ogni nodo si configura la commutazione ($N\,t_s$); la conferma torna indietro ($N\,t_p$); poi i dati partono, e dopo il tempo di trasmissione $M/R$ l'ultimo bit deve ancora propagarsi lungo $N$ collegamenti ($N\,t_p$): in totale tre attraversamenti. Non c'è store-and-forward: dopo il setup i bit scorrono come in un tubo, quindi $M/R$ compare una sola volta.

Nota sul termine di commutazione. Con $N$ collegamenti ci sono $N-1$ switch intermedi, e ciascuno è attraversato due volte dalla segnalazione (richiesta e conferma): contando così i termini $t_s$ sarebbero $2(N-1)\,t_s$, che per $N=2$ vale $2t_s=N\,t_s$. La formula del corso usa $N\,t_s$; la differenza è piccola perché $t_s$ è molto minore degli altri termini (con $N=4$ e $t_s=0{,}5$ ms sono $3$ ms contro $2$ ms su $114$ ms).

Esempio. $N=4$ collegamenti, $t_p=1$ ms, $t_s=0{,}5$ ms, $M=1$ Mbit, $R=10$ Mbit/s. Un termine alla volta: tre attraversamenti $3Nt_p=3\cdot4\cdot1=12$ ms; commutazione $Nt_s=4\cdot0{,}5=2$ ms; trasmissione $M/R=10^{6}/10^{7}=0{,}1$ s $=100$ ms (conversione in secondi prima di sommare). Totale $T_{CS}=12+2+100=114$ ms. Si veda Esercizio - Tempo di consegna in commutazione di circuito.

Pregi: prestazioni garantite, nessuna perdita di pacchetti per congestione. Difetti: risorsa dedicata anche quando non si trasmette (bassa utilizzazione), costosa, instradamento adattativo difficile, switch molto complessi, e il tempo di setup pesa sui messaggi brevi.

Commutazione di pacchetto (packet switching, PS)

Definizione (rete a commutazione di pacchetto). Il messaggio è diviso in unità più piccole, i pacchetti; i nodi intermedi sono store-and-forward: il nodo memorizza il pacchetto (lo riceve per intero) e poi decide verso quale nodo inoltrarlo. Non occorre alcuna conferma che la connessione sia stabilita.

Approccio a datagramma (datagram)

• Nessuna fase di setup a livello rete; i router non mantengono stato sulle connessioni end-to-end: non esiste il concetto di «connessione» a livello rete.
• Ogni pacchetto contiene l'indirizzo globale di destinazione (e di sorgente) e viene inoltrato in base a quello: serve un'intestazione (overhead).
• Pacchetti tra la stessa coppia sorgente-destinazione possono seguire percorsi diversi (e arrivare in disordine).
• Le risorse sono usate su base statistica: in media va bene, ma qualche volta può andare male (code, perdite).

Formula (tempo di consegna in PS a datagramma). Messaggio di $M$ bit diviso in $K$ pacchetti, ognuno con intestazione di $H$ bit (quindi pacchetti da $M/K+H$ bit), $N$ collegamenti uguali di bitrate $R$ e propagazione $t_p$, senza code né elaborazione: $$T_{PS}=N\,t_p+(N+K-1)\,\frac{M/K+H}{R}.$$

Perché: il primo pacchetto attraversa $N$ collegamenti in serie e ad ogni salto deve essere ritrasmesso per intero: $N$ tempi di trasmissione $t_{pkt}=\frac{M/K+H}{R}$. Gli altri $K-1$ pacchetti lo seguono a distanza di un tempo di trasmissione l'uno dall'altro (pipeline: mentre un pacchetto è sul secondo collegamento, il successivo è già sul primo). L'ultimo arriva quindi dopo $N\,t_{pkt}+(K-1)\,t_{pkt}$, e a tutto questo si aggiunge la propagazione $N\,t_p$.

Il numero di pacchetti $K$ ha un effetto contrastante: più pacchetti significa pacchetti piccoli e quindi meno tempo perso ad aspettare che un pacchetto sia ricevuto per intero prima di inoltrarlo, ma più intestazioni ($K\,H$ bit in più).

Formula (numero ottimo di pacchetti). Sviluppando, $(N+K-1)(M/K+H)=M+(N-1)\frac MK+(N-1)H+KH$; si deriva rispetto a $K$ e si pone uguale a zero: $-(N-1)\frac M{K^2}+H=0$, da cui $$K_{ott}=\sqrt{\frac{(N-1)\,M}{H}}.$$

Passo per passo. Si moltiplica ogni termine della prima parentesi per ogni termine della seconda: $(N-1+K)(\frac MK+H)=(N-1)\frac MK+(N-1)H+K\frac MK+KH$, e $K\cdot\frac MK=M$. Dei quattro addendi, $M$ e $(N-1)H$ non dipendono da $K$ e spariscono con la derivata; restano $(N-1)\frac MK$ (decresce con $K$: pacchetti più piccoli, meno attesa a ogni salto) e $KH$ (cresce con $K$: più intestazioni). Quindi, ricordando che $\frac{d}{dK}K^{-1}=-K^{-2}$ (Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →), $$\frac{d}{dK}\left[(N-1)\frac MK+KH\right]=-\frac{(N-1)M}{K^2}+H=0\ \Rightarrow\ K^2=\frac{(N-1)M}{H}.$$ È un minimo (condizione di Fermat più segno della derivata seconda, $\frac{2(N-1)M}{K^3}>0$: 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 →). Nell'ottimo i due addendi sono uguali, $(N-1)\frac M{K}=KH$: il costo dell'attesa e quello delle intestazioni si bilanciano. Poiché $K$ è un intero si provano i due interi vicini e si sceglie il minore.

Esempio. Gli stessi $N=4$, $t_p=1$ ms, $M=1$ Mbit, $R=10$ Mbit/s, con intestazione $H=400$ bit: $K_{ott}=\sqrt{3\cdot10^{6}/400}=86{,}6$. Con $K=87$: pacchetto di $M/K+H=11\,494+400=11\,894$ bit, tempo di trasmissione $11\,894/10^{7}=1{,}1894$ ms, numero di tempi $N+K-1=4+87-1=90$, quindi $T_{PS}=4+90\cdot1{,}1894=111{,}05$ ms. Provando i valori interi vicini: $K=87$ dà $111{,}05$ ms; $K=1$ dà $404$ ms; $K=1000$ dà $144$ ms; $K=100$ dà $111{,}12$ ms. Il minimo è piatto vicino all'ottimo. Notare che qui il PS ($111{,}05$ ms) batte il CS ($114$ ms) perché il CS paga il setup. Si veda Esercizio - Commutazione di pacchetto e numero ottimo di pacchetti.

Se i collegamenti hanno bitrate diversi, la formula non vale più: il pacchetto va seguito collegamento per collegamento e si deve tenere conto delle code (Esercizio - Due pacchetti da R1 ad A con collegamenti 128, 256 e 512 kbps); per le diverse velocità si veda anche Esercizio - Frammentazione di un pacchetto su tre collegamenti.

Approccio a circuito virtuale (virtual circuit, VC)

Una via di mezzo tra circuito e datagramma:

• come nel pacchetto, il messaggio è diviso in piccole unità (in ATM si chiamano celle);
• come nel circuito, la comunicazione richiede tre fasi: instaurazione, trasferimento dati, chiusura; è una connessione logica dedicata, senza risorse dedicate;
• l'indirizzo globale serve solo nella fase di instaurazione, non per ogni pacchetto;
• ogni cella porta un identificatore locale (VC identifier), corto, che cambia a ogni salto;
• tutti i pacchetti seguono lo stesso percorso, in ordine.

Confronto circuito virtuale contro datagramma

Confronto circuito contro pacchetto

Esempio (perché il pacchetto usa meglio i collegamenti). Un collegamento da $1$ Mbit/s serve utenti che quando trasmettono usano $100$ kbit/s, ma sono attivi solo il $10\,\%$ del tempo. Con il circuito si possono ammettere al più $1000/100=10$ utenti (la capacità è riservata anche quando tacciono). Con il pacchetto se ne possono collegare per esempio $35$. Se gli utenti sono indipendenti (Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →) e ciascuno è attivo con probabilità $p=0{,}1$, il numero di utenti attivi è una variabile binomiale di parametri $35$ e $0{,}1$ (Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →), con media $35\cdot0{,}1=3{,}5$. Il collegamento si congestiona solo se più di $10$ sono attivi insieme (e quindi si formano code): $P=\sum_{k=11}^{35}\binom{35}{k}0{,}1^k0{,}9^{35-k}=4{,}2\cdot10^{-4}$, trascurabile. Il fattore $\binom{35}{k}$ conta i modi di scegliere quali $k$ utenti sono attivi. È il vantaggio statistico del pacchetto con traffico a raffica, motivo storico della sua adozione (Storia e struttura di InternetInternet nasce da ARPANET (1969), una rete a commutazione di pacchetto finanziata dal Dipartimento della Difesa USA. Con TCP/IP (1972-77) i controlli d'errore passano dai nodi della rete ai calcolatori agli estremi (end host): è questo che la rende scalabile. DNS (1983), WWW (1989), apertura commerciale (1995). Oggi è una rete di reti: ISP locali, regionali e nazionali, collegati tra loro direttamente (peering) o tramite punti di interscambio (NAP/IXP, per esempio il MIX di Milano); IANA coordina indirizzi e DNS root, IETF/IRTF/IAB/ISOC definiscono standard e ricerca.Storia e struttura di Internet →).

I dispositivi che fanno commutazione sono descritti in Elementi di rete - hub, switch e routerI dispositivi che interconnettono le reti si distinguono per il livello della pila che arrivano a leggere. Hub (livello 1): ripetitore, rigenera il segnale e lo manda su tutte le porte, tutte le stazioni condividono la capacità. Bridge e switch (livello 2): leggono l'indirizzo MAC e inoltrano solo verso la porta giusta, imparando la tabella (FDB) dagli indirizzi sorgente. Router (livello 3): leggono l'indirizzo IP e collegano reti indipendenti (internetwork). Switch e bridge isolano il traffico e sono plug and play; il router fa instradamento ottimo ma va configurato.Elementi di rete - hub, switch e router →. Per vedere cosa succede quando più pacchetti arrivano insieme a un router si vedano gli esercizi con code, per esempio Esercizio - Quattro pacchetti da A verso E e D in una rete store-and-forward.