16: Network layer: introduzioneintroduzione, algoritmi...

1

16: Network layer:16: Network layer:

introduzioneintroduzione, , algoritmialgoritmi di routingdi routing

R. Cusani - F. Cuomo, Telecomunicazioni - Network layer: Routing, Maggio 2010

1

Funzioni dello strato di reteFunzioni dello strato di rete

� Allo strato di trasporto la comunicazione tra i processi paritari di livello 4 deve

apparire come una comunicazione punto-punto

� Lo strato di rete ha quindi come funzione quella di fornire allo strato di

trasporto un servizio per la consegna dei dati in modo da mascherare

l’infrastruttura della rete (la sottorete)

� Nomenclatura:

⇒ host o end-node: stazione su cui opera lo strato di trasporto che deve

trasmettere o ricevere i dati utilizzando il servizio dello strato di rete

⇒ pacchetto: insieme di dati+header+trailer che lo strato di rete costruisce e

deve trasmettere fino a destinazione

⇒ router: stazione intermedia che opera a livello 3, che riceve i pacchetti e li

inoltra attraverso la (sotto)rete


2

2

Funzioni dello strato di rete (Funzioni dello strato di rete (contcont.).)

� In generale due host sono separati da un certo numero di nodi, interconnessi

da svariate linee

� Spesso sono possibili più tragitti tra i due nodi (ad esempio nelle reti magliate)

� Potenzialmente i nodi sono separati da reti funzionanti con tecnologie

differenti


3

Funzioni dello strato di rete (Funzioni dello strato di rete (contcont.).)

� Lo strato di rete deve quindi occuparsi dei seguenti argomenti

⇒ determinare quale tragitto tra quelli disponibili dovranno seguire i dati

(instradamento, routing) - questo può richiedere che lo strato di rete

conosca la topologia della rete

⇒ reagire a modifiche di topologie della rete - se esiste un meccanismo

dinamico per l’apprendimento della topologia, questo permetterà di

apprenderne anche le modifiche nel tempo

⇒ evitare di sovraccaricare linee quando sono disponibili percorsi alternativi

(congestione)

⇒ risolvere i problemi connessi al transito attraverso reti differenti

(internetworking) - quest’ultima funzione è caratteristica del TCP/IP


4

3

Servizi offerti allo strato superioreServizi offerti allo strato superiore

� Inizialmente OSI prevedeva che lo strato di rete fornisse solo un servizio

connection oriented

⇒ analogo al funzionamento del servizio telefonico

⇒ questo servizio, caldeggiato dalle compagnie telefoniche, permette di

operare fatturazione a tempo e di offrire servizi di qualità riservando le

risorse a priori

� In seguito c’è stata forte richiesta di introdurre nello standard anche un

servizio connection less, e così è stato fatto

⇒ l’inaffidabilità intrinseca della sottorete fa si che comunque lo strato di

trasporto dovrà occuparsi della integrità dei dati

⇒ può quindi essere opportuno un meccanismo più leggero per il recapito

dei dati a livello 3


5

ServizioServizio connectionconnection--lessless

� Richiede che i pacchetti siano instradati indipendentemente l’un l’altro

� Generalmente un router dispone di una tabella che definisce la linea di uscita

dove trasmettere un pacchetto in base alla destinazione finale

⇒ il router riceve il pacchetto, lo memorizza per analizzarlo, decide su quale

linea in uscita instradarlo, lo accoda, quindi lo trasmette in base alla

tabella (store and forward)


6

4

ServizioServizio connectionconnection--lessless

� Ogni pacchetto deve quindi contenere l’indirizzo di destinazione

� Le tabelle possono modificarsi nel tempo � i pacchetti possono non seguire

la stessa strada


7

Servizio Servizio connectionconnection--orientedoriented

� Ad una connessione si associa un circuito (eventualmente virtuale) nella

sottorete a lei dedicato

� Sequenza di router del cammino: è definita a priori, durante la fase di

