Protocolli di instradamento - RIP, OSPF e BGP

Gli algoritmi (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 →) dicono come calcolare le rotte; un protocollo di instradamento (routing protocol) implementa un tipo di algoritmo e definisce i pacchetti con cui i router si scambiano le informazioni. Questa nota presenta i tre protocolli del corso e la struttura gerarchica di Internet che li rende necessari. Come si usano le tabelle risultanti: 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 →.

Instradamento gerarchico e sistemi autonomi

In Internet l'instradamento non si può fare con un unico protocollo, per due motivi:

• Scalabilità. Per non far esplodere la dimensione delle tabelle serve una partizione gerarchica dei router di bordo (gateway).
• Autonomia amministrativa. Un'azienda o un ISP vuole (e deve) gestire da sé i propri router (per esempio, un ISP non vuole inoltrare traffico che non riguarda i suoi utenti).

L'instradamento gerarchico considera ogni ISP un sistema autonomo (autonomous system, AS).

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.

Ogni AS ha un identificativo unico (numero di AS), un altro piano di indirizzamento globale: è passato da 16 a 32 bit dal 2006 perché i 16 bit si stavano esaurendo. Non è strutturato; una parte è riservata a uso privato (sotto-AS dentro AS più grandi): i numeri da 64 512 a 65 534 sono privati. I blocchi sono assegnati dalla IANA ai registri regionali (Regional Internet Registries, RIR) in unità da 1024.

In un AS gestito da un solo ISP (anche se un ISP può dividere la rete in più AS interconnessi) i gateway interni (Interior Gateways, IG) usano un algoritmo che può essere diverso da AS ad AS. I gateway di bordo (Border Gateways, BG) collegano AS diversi e informano gli IG del proprio AS sugli indirizzi raggiungibili attraverso quel BG.

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

Classificazione dei protocolli:

RIP

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 UDPUDP (User Datagram Protocol) è il protocollo di trasporto senza connessione e inaffidabile: rispetto a IP aggiunge soltanto la comunicazione processo-processo (numeri di porta) e un controllo d'errore facoltativo. L'intestazione è di soli 8 byte (porta sorgente, porta destinazione, lunghezza, checksum). Il checksum copre pseudo-intestazione (indirizzi IP, protocollo 17, lunghezza), intestazione e dati, ed è il complemento a uno della somma a 16 bit; se vale 0 significa "non calcolato", e un risultato 0 si trasmette come 0xFFFF. UDP non ha connessione, numeri di sequenza, controllo di flusso, di errore né di congestione: si sceglie per i messaggi brevi (DNS, DHCP, RIP, SNMP) e per le applicazioni in tempo reale, dove conta non aggiungere ritardo.Protocollo UDP →).

Tabella di inoltro in RIP. Tre colonne: (1) indirizzo della rete di destinazione, (2) indirizzo del router successivo a cui inoltrare il pacchetto, (3) costo (numero di salti) per raggiungere la rete.

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

e riceve da $R_2$ un annuncio con $N_2$ a 1 salto, $N_3$ a 2 salti e $N_4$ a 15 salti. Per ogni rete $R_1$ somma 1 (il salto verso $R_2$, che è il costo $D_{R_1,R_2}=1$ del collegamento con il vicino che annuncia) e applica la formula di Bellman-Ford vista in 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 →, $D=\min\{D_{\text{attuale}},\,D_{R_1,R_2}+d_{R_2,w}\}$: $N_2$: $\min\{3,\,1+1\}=2$ (migliora, next hop $R_2$); $N_3$: non c'era in tabella (costo attuale $\infty$), quindi $\min\{\infty,\,2+1\}=3$ via $R_2$; $N_4$: $15+1=16=\infty$, non raggiungibile: la riga si scarta (con 16 salti il costo supera il massimo 15). Nota: $N_1$ non cambia, perché non compare nell'annuncio e la rete è collegata direttamente a $R_1$.

Regola sul next hop. Se l'annuncio arriva proprio dal router che è già il next hop di una riga, $R_1$ aggiorna comunque il costo anche se peggiora: quella riga dipendeva da $R_2$, e se $R_2$ ora dice $N_2=5$, il costo giusto per $R_1$ è $5+1=6$ (non si può tenere il vecchio $3$ che non è più vero). Solo gli annunci di altri router devono battere il costo attuale per sostituire la riga.

RIP versione 2. Aggiunge: informazioni di connettività (route tag e indirizzo del next hop nel messaggio), autenticazione, supporto dell'instradamento senza classi (c'è la subnet mask nel messaggio), multicast (indirizzo $224.0.0.9$, tutti i router RIP).

Timer di RIP.

