Instradamento e inoltro

L'instradamento (routing) calcola le tabelle (Algoritmi di instradamento - link state e distance vectorL'instradamento (routing) trova il percorso di costo minimo in un grafo pesato in cui i router sono nodi e le reti tra due router sono archi. Link state: ogni router diffonde con un flooding i pacchetti LSP sui propri collegamenti, ricostruisce tutto il grafo e applica Dijkstra (nodi con stato (distanza, permanente o temporaneo)). Distance vector: ogni router conosce solo i vicini e scambia con loro il proprio vettore delle distanze, aggiornato con Bellman-Ford $D_{A,w}=\min{D_{A,w},,D_{A,Y}+d_{Y,w}}$; converge in al più $n-1$ giri ma può soffrire del conteggio all'infinito (limite a 16, hold down, aggiornamenti immediati, split horizon con poison reverse). Path vector: ogni annuncio porta l'intero cammino, si sceglie per politica e non per costo, e i cicli si scoprono trovando sé stessi nel cammino. Dijkstra è corretto se i costi sono non negativi (invariante: un nodo permanente ha già la distanza vera); Bellman-Ford è corretto perché dopo $k$ giri conosce i cammini minimi con al più $k+1$ archi.Algoritmi di instradamento - link state e distance vector →, Protocolli di instradamento - RIP, OSPF e BGPIn Internet l'instradamento non si può fare con un solo protocollo, per scalabilità (tabelle troppo grandi) e per autonomia amministrativa: ogni ISP è un sistema autonomo (AS) con il proprio algoritmo. All'interno di un AS si usano i protocolli IGP: RIP (distance vector, numero di salti, massimo 15, aggiornamenti ogni circa 30 s, su UDP porta 520) e OSPF (link state con Dijkstra, aree collegate all'area 0, cinque tipi di LSA, messaggi direttamente in IP). Tra AS si usa BGP4 (path vector, su TCP porta 179, eBGP tra AS e iBGP dentro l'AS, scelta del percorso per politica: preferenza locale, AS-PATH più corto, origine; i cicli si evitano scartando i cammini che contengono già il proprio AS; quattro messaggi: Open, Keepalive, Notification, Update).Protocolli di instradamento - RIP, OSPF e BGP →); l'inoltro (forwarding) le usa pacchetto per pacchetto. Questa nota descrive l'inoltro: che cosa fa un host o un router quando deve spedire un datagramma IP (Datagramma IP e frammentazioneIPv4 è un servizio senza connessione, non affidabile, best effort: i pacchetti (datagrammi) possono essere persi, corrotti, riordinati o ritardati. L'intestazione ha 20-60 byte (HLen conta parole da 4 byte, da 5 a 15); il campo Total Length (16 bit) dà la lunghezza totale fino a 65 535 byte; TTL limita i salti, Protocol identifica il protocollo trasportato (1 ICMP, 6 TCP, 17 UDP), il checksum copre solo l'intestazione. Se un datagramma è più grande dell'MTU del collegamento viene frammentato: solo il payload si divide, ogni frammento ha un'intestazione propria; l'Offset (13 bit) è in unità di 8 byte, MF=1 in tutti i frammenti tranne l'ultimo, e il riassemblaggio avviene solo a destinazione.Datagramma IP e frammentazione →), come legge le tabelle e come tiene conto delle netmask (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 →).

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.

IP è nato come protocollo senza connessione (approccio a datagramma): in quel caso l'inoltro si basa sull'indirizzo di destinazione del datagramma. Oggi c'è la tendenza a un funzionamento orientato alla connessione (circuito virtuale), nel quale l'inoltro si basa su un'etichetta (label) attaccata al datagramma (vedi MPLS in fondo).

L'inoltro può essere diretto o indiretto.

Inoltro diretto

È il caso in cui la destinazione è nella rete locale di chi inoltra, quindi raggiungibile direttamente.

Esempio. $B$ ($\text{IP}_B=193.17.31.55$) vuole mandare un datagramma ad $A$ ($\text{IP}_A=193.17.31.45$); entrambi sono nella rete $193.17.31.0$.

