FormularioInternet: definizioni, teoremi e formule delle note, in ordine di capitolo

In questa pagina 12

1. Introduzione

Storia e struttura di Internet

Definizione (internetworking). Interconnessione di reti eterogenee tramite dispositivi (gateway, oggi router) che instradano pacchetti con un formato comune (IP). Ogni rete interna può usare una propria tecnologia di collegamento.

Esempio. Un portatile collegato in Wi-Fi a casa (rete radio) apre una pagina web ospitata in un data center collegato in fibra: i pacchetti IP attraversano tecnologie diverse, e ognuna incapsula lo stesso pacchetto in un proprio frame (Livello di collegamento e framing).

Definizione (ISP). Un Internet Service Provider è un'azienda di telecomunicazioni che interconnette altre reti (più piccole) e ne dà accesso a Internet.

Definizione (NAP / IXP). Un Network Access Point (o Internet Exchange Point) è un'istituzione privata che fornisce un luogo in cui più ISP si interconnettono. Lo scambio di traffico diretto tra due reti si chiama peering; l'alternativa, in cui un ISP paga un altro per raggiungere il resto di Internet, si chiama transito (transit).

Esempio. Il MIX (Milan Internet eXchange) è il più grande NAP italiano e tra i primi in Europa: ISP, operatori e fornitori di contenuti vi collegano le proprie dorsali per scambiare traffico IP (peering) in modo efficiente e con costi vantaggiosi rispetto al transito. Il MIX non è un ISP: non fornisce accesso a utenti, non pubblica contenuti né vende spazio web.

Modello ISO-OSI e pila TCP-IP

Definizione (protocollo). Un protocollo è una serie di passi, che coinvolge due o più parti, progettata per svolgere un compito. Deve essere noto a tutti i nodi e accettato da tutti, non ambiguo (nessun margine di fraintendimento) e completo (c'è un'azione prevista per ogni situazione).

Proprietà (indirizzi MAC e IP, da non confondere). MAC: 48 bit, identifica il dispositivo (la scheda) sul collegamento locale e non è instradabile. IP: identifica la connessione ed è usato per l'instradamento; la sua validità si estende su più salti. Un pacchetto di livello rete può viaggiare per molte reti; un frame di livello collegamento resta locale. Esempio dalle slide: IP 131.175.21.1, MAC A3:34:45:11:92:F1.

Definizione (PDU, SDU, PCI). La PDU (Protocol Data Unit) è l'unità di dati scambiata tra due entità dello stesso livello. La PDU del livello $N+1$ diventa SDU (Service Data Unit) per il livello $N$ sottostante. Il livello $N$ non la inoltra semplicemente: aggiunge la propria informazione di controllo, la PCI (Protocol Control Information, l'intestazione, a volte anche una coda), e il risultato è la nuova PDU del livello $N$ : $\text{PDU}_N=\text{PCI}_N+\text{SDU}_N,\qquad \text{SDU}_N=\text{PDU}_{N+1}.$

Esempio. Il livello trasporto riceve dall'applicazione un messaggio da $1000$ B e aggiunge $20$ B di intestazione TCP: PDU di trasporto $=1020$ B. Il livello rete aggiunge $20$ B di intestazione IP: $1040$ B. Il collegamento aggiunge $18$ B di intestazione e coda Ethernet: $1058$ B. Il fisico invia $1058\cdot8=8464$ bit (un byte sono 8 bit). Il rapporto utile è $1000/1058\approx94{,}5\,\%$ (overhead $58/1000=5{,}8\,\%$ ). I $18$ B di Ethernet sono $14$ B di intestazione (MAC di destinazione $6$ , MAC di sorgente $6$ , tipo $2$ ) più $4$ B di coda (controllo di errore, FCS); il preambolo, che serve solo alla sincronizzazione del ricevitore, non è contato. In generale, con un carico utile di $L$ byte e un'intestazione totale di $h=58$ byte, la frazione utile è $\eta(L)=L/(L+h)$ : è bassa per messaggi piccoli (per $L=100$ vale $100/158=63{,}3\,\%$ , per $L=10$ vale $14{,}7\,\%$ ) e tende a 1 per messaggi grandi, perché l'intestazione ha dimensione fissa. Per questo i dati si inviano in pezzi grandi quanto l'MTU consente (Datagramma IP e frammentazione).

Grafico interattivo: Frazione utile L/(L+58) al variare del carico utile L

Definizione (incapsulamento). Al mittente, ogni livello impacchetta i dati del livello superiore insieme alla propria PCI (incapsulamento, encapsulation), scendendo lungo la pila. Al destinatario, ogni livello separa i dati del livello superiore dalla propria PCI e li passa su (decapsulamento, decapsulation).

2. Prestazioni e commutazione

Analisi delle prestazioni di rete

Definizione (throughput). Il throughput $S$ [bit/s, pacchetti/s, pacchetti/slot] è il ritmo medio con cui le unità di informazione (PDU) dell'utente sono effettivamente consegnate con successo all'entità pari di destinazione. Dipende dall'intervallo di tempo su cui si calcola. Vale sempre $S\le R_0$ .

Esempio. Un protocollo sopra il livello fisico offre $1000$ bit/s; se rivela errori e chiede di ritrasmettere $10$ bit ogni $1000$ , il throughput scende a $990$ bit/s.

Definizione (goodput). Il goodput è il throughput al livello applicazione: conta solo i bit utili consegnati all'applicazione, senza le intestazioni aggiunte dai livelli inferiori e senza le ritrasmissioni. Il rapporto tra i bit aggiunti dalle intestazioni e i bit utili è l'overhead.

Esempio. L'applicazione genera un pacchetto da $1200$ B ogni $10$ ms; i livelli inferiori aggiungono $60$ B, quindi al livello fisico passano $1260$ B ogni $10$ ms. Throughput al PHY $=1260\cdot8/0{,}01=1{,}008$ Mbit/s; goodput all'applicazione $=1200\cdot8/0{,}01=960$ kbit/s; overhead $=60/1200=5\,\%$ . Si veda Esercizio - Throughput al livello fisico e goodput all'applicazione.

Proprietà (throughput di un percorso). Su un percorso con collegamenti di bitrate $R_1,\dots,R_n$ in serie, il throughput è $S=\min\{R_1,\dots,R_n\},$ cioè quello del collegamento collo di bottiglia.

Esempio. Server $R_s=2$ Mbit/s, client $R_c=1$ Mbit/s: throughput $=\min\{2,1\}=1$ Mbit/s.

Formula (ritardo end-to-end). Il tempo per consegnare un messaggio al destinatario, dall'istante in cui il primo bit esce dalla sorgente, è la somma di quattro contributi: $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}.$

Formula (ritardo di trasmissione). Per mettere sulla linea tutti i bit di un pacchetto di lunghezza $L$ (un bit dopo l'altro, dal primo all'ultimo) a bitrate $R$ : $d_{trans}=\frac{L}{R}.$

Esempio. Pacchetto di $10$ kbit su Fast Ethernet a $100$ Mbit/s: $d_{trans}=10^4/10^8=100\ \mu\text{s}$ . (La slide scrive «10 Mbps» ma il calcolo $10\,000/100\,000\,000=100\ \mu$ s corrisponde a $100$ Mbit/s; a $10$ Mbit/s verrebbe $1$ ms.) Si riduce aumentando il bitrate del collegamento.

Formula (ritardo di propagazione). Tempo che un bit impiega per andare da un estremo all'altro del mezzo, a velocità $v$ su distanza $d$ : $d_{prop}=\frac{d}{v}.$ Nel vuoto $v=c=3\cdot10^{8}$ m/s; nei mezzi cablati $v\approx2\cdot10^{8}$ m/s (rame e fibra: la luce nel mezzo va a $c/n$ , con indice di rifrazione $n\approx1{,}5$ , quindi $3\cdot10^8/1{,}5=2\cdot10^8$ m/s; si veda Mezzi di trasmissione - cavi, fibre e collegamenti radio).

Esempio. Cavo transoceanico di $6000$ km: $d_{prop}=6\cdot10^{6}/2\cdot10^{8}=30$ ms. Il ritardo di propagazione non si può ridurre («è la fisica»); è trascurabile solo nelle reti terrestri corte, ma non nei collegamenti satellitari, nei cavi lunghi e nei collegamenti ad altissima velocità.

Definizione (jitter). Il jitter $J$ [s] è la variazione del ritardo tra pacchetti di uno stesso flusso: pacchetti diversi incontrano ritardi diversi (code diverse), e l'applicazione al ricevitore, se è sensibile al tempo, ne soffre.

Definizione (RTT). Il round trip time di una connessione $A\to B$ è il tempo che passa da quando un pacchetto parte da $A$ a quando ad $A$ torna il corrispondente riscontro (ACK): $RTT=\underbrace{d_{proc}+d_{queue}+d_{trans}+d_{prop}}_{A\to B,\ \text{dati}}+\underbrace{d_{proc}+d_{queue}+d_{trans}+d_{prop}}_{B\to A,\ \text{ACK}}.$ Trascurando elaborazione e coda, con $t_F$ tempo di trasmissione del frame, $t_A$ dell'ACK e $\tau_p$ propagazione in un verso: $RTT=t_F+t_A+2\tau_p$ . Se l'ACK è piccolo ( $t_A\approx0$ ) e il frame piccolo: $RTT_{min}\approx2\tau_p$ .

Esempio. Frame di $10$ kbit su collegamento a $10$ Mbit/s ( $t_F=1$ ms), ACK di $100$ bit ( $t_A=10\ \mu$ s), propagazione $\tau_p=5$ ms: $RTT=1+0{,}01+2\cdot5=11{,}01$ ms.

Definizione (BDP). Il bandwidth-delay product è il massimo numero medio di bit che si possono trasferire in un intervallo pari al ritardo, cioè i bit che «riempiono» il collegamento: $\text{BDP [bit]}=\text{throughput massimo [bit/s]}\cdot\text{ritardo [s]}.$ Spesso si definisce con l'RTT: allora è il numero di bit che si possono trasmettere senza aver ancora ricevuto riscontro (unacknowledged). In pacchetti: $\text{BDP}/F$ (capacità del tubo, pipe capacity).

Esempio. Collegamento a $10$ Mbit/s con $\tau_p=5$ ms ( $RTT\approx2\tau_p=10$ ms $=0{,}01$ s): $BDP=10^{7}\ \text{bit/s}\cdot0{,}01\ \text{s}=10^{5}$ bit $=100$ kbit (i secondi si semplificano e resta un numero di bit); con pacchetti da $10$ kbit la capacità del tubo è $10$ pacchetti. Cioè per tenere il canale pieno bisogna spedire $10$ pacchetti prima che torni il primo ACK: è il legame con la finestra dei protocolli Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat.

Definizione (efficienza del collegamento). Se si trasmettono $B_{sent}$ bit prima di ricevere un riscontro, l'efficienza (link utilization) è la frazione di tubo riempita: $\eta=\frac{B_{sent}}{BDP}\quad(\le1).$

Esempio. Se il tubo contiene $100$ kbit e si inviano $10$ kbit e poi si aspetta l'ACK: $\eta=10/100=10\,\%$ . Si veda Esercizio - Collegamento Terra-Luna, RTT, BDP ed efficienza.

Grafico interattivo: Efficienza dello stop-and-wait η = 1/(1+2a) in funzione di a = τp/tF: vale 1 per a = 0, 1/3 per a = 1, circa 0,05 per a = 10

Tipi di rete e topologie

Formula (collegamenti in una maglia completa). Con $n$ nodi servono $\frac{n(n-1)}{2}$ collegamenti fisici (se full-duplex).

Esempio. $n=5$ : $5\cdot4/2=10$ collegamenti (come in figura); $n=10$ : $45$ ; $n=100$ : $4950$ . Il numero cresce col quadrato di $n$ : la maglia completa è robusta ma costosa e si usa solo per pochi nodi. Per confronto, con $n$ nodi: un bus usa un mezzo condiviso, una stella $n-1$ collegamenti (uno per ogni slave), un anello $n$ , una maglia $n(n-1)/2$ . Per $n=5$ : $1$ , $4$ , $5$ , $10$ .

Grafico interattivo: Numero di collegamenti in funzione del numero di nodi n: la stella cresce linearmente (n − 1), la maglia completa col quadrato (n(n − 1)/2); per n = 5 sono 4 e 10, per n = 10 sono 9 e 45

Elementi di rete - hub, switch e router

Definizione (hub). Dispositivo che opera solo a livello fisico: non ha indirizzi di collegamento (MAC). Fisicamente è una stella, ma si comporta come un ripetitore: funge da punto di collegamento e rigenera e ritempifica la sequenza di bit originale (il segnale si attenua e si deforma lungo il cavo, per questo oltre una certa lunghezza va rigenerato: Mezzi di trasmissione - cavi, fibre e collegamenti radio).

Esempio. $4$ stazioni su un hub da $100$ Mbit/s: il canale è uno solo. Se tutte trasmettono sempre, ognuna ottiene in media $100/4=25$ Mbit/s (la capacità si divide in parti uguali: è il collegamento condiviso di Analisi delle prestazioni di rete), e due coppie $A\to B$ e $C\to D$ non possono comunicare in parallelo. In più, poiché il mezzo è condiviso, valgono i limiti di efficienza dell'accesso casuale (Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA): il throughput utile è sotto $100$ Mbit/s anche con carico massimo.

Definizione (bridge). Dispositivo di collegamento dati (un hub «intelligente») che divide la rete in due sottoreti (LAN) per ridurre il traffico in ciascuna o per sicurezza, gestendo il flusso tra esse.

Definizione (switch). Dispositivo che opera nei livelli fisico e di collegamento (un bridge «più flessibile»). Ha capacità di filtraggio: controlla l'indirizzo MAC di destinazione di ogni frame e decide da quale porta farlo uscire, usando una tabella locale detta tabella di inoltro o di filtraggio (forwarding/filtering database, FDB), che associa indirizzi MAC (48 bit: Livello di collegamento e framing) a porte.

Esempio. Switch a $3$ porte con $A$ sulla porta 1, $B$ sulla 2, $C$ sulla 3 e tabella vuota.

Grafico interattivo: Capacità complessiva con k flussi simultanei tra coppie di stazioni diverse su porte a 100 Mbit/s: l'hub resta a 100 Mbit/s (mezzo condiviso), lo switch arriva a 100·k (200 Mbit/s con k = 2)

Definizione (router). Dispositivo a tre livelli (fisico, collegamento, rete): rigenera il segnale (PHY), controlla gli indirizzi fisici sorgente e destinazione del frame (DLL) e controlla gli indirizzi di rete (rete). È il «gateway» di una rete e interconnette reti indipendenti formando una internetwork (INTERNET).

Commutazione di circuito e di pacchetto

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.

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.$

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.

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.

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}.$

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}}.$

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.

Grafico interattivo: Tempo di consegna T_PS (secondi) in funzione del numero di pacchetti K, con N = 4, M = 1 Mbit, H = 400 bit, R = 10 Mbit/s, tp = 1 ms: minimo vicino a K = 87 (≈ 0,111 s); a K = 1 vale 0,404 s

3. Controllo di errore

Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat

Definizione (ARQ). (Lo stesso argomento, visto con gli strumenti della teoria dell'informazione, è in Tecniche ARQ - stop-and-wait, go-back-N e selective repeat 1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →.) Metodo di controllo degli errori che usa riscontri (ACK) per ottenere una trasmissione affidabile su un servizio inaffidabile. Se il trasmettitore non riceve l'ACK, ritrasmette il pacchetto finché non lo riceve o supera un numero massimo di ritrasmissioni.

Proprietà (requisiti di un protocollo ARQ). Accuratezza: i pacchetti devono essere consegnati al livello $N+1$ del ricevitore senza errori, una e una sola volta (niente duplicati). Efficienza: va evitata la perdita di capacità per ritrasmissioni inutili e il tempo sprecato ad aspettare pacchetti o ACK.

Definizione (utilizzazione ed efficienza). Con $E[t_T]$ valore medio del tempo per consegnare con successo un frame: $\rho=\frac{t_F}{E[t_T]},\qquad \eta=\frac{t_I}{E[t_T]}=\rho\,\frac{t_I}{t_F}=\rho\,\frac IF.$ $\rho$ è la frazione di tempo in cui il trasmettitore sta mandando frame, $\eta$ la frazione in cui sta mandando dati utili (senza intestazione).

Definizione (Stop-and-Wait). Il più semplice protocollo ARQ: il trasmettitore spedisce un frame alla volta e aspetta il riscontro prima di spedire il successivo. Semplice non vuol dire inefficace: sul collegamento punto-punto, dove la capacità del tubo è vicina a 1, è ottimo.

Esempio (ACK perso). Il trasmettitore manda il frame SN $0$ ; il ricevitore lo riceve e genera $ACK\,1$ , che si perde. Scade il timeout, il trasmettitore rimanda il frame SN $0$ . Il ricevitore si aspetta l' $1$ ma riceve lo $0$ : riconosce un duplicato, non lo consegna in alto, ma rimanda $ACK\,1$ (continua ad aspettare l' $1$ ). Il trasmettitore riceve finalmente l' $ACK\,1$ e può mandare il frame $1$ .

Formula (Stop-and-Wait). $\rho_{SW}=\frac{t_F}{E[t_T]}=\frac{t_F(1-p)}{t_F+2\tau_p+t_A}=\frac{t_F(1-p)}{t_G},\qquad \eta_{SW}=\rho_{SW}\frac IF.$

Esempio. $C=1$ Mbit/s, $F=10$ kbit ( $t_F=10$ ms), $\tau_p=25$ ms, $t_A\approx0$ : $t_G=10+50=60$ ms. Senza errori ( $p=0$ ): $\rho=10/60=16{,}7\,\%$ : il collegamento è usato un sesto del tempo. Con $p=0{,}1$ : $E[t_T]=60/0{,}9=66{,}7$ ms, $\rho=0{,}9\cdot10/60=15\,\%$ . Il collo di bottiglia è la capacità del tubo: $t_G/t_F=6$ pacchetti potrebbero stare in volo, ma se ne spedisce uno.

