Capitolo 4 Livello di rete

(1)

Capitolo 4

Livello di rete

Reti di calcolatori e Internet:

Un approccio top-down 3^a edizione

Jim Kurose, Keith Ross Pearson Education Italia

Nota per l’utilizzo:

Abbiamo preparato queste slide con l’intenzione di renderle disponibili a tutti (professori, studenti, lettori). Sono in formato PowerPoint in modo che voi possiate aggiungere e cancellare slide (compresa questa) o modificarne il contenuto in base alle vostre esigenze.

Come potete facilmente immaginare, da parte nostra abbiamo fatto un sacco di lavoro. In cambio, vi chiediamo solo di rispettare le seguenti condizioni:

 se utilizzate queste slide (ad esempio, in aula) in una forma sostanzialmente inalterata, fate riferimento alla fonte (dopo tutto, ci piacerebbe che la gente usasse il nostro libro!)

 se rendete disponibili queste slide in una forma sostanzialmente inalterata su un sito web, indicate che si tratta di un adattamento (o che sono identiche) delle nostre slide, e inserite la nota relativa al copyright.

Thanks and enjoy! JFK/KWR

(2)

Capitolo 4: Livello di rete

Obiettivi del capitolo:

 Capire i principi che stanno dietro i servizi del livello di rete:



Instradamento (scelta del percorso)



Scalabilità



Funzionamento di un router



Argomenti avanzati: IPv6, mobilità

 Implementazione in Internet

(3)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 Formato dei datagrammi

 Indirizzamento IPv4

 ICMP

 IPv6

4.5 Algoritmi di instradamento

 Stato del collegamento

 Vettore distanza

 Instradamento gerarchico

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento broadcast e multicast

(4)

Livello di rete

 Il livello di rete prende i segmenti dal livello di trasporto nell’host mittente

 Sul lato mittente, incapsula i segmenti in datagrammi

 Sul lato destinatario, consegna i segmenti al livello di trasporto

 Protocolli del livello di rete in ogni host, router

 Il router esamina i campi intestazione in tutti i datagrammi IP che lo attraversano

ReteLink Fisico

ReteLink Fisico ReteLink

Fisico

Applicazione

Trasporto ReteLink Fisico

Applicazione

Trasporto ReteLink Fisico

(5)

Funzioni chiave del livello di rete



Inoltro (forwarding):

trasferisce i pacchetti dall’input di un router all’output del router appropriato



Instradamento (routing):

determina il percorso seguito dai pacchetti dall’origine alla

destinazione

 Algoritmi d’instradamento

analogia:

 instradamento:

processo di

pianificazione di un viaggio dall’origine alla destinazione

 inoltro: processo di

attraversamento di un

determinato svincolo

(6)

1

3 2

0111

Valore nell’intestazione del pacchetto in arrivo

Algoritmo d’instradamento

Tabella di inoltro locale Valore

d’intestazione

Collegamento d’uscita

0100 0101 0111 1001

3 2 2 1

Instradamento e inoltro

(7)

Impostazione della connessione



Terza funzione importante in qualche architettura a livello di rete:

 ATM, frame relay, X.25



Prima che i datagrammi fluiscano, due host e i router stabiliscono una connessione virtuale

 i router vengono coinvolti



Servizio di connessione tra livello di trasporto e livello di rete:

 Rete: tra due host

 Trasporto: tra due processi

(8)

Modello di servizio del livello di rete

D: Qual è il modello di servizio per il “canale” che trasporta i datagrammi dal mittente al

destinatario?

Servizi per un singolo datagramma:



Consegna garantita



Consegna garantita con un ritardo inferiore a 40 msec

Servizi per un flusso di datagrammi:



Consegna in ordine



Minima ampiezza di banda garantita



Restrizioni sul lasso di tempo tra la

trasmissione di due

pacchetti consecutivi

(9)

Modelli di servizi del livello di rete:

Architettura di rete

Internet ATM

ATM ATM ATM

Modello di servizio

best effort CBR VBR ABR UBR

Banda nessuna Tasso costante garantito

Minima garantita nessuna

Consegna no

sì

sì no no

Ordina- mento no sì

sì sì sì

Temporiz- zazione no

sì

sì no no

Indicazione di congestione

no

Nessuna congestione Nessuna congestione sì

no Garanzia?

(10)

Capitolo 4: Livello di rete

4.1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

broadcast e multicast

(11)

Reti a circuito virtuale e a datagramma



Reti a datagramma offrono solo il servizio senza connessione.



Reti a circuito virtuale (VC) mettono a disposizione solo il servizio con connessione.



