1
Il Routing
In un sistema packets switching quale il TCP/IP, il routing rappresenta il processo di scelta del percorso su cui inoltrare i pacchetti ed il router è un computer che effettua tale instradamento.
I router sono quindi dei dispositivi che scelgono il percorso che i datagrammi prenderanno per arrivare a destinazione. Un router deve avere almeno due schede di rete ciascuna collegata ad una rete diversa. Le reti a cui un router è collegato possono essere connesse ad altre reti che esso non conosce direttamente.
Gli scenari possibili sono due: sia l'emittente che il destinatario appartengono alla stessa rete oppure vi è almeno un router tra il mittente e il destinatario.
1. l'host locale ed il remoto appartengono alla stessa rete fisica (es. una singola rete Ethernet), in questo caso non sarà coinvolto alcun router, si parla di rimessa diretta
2. l'host destinazione è connesso ad una rete fisica diversa, diventa quindi necessario instradare il datagramma sorgente attraverso un router e allora si parla di rimessa indiretta.
Quando un programma applicativo su un host tenta di instaurare una comunicazione con un host remoto, sia l'host locale che i router partecipano all'instradamento dei datagrammi IP fino alla loro destinazione.
Il caso più semplice è rappresentato da un PC con una singola porta su una rete Ethernet.
Esso deve conoscere innanzitutto:
• Il proprio indirizzo fisico (MAC address)
• Il proprio indirizzo IP
• La Netmask
• L’indirizzo di un router che connette la LAN al resto di Internet: il Default Gateway Il PC ha una tabella di routing in cui è indicato come instradare un pacchetto:
• Se il pacchetto è diretto ad un indirizzo IP della propria rete o sottorete viene instradato direttamente con il protocollo ARP (rimessa diretta).
• Se è diretto fuori viene inviato all’indirizzo del default gateway che lo instraderà ulteriormente (rimessa indiretta).
In caso di rimessa indiretta, il ruolo del router, soprattutto quello della tabella di routing, è molto importante.
• Il router riceve una trama proveniente da un terminale connesso a una delle reti a cui è collegato
• I datagrammi sono trasmessi al livello IP del router
• Il router guarda l'intestazione del datagramma
• Se l'indirizzo IP di destinazione appartiene a una rete cui una delle interfacce del router è collegata, allora il datagramma viene inviato alla destinazione
• Se l'indirizzo IP di destinazione fa parte di una rete diversa, il router consulta la propria tabella di routing per decidere il percorso da prendere
2
Struttura di una tabella di routing
La tabella di routing è una tabella di corrispondenza tra l'indirizzo del terminale di destinazione e il nodo seguente al quale il router deve consegnare il messaggio.
In realtà è sufficiente che il messaggio sia consegnato sulla rete alla quale appartiene il terminale di destinazione e non è quindi necessario memorizzare l'indirizzo IP completo del terminale ma solo l'identificatore di rete dell'indirizzo IP (cioè il netID) relativo alla rete di destinazione.
In questo modo le tabelle necessarie possono essere abbastanza piccole in quanto non è necessario memorizzare ogni indirizzo IP di destinazione ma solo quello delle reti (o sottoreti) di destinazione.
L’informazione comunemente contenuta in ogni riga di una tabella di instradamento è la seguente:
• Destination: rete di destinazione
• Gateway: IP address del router successivo verso la destinazione (Next Hop)
• Genmask : porzione dell’indirizzo IP indicante il prefisso di rete (Subnet Mask)
• Interface: identificatore della porta fisica dove trovare il next hop
• Metric: peso assegnato al cammino
La coppia destination+ subnet_mask serve per identificare la possibile sottorete di destinazione La coppia gateway + interface serve per determinare univocamente dove instradare il datagramma Esempio di una parte dell’output del comando route da un host Linux:
Destination Gateway Genmask Iface 87.250.77.0 0.0.0.0 255.255.255.0 eth0 87.250.78.0 0.0.0.0 255.255.255.0 eth1 127.0.0.0 0.0.0.0 255.0.0.0 lo 0.0.0.0 87.250.77.254 0.0.0.0 eth0
Grazie a questa tabella, il router, conoscendo l'indirizzo del destinatario incapsulato nel messaggio, può sapere a quale interfaccia inviare il messaggio (cioè quale scheda di rete usare), e a quale router, direttamente accessibile sulla rete a cui la scheda è connessa, inviare il datagramma.
Questo meccanismo consiste nel riconoscere solo l'indirizzo del prossimo passaggio che porta a destinazione e viene detto routing per salti successivi (in inglese next-hop routing).
Comunque può succedere che il destinatario appartenga ad una rete non referenziata nella tabella di routing. In questo caso il router usa un router di default .
Il messaggio è così inviato da un router ad un altro per salti successivi, fino a che si arriva ad un router che appartiene ad una rete direttamente connessa al destinatario. A questo punto è possibile inviare direttamente il messaggio al terminale di destinazione.
La ricerca nella tabella avviene utilizzando
• l’indirizzo IP di destinazione del datagramma
• l’indirizzo di destinazione e la netmask specificati in ciascuna riga della tabella Procedura:
• si esegue un’operazione di AND bit per bit tra l’indirizzo di destinazione del datagramma e la netmask di ciascuna riga
3
• il risultato viene confrontato con la destinazione specificata nella riga stessa: se coincidono, la riga è quella giusta
• il controllo viene effettuato a partire dalla riga che presenta una netmask con un numero maggiore di bit a uno: priorità alle route più specifiche (longest-prefix match- prima host, poi reti piccole, poi reti grandi)
• una volta trovata la riga corrispondente, il lookup si ferma e il datagramma viene instradato secondo la modalità specificata
• se nessuna riga corrisponde, si usa il gateway di default
Esempi di lookup
Destination netmask Ecc…
1 0.0.0.0 0.0.0.0
2 192.168.2.0 255.255.255.0 3 192.168.2.18 255.255.255.255
Confronto prima con riga 3, poi con riga 2 e poi riga 1
Esempio 1 Datagramma con IP dest. = 192.168.2.18
192.168.002.018 &
255.255.255.255 ---
192.168.002.018 == 192.168.002.018 La riga 3 è quella giusta (host specific)
Esempio 2 Datagramma con IP dest. = 192.168.2.22
192.168.002.022 &
255.255.255.255 ---
192.168.002.022 != 192.168.002.018
192.168.002.022 &
255.255.255.000 ---
192.168.002.000 == 192.168.002.000 La riga 2 è quella giusta (network specific)
Esempio 3 Datagramma con IP dest. = 80.48.15.170
080.048.015.170 &
255.255.255.255 ---
080.048.015.170 != 192.168.002.018
4 080.048.015.170 &
255.255.255.000 ---
080.048.015.000 != 192.168.002.000
080.048.015.170 &
000.000.000.000 ---
000.000.000.000 == 000.000.000.000 La riga 1 è quella giusta (default gateway) In sintesi
• Gateway = 0.0.0.0 & Iface ≠ lo consegna diretta
• Gateway = 0.0.0.0 & Iface = lo consegna agli strati superiori (TCP/UDP)
• Altrimenti consegna indiretta tramite il gateway indicato
Comandi per la configurazione di un nodo UNIX/Linux o Windows ifconfig mostra / configura le interfacce di rete (Linux)
route mostra / manipola la tabella di routing IP (Linux/Windows) arp mostra / manipola la cache ARP del sistema (Linux/Windows) nslookup effettua interrogazioni al DNS (Linux/Windows)
netstat mostra connessioni di rete, tabelle di routing, statistiche sulle interfacce (Linux/Windows)
ping comando che consente l’invio di pacchetti dall’host sender all’host receiver, in modo da poter valutare il tempo di transito dei pacchetti in rete. Maggiore è il tempo, più scarse sono le prestazioni della rete (Linux/Windows)
traceroute/
tracert
traccia tutto il cammino dei pacchetti dall'host all’indirizzo specificato dopo il comando, visualizzando tutti gli indirizzi e/o i nomi dei router che vengono attraversati (Linux/Windows)
ipconfig mostra le configurazioni IP di tutte le interfacce di rete (Windows)
5
Funzionamento di un router
I router in Internet formano una struttura interconnessa nella quale il datagramma scorre finché non raggiunge quel particolare router attraverso il quale può giungere direttamente a destinazione.
L'algoritmo che svolge queste funzioni (IP routing algorithm) utilizza su ogni macchina una tabella di routing (IP routing table), che contiene informazioni circa alcune possibili destinazioni e su come raggiungerle. Se comprendesse tutte le destinazioni possibili diventerebbe troppo grande e sarebbe impossibile tenerla aggiornata. Di solito si limita a mantenere le informazioni degli host sulla stessa rete o quelle più frequentemente usate lasciando un indirizzo di default per tutti gli altri.
I router svolgono la propria funzione utilizzando:
• algoritmi di routing (Routing Algorithm RA) usati per il calcolo delle tabelle di routing
• protocolli di routing (Routing Protocol RP) usati per lo scambio delle informazioni sulla topologia della rete necessarie per applicare l’algoritmo. I protocolli di routing si differenziano per le modalità con cui le tabelle di instradamento vengono create ed eventualmente aggiornate nel tempo.
In base al modo con il quale è creata la tabella di routing si parla di:
• routing statico (utilizzabile per piccole reti) - Se la tabella di routing è inserita manualmente dall'amministratore in fase di configurazione del router e modificata in caso di variazioni della rete. Le tabelle di instradamento sono invarianti nel tempo e indipendenti dalle condizioni di traffico della rete.
• routing dinamico distribuito - Se la tabella di routing viene creata e periodicamente aggiornata in modo automatico. Il calcolo può essere basato o su informazioni locali, riguardanti il solo router in cui sta avvenendo il calcolo o su informazioni distribuite, in questo caso si utilizzano informazioni relative agli altri router e deve quindi essere previsto un meccanismo di scambio delle informazioni fra di essi attraverso i protocolli di routing. Consente di adattare le decisioni di instradamento in seguito a variazioni topologiche della rete, inserimento di nuovi collegamenti, caduta di un collegamento per guasto, condizioni di traffico evitando la scelta di percorsi che comprendono collegamenti congestionati.
Per Internet si usano protocolli dinamici distribuiti. La rete si evolve continuamente senza un vero controllo centralizzato, la configurazione diventa quasi impossibile. La rete deve reagire automaticamente ai cambiamenti e ai guasti.
La rete Internet è ripartita in porzioni, dette Authonomous System (AS) ogni AS è identificato da un nome, ad esempio AS-25488. Un AS è una collezione di reti amministrate da un'unica autorità.
Ogni AS è responsabile del routing all'interno delle sue reti. Un AS può essere ulteriormente suddiviso in Aree di routing (Routing Area). I router all’interno di un area (router interni) sono in grado di effettuare l’instradamento relativamente alla sola area, per destinazioni al di fuori dell’area si limitano ad inviare i pacchetti a dei router “di bordo” (router esterni) che sono a conoscenza della topologia esterna dell’area. I router esterni si occupano solamente dell'instradamento dei pacchetti fra aree e sono il mezzo attraverso il quale gli AS si scambiano informazioni di raggiungibilità..
Gli AS decidono autonomamente i protocolli e le politiche di routing che intendono adottare.
I protocolli di routing all’interno di un AS sono detti Interior Gateway Protocol (IGP), esempi di questi protocolli sono RIP e OSPF.
I protocolli di routing fra AS sono l'Exterior Gateway Protocol (EGP), ormai obsoleto, ed il Border Gateway Protocol (BGP).
6
I protocolli di routing di tipo IGP
Lo scopo di un protocollo di routing è di comunicare dinamicamente le informazioni circa tutti i percorsi di rete utilizzabili per raggiungere una destinazione e di selezionare il miglior percorso, tra tutti i possibili, per raggiungere tale rete di destinazione. I termini "Distance Vector" e "Link State"
sono utilizzati per raggruppare i protocolli di routing in due categorie principali basandosi sul fatto se il protocollo di routing seleziona il percorso migliore basandosi sulla coppia di valori (distanza metrica, vettore) o calcolando lo stato di ogni link in un percorso e determinando quello che ha la metrica totale più bassa per raggiungere la destinazione.
La metrica può essere calcolata usando informazioni diverse, ad esempio:
• una misura periodica del tempo necessario per raggiungere realmente una destinazione
• il conteggio degli hop (salti) necessari per raggiungere una destinazione in modo da approssimare la distanza
• il calcolo del costo del cammino da seguire per raggiungere una destinazione, utilizzando fattori come il carico della rete, l'ampiezza della banda...
• un peso settato dall'amministratore per fare in modo che un percorso sia preferibile ad altri Possiamo suddividere i più importanti protocolli IGP di routing in tre categorie:
Distance Vector: RIPv1, RIPv2, IGRP Link-State: OSPF, IS-IS.
Hybrid: EIGRP
Distance Vector
Il protocollo di routing seleziona il percorso migliore basandosi sulla coppia di valori (distanza, vettore) .
Distanza - è il costo per raggiungere una destinazione, di solito è basato sul numero di host che si attraversano sul percorso o il totale di tutti i pesi assegnati ai link nel percorso.
Vettore - dal punto di vista dei protocolli di routing il vettore è l'interfaccia attraverso la quale viene inoltrato il traffico al fine di raggiungere una destinazione attraverso un percorso selezionato come
“il migliore” per raggiungere la destinazione.
Con un protocollo distance-vector il router manda periodicamente a tutti i router vicini ( neighbor) una coppia di informazioni circa le destinazioni che esso sa come raggiungere; la prima informazione (la distanza) dice quanto ritiene sia lontana la destinazione, la seconda dice quale direzione (vettore) usare per raggiungere la destinazione. La direzione indica il prossimo hop che l'ascoltatore (il router che riceve la coppia distance-vector) dovrebbe usare per raggiungere la destinazione. Il concetto è riassumibile con la frase “manda a me il pacchetto, alla interfaccia che ti indico come vettore, io so come inoltrarlo”. Per esempio un “RIP route update” è semplicemente una lista di destinazioni che il router che fa l'annuncio sa come raggiungere e pensa di sapere quanto siano lontane. I router che ricevono l'annuncio deducono che il prossimo hop da usare per quelle destinazioni potrebbe essere il router che fa l'annuncio se la metrica da esso indicata per una destinazione è migliore di quella già conosciuta; in questo caso aggiornano la propria tabella di routing per le nuove destinazioni apprese, modificandone la metrica aggiungendo il costo relativo alla propria tratta, ad esempio aumentando di uno l'hop count. Se ricevono informazioni sulla stessa destinazione da più router vicini mantengono l'informazione del router che ha la metrica migliore.
RIP significa Routing Information Protocol. Si tratta di un protocollo di tipo Distance Vector , cioè ogni router comunica agli altri router la distanza che li separa (il numero di salti che li separa).
7 Quando un router riceve uno di questi messaggi aumenta questa distanza di 1 e comunica il messaggio ai router direttamente accessibili. Questo protocollo prende in considerazione solo la distanza tra due terminali in termini di numero di hop, ma non considera lo stato della connessione per scegliere la miglior banda passante possibile.
Link state
Un protocollo link-state fornisce informazione sulla topologia della rete nelle sue immediate vicinanze. L'informazione che mantiene è una lista di segmenti di rete (link) ai quali il router è connesso e lo stato di questi link (up/down), questa informazione viene poi propagata sulla rete (flooded). Propagando l'informazione sulla rete ogni router può costruirsi una propria immagine sullo stato di tutti i link della rete. Poiché ogni router vede la stessa informazione tutte le immagini dovrebbe essere uguali. A partire dall'immagine ogni router calcola il suo percorso migliore per le destinazioni e popola la sua tabella di routing con queste informazioni.
Questi protocolli sono in grado di sapere se un link è up o down e quanto è veloce, determinando
“quanto costa arrivare lì”. I protocolli Link State scelgono il percorso che risulta essere più veloce anche se richiede più hops di un altro che però risulta più lento.
I router inviano lo stato delle proprie interfacce (i link) a tutti i router (o a tutti i router in una parte di rete chiamata area) solo quando c’è un cambiamento (link up/down).
OSPF (Open Shortest Path First) è un protocollo link-state, è più performante di RIP e lo sta pian piano sostituendo.
Hybrid
I protocolli definiti Hybrid, prendono alcune caratteristiche sia dai Link-State e sia dai Distance Vector. Infatti i protocolli Hybrid, nei routing updates, inviano solo le informazioni che realmente sono cambiate (caratteristica Link-State) e le inviano solamente ai propri vicini (neighbor) (caratteristica Distance Vector).
