Protocolli e architetture di instradamento/L'algoritmo Link State

L'algoritmo Link State (LS) è basato sulla distribuzione nell'intera rete di informazioni sull'intorno del router. Ogni nodo può creare la mappa della rete (uguale per tutti i nodi), dalla quale è necessario ricavare la tabella di instradamento.

Componenti

• Neighbor Greeting
• Link State
• algoritmo di flooding
• algoritmo di Dijkstra
• riallineamento delle adiacenze

Neighbor Greeting

I Neighbor Greeting sono messaggi scambiati periodicamente tra nodi adiacenti per raccogliere le informazioni sulle adiacenze. Ogni nodo:

• invia i Neighbor Greeting per segnalare la propria esistenza ai suoi vicini;
• riceve i Neighbor Greeting per apprendere quali sono i suoi vicini e i costi per raggiungerli.

I Neighbor Greeting implementano il rilevamento dei guasti basato su un numero massimo di Neighbor Greeting consecutivi non ricevuti:

• rapido: i Neighbor Greeting possono essere inviati ad alta frequenza (ad es. ogni 2 secondi) per riconoscere le variazioni sulle adiacenze in un tempo molto breve:
  • una volta ricevuti, non sono propagati ma si fermano al primo hop → non intasano la rete;
  • sono pacchetti di piccole dimensioni perché non contengono informazioni su altri nodi oltre al nodo generante;
  • richiedono un overhead basso per i router, che non sono costretti a ricalcolare la tabella di instradamento ogni volta che ne ricevono uno;
• affidabile: non si affida al segnale "link-up", non disponibile in presenza di hub.

Link State

Ogni router genera un LS, che è un insieme di coppie adiacenza-costo:

• adiacenza: tutti i vicini del router generante;
• costo: il costo del link tra il router generante e il vicino.

Ogni nodo memorizza tutti i LS che arrivano da tutti i nodi della rete nel Link State Database, quindi scandisce la lista di tutte le adiacenze e costruisce un grafo unendo i nodi (router) con degli archi (link) al fine di costruire la mappa della rete.

