Corso di Reti di Calcolatori
A.A. 2005-2006
Prof. D. Rosaci
Capitolo Quarto:
Il livello di Rete
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Il livello di Rete






Si occupa di tramettere pacchetti dalla sorgente alla destinazione
Per raggiungere la destinazione può essere necessario
attraversare lungo il percorso diversi router indipendenti
Questa funzione è chiaramente diversa dal livello data link, che ha
il compito più modesto di trasportare pacchetti da un estremo a un
altro di un cavo
E’ il livello più basso che si occupa di trasmissioni punto-a-punto
Il livello di rete deve conoscere la topologia della rete e deve
scegliere livelli appropriati attraverso essa
I percorsi devono essere scelti in modo da non sovraccaricare
alcune linee e nodi di comuncazione, lasciandone inutilizzati altri
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Servizi offerti al livello di trasporto



I servizi devono essere indipendenti dalla
tecnologia della rete
Il livello trasporto deve essere indipendente
dal numero, dal tipo e dalla topologia delle
reti presenti
Gli indirizzi di rete disponibili al livello
trasporto devono utilizzare uno scehma di
numerazione uniforme, anche attraverso
LAN e WAN diverse
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Servizi Connection-Oriented o
Connectionless? - 1




Punto di vista della comunità Internet: il compito di una rete è
quella di trasportare bit e nient’altro. Le reti sono
intrinsecamente inaffidabili r quindi gli host dovrebbero
eseguire loro stessi controlli di errore e di flusso.
Il servizio dovrebbe quindi essere connectionless, con primitive
SEND PACKET e RECEIVE PACKET e poco altro.
Non si dovrebbero eseguire né ordinamento di pacchetti né
controllo di flusso, ed ogni pacchetto dovrebbe contenere
l’indirizzo di destinazione completo, in quanto viaggia
indipendentemente dai suoi predecessori
Ci si ispira al sistema postale
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Servizi Connection-Oriented o
Connectionless? - 2




Punto di vista delle società telefoniche (es. ATM): Le reti
dovrebbero fornire un servizio orientato alla connessione
affidabile, ispirandosi al sistema telefonico.
Prima di spedire dati, un processo a livello di rete lato sender
dovrebbe stabilire una connessione col receiver
Quindi, i processi dovrebbero instaurare una negoziazione su
parametri, costi e qualità del servizio
La comunicazione è bidirezionale, i pacchetti vengono
consegnati in sequenza e viene effettuato un controllo di flusso
per evitare che un mittente veloce sovraccarichi un ricevente
lento
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Servizi Connection-Oriented o
Connectionless? - 3




Nei servizi orientati alla connessione, la complessità
risiede nel livello di rete
Nei servizi senza connessione, la complessità
risiede nel livello di trasporto (host)
I sostenitori del connectionless affermano che ormai
il costo della potenza di calcolo a livello host è
diventato economico
I sostenitori del connection-oriented affermano che
molti utenti non desiderano eseguire sulle loro
macchine complessi protocolli del livello trasporto
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Circuiti Virtuali




Una connessione in una rete a servizi orientati alla
connessione viene chiamata circuito virtuale.
L’idea è quella di evitare di dover scegliere un nuovo
percorso per ogni pacchetto spedito
Quando viene stabilita una connessione, il percorso
è memorizzato una volta per tutte
Quando la connessione viene rilasciata, anche il
circuito virtuale viene chiuso
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Datagrammi




I pacchetti idipendenti dall’organizzazione senza
connessione, vengono chiamati datagram, in
analogia con i telegrammi
In una rete basata su datagrammi non viene
calcolato anticipatamente nessun percorso
Pacchetti successivi possono seguire percorsi
differenti
Queste reti devono lavorare di più, ma sono più
robuste e si adattano facilmente ai guasti e alle
congestioni
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Confronto:
Caratteristica
Reti basate su datagrammi
Reti basate su circuito
virtuale
Creazione circuito
Non richiesto
Richiesto
Indirizzamento
Ogni pacchetto contiene gli
indirizzi sorgente e
destinazione completi
ogni pacchetto contiene un
piccolo numero di circuito
virtuale
Informazioni di stato
La sottorete non ne conserva
Ogni circuito virtuale richiede
spazio di tabella nella
sottorete
Instradamento
Ogni pacchetto è instradato
indipendentemente
Percorso scelto alla creazione
del circuito virtuale
Effetto dei guasti nei router
Nessuno, a parte i pacchetti
persi durante il guasto
Tutti i circuiti virtuali che
passano attraverso il guasto
vengono terminati
Controllo di congestione
complesso
Semplice, se può essere
allocato spazio sufficiente in
anticipo per ogni CV
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Routing



