Routing Protocolli PDF

Instradamento nelle reti a pacchetto e in Internet Franco CALLEGATI Walter CERRONI 1 Funzioni di IP Indirizzamento Frammentazione Instradamento - Decidere che percorso un datagramma deve seguire per raggiungere la destinazione dalla sor...

Instradamento nelle reti a pacchetto e in Internet Franco CALLEGATI Walter CERRONI 1 Funzioni di IP Indirizzamento Frammentazione Instradamento - Decidere che percorso un datagramma deve seguire per raggiungere la destinazione dalla sorgente - Utilizza le PCI dei datagrammi, in particolari l’indirizzo destinazione - Determina il comportamento della funzione di commutazione nei nodi Il problema dell’instradamento è più generale rispetto allo specifico protocollo di livello 3 2 Algoritmi e protocolli Instradamento = scelta del percorso La scelta del percorso spesso significa semplicemente scegliere il prossimo router a cui inviare un pacchetto (scelta del next hop) Algoritmo di instradamento - Metodologia di scelta del next hop - Ha obiettivi di ottimalità ・Semplicità = bassa complessità computazionale ・Robustezza = capacità di adeguarsi a cambiamenti ・Stabilità = consistenza di risultato ・Efficienza = buon uso delle risorse disponibili senza sprechi 3 Tabella? I nodi di commutazione per applicare l’algoritmo possono utilizzare informazioni predisposte localente tipicamente sotto forma di tabelle Algoritmi senza tabella - Non fanno uso di tabelle di instradamento Algoritmi con tabella - Fanno uso di tabelle di instradamento 4 Algoritmi di instradamento Senza tabella - Flooding - Random - Deflection routing (hot potato) - Source routing Con tabella - Instradamento fisso e centralizzato - Instradamento dinamico a distanza minima 5 Flooding Flooding - ogni nodo ritrasmette su tutte le porte di uscita ogni pacchetto ricevuto - Prima o poi ・un pacchetto viene sicuramente ricevuto da tutti i nodi della rete e quindi anche da quello a cui è effettivamente destinato - Tutte le strade possibili sono percorse ・il primo pacchetto che arriva a destinazione ha fatto la strada più breve possibile - L’elaborazione associata è pressoché nulla Molto adatto quando si desidera inviare una certa informazione a tutti i nodi della rete (broadcasting) 6 Problema Proliferazione dei pacchetti Nel singolo nodo ogni pacchetto viene copiato tante volte quante sono le interfacce Se ritrasmesso sull’interfaccia da cui è arrivato il numero di copie cresce esponenzialmente ? ? Soluzioni Un nodo non ritrasmette il pacchetto nella direzione dalla quale è giunto Identificazione dei pacchetti - Ad ogni pacchetto viene associato un identificativo unico (l’indirizzo della sorgente e un numero di sequenza - Il nodo crea una lista dei pacchetti ricevuti e ritrasmessi - Ogni pacchetto già trasmesso, viene ignorato Contatore del tempo di vita (TTL) di un pacchetto per evitare che giri all’infinito ? Dinamicità Tutte le metodologie di instradamento dovrebbero adattarsi agli eventuali cambiamenti topologici della rete Lo possono fare più o meno velocemente per cui si parla di instradamento Statico (o fisso) - I percorsi sono decisi in momenti specifici (inizializzazione della rete) e non cambiano sul breve periodo - Se c’è un cambiamento repentino della topologia questo viene recepito solamente alla prossima inizializzazione Dinamico - I percorsi vengono modificati periodicamente per adattarsi velocemente ad eventuali cambiamenti della rete 9 Random Il next hop viene scelto a caso fra quelli possibili Le probabilità possono essere diverse e modificabili nel tempo Problemi - Non garantisce la consegna in tempi certi - Potrebbe dar luogo a comportamenti instabili (loop) 10 Deflection routing (hot potato) Quando un nodo riceve un pacchetto lo ritrasmette sulla linea d’uscita avente il minor numero di pacchetti in attesa di essere trasmessi E’ adatto a reti in cui - i nodi di commutazione dispongono di spazio di memorizzazione molto limitato - si desidera minimizzare il tempo di permanenza dei pacchetti nei nodi Problemi - I pacchetti possono essere ricevuti fuori sequenza - Alcuni pacchetti potrebbero percorrere all’infinito un certo ciclo in seno alla rete, semplicemente perché le sue linee sono poco utilizzate Si deve prevedere un meccanismo per limitare il tempo di vita dei pacchetti Non tiene conto della destinazione finale del pacchetto 11  Instradamento con tabella Funzione di instradamento Linee di Linee di ingresso uscita Tabella di instradamento 12  Store-and-Forward Il pacchetto entrante è verificato e memorizzato Si estraggono le informazioni di instradamento dall’intestazione (indirizzo, priorità, classe di servizio) Si confrontano queste informazioni con la tabella di instradamento - Identificando una o più uscite su cui inviare il pacchetto Il pacchetto è inserito nella coda relativa all’uscita prescelta, in attesa della effettiva trasmissione Il pacchetto viene prima memorizzato interamente nel nodo e quindi ritrasmesso nella direzione opportuna In generale dovrebbe esistere una base dati per il confronto che è la tabella di instradamento 13 Shortest path routing Si assume che ad ogni collegamento della rete possa essere attribuita una lunghezza Lunghezza - è un numero che serve a caratterizzare il peso di quel collegamento nel determinare la funzione di costo del percorso totale di trasmissione L’algoritmo cerca la strada di lunghezza minima fra ogni mittente e ogni destinatario Si applicano algoritmi di calcolo dello shortest path (Bellman-Ford e Dijkstra) L’implementazione può avvenire in modalità - Centralizzata ・ Un solo nodo esegue i calcoli per tutti - Distribuita ・ Ogni nodo esegue i calcoli per se ・ Sincrona Tutti i nodi eseguono gli stessi passi dell’algoritmo nello stesso istante ・ Asincrona I nodi eseguono lo stesso passo dell’algoritmo in momenti diversi 14 Rappresentazione della rete Ad una generica rete si può facilmente associare un grafo orientato: - i nodi rappresentano i terminali ed i commutatori - gli archi rappresentano i collegamenti - L’orientazione degli archi rappresenta la direzione di trasmissione - il peso degli archi rappresenta il costo dei collegamenti, che può essere espresso in termini di ・numero di nodi attraversati (ogni arco ha peso unitario) ・distanza geografica ・ritardo introdotto dal collegamento ・inverso della capacità del collegamento ・costo di un certo instradamento ・una combinazione dei precedenti 15  Il grafo della rete Una rete è un insieme di nodi di commutazione interconnessi da collegamenti Per rappresentarla si possono usare i modelli matematici della teoria dei grafi - Sia V un insieme finito di nodi - Un arco è definito come una coppia di nodi (i,j), i,j ∈ V - Sia E un insieme di archi - Un grafo G è definito come la coppia (V,E) e può essere ・orientato se E consiste di coppie ordinate, cioè se (i,j)≠(j,i) ・non orientato se E consiste di coppie non ordinate, cioè se (i,j)=(j,i) - Se (i,j) ∈ E, il nodo j è vicino del nodo i 16 Rappresentazione di grafi 1 2 1 2 7 7 3 3 6 4 6 4 5 5 Grafo orientato Grafo non orientato V = {1,2,3,4,5,6,7} V = {1,2,3,4,5,6,7} E = {(1,2),(1,3),(1,7), E = {(1,2),(1,3),(1,7), (2,3),(3,6),(4,3), (2,3),(3,4),(3,6), (4,5),(4,6),(6,4), (4,5),(4,6),(6,7)} (7,1),(7,6)} Dimensioni: |V|=7, |E|=9 Dimensioni: |V|=7, |E|=11 17  Grafo pesato Un grafo pesato è un grafo G=(V,E) tale che ad ogni arco (i,j) ∈ E è associato un numero reale w(i,j) chiamato peso (o costo, o distanza) - In un grafo non orientato vale sempre w(i,j) = w(j,i) - In un grafo orientato vale in generale w(i,j) ≠ w(j,i) - Se (i,j) ∉ E, allora w(i,j) = ∞ - Per semplicità si assume w(i,j) > 0 per ogni arco (i,j) ∈ E 1 1 2 1 2 2 1 2 6 6 3 3 7 4 7 3 3 3 2 3 2 3 3 1 1 w(1,7) = 4 6 4 6 4 w(7,1) = 2 5 5 w(1,2) = 1 4 w(1,7) = w(7,1) = 2 w(2,1)18= ∞ 5 w(1,6) = ∞ 5 Routing shortest path nel mondo IP Quando i nodi di rete vengono accesi conoscono solamente la configurazione delle loro interfacce - Statica - Dinamica con DHCP Con queste informazioni popolano la tabella di instradamento iniziale Per implementare il routing shortest path verso una qualunque destinazione devono utilizzare - Uno o più protocolli di routing per scambiarsi informazioni ed apprendere la topologia della rete - Uno o più algoritmi per il calcolo degli SP sulla base delle informazioni ottenute 19 Routing Distance Vector Basato su Bellman-Ford, in versione dinamica e distribuita proposta da Ford-Fulkerson Implementa meccanismi di dialogo per fare si che - Ogni nodo scopre i suoi vicini e ne calcola la distanza da se stesso - Ad ogni passo, ogni nodo invia ai propri vicini un vettore contenente la stima della sua distanza da tutti gli altri nodi della rete (quelli di cui è a conoscenza) E’ un protocollo semplice e richiede poche risorse Problemi: - convergenza lenta, partenza lenta (cold start) - problemi di stabilità: conteggio all’infinito 20  Esempio 6 Distance Vector iniziali: DV(i)= {(i,0)}, per i = A,B,C,D,E 7 C A 2 Distance Vector dopo la scoperta dei vicini: E 3 1 DV(A) = {(A,0), (B,1), (C,6)} 2 DV(B) = {(A,1), (B,0), (C,2), (D,1)} D B DV(C) = {(A,6), (B,2), (C,0), (D,3), (E,7)} 1 DV(D) = {(B,1), (C,3), (D,0), (E,2)} DV(E) = {(C,7), (D,2), (E,0)} Evoluzione delle tabelle di routing 1. A riceve DV(B) 2. A riceve DV(C) 3. B riceve DV(D) 4. A riceve DV(B) dest Costo, next hop dest Costo, next hop dest Costo, next hop dest Costo, next hop A 0 A 0 A 1, A A 0 B 1, B B 1, B B 0 B 1, B C 3, B C 3, B C 2, C C 3, B D 2, B D 2, B D 1, D D 2, B E 10, B E 3, D E 4, B Tabella di A Tabella di A Tabella di B Tabella di A 21  Esempio 3.18 dal libro B C B - Time T B - Time 2T B - Time 3T B - Time 4T 3 D C D C D C D C A 1 A 1 A 1 A 1 1 2 B - B - B - B - C 3 5 C 3 C 3 C 3 A 1 D D 5 D 4 D 5 6 E 4 E 5 E 3 E 3 3 1 F 1 F 1 F 1 F 1 A - Time T A - Time 2T A - Time 3T A - Time 4T A - Time 5T F 2 E D C NH D C NH D C NH D C NH D C NH A - A - A - A - A - B 1 B B 1 B B 1 B B 1 B B 1 B C 4 B C 4 B C 4 B C 4 B D 9 F D 6 F D 5 B D 6 B Evoluzione del distance vector di A E 5 F E 4 B E 4 B E 5 B F 3 F F 2 B F 2 B F 2 B F 2 B A riceve i DV sempre solo da B e F F - Time T F - Time 2T F - Time 3T F - Time 4T (suo diretti vicini) D C D C D C D C A 3 A 2 A 2 A 2 I DV di B ed F sono B 1 B 1 B 1 B 1 C 4 C 4 C 4 progressivamente più completi e D 6 D 3 D 6 D 6 permettono ad A di venire a E 2 E 2 E 3 E 3 conscenza dell’intera rete F - F - F - F 22 - Algoritmo Nodo sorgente del traffico denominato s Dhi costo del percorso di lunghezza minima da s a j in al più h salti dij costo del collegamento diretto fra i e j dij = ∞ se i e j non sono connessi direttamente Per h=1 Djh = dsj 8j 6= s Per h = h+1 Dh = min Dh 1 + h 1 dij , Dj j i i 23  Cold start e tempo di convergenza Allo start-up le tabelle dei singoli nodi contengono solo l’indicazione delle distanze dagli immediati vicini Da qui in poi lo scambio dei distance vector permette la creazione di tabelle sempre più complete L’algoritmo converge al più dopo un numero di passi pari al numero di nodi della rete Se la rete è molto grande il tempo di convergenza può essere lungo. Cosa succede se lo stato della rete cambia in un tempo inferiore a quello di convergenza dell’algoritmo? - Risultato imprevedibile à si ritarda la convergenza 24  Bouncing effect Il link fra due nodi A e B cade - A e B si accorgono che il collegamento non funziona e immediatamente pongono ad infinito la sua lunghezza - Se altri nodi hanno nel frattempo inviato anche i loro vettori delle distanze, si possono creare delle incongruenze temporanee, di durata dipendente dalla complessità della rete ・ad esempio A crede di poter raggiungere B tramite un altro nodo C che a sua volta passa attraverso A - Queste incongruenze possono dare luogo a cicli, per cui due o più nodi si scambiano datagrammi fino a che non si esaurisce il TTL o finché non si converge nuovamente A 2,A C 6 B B ∞,B B 3,A 2 1 DV(C) = {(A,2), (B,3)} B 6,B B 1,B B 5,C DV(A) = {(B,5), (C,2)} A C 2,C 25 Convergenza lenta A 2,A C 20 B B 3,A 2 1 40 B 7,A B 1,B A C 2,C B 40,B B 11,A B 5,C B 15, A B 9,C B 19,A B 13,C B 20, B 22,C B B 17,C B 21,C 26  Count to infinity A B C Situazione iniziale: DAB = 1, DBC = 1 e DAC = 2 - Link BC va fuori servizio - B riceve il DV di A che contiene l’informazione DAC = 2, per cui esso computa una nuova D'BC = DBA + DAC = 3 - B comunica ad A la sua nuova distanza da C - A calcola la nuova distanza DAC = DAB + D'BC = 4 - … La cosa può andare avanti all’infinito - Si può interrompere imponendo che quando una distanza assume un valore DIJ > Dmax allora si suppone che il nodo destinazione J non sia più raggiungibile Inoltre si possono introdurre meccanismi migliorativi - Split horizon - Triggered update 27  Split horizon Split horizon è una tecnica molto semplice per risolvere in parte i problemi suddetti - se A instrada i pacchetti verso una destinazione X tramite B, non ha senso per B cercare di raggiungere X tramite A - di conseguenza non ha senso che A renda nota a B la sua distanza da X Un algoritmo modificato di questo tipo richiede che un router invii informazioni diverse ai diversi vicini Split horizon in forma semplice: - A omette la sua distanza da X nel DV che invia a B Split horizon with poisonous reverse: - A inserisce tutte le destinazioni nel DV diretto a B, ma pone la distanza da X uguale ad infinito 28  Triggered update Una ulteriore modifica per migliorare i tempi di convergenza è relativa alla tempistica con cui inviare i DV ai vicini - i protocolli basati su questi algoritmi richiedono di inviare periodicamente le informazioni delle distanze ai vicini - è possibile che un DV legato ad un cambiamento della topologia parta in ritardo e venga sopravanzato da informazioni vecchie inviate da altri nodi Triggered update: un nodo deve inviare immediatamente le informazioni a tutti i vicini qualora si verifichi una modifica della propria tabella di instradamento 29  Ma non basta… I diversi rimedi proposti in realtà non sono davvero risolutivi - sono ancora presenti situazioni patologiche in cui i protocolli Distance Vector convergono troppo lentamente o non convergono affatto Inizialmente, A e B raggiungono D tramite C A B Dopo il guasto, C mette a ∞ la sua dist. da D Dopo aver ricevuto il DV da C, A crede di poter raggiungere comunque D tramite B C Idem per B che crede di poter usare A Stavolta A e B trasmettono i propri DV a C Si crea di nuovo un loop e un problema di D convergenza 30 Il routing link state Utilizzando il protocollo di routing ogni nodo si costruisce un’immagine del grafo della rete Il protocollo di routing ha come scopo fondamentale quello di permettere ad ogni nodo di crearsi l’immagine della rete - scoperta dei nodi vicini - raccolta di informazioni dai vicini - diffusione delle informazioni raccolte a tutti gli altri nodi della rete Noto il grafo della rete ogni nodo calcola le tabelle di routing utilizzando un opportuno algoritmo di routing 31 Raccolta delle informazioni Ogni router deve comunicare con i propri vicini ed “imparare” i loro indirizzi - Hello Packet Deve poi misurare la distanza dai vicini - Echo Packet In seguito ogni router costruisce un pacchetto con lo stato delle linee (Link State Packet o LSP) che contiene - la lista dei suoi vicini - le lunghezze dei collegamenti per raggiungerli 32 Diffusione ed elaborazione delle informazioni I pacchetti LSP devono essere trasmessi da tutti i router a tutti gli altri router della rete - si usa il Flooding - a tal fine nel pacchetto LSP occorre aggiungere ・l’indirizzo del mittente ・un numero di sequenza ・una indicazione dell’età del pacchetto Avendo ricevuto LSP da tutti i router, ogni router è in grado di costruirsi un’immagine della rete - tipicamente si usa l’algoritmo di Dijkstra per calcolare i cammini minimi verso ogni altro router 33  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b Passo 2: il nodo a minima distanza da a avente b A B C D E F G H come predecessore è e Passo 3: il nodo a minima distanza da a avente e come predecessore è c …… È dimostrato che, procedendo in questo modo, le distanze determinate sono minime e non possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 34  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 A B C D E F G H Passo 1: il nodo a minima distanza da a è b A 2 A 6 A 3 Passo 2: il nodo a minima distanza da a avente b A2 come predecessore è e Passo 3: il nodo a minima distanza da a avente e come predecessore è c …… È dimostrato che, procedendo in questo modo, le distanze determinate sono minime e non possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 35  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b A B C D E F G H Passo 2: il nodo a minima distanza da a avente b A 2 A 6 A 3 come predecessore è e A2 B 4 B 3 Passo 3: il nodo a minima distanza da a avente e A2 B3 come predecessore è c …… È dimostrato che, procedendo in questo modo, le distanze determinate sono minime e non possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 36  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b A B C D E F G H Passo 2: il nodo a minima distanza da a avente b A 2 A 6 A 3 come predecessore è e A2 Passo 3: il nodo a minima distanza da a avente e B 4 B 3 come predecessore è c A2 B3 …… E6 E5 E6 E7 È dimostrato che, procedendo in questo modo, A2 B4 B3 le distanze determinate sono minime e non possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 37  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b Passo 2: il nodo a minima distanza da a avente b A B C D E F G H A 2 A 6 A 3 come predecessore è e A2 Passo 3: il nodo a minima distanza da a avente e B 4 B 3 come predecessore è c A2 B3 …… E6 E5 E6 E7 È dimostrato che, procedendo in questo modo, A2 B4 B3 le distanze determinate sono minime e non C 5 A2 B4 E5 B3 possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 38  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b Passo 2: il nodo a minima distanza da a avente b A B C D E F G H A 2 A 6 A 3 come predecessore è e A2 Passo 3: il nodo a minima distanza da a avente e B 4 B 3 come predecessore è c A2 B3 …… E6 E5 E6 E7 È dimostrato che, procedendo in questo modo, A2 B4 B3 le distanze determinate sono minime e non C 5 A2 B4 E5 B3 possono essere migliorate nei passi successivi dell’algoritmo A2 B4 E5 B3 C5 Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 39  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b A B C D E F G H Passo 2: il nodo a minima distanza da a avente b A 2 A 6 A 3 come predecessore è e A2 Passo 3: il nodo a minima distanza da a avente e B 4 B 3 come predecessore è c A2 B3 E6 E5 E6 E7 …… A2 B4 B3 È dimostrato che, procedendo in questo modo, C 5 le distanze determinate sono minime e non A2 B4 E5 B3 possono essere migliorate nei passi successivi dell’algoritmo A2 B4 E5 B3 C5 Nella riga gialla viene riassunta la soluzione H 7 dell’algoritmo. Essa riporta la distanza minima A2 B4 E5 B3 E6 C5 verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 40  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b Passo 2: il nodo a minima distanza da a avente b A B C D E F G H A 2 A 6 A 3 come predecessore è e A2 Passo 3: il nodo a minima distanza da a avente e B 4 B 3 come predecessore è c A2 B3 …… E6 E5 E6 E7 È dimostrato che, procedendo in questo modo, A2 B4 B3 le distanze determinate sono minime e non C 5 A2 B4 E5 B3 possono essere migliorate nei passi successivi dell’algoritmo A2 B4 E5 B3 C5 Nella riga gialla viene riassunta la soluzione H 7 dell’algoritmo. Essa riporta la distanza minima A2 B4 E5 B3 E6 C5 verso X ed il nodo “predecessore” di X sul F 9 relativo percorso A2 B4 E5 B3 E6 H7 C5 Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo a cui A deve inviare i dati per raggiungere X) 41  Esempio 2 2 Determinare il percorso di lunghezza minima dal nodo a a b c verso tutti gli altri. 3 1 6 3 Nelle righe grigio chiare della tabella indichiamo le distanze determinate a quel passo dell’algoritmo d e 2 1 Nelle righe grigio scure indichiamo la distanza che viene 4 ritenuta la migliore determinando il nodo a cui fare 3 riferimento per i calcoli al prossimo passo dell’algoritmo f g h 2 2 Passo 1: il nodo a minima distanza da a è b Passo 2: il nodo a minima distanza da a avente b come predecessore è e Passo 3: il nodo a minima distanza da a avente e come predecessore è c …… È dimostrato che, procedendo in questo modo, le distanze determinate sono minime e non possono essere migliorate nei passi successivi dell’algoritmo Nella riga gialla viene riassunta la soluzione dell’algoritmo. Essa riporta la distanza minima verso X ed il nodo “predecessore” di X sul relativo percorso Nella riga arancio viene indicata la distanza da A al nodo X e il gateway da A verso X (ossia il nodo H precede G nel percorso ottimo da A a G a cui A deve inviare i dati per raggiungere X) B è il primo nodo che A incontra sul percorso ottimo verso G 42 Il router IP Il nodo di commutazione nelle reti IP viene detto router Il router è un nodo di commutazione a pacchetto specializzato per l’utilizzo del protocollo IP Nonostante siano tutti identificati con il termine router i nodi di commutazione della rete Internet possono essere fra loro molto diversi 43  Classificazione dei router SOHO (Small Office and HOme) router - Utilizzo domestico o piccoli uffici - Interfaccia sulla LAN (switch con poche porte Fast Ethernet 100Mbit/s e wi-fi) Router di accesso - used by ISPs to provide access service - large number of medium-low speed ports (50 kbps ÷ 10 Mbps) - capable of several protocols and access technologies (PPP, SLIP, ADSL, FTTx, …) Enterprise/campus router - Interconnessione fra LAN per organizzazioni di medie dimensioni - Poche porte ad elevata velocità (Fast o Gigabit Ethernet) Backbone router - Per reti di trasporto e connessioni inter-domain - Piccolo numero di porte ad elevata velocità (>= 1Gbps) - Equipaggiato con sistemi di garanzia dell’affidabilità (ridondanza, monitoraggio remoto, ecc.) 44 Le 4 funzioni dei Router Routing - Scambio di informazioni con altri router (IGP/EGP) - Elaborazione locale (routing algorithm) - Popolazione delle tabelle di routing Forwarding - IP ・Table lookup ・Header update Switching - Trasferimento del datagramma da interfaccia di input a interfaccia di output Trasmissione - Trasmissione del datagramma sul mezzo fisico (utilizzando l’interfaccia di rete di output) 45 Schema funzionale di un router Higher layer protocols (TCP, UDP, ICMP, OSPF, …) IP dest = errore à ICMP host locale Aggiunta Riassemblaggio intestazione IP IP dest = host remoto Inoltro Processamento intestazione IP Frammentazione Strato 2 46 Tabella di Routing e di forwarding Routing table - result of the routing protocols and algorithms - each entry includes route prefix, next hop and metric - also called Routing Information Base (RIB) Forwarding table - built upon routing table content (complete or partial) - each entry includes also the output interface - used to actually forward datagram - optimized for fast table lookup - also called Forward Information Base (FIB) 47 Routing vs. forwarding table 48 Arrivare alla FIB La RIB è una base dati che viene compilata con - il concorso di numerosi protocolli - diverse strategie di sintesi delle informazioni note La FIB si ottiene a partire dalle informazioni della RIB - Vengono utilizzati opportuni algoritmi Nel complesso queste operazioni determinano la strategia di instradamento utilizzata dai nodi della rete 49  Instradamento nell’Internet globale Franco CALLEGATI Dipartimento di Informatica - Scienza e Ingegneria Routing gerarchico In Internet si usa il routing gerarchico e le aree di routing sono chiamate Autonomous System (AS) - un AS può essere ulteriormente suddiviso in porzioni dette Routing Area (RA) interconnesse da un backbone (dorsale) - ogni network IP è tutta contenuta in un AS o in una RA ・tradizionalmente secondo la classe, oggi secondo il CIDR - gli AS decidono autonomamente i protocolli e le politiche di routing che intendono adottare al loro interno - i vari enti di gestione si devono accordare su quali protocolli utilizzare per il dialogo tra i router che interconnettono AS diversi I protocolli di routing all’interno di un AS sono detti Interior Gateway Protocol (IGP) I protocolli di routing fra AS sono detti Exterior Gateway Protocol (EGP) Authonomous Systems and peering Internet = rete di reti 53 Internet = sistemi interconnessi AS3 AS5 AS1 AS2 AS4 54 Internet: grafo semplificato AS3 AS5 AS1 AS2 AS4 55 Il routing a livello globale Routing gerarchico: - Identificazione di sottoinsiemi di rete autonomi per quanto riguarda l’instradamento - Identificazione di punti di contatto fra i sottoinsiemi Due tipi di grafo - Topologia dei sottoinsiemi della rete ・Grafi di dettaglio - Topologie dei sottoinsiemi interconnessi ・Grafo semplificato I sottoinsiemi sono i nodi I collegamenti fra i sottoinsiemi sono gli archi - A ciascun livello non si ha conoscenza dell’altro Authonomous Systems I sottoinsiemi in cui viene suddivisa logicamente la rete Internet sono detti Authonomous Systems (AS) Cosa è un AS? La definizione classica di AS è - un insieme di router gestiti da un’unica amministrazione - che utilizza ・un solo protocollo di routing ・un’unica logica per definire le metriche Questa definizione era applicabile nella prima fase di sviluppo di Internet ma è diventata troppo limitata con l’evolversi della rete I protocolli di routing Un AS deve implementare il routing al suo interno - Lo fa utilizzando uno o più protocolli di routing detti Interior Gateway protocols (IGP) Un AS deve comunicare con gli altri AS per implementare il routing fra AS - Lo fa utilizzando un protocollo di routing pensato appositamente detto Exterior Gateway Protocol (EGP) Interior Gateway Protocol - RIP: Routing Information Protocol - OSPF: Open Shortest Path First Exterior Gateway Protocol - EGP: Exterior Gateway Protocol - BGP: Border Gateway Protocol RFC 1930 L’evoluzione di Internet e l’introduzione del CIDR richiedono una definizione più estensiva dell’AS Oggi un AS è - Un insieme di prefissi di rete IP (network IP definite secondo la logica CIDR) - Gestito in modo unitario e con una ben definita politica di routing ・Questo significa che chi gestisce l’AS ha definito in modo chiaro al suo interno come raggiungere le network IP Quindi l’AS - Può ・Avere uno o più enti gestori ・Utilizzare una o più tecnologie - Ma deve ・Avere un’unica logica che garantisce la connettività con il resto del mondo Esempio Università di Bologna -> 137.204.0.0/16 Politecnico di Torino -> 130.192.0.0/16 Entrambi - sono connessi al GARR, la rete italiana degli enti di ricerca - comunicano con il resto del mondo tramite il GARR Non c’è bisogno di avere un AS per ogni ateneo e infatti il GARR (e tutte le reti connesse ad esso) costituiscono un unico AS (AS137) Internet Routing Registries Database contenenti le politiche di routing degli AS AS 137 Regole di Import: Da quali AS posso ricevere informazioni di routing (con scambio di path vector BGP ad esempio) Regole di Export: A quali AS comunico informazioni di routing (inviando path vector BGP ad esempio) AS20965 Regole di Import GEANT è la rete degli enti di ricerca Europea Ha interconnessioni con le principali reti mondiali Importa ed esporta informazioni di routing verso numerosi AS 1. Le network IP di GARR sono inviate a GEANT 2. GEANT le invia alle altre reti di trasporto mondiali Interconnessione fra AS AS3 AS5 Rotta inter-dominio (esterna) AS1 Indiretta tramite AS5 Interconnessione diretta (peering) fra AS2 e AS4 Rotta intra-dominio (interna) AS2 AS4 64 Internet Service Provider Un Internet Service Provider (ISP) è un’organizzazione che fornisce servizi per l’utilizzo di Internet Servizi: - Connettività - Web, mail hosting - Registrazione e noleggio di numeri IP e nomi di dominio - … Dal punto di vista giuridico un ISP può essere: - Privato con finalità di lucro - Privato senza finalità di lucro - In forma cooperativa - … Tipicamente un ISP si registra come AS Internet region Gli AS non sono necessariamente vincolate ad aree geografiche e/o confini nazionali Internet region - Una porzione di Internet contenuta in una specifica area geografica ・Tipicamente una nazione o un insieme di nazioni Relazione fra Internet Region e ISP - Un’Internet Region è solitamente servita da più ISP - Uno stesso ISP può servire più Internet Region Classificazione degli ISP Tier 1 ISP - Un ISP che all’interno di una “Internet Region” raggiunge tutte le reti senza accedere a servizi a pagamento di altri - In breve un soggetto che possiede un’infrastruttura di rete che copre tutta una nazione ・Tipicamente il gestore “incumbent” - Gli ISP Tier 1 possono essere ・Nazionali quando servono una sola Internet regione ・Globali quando hanno punti di accesso in paesi e continenti diversi Classificazione degli ISP Tier 2 - Un ISP che raggiunge l’Internet globale acquistando servizi di interconnessione da un Tier 1 ISP - Un ISP Tier 2 può avere interconnessioni anche con più di un ISP Tier 1 nella stesse o in diverse Internet Region Tier 3 - Un ISP che serve un’area abbastanza delimitata ・ISP locali o regionali - Per raggiungere l’Internet globale acquista servizi di interconnessione da un ISP Tier 2 - Può avere interconnessioni dirette (peering) con altri ISP Tier 3 che servono la stessa zona o zone limitrofe In sintesi Tier 1 ISP Tier 2 ISP Tier 2 ISP Local (Tier 3) ISP Local ISP Local ISP Internet Region In Italia Il principale ISP Tier 1 è Telecom Italia Sparkle - Da RadB aut-num: AS6762 as-name: SEABONE-NET descr: TELECOM ITALIA SPARKLE S.p.A. remarks: International Internet Backbone Il Peering Relazione di peering - Interconnessione fra due AS stabilita al fine di scambiarsi traffico ・Con operatore di contenuti (Amazon, Aruba, Netflix) La relazione di peering non ha carattere economico - Gli AS non devono pagarsi reciprocamente per lo scambio di traffico - I loro introiti rimangono limitati alla tariffazione dei rispettivi utenti Tipicamente il peering avviene fra ISP del medesimo livello Peering policy Ristretta - Devi chiedere di fare peering e la richiesta va approvata Aperta - Approvato di default In sintesi Tier 1 ISP Interconnessione a pagamento Tier 2 ISP Tier 2 ISP Local (Tier 3) ISP Local ISP Local ISP Peering Internet Region ISP locali e POP Un ISP locale fornisce il servizio a gruppi di utenti co-localizzati (singola città, area industriale ecc.) Realizza un’infrastruttura con router e switch in un punto della zona detto Point of Presence o POP Come collega gli utenti a quella infrastruttura? - Riutilizzo del vecchio collegamento telefonico in rame (ADSL e simili) - Fibra ottica (FTTH) - Collegamento radio (Wi-Fi e simili) - Soluzioni miste (rame+fibra ad esempio nel FTTC) Esempio ADSL POP ADSL/FTTH Wi-Fi Indirizzamento Un ISP dispone di un sottoinsieme di numeri IP da utilizzare per i suoi clienti - Se sono consecutivi possono avere lo stesso prefisso quindi unico Network ID - Se non sono consecutivi deve gestire più prefissi quindi più Network ID In funzione della dimensione (numero di utenti e distanze geografiche) la rete dell’ISP può essere composta da una o più LAN Interconnessione Come scambiano traffico ISP che coprono la medesima zona geografica Interconnettere fra loro tutti i POP? - Numerosi collegamenti - Complessità di gestione del routing ・Rotte specifiche per ogni POP in funzione dei numeri a loro connessi - Percorsi di lunghezza minima Interconnettere uno o pochi POP? - Minor numero di collegamenti - Routing semplificato - Percorsi potenzialmente più lunghi Non utilizzata Peering diretto tramite due POP Da Tier 3 a Tier 1 Teoricamente ogni ISP dovrebbe fare peering con ogni altro ISP con cui vuole scambiare traffico - Ogni AS dovrebbe essere connesso con ogni altro AS ・Gran numero di collegamenti dedicati fra POP Alcuni ISP svolgono la funzione di AS di transito per interconnettere con una topologia “a stella” gli ISP - Gli ISP specializzati nel fornire servizi di transito sono anche detti Network Service provider (NSP) Talvolta gli NSP coincidono con ISP Tier 1 Internet Exchange Per favorire l’interconnessione fra ISP e NSP (ssia fra i loro AS) esistono gli IXP Internet Exchange Point (IX o IXP) - Infrastrutture attraverso le quali gli ISP possono stabilire relazioni di peering - L’IXP è costruito per permettere l’interconnessione diretta degli AS senza utilizzare reti di terze parti - L’IXP fornisce soluzioni di connettività con specifiche garanzie di qualità (disponibilità elevata, sicurezza fisica, banda garantita ecc.) Un elenco degli IXP nel mondo si può trovare alla pagina www.internetexchangemap.com IXP in Italia MIX (Milan Internet eXchange) - Milano, Palermo, Catania NaMeX (Nautilus Mediterranean eXchange point - Roma TOP-IX (Torino Piemonte Internet Exchange) - Torino Tuscany Internet eXchange - Firenze PCIX - Piacenza Interior Gateway Protocol IGP Routing Information Protocol (RIP) Protocollo distance vector, di implementazione vecchia (RFC 1058, Giugno 1988), discende dal protocollo di routing realizzato per la rete XNS di Xerox Ne esiste una versione 2 più recente (RFC 2453) Molto diffuso in passato perché il codice di implementazione è liberamente disponibile Utilizzato praticamente solo su reti TCP/IP Utilizza due tipi di messaggi: – REQUEST serve per chiedere esplicitamente informazioni ai nodi vicini (ad es. all’avvio del nodo) – RESPONSE serve in generale per inviare informazioni di routing (cioè i distance vector) I messaggi RIP sono trasportati da UDP ed usano la porta 520 sia in trasmissione che in ricezione 84 Response Un RESPONSE con nuove informazioni di routing viene inviato: – periodicamente – come risposta ad una richiesta esplicita – quando una informazione di routing cambia (triggered update) Le informazioni periodiche sono inviate ogni 30 secondi, con uno scarto da 1 a 5 secondi, per evitare “tempeste” di aggiornamenti Response contiene il distance vector del router che lo invia – Destinazione – Distanza (hop count) 85  RIP: formato dei pacchetti La struttura del pacchetto è basata su parole di 32 bit Il pacchetto può avere lunghezza variabile fino a 512 byte (max 25 entry) command version must be zero address family identifier must be zero address ripetuto must be zero must be zero metric address family identifier must be zero address must be zero must be zero metric 86 RIP: significato dei campi I bit del pacchetto sono molto ridondanti rispetto alla quantità di informazioni da inviare (molti campi fissi con i bit tutti a zero) – inizialmente pensati per adattarsi ad altri protocolli command: distingue tra REQUEST (1) e RESPONSE (2) version: versione del RIP address family identifier: indica il tipo di indirizzo di rete utilizzato, vale 2 per IP address: identifica la destinazione per la quale viene data la distanza metrica: è la distanza dalla destinazione indicata 87 RIP: la tabella di routing Ogni riga nella tabella contiene: – indirizzo di destinazione: è un indirizzo IP a 32 bit – distanza dalla destinazione (metrica) in termini di hop-count (ogni link ha peso = 1) la distanza massima (∞) per RIP è pari a 16, al fine di limitare il conteggio all’infinito à adatto per reti relativamente piccole – next-hop sul percorso verso la destinazione router vicino a cui inviare i datagrammi per la destinazione – due contatori Timeout: se una route non viene aggiornata dopo TO secondi, la sua distanza è posta all’infinito (si ipotizza una perdita di connettività) Garbage-collection timer: se dopo ulteriori GC secondi la route viene eliminata del tutto dalla tabella I valori di default sono TO = 180 s e GC = 120 s 88 RIP: aggiornamento della tabella di routing A riceve un RESPONSE da B – Si controlla la correttezza dei dati (indirizzi IP e metriche validi) – Si considerano solo le voci i con distanze di < ∞ – Si calcola di = di + 1 Esiste già una entry per la destinazione i ? – NO Si crea una nuova entry –la distanza è di –il next-hop è B (mittente del RESPONSE) –si fa partire il timeout – SI di è minore di quella presente in tabella –la entry viene aggiornata con next hop = B e distanza = di –si fa ripartire il timeout Next hop = B –Si aggiorna a distanza –Si fa ripartire il timeout 89 RIP: problematiche Fa uso di split horizon – RESPONSE di interfacce diverse possono essere diverse Fa uso di triggered update – non è necessario indicare nella RESPONSE tutte le entry della tabella ma solamente quelle appena modificate Non supporta il CIDR È un protocollo insicuro – Chiunque trasmetta datagrammi dalla porta UDP 520 viene considerato come un router autorizzato – Esempio di malfunzionamento indotto: un router non autorizzato trasmette messaggi contenenti indicazione di una distanza 0 tra se stesso e tutti gli altri della rete dopo qualche tempo tutti i percorsi ottimi convergono su questo router 90 La mancanza di CIDR Si supponga di voler utilizzare la rete 10.0.0.0 suddivisa in sottoreti \24 Si realizzi la seguente architettura di rete 10.1.1.0-------router----200.200.200.0----router---100.100.100.0---router---10.2.2.0 RouterB riceve distance vector contenenti la rete 10.2.2.0 da RouterC e la rete 10.1.1.0 da RouterA In assenza di CIDR 10.1.1.0 e 10.2.2.0 sono indirizzi appartenti alla stessa rete di classe A 10.0.0.0/8 – Per RouterB 10.0.0.0/8 deve essere un'unica destinazione – RouterB è confuso perché vede la stessa rete in due diverse direzioni 91  RIP versione 2 I miglioramenti introdotti riguardano soprattutto: – subnetting e CIDR – autenticazione command version routing domain 11111111 11111111 authentication type authentication data authentication data authentication data authentication data address family identifier route tag address ripetuto subnet mask next hop metric 92 RIP versione 2 Compatibilità verso il basso – RIP-1 ignora le entry con i campi riservati diversi da zero Possibilità di indicare sottoreti o indirizzamento CIDR – tramite il campo subnet mask Possibilità di autenticare chi invia i messaggi Possibilità di indicare il proprio AS e di scambiare informazioni con protocolli EGP – tramite i campi route tag e routing domain Possibilità di specificare un next hop più appropriato Comunque non adatto ad AS grandi Comunque ha problemi di convergenza – è pur sempre un distance vector 93 Una tipica architettura Più router fungono da gateway verso diverse network Condividono una network per lo scambio - Delle informazioni di routing - Del traffico fra le varie network che interconnettono Network C H1 Network D User traffic (data plane) Inter Network B router Network E Routing infos Network A (control plane) H2 94 Il traffico di routing Il traffico di routing condivide le risorse con il traffico d’utente Per questa ragione va minimizzato Network C Network D Inter Network B router Network E Network A Maglia completa N router N(N-1)/2 (circa N2 scambi di informazioni di routing) 95 Multicast Domanda: - Possiamo ridurre il traffico del piano di controllo? Risposta: - SI se la network supporta il punto-multipunto un invio di informazioni di routing può raggiungere molti router in un sol colpo Operativamente - Utilizzo indirizzi IP Multicast 96 IP Multicast Indirizzi multicast da 224.0.0.0 a 239.255.255.255 Come utilizzarli? I router possono utilizzare diversi protocolli in contemporanea 224.0.0.9 RIPv2 224.0.0.5 OSPF All routers 224.0.0.6 OSPF Designated routers 224.0.0.10 EIGRP Routers 224.0.0.24 OSPF TE 97 The Internet Group Management Protocol (IGMP) Serve per dichiarare appartenenza ad un gruppo di multicast Prevede dei messaggi per - Iscriversi ad un gruppo - Abbandonare un gruppo - Valutare l’appartenenza ad un gruppo o meno 98 Open Shortest Path First (OSPF) Divenuto standard nella versione 2 (RFC 2328) Oggi è il più diffuso IGP Protocollo di tipo link state – invio di Link State Advertisement (LSA) a tutti gli altri router Incapsulato direttamente in IP – il valore del campo protocol dell’intestazione IP (89 per OSPF) serve a distinguere questi pacchetti da altri OSPF è stato progettato specificamente per: – semplificare il routing in reti grandi tramite la suddivisione in aree – gestire intrinsecamente reti punto-punto e punto-multipunto – separare logicamente gli host dai router 99 OSPF: aree di routing Un AS può essere suddiviso in porzioni dette Routing Area (RA) interconnesse da un backbone (Area 0) – ciascuna area risulta separata dalle altre per quanto riguarda lo scambio delle informazioni di routing e si comporta come un’entità indipendente (3° livello gerarchico di routing) – per interconnettere le aree vi devono essere router connessi a più aree e/o al backbone (almeno un router per area) Classificazione dei router secondo OSPF: – Internal Router: router interni a ciascuna area – Area Border Router: router che scambiano informazioni con altre aree – Backbone Router: router che si interfacciano con il backbone – AS Boundary Router: router che scambiano informazioni con altri AS usando un protocollo EGP 100 OSPF: aree di routing e tipologie di router AS AS Area Border AS boundary Router Router Area 0 e Backbone Router Backbone Stub Area Backbone Router con route di default Area Border Router RA e Backbone Router Internal Router 101 Tipi di route Route intra-area – aggiornamento delle informazioni di routing pertinenti all'area Route inter-area – Aggiornamento delle informazioni di routing pertinenti ad aree diverse da quella considerata Route esterni – Aggiornamenti delle informazioni di route provenienti da altri protocolli al di fuori del dominio OSPF – Inoltrati nel dominio OSPF dal ASBR Tipi di aree Area normale – Accetta tutti i tipi di route Stub area – Accetta route intra e inter area – Tutti i router della stub area usano un “default route” verso destinazioni al di fuori dell'AS Comunicato dall'Area Border Router (ABR) – I requisiti di memoria dei router sono ridotti Totally stub area – Vengono propagati solamente route intra-area ed il route di default Il default route viene propagato dal ABR Tutti i router dell'area usano il default route per destinazioni esterne all'area Not so stubby area – Stub area che importa alcuni route esterni – Uno dei router dell'area è connesso a un AS diverso e diventa un ASBR OSPF: ulteriori caratteristiche Bilanciamento del carico: se un router ha più percorsi di uguale lunghezza verso una certa destinazione, il carico viene ripartito equamente su di essi Autenticazione: per garantire maggiore sicurezza nello scambio delle informazioni di routing è prevista autenticazione con password ed uso di crittografia Routing dipendente dal grado di servizio: i router scelgono il percorso sul quale instradare un pacchetto sulla base dell’indirizzo e del campo Type of Service dell’intestazione IP, tenendo conto che percorsi diversi possono offrire diversi gradi di servizio 104 OSPF: rappresentazione di host e router H2 N4 N1 N5 N3 137.204.56.137/32 137.204.59.0/24 H2 N3 N1 137.204.57.0/24 N4 N3 137.204.58.0/24 137.204.56.0/25 105 OSPF: tipologie di rete OSPF è progettato per operare correttamente con reti: – Point-to-Point – Broadcast Multi-Access (BMA: LAN 802) – Non-Broadcast Multi-Access (NBMA: X.25, ATM, Frame Relay) In una rete ad accesso multiplo tutti gli N router connessi alla rete sono di fatto connessi con tutti gli altri – il numero di archi bidirezionali da inserire nel grafo è N(N–1)/2+N Sono inclusi gli archi per collegare i router alle network – il numero totale di LSA da trasmettere è N(N–1) – conviene adottare una topologia a stella equivalente, inserendo un nodo virtuale che rappresenta la rete à solo N archi bidirezionali 106 OSPF: rappresentazione di reti multi-accesso LAN rappresentazione secondo OSPF LAN 107 OSPF: vicinanza e adiacenza tra router Vicini: due router che sono connessi alla medesima rete e possono comunicare direttamente – punto-punto o punto-multipunto Adiacenti: due router che si scambiano informazioni di routing In una rete ad accesso multiplo risulta molto più efficiente eleggere un Designated Router (DR) fra gli N vicini – ogni router della LAN è adiacente solo al DR – lo scambio di informazioni di routing avviene solo tra router adiacenti (cioè DR fa da tramite) – inoltre il DR è l’unico a comunicare la raggiungibilità di router e host della LAN al mondo esterno – Per ragioni di affidabilità occorre avere anche un Backup Designated Router (BDR) adiacente a tutti i router locali 108 OSPF: vicinanza e adiacenza tra router router vicini DR router adiacenti 109 OSPF: identificazione di router e priorità Ogni router di un AS utilizzante OSPF deve avere un identificativo univoco (router ID): – di default si prende l’indirizzo IP più alto fra quelli assegnati alle interfacce del router – si può assegnare manualmente un router ID ad ogni router configurando opportunamente l’interfaccia di loop-back – configurare l’interfaccia di loop-back è un modo più stabile e sicuro di assegnare il router ID perché questa interfaccia non viene mai disabilitata Ai singoli router di un’area possono essere associate delle priorità – utilizzate nell’elezione del DR – valore di priorità compreso tra 0 e 255 (8 bit) – di default tutti i router hanno priorità 0 (più bassa) 110 OSPF: elezione di DR e BDR Ciascun router nella rete ad accesso multiplo: – esamina la lista dei suoi vicini – elimina dalla lista tutti i router non eleggibili (ad esempio tutti quelli che hanno priorità nulla) – fra quelli rimasti seleziona il router avente la priorità maggiore il più alto router ID in caso di uguale priorità – elegge il router selezionato a DR – rivede la tabella dei vicini e riseleziona gli eleggibili (a questo punto il router che è stato eletto DR non è più eleggibile) – seleziona ed elegge il BDR secondo le regole già adottate per il DR – termina la procedura una volta eletti DR e BDR 111 OSPF: Link State Database Il grafo orientato della rete sul quale ciascun router calcola lo shortest path tree è rappresentato dal Link State Database presente in ogni router – Nodi: router reti o host singoli nodi virtuali delle topologie a stella equivalenti destinazioni esterne – Archi: collegamenti fisici o virtuali Internet stub network transit 112network OSPF: i protocolli OSPF invia messaggi utilizzando direttamente il protocollo IP (campo protocol = 89) Si compone di tre sottoprotocolli: – hello, exchange, flooding Tutti i messaggi hanno una intestazione comune – vengono aggiunte informazioni per il particolare scopo a cui il messaggio è destinato (tipo di pacchetto) Version Type Packet Length Router ID Area ID Checksum AuType Authentication Authentication … 113 OSPF: intestazione comune Version indica la versione di OSPF (versione 2) Type indica il tipo di pacchetto Packet Length numero di byte del pacchetto Router ID indirizzo IP che identifica il router mittente Area ID identifica l’area di appartenenza – il numero 0.0.0.0 è l’area di backbone Checksum calcolata su tutto il pacchetto OSPF escludendo gli 8 byte del campo authentication – si utilizza l’algoritmo classico di IP AuType indica il tipo di autenticazione: – 0 nessuna autenticazione – 1 autenticazione semplice (password nel campo authentication) – 2 autenticazione crittografica (dati nel campo authentication) 114 Type Type 1 – Hello (Hello protocol, neighbour discovery) Type 2 – Database description (exchange protocol) Type 3 – Link state request Type 4 – Link state update Type 5 – Link state acknowledge OSPF: Hello protocol Unico tipo di pacchetto: Hello (Type = 1) Utilizzato per: – controllare l’operatività dei link – scoprire e mantenere relazioni fra vicini – eleggere DR e BDR OSPF Header (24 byte) Network Mask HelloInterval Options Router Priority RouterDeadInterval Designated Router Backup Designated Router Neighbor Neighbor … 116 OSPF: Hello protocol I pacchetti HELLO sono inviati sulle interfacce periodicamente secondo quanto specificato dal parametro HelloInterval – si riescono così a scoprire i propri vicini Includono una lista di tutti i vicini (Neighbor) dai quali è stato ricevuto un pacchetto HELLO recente (cioè non più vecchio di RouterDeadInterval) – si riesce così a conoscere se per ciascun vicino è presente un collegamento bidirezionale e se esso è ancora attivo I campi Router Priority, Designated Router e Backup Designated Router sono utilizzati per l’elezione di DR e BDR Network Mask indica la maschera relativa all’interfaccia del router (l’indirizzo è nell’header IP) Options indica se si supportano funzionalità opzionali 117 OSPF: Exchange protocol Una volta stabilite le adiacenze, router adiacenti devono sincronizzare i rispettivi Link State Database La procedura di sincronizzazione è asimmetrica – si stabilisce chi è il master e chi lo slave – il master invia una serie di pacchetti Database Description (Type = 2) contenenti l’elenco dei LSA del proprio database nell’elenco sono indicati il tipo di LSA, l’età, il router che lo ha generato e il numero di sequenza non ci sono i dati relativi al LSA – lo slave risponde con l’elenco dei LSA del suo database – durante lo scambio ciascuno dei due router confronta le informazioni ottenute con quelle in proprio possesso – se nel proprio database ci sono dei LSA meno recenti rispetto all’altro, questi (e solo questi) vengono richiesti con un successivo pacchetto Link State Request (Type = 3) 118 OSPF: Flooding protocol La diffusione dei LSA a tutti i router della rete avviene tramite l’invio di pacchetti Link State Update (Type = 4) – a fronte di un cambiamento nello stato di un collegamento – a fronte di una Link State Request – periodicamente (ogni 30 minuti) Si esegue in modalità flooding per fare in modo che tutti i router vedano gli aggiornamenti – flooding efficiente: si usano i numeri di sequenza dei LSA Si continua ad inviare lo stesso update finché non viene confermata la sua ricezione dai nodi adiacenti tramite il pacchetto Link State Acknowledgment (Type = 5) – in questo modo si rende il flooding affidabile 119 OSPF: sincronizzazione e aggiornamento Hello Fase di Hello Hello I router scoprono l’esistenza reciproca Database Description (Master) Database Description Database Description Fase di Exchange Si sceglie il master e lo slave Si confrontano i database Database Description Database Description Link State Request Fase di Update Link State Update Si inviano richieste di aggiornamento ai router adiacenti per aggiornare il database Link State Ack 120 Stub Area Stub Area = tipicamente un’area con uno solo punto di interconnessione con il resto della rete Instradamento verso l’esterno della stub area – Viene effettuato con la tecnica del “default route” – I percorsi verso network esterne alla stub area non vengono propagate da OSPF internamente alle stub areas. Vantaggi – Dimensioni molto ridotte della tabella di routing – Il router di bordo necessita di poca memoria Default route – Esiste un solo punto di uscita verso tutte le destinazioni possibile 121 Exterior Gateway Protocols EGP Exterior Gateway Protocols I protocolli di tipo EGP sono diversi da quelli di tipo IGP All’interno di un AS si persegue l’ottimizzazione dei percorsi Nel routing tra diversi AS si deve tener conto anche (e soprattutto) delle politiche di instradamento - ogni AS vuole mantenere una propria autonomia ed indipendenza dagli altri e non vuole subire decisioni prese da altri - alcuni AS non vogliono permettere ad altri AS di instradare il traffico attraverso le loro reti - in altri casi bisogna operare secondo accordi internazionali Per Internet sono stati definiti due protocolli di tipo EGP: - Exterior Gateway Protocol (EGP) - Border Gateway Protocol (BGP) 123 EGP: Exterior Gateway Protocol Primo protocollo tra AS - risale ai primi anni ottanta (RFC 827) Caratterizzato da tre funzionalità principali: - neighbor acquisition ・verificare se esiste un accordo per diventare vicini - neighbor reachability ・monitorare le connessioni con i vicini - network reachability ・scambiare informazioni sulle reti raggiungibili da ciascun vicino EGP è simile ad un protocollo distance vector - le informazioni inviate ai vicini sono sostanzialmente informazioni di raggiungibilità - non sono specificate le regole per definire le distanze - la distanza minima può non essere il criterio migliore da seguire 124  EGP: limiti EGP fu progettato per una topologia assai specifica, - una dorsale di Internet, la rete ARPAnet - vari domini connessi alla dorsale attraverso un unico router Funziona bene per una topologia ad albero, ma non per reti a maglia complessa (presenza di cicli) - la convergenza del protocollo può essere molto lenta - si possono facilmente creare instabilità Non si adatta velocemente alle modifiche della topologia EGP non implementa alcun meccanismo di sicurezza - qualunque malintenzionato può annunciare quello che vuole ed essere creduto dai router - un router guasto può danneggiare il routing di tutta la rete 125  BGP: Border Gateway Protocol BGP è stato concepito come sostituto di EGP Oggi è in uso la versione 4 (RFC 1771) I router BGP si scambiano informazioni attraverso connessioni TCP (porta 179) chiamate sessioni BGP - le comunicazioni sono affidabili - funzionalità di controllo degli errori demandate allo strato di trasporto à BGP più semplice Si distinguono due tipi di sessioni BGP: - sessioni BGP esterne (eBGP) instaurate tra router BGP appartenenti ad AS diversi - sessioni BGP interne (iBGP) instaurate tra router BGP appartenenti allo stesso AS Le informazioni scambiate riguardano la raggiungibilità di reti IP secondo lo scema classless (CIDR) 126 BGP: interconnessione tra AS AS3 AS5 AS1 BGP AS2 AS4 127 BGP: sessioni interne ed esterne AS3 AS5 AS1 eBGP iBGP AS2 AS4 128  BGP: Path Vector BGP è un protocollo di tipo Path Vector - evoluzione del Distance Vector - nel vettore dei percorsi si elencano tutti gli AS da attraversare per raggiungere una destinazione - risolve il problema dei percorsi ciclici - più consono a definire le politiche di routing tra AS rispetto alla semplice distanza Come si evitano i cicli: - quando un router di bordo di un AS riceve un path vector controlla se il suo AS è già elencato al suo interno - se lo è significa che esiste la possibilità di un loop e quel path vector non viene considerato - altrimenti il path vector viene aggiornato con l’indicazione dell’AS di appartenenza e comunicato ai vicini, in quanto considerato corretto 129  BGP: Path Vector Come si applicano le politiche di routing: - si comunicano ai vicini solo i path vector relativi alle destinazioni verso le quali si vuole permettere il transito (export policies) - dal path vector è possibile risalire agli AS da attraversare per raggiungere una destinazione: se nel path vector ricevuto da un vicino sono presenti uno o più AS incompatibili con le politiche di routing stabilite, esso viene ignorato (import policies) L’approccio basato sul percorso invece che sulla distanza non richiede che tutti i router usino la stessa metrica à possibilità di scelte arbitrarie Maggior consumo di banda per le informazioni di routing Maggiori requisiti di memoria nei router per mantenere le tabelle 130 BGP: scambio di path vector AS-PATH AS-PATH 151.16.0.0/14 151.16.0.0/14 AS5 AS3 151.16.0.0/16 AS3 151.17.0.0/16 151.18.0.0/15 AS3 AS-PATH AS5 151.16.0.0/14 AS-PATH AS1 151.16.0.0/14 AS1 AS5 AS5 AS3 AS3 AS4 AS2 80.128.0.0/12 AS-PATH 211.47.64.0/21 211.47.64.0/21 AS4 AS-PATH AS-PATH 151.16.0.0/14 80.128.0.0/12 AS2 AS2 AS5 131 AS3  000100 00 -> 16 000100 01 -> 17 000100 1 0 -> 18 000100 1 1 -> 19 151.000100 00 151.16.0.0/14 132  BGP: attributi A ciascun path vector sono associati degli attributi che ne specificano la natura (ad es. il “path” è un attributo) Un determinato attributo può essere: - well-known: riconoscibile da tutte le implementazioni BGP, deve essere inoltrato assieme al path vector (dopo un eventuale aggiornamento) ・mandatory: deve essere presente nel path vector ・discretionary: può anche non essere indicato - optional: può non essere riconosciuto da alcuni router ・transitive: deve essere inoltrato anche se non riconosciuto ・non-transitive: deve essere ignorato se non riconosciuto - partial: si tratta di un attributo optional-transitive che è stato ritrasmesso senza modifiche da un router perché non lo ha riconosciuto (indica se un determinato path vector è stato riconosciuto o meno da tutti i router attraversati) 133 BGP: codifica degli attributi All’interno di un path vector, gli attributi sono codificati da una struttura di lunghezza variabile 2 byte O T P E 0 0 0 0 Attribute Type Code Attribute Length Attr. Length/Value Attribute Value O = 1 à optional O = 0 à well-known T = 1 à transitive T = 0 à non-transitive P = 1 à partial E = 1 à attribute length = 2 byte E = 0 à attribute length = 1 byte 134  BGP: alcuni attributi Origin (Code = 1): è well-known mandatory e può valere: - 0 = IGP: l’informazione è stata ottenuta direttamente dal protocollo di routing operante all’interno dell’AS in cui si trova la destinazione e per cui la si ritiene veritiera - 1 = EGP: l’informazione è stata appresa dal protocollo EGP, che non funziona se vi sono cicli à un percorso caratterizzato da questo valore è peggiore di uno di tipo IGP - 2 = incomplete: serve ad indicare che il percorso è stato determinato in altro modo (es. statico) oppure è utilizzato per marcare un percorso di AS che è stato troncato perché la destinazione è al momento non raggiungibile AS path (Code = 2): è well-known mandatory - consiste nell’elenco degli AS da attraversare lungo il percorso verso la destinazione Next hop (Code = 3): è well-known mandatory - indica l’indirizzo IP del router di bordo dell’AS che deve essere usato come next hop verso la destinazione specificata 135  BGP: formato dei messaggi # byte HEADER COMUNE 16 Marker 2 Length 1 Type Tutti i messaggi hanno la seguente parte comune: Marker: campo per possibile schema di autenticazione Length: numero di byte del messaggio BGP, header incluso Type: assume uno dei seguenti valori: - Open - Notification - Update - Keepalive 136 BGP: tipi di messaggio Open: primo messaggio trasmesso quando viene attivata una connessione verso un router BGP vicino, contiene - informazioni di identificazione dell’AS di chi trasmette - durata del timeout per considerare un vicino non più attivo - dati di autenticazione Update: contiene il path vector e i relativi attributi Notification: messaggio di notifica di errori e/o di chiusura della connessione Keepalive: non contiene informazioni aggiuntive, ma è usato per comunicare ad un router BGP vicino, in assenza di nuove informazioni di routing, che il trasmettitore è comunque attivo, anche se silente 137