Definizione (Go-Back-N). Finestra di trasmissione $N$ , finestra di ricezione $M=1$ (il ricevitore può memorizzare un solo pacchetto, quindi nessuna ricezione fuori ordine). Ricevitore: scarta tutti i pacchetti fuori ordine. Trasmettitore: allo scadere di un timeout ritrasmette tutti i frame dal primo non riscontrato in poi (l'intera finestra). Era la versione antica di TCP.

Esempio ( $N=5$ , il pacchetto SN 3 si perde). Il trasmettitore spedisce SN 1-5. Il ricevitore riceve 1 e 2 e risponde $ACK(2)$ e $ACK(3)$ (cioè «aspetto il 3»); il frame 3 è perso. Il trasmettitore, ricevuti gli ACK, fa scorrere la finestra e spedisce SN 6 e 7. Ma il ricevitore aspetta il 3: scarta 4, 5, 6, 7 (ognuno provoca un $ACK(3)$ ripetuto, che le slide chiamano NACK(3)). Scade il timeout relativo a SN 3: il trasmettitore torna indietro e rimanda 3, 4, 5, 6, 7. Il ricevitore ora li riceve in ordine e risponde $ACK(4)$ ,... Totale: ritrasmessi $5=N$ pacchetti, anche se 4-7 erano arrivati correttamente (inefficiente).

Formula (Go-Back-N, finestra $N\ge t_G/t_F$ ). $\rho_{GBN}=\frac{t_F}{E[t_T]}=\frac{1-p}{1+(N-1)\,p},\qquad \eta_{GBN}=\rho_{GBN}\frac IF=\frac{I(1-p)}{F[(N-1)p+1]}.$

Esempio. $N=10$ (tubo di $10$ pacchetti), $p=0{,}1$ : $\rho_{GBN}=0{,}9/(1+9\cdot0{,}1)=0{,}9/1{,}9=47{,}4\,\%$ . Letto in tempo: $E[t_T]=t_F\,(1+\frac{0{,}1}{0{,}9}\cdot10)=2{,}11\,t_F$ , di cui $1{,}11\,t_F$ sono ritrasmissioni di finestre intere.

Definizione (Selective Repeat). Finestra di ricezione uguale a quella di trasmissione ( $M=N$ ): il ricevitore accetta e memorizza anche i pacchetti fuori ordine (fino a $M$ ) e li consegna ai livelli superiori solo quando ha una sequenza consecutiva. Per ogni frame ricevuto bene (nuovo o duplicato) manda l'ACK con l'SN del primo pacchetto mancante (ACK cumulativo). Allo scadere di un timeout ritrasmette solo il frame corrispondente. Si può tenere un timeout (RTO) per ogni pacchetto in volo, oppure uno solo per tutta la finestra, riavviato a ogni ritrasmissione.

Esempio (stesso scenario, $N=5$ ). SN 3 perso. Il ricevitore salva in coda 4, 5, 6, 7 e continua a rispondere $ACK(3)$ . Al timeout il trasmettitore rimanda solo SN 3. Appena il 3 arriva, il ricevitore ha 3-7 consecutivi: li riordina e li consegna tutti, e risponde $ACK(8)$ . Totale: ritrasmesso $1$ pacchetto.

Formula (Selective Repeat). $\rho_{SR}=\frac{t_F}{E[t_T]}=1-p,\qquad \eta_{SR}=\rho_{SR}\frac IF=\frac{I(1-p)}{F}.$

Esempio. Stesso caso ( $p=0{,}1$ ): $\rho_{SR}=90\,\%$ contro $47{,}4\,\%$ di GBN e $9\,\%$ di S&W ( $t_G/t_F=10$ : $\rho_{SW}=0{,}9/10$ ).

Formula (goodput di Selective Repeat in funzione di $x$ ). $g(x)=R_{LL}\,\eta(x)=R_{LL}\,\frac{x-o}{x}\,(1-p)=R_{LL}\,\frac{x-o}{x}\,(1-P_b)^x.$

Formula (dimensione ottima del frame). $x_{ott}=\frac{o+\sqrt{o^2-\dfrac{4o}{\ln(1-P_b)}}}{2}\ \simeq\ \frac o2+\sqrt{\frac o{P_b}}\quad(P_b\ll1).$

Esempio (le curve delle slide). Overhead $o=50$ bit.

Grafico interattivo: Efficienza di Selective Repeat η(x) = (x − o)/x · (1 − Pb)^x con overhead o = 50 bit: massimo 0,62 in x = 250 bit per Pb = 0,001 e 0,18 in x = 100 bit per Pb = 0,01

4. Accesso al canale

Protocolli di accesso multiplo - ALOHA e CSMA

Definizione (algoritmo dell'ALOHA puro).

Quando accedere: appena si ha qualcosa da trasmettere.

Mezzo occupato? Si trasmette comunque, senza guardare.

Esito: si usa uno schema ACK/NACK con timeout. Se l'ACK non arriva entro il timeout, si deduce una collisione.

Conflitto: si attende un tempo casuale (backoff) e si ritrasmette; si ripete finché non va a buon fine.

Definizione (tempo vulnerabile dell'ALOHA puro). Se la stazione B comincia a trasmettere un frame al tempo $t$ (il frame dura $t_F$ ), il frame non subisce collisione solo se nessun altro frame (nuovo o ritrasmesso) parte da $t_F$ secondi prima a $t_F$ secondi dopo il suo inizio. Il tempo vulnerabile (vulnerable time) è quindi $T_{vuln}=2\,t_F.$

Esempio. Frame da $1000$ bit su un canale a $1$ Mbit/s: $t_F=1$ ms. Se B parte a $t=10$ ms, qualsiasi altro frame che parta tra $9$ ms e $11$ ms lo distrugge: $T_{vuln}=2$ ms. Nell'esempio delle slide quattro stazioni inviano due frame ciascuna e solo due frame (quelli delle stazioni 1 e 3) sopravvivono, perché tutti gli altri si sovrappongono almeno in parte a un altro.

Grafico interattivo: Tempo vulnerabile dell'ALOHA puro con tF = 1 ms: il frame B parte a 10 ms (durata 10–11 ms); la fascia colorata, da 9 a 11 ms, è l'intervallo di partenza che distrugge B. A1 (parte a 9,3) e A2 (parte a 10,7) collidono, A3 (finisce a 9,4) e A4 (parte a 11,3) no

Definizione (algoritmo dello slotted ALOHA). Il tempo è diviso in slot di durata $t_F$ e le stazioni sono costrette a iniziare la trasmissione solo all'inizio di uno slot. Un frame generato a metà slot aspetta l'inizio del successivo (attesa media $t_F/2$ ). Per il resto l'algoritmo è quello dell'ALOHA puro (ACK, timeout, backoff casuale).

Definizione (CSMA). Carrier Sense Multiple Access: ogni stazione ascolta il mezzo prima di trasmettere (listen before talk) e trasmette solo se lo trova libero.

Definizione (tempo vulnerabile del CSMA). È il tempo di propagazione (massimo) $\tau_p$ da un estremo all'altro del mezzo: $T_{vuln}=\tau_p.$

Esempio. Bus di $2$ km con propagazione $2\cdot10^8$ m/s: $\tau_p=2000/(2\cdot10^8)=10^{-5}$ s $=10\ \mu$ s. Frame da $1000$ bit a $10$ Mbit/s: $t_F=1000/(10^{7})=10^{-4}$ s $=100\ \mu$ s. Il tempo vulnerabile è $10\ \mu$ s, cioè un decimo del frame ( $\tau_p/t_F=0{,}1$ ); per l'ALOHA puro sarebbe $2t_F=200\ \mu$ s, venti volte di più ( $200/10=20$ ). Se invece $\tau_p$ fosse paragonabile a $t_F$ (satellite, rete molto veloce), l'ascolto servirebbe a poco: la differenza tra CSMA e ALOHA sparisce (Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA).

Definizione (CSMA/CD). Carrier Sense Multiple Access with Collision Detection: al CSMA aggiunge la rilevazione delle collisioni mentre si trasmette. La stazione controlla il mezzo durante la trasmissione del frame:

se il livello di energia sul canale è coerente con la trasmissione del proprio frame, va tutto bene;

se è anormale (più alto), c'è una collisione: la trasmissione viene interrotta e si invia un breve segnale di disturbo (jamming) per avvertire tutte le altre stazioni.

Formula (durata minima del frame in CSMA/CD). Per essere sicuri che una trasmissione sia andata a buon fine bisogna che $t_F\ \ge\ 2\,\tau_p,\qquad t_F=\frac FR\ \Longrightarrow\ F\ \ge\ 2\,\tau_p\,R.$

Esempio (valori delle slide). $R=10$ Mbit/s e $\tau_p=25{,}6\ \mu$ s (si tratta del ritardo massimo, comprensivo dei ripetitori): $t_F\ge2\tau_p=2\cdot25{,}6=51{,}2\ \mu$ s, quindi $F_{min}=10\cdot10^{6}\ \text{bit/s}\cdot51{,}2\cdot10^{-6}\ \text{s}=512$ bit $=512/8=64$ B. È proprio la lunghezza minima del frame Ethernet (LAN - Ethernet e Wi-Fi). Nelle slide l'ultimo passaggio riporta $52{,}1\ \mu$ s: è un refuso, il valore che dà $64$ B è $51{,}2\ \mu$ s.

Grafico interattivo: Diagramma spazio-tempo del caso peggiore del CSMA/CD (posizione sull'asse x da A in 0 a B in 1; tempo sull'asse y in unità di τp): A parte a t = 0, B parte a t = τp, un istante prima di sentire A; la collisione arriva ad A a t = 2τp, quindi A deve ancora star trasmettendo

Definizione (CSMA/CA). Carrier Sense Multiple Access with Collision Avoidance: inventato per le reti senza fili, dove non si può rilevare una collisione durante la trasmissione (la propria trasmissione sovrasta ciò che si riceve). Non si rileva, si evita.

Esempio. Al primo tentativo $CW=15$ e $T_{slot}=9\ \mu$ s: se si estrae $b=7$ la stazione aspetta $7\cdot9=63\ \mu$ s di canale libero. Se il canale diventa occupato dopo $4$ slot liberi, il contatore resta fermo a $3$ finché la trasmissione altrui non finisce, poi riprende e a $0$ si trasmette. Chi ha estratto il contatore più basso vince la contesa: è il motivo per cui le stazioni che hanno aspettato di più (contatore congelato) tendono ad andare per prime la volta successiva.

Grafico interattivo: Finestra di contesa CW dopo n fallimenti consecutivi (nello standard 802.11): 15, 31, 63, ..., 1023 e poi resta al massimo

Introduzione alla teoria delle code

Definizione (sistema a coda). Una popolazione di clienti (nelle reti: pacchetti dati; ma anche viaggiatori in fila al check-in, persone alla posta) arriva a un sistema formato da una coda (buffer, sala d'attesa) e da una struttura di servizio con $m$ servitori. I clienti escono dopo il servizio (processo di partenza).

Definizione (stabilità). Un QS è stabile se ammette una distribuzione asintotica propria $p_x(n)$ , $n=0,1,2,\dots$ , per $x(t)$ , indipendente dallo stato iniziale $x(0)$ . Se la distribuzione asintotica è identicamente nulla o dipende dallo stato iniziale, il QS è instabile.

Teorema (legge di Little). Il numero medio di clienti $E[x]$ in una struttura che conserva il flusso è uguale al tasso di arrivo dei clienti alla struttura per il tempo medio che un cliente vi trascorre: $E[x]=\lambda\,E[s].$

Formula (distribuzione e numero medio nel sistema, M/M/1). Il numero di clienti nel sistema ha distribuzione geometrica (Distribuzione geometrica): $p_x(n)=(1-\rho)\rho^{\,n},\qquad n=0,1,2,\dots$ $E[x]=\frac\rho{1-\rho},\qquad\mathrm{Var}(x)=\frac\rho{(1-\rho)^2}.$

Grafico interattivo: Distribuzione del numero di clienti nel sistema M/M/1 con ρ = 0,8: p(n) = 0,2·0,8^n, geometrica decrescente (p(0) = 0,2 = 1 − ρ, p(1) = 0,16, p(2) = 0,128); la media è ρ/(1−ρ) = 4

Formula (coda e tempi, M/M/1). Dal numero medio nel sistema togliendo quello in servizio ( $\rho$ ): $E[q]=E[x]-\rho=\frac{\rho^2}{1-\rho}.$ Con Little: $E[s]=\frac{E[x]}\lambda=\frac{1/\mu}{1-\rho},\qquad E[w]=E[s]-\frac1\mu=\frac{\rho/\mu}{1-\rho}.$

Esempio. Il collegamento da $1$ Mbit/s con pacchetti da $1000$ bit, $\mu=1000$ pacchetti/s, e $\lambda=800$ pacchetti/s ( $\rho=0{,}8$ ), con pacchetti di lunghezza esponenziale (M/M/1):

Formula (M/G/1 con servizio costante, usata nelle slide). $E[x]=\rho+\frac{\rho^2}{2(1-\rho)},\qquad E[w]=\frac{\rho}{2\mu(1-\rho)},\qquad E[s]=\frac{E[x]}\lambda=\frac1\mu\left(1+\frac{\rho}{2(1-\rho)}\right).$ Il tempo medio di servizio si ritrova per differenza: $E[y]=E[s]-E[w]=1/\mu$ .

Esempio. Stessi dati ( $\mu=1000$ , $\lambda=800$ , $\rho=0{,}8$ ) ma pacchetti tutti da $1000$ bit (servizio costante, M/D/1): $E[w]=\dfrac{0{,}8}{2\cdot1000\cdot0{,}2}=2$ ms (contro $4$ ms della M/M/1), $E[s]=2+1=3$ ms, $E[x]=0{,}8+\dfrac{0{,}64}{0{,}4}=2{,}4$ pacchetti (Little: $800\cdot0{,}003=2{,}4$ ✓).

Grafico interattivo: Tempo medio di sistema normalizzato E[s]·μ in funzione del fattore di carico ρ: M/M/1 (1/(1−ρ)) e servizio costante (1 + ρ/(2(1−ρ))). Tutte e due divergono per ρ → 1

Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA

Definizione (metriche del protocollo ad accesso casuale).

Traffico offerto $G$ : numero medio di frame (nuovi e ritrasmessi) che arrivano in un tempo di servizio, $G=\dfrac{\lambda'}{\mu}=\lambda't_F$ .

Probabilità di successo $P_S$ : probabilità che una trasmissione abbia successo, $P_S=\dfrac{\lambda}{\lambda'}=\dfrac{\text{arrivi nuovi/s}}{\text{arrivi totali/s (nuovi + ritrasmessi)}}$ .

Throughput $S$ : numero medio di frame trasmessi con successo in un tempo di frame, $S=GP_S=\lambda t_F$ .

Formula (throughput dell'ALOHA puro). $S=G\,P_S=G\,e^{-2G}.$

Esempio. Con $G=0{,}5$ : $P_S=e^{-1}=0{,}368$ e $S=0{,}5\cdot0{,}368=0{,}184$ , il canale è sfruttato al $18{,}4\,\%$ : su un canale a $1$ Mbit/s si consegnano al massimo $184$ kbit/s utili ( $0{,}184\cdot1$ Mbit/s). Con $G=0{,}1$ (carico basso) $P_S=e^{-0{,}2}=0{,}819$ e $S=0{,}1\cdot0{,}819=0{,}082$ : quasi tutto ciò che arriva passa, ma il $18\,\%$ dei tentativi ( $1-e^{-0{,}2}=0{,}181$ ) si scontra. Con $G=2$ (carico alto) $P_S=e^{-4}=0{,}018$ e $S=2\cdot0{,}018=0{,}037$ : il canale è sommerso da collisioni.

Formula (ritardo medio dell'ALOHA puro). $E[T]=t_F+\tau_p+E[n_{retx}](t_F+2\tau_p+E[t_b])=t_F+\tau_p+(e^{2G}-1)(t_F+2\tau_p+E[t_b]).$

Esempio. $t_F=1$ ms, $\tau_p=0{,}1$ ms, $E[t_b]=5$ ms.

Formula (throughput dello slotted ALOHA). $S=G\,P_S=G\,e^{-G},\qquad\frac{dS}{dG}=e^{-G}(1-G)=0\ \Rightarrow\ G=1,\quad S_{max}=\frac1e\simeq0{,}37.$

Esempio. Gli stessi dati dell'ALOHA puro: $G=0{,}1$ dà $E[T]=1{,}5+0{,}1+0{,}105\cdot(1{,}5+0{,}2+5)=2{,}30$ ms (contro $2{,}47$ ms dell'ALOHA puro); $G=0{,}5$ dà $5{,}95$ ms (contro $11{,}75$ ); $G=1$ dà $13{,}1$ ms. A basso carico lo slotted ha un ritardo maggiore per via dell'attesa dello slot, ma poi cresce molto più lentamente: conta il numero di collisioni. Per esempio per $G=0{,}5$ : parte fissa $\frac{3t_F}{2}+\tau_p=1{,}5+0{,}1=1{,}6$ ms, ritrasmissioni $e^{0{,}5}-1=0{,}649$ , costo di ciascuna $1{,}5+0{,}2+5=6{,}7$ ms, quindi $E[T]=1{,}6+0{,}649\cdot6{,}7=5{,}95$ ms.

Grafico interattivo: Ritardo medio E[T] in funzione del carico offerto G (tF = 1 ms, τp = 0,1 ms, backoff medio 5 ms): a G piccolo lo slotted ha più ritardo (1,6 ms contro 1,1 ms per G → 0), ma cresce molto più piano (13,1 ms contro 40,7 ms in G = 1)

Formula (throughput del CSMA non persistente). Il throughput è il tempo utile medio per ciclo diviso la durata media del ciclo $m_B+m_I$ : $S=\frac{m_U}{m_B+m_I}=\frac{t_Fe^{-aG}}{t_F\left(1+2a-\frac{1-e^{-aG}}G\right)+\frac{t_F}G}=\frac{G\,e^{-aG}}{G(1+2a)+e^{-aG}}.$

Esempio. $a=0{,}1$ , $G=1$ : $1+2a=1{,}2$ e $e^{-aG}=e^{-0{,}1}=0{,}9048$ , quindi $S=\dfrac{e^{-0{,}1}}{1\cdot1{,}2+e^{-0{,}1}}=\dfrac{0{,}9048}{2{,}1048}=0{,}430$ . Con $a=0{,}01$ : $S=0{,}493$ ; con $a=1$ : $S=0{,}109$ .

Grafico interattivo: Throughput normalizzato del CSMA non persistente per diversi ritardi di propagazione normalizzati a = τp/tF, confrontato con lo slotted ALOHA (asse G in scala logaritmica)

Formula (ritardo medio del CSMA non persistente). $E[T]=E[W]+t_F+\tau_p+\left(\frac GS-1\right)\big(E[W]+t_F+2\tau_p+E[t_b]\big).$

Esempio. $t_F=1$ ms, $\tau_p=0{,}1$ ms ( $a=0{,}1$ ), $E[t_b]=5$ ms, $G=1$ . Passo per passo:

Definizione (TDMA). L'asse del tempo è diviso in slot di uguale durata, preassegnati agli $N_u$ utenti; ogni utente può trasmettere liberamente nel suo slot, in cui dispone dell'intero bitrate $R$ . L'assegnazione segue uno schema periodico (la trama TDMA: $1,2,\dots,N_u$ ). Il tempo di trasmissione del pacchetto coincide con la durata dello slot: $t_F=F/R$ .

Formula (ritardo medio del TDMA). $E[T]=\frac{N_ut_F}2+\frac{SN_ut_F}{2(1-S)}+t_F+\tau_p=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right).$

Esempio. $N_u=10$ utenti, $t_F=1$ ms, $a\approx0$ , carico $S=0{,}5$ : attesa dello slot $N_u/2=5$ , attesa in coda $\dfrac{10\cdot0{,}5}{2\cdot(1-0{,}5)}=\dfrac{5}{1}=5$ , trasmissione $1$ , quindi $E[T]/t_F=5+5+1=11$ , cioè $E[T]=11$ ms. A basso carico ( $S=0{,}1$ ) $E[T]/t_F=5+\dfrac{10\cdot0{,}1}{2\cdot0{,}9}+1=5+0{,}56+1=6{,}56$ ; con $S=0{,}9$ la coda pesa $\dfrac{10\cdot0{,}9}{2\cdot0{,}1}=45$ e si arriva a $5+45+1=51$ .

Definizione (FDMA). La banda disponibile è divisa in sottobande disgiunte, assegnate ciascuna a un utente. Il sistema ha un bitrate totale $R$ , diviso in parti uguali tra i $N_u$ utenti: ognuno ha $R/N_u$ bit/s. Il tasso di servizio di un utente è $\mu=\frac{R/N_u}{F}=\frac R{FN_u}\quad[\text{pacchetti/s}].$

Formula (ritardo medio dell'FDMA). $E[T]=N_ut_F+\frac{N_ut_FS}{2(1-S)}+\tau_p=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right).$

5. Framing e indirizzi di collegamento

Livello di collegamento e framing

Definizione (compito del DLL). Consegnare un frame da un nodo a un nodo fisicamente adiacente attraverso un collegamento, possibilmente in modo affidabile. Frame diversi possono essere trasportati da protocolli di collegamento diversi su collegamenti diversi.

Esempio (analogia del viaggio Padova - New York). Auto da Padova all'aeroporto di Venezia, aereo fino a New York JFK, metropolitana fino al centro. Il turista è il frame, ogni tratto è un collegamento, il mezzo di trasporto è il protocollo di collegamento, l'agenzia di viaggio è l'algoritmo di instradamento (livello rete).

Definizione (indirizzo MAC). Indirizzo del livello di collegamento di 48 bit ( $2^{48}\approx2{,}8\cdot10^{14}$ indirizzi possibili, circa $280$ mila miliardi), scritto come $12$ cifre esadecimali separate da due punti, per esempio A3:34:45:11:92:F1.

Esempio. Su un PC Linux ifconfig mostra per l'interfaccia eth0 l'indirizzo hardware 28:d2:44:eb:bd:98 e per wlan0 38:b1:db:7c:78:c7: ogni scheda ha il suo. In 28:d2:... la seconda cifra è 8 (pari): indirizzo unicast.

Protocollo ARP

Definizione (ARP). Protocollo ausiliario di livello rete che, dato l'indirizzo IP di un nodo della stessa rete locale, ne ricava l'indirizzo MAC. Usa la capacità di diffusione (broadcast) del collegamento sottostante.

Definizione (proxy ARP). Funzione realizzata nel router che interconnette le sottoreti: intercetta tutte le richieste ARP per indirizzi IP di altre sottoreti e risponde con il proprio MAC; poi inoltra alla sottorete giusta tutti i frame che portano il suo MAC.

6. LAN

LAN - Ethernet e Wi-Fi

Definizione (LAN). Una Local Area Network è una rete progettata per un'area geografica limitata. La maggior parte delle LAN è collegata a una WAN, cioè a Internet (Tipi di rete e topologie).

Formula (dimensione minima del frame). Un frame di dimensione $S$ con bitrate $C$ dura $T_{fr}=S/C$ . Per rilevare la collisione deve essere $T_{fr}\ge2T_p$ , cioè $S\ \ge\ C\cdot2T_p.$

Esempio (valori storici). Velocità del segnale sul cavo $2\cdot10^{8}$ m/s (Mezzi di trasmissione - cavi, fibre e collegamenti radio); lunghezza massima del cavo $d=2500$ m (imposta dai progettisti); $C=10$ Mbit/s (la velocità standard di allora). Allora $T_p=d/v=2500/(2\cdot10^8)=12{,}5\ \mu$ s; il vincolo è $T_{fr}\ge2T_p=25\ \mu$ s e $S_{min}=C\cdot T_{fr}=10^{7}\ \text{bit/s}\cdot25\cdot10^{-6}\ \text{s}=250\ \text{bit}\approx31{,}25\ \text{B}\quad(250/8).$ Considerando i ritardi aggiuntivi dei ripetitori e un certo margine di sicurezza, il minimo è fissato a 64 byte ( $512$ bit, cioè $51{,}2\ \mu$ s a $10$ Mbit/s). Quando il campo dati è più corto si aggiunge il PAD.

Definizione (IEEE 802.11). Specifiche IEEE per le reti locali senza fili (in alcuni paesi il pubblico le chiama Wi-Fi, abbreviazione di Wireless Fidelity).

7. Livello di rete

Livello di rete e indirizzamento IP

Definizione (indirizzo IPv4). È un numero di 32 bit che identifica la connessione di un dispositivo a Internet (non il dispositivo: un router con tre interfacce ha tre indirizzi). È univoco (un indirizzo individua una sola connessione) e universale (lo schema è accettato da qualunque host). Si scrive in notazione decimale puntata (dotted-decimal): i 32 bit sono divisi in 4 byte e ogni byte è scritto come numero tra 0 e 255.

Esempio. $10000011\ 10101111\ 00010101\ 00000001$ è $131.175.21.1$ . Ogni byte si converte in decimale: $10000011_2=128+2+1=131$ , $10101111_2=128+32+8+4+2+1=175$ , $00010101_2=16+4+1=21$ , $00000001_2=1$ .

Definizione (prefisso e suffisso). I primi $n$ bit formano il prefisso, detto NetID (identifica la rete); i restanti $32-n$ bit formano il suffisso, detto HostID (identifica l'host dentro la rete). Nodi nella stessa rete hanno lo stesso NetID e HostID diversi.

Esempio. Con $n=16$ , in $131.175.12.8$ il NetID è $131.175$ e l'HostID è $12.8$ .

Definizione (indirizzo di rete). Si ottiene mettendo a 0 tutti i bit dell'HostID. Identifica la rete intera e si usa solo nelle tabelle di instradamento: non si assegna a nessun host.

Esempio. $131.175.12.8$ (classe B): indirizzo di rete $131.175.0.0$ . Per $193.17.31.37$ (classe C): $193.17.31.0$ .

Definizione (broadcast diretto, direct broadcast address). Si ottiene mettendo a 1 tutti i bit dell'HostID. Un pacchetto con questo destinatario raggiunge tutti i nodi della rete con quel NetID. Può essere generato da fuori della rete, ma non può uscirne.

Esempio. $131.175.12.8$ con $n=16$ : broadcast $131.175.255.255$ . Per $193.17.31.37$ : $193.17.31.255$ .

Formula (blocco CIDR). Dato $a.b.c.d/n$ : $N=2^{32-n},\qquad \text{indirizzo di rete}=\text{primi }n\text{ bit invariati e gli altri }32-n\text{ a }0,\qquad \text{broadcast}=\text{primi }n\text{ bit invariati e gli altri a }1.$ Gli host utilizzabili sono $N-2$ (si tolgono rete e broadcast).

Esempio. $167.199.170.82/27$ : $N=2^5=32$ indirizzi ( $30$ host). Il byte significativo è l'ultimo, $82=01010010_2$ ; con 27 bit di prefisso si tengono i primi 3 bit di questo byte ( $010$ ) e gli altri 5 si azzerano: $01000000_2=64$ . Rete $167.199.170.64/27$ ; broadcast: $01011111_2=95$ , cioè $167.199.170.95$ .

Definizione (netmask). È un numero di 32 bit in cui i primi $n$ bit (quelli del NetID) valgono 1 e i restanti $32-n$ (quelli dell'HostID) valgono 0. Per $n=27$ : $11111111.11111111.11111111.11100000=255.255.255.224$ .

Formula (operazioni con la maschera). $N=\text{NOT}(\text{maschera})+1,\qquad \text{rete}=\text{indirizzo}\ \text{AND}\ \text{maschera},\qquad \text{broadcast}=\text{indirizzo}\ \text{OR}\ \text{NOT}(\text{maschera}).$

Esempio. $167.199.170.82$ con maschera $255.255.255.224$ . Sull'ultimo byte: $82=01010010$ , maschera $11100000$ . AND: $01000000=64$ , quindi rete $167.199.170.64$ . NOT(maschera) $=00011111=31$ , quindi $N=31+1=32$ ; OR: $01010010\ \text{OR}\ 00011111=01011111=95$ , broadcast $167.199.170.95$ . È lo stesso risultato del metodo precedente.

Proprietà (un indirizzo appartiene a una rete se...). Un indirizzo $X$ appartiene alla rete di indirizzo $R$ e maschera $M$ se e solo se $X\ \text{AND}\ M=R$ .

Esempio. Rete $205.16.32.0$ con maschera $255.255.248.0$ ( $/21$ ). Il byte interessante è il terzo, con maschera $248=11111000$ . Per $205.16.42.56$ : $42=00101010$ , AND $11111000=00101000=40$ , quindi $205.16.40.0\neq205.16.32.0$ : non appartiene. Per $205.16.37.44$ : $37=00100101$ , AND $11111000=00100000=32$ , quindi $205.16.32.0$ : appartiene. Il blocco $205.16.32.0/21$ ha $2^{11}=2048$ indirizzi e va da $205.16.32.0$ a $205.16.39.255$ .

Subnetting e supernetting

Definizione (subnetting). Un'organizzazione (o un ISP) a cui è stato assegnato un intervallo di indirizzi può dividerlo in più sottointervalli e assegnare ciascuno a una sottorete (subnet). Ogni sottorete si può dividere a sua volta in sotto-sottoreti. Si crea così un livello di gerarchia in più: NetID (rete), SubnetID (sottorete), HostID (host).

Formula (conteggio delle sottoreti). Si parte da una rete con prefisso $n$ (HostID di $32-n$ bit). Si prendono $s$ bit dall'HostID per il SubnetID: il nuovo prefisso è $n'=n+s$ , ci sono $2^{s}$ sottoreti e ogni sottorete ha $2^{32-n'}$ indirizzi, cioè $2^{32-n'}-2$ host utilizzabili.

Esempio. Dalla rete $147.162.0.0/16$ (UniPD, classe B) con maschera $255.255.255.0$ ( $n'=24$ ): $s=24-16=8$ bit di SubnetID, quindi al più $2^8=256$ sottoreti, ciascuna con $2^{32-24}-2=254$ host. Senza subnetting si avrebbe un'unica rete con $2^{16}-2=65\,534$ host.

Formula (progetto di una sottorete). $M=2^{\lceil\log_2(H+2)\rceil},\quad n=32-\log_2M,\quad \text{broadcast}=\text{rete}+M-1.$

Esempio. Servono 100 host: $H+2=102$ ; $2^6=64<102\le2^7=128$ , quindi $\lceil\log_2102\rceil=7$ e $M=128$ ; $n=32-7=25$ ; il broadcast è la rete $+127$ (la rete è il primo indirizzo, quindi l'ultimo dista $M-1$ ).

Definizione (supernetting). È il duale del subnetting: si uniscono più blocchi piccoli e contigui in un unico blocco più grande. Si accorcia il prefisso (più bit di HostID, meno bit di NetID). È il caso della classe C: le reti da 254 host sono piccole, quindi se ne prendono alcune per formare una rete più grande. Nelle tabelle di instradamento si parla di aggregazione (route aggregation).

Proprietà (condizioni per aggregare). $2^j$ blocchi con prefisso $n$ si possono sostituire con un unico blocco di prefisso $n-j$ se e solo se (a) sono contigui, (b) sono esattamente $2^j$ (una potenza di 2), (c) il primo indirizzo è un multiplo della dimensione del blocco aggregato ( $2^{32-(n-j)}$ ).

Esempio. I quattro blocchi $193.23.136.0/24$ , $193.23.137.0/24$ , $193.23.138.0/24$ , $193.23.139.0/24$ sono contigui ( $j=2$ ) e il terzo byte del primo, $136$ , è multiplo di $4$ : si uniscono in $193.23.136.0/22$ (maschera $255.255.252.0$ , $2^{10}=1024$ indirizzi). Quattro blocchi sono $2^j$ con $j=\log_24=2$ , quindi il prefisso scende di 2: $24-2=22$ . In binario il terzo byte è $10001000$ : i due bit meno significativi ( $00$ ) diventano parte dell'HostID (due bit assumono $4$ combinazioni: $00,01,10,11$ ), quindi il terzo byte va da $10001000=136$ a $10001011=139$ , cioè proprio i quattro blocchi. Si può verificare con la maschera (AND bit a bit): ciascuno dei quattro terzi byte $136,137,138,139$ ha la forma $100010xx$ e dopo l'AND diventa $136$ , quindi tutti e quattro cadono nella stessa rete $193.23.136.0/22$ .

Datagramma IP e frammentazione

Formula (checksum IP). Si sommano le parole da 16 bit dell'intestazione (con checksum $=0$ ); si riporta l'eventuale riporto oltre i 16 bit sommandolo al risultato (complemento a uno); il checksum è il complemento a 1 (NOT bit a bit) della somma. Alla ricezione la somma di tutte le parole (checksum compreso) deve dare $\texttt{FFFF}$ .

Esempio. Intestazione di 20 byte (in esadecimale): $4500\ 0073\ 0000\ 4000\ 4011\ \mathbf{0000}\ C0A8\ 0001\ C0A8\ 00C7$ . Le parole sono scritte in esadecimale (una parola da 16 bit sono 4 cifre). Somme parziali: $4500+0073=4573$ ; $+0000=4573$ ; $+4000=8573$ ; $+4011=\texttt{C584}$ ; $+0000=\texttt{C584}$ ; $+\texttt{C0A8}=\texttt{1862C}$ (qui la somma supera i 16 bit; si fa cifra per cifra da destra: $\texttt{4}+\texttt{8}=12=\texttt{C}$ ; $\texttt{8}+\texttt{A}=18=\texttt{12}_{16}$ , si scrive 2 e si riporta 1; $\texttt{5}+\texttt{0}+1=6$ ; $\texttt{C}+\texttt{C}=24=\texttt{18}_{16}$ , si scrive 8 e si riporta 1 nella quinta cifra: risultato $\texttt{1862C}$ ); $+0001=\texttt{1862D}$ ; $+\texttt{C0A8}=\texttt{246D5}$ ; $+\texttt{00C7}=\texttt{2479C}$ . Il riporto oltre i 16 bit (il "2" iniziale) si somma al resto: $\texttt{479C}+2=\texttt{479E}$ (aritmetica del complemento a uno: il riporto che esce a sinistra rientra a destra, Aritmetica binaria). Complemento: $\texttt{FFFF}-\texttt{479E}=\texttt{B861}$ , che equivale a negare ciascuno dei 16 bit ( $\texttt{FFFF}$ ha tutti i bit a 1, quindi sottrarre da esso scambia 0 e 1). Controllo: sommando $479E+B861=\texttt{FFFF}$ ✓: ecco perché il ricevente, sommando tutte le parole checksum compreso, deve trovare $\texttt{FFFF}$ . Lettura dei campi: $45$ = versione 4, HLen 5; $0073=115$ byte di lunghezza totale; $40\,11$ : TTL $=\texttt{40}=64$ , Protocol $=\texttt{11}=17$ (UDP).

Definizione (MTU). La Maximum Transfer Unit è la dimensione massima del payload di un frame del collegamento, e quindi la dimensione massima di un datagramma IP (intestazione compresa) che quel collegamento può trasportare. Ethernet: $1500$ byte (le WAN possono avere MTU più piccole).

Formula (frammentazione). Datagramma con Total Length $L$ , intestazione $h$ (di solito 20), collegamento con MTU $m$ . Payload da trasportare $P=L-h$ . Payload massimo per frammento: $p_{\max}=8\cdot\left\lfloor\dfrac{m-h}{8}\right\rfloor$ . Numero di frammenti: $\left\lceil P/p_{\max}\right\rceil$ . L'offset dell' $i$ -esimo frammento (da 0) è $\dfrac{i\cdot p_{\max}}{8}$ (se i frammenti precedenti sono tutti da $p_{\max}$ ).

Esempio. $L=4000$ (intestazione 20 + payload 3980), $m=1500$ . $m-h=1500-20=1480$ byte di dati per frammento; $1480/8=185$ esatto, quindi $1480$ è già multiplo di 8 e $p_{\max}=1480$ . Frammenti: $3980/1480=2{,}69$ , per eccesso $\lceil3980/1480\rceil=3$ : due frammenti pieni da $1480$ e uno con quello che resta, $3980-2\cdot1480=3980-2960=1020$ byte di payload. Total Length del frammento $=$ payload $+$ 20; l'offset di ciascuno è il numero di byte già inviati diviso 8 ( $0$ , $1480/8=185$ , $2960/8=370$ ). MF vale 1 nei primi due e 0 nell'ultimo.

Grafico interattivo: Payload di 3980 byte diviso in tre frammenti (posizione in byte)

Protocollo ICMP

Formula (checksum ICMP). Come per IP: complemento a uno della somma in complemento a uno delle parole da 16 bit del messaggio, con il campo checksum posto a 0 durante il calcolo.

Esempio. Echo request di tipo 8, codice 0, identifier $\texttt{1234}$ , sequence number $\texttt{0001}$ , dati "ab" ( $\texttt{6162}$ ). Parole: $\texttt{0800},\ \texttt{0000},\ \texttt{1234},\ \texttt{0001},\ \texttt{6162}$ . Somma passo per passo (in esadecimale): $\texttt{0800}+\texttt{0000}=\texttt{0800}$ ; $+\texttt{1234}=\texttt{1A34}$ (infatti $8+2=\texttt{A}$ nella terza cifra); $+\texttt{0001}=\texttt{1A35}$ ; $+\texttt{6162}=\texttt{7B97}$ (cifra per cifra da destra: $5+2=7$ , $3+6=9$ , $\texttt{A}+1=\texttt{B}$ , $1+6=7$ ). Nessun riporto oltre i 16 bit, quindi non c'è nulla da riportare. Checksum $=\overline{\texttt{7B97}}=\texttt{FFFF}-\texttt{7B97}=\texttt{8468}$ (si nega ogni bit; cifra per cifra $\texttt{F}-\texttt{7}=\texttt{8}$ , $\texttt{F}-\texttt{B}=\texttt{4}$ , $\texttt{F}-\texttt{9}=\texttt{6}$ , $\texttt{F}-\texttt{7}=\texttt{8}$ ). Il metodo è lo stesso del checksum IP, con il complemento a uno spiegato in Datagramma IP e frammentazione. Alla ricezione, sommando anche il checksum: $\texttt{7B97}+\texttt{8468}=\texttt{FFFF}$ , quindi il messaggio è integro.

NAT e indirizzi privati

Definizione (intranet). Rete privata che usa la pila di protocolli TCP/IP (server web, server di posta, router, ...). Può essere connessa a Internet oppure no, e non è mai attraversata da traffico "esterno". Dentro l'intranet ci sono Internal Gateway (IG) che collegano le sottoreti; un External Gateway (EG) la collega a Internet. Dentro l'intranet si usano indirizzi privati, fuori indirizzi pubblici.

Definizione (indirizzi privati). Tre blocchi riservati, mai instradati nella rete pubblica:

Esempio. $172.31.255.255$ è l'ultimo indirizzo del blocco B privato: $172.16.0.0$ con $/12$ copre i secondi byte da $16$ a $31$ ( $16=00010000_2$ , i 4 bit di prefisso nel secondo byte sono $0001$ , quindi il secondo byte va da $00010000=16$ a $00011111=31$ ). Controllo sul conteggio: i secondi byte possibili sono $31-16+1=16=2^4$ e per ciascuno restano i $16$ bit degli ultimi due byte, cioè $16\cdot65\,536=2^4\cdot2^{16}=2^{20}=1\,048\,576$ indirizzi, come dice la tabella.

8. Instradamento

Algoritmi di instradamento - link state e distance vector

Definizione (instradamento). L'insieme delle procedure che permettono di determinare un percorso da un punto a un altro. È possibile solo se ogni router ha una tabella di inoltro per mandare il datagramma al nodo successivo (next hop) sulla strada verso la destinazione.

Definizione (percorso di costo minimo). Dato un grafo connesso $G=(V,E)$ e una funzione di costo additiva (il costo di un cammino è la somma dei costi degli archi), il percorso di costo minimo (least-cost route, LCR) da una sorgente $s$ a un nodo $v$ è la sequenza di nodi connessi, da $s$ a $v$ , con somma dei costi minima fra tutti i cammini possibili.

Definizione (stato di un nodo in Dijkstra). Ogni nodo $\ell$ ha uno stato $(d_\ell,\ p\text{ oppure }t)$ :

$d_\ell$ è la stima corrente della distanza da $s$ (il costo accumulato);

l'etichetta è permanente ( $p$ ) se $d_\ell$ è già la distanza minima da $s$ , temporanea ( $t$ ) altrimenti.

A ogni passo un nodo è il nodo corrente.

Esempio 1 (grafo a 6 nodi, sorgente 1). Archi: $1\!-\!2=7$ , $1\!-\!3=9$ , $1\!-\!6=14$ , $2\!-\!3=10$ , $2\!-\!4=15$ , $3\!-\!4=11$ , $3\!-\!6=2$ , $4\!-\!5=6$ , $5\!-\!6=9$ .

Grafico interattivo: Albero di costo minimo di A (archi colorati)

Formula (aggiornamento di Bellman-Ford). Il nodo $A$ riceve dal vicino $Y$ il DV con le stime $d_{Y,w}$ del costo da $Y$ a ogni destinazione $w$ . Per ogni $w$ : $D_{A,w}=\min\{\,D_{A,w},\ D_{A,Y}+d_{Y,w}\,\}.$ Se il valore passando per $Y$ è minore, si mettono nella riga $w$ il nuovo costo e next hop $=Y$ .

Qui $D_{A,Y}$ è il costo immediato del collegamento $A\to Y$ e $d_{Y,w}$ è il costo minimo stimato da $Y$ a $w$ (che può passare per più salti).

Esempio. $A$ riceve da $B$ il primo DV di $B$ , che dice $d_{B,A}=4$ , $d_{B,C}=2$ , $d_{B,G}=1$ e $\infty$ per $D$ , $E$ , $F$ . Con $D_{A,B}=4$ : per $C$ , $\min\{\infty,\,4+2\}=6$ (next hop $B$ ); per $G$ , $\min\{\infty,\,4+1\}=5$ (next hop $B$ ); per $D$ , $\min\{\infty,\,4+\infty\}=\infty$ (nessun miglioramento: $B$ non conosce ancora $D$ ). Poi arriva il DV di $F$ (con $d_{F,G}=1$ , $d_{F,E}=3$ ) e $A$ calcola, con $D_{A,F}=1$ : per $G$ , $\min\{5,\,1+1\}=2$ (next hop $F$ ); per $E$ , $\min\{\infty,\,1+3\}=4$ (next hop $F$ ).

Proprietà (sottostruttura ottima). Se $s=v_0,v_1,\dots,v_k=v$ è un cammino minimo da $s$ a $v$ , ogni suo tratto $v_i,\dots,v_j$ è un cammino minimo da $v_i$ a $v_j$ . Di conseguenza $\delta(s,v)=\min_{u}\{\delta(s,u)+c(u,v)\}$ al variare dei vicini $u$ di $v$ (equazione di Bellman).

Proprietà (invariante di Dijkstra). Quando un nodo $u$ diventa permanente, $d_u=\delta(s,u)$ . Inoltre per ogni nodo $v$ non permanente $d_v$ è la lunghezza del cammino minimo da $s$ a $v$ che usa come nodi intermedi soli nodi permanenti.

Proprietà (invariante di Bellman-Ford). $D^{k}(A,w)$ è il costo minimo tra i cammini da $A$ a $w$ con al più $k+1$ archi.

Instradamento e inoltro

Definizione (inoltro). Mettere il pacchetto sul percorso verso la destinazione. Poiché Internet è una combinazione di collegamenti (reti), inoltrare vuol dire consegnare il pacchetto al salto successivo (next hop): si procede hop by hop.

Proprietà (cosa cambia a ogni salto). Gli indirizzi IP sorgente e destinazione restano gli stessi dall'origine alla destinazione finale; gli indirizzi MAC cambiano a ogni salto (sorgente = interfaccia che trasmette, destinazione = interfaccia del prossimo nodo). Si può verificare con l'esercizio Esercizio - pacchetti ARP e IP con router e con switch.

Esempio. Con un router tra due reti, un pacchetto da $A$ a $D$ viaggia come $\text{MAC}_A\!\to\!\text{MAC}_{R,\text{eth0}}$ nel primo collegamento e $\text{MAC}_{R,\text{eth1}}\!\to\!\text{MAC}_D$ nel secondo; in tutti e due gli indirizzi IP sono $\text{IP}_A\!\to\!\text{IP}_D$ . Con un semplice switch (livello 2) invece anche i MAC non cambiano.

Formula (condizione di inoltro diretto). Per ogni interfaccia $x$ del router: se $\text{IP}_{\text{dst}}\ \text{AND}\ \text{NM}(x)\;=\;\text{IP}(x)\ \text{AND}\ \text{NM}(x),$ si inoltra direttamente attraverso l'interfaccia $x$ ; altrimenti si prova l'interfaccia successiva. Se nessuna interfaccia corrisponde, l'inoltro è indiretto.

Qui $\text{IP}_{\text{dst}}$ è l'indirizzo di destinazione del pacchetto, $\text{IP}(x)$ e $\text{NM}(x)$ sono indirizzo e maschera dell'interfaccia $x$ .

Esempio. eth0 $=131.175.21.96/24$ e destinazione $131.175.21.77$ : $131.175.21.77\ \text{AND}\ 255.255.255.0=131.175.21.0=131.175.21.96\ \text{AND}\ 255.255.255.0$ . Corrisponde (positive match): inoltro diretto da eth0.

Definizione (tabella di instradamento). Elenco di righe (rete, netmask, next hop): la rete è l'indirizzo di rete della destinazione, la netmask serve a confrontarlo, il next hop è l'indirizzo IP del router a cui consegnare il pacchetto (e deve appartenere a una delle reti delle interfacce, così il router sa da quale interfaccia mandarlo e quale MAC cercare con ARP).

Protocolli di instradamento - RIP, OSPF e BGP

Definizione (sistema autonomo). Insieme di router interconnessi che eseguono tutti lo stesso algoritmo di instradamento (scelto dall'AS) e usano un protocollo standard per collegarsi ai router degli altri AS. Due livelli di protocolli:

IGP (Interior Gateway Protocol, instradamento intra-AS): dentro un AS;

EGP (Exterior Gateway Protocol, instradamento inter-AS): da un AS all'altro.

Esempio. Gli host $h_1$ (in AS $A$ ) e $h_2$ (in AS $B$ ) comunicano: dentro $A$ il pacchetto è instradato con il protocollo intra-AS di $A$ fino al router di bordo, tra $A$ e $B$ con il protocollo inter-AS, dentro $B$ con il protocollo intra-AS di $B$ .

Definizione (RIP). Protocollo IGP progettato a Berkeley (1982), definito nella RFC 1058. Distance vector (Bellman-Ford). Metrica: numero di salti (hop count). Costo massimo: 15 salti (16 è infinito). Aggiornamenti dei DV: periodici (circa ogni 30 s) più asincroni (a ogni cambio di topologia). Messaggi: pacchetti RIP incapsulati in datagrammi UDP, porta assegnata 520 (Protocollo UDP).

Esempio (aggiornamento). Il router $R_1$ ha la tabella

Definizione (OSPF). Protocollo IGP per AS grandi (RFC 1247, 1583). Link state: supporta l'instradamento gerarchico; usa il protocollo HELLO; ogni router ha un identificativo unico (per esempio uno dei suoi indirizzi IP); si scambiano Link State Advertisement (LSA). Metriche: a ogni collegamento (rete) si può assegnare un peso in base a metriche diverse (massimo throughput, numero di salti, ritardo minimo, ecc.), quindi tipi di servizio diversi possono avere costi diversi. I messaggi sono incapsulati direttamente in pacchetti IP (senza UDP né TCP).

9. Livello di trasporto

Livello di trasporto - porte e multiplexing

Definizione (livello di trasporto). Fornisce una comunicazione logica end-to-end tra processi applicativi in esecuzione su host diversi. Il mittente spezza i messaggi applicativi in segmenti e li passa al livello di rete; il ricevente li ricompone in messaggi e li passa all'applicazione.

Definizione (numero di porta). È un intero di 16 bit, quindi compreso tra $0$ e $2^{16}-1=65\,535$ (con $16$ bit ci sono $2^{16}=65\,536$ combinazioni distinte, da $0$ a $65\,535$ ). L'indirizzo IP di destinazione sceglie l'host tra tutti gli host del mondo; una volta scelto l'host, il numero di porta di destinazione sceglie il processo su quell'host.

Definizione (socket). È la combinazione di un indirizzo IP e di un numero di porta, scritta $\langle\text{IP},\text{porta}\rangle$ . Seleziona un host (IP) e un processo su quell'host (porta).

Esempio. $\langle158.108.33.3,\,3000\rangle$ : l'IP $158.108.33.3$ individua l'host, la porta $3000$ il processo.

Proprietà (quaterna di una connessione). Una connessione è identificata in modo univoco dalla quaterna $(\text{porta sorgente},\ \text{porta destinazione},\ \text{IP sorgente},\ \text{IP destinazione}).$

Esempio. Due studenti, $A=147.162.10.5$ e $B=147.162.10.6$ , aprono la stessa pagina su un server $S=93.184.216.34$ . Le connessioni sono $(51234,80,A,S)$ e $(51234,80,B,S)$ : stessa porta sorgente e stesse porte di destinazione, ma indirizzi IP diversi, quindi sono connessioni diverse. Se $A$ apre una seconda scheda sullo stesso server, il sistema operativo di $A$ sceglie un'altra porta effimera, per esempio $51\,240$ : $(51240,80,A,S)$ . Il server usa una sola porta (la 80) per tutte le connessioni; è la quaterna a distinguerle.

Definizione (multiplexing e demultiplexing). In un host c'è un solo UDP e un solo TCP, ma molti processi vogliono usarli. Il multiplexing (lato mittente) è la raccolta dei messaggi di molti processi in un unico flusso di segmenti, ciascuno con la propria porta sorgente. Il demultiplexing (lato ricevente) è lo smistamento dei segmenti in arrivo verso il processo giusto, guardando le porte.

Esempio. Sul server $S$ la porta $80$ ha tre connessioni aperte: $(51234,80,A,S)$ , $(51234,80,B,S)$ e $(51240,80,A,S)$ . Un segmento TCP arriva con porta sorgente $51234$ , porta destinazione $80$ , IP sorgente $B$ : il demultiplexing lo consegna al processo che gestisce la seconda connessione. Anche il NAT con traduzione delle porte usa questo schema: NAT e indirizzi privati.

Formula (numeri di sequenza). Con un campo di $m$ bit i numeri di sequenza vanno da $0$ a $2^m-1$ .

Esempio. Con $m=3$ i numeri sono $0,1,\dots,7$ (otto valori, $2^3=8$ ); con i 32 bit di TCP, $0$ – $2^{32}-1=4\,294\,967\,295$ . Finiti i numeri si ricomincia da $0$ (aritmetica modulo $2^m$ ), per questo la finestra dei protocolli ARQ non può coprire tutti i numeri disponibili. I protocolli del livello di collegamento (Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat) sono i "parenti" di quelli di trasporto: TCP usa una modifica o una combinazione di stop-and-wait, Go-Back-N e Selective Repeat.

Protocollo UDP

Formula (dati utili in un datagramma UDP). $\text{dati}=\text{lunghezza UDP}-8$ .

Esempio. Un datagramma con lunghezza $12$ trasporta $12-8=4$ byte di dati. Un messaggio più grande di $65\,507$ byte non si può inviare con un solo UDP: UDP non spezza un flusso in datagrammi correlati, quindi può essere usato solo da processi che inviano messaggi brevi.

Formula (checksum UDP). Si sommano tutte le parole da 16 bit di pseudo-intestazione, intestazione (con il campo checksum posto a $0$ ) e dati (se i byte sono dispari si aggiunge un byte di zeri in fondo); i riporti oltre il sedicesimo bit si sommano al risultato (aritmetica a complemento a uno); il checksum è il complemento a uno (NOT bit a bit) della somma. Il ricevente somma tutte le parole, checksum compreso: se non ci sono errori ottiene $\texttt{FFFF}$ .

Esempio completo. Un host $192.168.0.1$ invia dalla porta $5000$ alla porta $53$ dell'host $192.168.0.199$ i quattro byte Ciao (in esadecimale $43\,69\,61\,6F$ ). Lunghezza UDP $=8+4=12=\texttt{000C}$ . Conversioni in esadecimale (Basi di numerazione e conversioni - binario, ottale ed esadecimale): ogni byte dell'IP si scrive con due cifre, $192=12\cdot16+0=\texttt{C0}$ , $168=10\cdot16+8=\texttt{A8}$ , $199=12\cdot16+7=\texttt{C7}$ ; le porte: $5000=1\cdot4096+3\cdot256+8\cdot16+8=\texttt{1388}$ , $53=3\cdot16+5=\texttt{0035}$ ; i caratteri sono in ASCII (Codici binari - BCD, ASCII, Unicode, parità e Gray): C $=\texttt{43}$ , i $=\texttt{69}$ , a $=\texttt{61}$ , o $=\texttt{6F}$ . Parole:

TCP - connessione, affidabilità e controllo di flusso

Formula (MSS). $\text{MSS}=\text{MTU}-\text{(intestazione IP)}-\text{(intestazione TCP)}=\text{MTU}-40$ (con intestazioni di 20 byte ciascuna).

Esempio. Ethernet, MTU $=1500$ byte: $\text{MSS}=1500-20-20=1460$ byte (i $1500$ byte del datagramma IP contengono $20$ byte di intestazione IP, $20$ di intestazione TCP e il resto è payload). Un collegamento con MTU $512$ dà $\text{MSS}=512-40=472$ . Un segmento pieno è quindi $1460$ byte di dati più $20$ di TCP $=1480$ byte e, con i $20$ di IP, esattamente $1500$ byte (l'MTU): la frazione di byte utili è $1460/1500=97{,}3\,\%$ .

Proprietà (quanti numeri di sequenza consuma un segmento). Un segmento senza dati (per esempio un semplice ACK) non consuma numeri di sequenza. I segmenti SYN e FIN, pur senza dati, ne consumano uno (come se portassero un byte immaginario), perché devono essere riscontrati.

Formula (finestra di invio). $\text{swnd}=\min(\text{rwnd},\,\text{cwnd})$ , e un nuovo byte si può inviare se $\text{ultimo\_inviato}-\text{ultimo\_riscontrato}\le\text{swnd}$ . rwnd (finestra del ricevitore) dipende dall'estremo di destinazione; cwnd (finestra di congestione, TCP - controllo di congestione) dipende dalla rete.

Esempio. Con rwnd $=6$ MSS e cwnd $=4$ MSS, $\text{swnd}=4$ MSS; quando cwnd sale a $7$ MSS, $\text{swnd}=6$ MSS: oltre rwnd non si può andare.

Formula (finestra del ricevitore). $\text{rwnd}=\text{dimensione del buffer}-\text{byte in attesa di essere letti dal processo}.$

Definizione (persist timer). Quando rwnd $=0$ il mittente avvia un persist timer (inizialmente $500$ ms, dipende dall'implementazione). Se scade senza aver ricevuto segmenti, il mittente invia una sonda (probe) di 1 byte, che fa ripetere al ricevente il prossimo byte atteso e la finestra corrente. Se il ricevente è ancora pieno rifiuta la sonda; altrimenti la riscontra e annuncia la finestra disponibile. A ogni mancata risposta il timer raddoppia (backoff esponenziale), fino a un massimo di $60$ s.

Esempio. Sonde a $0{,}5$ , $1$ , $2$ , $4$ , $8$ , $16$ , $32$ , $60$ s: il valore dopo $n$ mancate risposte è $0{,}5\cdot2^n$ s (progressione geometrica di ragione $2$ ) e, arrivati a $0{,}5\cdot2^7=64$ s, che supera il massimo, si ferma a $60$ s. Dopo l'ottava sonda quindi si sonda ogni $60$ s.

Definizione (algoritmo di Nagle). Dopo aver inviato il primo segmento, il mittente accumula i dati nel buffer d'uscita e aspetta o che arrivi l'ACK del ricevente, o che si siano accumulati dati sufficienti per riempire un MSS; poi trasmette.

Definizione (BDP). Il prodotto banda-ritardo (bandwidth-delay product) è $\text{BDP}=C\cdot\text{RTT}$ , la quantità di bit in volo. La finestra ideale in bit è $W\cdot L=\text{BDP}$ .

Esempio (continuità). $C=10$ Mbit/s, $L=1500$ byte $=12\,000$ bit, $\tau=5$ ms per tratta: $t_x=1{,}2$ ms, $\text{RTT}=t_x+2\tau=11{,}2$ ms (ACK trascurabile). Serve $W\ge11{,}2/1{,}2=9{,}33$ , cioè $W=10$ segmenti.

Formula (throughput massimo). La finestra limita la quantità di dati inviabili per RTT, quindi qualunque variante di TCP non può superare $\text{throughput}\le\frac{\text{MSS}\cdot W_{\max}}{\text{RTT}}.$

Esempio. Collegamento da $100$ Mbit/s, $\text{RTT}=40$ ms, $\text{MSS}=1460$ byte. $\text{BDP}=10^8\cdot0{,}04=4\cdot10^6$ bit $=500$ kB, cioè $500\,000/1460=342{,}5\approx343$ segmenti: per riempire il canale servono $343$ segmenti in volo. Con la sola finestra a 16 bit ( $W_{\max}=65\,535$ byte, senza l'opzione di scalatura) il throughput è al più $65\,535\cdot8/0{,}04=13{,}1$ Mbit/s (il fattore $8$ converte byte in bit, $0{,}04$ s è l'RTT): solo il $13\%$ del canale, perché $13{,}1/100=0{,}131$ . Nel grafico l'utilizzazione $U=\min(1,\,W/343)$ cresce linearmente con la finestra e arriva a $1$ solo con $W\ge\text{BDP}/\text{MSS}$ ; la finestra a 16 bit ( $65\,535/1460\approx45$ segmenti) si ferma al $13\%$ .

{"tipo":"funzione","titolo":"Utilizzazione del canale U = min(1, W/342,5) con C = 100 Mbit/s, RTT = 40 ms, MSS = 1460 byte: con rwnd massima di 16 bit (≈ 44,9 segmenti) U = 13%","curve":[{"espressione":"min(1,x/342.47)","etichetta":"U"}],"x":[0,400],"y":[0,1.1],"verticali":[{"x":44.89,"etichetta":"65 535 B"},{"x":342.47,"etichetta":"BDP"}],"assi":{"x":"W (segmenti in volo)","y":"U"}}
``` Esercizi su questi temi: <a class="wiki" href="/internet/esercizi/esercizio-tcp-con-finestra-del-ricevitore-di-4-segmenti-su-tre-collegamenti/">Esercizio - TCP con finestra del ricevitore di 4 segmenti su tre collegamenti</a>; per misurare capacità e ritardo con i tempi di andata e ritorno, <a class="wiki" href="/internet/esercizi/esercizio-capacita-e-ritardo-di-propagazione-di-un-collegamento-con-due-messaggi-echo/">Esercizio - capacita e ritardo di propagazione di un collegamento con due messaggi echo</a>.

TCP - controllo di congestione

Formula (indice di equità di Jain). Per $N$ flussi con rate $x_1,\dots,x_N$ : $\text{FI}=\frac{\left(\sum_{i=1}^{N}x_i\right)^2}{N\sum_{i=1}^{N}x_i^2},\qquad \frac1N\le\text{FI}\le1.$ Vale $1$ se tutti hanno lo stesso rate, $1/N$ se uno solo usa tutto.

Esempio. Tre flussi su un link da $30$ Mbit/s. Divisione $(10,10,10)$ : $\text{FI}=30^2/(3\cdot300)=1$ . Divisione $(18,1,1)$ : $\text{FI}=20^2/(3\cdot326)=400/978=0{,}409$ . Divisione $(8,6,4)$ : $\text{FI}=18^2/(3\cdot116)=324/348=0{,}931$ .

Formula (finestra effettiva). $W=\min(\text{cwnd},\text{rwnd})$ .

Esempio. Con $\text{ssthresh}=4$ MSS e $\text{rwnd}=6$ MSS: $W=\min(1,6)=1$ , poi $2$ , $4$ (si raggiunge ssthresh), $5$ , $6$ (si raggiunge rwnd: da lì $W$ resta $6$ anche se cwnd continua a crescere: $\min(6,7)=6$ ).

Formula (regole per ogni ACK nuovo).

se $\text{cwnd}\le\text{ssthresh}$ (SS): $\text{cwnd}\leftarrow\text{cwnd}+1$ ;

se $\text{cwnd}>\text{ssthresh}$ (CA): $\text{cwnd}\leftarrow\text{cwnd}+\dfrac1{\text{cwnd}}$ .

Conseguenza per RTT: in SS $\text{cwnd}$ raddoppia a ogni RTT (un ACK per ogni segmento: $+1$ per ACK vale $+W$ per round); in CA aumenta di 1 MSS per RTT (arrivano $W$ ACK, ciascuno vale $1/W$ ).

Esempio. Partendo da $\text{cwnd}=1$ con $\text{ssthresh}=8$ : round $0$ : $1$ ; round $1$ : $2$ ; round $2$ : $4$ ; round $3$ : $8$ ; da qui $9$ , $10$ , $11$ , $\dots$ . Nel round $i\le3$ la finestra vale $W_i=2^i$ e sono stati inviati $2^{i+1}-1$ segmenti in tutto ( $1+2+4+8=15$ dopo il round $3$ ): è la somma di una progressione geometrica di ragione $2$ , $\sum_{k=0}^{i}2^k=\frac{2^{i+1}-1}{2-1}$ . Viceversa, per arrivare a una finestra $W$ in SS servono $\log_2W$ round (Esponenziale e logaritmo): da $1$ a $8$ sono $\log_28=3$ round.

Formula (reazioni di base, regole del corso). Quando la congestione è indicata da $K$ dupACK: $\text{ssthresh}=W/2$ . Con timeout: $\text{ssthresh}=W/2$ e $\text{cwnd}=1$ (nuovo slow start). ( $W$ è la finestra al momento dell'evento.)

Formula (Reno).

Alla terza dupACK: $\text{ssthresh}=\text{cwnd}/2$ ; si ritrasmette il segmento mancante; $\text{cwnd}=\text{ssthresh}+3$ MSS (i tre pacchetti che hanno generato i tre dupACK hanno lasciato la rete).

A ogni dupACK successivo: $\text{cwnd}\leftarrow\text{cwnd}+1$ MSS (un altro pacchetto ha raggiunto il ricevente) e si trasmette un pacchetto se cwnd lo consente.

Quando arriva un ACK che riscontra dati nuovi: $\text{cwnd}=\text{ssthresh}$ e si esce dal fast recovery (si prosegue in CA).

Dopo un timeout: come Tahoe ( $\text{ssthresh}=\text{cwnd}/2$ , $\text{cwnd}=1$ , slow start).

Esempio. $\text{cwnd}=12$ : tre dupACK $\Rightarrow$ $\text{ssthresh}=6$ , $\text{cwnd}=9$ ; due dupACK in più $\Rightarrow\text{cwnd}=11$ ; all'ACK nuovo $\text{cwnd}=6$ e CA ( $7,8,\dots$ ). Tahoe, nello stesso caso, ripartirebbe da $1$ .

Formula (NewReno).

Alla $K$ -esima dupACK: $\text{recover}=\text{lastseqno}$ ; $\text{ssthresh}=\max(\text{flightsize}/2,\ 2\,\text{MSS})$ ; $\text{cwnd}=\text{ssthresh}+3$ MSS; si azzera il timer di ritrasmissione (per evitare un timeout durante il recupero); si ritrasmette il segmento mancante.

A ogni nuovo dupACK: $\text{cwnd}\leftarrow\text{cwnd}+1$ , e si trasmette se cwnd lo permette.

Quando arriva un ACK che riscontra dati nuovi: se $\text{ack\_no}>\text{recover}$ (ACK completo) allora $\text{cwnd}=\text{ssthresh}$ ed esce dal fast recovery; altrimenti è un ACK parziale che riscontra $n_{\text{acked}}$ pacchetti: $\text{cwnd}\leftarrow\text{cwnd}-n_{\text{acked}}+1$ , si azzera il timer, si ritrasmette il pacchetto con $\text{seq\_no}=\text{ack\_no}$ e si trasmette se consentito.

Esempio (slide del corso). Finestra $W=9$ in CA, sono in volo i pacchetti $P_3,\dots,P_{11}$ ; si perdono $P_6$ e $P_8$ ; ACK ritardati con $b=2$ . Il ricevente manda $\text{ACK}\,5$ (riscontra $P_3,P_4$ ), $\text{ACK}\,6$ (riscontra $P_5$ ), poi ogni pacchetto che arriva fuori ordine ( $P_7,P_9,P_{10},P_{11}$ ) genera un dupACK $\,6$ . Alla terza dupACK il mittente ha già inviato fino a $P_{14}$ : $\text{recover}=P_{14}$ , $\text{flightsize}=14-6+1=9$ , $\text{ssthresh}=\lfloor9/2\rfloor=4$ , $\text{cwnd}=4+3=7$ ; ritrasmette $P_6$ . Gli altri dupACK portano cwnd a $8$ , $9$ , $10$ e fanno partire $P_{15}$ . L'arrivo di $P_6$ al ricevente genera $\text{ACK}\,8$ (riscontra $P_6$ e $P_7$ , manca $P_8$ ): è un ACK parziale ( $8\le14$ ) con $n_{\text{acked}}=2$ , quindi $\text{cwnd}=10-2+1=9$ ; in volo ci sono $P_8,\dots,P_{15}$ , cioè $8$ pacchetti $<9$ , quindi parte un nuovo pacchetto, $P_{16}$ , e si ritrasmette $P_8$ . Quando poi arriva $\text{ACK}\,16$ , $16>\text{recover}=14$ : ACK completo, $\text{cwnd}=\text{ssthresh}=4$ e fine del recupero. Due perdite sono state recuperate in due RTT senza timeout.

Formula (lunghezza dell'opzione SACK). Con $n$ blocchi: $\text{lunghezza}=8n+2$ byte. Poiché le opzioni TCP sono al massimo $40$ byte, $n\le4$ ( $8\cdot4+2=34$ ). Se c'è anche il timestamp ( $12$ byte con riempimento), restano $28$ byte e $n\le3$ ( $8\cdot3+2=26$ ).

Esempio. Il ricevente ha i byte $1$ – $1000$ (campo ACK $=1001$ , riscontro cumulativo), manca $1001$ – $2000$ , ha $2001$ – $3000$ , manca $3001$ – $4000$ , ha $4001$ – $5000$ . Opzione: Kind $=5$ , Length $=2+2\cdot8=18$ , blocchi $[2001,3001)$ e $[4001,5001)$ .

Modello analitico del tasso di invio di TCP

Definizione (tasso di invio). Se $N_t$ è il numero di pacchetti trasmessi nell'intervallo $[0,t]$ , il tasso di invio nell'intervallo è $N_t/t$ e il tasso di invio a lungo termine (a regime) è $B=\lim_{t\to\infty}\frac{N_t}{t}\quad[\text{pacchetti/s}].$

Formula (tasso a lungo termine). $B=\frac{E[Y]}{E[A]}.$

Formula (primo calcolo). $E[Y]=E[\alpha]-1+E[W]=\frac{1-p}{p}+E[W].\tag{3}$

Formula (finestra media). $E[W]=\frac{2-3b}{3b}+\sqrt{\left(\frac{3b-2}{3b}\right)^2+\frac{8(1-p)}{3bp}}\ \xrightarrow{\,p\to0\,}\ \sqrt{\frac{8}{3bp}}.$

Esempio. $b=2$ , $p=0{,}01$ : $E[W]=-\tfrac23+\sqrt{\tfrac49+\tfrac{4\cdot0{,}99}{3\cdot0{,}01}}=-0{,}667+\sqrt{0{,}444+132}=10{,}84$ pacchetti (l'approssimazione $\sqrt{8/(3\cdot2\cdot0{,}01)}=11{,}55$ dà una stima un po' alta, perché trascura il termine costante).

Formula (durata media). $E[A]=(E[X]+1)\,\text{RTT}\simeq\text{RTT}\sqrt{\frac{2b}{3p}}.$

Formula (radice quadrata). $B(p,b,\text{RTT})=\frac1{\text{RTT}}\sqrt{\frac{3}{2bp}}+o\!\left(\frac1{\sqrt p}\right).\tag{7}$

Esempio. $b=2$ , $\text{RTT}=100$ ms, $p=10^{-4}$ : $B=\frac1{0{,}1}\sqrt{\frac3{4\cdot10^{-4}}}=10\cdot86{,}6=866$ segmenti/s. Dimezzare l'RTT raddoppia $B$ ; ridurre $p$ di un fattore $100$ moltiplica $B$ per $10$ . Con $p=10^{-2}$ la (7) dà $86{,}6$ seg/s, mentre la formula esatta senza arrotondare ( $E[Y]/E[A]$ ) dà $79{,}4$ : per $p$ grande la radice quadrata sovrastima.

Formula (tasso con timeout, forma generale). $B=\frac{E[Y]+Q\,E[R]}{E[A]+Q\,E[Z^{TO}]}.\tag{8}$

Formula (probabilità di timeout). $\hat Q(w)=\min\left\{1,\ \frac{1-(1-p)^3}{1-(1-p)^w}\Big[1+(1-p)^3\big(1-(1-p)^{w-3}\big)\Big]\right\}\ \xrightarrow{\,p\to0\,}\ \min\left\{1,\frac3w\right\}.$

Esempio. $w=10$ , $p=0{,}01$ : $\hat Q=0{,}331$ (contro l'approssimazione $3/w=0{,}30$ ). Con $w\le3$ è $\hat Q=1$ (con finestra di 3 pacchetti o meno un solo pacchetto perso non può produrre tre dupACK: sempre timeout). Poiché $w$ non è costante si usa $Q\simeq\hat Q(E[W])$ .

Formula (modello completo, "full model"). $B(p,b,\text{RTT},T_0)=\frac{\dfrac{1-p}{p}+E[W]+\hat Q(E[W])\dfrac1{1-p}}{\text{RTT}\left(\dfrac b2E[W]+b+1\right)+\hat Q(E[W])\,\dfrac{T_0\,f(p)}{1-p}}.\tag{9}$

Formula (modello approssimato). $B\simeq\frac1{\text{RTT}\sqrt{\dfrac{2bp}3}+T_0\min\left\{1,\,3\sqrt{\dfrac{3bp}8}\right\}p\,(1+2p+4p^2)}\quad[\text{seg/s}].\tag{10}$

Formula (tetto della finestra). $B^{W_{\max}}=\min\left\{\frac{W_{\max}}{\text{RTT}},\ B(p,b,\text{RTT},T_0)\right\}\quad[\text{pacchetti/s}].\tag{11}$

Stima del timeout di ritrasmissione (RTO)

Formula (SRTT). $\text{SRTT}_i=(1-\alpha)\,\text{SRTT}_{i-1}+\alpha\cdot\text{rtt}_i,\qquad\alpha=\frac18.$

Esempio. $\text{SRTT}_{i-1}=80$ ms, $\text{rtt}_i=120$ ms: $\text{SRTT}_i=\tfrac78\cdot80+\tfrac18\cdot120=70+15=85$ ms.

Grafico interattivo: Peso del campione di k passi fa nella media esponenziale SRTT: α(1−α)^k con α = 1/8 (0,125; 0,109; 0,096; ...)

Formula (MAD). $\text{MAD}_i=(1-\rho)\,\text{MAD}_{i-1}+\rho\,\big|\text{rtt}_i-\text{SRTT}_{i-1}\big|,\qquad\rho=\frac14.$

Formula (RTO). $\text{RTO}_i=\text{SRTT}_i+4\cdot\text{MAD}_i,\qquad T_0=\max\{\text{RTO},\,1\text{ s}\}.$

Proprietà (MAD di una gaussiana). $\text{MAD}=\sigma\sqrt{2/\pi}\approx0{,}797\,\sigma$ .

Esempio. Un percorso formato da collegamenti con RTT indipendenti: il RTT medio totale è la somma dei medi e la varianza è la somma delle varianze (Somma di variabili aleatorie indipendenti: la somma di gaussiane indipendenti è ancora gaussiana). Con $\sigma_n=0{,}1;\,2;\,1;\,0{,}5$ ms: $\sigma^2_{\text{tot}}=0{,}01+4+1+0{,}25=5{,}26$ ms $^2$ , $\sigma=2{,}293$ ms; $\text{MAD}=0{,}7979\cdot2{,}293=1{,}829$ ms. Con $\text{RTT}=27$ ms (la media): $\text{RTO}=\text{SRTT}+4\,\text{MAD}=27+4\cdot1{,}829=34{,}3$ ms, e quindi $T_0=\max\{34{,}3\text{ ms},1\text{ s}\}=1$ s: è il valore che si usa nel modello del tasso di invio (Modello analitico del tasso di invio di TCP). La verifica numerica con $400\,000$ campioni gaussiani dà $E|Y|=0{,}7985\,\sigma$ .

10. Livello applicazione

Livello applicazione - DNS

Definizione (dominio e nome di dominio). Un nome di dominio è la sequenza di etichette dal nodo dell'albero fino alla radice, separate da punti. Un dominio è il sotto-albero che parte da quel nodo.

Esempio. signet.dei.unipd.it ha 4 etichette: il nodo signet sta al livello 4 dell'albero (it livello 1, unipd 2, dei 3) ed è dentro i domini dei.unipd.it, unipd.it e it.

Definizione (risoluzione). La traduzione di un nome in un indirizzo si chiama risoluzione nome-indirizzo (name-address resolution). L'host che ha bisogno di tradurre è il risolutore (resolver): manda la richiesta al server DNS più vicino. Se il server ha l'informazione, risponde al risolutore; altrimenti lo rimanda ad altri server oppure chiede lui ad altri server.

Formula (tempo di risoluzione con cache vuota). Ogni coppia domanda-risposta costa un RTT con il suo interlocutore (il round trip time è il tempo di andata e ritorno: due ritardi di propagazione più i tempi di trasmissione e di elaborazione, Analisi delle prestazioni di rete; i messaggi DNS sono molto brevi, per esempio $100$ byte $=800$ bit su un collegamento a $10$ Mbit/s si trasmettono in $800/10^7=80\ \mu$ s, trascurabili davanti ai millisecondi di propagazione, quindi RTT $\approx2\tau_p$ ), quindi $T=\text{RTT}_{\text{host-locale}}+\text{RTT}_{\text{radice}}+\text{RTT}_{\text{TLD}}+\text{RTT}_{\text{autoritativo}}$ . Con una frazione $h$ di richieste risolte dalla cache del DNS locale, $\bar T=h\,\text{RTT}_{\text{host-locale}}+(1-h)\,T$ .

Esempio. RTT: host-DNS locale 5 ms, DNS locale-radice 30 ms, DNS locale-server com 25 ms, DNS locale-DNS dell'azienda 40 ms. $T=5+30+25+40=100$ ms. Se il DNS locale ha già in cache l'indirizzo del DNS dell'azienda (caso normale per un sito visitato spesso) salta radice e com e va direttamente da lui: $5+40=45$ ms; se è in cache la risposta stessa: 5 ms. Con $h=0{,}9$ : $\bar T=0{,}9\cdot5+0{,}1\cdot100=14{,}5$ ms.

Grafico interattivo: Tempo medio di risoluzione DNS in funzione della frazione h di richieste risolte dalla cache del DNS locale: T medio = 5h + 100(1−h) ms. Con h = 0,9 si ottengono 14,5 ms

Proprietà (cache e TTL). Finché il TTL non è scaduto, il server risponde dalla cache senza interrogare nessuno; allo scadere cancella il dato. Un cambiamento nella zona resta quindi invisibile a chi ha la copia in cache fino alla fine del TTL.

Esempio. www.example.it ha TTL 3600 s: per un'ora tutti i client dello stesso DNS locale ricevono la risposta in un solo RTT. Se l'amministratore cambia l'indirizzo, il vecchio valore può circolare fino a $3600$ s $=60$ minuti: per questo, prima di una migrazione, si abbassa il TTL (per esempio a 300 s) con un certo anticipo.

Definizione (record di risorsa). Una quintupla (nome, tipo, valore, classe, TTL) conservata dai server DNS.

Esempio. www.example.it. 3600 IN A 192.0.2.80: il nome www.example.it ha l'indirizzo IPv4 192.0.2.80, per un'ora, in classe Internet. Un record example.it. 3600 IN MX 10 mail.example.it. dice che la posta di example.it va al server mail.example.it (il numero 10 è la preferenza: vince il valore più basso).

Livello applicazione - HTTP

Definizione (URL). protocollo://host/percorso (usato quasi sempre) oppure protocollo://host:porta/percorso (quando serve indicare la porta).

Protocollo: abbreviazione del programma client-server usato per accedere alla pagina, di solito HTTP.

Host: l'indirizzo IP del server oppure il suo nome unico, di norma il nome di dominio (per esempio wikipedia.org, tradotto dal DNS, Livello applicazione - DNS www.amazon.com) negli indirizzi IP, perché le persone preferiscono i nomi e i protocolli TCP/IP usano gli indirizzi. È un database distribuito e gerarchico: albero rovesciato con radice, domini di primo livello e sottodomini (al più 128 livelli); le informazioni sono su tanti server (13 server radice) e i nuovi domini si registrano presso un registrar accreditato ICANN. Ogni ISP ha un DNS locale, il cui indirizzo l'host riceve con DHCP: l'host (resolver) gli manda la richiesta, di solito su UDP, e il DNS locale interroga radice, dominio di primo livello e server dell'organizzazione. Ogni server che impara un'associazione la tiene in cache, marcando la risposta non autoritativa, e la scarta dopo il TTL. Record (nome, tipo, valore, classe, TTL). Con il NAT il DNS deve restituire l'indirizzo pubblico. Quattro attacchi: macchina compromessa, risposta falsa all'host, avvelenamento della cache del DNS locale, server DNS malevolo.Livello applicazione - DNS →).

Porta: intero a 16 bit (da $0$ a $2^{16}-1=65\,535$ , Sistemi di numerazione posizionali), normalmente predefinito per l'applicazione (HTTP usa la porta 80); si scrive solo se è diverso.

Percorso: posizione e nome del file nel sistema operativo del server; in UNIX è una serie di nomi di cartelle seguiti dal nome del file, separati da / (per esempio /top/next/last/myfile).

Esempio. http://www.example.it:8080/corsi/internet.html: protocollo http, host www.example.it, porta 8080 (invece della 80), percorso /corsi/internet.html. La richiesta conterrà GET /corsi/internet.html HTTP/1.1 e Host: www.example.it:8080.

Definizione (intestazioni principali).

Richiesta: Host (sito richiesto), User-Agent (programma client), Accept e Accept-Language (formati e lingue preferiti, con pesi q), Cookie (cookie memorizzati). Risposta: Date, Server, Set-Cookie, Location (dove andare, per i reindirizzamenti). Entrambe: Content-Type (formato del corpo, per esempio text/html, image/png, application/json), Content-Length (lunghezza del corpo in byte), Connection (keep-alive o close).

Esempio. Una POST che invia un modulo: Content-Type: application/x-www-form-urlencoded e Content-Length: 17 per il corpo nome=Mario&eta=30 (17 caratteri contati).

Definizione (metodo sicuro, metodo idempotente). Un metodo è sicuro se non modifica lo stato del server (solo lettura); è idempotente se ripeterlo $n$ volte ha lo stesso effetto che eseguirlo una volta.

Esempio. DELETE /foto/7 ripetuto due volte lascia il server nello stesso stato (la foto 7 non c'è più; la seconda volta può rispondere 404): idempotente. Due POST /ordini creano invece due ordini: non idempotente. Per questo il browser avvisa quando si ricarica una pagina ottenuta con una POST.

Proprietà (reindirizzamento). Una risposta 301/302 contiene Location: nuovo-URL: il browser fa una nuova richiesta a quell'URL, automaticamente. Un solo clic può quindi costare più richieste (e più RTT).

Esempio. Chi scrive http://www.example.it/ riceve 301 con Location: https://www.example.it/: oltre ai 2 RTT già spesi per ottenere la 301, servono una nuova connessione TCP verso la porta 443 (1 RTT) e la nuova richiesta (almeno 1 RTT, più l'handshake TLS).

Formula (tempo di caricamento di una pagina con $N$ oggetti incorporati). Trascurando i tempi di trasmissione, con $N+1$ oggetti in tutto (la pagina HTML più $N$ oggetti):

non persistente: $T=2(N+1)\,\text{RTT}$ ;

persistente senza pipelining: $T=(2+N)\,\text{RTT}$ (2 per la pagina, 1 per ciascun oggetto);

persistente con pipelining: $T=3\,\text{RTT}$ (2 per la pagina, 1 per tutti gli oggetti insieme).

Esempio. $\text{RTT}=100$ ms, $N=10$ : non persistente $2\cdot11\cdot0{,}1=2{,}2$ s; persistente $12\cdot0{,}1=1{,}2$ s; con pipelining $0{,}3$ s. Il risparmio della persistenza rispetto al non persistente è $2(N+1)-(2+N)=N$ RTT: un RTT per ogni oggetto incorporato (l'handshake che non si ripete).

Grafico interattivo: Tempo di caricamento (s) al crescere del numero N di oggetti incorporati, RTT = 100 ms, trasmissione trascurata

Definizione (cookie). Una piccola stringa, per esempio sessione=18988466, che il server manda in una risposta con l'intestazione Set-Cookie; il browser la memorizza e la rimanda in ogni richiesta successiva allo stesso sito, con l'intestazione Cookie. Il server usa il valore come chiave per ritrovare nella propria base di dati i dati dell'utente.

Esempio (come nelle slide).

Formula (tempo medio con una cache). Se la frazione $h$ delle richieste è soddisfatta dalla cache (hit ratio), $\bar T=h\,T_{\text{hit}}+(1-h)\,T_{\text{miss}}$ , dove $T_{\text{miss}}=T_{\text{hit}}+T_{\text{origine}}$ (la cache va attraversata comunque).

Esempio. $T_{\text{hit}}=10$ ms, $T_{\text{origine}}=200$ ms, $h=0{,}4$ : $\bar T=0{,}4\cdot10+0{,}6\cdot210=130$ ms invece di $200$ ms senza cache.

Grafico interattivo: Tempo medio di risposta con proxy in funzione dell'hit ratio h: T medio = 210 − 200h ms, contro i 200 ms senza cache. La cache conviene per h > 5%

Posta elettronica - SMTP, POP3 e IMAP

Definizione (scenario tipico). Servono due UA (User Agent) sugli host locali; due programmi client/server di spinta (push), gli MTA (Message Transfer Agent); un programma client/server di tiro (pull), il MAA (Message Access Agent).

Definizione (busta e contenuto). Le righe From: e To: dentro il messaggio sono il contenuto, quello che l'utente vede. Gli indirizzi che i server usano per consegnare sono quelli del dialogo SMTP, MAIL FROM e RCPT TO (la busta, envelope): possono essere diversi.

Esempio. Con la copia nascosta (Bcc) il server riceve un RCPT TO in più, ma l'indirizzo non compare nel contenuto: gli altri destinatari non lo vedono.

Proprietà (le tre fasi del trasferimento). Un messaggio si trasferisce in tre fasi: apertura della connessione, trasferimento della posta, chiusura della connessione.

Esempio (la sequenza delle slide). S: server, C: client; il nome some.com è quello dell'host del client.

Proprietà (POP3 contro IMAP4).

POP3 IMAP4

dove stanno i messaggi sul computer dell'utente, dopo lo scaricamento sul server

cartelle sul server no sì, con gerarchia

controllo prima del download no intestazione, ricerca, download parziale

porta TCP 110 143

	POP3	IMAP4
dove stanno i messaggi	sul computer dell'utente, dopo lo scaricamento	sul server
cartelle sul server	no	sì, con gerarchia
controllo prima del download	no	intestazione, ricerca, download parziale
porta TCP	110	143

Esempio. Con una casella letta da PC e da telefono, IMAP4 mostra su entrambi gli stessi messaggi e le stesse cartelle; con POP3 e scarica-e-cancella ciascun dispositivo avrebbe solo i messaggi che ha scaricato.

Definizione (base64). Prende i dati 3 byte alla volta (24 bit), li divide in 4 gruppi da 6 bit e scrive ciascun gruppo (valore da 0 a 63) con un carattere dell'alfabeto A-Z a-z 0-9 + /.

Esempio. Man = byte 01001101 01100001 01101110 (i codici ASCII di M, a, n sono $77,97,110$ , Codici binari - BCD, ASCII, Unicode, parità e Gray) $\to$ si riscrivono i 24 bit di fila, 010011010110000101101110, e si tagliano ogni 6: 010011 010110 000101 101110 $=19,22,5,46$ ( $010011_2=16+2+1=19$ ) $\to$ lettere $\texttt{T},\texttt{W},\texttt{F},\texttt{u}$ $=$ TWFu. Ma (2 byte) $\to$ TWE=, M $\to$ TQ==, Ciao $\to$ Q2lhbw==. Passaggi del riempimento: Ma sono $16$ bit, che si dividono in $2$ gruppi da 6 ( $12$ bit) più $4$ bit restanti, completati con due zeri per fare un terzo gruppo da 6 (010011 010110 0001 + 00 $=19,22,4\to\texttt{TWE}$ ); mancando un byte su tre si aggiunge un =. M sono $8$ bit: un gruppo da 6 e uno da 2 bit completato con quattro zeri (010011 010000 $=19,16\to\texttt{TQ}$ ), mancano due byte su tre, quindi ==. Ciao sono $4$ byte: Cia $\to$ Q2lh, e il byte o solo $\to$ bw==. Un allegato di $3\cdot1024^2=3\,145\,728$ byte diventa $4\cdot3\,145\,728/3=4\,194\,304$ caratteri (ogni $3$ byte $\to4$ caratteri); poi si va a capo ogni $76$ caratteri: $\lceil4\,194\,304/76\rceil=\lceil55\,188{,}2\rceil=55\,189$ righe, ciascuna con un CRLF di $2$ byte, quindi $4\,194\,304+2\cdot55\,189=4\,304\,682$ byte, e $4\,304\,682/3\,145\,728\approx$ $\times1{,}37$ (il $33\%$ di base64 più il $2{,}6\%$ degli a capo).

11. Sicurezza

Introduzione alla sicurezza delle reti

Definizione (minaccia e attacco). Una minaccia (threat) in una rete di comunicazione è qualsiasi evento o sequenza di azioni che possa portare alla violazione di uno o più obiettivi di sicurezza. La realizzazione di una minaccia si chiama attacco.

Esempio. Un hacker che si introduce in un computer, la divulgazione di e-mail in transito, un'entità malevola che modifica dati (per esempio finanziari): sono tre attacchi.

Definizione (obiettivi di sicurezza). Sono le caratteristiche desiderabili di comunicazioni e reti:

obiettivo significato

Riservatezza (confidentiality) l'informazione è disponibile solo al destinatario previsto (detta anche anonimato)

Integrità (integrity) l'informazione è ricevuta esattamente come è stata spedita; se cambia, deve essere possibile scoprirlo, e quindi identificare chi ha creato il dato

Disponibilità (availability) il servizio è sempre disponibile e operativo anche se qualcuno cerca di disturbare la rete

Responsabilità (accountability) è sempre possibile identificare il responsabile di ogni azione (per esempio dell'invio di un'informazione sul canale)

Privacy l'informazione è usata ma non rivelata a nessuno, tranne alle entità autorizzate (detta anche accesso controllato)

obiettivo	significato
Riservatezza (confidentiality)	l'informazione è disponibile solo al destinatario previsto (detta anche anonimato)
Integrità (integrity)	l'informazione è ricevuta esattamente come è stata spedita; se cambia, deve essere possibile scoprirlo, e quindi identificare chi ha creato il dato
Disponibilità (availability)	il servizio è sempre disponibile e operativo anche se qualcuno cerca di disturbare la rete
Responsabilità (accountability)	è sempre possibile identificare il responsabile di ogni azione (per esempio dell'invio di un'informazione sul canale)
Privacy	l'informazione è usata ma non rivelata a nessuno, tranne alle entità autorizzate (detta anche accesso controllato)

Esempio. Un sito di home banking deve garantire riservatezza (nessuno legge il saldo), integrità (nessuno cambia l'importo di un bonifico), disponibilità (il sito risponde anche sotto attacco) e responsabilità (si sa quale utente ha ordinato il bonifico).

Definizione (protocollo di sicurezza di livello N). Un meccanismo (o una combinazione di meccanismi) che offre uno o più servizi di sicurezza per proteggere l'informazione contenuta nelle PDU di livello N e dei livelli superiori, ma non di quelli sotto (Modello ISO-OSI e pila TCP-IP).

Esempio (livello applicazione). Si protegge solo il dato applicativo: la cifratura end-to-end (come in WhatsApp) e l'autenticazione a livello applicazione (HTTPS). Esempio (livello 3). Tutti i dispositivi di livello 4 e 3 (tipicamente i router) devono realizzare il protocollo di sicurezza: instradamento anonimo, instradamento sicuro, IPsec (VPN).

Definizione (sniffing e spoofing). Lo sniffing è l'intercettazione del traffico per accedere a intestazioni e dati e leggerli; non è necessariamente un'azione fraudolenta, può servire per la diagnostica (un sniffer l'abbiamo usato in laboratorio: Wireshark, Katharà - emulare una rete). Lo spoofing è la manipolazione di (una parte del) traffico, di solito un'azione non legittima.

Funzioni hash e crittografia simmetrica

Definizione (crittografia). La crittografia è la cifratura (encryption) e la decifratura (decryption) di messaggi in codice segreto. Può dare riservatezza, integrità e autenticazione. Converte un messaggio (testo in chiaro, plaintext) in un codice segreto (testo cifrato, ciphertext) usando una chiave, in modo che senza la chiave giusta non si possa fare la conversione inversa.

Proprietà (ricerca esaustiva). Provare tutte le chiavi di $k$ bit richiede in media $2^{k-1}$ tentativi: ogni bit in più raddoppia il lavoro.

Esempio. Con $10^{12}$ chiavi al secondo, il DES ( $2^{56}=7{,}2\cdot10^{16}$ chiavi) richiede in media $2^{55}/10^{12}=3{,}6\cdot10^{4}$ s, circa 10 ore ( $3{,}6\cdot10^4/3600=10$ ); AES-128 ( $2^{128}=3{,}4\cdot10^{38}$ ) richiede in media $2^{127}/10^{12}=1{,}7\cdot10^{26}$ s, cioè $1{,}7\cdot10^{26}/(3{,}15\cdot10^7\ \text{s/anno})\approx5{,}4\cdot10^{18}$ anni (per confronto, l'universo ha $1{,}4\cdot10^{10}$ anni). Il rapporto tra i due è $2^{72}$ : ogni bit in più raddoppia, $72$ bit in più moltiplicano per $2^{72}\approx4{,}7\cdot10^{21}$ .

Definizione (funzione hash). Qualsiasi funzione che mappa dati di dimensione arbitraria in dati di dimensione fissa. I valori restituiti si chiamano valori hash, digest o hash.

Esempio. $f(x)=x\bmod1000$ è una funzione hash: porta qualunque $x$ in un numero di $\lceil\log_2 1000\rceil=10$ bit (da 0 a 999: $2^{9}=512<1000\le2^{10}=1024$ , Esponenziale e logaritmo): $1234\to234$ e $2234\to234$ . Però non è one-way, perché dato $h=234$ si trovano subito tutti gli $x=234+1000k$ .

Definizione (funzione hash one-way). Una funzione hash che soddisfa due proprietà:

proprietà one-way: dato $h$ , è "difficile" trovare $m$ tale che $\text{hash}(m)=h$ . La funzione non è invertibile (la corrispondenza è molti-a-uno), ma deve essere difficile trovare un qualsiasi $m$ valido;

resistenza alle collisioni: è "difficile" trovare $m_1$ e $m_2$ diversi tali che $\text{hash}(m_1)=\text{hash}(m_2)$ .

Esempio. Se $x=7$ e l'hash è SHA-256 della stringa 7, che inizia con 7902699b…, e i numeri possibili sono da 1 a 100, chi riceve l'hash prova i 100 candidati e trova $x=7$ al primo colpo (verificato con Python): serve uno spazio di scelta enorme.

Definizione (crittografia simmetrica). Detta anche a chiave privata. Usa la stessa chiave $K$ per cifrare e decifrare: $C=E_K(P)$ , $P=D_K(C)$ . Garantisce riservatezza, integrità e autenticazione dei messaggi. I nodi che comunicano devono condividere una chiave segreta.

Formula (Diffie-Hellman). A manda a B $L=g^x\bmod p$ ; B manda ad A $M=g^y\bmod p$ . A calcola $K=M^x\bmod p$ , B calcola $K'=L^y\bmod p$ . Si ha $K=K'=g^{xy}\bmod p$ : la stessa chiave condivisa.

Esempio ( $p=23$ , $g=5$ ). $x=6$ : $L=5^6\bmod23=8$ . $y=15$ : $M=5^{15}\bmod23=19$ . Alice calcola $K=19^6\bmod23=2$ ; Bob calcola $K'=8^{15}\bmod23=2$ . Chiave condivisa $K=2$ (verificato con Python). Passaggi con le potenze ripetute (si riduce modulo $23$ a ogni prodotto): $5^2=25\equiv2$ , $5^4\equiv2^2=4$ , $5^8\equiv16$ ; $5^6=5^4\cdot5^2\equiv4\cdot2=8$ ; $5^{15}=5^8\cdot5^4\cdot5^2\cdot5\equiv16\cdot4\cdot2\cdot5=640=27\cdot23+19\equiv19$ . Poi $19\equiv-4\pmod{23}$ , quindi $19^6\equiv(-4)^6=4096=178\cdot23+2\equiv2$ ; e $8^{15}$ : $8=2^3$ , $8^{15}=2^{45}$ , con $2^{11}=2048=89\cdot23+1\equiv1$ si ha $2^{45}=(2^{11})^4\cdot2\equiv2$ . Le due strade danno lo stesso $K$ perché $(g^y)^x=g^{xy}=(g^x)^y$ . Un ascoltatore conosce $p=23$ , $g=5$ , $L=8$ , $M=19$ ; per ottenere $K$ dovrebbe ricavare $x$ da $5^x\equiv8\pmod{23}$ , cioè il logaritmo discreto ( $x=6$ qui, trovato provando tutti i valori: con $p$ da 2048 bit non è fattibile).

Definizione (MAC). Un codice di autenticazione del messaggio (Message Authentication Code) realizza l'autenticazione con una chiave segreta condivisa (anche diversa da quella di cifratura). Il nodo mittente lo calcola con una funzione nota e la chiave segreta, ottenendo un valore breve e di lunghezza fissa, l'autenticatore (detto anche tag), che viene aggiunto al messaggio.

Formula (HMAC). L'HMAC (Keyed-Hash MAC) è l'algoritmo standard per il MAC basato su hash. Con $B$ la dimensione del blocco usato dalla funzione hash $H$ (di solito 64 byte) e $K$ la chiave di lunghezza variabile (completata con zeri fino a $B$ ), si usano due hash combinati:

$\text{HMAC}_K(m)=H\big((K\oplus\text{opad})\,\|\,H\big((K\oplus\text{ipad})\,\|\,m\big)\big),$

dove $\text{ipad}$ (hash interno) e $\text{opad}$ (hash esterno) sono valori fissi ( $\texttt{0x36}$ e $\texttt{0x5c}$ ) ripetuti $B$ volte. Perché due hash e non semplicemente $H(K\,\|\,m)$ : con le funzioni costruite alla Merkle-Damgård (MD5, SHA-1, SHA-2) chi conosce $H(K\,\|\,m)$ può calcolare l'hash di $K\,\|\,m\,\|\,\text{padding}\,\|\,m'$ continuando la catena dallo stato finale, senza conoscere $K$ (length extension); l'hash esterno dell'HMAC chiude la catena e lo impedisce. Con $\text{ipad}$ e $\text{opad}$ diversi, le due chiavi usate nei due hash sono diverse anche se partono dalla stessa $K$ .

Esempio. Con $K=$ chiave-segreta e $m=$ bonifico:100:IT60, HMAC-SHA256 $=$ bc838925c97eca28…; per $m'=$ bonifico:900:IT60 si ottiene dadd0ebe877f0fc5…. Chi cambia 100 in 900 non sa ricalcolare il tag giusto senza $K$ . Con il solo SHA-256 (4a8354a1a8c53cb1… per $m$ ) l'avrebbe saputo ricalcolare. (La formula è stata verificata calcolando a mano ipad, opad e i due SHA-256: coincide con la libreria standard.)

Proprietà (MAC contro firma digitale).

aspetto MAC firma digitale

si basa su chiave simmetrica (segreto condiviso) chiavi asimmetriche (privata e pubblica)

proprietà della chiave condivisa tra mittente e destinatario privata del mittente, pubblica di tutti

come funziona mittente e destinatario usano la stessa chiave segreta per generare e verificare il mittente firma con la chiave privata, il destinatario verifica con la pubblica

scopo principale integrità + autenticazione integrità + autenticazione + non ripudio

aspetto	MAC	firma digitale
si basa su	chiave simmetrica (segreto condiviso)	chiavi asimmetriche (privata e pubblica)
proprietà della chiave	condivisa tra mittente e destinatario	privata del mittente, pubblica di tutti
come funziona	mittente e destinatario usano la stessa chiave segreta per generare e verificare	il mittente firma con la chiave privata, il destinatario verifica con la pubblica
scopo principale	integrità + autenticazione	integrità + autenticazione + non ripudio

Crittografia asimmetrica, RSA e TLS

Definizione (crittografia asimmetrica). Detta anche a chiave pubblica. Usa chiavi diverse per cifrare e decifrare. La chiave di cifratura è pubblica e può essere visibile a tutti; la chiave di decifratura è privata, tenuta segreta da ogni nodo e conservata in registri protetti dall'hardware. Le due chiavi sono generate da un metodo che calcola una coppia corrispondente: sono legate matematicamente.

Esempio. In una rete di $n=100$ persone servono $100$ coppie di chiavi, una per persona (e non $\binom{100}{2}=\frac{100\cdot99}2=4950$ chiavi segrete come nella crittografia simmetrica, Funzioni hash e crittografia simmetrica: lì ogni coppia di persone ha una chiave segreta propria, e le coppie non ordinate di $100$ persone si contano con il coefficiente binomiale), e ciascuno può pubblicare la sua chiave pubblica su un sito. Ma una chiave pubblica va distribuita e il suo legame con il proprietario va certificato: lo fanno i certificati.

Definizione (certificato digitale). Un certificato è gestito da una terza parte, la Certificate Authority (CA). Per ottenerlo, un'entità fornisce alla CA la propria identità e la propria chiave pubblica; la CA convalida l'identità ed emette il certificato. Il certificato contiene: il nome dell'entità proprietaria e la sua chiave pubblica; la validità o scadenza; la CA che l'ha emesso (e molti altri dati). È firmato con la chiave privata della CA: chiunque abbia la sua chiave pubblica può verificare il certificato.

Esempio (come nelle slide). Visitando https://www.google.com, il browser controlla automaticamente il certificato digitale inviato da Google. Un certificato reale contiene: nome del sito www.google.com; chiave pubblica (una lunga stringa casuale); emittente (Google Trust Services LLC, la CA); periodo di validità (per esempio da marzo 2025 a marzo 2026); firma della CA, che prova che è legittimo. Il browser lo controlla: se è valido pensa "questa chiave pubblica appartiene davvero a Google", e può cifrare i dati verso Google in sicurezza.

Definizione (firma digitale). Fase 1, firma: si calcola l'hash del messaggio (con una funzione hash crittografica come SHA-256, Funzioni hash e crittografia simmetrica); si cifra l'hash con la chiave privata: questa è la firma; si manda il messaggio insieme alla firma. Fase 2, verifica: il ricevente calcola da sé l'hash del messaggio; decifra la firma ricevuta con la chiave pubblica del mittente; se hash decifrato == hash calcolato, il messaggio è autentico.

Definizione (inverso modulare). $b^{-1}$ è l'inverso modulare di $b$ modulo $d$ se $b\cdot b^{-1}\equiv1\pmod d$ . Esiste se $\gcd(b,d)=1$ (cioè se $b$ e $d$ sono coprimi); quindi, se $d=p$ è primo, ogni intero tra 1 e $p-1$ ha un inverso modulo $p$ . La divisione modulare è $(a/b)\bmod d=(a\cdot b^{-1})\bmod d$ .

Esempio. $b=4$ , $d=7$ : deve valere $4\cdot b^{-1}\equiv1\pmod7$ , quindi $b^{-1}=2$ , infatti $4\cdot2=8\equiv1$ . $b=5$ , $d=11$ : $b^{-1}=9$ , infatti $5\cdot9=45=4\cdot11+1\equiv1$ . Divisione: $(8/4)\bmod5=(8\cdot4^{-1})\bmod5$ ; poiché $4^{-1}=4\pmod5$ ( $4\cdot4=16\equiv1$ ), $=(8\cdot4)\bmod5=2$ . Altri: $(8/3)\bmod5=1$ , $(11/4)\bmod5=4$ (verificati con Python). La divisione per 0 non è ammessa.

Definizione (logaritmo discreto). Se $b^a\equiv y\pmod d$ , allora $\log_b y=a$ è il logaritmo discreto. Non si conosce alcun algoritmo in tempo polinomiale per calcolarlo.

Esempio. $b=5$ , $d=7$ , $y=4$ : $5^a\equiv4\pmod7$ . Le potenze di 5 modulo 7 sono $5,4,6,2,3,1$ per $a=1,\dots,6$ : $5^2\equiv4$ , quindi $a=2$ . Con $d$ di 2048 bit non si può più provare.

Formula (generazione delle chiavi RSA).

Si scelgono due numeri primi grandi $p$ e $q$ .

Si calcola $N=p\,q$ .

Si calcola il totiente $\varphi(N)=(p-1)(q-1)$ , cioè quanti interi tra $1$ e $N-1$ sono coprimi con $N$ (motivazione sotto).

Si trova un intero positivo $e<\varphi(N)$ coprimo con $\varphi(N)$ , cioè $\gcd(e,\varphi(N))=1$ .

Si calcola $d=e^{-1}\bmod\varphi(N)$ .

$e^{-1}$ esiste, perché $e$ e $\varphi(N)$ sono coprimi; $e$ e $d$ sono uno l'inverso modulare dell'altro: $d\,e\equiv1\pmod{\varphi(N)}$ (per costruzione: proprietà P1).

Chiave pubblica di Bob: $PK=(N,e)$ , comunicata a chiunque voglia scrivergli. Chiave segreta: $SK=(N,d)$ ; le informazioni segrete sono la quaterna $SI=(p,q,d,\varphi(N))$ , che non va condivisa con nessuno.

Formula (cifratura e decifratura RSA). Bob manda a Alice $PK=(N,e)$ . Alice cifra il messaggio $m$ (con $m<N$ ): $c=\text{Enc}(m,PK)=m^e\bmod N$ . Bob decifra con la chiave segreta: $m=\text{Dec}(c,SK)=c^d\bmod N$ . Il blocco di messaggio può essere al massimo lungo quanto $N$ .

Esempio completo (numeri piccoli). $p=61$ , $q=53$ : $N=3233$ , $\varphi(N)=60\cdot52=3120$ . Si prende $e=17$ (coprimo con $3120=2^4\cdot3\cdot5\cdot13$ , perché $17$ è primo e non compare tra i fattori) e $d=e^{-1}\bmod3120=2753$ (calcolato con Euclide esteso nella sezione sopra), perché $17\cdot2753=46801=15\cdot3120+1\equiv1$ . Messaggio $m=65$ : $c=65^{17}\bmod3233$ . Con le potenze ripetute ( $17=10001_2=16+1$ , ogni valore è il quadrato del precedente ridotto modulo $3233$ ): $65^2\equiv992$ , $65^4\equiv1232$ , $65^8\equiv1547$ , $65^{16}\equiv789$ , quindi $65^{17}=65^{16}\cdot65\equiv789\cdot65=51285=15\cdot3233+2790\equiv\mathbf{2790}$ (per esempio l'ultimo quadrato è $1547^2=2393209=740\cdot3233+789$ ). Decifratura: $2790^{2753}\bmod3233=65$ (verificato con Python; verificato anche $65^{3120}\equiv1$ ). Chiave pubblica $(3233,17)$ , segreta $(3233,2753)$ ; il messaggio deve essere minore di 3233.

Definizione (SSL/TLS). SSL e TLS (Secure Socket Layer, Transport Layer Security) sono protocolli crittografici che garantiscono una comunicazione affidabile in rete. SSL (3.0) è ancora usato ma ha vulnerabilità note (POODLE) e se ne sconsiglia l'uso; TLS è la versione più recente e più sicura, ed è quella raccomandata. Sono progettati per funzionare con TCP (TCP - connessione, affidabilità e controllo di flusso) e usano i certificati per stabilire un collegamento cifrato tra client e server.

Firewall

Definizione (firewall). Parte di un sistema informatico o di una rete progettata per fermare il traffico non autorizzato che passa da una rete a un'altra. Può essere realizzato in hardware o in software (o in una combinazione). Filtra i dati, reindirizza il traffico, protegge dagli attacchi.

Definizione (esiti possibili). Un pacchetto che attraversa un firewall può avere tre esiti: accettato (accepted, può entrare nella rete o nell'host attraverso il firewall); negato (denied, non gli è permesso entrare dall'altra parte); rifiutato (rejected: come negato, più il tentativo di avvisare la sorgente che è stato negato, con un messaggio ICMP, Protocollo ICMP).

Proprietà (intervalli di porte). Il numero di porta ha 16 bit, quindi i valori possibili sono $2^{16}=65\,536$ , da $0$ a $65\,535$ (Sistemi di numerazione posizionali).

tipo intervallo usate da

porte note (well-known) 0-1023 server (servizi critici)

porte registrate 1024-49151 applicazioni registrate

porte effimere (ephemeral) 49152-65535 client (di breve durata)

tipo	intervallo	usate da
porte note (well-known)	0-1023	server (servizi critici)
porte registrate	1024-49151	applicazioni registrate
porte effimere (ephemeral)	49152-65535	client (di breve durata)

Esempio. Un server SMTP ascolta sulla porta 25 (nota); un client che gli scrive usa una porta sorgente effimera, per esempio 51034. Per questo nelle regole si scrive "porta sorgente $>1023$ " per i client. Nelle slide la regola " $>1023$ " include tutte le porte non note (Livello di trasporto - porte e multiplexing).

Definizione (stateful firewall). Un firewall con stato segue lo stato del traffico, controllando tutte le interazioni di una connessione finché non è chiusa. Trattiene i pacchetti finché ha informazioni sufficienti per decidere, in base al contesto.

Esempio. Si vuole: permettere il traffico HTTP degli host esterni (porta TCP server 80); permettere agli host interni di iniziare HTTP (TCP 80) o DNS (UDP 53); non permettere altre comunicazioni.

Definizione (firewall applicativo). Controlla input, output e accesso da e verso una specifica applicazione. Gli altri firewall ispezionano il traffico fino al livello di trasporto; questo ispeziona il traffico del livello applicazione.

VPN

Definizione (VPN). Una rete privata virtuale (Virtual Private Network) è una rete privata costruita sopra una rete pubblica (per esempio Internet). I nodi di una VPN comunicano nella rete pubblica in modo sicuro, come se fossero in una rete privata.

Esempio d'uso. Con una VPN i dipendenti possono accedere in sicurezza all'intranet dell'azienda mentre viaggiano, e le aziende possono estendere la loro rete privata nel mondo.

Definizione (tunnel IP). Il pacchetto reale tra i due estremi del tunnel porta come carico un altro pacchetto IP: quello da proteggere (per esempio i pacchetti da e verso una rete privata). Il tunnel attraversa una rete pubblica come Internet; il traffico dentro il tunnel è protetto.

Esempio. Il tunnel collega due reti private; $U$ (rete 10.0.7.0/24) manda un pacchetto a $V$ (rete 10.0.8.0/24). Sulla rete pubblica viaggia un pacchetto con indirizzi dei due estremi del tunnel, per esempio 198.51.100.7 $\to$ 203.0.113.1, il cui carico (cifrato) contiene il pacchetto originale 10.0.7.5 $\to$ 10.0.8.9. Chi osserva Internet vede solo il traffico tra i due estremi. Perché $U$ affida il pacchetto al client VPN: con la maschera /24 l'indirizzo di $V$ , 10.0.8.9 AND 255.255.255.0 $=$ 10.0.8.0, è diverso dalla rete di $U$ (10.0.7.0), quindi $U$ lo manda al gateway di default, che è il client VPN (Subnetting e supernetting, Instradamento e inoltro).

Grafico interattivo: Efficienza di un tunnel ESP in funzione della lunghezza L del pacchetto interno: η = L/(L + 58), senza contare il riempimento (fino a 15 byte in più). I pacchetti piccoli sprecano metà della banda

Definizione (modo tunnel). L'intero pacchetto IP originale è incapsulato e diventa il carico di un nuovo pacchetto IP: sopra il pacchetto originale si aggiunge una nuova intestazione IP. Protegge l'intero pacchetto IP. È utile per proteggere il traffico tra reti diverse: il pacchetto viaggia con una nuova intestazione IP e i router intermedi non vedono nulla del pacchetto originale. Semplifica la procedura di scambio delle chiavi.

Definizione (modo trasporto). Mantiene l'intestazione IP originale. Svantaggio: l'intestazione IP non è protetta, quindi permette l'analisi del traffico. Si usa per la comunicazione end-to-end tra due host che hanno già stabilito un tunnel IPsec sicuro. Non crea una nuova intestazione IP: il procedimento è meno complesso dell'incapsulamento.

Esempio. La sede A (10.1.0.0/16) e la sede B (10.2.0.0/16) hanno un tunnel ESP in modo tunnel tra i router di bordo (203.0.113.1 e 203.0.113.2). Un pacchetto 10.1.0.5 $\to$ 10.2.0.9 (con la maschera /16, 255.255.0.0, 10.2.0.9 AND maschera $=$ 10.2.0.0: non è nella rete 10.1.0.0/16 di partenza, quindi va al gateway di default, il router di bordo) esce dalla sede A con una nuova intestazione 203.0.113.1 $\to$ 203.0.113.2 e protocollo 50: all'esterno si vede solo il traffico tra i due gateway, non gli indirizzi interni.

Proprietà (compiti della coppia client-server VPN).

stabilire un tunnel sicuro tra i due;

inoltrare nel tunnel i pacchetti IP che devono andare dall'altra parte della VPN;

dopo aver ricevuto un pacchetto IP dall'altra estremità del tunnel, rilasciarlo nella rete privata.

Esempio. Reti: principale 10.0.8.0/24 con l'host $V$ , satellite 10.0.7.0/24 con l'host $U$ . $U$ manda un pacchetto a $V$ :

12. Laboratorio

Katharà - emulare una rete

Definizione (simulazione e emulazione). Un simulatore riproduce le prestazioni di un sistema reale (ritardi, perdite di pacchetti) con un modello. Un emulatore riproduce le funzionalità (configurazioni, architetture, protocolli): i programmi che girano sono quelli veri, ma poca attenzione è data alle prestazioni.

Esempio. Su Katharà un ping tra due container risponde in meno di 1 ms perché i container sono sulla stessa macchina: i tempi non sono quelli di un collegamento vero, e infatti nel laboratorio non si misurano ritardi ma si controlla se i pacchetti arrivano e per dove passano.

Definizione (dispositivo emulato e dominio di collisione). Ogni dispositivo ha: una console (una finestra di terminale), una memoria, un filesystem proprio e zero, una o più interfacce di rete (eth0, eth1, ...). Ogni interfaccia si collega a un dominio di collisione (collision domain) virtuale, indicato con una lettera o un nome (A, B, MYNET...), e ogni dominio di collisione può collegare più interfacce.

Esempio. Se pc1.eth0 e pc2.eth0 sono collegate al dominio A, i due host stanno sulla stessa rete locale e si vedono direttamente, come se fossero attaccati allo stesso hub. Per questo, in Katharà, non si aggiungono hub o switch: basta mettere più interfacce sullo stesso dominio.

Definizione (laboratorio Katharà). Un laboratorio è una cartella che contiene: un file lab.conf con la topologia; per ogni dispositivo un file <nome>.startup (comandi eseguiti dentro il dispositivo subito dopo l'avvio); eventualmente una sottocartella <nome>/ per ogni dispositivo, il cui contenuto viene copiato nella radice / del filesystem di quel dispositivo.

Esempio. Il file pc1/foo/file.txt diventa /foo/file.txt dentro pc1. Nel laboratorio del firewall la cartella vpc/var/www/index.html mette la pagina web nel server vpc, e r1/etc/shadow fissa la password dell'utente root di r1.

Formula (sintassi di ifconfig). ifconfig <interfaccia> <indirizzo> netmask <maschera> broadcast <indirizzo di broadcast> [mtu <byte>] up. Equivale a ifconfig eth0 <indirizzo>/<lunghezza> up: la maschera può essere scritta come lunghezza del prefisso.

Esempio. Nella rete 10.0.0.0/24, la riga ifconfig eth0 10.0.0.1 netmask 255.255.255.0 broadcast 10.0.0.255 up equivale a ifconfig eth0 10.0.0.1/24 up: l'indirizzo broadcast è quello con tutti $1$ nella parte host, cioè $10.0.0.255$ (vedi Subnetting e supernetting).

Routing statico in Katharà

Proprietà (reti direttamente collegate). Quando un'interfaccia viene attivata, la rete a cui appartiene è inserita automaticamente nella tabella di instradamento. Tutte le altre reti vanno inserite a mano (o da un protocollo di instradamento). Vale per qualunque dispositivo IP, anche per i router veri.

Esempio. Con ifconfig eth0 195.11.14.5/24 up, pc1 ottiene la riga 195.11.14.0 * 255.255.255.0 U eth0: per questo vede r1 (195.11.14.1) ma non le interfacce 100.0.0.9 o 200.1.1.7. Allo stesso modo, anche r1 e r2 conoscono solo le proprie reti: r2 ha 100.0.0.8/30 su eth1 e 200.1.1.0/24 su eth0.

Definizione (rotta predefinita). Default route o default gateway: rotta con destinazione 0.0.0.0 e maschera 0.0.0.0 (cioè $0.0.0.0/0$ , che contiene tutti gli indirizzi). Si usa quando nessuna rotta più specifica corrisponde.

Esempio. Ora ping 100.0.0.9 da pc1 funziona: nessuna rotta specifica corrisponde, si usa quella predefinita, il pacchetto va al MAC di r1 (ARP sul gateway, vedi Protocollo ARP) e r1, che ha l'indirizzo 100.0.0.9 su eth1, risponde. Nella lezione si osserva che l'«interfaccia backbone» di r1 è raggiungibile.

Proprietà (raggiungibilità in due versi). Perché due nodi comunichino serve un percorso di andata e uno di ritorno: ogni router lungo la strada deve avere una rotta verso la destinazione e verso il mittente. Un ping senza risposta non dice che l'andata sia rotta: bisogna sniffare ai due estremi.

Esempio. La richiesta pc1 $\to$ r2 funziona perché pc1 ha il default verso r1 e r1 conosce la rete 100.0.0.8/30. La risposta r2 $\to$ pc1 non parte perché r2 non conosce 195.11.14.0/24.

Formula (sintassi di route add). route add -net <rete>/<prefisso> gw <next hop> dev <interfaccia>: «la rete <rete>/<prefisso> si raggiunge tramite <next hop> uscendo da <interfaccia>». Il next hop deve stare in una rete direttamente collegata all'interfaccia indicata.

Esempio. Su r2: rete 195.11.14.0 con prefisso $24$ , raggiungibile tramite $100.0.0.9$ (l'eth1 di r1) uscendo da eth1. Equivale a route add -net 195.11.14.0 netmask 255.255.255.0 gw 100.0.0.9 dev eth1.

Proprietà (TTL e router attraversati). Ogni router che inoltra un datagramma sottrae $1$ al TTL (vedi Datagramma IP e frammentazione e Protocollo ICMP). Se l'host di destinazione parte con $\text{TTL}=64$ , a destinazione arriva con $64-n$ , dove $n$ è il numero di router attraversati.

Esempio. La risposta di pc2 a pc1 passa per r2 e r1: $64-2=62$ , esattamente il ttl=62 della cattura. Verso un'interfaccia di r1 il TTL resta $64$ (nessun router attraversato, perché è r1 stesso a rispondere).

Proprietà (corrispondenza più specifica). Se più rotte corrispondono a un indirizzo di destinazione, il kernel usa quella con il prefisso più lungo (longest prefix match). La rotta predefinita ( $/0$ ) è la meno specifica e vince solo se non c'è altro.

Esempio. Su r2 un pacchetto per 195.11.14.5 corrisponde a 195.11.14.0/24 (prefisso $24$ ) e alla rotta predefinita, se ci fosse: vince la prima. Verifica: con /24, 195.11.14.5 AND 255.255.255.0 $=$ 195.11.14.0 (corrisponde); con /0 la maschera è 0.0.0.0 e qualunque indirizzo dà 0.0.0.0 (corrisponde sempre). I prefissi sono $24$ e $0$ , vince il più lungo, $24$ .

Proprietà (ARP risolve il prossimo salto). In ogni rete locale l'ARP chiede il MAC del prossimo nodo (gateway o destinazione finale). Gli indirizzi IP del pacchetto restano uguali per tutto il percorso, i MAC cambiano a ogni dominio.

Esempio. I MAC di Katharà si ricavano dall'IP (fe:fd più i quattro byte): 200.1.1.1 è FE:FD:C8:01:01:01, 100.0.0.10 è FE:FD:64:00:00:0A, 195.11.14.5 è FE:FD:C3:0B:0E:05 (verificato con Python). Conversione di ogni byte in esadecimale, dividendo per $16$ (Basi di numerazione e conversioni - binario, ottale ed esadecimale): $200=12\cdot16+8\to\text{C8}$ ; $100=6\cdot16+4\to\text{64}$ ; $10\to\text{0A}$ ; $195=12\cdot16+3\to\text{C3}$ ; $14\to\text{0E}$ ; $11\to\text{0B}$ .

Router CISCO

Formula (rotta statica Cisco). ip route <rete> <maschera> <next hop>: «per raggiungere <rete>/<maschera> si invia al <next hop>», con la maschera per esteso. La rotta predefinita è la rete 0.0.0.0 con maschera 0.0.0.0.

Esempio ( $x=2$ ). Su r1, per raggiungere la rete di pcD: ip route 192.168.52.0 255.255.255.0 192.168.32.2, cioè «la 192.168.52.0/24 si raggiunge tramite l'eno1 di pcC».

RIP in Katharà

Definizione (FRR). FRRouting è una suite libera di protocolli di instradamento per Linux. Implementa RIP (v1 e v2), OSPF (v2 e v3), IS-IS, BGP e altri. Deriva dal progetto Quagga, a sua volta derivato da Zebra.

Formula (metrica RIP). La metrica di una rete è il numero di router che si attraversano per raggiungerla, contando $1$ per le reti collegate e aggiungendo $1$ a ogni router che inoltra l'annuncio; $16$ significa irraggiungibile.

Esempio. r3 verso 100.0.0.0/24: $1$ (su r1) $+1$ (su r2) $+1$ (su r3) $=3$ , come in [120/3].

Proprietà (annunci predefiniti di RIP). Senza altre istruzioni, RIP annuncia le reti collegate delle sole interfacce su cui è attivo (network). redistribute connected costringe ad annunciare tutte le reti collegate. Il significato vale per qualunque protocollo, ma il comportamento predefinito no: alcuni protocolli (BGP, per esempio) non annunciano nulla se non lo si dice espressamente.

Esempio. Nel laboratorio RIP, r4 non ha RIP attivo su eth0 (100.2.0.1 non è in 100.1.0.0/16): con redistribute connected annuncia comunque 100.2.0.0/30, così r1 impara che dietro r4 c'è anche la rete verso r5.

Firewall con iptables in Katharà

Definizione (target). Azione di una regola. Nella tabella filter: ACCEPT (accetta), DROP (scarta in silenzio), REJECT (scarta e invia un errore al mittente, con --reject-with icmp-host-unreachable, icmp-net-unreachable, icmp-port-unreachable, ...), una catena definita dall'utente, RETURN (torna dalla catena utente), LOG (registra il pacchetto, non termina la catena, con --log-level e --log-prefix). Nella tabella nat: DNAT (cambia destinazione), SNAT (cambia sorgente), MASQUERADE (come SNAT, ma per indirizzo pubblico dinamico), REDIRECT (porta il pacchetto sul firewall).

Esempio. Con DROP un client che prova a collegarsi a una porta chiusa aspetta invano e va in timeout; con REJECT riceve subito un errore ICMP.

Formula (regola di filtro). iptables --table filter --append CATENA [criteri] --jump TARGET: aggiunge in coda alla catena una regola che applica il target ai pacchetti che soddisfano tutti i criteri.

Esempio. iptables --table filter --append INPUT --protocol tcp --destination-port 22 --jump ACCEPT accetta in ingresso i pacchetti TCP diretti alla porta $22$ (SSH).

Proprietà (politica restrittiva). Si parte con INPUT in DROP (si vieta tutto) e si aggiungono eccezioni per ciò che serve (whitelist). Il vantaggio è che tutto ciò che non è stato previsto resta chiuso.

Esempio. Qui: loopback, ping, SSH e le risposte alle conversazioni iniziate dalla macchina. Il servizio web resta chiuso da fuori.

Attacco man-in-the-middle

Definizione (telnet). Protocollo client-server per accedere a una macchina remota con un canale bidirezionale. Il client chiede utente e password di un account della macchina remota; se sono accettati, i comandi digitati vengono eseguiti sulla macchina remota come se si fosse collegati localmente. Tutto, utente e password compresi, viaggia in chiaro: chiunque veda il flusso può rubare le credenziali.

Esempio. telnet s1_server dal client e, dopo l'accesso, i comandi hostname (stampa s1_server), pwd (stampa /home/rdclab), ls -al (mostra i file della cartella, anche quelli nascosti): sembra tutto locale, ma sono eseguiti sul server. Il prompt passa da root@s1_client:/# a rdclab@s1_server:~$.

Proprietà (hub contro switch). Un hub (livello fisico) ripete il segnale in ingresso su tutte le altre porte, quindi ogni macchina collegata vede tutto il traffico. Uno switch (livello di collegamento) invia in genere i frame solo alla porta dove si trova la destinazione, dopo aver imparato gli indirizzi MAC (vedi LAN - Ethernet e Wi-Fi).

Esempio. Se s1_client (hub) parla con il server, s1_attacker riceve comunque tutti i frame sul proprio eth0; se s2_client (switch) parla con il server, s2_attacker non riceve nulla di quella conversazione.

Definizione (Follow TCP stream). Funzione di Wireshark che, da una cattura, estrae e riassembla il flusso di un protocollo in chiaro e lo mostra leggibile. Si usa selezionando un pacchetto della conversazione e scegliendo dal menu del tasto destro Follow $\to$ TCP Stream.

Esempio. Nel flusso i caratteri rossi sono quelli inviati dal client al server, quelli blu quelli del server verso il client; i byte non rappresentabili sono sostituiti da punti. Il flusso mostra, quasi identico, quello che si vedeva nel terminale del client, e quindi anche utente e password.

Definizione (attacco man-in-the-middle, MITM). L'attaccante si mette in mezzo ai due estremi di una conversazione (mittente e destinatario) facendo credere al destinatario di essere il mittente e al mittente di essere il destinatario. Può essere passivo (intercetta il flusso e lo inoltra al destinatario originale senza che nessuno si accorga di lui) o attivo (intercetta e modifica il flusso prima di inoltrarlo).

Esempio. Qui l'attacco è passivo: l'attaccante inoltra tutto senza cambiare nulla, il client e il server vedono una sessione telnet normale.

Definizione (ARP poisoning). Tecnica che reindirizza il traffico di due parti attraverso la macchina dell'attaccante, corrompendo le cache ARP dei bersagli con risposte ARP false inviate di continuo.