Retistekandaloro.altervista.org/blog/wp-content/uploads/2015/09/reti-1.pdfReti di Computer Si...

Programma● Architettura di un router● Configurare un router● Routing ● Topologia delle reti● Algoritmi di routing● Strato di trasporto

● Protocolli UDP e TCP

● Strato applicativo● Protocollo Telnet● Protocolli WEB, HTTP, FTP● DNS

La storia...

Già negli anni sessanta, in America, fu progettato il primo esempio di rete informatica dal Dipartimento della Difesa, per facilitare lo scambio di informazioni da un punto all’altro. Infatti la prima applicazione viene dal campo militare; poi negli anni a seguire anche strutture come le Università adoperarono questo nuovo tipo di tecnologia.

La storia

Definizione

● Una rete di computer è un insieme eterogeneo di dispositivi che, tramite delle schede di interfacciamento, comunicano tra loro tramite:

– Cavo telefonico– Fibra ottica– WI-FI– Satelitte

● L'obiettivo di una rete è il trasferimento dati.● Nota: la rete è divisa in:

– Componenti fisiche

– Software

– Dati

Definizione

Reti Mainframe

● Agli inizi degli anni '60 le reti di erano tutte costruite con al centro un computer molto potente chiamato 'mainframe'. Infatti una serie di terminali erano collegati allo stesso sistema centrale e ne condividevano le informazioni e il software. Tanti computer anche se potenti non potevano eguagliare le prestazioni di una rete così costruita.

● Nota: i terminali erano definiti stupidi

Reti Mainframe

Reti di Computer

● I Pc diventano competitivi nei confronti di una rete con sistema centrale solo se sono collegati tra loro in rete. Infatti ora è la rete che diventa il centro di condivisione e non un unico mainframe. Quindi nel tempo si è passato dal modello mainframe-terminali al modello attuale in cui vi è un gran numero di Pc autonomi e interconnessi:● Autonomi: non esiste tra loro una relazione

master/slave● Interconnessi: sono tutti collegati tra loro grazie ad

un mezzo fisico

Reti di computer

● Nota: i terminali ora sono definiti intelligenti

Reti di Computer

● Si possono indicare almeno tre punti di forza di una rete di calcolatori rispetto al mainframe tradizionale:

– fault tolerance (resistenza ai guasti): il guasto di una macchina non blocca tutta la rete, ed è possibile sostituire il computer guasto facilmente (la componentistica costa poco e un'azienda può permettersi di tenere i pezzi di ricambio in magazzino);

– economicità: come accennato sopra, hardware e software per computer costano meno di quelli per i mainframe;

– gradualità della crescita e flessibilità (scalabilità): l'aggiunta di nuove potenzialità a una rete già esistente e la sua espansione sono semplici e poco costose.

Reti di Computer● Tuttavia una rete mostra alcuni punti deboli

rispetto a un mainframe:– scarsa sicurezza: un malintenzionato può avere accesso

più facilmente ad una rete di computer che ad un mainframe: al limite gli basta poter accedere fisicamente ai cablaggi della rete. Inoltre, una volta che un worm abbia infettato un sistema della rete, questo si propaga rapidamente a tutti gli altri e l'opera di disinfezione è molto lunga, difficile e non offre certezze di essere completa;

– alti costi di manutenzione: con il passare del tempo e degli aggiornamenti, e con l'aggiunta di nuove funzioni e servizi, la struttura di rete tende ad espandersi e a diventare sempre più complessa, e i computer che ne fanno parte sono sempre più eterogenei, rendendo la manutenzione sempre più costosa in termini di ore lavorative.

Reti di Computer

Oltre un certo limite di grandezza della rete (circa 50 computer) diventa necessario eseguire gli aggiornamenti hardware e software su interi gruppi di computer invece che su singole macchine, vanificando in parte il vantaggio dei bassi costi dell'hardware.

Client-Server

● Il termine server (servitore), indica genericamente un componente informatico che fornisce, a livello logico e a livello fisico, un qualunque tipo di servizio ad altre componenti (tipicamente chiamate client, cioè "cliente") attraverso una rete di computer. Al termine server, così come per il termine client, possono dunque riferirsi sia la componente hardware che la componente software.

Client-Server

● La figura schematizza appunto un sistema client-server. In questo modello la comunicazione ha la forma di messaggio, cioè un insieme di caratteri e dati che devono essere trasferiti da un sistema all'altro.

Client-Server

● Quindi possiamo classificare le reti come:– Client-server: alcuni dispositivi fungono da client e uno o

più da server. Il server ha il compito di:– Condividere i dati– Condividere i dispositivi– Proteggere la rete

I diversi utenti hanno diverse autorizzazioni per l'accesso e l'utilizzo della rete (dovrà esistere l'amministratore di rete), ognuno avrà il proprio dominio di directory. Questo tipo di rete offre i seguenti vantaggi:

– Sicurezza (come nei mainframe...)– Facilità nella condivisione degli stessi dati da parte di più

utenti– Gestione multiutenza

Reti Peer-to-peer e Ibride

– Peer-to-peer: non ci sono sistemi centrali, ma chiunque può condividere dati. Logicamente i costi sono minori, a scapito della sicurezza. Non posso avere molti utenti. Le reti peer-to-peer sono organizzati in gruppi di lavoro (workgroup).

– Ibride: prevedono l'uso di entrambe le tecnologie appena spiegate.

LAN● Una rete può essere costruita tra dispositivi

situati nella stessa stanza o in ambienti relativamente piccoli o essere estesa su più ampie zone geografiche.

● Classifichiamo le reti quindi come:– LAN (local area network): si usano per condividere dati

all'interno di una piccola azienda o di un ufficio. Possiamo condividere dispositivi come stampanti e le prestazioni sono ottime viste le ridotte distanze. Non hanno bisogno di grandi sistemi diagnostici. Abbiamo un'alta tolleranza ai guasti grazie alla ridondanza nei cablaggi: in sostanza avremo maggiori porte libere negli Hub o switch e più cavi (o fibre ottiche) di quanto sia realmente necessario. Non richiedono conformità alla CCITT (Comitè Consultatif International de Telegraphie e Telephonie).

Reti MAN e WAN

– MAN (Metropolitan Area Network): sono estenzioni delle reti locali, assorbite ormai dalle:

– WAN (Wide Area Network): sono estese su aree geografiche molto più ampie e sfruttano la rete telefonica. Solitamente necessitano di particolari strutture per il controllo dell'accesso. Ad esempio le reti che usano le banche per cominicare da una parte all'altra del pianeta dati sensibili. A volte queste imprese hanno loro linee private interne irraggiungibili dall'esterno. In Italia la connessione dati è nata con i CDA (canali diretti analogici), sostituita poi dai CDN (canali diretti numerici). Successivamente sono state costruite reti apposite per la trasmissione dati e molte WAN private.

Velocità di trasmissione

● La velocità di trasferimento dati è il bps (bit per secondo)

●


● La velocità di trasmissione è strettamente legata alla frequenza del segnale veicolato dai vari mezzi trasmissivi. Si pensi ad un bit che viene trasmesso in un microsecondo: esso corrisponde ad una frequenza di trasmissione del segnale di 1 Mhz.

● È quindi importante conoscere lo spettro di frequenza delle trasmissioni, sotto forma di onde elettromagnetiche, che vengono utilizzate quotidianamente.


● La prossima tabella riporta l'unità di misura della velocità di trasmissione, chiamata anche larghezza di banda del canale tramissivo, per alcuni mezzi trasmissivi usati nelle LAN.


● La tabella sottostante riassume le velocità di trasmissione delle WAN

Diffusione dei dati

● Dal punto di vista della distribuzione dei dati possiamo fare un ulteriore classificazione:

– Reti a diffusione globale (broadcast): ogni trasmissione viene trasmessa da tutti gli host connessi

Diffusione dei dati● É possibile inviare un messaggio anche ad un

sottoinsieme degli host (multicasting)

Connessione punto punto● Nelle reti punto punto due dispositivi collegati

uno con l'altro si scambiano dati. Ad esempio la connessione di un pc di casa con l'ISP (Internet Service Provider).

Regole per il trasferimento dei dati

● Esistono tre regole per il trasferimento dei dati, che danno origine a tre tipi di linee diverse:

– Linea Simplex il trasferimento dei dati avviene in maniera monodirezionale, cioè il sistema che riceve la comunicazione non è in grado di rispondere (es. trasmissione radiotelevisiva);

– linea Half-duplex, per la quale la comunicazione è possibile in entrambe le direzioni, ma uno solo per volta dei due elementi posti in comunicazione può trasmettere (es. ricetrasmettitori);

– linea Full-duplex, per la quale la comunicazione è possibile in entrambe le direzioni e gli elementi interconnessi possono fruire del canale di comunicazione in contemporanea (es. Comunicazione telefonica).

Le tecniche di commutazione

● Per mettere in comunicazione due utenti esistono fondamentalmente due tecniche:

– Commutazione di circuito, di derivazione dal sistema telefonico. Le linee commutate, cioè le normali linee telefoniche, sono state basate per lungo tempo su una tecnica di commutazione detta commutazione di circuito. Le prime centrali telefoniche funzionavano manualmente. Le operatrici collegavano a richiesta la linea dell'utente, che effettuava la chiamata, con l'utente desiderato. La commutazione di circuito crea quindi un vero collegamento fisico tra i due utenti, ed esso resta stabile e riservato a loro per tutta la durata della comunicazione. Questo comporta in media un basso utilizzo del canale trasmissivo, risultando occupato da una comunicazione anche quando i due interlocutori non parlano.


L'utilizzo della commutazione di circuito prevede tre fasi distinte:

● attivazione del circuito, in cui si stabilisce la connessione fisica tra l'unità chiamante e l'unità chiamata; nel caso della comunicazione telefonica corrisponde all'attivazione del numero e all’attesa che il numero chiamato risponda.

● utilizzo del canale trasmissivo, è la fase in cui i dati possono essere trasmessi senza necessità di particolari controlli; nel caso della comunicazione telefonica è la parte di comunicazione tra i due interlocutori.

● svincolo, è la fase in cui la connessione viene chiusa; nella comunicazione telefonica, corrisponde a rimettere nella sede il ricevitore del telefono con la riattivazione del servizio da parte della centrale telefonica.


– Commutazione di pacchetto, di derivazione dall'informatica. Il pacchetto è costituito da due parti

Questi attributi permettono al pacchetto di essere svincolato dal percorso fisico dei dati, perchè, anche se i pacchetti di una stessa sequenza fanno percorsi diversi per giungere a destinazione, il destinatario ha comunque gli elementi per ricostruire la squenza


I pacchetti vengono instradati dai nodi intermedi su percorsi differenti:

Architettura di rete

● Per ridurre la complessità di progetto, le architetture di rete sono organizzate a livelli, ciascuno dei quali fornisce al livello superiore i servizi richiesti, mascherando le modalità con le quali sono ottenuti. Le regole e le convenzioni usate nel dialogo tra livelli omologhi sono generalmente conosciute come protocolli. Un insieme di livelli e protocolli è chiamato architettura di rete.


● Il livello n in un host dialoga con il livello n su di un altro host. Le regole che governano la conversazione a pari livello è chiamata protocollo livello n. Le entità a pari livello si chiameranno peer entity. Il dialogo in questione consiste nello scambio di PDU (Prodocol Data Unit), composto dalla parte di dati e dall'intestazione specifica del livello. In realtà non c'è trasferimento diretto di dati dal livello n di host1 al livello n di host2. Ogni livello di host1 passa i dati e le informazioni di controllo, al livello sottostante. Al livello 1 c'è il mezzo fisico,


attraverso il quale i dati vengono trasferiti da host1 ad host2. Quando arrivano a host2, i dati vengono passati da ogni livello (a partire dal livello 1) a quello superiore, fino a raggiungere il livello delle applicazioni. Ogni livello n comunica con quello direttamente superiore n+1 attraverso un'interfaccia, che caratterizza le operazioni primitive che possono essere richieste al livello sottostante. SDU (Service Data Unit) è il termine con cui si indicano i dati scambiati attraverso l'interfaccia.

Protocolli

● La comunicazione tra tutti i dispositivi di una rete è regolata da un insieme di norme che definiscono il linguaggio comune per fare dialogare tra loro le componenti. Questo linguaggio comune prende il nome di protocollo.

● I protocolli di rete sono strutturati a livelli sovrapposti.

Protocolli

● OSI (Open System Interconnection)

Regolarizzato nel 1984 dalla ISO (International Organization for Standardization) è organizzato su sette levelli.

● TCP-IP (Transmission Control Protocol e Internet Protocol)

L'OSI può essere considerato il padre del più moderno TCP-IP, distribuito invece su quattro livelli.

ProtocolliISO-OSI Nome TCP-IP Nome Esempi TCP-IP

Livello 7 ApplicazioneDai Processi di rete all'applicazione

Livello 4 ApplicazioneTelnet, FTP, SMTP, ecc

Livello 6 PresentazioneDei dati e decriptazione

Livello 5 SessioneControllo comunicazione

Livello 3 Trasporto TCP, UDP

Livello 4 TrasportoConnessione end-to-end

Livello 3 ReteDeterminazione IP

Livello 2 Rete IP

Livello 2 CollegamentoIndirizzamento MAC

Livello 1 Collegamento NIC

Livello 1 Fisicosegnale

Livello 1

1)Livello di collegamento fisico (physical layer)

A questo livello spetta la definizione delle funzioni basilari della connessione fisica, dalla struttura elettronica che realizza il collegamento, agli aspetti tecnici delle interconnessioni. Questo è il livello che gestisce le caratteristiche hardware. Il livello fisico si occupa della trasmissione dei singoli bit da un estremo all’altro dei vari mezzi di comunicazione che possono essere le fibre ottiche, le onde radio, i satelliti ecc.

Livello 1

La connessione tipica di una rete locale utilizza sistemi ethernet. Gli elementi che si trovano a livello 1 sono i seguenti:

– Le schede di rete o NIC che vengono installate all’interno del computer nell’alloggiamento della scheda madre dedicato alle schede di espansione.

– Gli hub o ripetitori sono semplici apparecchiature di livello 1 che collegano tra loro gruppi di utenti.

Livello 2

2)Livello di collegamento dati (data link layer)