Ci sono alcune analogie con quanto avviene a livello di trasporto ma:

 Servizio: da host a host

 Non si può scegliere: il livello di rete offre un servizio senza connessione o con connessione ma non entrambi

 Le implementazioni: sono fondamentalmente diverse.

(12)

Reti a circuito virtuale

 Il pacchetto di un circuito virtuale ha un numero VC nella propria intestazione.

 Un circuito virtuale può avere un numero VC diverso su ogni collegamento.

 Ogni router sostituisce il numero VC con un nuovo numero.

“il percorso tra origine e destinazione si comporta in

modo analogo a un circuito telefonico”

(13)

Implementazioni

Un circuito virtuale consiste in:

1.

un percorso tra gli host origine e destinazione

2.

numeri VC, uno per ciascun collegamento

3.

righe nella tabella d’inoltro in ciascun router.

 Il pacchetto di un circuito virtuale ha un numero VC nella propria intestazione.

 Il numero VC del pacchetto cambia su tutti i collegamenti lungo un percorso.



Un nuovo numero VC viene rilevato dalla tabella

d’inoltro.

(14)

Tabella d’inoltro

12 22 32

1 2 3

Numero VC

Numero interfaccia

Interf.in ingresso Nr. VC entrante Interf. in uscita Nr. VC uscente

1 12 3 22

2 63 1 18

3 7 2 17

1 97 3 87

… … … …

Tabella d’inoltro:

(15)

Protocolli di segnalazione

 Messaggi inviati dai sistemi terminali per avviare o concludere un circuito virtuale

 Usati in ATM, frame-relay e X.25

 Non usati in Internet.

Applicazione Trasporto

ReteLink Fisico

1. Chiam. di inizialz. 2. Chiam. in ingresso 3. Accettaz. di chiam.

4. Chiamata connessa5. Inizia il flusso di dati 6. Ricezione dei dati Applicazione Trasporto

ReteLink Fisico

(16)

Reti a datagramma

 L’impostazione della chiamata non avviene a livello di rete

 I router della rete a datagramma non conservano informazioni sullo stato dei circuiti virtuali (perché non ce ne sono).

 I pacchetti vengono inoltrati utilizzando l’indirizzo dell’host destinatario.

 I pacchetti passano attraverso una serie di router che utilizzano gli indirizzi di destinazione per inviarli.

1. Invio di dati 2. Ricezione di dati

ReteLink Fisico

(17)

Tabella d’inoltro

Intervallo degli indirizzi di destinazione Interfaccia da 11001000 00010111 00010000 00000000

0 a 11001000 00010111 00010111 11111111

da 11001000 00010111 00011000 00000000

1 a 11001000 00010111 00011000 11111111

da 11001000 00010111 00011001 00000000

2 a 11001000 00010111 00011111 11111111

4 miliardi

di possibili indirizzi

(18)

Confronta un

Corrispondenza di prefisso

prefisso dell’indirizzo

Interfaccia

11001000 00010111 00010 0

11001000 00010111 00011000 1

11001000 00010111 00011 2

altrimenti 3

con: 11001000 00010111 00011000 10101010 Esempi:

con: 11001000 00010111 00010110 10100001 Qual è l’interfaccia?

Qual è l’interfaccia?

(19)

Perché reti a circuito virtuale o a datagramma?

Internet

 Necessità di scambiare dati tra differenti calcolatori.

 Servizi elastici, non vi sono eccessivi requisiti di tempo

 L’interconnessione è semplice (computer)

 È adattabile, effettua controlli e recupera errori

 Rete interna non complessa, la complessità sta agli

estremi

 Svariati tipi di link

 Caratteristiche differenti

 Difficile uniformarne il servizio

ATM

 Deriva dal mondo della telefonia.

 Conversazione telefonica:

 Requisiti stringenti in termini di tempo e affidabilità.

 Necessità di servizi garantiti.

 Sistemi terminali “stupidi”

 Telefoni.

 La complessità sta nella

(20)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

 RIP

 OSPF

 BGP

(21)

Architettura del router?

Due funzioni chiave:

 Far girare i protocolli/algoritmi d’instradamento (RIP, OSPF, BGP)

 Inoltro di datagrammi dai collegamenti in ingresso a quelli in uscita.

(22)

Porte d’ingresso

Commutazione decentralizzata :

 Determina la porta d’uscita dei pacchetti utilizzando le informazioni della tabella d’inoltro

 Obiettivo: completare l’elaborazione allo stesso tasso della linea

 Accodamento: se il tasso di arrivo dei Livello fisico:

ricezione a livello di bit

Livello di link:

Es. Ethernet (vedi Capitolo 5)

(23)

Tre tecniche di commutazione

(24)

Commutazione in memoria

