Posts Tagged ‘loop’

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.

Distance vector e routing loop

Abbiamo visto nei precedenti articoli le caratteristiche principali dei protocolli che utilizzano l’algoritmo di routing distance vector e in particolare che ogni router invia periodicamente la sua intera tabella di routing ai router adiacenti compreso il costo totale del percorso (metrica) e l’indirizzo del primo router del cammino nel percorso (detto next hop). Tuttavia l’algoritmo distance vector soffre di una problematica: i loop.

I routing loop si possono verificare se le routing table non sono aggiornate o sono inconsistenti a causa di una lenta convergenza del protocollo. Facciamo un esempio con la figura di seguito riportata.

Distance vector routing loop

Distance vector routing loop

In questa situazione può capitare che se una tratta diventa isolati; quando la rete 1 si guasta il router E emette un updateverso A. Il router A blocca l’instradamento verso la rete 1, ma i router B, C e D continuano ad inviare pacchetti verso A perché ancora non sono aggiornati sul guasto della rete 1. Appena A emette gli updateverso B e D questi bloccano le emissioni verso la rete 1. In questa situazione, il router C ancora vede la rete 1 come raggiungibile attraverso il router B; il router C manda un update verso D indicando che il path verso la rete 1 è attraverso B. Il router D aggiorna la sua routing table e propaga questa informazione verso il router A. Il router A rilancerà l’update verso i router B ed E. A questo punto ogni pacchetto emesso da C destinato alla rete 1 seguirà un looptra i router C, B, A e D.

Gli update non validi relativi alla rete 1 continueranno fino a che un altro processo non fermerà il loop. Questa situazione, detta Count-to-Infinity, è creata dalla propagazione di informazioni di routing non valide. Per evitare il count-to-infinity, i protocolli distance vector definiscono “infinity” uno specifico numero massimo (self-correcting); con tale approccio il routing protocol permette al loop di continuare sino a che la metrica non eccede il massimo valore permesso. Quando il valore della metrica eccede il massimo valore la rete è considerata non raggiungibile.

In poche parole, i loop avvengono quando gli update non corretti contraddicono gli update corretti. Per evitare questa situazione si è implementato lo Split Horizon, ovvero le informazioni di rete irraggiungibile da parte di un router non possono tornare indietro allo stesso router da parte degli adiacenti. Con questa tecnica si riducono sia le informazioni errate che il tempo necessario alla convergenza della rete.
Un ulteriore metodo per aumentare la convergenza della rete è utilizzare il route poisoning, ovvero si fa in modo che il primo router (nella figura il router E) che identifica la rete come irraggiungibile modifica la metrica di tale rete al numero massimo (e quindi la pone subito come irraggiungibile anche per i router adiacenti). Un ulteriore passo di convergenza è l’invio di update appena si verifica l’irraggiungibilità (trigger update) senza aspettare l’update periodico. I triggered update, usati in congiunzione con il route poisoning, assicurano che tutti i router sappiano delle route indisponibili nel piùbreve tempo possibile.

L’ultima tecnica per evitare i routing loop è l’holddown timer, vediamone il funzionamento. Quando un router riceve un update da un vicino che gli indica che una rete prima accessibile adesso non lo è più, il router marca la rete come tale e fa partire un holddown timer. Se arriva un update prima che tale timer si esaurisca dallo stesso vicino indicando che la rete in questione è di nuovo accessibile allora il timer è rimosso e la rete marcata come accessibile. Se un update arriva da un router vicino diverso con una metrica migliore di quella originale allora il router marca la rete come accessibile e ferma l’holddown timer. Se prima che l’holddown timer scada si riceve un update da un router vicino diverso dal primo, con una metrica peggiore, l’update è ignorato; ignorare un update di tale tipo ha lo scopo di dare più tempo all’informazione di irrangiugibilità della rete di propagarsi.

CountGli updatenon validi relativi alla rete 1 continueranno fino a che un altro processo non fermeràil loopQuesta situazione, detta CounttoInfinity, ècreata dalla propagazione di informazioni di routingnon validePer evitare il counttoinfinity, i protocolli distancevectordefiniscono “infinity”uno specifico numero massimo (self-correcting)Con tale approccio il routingprotocolpermette al loopdi continuare sino a che la metrica non eccede il massimo valore permessoQuando il valore della metrica eccede il massimo valore la rete èconsiderata non raggiungibile