I Routing e la Routing Table nelle reti informatiche, Appunti universitari

I Routing e la Routing Table

Un router per ottimizzare il percorso dei pacchetti da instradare, deve conoscere e aggiornare una serie di informazioni:

• l'indirizzo del destinatario
• i router adiacenti
• l'insieme dei possibili percorsi (route) verso tutte le reti remote
• il percorso migliore per ciascuna rete remota
• il modo di mantenere e di verificare le informazioni necessarie per il routing.

Basandosi su queste informazioni il router può dare avvio al processo di forwarding, processo per stabilire verso quale linea inviare il pacchetto.

Il router deve quindi costruire, nella propria memoria, una tabella di instradamento, detta routing table, che gli permetta di memorizzare i dati indispensabili per individuare il percorso ottimale verso le reti remote che deve raggiungere.

La routing table è una lista di tutte le reti che il router può raggiungere insieme a informazioni sulla modalità di instradamento.

Il formato della tabella di routing varia a seconda del protocollo routing utilizzato. In generale ogni riga (detta entry) della tabella presenta 4 campi:

• Network adress: contenente l'indirizzo IP di ciascuna rete raggiungibile
• Next hop: l'indirizzo del router successivo nel percorso verso il destinatario
• Interface: interfaccia del router a cui deve essere inoltrato il pacchetto per raggiungere il next hop (un router può avere più interfacce di rete)
• Metric: è una misura utilizzata dal router per scegliere quale percorso inserire nella routing table quando ci sono più alternative: nella routing table si inserisce il percorso a costo minore.

Router di Default

Il router deve estrarre dall'header IP del datagram l'indirizzo del destinatario.

Nel caso in cui l'indirizzo di rete del destinatario sia presente nel campo network adress della routing table, il pacchetto viene instradato verso la sua direzione in modo diretto o indiretto.

Nel caso in cui il destinatario appartenga ad una rete che non è presente nella tabella di routing, il router inoltrerà il pacchetto verso un router di default che lo prenderà in carico con il compito di farlo giungere a destinazione. Se nella routing table non è definita questa default route, il router invia al mittente un messaggio ICMP Destination Unreachable.

Routing Statico e Dinamico

Il funzionamento di un router è caratterizzato dal modo in cui la tabella di routing viene creata:

• Manualmente, se la tabella di routing viene inserita dall'amministratore; in questo caso di parla di routing statico ( utilizzabile per piccole reti)
• Automaticamente, se il router costruisce da solo la tabella di routing in funzione delle informazioni ricevute attraverso i protocolli di routing; in questo caso di parla di routing dinamico.

Il routing statico ha il vantaggio di non richiedere che i router si scambino informazioni per aggiornare i percorsi o per individuarne di nuovi, limitando così l'uso di banda; inoltre essendo i percorsi già determinati una volta configurata la tabella, non è richiesto nessuno sforzo computazionale da parte del router stesso per selezionare i percorsi più ottimali.

Il router statico ha però lo svantaggio di richiedere sempre la riconfigurazione da parte dell'amministratore tutte le volte che si devono modificare le entry, sia in seguito a guasti, sia per inserire nuove route; inoltre tale metodo può divenire oneroso quando l' Internetwork contiene diversi percorsi. Infatti il router statico viene usato quando il numero di segmenti LAN non è elevato.

Il routing dinamico permette ai vari router di scambiarsi informazioni necessarie per determinare i percorsi utili per raggiungere le destinazioni remote, mediante dei protocolli, chiamati appunto routing protocol, che usano appropriati algoritmi di routing.

Il vantaggio di tale metodo è che richiede un minor controllo da parte dell'amministratore; di contro richiede un maggior uso di banda rispetto al routing statico perchè, oltre al traffico relativo ai pacchetti, c'è un traffico relativo agli scambi di informazioni indispensabili ai routing protocol.

Un ulteriore vantaggio è dato dalla capacità di adattarsi automaticamente ai cambiamenti della topologia di rete: se si verifica un guasto lungo una connesione oppure ne viene attivata una nuova, gli aggiornamenti dei vari percorsi vengono automaticamente propagati a tutti i router.

Sintesi: Vantaggi e Svantaggi

Il Problema della Ricerca nella Routing Table

Un problema molto comune è il cosiddetto Routing Table Lookup Problem (RTLP), cioè il problema di dover decidere molto in fretta dove instradare i pacchetti per evitare rallentamenti e relative congestioni.

La difficoltà di RTLP risiede nel numero estremamente elevato di pacchetti che devono essere esaminati ogni secondo.

Inoltre il problema diventa ancora più complesso se si considera che un qualsiasi router ha più interfacce e che il tempo di accesso per una cache veloce è di 50 nanosecondi: in queste condizioni sono sufficienti pochi accessi alla memoria per esaurire il tempo disponibile per il routing.