Prima generazione di router:

 Erano tradizionali calcolatori e la commutazione era effettuata sotto il controllo diretto della CPU.

 Il pacchetto veniva copiato nella memoria del processore.

 I pacchetti venivano trasferiti dalle porte d’ingresso a quelle d’uscita con una frequenza totale inferiore a B/2.

Porta d’ingresso

Porta d’uscita

Memoria

Bus

(25)

Commutazione tramite bus



Le porte d’ingresso trasferiscono un pacchetto direttamente alle porte d’uscita su un bus condiviso.



La larghezza di banda della

commutazione è limitata da quella del bus.



Cisco 1900 opera con bus da 1

Gbps: è sufficiente per router che

operano in reti d’accesso o in quelle

(26)

Commutazione attraverso rete d’interconnessione

 Supera il limite di banda di un singolo bus condiviso.

 Tendenza attuale: frammentazione dei

pacchetti IP a lunghezza variabile in celle di lunghezza fissa.

 Switch Cisco 12000: usano una rete

d’interconnessione che raggiunge i 60 Gbps

nella struttura di commutazione.

(27)

Porte d’uscita

 Funzionalità di accodamento: quando la struttura di commutazione consegna pacchetti alla porta d’uscita a una frequenza che supera quella del collegamento uscente.

 Schedulatore di pacchetti: stabilisce in quale ordine trasmettere i pacchetti accodati.

(28)

Dove si verifica l’accodamento?

 Se la struttura di commutazione non è sufficientemente rapida nel trasferire i pacchetti, si può verificare un accodamento.

 Se le code diventano troppo lunghe, i buffer si possono saturare e quindi causare una perdita di pacchetti!

(29)

Dove si verifica l’accodamento?



Blocco in testa alla fila (HOL): un pacchetto nella coda d’ingresso deve attendere il trasferimento

(anche se la propria destinazione è libera) in quanto risulta bloccato da un altro pacchetto in testa alla fila.



Se le code diventano troppo lunghe, i buffer si

possono saturare e quindi causare una perdita di

pacchetti!

(30)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

 RIP

 OSPF

 BGP

(31)

Protocollo Internet (IP): inoltro e indirizzamento in Internet

Tabella d’inoltro

Uno sguardo al livello di rete Internet:

Protocolli

di instradamento

•Selezione di percorso

•RIP, OSPF, BGP

Protocollo IP

•Convenzioni di indirizzamento

•Formato dei datagrammi

•Convenzioni di manipolazione dei pacchetti

Protocollo ICMP

•Notifica degli errori

•Segnalazioni del router

Livello di trasporto: TCP, UDP

Livello di collegamento Livello fisico

Livello

di rete

(32)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

broadcast e multicast

(33)

Formato dei datagrammi

ver ^Lunghezza

32 bit

(contiene il segmentoDati a livello di trasporto,

TCP o UDP)

Identificatore a 16 bit

Checksum dell’intestazione Tempo di

vita residuo

Indirizzo IP origine (32 bit) Numero di versione

Lunghezza dell’intestazione

Tempo di vita (si decrementa ogni volta che viene elaborato dal router)

Identificatore, flag,

Spiazzamento

di frammentazione Lunghezza

del datagramma (byte)

Protocollo di livello superiore

Lungh.

Intest. ^servizio^{Tipo di}

Tipo di servizio _flag Spiazzamento

di framm. a 13 bit Protoc. di

livello sup.

Indirizzo IP destinazione (32 bit)

Campi opzionali Es.: timestamp, registrazione dei percorsi, elenco dei router

(34)

Frammentazione dei datagrammi IP

 L’unità massima di trasmissione (MTU) è la massima quantità di dati che un frame a livello di collegamento può trasportare.

 Differenti tipi di link, differenti MTU.

 Datagrammi IP grandi vengono frammentati in datagrammi IP più piccoli.

 Un datagramma viene frammentato.

 I frammenti saranno

riassemblati solo una volta raggiunta la destinazione

 I bit dell’intestazione IP sono usati per identificare e

ordinare i frammenti

Frammentazione:

ingresso: un datagramma grande

uscita: 3 datagrammi più piccoli

Riassemblaggio

(35)

Frammentazione e riassemblaggio IP

ID=x Flag ^Spiazz.=0

=0

Lunghez.

=4000

=1

Lunghez.

=1500

=1

Lunghez.

=1500

=0

Lunghez.

=1040

Un datagramma IP grande viene

frammentato in datagrammi IP più piccoli.

Esempio

 Datagramma di 4000 byte

 MTU = 1500 byte

1480 byte nel campo dati

Spiazzamento = 1480/8

(36)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

broadcast e multicast

(37)

Indirizzamento IPv4

 Indirizzo IP: ogni interfaccia di host e

