Sartomiki.net

Routing e metrica
A seconda del protocollo di forwarding scelto si possono adottare diversi tipi di algoritmi di routing. Se si usa, ad esempio, un protocollo di tipo Label Swapping, la scelta del protocollo di routing è abbastanza libera, in quanto l'operazione di inoltro è completamente eseguita da pacchetti dati tradizionali che non hanno la funzione di segnalazione. Se si usa, invece, un protocollo di tipo forwarding by network (tecnica più utilizzata), l'algoritmo di routing è strettamente dipendente dal forwarding.
Gli algoritmi di routing, come già detto, hanno lo scopo di trovare quale è il percorso migliore all'interno di una rete data per tutti i nodi della rete. Affinchè l'algoritmo funzioni è necessario che tutti i nodi siano coerenti tra di loro, prendendo quindi scelte uguali in circostanze uguali.
Gli algoritmi di routing sono distribuiti, nel senso che all'interno della rete non è presente un'entità che coordina tutto, ma ogni nodo prende le decisioni in base a ciò che gli altri nodi gli comunicano.
La forma migliore di coerenza è data dall'ottimalità, per la quale tutti i nodi scelgono il percorso più breve per inoltrare i pacchetti. L'ottimalità non è rispettata da tutti gli algoritmi di routing, perchè normalmente trovare il percorso migliore comporta costi molto elevati in termini di banda e di tempo.
In più molti algoritmi ottimi non sono molto performanti in caso di guasti o di malfunzionamenti.
Il criterio per definire un algoritmo ottimo è dato dal peso (metrica) che è attribuito ad ogni arco del grafo in cui è rappresentabile la rete. Se la somma delle metriche per raggiungere ogni nodo è sempre la minore possibile, l'algoritmo si dice ottimo. La metrica è un valore numerico, che solitamente può variare con il tempo, ed è dato dall'analisi di diversi parametri, come il ritardo introdotto dall'arco, la distanza che deve percorrere il pacchetto, il traffico del ramo…
Affinchè gli algoritmi di routing funzionino in modo corretto è necessario che tutti i nodi utilizzino la stessa metrica.

Caratteristiche di un algoritmo
Per giudicare la bontà di un algoritmo di routing si prendono in considerazione diversi parametri:
-semplicità, nel senso che deve essere facilmente implementabile.
-robustezza e adattabilità, nel senso che deve essere in grado di rilevare velocemente gli errori o i cambiamenti di metrica, e deve adattarsi alla nuova situazione. Un algoritmo molto affidabile deve accorgersi autonomamente dei problemi, anche se nessuno gli indica l'errore. In più un algoritmo adattabile deve rendersi conto in modo automatico dell'introduzione di un nuovo nodo all'interno della rete.
-autostabilizzazione, nel senso che quando avviene una variazione all'interno della rete, essa non deve portare a un lungo transitorio. Non si devono mai creare situazioni nelle quali esistono percorsi non coerenti tra i nodi, perchè questo potrebbe portare all'intasamento della rete a causa e alla mancata consegna di alcuni pacchetti.
-robustezza Bizantina, anche se non è quasi mai preso in considerazione negli algoritmi di routing, consiste nella capacità dell'algoritmo di individuare se alcuni nodi stanno generando informazioni errate.
-ottimalità, consiste nel prendere sempre il percorso migliore.
-stabilità, nel senso che l'algoritmo deve raggiungere, dopo un trasitorio, una situazione in cui non i percorsi non variano a meno di ulteriori cambiamenti della metrica.
-equità, nel senso che non devono esistere nodi sovraccaricati o ignorati dalla scelta dei percorsi di instradamento.

Problemi di transitorio
Nel caso in cui si verifichino modifiche nella rete è necessario calcolare nuovamente tutti i percorsi. Questo genera dei problemi, in quanto questa operazione necessità di tempo. Durante il transitorio, infatti, la rete non è a regime e quindi i nodi potrebbero calcolare percorsi non coerenti. E' proprio in questi momenti che si creano due fenomeni:
-Black Hole, per il quale alcuni nodi perdono la conoscenza di una destinazione. In questo caso un router cancella il pacchetto, che quindi viene perso.
-Routing loop, per il quale alcuni nodi non hanno nelle proprie routing table percorsi coerenti e continuano a inviarsi i pacchetti formando un ciclo. Questo fenomeno è molto più pericoloso del black hole in quanto crea problemi di traffico elevato. Per evitare che si creino problemi irreversibili, normalmente i pacchetti sono dotati di un time to live, che prevede la distruzione di un pacchetto nel caso in cui esso percorra troppi nodi senza essere consegnato.
Questi due fenomeni avvengono spessissimo durante i transitori, è quindi necessario che i transitori durino il minor tempo possibile in modo da evitare il loro propagarsi. E' inoltre necessario diminuire il numero dei transitori e questo si ottiene evitando l'ottimalità dell'algoritmo, ma aumentando la stabilità.

Classificazione degli algoritmi di routing
Esistono diversi tipi di algoritmi di routing a seconda delle loro caratteristiche e dalle tecniche che utilizzano in determinate situazioni:
-Algoritmi non adattativi (detti statici). Essi non cambiano mai le loro decisioni e non si possono quindi adattare ai cambi di metrica.
--Fixed directory routing (routing statico), in cui l'operatore scrive manualmente le routing table di ogni nodo. Questo tipo di routing è molto personalizzabile e semplice da realizzare su reti piccole, ma risulta molto poco scalabile e non è per nulla tollerante ai guasti. Questo tipo di protocollo è utilizzato in piccoli laboratori.
--Flooding (allagamento), in cui è previsto che ogni nodo duplichi il pacchetto su tutte le uscite, in modo tale che alla fine almeno un pacchetto arrivi a destinazione. Questo algoritmo di routing è molto robusto ed è in grado di fare un broadcast sulla rete a livello 3. Il problema che porta velocemente alla saturazione della rete.
--Selective flooding, che è simile al flooding, anche se ogni nodo prima di inoltrare un pacchetto controlla di non averlo già inoltrato. In tal caso il pacchetto viene eliminato. Questo algoritmo necessita un hardware molto più sofisticato per la gestione dei pacchetti rispetto ai casi precedenti. Normalmente al posto che memorizzare l'intero pacchetto si memorizza solo il numero identificativo.
-Algoritmi adattativi (detti dinamici). Essi variano al cambiare della topologia.
--Routing centralizzato, che prevede che tutte le entità dialoghino con un'entità centrale, la quale raccoglie tutte le informazioni sulla rete, le elabora e definisce i percorsi. A questo punto consegna a tutti i nodi periferici i percorsi per raggiungere le varie destinazioni. Con questo algoritmo si può controllare la rete in modo molto semplice in quanto l'intelligenza si trova solo nel routing control center. E' una soluzione efficiente, che non crea loop.
--Routing isolato, secondo il quale ogni nodo della rete decide l'instradamento in maniera autonoma, senza parlare con nessuno. Un esempio sono i bridge e gli switch, che inoltrano i pacchetti a seconda di come li ricevono.
--Routing distribuito, che è l'unione dei due metodi precedenti. Per questo tipo di routing, infatti, tutti i nodi hanno la stessa importanza (come per il routing isolato), e le decisioni vengono prese in base alle informazioni reperite dalla rete (come per il routing centralizzato). I principali algoritmi di routing utilizzano questa politica (distance vector e link state).
-Algoritmi gerachici, che prevede di dividere le reti molto grandi in sottoreti, attraverso il partizionamento in domini più piccoli. Gli algoritmi di questo tipo dettano regole specifiche all'interno di questi domini.