1 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

A R G O M E N T I D E LL A L E Z IO N E

TEORIA DEL ROUTING

ROUTING STATICO

ROUTING DINAMICO o PROTOCOLLI DISTANCE VECTOR

• COUNT TO INFINITY E SOLUZIONI o PROTOCOLLI LINK STATE

o PROTOCOLLI IBRIDI

T E O R IA D E L R O U T IN G

SCOPO: trovare un buon percorso tra il router di origine e quello di destinazione.

Inoltro basato sulla TABELLA DI ROUTING contenente route:

• STATICHE

 direttamente connesse alle interfacce

 default route

 immesse dall’amministratore (routing statico)

• DINAMICHE derivate da protocollo di routing

differenza tra routing protocol e routed protocol

concetto di DISTANZA AMMINISTRATIVA

T E O R IA D E L R O U T IN G

Autonomous System: gruppo di reti sotto lo stesso controllo amministrativo

numero pubblico assegnato dallo IANA (da 1 a 65,535)

Interior Gateway Protocol (IGP) e Border Gateway Protocol (BGP)

T E O R IA D E L R O U T IN G

IL PROBLEMA grafo G = (N,E)

archi

ad ogni arco associato un costo dipendente da una metrica (es.

lunghezza link, velocità, prezzo) nodi

cammino: sequenza di nodi collegati a due a due da un arco costo del cammino: somma dei costi degli archi interessati

SCOPO: trovare il cammino a costo minimo

non necessariamente il più breve

T E O R IA D E L R O U T IN G

IL PROBLEMA

routing STATICO

DINAMICO metrica usata es: load in/sensitive

tipo algoritmo:

• Distance Vector

• Link State

• Ibridi

2

R O U T IN G S T A T IC O

ROUTING STATICO

• adatto a reti di piccole dimensioni

• regole imposte dall’amministratore

 topologia

 aspetti economico-amministrativi

• scarsa tolleranza ai guasti

R O U T IN G S T A T IC O

ROUTING STATICO POSSIBILI ALGORITMI:

• Albero di inoltro dei router

• Albero di inoltro delle destinazioni

più semplice gestire inserimento di una nuova destinazione

router

destinazioni

Casella A

contiene il next hop usato dal router j per raggiungere la destinazione i

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

DISTANCE VECTOR

CARATTERISTICHE

• Iterativo: processo si ripete fino a quando non c’è più scambio di informazioni

• Asincrono: non richiede sincronismo tra i nodi

• Distribuito: informazioni ottenute dai vicini, il risultato dei calcoli viene a sua volta inviato ai vicini

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

Basato sulla formula di Bellman-Ford

costo del percorso con costo minimo da x a y:

min tra tutti i nodi adiacenti

costo del link tra x e v

costo del percorso min da v a y

il pacchetto va inviato al vicino v* che minimizza l’espressione

con i diversi v* costruisco la tabella d’inoltro

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

ALGORITMO

• Inizia con ogni nodo che crea un vettore di stima del costo del percorso min per ogni destinazione nota.

• Ogni nodo mantiene:

1) Costo verso i vicini

2) Vettore distanza: che viene inviato a tutti i vicini

tip. broadcast periodici (dest. 255.255.255.255) ogni 30-60 secondi

no handshake da parte dei peers

quando ricevuto vettore di un vicino, la stima del costo viene ricalcolata converge a quella reale

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

Routing by rumor

Nella pratica:

• quando ottengo update incremento i suoi costi in base al costo del link dal quale ho ottenuto

• confronto le route dell’update con quelle della tabella interna

 se peggiori le ignoro

 se migliori cambio quelle interne

 se uguali reset del timer per la specifica entry.

 se medesimo costo ma path diverso, la route viene

aggiunta senza rimuovere quella vecchia ottenuta da un

vicino diverso

3

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

ESEMPIO

tabella router A Network Costo 192.168.1.0 192.168.2.0

0 0

tabella router B Network Costo 192.168.2.0 192.168.3.0