inizializzazione della connessione

� Tutti i pacchetti della stessa connessione seguono la stessa strada

� L’instradamento del pacchetto viene quindi fatto in base alla sua appartenenza

ad una connessione e non alla sua destinazione finale

� L’intestazione del pacchetto sarà più semplice, dovendo contenere solo

l’identificativo della connessione

� La connessione potrà essere stabilita in modo da garantire le risorse necessarie

alla trasmissione, rendendola più affidabile

� Una connessione successiva tra gli stessi nodi potrebbe definire un circuito

virtuale differente dal precedente


8

5

Tabelle per la definizione dei circuiti virtualiTabelle per la definizione dei circuiti virtuali

� Il nodo sceglie un identificativo per il circuito virtuale, utilizzando un numero (il

più basso disponibile)

� Il router adiacente non è detto abbia disponibile l’identificativo scelto dal nodo

⇒ potrebbe averlo già assegnato ad un’altro circuito virtuale proveniente da

un altro nodo

� In generale sceglie un identificativo differente, ma lo associa all’identificativo

scelto dal nodo per i pacchetti provenienti dal nodo stesso

� Questo processo viene iterato fino a destinazione

� Ogni router avrà quindi una tabella del tipo:

Nodo provenienza

Circuito virtualeNodo

destinazioneCircuito virtuale


9

Tabelle per la definizione dei circuiti virtualiTabelle per la definizione dei circuiti virtuali

� Ad ogni pacchetto in arrivo da un certo nodo (host o router) contenente un

certo identificativo, il router cercherà nella tabella l’host a cui inoltrare il

pacchetto e l’identificativo relativo

� Sostituirà l’ID vecchio col nuovo ed inoltrerà il pacchetto


10

6

ConfrontoConfronto

Problema Datagrammi Circuito virtuale

Impostazione circuito Non necessaria Richiesta

Indirizzamento Ogni pacchetto contiene l’indirizzo completo di mittente e destinatario

Ogni pacchetto contiene un numero di circuito virtuale

Informazioni sullo stato I router non conservano informazioni sullo stato delle connessioni

Ogni CV richiede spazio nella tabella dei router per la connessione

Routing Ogni pacchetto viene instradato indipendentemente

Il percorso è definito all’impostazione del CV

Effetto dei guasti Nessuno tranne i pacchetti che si trovano in coda sul router che si guasta al momento del guasto

Tutti i CV che attraversano il router che si guasta vengono terminati

Qualità del servizio Realizzazione complessa Semplice

Controllo congestione Difficile Semplice


11

RoutingRouting ed inoltroed inoltro

� La funzione principale dello strato di rete è il routing

� Questo è il processo che permette al router di scegliere – tramite un algoritmo

– la linea di uscita verso cui instradare i dati

� Si possono distinguere le due operazioni:

⇒ inoltro: il processo che, in base all’indirizzo di destinazione o al circuito

virtuale, sceglie la linea di uscita in funzione di dati noti (tabelle, stato

delle linee, …)

⇒ definzione delle tabelle: il processo di creazione ed aggiornamento della

tabella (detta tabella di routing) che associa alla destinazione la linea di

uscita da utilizzare; questa operazione viene eseguita in base ad

algoritmi detti algoritmi di routing

� In molti casi queste sono operazioni distinte eseguite in momenti diversi da

processi distinti all’interno dello strato di rete


12

7

Caratteristiche di un algoritmo di Caratteristiche di un algoritmo di routingrouting

� è desiderabile che un algoritmo di routing abbia le seguenti caratteristiche

⇒ correttezza: ovvio

⇒ semplicità: meno soggetto ad errori in implementazione o in esecuzione

⇒ robustezza: la rete non è stabile, e l’algoritmo deve poter fare fronte alle

modifiche di topologia

⇒ stabilità: convergenza verso l’equilibrio

⇒ imparzialità: servire qualunque tragitto possibile senza penalizzare

nessuno