E’ quella parte del software del livello di rete che ha
la responsabilità di decidere su quale linea di output
trasmettere i pacchetti in arrivo
Se la rete utilizza i datagram, questa decisione deve
essere eseguita nuovamente per ogni pacchetto di
dati
Se la rete utilizza i circuiti virtuali, questa decisione è
presa una volta per tutte, all’atto di stabilire una
connessione (routing di sessione)
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Prorietà degli Algoritmi di Routing






Semplicità
Correttezza
Robustezza: capacità di resistere ai guasti
Stabilità: l’algoritmo dovrebbe convergere ad
uno stato di equilibrio
Imparzialità
Ottimalità
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Cosa ottimizzare?




Minimizzazione del ritardo medio del pacchetto
Massimizzazione del volume di dati trasmesso
dall’intera rete
Goal in conflitto: gestire un sistema a coda al limite
della capacità implica ritardi nella formazione delle
code
Compromesso: minimizzare il numero di salti che un
pacchetto deve attraversare, facendo diminuire i
ritardi e quindi la quantità di banda consumata, che
porta anche a migliorare la capacità globale della
rete
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Classi di algoritmi di routing


Algoritmi non adattativi:
Algoritmi adattativi
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmi non adattativi

Non basano le decisioni di routing su
misurazioni o stime del traffico corrente e
della topologia. La scelta del percorso da
usare per andare da I a J (per ogni I e J) è
calcolata in anticipo, off line, e copiata nei
router quando la rete viene fatta partire
(routing statico)
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmi adattativi

Modificano le decisioni di routing a seconda
dei cambiamenti nella topologia e nel traffico
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmi statici



Routing lungo il cammino minimo
Flooding
Routing basato su flusso
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing lungo il cammino minimo


Si costruisce un grafo della rete, dove ogni
nodo rappresenta un router ed ogni arco
rappresenta un canale di comunicazione
Un algoritmo molto noto per il calcolo del
cammino minimo è quello di Dijkstra (1959)
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Dijkstra - 1
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Dijkstra - 2







Ogni noto è etichettato in parentesi con la sua
distanza lungo il miglior cammino conosciuto
Inizialmente tutti i nodi sono etichettati con infinito
Mentre l’algoritmo procede le etichette possono
cambiare riflettendo cammini migliori
Un’etichetta può essere o un tentativo o permanente
Inizialmente ogni etichetta è un tentativo
Quando si scopre che un’etichetta rappresenta il
cammino più breve possibile viene resa permanente
I pesi sugli archi rappresentano le distanze
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Dijkstra - 3
•Cammino più breve da A a D
•Marchiamo il nodo A come permanente, con un nodo nero
•Esaminiamo ogni nodo adiacente ad A (il nodo attivo), etichettando
ognuno con la sua distanza da A
•Ogni volta che un nodo è rietichettato, si aggiunge all’etichetta il nodo a
partire dal quale è stata fatta l’indagine, per poter ricostruire il percorso
alla fine
•Dopo aver esaminato tutti gli adiacenti, rendiamo permanente quello
con etichetta minima (B, nell’esempio), che diventa il nuovo nodo attivo
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Dijkstra - 4
•A questo punto, partendo da B, si esaminino tutti i nodi adiacenti ad
esso. Se la somma dell’etichetta di B e della distanza di B dal nodo che si
sta considerando è minore dell’etichetta associata al nodo, il cammino
ispezionato è più breve e quindi il nodo viene rietichettato (vedi E e C)
•Dopo aver ispezionato tutti i nodi adiacenti al nodo attivo e possibilmente
dopo aver cambiato le etichette di tentativo, si cerca nell’intero grafo il
nodo con il valore minore (E), che diventa il nuovo nodo attivo per il
prossimo round
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Algoritmo di Dijkstra - 5
• Supponiamo esista un cammino più corto di ABE, diciamo AXY..ZE. Due
possibilità. (a) Z è permanente: allora E è stato già ispezionato e quindi il
cammino AXY…ZE non è potuto sfuggire alla nostra attenzione; (b) Z è
etichettato come tentativo: O l’etichetta di Z è più grande di quella di E,
nel qual caso AXY..ZE non può essere un cammino più breve di ABE,
oppure è minore di quella di E, nel qual caso Z (e non E) diventerà
permanente per primo, consentendo ad E di essere indagato da Z
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing Dinamico: Rounting basato su
vettori di distanza - 1