router di Internet ha un indirizzo IP globalmente univoco.

 Interfaccia: è il confine tra host e collegamento fisico.

 I router devono

necessariamente essere connessi ad almeno due collegamenti.

 Un host, in genere, ha un’interfaccia

 A ciascuna interfaccia sono associati indirizzi IP

223.1.1.1 223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2 223.1.2.1

223.1.3.2 223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

(38)

Sottoreti



Cos’è una sottorete?

 Per IP una rete che interconnette tre interfacce di host e l’interfaccia di un router forma una sottorete.

 Nella letteratura

Internet le sottoreti sono anche chiamate reti IP.

223.1.1.1 223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2 223.1.2.1

223.1.3.2 223.1.3.1

223.1.3.27

rete composta da 3 sottoreti sottorete

(39)

Sottorete

223.1.1.0/24

223.1.2.0/24

223.1.3.0/24

Definizione



È detta sottorete una rete isolata i cui punti terminali sono collegati all’interfaccia di un

host o di un router.

Maschera di sottorete: /24

(40)

Sottoreti

Quante sono?

^223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2 223.1.2.1

223.1.2.6

223.1.3.2 223.1.3.1

223.1.3.27 223.1.1.2

223.1.7.0

223.1.7.1 223.1.8.0

223.1.8.1 223.1.9.1

223.1.9.2

(41)

Assegnazione indirizzi Internet

CIDR: Classless InterDomain Routing CIDR



È la strategia di assegnazione degli indirizzi.



Struttura dell’indirizzo: l’indirizzo IP viene diviso in due parti e mantiene la forma decimale puntata a.b.c.d/x, dove x indica il numero di bit nella prima parte dell’indirizzo.

11001000 00010111 00010000 00000000

Parte di sottorete

Parte host

(42)

Come ottenere un blocco di indirizzi

D: Cosa bisogna fare per assegnare un indirizzo IP a un host?

 Configurazione manuale:

 Wintel: control-panel->network->configuration->tcp/ip-

>properties

 UNIX: /etc/rc.config

 DHCP: Dynamic Host Configuration Protocol: permette a un host di ottenere un indirizzo IP in modo automatico

 “plug-and-play”

(vedi il Capitolo 5)

(43)

Come ottenere un blocco di indirizzi

D: Cosa deve fare un amministratore di rete per ottenere un blocco di indirizzi IP da usare in una sottorete?

R: deve contattare il proprio ISP e ottenere la divisione in otto blocchi uguali di indirizzi contigui.

Blocco dell’ISP 11001000 00010111 00010000 00000000 200.23.16.0/20 Organizzazione 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organizzazione 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organizzazione 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. ….

Organizzazione 7 11001000 00010111 00011110 00000000 200.23.30.0/23

(44)

Indirizzamento gerarchico

“Inviami tutto quello il cui indirizzo

inizia per

200.23.16.0/20”

200.23.16.0/23 200.23.18.0/23

200.23.30.0/23

Scappo-Con-La-Cassa Organizzazione 0

Organizzazione 7 Internet

Organizzazione 1

Provvedo-Io “Inviami tutto quello il cui indirizzo

inizia per

200.23.20.0/23

Organizzazione 2

...

Indirizzamento gerarchico e aggregazione di indirizzi:

(45)

Indirizzamento gerarchico più specifico

Provvedo-Io presenta un percorso più specifico verso Organizzazione 1

“Inviami tutto quello il cui indirizzo

inizia per

200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23 200.23.30.0/23

Organizzazione 0

Organizzazione 7 Internet

Organizzazione 1

Provvedo-Io “Inviami tutto quello il cui indirizzo

inizia per 199.31.0.0/16 o 200.23.18.0/23”

200.23.20.0/23

Organizzazione 2

...

... Scappo-Con-La-Cassa

(46)

Indirizzi IP alla fonte

D: Ma come fa un ISP, a sua volta, a ottenere un blocco di indirizzi?

R: ICANN: Internet Corporation for Assigned Names and Numbers



Ha la responsabilità di allocare i blocchi di indirizzi.



Gestisce i server radice DNS.



Assegna e risolve dispute sui nomi di dominio.

(47)

Traduzione degli indirizzi di rete (NAT)

10.0.0.1

10.0.0.2

10.0.0.3 10.0.0.4

138.76.29.7

Rete locale

(es., rete domestica) 10.0.0/24

Internet globale

Spazio di indirizzi riservato alle reti private, molte delle quali

usano un identico spazio,

10.0.0/24 per scambiare pacchetti I router abilitati alla NAT non

appaiono al mondo esterno come router ma come un unico dispositivo

con un unico indirizzo IP.

Indirizzo IP origine: 138.76.29.7,