0 0

tabella router C Network Costo 192.168.3.0 192.168.4.0

0 0

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

ESEMPIO

tabella router A Network Costo 192.168.1.0 192.168.2.0 192.168.3.0

0 0 1

tabella router B Network Costo 192.168.2.0 192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

tabella router C Network Costo 192.168.3.0 192.168.4.0 192.168.2.0

0 0 1

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

ESEMPIO

tabella router A Network Costo 192.168.1.0 192.168.2.0 192.168.3.0 192.168.4.0

0 0 1 2

tabella router B Network Costo 192.168.2.0 192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

tabella router C Network Costo 192.168.3.0 192.168.4.0 192.168.2.0 192.168.1.0

0 0 1 2

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

ESEMPIO

tabella router A Network Costo

192.168.2.0 192.168.3.0 192.168.4.0

0

0 1 2

tabella router B Network Costo 192.168.2.0 192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

tabella router C Network Costo 192.168.3.0 192.168.4.0 192.168.2.0 192.168.1.0

0 0 1 2

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

PROBLEMI Lenta convergenza

• Update più frequenti

aumento timer

• Triggered Updates

problemi con flapping route

R O U T IN G D IN A M IC O – D IS T A N C E V E C T O R

PROBLEMI Count to Infinity

• Maximum hop count: stabilito il numero massimo di hop

• Split Horizon: non propago le informazioni all’indietro

• Route Poisoning e Hold-Down Timers

4

R O U T IN G D IN A M IC O – LI N K S T A T E

LINK STATE CARATTERISTICHE

• Instradamento globale: ogni nodo ottiene conoscenza totale della rete ricevendo messaggi da ogni altro nodo

• Distribuito e indipendente: ogni nodo esegue indipendentemente lo stesso algoritmo arrivando ai medesimi risultati.

Basati sull’algoritmo SPF (Shortest Path First) di Dijkstra:

iterattivo, alla k-esima iterazione diventano noti i cammini a costo minimo per k destinazioni.

R O U T IN G D IN A M IC O – LI N K S T A T E

Routing by propaganda

LSA (Link State Advertisement)

tipicamente generati solo quando ci sono dei cambiamenti

inviati in multicast (quindi non impegnano tutti nella decodifica)

invio di un pacchetto ack alla ricezione Al termine dell’algoritmo:

• costo per ogni destinazione

• predecessore: posso ripercorrere a ritroso tutto il cammino minimo e quindi posso costruire la tabella d’inoltro.

R O U T IN G D IN A M IC O – LI N K S T A T E

VANTAGGI

• creano un albero come SPF, assenza di loop tipicamente

• LSA contengono solo info incrementali

• gestione topologia gerarchica

• supporto classless routing

R O U T IN G D IN A M IC O – LI N K S T A T E

SVANTAGGI

• Richiedono più risorse computazionali

 CPU: per eseguire algoritmo più complesso

grosso problema con flapping rapidi (10-15 sec)

 Memoria: più tabelle da mantenere

• Problemi di scalabilità

spesso questi protocolli danno la possibilità di limitare lo scope nel processo di apprendimento

R O U T IN G D IN A M IC O

CONFRONTO DV vs. LS

• Complessità computazionale:

 LS: complesso ma sicuro

 DV: semplice come implementazione e troubleshooting

• Comunicazioni:

 LS: deve informare tutti in caso di cambio topologia

 DV: informa solo i vicini ma la notizia è lenta nel propagarsi

• Robustezza:

 LS: calcoli eseguiti indipendentemente da ogni nodo

 DV: il calcolo è collaborativo, possibili problemi.

R O U T IN G D IN A M IC O – IB R ID I

STATO ATTUALE

• PROTOCOLLI IBRIDI: tipicamente basati su DV incorporano funzionalità LS

• Un tempo i DV erano sufficienti per piccole reti, oggi come IGP viene usato principalmente OSPF (EIGRP come secondo classificato distante)

• Per SOHO si usano route statiche.