Politiche di instradamento
Controllo di congestione

 

Struttura del collegamento e modalità di connessione

La struttura di rete secondo la quale i terminali vengono connessi, rientra quasi sempre in uno dei seguenti tipi:

• collegamento punto a punto half-duplex commutato;
• collegamento punto a punto full-duplex commutato;
• collegamento multipunto full-duplex non commutato;
• collegamento punto a punto full-duplex non commutato;
• collegamento ad anello multipunto.

Analizziamo ora in dettaglio tutte le possibili modalità di collegamento:

• trasmissione simplex, il canale di comunicazione può essere usato soltanto in modalità unidirezionale, quindi i dati sono trasmessi in un'unica direzione;

• trasmissione half-duplex, il canale permette di trasmettere nei due ma in modo alternato. Quindi prima il canale può essere usato per trasmettere dal primo al secondo punto, successivamente il secondo punto può rispondere al primo e così via;

• trasmissione full-duplex, il canale permette di trasmettere contemporaneamente nei due sensi. Mentre la comunicazione half-duplex richiede solo una coppia di fili di connessione, la tecnica full-duplex necessita di due coppie di fili oppure di una sola coppia, ma adottando qualche accorgimento per distinguere e separare i segnali in trasferimento nei due sensi: ad es. si possono allocare i segnali in due campi di frequenze diversi;

• rete commutata, il collegamento fisico tra due punti viene stabilito tramite un telefono e un commutatore. Il commutatore è un dispositivo con cui è possibile selezionare la trasmissione telefonica normale o la trasmissione dati. Il collegamento viene quindi stabilito selezionando la trasmissione telefonica normale sul commutatore, facendo una normale chiamata con il telefono di servizio e ponendo successivamente il commutatore nella posizione di trasmissione dati;

• rete non commutata, o fissa, è invece un collegamento permanente tra due punti che non passa attraverso centrali di commutazione, questo elimina alcune possibili cause di errori;

• trasmissioni orientate alla connessione (connection oriented), necessitano di una fase di instaurazione del collegamento (establishment) e una di abbattimento, realizzate con delle apposite primitive. Viene quindi realizzato un circuito virtuale (come nel caso di un centralino telefonico). Garantiscono una maggiore efficienza prevedendo, generalmente, delle procedure per il controllo degli errori di trasmissione;

• trasmissioni senza connessione (connectionless), non necessitano di una fase di instaurazione e di abbattimento della trasmissione. Non viene quindi creato un circuito virtuale, ma una connessione datagram (commutazione di pacchetto). Sono più semplici da realizzare a discapito della loro efficienza.

• collegamento di tipo punto a punto, è certamente il collegamento più semplice da realizzare coinvolgendo soltanto due stazioni. Come tipo di collegamento può essere realizzato sia su linee commutate che non, con un funzionamento di tipo half o full-duplex. Una delle due stazioni è generalmente definita come stazione primaria (master), mentre l'altra è definita secondaria (slave), ciò per risolvere eventuali contese simultanee della linea.

• collegamento di tipo multipunto, è costituito da più stazioni collegate in parallelo o in serie (collegamento multipunto ad anello). Particolarità di tale collegamento è l'esistenza di una sola stazione primaria mentre tutte le rimanenti sono stazioni secondarie. Inoltre, contrariamente a quanto avviene in un collegamento punto a punto, le stazioni secondarie non possono iniziare liberamente la trasmissione di informazioni, essendo tale decisione riservata solamente alla stazione principale. La stazione primaria inizia l'invio di un messaggio verso uno o più terminali interessati premettendo all'invio una fase di selecting in cui comunica ai terminali interessati di prepararsi a ricevere. Una fase in cui la stazione primaria desidera ricevere messaggi, se disponibili, da una particolare stazione secondaria viene fatta precedere da una fase di polling, che viene interpretata dal terminale indirizzato come una richiesta a trasmettere. Per ciò che riguarda invece il tipo di trasmissione si ha generalmente la stazione primaria che trasmette in full-duplex mentre le stazioni secondarie funzionano in half-duplex;

 

Strategie di instradamento