Ogni router mantiene una tabella (tabella di
routing) contenente, per ogni destinazione, la
migliore distanza conosciuta e quale canale
utilizzare per raggiungerla
Queste tabelle sono aggiornate scambiando
informazioni con i vicini
L’algoritmo è noto come Distance Vector
Routing, oppure Bellman-Ford o Ford e
Fulkerson
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing Dinamico: Routing basato su
vettori di distanza - 2



Ogni router conosce la distanza dei suoi vicini (ad
esempio, come metrica si può usare il ritardo del
ritorno di un pacchetto speciale ECHO)
Una volta ogni T ms, il router X spedisce ai suoi
vicini una lista dei ritardi stimati per ogni
destinazione, e riceve una lista simile da ogni vicino
Supponiamo che una di queste liste provenga dal
vicino Y, e che YI sia la stima fatta da Y per la
destinazione I. Se X sa che il ritardo di Y è m, allora
può stimare che può raggiungere I attraverso X in un
tempo YI +m.
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing Dinamico: Routing basato su
vettori di distanza - 3
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing Adattativo: Routing basato
sullo stato dei canali - 1

1.
2.
3.
4.
5.
Ogni router deve:
Scoprire i propri vicini e il loro indirizzi di rete
Misurare il ritardo o il costo di ogni vicino
Costruire un pacchetto contenente tutto quello che
ha scoperto
Spedire questo pacchetto a tutti i router
Calcolare il cammino minimo per ogni altro router
(usando Dijkstra)
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Routing gerarchico




Con la crescita delle dimensioni della rete, le tabelle di routing
crescono proporzionalmente
I router possono essere suddivisi in regioni
Ogni router conosce tutti i dettagli su come instradare pacchetti
all’interno della propria regione, ma ignora la struttura delle
altre regioni
Esempio: Un pacchetto deve andare da Berkeley (California)
fino a Malindi (Kenya). Il router Berkeley sa instradare solo
all’interno della California, mentre il traffico extrastatale è
spedito a Los Angeles. Il router Los Angeles sa instradare verso
altre destinazioni nazionali, mentre il traffico estero è spedito al
router New York. New York potrebbe spedire ogni pacchetto
con destinazione kenyana a Nairobi, e il router Nairobi sarebbe
in grado di instradare verso Malindi
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Il livello di Rete in Internet




Dal punto di vista del livello di rete, Internet può
essere visto come una collezione di sottoreti
connesse insieme
Esistono molte backbone (dorsali) basate su canali
ad alta velocità e router veloci
Alle backbone vengone connesse reti regionali e
collegate a queste ultime vi sono le LAN di
università, società e fornitori di servizi internet
La colla che tiene unita internet è il protocollo del
livello di rete: l’Internet Protocol (IP)
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Funzionamento del livello di Rete




Il livello di trasporto riceve un flusso di dati e lo
frammenta in datagram
Ogni datagram viene trasmesso attraverso Internet,
possibilmente frammentato in segmenti più piccoli
durante la destinazione
Quando tutti i pezzi raggiungono la destinazione,
vengono riassemblati dal livello di Rete nel datagram
originale
Questo datagram viene poi passato al livello
trasporto, che lo inserisce nel flusso di input del
processo ricevente
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Il protocollo IP



