Corso di Reti di Calcolatori A.A. 2005-2006 Prof. D. Rosaci Capitolo Quarto: Il livello di Rete.

Corso di Reti di CalcolatoriA.A. 2005-2006Prof. D. Rosaci

Capitolo Quarto:

Il livello di Rete

D. RosaciCorso 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


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


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



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



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


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


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


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


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)


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à


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


Classi di algoritmi di routing

Algoritmi non adattativi: Algoritmi adattativi


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)


Algoritmi adattativi

Modificano le decisioni di routing a seconda dei cambiamenti nella topologia e nel traffico


Algoritmi statici

Routing lungo il cammino minimo Flooding Routing basato su flusso


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)


Algoritmo di Dijkstra - 1



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



•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



•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



• 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


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


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.


Routing Dinamico: Routing basato su vettori di distanza - 3


Routing Adattativo: Routing basato sullo stato dei canali - 1

Ogni router deve:

1. Scoprire i propri vicini e il loro indirizzi di rete

2. Misurare il ritardo o il costo di ogni vicino

3. Costruire un pacchetto contenente tutto quello che ha scoperto

4. Spedire questo pacchetto a tutti i router

5. Calcolare il cammino minimo per ogni altro router (usando Dijkstra)


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


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)


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


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


Il preambolo IP


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



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



Source Address: identificatore di rete Destination Address: identificatore di host Options


Indirizzi IP

Ogni host e router in Internet ha un indirizzo IP Tutti gli indirizzi IP sono lunghi 32 bit


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


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


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


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


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.

Corso di Reti di Calcolatori A.A. 2005-2006 Prof. D. Rosaci Capitolo Quarto: Il livello di Rete.

Documents

Transcript of Corso di Reti di Calcolatori A.A. 2005-2006 Prof. D. Rosaci Capitolo Quarto: Il livello di Rete.