RETI DI CALCOLATORI Quinta Esercitazione. 2 I router Applicazione Presentazione Sessione Trasporto...

RETI DI CALCOLATORIRETI DI CALCOLATORI

Quinta EsercitazioneQuinta Esercitazione

22

I routerI router

Applicazione

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

Applicazione

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

Rete

Data Link

Fisico

Data Link

Fisico

ROUTER

33

I routerI router

I router sono dei dispositivi che I router sono dei dispositivi che lavorano a livello network (e lavorano a livello network (e pertanto utilizzano tutte le pertanto utilizzano tutte le informazioni contenute nella informazioni contenute nella busta di livello 3) del modello OSI busta di livello 3) del modello OSI e risultano essere, in teoria, gli e risultano essere, in teoria, gli elementi più adeguati per elementi più adeguati per l'interconnessione di LAN. l'interconnessione di LAN.

44

I routerI router

Il loro operato è di norma limitato ad Il loro operato è di norma limitato ad un solo o pochi protocolli e ben si un solo o pochi protocolli e ben si caratterizza per la gestione di caratterizza per la gestione di topologie complesse.topologie complesse.

Sfruttano tutte le linee a Sfruttano tutte le linee a disposizione della rete, comprese disposizione della rete, comprese quelle più lente, e consentono quelle più lente, e consentono inoltre di suddividere la rete stessa inoltre di suddividere la rete stessa in più aree in modo da avere un in più aree in modo da avere un routing di tipo gerarchico.routing di tipo gerarchico.

55

I routerI router

I router possono essere indicati I router possono essere indicati tramite terminologie alternative tramite terminologie alternative quali quali ISIS ( (Intermediate SystemIntermediate System) in ) in ambito ISO, ambito ISO, gatewaygateway in ambito IP in ambito IP (anche se in questo caso tale (anche se in questo caso tale termine è usato impropriamente) termine è usato impropriamente) e e ICMPICMP (Interface Message (Interface Message Processor) in ambito Arpanet.Processor) in ambito Arpanet.

66

Multiprotocol RouterMultiprotocol Router

Di notevole importanza risultano Di notevole importanza risultano essere i essere i router multiprotocollorouter multiprotocollo, in , in grado di trattare più architetture grado di trattare più architetture di rete. Analizzando la loro di rete. Analizzando la loro struttura si può notare che il struttura si può notare che il modulo di instradamento è modulo di instradamento è replicato per ogni protocollo replicato per ogni protocollo trattato.trattato.

77

Multiprotocol RouterMultiprotocol Router

FDDI

LAN #1 LAN #2 WAN #1 WAN #2

Algoritmo dicalcolo della

tabella diinstradamento

DECNET

Processo diforwarding

Tabella diinstradamento



TCP/IP





OSI



88

I brouter I brouter

Il problema dell'esistenza di Il problema dell'esistenza di protocolli privi del terzo livello è protocolli privi del terzo livello è stato risolto mediante utilizzo di stato risolto mediante utilizzo di moduli di bridgingmoduli di bridging; se un router ; se un router realizza tale funzione viene realizza tale funzione viene chiamato chiamato brouterbrouter..

99

Router vs. BridgeRouter vs. Bridge

Una prima distinzione può essere Una prima distinzione può essere fatta nella fatta nella modalità di utilizzo delle modalità di utilizzo delle bustebuste: i router manipolano buste di : i router manipolano buste di livello tre adattando, se è il caso, la livello tre adattando, se è il caso, la lunghezza dei messaggi in base lunghezza dei messaggi in base alle reti di destinazione mediante alle reti di destinazione mediante frammentazione o divisione degli frammentazione o divisione degli stessi. I bridge non hanno invece la stessi. I bridge non hanno invece la facoltà di manipolare il contenuto facoltà di manipolare il contenuto del campo dati.del campo dati.

1010


Per quanto riguarda l'Per quanto riguarda l'indirizzamentoindirizzamento, , per i router è esplicito mentre i per i router è esplicito mentre i bridge vengono totalmente ignorati bridge vengono totalmente ignorati dai nodi, ad eccezione dei source dai nodi, ad eccezione dei source routing bridge. In relazione routing bridge. In relazione all'all'instradamentoinstradamento, i bridge utilizzano , i bridge utilizzano esclusivamente indirizzi di mittente e esclusivamente indirizzi di mittente e destinatario di livello due mentre i destinatario di livello due mentre i router hanno una più ampia gamma router hanno una più ampia gamma di informazioni su cui basare di informazioni su cui basare l'instradamento.l'instradamento.

1111


In ambito di forwarding e anche per In ambito di forwarding e anche per quanto detto prima, i bridge non quanto detto prima, i bridge non modificano assolutamente gli modificano assolutamente gli indirizzi, operazione che però è indirizzi, operazione che però è consentita ai router che possono consentita ai router che possono inoltre differenziare i messaggi in inoltre differenziare i messaggi in base alla loro priorità.base alla loro priorità.

1212

Tecniche di Tecniche di instradamentoinstradamento

Le tre principali tecniche di Le tre principali tecniche di instradamento, che variano in instradamento, che variano in funzione dell'architettura di rete funzione dell'architettura di rete adottata, sono il adottata, sono il routing by routing by network addressnetwork address, il , il label label swappingswapping e il e il source routingsource routing..

1313

Routing by network Routing by network addressaddress

Secondo questa tecnica di Secondo questa tecnica di instradamento un sistema è instradamento un sistema è indirizzato scrivendo nel pacchetto indirizzato scrivendo nel pacchetto il suo indirizzo di livello tre, univoco il suo indirizzo di livello tre, univoco per tutta la rete. I router utilizzano per tutta la rete. I router utilizzano tale indirizzo come chiave di tale indirizzo come chiave di accesso alla tabella di accesso alla tabella di instradamento per determinare su instradamento per determinare su quale percorso deve essere quale percorso deve essere ritrasmesso il pacchetto.ritrasmesso il pacchetto.

1414

Label swappingLabel swapping

