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:

IGRP Routing

Routing dinamico: dinamico:

IGRP IGRP

Argomenti della lezione Argomenti della lezione

Î Interior Gateway Routing Protocol (IGRP)

Î Interior Gateway Routing Protocol (IGRP)

Î Enhanced IGRP Î Enhanced IGRP

IGRP IGRP

Î Algoritmo Distance Vector (o di Bellman-Ford)

Î Algoritmo Distance Vector (o di Bellman-Ford)

Î Algoritmo dinamico per il routing distribuito

ÎAlgoritmo dinamico per il routing distribuito

Î Approccio di tipo adattativo ÎApproccio di tipo adattativo

Interior Gateway Routing Protocol Interior Gateway

Routing Protocol

Generalità Generalità

Î Protocollo proprietario ÎProtocollo proprietario

Î Sviluppato da Cisco a metà ’80 ÎSviluppato da Cisco a metà ’80 Î Versione Enhanced agli inizi ’90 ÎVersione Enhanced agli inizi ’90 Î Più efficiente del RIP

ÎPiù efficiente del RIP

(2)

Î Metriche ÎMetriche

Î Multipath routing ÎMultipath routing Î Messaggi

Î Messaggi Î Stabilità ÎStabilità Î Timer ÎTimer

Î Confronto con RIP ÎConfronto con RIP

IGRP IGRP

Metriche Metriche

Più articolate del RIP

Più articolate del RIP Î B – banda (3 B) → 600b/s-10Gb/s ÎÎBB––banda (3 B) banda (3 B) →→600b/s-600b/s-10Gb/s10Gb/s Î D – ritardo (3 B) → 10 µs - 168 s ÎÎDD––ritardo (3 B) ritardo (3 B) →→10 10 µµs s --168 s168 s Î R – affidabilità (1 B) → 0 - 100%

Î

ÎRR––affidabilitàaffidabilità(1 B) (1 B) →→0 -0 -100%100%

Î L – carico (1 B) → 0 - 100%

ÎÎLL––carico (1 B) →carico (1 B) →0 0 --100%100%

Calcolo delle metriche Calcolo delle metriche

Î Banda: minimo sul percorso Î Banda:minimo sul percorso Î Ritardo: somma sul percorso Î Ritardo:somma sul percorso Î Affidabilità: peggiore sul percorso Î Affidabilità:peggiore sul percorso Î Carico: più alto sul percorso Î Carico:più alto sul percorso Æ Media esponenziale su 5 min ÆMedia esponenziale su 5Media esponenziale su 5minmin

Valori di default Valori di default

Dipendenti dal tipo di interfaccia Dipendenti dal tipo di interfaccia

ÎEthernet (10 Mb/s) ÎEthernet (10 Mb/s)

Æ B = 1.000 ÆB = 1.000 Æ D = 100 (1 ms) ÆD = 100 (1 ms) ÎCDN 64 Kb/s ÎCDN 64 Kb/s Æ B = 156.250 ÆB = 156.250 Æ D = 2.000 (20 ms) ÆD = 2.000 (20 ms)

Qual è il percorso migliore?

minima minima Metrica composta (composit metric) Metrica composta (composit metric)

Metrica composta Metrica composta

Configurabili Configurabili

Per ToS (Type of Service) Per ToS (Type of Service) Dalle metriche tramite 5 parametri (k1, k2, k3, k4, k5)

Dalle metriche tramite 5 parametri (k1, k2, k3, k4, k5)

Importanza delle metriche Importanza delle metriche

(3)

Metrica composta: calcolo Metrica composta: calcolo

Se k5 = 0

Se k5 = 0

C = (107/B) [k1+k2/(256-L)]+k3 D C = (107/B) [k1+k2/(256-L)]+k3 D

Se k5 ‡ 0 Se k5 ‡ 0

C’ = C [k5/(R+k4)]

Default (per ToS = 0):

k1 = k3 = 1; k2 = k4 = k5 = 0 Default (per ToS = 0):

k1 = k3 = 1; k2 = k4 = k5 = 0 C = (107/B)+D

C = (107/B)+D

Informazioni aggiuntive Informazioni aggiuntive

Numero di router sul percorso Numero di router sul percorso

Hop count Hop count

Non usate per scegliere i percorsi Non usate per scegliere i percorsi

Limitazione count to infinity Limitazione count to infinity

Informazioni aggiuntive Informazioni aggiuntive

