1.6 Panoramica della tecnologia Internet
2.2.1 Il routing
Il problema del routing `e pi`u pressante nel caso del packet switching: in questo caso le decisioni devono essere prese rapidamente, e devono adattarsi dinamicamente al carico del sistema. Un algoritmo di routing deve possedere tutte le caratteristiche di un buon algoritmo distribuito.
Semplicit`a Incide sulla prevedibilit`a e sulla affidabilit`a.
Robustezza Garantisce la funzionalit`a anche in caso di guasto.
Stabilit`a Serve ad evitare che brusche modifiche nelle strategie locali pos-sano portare a comportamenti oscillanti, che sotto-utilizzano le risorse. Ve-dremo un esempio tra poco.
Fairness `E necessario garantire che le risorse siano distribuite equamente, anche in ragione della priorit`a.
Ottimalit`a Va valutata rispetto a quei parametri scelti per rappresentare le prestazioni della rete.
Efficienza Indica che l’overhead computazionale `e ridotto, tanto sulle di-mensioni dei messaggi quanto sul numero di nodi interessati.
Per arrivare ad un algoritmo che presenti queste caratteristiche dovranno essere valutate un gran numero di scelte realizzative.
Trasmissione pacchetti dati
Packet switching su rete datagram
conferma di collegamento
Richiesta e
Trasmissione dati
Conferma di ricezione
Circuit switching
conferma di collegamento
Richiesta e Trasmissione
pacchetti dati Conferma di ricezione
Packet switching su circuito virtuale
Figura 2.4Confronto tra Circuit e Packet switching
Obiettivi di ottimizzazione In genere `e necessario operare un compro-messo tra i possibili parametri da ottimizzare. Sar`a poi difficile modificare l’algoritmo se cambiano le priorit`a nelle prestazioni. Tra i parametri che pos-sono essere oggetto di ottimizzazione ci pos-sono il numero di canali interessati da una comunicazione, il costo di una connessione, quando l’utilizzazione dei canali abbia costo variabile da canale a canale, il ritardo, ottenuto
cu-mulando ritardi interni, di buffering e di rete, la quantit`a di informazione trasferita nell’unit`a di tempo (throughput).
Collocazione delle decisioni `E necessario indicare chi controlla il routing, e quando `e opportuno intraprendere questa operazione. Esistono almeno tre alternative, per quanto riguarda la localizzazione del controllo del routing:
Routing centralizzato Un solo nodo nella rete controlla il routing. `E poco affidabile, visto che il guasto di quel nodo immobilizza la rete.
Routing distribuito Ogni nodo pu`o controllare il proprio routing, coor-dinandosi con i vicini. Notevolmente pi`u complesso, ma molto pi`u robusto.
Source routing Il mittente determina, su base locale, il percorso che verr`a seguito dalla comunicazione.
Il momento in cui viene determinato il routing dipende anche da altre de-cisioni: in una rete virtual circuit le decisioni verranno prese solo prima di stabilire la connessione, mentre in una rete datagram potranno essere modificate non appena cambino le condizioni di carico della rete.
Provenienza delle informazioni e temporizzazione delle decisioni In caso di routing distribuito, un nodo pu`o ottenere informazioni da nodi adia-centi, o da nodi attraverso i quali transitano comunicazioni dirette a lui.
In caso di routing centralizzato l’informazione viene raccolta da tutti i no-di. Se la raccolta delle informazioni richiede comunicazioni, `e necessario determinare quando raccoglierle.
Una strategia di routing consiste in una serie di risposte alle scelte illu-strate di sopra: vediamo alcune di queste illu-strategie.
Il routing statico
E l’alternativa concettualmente pi`` u semplice. La rete `e rappresentata come un grafo pesato (v. figura 2.5): per determinare il routing, per ogni coppia di nodi viene calcolato il cammino di costo minimo. Il risultato di questo calcolo risulta in una tabella simile alla 2.1. Questa tabella potr`a risiedere su un nodo specializzato.
Quindi su ogni nodo viene registrata una tabella, che, per ciascun nodo della rete, indica verso quale dei vicini istradare un messaggio diretto a quel
A
Figura 2.5Una rete di comunicazione rappresentata con un grafo pesato Tabella 2.1Tabella di routing del sistema
origine destinazione
-nodo. In pratica si tratter`a di una riga della matrice di partenza. La tabella 2.2 corrisponde alla tabella di routing per il nodo B.
Tabella 2.2Tabella di routing per il nodo B
destinazione prossimo
Quindi la tabella complessiva viene distribuita tra tutti i nodi del sistema.
Il routing statico ha il pregio di essere concettualmente semplice da realiz-zare. Tuttavia non `e in grado di reagire alla congestione di un link. Una
sem-plice modifica consiste nel predisporre dei cammini alternativi, che possono essere utilizzati in caso di guasti o di congestione.
Flooding
Si tratta di una strategia che presenta vantaggi e svantaggi speculari rispet-to al routing statico: consiste nel fatrispet-to che ogni nodo ritrasmette a tutti i propri vicini tutti i pacchetti che riceve. Quindi l’invio di un messaggio ge-nera una valanga di messaggi che, prima o poi, raggiungono il destinatario finale: flooding sta appunto per “inondazione”. Per arrestare o rallentare la moltiplicazione dei messaggi si possono utilizzare diverse tecniche:
• Non ritrasmettere il pacchetto verso il mittente.
• Identificare ogni messaggio e non ritrasmetterlo pi`u di una volta.
• Inserire in ciascun messaggio un valore che indichi il massimo numero di ritrasmissioni (hop-count). Ad ogni ritrasmissione il campo deve essere decrementato di una unit`a, ed il messaggio non viene ritrasmesso quando l’hop-count raggiunge il valore 0.
La strategia di flooding, a fronte di un costo che pu`o essere molto alto, offre diversi vantaggi:
• Se esiste almeno un cammino tra i due nodi, il pacchetto giunge a desti-nazione: quindi `e eccezionalmente robusta.
• Il pacchetto giunge a destinazione nel pi`u breve tempo possibile.
• Tutti i nodi connessi all’origine del messaggio (entro una certa distanza, se viene utilizzato l’hop-count) vengono raggiunti.
Questa ultima caratteristica rende estremamente attraente questa strate-gia nel caso in cui si debba realizzare un broadcast, cio`e una comunicazione da un nodo verso tutti gli altri nodi.
Naturalmente il punto debole del flooding `e il grande traffico generato, che `e proporzionale al numero di link nella rete.
Routing casuale
Il nodo verso il quale ritrasmettere il pacchetto `e scelto a caso. Eventual-mente, pu`o essere scelta una regola che privilegi alcuni nodi rispetto ad altri (ad esempio secondo la capacit`a del canale). Come nel caso precedente, la strategia pu`o non avere necessit`a di informazioni sulla rete.
Routing adattivo
Consente alle regole di routing di adattarsi alle condizioni della rete, in par-ticolare per quanto riguarda la congestione od il guasto di nodi o collegamen-ti. Tende anzi a prevenire le possibili cause di congestione, allontanandone quindi l’instaurazione prima di porvi rimedio.
Nelle intenzioni, dovrebbe quindi garantire prestazioni pi`u equilibrate ri-spetto a quelle proprie delle altre strategie, ma gli algoritmi di adattamento possono essere notevolmente complessi e difficili da controllare.
Infatti la principale difficolt`a di un algoritmo di routing adattivo sta pro-prio nel modo in cui viene ottenuta l’informazione “di controllo” riguardante la rete, e le modalit`a di reazione, cio`e di adattamento locale.
Le informazioni possono ridursi a dati disponibili localmente (ad esempio lunghezza della coda di spedizione) o relative ai nodi vicini (ad esempio richiedendo periodicamente ai vicini una valutazione del proprio carico di lavoro). Ma le strategie adattive normalmente devono appoggiarsi a dati relativi all’intera rete, per ottenere le migliori prestazioni. Purtroppo non `e semplice ottenere tali informazioni, che spesso non sono neppure attendibili.
Le maggiori reti di comunicazione hanno incontrato problemi con gli algoritmi di routing scelti: vediamo quale `e stata l’evoluzione.