In questo articolo faremo una rapida - ma completa - panoramica sugli algoritmi di routing implementabili nel livello di rete, ma prima di iniziare questa analisi è necessario capire cosa si intende con la parola routing.
In linea generale, il routing è la funzione di instradamento svolta da un commutatore il cui compito consiste nel decidere dove inviare un dato elemeto di una comunicazione.
Questa funzione è normalmente implementata in dispositivi di rete detti router che lavorano, appunto, al livello rete al fine di gestirne i flussi di traffico. Oltre alle fuznionalità specifiche di inoltro, i Router possono svolgere diversi altri compiti, ad esempio:
Per quanto riguarda la funzione di routing (in senso stretto) possiamo fare un'analogia con il sistama postale: affinchè una lettera venga recapitata con successo al destinatario abbiamo bisogno di conoscerne nome e cognome ed indirizzo; oltre a queste informazioni, però, un centro di smistamento postale avrà bisogno di conoscere anche altri dati riguardanti, ad esempio, la situazione die centri postali limitrofi, ad esempio per sapere se un dato centro postale è chiuso o intasato al fine di cercare un percorso alternativo per la consegna della missiva.
Anche il processo di routing, necessariamente, ha bisogno di alcune informazioni: indispensabile l'indirizzo IP del destinatario del pacchetto, ma è anche necessario conoscere lo stato dei router adiacenti per capire se un cammino è interrottto, troppo congestionato ed eventualmente scegliere un percorso alternativo.
Il router quindi, acquisite le informazioni dagli altri router, creerà delle tabelle di routing (nel caso in cui venga implementato un algortimo di routing con tabella) dove verranno inseriti i cammini più convenienti per collegare una generica sorgente con una generica destinazione.
Distinguiamo due scenari possibili per quanto riguarda il processo di routing:
Come accennato precedentemente esistono vari tipi di algoritmi di routing più o meno performanti.
Un modo per identificare vantaggi e svantaggi, è definire dei criteri precisi di valutazione che sono la base per l'analisi di un algoritmo. I criteri di valutazione e confronto sono sostanzialmente i seguenti:
I quattro criteri di valutazione, a volte, possono trovarsi in contrapposizione tra di loro: lavorando sull'ottimizzazione, ad esempio, viene compromessa, di fatto, la semplicità, in quanto l'algoritmo ottimizzato solitamente è più complesso rispetto a quello non ottimizzato.
Diciamo che gli obiettivi principali da raggiungere sono la robustezza e la stabilità dell'algoritmo ed in un secondo momento riuscire ad avvicinarsi il più possibile all'ottimalità, per quanto riguarda le prestazione, senza però minare sensibilmente la semplicità di implementazione.
Gli algoritmi di routing, a seconda della loro implementazione, possono essere classificati nel modo seguente:
A questo punto è necessario, ai fini della comprensione delle pagine seguenti, introdurre il concetto di metrica.
Sostanzialmente con questo termine si intende classificare un certo percorso così da capire quale sia il più conveniente. Vengono così introdotti due parametri fondamentali per la metrica che sono gli Hops (che rappresentano il numero di nodi intermedi attraversati nel percorso mittente-destinatario) e il costo (che rappresenta il costo totale del cammino ovvero la somma dei costi di ogni singola interconnessione tra due nodi intermedi attraversati).
Solitamente il costo di un percorso è inversamente proporzionale alla velocità di trasmissione e, quindi, interconnessioni che garantiscono velocità di trasmissione molto alte avranno un costo molto basso.
L'obiettivo principale degli algoritmi di routing che ricerchino l'ottimo è quello di minimizzare il costo del percorso.
mrwebmaster.it
Formattazione testo mia.
In linea generale, il routing è la funzione di instradamento svolta da un commutatore il cui compito consiste nel decidere dove inviare un dato elemeto di una comunicazione.
Questa funzione è normalmente implementata in dispositivi di rete detti router che lavorano, appunto, al livello rete al fine di gestirne i flussi di traffico. Oltre alle fuznionalità specifiche di inoltro, i Router possono svolgere diversi altri compiti, ad esempio:
- integrare funzionalità di Access Point (nel caso si trovasse in una rete Wi-Fi);
- svolgere funzioni di filtro mediante l'implementazione di firewall interni per l'analisi del traffico.
Per quanto riguarda la funzione di routing (in senso stretto) possiamo fare un'analogia con il sistama postale: affinchè una lettera venga recapitata con successo al destinatario abbiamo bisogno di conoscerne nome e cognome ed indirizzo; oltre a queste informazioni, però, un centro di smistamento postale avrà bisogno di conoscere anche altri dati riguardanti, ad esempio, la situazione die centri postali limitrofi, ad esempio per sapere se un dato centro postale è chiuso o intasato al fine di cercare un percorso alternativo per la consegna della missiva.
Anche il processo di routing, necessariamente, ha bisogno di alcune informazioni: indispensabile l'indirizzo IP del destinatario del pacchetto, ma è anche necessario conoscere lo stato dei router adiacenti per capire se un cammino è interrottto, troppo congestionato ed eventualmente scegliere un percorso alternativo.
Il router quindi, acquisite le informazioni dagli altri router, creerà delle tabelle di routing (nel caso in cui venga implementato un algortimo di routing con tabella) dove verranno inseriti i cammini più convenienti per collegare una generica sorgente con una generica destinazione.
Distinguiamo due scenari possibili per quanto riguarda il processo di routing:
- Mittente e destinatario sono situati nella stessa rete
Il router leggendo il pacchetto si accorge che la destinazione si trova nella rete da lui gestita e quindi semplicemente inoltrerà il pacchetto verso la destinazione. - Mittente e destinazione sono situati su reti diverse
In questa situazione le cose si complicano perchè l'instradamento non è immediato. Il router che serve la rete del mittente si accorge che il pacchetto non è indirizzato a nessuno degli host a lui connessi. A questo punto il router controlla la sua tabbella di routing e inoltra il pacchetto al router indicato nella tabella. Questo processo di inoltro del pacchetto tra vari router prosegue finchè il pacchetto non raggiunge il router che serve la rete di destinazione. A questo punto quest'ultimo si accorge che il pacchetto è indirizzato ad uno dei suoi host connessi e semplicemente inoltra il pacchetto direttamente all'host di destinazione.
Algoritmi di routing e classificazione
Come accennato precedentemente esistono vari tipi di algoritmi di routing più o meno performanti.
Un modo per identificare vantaggi e svantaggi, è definire dei criteri precisi di valutazione che sono la base per l'analisi di un algoritmo. I criteri di valutazione e confronto sono sostanzialmente i seguenti:
- Semplicità: per quanto riguarda la realizzazione e l'implementazione nei dispositivi.
- Robustezza: l’algoritmo deve sapere reagire in maniera positiva e autonoma a particolari perturbazioni. Più precisamente l'algoritmo non deve subire penalizzazioni, per quanto riguarda l'efficienza, se avvengono degli errori o cambiamenti di metrica (che spiegheremo più avanti) all'interno della rete. Un buon algoritmo di routing deve rilevare autonomamente se sono presenti degli errori, per esempio un mal funzionamento di un nodo, ed adattarsi di conseguenza.
- Stabilità: l'algoritmo dovrà convergere ad una situazione che garantisca la stabilità. In particolare se avvengono errori all'interno della rete che allontanano l'algoritmo del punto di stabilità, l'algoritmo deve reagire velocemente a questa situazione e riuscire a convergere nuovamente alla stabilità nel minor tempo possibile.
- Ottimalità: questo parametro viene valutato seguendo opportuni criteri.
I quattro criteri di valutazione, a volte, possono trovarsi in contrapposizione tra di loro: lavorando sull'ottimizzazione, ad esempio, viene compromessa, di fatto, la semplicità, in quanto l'algoritmo ottimizzato solitamente è più complesso rispetto a quello non ottimizzato.
Diciamo che gli obiettivi principali da raggiungere sono la robustezza e la stabilità dell'algoritmo ed in un secondo momento riuscire ad avvicinarsi il più possibile all'ottimalità, per quanto riguarda le prestazione, senza però minare sensibilmente la semplicità di implementazione.
Gli algoritmi di routing, a seconda della loro implementazione, possono essere classificati nel modo seguente:
- Algoritmi con tabella: Un nodo che implementa un algoritmo di questa famiglia memorizza, per ogni richiesta di instradamento in ingresso, la linea in uscita che deve essere utilizzata.
- Algoritmi senza tabella: Questo tipo di algoritmi non prevedono abbinamenti ingresso-uscita predefiniti, ma sono di tipo reattivo, cioè attivati solo su richiesta, quando necessario.
- Algoritmi centralizzati: Prevedono esclusivamente l'uso di tabelle e hanno una unità di elaborazione dell’algoritmo centralizzata.
- Algoritmi distribuiti: Prevedono un’esecuzione dell’algoritmo in maniera distribuita a volte detta cooperativa. Anche in questo caso si prevede l'uso di tabelle.
- Algoritmi isolati: Tipicamente rivolti a realizzazioni senza tabella. Prevedono l’esecuzione in locale (stand-alone) dell’algoritmo.
A questo punto è necessario, ai fini della comprensione delle pagine seguenti, introdurre il concetto di metrica.
Sostanzialmente con questo termine si intende classificare un certo percorso così da capire quale sia il più conveniente. Vengono così introdotti due parametri fondamentali per la metrica che sono gli Hops (che rappresentano il numero di nodi intermedi attraversati nel percorso mittente-destinatario) e il costo (che rappresenta il costo totale del cammino ovvero la somma dei costi di ogni singola interconnessione tra due nodi intermedi attraversati).
Solitamente il costo di un percorso è inversamente proporzionale alla velocità di trasmissione e, quindi, interconnessioni che garantiscono velocità di trasmissione molto alte avranno un costo molto basso.
L'obiettivo principale degli algoritmi di routing che ricerchino l'ottimo è quello di minimizzare il costo del percorso.
mrwebmaster.it
Formattazione testo mia.
