5) Il livello tre (Network)

Il livello network è incaricato di muovere i pacchetti dalla sorgente fino alla destinazione finale, attraversando tanti sistemi intermedi (router) della subnet di comunicazione quanti è necessario.

Ciò è molto diverso dal compito del livello data link, che è di muovere informazioni solo da un capo all'altro di un singolo canale di comunicazione wire-like.

Le incombenze principali di questo livello sono:

• conoscere la topologia della rete;
• scegliere di volta in volta il cammino migliore (routing);
• gestire il flusso dei dati e le congestioni (flow control e congestion control);
• gestire le problematiche derivanti dalla presenza di più reti diverse (internetworking).

Nel progetto e nella realizzazione del livello network di una architettura di rete si devono prendere decisioni importanti in merito a:

• servizi offerti al livello transport;
• organizzazione interna della subnet di comunicazione.

5.1) Servizi offerti

In merito ai servizi offerti al livello superiore, ci sono (come abbiamo già accennato) due tipologie fondamentali di servizi:

• servizi connection-oriented;
• servizi connectionless.

In proposito, ci sono due scuole di pensiero:

• fautori dei servizi connection-oriented (compagnie telefoniche);
• fautori dei servizi connectionless (Internet Community).

La prima scuola di pensiero afferma che il livello network deve fornire un servizio sostanzialmente affidabile e orientato alla connessione. In questa visione, succede che:

• le peer entitiy stabiliscono una connessione, negoziandone i parametri (di qualità, di costo, ecc.), alla quale viene associato un identificatore;
• tale identificatore viene inserito in ogni pacchetto che verrà inviato;
• la comunicazione è bidirezionale e i pacchetti viaggiano, in sequenza, lungo il cammino assegnato alla connessione;
• il controllo di flusso è fornito automaticamente (attraverso alcuni dei parametri negoziati, come ad esempio il dimensionamento di una o più finestre scorrevoli).

La seconda scuola di pensiero ritiene invece che la sottorete debba solo muovere dati e nient'altro:

• la sottorete è giudicata inerentemente inaffidabile, per cui gli host devono provvedere per conto proprio alla correzione degli errori e al controllo di flusso;
• una ovvia conseguenza è che il servizio offerto dal livello network dev'essere datagram, visto che è inutile inserire le funzioni di controllo degli errori e del flusso in due diversi livelli;
• i pacchetti viaggiano indipendentemente, e dunque devono tutti contenere un identificatore (ossia l'indirizzo) della destinazione.

Di fatto, il problema è dove mettere la complessità della realizzazione:

• la prima scuola la mette nei nodi della subnet, che si devono occupare del setup delle connessioni e di fornire la necessaria affidabilità;
• la seconda scuola la mette negli host, i cui livelli transport forniscono l'affidabilità e l'orientamento alla connessione.

In realtà le decisioni sono due, separate:

• offrire o no un servizio affidabile;
• offrire o no un servizio orientato alla connessione.

Le scelte più comuni sono di offrire servizi connection oriented affidabili oppure servizi connectionless non affidabili, mentre le altre due combinazioni, anche se tecnicamente possibili, non sono diffuse.

5.2) Organizzazione interna della subnet

Questo è un problema separato ed indipendente da quello dei servizi offerti, anche se spesso c'è una relazione fra i due.

Una subnet può essere organizzata con un funzionamento interno:

• basato su connessioni (che in questo contesto si chiamano circuiti virtuali):
  • la subnet stabilisce un circuito virtuale (sul quale verrà tipicamente veicolato il traffico di un servizio connection oriented), cioé crea un cammino fra la sorgente e la destinazione;
  • tutti i router lungo tale cammino ricordano, in una apposita struttura dati, la parte di loro competenza di tale cammino (e cioé quale linea in entrata e quale in uscita sono assegnate al cammino);
  • quando arrivano pacchetti che contengono l' ID di tale circuito virtuale, essi vengono instradati di conseguenza (tutti nello stesso modo).
