Posts Tagged ‘Dijkstra’

Link state routing protocol

Abbiamo già visto in un precedente articolo quali sono le principali differenze tra i protocolli di routing distance vector e i protocolli link state. In questo articolo continuiamo la trattazione e vedremo nel dettaglio le caratteristiche dei protocolli link state; prima, però, riprendiamo le differenze tra le due classi di protocolli di routing.

I protocolli distance vector (come RIP e IGRP) presentano le seguenti caratteristiche:

  • inviano l’intera tabella di routing ai router vicini;
  • aggiornamenti periodici frequenti;
  • metrica basata sui salti (solo il RIP);
  • vedono la rete dalla prospettiva dei vicini;
  • convergenza lenta;
  • possibili routing loops;
  • semplicità di configurazione;
  • alto consumo di banda.

Caratteristiche dei protocolli link state:

  • aggiornamenti al variare della topologia della rete;
  • uso dello Shortest Path;
  • invio di pacchetti link-state a tutta la rete (LSA, Link State Advertisement);
  • vista totale della rete in comune tra i router;
  • convergenza veloce;
  • non suscettibili di routing loops;
  • complessi da configurare;
  • richiedono molta memoria e potenza computazionale;
  • consumano poca banda.

Un router che utilizza protocolli link state colleziona le informazioni da tutti gli altri router nella rete e, successivamente, calcola il miglior percorso (SPF algorithm) per tutte le destinazioni della rete stessa. Le variazioni della rete vengono acquisite dai router in maniera veloce: le informazioni vengono inviate in maniera non periodica ma al variare della topologia (triggered updates). Inoltre, vengono inviati dei pacchetti “hello” per verificare la raggiungibilità dei vicini. Informazioni di “hello” e LSAs costituiscono lo strumento per conoscere la topologia della rete per poter creare la tabella di routing (routing table).

Quando vi è una rottura nella rete si ha un fooding di pacchetti LSAs a un indirizzo multicast dedicato; ogni router invia queste informazioni su tutte le porte tranne su quella in cui l’informazione è arrivata. Questo fa si che ogni router appartenente a una certa area debba ricalcolare le rotte, ecco perché il numero di router di un’area deve essere limitato.

Un link è un’interfaccia del router. Lo stato di un link è la descrizione dell’interfaccia e della relazione con i router vicini. La descrizione dell’interfaccia può includere l’indirizzo IP della stessa, la subnet mask, il tipo di rete a cui è connessa, i router connessi ecc. L’insieme di tali informazioni forma il database link state meglio conosciuto come database topologico (topological database). Applicando l’algoritmo di Dijkstra (SPF, Shortest Path First) si forma un albero SPF in cui il router che lo applica è la radice (root). Il percorso migliore calcolato viene inserito nella routing table.

Vediamo di riassumere i vantaggi e gli svantaggi dei protocolli link state. Vantaggi:

  • utilizzo del costo di un link come metrica che tiene conto della capacità del link;
  • utilizzo di LSAs per informare immediatamente gli altri router dei cambiamenti della topologia della rete così da avere un convergenza veloce;
  • vista completa della rete, i routing loops sono facilmente evitabili;
  • routing table sempre aggiornata in base alle ultime informazioni ricevute;
  • supporto a CIDR e VLSM.

Svantaggi dei protocolli link state:

  • richiedono maggiore memoria e potenza di calcolo rispetto ai protocolli distance vector. Questo può determinare un costo eccessivo per un’azienda con poco budget o con hardware datato;
  • richiedono una struttura gerarchica della rete per poterla suddividere in aree più piccole e gestibili riducendo la dimensione della topology table;
  • richiedono una buona conoscenza del protocollo da parte dell’amministratore di rete;
  • effettuano un flooding di LSAs durante il processo di discovery iniziale che può determinare un significativo calo della capacità della rete in questo periodo.

Introduzione ai protocolli di routing: AS, distance vector e link state

Un protocollo di routing è un processo di comunicazione tra router per scambiarsi informazioni; tali informazioni andranno a formare la tabella di routing (routing table). L’invio del traffico utente è affidato, invece, ai protocolli routed.I protocolli di routing stanno alla base del routing dinamico.

