Router - Progettazione e gestione delle reti

Richiami sui grafi diretti pesati
G (N,A)
{N} nodi
{A} archi tra nodi rappresentati come coppie di nodi (i,j)
Ad ogni (i,j) € A è associato un peso d i,j
Considereremo solo grafi connessi: per ogni i,,j € N esiste un
cammino da i a j
Cammino da “i “ a “j”: percorso senza nodi ripetuti
Percorso: {n1,n2,.....,nk}, dove ni € N e (ni, ni+1) € A
L'algoritmo di routing calcolerà per ogni coppia di nodi un
cammino di lunghezza minima pari alla somma dei pesi d i,j
L'algoritmo per il calcolo dei cammini minimi può essere
eseguito in modo distribuito tra i router della rete e ha
complessità polinomiale funzione del numero dei nodi della rete
1
Database topologico
È rappresentato da un grafo diretto
Vertici: router oppure reti
Arco:
tra due router: esiste una connessione punto-punto tra i due router
tra router e rete: se il router ha una interfaccia sulla rete
Vertici di transito: archi entranti e uscenti
Reti multiaccesso (e.g. Ethernet): reti con 2+ router
Reti stub: reti con un solo router
Reti non broadcast: e.g. reti punto-punto
Interfaccia: connessione fisica di un router con una rete (e.g.
porta seriale, porta ethernet,..)
Neighbor: 2 router che hanno una interfaccia su una rete comune
2
Rete punto - punto
From
interfaccia
R1
Ia
4
R1 (origine)
4
4
Ib
R2
Ib
6
R1
R2
To
R1
R2 4
Ia
Ib 4
R2
6
6
Grafo diretto
6
Ia
SPF tree di R1
I router sono collegati in modalità diretta punto-punto (e.g. un collegamento
seriale)
Le porte/interfacce dei router sono indentificate tramite Ix
Il peso associato alla rete è diverso a seconda del verso di percorrenza
(potrebbe anche essere simmetrico)
L'interfaccia viene rappresentata come rete stub a cui è connesso il solo router
a cui appartiene
3
Rete multi accesso
4
R1
R1
R2
To
N1
R3
R4
4
R1 (origine)
R3
R1
R2
R3
R4
N1
R2
R3
R4 N1
0
0
0
0
4
4
4
4
Grafo diretto
N1
R2
From
R4
SPF tree di R1
I router sono attestati ad una stessa LAN
Il peso associato alla rete è lo stesso per tutti i router
La rete è connessa con un arco di costo zero a tutti i router (ogni coppia di
router può comunicare direttamente sulla rete)
4
Rete Stub ( rete multiaccesso con 1 router)
From
R1
4
R1
To
N1 4
N1
4
R1 (origine)
Grafo diretto
N1
SPF tree di R1
Rete STUB (non è possibile attraversarla) – un solo arco
La rete è una foglia dello SPF
Differenti reti STUB: reti multiaccesso con 1 router,
interfaccia di rete punto - punto, interfaccia di loopback di un
router
5
Esempio completo
R1
1
N5
1
R2
N6
N3
N1
1
N4 3
R3
R5
N5
6
Ib
4
Ia
3
R4
2 N2
2
N6
1
R1 (origine)
N1
0
0
3
R2 R3
4 4 N4
N5 N6
R4 Ib R5
2
6
Ia N5 N6 N2
SPF tree di R1
TO
R1
R2
R3
R4
R5
N1
N2
N3
N4
N5
N6
N7
Ia
Ib
FROM
R1 R2 R3 R4 R5 N1 N2 N4
0
0
6
0
0
4
0
0 0
1 1 1
2 2
3
3
6
4
Grafo diretto
N1, N2 e N4 sono reti interne al
dominio OSPF
N3, N5 e N6 sono reti esterne ( la
gestione delle reti esterne in OSPF
sarà illustrata nel seguito)
6
Esempio completo
N1, N2, N4 sono reti multiaccesso
Ia, Ib sono reti STUB
N3, N5, N6 sono reti esterne; i router R2 e R5 “apprendono” queste reti da un
altro protocollo (e.g. RIP); queste network sono viste come originate da un
dominio esterno anche se potrebbero essere di un protocollo di routing diverso
nella stessa rete; nel caso più generale possono essere reti di altri domini (e.g.
Connettività Internet – BGP-4) “iniettate” nell'OSPF. I router inseriscono questi
reti nella propria tabella di routing assieme alle reti interne. Vedremo che le reti
esterne possono essere “iniettate” nell'OSPF in 2 modi differenti
In OSPF se una rete può essere raggiunta con più percorsi di costo uguale, il
traffico userà in uguale misura tali percorsi
7
OSPF routing gerarchico
Un AS può essere suddiviso in più aree allo scopo di:
Ridurre la complessità della topologia (la topologia di ogni
area non è nota alle altre aree)
Ridurre il traffico di controllo
Proteggere la rete da problemi/instabilità di routing
(isolamento delle aree)
Regole da seguire:
Esiste un'area speciale chiamata backbone a cui tutte le altre
aree devono essere connesse
8
OSPF routing gerarchico
N14
N14
N9
N15
R14
R9
N3
N2
R3
R2
R15
R10
R14
R7
R11
N1
R1
N5
R5
N11
R4
N6
N13
R13
N12
R12
R6
N4
N10
N7
R8
N8
Tutti i router hanno lo stesso DB topologico che contiene un
numero di vertici pari alla somma dei router (R) e delle reti (N)
Matrice sparsa di dimensione (R+N) x (R+N)
9
OSPF routing gerarchico
FROM
TO R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 N1 N2 N3 N4 N5 N6 N7 N8 N9 N10 N11 N12 N13 N14 N15
R1
R2
R3
R4
R5
R6
R7
R8
R9
R10
R11
R12
R13
R14
R15
N1
N2
N3
N4
N5
N6
N7
N8
N9
N10
N11
N12
N13
N14
N15
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Grafo diretto
10
OSPF routing gerarchico
Area 1
IR
Area 4
ABR
IR
Area 2
IR
ABR
Area 0
IR
IR
IR
ABR
ABR
Area 3
IR
I router ABR (Area Border) hanno delle interfacce in due aree
diverse, IR (Internal Router) hanno tutte le interfacce in un'area
I router di backbone sono quelli che hanno almeno una
interfaccia nell'area 0
11
OSPF routing gerarchico
Area 1
R14
R9
R14
R3
R2
Area 2
R15
R10
R7
Area 0
R1
Area 4
R11
R13
R5
R4
R12
R6
Area 3
R8
Le topologie delle singole aree sono invisibili all'esterno
dell'area
I router ABR conoscono la topologia delle aree direttamente
connesse e la topologia del backbone
12
OSPF routing gerarchico
Area 2
N15
N10
R15
R10
R4
N1,N2,N3,N5,N6,N7,N8,N9,
N11,N12,N13,N14,N15
N4
Con riferimento all'area 2 tutte
le reti esterne sono viste dai
router interni come connesse
all'ABR (R4)
La dimensione della matrice,
se la dimensione dell'area è
trascurabile rispetto all'intera
rete, é N x ( Rarea + Narea )
Vedremo che in realtà i router
di un'area devono concoscere
anche gli ASBR
TO
R4
R10
R15
N1
N2
N3
N4
N5
N6
N7
N8
N9
N10
N11
N12
N13
N14
N15
FROM
R4 R10 R15 N4 N10 N15
X
X
X
X
X X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Grafo diretto
13
Summarization delle rotte inter-area
Meccanismo previsto da OSPF per ridurre il numero di annunci
(meno traffico di controllo in rete, meno carico elaborativo sui
router)
Consente di inviare un unico annuncio (consolidato) di
destinazioni multiple (route)
Il router deputato al compito di consolidare gli annunci è l'ABR
L'ABR invia un annuncio consolidato verso il backbone
Il backbone distribuisce gli annunci già consolidati verso le
altre aree
Prerequisito per poter effettuare la summarization è che le reti
di un'area OSPF siano contigue
14
Summarization delle rotte inter-area
Area 0
Backbone
Area 2
80.17.0.0 255.255.248.0
R7
80.17.1.0 255.255.255.0
80.17.4.0
R14
255.255.255.0
R11
R13
80.17.2.0
255.255.255.0
Network 01000000 00010001 00000001 00000000
Reti: 80.17.1.0
01000000 00010001 00000010 00000000
Reti: 80.17.2.0
01000000 00010001 00000100 00000000
Reti: 80.17.4.0
01000000 00010001 00000000 00000000
11111111 11111111 11111000 00000000
Reti: 80.17.0.0 – 80.17.7.0
80.17.0.0/21
15
Summarization delle rotte inter-area
Area 3
Area 0
Backbone
Area 2
80.17.0.0
255.255.224.0
80.17.4-7.0
ABR
80.17.4.0
255.255.252.0
Network 01000000 00010001 00000001 00000000
mask
R7
80.17.1.0 255.255.255.0
80.17.16.0
R14
255.255.240.0
R11
R13
80.17.2.0
255.255.254.0
Reti: 80.17.1.0 /24
01000000 00010001 00000010 00000000
Reti: 80.17.2.0 - 80.17.3.0
01000000 00010001 00010000 00000000
Reti: 80.17.16.0 - 80.17.31.0
01000000 00010001 00000000 00000000
11111111 11111111 11100000 00000000
Reti: 80.17.0.0 - 80.17.31.0/24
Inconsistenza di routing per le reti 80.17.4.0, ...., 80.17.7.0/24 perchè sono annunciate da due
aree; il problema è causato dall'assegnazione non consecutiva delle reti nell'area 2. In questo
caso la summarization non va usata.
16
OSPF descrizione dei tipi di pacchetti
I messaggi scambiati tra i router sono classificati nelle seguenti tipologie:
1. HELLO: per scoprire e controllare lo stato (alive ?) dei router vicini
2. Database Description (DD): usati nel processo di creazione delle adiacenze
3. Link State Request (LSR): usati nel processo di creazione delle adiacenze
4. Link State Update usati per scambiare gli “annunci” in modo reliable . Sono i
pacchetti che trasportano informazioni relative alla raggiungibilità di specifiche
destinazioni un hop più avanti rispetto al router che ha originato l'annuncio. Le
unità informative contenuti all'interno dei pacchetti LSU, sono chiamati Link State
Advertisment (LSA) e vanno a popolare il database OSPF
5. Link State Upadate ACK: riscontrano la ricezione dei LSA
17
OSPF descrizione dei tipi di pacchetti
Hello
Viene inviato periodicamente (in multicast) dal router su
tutte le sue interfacce; in questo modo il router avvisa i
suoi vicini della sua presenza e dei vicini (neighbors)
precedentemente appresi
Tra alcuni vicini (tra i quali è stata già accertata la
comunicazione bidirezionale) si stabiliranno delle relazioni
più forti “adiacenze”); in particolare, i router agli estremi
di una rete punto-punto diventeranno sempre adiacenti,
mentre nelle reti multiaccesso ogni router diventa
adiacente solo con un router particolare (che fa da centro
stella per tutti i router della rete e verso l'esterno) chiamato
Designated Router e il suo back-up caldo (BDR)
il protocollo OSPF prevede che i DB siano sincronizzati
tra i router adiacenti
18
Processamento dei pacchetti OSPF – Hello
Invio dei pacchetti Hello:
contiene:
la lista di tutti i router da cui si è già ricevuto un pacchetto hello e
l’identificativo proposto per il DR e il BRD (0.0.0.0 in caso di mancanza di
indicazioni)
la priorità del router (utilizzata nella scelta del DR e del BDR)
i valori di HelloInterval e RouterDeadInterval rispettivamente l’intervallo tra
due invii successivi di un pacchetto Hello e il tempo entro cui il neighbor deve
ascoltare un Hello prima di dichiarare morto il router (questi due valori
devono essere identici per tutti i router sulla stessa area OSPF)
network mask
`
Indirizzo IP di destinazione: sulle reti punto-punto e reti multicast viene
inviato all’indirizzo multicast AllSPFRouters (224.0.0.5)
Indirizzo IP sorgente: indirizzo IP dell’interfaccia del router
Frequenza di invio: ogni HelloInterval secondi
• Utilizzo: discovery e mantenimento dei neighbor
• A chi viene inviato: su tutte le interfacce del router
19
Creazione delle adiacenze
bo
h
g
i
e
n
Router
r
R
R
interfaccia
R
R
Per ogni porta di connessione esterna del router (interfaccia) il router
gestisce:
una macchina a stati dell’interfaccia
una macchina a stati per ogni neighbor
La macchina a stati dell’interfaccia è responsabile della gestione
degli eventi di interfaccia e dell’elezione del DR della rete
La macchina a stati dei neighbor gestisce il processo di creazione
delle adiacenze
20
Struttura dati per gestire i neighbor
Tra due router ospf presenti su una stessa rete viene instaurata una “conversazione”; se tra una coppia di
router esiste più di una rete in comune, verrà istanziata una conversazione per ognuna di essa.
La struttura dati identifica una particolare istanza di conversazione tra due router e il suo stato in merito
alla creazione dell’adiacenza tra due router (che può essere vista come lo stadio più alto di evoluzione di
neighborood tra due router, non sempre raggiunto). Di seguito sono descritti i campi della struttura dati:
Stato
Inactivity timer: istanziato pari al RouterDeadInterval, se scaduto indica che non sono stati ricevuti hello
dal neighbor
master/slave: ruolo durante la fase di scambio del database tramite pacchetti Database Description
DD sequence number: identificativo dell’ultimo pacchetto DD inviato
ultimo pacchetto DD ricevuto: utilizzato per individuare pacchetti duplicati
Neighbor id: identificativo del neighbor, appreso dal pacchetto hello ricevuto
neighbor priority: utilizzata per il calcolo del DR, BDR
neighbor’s DR e BDR: quali sono il DR e il BDR a detta del neighbor
Link state retransmission list: elenco dei LSA inviati per i quali non è stato ricevuto un ACK dal router
adiacente e che quindi vanno ritrasmessi
Database Summary List: lista completa dei LSA che compongono il DB del router e che andranno trasmessi
nel momento in cui si crea l’adiacenza
Link state request list: il router crea questa lista man mano che riceve i pacchetti DD dal router adiacente;
successivamente la invia tramite i pacchetti Link State Request e cancella gli item della lista quando riceve i
relativi pacchetti Link State Updade
21
Struttura dati per gestire una interfaccia
Type : punto-punto, broadcast,..
Stato: stato funzionale
IP address: questo indirizzo viene usato come IP sorgente di tutti i
pacchetti di controllo che escono dall'interfaccia
Area_ID: area OSPF
Hello Interval: parametro che definisce l'intervallo in secondi tra due
pacchetti Hello (inserito nei pacchetti Hello trasmessi)
RouterDeadInterval: parametro che definisce il tempo massimo che
trascorre tra 2 hello dopo il quale un neighbor viene considerato non più
disponibile ( = n* HelloInterval) - (inserito nei pacchetti Hello trasmessi)
InfTranDelay: stima del tempo di propagazione di un messaggio
sull'interfaccia (viene sommato all'age dell'LSA quando il messaggio viene
inoltrato)
Router Priority: valore usato nell'elezione del DR/BDR
22
Struttura dati per gestire una interfaccia
Hello Timer: timer che scade ogni Hello Interval secondi e causa
l'invio di un pacchetto Hello
Wait Timer: timer che provoca l'uscita dallo stato di waiting e la
selezione del DR
Lista dei neighbors: è la lista di tutti i neighbor (appresi tramite
pacchetti Hello) presenti sulla rete a cui l'interfaccia è connessa
Designated router: identificato da Router ID e interfaccia IP del
router sulla rete
Backup Designated router: identificato da Router ID e interfaccia IP
del router sulla rete
Costo: metrica dell'interfaccia (output)
RxmtInterval: intervallo per la ritrasmissione di LSA
AuType/Authentication Key: è possibile prevedere la mutua
autenticazione tra i router che partecipano al processo OSPF
23
Neighbor states: cambiamenti determinati dai pacchetti Hello
Down
start
Attempt
AdjOK? é un evento generato dal
processo di gestione
dell'interfaccia a seguito di un
cambiamento del DR/BDR (è
descritto nell'ambito del
processo di elezione del DR/BDR
HelloReceived
init
AdjOK?
2-wayReceived
ExStart
AdjOK?
HelloReceived
1-wayReceived
2-Way
AdjOK?
Attempt: stato utilizzato solo per reti NBMA (non broadcast multiaccess)
Init: il router ha ricevuto un pacchetto Hello dal neighbor ma lui stesso non è
inlcuso nella lista dei router neighbors (la comunicazione non è ancora
bidirezionale)
2-Way/ExStart: è stata stabilita la comunicazione bidirezionale; l’evento 2wayReceived indica che il router ha visto se stesso nella lista dei neighbor del
pacchetto Hello ricevuto; l’evento 1-wayReceieved (pacchetto Hello che non
contiene se stesso nella lista dei router) riporta allo stato init. Il router sceglie se
passare in 2-Way o ExStart a seconda se debba o meno provare a istanziare
un’adiacenza con l’altro router (sulle reti punto-punto e multiaccesso è sempre
necessario). Lo stato 2-Way non prevede ulteriori evoluzioni.
24
Neighbor states: come decide un router se creare o meno
un'adiacenza
Reti Punto-Punto: crea sempre l'adiacenza
Reti broadcast: le adiacenze si creano solo verso i DR /BDR
Quando viene innescato il processo decisionale:
• quando la comunicazione diventa bidirezionale (evento 2-wayReceived)
• tutte le volte che cambia il DR/BDR (evento scatenato dal processo di
gestione dell'interfaccia)
Condizioni che scatenano il processo di creazione di un'adiacenza su una
rete broadcast :
• il router stesso è un DR o un BDR
• il neighbor è un DR o un BDR
25
Macchina a stati dell’interfaccia
down
InterfaceUP
Waiting: il router (monitarando i
pacchetti Hello) sta cercando di
scoprire l’identità di DR/BDR
InterfaceUP
Waiting
P-to-P
Wait timer
Neighbor change
Backup
Neighbor
DRother
?
point-to-point: una volta in
questo stato il router è pronto a
creare le adiacenze con il neighbor;
l’interfaccia inizia quindi ad
inviare pacchetti Hello con un
intervalli definito da HelloInterval
Neighbor
change
change
DR
Eventi:
wait timer: trascorso il tempo max previsto per l’elezione di DR/BDR
Neighbor change: vedi dopo...
26
Macchina a stati dell’interfaccia
down
InterfaceUP
InterfaceUP
Waiting
P-to-P
Wait timer
Neighbor change
Backup
Neighbor
DRother
?
Neighbor
change
change
DR
Stato
Evento
Nuovo stato
Azione
Down
InterfaceUP
P-to-P / Waiting /
DROther
Inizia l’invio di pacchetto Hello ogni
HelloInterval secondi; se l’interfaccia è p-top passa in questo stato; altrimenti se
l’interfaccia è configurata come non elegibile
passa direttamente nello stato DROthter
27
altrimenti passa in waiting
Macchina a stati dell’interfaccia
down
InterfaceUP
InterfaceUP
Waiting
P-to-P
Wait timer
Neighbor change
Backup
Neighbor
DRother
?
Neighbor
change
change
DR
DR other: il router non è né DR
né BDR; in questo caso dovrà
creare adiacenze verso il DR e il
BDR eletti
Back up: router eletto come
back up designated roueter;
dovrà pertanto creare adiacenze
con tutti i router della rete
multiaccesso. In caso di fail del
DR dovrà prendere il suo posto.
DR: il router è stato eletto
come Designated Router della
LAN. Il router dovrà creare
adiacenze con tutti i router della
rete e generare LSA per tutta la
rete multiaccesso
Eventi:
Neighbor change: è cambiato l’insieme dei router con cui c’è una comunicazione
bidirezionale (vedi macchina a stati neighbor) oppure si è aggiunto/eliminato un router
che si dichiara DR/BDR oppure è cambiata la priorità di uno di questi router. Questo 28
evento causa il ricalcolo del DR/BDR della rete multiaccesso
Macchina a stati dell’interfaccia
down
InterfaceUP
InterfaceUP
Waiting
P-to-P
Wait timer
Neighbor change
Backup
Neighbor
DRother
?
Neighbor
change
change
DR
Stato
Evento
Nuovo stato
Azione
Waiting
wait timer
DR/backup/DRotrher
Esegue il calcolo di DR/BDR e
cambia stato di conseguenza
Backup /
DR / DR
Other
Neighbor
change
DR/backup/
DRother
Esegue il calcolo di DR/BDR e
cambia stato di conseguenza
29
Esempio di comunicazione tra processi interfaccia e neighbor
Processo di
Processodidi
Processo
gestione
gestione
gestione
neighbor
neighbor
neighbor
Processo di
gestione
interfaccia
init
DR/DRother.
Evento “Neighbor
change”
2-way
Esegue elezione
DR/BDR
Evento “AdjOK?”
Cambia stato
DR/DRother.
Exstart
30
Processo di elezione del DR
Stato neighbor
2-way
Exstart o
superiori
Evento
Nuovo stato
Azione
AdjOK?
Exstart / 2-way
Verifica se con il neighbor deve essere
creata un'adiacenza; se si, passa nello stato
Exstart, altrimenti resta nello stato 2-way
AdjOK?
2-way o nessun
cambiamento di stato
Verifica se l'adiacenza esistente deve
essere mantenuta; se si resta nello stato
attuale, altrimenti distrugge l'adiacenza,
cancella gli LSA e i DB summary list di
questa adiacenza e passa nello stato 2-way
Il processo di calcolo del DR/BDR triggera il processo di costruzione delle adiacenze con
l'evento AdjOK? , tramite il quale chiede di verificare se le adiacenze attuali devono essere
mantenute oppure no e se nuove adiacenze devono essere create.
31
Neighbor states: cambiamenti determinati da DB exchange
Exstart
NegotiationDone
Exchange
ExChangeDone
Loading
Full
LoadingDone
Exstart: primo stadio del processo di creazione delle adiacenze; in questa fase viene
negoziato chi è il master e il numero di sequenza iniziale dei pacchetti Database
Description
Exchange: stato nel quale viene sincronizzato il DB OSPF tramite l'invio di pacchetti
DD
Loading: il router ha scoperto dai pacchetti DD che esistono degli LSA più recenti di
quelli contenuti nel suo DB e ha chiesto quindi di riceverli esplicitamente tramite
pacchetti Link State Request
Full: adiacenza completata
32
Passaggio dallo stato exstart a exchange
10.0.0.3
10.0.0.1
R1
R3
P =1
.1
P =1
.3
Lo stato del neighbor è Exstart – bisogna negoziare chi è Master/slave e il numero di sequenza iniziale dei
pacchetti DD
Numero di
sequenza
Bit che indica inizio
di una nuova
sequenza
More bit: indica che
si hanno altri DD da
inviare
Bit Master/Slave:
indica il proprio
stato
DD ( Seq = x, I, M , Master)
DD ( Seq = y, I, M , Master)
DD ( Seq = y, M , Slave)
DD ( Seq = y+1, M , Master)
R1 accetta R3 come master (router id più alto) e adotta il numero di sequenza di R3; lo stato del neighbor passa
a Exchange
33
Passaggio dallo stato exchange a loading
10.0.0.3
10.0.0.1
R1
P =1
slave
.1
master
R3
P =1
.3
DD ( Seq = y+1, M , Master)
DD ( Seq = y+1, M , Slave)
DD ( Seq = y+n, Master)
DD ( Seq = y+n, Slave)
Il master trasmette tutto il suo database LSA in pacchetti DD; lo slave risponde con
pacchetti DD che hanno lo stesso numero di sequenza (ACK) e contengono gli LSA
dello Slave. Nota che i pacchetti DD contengono solo le intestazioni degli LSA non gli
LSA stessi.
Se il master completa la trasmissione degli LSA prima dello slave, continuerà ad inviare
pacchetti DD fino a che lo slave non ha completato anch'esso l'invio dei suoi LSA
34
Passaggio dallo stato loading a full
10.0.0.3
10.0.0.1
R1
P =1
slave
master
.1
R3
P =1
.3
LSR
LSU
LSU-ACK
LSR
LSU
LSU-ACK
Infine i due peer si scambiano gli LSA che risultano più aggiornati o nuovi rispetti a
quelli contenuti nel proprio DB.
Prima il master aggiorna i propri LSA, successivamente lo slave aggiorna i propri LSA
35
Funzionalità DR/BDR (1/2)
DR
R
BDR
R
R
R
I router della LAN sincronizzano il loro DB con il DR e in
caso di fault con il BDR
La comunicazione verso il resto della rete è demandata al DR
(riducendo così il traffico OSPF sulla rete) e gli altri router si
affidano agli aggiornamenti (LSA) che riceveranno da esso
N.B. Tutti i pacchetti OSPF (ad eccezione di quelli Hello che
sono usati per scoprire i vicini) sono scambiati tra router
adiacenti, quindi attraversano un solo hop IP prima di essere
processati.
36
Funzionalità DR/BDR (2/2)
DR
R
BDR
R
R
R
Se un router che non è il DR deve inviare un update:
Invia LSA a AllDRouter (224.0.0.6)
Il DR propaga l'informazione a tutt gli altri router:
Invia LSA a AllSPFrouter (224.0.0.5)
I router inviano le conferme al DR:
Invia LSU_ACK a AllDRouter
Se DR non riceve ACK da un router re-invia LSA in modo unicast
DR e BDR hanno le stesse info sui neighbor per cui se BDR può
prendere il posto del DR in modo semplice.
37
Processo di elezione del DR
Chiamiamo X il router che effettua il calcolo
X crea una lista (L) con tutti i neighbor che sono nello stato almeno 2-way e che
sono elegibili a DR (scarta quelli con priorità uguale a zero) più se stesso (se
considerato elegibile)
L_DR = sottoinsieme di L, tutti i Router che hanno dichiarato se stessi DR (nei
pacchetti Hello)
L_BDR = sottoinsieme di L, tutti i Router che hanno dichiarato se stessi BDR ma
non DR (nei pacchetti Hello)
L_noDR = sottoinsieme di L, tutti i router che non hanno dichiarato se stessi né
DR né BDR
38
Processo di elezione del DR
Step 1
Step 2
Step 3
Memorizza valore attuale DR e BDR
(I_DR, I_BDR)
Calcolo BDR: prendi da L_BDR il
router con la priorità più alta, in caso
di parità quello con il router id più
alto. Se L_BDR è vuota prendi
L_noDR ed effettua lo stesso processo
di scelta
Calcolo DR: prendi da L_DR il router
con la priorità più alta, in caso di
parità quello con il router id più alto.
Se L_DR è vuota scegli come DR il
BDR appena eletto
39
Processo di elezione del DR
Step 4
Se X è il nuovo eletto DR/BDR
oppure non è più il DR/BDR esegui
novamente i passi 2 e 3 e poi vai al 5.
Step 5
Cambia stato all'interfaccia in
accordo ai risultati ottenuti (DR,
BDR, DRother)
Step 6
Se interfaccia NBA......
Step 7
Se è cambiato il DR o il BDR invoca
l'evento AdjOK? su tutti i neighbor
nello stato da 2-way in su
40
Esempio di elezione di DR/BDR
10.0.0.2
10.0.0.1
R1
P =1
.1
R2
10.0.0.3
R3
P =1
.2
P =1
.3
192.168.1.0 mask 255.255.255.0
Hello packet inviati a 224.0.0.5
Router id= 10.0.0.1
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = { }
Router id= 10.0.0.2
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = { }
Router id= 10.0.0.3
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = { }
Router id= 10.0.0.1
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = {10.0.0.2,
10.0.0.3 }
Router id= 10.0.0.2
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = { 10.0.0.1,
10.0.0.3}
Router id= 10.0.0.3
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 0.0.0.0
BDR = 0.0.0.0
Neighbor = {10.0.0.1,
10.0.0.2 }
41
A questo punto lo stato dei neighbor passa a 2-way (comunicazione bidirezionale)
Esempio di elezione di DR/BDR
10.0.0.2
10.0.0.1
R1
P =1
.1
R2
10.0.0.3
P =1
.2
R3
P =1
.3
192.168.1.0 mask 255.255.255.0
Il processo di gestione delle interfacce incomincia il calcolo del DR/BDR
Step 1: I_DR=I_BDR = 0.0.0.0
L_DR = {}. L_BDR = {}. L_noDR =
{10.0.0.1,10.0.0.2, 10.0.0.3}
Step 1: I_DR=I_BDR = 0.0.0.0
L_DR = {}. L_BDR = {}. L_noDR =
{10.0.0.1,10.0.0.2, 10.0.0.3}
Step 1: I_DR=I_BDR = 0.0.0.0
L_DR = {}. L_BDR = {}. L_noDR =
{10.0.0.1,10.0.0.2, 10.0.0.3}
Step 2: L_BDR = {} => BDR = max
L_noDR = 10.0.0.3
Step 2: L_BDR = {} => BDR = max
L_noDR = 10.0.0.3
Step 2: L_BDR = {} => BDR = max
L_noDR = 10.0.0.3
Step 3: L_DR = {} => DR =
BDR=10.0.0.3
Step 3: L_DR = {} => DR =
BDR=10.0.0.3
Step 3: L_DR = {} => DR =
BDR=10.0.0.3
Step 4:
Step 5: stato Intf = Drother
Step 6: ..
Step 7: invoca AdjOK ?
Step 4:
Step 5: stato Intf = Drother
Step 6: ..
Step 7: invoca AdjOK ?
Step 4: R3 è eletto DR
Step 2: L_DR ={10.0.0.3}, L_BDR =
{}, L_noDR = {10.0.0.1.10.0.0.2}
BDR = max L_noDR = {10.0.02}
Step 3: DR = max L_DR = {10.0.0.3}
Step 5: stato Intf = DR
Step 6: ..
Step 7: invoca AdjOK ?
42
Esempio di elezione di DR/BDR
10.0.0.2
10.0.0.1
R1
P =1
.1
R2
10.0.0.3
P =1
.2
R3
P =1
.3
192.168.1.0 mask 255.255.255.0
Hello packet inviati a 224.0.0.5
Router id= 10.0.0.1
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR =1 0.0.0.3
Neighbor = {10.0.0.2,
10.0.0.3 }
Router id= 10.0.0.2
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR = 10.0.0.3
Neighbor = { 10.0.0.1,
10.0.0.3}
Router id= 10.0.0.3
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR = 10.0.0.2
Neighbor = {10.0.0.1,
10.0.0.2 }
A questo punto il router genera un evento NeighborChange (si è aggiunto un router che si dichiara DR) che
causa il ricalcolo del DR/BDR
43
Esempio di elezione di DR/BDR
10.0.0.2
10.0.0.1
R1
P =1
.1
R2
10.0.0.3
P =1
.2
R3
P =1
.3
192.168.1.0 mask 255.255.255.0
Il processo di gestione delle interfacce incomincia il calcolo del DR/BDR
Step 1: I_DR=I_BDR = 10.0.0.3
L_DR = {10.0.0.3}. L_BDR = {}.
L_noDR = {10.0.0.1,10.0.0.2}
Step 1: I_DR=I_BDR =10.0.0.3
L_DR = {10.0.0.3}. L_BDR = {}.
L_noDR = {10.0.0.1,10.0.0.2}
Step 1: I_DR=10.0.0.3 I_BDR = 10.0.0.2
L_DR = {10.0.0.3}. L_BDR = {}. L_noDR =
{10.0.0.1,10.0.0.2}
Step 2: L_BDR = {} => BDR = max
L_noDR = 10.0.0.2
Step 2: L_BDR = {} => BDR = max
L_noDR = 10.0.0.2
Step 2: L_BDR = {} => BDR = max L_noDR =
10.0.0.2
Step 3: L_DR = {10.0.0.3} => DR =
10.0.0.3
Step 3: L_DR = {10.0.0.3} => DR =
10.0.0.3
Step 3: DR =max L_DR =10.0.0.3
Step 4: R3 è eletto DR
Step 4:
Step 5: stato Intf = Drother
Step 6: ..
Step 7: invoca AdjOK ?
Step 4: R2 elettoBDR
Step 2: L_DR = {10.0.0.3}, L_BDR =
{10.0.0.2}
BDR = max L_BDR = {10.0.0.2}
Step 2: L_DR ={10.0.0.3}, L_BDR = {},
L_noDR = {10.0.0.1.10.0.0.2}
BDR = max L_noDR = {10.0.02}
Step 3: DR = max L_DR = {10.0.0.3}
Step3: DR = max L_DR = 10.0.0.3
Step 5: stato Intf = Backup
Step 6: ..
Step 7: invoca AdjOK ?
Step 5: stato Intf = DR
Step 6: ..
Step 7: invoca AdjOK ?
44
Esempio di elezione di DR/BDR
10.0.0.2
10.0.0.1
R1
P =1
.1
R2
10.0.0.3
P =1
.2
R3
P =1
.3
192.168.1.0 mask 255.255.255.0
Hello packet inviati a 224.0.0.5
Router id= 10.0.0.1
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR =1 0.0.0.2
Neighbor = {10.0.0.2,
10.0.0.3 }
Router id= 10.0.0.2
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR = 10.0.0.2
Neighbor = { 10.0.0.1,
10.0.0.3}
Router id= 10.0.0.3
Area = 0.0.0.0
Hello Int = 10
DeadInt = 40
Option = ...
Priority = 1
DR = 10.0.0.3
BDR = 10.0.0.2
Neighbor = {10.0.0.1,
10.0.0.2 }
A questo punto il router genera un evento NeighborChange (si è aggiunto un router che si dichiara BDR) che
causa il ricalcolo del DR/BDR, che porterà però allo stesso risultato.
45

Download Report