• connectionless:
  • i router si limitano a instradare ogni pacchetto che arriva sulla base del suo indirizzo di destinazione, decidendo di volta in volta come farlo proseguire;
  • i router hanno delle tabelle di instradamento (routing table)che indicano, per ogni possibile destinazione, quale linea in uscita utilizzare; si noti che queste tabelle esistono anche nelle subnet del tipo precedente, dove però servono solamente nella fase di setup della connessione (per decidere come instradare i pacchetti di setup);
  • quando offre un servizio connection-oriented, questo livello fa credere al livello superiore che esista una connessione, ma poi i pacchetti viaggiano indipendentemente (e quindi hanno tutti l'indirizzo del destinatario) e vengono rimessi in ordine dal livello network solo a destinazione, prima di essere consegnati al livello superiore.

Ognuna delle due organizzazioni della subnet sopra viste ha i suoi supporter e i suoi detrattori, anche sulla base delle seguenti considerazioni:

Dev'essere chiaro che i servizi offerti sono indipendenti dalla realizzazione interna della subnet. E' possibile avere tutte le quattro combinazioni di servizio offerto e implementazione della subnet:

• servizi connection oriented su circuiti virtuali;
• servizi connectionless su subnet datagram;
• servizi connection oriented su subnet datagram (si cerca di fornire comunque un servizio robusto);
• servizi connectionless su circuito virtuale (esempio: IP su subnet ATM).

5.3) Algoritmi di routing

La funzione principale del livello network è di instradare i pacchetti sulla subnet, tipicamente facendo fare loro molti hop (letteralmente, salti) da un router ad un altro.

Un algoritmo di routing è quella parte del software di livello network che decide su quale linea di uscita instradare un pacchetto che è arrivato:

• in una subnet datagram l'algoritmo viene applicato ex novo ad ogni pacchetto;
• in una subnet basata su circuiti virtuali l'algoritmo viene applicato solo nella fase di setup del circuito; in tale contesto si usa spesso il termine session routing.

Da un algoritmo di routing desideriamo:

• correttezza (deve muovere il pacchetto nella giusta direzione);
• semplicità (l'implementazione non deve essere troppo complicata);
• robustezza (deve funzionare anche in caso di cadute di linee e/o router e di riconfigurazioni della topologia);
• stabilità (deve convergere, e possibilmente in fretta);
• equità (non deve favorire nessuno);
• ottimalità (deve scegliere la soluzione globalmente migliore.

Purtroppo, gli ultimi due requisiti sono spesso in conflitto fra loro; inoltre, a proposito dell'ottimalità, non sempre è chiaro cosa si voglia ottimizzare. Infatti, supponiamo che si vogliano:

• minimizzare il ritardo medio pacchetti;
• massimizzare il throughput totale dei pacchetti.

Si scopre facilmente che questi due obiettivi sono in conflitto fra loro, perché di solito aumentare il throughput allunga le code sui router e quindi aumenta il ritardo: questo è vero per qualunque sistema basato su code gestito in prossimità della sua capacità massima.

Gli algoritmi di routing si dividono in due classi principali:

• algoritmi non adattivi (static routing):
  • le decisioni di routing sono prese in anticipo, all'avvio della rete, e sono comunicate ai router che poi si attengono sempre a quelle;
• algoritmi adattivi (dynamic routing):
  • le decisioni di routing sono riformulate (sulla base del traffico, della topologia della rete, ecc.) molto spesso.

Gli algoritmi adattivi differiscono fra loro per:

• come ricevono le informazioni:
  • localmente;
  • dai router adiacenti;
  • da tutti i router;
• quanto spesso rivedono le decisioni:
  • a intervalli di tempo prefissati;
  • quando il carico cambia;
  • quando la topologia cambia;
• quale metrica di valutazione adottano:
  • distanza;
  • numero di hop;
  • tempo di transito stimato.

5.3.1) Il principio di ottimalità

E' possibile fare una considerazione generale sull'ottimalità dei cammini, indipendentemente dallo specifico algoritmo adottato per selezionarli.

Il principio di ottimalità dice che se il router j è nel cammino ottimo fra i e k, allora anche il cammino ottimo fra j e k è sulla stessa strada:

Se così non fosse, ci sarebbe un altro cammino (ad es. quello tratteggiato in figura) fra j e k migliore di quello che è parte del cammino ottimo fra i e k, ma allora ci sarebbe anche un cammino fra i e k migliore di quello ottimo.

Una diretta conseguenza è che l'insieme dei cammini ottimi da tutti i router a uno specifico router di destinazione costituiscono un albero, detto sink tree per quel router.

In sostanza, gli algoritmi di routing cercano e trovano i sink tree relativi a tutti i possibili router di destinazione, e quindi instradano i pacchetti esclusivamente lungo tali sink tree.

5.3.2) Algoritmi statici