(48)

Traduzione degli indirizzi di rete (NAT)



Il router abilitato alla NAT nasconde i dettagli della rete domestica al mondo esterno



Non è necessario allocare un intervallo di indirizzi da un ISP: un unico indirizzo IP è sufficiente per tutte le macchine di una rete locale.



È possibile cambiare gli indirizzi delle macchine di una rete privata senza doverlo comunicare all’Internet

globale.



È possibile cambiare ISP senza modificare gli

indirizzi delle macchine della rete privata

(49)

Traduzione degli indirizzi di rete (NAT)

10.0.0.1

10.0.0.2

10.0.0.3

S: 10.0.0.1, 3345 D: 128.119.40.186, 80

1

10.0.0.4 138.76.29.7

1: l’host 10.0.0.1

invia il datagramma a 128.119.40.186, 80

138.76.29.7, 5001 10.0.0.1, 3345

…… ……

S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4

S: 138.76.29.7, 5001 D: 128.119.40.186, 80

2

2: il router NAT cambia l’indirizzo d’origine del datagramma da

10.0.0.1, 3345 a 138.76.29.7, 5001, e aggiorna la tabella.

S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3 3: la risposta arriva

all’indirizzo di destinazione:

138.76.29.7, 5001

4: il router NAT cambia l’indirizzo di destinazione del datagramma da

Tabella di traduzione NAT

Lato WAN LatoLAN

(50)

Traduzione degli indirizzi di rete (NAT)



Il campo numero di porta è lungo 16 bit:

 Il protocollo NAT può supportare più di 60.000

connessioni simultanee con un solo indirizzo IP sul lato WAN.



NAT è contestato perché:

 i router dovrebbero elaborare i pacchetti solo fino al livello 3.

 Viola il cosiddetto argomento punto-punto

• Interferenza con le applicazioni P2P, a meno che non sia

specificamente configurato per quella specifica applicazione P2P.

 Per risolvere la scarsità di indirizzi IP si dovrebbe usare IPv6.

(51)

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

 RIP

 OSPF

 BGP

Capitolo 4: Livello di rete

(52)

Internet Control Message Protocol (ICMP)

 Viene usato da host e router per scambiarsi informazioni a livello di rete.

 report degli errori: host, rete, porta, protocollo irraggiungibili.

 echo request/reply

(usando il programma ping).

 Livello di rete “sopra” IP:

 ICMP è considerato parte di IP.

 Messaggi ICMP: hanno un

campo tipo e un campo codice, e contengono l’intestazione e i primi 8 byte del datagramma IP.

Tipo Codice Descrizione

0 0 Risposta eco (a ping)

3 0 rete destin. irraggiungibile 3 1 host destin. irraggiungibile 3 2 protocollo dest. irraggiungibile 3 3 porta destin. irraggiungibile 3 6 rete destin. sconosciuta 3 7 host destin. sconosciuto 4 0 riduzione (controllo

di congestione) 8 0 richiesta eco

9 0 annuncio del router 10 0 scoperta del router 11 0 TTL scaduto

12 0 errata intestazione IP

(53)

Traceroute e ICMP

 Il programma invia una serie di datagrammi IP alla

destinazione.

 Il primo pari a TTL =1

 Il secondo pari a TTL=2, ecc.

 Numero di porta improbabile

 Quando l’n-esimo datagramma arriva all’n-esimo router:

 Il router scarta il datagramma.

 Invia all’origine un messaggio di allerta ICMP (tipo 11,

codice 0).

 Il messaggio include il nome

 Quando il messaggio ICMP arriva, l’origine può calcolare RTT

Criteri di arresto dell’invio

 Quando un segmento UDP arriva all’host di destinazione.

 L’host di destinazione

restituisce un messaggio ICMP di porta non raggiungibile (tipo 3, codice 3).

 Quando l’origine riceve questo messaggio ICMP, si blocca.

(54)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

 RIP

 OSPF

 BGP

(55)

IPv6

 Esigenza principale: lo spazio di

indirizzamento IP a 32 bit stava incominciando a esaurirsi.

 Altre motivazioni:



Il formato dell’intestazione aiuta a rendere più veloci i processi di elaborazione e inoltro



Agevolare la QoS.

Formato dei datagrammi IPv6:



Intestazione a 40 byte e a lunghezza fissa.

(56)

Formato dei datagrammi IPv6

Priorità di flusso: attribuisce priorità a determinati datagrammi di un flusso.

Etichetta di flusso: identifica i pacchetti che appartengono a flussi particolari (anche se non è ben chiaro il concetto di “flusso”).

Intestazione successiva: identifica il protocollo cui verranno consegnati i contenuti del datagramma.

