RETI DI CALCOLATORI II

(1)

RETI DI CALCOLATORI II

Facoltà di Ingegneria Università degli Studi di Udine

Ing. DANIELE DE CANEVA

RETI DI CALCOLATORI II

Facoltà di Ingegneria Università degli Studi di Udine

a.a. 2009/2010

ARGOMENTI DELLA LEZIONE

ROUTING DINAMICO oOSPF

oBGP

ROUTING BROADCAST oN VIE

oFLOODING oRPF

oALBERO DI COPERTURA

ROUTING DINAMICO

ALGORITMO SHORTEST PATH FIRST

Sviluppato nel 1959 da Dijkstra

1. a tutti i percorsi associato un costo infinito 2. si definisce come working node il nodo di origine 3. ciclo che termina quando tutti i nodi hanno etichetta

permanente:

I. aggiorna il costo dei nodi adiacenti al working node II. tra tutti i nodi con etichetta non permanente si

definisce come working node quello con costo minore e si contrassegna la sua etichetta come permanente

ROUTING DINAMICO

ALGORITMO SHORTEST PATH FIRST ^R^O_U

TING DINAMICO

(2)

ROUTING DINAMICO

TING DINAMICO

ROUTING DINAMICO

ALGORITMO SHORTEST PATH FIRST ^ROUTING DINAMICO

ROUTING DINAMICO

TING DINAMICO

(3)

ROUTING DINAMICO

TING DINAMICO

ROUTING DINAMICO

ALGORITMO SHORTEST PATH FIRST ^ROUTING DINAMICO

ROUTING DINAMICO

TING DINAMICO

(4)

ROUTING DINAMICO

OSPF

Sviluppato per dare risposta ai grossi problemi di scalabilità e velocità di convergenza del protocollo RIP

1988 l’IETF iniziò a lavorare su OSPF (Open Shortest Path First), standardizzato nel 1990 con RFC 2338

Attualmente alla versione 2, è utilizzato dagli ISP di livello superiore

ROUTING DINAMICO -OSPF

OBIETTIVI PERSEGUITI DALL’IETF:

basato su standard aperto

diverse metriche

dinamico e rapido

routing basato su tipo del servizio (type of service IP)

funzionalità rimossa in seguito

supporto per sistemi gerarchici

sicurezza

CARATTERISTICHE

triggered updates incrementali

anche periodico (30 min) per robustezza

classless

metrica: non viene imposta una politica dei pesi, costi definiti dall’amministratore

hop

capacità del link = inverso della banda dell’interfaccia

sicurezza: possibile autenticazione

password in chiaro

firma MD5 con numeri di sequenza per protezione da attacchi ripetuti

CARATTERISTICHE

multipath load balancing: fino a 16 equal-cost route per ogni destinazione (utilizzati 4 di def)

supporto multicast: MOSPF

instradamento gerarchico

riconosce aree e AS

ROUTING DINAMICO -OS

SVANTAGGI

memoria: più memoria per contenere topologia e tabella routing

carico computazionale: richiede extra CPU

GERARCHIA

gerarchia a 2 livelli: backbone + aree

area 0

(5)

AREE

CARATTERISTICHE:

• non si sovrappongono

• la topologia di un’area è invisibile all’esterno

• tutte le aree sono collegate alla dorsale

4 CLASSI DI ROUTER

• internal router: completamente interno a un’area

• border router: collegamento tra 2 o più aree

• backbone router: appartiene alla dorsale

• boundary router: router di confine con altri AS

le classi possono sovrapporsi! es. router di confine sono anche di dorsale

3 TIPI DI PERCORSO

• intra-area: il router sorgente conosce già il percorso più breve

• inter-area: dalla sorgente alla dorsale, attraverso alla dorsale, fino alla destinazione

• inter-AS

ROUTER ID

• ID univoco su tutta la rete

• criteri di scelta dell’ID:

1. l’indirizzo IP più alto sulle interfacce di loopback del

SCAMBIO LSA

• lo scambio di LSA avviene tra nodi adiacenti

non equivale a dire vicini

una coppia di router devono creare un’adiacenza per essere considerati “neighbors” e scambiare LSA

(6)

SCAMBIO LSA

Per ottenere adiacenza:

• numero area

• tempi di hello e dead sulle interfacce connesse

• password preconfigurata (se presente)

• area stub flag che indica il tipo di area

• dimensione massima MTU sulle interfacce

SCAMBIO LSA

raggiunto il two-way state si verifica un processo di elezione

SCAMBIO LSA

Per evitare inefficienza viene creato un design client/server per ogni segmento di broadcast

fanno eccezione i point to point WAN

Designated router: nodo che mantiene le informazioni aggiornate di topologia e le propaga in tutto il segmento di broadcast

Backup designated router: per fault tollerance in caso di guasto del designated router