Il livello del collegamento dati riguarda i dispositivi che gestiscono il collegamento da un computer a un altro della stessa rete. Controlla la correttezza delle sequenze di bit trasmesse e ne richiede eventualmente la trasmissione. Provvede alla formattazione delle informazioni e alla sincronizzazione dei frame, nonché alla correzione e al recupero dei messaggi errati.

Livello 2

Un frame (in italiano trama) contiene, a livello del collegamento dati, l’indirizzo di destinazione e, se richiesto da un livello superiore, anche l’indirizzo di origine, e un codice per la correzione e rilevazione degli errori. Il frame costituisce l’entità di dati che è trasmessa senza interruzioni. A livello successivo (livello 3) prende il nome di pacchetto.

Livello 2

Gli elementi di interconnessione della rete a livello 2 sono i seguenti:

– Gli switch sono dispositivi più intelligenti degli hub e si caratterizzano anch’essi per il numero di porte disponibili. Uno switch invia i pacchetti di dati alle porte specifiche dei destinatari, sulla base delle informazioni contenuti nelle header di ogni pacchetto. Per isolare la trasmissione dalle altre porte, lo switch stabilisce una connessione temporanea tra la sorgente e il punto di destinazione, chiudendola al termine del collegamento.

– I bridge sono dispositivi del tutto analoghi agli switch, ma hanno solo due porte e quindi sono gli elementi di interconnessione tipici di due LAN.

Livello 3

3)Livello di controllo della rete (network layer)

A questo livello appartengono funzioni tipicamente di rete. Nel livello di rete i messaggi vengono suddivisi in pacchetti che, una volta giunti a destinazione, vengono riassemblati nella loro forma originaria. Il livello di rete si fa carico di scegliere una strada tra quelle disponibili, tramite i router che instradano i pacchetti verso il computer di destinazione. Il protocollo di rete più utilizzato nel livello 3 è il protocollo IP.