Utilizzato soprattutto nei protocolli Utilizzato soprattutto nei protocolli connessi, l'instradamento dei connessi, l'instradamento dei pacchetti viene deciso nella fase di pacchetti viene deciso nella fase di connessione; per ciascuno di essi connessione; per ciascuno di essi viene definita una label, univoca viene definita una label, univoca all'interno dei data link, che viene all'interno dei data link, che viene usata dai router come chiave di usata dai router come chiave di accesso alla tabella di accesso alla tabella di instradamento. Ogni router, prima di instradamento. Ogni router, prima di ritrasmettere il pacchetto, sostituisce ritrasmettere il pacchetto, sostituisce la vecchia label con una nuova.la vecchia label con una nuova.

1515

Source routingSource routing

Con il source routing l'intero Con il source routing l'intero instradamento viene deciso dalla instradamento viene deciso dalla stazione mittente. Questa tecnica stazione mittente. Questa tecnica è utilizzata dai bridge token ring.è utilizzata dai bridge token ring.

1616

Il livello Network

Il livello network è incaricato di Il livello network è incaricato di muovere i pacchetti dalla sorgente muovere i pacchetti dalla sorgente fino alla destinazione finale, fino alla destinazione finale, attraversando tanti sistemi intermedi attraversando tanti sistemi intermedi (i router appunto) della subnet di (i router appunto) della subnet di comunicazione quanti è necessario. comunicazione quanti è necessario. Ciò è molto diverso dal compito del Ciò è molto diverso dal compito del livello data link, che è di muovere livello data link, che è di muovere informazioni solo da un capo all'altro informazioni solo da un capo all'altro di un singolo canale di di un singolo canale di comunicazione wire-like.comunicazione wire-like.

1717

Il livello Network

Le incombenze principali di questo livello Le incombenze principali di questo livello sono: sono:

• conoscere la topologia della rete; conoscere la topologia della rete; • scegliere di volta in volta il cammino scegliere di volta in volta il cammino

migliore (migliore (routingrouting); ); • gestire il flusso dei dati e le congestioni gestire il flusso dei dati e le congestioni

((flow control flow control ee congestion control congestion control); ); • gestire le problematiche derivanti dalla gestire le problematiche derivanti dalla

presenza di più reti diverse presenza di più reti diverse ((internetworkinginternetworking).).

1818

Il livello Network

Nel progetto e nella realizzazione Nel progetto e nella realizzazione del livello network di una del livello network di una architettura di rete si devono architettura di rete si devono prendere decisioni importanti in prendere decisioni importanti in merito a: merito a:

• servizi offerti al livello transport; servizi offerti al livello transport; • organizzazione interna della organizzazione interna della

subnet di comunicazione.subnet di comunicazione.

1919

Servizi offerti

In merito ai servizi offerti al livello superiore, In merito ai servizi offerti al livello superiore, ci sono due tipologie fondamentali di ci sono due tipologie fondamentali di servizi: servizi:

• servizi servizi connection-orientedconnection-oriented; ; • servizi servizi connectionlessconnectionless. . In proposito, esistono due scuole di pensiero: In proposito, esistono due scuole di pensiero: • fautori dei servizi connection-oriented fautori dei servizi connection-oriented

(compagnie telefoniche); (compagnie telefoniche); • fautori dei servizi connectionless (Internet fautori dei servizi connectionless (Internet

Community).Community).

2020

Servizi offerti

La prima scuola di pensiero afferma che La prima scuola di pensiero afferma che il livello network deve fornire un il livello network deve fornire un servizio sostanzialmente affidabile e servizio sostanzialmente affidabile e orientato alla connessione. In questa orientato alla connessione. In questa visione, succede che: visione, succede che:

• le peer entitiy stabiliscono una le peer entitiy stabiliscono una connessione, negoziandone i parametri connessione, negoziandone i parametri (di qualità, di costo, ecc.), alla quale (di qualità, di costo, ecc.), alla quale viene associato un identificatore; viene associato un identificatore;

• tale identificatore viene inserito in ogni tale identificatore viene inserito in ogni pacchetto che verrà inviato;pacchetto che verrà inviato;

2121

Servizi offerti

• la comunicazione è bidirezionale la comunicazione è bidirezionale e i pacchetti viaggiano, in e i pacchetti viaggiano, in sequenza, lungo il cammino sequenza, lungo il cammino assegnato alla connessione; assegnato alla connessione;

• il controllo di flusso è fornito il controllo di flusso è fornito automaticamente.automaticamente.

2222

Servizi offerti

La seconda scuola di pensiero ritiene invece che La seconda scuola di pensiero ritiene invece che la sottorete debba solo muovere dati e la sottorete debba solo muovere dati e nient'altro: nient'altro:

• la sottorete è giudicata inerentemente la sottorete è giudicata inerentemente inaffidabile, per cui gli host devono provvedere inaffidabile, per cui gli host devono provvedere per conto proprio alla correzione degli errori e al per conto proprio alla correzione degli errori e al controllo di flusso; controllo di flusso;

• una ovvia conseguenza è che il servizio offerto una ovvia conseguenza è che il servizio offerto dal livello network dev'essere datagram, visto dal livello network dev'essere datagram, visto che è inutile inserire le funzioni di controllo che è inutile inserire le funzioni di controllo degli errori e del flusso in due diversi livelli; degli errori e del flusso in due diversi livelli;

• i pacchetti viaggiano indipendentemente, e i pacchetti viaggiano indipendentemente, e dunque devono tutti contenere un identificatore dunque devono tutti contenere un identificatore (ossia l'indirizzo) della destinazione.(ossia l'indirizzo) della destinazione.

2323

Servizi offerti

Di fatto, il problema è dove mettere la Di fatto, il problema è dove mettere la complessità della realizzazione: complessità della realizzazione:

• la prima scuola la mette nei nodi della la prima scuola la mette nei nodi della subnet, che si devono occupare del subnet, che si devono occupare del setup delle connessionisetup delle connessioni e di fornire la e di fornire la necessaria affidabilità; necessaria affidabilità;

• la seconda scuola la mette negli host, i la seconda scuola la mette negli host, i cui livelli transport forniscono cui livelli transport forniscono l'affidabilità e l'orientamento alla l'affidabilità e l'orientamento alla connessione.connessione.