Un datagram IP consiste in un preambolo e
in una parte testo.
Il preambolo ha una parte fissa di 20 byte ed
una parte opzionale di lunghezza variabile
Viene trasmesso in formato big endian, da
sinistra verso destra
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Il preambolo IP
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Campi del preambolo IP - 1






Version: descrive la versione del protocollo
IHL: lunghezza del preambolo, in parole di 32 bit (valore
massimo 15, quindi al massimo il preambolo può essere lungo
60 byte)
Type of service: tipo di servizio desiderato (es. ricezione rapida,
ricezione accurata, ecc.)
Total length:lunghezza totale del datagram (preambolo più dati:
lunghezza massima 65.535 byte)
Identification: serve per permettere all’host destinazione di
determinare a quale datagram appartiene il frammento
1 bit inutilizzato
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Campi del preambolo IP - 2






DF: sta per don’t fragment
MF: sta per more fragments: tutti i frammenti hanno
questo bit pari a 1, tranne l’ultimo. Serve per
determinare quando l’ultimo frammento è arrivato
Fragment offset: posizione del frammento nel
datagram corrente
Time to live: serve a limitare la vita dei pacchetti
Protocol: indica a quale processo del trasporto il
datagram deve essere consegnato (TCP,UDP)
Header Checksum: verifica errori interni al
preambolo
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Campi del preambolo IP - 3



Source Address: identificatore di rete
Destination Address: identificatore di host
Options
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Indirizzi IP


Ogni host e router in Internet ha un indirizzo IP
Tutti gli indirizzi IP sono lunghi 32 bit
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Classi di Reti





Gli indirizzi di classe A generano 126 reti con 16
milioni di host ognuna
Gli indirizzi di classe B generano 16382 reti con
64000 host ognuna
Gli indirizzi di classe C generano 2 milioni di reti con
254 host ognuna (es. LAN)
Gli indirizzi di classe D generano un insieme di
indirizzi multicast nei quali un datagram viene
indirizzato a più host
Gli indirizzi di classe E sono riservati a scopi futuri
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Ancora sugli indirizzi IP


Sono assegnati dal Network Information
Center (NIC)
Sono espressi in notazione decimale a punti,
dove ognuno dei 4 byte dell’indirizzo è
espresso da un numero che va da 0 a 255
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Problemi connessi con IP




IP ha funzionato molto bene, come dimostra la crescita
esponenziale di Internet, ma a causa di ciò sta esaurendo gli
indirizzi
Teoricamente esisterebbero oltre 4 miliardi di indirizzi, ma la
pratica di organizzare lo spazio di indirizzamento in classi ne
spreca milioni
Il problema sono gli indirizzi di classe A (reti troppo grandi, con
16 milioni di indirizzi) e di classe C (reti troppo piccole con 256
indirizzi). Le reti di classe B, andrebbero bene per la maggior
parte dei casi (reti con al massimo 65536 indirizzi) ma
comunque sono ancora troppo grandi per moltissime
organizzazioni
Sarebbe stato meglio avere una classe C con 10 bit invece che
8
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Una soluzione temporanea: CIDR



Classless InterDomain Routing)
Le reti di classe C rimaste vengono allocate
in blocchi di dimensione variabile
Se un sito necessita di 2000 indirizzi, gli si
assegnano otto reti di classe C contigue
invece di un indirizzo completo di classe B
D. Rosaci
Corso di Reti di Calcolatori
Capitolo Quarto
Il futuro: IPv6



IPv6 rappresenta la versione 6 dell'Internet Protocol.
IPv6 è stato disegnato per sostituire il precedente standard
IPv4, che gestisce soltanto fino a circa 4 miliardi di indirizzi,
mentre IPv6 gestisce fino a circa 3,4 × 1038 indirizzi. Ciò è
equivalente a 280.000.000.000.000.000 indirizzi unici per ogni
metro quadrato della superficie terrestre.
Il 20 luglio 2004 l'ICANN ha annunciato che i root server DNS
erano stati modificati per supportare sia il protocollo IPv6 che
IPv4. Il protocollo IPv4 dovrebbe essere ancora utilizzato fino al
2025 circa, per dare il tempo necessario a gestire il periodo di
transizione.