⇒ ottimizzazione: efficienza globale


13

Algoritmi adattivi e non adattiviAlgoritmi adattivi e non adattivi

� Esistono due classi di algoritmi di routing

⇒ non adattivi: l’algoritmo per l’instradamento viene calcolato a priori e non

si modifica più (routing statico)

⇒ adattivi: questi algoritmi modificano le tabelle in funzione di cosa accade

sulla rete (modifiche di topologia, carico sulla rete)

� Gli algoritmi adattivi si differenziano in base a:

⇒ sorgente delle informazioni, che possono essere il router stesso, i soli

router adiacenti o tutti i router della rete

⇒ al momento in cui effettuano le modifiche, che possono avvenire ad

intervalli regolari, in funzione del carico della rete o in funzione di

modifiche della topologia

⇒ al tipo di informazioni su cui si basano le decisioni (la metrica): la

distanza, il numero di salti, il tempo di transito stimato, …


14

8

RoutingRouting staticostatico

� Esempio più semplice di algoritmo non adattivo

� La tabella di routing viene inserita a mano nella configurazione del router, e non

viene modificata dinamicamente; eventualmente può essere modificata

manualmente anche in corso d’opera

� Virtualmente ingestibile in condizioni di reti anche banalmente complesse, ma

utilizzato diffusamente per circostanze particolari:

1. un router ha una unica connessione

2. un router ha più di una connessione, ma per tutte le connessioni tranne una c’è

una destinazione che non può

cambiare per motivi di topologia,

e l’ultima connessione deve

essere utilizzata per tutte le altre

destinazioni


15

Instradamento Instradamento multicamminomulticammino

� Questa tecnica si applica quando esistono più percorsi possibili, e si vogliono

utilizzare tutti, ciascuno con intensità di carico potenzialmente differente

� A ciascun cammino viene assegnato un peso, e la scelta di instradamento

viene fatta in base ad una estrazione casuale pesata

� In questo modo si separa il traffico statisticamente con probabilità pari al peso

delle alternative (per ogni pacchetto in caso di protocollo senza connessione,

per ogni circuito virtuale in caso di protocollo connection oriented)


16

9

Instradamento Instradamento floodingflooding

� Altro esempio di algoritmo statico, prevede di inoltrare ogni pacchetto entrante su

tutte le linee disponibili tranne quella da cui è arrivato

� Viene generato un elevato numero di duplicati del pacchetto, che possono anche

ritornare più volte a chi lo ha già ricevuto

⇒ si utilizza in ogni pacchetto un contatore di hop (salti), inizializzato ad un valore

massimo e decrementato da ogni router: allo 0 il pacchetto viene eliminato

� si può anche utilizzare un meccanismo per evitare le ritrasmissioni:

⇒ il router che trasmette per primo il pacchetto gli assegna un numero di

sequenza ed il proprio indirizzo di rete

⇒ ogni router tiene una tabella dei numeri di sequenza originati dai diversi router e

già trasmessi

⇒ se arriva un pacchetto già trasmesso si evita la ritrasmissione

⇒ se i numeri di sequenza sono incrementali, la tabella da memorizzare sarà di

dimensioni ragionevoli (si memorizza solo l’ultimo)


17

Algoritmo Algoritmo floodingflooding ((contcont.).)

� Gli aspetti negativi di questo algoritmo sono essenzialmente legati alla inefficienza

nell’utilizzo delle risorse:

⇒ ogni pacchetto va a finire su tutte le linee della rete, provocando un utilizzo

inefficiente della rete stessa

⇒ ogni pacchetto va a finire su tutti i router, aumentando il carico di lavoro dei

router stessi (CPU, occupazione di buffer)


18

10

Algoritmo Algoritmo floodingflooding ((contcont.).)

� Aspetti positivi sono:

⇒ qualsiasi pacchetto arriverà a destinazione nel tempo più breve possibile

(segue tutte le strade, anche la più veloce)