se DR cade viene sostituito e si elegge un nuovo BDR

Drothers: tutti gli altri nodi

ELEZIONE DEL DR

• il router con più alta priorità (su 8 bit da 0 a 255, def 1)

se uguale a zero il router viene escluso dall’elezione

• a parità di priorità si sceglie il router con ID più alto

POST-ELEZIONE DEL DR

! un router può fare capo a più DR/BDR se si affaccia su diversi segmenti broadcast

• si formano coppie master-slave che portano alla

POST-ELEZIONE DEL DR

In caso di caduta di un collegamento:

1. il router avvisa il DR (multicast 224.0.0.6) 2. il DR propaga l’info agli altri router del segmento

(multicast 224.0.0.5)

(7)

POST-ELEZIONE DEL DR ^R^O_U

TING DINAMICO -BGP

ROUTING TRA AS

Protocolli diversi per ragioni:

• politico-amministrative

• scalabilità

• prestazioni

ROUTING DINAMICO -BGP

BGP

Attualmente utilizzata la versione 4

definita nelle RFC da 1771 a 1774

std de facto per il routing tra AS

Scopi:

• ottenere info raggiungibilità dagli AS confinanti

• propagare tali info all’interno della propria rete

• determinare i precorsi più brevi verso tali destinazioni

BGP

Caratteristiche:

• utilizza sessioni TCP semipermanenti sulla porta 173

le connessioni tra i router non corrispondono necessariamente a collegamenti fisici

• le destinazioni non sono host ma prefissi CIDR

• eBGP per scambio dei prefissi

• iBGP per inoltro delle info dentro l’AS

ROUTING DINAMICO -BG

BGP ^R^O_U

TING DINAMICO -BG

BGP

“route BGP”: prefisso + attributi

tra cui:

• AS_PATH: elenco degli AS attraversati

(8)

BGP

Scelta tra percorsi alternativi:

• attributo di preferenza locale: assegnato

dall’amministratore, si sceglie valore preferenza più alto

• AS_PATH più breve: hop come metrica

• next hop più vicino

hot potato routing

• identificatori BGP

! Nella realtà è più complesso di così

BGP

Politiche di instradamento:

• solo il traffico che ha origine e/o destinazione in una rete cliente

• accordi di peering: negoziati privati tra ISP

MULTIPATH ROUTING? ^BROADCAST ROUTING

BROADCAST ROUTING

Scopo: inviare pacchetto a tutti i nodi

Tecniche:

• UNICAST a N VIE: semplice ma inefficiente, certi segmenti della rete verranno attraversati più volte

es. origine connessa con singolo segmento questo vedrà N pacchetti, uno per destinazione

! richiede conoscenza dell’indirizzo di tutti i destinatari (propagato in broadcast?)

BROADCAST ROUTING

• FLOODING CONTROLLATO: ogni nodo invia copia ai propri vicini tranne a quello dal quale ha ottenuto il pacchetto

! in caso di cicli si ottiene broadcast storm

BROADCAST ROUTING

(9)

BROADCAST ROUTING

• FLOODING CONTROLLATO

o NUMERO DI SEQUENZA: il nodo origine inserisce un identificatore e un numero di sequenza

i destinatari possono discriminare se è pacchetto ripetuto e quindi se devono inoltrarlo o meno

! deve mantenere una lista dei pacchetti visti

BROADCAST ROUTING

• FLOODING CONTROLLATO

o REVERSE PATH FORWARDING (RPF) (detto anche RPB Reverse Path Broadcast):

1. pacchetto inoltrato su tutte le uscite tranne quella dalla quale ho ricevuto il pacchetto 2. l’inoltro avviene solo se il pacchetto è pervenuto

dal percorso più breve che collega origine al nodo

non è necessario conoscere tutto il percorso da sorgente a nodo, è sufficiente sapere quale interfaccia fa parte del percorso più breve

BROADCAST ROUTING

Con flooding controllato evitati i broadcast storm ma permane l’inefficienza legata a pacchetti ripetuti

! consumo di banda e CPU

• BROADCAST CON ALBERO DI COPERTURA

• assenza di cicli

albero di copertura minimo: albero per il quale la somma dei costi associati ai lati è minima

BROADCAST ROUTING

tutti i pacchetti di broadcast seguono sempre l’albero, indipendentemente dalla sorgente

BROADCAST ROUTING

tutti i pacchetti di broadcast seguono sempre l’albero, indipendentemente dalla sorgente

(10)

BROADCAST ROUTING

! il problema si sposta sulla creazione dell’albero e sul suo mantenimento/aggiornamento

o APPROCCIO BASATO SUL CENTRO

1. viene stabilito un nodo che sarà la radice dell’albero

2. ogni nodo invia alla radice un messaggio di adesione

si procede per innesti

BROADCAST ROUTING

BROADCAST ROUTING ^BROADCAST ROUTING