2424

Servizi offerti

In realtà le decisioni sono due, separate: In realtà le decisioni sono due, separate: • offrire o no un servizio affidabile; offrire o no un servizio affidabile; • offrire o no un servizio orientato alla offrire o no un servizio orientato alla

connessione. connessione. Le scelte più comuni sono di offrire Le scelte più comuni sono di offrire

servizi connection oriented affidabiliservizi connection oriented affidabili oppure oppure servizi connectionless non servizi connectionless non affidabiliaffidabili, mentre le altre due , mentre le altre due combinazioni, anche se tecnicamente combinazioni, anche se tecnicamente possibili, non sono diffuse.possibili, non sono diffuse.

2525

Organizzazione interna Organizzazione interna della subnetdella subnet

Questo è un problema separato ed Questo è un problema separato ed indipendente da quello dei servizi indipendente da quello dei servizi offerti, anche se spesso c'è una offerti, anche se spesso c'è una relazione fra i due.relazione fra i due.

Una subnet può essere organizzata Una subnet può essere organizzata con un funzionamento interno con un funzionamento interno basato su connessionibasato su connessioni oppure oppure connectionlessconnectionless..

2626

Funzionamento interno Funzionamento interno basato su connessionibasato su connessioni

La subnet stabilisce un circuito virtuale (sul La subnet stabilisce un circuito virtuale (sul quale verrà tipicamente veicolato il traffico quale verrà tipicamente veicolato il traffico di un servizio connection oriented), cioé di un servizio connection oriented), cioé crea un cammino fra la sorgente e la crea un cammino fra la sorgente e la destinazione. Tutti i router lungo tale destinazione. Tutti i router lungo tale cammino ricordano, in una apposita cammino ricordano, in una apposita struttura dati, la parte di loro competenza struttura dati, la parte di loro competenza di tale cammino (e cioé quale linea in di tale cammino (e cioé quale linea in entrata e quale in uscita sono assegnate al entrata e quale in uscita sono assegnate al cammino). Quando arrivano pacchetti che cammino). Quando arrivano pacchetti che contengono l' ID di tale circuito virtuale, contengono l' ID di tale circuito virtuale, essi vengono instradati di conseguenza essi vengono instradati di conseguenza (tutti nello stesso modo).(tutti nello stesso modo).

2727

Funzionamento interno Funzionamento interno connectionlessconnectionless

I router si limitano a instradare ogni I router si limitano a instradare ogni pacchetto che arriva sulla base del suo pacchetto che arriva sulla base del suo indirizzo di destinazione, decidendo di volta indirizzo di destinazione, decidendo di volta in volta come farlo proseguire. I router in volta come farlo proseguire. I router hanno delle hanno delle tabelle di instradamentotabelle di instradamento ((routing tablerouting table) che indicano, per ogni ) che indicano, per ogni possibile destinazione, quale linea in uscita possibile destinazione, quale linea in uscita utilizzare; si noti che queste tabelle esistono utilizzare; si noti che queste tabelle esistono anche nelle subnet del tipo precedente, anche nelle subnet del tipo precedente, dove però servono solamente nella fase di dove però servono solamente nella fase di setup della connessione (per decidere come setup della connessione (per decidere come instradare i pacchetti di setup). instradare i pacchetti di setup).

2828

Funzionamento interno Funzionamento interno connectionlessconnectionless

Quando offre un servizio connection-Quando offre un servizio connection-oriented, questo livello fa credere al oriented, questo livello fa credere al livello superiore che esista una livello superiore che esista una connessione, ma poi i pacchetti connessione, ma poi i pacchetti viaggiano indipendentemente (e viaggiano indipendentemente (e quindi hanno tutti l'indirizzo del quindi hanno tutti l'indirizzo del destinatario) e vengono rimessi in destinatario) e vengono rimessi in ordine dal livello network solo a ordine dal livello network solo a destinazione, prima di essere destinazione, prima di essere consegnati al livello superiore.consegnati al livello superiore.

2929

Combinazioni di Combinazioni di servizio offertoservizio offerto

È possibile avere tutte le quattro È possibile avere tutte le quattro combinazioni di servizio offerto e combinazioni di servizio offerto e implementazione della subnet: implementazione della subnet:

• servizi connection oriented su circuiti servizi connection oriented su circuiti virtuali; virtuali;

• servizi connectionless su subnet servizi connectionless su subnet datagram; datagram;

• servizi connection oriented su subnet servizi connection oriented su subnet datagram (si cerca di fornire datagram (si cerca di fornire comunque un servizio robusto); comunque un servizio robusto);

• servizi connectionless su circuito servizi connectionless su circuito virtuale (esempio: IP su subnet ATM).virtuale (esempio: IP su subnet ATM).

3030

Algoritmi di routingAlgoritmi di routing

La funzione principale del livello network è di La funzione principale del livello network è di instradare i pacchetti sulla subnet.instradare i pacchetti sulla subnet.

Un Un algoritmo di routingalgoritmo di routing è quella parte del è quella parte del software di livello network che decide su software di livello network che decide su quale linea di uscita instradare un pacchetto quale linea di uscita instradare un pacchetto che è arrivato: che è arrivato:

• in una subnet datagram l'algoritmo viene in una subnet datagram l'algoritmo viene applicato ex novo ad ogni pacchetto; applicato ex novo ad ogni pacchetto;

• in una subnet basata su circuiti virtuali in una subnet basata su circuiti virtuali l'algoritmo viene applicato solo nella fase di l'algoritmo viene applicato solo nella fase di setup del circuito; in tale contesto si usa setup del circuito; in tale contesto si usa spesso il termine spesso il termine session routingsession routing..

3131


Da un algoritmo di routing si desidera: Da un algoritmo di routing si desidera: • correttezza (deve inviare il pacchetto nella correttezza (deve inviare il pacchetto nella

giusta direzione); giusta direzione); • semplicità (l'implementazione non deve semplicità (l'implementazione non deve

essere troppo complicata); essere troppo complicata); • robustezza (deve funzionare anche in caso di robustezza (deve funzionare anche in caso di

cadute di linee e/o router e di riconfigurazioni cadute di linee e/o router e di riconfigurazioni della topologia); della topologia);