Questi algoritmi, come abbiamo già accennato, sono eseguiti solamente all'avvio della rete, e le decisioni di routing a cui essi pervengono sono poi applicate senza più essere modificate.

Esamineremo i seguenti algoritmi statici:

• shortest path routing;
• flooding;
• flow-based routing.

Shortest path routing

L'idea è semplice: un host di gestione della rete mantiene un grafo che rappresenta la subnet:

• i nodi rappresentano i router;
• gli archi rappresentano le linee punto-punto.

All'avvio della rete (o quando ci sono variazioni permanenti della topologia) l'algoritmo:

• applica al grafo un algoritmo per il calcolo del cammino minimo fra ogni coppia di nodi; ad esempio, il noto algoritmo di Dijkstra ('59) può essere usato;
• invia tali informazioni a tutti i router.

Quale sia il cammino minimo dipende da qual'è la grandezza che si vuole minimizzare. Tipicamente si usano:

• numero di hop, cioè di archi, da attraversare;
• lunghezza dei collegamenti;
• tempo medio di accodamento e trasmissione;
• una combinazione di lunghezza, banda trasmissiva, traffico medio, ecc.

Flooding

La tecnica del flooding consiste nell'inviare ogni pacchetto su tutte le linee eccetto quella da cui è arrivato.

In linea di principio il flooding può essere usato come algoritmo di routing (ogni pacchetto inviato arriva a tutti i router) ma presenta l'inconveniente di generare un numero enorme (teoricamente infinito!) di pacchetti.

Ci sono delle tecniche per limitare il traffico generato:

• inserire in ogni pacchetto un contatore che viene decrementato ad ogni hop. Quando il contatore arriva a zero, il pacchetto viene scartato. Un appropriato valore iniziale può essere il diametro della subnet;
• inserire la coppia (source router ID, sequence number) in ogni pacchetto. Ogni router esamina tali informazioni e ne tiene traccia, e quando le vede per la seconda volta scarta il pacchetto;
• selective flooding: i pacchetti vengono duplicati solo sulle linee che vanno all'incirca nella giusta direzione (per questo si devono mantenere apposite tabelle a bordo).

Il flooding non è utilizzabile in generale come algoritmo di routing, però:

• è utile in campo militare (offre la massima affidabilità e robustezza);
• è utile per l'aggiornamento contemporaneo di informazioni distribuite;
• è utile come strumento di paragone per altri algoritmi, visto che trova sempre, fra gli altri, il cammino minimo.

Flow-based routing

Questo algoritmo è basato sull'idea di:

• calcolare in anticipo il traffico atteso su ogni linea;
• da questi calcoli derivare una stima del ritardo medio atteso per ciascuna linea;
• basare su tali informazioni le decisioni di routing.

Le informazioni necessarie per poter applicare l'algoritmo sono:

• la topologia della rete;
• la matrice delle quantità di traffico T(i,j) stimate fra ogni coppia (i,j) di router;
• le capacità (in bps ad esempio) delle linee point to point.

Vengono fatte le seguenti assunzioni:

• il traffico è stabile nel tempo e noto in anticipo;
• il ritardo su ciascuna linea aumenta all'aumentare del traffico sulla linea e diminuisce all'aumentare della velocità della linea secondo le leggi della teoria delle code.

Dai ritardi calcolati per le singole linee si può calcolare il ritardo medio dell'intera rete, espresso come somma pesata dei ritardi delle singole linee. Il peso di ogni linea è dato dal traffico su quella linea diviso il traffico totale sulla rete.

Il metodo nel suo complesso funziona così:

• si sceglie un algoritmo di routing;
• sulla base di tale algoritmo si determinano i percorsi che verranno seguiti per il collegamento fra ogni coppia di router;
• si calcola il traffico che incide su ogni linea (che è uguale alla somma di tutti i T(i,j) instradati su quella linea);
• si calcola il ritardo di ogni linea;
• si calcola il ritardo medio della rete;
• si ripete il procedimento con vari algoritmi di routing, scegliendo alla fine quello che minimizza il ritardo medio dell'intera rete.

5.3.3) Algoritmi dinamici