⇒ estremamente resistente a modifiche della topologia

• anche il malfunzionamento di grandi porzioni della rete permette il recapito

del pacchetto se almeno un cammino rimane operativo

⇒ non richiede una conoscenza a priori della topologia della rete

� Scarsamente utilizzato per via della inefficienza, le caratteristiche di estrema

affidabilità di questo protocollo sono sfruttate in diverse circostanze particolari


19

RoutingRouting dinamico: percorso più brevedinamico: percorso più breve

� Gli algoritmi di routing spesso si basano sulla analisi della rappresentazione

della rete tramite un grafo (i punti identificano i router, gli archi rappresentano le

linee di connessione)

� Per scegliere il percorso ottimale la soluzione è trovare il percorso più breve, in

base ad una certa metrica

� Possono essere scelte differenti metriche:

⇒ distanza geografica

⇒ numero di salti

⇒ costo delle linee

⇒ ritardo temporale (rtt: round trip time)

⇒ larghezza di banda

o una funzione di alcune di queste


20

11

RoutingRouting dinamico: percorso più brevedinamico: percorso più breve

� Definita una metrica, le linee potranno essere etichettate con un numero (peso,

costo o metrica della linea): più basso è il numero, “più breve” è la linea (quindi

preferibile)

� La distanza di un percorso è dato dalla somma delle distanze dei singoli salti

� Dijkstra ha ideato un algoritmo (Shorted Path First) semplice e rapido capace di

determinare, in base alla topologia ed ai pesi, il cammino più breve tra due nodi del

grafo


21

Algoritmo di Algoritmo di DijkstraDijkstra


22

12

DistanceDistance vectorvector ((BellmanBellman--FordFord))

� Algoritmo adattivo sviluppato attorno al 1960, utilizzato per molto tempo

⇒ Arpanet lo ha utilizzato fino al 1979 nella implementazione chiamata RIP

(ancora in uso adesso in realtà di piccole dimensioni)

� Ad ogni linea è assegnata una distanza, valutata in base ad una metrica,

indicata anche col nome di costo

� La tabella di routing è costituita dalla associazione di tre informazioni:

⇒ destinazione, distanza fino alla destinazione, linea di uscita

� Ogni router estrae dalla tabella di routing una tabella contenente, per ogni

destinazione, indirizzo di destinazione e relativa distanza, detta vettore delle

distanze


23


� Il vettore delle distanze viene scambiato ciclicamente con tutti i router

adiacenti

� In base alle informazioni ricevute dai vicini viene aggiornata la tabella di

routing

� Il valore della distanza avrà un certo limite massimo, indicante che la

destinazione non è raggiungibile

⇒ nel caso di metrica ad hop, la distanza di infinito dovrà essere almeno

pari al numero massimo di hop possibili nella rete più uno

⇒ in caso di metrica secondo i ritardi può essere più complesso

determinare l’irraggiungibiltà della destinazione: si deve valutare a priori

un valore ragionevolmente elevato (ma non troppo)


24

13


� Valutazione delle distanze:

⇒ il router deve conoscere i router adiacenti, ed il costo delle linee che li

connettono direttamente

• per fare questo un router scambia a tempi definiti con i propri vicini

dei pacchetti per essere aggiornati sulla loro presenza

• se la metrica scelta dipende dal ritardo della linea, questi pacchetti

sono utilizzati per aggiornare la valutazione del costo della linea

diretta verso il router adiacente

• la metrica può essere un parametro statico, definito manualmente

nella configurazione del router


25


⇒ Quando viene ricevuto il vettore delle distanze dai vicini, per ogni

destinazione si valuta la distanza aggiungendo alla distanza riportata dal

router adiacente quella relativa alla linea che li connette

⇒ Tra tutte le distanze relative alla stessa destinazione riportate dai router

adiacenti, e rivalutate in base alla distanza verso ciascun router

adiacente, si sceglie quella con distanza inferiore


26

14