Livello 3Il principale apparato di interconnessione della rete a livello 3 è il router. Ancora più intelligenti di hub e switch, i router utilizzano un indirizzo IP per determinare il nodo intermedio successivo che deve ricevere il pacchetto. Basandosi su una mappa di rete denominata tabella di routing, i router possono fare in modo che i pacchetti raggiungano le loro destinazioni attraverso i percorsi più idonei. Se cade la connessione tra due router, per non bloccare il traffico, il router sorgente può cercare un percorso alternativo. I router definiscono anche i collegamenti tra reti che utilizzano protocolli diversi.

Livello 4

4)Livello del trasporto (transport layer)

Il livello di trasporto gestisce la trasmissione dei pacchetti end-to-end. Ha il compito specifico di assicurare il trasferimento dei dati tra strati di sessione appartenenti a sistemi diversi, geograficamente separati, evitando che sui dati vi siano errori o duplicazioni. È in grado di identificare il destinatario, aprire o chiudere una connessione con il sistema corrispondente, suddividere o riassemblare un testo, controllare e recuperare gli errori, controllare la velocità con cui fluiscono le informazioni.

Livello 4

A questo livello l’esistenza dei livelli inferiori è completamente ignorata: ciò porta a identificare questo livello come il primo che prescinde dal tipo e dalle caratteristiche della rete utilizzata. Il protocollo standard utilizzato nel livello 4 è il protocollo TCP (Trasmission Control Protocol). Talvolta viene usato anche il protocollo UDP (User Datagram Protocol).

Livello 5

5)Livello di sessione (session layer)

Il livello di sessione gestisce la corretta sincronizzazione della corrispondenza dei dati che verranno poi visualizzati. Instaura una sessione, cioè un collegamento logico e diretto tra due interlocutori, organizzandone il dialogo. La modalità del dialogo può essere full-duplex, half-duplex, oppure in simplex. Per sincronizzazione si intende invece la capacità di sapere sempre fino a che punto la comunicazione sia arrivata a buon fine.

Livello 5

Si immagini un trasferimento dati tra due host della durata di alcune ore: la sincronizzazione consiste nel mettere dei punti di controllo nel processo in modo che, se il trasferimento si interrompe, non sia necessario ritrasferire l’intero archivio, ma solo la parte inviata dopo l’ultimo punto di controllo.

Livello 6

6)Livello di presentazione (presentation layer)

Le varie informazioni che viaggiano all’interno della rete subiscono a questo livello una particolare decodifica, che le trasforma in modo da renderle visualizzabili nei normali dispositivi di output a disposizione degli utenti, tipicamente i video e le periferiche di stampa. La nostra abitudine all’informatica dei Personal Computer può indurci a pensare erroneamente che il codice ASCII utilizzato dai terminali sia uguale per tutti, dimenticando realtà differenti, cioè terminali che utilizzano codifiche diverse,

Livello 6

che vengono supportate correttamente dal livello di presentazione. Il livello di presentazione gestisce quindi i formati di conversione dei dati, cioè effettua tutte le opportune conversioni in modo da compensare eventuali differenze di rappresentazione e di formato dei dati in arrivo e in partenza.

Livello 7

7)Livello di applicazione (application layer)

Il livello di applicazione riguarda i cosiddetti programmi applicativi. Questo livello gestisce la visualizzazione dei dati relativa a programmi di login remoto, file transfer, posta elettronica. Per la gestione dei Personal Computer, il problema si presenta quando due sistemi che vogliono comunicare possiedono video o tastiere diverse, e quindi non compatibili. Per esempio, per spostare il cursore a inizio linea o per cancellare lo schermo, ogni scheda ha i suoi comandi specifici:

Livello 7

invece di dotare tutti i sistemi di opportuni traduttori per tutti i possibili interlocutori, è evidentemente molto più semplice definire un terminale virtuale di rete come standard unico virtuale, a cui tutti i corrispondenti terminali reali devono adeguarsi per comunicare.

Router● Un router ha queste funzioni principali:

– Instradamento dei dati– Connessione tra le varie reti WAN– Connessione a Internet– Limitare il broadcast alle singole subnet

● Il compito fondamentale del router è quindi l'instradamento, cioè una funzione del livello 3 (dell'ISO-OSI). Il router non fa altro che gestire gli insiemi di indirizzi, determinando percorsi computazionalmente validi affinchè i messaggi siano consegnati ai vari destinatari.

● La segmentazione della rete si ispira al concetto divide et impera.

Router

● Funzioni di routing:– Creare e gestire tabelle di routing;– Determinare tramite le tabelle di routing i percorsi

(minimi...).

● Un router ha le stesse componenti di un normale PC.● CPU● Memoria● System bus● Interfacce input/output

● Nota: segue il modello di Von Neumann...

Router

● Di router ne esistono innumerevoli tipi e specie. Può essere usato per dirigere reti LAN domestiche con e senza connessione WI-FI. Ma ci sono router che possono regolarizzare il traffico su reti aziendali relativamente grandi.

● Anche i router necessitano quindi un sistema operativo specifico, questo viene chiamato IOS (Internetwork Operating System).

● Normalmente i router sono configurati dall'amministratore della rete.

Router

● Classifichiamo le componenti fisiche come:– Porte di accesso (>=2)– Porte di uscita (>=2)– Matrice di commutazione: collega ciascuna porta di

ingresso a ciascuna porta di uscita– Processore di controllo, RAM, NVRAM, flash memory,

ROM

Router Cisco 2600 Series

● Prenderemo questo modello proprio perchè essendo un router modulare permette di installare su di esso qualsiasi configurazione. Nota: appartiene alla fascia midrange..


