TFA 2014/15 SISTEMI E RETI DI CALCOLATORI PER L ... › pluginfile.php › 3556 › ... · INOLTRO...
Transcript of TFA 2014/15 SISTEMI E RETI DI CALCOLATORI PER L ... › pluginfile.php › 3556 › ... · INOLTRO...
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 1Unità Didattica:Protocolli di Routing
TFA 2014/15SISTEMI E RETI DI
CALCOLATORI PER L'INSEGNAMENTOUNITA' DIDATTICA:
ALGORITMI DI ROUTING
Università degli Studi di Pisa Dipartimento di Informatica
21/05/2015Laura Ricci
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 2Unità Didattica:Protocolli di Routing
STRUTTURA UNITA' DIDATTICA● Prerequisiti della unità didattica:
● conoscere le funzionalità del livello IP,struttura di un pacchetto IP● funzioni di un router● nozione di grafo
● contenuto della lezione: illustrazione di alcuni algoritmi di routing
● metodologia:● presentazione algoritmo sequenziale centralizzato● dimostrazione funzionamento dell'algoritmo mediante animazioni● introdurre il concetto di algoritmo distribuito: tutti i router
eseguono lo stesso codice● coordinamento comportamento router diversi● presentazione algoritmo distribuito
● laboratorio: implementazione dell'algoritmo sequenziale.
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 3Unità Didattica:Protocolli di Routing
PREREQUISITI: LIVELLO IP
Livello Network = livello IP
Modello di servizio di IP: invio di datagrams secondo la filosofia best effort.
datagram (o pacchetto IP) : contiene informazioni sufficienti affinchè la rete (i routers) possa inoltrarlo verso la destinazione
best effort: IP fornisce un servizio minimale. Motivazione: possibilità di eseguire il protocollo su reti che utilizzano diverse tecnologie
IP attualmente può essere eseguito su qualsiasi rete, anche su reti con tecnologie non esistenti al momento della sua definizione
metafora: “IP può operare su una rete che trasporta i messaggi mediante piccioni viaggiatori”
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 4Unità Didattica:Protocolli di Routing
PREREQUISITI: FORMATO DI UN PACCHETTO
IP VersionLungh.Header TOS Lunghezza Datagram
Identificatore Flag Offsetframmentazione
TTL Protocollo Checksum
Indirizzo Mittente
Indirizzo Destinatario
Opzioni
Dati
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 5Unità Didattica:Protocolli di Routing
PREREQISITI: FORMATO DEL PACCHETTO
IP Version: IPV4 / IPV6
TOS ( Type of Service) Consente un trattamento differenziato dei pacchetti.Ad esempio, un particolare valore di TOS indica che il pacchetto ha unapriorità maggiore rispetto agli altri. Utile per distinguere per distinguere tipi diversi di traffico ( traffico realtime, messaggi per la gestione della rete,..)
TTL – Time to Live: consente di limitare la diffusione del pacchetto sulla rete valore iniziale impostato dal mittente quando il pacchetto attraversa un router, il valore viene decrementato quando il valore diventa 0, il pacchetto viene scartatoIntrodotto inizialmente per evitare percorsi circolari infiniti del pacchetto.
Utilizzato anche per limitare la diffusione del pacchetto nel multicast
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 6Unità Didattica:Protocolli di Routing
PACCHETTI IP: FRAMMENTAZIONE
Trasmissione di pacchetti IP su reti fisiche diverse ed eterogenee:
quando un pacchetto P viene spedito su una rete fisica R, P deve essere incapsulato in un pacchetto Plink.
la dimensione di Plink dipende dal livello link della rete fisica R, in particolare dall’ MTU (Maximum Transfer Unit) di quella rete
Reti fisiche diverse MTU diversiEthernet: MTU = 1500 bytesFDDI : MTU = 45500 bytes
la dimensione di Plink in genere è diversa da quella di P
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 7Unità Didattica:Protocolli di Routing
PACCHETTI IP: FRAMMENTAZIONE
Approcci per la gestione di links eterogenei
definire la dimensione massima di un pacchetto IP come la minima dimensione dei pacchetti supportata a livello link dalle rete fisiche
svantaggi: difficoltà relativa alla definizione a priori di un limite inferiore alla
dimensione dei pacchetti a livello link (specie per reti in espansione come Internet)
spreco di risorse
fragmentazione: dividere un datagram IP in una o più parti (fragmenti) nel caso in cui l’MTU di una rete fisica sia inferiore alla dimensione del datagram.
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 8Unità Didattica:Protocolli di Routing
PACCHETTI IP: FRAMMENTAZIONE
HOSTH1
HOSTH2
ROUTER1 ROUTER2 ROUTER3
ETH IP 1400
PPP IP 376
PPP IP 512
PPP IP 512ETH IP 1400
ETH IP 376
ETH IP 512
ETH IP 512
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 9Unità Didattica:Protocolli di Routing
PACCHETTI IP: FRAMMENTAZIONE
la frammentazione del pacchetto viene effettuata dai routers
la ricostruzione del pacchetto avviene nell’host finale (un pacchetto una volta frammentato viene ricostruito solamente quando arriva a destinazione)
ricostruzione del pacchetto frammentato: utilizza i campi identificatore, flag, offset contenuti nel pacchetto IP identificatore: identifica in modo univoco i pacchetti generati da un
host. Quando un router fragmenta un pacchetto assegna a tutti i segmenti generati l’identificatore del pacchetto da cui provengono
offset: identifica la posizione del fragmento all’interno del datagram originale
flag M (more): indica se questo è l’ultimo fragmento del pacchetto IP
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 10Unità Didattica:Protocolli di Routing
PACCHETTI IP: FRAMMENTAZIONE
1400
PPP IP 376
PPP IP 512
PPP IP 512
Pacchetto IP, identificatore 233IP
Fragmento 1, identificatore 233, offset 0, M=1Fragmento 2, identificatore 233, offset 512, M=1Fragmento 3, identificatore 233, offset 1024, M=0
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 11Unità Didattica:Protocolli di Routing
PREREQUISITI: INDIRIZZI IP
Schemi di indirizzamento IP Classful Addressing Subnetting Classless Addressing CIDR
Classfull Addressing: ogni indirizzo IP rappresenta una gerarchia a due livelli la prima parte dell’indirizzo identifica la rete fisica a cui
appartiene l’host individuato da quell’indirizzzo la seconda parte individua l’host
171.69.210.245rete
host
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 12Unità Didattica:Protocolli di Routing
PREREQUISITI: INDIRIZZI IP
Tutti gli hosts ed i routers che condividono lo stesso indirizzo di rete sono connessi alla stessa rete fisica
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
ogni rete fisica connessa ad Internet ha almeno un router che è connesso ad un’altra rete fisica un router possiede un insieme di interfacce di rete
223.1.2.1
223.1.2.2
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 13Unità Didattica:Protocolli di Routing
PREREQUISITI: LA STRUTTURA DI INTERNET
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 14Unità Didattica:Protocolli di Routing
PREREQUISITI: LA STRUTTURA DI INTERNET
Autonomous System (AS) o routing domain è una regione di Internet amministrata da una singola entità
i prefissi di tutti gli host sono caratterizzati da un prefisso comune le politiche di routing appartengono ad un dominio amministrativo
unico Esempi:
IBM corporate network in generale gestite da grosse compagnie, università, enti
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 15Unità Didattica:Protocolli di Routing
PREREQUISITI: LA STRUTTURA DI INTERNET
AS diversi diversi possono utilizzare algoritmi di routing diversi
Routing all'interno di un AS Intra-AS Routing: focus sulla performance intra-domain or internal gateway (IGP) routing l'amministratore decide quale protocollo di roouting adottare
(interior gateway protocol) decisioni locali, non visibili all'esterno
Routing tra AS diversi focus sulla politica di instradamento inter-domain or external gateway (EGP) routing
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 16Unità Didattica:Protocolli di Routing
PREREQUISITI: INOLTRO DI PACCHETTI
routing: meccanismo di inotro utilizzato da routers ed hosts per decidere su quale porta di uscita inviare un pacchetto ricevuto su una porta di ingresso
il meccanismo di inoltro sfrutta un insieme di tabelle di inoltro che contengono un insieme di coppie
(numero di rete, interfaccia di uscita, prossimo router)
indirizzamento gerarchico nelle tabelle dei routers vengono memorizzati solo gli indirizzi delle reti,
piuttosto che gli indirizzi dei singoli hosts della rete. il router associato alla rete destinataria invia il messaggio all’host
selezionato.
indirizzamento gerarchico= aumento della scalabilità del sistema
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 17Unità Didattica:Protocolli di Routing
TABELLE DI ROUTING
Rete 3 (FDDI)
H1 H2 H3
Rete2 (Ethernet)
Rete 1 (Ethernet)
Rete 4(punto a punto)
Router1
Router 2
Router 3
H4
H5
H6
H7 H8
Tabella di inoltro del router2
N. di rete Interfaccia di uscita
Next router
1 0 Router32
int0
int1
1 Router1
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 18Unità Didattica:Protocolli di Routing
INOLTRO DEI PACCHETTI
Algoritmo di inoltro eseguito dal nodo N (host o router)NetworkAdd = indirizzo di rete contenuto nel pacchetto da inoltrare
• Networkadd è uguale all’ indirizzo di rete di una delle interfacce di N in questo casoil destinatario si trova sulla stessa rete del mittente, il pacchetto può essere consegnato direttamente dal livello link
• Networkadd è contenuto nella tabella di inoltro di Nin questo caso il pacchetto va consegnato al router next router
• altrimentiil pacchetto va consegnato ad un default router
(ad esempio un host può avere un default router a cui consegnare tutti i pacchetti non destinati alla rete loacle su cui tale host è connesso)
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 19Unità Didattica:Protocolli di Routing
INOLTRO DEI PACCHETTI
la trasmissione di un pacchetto IP su una rete fisica avviene mediante il livello link
ogni nodo connesso ad una rete fisica possiede un indirizzo detto indirizzo fisico o MAC (media acces control)
quando un pacchetto IP viene spedito su una rete fisica va utilizzato il MAC del nodo destinazione
traduzione indirizzo IP–MAC address avviene mediante ARP (Address Resolution Protocol)
Pacchetto IP incapsulato in un frame a livello link che contiene il MAC address del prossimo router o dell’host destinatario
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 20Unità Didattica:Protocolli di Routing
INSTRADAMENTO (ROUTING)
Autonomous System Architecture la rete viene vista come un insieme di gruppi indipendenti ogni gruppo corrisponde ad un sistema autonomo(AS) ogni AS comprende un gruppo di routers gestiti in modo indipendente
da una organizzazione il tipo di routing utilizzato all'interno di un sistema autonomo è
diverso da quello utilizzato tra sistemi autonomi diversi
All'interno di un sistema autonomo, si distinguono due tipi di routers routers interni: sono connessi unicamente ad altri routers dello stesso
sitema autonomo. Eseguono solo interior routing protocols border routers: sono connessi sia a routers interni che a routers di
altri sistemi autonomi. Eseguono interior ed exterior routing protocols
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 21Unità Didattica:Protocolli di Routing
INTERIOR ROUTING PROTOCOLS
assunzione base: la rete è rappresentata come un grafo, in cui i nodi rappresentano routers, gli archi linee fisiche di collegamento
Ad ogni arco è associato un valore che indica il costo dell’invio di un pacchetto su quel link. Nel caso più semplice i costi sono unitari ed il percorso di costo minimo è quello che attraversa il minor numero di routers
Assegnazione dei costi ai link: possono essere assegnati in base traffico sulla linea alla latenza delle linea alla banda delle linea
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 22Unità Didattica:Protocolli di Routing
MODELLARE UNA RETE
A
C D
B
F
E
4
3
6
21
1
1
9
Problema: dato un nodo mittente N1 ed un nodo destinatario N1, trovare il cammino di costo minimo tra N1 ed N2 (costo di un cammino= somma dei costi associati agli archi che definiscono il cammino)
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 23Unità Didattica:Protocolli di Routing
INTERIOR ROUTING PROTOCOLS
Algoritmi di routing intradominio: tutti gli algoritmi vengono eseguiti inmodo distribuito = ogni nodo esegue lo stesso algoritmo, i nodi cooperanoscambiandosi informazioni sulla topologia della rete e sui costi associai ailinks
Algoritmi di routing con conoscenza globale: ogni nodo deve avere conoscenza del grafo dell’intera rete e dei costi associati ai links.
Algoritmi basati sullo Stato delle Linee (OSPF)
Algoritmi di routing decentralizzati: ogni nodo ha solo conoscenza dei costi dei costi relativi ai links che lo collegano ai nodi vicini
Algoritmi basati su vettori distanza (RIP)
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 24Unità Didattica:Protocolli di Routing
CLASSIFICAZIONE PROTOCOLLI DI ROUTING
Classificazione dei protocolli di routing: interior routing protocols: utilizzati all’interno di un unico sistema
autonomo RIP (Routing Information Protocol) OSPF (Open shortestest Path First) IS-IS EIGRP Protocolli proprietari
Exterior gateway protocols : utilizzati tra sistemi autonomi diversi BGP
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 25Unità Didattica:Protocolli di Routing
CLASSIFICAZIONE ALGORITMI DI ROUTING
Distance-Vector:
vettori (destinazione-distanza) inviati ai vicini “Tell your neighbors about the rest of the network”
distanza definita in termini di diverse metriche: hop count, delay, banda
utilizza Distributed Bellman-Ford path selection algorithm protocolli: Routing Information Protocol (RIP)
Link-State flooding della descrizione dei propri links (link state) “Tell the rest of the network about your neighbors” usa l'algoritmo di selezione dei path di Dijkstra protocol: Open Shortest Path First (OSPF)
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 26Unità Didattica:Protocolli di Routing
OVERVIEW
Bellman-Ford shortest path algorithm
Distributed Bellman-Ford (DBF) e Routing Information Protocol (RIP)
Uso di algoritmi shortest-path algorithms in reti reali
– La debolezza principale del DBF: counting-to-infinity
Dijkstra algorithm
Dijkstra e OSPF
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 27Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMANN-FORD
● consideriamo un nodo A
● il nodo ha raccolto informazioni su tutti gli altri nodi e collegamenti della rete
● il nodo modella la rete mediante un grafo
● Bellman Ford:● A esegue l'algoritmo per calcolare la sua distanza da qualsiasi altro
nodo dell rete● quindi costruisce la sua tabella di routing che indica, per ogni altro
nodo N della rete, il vicino verso cui inoltrare il messaggio per raggiungere N tramite un cammino minimo
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 28Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 29Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 30Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 31Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 32Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 33Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 34Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
Idea generale: ricerca breadth-first dei cammini, incremento del numero di hops,
ricerca dei cammini migliori dal nodo sorgente a tutte le destinazioni termina quando non è possibile trovare un miglioramento
L'algoritmo in breve: R: insieme dei nodi per cui è stato trovato un cammino passo iterativo:
analizza tutti i nodi vicini di R, sia questo insieme R' se si individua un nodo n in R' per cui un cammino tramite uno
dei nodi in R è migliore del cammino migliore attuale associato al nodo n, si aggiorna il cammino di n in R
ripeti il passo iterativo viene ripetuto fino a che nessun cammino dei nodi in R può essere migliorato
alla fine da R si ricava la routing table
Dipartimento di InformaticaUniversità degli studi di Pisa
Laura Ricci 35Unità Didattica:Protocolli di Routing
L'ALGORITMO DI BELLMAN-FORD
V insieme di verticiE insieme di archi
wij peso del link tra i nodi i e j
R insieme dei nodi per cui si è trovato un cammino
R' insieme dei nodi vicini dei nodi in R
dj distanza dal nodo i al nodo j
pj predecessore del nodo j nel cammino che parte da i