Datagramma IP e frammentazione

IPv4 (Internet Protocol version 4) è un protocollo senza connessione (connectionless, approccio a datagramma) e non affidabile: il servizio è best effort ("faccio del mio meglio"). Un pacchetto IPv4 può essere corrotto, perso, arrivare fuori ordine, subire ritardi e contribuire a congestionare la rete. Se serve affidabilità, IP va affiancato da un protocollo di trasporto affidabile come TCP (TCP - connessione, affidabilità e controllo di flussoTCP (Transmission Control Protocol) è il protocollo di trasporto con connessione e affidabile: trasforma il servizio senza connessione e inaffidabile di IP in un flusso di byte ordinato, senza errori né duplicati. La connessione si apre con l'handshake a tre vie (SYN, SYN+ACK, ACK) e si chiude con tre o quattro segmenti (FIN). I byte sono numerati: il numero di sequenza è quello del primo byte del segmento, il numero di ACK (cumulativo) è il prossimo byte atteso. Il mittente può inviare $\min(\text{rwnd},\text{cwnd})$ byte non ancora confermati; rwnd (finestra del ricevitore, in un campo di 16 bit) è il controllo di flusso. L'errore si gestisce con checksum, ACK, timeout di ritrasmissione (RTO) e ritrasmissione rapida dopo tre ACK duplicati. Per usare tutto il canale la finestra deve valere almeno il prodotto banda-ritardo (BDP); il throughput massimo è $\text{MSS}\cdot W_{\max}/\text{RTT}$.TCP - connessione, affidabilità e controllo di flusso →). IP si occupa di impacchettare, inoltrare e consegnare i pacchetti (Livello di rete e indirizzamento IPIl livello di rete (network layer) porta i datagrammi da host a host attraverso i router: incapsula (framing), sceglie il percorso (routing) e sposta il pacchetto da un ingresso a un'uscita del router (forwarding); in Internet lascia ai livelli superiori controllo d'errore, di flusso e di congestione. Un indirizzo IPv4 è di 32 bit, diviso in prefisso (rete, $n$ bit) e suffisso (host, $32-n$ bit). L'indirizzamento a classi (A, B, C, D, E) è obsoleto; oggi si usa quello senza classi (CIDR): data una notazione $a.b.c.d/n$ si ricavano $N=2^{32-n}$ indirizzi, indirizzo di rete (suffisso tutto 0) e di broadcast (suffisso tutto 1), oppure con la netmask: rete $=$ indirizzo AND maschera, broadcast $=$ indirizzo OR (NOT maschera).Livello di rete e indirizzamento IP →).

Un datagramma IP è fatto di intestazione (header) di 20-60 byte e carico utile (payload); la lunghezza totale va da 20 a 65 535 byte.

L'intestazione

Organizzata in parole da 32 bit (4 byte); i campi fissi occupano 20 byte, seguiti da al più 40 byte di opzioni.

• Version (4 bit): vale 4.
• HLen (header length, 4 bit): lunghezza dell'intestazione in parole da 4 byte. Serve al ricevente per sapere dove finisce l'intestazione e dove iniziano i dati. Minimo $0101_2=5$, cioè $5\cdot4=20$ byte; massimo con 4 bit $2^4-1=15$, cioè $15\cdot4=60$ byte.
• TOS (type of service) o DS: 8 bit, definiscono come trattare il datagramma: tre bit di precedenza (precedence) e bit per ritardo (D), throughput (T), affidabilità (R), costo (C).
• Total Length (16 bit): lunghezza totale (intestazione + dati) in byte: al massimo $2^{16}-1=65\,535$.
• TTL (time to live, 8 bit): un datagramma può smarrirsi in Internet, visitando le stesse reti all'infinito e creando traffico inutile. Il TTL limita il numero massimo di salti (router): viene diminuito di 1 a ogni inoltro; se arriva a 0 il datagramma viene scartato e il router può inviare un messaggio ICMP (Protocollo ICMPIPv4 non ha meccanismi per segnalare o correggere gli errori né per interrogare host e router: li fornisce l'ICMP (Internet Control Message Protocol), un protocollo di rete i cui messaggi viaggiano dentro datagrammi IP con campo Protocol $=1$. I messaggi sono di errore (destination unreachable, tipo 3; time exceeded, tipo 11; redirect, tipo 5; parameter problem, tipo 12), sempre inviati alla sorgente originale e con l'intestazione IP più i primi 8 byte del datagramma che ha causato l'errore, oppure di interrogazione (echo request 8 e reply 0, timestamp 13-14). ICMP segnala ma non corregge. Con l'echo si fanno ping (RTT) e scoperta dell'MTU (bit D, codice 4, payload massimo $1500-20-8=1472$ byte); con time exceeded e port unreachable si fa traceroute ($n+1$ messaggi con TTL crescente). Attacchi: smurf e redirect.Protocollo ICMP →, tipo 11).
• Protocol (8 bit): identifica il protocollo del livello superiore contenuto nel payload; è il campo che permette il multiplexing/demultiplexing a destinazione. Valori: $1$ = ICMP, $6$ = TCP, $17$ = UDP.
• Header Checksum (16 bit): IP non controlla gli errori nel payload, ma un errore nell'intestazione sarebbe grave (un indirizzo di destinazione corrotto consegna il pacchetto all'host sbagliato). Il checksum copre solo l'intestazione e va ricalcolato a ogni salto perché il TTL cambia. È il complemento a uno della somma (in aritmetica del complemento a uno) di tutte le parole da 16 bit dell'intestazione, con il campo checksum posto a 0 durante il calcolo.
• Indirizzi sorgente e destinazione (32 bit ciascuno): non cambiano durante il viaggio. Le netmask non sono nell'intestazione: le forniscono gli amministratori o i server DHCP (Protocollo DHCPDopo che a un'organizzazione è stato assegnato un blocco di indirizzi, configurare a mano IP e netmask di ogni host non è efficiente. BOOTP (obsoleto) associa in modo statico un indirizzo MAC a un indirizzo IP; DHCP (Dynamic Host Configuration Protocol) assegna gli indirizzi in modo dinamico, a prestito (lease) per un tempo limitato, anche a sistema operativo già avviato. Il dialogo client-server è su UDP (porta 67 server, 68 client) e usa quattro messaggi: DHCPDISCOVER, DHCPOFFER, DHCPREQUEST, DHCPACK (più DHCPRELEASE a fine uso). Nell'ACK arrivano IP, netmask, default gateway e server DNS.Protocollo DHCP →) e vanno nelle tabelle di instradamento (Instradamento e inoltroL'inoltro (forwarding) mette il pacchetto sulla strada verso la destinazione, un salto alla volta (hop by hop). Se la destinazione è nella stessa rete del mittente l'inoltro è diretto (si usa l'ARP per il MAC del destinatario), altrimenti è indiretto: il pacchetto va al router successivo (next hop) indicato dalla tabella di instradamento, o al default gateway. Con le netmask: l'inoltro è diretto attraverso l'interfaccia $x$ se $\text{IP(dst)}\ \text{AND}\ \text{NM}(x)=\text{IP}(x)\ \text{AND}\ \text{NM}(x)$; altrimenti si scorre la tabella dalla maschera più lunga (longest prefix match) e si usa il primo match. La riga con rete $0.0.0.0$ e maschera $0.0.0.0$ (default route) corrisponde sempre. L'aggregazione di rotte (route aggregation) riduce la tabella, e nell'inoltro con etichette (MPLS) la tabella si consulta per indice.Instradamento e inoltro →).
• Opzioni (fino a 40 byte, per il limite di HLen): servono per prove e diagnostica della rete.

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 esadecimaleogni cifra esadecimale vale 4 bit e le cifre vanno da 0 a 9 e da A a F, dove A=10, B=11, C=12, D=13, E=14, F=15Basi di numerazione e conversioni - binario, ottale ed 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 binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.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).

