Tutto quello che devi sapere sul routing

Quando un terminale A manda un pacchetto a un terminale B,questo pacchetto attraverso tanti router nella rete. Come fa ogni router che riceve il pacchetto a determinare qual'è il prossimo router più vicino al terminale B ? Questa domanda pone in modo molto semplice il problema del routing.

Prima di andare nello specifico,vediamo cosa fa il router. Il router
Elabora l’indirizzo dei pacchetti IP e determina la subnet in cui si trova l’host
di destinazione.
1.se l’host di destinazione si trova in una delle subnets a cui il router `e
direttamente connesso affida il pacchetto alla subnet per la consegna;
2.altrimenti determina il router successivo verso cui instradare il pacchetto. L'obbiettivo è di determinare il percorso migliore per ogni terminale possibile.
Il routing è composto da due elementi:
1.Un protocollo di routing per costruire la Routing Table. Viene eseguito periodicamente a prescindere dai pacchetti dati.
2.Un algoritmo di switching, che si applica ad ogni pacchetto in transito.
Una routing table è una tabella che permette di determinare dove mandare il pacchetto analizzando il suo indirizzo ip di destinazione.
In questo articolo,vedremmo gli algoritmi di routing con i protocolli che gli implementano.
Algoritmi di routing
Distance Vector:
Questo algoritmo locale e dinamico è un implementazione di BellMan Ford distribuita. Ogni router mantiene una tabella che dice dove mandare un pacchetto diretto verso uno specifico router e quanto costa questo trasferimento. Quindi la tabella da tre informazioni: destinazione,costo e prossima fermata. Per avere queste informazioni su tutte le destinazioni della rete,Ogni router misura la distanza o costo (secondo una metrica che può includere vari fattori) che lo separa dai nodi adiacenti e riceve la stessa informazione dai nodi vicini .Utilizzando l'algoritmo di Bellman-Ford con i suoi dati e quelli dei nodi adiacenti, il router costruisce una tabella che associa ad ogni destinazione conosciuta: la stima della distanza che lo separa dalla destinazione e il primo passo del percorso calcolato.Periodicamente ogni router manda un aggiornamento ai suoi vicini. Un aggiornamento è una lista di coppie (destinazione,distanza) cioè tutta la tabella di routing.
Il problema con quest'algoritmo resta la formazione di cicli all'interno dei percorsi calcolati. Ci sono varie alternative per evitare la formazione di cicli. Per esempio Split Horizon che segue questa regola:
Quando mandi un aggiornamento al router A,non specificare le destinazioni che raggiungi tramite A.
Un altro svantaggio è la propagazione di un informazione errata attraverso la rete nel caso di un malfunzionamento di un router per esempio.
Link State
Questo è un algoritmo basato sullo stato dei collegamenti della rete che implementa al suo interno Dijkstra.
La strategia usata è quella di mandare dei messaggi a tutti i router (non solo i vicini). I messaggi tratta solo di informazioni sui collegamenti diretti(non di tutta la tabella di routing).
I messaggi sono chiamati Link state Packet e sono composti di un ID (indentifica il nodo che manda il pacchetto),il costo del collegamento a tutti i nodi direttamente connessi a lui,un numero di sequenza e un Time-To-Live (durata di vita del pacchetto).
Il numero di sequenza serve a sapere se un pacchetto è recente o meno rispetto a pacchetti ricevuti in precedenza.
Ogni nodo memorizza i pacchetti ricevuti e costruisce una mappa completa e aggiornata della rete: il Link State Database.
A questo punto ogni router usando l'algoritmo Dijkstra single shortest Path sugli informazioni ottenuti dagli altri nodi calcola il percorso a più basso costo partendo da se stesso.
Quindi in questo caso la topologia dell'intera rete è conosciuta.
È possibile costruire la tabella di routing di un nodo memorizzando per ciascuna destinazione il nodo successivo sul cammino a costo minimo.
Vantaggi e svantaggi
L'utilizzo di un algoritmo di routing Link State, presenta diversi vantaggi:
può gestire reti composte da un gran numero di nodi;
converge rapidamente al cammino minimo;
difficilmente genera cammini ciclici;
è facile da comprendere poiché ogni nodo ha la mappa della rete;
Il principale svantaggio di un algoritmo Link State è la complessità di realizzazione, anche dovuta alla notevole capacità di memoria ed elaborazione richiesti.
Ora vediamo i protocolli di routing.
Protocolli di routing.
Ci sono 2 grande categorie di routing che hanno a che vedere con l'organizzazione delle reti di internet:Interior Gateway Protocol e Exterior Gateway protocol. Internet è fatta di più sotto reti(AS:autonomous System) connesse fra loro. Interior Gateway Protocol raggruppa l'insieme dei protocolli che si occupa del routing interno a un AS. Exterior Gateway protocol si occupa del routing esterno ad un AS cioè fra due router di bordo .

Interior Gateway Protocol
RIP(routing information protocol)
Il Routing Information Protocol (RIP) è molto usato su reti locali ed aiuta i router ad adattarsi dinamicamente ai cambiamenti dei collegamenti di rete, scambiandosi informazioni riguardo a quali reti possono raggiungere e quanto siano lontane. Il RIP è un'implementazione del Distance Vector che impiega il conteggio dei numeri di passi (hop count) come metrica di routing. Il massimo numero di hop permessi è 15. Ogni router RIP trasmette di default, ogni 30 secondi, la propria tabella completa di routing a tutti i vicini direttamente collegati, generando grandi quantità di traffico di rete. Opzionalmente può utilizzare un meccanismo di ottimizzazione denominato split horizon.
E da notare che il basso numero di hop impone un limite alla grandezza della rete. D'altra parte, è molto facile da configurare.
OSPF(open shortest path first)
Il protocollo Open Shortest Path First(OSPF) è un protocollo, che gestisce le tabelle di routing in una rete con il metodo del Link State. Questo standard è open (aperto) nel senso che è un protocollo non proprietario. Il protocollo utilizza un metodo di instradamento che non si differenzia sostanzialmente dal Link State, ma aggiunge delle altre proprietà:Autenticazione dei messaggi, Bilanciamento del carico,e Aggiunta di un ulteriore grado di gerarchia nei domini.
Inizializzazione del protocollo:
Inizializzazione e controllo (attraverso livelli inferiori) del funzionamento delle interfacce
Si inviano pacchetti Hello in broadcast per acquisire le informazioni sui router vicini
Si ricevono i pacchetti Hello dei vicini
I pacchetti Hello vengono anche usati per testare il funzionamento di link (keep alive)
Funzionamento del protocollo:
i router
formano i Link State Advertisement (LSA) che contengono una lista delle reti adiacenti con i relativi costi di raggiungimento
gli LSA sono trasmessi a tutti gli altri router
tutti i router della rete hanno lo stesso insieme di dati e quindi possono costruire lo stesso grafo pesato della rete
il grafo di rete è utilizzato per determinare i cammini ottimi e quindi l’instradamento
Exterior Gateway Protocol
Border Gateway Protocol
Per stabilire una route i router BGP si scambiano informazioni riguardanti la
raggiungibilità di una rete e una serie di attributi relativi al link (o ai link) tra i
due AS coinvolti:
Weight (prop. Cisco)
E’ un attributo locale (interno ad un router).
Non `e propagato (advertised).
In caso di multipath, viene preferita la route con maggior weight.
Local preference
E’ usato per scegliere la strada di uscita preferita tra due o più router.
In caso di multi-route, viene preferita la route con maggior peso.
Multi-exit discriminator (MED) o metric attribute
MED
E’ usato per suggerire la strada di ingresso preferita tra due o pi `u router.
In caso di multi-route, viene preferita la route con minor peso.
Origin
E’ usato per classificare il modo in cui BGP ha appreso una route.
Le route sono divise in:
IGP - la route e generata da un protocollo IGP ed `e interna all’AS che la
propaga
EGP - la route e stata appresa attraverso un protocollo EGP
Incomplete - la route e di origine sconosciuta o appresa tramite altra via
La classificazione `e usata per la scelta della tabella di routing, ovviamente
preferendo le prime alle altre: IGP >EGP >Incomplete
AS path
usato per determinare i loop:
Ogni router traversato viene aggiunto ad una lista ordinata.
Vengono scartate tutte le routes che contengano loops.
Next hop
usato per indicare il next hop (numero IP del router che fa
l’advertising)
Community
E’ usato per raggruppare destinazioni (comunità) per le quali le decisioni di
routing debbano subire speciali trattamenti.
Per definire le comunità si usano Route maps.
Terminiamo l'articolo dicendo che il RIP è un protocollo molto usato ma è spesso sostituito dal OSPF soprattutto per reti molto grandi.
Grazie per l'attenzione
Riferimenti e approfondimenti:
Slide del Professore Peccorella dell'università degli studi di Firenze
Articoli presi su internet: Wikipedia