Un aspetto generale per le reti a commutazione di pacchetto è rappresentato dalla maniera con la quale i pacchetti vengono trasferiti dal nodo sorgente a quello destinatario.I pacchetti attraversano più nodi, in ognuno dei quali vengono ricevuti, memorizzati, immessi in una coda di trasmissione e quindi instradati ad un nodo adiacente. Il problema dell'instradamento è universalmente noto come routing.

Se c'è un solo collegamento fisico tra due nodi, come ad esempio in una topologia a stella, il pacchetto deve ovviamente seguire quella strada. In altri casi, invece, vi possono essere più connessioni tra due siti e quindi si presenta un problema di scelta fra le varie strade possibili.

Ogni nodo possiede una tabella a cui si attiene diligentemente, detta tabella di instradamento (routing table), che riporta, in funzione del sito di destinazione, verso quale successivo nodo instradare il pacchetto. Generalmente esse contengono anche una informazione che stima in qualche modo la distanza dalla destinazione. La metrica può essere un tempo in millisecondi o un numero che indica quanti salti (hop) o attraversamenti di nodo sono necessari fino a destinazione.

Per evitare che ogni tabella di routing dovendo contenere una riga (entry) per ogni nodo della rete (i nodi possono essere migliaia) diventi eccessivamente lunga e laboriosa da gestire, si può riorganizzare la rete in modo tale da suddividerla in sottoreti o regioni. Ogni nodo, appartenente ad una regione, disporrà nella propria routing table di una entry per tutti i nodi della sua stessa regione e soltanto di una entry per ciascuna delle altre regioni. Così facendo si riduce notevolmente la dimensione delle singole tabelle di instradamento a scapito però di un routing non ottimo (si deve sempre passare dai nodi radice delle sottoreti anche quanto esistesse un collegamento diretto). Di seguito vengono illustrate alcune strategie di instradamento.

Instradamento fisso o statico

Il percorso da seguire dal nodo sorgente al nodo destinatario è calcolato in anticipo e non cambia a meno che non si verifichino dei guasti che ne rendano impossibile l'uso. Generalmente viene scelto il percorso più corto per diminuire il costo della comunicazione. Questa strategia è di estrema semplicità, e però anche molto rigida e non consente adattamenti in funzione di cambiamenti della quantità di informazione (carico) trasmessa lungo i vari percorsi anche se è comunque straordinariamente efficace in condizioni di traffico piuttosto costante. Le tabelle vengono scaricate (downloaded) nei nodi di rete in fase di boot o di inizializzazione del sistema.

Instradamento "adattivo"

Si applica al caso di traffico "lentamente variabile". Può essere di tipo: centralizzato (il calcolo viene effettuato sulla base di informazioni globali di tutta la rete), isolato (viene usata soltanto l'informazione locale al nodo) e distribuito (viene usata sia l'informazione locale che, in parte, quella globale).