1. $B$ confronta il NetID del proprio indirizzo con quello dell'indirizzo di destinazione: sono uguali, quindi $A$ è nella stessa rete locale.
2. $B$ cerca nella tabella ARP il MAC corrispondente a $\text{IP}_A$ (se non c'è lo chiede con una richiesta ARP: Protocollo ARPUn host ha tre «nomi»: nome DNS, indirizzo IP (rete) e indirizzo MAC (collegamento). Per spedire un datagramma IP in un frame serve il MAC del prossimo nodo, che si ottiene da quel nodo con ARP: richiesta in broadcast (MAC destinazione FF:FF:FF:FF:FF:FF, contiene IP e MAC del mittente e l'IP cercato) e risposta unicast con il MAC richiesto, memorizzata nella cache ARP. ARP risolve sempre il prossimo salto (host di destinazione o router), non la destinazione finale. Un broadcast non esce dalla sottorete: il proxy ARP del router risponde con il proprio MAC.Protocollo ARP →).
3. Il livello IP passa il datagramma al livello MAC, che costruisce un frame con $\text{MAC}_A$ come destinazione.

Il frame ha: indirizzo MAC sorgente $=\text{MAC}_B$, destinazione $=\text{MAC}_A$; datagramma IP con sorgente $\text{IP}_B$, destinazione $\text{IP}_A$.

Inoltro indiretto

La destinazione è su un'altra rete: serve almeno un altro salto. Quale? Lo dice la tabella di instradamento.

Esempio. $B$ ($193.17.31.55$) vuole spedire a $D$ con $\text{IP}_D=131.17.23.4$. Nella rete di $B$ c'è un router $C$ con indirizzo $193.17.31.254$.

1. $B$ confronta il NetID del proprio indirizzo con quello di $D$: non sono uguali.
2. $B$ deve consegnare il datagramma a un router di bordo: di solito ogni host è configurato con l'indirizzo IP di un default gateway, il router che si occuperà di instradare il pacchetto verso la rete di destinazione.
3. $B$ trova nella tabella ARP il MAC del default gateway.
4. Il livello MAC costruisce il frame e lo spedisce al router.

Il frame ha: MAC sorgente $\text{MAC}_B$, MAC destinazione $\text{MAC}_C$ (il router, non $D$); datagramma IP con sorgente $\text{IP}_B$ e destinazione $\text{IP}_D$.

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.

Nel caso di inoltro indiretto il mittente deve conoscere l'indirizzo IP del default gateway: lo ottiene dal messaggio DHCPACK (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 →), insieme alla netmask e al server DNS.

Router, interfacce e configurazione

Un router ha più interfacce (di uscita), ciascuna con un proprio indirizzo IP. La configurazione di un'interfaccia richiede indirizzo IP e netmask. Ogni router ha:

• la tabella di instradamento (routing table): contiene gli indirizzi delle reti di destinazione con le relative netmask e il next hop;
• la configurazione delle interfacce: l'elenco delle reti raggiungibili direttamente (dove si può consegnare senza altri router).

Esempio. Un router $R$ con eth0 $=145.170.123.76/25$ ed eth1 $=145.170.124.169/25$. L'indirizzo di rete di ciascuna interfaccia si ottiene con l'AND con la maschera ($255.255.255.128$):

• eth0: $145.170.123.76\ \text{AND}\ 255.255.255.128=145.170.123.0$ (perché $76=01001100_2$, con 7 bit di host in questo ultimo byte si tiene solo il primo bit, $0$, quindi $0$);
• eth1: $145.170.124.169\ \text{AND}\ 255.255.255.128=145.170.124.128$ (perché $169=10101001_2$, si tiene il primo bit, $1$, quindi $128$).

Le due reti sono $145.170.123.0/25$ e $145.170.124.128/25$.

La decisione di inoltro con le netmask

Un pacchetto da inoltrare viene trattato in due fasi, nell'ordine.

Fase 1: inoltro diretto (si guarda la configurazione delle interfacce)

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.

