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

(2)

ARGOMENTI DELLA LEZIONE

TEORIA DEL ROUTING

ROUTING STATICO

ROUTING DINAMICO

o PROTOCOLLI DISTANCE VECTOR

• COUNT TO INFINITY E SOLUZIONI o PROTOCOLLI LINK STATE

o PROTOCOLLI IBRIDI

(3)

TEORIA DEL ROUTING

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

(4)

TEORIA DEL ROUTING

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)

(5)

TEORIA DEL ROUTING

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

(6)

TEORIA DEL ROUTING

IL PROBLEMA

routing STATICO

DINAMICO metrica usata

es: load in/sensitive tipo algoritmo:

• Distance Vector

• Link State

• Ibridi

(7)

ROUTING STATICO

• adatto a reti di piccole dimensioni

• regole imposte dall’amministratore

 topologia

 aspetti economico-amministrativi

• scarsa tolleranza ai guasti

(8)

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_ij contiene il next hop usato

dal router j per raggiungere la destinazione i

(9)

ROUTING DINAMICO –DISTANCE VECTOR

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

ESEMPIO

192.168.2.0 192.168.3.0

0 0 1

192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

192.168.4.0 192.168.2.0

0 0 1

(15)

ESEMPIO

192.168.2.0 192.168.3.0 192.168.4.0

0 0 1 2

192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

192.168.4.0 192.168.2.0 192.168.1.0

0 0 1 2

(16)

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

192.168.3.0 192.168.1.0 192.168.4.0

0 0 1 1

192.168.4.0 192.168.2.0 192.168.1.0

0 0 1 2

(17)

PROBLEMI

Lenta convergenza

• Update più frequenti

 aumento timer

• Triggered Updates

problemi con flapping route

(18)

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

(19)

ROUTING DINAMICO –LINK STATE

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.

(20)

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.

(21)

VANTAGGI

• creano un albero come SPF, assenza di loop tipicamente

• LSA contengono solo info incrementali

• gestione topologia gerarchica

• supporto classless routing

(22)

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

(23)

ROUTING DINAMICO

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.

(24)

ROUTING DINAMICO –IBRIDI

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.