Algoritmi e Protocolli di Routing su Internet

Esistono protocolli di routing per gli IGP e per gli EGP, quindi per gestire il routing all’interno e all’esterno dell’AS.

Interior Gateway Protocol: il suo obiettivo è distribuire informazioni sulla topologia della rete e quindi scegliere i percorsi migliori per l’inoltro dei pacchetti sulla base di tali informazioni topologiche.

I protocolli più usati per il routing IGP sono i seguenti:

RIP – Routing Information Protocol (algoritmo Distance Vector)

Questo algoritmo utilizza il numero di hop come metrica di routing adottando un limite massimo di hop dalla sorgente alla destinazione, allo scopo di evitare i loop, imponendo 15 come numero massimo. Questo numero limita in ogni caso il diametro massimo della rete, dal momento che in una rete con RIP un pacchetto potrà attraversare al massimo 15 router.

RIP utilizza l’algoritmo di Distance Vector con le tecniche di Split Horizon e Poison Reverse per evitare di dare informazioni potenzialmente errate, incrementare la stabilità ed evitare il problema dei loop e del count-to-infinity. RIP utilizza la porta 520 UDP, lavorando quindi a livello Transport.

Nella maggior parte degli scenari attuali, RIP non è la prima scelta in quanto convergenza e scalabilità non sono delle migliori rispetto ad altri algoritmi di routing. Resta tuttavia usato su reti di piccole dimensioni per la sua facilità di implementazione.

Split Horizon

Un router, quando inoltra la propria tabella di routing ad un altro router vicini, omette di specificare i percorsi che ha appreso dal vicino al quale sta trasmettendo la propria tabella.

Poison Reverse: in questa modalità un router invierà al proprio vicino anche le informazioni che ha appreso da lui, ma con una metrica infinita, ovvero comunicando a quel router che per lui la destinazione è sempre raggiungibile.

Hop indica il salto, ovvero il numero di consegne dirette da effettuare, ovvero il numero di link che vengono attraversati per raggiungere la destinazione. Nel RIP il numero massimo di hop varia da 1 a 15. Un valore di hop = 16 viene considerato come distanza infinita, ovvero come rotta inaccessibile.

IGRP/E-IGRP – Interior Gateway Routing Protocol / Enhanced Interior Gateway Protocol

È un protocollo proprietario della Cisco System nato per superare alcuni limiti del RIP, e per qualche tempo ha costituito la sua unica alternativa. Anch’esso si basa sull’algoritmo Distance Vector, con tutti i limiti che ne conseguono, ma introduce alcuni aspetti che lo rendono più efficiente del RIP. In particolare, introduce:

• Metriche più sofisticate del semplice hop: IGRP inserisce nelle metriche anche i parametri di Banda, Ritardo, Affidabilità e Carico. La variazione del valore di tali coefficienti permette di privilegiare determinati parametri rispetto ad altri, ad esempio la Banda rispetto al Ritardo, e decidere la politica di routing. In particolare, si considera la banda minima sul percorso, la somma dei ritardi sul percorso, la peggiore affidabilità del percorso e il carico più alto del percorso.
• Supporto del multipath routing;
• Migliore stabilità;

OSPF – Open Shortest Path First (algoritmo Link State)

Questo algoritmo lavora secondo il principio del routing gerarchico, ovvero il dominio di routing viene suddiviso in diverse aree. Attualmente OSPF rappresenta l’algoritmo di interior routing più diffuso sulle reti TCP/IP. Esso è in grado di gestire efficacemente reti di grandi dimensioni, ma la sua implementazione è molto più complessa del semplice RIP. Nell’OSPF il dominio di routing viene rappresentato dall’unione di Autonomous System, a loro volta suddivisi in più aree per poter implementare una soluzione di routing di tipo gerarchico. OSPF opera in modo indipendente in ogni area gerarchicamente definita e prevede meccanismi per lo scambio di informazioni. OSPF quindi, rispetto a RIP, introduce:

• metriche più efficienti;
• suddivisione gerarchica dei domini di routing;
• separazione delle informazioni interne ed esterne all’AS;

In OSPF, come previsto dall’algoritmo di routing Link State, ogni router della rete costruisce la propria mappa, e avrà quindi la propria “visione” della rete. Tuttavia, dal momento che in OSPF il routing è gerarchico, quindi suddiviso in diversi domini, non tutti i router avranno la stessa mappa della rete, a parte ovviamente quelli che si trovano nella stessa area. Ciò contribuisce a conservare i vantaggi dell’algoritmo Link State diminuendone la complessità.

Integrated IS-IS

È l’acronimo di Intermediate System to Intermediate System ed è un protocollo simile a OSPF, basato quindi su Link State. Anch’esso imposta il dominio di routing a livello gerarchico ma differisce da OSPF per il modo in cui le aree sono definite.

IS-IS definisce le aree come Livello 1 (intra area), Livello 2 (inter-area) o Livello 1-2 (entrambi). Le informazioni di instradamento vengono scambiate solo tra router di Livello 1 della stessa area, analogamente i router di Livello 2 potranno scambiare informazioni solo con altri router di Livello 2. I router di Livello 1-2 invece possono scambiare informazioni con entrambi i livelli e vengono utilizzati per collegare i router inter-area con i router intra-area.

EGP – Exterior Gateway Protocol

Il suo obiettivo è distribuire le informazioni sugli Autonomous System e quindi decidere la route migliore per le comunicazioni tra nodi che si trovano su AS differenti.

I protocolli più usati per il routing EGP sono i seguenti:

EGP:

Exterior Gateway Protocol propriamente detto, ormai obsoleto.

BGP – Border Gateway Protocol (algoritmo Path Distance)

BGP è stato realizzato per sostituire il vecchio EGP. I router BGP appartenenti ad AS adiacenti si scambiano informazioni attraverso connessioni affidabili, tramite la porta 179 su protocollo TCP, e sono previste funzioni di controllo degli errori demandate al livello Transport.

BGP è un protocollo di tipo Path Vector (una variante di Distance Vector), ovvero le informazioni sul percorso vengono aggiornate dinamicamente e non vengono utilizzate metriche di carattere tecnico ma le decisioni di instradamento vengono prese basandosi su regole determinate da ciascuna rete: nel vettore dei percorsi si elencano tutti gli AS da attraversare per andare da una sorgente ad una destinazione. Quindi mentre nel Distance Vector viene indicato solo il costo di un cammino, nel Path Vector per ogni destinazione IP viene fornita la sequenza di AS da attraversare.

IDRP – Inter Domain Routing Protocol

IDRP è un’evoluzione di BGP, quindi basato sull’algoritmo Distance Vector, e nelle intenzioni dei progettisti doveva essere la scelta naturale per il routing IPv6. Oggi non è molto usato.