• stabilità (deve convergere, e possibilmente in stabilità (deve convergere, e possibilmente in fretta); fretta);

• equità (non deve favorire nessuno); equità (non deve favorire nessuno); • ottimalità (deve scegliere la soluzione ottimalità (deve scegliere la soluzione

globalmente migliore).globalmente migliore).

3232


Purtroppo, gli ultimi due requisiti sono spesso in Purtroppo, gli ultimi due requisiti sono spesso in conflitto fra loro; inoltre, a proposito conflitto fra loro; inoltre, a proposito dell'ottimalità, non sempre è chiaro cosa si dell'ottimalità, non sempre è chiaro cosa si voglia ottimizzare. Infatti, supponiamo che si voglia ottimizzare. Infatti, supponiamo che si vogliano: vogliano:

• minimizzare il ritardo medio pacchetti; minimizzare il ritardo medio pacchetti; • massimizzare il throughput totale dei pacchetti. massimizzare il throughput totale dei pacchetti. Si scopre facilmente che questi due obiettivi sono Si scopre facilmente che questi due obiettivi sono

in conflitto fra loro, perché di solito aumentare in conflitto fra loro, perché di solito aumentare il throughput allunga le code sui router e quindi il throughput allunga le code sui router e quindi aumenta il ritardo: questo è vero per qualunque aumenta il ritardo: questo è vero per qualunque sistema basato su code gestito in prossimità sistema basato su code gestito in prossimità della sua capacità massima.della sua capacità massima.

3333


Gli algoritmi di routing si dividono in due Gli algoritmi di routing si dividono in due classi principali: classi principali:

• algoritmi non adattativialgoritmi non adattativi ( (statici, statici, deterministicideterministici) in cui le decisioni di ) in cui le decisioni di routing sono prese in anticipo, all'avvio routing sono prese in anticipo, all'avvio della rete, e sono comunicate ai router della rete, e sono comunicate ai router che poi si attengono sempre a quelle; che poi si attengono sempre a quelle;

• algoritmi adattativialgoritmi adattativi ( (dinamici, non dinamici, non deterministicideterministici) in cui le decisioni di ) in cui le decisioni di routing sono riformulate molto spesso routing sono riformulate molto spesso (sulla base del traffico, della topologia (sulla base del traffico, della topologia della rete, ecc.).della rete, ecc.).

3434


Gli algoritmi adattivi differiscono fra loro per: Gli algoritmi adattivi differiscono fra loro per: • come ricevono le informazioni: come ricevono le informazioni:

localmente; localmente; dai router adiacenti; dai router adiacenti; da tutti i router; da tutti i router;

• quanto spesso rivedono le decisioni: quanto spesso rivedono le decisioni: a intervalli di tempo prefissati; a intervalli di tempo prefissati; quando il carico cambia; quando il carico cambia; quando la topologia cambia; quando la topologia cambia;

• quale metrica di valutazione adottano: quale metrica di valutazione adottano: distanza; distanza; numero di hop; numero di hop; tempo di transito stimato.tempo di transito stimato.

3535

Il principio di Il principio di ottimalitàottimalità

È possibile fare una considerazione generale È possibile fare una considerazione generale sull'ottimalità dei cammini, sull'ottimalità dei cammini, indipendentemente dallo specifico algoritmo indipendentemente dallo specifico algoritmo adottato per selezionarli.adottato per selezionarli.

Il Il principio di ottimalitàprincipio di ottimalità afferma che se il router afferma che se il router j è nel cammino ottimo fra i e k, allora anche j è nel cammino ottimo fra i e k, allora anche il cammino ottimo fra j e k è sulla stessa il cammino ottimo fra j e k è sulla stessa strada:strada:

ij

k

Cammino ottimo fra i e k

3636

Il principio di Il principio di ottimalitàottimalità

Se così non fosse, ci sarebbe un altro cammino Se così non fosse, ci sarebbe un altro cammino fra j e k migliore di quello che è parte del fra j e k migliore di quello che è parte del cammino ottimo fra i e k, ma allora ci sarebbe cammino ottimo fra i e k, ma allora ci sarebbe anche un cammino fra i e k migliore di quello anche un cammino fra i e k migliore di quello ottimo.ottimo.

Una diretta conseguenza è che l'insieme dei Una diretta conseguenza è che l'insieme dei cammini ottimi da tutti i router a uno specifico cammini ottimi da tutti i router a uno specifico router di destinazione costituiscono un router di destinazione costituiscono un alberoalbero, , detto detto sink treesink tree per quel router. per quel router.

In sostanza, gli algoritmi di routing cercano e In sostanza, gli algoritmi di routing cercano e trovano i sink tree relativi a tutti i possibili trovano i sink tree relativi a tutti i possibili router di destinazione, e quindi instradano i router di destinazione, e quindi instradano i pacchetti esclusivamente lungo tali sink tree.pacchetti esclusivamente lungo tali sink tree.

3737

Algoritmi staticiAlgoritmi statici

Questi algoritmi sono eseguiti solamente Questi algoritmi sono eseguiti solamente all'avvio della rete, e le decisioni di all'avvio della rete, e le decisioni di routing a cui essi pervengono sono poi routing a cui essi pervengono sono poi applicate senza più essere modificate. In applicate senza più essere modificate. In sostanza utilizzano criteri fissi di sostanza utilizzano criteri fissi di instradamento.instradamento.

I principali algoritmi statici risultano essere:I principali algoritmi statici risultano essere:• il il Fixed Directory RoutingFixed Directory Routing;;• Il Il FloodingFlooding..

3838

Fixed Directory Fixed Directory RoutingRouting

Ogni nodo ha una tabella di Ogni nodo ha una tabella di instradamento, scritta manualmente dal instradamento, scritta manualmente dal gestore della rete, che mette in gestore della rete, che mette in corrispondenza il nodo da raggiungere corrispondenza il nodo da raggiungere con la linea da utilizzare. In questo con la linea da utilizzare. In questo modo il gestore ha il totale controllo del modo il gestore ha il totale controllo del traffico, ma deve obbligatoriamente traffico, ma deve obbligatoriamente intervenire ogni volta che si verifica un intervenire ogni volta che si verifica un guasto. Sono state comunque introdotte guasto. Sono state comunque introdotte delle tabelle con più alternative di delle tabelle con più alternative di scelta e che ben si adattano al variare scelta e che ben si adattano al variare dello stato della rete.dello stato della rete.

