Antonio Cianfrani
Open Shortest Path First
(OSPF)
Il protocollo OSPF
OSPF è un protocollo di routing interno (IGP)
OSPF è un protocollo di routing link-state: ogni router conosce l’esatta topologia della rete.
I pacchetti OSPF sono incapsulati direttamente in datagrammi IP, in cui il campo protocol è impostato a 89
La distanza amministrativa del protocollo OSPF è pari a 110Principi di funzionamento
Ciascun router OSPF emette periodicamente (default: 10 s) dei pacchetti Hello, per valutare possibili modifiche topologiche
Ogni router OSPF descrive la propria topologia (interfacce attive) tramite dei pacchetti denominati Link State Advertisement (LSA)
Le LSA vengono propagate in tutta la rete tramite la tecnica del flooding: ogni router che riceve una LSA la invia su tutte leinterfacce ad eccezione di quella da cui l’ha ricevuta
Ogni router ha una visione completa della rete (database delleLSA) e calcola l’insieme dei cammini a costo minimo (Shortest Path Tree: SPT) tramite l’algoritmo di Dijkstra.
Gli elementi checostituiscono il Sistema Autonomo sono:
•
i Router: si occupano di eseguire il protocollo OSPF•
le Network: collegano tra loro i Router e si dividono in Transit Network e StubNetwork (collegate ad un solo Router)
N1 R1
N3 R4 R5
N2 R2
R3
R6
R7
R10 N5
R8
N6 N7
N8 R11 R9
N10
R12 N9
3
3
1
1
1 8
8
7 6
6
6 1
N4
2
8
6 7
5
1
1
4 2
1 3 1
1
2 1
3
Router e network
Link State Advertisment (LSA)
Un LSA si compone di un Link State Header e un Link State Data
Tutti i tipi di LSA hanno la stessa Header
• Un campo Type identifica il particolare tipo di LSA:
Router_Lsa (type 1)
Network_Lsa (type 2)
……….
Link State Header LSA Type
Link State Data
Flooding
Gli LSA sono inviati a tutti gli altri Router dell’AS mediante una tecnica di flooding
• un LSA è rilanciato da un router su tutte le sue interfacce tranne quella da cui è stato ricevuto
• gli LSA trasportano un numero di sequenza
Evita il rilancio di pacchetti già rilanciati
Consente un corretto riscontro dal ricevente
R2
N
R3
R1 LSA LSA R4 LSA
Calcolo dello Shortest Path Tree (SPT)
Ogni router mantiene un database che riflette i dati aggiornati sulla topologia della rete
La topologia della rete è rappresentata come un grafo orientato – I nodi rappresentano router e network
– I rami rappresentano
• collegamenti diretti tra nodi di tipo router
• collegamenti tra nodi di tipo router e nodi di tipo network
Ogni router calcola lo Shortest Path Tree (insieme dei cammini ottimi) mediante l’algoritmo di Dijkstra e si costruisce la sua tabella di routing
OSPF: Esempio (1/2)
N1 R1
N3 R4 R5
N2 R2
R3
R6
R7
R10 N5
R8
N6 N7
N8 R11 R9
N10
R12 N9
3
3
1
1
1 8
8
7 6
6
6 1
N4
2
8
6 7
5
1
1
4 2
1 3
1 1
2 1
3
N1 R1
N3 R4 R5
3
N2 R2
3
0 1
0 1
R7
N5
R8
1 0
8
8
6 6
0 1
1 0
N6
4
R3
1 0
R6
7 6 6
8
5 7
R10
0 1
N7
3 0
R11 2
0
N8 R9
0
1 1 0
N10
3
0 1
R12 2 N9
N4
2
Ogni router calcola il proprio SPT mediante l’algoritmo di Dijkstra
Shortest Path Tree e Routing Table in R6
Destin. N.H. Cost N1
N2 N3 N4
R3 R3 R3 R3
10 10
7 8 N5
N6 N7 N8 N9 N10
R10 R10 R10 R10 R10 R10
8 12 10 11 13 14
N1 R1
N3 R4 R5
3
N2 R2
3
0 0
R7
N5
R8
N6
0
0
0
4
R3
1
R6
6
6
7
R10 1
N7
3
R11 N8 0
R9
1 0
N10
3
0
R12 2 N9
N4
2
OSPF: Esempio (2/2)
Configurazione di un router OSPF
Il comando per abilitare il protocollo OSPF è:
R(config)# router ospf id
Il campo id rappresenta un numero compreso tra 1 e 65535 ed ha validità locale
In seguito bisogna definire le sottoreti (e di conseguenza le interfacce) su cui è abilitato il protocollo:
R(config-router)# network network-address wildcard mask
area area-number
• La wildcard mask è il reciproco della maschera di sottorete
• Area: un AS può essere diviso in aree per risolvere problemi di scalabilità. L’area 0 c’è sempre.
Identificativo (ID) di un router OSPF
L’identificativo di un router OSPF è uno dei suoi indirizzi IP con il quale viene identificato all’interno del database topologico.
Viene configurato con il comando:
R(config-router)# router-id ip-address
Se manca il comando router-id si utilizza:
• Il più alto tra gli indirizzi loopback del router
• Se non ci sono indirizzi loopback configurati si utilizza il più alto tra i rimanenti indirizzi IP
Metrica OSPF
La metrica di un link OSPF può essere impostata liberamente, entrando nella configurazione della relativa interfaccia
R(config)# interface FastEthernet 0/0 R(config-if)# ip ospf cost costo
Se non viene impostata manualmente viene scelta in funzione della banda del link
Verifica configurazione OSPF
R# show ip ospf neighbor
R# show ip protocols
Antonio Cianfrani
Multi-area OSPF
Problemi di scalabilità dell’OSPF
Il protocollo OSPF presenta problemi di scalabilità:– Ogni router mantiene un database contenente tutte le LSA dell’AS – Le LSA di tutti i router e di tutte le network sono inviate all’interno
dell’AS
– Il calcolo dello Shortest Path Tree dipende dal numero di router e network: complessità O(NlogN), dove N è il numero di router e
network nella rete
Il problema viene risolto suddividendo un AS in aree
All’interno di ciascuna area i router “interni” si scambiano le informazioni relative alla propria area di appartenenza:– Database separati – Flooding indipendente
Multi-area OSPF (1/2)
AS 4 AS 4
AS 23 AS 23
Area 0
Area 1 Area 2
Multi-area OSPF (2/2)
AS 4 AS 23
Backbone area
– Ogni area è
connessa almeno all’area di backbone – SEMPRE presente
Area 0
Area 1 Area 2
ASBR (AS Border Router)
– Identificato da un
particolare bit (e bit) nella router LSA
ABR (Area Border Router)
– Contiene i database delle aree cui appartiene
– Identificato da un
particolare bit (b bit) nella router LSA
ABR
