Laboratorio di Calcolo Avanzato del Dipartimento di Fisica

Il Routing

La trattazione fin qui esposta riguarda reti con differenti mezzi fisici, ma, tuttavia, facenti parte della stessa LAN. Vediamo ora come l'instradamento procede su reti più estese, le cosiddette WAN.
I router appartengono a due categorie, End System (ES) ed Intermediate System (IS). Sui primi risiedono le applicazioni che comunicano usando la rete, i secondi hanno solo funzioni di instradamento dei messaggi.

Un primo problema è quello di identificare in modo univoco ogni nodo della rete. A tale scopo, ad ogni sistema viene associato un indirizzo numerico. Per ragioni di comodità viene solitamente utilizzata una codifica che prevede un nome invece di un indirizzo numerico. E' perciò necessario mantenere una corrispondenza biunivoca tra gli indirizzi e i nomi; per fare questo viene utilizzato un database distribuito detto "name server".

Nel caso in cui il mittente sia su una rete diversa dal destinatario è indispensabile un'operazione di internetworking: il mittente affida il pacchetto ad un IS che si occuperà di farlo giungere fino a destinazione.

Esistono tre diverse tecniche per l'instradamento dei pacchetti:

Routing by Network Address. Un sistema è indirizzato scrivendo nel pacchetto il suo indirizzo. Ogni IS usa tale indirizzo come chiave di ricerca nella sua tabella di instradamento e determina lungo quale cammino il pacchetto debba essere ritrasmesso. Tale tecnica è in generale adottata dai protocolli non connessi; è usata, ad esempio, in Decnet, in OSI-Clns e in IP.
Label Swapping. E' generalmente utilizzata nei protocolli connessi e trova applicazioni in ATM e APPN. Ogni pacchetto è marcato con una label che serve come chiave in una tabella di instradamento sull'IS. L'IS, prima di ritrasmettere il pacchetto, sostituisce la label con una nuova; in questo modo le label devono essere univoche solo all'interno di un dato link. Se il protocollo è connesso le label non sono altro che gli identificativi delle connessioni.
Source Routing. E' una tecnica usata dai bridge token ring.

L'OSI delega la funzionalità di instradamento al livello 3 e in particolare agli IS detti anche router.

Routing by Network Address

Su reti ad accesso multiplo come le LAN si devono stabilire le relazioni tra gli indirizzi di livello 2 sottolivello MAC e gli indirizzi di livello 3 per poter effettuare l'instradamento. Questo è necessario, in quanto l'indirizzo di livello 3 serve per identificare il destinatario finale di un pacchetto nell'ambito dell'intera rete, mentre quello di livello 2MAC serve a discriminare il destinatario finale di un pacchetto nell'ambito di una LAN.
E' anche possibile che un nodo con un solo indirizzo di livello 3 abbia più indirizzi di livello 2MAC (uno per ogni interfaccia di rete); l'unica eccezione di rilievo è data dal TCP/IP che ha un indirizzo di livello 3 per ogni scheda di rete. Per mantenere le corrispondenze tra gli indirizzi dei due livelli viene spesso utilizzato il protocollo ARP (Address Resolution Protocol).
Vediamo con l'aiuto della figura seguente il ruolo dei due tipi di indirizzi.

Supponiamo di voler trasmettere un pacchetto dall'ES B all'ES A.
B genera un pacchetto di livello 3 con L3-DSAP=A e L3-SSAP=B che rimarrà immutato fino a destinazione. B verifica se A è sulla sua stessa LAN e, poichè non è così invia il mmessaggio ad R2 specificando L2-DSAP=R2 e L2-SSAP=B.
L'IS R2 riceve il pacchetto ed utilizza le sue tabelle di instradamento per decidere di ritrasmettere il messaggio sul CDN. In questo caso non sono necessari gli indirizzi di livello 2 perchè stiamo inviando il pacchetto in un canale punto-punto.
R1 riceve il pacchetto e decide che deve trasmetterlo ad A tramite la LAN. Usando, ad esempio, un algoritmo di ARP ricava l'idirizzo di livello 2 di A a partire dal suo indirizzo di livello 3 e quindi effettua la trasmissione del pacchetto.
A riceve il pacchetto e, poichè lo L3-DSAP è uguale al suo indirizzo di livello 3, non lo inoltra ulteriormente sulla rete, ma lo passa ai suoi livelli superiori.

Le tabelle di instradamento possono essere scritte manualmente dal gestore della rete oppure calcolate automaticamente da un opportuno algoritmo. Tale algoritmo opera scambiando tra gli IS informazioni relative alla topologia e allo stato della rete. Ogni IS deve conoscere quali ES sono collegati alla sua stessa LAN per inserirli nelle tabelle e propagare l'informazione della loro raggiungibilità ad altri IS. Vale anche il viceversa, perché ogni ES deve sapere a chi inviare i messaggi non destinati ai nodi collegati alla stessa LAN. Questo problema è noto con il nome di "Neighbor Greetings".