3939

Fixed Directory Fixed Directory RoutingRouting

pol88a L2 L4

vaxrom L4 L3

vaxto L2 L5

infngw L1 L7

poldid L6 -

vaxlnf L2 L4

IS

L1

L2

L3L4

L5

L6

L7L8 Indirizzo

Prima sceltaSeconda scelta

4040

FloodingFlooding

In questo tipo di algoritmo ciascun In questo tipo di algoritmo ciascun pacchetto in arrivo viene pacchetto in arrivo viene ritrasmesso su tutte le linee ad ritrasmesso su tutte le linee ad eccezione di quella su cui è stato eccezione di quella su cui è stato ricevuto. Induce ad un carico ricevuto. Induce ad un carico elevato sulla rete e per questo si è elevato sulla rete e per questo si è pensato di introdurre il pensato di introdurre il selective selective floodingflooding secondo cui i pacchetti secondo cui i pacchetti vengono ritrasmessi solamente a vengono ritrasmessi solamente a linee selezionate.linee selezionate.

4141

FloodingFlooding

L'algoritmo può inoltre essere L'algoritmo può inoltre essere migliorato scartando pacchetti migliorato scartando pacchetti troppo vecchi (nell'header del troppo vecchi (nell'header del pacchetto viene inserito un pacchetto viene inserito un age-age-countercounter che indica il numero di che indica il numero di router attraversati) o quelli che router attraversati) o quelli che attraversano per una seconda volta attraversano per una seconda volta un nodo (ogni nodo deve però un nodo (ogni nodo deve però mantenere in memoria tutti i mantenere in memoria tutti i pacchetti che lo attraversano). pacchetti che lo attraversano).

4242

Algoritmi dinamiciAlgoritmi dinamici

Nelle moderne reti si usano algoritmi Nelle moderne reti si usano algoritmi dinamici, che si adattano dinamici, che si adattano automaticamente ai cambiamenti della automaticamente ai cambiamenti della rete. Questi algoritmi non sono eseguiti rete. Questi algoritmi non sono eseguiti solo all'avvio della rete, ma rimangono in solo all'avvio della rete, ma rimangono in esecuzione sui router durante il normale esecuzione sui router durante il normale funzionamento della rete. È importante funzionamento della rete. È importante notare che le tabelle dipendono dalle notare che le tabelle dipendono dalle informazioni che sopraggiungono dalla informazioni che sopraggiungono dalla rete (topologia, costi dei cammini, stato rete (topologia, costi dei cammini, stato dei dispositivi).dei dispositivi).

4343

Algoritmi dinamiciAlgoritmi dinamici

Possono classificarsi in:Possono classificarsi in:• Routing centralizzatoRouting centralizzato;;• Routing isolatoRouting isolato;;• Routing distribuitoRouting distribuito..

4444

Routing centralizzatoRouting centralizzato

Si avvicina molto al Si avvicina molto al fixed directory fixed directory routingrouting. In questo tipo di algoritmo . In questo tipo di algoritmo viene definito il viene definito il Routing Control Routing Control CenterCenter ( (RCCRCC) che riceve dai nodi ) che riceve dai nodi le informazioni della rete. Queste le informazioni della rete. Queste informazioni vengono utilizzate informazioni vengono utilizzate dall'RCC per calcolare le nuove dall'RCC per calcolare le nuove tabelle di instradamento che tabelle di instradamento che vengono poi distribuite ai router.vengono poi distribuite ai router.

4545

Routing centralizzatoRouting centralizzato

Il routing centralizzato sicuramente Il routing centralizzato sicuramente ottimizza le prestazioni, ma ottimizza le prestazioni, ma induce ad un notevole carico sulla induce ad un notevole carico sulla rete (specie in prossimità dei rete (specie in prossimità dei nodi). Inoltre è poco robusto in nodi). Inoltre è poco robusto in quanto aggiornamenti parziali quanto aggiornamenti parziali delle tabelle dovuti a guasti sulla delle tabelle dovuti a guasti sulla rete possono generare dei loop.rete possono generare dei loop.

4646

Routing isolatoRouting isolato

Ogni nodo si calcola indipendentemente Ogni nodo si calcola indipendentemente le tabelle di instradamento senza che le tabelle di instradamento senza che avvenga uno scambio di informazioni avvenga uno scambio di informazioni con gli altri router. Esistono due tipi di con gli altri router. Esistono due tipi di algoritmi di routing isolato: con l'algoritmi di routing isolato: con l'hot hot potatopotato il router cerca di liberarsi del il router cerca di liberarsi del pacchetto nel minor tempo possibile, pacchetto nel minor tempo possibile, ritrasmettendolo sulla linea con la coda ritrasmettendolo sulla linea con la coda di trasmissione più corta; con il di trasmissione più corta; con il backward learningbackward learning i pacchetti i pacchetti aggiornano un campo in cui vengono aggiornano un campo in cui vengono sommati i costi delle linee attraversate.sommati i costi delle linee attraversate.

4747

Routing isolatoRouting isolato

Analizzando questo campo, i router Analizzando questo campo, i router "imparano" quanto è distante il "imparano" quanto è distante il mittente tramite la linea in cui è mittente tramite la linea in cui è avvenuta la ricezione. Questa avvenuta la ricezione. Questa tecnica non è però in grado di tecnica non è però in grado di rilevare la non disponibilità di un rilevare la non disponibilità di un cammino e pertanto occorre limitare cammino e pertanto occorre limitare la validità temporale delle la validità temporale delle informazioni acquisite.informazioni acquisite.

4848

Routing distribuitoRouting distribuito

