2. The Link-state Database: Organization and Calculations (Database a stato del collegamento: Organizzazione e calcoli)
Questo capitolo descrive la struttura organizzativa del database a stato del collegamento OSPF e come utilizzare questo database per calcolare la tabella di routing.
Panoramica del capitolo (Chapter Overview)
Questo capitolo copre i seguenti argomenti principali:
- Metodi di rappresentazione di router e reti
- Costruzione dell'albero del percorso più breve
- Utilizzo delle informazioni di routing esterno
- Implementazione del multipath a costo uguale
2.1 Representation of Routers and Networks (Rappresentazione di router e reti)
Concetti fondamentali (Core Concepts)
Rappresentazione grafica (Graph Representation)
- Il sistema autonomo è modellato come grafo orientato (AS modeled as directed graph)
- Vertici (Vertices): router e reti
- Archi (Edges): interfacce router
- Costo (Cost): peso di ogni arco
Rappresentazione del router (Router Representation)
- ID router: identificatore univoco a 32 bit
- Lista interfacce: interfacce connesse alle reti
- Relazioni di vicinato: connessioni con router adiacenti
- Stato del collegamento: informazioni di stato per ogni interfaccia
Tipi di rete (Network Types)
| Tipo di rete | Inglese | Caratteristiche | Esempi |
|---|---|---|---|
| Punto a punto | Point-to-Point | Collega due router | Linea T1, PPP |
| Broadcast | Broadcast | Multi-accesso, supporto broadcast | Ethernet, Token Ring |
| NBMA | Non-Broadcast Multi-Access | Multi-accesso, nessun broadcast | Frame Relay, X.25 |
| Punto a multipunto | Point-to-MultiPoint | Trattato come insieme di collegamenti punto a punto | Frame Relay parzialmente meshato |
2.1.1 Representation of Non-broadcast Networks (Rappresentazione di reti non-broadcast)
Caratteristiche della rete NBMA (NBMA Network Characteristics)
- Nessun supporto per broadcast o multicast a livello di collegamento
- Configurazione manuale dei vicini richiesta
- Necessaria l'elezione di un router designato (DR) e di un router designato di backup (BDR)
- Deve avere connettività fully-meshed o utilizzare modalità punto a multipunto
Requisiti di configurazione (Configuration Requirements)
- Configurazione lista vicini
- Impostazione priorità DR
- Intervalli Hello e Dead
- Intervallo di polling (Poll Interval)
2.1.2 An Example Link-state Database (Esempio di database a stato del collegamento)
Questa sezione mostra la struttura e il contenuto del database a stato del collegamento attraverso un esempio concreto.
Topologia di rete esempio (Example Network Topology)
- Più router interconnessi
- Diversi tipi di rete
- Divisione in aree
- Collegamenti virtuali
Tipi di LSA (LSA Types)
| Tipo LSA | Nome | Descrizione | Ambito flooding |
|---|---|---|---|
| Type 1 | Router-LSA | Stato collegamenti router | All'interno dell'area |
| Type 2 | Network-LSA | Stato collegamenti rete | All'interno dell'area |
| Type 3 | Summary-LSA (rete) | Route di rete inter-area | Singola area |
| Type 4 | Summary-LSA (ASBR) | Route ASBR | Singola area |
| Type 5 | AS-external-LSA | Route esterne | Intero AS |
2.2 The Shortest-path Tree (Albero del percorso più breve)
Algoritmo di Dijkstra (Dijkstra's Algorithm)
Passaggi dell'algoritmo (Algorithm Steps)
- Inizializzazione: impostare se stesso come nodo radice
- Lista candidati: mantenere lista di vertici da elaborare
- Selezionare il vertice a costo minimo
- Aggiornare i costi dei vicini
- Ripetere finché tutti i vertici sono elaborati
Calcolo del costo (Cost Calculation)
- Costo interfaccia: basato su larghezza di banda o configurazione manuale
- Costo percorso: somma di tutti i costi delle interfacce lungo il percorso
- Formula costo predefinita:
Costo = Larghezza di banda di riferimento / Larghezza di banda interfaccia
Costruzione dell'albero (Tree Construction)
- Nodo radice: il router che esegue il calcolo
- Nodi interni: router e reti all'interno dell'AS
- Nodi foglia: route esterne (AS-external-LSA)
Termini chiave (Key Terms)
| Termine | Inglese | Definizione |
|---|---|---|
| Albero SPF | SPF Tree | Albero del percorso più breve con router come radice |
| Lista candidati | Candidate List | Vertici in attesa di essere aggiunti all'albero |
| Nodo genitore | Parent | Nodo predecessore nell'albero |
| Distanza | Distance | Costo dalla radice al nodo |
| Prossimo hop | Next Hop | Primo router per raggiungere la destinazione |
2.3 Use of External Routing Information (Utilizzo di informazioni di routing esterno)
Tipi di rotte esterne (External Route Types)
Rotta esterna Type 1 (Type 1 External)
- Costo = costo interno + costo esterno
- Metrica comparabile
- Applicabile a IGP all'interno dello stesso AS
Rotta esterna Type 2 (Type 2 External)
- Costo = costo esterno (costo interno solo per tie-breaking)
- Metrica non comparabile
- Applicabile a EGP di AS diversi
- Tipo predefinito OSPF
ASBR (Autonomous System Boundary Router)
Ruolo dell'ASBR (ASBR Role)
- Introduce rotte esterne in OSPF
- Genera AS-external-LSA
- Può essere qualsiasi router OSPF
- Annunciato tramite Type 4 Summary-LSA
Ridistribuzione delle rotte (Route Redistribution)
- Importare rotte da altri protocolli
- Impostare il tipo di rotta esterna
- Configurare il tag della rotta (Route Tag)
- Impostare l'indirizzo di inoltro (Forwarding Address)
2.4 Equal-cost Multipath (Multipath a costo uguale)
Concetto ECMP (ECMP Concept)
Principi di base (Basic Principles)
- Più percorsi equivalenti verso la stessa destinazione
- Costi dei percorsi completamente identici
- Traffico distribuito tra più percorsi
- Miglioramento dell'utilizzo della larghezza di banda e della ridondanza
Metodi di implementazione (Implementation Methods)
| Metodo | Descrizione | Vantaggi | Svantaggi |
|---|---|---|---|
| Round-robin per pacchetto | Per-packet round-robin | Semplice | Può causare disordine |
| Distribuzione per flusso | Per-flow distribution | Mantiene l'ordine | Richiede identificazione flusso |
| Basato su hash | Hash-based | Efficiente, deterministico | Può essere sbilanciato |
Parametri di configurazione (Configuration Parameters)
- Numero massimo di percorsi: numero massimo di percorsi ECMP supportati dal sistema
- Algoritmo di bilanciamento del carico: selezione del metodo di distribuzione del traffico
- Soglia di costo: intervallo di differenza di costo consentito
Voci della tabella di routing (Routing Table Entries)
Rappresentazione multipath (Multipath Representation)
- Prefisso di destinazione singolo
- Interfacce next hop multiple
- Costo della rotta identico
- Tipo di rotta identico
Riepilogo tecnico (Technical Summary)
Strutture dati chiave (Key Data Structures)
- Database a stato del collegamento (LSDB): memorizza tutti i LSA
- Albero SPF: struttura dell'albero del percorso più breve
- Tabella di routing: tabella di inoltro finale
- Tabella vicini: informazioni sui router adiacenti
Algoritmi importanti (Important Algorithms)
- Dijkstra SPF: calcolo del percorso più breve
- Flooding LSA: distribuzione delle informazioni sullo stato del collegamento
- Calcolo rotte: generazione della tabella di routing dall'albero SPF
- Selezione ECMP: bilanciamento del carico multipath
Considerazioni sulle prestazioni (Performance Considerations)
- Complessità calcolo SPF: O(N log N)
- Dimensione database: impatto sull'utilizzo della memoria
- Tempo di convergenza: da cambiamento topologia ad aggiornamento rotte
- Scalabilità: divisione in aree per reti grandi
Riferimenti (References)
- Testo completo: RFC 2328 Section 2
- Algoritmo di Dijkstra: E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"
Nota (Note): Questo documento si basa sulla specifica ufficiale RFC 2328. Per dettagli tecnici completi, pseudocodice degli algoritmi e linguaggio normativo, consultare il documento originale.