Minore sul percorso Minore sul percorso (Maximum Transmission Unit)MTUMTU (Maximum Transmission Unit) Non usate per scegliere i percorsi Non usate per scegliere i percorsi

Multipath routing Multipath routing

Più “entry” nella tabella di routing per la stessa destinazione

Il carico è ripartito tra le route in base alla metrica

composta associata

Multipath routing Multipath routing

Considerate solo entry con metriche in predefinito rapporto con la migliore Considerate solo entry con metriche in

predefinito rapporto con la migliore Il carico è ripartito tra le route in base alla metrica

Threshold (soglia) Threshold (soglia)

Î Simile al RIP Î Simile al RIP

Î In pacchetto IP di 1500 byte Î In pacchetto IP di 1500 byte

Update Update

Î Fino a 104 annunci Î Fino a 104 annunci

Messaggi Messaggi

Î Richiesta di update al vicino Î Richiesta di update al vicino

Request Request

(4)

Î Analogo al RIP Î Analogo al RIP

Split Horizon Split Horizon

Stabilità Stabilità

Î Analogo al RIP Î Analogo al RIP

Triggered update Triggered update

Simile a poisoned reverse in RIP Simile a poisoned reverse in RIP

Î Sintomo di routing loop Î Sintomo di routing loop

Stabilità: route poisoning Stabilità: route poisoning

Attivato se la metrica composita aumenta di un fattore > 1.1 Attivato se la metrica composita aumenta di un fattore > 1.1

Dar tempo alle informazioni di propagarsi

Î Route non usata Î Route non usata

Stabilità: hold down Stabilità: hold down

Quando una destinazione diviene irraggiungibile

Î Route poisoning Î Route poisoning

Nuove route per la destinazione

sono ignorate per un certo tempo

Nuove route per la destinazione

sono ignorate per un certo tempo

Stabilità: hold down Stabilità: hold down

Î Invio periodico di messaggi update Î Invio periodico di messaggi update

Update timer (90s) Update timer (90s)

Timer

Î Route non valida in assenza di annunci

Î Route non valida in assenza di annunci

Invalid timer (3 x update) Invalid timer (3 x update) Î Più lungo che nel RIP Î Più lungo che nel RIP Î Minor traffico

Î Minor traffico

Î Durata dell’hold down Î Durata dell’hold down

Timer Timer

Î Eliminazione di route “invalid”

Î Eliminazione di route “invalid”

Flush timer (7 x update) Flush timer (7 x update)

Hold down timer (3 x update) + 10s

Æ Tenuta per essere annunciata come irraggiungibile

ÆTenuta per essere annunciata come irraggiungibile

(5)

IGRP vs. RIP IGRP vs. RIP

Î RIP progettato per reti di modeste dimensioni e semplici Î RIP progettato per reti di

modeste dimensioni e semplici Î Metriche

Î Metriche

Î Multipath routing in IGRP Î Multipath routing in IGRP

IGRP vs. RIP IGRP vs. RIP

Î Istanze multiple di IGRP ÎIstanze multiple di IGRP

Æ Numero di autonomous system ÆNumero di autonomous system Î Default route

ÎDefault route

IGRP vs. RIP: metriche IGRP vs. RIP: metriche

Î Hop count del RIP non tiene conto del tipo di collegamenti Î Hop count del RIP non tiene

conto del tipo di collegamenti Î RIP non sceglie la strada più

lunga

Î RIP non sceglie la strada più lunga

Æ Che può essere la più “veloce”

ÆChe può essere la più “veloce”

IGRP vs. RIP: metriche IGRP vs. RIP: metriche

Î Riduzione del diametro della rete ÎRiduzione del diametro della rete

Æ Sono ammessi solo 15 hop ÆSono ammessi solo 15 hop Î Metriche IGRP sono più intuitive Î Metriche IGRP sono più intuitive Î Manuale

Î Manuale

Alcune implementazioni consentono di configurare un collegamento

come hop multipli

Alcune implementazioni consentono di configurare un collegamento

come hop multipli

Î Default per destinazioni per cui non è presente altra route Î Default per destinazioni per cui

non è presente altra route

Default route

Î Inutile annunciare tutte le destinazioni

Î Inutile annunciare tutte le destinazioni

Î Router “periferici” hanno route per destinazioni non annunciate Î Router “periferici” hanno route

per destinazioni non annunciate

IGRP vs. RIP: default route IGRP vs. RIP: default route

RIP (come altri) annuncia come vera e propria destinazione

(0.0.0.0/0)

RIP (come altri) annuncia come vera e propria destinazione