È una scelta intermedia a quelle È una scelta intermedia a quelle precedenti. Ogni router calcola le precedenti. Ogni router calcola le sue tabelle di instradamento sue tabelle di instradamento scambiando informazioni (tramite scambiando informazioni (tramite protocolli ausiliari di livello tre) con protocolli ausiliari di livello tre) con gli altri router e con gli end-node. Il gli altri router e con gli end-node. Il routing distribuito viene routing distribuito viene implementato mediante algoritmi implementato mediante algoritmi Distance VectorDistance Vector o o Link State PacketLink State Packet..

4949

Distance VectorDistance Vector

L'algoritmo adattativo L'algoritmo adattativo Distance VectorDistance Vector, , noto anche come algoritmo di noto anche come algoritmo di Bellman-Bellman-FordFord, è caratterizzato dal fatto che ogni , è caratterizzato dal fatto che ogni router mantiene contemporaneamente router mantiene contemporaneamente una tabella di instradamento ed una una tabella di instradamento ed una struttura dati per ogni linea (denominata struttura dati per ogni linea (denominata distance vectordistance vector). Le informazioni ). Le informazioni contenute in tale struttura sono ricavabili contenute in tale struttura sono ricavabili dalla tabella di instradamento del router dalla tabella di instradamento del router collegato all'altro capo della linea.collegato all'altro capo della linea.

5050


Ogni nodo infatti, quando modifica Ogni nodo infatti, quando modifica le proprie tabelle di le proprie tabelle di instradamento, invia ai nodi instradamento, invia ai nodi adiacenti una triplaadiacenti una tripla

[indirizzo - hops - costo][indirizzo - hops - costo]

che rappresenta il distance vector.che rappresenta il distance vector.

5151


Le nuove tabelle di instradamento Le nuove tabelle di instradamento sono ricavabili mediante fusione dei sono ricavabili mediante fusione dei distance vector associati alle linee distance vector associati alle linee attive di un nodo. Per quanto attive di un nodo. Per quanto riguarda il ricalcolo delle tabelle, riguarda il ricalcolo delle tabelle, questo avviene quando il router questo avviene quando il router rileva una caduta di una linea attiva rileva una caduta di una linea attiva o quando riceve un distance vector o quando riceve un distance vector da un nodo adiacente diverso da da un nodo adiacente diverso da quello in memoria.quello in memoria.

5252


Il vantaggio del distance vector è la Il vantaggio del distance vector è la facile implementazione. Gli facile implementazione. Gli svantaggi sono una complessità svantaggi sono una complessità elevata per reti non partizionate elevata per reti non partizionate gerarchicamente, la lenta gerarchicamente, la lenta convergenza ad un instradamento convergenza ad un instradamento stabile, la difficoltà di prevederne il stabile, la difficoltà di prevederne il comportamento su grandi reti e la comportamento su grandi reti e la possibilità che si inneschino dei possibilità che si inneschino dei loop.loop.

5353

Due router Distance Due router Distance VectorVector

Costo 5Tabellainstradam.

di A

Distancevector di B

Router A(indirizzo 3)

Tabellainstradam.

di B

Distancevector di A

Router B(indirizzo 7)

L3 L8

5454

Tabella di Tabella di instradamento di Ainstradamento di A

Indirizzo Hops Costo Linea

1 5 25 3

2 3 20 2

3 0 0 0

4 2 15 3

5 7 55 1

6 4 23 1

7 1 5 3

... ... ... ...

5555

Distance Vector di A Distance Vector di A memorizzato in Bmemorizzato in B

Indirizzo Hops Costo

1 6 30

2 4 25

3 1 5

4 3 20

5 8 60

6 5 28

7 2 10

... ... ...

5656

Fusione di Distance Fusione di Distance VectorVector

I H C1 3 152 5 443 2 114 3 115 4 306 2 147 2 10 ... ... ...

Linea 1

I H C1 4 202 3 253 3 434 4 205 4 306 2 147 2 10 ... ... ...

Linea 3

I H C1 6 302 4 253 1 54 3 205 8 606 5 287 2 10 ... ... ...

Linea 8

I H C7 0 0

Linea 0

I H C L1 3 15 12 3 25 33 1 5 84 3 11 15 4 30 16 2 14 37 0 0 0 ... ... ...

DistanceVector

Tabella di Instradamento

5757

Link State PacketLink State Packet

L'algoritmo adattativo L'algoritmo adattativo Link State Link State PacketPacket prevede che ogni router prevede che ogni router impari, mediante protocolli di impari, mediante protocolli di neighbor greetingsneighbor greetings, le , le informazioni del suo ambito informazioni del suo ambito locale.locale.

5858


Queste informazioni vengono inviate in Queste informazioni vengono inviate in floodingflooding a tutti gli altri router della rete a tutti gli altri router della rete mediante un mediante un link state packetlink state packet. . Quest’ultimo contiene lo stato di ogni Quest’ultimo contiene lo stato di ogni link connesso al router, il costo del link, link connesso al router, il costo del link, l'identità del vicino, il tempo di vita, il l'identità del vicino, il tempo di vita, il checksum ed il numero di sequenza checksum ed il numero di sequenza dello stesso); in questo modo i router, dello stesso); in questo modo i router, memorizzando i dati contenuti nel LSP, memorizzando i dati contenuti nel LSP, costruiscono la mappa aggiornata della costruiscono la mappa aggiornata della rete. Tale mappa viene anche chiamata rete. Tale mappa viene anche chiamata LSP databaseLSP database e risulta essere la matrice e risulta essere la matrice delle adiacenze del grafo della rete.delle adiacenze del grafo della rete.

5959

Allineamento dei LSP Allineamento dei LSP database database

Un router LSP, all'atto del ricevimento di un Un router LSP, all'atto del ricevimento di un LSP (trasmesso in flooding) allinea il LSP (trasmesso in flooding) allinea il proprio LSP database nel seguente modo:proprio LSP database nel seguente modo:

• se non ha mai ricevuto LSP da quel se non ha mai ricevuto LSP da quel mittente o se il numero di sequenza del mittente o se il numero di sequenza del LSP è maggiore di quello del LSP LSP è maggiore di quello del LSP proveniente dalla stessa sorgente e proveniente dalla stessa sorgente e memorizzato nel LSP database, allora memorizzato nel LSP database, allora memorizza il pacchetto nel LSP database memorizza il pacchetto nel LSP database e lo ritrasmette in flooding su tutte le e lo ritrasmette in flooding su tutte le linee eccetto quella da cui l'ha ricevuto;linee eccetto quella da cui l'ha ricevuto;