● NMs= Network Modules

● AIMs= Advanced integration modules

● WICs=WAN Interface Cards


● CPU: esegue IOS, gestisce il routing, possiamo avere più CPU

● RAM: ha le normali funzioni di una RAM... (DRAM, con moduli DIMM)

● Flash: contiene l'immagine del sistema operativo

● Bus: – Bus di sistema: cpu-interfacce

– CPU-Bus: cpu-memorie

● NVRAM: contiene la configurazione all'avvio del router

● ROM: – Effettua la diagnostica

– Carica l'IOS dalla Flash


● Porte:● Possiamo aggiungere tramite espansione:

– Porte ethernet (Network Module Slot)

– Porte seriali o ISDN (WAN Interface Card Slot)

● AUX/Console: usate per configurare il router, recovery o pw recovery

● Power supply: alimentazione

Fondamenti di Routing

● L'instradamento è alla base del livello 3 (ISO-OSI)

● I terminali della rete vengono chiamati host e i nodi di commutazione router


● Il router sono dispositivi con uscite multiple. Ricevono un pacchetto da un'interfaccia e lo instradano su un'altra a secondo dell'indirizzo univoco assegnato ad ogni host.

● L'instradamento può essere:– Diretto: due host solo collegati senza router intermedi

alla stessa sottorete, il messaggio viene instradato a secondo del suo mac


– Indiretto: due host sono collegati a sottoreti diverse attraverso uno o più router. Il mittente fornisce l'indirizzo del router, quando questo perciò riceverà il pacchetto lo instraderà ad un altro router...., fino a destinazione!


● Ogni router contiene una tabella di instradamento che contiene informazioni relative alle destinazioni conosciute. Una tabella è un insieme di righe, ciascuna delle quali contiene:

– Indirizzo della rete di destinazione (N)– Maschera di rete (M)– Indirizzo del prossimo router (Next Hop)– Interfaccia su cui inoltrare i pacchetti


● La maschera di rete ci fornisce un metodo per capire se l'host cercato si trova nella stessa sottorete.

● Metodo:

il nostro IP= 192.168.32.97, (11000000 10101000 00100000 01100001)

subnetmask=255.255.255.224, (11111111 11111111 11111111 11100000)

vogliamo connetterci all'indirizzo 192.168.32.130(11000000 10101000 00100000 10000010)

si fa un AND tra gli IP e il subnetmask se il risultato è lo stesso allora appartengono alla stessa rete

11000000 10101000 00100000 01100001(AND) 11000000 10101000 00100000 10000010

11111111 11111111 11111111 11100000 11111111 11111111 11111111 11100000

__________________________________ _________________________________

11000000 10101000 00100000 01100000 11000000 10101000 00100000 10000000


● Tabella di routing per R2:


● Se una destinazione non è presente nella tabella il pacchetto viene instradato al router di default. L'indirizzo di questo viene inserito come ultima riga ed è codificato con tutti 0 sia nel campo N che nel campo M.


● Es: Data la seguente tabella, individuare verso quale porta vengono instradati i pacchetti indirizzati ai seguenti indirizzi:

– 198.12.17.3– 198.12.0.3– 20.12.0.3


● Il primo darà due confronti positivi, verrà instradato alla porta 5 visto che ha un prefisso più lungo.

● Le subnetmask più usate sono:– 255.000.000.000, 2^24 indirizzi possibili per subnet – 255.255.000.000, 2^16 indirizzi possibili per subnet– 255.255.255.000, 2^8 indirizzi possibili per subnet

● Quindi il numero degli indirizzi dipende dal numero di zeri.

– Es: 255.255.255.192=11111111.11111111.11111111.11000000

fornirà 2^6 indirizzi per subnet

Fondamenti di Routing● Il secondo verrà instradato sulla porta 1.

Fondamenti di Routing● Il terzo verrà instradato al router di default.

Fondamenti di Routing● Se noi avessimo un'interfaccia con indirizzo

131.175.21.77/24 significa che lavoriamo con un'interfaccia submask di 24 bit. Se avessimo una destinazione 131.175.21.96/24:


● Indirizziamo i seguenti 4 pacchetti a:– 131.175.21.96– 131.17.123.88– 131.56.78.4– 190.78.90.2

● Un'altra colonna che può essere presente nella tabella può essere il costo.

IGP e EGP

● Le reti WAN possono essere viste come un insieme di reti LAN (o Sistemi Autonomi AS), ognuna gestita autonomamente da dei protocolli chiamati IGP (Internal Gateway Protocol). I protocolli che gestiscono le interconnesioni tra le AS sono chiamati EGP (Exterior Gateway Protocol).

● Le AS possono essere suddivise ulteriormente in Routing Area (RA) e interconnesse tra di loro tramite un backbone (dorsale).

IGP e EGP

Algoritmi di Routing ● Un algoritmo di routing stabilisce i criteri di

scelta del cammino che devono effettuare i pacchetti all'interno della rete.

● Il vincolo primario è che ogni cammino dal mittente di un pacchetto fino al destinatario deve necessariamente essere un albero.

Algoritmi di Routing ● Ogni cammino potrà essere schematizzato

come un albero, cioè senza percorsi di tipo ciclico. Ogni rete può essere schematizzata con un grafo. Un grafo è uno schema composto da nodi (o vertici) e archi (o spigoli). I nodi rappresentano i dispositivi che intervengono sulla rete stessa, mentre gli archi sono i vari collegamenti. I percorsi per ogni pacchetto devono seguire le leggi stabilite da un algoritmo. Questi algoritmi trovano il cammino minimo (quindi il cammino più conveniente possibile) dal mittente al destinatario. Ad ogni arco verrà associato un peso, anch'esso influirà nella ricerca del cammino minimo.