Esempi di protocolli di routing sono:

  • RIP (Routing Information Protocol)
  • IGRP (Interior Gateway Routing Protocol)
  • EIGRP (Enhanced Interior Gateway Routing Protocol)
  • OSPF (Open Shortest Path First)

Esempi di protocolli routed sono:

  • IP (Internet Protocol)
  • IPX (Internetwork Packet Exchange)

In questo articolo vedremo in maniera teorica la distinzione tra i protocolli di routing e in particolare tra 2 categorie di algoritmi utilizzabili: distance vectorlink state. Prima però diamo la definizione di sistema autonomo (autonomous system o AS). Un AS è un insieme di reti che stanno sotto la supervisione di uno stesso amministratore di rete e che condividono strategie di routing comuni.
Lo scopo dei protocolli di routing è mantenere aggiornata la tabella di routing in base alle variazioni della topologia della rete. Una convergenza veloce delle rete a informazioni aggiornate nella routing è senza dubbio desiderabile in quanto si riduce il periodo di tempo in cui i router prendono decisioni di routing non corrette. In questo ambito si inseriscono gli AS che dividono l’internetwork globale in piccole reti che sono così molto più gestibili.

Passiamo ora ad esaminare l’algoritmo distance vector. L’algoritmo di routing distance vector invia periodicamente copie della propria tabella di routing da un router ad un altro per comunicare le variazioni sulla topologia della rete;  gli invii avvengono tra router adiacenti direttamente connessi. L’algoritmo utilizzato è anche conosciuto come algoritmo di Bellman-Ford.
Ogni router confronta la tabella di router che gli è stata inviata con la sua, se vi sono variazioni nella topologia della rete la propria viene aggiornata. Ogni router invia interamente la propria tabella di routing ai router adiacenti. La tabella di routing include informazioni circa la metrica (costo totale del percorso). Non si conoscono con tale algoritmo informazioni riguardanti reti o router distanti.

L’algoritmo link state è anche chiamato algoritmo di Dijkstra o shortest path first (SPF). Tale algoritmo mantiene una complessa tabella con le informazioni sulla topologia della rete e ha conoscenza totale dei router distanti da esso e le reti a essi interconnesse.

Un protocollo link state ha le seguenti caratteristiche:

  • LSA (link state advertisement), un piccolo pacchetto contenente le informazioni di routing;
  • topological database, l’insieme delle informazioni raccolte tramite i LSA;
  • algoritmo SPF, effettua i calcoli in base alle informazioni contenute nel database;
  • routing table, la tabella contenente la lista dei percorsi e delle interfacce conosciute.

I router che utilizzano protocolli basati su link state hanno bisogno di maggiore memoria e potenza di calcolo di altri che utilizzano protocolli basati su distance vector. La maggiore memoria è dovuta al fatto di dover immagazzinare informazioni sui vari database, sulla topologia della rete e i dati della routing table.
Vediamo in breve il funzionamento.  Inizialmente avviene il processo di scoperta (discovery process) attraverso il flooding (letteralmente, inondazione) di pacchetti link state tramite pacchetti LSA a tutti gli altri router. Questo processo inonda la rete di pacchetti LSA riducendone temporaneamente la banda disponibile per il traffico utente. Dopo questa fase iniziale, però, i protocolli link state richiedono generalmente poca banda per inviare i LSA che verranno inviati solo quando vi saranno delle variazioni della topologia della rete.

Concludiamo dicendo che i router hanno 2 funzioni di base:

  • determinazione del percorso;
  • funzioni di switching.

A livello rete vi è la funzione di calcolo del percorso, che consente al router di calcolare il percorso di un pacchetto fino a destinazione e stabilisce quale sia la via migliore. Per effettuare tali scelte viene utilizzata la tabella di routing.
La funzione di switching è una funzione interna del router che ha il compito di inviare un pacchetto ricevuto su una interfaccia ad un’altra interfaccia dello stesso. Il compito principale dello switching è quello di incapsulare in maniera appropriata il pacchetto in base alla rete che ci si trova sulla porta di uscita.