Dato che l'RTLP è un problema chiave per lo sviluppo della rete internet, è stato affrontato intervenendo su più fattori con lo scopo di velocizzare al massimo il processo di routing: si sono studiate strutture dati per memorizzare la tabella di routing in maniera più efficiente; si sono ideati algoritmi per velocizzare la consultazione della tabella.

Tuttavia questo non è ancora sufficiente: negli ultimi anni per risolvere il problema legato alla gestione del traffico dei pacchetti (packet processing) in riferimento alle prestazioni, si è cominciato a sviluppare un hardware dedicato a tale gestione.

In questo caso i network processor sono un promettente tentativo di ottenere prestazioni elevate mantenendo almeno parte della flessibilità dei microprocessori tradizionali e con essa la capacità di adattarsi a mutamenti degli algoritmi e dei protocolli di rete.

Algoritmi e Protocolli di Routing

Scopo di un Protocollo di Routing

Lo scopo di un protocollo di routing è quello di aggiornare dinamicamente le routing table. Rer fare ciò i rotuer condividono le informazioni sui percorsi (route) che ciascuno conosce. Tale scambio di informazioni è compiuto tramite pacchetti speciali chiamati routing update.

Lo scopo che un routing protocol si deve prefiggere sono:

• Ottimalità: deve essere in grado di fornire il percorso migliore o più veloce lungo l'Interetwork;
• Imparzialità: deve utilizzare tutte le linee disponibili per distribuire il traffico evitando le congestioni;
• Flessibilità: deve garantire la capacità di adattarsi ai cambiamenti della topologia di rete;
• Convergenza veloce: deve far sì che i cambiamenti all'interno dell'Internetwork si propaghino verso tutti i router nel minor tempo possibile;
• Robustezza: deve essere in grado di funzionare anche nel caso di configurazion non corrette e guasti componenti;
• Semplicità: deve essere semplice ed efficiente.

La maggior parte dei protocolli che regolano il routing moderno utilizzano uno dei seguenti algoritmi:

• Distance Vector Routing
• Link State Routing

Gli algoritmi di routing calcolano il percorso migliore o a costo minimo.

Algoritmo di Routing Distance Vector

Lalgoritmo Distance Vector si basa sull'algoritmo Bellman-Ford per calcolare il percorso migliore. Crea una tabella di routing costituita essenzialmente da due colonne: una contenente la distanza (il costo) stimata per raggiungere ogni nodo della rete e una che specifica l'interfaccia (la linea) da utilizzare. La distanza può essere calcolata secondo metriche diverse in base al protocollo in uso. Le righe della tabella saranno invece tante quanti sono i nodi della rete.

Essendo un algoritmo dinamico, le tabelle vengono aggiornate a intervalli di tempo prestabiliti.

Inizialmente ogni router invia ai router vicini (neighbour) un pacchetto di ECHO per calcolare la distanza che lo separa da ciascuno di essi e inserisce il valore nella tabella. Subito dopo i router vicini si scambiano un vettore delle distanze, cioè un array contenente le informazioni che ciascun router ha a disposizione riguardo i costi per raggiungere le varie destinazioni. A quel punto, ricevuti i vettori dai vicini, ciascun router aggiorna la propria tabella mediante un confronto tra i costi risultanti dalla propria tabella e quelli ricevuti, modificando i valori laddove risultino inferiori e aggiornando le relative interfacce (linee d'uscita).

Principali Problemi del Distance Vector

I due rincipali problemi che possono presentarsi con in Distance Vector sono:

• Routing loop: si verifica quando un pacchetto è inoltrato su percorso circolare senza mai giungere a destinazione; il problema si risolve grazie al contatore TTL ( Time To Live) il cui valore si riduce ad ogni hop e quando arriva a 0 il pacchetto viene scartato;
• Count to infinity: si verifica quando il costo per il raggiungimento di una destinazione viene progressivamente aumentato (esempio: destinazione non raggiungibile a causa di un guasto di cui il mittente non è a conoscenza); in questo caso il percorso finisce per essere scartato a causa dei costi sempre crescenti.

Entambi i problemi sono legati al fatto che il Distance Vector non conosce la topologia della rete e che la convergenza della rete ( cioè la propagazione della rete) può richiedere molto tempo.

Modifiche all'Algoritmo Distance Vector

È possibile migliorare l'algoritmo Distance Vector, limitando così i due problemi, mediante modifiche all'algoritmo originale.

Le più note varianti sono:

• split horizon: serve a prevenire il loop tra due nodi adiacenti. Ovvero, un router, che riceve informazioni che fanno riferimenti ad una certa destinazione, da un router adiacente, non può rispedire indietro informazioni su quella stessa destinazione ;.
• poison reverse: può essere considerato come uno split horizon leggermente modificato, infatti talvolta è chiamato split horizon with poison reverse. Con questa tecnica il router spedisce ugualmente informazioni su certe route a chi le ha inviate, ma attribuisce loro una metrica infinita, per cui la destinazione viene considerata come irraggiungibile;