Esempi rapidi sui campi

• Un pacchetto arriva con primo byte $01000010$. Versione $0100=4$ ✓, HLen $0010=2$, cioè $2\cdot4=8<20$ byte: non valido, il ricevente lo scarta (pacchetto corrotto).
• HLen $=1000_2=8$: intestazione di $8\cdot4=32$ byte, cioè 20 di base e 12 di opzioni.
• HLen $=5$ e Total Length $=0028_{16}=40$: intestazione di 20 byte, quindi $40-20=20$ byte di dati.
• Un pacchetto con MF $=0$: è l'ultimo frammento; ma da solo non dice se il datagramma era frammentato (bisogna guardare l'offset).
• MF $=1$ e offset $=0$: è il primo frammento (ne seguono altri, nessuno prima).
• Offset $=100$, HLen $=5$, Total Length $=100$: primo byte $100\cdot8=800$; dati $=100-20=80$ byte, quindi l'ultimo byte è il numero $800+80-1=879$.

MTU e frammentazione

Un datagramma può attraversare reti diverse. Ogni router estrae il datagramma dal frame che riceve, lo elabora e lo reincapsula in un frame del collegamento d'uscita; ogni tecnologia di collegamento ha un proprio formato e un limite alla dimensione del carico utile del frame.

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