(57)

Altre novità di IPv6



Checksum : i progettisti hanno deciso di rimuoverla dal livello di rete in quanto risultava ridondante.



Opzioni: non fa più parte dell’intestazione IP

standard. Il campo non è del tutto scomparso ma è diventato una delle possibili “intestazioni

successive” cui punta l’intestazione di IPv6.



ICMPv6: nuova versione di ICMP:

 Ha aggiunto nuovi tipi e codici, es. “Pacchetto troppo grande”.

 Assume le funzionalità dell’IGMP, e gestisce l’ingresso e l’uscita di host nei gruppi multicast.

(58)

Passaggio da IPv4 a IPv6

 Non è possibile aggiornare simultaneamente tutti i router:



Impossibile dichiarare una “giornata campale” in cui tutte le macchine Internet verranno spente e

aggiornate da IPv4 a IPv6.



Come riuscirà la rete a funzionare in presenza di router IPv4 e IPv6?

 Tunneling: IPv6 viene trasportato come

payload in datagrammi IPv4 quando attraversa

router IPv4

(59)

Tunneling

A B E F

IPv6 IPv6 IPv6 IPv6

tunnel

Vista logica:

Vista fisica: A B E F

IPv6 IPv6 IPv6 IPv6

C D

IPv4 IPv4

Flusso: X Orig.: A Dest: F

dati

dati Flusso: X

Orig.: A Dest: F

dati

Orig.:B Dest: E

dati

Orig.:B Dest: E

Da A a B: Da E a F:

(60)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

(61)

1

3 2

0111

valore nell’intestaz.

del pacchetto entrante

Tabella d’instrad. locale Val. intestaz. link in usc.

0100 0101 0111 1001

3 2 2 1

Algoritmi d’instradamento

(62)

u

x

y

w v

2

z

2

1 3

1

2 3 5

5

Grafo: G = (N,E)

N = insieme di nodi = { u, v, w, x, y, z }

E = insieme di archi ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Grafo di una rete di calcolatori

N.B.: Il grafo è un’astrazione utile anche in altri contesti di rete

Esempio: P2P, dove N è un insieme di peer ed E è un insieme di collegamenti TCP

(63)

Grafo di una rete : costi

u

x

y

w v

2

z

2

1 3

1

2 3 5

5 • c(x,x’) = costo del collegamento (x,x’) - es., c(w,z) = 5

• il costo di un cammino è

semplicemente la somma di tutti i costi degli archi lungo il cammino

Costo di un cammino (x₁, x₂, x₃,…, x_p) = c(x₁,x₂) + c(x₂,x₃) + … + c(x_p-1,x_p) Domanda: Qual è il cammino a costo minimo tra u e z ?

Algoritmo d’instradamento: determina il cammino a costo minimo.

(64)

Classificazione degli algoritmi d’instradamento

Globale o decentralizzato?

Globale:

 L’algoritmo riceve in ingresso tutti i collegamenti tra i nodi e i loro costi.

 Algoritmi a stato del collegamento (link-state algorithm).

Decentralizzato:

 Ogni nodo elabora un vettore di stima dei costi (distanze) verso tutti gli altri nodi nella rete.

 Il cammino a costo minimo viene calcolato in modo distribuito e iterativo.

 Algoritmo a vettore distanza (VC, distance-vector algorithms)

Statico o dinamico?

Statico:

 I cammini cambiano molto raramente.

Dinamico:

 Determinano gli instradamenti al variare di:

 Volume di traffico

 Topologia della rete

(65)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

(66)

Algoritmo d’instradamento a stato del collegamento (LS)

Algoritmo di Dijkstra:

 La topologia di rete e tutti i costi dei collegamenti sono noti a tutti i nodi

 attraverso il “link-state broadcast”.

 tutti i nodi dispongono delle stesse informazioni

 Calcola il cammino a costo minimo da un nodo (origine) a tutti gli altri nodi della rete.

 Crea una tabella d’inoltro per quel nodo

 È iterativo: dopo la k-esima iterazione i cammini a costo minimo sono noti a k nodi di

Definiamo la seguente notazione:

 c(x,y): costo del collegamenti dal nodo x al nodo y; = ∞ se non sono adiacenti.

 D(v): costo del cammino dal nodo origine alla destinazione v per quanto riguarda

l’iterazione corrente.

 p(v): immediato predecessore di v lungo il cammino.

 N': sottoinsieme di nodi per cui il cammino a costo minimo

dall’origine è definitivamente noto.

(67)

Algoritmo di Dijsktra

1 Inizializzazione:

2 N' = {u}

3 per tutti i nodi v

4 se v è adiacente a u 5 allora D(v) = c(u,v) 6 altrimenti D(v) = ∞ 7