A differenza dei bridge che sono trasparenti al protocollo di livello 3, nel senso che ignorano il contenuto del campo INFO di livello 2, i router operano a livello 3 e utilizzano per l'internetworking tutte le informazioni contenute nella busta di questo livello. Visto che le buste di livello 3 di diverse architetture di rete (Decnet, TCP/IP, etc) hanno formati incompatibili si è reso necessario l'uso di router multiprotocollo che devono replicare il modulo di instradamento (che contiene l'agoritmo di calcolo della tabella di instradamento, la tabella di instradamento ed il processo di forwardind del pacchetto) per ogni protocollo.
E' anche stata sviluppato un modulo detto di bridging per trattare quei protocolli che non hanno un livello 3 quali, ad esempio, LAT, MOP etc.

Molto spesso a livello 3, oltre al protocollo per trasportare i dati utente, sono definiti uno o più protocolli ausiliari per il neighbor greetings e per permettere ai router di scambiarsi informazioni di instradamento. La necessità di realizzare funzionalitè di gestione (management) del router rende necessaria la presenza negli IS di protocolli specifici per la gestione, che sono collocati nei livelli superiori al terzo (lo standard "de facto" e con cui si opera normalmente sulle apparecchiature di rete è SNMP).

Il livello network può offrire servizi di tipo connesso e non connesso: l'implementazione dei servizi connessi (CONS) avviene tramite circuiti virtuali mentre i servizi non connessi (CLNS) sono adottati nelle reti quali Decnet e TCP/IP.

Algoritmi di instradamento

Per instradare un pacchetto un router si basa sull'indirizzo del destinatario finale e sulle tabelle di instradamento. Tuttavia, un router si trova ad elaborare pacchetti che, la maggior parte delle volte, devono attraversare più LAN e la scelta della porta su cui immettere i dati non è più univoca. Ci possono essere più cammini alternativi e la scelta è influenzata da due parametri principali, quali il n° di router che il pacchetto deve attraversare per giungere a destinazione (hops) o il costo, cioè la somma dei costi di tutte le linee attraversate. Il costo di una linea è inversamente proporzionale alla velocità di una linea stessa, mentre gli hops rappresentano dei ritardi introdotti dai routers attraversati.

Gli algoritmi di instradamento hanno la funzione di ottimizzare l'utilizzo delle linee e devono avere alcune caratteristiche:

Devono essere molto semplici, poiché i routers hanno CPU e memoria finite e potrebbero introdurre dei ritardi inaccettabili.
Devono permettere ai routers di adattarsi a voluti o imprevisti cambiamenti di topologia senza interrompere il funzionamento della rete.
Devono convergere velocemente ad un instradamento stabile, la modifica delle tabelle di instradamento deve avvenire soltanto a fronte di un cambiamento di topologia.
Nessun nodo deve essere privilegiato o danneggiato.

Gli algoritmi si dividono in due categorie, non adattativi ed adattativi.
I primi utilizzano criteri fissi di instradamento e sono, perciò, statici e deterministici, i secondi calcolano ed aggiornano le tabelle di instradamento in funzione della topologia della rete e dello stato dei link e sono così dinamici e non deterministici.

Nelle reti con topologia ad albero i primi sono i più efficienti, poiché sono più semplici. Dove invece la configurazione della rete è magliata, per sfruttare al meglio ogni possibile percorso è bene utilizzare algoritmi dinamici.
Appartengono al primo gruppo il Fixed Directory Routing ed il Flooding, mentre appartengono al secondo il Routing Centralizzato, il Routing Isolato ed il Routing Distribuito.
Gli algoritmi di più moderna concezione sono quelli distribuiti che si dividono ulteriormente in due categorie: Distance Vector e Link State Packet.

Fixed Directory Routing

Il Fixed Directory Routing prevede che ogni nodo abbia una tabella di instradamento che metta in corrispondenza il nodo da raggiungere con la linea da usare. Queste entry sono puramente statiche, poiché è il gestore che si occupa di determinarle e di configurare il router. Il gestore ha così il completo controllo sul traffico ed è necessario un suo intervento in caso di guasti.

È comodo utilizzare quest'algoritmo nelle zone più periferiche di una rete, dove esiste un solo collegamento che le interconnette al resto della rete, poiché risulta difficoltoso gestire le tabelle in reti di grandi dimensioni; le regole di instradamento specificate su ogni singolo router prendono il nome di route statiche.

Flooding

Ciascun pacchetto che arriva ad un router viene instradato su tutte le porte, eccetto quella da cui è arrivata. Con questo metodo, concepito per reti militari, si massimizza la probabilità che i dati arrivino a destinazione, ma si induce sulla rete un carico molto elevato. Per limitare il carico prodotto si può introdurre un age-counter che permette di eliminare i pacchetti che hanno attraversato molti router, oppure si può usare una tecnica che prevede di scartare i pacchetti che passano da un router per la seconda volta.

Routing Centralizzato

Si presuppone che esista un RCC, Routing Control Center, che conosca la topologia di tutta la rete e che calcoli e distribuisca le tabelle di instradamento per ogni router della rete.

Questo metodo consente una gestione della rete molto accurata, in quanto le tabelle possono essere calcolate con algoritmi sofisticati, ma implica l'ipotesi di un gestore a livello mondiale, ipotesi oggi sicuramente non realistica. Il RCC dovrebbe essere duplicato e la porzione di rete intorno ad esso sarebbe soggetta ad un elevato volume di traffico di servizio; inoltre, in caso di guasti, possono verificarsi situazioni in cui il RCC perde il contatto con intere porzioni di rete e che si verifichino degli aggiornamenti solo parziali che potrebbero portare a situazioni di loop.

Routing Isolato

È un metodo esattamente opposto al precedente. Infatti, ogni router presente in rete calcola le proprie tabelle di instradamento in maniera del tutto indipendente dagli altri.

L'algoritmo più diffuso è il Backward Learning, utilizzato con successo nei bridge IEEE 802.1D all'interno di una LAN. La modifica più importante per adattarlo a situazioni più estese è l'aggiunta nell'header del pacchetto di un campo di costo, inizializzato a zero dalla stazione mittente ed incrementato da ogni stazione intermedia, di modo che ogni router possa modificare la propria tabella se si accorge che una stazione è raggiungibile con un costo minore.

Un limite di questo algoritmo è che i router si accorgono soltanto di eventuali miglioramenti dello stato della rete. È necessario, quindi, che le entry dinamiche restino valide solo per un determinato periodo di tempo, allo scadere del quale vengono riaggiornate.

Routing Distribuito

È una fusione dei due metodi sopra descritti. Non esiste un RCC, ma le sue funzionalità sono realizzate in modo distribuito da ogni singolo nodo della rete. Le tabelle vengono aggiornate dai routers scambiandosi fra loro informazioni di servizio mediante un apposito protocollo. Le tabelle di instradamento, come già detto in precedenza, vengono calcolate a partire dai due parametri: costo e hops. Il costo di ciascuna linea di ciascun router è un parametro che viene impostato dal network manager tramite il software di gestione dei router stessi. Oggi gli algoritmi distribuiti principali sono il Distance Vector ed il Link state Packet (lo stato dell'arte), descritti nei paragrafi seguenti.

DISTANCE VECTOR

Ogni router mantiene in memoria, oltre alla propria tabella di instradamento, una struttura dati, detta appunto Distance Vector per ogni linea. Il Distance Vector associato a ciascuna linea contiene informazioni ricavate dalla tabella di instradamento del router collegato all'altro estremo della linea.
Il calcolo delle tabelle di instradamento avviene tramite un processo di funzione di tutti i distance vector associati alle linee attive del router. Tutte le volte che un router calcola una nuova tabella di instradamento, la invia agli IS adiacenti (cioè quelli collegati da un cammino fisico diretto) sotto forma di distance vector.

Ogni entry è composta da quattro parametri, indirizzo, hops, costo e linea, e la tabella contiene entry relative ad ogni nodo presente in rete.

Indirizzo	Hops	Costo	Linea
1	3	25	3
2	5	35	2
3	9	50	6
4	1	5	7
5	0	0	0

Tabella 4.1 Tabella di instradamento

Si nota che il router a cui appartiene questa tabella ha indirizzo 5, poiché appare raggiungibile con costo 0 ed in 0 hops.

Il Distance Vector da inviare al router adiacente è composto dalle prime tre colonne. Il router che lo riceve prima di tutto verifica se vi sono delle modifiche dal precedente e, in caso affermativo, aggiorna i campi hops e costo, sommando 1 a tutti gli hops e sommando il costo della linea da cui è arrivato il messaggio al campo costo. Il passo successivo è l'aggiornamento della propria tabella tramite un processo di fusione (merge) di tutti i Distance Vector a lui pervenuti da ogni linea attiva.
La fusione avviene selezionando dalle entry con indirizzo uguale quella con il minor costo. A parità di costo, si seleziona quella che ha il minor numero di hops. La selezione avviene in maniera casuale se entrambi i parametri sono uguali.
Un vantaggio di questo algoritmo è la facile implementazione. Tuttavia è sconsigliato utilizzarlo in reti con più di mille nodi, poiché ha una complessità elevata (esponenziale nel caso peggiore). Inoltre è lento a convergere, poiché dipende dalla velocità del router più lento presente in rete.

Questo algoritmo è usato in Decnet fase IV e in alcune realizzazioni di TCP/IP (RIP e IGRP)

LINK STATE PACKET

Questo algoritmo presuppone che ogni router abbia in memoria la mappa di tutta la rete. Non è pensabile che questa mappa sia scritta nel router da management, ma ogni router, a differenza dell'algoritmo precedente, coopera per crearla e mantenerla aggiornata, poi calcola indipendentemente la propria tabella.

Supponiamo di avere una rete con 6 nodi come in figura.

Un router apprende, tramite protocolli Neighbor Greetings, i primi n nodi vicini, associando ad ognuno di essi il costo della linea.

Il passo successivo consiste nel propagare tale informazione ai router presenti in rete tramite un messaggio definito Link State Packet (LSP). La propagazione avviene con un algoritmo di tipo Flooding.

Adiacente	Costo
B	3
F	4
G	3

LSP nodo D

La mappa della rete si costruisce fondendo ogni LSP e viene memorizzata in una LSP base dati del formato mostrato nella tabella seguente.

A	B/3	E/1
B	A/3	C/9	D/3
C	B/9	G/5
D	B/3	F/4	G/3
E	A/1	F/2	G/10
F	D/4	F/2
G	C/5	D/3	E/10
H	G/3

LSP Data Base

Si nota che tale database è simile ad una matrice di adiacenza di un grafo che rappresenta la rete intera. Tale database, se l'algoritmo converge, deve risultare uguale in ogni IS della rete.
Il LSP database, rappresentando la mappa della rete con i costi associati, è l'informazione necessaria e sufficiente affinchè un router possa calcolare le sue tabelle di instradamento.
Si noti la differenza con il distance vector: in quel caso i router cooperano direttamente per calcolare le tabelle di instradamento, qui i router cooperano per mantenere aggiornata la mappa della rete, poi ogni router calcola la propria tabella di instradamento in modo autonomo.
Il calcolo della tabella di instradamento si riduce ora al calcolo dello spanning tree di tipo SPF (Shortest Path First) e lo si effettua tramite il noto algoritmo di Dijkstra.

Lo spanning tree ad esempio del nodo D risulterà come nella figura seguente:

Ecco la relativa tabella di instradamento.

A	l3
B	l3
C	l2
E	l1
F	l1
G	l2
H	l2

Tabella di instradamento nodo D

Questo algoritmo è capace di gestire reti di grandi dimensioni grazie alla sua rapida convergenza ed il suo comportamento è prevedibile, poiché ogni nodo ha in memoria la mappa intera della rete. Difficilmente si generano loop e, comunque, risulta facile identificarli ed eliminarli.

Algoritmi di tipo link state packet sono utilizzati nello stadard IS-IS e nel protocollo OSPF (adottato in alcune reti TCP/IP).

Routing Gararchico

Anche adottando algoritmi LSP non è certo pensabile che essi riescano a trattare qualsiasi rete di qualsiasi dimensione (si pensi a Internet con le sue decine di milioni calcolatori collegati nel mondo). Quindi occorr organizzare il routing in modo gerarchico, cioè partizionare la rete in aree. All'interno dell'area il routing segue esattamente le regole descritte in precedenza. Quando invece bisogna far comunicare due nodi appartenenti ad aree diverse (routing inter-area) si divide il problema in tre sottoproblemi:

instradamento tra il nodo mittente e la periferia dell'area cui il nodo mittente appartiene
instradamento tra l'area mittente e l'area destinazione
instradamento all'interno dell'area destinazione

La figura precedente mostra una rete ripartita in tre aree.
Supponiamo di dover instradare il messaggio dal nodo G al nodo A.
In una prima fase si invia il messaggio ad F. F deve instradare il messaggio all'area 1 ed ha due possibilità: il cammino diretto con costo 3 o quello indiretto con costo 4 (tramite l'area 2). Sceglie ovviamente il cammino diretto e passa il messaggio ad E, che lo passa a D, che lo passa a B che lo recapita ad A, nodo destinatario.
Si noti che l'instradamento ottenuto è ottimale, ma non ottimo: infatti il suo costo è pari a 16 mentre se si fosse passati da C sarebbe stato pari a 10.
Questo è uno degli svantaggi del routing gerarchico in quanto, non avendo una visione globale della rete, si compiono tante scelte ottime di per se, ma che considerate nell'insieme possono non rappresentare l'ottimo globale.