Esempio: costruzione della tabella di routing del router J


27

Problemi del Problemi del DistanceDistance VectorVector

� Normalmente raggiunge sempre la convergenza ma lentamente, in particolare

in occasione della perdita di un router (o di una linea) � problema noto come

conto all’infinito, che peggiora all’aumentare del numero di router

� Nell’esempio seguente si valuta la distanza a cui il router A è visto dagli altri

� a sinistra si vede cosa accade quando il router A viene acceso, a destra se si

spegne o se va giù il link con B (tutti i costi sono pari a 1)


28

Nel secondo caso si vede come l’informazione che A non è piùraggiungibile si propaga con lentezza

15

Link StateLink State

� Basa il suo funzionamento sulla conoscenza che ciascun router deve avere

della intera topologia della rete, superando i problemi del distance vector

� L’algoritmo si sviluppa secondo i seguenti punti:

⇒ scoprire i router adiacenti ed i loro indirizzi

⇒ misurare il costo della linea verso ogni vicino

⇒ costruire un pacchetto contenente questi dati (link state, o stato dei

collegamenti)

⇒ inviare questa informazione a tutti i router della rete

⇒ ricostruire la topologia della rete in base alle informazioni di link state

ricevute da tutti gli altri router

⇒ elaborare in base alla conoscenza della topologia i percorsi più brevi per

ogni destinazione


29

Scoperta dei viciniScoperta dei vicini

� Per realizzare questa funzione il protocollo prevede che un router invii ciclicamente

(a cominciare dalla sua accensione) sulle linee a disposizione dei pacchetti speciali

detti “HELLO”

� Questi pacchetti contengono l’indirizzo di rete del router che lo invia

⇒ l’indirizzo del router deve essere unico in tutta la rete, per poter essere distinto

da tutti gli altri

� Il router che riceve un HELLO, deve rispondere con un pacchetto analogo

� In questo modo un router, alla accensione, impara a conoscere tutti i vicini, ed i

vicini acquisicono l’informazione della esistenza del nuovo router


30

16

Misura del costo della lineaMisura del costo della linea

� L’algoritmo si basa, come vedremo, sulla conoscenza del costo delle linee

dirette con i router vicini

� Come prima, sono possibili diverse metriche

⇒ generalmente il router utilizza un pacchetto speciale, detto ECHO, al

quale il router adiacente deve rispondere immediatamente

⇒ misurando il tempo di andata e ritorno e dividendo per due si ha una

misura del ritardo della linea

� è possibile inserire nel computo il ritardo dovuto al carico del traffico,

contando il tempo di accodamento del pacchetto


31

Misura del costo della lineaMisura del costo della linea

� questa soluzione può comportare instabilità nel routing: nel caso di un doppio

cammino, quello migliore sarà caricato di traffico, quindi l’altro, scarico,

diventerà preferibile, ma dopo poco tempo il secondo sarà carico di traffico

mentre il primo sarà scarico, rendendo nuovamente preferibile il primo, e così

via

� in queste circostanze è più opportuno utilizzare metodi di suddivisione del

carico in funzione delle destinazioni, utilizzando opportunamente i costi delle

linee


32

17

Costruzione dello stato dei collegamentiCostruzione dello stato dei collegamenti

� Ora il router dispone dello stato dei suoi collegamenti

� Questi dati vengono messi in una tabella contenente il nome del router in

questione, un numero sequenziale, un numero indicante l’età del pacchetto, e

l’elenco di record “router adiacente”-”ritardo della linea”

� Questi pacchetti possono essere costruiti periodicamente, o in occasione di

modifiche di topologia


33

Distribuzione del link stateDistribuzione del link state

� Il problema di propagare l’informazione agli altri ha due aspetti

⇒ bisognerebbe sapere a priori chi sono gli altri

⇒ via via che il pacchetto raggiunge alcuni router, questi potrebbero

cambiare la loro topologia mentre altri no, quindi si potrebbero verificare