8 Ciclo

9 determina un w non in N' tale che D(w) sia minimo 10 aggiungi w a N'

11 aggiorna D(v) per ciascun nodo v adiacente a w e non in N' : 12 D(v) = min( D(v), D(w) + c(w,v) )

13 /* il nuovo costo verso v è il vecchio costo verso v oppure

14 il costo del cammino minimo noto verso w più il costo da w a v */

(68)

Algoritmo di Dijkstra: esempio

passo 0 1 2 3 4 5

N' u ux uxy uxyv uxyvw uxyvwz

D(v),p(v) 2,u 2,u 2,u

D(w),p(w) 5,u 4,x 3,y 3,y

D(x),p(x) 1,u

D(y),p(y)

∞ 2,x

D(z),p(z)

∞ ∞

4,y 4,y 4,y

u

x

w v

z

2

1 3 1

2 3 5

5

(69)

Algoritmo di Dijkstra: un altro esempio

u

x

y

w v

z

Cammino a costo minimo da u:

xv y

(u,v) (u,x) (u,x)

destinazione collegamento Tabella d’inoltro in u:

(70)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

(71)

Algoritmo d’instradamento con vettore distanza (DV)

Formula di Bellman-Ford (programmazione dinamica) definisce

d

x

(y) := il costo del percorso a costo minimo dal nodo x al nodo y .

Allora:

d

x

(y) = min {c(x,v) + d

v

(y) }

dove min riguarda tutti i vicini di x .

v

(72)

Formula di Bellman-Ford: esempio

u

x

y

w v

2

z

2

1 3

1

2 3 5

5 Chiaramente, d_v(z) = 5, d_x(z) = 3, d_w(z) = 3

d_u(z) = min { c(u,v) + d_v(z), c(u,x) + d_x(z), c(u,w) + d_w(z) } = min {2 + 5,

1 + 3,

5 + 3} = 4 L’equazione B-F definisce:

(73)

Algoritmo con vettore distanza



D

x

(y) = stima del costo del percorso a costo minimo da se stesso al nodo y .



Vettore distanza: D

_x

= [D

_x

(y): y є N ]



Il nodo x conosce il costo verso ciascun vicino v:

c(x,v)



Il nodo x mantiene D

x

= [D

x

(y): y є N ]



Il nodo x mantiene anche i vettori distanza di ciascuno dei suoi vicini

 Per ciascun vicino v, x mantiene Dv = [Dv(y): y є N ]

(74)

Algoritmo con vettore distanza

Idea di base:

 Ogni nodo invia una copia del proprio vettore distanza a ciascuno dei suoi vicini.

 Quando un nodo x riceve un nuovo vettore distanza, DV, da qualcuno dei sui vicini, lo salva e usa la formula B-F per

aggiornare in proprio vettore distanza come segue:

D

_x

(y) ← min

_v

{c(x,v) + D

_v

(y)} per ciascun nodo y in N.

 Finché tutti i nodi continuano a cambiare i propri DV in

maniera asincrona, ciascuna stima dei costi Dx(y) converge a dx(y).

(75)

Algoritmo con vettore distanza

Iterativo, asincrono:

^ogni

iterazione locale è causata da:

 cambio del costo di uno dei collegamenti locali.

 Ricezione da qualche vicino di un vettore distanza

aggiornato.

Distribuito:

 Ogni nodo aggiorna i suoi vicini solo quando il suo DV cambia.

 i vicini avvisano i vicini solo se necessario.

Attende

(un messaggio del cambio del costo da parte del suo vicino )

Effettua il calcolo

Se il DV cambia,

lo

notifica

ai suoi vicini.

Ciascun nodo:

(76)

x y z x

y z

0 2 7

∞ ∞ ∞

da

costo verso

da

x y z x

y z

0 2 3

da

costo verso

x y z x

y z

0 2 3

da

costo verso

x y z x

y z

∞ ∞

∞ ∞ ∞

costo verso

x y z x

y z

0 2 7

da

costo verso

x y z x

y z

0 2 3

da

costo verso

x y z x

y 0 2 3

costo verso

x y z x

y 0 2 7

costo verso

x y z x

y ∞∞ ∞

costo verso

∞2 0 1

∞ ∞ ∞

2 0 1 7 1 0

2 0 1

2 0 1 3 1 0

2 0 1

2 0 1 3 1 0

x ² ₇ ¹

z

y

Tabella del nodo x

Tabella del nodo y

Tabella del nodo z

D_x(y) = min{c(x,y) + D_y(y), c(x,z) + D_z(y)}

= min{2+0 , 7+1} = 2

D_x(z) = min{c(x,y) + D_y(z), c(x,z) + D_z(z)}

