Descrizione del metodo di routing e costruzione dell'LSP Database

Come si costruisce la mappa di rete?

Tale metodo di routing prevede che ogni nodo conosca la mappa completa della rete. Per la costruzione di tale mappa e del database dei collegamenti (detto LSP Database) che la rappresenta, occorre innanzitutto scoprire, tramite l’invio di pacchetti speciali denominati Hello, se ci sono e quali sono i nodi adiacenti. Successivamente vengono inviati altri pacchetti speciali denominati Echo per misurare il tempo di risposta di ogni router adiacente e quindi stimare il costo dei collegamenti. Poi ogni router costruisce i Link State Packet (LSP), pacchetti speciali contenenti le informazioni raccolte, che verranno distribuiti agli altri nodi. Le informazioni contenute nell’LSP sono l’elenco dei nodi adiacenti e i rispettivi costi dei collegamenti.

Distribuzione e utilizzo dell'LSP

Ogni router, predisposto il proprio LSP, provvede a inoltrarlo a “pioggia” verso gli altri nodi, con un algoritmo di flooding. Raccogliendo tutte queste informazioni, ogni router può predisporre l’LSP Database sopra citato, che sarà uguale per tutti i nodi e rappresenta tutti i router dell’intera rete e i collegamenti tra questi con i rispettivi costi. Tale database è il risultato dell’unione di tutti gli LSP distribuiti sulla rete e sarà memorizzato su ogni router. L’LSP Database, che rappresenta il grafo dell’intera rete, è lo strumento che verrà utilizzato da ogni router per calcolare la propria tabella d’instradamento servendosi di un particolare algoritmo noto con il nome di algoritmo di Dijkstra. Tale algoritmo permette di stabilire il miglior percorso, cioè a costo minore, tra due nodi qualsiasi della rete. Ogni router può, utilizzando l’LSP Database e l’algoritmo di Dijkstra, determinare il miglior percorso verso tutte le possibili destinazioni e installare il risultato di queste elaborazioni nella propria tabella di routing.