Grafi

● Come già detto in precedenza si può schematizzare una rete con un Grafo.

● Un grafo G è una coppia (V,E):

– V insieme di vertici – E è l'insieme delle

coppie di vertici, detti archi

Grafi

● Un grafo si definisce orientato se su ogni arco vi è definito l'ordinamento della coppia di vertici, cioè che la direzione dal nodo di partenza al nodo di origine.

Grafi● In un grafo pesato

ogni arco è contraddistinto da un peso.

● Il cammino è una sequenza di vertici adiacenti, che ci permette di andare da un nodo ad un altro, è definito semplice se contiene solo nodi distinti.

Grafi

● Per lunghezza di un cammino si intende il numero di archi che lo compone

● Per distanza si intende il cammino più breve tra due nodi

● Un circuito è un cammino che partendo da un nodo n1 torna allo stesso senza archi ripetuti

● Il peso di un cammino è la somma di tutti i pesi associati ad ogni arco che fa parte di quel cammino

● Un ciclo è un cammino che partendo da un nodo n1 torna allo stesso senza archi nè nodi ripetuti

Grafi

● Un grafo si definisce aciclico se non contiene cicli, un grafo connesso e aciclico è definito un albero.

Grafi

● Per rappresentare un grafo possiamo usare la matrice di adiacenze. In tale matrice l'elemento è 1 se i nodi sono collegati direttamente, 0 altrimenti. Vediamo alcuni esempi:

Grafi

● Nei grafi pesati si mette il valore del peso al posto dell'1 e ∞ al posto dello 0 (0 si lascia sulla diagonale...).

Grafi

● Un cammio p2 è definito minimo (ottimo) in questo caso:

● L'insieme dei percorsi minimi definisce l'albero di inoltro dove il router sorgente viene chiamato radice (root) e i router destinazioni foglie (leaves)

Grafi● È possibile trasformare un grafo in un albero di

ricoprimento (spanning tree), cioè un suo sottografo (se gli insiemi dei suoi nodi e dei suoi spigoli sono sottoinsiemi di quelli del grafo..), privato di tutti i cicli.

● Tra tutti gli alberi ricoprenti è possibile determinare il Minimum Spanning Tree, cioè quello con il peso minore

Algoritmi statici

● Ogni router contiene la topologia della rete di appartenenza. Le decisioni di router sono prese in anticipo, all'avvio della rete

● Principio di ottimalità:se il router j è nel cammino ottimo fra i e k, allora anche il cammino ottimo fra j e k è sulla stessa strada.

Algoritmi statici

● Gli algoritmi statici si definiscono anche Link State, perchè ogni router dopo che aver acquisito tutte le informazioni che gli servono invia a tutti gli altri nodi dei Link State Packet (LSP), contenenti una serie di dati come: lo stato di ogni link, il costo o anche il numero sequenziale per l'LSP.

● Al ricevimento degli LSP ogni nodo si costruirà un database con questi e ricostruirà la topologia della rete; successivamente procederà a calcolare i cammini minimi.

Algoritmi statici

● Al ricevimento dell'LSP il router deve controllare il numero di sequenza:

– Se non ha mai ricevuto LSP da quel router o l'LSP è più recente di quello in suo possesso deve aggiornare il suo database e rimandare agli altri questo pacchetto nuovo

– Se il numero di sequenza è uguale a quello in suo possesso non farà nulla

– Se il router ha un LSP più recente di quello ricevuto, invia all'altro nodo il nuovo LSP

Algoritmi statici

● Esempio di database:

Algoritmi statici

● Proviamo a costruire un LS database da questa situazione:

Algoritmi statici

● R1 riceve il peso di ogni collegamento e ricostruisce la seguente tabella:

Algoritmi statici

● Ogni router quindi invierà il suo messaggio:

Algoritmi statici

A B C R1 R2 R3 R4

A 0 0 0 4

B 0 0 0 4

C 0 0 0 4

R1 4 4 4 0 3 5

R2 3 0 2

R3 5 0

R4 2 0

● Unendo tutte le informazioni precedenti sarà possibile stabilire questa matrice di adiacenza

Algoritmi statici

● Flooding:– Questo algoritmo invia ogni pacchetto su tutte le porte,

tranne su quella dalla quale è arrivato. – Svantaggi: Logicamente questa tecnica potrebbe

provocare la duplicazione dello stesso pacchetto sullo stesso nodo per molte volte e anche che ogni pacchetto rimbalzi da un router all'altro in continuazione.... Per evitare ciò si mette un contatore che una volta azzerato arresta l'invio e soprattutto una volta che il router ha ricevuto un pacchetto se lo riceve nuovamente lo ignora.

– Vantaggi: questo tipo di algoritmo è ottimale in termini di tempi di elaborazione dei router. Viene usato appunto su topologie molto semplici e quando è richiesto un messaggio broadcast.

Algoritmi statici

● Flow-based routing:– Questo algoritmo sceglie il percorso migliore calcolando il

traffico medio di ogni linea. Un router può essere pensato come un automobilista che sceglie la strada migliore pensando al traffico che potrebbe trovare su ogni percorso. Peccato che per costruzione stessa dell'algoritmo questa tecnica non può essere usata da tutti i router in quanto tutti finirebbero ad instradare pacchetti sulle vie considerate meno percorse e lasciando libere le vie principali...