= min{2+1 , 7+0} = 3

(77)

Algoritmo con vettore distanza:

modifica dei costi

Modifica dei costi:

 Un nodo rileva un cambiamento nel costo dei collegamenti.

 Aggiorna il proprio vettore distanza.

 Se si verifica un cambiamento nel costo, trasmette ai suoi vicini il nuovo DV.

x z

1 4

50 1 y

All’istante t₀, y rileva il cambiamento nel costo del collegamento, aggiorna il proprio DV e informa i vicini del cambiamento.

All’istante t₁, z riceve l’aggiornamento da y e aggiorna la propria tabella, calcola un nuovo costo minimo verso x e invia il nuovo DV ai vicini.

All’istante t₂, y riceve l’aggiornamento di z e aggiorna la propria tabella di distanza. I costi minimi di y non cambiano e y non manda alcun messaggio a z.

(78)

Algoritmo con vettore distanza:

modifica dei costi

Modifica dei costi:

 Le buone notizie (costo diminuito) si sono propagate rapidamente.

 Le cattive notizie si propagano lentamente:

problema dell’instradamento ciclico!

 44 iterazioni prima che l’algoritmo di stabilizzi (esempio nel testo pp. 312-313)

x z

4 1

50 60 y

Inversione avvelenata:

 Se Z instrada tramite Y per giungere alla

destinazione X :

 Allora Z avvertirà Y che la sua distanza verso X è infinita (così Y non tenterà mai d’instradare verso X passando per Z)

L’inversione avvelenata può

(79)

Confronto tra gli algoritmi LS e DV

Complessità dei messaggi:

 LS: con n nodi, E collegamenti, implica l’invio di O(nE) messaggi.

 DV: richiede scambi tra nodi adiacenti.

 Il tempo di convergenza può variare.

Velocità di convergenza:

 LS: l’algoritmo O(n²) richiede O(nE) messaggi.

 ci possono essere oscillazioni di velocità.

 DV: può convergere lentamente.

 può presentare cicli d’instradamento.

 può presentare il problema del conteggio all’infinito.

Robustezza: cosa avviene se un router funziona male?

LS:

 un router può comunicare via broadcast un costo sbagliato per uno dei suoi collegamenti connessi (ma non per altri).

 i nodi si occupano di calcolare soltanto le proprie tabelle.

DV:

 un nodo può comunicare

cammini a costo minimo errati a tutte le destinazioni.

 la tabella di ciascun nodo può essere usata degli altri.

• Un calcolo errato si può diffondere per l’intera rete.

(80)

Capitolo 4: Livello di rete

4. 1 Introduzione

4.2 Reti a circuito virtuale e a datagramma

4.3 Che cosa si trova

all’interno di un router?

4.4 Protocollo Internet (IP)

 ICMP

 IPv6

4.5 Algoritmi di instradamento

4.6 Instradamento in Internet

 RIP

 OSPF

 BGP

4.7 Instradamento

(81)

Instradamento gerarchico

Scala: con 200 milioni di destinazioni:

 Archiviare le informazioni

d’instradamento su ciascun host richiederebbe un’enorme quantità di memoria.

 Il traffico generato dagli

aggiornamenti LS non lascerebbero banda per i pacchetti di dati!

Autonomia amministrativa:

 Internet = la rete delle reti

 Da un punto di vista ideale, ciascuno dovrebbe essere in

grado di amministrare la propria rete nel modo desiderato, pur mantenendo la possibilità di connetterla alle reti esterne.

Abbiamo fin qui visto la rete come una collezione di router interconnessi

 Ciascun router era indistinguibile dagli altri

 Visione omogenea della rete

… nella pratica le cose non sono così semplici

(82)

Instradamento gerarchico

 Organizzazione di router in sistemi autonomi (AS,

autonomous system).

 I router di un gruppo autonomo eseguono lo stesso algoritmo

d’instradamento.

 Protocollo d’instradamento interno al sistema

autonomo (intra-AS).

 I router appartenenti a differenti AS possono eseguire protocolli

d’instradamento intra-AS

Router gateway

 Hanno il compito aggiuntivo d’inoltrare pacchetti a

destinazioni esterne.

(83)

3b

1d 3a

1c 2a

AS3

AS1 1a AS2

2c 2b

1b

(intra-AS)

Tabella d’inoltro

3c

Sistemi autonomi interconnessi

 Ciascun sistema autonomo sa come inoltrare pacchetti lungo il percorso ottimo verso

qualsiasi destinazione interna al gruppo

 I sistemi AS2 e AS3 hanno tre router ciascuno

 I protocolli d’instradamento dei tre sistemi autonomi non sono necessariamente gli stessi