inconsistenze che impediscono la diffusione completa dell’informazione

� L’idea fondamentale, che risolve entrambi i problemi, è di utilizzare il flooding

per propagare le informazioni di link state

� Il carico complessivo sulla rete dovuto al meccanismo di flooding è accettabile

in quanto solo i pacchetti di link state vengono propagati con questa tecnica


34

18


� Vi sono alcuni aspetti da osservare

⇒ il numero di sequenza viene incrementato da un router ogni volta che

genera un nuovo pacchetto di link state

⇒ questo permette ai router che devono instradare l’informazione via

flooding di rimuovere dalla rete i pacchetti relativi ad informazioni

obsolete

⇒ per evitare numeri duplicati si utilizza una numerazione a 32 bit

� Questo meccanismo ha però due problemi

⇒ al riavvio del router, questo ricomincia da zero!

⇒ se per un errore di trasmissione non rilevato giungesse un numero alto al

posto di uno basso, tutti i pacchetti successivi verrebbero scartati


35


� Per ovviare a questi problemi si inserisce anche un numero indicante l’ “età”

del pacchetto, che viene decrementato di una unità al secondo

� Quando l’età raggiunge lo zero, l’informazione viene comunque considerata

obsoleta e scartata

� Tipicamente i pacchetti di link state vengono inviati ogni qualche secondo o

decina di secondi, quindi un valore di età dello stesso ordine di grandezza

garantisce di poter ricevere sempre informazioni aggiornate


36

19

Elaborazione dei percorsiElaborazione dei percorsi

� Quando un router ha ricevuto una serie completa di pacchetti sullo stato dei

collegamenti dei router della rete, riesce a ricostruire la topologia della rete (i router

ed i costi delle linee)

� Viene quindi eseguito l’algoritmo di Dijkstra per valutare i percorsi verso ogni

destinazione in base al cammino più breve

� Il risultato di questi calcoli viene utilizzato per costruire la tabella di routing


37

Caratteristiche del link stateCaratteristiche del link state

� Questo protocollo richiede ai router una discreta capacità di memoria (per

memorizzare i pacchetti del link state, che sono in numero proporzionale al

numero di router e di dimensione proporzionale al numero medio di

collegamenti per router)

� Richiede anche capacità di calcolo per eseguire gli algoritmi di Dijkstra una

volta per ogni destinazione

� Però risponde molto rapidamente a modifiche della topologia:

⇒ appena un router vede una modifica, manda le informazioni aggiornate a

tutti i router immediatamente

⇒ la nuova topologia si stabilizza sulla rete in tempi di alcuni secondi al

massimo, contro i minuti o decine di minuti dell’algoritmo distance vector

� Anche per questo, come per tutti gli algoritmi di routing adattivi, il malfunziona-

mento di un router che annunci informazioni errate può avere effetti disastrosi


38

20

RoutingRouting gerarchicogerarchico

� Al crescere delle dimensioni della rete i protocolli di routing manifestano

difficoltà crescenti a causa di:

⇒ tempi di convergenza, come nel caso di protocolli distance vector

⇒ dimensioni delle tabelle di routing da memorizzare ed elaborare

� La risposta a questo problema è il routing gerarchico

⇒ i router sono divisi in regioni (geograficamente o per altri criteri)

� il routing viene operato a due livelli:

⇒ internamente alla regione i router utilizzano un protocollo che si

preoccupa della topologia esclusivamente all’interno della regione

⇒ alcuni router per ciascuna regione operano il routing inter-regionale e

conoscono il modo per raggiungere le altre regioni, senza conoscerne la

topologia interna


39

RoutingRouting gerarchico (gerarchico (contcont.).)

� può occasionalmente generare cammini non ottimali, ma il vantaggio in

termini di riduzione delle tabelle di routing vale la spesa


40

16: Network layer: introduzioneintroduzione, algoritmi...

Documents

Transcript of 16: Network layer: introduzioneintroduzione, algoritmi...