Algoritmi statici● L'algoritmo di Dijkstra:

– È uno degli algoritmi più usati e conosciuti per routing statico. Permette di trovare l'albero dei cammini minimi partendo da ogni nodo; per questo viene definito centralizzato. Facciamo un esempio per spiegare il metodo:

Prendiamo il grafo in figura e pensiamo di partire dal nodo A

Algoritmi statici

– Etichettiamo B e F con il peso degi corrispondenti archi di collegamento con A

Algoritmi statici

– Scegliamo ora quindi l'arco più conveniente, quindi quello passante per B. A questo punto dobbiamo assegnare a tutti i nodi comunicanti con B una etichetta, ottenuta come somma dell'etichetta di B stesso e il peso di ogni arco. Se un nodo ha già un'etichetta, gli si assegna quella minore.

Algoritmi statici

– Scegliamo a questo punto di nuovo il percorso migliore, quindi quello passante per F ed aggiorniamo le etichette dei nodi ad esso adiacenti.

Algoritmi statici

– Il prossimo nodo da analizzare sarà E dal quale possiamo raggiungere il nodo D, al quale sarà assegnato un'etichetta minore.

Algoritmi statici

– Il nodo rimanente sarà il nodo C al quale però conviene lasciare l'etichetta assegnata perchè un eventuale collegamento con D non porterebbe migliorie. A questo punto le etichette diventano permanenti e otteniamo il seguente albero minimo.

Algoritmi statici

– Applicare ora lo stesso metodo al seguente grafo orientato:

Algoritmi statici

– Esercizio: trovare il cammino minimo tra 0 e 5 e l'albero di ricoprimento nel seguente grafo:

Soluzione: il cammino minimo è 0-2-1-4-5 con peso 13

Algoritmi dinamici

● Per quanto possano essere efficienti, performanti e computazionalmente validi, agli algoritmi statici devono essere affiancati gli algoritmi dinamici. Questo accade a causa della continua espansione della rete e della sempre crescente innovazione tecnologica. Gli algoritmi dinamici sono capaci di scoprire i percorsi minimi su una rete e mantenerli costantemente aggiornati.

Algoritmi dinamici

● Algoritmo di Bellman-Ford:– È un algoritmo dinamico che calcola per ciascun nodo il

cammino migliore. Il calcolo viene fatto sulle informazioni ricevute dagli altri router e non conosce la topologia della rete. In pratica ogni nodo conosce solo i nodi adiacenti ad esso. Proviamo a fare un esempio sul seguente grafo ad archi con costo unitario:

Algoritmi dinamici

● Alla prima accensione la tabella di instradamento per B sarà:

● A questo punto avviene la comunicazione tra i vari router che acquisiscono informazioni sulle tabelle dei loro vicini. Quindi possono riaggiornare le loro tabelle e la matrice di adiacenza diventa:

Algoritmi dinamici

● Come avviene questo aggiornamento?– Ogni nodo riceve dai suoi adiacenti le coppie

destinazione-costo. Quando un nodo riceve una nuova distanza, se è minore di quella in suo possesso procede con l'aggiornamento, altrimenti la ignora. Ad esempio A invia a B la distanza da E, che poi sommato con la distanza tra A e B attribuisce alla distanza tra B e E il valore 2; il valore che lui ha per ora è ∞ quindi lo sostituisce. La sua tabella diventerà quindi:

Algoritmi dinamici

● Alla fine del processo, cioè quando lo scambio di informazioni si sarà stabilizzato, la tabella di routing per B sarà la seguente:

Algoritmi dinamici

● L'algoritmo è ricorsivo in quanto può essere scritto come:

● La formula va interpretata così:– La distanza minima tra x e y è uguale al minimo delle

distanze tra le somme dei costi dei nodi adiacenti v e la loro distanza da y. Appunto il calcolo del secondo membro della somma è ottenuto sempre dalla formula stessa!!!.....

– Facciamo un esempio......

Algoritmi dinamici

● Dobbiamo calcolare il percorso minore tra A e F d

A(F):

● Prendiamo i nodi adiacenti ad A (B,C e D), avranno costi c(A,B)=3, c(A,C)=1, c(A,D)=6

Algoritmi dinamici● A questo punto dovremo calcolare le distanze

dB(F), d

C(F) e d

D(F) per poter poi applicare la

formula:

dA(F)=min{c(A,B)+d

B(F),c(A,C)+d

C(F),c(A,D)+d

D(F)}

dA(F)=min{3+d

B(F),1+d

C(F),6+d

D(F)}

● dB(F), d

C(F) e d

D(F) verranno calcolati sempre

con la stessa formula

dB(F)=min{c(B,C)+d

C(F),c(B,D)+d

D(F)}

dC(F)=min{c(C,D)+d

D(F),c(C,E)+d

E(F)}

dD(F)=5, d

E(F)=3 banalmente

dC(F)=min{3+5, 1+3}=4, d

B(F)=min{2+4,3+5}

Algoritmi dinamici

dA(F)=min{3+6,1+4,6+5}=5

In conclusione potremo dire che A instrada a F tramite C a costo 5

Algoritmi dinamici

● Ora proviamo invece, analizzando un grafo più piccolo, a compilare le tabelle di routing. Prendiamo quindi la seguente rete:

Le tabelle all'inizio (al passo 0)

saranno:

Algoritmi dinamici

● Passo 1 per il nodo x:

Algoritmi dinamici

● Passo 1 per il nodo y:

Algoritmi dinamici

● Passo 1 per il nodo z:

Algoritmi dinamici

● Con un ulteriore passo l'algoritmo aggiorna le tabelle, se ha in memoria valori migliori. Se in caso abbia determinato ulteriori percorsi migliori, invia gli aggiornamenti:

Algoritmi dinamici

● A questo punto le tabelle convergono, quindi il sistema è stabilizzato. Le conseguenti tabelle di routing saranno:

Confronto tra Bellman-ford e Dijkstra

● Applichiamo l'algoritmo di Dijkstra al seguente grafo, vogliamo trovare il cammino minimo e l'albero di ricoprimento da casa all'ufficio.


● Vediamo cosa avviene:

2

8

4

13

10

8

69


Passo Casa A B C D E Ufficio

0 0 ∞ ∞ ∞ ∞ ∞ ∞

1 0 2 ∞ ∞ 8 ∞ ∞

2 0 2 8 4 8 ∞ ∞

3 0 2 8 4 6 13 ∞

4 0 2 8 4 6 9 ∞

5 0 2 8 4 6 9 10

● Facciamo una tabella per individuare passo passo i conti effettuati:


● Il cammino minimo da casa a ufficio sarà: casa-A-C-D-E-ufficio con costo 5. Il router di casa per mandare un mesaggio all'ufficio ha bisogno di conoscere la topologia della rete. Questo algoritmo è efficiente e veloce.


● Eseguiamo sulla stessa rete l'algoritmo di Bellman-Ford:


● Compiliamo una tabella per aiutare a fare i conti. Al passo 0 sono tutti ∞. Al passo 1 vengono compilati solo i valori dei pesi dei nodi

adiacenti. Passo 0 e 1 CASA A B C D E UFFICIO

Tutti(Passo 0) ∞ ∞ ∞ ∞ ∞ ∞ ∞

CASA 0CASA

2A ∞ ∞ 8

D ∞ ∞

A 2CASA

0A

6B

2C ∞ ∞ ∞

B ∞ 6A

0B ∞ ∞ ∞ 5

UFFICIO

C ∞ 2A ∞ 0

C2

D9

E ∞

D 8CASA ∞ ∞ 2

C0

D3

E ∞

E ∞ ∞ ∞ 9C

3D

0E

1UFFICIO

UFFICIO ∞ ∞ 5B ∞ ∞ 1

E0

UFFICio


● Al passo 2 i router si scambiano le informazioni. I valori che prima erano ∞ li coloro di rosso, mentre quelli aggiornati di giallo. Cioè d

C(E)=min{c(C,E)+d

E(E),c(C,D)+d

D(E)}= min{9+0,2+3}=5

Passo 2 CASA A B C D E UFFICIO

CASA 0CASA

2A 8

A4

A8

D 11D

∞

A 2CASA

0A

6B

2C 4

C11

C11

B

B 8A

6A

0B 8

A∞ 6

UFFICIO5

UFFICIO

C 4A

2A 8

A0

C2

D 5D

6D

D 8CASA 4

C∞ 2

C0

D3

E 4E

E ∞ 7D

6UFFICIO

5D

3D

0E

1UFFICIO

UFFICIO ∞ 11B

5B 6

E4

E1

E0

UFFICIO


● Saltando qualche passo.... arriviamo al passo 3

dCASA

(D)=min{c(CASA,A)+dA(D),c(CASA,D)+d

D(D)}

dA(D)=min{c(A,C)+d

C(D),c(B,D)+d

B(D)}=4

dCASA

(D)=min{2+4,8}=6


CASA 0CASA

2A 8

A4

A6

A9

A13

A

A 2CASA

0A

6B

2C 4

C7

C8

C

B 8A

6A

0B 8

A9

UFFICIO6

UFFICIO5

UFFICIO

C 4A

2A 8

A0

C2

D 5D

6D

D 6C

4C

9E

2C

0D

3E 4

E

E 9D

7D

6UFFICIO

5D

3D

0E

1UFFICIO

UFFICIO 10E

8E

5B 6

E4

E1

E0

UFFICIO


● Se continuassimo ad iterare non otterremmo nessuno ulteriore aggiornamento. Il cammino minimo risultante è sempre lo stesso: Casa-A-C-D-E-Ufficio con costo 10. Come si vede dalla tabella ad ogni nodo è associato un cammino verso gli altri nodi. Ma in realtà lui conosce solamente verso quale router adiacente verrà instradato il messaggio. Esempio: mandiamo un messaggio da Casa all'Ufficio. Casa saprà che deve instradare ad A con costo totale 10. A sa che deve instradare a C con costo 8. C instrada a D con costo 6, D ad E con costo 4 e D finalmente a Ufficio con costo 1. Ogni router, come possiamo notare da ogni riga, conosce solo i nodi adiacenti!!!!


CASA 0CASA

2A 8

A4

A6

A9

A10

A

A 2CASA

0A

6B

2C 4

C7

C8

C

B 8A

6A

0B 8

A9

UFFICIO6

UFFICIO5

UFFICIO

C 4A

2A 8

A0

C2

D 5D

6D

D 6C

4C

9E

2C

0D

3E 4

E

E 9D

7D

6UFFICIO

5D

3D

0E

1UFFICIO

UFFICIO 10E

8E

5B 6

E4

E1

E0

UFFICIO

Retistekandaloro.altervista.org/blog/wp-content/uploads/2015/09/reti-1.pdfReti di Computer Si...

Documents

Transcript of Retistekandaloro.altervista.org/blog/wp-content/uploads/2015/09/reti-1.pdfReti di Computer Si...