Se un datagramma è più grande dell'MTU del collegamento d'uscita, viene frammentato (fragmented):

• si divide solo il payload; l'intestazione (tranne alcune opzioni) viene copiata in ogni frammento;
• un frammento può essere a sua volta frammentato se incontra una rete con MTU ancora più piccola;
• il router (o l'host) che frammenta modifica tre campi: Flags, Fragment Offset e Total Length (e ricalcola il checksum);
• il riassemblaggio avviene solo a destinazione: i router non ricompongono.

I campi che gestiscono la frammentazione:

• Identification (16 bit): uguale per tutti i frammenti dello stesso datagramma; il destinatario ricompone insieme i frammenti con la stessa identificazione.
• Flags (3 bit): R riservato (non usato); D (don't fragment): se il datagramma non passa su una rete per via dell'MTU, viene scartato e si manda un errore alla sorgente (Protocollo ICMPIPv4 non ha meccanismi per segnalare o correggere gli errori né per interrogare host e router: li fornisce l'ICMP (Internet Control Message Protocol), un protocollo di rete i cui messaggi viaggiano dentro datagrammi IP con campo Protocol $=1$. I messaggi sono di errore (destination unreachable, tipo 3; time exceeded, tipo 11; redirect, tipo 5; parameter problem, tipo 12), sempre inviati alla sorgente originale e con l'intestazione IP più i primi 8 byte del datagramma che ha causato l'errore, oppure di interrogazione (echo request 8 e reply 0, timestamp 13-14). ICMP segnala ma non corregge. Con l'echo si fanno ping (RTT) e scoperta dell'MTU (bit D, codice 4, payload massimo $1500-20-8=1472$ byte); con time exceeded e port unreachable si fa traceroute ($n+1$ messaggi con TTL crescente). Attacchi: smurf e redirect.Protocollo ICMP →, destinazione irraggiungibile, codice 4); M (more fragments): $1$ se il frammento non è l'ultimo.
• Fragment Offset (13 bit): posizione relativa del frammento nel datagramma originale, misurata in unità di 8 byte: 13 bit per coprire fino a $2^{13}\cdot8=65\,536$ byte. Conseguenza: tutti i frammenti tranne l'ultimo devono avere un payload multiplo di 8.

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

Come nasce la formula. Ogni frammento ha una sua intestazione di $h$ byte, quindi dei $m$ byte che il collegamento può trasportare ne restano $m-h$ per i dati. Questo numero va però arrotondato per difetto a un multiplo di 8, perché l'offset si esprime in unità di 8 byte: un payload non multiplo di 8 renderebbe impossibile indicare dove comincia il frammento successivo (da qui $8\lfloor(m-h)/8\rfloor$). La scelta delle unità da 8 byte non è casuale: l'offset ha 13 bit e può valere al massimo $2^{13}-1=8191$; moltiplicato per 8 copre $8191\cdot8=65\,528$ byte di posizione iniziale, cioè tutto un datagramma da $65\,535$ byte (con offset in byte ne servirebbero 16). Il numero di frammenti è un arrotondamento per eccesso ($\lceil\cdot\rceil$) perché anche un ultimo frammento quasi vuoto conta come frammento.

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.

Tutti hanno la stessa Identification (nell'esempio delle slide, $14567$, scelto a caso). Si ricostruisce così:

• datagramma non frammentato: MF $=0$ e offset $=0$;
• primo frammento: MF $=1$, offset $=0$ (altri frammenti in arrivo, nessuno prima);
• ultimo frammento: MF $=0$, offset $\neq0$ (nessun altro dopo, ma ce ne sono prima);
• frammenti dello stesso datagramma: stessa Identification;
• l'offset si calcola con solo i dati contenuti nei frammenti precedenti.

Quali campi cambiano con la frammentazione: Total Length, Flags (MF), Fragment Offset, Header Checksum sempre; HLen e Opzioni solo se alcune opzioni non vengono copiate nei frammenti; non cambiano Version, TOS, Identification, Protocol, indirizzi, e il TTL cambia soltanto perché diminuisce a ogni salto come per qualunque inoltro.

Esempio (quanti frammenti). Pacchetto di $20\,000$ byte (Total Length), $m=400$. $P=20\,000-20=19\,980$; $m-h=400-20=380$, che non è multiplo di 8 ($380/8=47{,}5$), quindi si scende a $p_{\max}=8\lfloor380/8\rfloor=8\cdot47=376$ (i 4 byte di differenza restano inutilizzati in ogni frammento). Frammenti: $\lceil19\,980/376\rceil=\lceil53{,}14\rceil=54$: $53$ da $376$ byte e uno da $19\,980-53\cdot376=52$ byte. (Dividere semplicemente $20\,000/400=50$ non è corretto: i 20 byte di intestazione si ripetono in ogni frammento e il payload deve essere multiplo di 8.) Altro caso, Esercizio - piano di indirizzamento e inoltro con MTU (tema d'esame): $18\,000$ byte con $m=1500$ danno $\lceil17\,980/1480\rceil=13$ frammenti (12 da $1480$ byte e uno da $220$).

Problemi della frammentazione

• Se un frammento si perde, tutti gli altri sono inutili: il datagramma intero va ritrasmesso (e IP non se ne occupa; il trasporto, che non vede la frammentazione, può recuperare un datagramma intero ma non il singolo frammento).
• Un solo frammento in ritardo può causare la perdita dell'intero datagramma; allo scadere di un timer di riassemblaggio la destinazione manda un ICMP tipo 11, codice 1.

È meglio evitare la frammentazione: se l'MTU è nota, basta non superarla quando si crea il PDU (con TCP si imposta l'MSS, TCP - connessione, affidabilità e controllo di flussoTCP (Transmission Control Protocol) è il protocollo di trasporto con connessione e affidabile: trasforma il servizio senza connessione e inaffidabile di IP in un flusso di byte ordinato, senza errori né duplicati. La connessione si apre con l'handshake a tre vie (SYN, SYN+ACK, ACK) e si chiude con tre o quattro segmenti (FIN). I byte sono numerati: il numero di sequenza è quello del primo byte del segmento, il numero di ACK (cumulativo) è il prossimo byte atteso. Il mittente può inviare $\min(\text{rwnd},\text{cwnd})$ byte non ancora confermati; rwnd (finestra del ricevitore, in un campo di 16 bit) è il controllo di flusso. L'errore si gestisce con checksum, ACK, timeout di ritrasmissione (RTO) e ritrasmissione rapida dopo tre ACK duplicati. Per usare tutto il canale la finestra deve valere almeno il prodotto banda-ritardo (BDP); il throughput massimo è $\text{MSS}\cdot W_{\max}/\text{RTT}$.TCP - connessione, affidabilità e controllo di flusso →). Tutte le reti collegate a Internet devono garantire un MTU di almeno 576 byte (per questo molti datagrammi avevano quella dimensione). La dimensione tipica è 1500 byte per l'MTU Ethernet: payload massimo del frame 1500, datagramma IP massimo 1500, payload IP massimo 1480. La scoperta dell'MTU di un cammino con il ping e il bit D è in Protocollo ICMPIPv4 non ha meccanismi per segnalare o correggere gli errori né per interrogare host e router: li fornisce l'ICMP (Internet Control Message Protocol), un protocollo di rete i cui messaggi viaggiano dentro datagrammi IP con campo Protocol $=1$. I messaggi sono di errore (destination unreachable, tipo 3; time exceeded, tipo 11; redirect, tipo 5; parameter problem, tipo 12), sempre inviati alla sorgente originale e con l'intestazione IP più i primi 8 byte del datagramma che ha causato l'errore, oppure di interrogazione (echo request 8 e reply 0, timestamp 13-14). ICMP segnala ma non corregge. Con l'echo si fanno ping (RTT) e scoperta dell'MTU (bit D, codice 4, payload massimo $1500-20-8=1472$ byte); con time exceeded e port unreachable si fa traceroute ($n+1$ messaggi con TTL crescente). Attacchi: smurf e redirect.Protocollo ICMP →.