Nelle moderne reti si usano algoritmi dinamici, che si adattano automaticamente ai cambiamenti della rete. Questi algoritmi non sono eseguiti solo all'avvio della rete, ma rimangono in esecuzione sui router durante il normale funzionamento della rete.

Distance vector routing

Ogni router mantiene una tabella (vector) contenente un elemento per ogni altro router. Ogni elemento della tabella contiene:

• la distanza (numero di hop, ritardo, ecc.) che lo separa dal router in oggetto;
• la linea in uscita da usare per arrivarci;

Per i suoi vicini immediati il router stima direttamente la distanza dei collegamenti corrispondenti, mandando speciali pacchetti ECHO e misurando quanto tempo ci mette la risposta a tornare.

A intervalli regolari ogni router manda la sua tabella a tutti i vicini, e riceve quelle dei vicini.

Quando un router riceve le nuove informazioni, calcola una nuova tabella scegliendo, fra tutte, la concatenazione migliore

per ogni destinazione.

Ovviamente, la migliore è la concatenazione che produce la minore somma di:

• distanza fra il router stesso ed un suo vicino immediato (viene dalla misurazione diretta);
• distanza fra quel vicino immediato ed il router remoto di destinazione (viene dalla tabella ricevuta dal vicino immediato).

L'algoritmo distance vector routing funziona piuttosto bene, ma è molto lento nel reagire alle cattive notizie, cioè quando un collegamento va giù. Ciò è legato al fatto che i router non conoscono la topologia della rete.

Infatti, consideriamo questo esempio:

A     B     C     D     E   <- Router
*-----*-----*-----*-----*   <- Collegamenti (topologia lineare)
      1     2     3     4   <- Distanze da A

Se ora cade la linea fra A e B, dopo uno scambio succede questo:

A     B     C     D     E   <- Router
*     *-----*-----*-----*   <- Collegamenti
      3     2     3     4   <- Distanze da A (dopo uno scambio)

Ciò perché B, non ricevendo risposta da A, crede di poterci arrivare via C, che ha distanza due da A. Col proseguire degli scambi, si ha la seguente evoluzione:

A     B     C     D     E   <- Router
*     *-----*-----*-----*   <- Collegamenti
      3     4     3     4   <- Distanze da A (dopo due scambi)
      5     4     5     4   <- Distanze da A (dopo tre scambi)
      5     6     5     6   <- Distanze da A (dopo quattro scambi)
ecc.

A lungo andare, tutti i router vedono lentamente aumentare sempre più la distanza per arrivare ad A. Questo è il problema del count-to-infinity.

Se la distanza rappresenta il numero di hop si può porre come limite il diametro della rete, ma se essa rappresenta il ritardo l'upper bound dev'essere molto alto, altrimenti cammini con un ritardo occasionalmente alto (magari a causa di congestione) verrebbero considerati interrotti.

Sono state proposte molte soluzioni al problema count-to-infinity, ma nessuna veramente efficace.

Nonostante ciò, il distance vector routing era l'algoritmo di routing di ARPANET ed è usato anche in Internet col nome di RIP (Routing Internet Protocol), e nelle prime versioni di DECnet e IPX.

Link state routing

Sopratutto a causa della lentezza di convergenza del distance vector routing, si è cercato un approccio diverso, che ha dato origine al link state routing.