• routing centralizzato, ogni nodo manda periodicamente informazioni di stato (ad esempio la lista dei nodi vicini cioè raggiungibili con un solo hop, la lunghezza delle proprie code, la quantità del traffico processato a partire dall'ultimo report) ad un centro di calcolo (Routing Control Center, RCC), incaricato di gestire al meglio la rete. L'RCC calcola quindi le nuove tabelle di routing per tutti i nodi sulla base dell'informazione completa, bilanciando il traffico in maniera "predittiva". Purtroppo questa modalità presenta diversi svantaggi: difficoltà ad adattarsi a reti in cui le condizioni di traffico variano rapidamente, vulnerabilità intrinseca dovuta alla centralizzazione, alta concentrazione di traffico nei pressi del RCC, e distribuzione disordinata delle tabelle (quando queste vengono inviate dal centro, raggiungono dei nodi prima di altri creando un intervallo di tempo nel quale non si ha una perfetta corrispondenza tra le routing table di tutti i nodi, qualcuna è aggiornata e qualcuna no. Inoltre si utilizzano le tabelle non aggiornate per inviare gli aggiornamenti stessi);

• hot potato routing (isolato), l'idea alla base di questa strategia è quella della patata bollente (hot potato). Ogni nodo cerca di disfarsi di un pacchetto in arrivo più in fretta che può. Questo viene realizzato inviando il pacchetto lungo l'output link avente la coda di uscita di dimensioni minori. L'idea può essere perfezionata in diversi modi;

• backward learning routing (isolato), l'idea di base è quella di imparare la strada per ogni destinazione attraverso un esame dei pacchetti da essa provenienti. Si supponga che in ogni pacchetto siano inclusi: l'identità del nodo sorgente e un contatore che viene incrementato ad ogni hop. Se un nodo vede un pacchetto arrivargli attraverso il link ‘L' dal nodo ‘N' con hop-count uguale ad h, supponendo i link completamente full-duplex (cioè percorribili in entrambi i sensi), il nodo saprà che N è raggiungibile via L in h hop e aggiornerà la voce della sua routing table corrispondente ad N se la distanza in essa contenuta è maggiore di h. Periodicamente il learning deve essere rifatto per tenere conto di eventuali link che possono improvvisamente cadere o cambiare parametri. A seconda della frequenza cui viene fatta questa operazione si ha un diverso sovraccarico ed una diversa rispondenza alla dinamica della rete;

• flooding routing (isolato), secondo questa strategia ogni nodo invia ogni pacchetto in arrivo su tutti i link d'uscita escluso quello attraverso cui il pacchetto è arrivato. Deve però esistere un modo per eliminare i pacchetti in transito sulla rete (ad esempio attraverso un limite al hop-count) e per selezionare e scartare i duplicati in ricezione onde evitare la congestione della rete.

• distributed routing, questa strategia fa ricorso sia all'informazione locale che a quella globale; fondendo i vantaggi del routing centralizzato e del routing isolato. Un esempio di questi è il Vector Distance Routing. Esso prevede che ad intervalli di tempo regolari ogni nodo invii ai suoi vicini (cioè a tutti i nodi che esso può raggiungere direttamente con un solo hop) una copia della propria routing table e riceva la stessa informazione da essi. A partire da queste informazioni e dall'informazione della distanza di ogni vicino, il nodo può aggiornare la propria tabella di routing. La distanza è determinata secondo una metrica che può essere: il numero di hop che li separa, il tempo di volo in msec, il numero di pacchetti disponibili per quel nodo, etc..

Instradamento dinamico o datagram

Si ha quando in una rete ogni pacchetto viene instradato indipendentemente dagli altri appartenenti a quella connessione, quindi il percorso da seguire dal nodo sorgente al nodo destinatario viene determinato solo al momento dell'invio effettivo del pacchetto. Con il routing datagram ogni singolo pacchetto contiene tutte le informazioni per poter arrivare a destinazione e poter fornire al ricevente la possibilità di ricostruire l'esatta sequenza di trasmissione. Ogni nodo elabora ogni singolo pacchetto in maniera autonoma in funzione del carico momentaneo, può capitare che ogni pacchetto percorra strade diverse e che possa arrivare prima di uno spedito precedentemente. Con questa strategia si possono evitare le situazioni in cui certe linee di comunicazione sono sovraccariche e altre scariche, inoltre il guasto di un nodo non comporta la perdita della connessione. Esistono molte modalità di intradamento dinamico, di seguito ne vengono evidenziate alcune:

• multipath routing, in questa modalità ogni nodo mantiene nella sua routing table, in corrispondenza di uno stesso nodo di destinazione, più link d'uscita, caratterizzati ciascuno da un peso diverso. Il criterio con cui viene effettuata la scelta del link verso cui instradare i pacchetti può essere implementato in base ad esigenze specifiche. Ad esempio, usando una metrica probabilistica, si può assegnare ad ogni possibile link un range di probabilità e scegliere quello nel cui range è caduto un numero estratto casualmente. In alternativa si possono suddividere i pacchetti in diverse classi di traffico (ad es. FTP, Telnet, e-mail, etc.) ed assegnare ad ogni classe un link dedicato ;

• routing con garanzia di performance, moderna modalità di instradamento dinamica che garantisce, possibilmente o certamente, un tempo di "volo" del pacchetto entro un determinato intervallo temporale imposto. Questo tempo, che deve essere valutato per soddisfare la specifica, è in parte fisso e determinato dal tempo di propagazione del segnale lungo il portante fisico, e in parte variabile e dovuto al tempo durante il quale il pacchetto rimane in coda d'attesa nei nodi attraversati lungo il percorso. La garanzia di consegna con un ritardo massimo predeterminato consente l'esecuzione di applicazioni critiche che risentono pesantemente dei ritardi di trasmissione, ad esempio le trasmissioni video.

Broadcast e multicast routing

Vi sono alcuni casi in cui invece di avere trasmissioni punto-punto si richiedono trasmissioni punto a multipunto, cioè si deve inviare lo stesso pacchetto a più nodi di destinazione (ad esempio inviare la stessa tabella di routing aggiornata ai nodi della propria rete). Un pacchetto si definisce di broadcast quando è inviato a tutti i nodi di una rete, mentre di multicast quando è inviato ad un suo sottoinsieme proprio. Esistono diverse modalità di routing per supportare efficacemente il broadcast e il multicast:

• inviare un pacchetto distinto a ciascun nodo di destinazione;

• flooding broadcast, ogni nodo invia il pacchetto in arrivo su tutti i link d'uscita escluso quello attraverso cui il pacchetto è arrivato (simile al già citato flooding routing);

• multidestination broadcast, funziona come il multidestination routing ma con la differenza che il pacchetto viene trasmesso una sola volta lungo ogni link. Ogni pacchetto contiene una lista dei nodi di destinazione a cui è diretto e viaggia in unica copia finché la strada è la stessa;

• spanning-tree broadcast, se ogni nodo conosce la propria posizione nello spanning-tree^* della rete è sufficiente inviare i pacchetti su tutti i link di uscita appartenenti allo spanning-tree tranne che verso il nodo da cui sono arrivati;

• spanning-tree broadcast approssimato, usato quanto non è possibile conoscere quello esatto. Si cerca di costruire un albero approssimato secondo il seguente algoritmo (Reverse Path Forwarding): un pacchetto che arriva ad un nodo da un link che è quello che verrebbe utilizzato per trasmettere con il nodo sorgente, viene considerato come appartenente allo spanning-tree e il pacchetto viene allora inviato su tutti gli altri link d'uscita.

Circuiti virtuali

Il percorso dal nodo sorgente al nodo destinatario è fissato per la durata di una sessione, quindi i pacchetti inviati durante una sessione seguono tutti lo stesso percorso mentre quelli inviati in sessioni diverse possono seguire percorsi diversi. Questa modalità di instradamento consente di risolvere, almeno in parte, il problema dell'adattamento al carico in quanto all'apertura di una sessione può essere scelta la strada più opportuna da seguire in base alla situazione di carico della rete presente in quel momento.

 

Controllo di congestione

La congestione si verifica quando il carico in un determinato nodo o gruppo di nodi cresce fino alla saturazione del nodo o del gruppo, cioè quando i buffer messi a disposizione dal nodo per ospitare i pacchetti intanto che vengono instradati verso i nodi successivi si esauriscono. Controllare la congestione significa cercare di evitarla. Esistono diversi metodi di controllo:

• preallocazione dei buffer, un nodo sorgente prima di iniziare a trasmettere richiede e prenota un certo numero di buffer (secondo le proprie esigenze) presso ogni nodo che attraverserà. Combinando la preallocazione con un controllo di flusso da parte del nodo sorgente (cioè la velocità con cui questo invia i pacchetti sulla rete) si può garantire l'assenza di congestione. Normalmente in fase di setup di una connessione non vengono allocati buffer;

• packet discarding, contrariamente alla preallocazione non c'è nessuna prevenzione. Se si ha congestione i pacchetti in eccesso vengono eliminati. Nel caso connection oriented il nodo sorgente deve essere informato perché ritrasmetta successivamente i pacchetti, mentre nel caso connectionless non si ha nessuna azione addizionale. La scelta dei pacchetti da eliminare può essere effettuata in base a diversi criteri, ad esempio: gli ultimi arrivati oppure quelli che hanno viaggiato meno (per minimizzare lo spreco di risorse);

• choke packet (pacchetto di soffocamento), l'idea è quella di fornire un feedback per prevenire le congestioni. Un criterio può essere basato sull'utilizzazione delle linee di uscita: periodicamente viene calcolato il fattore di utilizzazione di ogni linea e quando questo cresce al di sopra di una certa soglia un choke packet viene inviato al nodo sorgente, indicando l'indirizzo di destinazione. Il nodo sorgente rallenterà quindi il flusso di dati verso quel nodo.