Lo scopo degli algoritmi di instradamento è quello di determinare i percorsi, detti anche cammini, tra le sorgenti e i destinatari, attraverso la rete di router. Tipicamente il percorso migliore è quello con costo minimo. Questi, sia che si tratti di approccio logico-centralizzato, sia che si tratti di controllo locale, sono gli stessi, e sono la base.
Per formulare i problemi di instradamento si utilizza un grafo.
Un grafo è un insieme di nodi e un insieme di archi (edges), ove ciascun arco collega una coppia di nodi appartenenti all'insieme di nodi.
Nodi del grafo: router
Archi dei nodi: collegamenti tra i router

Quello che vediamo in figura è un grafo non orientato e pesato:

• Non orientato: arco percorribile in entrambe le direzioni (avanti/indietro)
• Pesato: ogni arco ha un peso o costo
• Il costo è il costo dell'arco che congiunge e , che in questo caso risulta essere 1.
• Se la coppia specificata è un arco che nel grafo non esiste, allora il costo sarà infinito.
• In un arco non orientato (considereremo solo questo tipo di grafi): se esiste e .
• Se esiste in (che è l'insieme degli archi), allora si dice che è un vicino di (o adiacente) di e viceversa.
• Dati due nodi nel grafo, esistono più percorsi che li collegano, uno o più percorsi tra questi avrà costo minimo, il problema che risolvono gli algoritmi di instradamento è quello di trovare il percorso minimo che collega due nodi del grafo (shortest path).

Un algoritmo di instradamento che è centralizzato calcola il percorso a costo minimo tra un sorgente e una destinazione avendo una conoscenza globale e completa della rete. Ciò vuol dire che un algoritmo di questo genere deve ricevere in input le informazioni relative ai router prima di effettuare il calcolo, ciò potrebbe essere effettuato (come abbiamo già detto):

• In ogni singolo router (localmente)
• In maniera logicamente centralizzata
  In pratica gli algoritmi con informazioni di stato globali sono spesso detti algoritmi link-state (LS) dato che devono essere a conoscenza del costo di ciascun collegamento della rete.

In un algoritmo di instradamento non centralizzato il costo minimo di un percorso viene
calcolato in modo distributivo e iterativo. Nessun nodo possiede informazioni complete sul costo di tutti i collegamento di rete. Inizialmente i nodi conoscono soltanto i costi dei collegamenti a loro adiacenti. Poi, attraverso un processo iterativo (e lento) e lo scambio di informazioni con i nodi adiacenti, un nodo gradualmente calcola il percorso a costo minimo verso una destinazione o un insieme di destinazioni. L'algoritmo che vedremo a tal proposito è distance-vector (DV).

Altro criterio per la categorizzazione di algoritmi di instradamento riguarda il fatto di essere statici o dinamici.

• Statici: i percorsi cambiano molto raramente, spesso come risultato di un intervento umano (modifica manuale di tabelle di inoltro).
• Dinamici: gli instradamenti vengono determinati al variare del volume di traffico o topologia della rete. Questo può essere eseguito periodicamente o come conseguenza diretta di un cambiamento. Questi algoritmi rispondono meglio ai cambiamenti della rete, ma più facilmente sono soggetti a problemi quali l'instradamento in loop e l'oscillazione dei percorsi.

Un altro modo ancora è il fatto di essere più o meno sensibili al carico della rete.

• Algoritmo sensibile al carico (load sensitive): i costi dei collegamenti variano dinamicamente per riflettere il livello corrente di congestione.
• Algoritmi non sensibili al carico (load insensitive, usati oggi): dato che il costo di un collegamento non riflette esplicitamente il suo attuale livello di congestione.

Navigazione:

• Instradamento Link-State
• Instradamento Distance-Vector
• OSPF e BGP