L'idea è questa:

• ogni router tiene sott'occhio lo stato dei collegamenti fra se e i suoi vicini immediati (misurando il ritardo di ogni linea) e distribuisce tali informazioni a tutti gli altri;
• sulla base di tali informazioni, ogni router ricostruisce localmente la topologia completa dell'intera rete e calcola il cammino minimo fra se e tutti gli altri.

I passi da seguire sono:

1. scoprire i vicini e identificarli;
2. misurare il costo (ritardo o altro) delle relative linee;
3. costruire un pacchetto con tali informazioni;
4. mandare il pacchetto a tutti gli altri router;
5. previa ricezione degli analoghi pacchetti che arrivano dagli altri router, costruire la topologia dell'intera rete;
6. calcolare il cammino più breve a tutti gli altri router.

Quando il router si avvia, invia un pacchetto HELLO su tutte le linee in uscita. In risposta riceve dai vicini i loro indirizzi (univoci in tutta la rete).

Inviando vari pacchetti ECHO, misurando il tempo di arrivo della risposta (diviso 2) e mediando su vari pacchetti si deriva il ritardo della linea.

Si costruisce un pacchetto con:

• identità del mittente;
• numero di sequenza del pacchetto;
• età del pacchetto;
• lista dei vicini con i relativi ritardi.

La costruzione e l'invio di tali pacchetti si verifica tipicamente:

• a intervalli regolari;
• quando accade un evento significativo (es.: una linea va giù o torna su).

La distribuzione dei pacchetti è la parte più delicata, perché errori in questa fase possono portare qualche router ad avere idee sbagliate sulla topologia, con conseguenti malfunzionamenti.

Di base si usa il flooding, inserendo nei pacchetti le coppie (source router ID, sequence number) per eliminare i duplicati. Tutti i pacchetti sono confermati. Inoltre, per evitare che pacchetti vaganti (per qualche errore) girino per sempre, l'età del pacchetto viene decrementata ogni secondo, e quando arriva a zero il pacchetto viene scartato.

Combinando tutte le informazioni arrivate, ogni router costruisce il grafo della subnet e calcola il cammino minimo a tutti gli altri router.

Il link state routing è molto usato attualmente:

• in Internet OSPF (Open Shortest Path First) è basato su tale principio e si avvia ad essere l'algoritmo più utilizzato;
• un altro importante esempio è IS-IS (Intermediate System-Intermediate System), progettato per DECnet e poi adottato da OSI. La sua principale caratteristica è di poter gestire indirizzi di diverse architetture (OSI, IP, IPX) per cui può essere usato in reti miste o multiprotocollo.

5.3.4) Routing gerarchico

Quando la rete cresce fino contenere decine di migliaia di nodi, diventa troppo gravoso mantenere in ogni router la completa topologia. Il routing va quindi impostato in modo gerarchico, come succede nei sistemi telefonici.

La rete viene divisa in zone (spesso dette regioni):

• all'interno di una regione vale quanto visto finora, cioè i router (detti router interni) sanno come arrivare a tutti gli altri router della regione;
• viceversa, quando un router interno deve spedire qualcosa a un router di un'altra regione sa soltanto che deve farlo pervenire a un particolare router della propria regione, detto router di confine.
• il router di confine sa a quale altro router di confine deve inviare i dati perché arrivino alla regione di destinazione.

Di conseguenza, ci solo due livelli di routing:

• un primo livello di routing all'interno di ogni regione;
• un secondo livello di routing fra tutti i router di confine.

I router interni mantengono nelle loro tabelle di routing:

• una entrata per ogni altro router interno, con la relativa linea da usare per arrivarci;
• una entrata per ogni altra regione, con l'indicazione del relativo router di confine e della linea da usare per arrivarci.

I router di confine, invece, mantengono:

• una entrata per ogni altra regione, con l'indicazione del prossimo router di confine da contattare e della linea da usare per arrivarci.

Non è detto che due livelli siano sufficienti. In tal caso il discorso si ripete su più livelli.