Routing dinamico:

(1)

RETI DI CALCOLATORI II

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Prof. MARIO BALDI Facoltà di Ingegneria

Politecnico di Torino Prof. PIER LUCA MONTESSORO

Facoltà di Ingegneria Università degli Studi di Udine

Prof. MARIO BALDI Facoltà di Ingegneria

Politecnico di Torino

© 2003 Pier Luca Montessoro – Mario Baldi (si veda la nota a pagina 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà degli autori prof. Pier Luca Montessoro, Università degli Studi di Udine, e prof. Mario Baldi, Politecnico di Torino.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Routing dinamico:

OSPF Routing

Routing dinamico: dinamico:

OSPF OSPF

OSPF

Introduzione a Open Shortest Path First

OSPF

Introduzione a Open Shortest Path First

Generalità Generalità

Î Basato sull’algoritmo link state ÎBasato sull’algoritmo link state

Æ Difficile implementazione ÆDifficile implementazione Î Specificato dall’IETF ÎSpecificato dall’IETF

Æ Pubblico dominio ÆPubblico dominio

Î Versione 2:

RFC 2328/STD 54 (1998)

Î Versione 2:

RFC 2328/STD 54 (1998) Æ Versione 1: RFC 1131 (1989) ÆVersione 1: RFC 1131 (1989)

Terminologia Terminologia

Area 0 Area 0

Area 5 Area 5

Area 4 Area 4 Backbone router

Backbone router Backbone areaBackbone area

AS boundary router AS

ASboundary routerboundary router border routerAreaAreaArea border router border router R2R2 R7R7

Area 3 Area 3 R4R4 R8R8

R9R9

R3R3

Area 2 Area 2 R6R6

R1R1 Area 1 Area 1 R5R5

D1D1

(2)

Gerarchia nel routing Gerarchia nel routing

Î Il dominio di routing è suddiviso

in aree

Î

Il dominio di routing è suddiviso in aree

Î Identificate da numero di 4 byte Î

Identificate da numero di 4 byte

Æ Notazione decimale puntata ÆNotazione decimale puntata

Gerarchia nel routing Gerarchia nel routing

Î Le aree contengono un gruppo

di reti (destinazioni) contigue

Î

Le aree contengono un gruppo di reti (destinazioni) contigue

Æ Un pacchetto può passare da una qualsiasi rete ad un’altra senza uscire dall’area ÆUn pacchetto può passare

da una qualsiasi rete ad un’altra senza uscire dall’area

Terminologia

Backbone areaBackbone area

Area 0 Area 0

Area 5 Area 5

Area 4 Area 4 R2

R2 R7R7

Area 3 Area 3 R4R4 R8R8

R9R9

R3R3

Area 2 Area 2 R6R6

R1R1 Area 1 Area 1 R5R5

D1D1

Particolarmente importante Particolarmente importante

Numero 0 Numero 0 Backbone area Backbone area

Terminologia

area di transito tra le altre aree area di transito tra le altre aree

Terminologia Terminologia

Backbone router Backbone router

Area 0 Area 0

Area 5 Area 5

Area 4 Area 4 R2R2 R7R7

Area 3 Area 3 R4R4 R8R8

R9R9

R3R3

Area 2 Area 2 R6R6

R1R1 Area 1 Area 1 R5R5

D1D1 Backbone routerBackbone router

Terminologia

router che è nel backbone router che è nel backbone

Internal router Internal router

router che fa parte

di una sola area router che fa parte

di una sola area

(3)

Terminologia Terminologia

R3R3

Area 2 Area 2 R6R6

R1R1

border routerAreaAreaArea border router border router

Area 0 Area 0

Area 5 Area 5

Area 4 Area 4 R2R2 R7R7

Area 3 Area 3 R4R4 R8R8

R9R9 Area 1

Area 1 R5R5

D1D1

Area border router (ABR) Area border router (ABR)

Terminologia

router che si affaccia su più aree router che si affaccia su più aree

Deve affacciarsi anche sulla backbone area

Esegue una copia dell’algoritmo per ogni area

Si occupa della propagazione di informazioni tra aree

Autonomous System (AS) Autonomous System (AS)

Terminologia

dominio di routing dominio di routing

Terminologia Terminologia

AS boundary router AS

ASboundary routerboundary router

Area 0 Area 0

Area 5 Area 5

Area 4 Area 4 R2

R2 R7R7

Area 3 Area 3 R4R4 R8R8

R9R9

R3R3

Area 2 Area 2 R6R6

R1R1 Area 1 Area 1 R5R5

D1D1

AS boundary router (ASBR) AS boundary router (ASBR)

Collegato a router non OSPF Collegato a router non OSPF

Dotato di route statiche Dotato di route statiche

Terminologia

diffonde informazioni sull’esterno del dominio di routing

Informazioni topologiche Informazioni topologiche

Î Sofisticato meccanismo di propagazione: selective flooding Î Sofisticato meccanismo di

propagazione:selective flooding Î LSA (Link State Advertisement)

contengono le informazioni topologiche

Î LSA (Link State Advertisement) contengono le informazioni topologiche

(4)

Tutti i router di un’area dispongono delle stesse informazioni

Æ Hanno la stessa mappa della rete

ÆHanno la stessa mappa della rete

Propagazione interna Propagazione interna

Gli LSA generati da un router all’interno di un’area sono

propagati a tutti i router dell’area Gli LSA generati da un router all’interno di un’area sono

propagati a tutti i router dell’area

Area singola Area singola

Un dominio di routing di piccole dimensioni può essere organizzato

in un’unica area

Un dominio di routing di piccole dimensioni può essere organizzato

in un’unica area

Classe degli apparati Classe degli apparati Complessità dei collegamenti Complessità dei collegamenti Da 20 a 50 router a seconda di Da 20 a 50 router a seconda di

Area singola Area singola

Un dominio di routing di piccole dimensioni può essere organizzato

in un’unica area

Un dominio di routing di piccole dimensioni può essere organizzato

in un’unica area

Sconsigliabile se si prevede

espansione futura Sconsigliabile se si prevede

espansione futura

Informazioni sull’esterno consentono agli internal router di scegliere un punto di uscita dall’area ottimale

Propagazione interna Propagazione interna

Un area border router diffonde in un’area un riassunto delle informazioni raccolte nelle altre aree su cui si affaccia

Î Comunicare Î Comunicare

Minor quantità di informazioni da Minor quantità di informazioni da

Î Memorizzare

Î Memorizzare

Î Elaborare (~ E log N) Î Elaborare (~ E log N)

Minore dimensione delle tabelle di routing

Scalabilità Scalabilit Scalabilità à Benefici del riassumere Benefici del riassumere

Î Esistenza di router e collegamenti in un’area è irrilevante all’esterno Î Esistenza di router e collegamenti

in un’area è irrilevante all’esterno

Eliminazione di dettaglio

Eliminazione di dettaglio Benefici del riassumere Benefici del riassumere

Î Riduzione delle tabelle di routing dei router esterni

Î Riduzione delle tabelle di routing dei router esterni

Aggregazione di indirizzi Aggregazione di indirizzi

(5)

Basata su address summary

Basata su address summary Aggregazione di indirizzi Aggregazione di indirizzi

10.1.1.0/24 10.1.2.0/24 10.1.8.0/24 10.1.11.0/24 10.1.1.0/24 10.1.2.0/24 10.1.8.0/24 10.1.11.0/24

Esempio:

Può essere aggregato come 10.1.0.0/16

Configurata esplicitamente (non automatica) Configurata esplicitamente

(non automatica)

Effetti del riassumere Effetti del riassumere

Topologia di rete Topologia di rete

Area 1 Area 1 R1R1

R2R2 D1D1

R4R4 D3D3

D2D2

D4 R3 D4 R3

D5D5

Area 0 Area 0 R5R5 R8R8

R9R9 R10R10 D7D7

Area 5 Area 5 R11 R11 R12R12 D8D8

D9 D9

Area 2 Area 2 R7R7

R6R6 D6D6

Effetti del riassumere Effetti del riassumere

Visione della rete da parte dei router dell’area 1Visione della rete da parte dei router dell’area 1

Area 1 Area 1 R5R5 R2R2

D1 D1

R4R4 D3D3

D2D2

D4D4 R3R3

D5D5

D7D7 D8D8 D9D9 D6D6

Area 0 Area 0 R5R5

R2R2 D1D1

R8R8 D3D3

D2D2 D4D4

R9R9 R10R10 D5D5

D7D7 D6D6

D8D8 D9D9

Effetti del riassumere Effetti del riassumere

Visione della rete da parte dei backbone routerVisione della rete da parte dei backbone router

Inoltro dei pacchetti Inoltro dei pacchetti

Da D2 a D9 Da D2 a D9

Area 1 Area 1 R1R1

R2R2 D1D1

R4R4 D3D3 R3R3 D4D4

D5D5

Area 0 Area 0 R5

R5 R8R8 R9 R9 R10R10 D7D7

Area 5 Area 5 R11R11 R12R12

D8D8 Area 2

Area 2 R7R7

R6R6 D6 D6

D2D2 D9D9

(6)

Area 1 R1R1

R2R2 D1D1

R4R4 D3D3 R3R3 D4D4

D5D5

Area 0 Area 0 R5R5 R8R8

R9R9 R10R10 D7D7

Area 5 Area 5 R11R11 R12R12

D8D8 Area 2

Area 2 R7R7

R6R6 D6D6 D2

D2 D9D9

Inoltro dei pacchetti Inoltro dei pacchetti

Il pacchetto è consegnato al default gateway R2 Il pacchetto è consegnato

al default gateway R2

Inoltro dei pacchetti Inoltro dei pacchetti

La visione della rete di R2 gli permette di sapere che D9 è raggiungibile a valle di R5

Area 1 Area 1 R5R5 R2R2

D1D1

R4R4 D3D3

D2 D2

D4D4 R3R3

D5D5

D7D7 D8D8 D6D6 D9D9

Area 0 R5R5

R2R2 D1D1

R8R8 D3

D3 D2D2 D4D4

R9R9 R10R10 D5

D5

D7D7 D6D6

D8D8 D9D9

Inoltro dei pacchetti Inoltro dei pacchetti

R5 conosce la topologia della backbone area e sa che D9 è raggiungibile a valle di R10

R10 R11 R12 D8

D9

D3 D4 D5

D6 D1 D2

D7

Inoltro dei pacchetti Inoltro dei pacchetti

R10 conoscendo i dettagli dell’area 5 inoltra il pacchetto alla destinazioneR10 conoscendo i dettagli dell’area 5 inoltra il pacchetto alla destinazione

I pacchetti destinati ad un’area diversa da quella del mittente transitano attraverso l’area backbone

Ruolo dell’area backbone Ruolo dell’area backbone

Le informazioni di routing raccolte in ogni area

raggiungono le altre attraverso l’area backbone

Le informazioni di routing raccolte in ogni area

raggiungono le altre attraverso l’area backbone

Il mancato funzionamento del backbone compromette l’intero dominio di routing

Criticità dell’area backbone Criticità dell’area backbone

Collegamenti e router affidabili e veloci

Le prestazioni del backbone influenzano quelle dell’intero dominio di routing

(7)

Equal-cost multipath routing Equal-cost multipath routing

Î Più next hop per la stessa destinazione

Î Più next hop per la stessa destinazione

Î Non è detto che il router mantenga tutte le possibili route aventi stesso costo Î Non è detto che il router

mantenga tutte le possibili route aventi stesso costo

Stub Area Stub Area

Î Solo informazioni sull’interno del dominio di routing

Î Solo informazioni sull’interno del dominio di routing

Î Default route (0.0.0.0/0) Î Default route (0.0.0.0/0)

Non serve propagare informazioni esterne Non serve propagare informazioni esterne

Unico punto di uscita Unico punto di uscita Singolo area border router Singolo area border router

Partizioni di area Partizioni di area

A seguito di guasti due o più reti risultano non più contigue A seguito di guasti due o più reti

risultano non più contigue

Area 1 Area 1 Area 0 – Backbone area Area 0 – Backbone area

D51D51 D52D52 R1R1 R2R2

R3R3

Area 1 Area 0 – Backbone area Area 0 – Backbone area

D51D51 D52D52 R1R1 R2R2

R3R3

Partizioni e aggregazione Partizioni e aggregazione

Se R1 ed R2 non aggregano D51 e D52

non ci sono problemi

Se R1 ed R2 non aggregano D51 e D52 non ci sono problemi

D52D52 è èquiqui D51

èD51 èquiqui

Area 1 Area 1 Area 0 – Backbone area Area 0 – Backbone area

D51D51 D52D52 R1R1 R2R2

R3R3

Partizioni e aggregazione Partizioni e aggregazione

Se R1 ed R2 aggregano D51 e D52

in un unico annuncio di D5 Se R1 ed R2 aggregano D51 e D52

in un unico annuncio di D5

D5 D5 èè

quiqui D5 èD5 è

qui qui

Partizioni e aggregazione Partizioni e aggregazione

Secondo i backbone router D5 (D51 e D52) sono raggiungibili indifferentemente tramite R1 o R2

Area 0 – Backbone area Area 0 – Backbone area R1R1 R2R2

D5D5 D5D5

R3R3

Se R3 riceve un pacchetto per D52 ...

(8)

Area 1 Area 0 – Backbone area Area 0 – Backbone area

D51D51 D52D52 R1R1 R2R2

R3R3

Partizioni e aggregazione Partizioni e aggregazione

... lo inoltra a R1 che non lo può recapitare... lo inoltra a R1 che non lo può recapitare

Partizioni di area: soluzione Partizioni di area: soluzione

Î Propagazione di maggior quantità di informazioni Î Propagazione di maggior

quantità di informazioni Î Limitata scalabilità Î Limitata scalabilità

Riconfigurare l’aggregazione sugli area border router Riconfigurare l’aggregazione

sugli area border router Intervento manuale

Intervento manuale Rinuncia ai benefici Rinuncia ai benefici

Elevato numero di collegamenti Elevato numero di collegamenti

Svariati percorsi alternativi tra ogni coppia di destinazioniSvariati percorsi alternativi tra ogni coppia di destinazioni

Partizioni di area: prevenzione Partizioni di area: prevenzione

Assicurarsi che le aree siano densamente connesse Assicurarsi che le aree siano

densamente connesse

Î Hello ÎHello

Î Database Description ÎDatabase Description Î Link State Request ÎLink State Request Î Link State Update ÎLink State Update

Î Link State Acknowledgement ÎLink State Acknowledgement

I pacchetti OSPF I pacchetti OSPF

Imbustati in IP Imbustati in IP

Intestazione comuneIntestazione comune

Campi di lunghezza fissa Campi di lunghezza fissa No estensioni ignorabili No estensioni ignorabili

Î Codifica compatta Î Codifica compatta Î Elaborazione veloce Î Elaborazione veloce Î Maggiore rigidità all’evoluzione Î Maggiore rigidità all’evoluzione

Formato dei pacchetti OSPF

Formato dei pacchetti OSPF Intestazione OSPF Intestazione OSPF

1 byte

1 byte 1 byte1 byte 1 byte1 byte 1 byte1 byte

Authentication data Authentication data Checksum

Checksum

Area ID Area ID Router ID Router ID

Packet lenght Packet lenght

Authentic. type Authentic. type Version

Version Packet Type Packet

Type

(9)

Î Normalmente uno dei propri indirizzi IP

Î Normalmente uno dei propri indirizzi IP

Identificativo del router Identificativo del router Ogni router sceglie un identificativo univoco Ogni router sceglie un identificativo univoco

Î Mai cambiato Î Mai cambiato

Î Identificativo del router che genera il pacchetto

Î Identificativo del router che genera il pacchetto

Router ID Router ID

Solo per schemi semplici Solo per schemi semplici

Autenticazione Autenticazione

Authentication data Authentication data

Authentic. type Authentic. type

Authentication data

(64 bit)

Authentication data

(64 bit)

Insufficiente per schemi complessi Insufficiente per schemi complessi

Autenticazione Autenticazione

Authentication data Authentication data

Authentic. type Authentic. type

Authentication data

(64 bit)

Authentication data

(64 bit)

Ad esempio, chiave pubblica Ad esempio, chiave pubblica

Autenticazione Autenticazione

Authentication type Authentication type

Null authentication

Null authentication Previsti 3 schemi Previsti 3 schemi

Simple password authentication Simple password authentication Cryptographic authentication Cryptographic authentication Altri schemi potranno

essere definiti Altri schemi potranno

essere definiti

Neighbor greeting Neighbor greeting

Î Invio periodico di pacchetti hello su ogni interfaccia

ÎInvio periodico di pacchetti hello su ogni interfaccia

Î Scoprire l’identità dei vicini ÎScoprire l’identità dei vicini

Neighbor greeting Neighbor greeting

Î Realizzare meccanismi di elezione ÎRealizzare meccanismi di elezione

Æ Designated router e Backup designated router

ÆDesignated router e Backup designated router

Æ Master e slave ÆMaster e slave

(10)

(Link State Advertisement)

LSA LSA

(Link State Advertisement)

Vari LSA in un pacchetto link state update

Inviati in modo affidabile Inviati in modo affidabile

Conferme di ricezione in pacchetto link state acknowledgment

Informazioni topologiche: LSA Informazioni topologiche: LSA

Memorizzato nella base dati Memorizzato nella base dati

Se un LSA non è già stato ricevuto viene

Tranne quello da cui lo si è ricevuto Tranne quello da cui lo si è ricevuto

Selective flooding Selective flooding

Inviato a tutti i vicini Inviato a tutti i vicini

Problema: identificare univocamente ogni LSA

Non banale Non banale

Î Identificativo del router (advertising router) Î Identificativo del router

(advertising router)

Identificazione degli LSA Identificazione degli LSA Ogni LSA è generato da un router Ogni LSA è generato da un router

Î Numero di sequenza Î Numero di sequenza

Nuove copie sono generate a seguito di cambiamenti

topologici e periodicamente

Nuove copie sono generate a seguito di cambiamenti

topologici e periodicamente

Elevata complessità Elevata complessità Æ Molte informazioni ÆMolte informazioni Æ Molti timer

ÆMolti timer

Propagazione di LSA su LAN Propagazione di LSA su LAN

Un LSA inviato deve essere ricevuto da tutti i router della LANUn LSA inviato deve essere ricevuto da tutti i router della LAN

Problema: gestire le conferme Problema: gestire le conferme

Æ … e le ritrasmissioni Æ… e le ritrasmissioni

Designated Router (DR) Designated Router (DR)

Propagazione di LSA su LAN Propagazione di LSA su LAN

Soluzione:

delegare un solo router

Soluzione:

delegare un solo router

Propagazione di LSA su LAN Propagazione di LSA su LAN Distribuisce LSA

Distribuisce LSA

Î Timer di ritrasmissione Î Timer di ritrasmissione

Raccoglie conferme di ricezione Raccoglie conferme di ricezione

Grossa mole di informazioni raccolte nel tempo

Designated Router (DR) Designated Router (DR)

Î Ritrasmissioni Î Ritrasmissioni

(11)

Criticità del

designated router Criticità del

designated router

Solo DR sa quali router hanno ricevuto gli LSA inviati sulla LAN Solo DR sa quali router hanno ricevuto gli LSA inviati sulla LAN Malfunzionamento improvviso Æ perdita informazioni

Malfunzionamento improvviso Æ perdita informazioni

Î Molto tempo Î Molto tempo Î Elevato traffico Î Elevato traffico

Sostituzione Æ scambio grossa mole di dati Sostituzione Æ scambio grossa

mole di dati Criticità del

designated router Criticità del

designated router

Backup designated router Backup designated router

Î Basato su identificativo Î Basato su identificativo

Ascolta i messaggi diretti al DR Ascolta i messaggi diretti al DR Memorizza le stesse informazioni Memorizza le stesse informazioni

DR e backup DR non decadono DR e backup DR non decadono Eletto nello stesso procedimento elettivo che identifica il DR

Eletto nello stesso procedimento elettivo che identifica il DR

RR

B-DRB-DR DRDR

Propagazione di LSA su LAN Propagazione di LSA su LAN

Ma allora, come funziona?

Î LSA da propagare è inviato ad un indirizzo riservato ai DR Î LSA da propagare è inviato ad

un indirizzo riservato ai DR Î Link state update in multicast Î Link state update in multicast

Æ AllDrouters ÆAllDrouters

RR

Propagazione di LSA su LAN Propagazione di LSA su LAN

Î Il DR invia l’LSA ad un indirizzo multicast riservato a tutti i router Î Il DR invia l’LSA ad un indirizzo

multicast riservato a tutti i router Æ AllSPFrouters

ÆAllSPFrouters

RR

Propagazione di LSA su LAN Propagazione di LSA su LAN

Î Inviata all’indirizzo AllDrouters Î Inviata all’indirizzo AllDrouters

Î Ogni router invia una conferma di ricezione (acknowledgment)

Î Ogni router invia una conferma di ricezione (acknowledgment)

Æ Il B-DR mantiene allineate le proprie informazioni ÆIl B-DR mantiene allineate

le proprie informazioni

(12)

RR

B-DR B-DR DRDR

Propagazione di LSA su LAN Propagazione di LSA su LAN

Î Il DR esegue ritrasmissioni

selettive verso i router da cui non riceve conferme

Î Il DR esegue ritrasmissioni

selettive verso i router da cui non riceve conferme

Æ Un timer per ogni router ÆUn timer per ogni router

Sincronizzazione della base dati Sincronizzazione della base dati

Î Copia più recente di ogni LSA propagato nella loro area Î Copia più recente di ogni LSA

propagato nella loro area

Tutti i router di un’area hanno la stessa base dati

Sincronizzazione della base dati Sincronizzazione della base dati

Î Accensione Î Accensione

Due router che scoprono di essre adiacenti sincronizzano le proprie basi dati

Î Riparazione collegamento Î Riparazione collegamento

Sincronizzazione della base dati Sincronizzazione della base dati

Î Master Î Master

Identificazione (processo di elezione basato su identificativo) Identificazione (processo di elezione basato su identificativo)

Î Slave

Î Slave

Trasmissione di pacchetti

Database Description (DD)

Trasmissione di pacchetti

Database Description (DD)

Il master comincia il processo Il master comincia il processo

Pacchetti database description Pacchetti database description

Î Solo informazioni necessarie ad identificarli

Î Solo informazioni necessarie ad identificarli

Î Intestazione Î Intestazione

Numero di sequenza Numero di sequenza

Contengono un elenco di LSA Contengono un elenco di LSA

Non ha alcuni LSA elencati nei pacchetti DD Non ha alcuni LSA elencati

nei pacchetti DD

Se un router si accorge che:

Allineamento delle basi dati Allineamento delle basi dati

ne richiede la trasmissione mediante pacchetto

link state request ne richiede la trasmissione

mediante pacchetto link state request

(13)

L’interlocutore non ha elencato alcuni LSAL’interlocutore non ha elencato alcuni LSA

Se un router si accorge che:

Allineamento delle basi dati Allineamento delle basi dati

glieli invia mediante pacchetto link state updateglieli invia mediante pacchetto link state update

Trasmissione LSA Trasmissione LSA

Link state acknowledgment Link state acknowledgment

Database description Database description

Link state request Link state request

Le sole intestazioni di LSA sono trasmesse in pacchetti Le sole intestazioni di LSA sono

trasmesse in pacchetti Gli LSA sono trasmessi in pacchetti link state update Gli LSA sono trasmessi in pacchetti link state update

Intestazione dell’LSA (LSA header)

1 byte 1 byte 1 byte

1 byte 1 byte1 byte 1 byte1 byte

LS Checksum

LS Checksum LengthLength Link state sequence number Link state sequence number

Advertising router Advertising router

Link state ID Link state ID Link state age

Link state age ResRes EETT LS TypeLS Type

Indentificativo dell’LSA Indentificativo dell’LSA

Î Identifica l’oggetto descritto Î Identifica l’oggetto descritto Î Semantica dipende dal tipo di LSA

(5 tipi)

Î Semantica dipende dal tipo di LSA (5 tipi)

Link State ID Link State ID

Indentificativo dell’LSA Indentificativo dell’LSA

Î Router che ha generato il LSA Î Router che ha generato il LSA

Advertising Router Advertising Router

LSA sequence number LSA sequence number

Î Aggiornato durante il selective flooding

Î Aggiornato durante il selective flooding

Il tempo in secondi da quando il LSA è stato generato

Î Aggiornato nella base dati Î Aggiornato nella base dati

Link state age

(14)

Eliminazione dopo 3600s Eliminazione dopo 3600s

Link state age Link state age

Nuova copia generata ogni 1800s Nuova copia generata ogni 1800s

Î Router links-1 Î Router links-1 Î Network links-2 Î Network links-2

Î Network summary link-3 Î Network summary link-3

Î AS boundary router summary link-4 Î AS boundary router summary link-4 Î AS external link-5

Î AS external link-5

LSA type

Descrizione di aspetti diversi

Î Classico link state Î Classico link state Î Informazioni su Î Informazioni su

LSA di tipo 1

Router links advertisement LSA di tipo 1

Router links advertisement

Æ Router adiacenti ÆRouter adiacenti Æ Reti (LIS) collegate ÆReti (LIS) collegate

Î Propagato solo nell’area in cui è stato generato

Î Propagato solo nell’area in cui è stato generato

Î Descrive una LAN Î Descrive una LAN

LSA di tipo 2

Network links advertisement LSA di tipo 2

Network links advertisement

Î Propagato solo nell’area in cui è stato generato

Î Propagato solo nell’area in cui è stato generato

Î Elenco dei router presenti sulla LAN

Î Elenco dei router presenti sulla LAN

Î Generato dal DR di una LAN Î Generato dal DR di una LAN

LSA di tipo 2

Network links advertisement LSA di tipo 2

Network links advertisement

Æ Equivalente al link state generato dallo pseudo-nodo

ÆEquivalente al link state generato dallo pseudo-nodo

Link state e LAN Link state e LAN

BB

AA XX CC

DD Y

Y ZZ

(15)

Î Magliatura completa Î Magliatura completa

Link state e LAN Descrizione “normale”

Link state e LAN

Descrizione “normale”

Î Complessità SPF: E log N Î Complessità SPF: E log N

BB AA

CC DD

X X

YY ZZ

Î Pseudo-nodo Æ stella Î Pseudo-nodo Æ stella

Î Minor numero di collegamenti (E) Î Minor numero di collegamenti (E)

P-NP-N BB AA

CC DD

X X

YY ZZ

Link state e LAN Descrizione a bassa complessità Link state e LAN

Descrizione a bassa complessità

Î Descrizione riassuntiva di un’area Î Descrizione riassuntiva di un’area

LSA di tipo 3

Network summary link advertisement

LSA di tipo 3

Network summary link advertisement

Î Propagato solo nell’area in cui è stato generato

Î Propagato solo nell’area in cui è stato generato

Î Generato da un area border router nelle altre sue aree Î Generato da un area border

router nelle altre sue aree

Descrizione tramite LSA di tipo 3

Area 1 Area 1 R1R1

R2 R2 D1 D1

R4R4 D3

D3 D2 D2

D4D4 R3R3

D5D5

Area 0 Area 0 R5

R5 R8R8 R9 R9 R10R10 D7D7

Area 5 Area 5 R11R11 R12R12 D8D8

D9D9

Area 2 Area 2 R7R7

R6R6 D6D6

LSA di tipo 3

Descrizione di un’area all’esterno LSA di tipo 3

Descrizione di un’area all’esterno

Area 1 Area 1 R2R2 D1D1

R4R4 D3D3

D2D2

D4D4 R3R3

D5D5 R5R5

Grazie agli LSA di tipo 1 e 2 propagati nell’area 1 R5 ne apprende tutti i dettagli topologici

R5 genera LSA di tipo 3 nell’area 0 e nell’area 2 per descrivere l’area 1R5 genera LSA di tipo 3 nell’area 0 e nell’area 2 per descrivere l’area 1

Area 0 Area 0 R5R5

D3 D2 D3 D4 D2 D4 D5D5 Area 2 Area 2

LSA di tipo 3

Descrizione di un’area all’esterno LSA di tipo 3

Descrizione di un’area all’esterno

(16)

Dagli LSA di tipo 1 e 2 propagati nell’area 0 e nell’area 2 R5 apprende

tutti i dettagli topologici di queste aree

Dagli LSA di tipo 1 e 2 propagati nell’area 0 e nell’area 2 R5 apprende

tutti i dettagli topologici di queste aree

Area 0 Area 0 R5R5 R8R8

R9R9 R10R10 D7D7 Area 2

Area 2 R7R7

R6R6 D6D6

LSA di tipo 3

Descrizione dell’esterno in un’area LSA di tipo 3

Descrizione dell’esterno in un’area

Dagli LSA di tipo 3 propagati nell’area 0 R5 apprende

informazioni sulle destinazioni delle altre aree

Dagli LSA di tipo 3 propagati nell’area 0 R5 apprende

informazioni sulle destinazioni delle altre aree

Area 0 Area 0 R5R5 R10R10

D8D8 D9D9

LSA di tipo 3

Descrizione dell’esterno in un’area LSA di tipo 3

R5 genera LSA di tipo 3 nell’area 1 per descrivere le destinazioni delle

altre aree

R5 genera LSA di tipo 3 nell’area 1 per descrivere le destinazioni delle

altre aree

Area 1 Area 1 R5R5

D7D7 D8D8 D9D9 D6D6

LSA di tipo 3

Descrizione dell’esterno in un’area LSA di tipo 3

Î Distanza da R5 alla destinazione Î Distanza da R5 alla destinazione Î Ogni LSA riguarda una singola

destinazione (LIS) interna all’area 1 Î Ogni LSA riguarda una singola

destinazione (LIS) interna all’area 1

Area 0 Area 0 R5R5

D3D3 D2D2 D4D4 D5D5

Area 2 Area 2 Area 1

Area 1 R5R5

D7D7 D8D8 D9D9 D6D6

LSA di tipo 3

Network summary link advertisement

LSA di tipo 3

Network summary link advertisement

Î Descrizione degli AS boundary router di un’area

Î Descrizione degli AS boundary router di un’area

LSA di tipo 4

AS boundary router summary link advertisement

LSA di tipo 4

AS boundary router summary link advertisement

Î Generato da un area border router nelle altre sue aree

Î Generato da un area border router nelle altre sue aree

Î Propagato solo nell’area in cui è stato generato

Î Propagato solo nell’area in cui è stato generato

Area 0 Area 0 R5R5

R2R2 Area 2 Area 2

Î Descrizione una destinazione (LIS) esterna al dominio di routing Î Descrizione una destinazione (LIS)

esterna al dominio di routing

LSA di tipo 5

AS external link advertisement

LSA di tipo 5

AS external link advertisement

Î Generato da un AS boudary router Î Generato da un AS boudary router Î Propagato in tutto il dominio di routing Î Propagato in tutto il dominio di routing

Æ Distanza alla destinazione ÆDistanza alla destinazione Æ AS in terminologia OSPF ÆAS in terminologia OSPF

R2R2 D1D1