Algoritmo d Dijkstra

Note

L'algoritmo di Dijkstra si applica al generico nodo sorgente .

Complessità

A differenza dell'algoritmo di Bellman-Ford, che ha complessità asintotica , l'algoritmo di Dijkstra ha complessità , e quindi è più conveniente.

Caratteristiche

Vantaggi:

  • Più flessibile in quanto ogni nodo ha una mappa completa della rete
  • Non è necessario inviare LSP periodicamente ma solo dopo un cambiamento
  • Tutti i nodi vengono subito informati dei cambiamenti
    Svantaggi:
  • È necessario un protocollo dedicato a mantenere l'informazione sui vicini
  • È necessario l'uso del flooding
  • È necessario un riscontro dei pacchetti di routing inviati
  • Difficile da implementare

Ogni nodo riconosce i nodi e le destinazioni adiacenti, e le distanze per raggiungerle. A questo punto il nodo invia tutti gli altri nodi della rete (flooding) mediante LSP (Link State Packet). Tutti i nodi costruiscono quindi un database di LSP e una mappa completa della tipologia della rete. Sulla base di questa informazione vengono calcolati i cammini minimi verso tutte le destinazioni.

Flooding

Ogni pacchetto in arrivo viene ritrasmesso su tutte le uscite eccetto quella da cui è stato ricevuto. Occorre prevenire i loop e di conseguenza si usa un numero di sequenza (e un database che li memorizza) e un TTL.