6060

Allineamento dei LSP Allineamento dei LSP databasedatabase

• se il LSP ricevuto ha lo stesso numero di se il LSP ricevuto ha lo stesso numero di sequenza di quello posseduto, allora non sequenza di quello posseduto, allora non occorre fare nulla perché lo stesso occorre fare nulla perché lo stesso pacchetto era già stato pacchetto era già stato precedentemente trasmesso in flooding;precedentemente trasmesso in flooding;

• se il LSP è più vecchio di quello se il LSP è più vecchio di quello posseduto, cioè obsoleto, allora il router posseduto, cioè obsoleto, allora il router ricevente trasmette il LSP aggiornato al ricevente trasmette il LSP aggiornato al router mittente.router mittente.

6161

LSP trasmesso da R1LSP trasmesso da R1

A B CR1

R2

R3

Costo 3

Costo 5

Costo 4

Adiacenza Costo A 4 B 4 C 4 R1 0 R2 3 R3 5

LSP trasmesso da R1

R4

6262

Grafo della rete e LSP Grafo della rete e LSP databasedatabase

F

E

DB

A C2

13

2

12

5

41

A B/2

B A/2 D/3 E/2

C D/1

D B/3 C/1 G/1

E B/2 F/5 G/2

F E/5 H/4

G D/1 E/2 H/1

H F/4 G/1

LSP Database

(replicato su ogni IS)H

G

6363

Albero e Tabella di BAlbero e Tabella di B

H

G

F

E

DB

A C2 13

2

2

51

L1L2L3 A L1

C L2

D L2

E L3

F L3

G L3

H L3

ForwardingTable di B

6464

Pseudo-nodo Pseudo-nodo

È un nodo fittizio non presente nella rete e È un nodo fittizio non presente nella rete e rappresenta una LAN. Esso viene realizzato rappresenta una LAN. Esso viene realizzato dal designated router per avere una topologia dal designated router per avere una topologia equivalente a stella con al centro appunto il equivalente a stella con al centro appunto il nodo. Questo trucco viene adottato nodo. Questo trucco viene adottato dall'algoritmo adattativo Link State Packet, il dall'algoritmo adattativo Link State Packet, il quale presuppone di lavorare su canali punto-quale presuppone di lavorare su canali punto-punto; occorre infatti ricordare che le reti si punto; occorre infatti ricordare che le reti si comportano come canali broadcast e la più comportano come canali broadcast e la più semplice struttura equivalente risulterebbe semplice struttura equivalente risulterebbe una maglia completa. Ciò non è accettabile in una maglia completa. Ciò non è accettabile in quanto i link crescono quadraticamente quanto i link crescono quadraticamente rispetto alla crescita dei nodi, rendendone rispetto alla crescita dei nodi, rendendone improponibile qualsiasi approccio. improponibile qualsiasi approccio.

6565

Pseudo-nodoPseudo-nodo

A B C D E F

A

B C D E

Fpseudonodo

Router

End Node

Verso altri router

Verso altri router

Topologia Fisica

Topologia equivalente

6666


I vantaggi di questo algoritmo I vantaggi di questo algoritmo risiedono nel fatto che può gestire risiedono nel fatto che può gestire reti di notevoli dimensioni, reti di notevoli dimensioni, difficilmente genera loop e ha una difficilmente genera loop e ha una rapida convergenza ad un rapida convergenza ad un instradamento stabile. Gli svantaggi instradamento stabile. Gli svantaggi sono riferibili invece nella difficile sono riferibili invece nella difficile implementazione a causa di implementazione a causa di meccanismi speciali di gestione meccanismi speciali di gestione della LAN.della LAN.

6767

Neighbor GreetingsNeighbor Greetings

Il neighbor greetings è un meccanismo che Il neighbor greetings è un meccanismo che consente agli End System di conoscere gli consente agli End System di conoscere gli Intermediate System presenti sulla rete e Intermediate System presenti sulla rete e viceversa. Come funziona: gli ES inviano viceversa. Come funziona: gli ES inviano periodicamente degli periodicamente degli End System HelloEnd System Hello ( (ESHESH) ) per informare agli IS della loro presenza; gli IS per informare agli IS della loro presenza; gli IS inviano periodicamente degli inviano periodicamente degli Intermediate Intermediate System HelloSystem Hello ( (ISHISH) per lo stesso motivo. Il ) per lo stesso motivo. Il neighbor greetings consente inoltre agli IS di neighbor greetings consente inoltre agli IS di apprendere tramite pacchetti di apprendere tramite pacchetti di routing redirectrouting redirect se un nodo è direttamente raggiungibile sulla se un nodo è direttamente raggiungibile sulla LAN oppure qual è il miglio router tramite il LAN oppure qual è il miglio router tramite il quale è possibile raggiungerlo.quale è possibile raggiungerlo.

6868

Neighbor GreetingsNeighbor Greetings

ISES

ESH

ISH

Routing Redirect

6969

Routing gerarchicoRouting gerarchico

Quando la rete cresce fino Quando la rete cresce fino contenere decine di migliaia di contenere decine di migliaia di nodi, diventa troppo gravoso nodi, diventa troppo gravoso mantenere in ogni router la mantenere in ogni router la completa topologia. Il routing va completa topologia. Il routing va quindi impostato in modo quindi impostato in modo gerarchico, come succede nei gerarchico, come succede nei sistemi telefonici.sistemi telefonici.

7070


La rete viene divisa in La rete viene divisa in zone zone (spesso dette (spesso dette regioniregioni): ): • all'interno di una regione i router (detti all'interno di una regione i router (detti router router

interniinterni) sanno come arrivare a tutti gli altri ) sanno come arrivare a tutti gli altri router della regione stessa; router della regione stessa;

• viceversa, quando un router interno deve viceversa, quando un router interno deve spedire qualcosa a un router di un'altra regione spedire qualcosa a un router di un'altra regione sa soltanto che deve farlo pervenire a un sa soltanto che deve farlo pervenire a un particolare router della propria regione, detto particolare router della propria regione, detto router di confinerouter di confine. .

