Algoritmi di routing

Algoritmi per il routing al volo/forwarding sono i seguenti:

• Routing by Network Address
• Label Swapping
• Source Routing

Ogni architettura protocollare tipicamente ne utilizza più di uno.

Fasi del forwarding

All’arrivo del pacchetto si seleziona la porta d’uscita, si effettua lo switching (ovvero la commutazione) su tale porta e quindi si procede alla sua trasmissione.

Nel routing proattivo invece ci sono diversi algoritmi, classificati in due grosse categorie:

• Algoritmi non adattativi (statici)
• Algoritmi adattativi (dinamici)

Nel routing statico i percorsi per l’inoltro dei pacchetti sono determinati a priori (ed eventualmente modificati all’occorrenza) dall’amministratore della rete, che si occupa quindi di costruire la tabella di routing. Il principale svantaggio del routing statico è la sua impossibilità a reagire autonomamente ad eventuali guasti o cambiamenti topologici della rete. Per ovviare in parte a questo inconveniente, nelle situazioni di routing statico, si prevedono a priori diversi percorsi per raggiungere un altro router della rete in modo da avere diverse possibilità per l’instradamento in caso di problemi ai nodi.

Nel routing dinamico i percorsi per l’inoltro dei pacchetti sono individuati da un determinato protocollo di routing che viene aggiornato in maniera automatica in funzione delle modifiche di topologia o di traffico. Questo sistema risulta senz’altro più complesso, ma decisamente più efficiente. Per implementarlo occorre che i router si scambino informazioni sullo stato della rete e dei collegamenti.

Algoritmi non adattativi – Statici

Con gli algoritmi statici l’amministratore ha il pieno controllo sulle politiche di instradamento, ma questo algoritmo presenta il grave problema di non adattarsi ad eventuali cambiamenti topologici. I principali sono i seguenti:

Fixed Directory Routing: noto come algoritmo di routing statico che necessita di configurazione manuale.

Flooding: algoritmo selettivo che ha diversi derivati.

Algoritmi adattativi – Dinamici

Gli algoritmi adattativi possono prevedere diverse tipologie di routing:

• Routing centralizzato
• Routing isolato
• Routing distribuito (algoritmi Distance Vector e Link State)

Routing Centralizzato

Il routing centralizzato utilizza un Routing Control Center (RCC) che calcola e distribuisce le tabelle di routing e che per funzionare ha bisogno di conoscere le informazioni di tutti i nodi della rete.

Questo tipo di routing ottimizza le prestazioni, semplifica il troubleshooting e determina un traffico di rete sostenuti nelle vicinanze dell’RCC. Tuttavia, la presenza dell’RCC come punto fondamentale del sistema ne fa un collo di bottiglia e può determinare, in caso di malfunzionamento, un blocco di tutta la rete. Tale sistema risulta quindi inadeguato per le reti dinamiche.

Routing Isolato

Nel routing isolato, ogni nodo decide in maniera indipendente i percorsi che dovranno intraprendere i pacchetti. In questa modalità di routing non c’è scambio di informazioni tra i nodi della rete.

Questa modalità unisce i vantaggi del routing isolato e di quello centralizzato:

i router collaborano nello scambio di informazioni sulla connettività;

ogni router decide in maniera autonoma ma coerente;

Routing Distribuito

Nel routing distribuito ogni nodo calcola in maniera autonoma le proprie tabelle di instradamento, basandosi su informazioni locali o distribuite, ovvero utilizzando informazioni relative ad altri nodi della rete. Nel caso di routing distribuito deve essere implementato un meccanismo di scambio delle informazioni, ovvero un protocollo.

Algoritmo di Distance Vector

Questo algoritmo si basa sulla teoria dei grafi e calcola i vettori delle distanze tra i vari nodi. Ogni nodo, che solitamente è costituito da un router, può essere un firewall, un host o comunque un qualsiasi dispositivo o apparato di rete in gradi di replicare i pacchetti.

Il Distance Vector è un algoritmo di tipo dinamico e tiene conto del carico istantaneo della rete. In sintesi, ogni nodo misura la distanza che lo separa dai nodi adiacenti, secondo una metrica che include vari fattori, ricevendo i dati dai nodi vicini. A partire da tali dati, usando l’algoritmo di Bellman-Ford, il nodo costruisce una tabella contenente delle informazioni su ogni destinazione (ovvero su ogni nodo) a lui conosciuto.

Queste informazioni sono:

• La stima della distanza che lo separa dalla destinazione;
• Il primo passo del percorso calcolato;