Fase 2: inoltro indiretto (si guarda la tabella di instradamento)

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

Regola (corrispondenza della maschera più lunga, longest prefix match). Si esaminano le righe a partire da quella con la netmask più lunga (attenzione: la tabella non è necessariamente ordinata): per ogni riga si calcola $\text{IP}_{\text{dst}}\ \text{AND}\ \text{NM}_{\text{riga}}$ e si confronta con l'indirizzo di rete della riga; la prima che corrisponde decide il next hop.

Perché la maschera più lunga. Una riga con prefisso più lungo descrive un gruppo di indirizzi più piccolo e quindi più preciso: se la destinazione appartiene a più righe (per esempio $131.180.21.78$ sta sia in $131.180.21.0/24$ sia in $131.180.0.0/16$) la riga più specifica contiene un'informazione più mirata, come "tutta la Francia" contro "Parigi" per una lettera diretta a Parigi. Le righe sono quindi annidate come insiemi: l'insieme di indirizzi del $/24$ è contenuto in quello del $/16$, e si sceglie il più piccolo che contenga la destinazione. Come si esegue l'AND: lo si fa byte per byte; un byte di maschera $255$ lascia passare il byte dell'indirizzo, un byte $0$ lo azzera, e solo il byte "di confine" (per esempio $128$ in $255.255.255.128$) richiede di scrivere il numero in binario (AND bit a bitAND vale 1 solo se entrambi i bit valgono 1Algebra di Boole e porte logiche →).

Regola (default gateway o default route). L'ultima riga ha rete $0.0.0.0$ e netmask $0.0.0.0$: corrisponde a qualsiasi indirizzo (la maschera è tutta a zero, quindi l'AND dà sempre $0.0.0.0$). Viene usata per tutte le destinazioni che non corrispondono a nessuna riga precedente; è la più corta delle maschere, quindi si prova per ultima.

Pseudocodice dell'intero procedimento:

inoltra(pacchetto):
    per ogni interfaccia x:
        se IP_dst AND NM(x) == IP(x) AND NM(x):  consegna direttamente (ARP) su x;  fine
    ordina le righe della tabella per netmask decrescente
    per ogni riga r:
        se IP_dst AND NM(r) == rete(r):  next hop = r.nexthop;  trova l'interfaccia della rete del next hop;  fine
    (la riga di default corrisponde sempre, quindi si arriva sempre a una riga)

Esempio completo

Router con interfacce eth0 $=131.175.21.254/24$ (rete $131.175.21.0$) ed eth1 $=131.175.12.254/24$ (rete $131.175.12.0$) e tabella:

• $131.175.21.86$. Con eth0: $131.175.21.86\ \text{AND}\ 255.255.255.0=131.175.21.0$, uguale alla rete di eth0: inoltro diretto da eth0 (non si guarda neanche la tabella).
• $131.175.16.65$. Con eth0: $131.175.16.0\neq131.175.21.0$. Con eth1: $131.175.16.0\neq131.175.12.0$. Nessuna corrispondenza: inoltro indiretto. Righe a maschera /24 in ordine: la prima ($131.175.15.0$) no, perché $131.175.16.65\ \text{AND}\ 255.255.255.0=131.175.16.0\ne131.175.15.0$; la seconda sì ($131.175.16.0$). Next hop $131.175.21.2$, che appartiene alla rete di eth0: si usa eth0.
• $131.180.21.78$. Nessun match diretto. Tra le righe /24: $131.180.23.0$ no, $131.180.18.0$ no, $131.180.21.0$ sì: next hop $131.175.21.4$. Anche la riga $131.180.0.0/16$ corrisponderebbe, ma ha la maschera più corta e non viene considerata.
• $131.180.5.9$ (variante). Nessun match tra le /24; la riga /16 ($131.180.0.0$) corrisponde: next hop $131.175.21.5$.
• $200.45.21.84$. Nessun match diretto e nessuna riga specifica: si usa la default route, next hop $131.175.12.254$ (rete di eth1).