• Periodic timer: regola l'invio degli aggiornamenti periodici. Ogni router ha un timer impostato a caso tra 25 e 35 s, per evitare che tutti i router mandino i messaggi nello stesso istante (traffico eccessivo); scende a zero, invia l'aggiornamento e viene reimpostato a caso. Se il valore è uniforme su $[25,35]$ (Distribuzioni uniforme continua ed esponenzialeU(a, b) ha densità costante 1/(b − a) su [a, b], media (a + b)/2 e varianza (b − a)²/12; Exp(λ) ha densità λe^(−λx) per x ≥ 0, FdD 1 − e^(−λx), P(X > t) = e^(−λt), media 1/λ, varianza 1/λ², ed è l'unica legge continua senza memoria (versione continua della geometrica).Distribuzioni uniforme continua ed esponenziale →), l'intervallo medio è $(25+35)/2=30$ s, che è il «circa 30 s» citato sopra.
• Expiration timer: regola la validità di una rotta, 180 s. Ogni aggiornamento ricevuto per la rotta lo azzera; se non ne arrivano in 180 s la rotta è scaduta e il suo costo diventa 16 (infinito).
• Garbage collection timer: dopo la scadenza la riga è tolta dalla tabella dopo altri 120 s: nel frattempo i vicini si accorgono che la rotta non è più valida prima che sia cancellata.

Esempio. Ultimo aggiornamento di una rotta all'istante $t=0$: a $t=180$ s la rotta scade (costo 16, ma resta in tabella per annunciare l'invalidità); a $t=180+120=300$ s la riga è eliminata.

Il distance vector soffre del conteggio all'infinito: per questo RIP usa l'infinito limitato a 16 e le contromisure della nota sugli algoritmi (split horizon, poison reverse, hold down, aggiornamenti immediati). Un lab con RIP: RIP in KatharàLaboratorio 5 (LAB5), con FRRouting (FRR) in Katharà. Un router è una macchina che esegue un demone di instradamento: FRR contiene zebra (gestisce la tabella) e demoni per RIP, OSPF, BGP; si attivano nel file /etc/frr/daemons (ripd=yes) e si configurano in /etc/frr/frr.conf o dalla shell vtysh. RIPv2 (distance vector, metrica in numero di salti, messaggi multicast UDP 520 verso 224.0.0.9) si abilita con router rip e network <prefisso>; redistribute connected annuncia anche le reti collegate. Due laboratori: tre router in fila (kathara-lab_frr) e una rete stub di cinque router (kathara-lab_rip) con rotta predefinita verso l'esterno iniettata in RIP con route 0.0.0.0/0.RIP in Katharà →.

OSPF

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

Ogni router OSPF crea la propria tabella di inoltro dopo aver trovato con Dijkstra (Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →) l'albero dei cammini minimi tra sé e le destinazioni; i grafi su cui lavora sono quelli descritti da Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà → (router e reti come nodi, collegamenti come archi con peso). Confrontando le tabelle di OSPF e di RIP nello stesso AS, l'unica differenza sono i valori dei costi: con il numero di salti come costo in OSPF le tabelle sono identiche (entrambi usano alberi dei cammini minimi).

Aree. OSPF opera in genere in AS grandi, dove il flooding degli LSP creerebbe molto traffico di controllo: l'AS è diviso in aree.

• Area: insieme di reti, host e router collegati, tutti dentro un AS.
• Tutte le aree dell'AS devono essere collegate all'area 0 (backbone), che le tiene insieme.
• Il flooding delle informazioni di stato è limitato a ciascuna area. Perché conviene: ogni LSA viene ritrasmesso su tutti i collegamenti dell'area (al più una volta per verso), quindi con $m$ collegamenti e $n$ router il traffico di un giro completo di LSA è dell'ordine di $n\cdot m$ messaggi; se un AS con $n=60$ router e $m=120$ collegamenti si divide in 6 aree da 10 router e 20 collegamenti ciascuna, ogni area genera circa $10\cdot20=200$ messaggi invece di $60\cdot120=7200$ (più il costo dei riassunti sul backbone). Anche il grafo su cui gira Dijkstra è più piccolo.
• I router di bordo d'area (Area Border Router, ABR) riassumono la topologia della propria area e la inviano alle altre aree attraverso il backbone.

Gli LSA. OSPF si basa sul link state, quindi ogni router annuncia lo stato di ogni suo collegamento per costruire la topologia. Per rivelare la presenza di entità diverse si usano cinque tipi di LSA:

• Tipo 1, router link. Annuncia la presenza di un router nell'area: l'indirizzo del router e i tipi di collegamenti che lo uniscono ad altre entità: transient (verso un router in un'area di transito, cioè che accetta traffico di transito), stub (verso un'area che non ammette traffico di transito: i dati terminano lì) e point-to-point (verso un router nella stessa area). Resta dentro l'area.
• Tipo 2, network link. Annuncia la presenza di una rete. Una rete è un'entità passiva e non può annunciarsi da sola: un router è eletto Designated Router (DR) e annuncia per lei. Il messaggio porta l'IP del DR e quello di tutti i router della rete (con le netmask). Costi e tipi di collegamento non sono annunciati qui perché li annuncia ogni router con i tipo 1.
• Tipo 3, summary link to network. Inviato da un ABR per far conoscere le reti di un'area alle altre aree collegate al backbone: l'ABR converte gli LSA di tipo 1 in LSA di tipo 3 per le reti delle altre aree (serve a incollare le aree e costruire la topologia completa).
• Tipo 4, summary link to AS. Inviato per far conoscere la presenza di un router di bordo dell'AS (ASBR, Autonomous System Border Router), cioè connesso direttamente a un altro AS; contiene l'IP dell'ASBR ed è diffuso nelle diverse aree.
• Tipo 5, external link. Inviato dall'ASBR per annunciare l'esistenza di una rete fuori dall'AS (per esempio $5.5.5.0/24$ di un altro AS) raggiungibile dal backbone; serve comunque il tipo 4 per localizzare l'ASBR.

BGP

Ogni router in un AS sa come raggiungere le reti del proprio AS ma non quelle di un altro AS. Il Border Gateway Protocol versione 4 (BGP4) è l'unico protocollo di instradamento inter-dominio disponibile oggi. È basato sull'algoritmo path vector (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 →) e fornisce informazioni sulla raggiungibilità delle reti in Internet.

Funzionamento:

• ogni router di bordo (ASBR) installa eBGP (external BGP) per ottenere informazioni di raggiungibilità dagli AS vicini;
• tutti i router di ogni AS installano iBGP (internal BGP), che gli ASBR usano per diffondere le informazioni di raggiungibilità a tutti i router dello stesso AS;
• si determinano rotte "buone" verso le sottoreti in base alle informazioni di raggiungibilità e alla politica.

Ogni aggiornamento porta un path vector, cioè l'intero cammino dall'AS sorgente all'AS destinazione. Quando un AS riceve una rotta controlla se lui stesso è già nel cammino:

• se sì, rifiuta la rotta: i cammini sono privi di cicli e non c'è conteggio all'infinito;
• se no, controlla se il costo del cammino corrente è maggiore di quello nuovo: se sì, aggiunge sé stesso e (eventualmente) riannuncia la rotta; altrimenti tiene la tabella com'è.

eBGP. È eseguito dai router di bordo di AS adiacenti. Quando il software è installato su due gateway di AS diversi (BGP peer, o BGP speaker), essi cercano di creare una connessione TCP sulla porta nota 179. In ogni sessione TCP la coppia di peer si scambia informazioni sulle reti (o aree) dei rispettivi AS. Esempio: il messaggio 1, inviato dal router di bordo $R_1$, dice al router di bordo $R_5$ che $N_1,N_2,N_3,N_4$ sono raggiungibili attraverso $R_1$; quando $R_5$ riceve un pacchetto per una di queste quattro reti, la sua tabella gli dice che il router successivo è $R_1$.

iBGP. È eseguito dai gateway di uno stesso AS e diffonde l'informazione sulle raggiungibilità di altri AS. Ogni router di ogni AS deve implementare anche iBGP, che crea sessioni TCP (sempre sulla porta 179) tra ogni coppia di router dentro un AS (anche non adiacenti). La propagazione delle rotte potrebbe essere fatta con un IGP (OSPF, RIP), ma a causa del numero potenzialmente enorme di rotte è fortemente sconsigliata. Esempio: $R_1$ annuncia che le reti $N_8$ e $N_9$ di AS2 sono raggiungibili con il cammino $\text{AS1}\to\text{AS2}$, ma che il router successivo è $R_1$.

Politiche di scelta del percorso. Se per una destinazione si ricevono più rotte BGP deve sceglierne una. La scelta non è facile come negli IGP, perché i path vector non si basano necessariamente su un albero dei cammini minimi. Esempi:

• preferenza locale (local preference): l'amministratore può preferire alcune rotte;
• AS-PATH minimo: il numero di AS attraverso cui si raggiunge la destinazione (aiuta a evitare i cicli);
• origine del percorso: l'informazione viene da un IGP, da BGP oppure da una fonte sconosciuta;
• dinamica dei collegamenti, e altro.

Esempio. Un router riceve per la rete $N$ due rotte: $\text{AS}_3\,\text{AS}_2\,\text{AS}_1$ (3 AS) e $\text{AS}_4\,\text{AS}_1$ (2 AS). A parità di preferenza locale vince la seconda (AS-PATH più corto). Se l'amministratore ha dato preferenza locale più alta alla prima, vince la prima, anche se più lunga. Se una rotta ricevuta contiene l'AS del router (per esempio $\text{AS}_5\,\text{AS}_1\,\text{AS}_6$ ricevuta in $\text{AS}_1$), viene scartata (ciclo).

Messaggi BGP. Quattro, scambiati tra gli speaker BGP, tra AS e dentro un AS:

Confronto delle prestazioni