• il router di confine sa a quale altro router di il router di confine sa a quale altro router di confine deve inviare i dati perché arrivino alla confine deve inviare i dati perché arrivino alla regione di destinazione.regione di destinazione.

7171


Di conseguenza, ci solo due livelli di Di conseguenza, ci solo due livelli di routing: routing:

• un primo livello di routing un primo livello di routing all'interno di ogni regione; all'interno di ogni regione;

• un secondo livello di routing fra un secondo livello di routing fra tutti i router di confine.tutti i router di confine.

7272


Router interniRouter di confine

Regione

7373


I router interni mantengono nelle loro tabelle di I router interni mantengono nelle loro tabelle di routing: routing:

• una entrata per ogni altro router interno, con una entrata per ogni altro router interno, con la relativa linea da usare per arrivarci; la relativa linea da usare per arrivarci;

• una entrata per ogni altra regione, con una entrata per ogni altra regione, con l'indicazione del relativo router di confine e l'indicazione del relativo router di confine e della linea da usare per arrivarci. della linea da usare per arrivarci.

I router di confine, invece, mantengono una I router di confine, invece, mantengono una entrata per ogni altra regione, con entrata per ogni altra regione, con l'indicazione del prossimo router di confine l'indicazione del prossimo router di confine da contattare e della linea da usare per da contattare e della linea da usare per arrivarci. arrivarci.

Non è detto che due livelli siano sufficienti. In Non è detto che due livelli siano sufficienti. In tal caso il discorso si ripete su più livelli.tal caso il discorso si ripete su più livelli.

7474

Il pacchetto di livello 3Il pacchetto di livello 3

I campi principali di un pacchetto di livello 3 I campi principali di un pacchetto di livello 3 (protocolli connectionless) sono:(protocolli connectionless) sono:

• indirizzi del mittente e del destinatario;indirizzi del mittente e del destinatario;• lunghezze dell'header e del campo dati;lunghezze dell'header e del campo dati;• checksum dell'header (per la protezione dello checksum dell'header (per la protezione dello

header stesso);header stesso);• indicatori di frammentazione;indicatori di frammentazione;• lifetime (per evitare situazioni di loop);lifetime (per evitare situazioni di loop);• opzioni, tra cui:opzioni, tra cui:

security;security; source routing.source routing.

7575

I gatewayI gateway

Applicazione

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

Applicazione

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

Applicazione

GATEWAY

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

Presentazione

Sessione

Trasporto

Rete

Data Link

Fisico

7676

I gatewayI gateway

I Gateway servono a collegare due applicativi I Gateway servono a collegare due applicativi con funzionalità simili appartenenti ad con funzionalità simili appartenenti ad architetture di rete diverse.architetture di rete diverse.

Lavorando a livello di applicativo si collocano Lavorando a livello di applicativo si collocano a livello 7 OSI.a livello 7 OSI.

Esempio classico di gateway è quello per la Esempio classico di gateway è quello per la posta elettronica.posta elettronica.

Esistono gateway tra i tre applicativi Esistono gateway tra i tre applicativi principali (terminale virtuale, file transfer e principali (terminale virtuale, file transfer e posta elettronica) delle tre principali posta elettronica) delle tre principali architetture di rete (SNA, DECNET, TCP/IP).architetture di rete (SNA, DECNET, TCP/IP).

7777

Domande di riepilogoDomande di riepilogo

• Che cosa sono gli IS e gli ES?Che cosa sono gli IS e gli ES?• Con quali altri termini sono spesso Con quali altri termini sono spesso

indicati?indicati?• Quali servizi può offrire il livello 3?Quali servizi può offrire il livello 3?• Come funziona un Multiprotocol Router?Come funziona un Multiprotocol Router?• Come funziona un Brouter?Come funziona un Brouter?• Quali sono le tre principali tecniche di Quali sono le tre principali tecniche di

instradamento?instradamento?

7878


• Quanti e quali tipi di indirizzi Quanti e quali tipi di indirizzi determinano l'instradamento di un determinano l'instradamento di un pacchetto sulla rete?pacchetto sulla rete?

• Qual è il loro ruolo?Qual è il loro ruolo?• Quale problematica viene indicata con il Quale problematica viene indicata con il

termine di neighbor greeting?termine di neighbor greeting?• Quali sono i due principali criteri di Quali sono i due principali criteri di

ottimalità usati nell'instradamento?ottimalità usati nell'instradamento?• Quali sono le due metriche principali?Quali sono le due metriche principali?

7979


• Quali sono gli algoritmi di routing non Quali sono gli algoritmi di routing non adattativo?adattativo?

• Quali sono gli algoritmi di routing Quali sono gli algoritmi di routing adattativo?adattativo?

• Dove trova impiego il routing isolato?Dove trova impiego il routing isolato?• Quali sono gli algoritmi di routing Quali sono gli algoritmi di routing

distribuito?distribuito?• Si descriva l'algoritmo Distance Vector.Si descriva l'algoritmo Distance Vector.• Si descriva l'algoritmo Link State Si descriva l'algoritmo Link State

Packet.Packet.

8080


Con quale tecnica i router LSP mantengono Con quale tecnica i router LSP mantengono allineati i loro LSP database?allineati i loro LSP database?

• Quali tecniche utilizzano per gestire le Quali tecniche utilizzano per gestire le LAN?LAN?

• Che cos'è il neighbor greetings?Che cos'è il neighbor greetings?• Che cos'è il routing gerarchico?Che cos'è il routing gerarchico?• Perché lo si utilizza?Perché lo si utilizza?• Quali sono i campi principali di un Quali sono i campi principali di un

pacchetto di livello 3?pacchetto di livello 3?• Che cos'è un gateway?Che cos'è un gateway?

RETI DI CALCOLATORI Quinta Esercitazione. 2 I router Applicazione Presentazione Sessione Trasporto...

Documents

Transcript of RETI DI CALCOLATORI Quinta Esercitazione. 2 I router Applicazione Presentazione Sessione Trasporto...