Attenzione alla maschera giusta

Con i confronti conta la maschera di quella riga o interfaccia. Esempio con una tabella di tipo (rete, netmask, interfaccia): $180.70.65.192/26\to m_2$, $180.70.65.128/25\to m_0$, $201.4.22.0/24\to m_3$, $201.4.16.0/22\to m_1$, default via $180.70.65.200$. Destinazione $180.70.65.140$:

• con la riga /26: $140=10001100_2$, con 6 bit di host si tengono i primi 2 bit, $10$, quindi $128$: $180.70.65.128\ne180.70.65.192$, nessun match;
• con la riga /25: si tiene solo il primo bit, $1$, quindi $128$: $180.70.65.128$ = rete della riga: match, uscita $m_0$.

Partendo dalla maschera più lunga si prova prima la /26, che non corrisponde, e poi la /25, che corrisponde: l'uscita è $m_0$. Se si confrontasse con la maschera sbagliata (per esempio la /26 con la rete della riga /25) si concluderebbe a torto che non c'è corrispondenza.

Il grafico mostra gli intervalli dell'ultimo byte coperti dalle due righe: il /25 copre $128$-$255$, il /26 solo $192$-$255$ (contenuto nel /25). La destinazione $140$ cade nel /25 ma non nel /26.

Casi particolari

• Indirizzo di broadcast della rete d'arrivo. Un pacchetto con destinazione $131.175.123.255$ arrivato dall'interfaccia eth0 ($131.175.123.235/25$) è il broadcast diretto della rete di eth0: non va inoltrato (si è già nella rete) Esercizio - inoltro diretto e indiretto con router a tre interfacce.
• Indirizzi $0.0.0.x$. $0.0.0.132$ significa "l'host 132 di questa rete" (unicast dentro la sottorete): il router lo scarta.
• Next hop sulla stessa interfaccia di arrivo. Se la tabella dice di mandare il pacchetto a un router che sta nella stessa rete da cui il pacchetto è arrivato, il router non lo inoltra come normale: il mittente avrebbe potuto raggiungerlo direttamente. In pratica il router manda al mittente un messaggio ICMP di redirect (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 →).
• TTL. A ogni inoltro il router decrementa il TTL del datagramma; se arriva a 0 lo scarta e invia un messaggio ICMP di tempo scaduto.

Esercizi svolti: Esercizio - tabella di instradamento del router R1 e inoltro di due pacchetti, Esercizio - tabelle di inoltro e instradamento dei router A e B, Esercizio - inoltro diretto e indiretto con router a tre interfacce, Esercizio - piano di indirizzamento con cinque router e collegamenti punto-punto.

Aggregazione delle rotte

Con gli indirizzi senza classi il numero di righe delle tabelle tende ad aumentare, perché lo scopo dell'indirizzamento senza classi è dividere lo spazio in blocchi gestibili. Tabelle più lunghe richiedono più tempo di ricerca (con una scansione riga per riga il costo cresce in proporzione al numero $n$ di righe, cioè è $O(n)$: Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →; i router reali usano strutture dati più veloci, ma ridurre le righe resta utile). L'indirizzamento gerarchico con aggregazione delle rotte (route aggregation) permette di annunciare le informazioni di instradamento in modo efficiente (Subnetting e supernettingIl subnetting divide un blocco di indirizzi in sottoblocchi più piccoli allungando la maschera ($n_{\text{sub}}=n_{\text{rete}}+s$, con $2^s$ sottoreti); il supernetting (aggregazione CIDR) fa l'opposto, accorciando il prefisso per unire blocchi contigui in uno più grande. Regole di progetto: ogni sottorete ha un numero di indirizzi potenza di 2 ($M=2^k\ge$ host richiesti $+2$), prefisso $n=32-k$, indirizzo iniziale multiplo di $M$; si assegnano prima le sottoreti più grandi. Per aggregare $2^j$ blocchi di prefisso $n$ servono blocchi contigui il cui primo indirizzo sia multiplo della dimensione dell'aggregato, e il nuovo prefisso è $n-j$.Subnetting e supernetting →).