(0.0.0.0/0)

Î Router “periferico” configurato per generare tale annuncio Î Router “periferico” configurato

per generare tale annuncio Î Ottimizzazione del solo percorso

verso il router “periferico”

Î Ottimizzazione del solo percorso verso il router “periferico”

(6)

IGRP vs. RIP: default route IGRP vs. RIP: default route

IGRP indica alcune destinazioni

come potenziali default IGRP indica alcune destinazioni

come potenziali default Î La migliore tra le potenziali

route è usata come default Î La migliore tra le potenziali

route è usata come default

Î Ottimizzazione del percorso verso la destinazione potenziale default Î Ottimizzazione del percorso verso

la destinazione potenziale default Æ Miglior adattabilità

ÆMiglior adattabilità

E-IGRP

Enhanced IGRP

E-IGRP

Enhanced IGRP

Î Annuncio netmask Î Annuncio netmask Æ Classless routing ÆClassless routing

Î Route esterne Î Route esterne

Î Convergenza più rapida Î Convergenza più rapida

Caratteristiche salienti Caratteristiche salienti

Î Supporto multiprotocollo Î Supporto multiprotocollo Î Minore traffico di routing Î Minore traffico di routing

Principi generali Principi generali

Non prevede annunci periodici Non prevede annunci periodici Un router memorizza la tabella di routing di ogni router adiacente Un router memorizza la tabella di routing di ogni router adiacente

Principi generali Principi generali

Î Velocizzare la reazione ai guasti Î Velocizzare la reazione ai guasti

Per ogni destinazione, oltre al next hop, sono identificati

“possibili successori”

Per ogni destinazione, oltre al next hop, sono identificati

“possibili successori”

Meccanismi fondamentali Meccanismi fondamentali

Reliable Transport Protocol Reliable Transport Protocol Neighbor discovery e recovery Neighbor discovery e recovery

DUAL – Diffusion Update Algorithm DUAL – Diffusion Update Algorithm

Alla base dell’eliminazione di annunci periodici Alla base dell’eliminazione

di annunci periodici

(7)

Neighbor discovery e recovery Neighbor discovery e recovery

Scoperta automatica di router collegati

Identificazione di non

raggiungibilità o non operatività Identificazione di non

raggiungibilità o non operatività Î Poco traffico

Î Poco traffico

Invio di messaggi hello Invio di messaggi hello Î Poco carico elaborativo Î Poco carico elaborativo

Cambiamento topologico Cambiamento topologico

Un next hop diviene irraggiungibile Un next hop diviene irraggiungibile Collegamento non funzionante Collegamento non funzionante

Cambiamento della metrica in un annuncio

Annunci parziali:

solo route cambiate Annunci parziali:

solo route cambiate

Cambiamento topologico Cambiamento topologico

Reazione immediata Reazione immediata Nessuna informazione scambiata Nessuna informazione scambiata Se esiste un “possibile successore”

è usato come next hop Se esiste un “possibile successore”

è usato come next hop

Richiede ai vicini di individuare percorsi verso la destinazione Richiede ai vicini di individuare percorsi verso la destinazione

I vicini propagano la richiesta ai loro vicini

Cambiamento topologico Cambiamento topologico

Altrimenti, si esegue il Diffusion Update ALgorithm (DUAL) Altrimenti, si esegue il Diffusion

Update ALgorithm (DUAL)

Computazionalmente leggero Computazionalmente leggero

Richiede tempo Richiede tempo

Cambiamento topologico Cambiamento topologico

Altrimenti, si esegue il Diffusion Update ALgorithm (DUAL) Altrimenti, si esegue il Diffusion

Update ALgorithm (DUAL)

Etichettamento (tagging) di route apprese tramite altri protocolli Etichettamento (tagging) di route apprese tramite altri protocolli

Î Normalmente route interne sono preferite a quelle esterne

Î Normalmente route interne sono preferite a quelle esterne

Route esterne Route esterne

Trattate in modo differenziato Trattate in modo differenziato

Importante per evitare routing loop

Importante per evitare

routing loop

(8)

Compatibilità con IGRP Compatibilità con IGRP

Î Stesse metriche Î Stesse metriche

Î Possibile migrazione graduale Î Possibile migrazione graduale

Le route di IGRP sono trasportate in E-IGRP e viceversa

Î Possono essere trattate opportunamente

Î Possono essere trattate opportunamente

Compatibilità con IGRP Compatibilità con IGRP

E-IGRP etichetta route apprese da IGRP