Passa al contenuto principale

14. Routing Table Calculation (Calcolo della tabella di routing)

Questo capitolo descrive il calcolo della tabella di routing usando l'algoritmo Dijkstra SPF.

14.1 Panoramica algoritmo Dijkstra​

Obiettivo​

  • Costruire l'albero del percorso più breve (SPF Tree)
  • Radice: router calcolante
  • Pesi degli archi: costi dei collegamenti

Strutture dati​

  • Lista candidati: nodi da elaborare
  • Albero SPF: nodi elaborati
  • Tabella routing: rotte finali

14.2 Passi dell'algoritmo​

Fase 1: Inizializzazione​

  • Aggiungere nodo radice (se stesso) ad albero SPF
  • Distanza = 0

Fase 2: Costruzione albero SPF​

WHILE lista candidati non vuota:
    1. Selezionare nodo V a distanza minima
    2. Aggiungere V ad albero SPF
    3. Per ogni vicino W di V:
       - Calcolare distanza
       - Aggiornare lista candidati

Percorsi equivalenti (ECMP)​

  • Più percorsi con stesso costo
  • Mantenere tutti i percorsi equivalenti

14.3 Fasi di calcolo delle rotte​

Rotte intra-area​

  • Generate da albero SPF
  • Priorità più alta

Rotte inter-area​

  • Calcolate da LSA Type 3
  • Priorità media

Rotte esterne (External)​

  • Calcolate da LSA Type 5
  • Type 1: Costo = interno + esterno
  • Type 2: Costo = solo esterno (predefinito)

14.4 Priorità selezione rotte​

  1. Rotte intra-area
  2. Rotte inter-area
  3. Rotte esterne Type 1
  4. Rotte esterne Type 2

Trigger di calcolo​

Ricalcolo necessario quando​

  • Cambiamento LSDB
  • Cambiamento stato interfaccia
  • Cambiamento stato adiacenza

Ottimizzazioni​

  • Calcolo ritardato
  • SPF incrementale (iSPF)

Punti tecnici​

Complessità algoritmica​

  • Implementazione standard: O(N²)
  • Implementazione ottimizzata: O((E + N) log N)

Punti di implementazione​

  • Coda di priorità efficiente
  • Ricerca LSDB veloce
  • Elaborazione ECMP corretta

Riferimenti (References)