Esempio. Il router $R_1$ è collegato a quattro organizzazioni, ciascuna con 64 indirizzi (maschera con 26 uni, 6 bit di host): $140.24.7.0/26$, $140.24.7.64/26$, $140.24.7.128/26$, $140.24.7.192/26$. $R_1$ ha una tabella più lunga, perché deve instradare correttamente ogni pacchetto verso l'organizzazione giusta (quattro righe /26). Il router $R_2$, lontano da $R_1$, ha bisogno di una sola riga: qualunque pacchetto con destinazione $140.24.7.0/24$ esce dall'interfaccia $m_0$, indipendentemente dall'organizzazione. I quattro blocchi sono aggregati in uno solo ($4\times64=256$ indirizzi, cioè il $/24$). $R_2$ avrebbe una tabella più lunga se i blocchi delle organizzazioni non fossero aggregabili in un blocco unico (condizioni: contigui, in numero potenza di 2, primo indirizzo multiplo della dimensione dell'aggregato).

Quando è possibile si aggregano i NetID per semplificare la tabella; negli Interior Gateway si possono aggregare quattro reti ma non le altre quattro (il blocco non è unico). Con l'aggregazione continua a funzionare l'instradamento grazie alla regola del prefisso più lungo: una riga più specifica (per un'eccezione, per esempio un cliente che si sposta) vince sempre su quella aggregata.

Inoltro con etichette: MPLS

Negli anni '80 l'instradamento ha cominciato a essere affiancato dalla commutazione (switching): serve una rete orientata alla connessione (circuiti virtuali, Commutazione di circuito e di pacchettoUn nodo di commutazione (switch) può collegare ingresso e uscita in tre modi. Commutazione di circuito: si stabilisce prima un collegamento fisico dedicato (rete telefonica), tempo di consegna $T=3Nt_p+Nt_s+M/R$. Commutazione di pacchetto a datagramma: il messaggio è diviso in $K$ pacchetti con intestazione, ognuno è instradato indipendentemente con store-and-forward, $T=Nt_p+(N+K-1)\frac{M/K+H}{R}$, con $K_{ott}=\sqrt{(N-1)M/H}$. A circuito virtuale: tre fasi (setup, dati, chiusura), connessione logica dedicata ma senza risorse dedicate, identificatore locale che cambia a ogni salto.Commutazione di circuito e di pacchetto →). Gli switch inoltrano in base a etichette (label) attaccate ai pacchetti. L'instradamento si basa sulla ricerca nella tabella (confronto di prefissi); la commutazione sull'accesso per indice, perché il circuito è già stato scelto dalla sorgente alla destinazione, e per questo è più veloce.

Per rendere IPv4 "simile a un servizio con connessione" si aggiungono le etichette per la scelta dell'interfaccia: il pacchetto IP è incapsulato in un pacchetto MPLS (Multi-Protocol Label Switching), un livello intermedio tra collegamento e rete, con un'intestazione di 32 bit che contiene un campo etichetta di 20 bit. La commutazione gerarchica si realizza in modo simile all'instradamento gerarchico (un pacchetto può avere più etichette).

Lab: l'inoltro e le tabelle di instradamento si provano in Routing statico in KatharàLaboratorio 2 (LAB2). Due LAN (195.11.14.0/24 e 200.1.1.0/24) sono unite da due router r1 e r2 collegati da una rete 100.0.0.8/30. Una interfaccia attiva inserisce da sola nella tabella di instradamento solo la rete direttamente collegata: per le altre servono rotte inserite a mano. I PC usano una rotta predefinita (route add default gw 195.11.14.1), i router rotte statiche (route add -net 195.11.14.0/24 gw 100.0.0.9 dev eth1). Senza la rotta di ritorno su r2 le richieste di ping arrivano ma le risposte no: la raggiungibilità vale solo se c'è un percorso in entrambi i versi. A configurazione finita ping da pc1 a pc2 risponde con ttl=62 (64 meno 2 router).Routing statico in Katharà →.