L’instradamento ha il compito di individuare il destinatario all’interno di una rete e di calcolare il percorso per raggiungerlo. L’instradamento è effettuato tramite tabelle. Le tabelle di ogni router non contengono tutte le informazioni riguardanti il percorso che il pacchetto svolgerà, ma solo il passo successivo a quello in cui il pacchetto si trova. I protocolli di instradamento definiscono le modalità di scambio delle informazioni con il fine di comporre una topologia. Gli algoritmi di instradamento si applicano alla topologia e mirano a trovare il percorso migliore, memorizzato nelle tabelle di instradamento. La procedura di forwarding è costituita dalla serie di passaggi fisici che i singoli pacchetti devono subire per essere indirizzati alla porta in uscita corretta.
Algoritmi di instradamento
La topologia viene trasformata in un grafo ad archi pesati e si applica un algoritmo come Dijkstra. Il peso degli archi può rappresentare la distanza, il costo, il ritardo o il livello di congestione. Il metodo per valutare il peso deve essere comune alla topologia. Per far conoscere a tutti i nodi la topologia si può ricorrere a diversi metodi: random, se tutti i nodi inviano su una porta causale la topologia che conoscono; flooding, se tutti i nodi inviano a tutte le porte la topologia; hot portato, se tutti i nodi inviano su una porta libera.
Gli algoritmi possono essere di tipo centralizzato, se un solo nodo esegue il calcolo dei percorsi e invia a tutti i nodi la topologia corretta oppure distribuito se tutti i nodi calcolano il percorso. Questa seconda tipologia si divide a sua volta in link state, se ogni nodo comunica a tutti i nodi la sua posizione o distance vector se ogni nodo dice ai suoi vicini tutto ciò che sa della rete.
Algoritmo link state
Ogni nodo comunica in multi cast l’elenco dei suoi vicini e il peso dei suoi collegamenti. Questa tecnica permette di individuare errori di consistenza, in quanto bisogna avere doppia corrispondenza. Dopo che è stata creata la tabella delle adiacenze si applica un algoritmo comune a tutti i nodi e si calcola la tabella dei percorsi minimi. Questo metodo è consistente e si evitano cicli.
Questo algoritmo h un tempo di convergenza immediato (dopo time out) e privo di errori.
Algoritmo di Distance Vector
Ogni nodo comunica ai vicini il peso per arrivare a tutti i nodi. In questo modo si ottiene una tabella delle distanze che ha una riga per ogni possibile destinazione e una colonna per ogni vicino. Tramite l’equazione di distance vector si ottiene il percorso migliore per raggiungere tutti i nodi. Questa equazione afferma che per andare da x a y passando per z si paga un peso pari al percorso da x a z e il minore dei pesi per andare da z a y passando per un altro nodo. Questo algoritmo è ricorsivo e funziona solo se poi ogni nodo comunica ai vicini i propri risultati. Quando il peso di un ramo aumenta si fa fatica a comunicare il cambiamento, provocando la perdita di alcuni pacchetti.
Questo algoritmo ha convergenza variabile e ha un’alta propagazione degli errori.
Per le immagini Ringraziamo ©scandblue
| < Prec. | Succ. > |
|---|