La generazione dei LS è principalmente basata sugli eventi: un LS viene generato in seguito a un cambiamento nella topologia locale (= nell'intorno del router):

• il router ha un nuovo vicino;
• è cambiato il costo per raggiungere un vicino;
• il router ha perduto la connettività ad un vicino precedentemente raggiungibile.

La generazione basata sugli eventi:

• permette un migliore utilizzo della rete: non consuma la larghezza di banda;
• richiede il componente di "hello", basato sui Neighbor Greeting, poiché il router non può più utilizzare la generazione periodica per rilevare i guasti verso i suoi vicini.

In aggiunta, i router implementano anche una generazione periodica, con frequenza molto bassa (dell'ordine di decine di minuti):

• aumenta l'affidabilità: se un LS per qualche motivo va perso, può essere nuovamente inviato senza dover aspettare l'evento successivo;
• permette di includere un campo "age": la entry relativa a una destinazione scomparsa rimane nella tabella di instradamento e i pacchetti continuano a essere mandati a quella destinazione fino a quando l'informazione, se non rinfrescata, non invecchia abbastanza da poter essere cancellata.

Algoritmo di flooding

Ogni LS deve essere inviato in "broadcast" a tutti i router della rete, che devono riceverlo invariato → i protocolli reali implementano una sorta di flooding selettivo, che rappresenta l'unico modo per raggiungere tutti i router con gli stessi dati e con overhead minimo. Il broadcast è limitato ai soli LS, per evitare l'intasamento della rete.

La propagazione dei LS avviene a velocità elevata: al contrario dei DV, ogni router può subito propagare il LS ricevuto e in un secondo momento elaborarlo localmente.

I protocolli reali implementano un meccanismo affidabile per la propagazione dei LS: ogni LS deve essere confermato "hop by hop" con un acknowledgment, perché il router deve essere sicuro che il LS inviato ai suoi vicini sia stato ricevuto, anche considerando che i LS sono generati con una frequenza bassa.

Algoritmo di Dijkstra

Dopo aver costruito la mappa della rete dalla lista delle adiacenze, ogni router è in grado di calcolare l'albero ricoprente del grafo, cioè l'albero con i percorsi a costo minimo avente il nodo come radice, grazie all'algoritmo di Dijkstra: a ogni iterazione vengono considerati tutti i link che collegano i nodi già selezionati con i nodi non ancora selezionati, e viene selezionato il nodo adiacente più vicino.

Tutti i nodi hanno lo stesso Link State Database, ma ogni nodo ha un albero di instradamento diverso verso le destinazioni, perché al cambiare del nodo scelto come radice cambia l'albero ricoprente ricavato:

• migliore distribuzione del traffico: ragionevolmente non ci sono link inutilizzati (a differenza dello Spanning Tree Protocol);
• ovviamente l'albero di instradamento deve essere consistente tra i vari nodi.

Riallineamento delle adiacenze

Il riallineamento delle adiacenze è richiesto per sincronizzare i Link State Database dei router quando viene rilevata una nuova adiacenza:

• un nuovo nodo si collega alla rete: il nodo adiacente comunica ad esso tutti i LS relativi alla rete, per popolare il suo Link State Database da cui potrà calcolare la sua tabella di instradamento;
• due sottoreti partizionate (ad es. a causa di un guasto) vengono riconnesse insieme: ognuno dei due nodi alle estremità del link comunica all'altro nodo tutti i LS relativi alla sua sottorete.

Procedura

1. una nuova adiacenza viene rilevata dal protocollo di "hello", che tiene le adiacenze sotto controllo;
2. la sincronizzazione è un processo punto-punto, cioè interessa solo i due router alle estremità del nuovo link;
3. gli LS che erano precedentemente sconosciuti vengono inviati agli altri nodi della rete in flooding.

Comportamento su reti broadcast di livello data-link

L'algoritmo LS modella la rete come un insieme di link punto-punto → soffre in presenza di reti broadcast di livello data-link (come Ethernet), dove ogni entità ha accesso diretto a ogni altra entità sullo stesso collegamento dati (bus condiviso), creando perciò un insieme di adiacenze a maglia completa ($N$ nodi → ${\tfrac {N\left(N-1\right)}{2}}$ link punto-punto).

Il numero elevato di adiacenze ha un impatto importante sull'algoritmo LS:

• problemi computazionali: la convergenza dell'algoritmo di Dijkstra dipende dal numero di link ($L\cdot \log {N}$), ma il numero di link esplode su reti broadcast;
• overhead non necessario nella propagazione dei LS: ogni volta che un router deve inviare il suo LS sulla rete broadcast, deve generare $N-1$ LS, uno per ogni vicino, anche se sarebbe sufficiente inviarlo una volta sola sul canale condiviso per raggiungere tutti i vicini, poi ogni vicino a sua volta propagherà più volte il LS ricevuto ($\sim N^{2}$);
• overhead non necessario nel riallineamento delle adiacenze: ogni volta che viene aggiunto un nuovo router alla rete broadcast, deve iniziare $N-1$ fasi di riallineamento, una per ogni vicino, anche se sarebbe sufficiente riallineare il database con uno solo di essi.

La soluzione è trasformare la topologia broadcast in una topologia a stella, aggiungendo uno pseudo-nodo (NET): la rete è considerata un componente attivo che inizierà ad annunciare le sue adiacenze, diventando il centro di una topologia a stella virtuale:

• viene "promosso" uno dei router che sarà responsabile di inviare anche quei LS aggiuntivi a nome della rete broadcast;
• tutti gli altri router annunciano un'adiacenza solamente a quel nodo.

La topologia a stella virtuale è valida solo per la propagazione dei LS e il riallineamento delle adiacenze, mentre il normale traffico dati utilizza ancora la topologia broadcast reale:

• propagazione dei LS: il nodo generante invia un LS allo pseudo-nodo, il quale lo invia agli altri nodi ($\sim N$);
• riallineamento delle adiacenze: il nuovo nodo attiva una fase di riallineamento solo con lo pseudo-nodo.

Vantaggi

• convergenza rapida:
  • i LS vengono velocemente propagati senza alcuna elaborazione intermedia;
  • ogni nodo ha informazioni certe perché provenienti direttamente dalla fonte;
• breve durata dei routing loop: possono accadere durante il transitorio per una quantità di tempo limitata;
• facilità di debug: ogni nodo ha una mappa della rete, e tutti i nodi hanno database identici → basta interrogare un singolo router per avere la mappa completa della rete in caso di necessità;
• buona scalabilità, anche se è meglio non avere domini grandi (ad es. OSPF suggerisce di non avere più di 200 router in una singola area).