Tutti i nodi della rete aggiorneranno periodicamente le misure di distanza dai nodi adiacenti scambiandosi informazioni con i nodi vicini.

Vantaggi

Questo algoritmo è stato uno dei primi ad essere utilizzati per i suoi meccanismi di implementazione ed aggiornamento molto semplici, ma presenta numerosi limiti sulle reti di grandi dimensioni.

Svantaggi

Principale inconveniente di questo algoritmo è che ogni nodo memorizza nella propria tabella solo il primo passo dei percorsi. Questo implica che se, ad esempio, il nodo A pubblica un percorso verso il nodo C, i nodi vicini di A non possono sapere se sono stati inclusi da A nel percorso che esso ha pubblicato fino a C, quindi si potrebbero creare dei cicli e quando un collegamento si interrompe si potrebbe verificare una situazione di count-to-infinity, ovvero dei tentativi infiniti di instradare il pacchetto.

Ad esempio, se nel percorso da A a C si interrompe il collegamento con B, il nodo B, al momento di aggiornare la propria tabella, vedrà che non può più raggiungere A tramite il collegamento diretto. Tuttavia, il nodo C, che non conosce la situazione, è convinto di poter ancora raggiungere A e quindi mantiene nella tabella il suo percorso per raggiungere A in due passi (attraverso B). B, quindi potrebbe tentare di raggiungere A tramite C in tre passi, senza mai riuscirci.

Questa situazione subisce un progressivo peggioramento sulle reti di grandi dimensioni dove entrano in gioco distanza sempre maggiori.

Alcune soluzioni parziali sono le seguenti:

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

Algoritmo di Link State

In questo algoritmo tutti i costi dei collegamenti dell’intera topologia della rete sono noti a tutti i router della rete, quindi ogni singolo router acquisisce le informazioni sullo stato dei collegamenti adiacenti e anche sullo stato dei collegamenti di tutti gli altri.

Si tratta quindi di una vera e propria mappa distribuita della rete, che viene regolarmente aggiornata.

Il funzionamento di questo algoritmo è basato sul fatto che ogni router descrive compiutamente la topologia della rete intorno a lui e invia questa descrizione a tutta la rete mediante opportuni pacchetti detti LSP, ovvero Link State Packet. Il pacchetto LSP contiene quindi tutte le informazioni necessarie a costruire la topologia della rete come: stato di ogni link connesso al router, identità di ogni vicino connessi, costo del link, numero di sequenza, checksum, lifetime. Un LSP viene generato periodicamente oppure quando viene rilevata una variazione nella topologia della rete. Il pacchetto LSP è trasmesso su tutti i link del router e tutti i router del dominio di routing ricevono gli LSP, ottenendo quindi le informazioni necessaria a costruire la topologia completa della rete.

Dal momento che ogni router riceve i pacchetti LSP da tutti gli altri, potrà mettere insieme le varie descrizioni per costruire una propria mappa della rete.

Mediante l’algoritmo di Dijkstra (detto anche algoritmo Shortest Path First) ogni nodo è quindi in grado di valutare sulla mappa il percorso migliore da far compiere ai pacchetti da inviare per fargli raggiungere una destinazione della rete.

Vantaggi

L’algoritmo di Link State è quindi caratterizzato da un’elevata stabilità garantendo quindi tempi brevi di convergenza, ovvero i link state si propagano velocemente e non hanno bisogno di nessuna elaborazione prima dell’inoltro. Inoltre, ha una bassissima probabilità di routing loop e genera un traffico di routing limitato assieme ad un basso uso di memoria.

Queste caratteristiche sono conseguenza dell’algoritmo di Dijkstra. Questo algoritmo risolve lo stesso problema di quello di Bellman-Ford, ovvero trovare il cammino minimo di un grafo, ma lo fa in un tempo computazionalmente inferiore, presentando quindi una minore complessità computazionale (L*log(N) per Dijkstra contro N2 di Bellman-Ford, dove N=nodi e L=link).

Altri vantaggi sono la semplicità nel rilevare eventuali guasti, dal momento che tutti i router hanno la stessa tabella.

Svantaggi

Il suo principale svantaggio è l’elevata complessità di implementazione, a causa dell’utilizzo del selective flooding utilizzato per l’invio dei pacchetti LSP, e della conseguente elevata complessità dei protocolli che devono implementare questo algoritmo.

Nel Selective Flooding ogni pacchetto in arrivo in un nodo viene inviato attraverso ogni collegamento in uscita, tranne quello del nodo che lo ha inviato.