L'instradamento dei pacchetti

L'instradamento dei pacchetti è la tipica attività di una rete che si occupa di muovere i pacchetti dall'unità sorgente fino alla destinazione utilizzando la subnet di comunicazione, attraverso tutti i sistemi intermedi necessari (una serie di router), tipicamente facendo fare molti hop (salti) da un router all'altro. Questa attività è gestita dal livello tre dello schema OSI, ovvero dal livello di Rete o Network.

Le attività peculiari di questo livello sono, oltre alla scelta del cammino migliore, la gestione del flusso dei dati e delle congestioni nonché la risoluzione delle problematiche di interconnessione tra reti diverse.

Il funzionamento delle sottoreti di comunicazione può essere di due tipi:

• Connection-oriented (o circuiti virtuali), in cui viene stabilito un circuito virtuale fra sorgente e destinazione e tutti i router lungo il cammino seguono le indicazioni fornite;
• Connectionless, in cui i router stabiliscono, sulla base della destinazione fornita (e solo quella) come far proseguire la trasmissione; ciò avviene attraverso delle tabelle di instradamento (routing table) che indicano, per ogni possibile destinazione, quale linea di uscita dal router bisogna utilizzare (le tabelle sono utilizzate anche nel caso di trasmissioni basate sui circuiti virtuali, ma solo in fase iniziale).

Alcune caratteristiche e conseguenze del tipo di funzionamento delle subnet di comunicazione sono riassunte dalla tabella seguente: 

Algoritmi di routing

Gli algoritmi di routing si occupano di decidere su quale linea in uscita dal router debbono essere instradati i pacchetti e tale porzione del software di rete viene applicato a tutti i pacchetti delle sottoreti datagram, solo nel setup del circuito nel caso di sottoreti a circuiti virtuali (si parla di session routing). Le caratteristiche che si richiedono a questi algoritmi sono sostanzialmente gli stessi richiesti agli algoritmi in generale tenendo però conto che su alcuni aspetti ci possano essere contraddizioni. Un esempio illuminante può essere la ricerca dell'ottimalità che può essere sia rivolta alla riduzione dei ritardi, sia all'aumento dei pacchetti trasmessi (richieste in conflitto tra loro).

Possiamo distinguere due classi principali di algoritmi di instradamento:

• non adattivi o statici (static routing), in cui le decisioni di routing sono prese all'avvio della rete e non vengono più modificate
• adattivi o dinamici (dynamic routing), in cui le decisioni di routing sono riformulate molto spesso. Le modalità con cui le decisioni vengono cambiate possono essere diverse: 
  - le informazioni arrivano solo dal router locale, oppure solo da quelli adiacenti, oppure da tutti
  - le decisioni vengono riviste ad intervalli di tempo prefissati, oppure in seguito al cambiamento di traffico o topologia delle reti
  - il metro di valutazione utilizzato può essere la distanza, il numero dei salti tra i router o il tempo stimato per il transito.

Principio di ottimalità. Utilizzato per ottimizzare i percorsi di instradamento. Supponiamo di avere tre nodi i, j e k. Supponiamo inoltre che il cammino ottimo fra i e k sia stato individuato e lo indichiamo con (i, k). Allora: se il nodo j si trova sul cammino (i, k), il cammino ottimo (j, k) è il sottocammino tra j e k che si trova su (i, k). 

Per conseguenza di questo principio, l'insieme dei cammini ottimi da tutti i router ad uno specifico router costituisce un albero, anche detto sink tree per quel router (il cui vertice è il router di destinazione).

Algoritmi statici. I principali algoritmi di questa categoria sono:

• routing a cammino minimo (shortest path routing), in cui si calcola il cammino minimo che congiunge una coppia di router (problema analogo alla ricerca del cammino minimo in un grafo). In realtà la grandezza da minimizzare può essere di vario tipo, ad esempio: la lunghezza dei collegamenti, il numero degli hop da effettuare, il tempo medio di attesa e trasmissione, o anche una combinazione fra tutte queste possibilità;
• flooding, (non propriamente un algoritmo di routing ma molto utile soprattutto nel caso di informazioni distribuite) che consiste nell'inviare un pacchetto su tutte le linee eccetto che sulla linea da cui è arrivato. Questo algoritmo ha l'inconveniente di generare molti pacchetti e quindi incrementare il traffico di rete, ma esistono tecniche per limitare il traffico prodotto, ad esempio ricorrendo ad un contatore (che decresce ad ogni hop, in modo da eliminare il pacchetto quando arriva a zero) oppure applicando un flooding selettivo (duplicando i pacchetti solo verso le linee che vanno all'incirca nella giusta direzione) oppure eliminando le copie di pacchetti già ricevuti;
• routing a ritardo minimo (flow-based  routing), in cui si sceglie il cammino che minimizza il ritardo medio dell'intera rete. Una volta in possesso di informazioni quali la topologia della rete, la matrice delle quantità di traffico stimate e le capacità dei canali è possibile calcolare in anticipo il ritardo medio atteso su ogni linea, espresso come somma pesata dei ritardi su ogni singola linea dell'intero collegamento (dove il peso di ogni linea si ottiene dal rapporto fra traffico della linea e traffico totale della rete).

Algoritmi dinamici. Sono gli algoritmi adottati nelle reti attuali. L'esecuzione avviene sia nella fase iniziale per creare le tabelle di routing, sia in fasi successive per modificarle laddove opportuno. I principali algoritmi di questa categoria sono:

• routing basato sulla distanza (distance vector routing), in cui la tabella di routing (che contiene informazioni sulla distanza, numero di hop, ritardo, ... di ogni router) viene aggiornata con regolarità sfruttando i dati acquisiti dal router stesso sui router adiacenti, che avviene mandando speciali pacchetti ECHO, e le tabelle dei router adiacenti (in maniera ricorsiva). Dunque ogni router riceve la tabella dei vicini e manda la propria agli stessi e provvede a calcolare la concatenazione migliore per ogni destinazione. L'aspetto negativo è che la reazione alle cattive notizie è molto lenta (in caso di mancato collegamento ad un nodo la distanza tende ad aumentare, problema noto come count-to-infinity). Questo algoritmo è usato in Internet col nome di RIP (Routing Internet Protocol)
• routing basato sullo stato dei collegamenti (link state routing), in cui ogni router analizza lo stato dei collegamenti con i suoi vicini ed invia tali informazioni a tutti gli altri, ricevendo da questi informazioni dello stesso genere. La tabella di routing, che viene aggiornata in seguito ad eventi significativi o ad intervalli regolari, viene così formata ricostruendo la struttura topologia della rete e calcolando il cammino minimo con tutti gli altri. Un altro pacchetto tipico (oltre ad ECHO) è denominato HELLO ed è inviato all'avvio del router, in risposta al quale ogni router invia il proprio indirizzo. La distribuzione dei pacchetti nelle varie fasi avviene tramite il flooding. Questo algoritmo è molto usato in Internet col nome di OPSF (Open Shortest Path First).

Il routing statico è preferito in situazioni periferiche di dimensioni ridotte, ovvero in condizioni di gestione semplificata dell'intera rete. Al contrario, laddove sono possibili frequenti cambi di topologia, variazioni di prestazioni in dipendenza del carico di lavoro dei router e dei link, dei guasti e dei percorsi, o di altre ragioni similari, è preferito l'utilizzo del routing dinamico.

Routing gerarchico. Per semplificare il lavoro dei router nella raccolta dei dati e nella formulazione delle tabelle di routing si fa ricorso ad una struttura di tipo gerarchico. Per evitare l'acquisizione e il mantenimento dell'intera topologia, la rete viene divisa in zone (o regioni) per le quali valgono le seguenti proprietà:

• i router presenti all'interno di una regione (router interni) hanno dati di routing relativi ad ogni altro router della regione
• i router di una regione che devono spedire dati in un'altra regione sanno che devono passare attraverso un particolare router della propria regione (router di confine)
• i router di confine che devono far arrivare dati in un'altra regione sanno a quale router dell'altra regione (sempre di confine) devono spedire i dati.

Per via di questa modalità di instradamento si possono identificare due livelli di routing (ma in generale i livelli possono essere anche più di due):
- il primo, che si svolge all'interno di ogni regione; le tabelle di routing in questo caso contengono una voce per ogni altro router interno e per ogni altra regione, con l'indicazione del router di confine e della linea da percorrere
- il secondo, che si svolge tra tutti i router di confine; le tabelle di routing in questo caso contengono una voce per ogni altra regione, con l'indicazione del router di confine e della linea da percorrere.

Internetworking.

La connessione di reti eterogenee, caratterizzate da architetture a volte completamente differenti, è un problema di non banale soluzione. A volte le differenze si collocano su molteplici livelli: i servizi offerti dai livelli sono difformi, i formati dei pacchetti e degli indirizzi sono diversi, la dimensione massima dei pacchetti è differente, i meccanismi di controllo sono discordanti. La risoluzione di questi problemi di tipo "comunicativo" avviene attraverso tecniche specifiche che si basano su particolari dispositivi: i bridge (vedi reti locali) e i router multiprotocollo.

I router multiprotocollo. Sono dei router in grado di gestire contemporaneamente pile diverse di protocolli. Tipiche implementazioni di questi dispositivi sono:

• reti di router multiprotocollo, in cui ogni rete può comunicare con le altre reti ad essa conformi e con reti costituite da router multiprotocollo. Nell'esempio in figura i pacchetti di tipo X possono viaggiare nelle reti X e nella rete multiprotocollo, discorso analogo per i pacchetti del tipo Y;

• tunneling, utilizzato per mettere in comunicazione reti uguali per mezzo di una rete diversa. Nell'esempio in figura i pacchetti di tipo X vengono incapsulati in pacchetti di tipo Y per mezzo dei router multiprotocollo e quindi fatti viaggiare attraverso la rete Y. Ciò avviene aggiungendo ai pacchetti di tipo X, che quindi hanno già un header X, un header di tipo Y, ovvero

[Header X][Dati] ---> [Header Y][Header X][Dati] ---> [Header X][Dati]

Ulteriori tecniche.
Il problema della dimensione troppo grande dei pacchetti viene risolto attraverso una frammentazione degli stessi prima di consegnarli alla rete di transito e una ricomposizione nella rete di destinazione.
Se tutte le reti coinvolte offrono servizi connessi nel livello di Rete è possibile una concatenazione di circuiti virtuali attraverso porzioni di circuito virtuale in tutte le reti e con i necessari router multiprotocollo per l'attraversamento.
Il problema dei circuiti è diffuso a livello di Trasporto, visto che offre quasi sempre servizi connessi. Le apparecchiature che realizzano i circuiti sono dette transport gateway.
Il problema della spedizione dei dati fra due reti con differenti architetture viene risolto dalle application gateway, attrezzature capaci di convertire i dati a livello di Applicazione.

Internetwork routing. Le singole reti collegate ad Internet sono generalmente entità autonome, divise in gruppi (ciascuno controllato da un'unica autorità amministrativa) e chiamate AS (Autonomous System), connesse tra loro da dorsali (backbone) ad alta velocità. Ogni AS è identificato da un numero univoco a livello internazionale rilasciato dall'autorità che rilascia gli indirizzi Internet.    

Il routing in questo caso è a due livelli:

• livello IGP (Interior Gateway Protocol), che identifica l'algoritmo di routing utilizzato da ogni singolo AS al proprio interno (algoritmo che può essere diverso da rete a rete). Un IGP può essere anche gerarchico in caso di grosse dimensioni (e quindi dividersi in ulteriori livelli di routing);
• livello EGP (Exterior Gateway Protocol), che identifica l'algoritmo utilizzato per il routing fra diversi AS. Tipicamente questo algoritmo viene implementato dai router multiprotocollo.

Ogni AS può essere visto, inoltre, come composizione di reti di calcolatori e dorsali di collegamento.  Le funzioni dei router, le modalità d'esecuzione e gli algoritmi utilizzati dipendono dunque dalla dislocazione logica, che può essere: internamente ad una rete (IGP), sul confine di una rete (IGP), nell'area della dorsale dell'AS (IGP), sul confine dell'AS (EGP). Ciascun Internet Service Provider è un AS che usa un protocollo EGP per far conoscere la presenza dei propri clienti, e delle relative reti, agli altri ISP. Quando una destinazione è stata resa nota, quella destinazione può iniziare a ricevere dati dalla rete globale.

Routing multicast. Questo routing è speciale perché consente di raggiungere molte destinazioni con un unico pacchetto inviato ad un indirizzo di gruppo. In pratica, mentre il routing unicast permette l'invio di un pacchetto ad una sola destinazione (e quindi per raggiungere molte destinazioni bisogna creare da subito molte copie del pacchetto), il routing multicast permette l'invio di un pacchetto ad un numero arbitrario di destinazioni nella maniera più efficiente, anche seguendo un numero arbitrario di percorsi. Alcune situazioni tipiche nelle quali è richiesto l'instradamento multicast sono: il broadcast media (audio, video), l'aggiornamento simultaneo di dati (come le quotazioni di borsa), le applicazioni condivise (come le teleconferenze), i giochi interattivi, ecc.

La soluzione utilizzata permette l'invio dei pacchetti interessati ad un indirizzo di gruppo (o indirizzo multicast). L'elemento base del multicast è comunque il concetto di gruppo, che nasce quando il primo elemento si aggrega (attraverso una registrazione) e termina quando tutti gli elementi si dissociano. 

Il multicast in ambito LAN (senza l'attraversamento di un router) viene realizzato attraverso un indirizzo multicast utilizzato in quel dominio di broadcast. In generale, per "associare" unità appartenenti a reti diverse, poiché un normale router è sprovvisto delle funzionalità necessarie, occorre utilizzare dei router con algoritmi specifici (e sono detti Multicast routing o Mrouter). 

L´algoritmo più semplice per realizzare il routing multicast è denominato flooding e consiste nell'inoltro del pacchetto se questo è stato ricevuto per la prima volta. Questo algoritmo, seppur molto robusto, crea problemi di memoria in quanto ogni router deve ricordarsi tutti i pacchetti ricevuti per un certo lasso di tempo, onde evitare l'aumento indiscriminato di traffico in rete. L'instradamento viene così risolto individuando un albero di distribuzione (spanning tree) che comprenda tutti i nodi interessati, gestendo in maniera opportuna le tabelle di routing generate per la normale distribuzione unicast e cercando di evitare i problemi di loop dei pacchetti. I problemi legati al loop dei pacchetti sono risolti facendo in modo che ciascun nodo sia attraversato una sola volta. Le possibilità principali sono due:

• albero basato sul gruppo (group-shared tree), quello più utilizzato, che prevede un unico spanning tree per tutti i nodi del gruppo; l'albero viene costruito cercando percorsi di distribuzione che rendano minimo il costo dei percorsi utilizzati in generale (non rispetto ad una specifica sorgente),
• albero basato sulla sorgente (source-based tree), che prevede uno spanning tree diverso per ciascuna sorgente; è poco utilizzato in ambiti non locali perché l'ottimizzazione ha bisogno di conoscere il costo di ogni collegamento, e sue eventuali variazioni,

Molti router utilizzano la tecnica di instradamento Reverse Path Forwarding (RPF) con la quale un pacchetto viene inoltrato a tutte le altre sorgenti, esclusa quella di provenienza, solo se arriva dal percorso ottimale. Questa tecnica può essere ulteriormente migliorata con le tecniche di potatura (pruning) che permettono di escludere i nodi "foglia" non interessati (già raggiunti in precedenza). In generale, l'unione delle due tecniche è noto come diffondi e pota (broadcast and prune).