Algoritmo di Dijkstra - Domande e Risposte

Instradamento nelle reti a pacchetto e in Internet

•  Il tema riguarda l'instradamento di pacchetti nelle reti a pacchetto e in Internet.
•  Le funzioni di IP includono indirizzamento, frammentazione e instradamento.
•  L'instradamento decide il percorso che un datagramma deve seguire per raggiungere la destinazione.
•  Utilizza le informazioni contenute nei datagrammi, in particolare l'indirizzo di destinazione.
•  Determina il comportamento di commutazione nei nodi.
•  Il problema dell'instradamento è più generale del protocollo di livello 3.

Algoritmi e protocolli

•  L'instradamento implica la scelta di un percorso.
•  Spesso implica la scelta del router successivo a cui inviare il pacchetto ("next hop").
•  Gli algoritmi di instradamento hanno obiettivi di ottimalità e includono la semplicità, robustezza, stabilità ed efficienza.

Tabella?

•  I nodi di commutazione possono usare tabelle per l'applicazione di algoritmi e informazioni predisposte localmente.
•  Gli algoritmi senza tabella non usano tabelle di instradamento.
•  Gli algoritmi con tabella invece utilizzano tabelle di instradamento.

Algoritmi di instradamento

•  Gli algoritmi di instradamento senza tabella includono Flooding, Random, Deflection routing (hot potato), Source routing.
•  Gli algoritmi di instradamento con tabella includono instradamento fisso e centralizzato, instradamento dinamico a distanza minima.

Flooding

•  Ogni nodo ritrasmette ogni pacchetto ricevuto su tutte le porte di uscita.
•  Il pacchetto viene sicuramente ricevuto da tutti i nodi della rete e quindi anche dal nodo destinatario.
•  Tutte le strade possibili sono percorse.
•  L'elaborazione associata a questo metodo è minima.
•  Adatto per inviare informazioni a tutti i nodi della rete (broadcasting).

Problema

•  Il problema di flooding è la proliferazione dei pacchetti che si moltiplicano esponenzialmente in ogni nodo.

Soluzioni

•  Un nodo non ritrasmette un pacchetto nella stessa direzione da cui è arrivato.
•  Ogni pacchetto ha un identificativo unico (indirizzo sorgente e numero di sequenza)
•  Ogni nodo crea una lista dei pacchetti già ricevuti e ritrasmessi.
•  I pacchetti già trasmessi vengono ignorati.
•  Un contatore del tempo di vita (TTL) del pacchetto impedisce di rimbalzare all'infinito.

Dinamicità

•  Le metodologie di instradamento devono adattarsi ai cambiamenti topologici della rete.
•  Lo statico decide i percorsi in momenti specifici e non cambia nel breve periodo.
•  Il dinamico modifica i percorsi periodicamente per adattarsi ai cambiamenti della rete.

Random

•  Il next hop viene scelto a caso fra quelli possibili.
•  Le probabilità di scelta possono variare nel tempo.
•  Questo metodo non garantisce la consegna in tempi certi e può portare a comportamenti instabili (loop).

Deflection routing (hot potato)

•  Un nodo riceve un pacchetto e lo ritrasmette sulla linea di uscita avente il minor numero di pacchetti in attesa.
•  Adatto per reti a bassa memorizzazione nei nodi di commutazione.
•  Non tiene conto della destinazione finale del pacchetto e può portare a pacchetti fuori sequenza.

Instradamento con tabella

•  Le linee di ingresso e uscita dei pacchetti sono gestite da una tabella di instradamento all'interno di un nodo di commutazione.
•  Ogni nodo gestisce una tabella di instradamento per il posizionamento dei pacchetti.

Store-and-Forward

•  Il pacchetto entrante viene memorizzato nel nodo.
•  Una volta completamente memorizzato, il nodo lo ritrasmette nella direzione opportuna.
• In generale, una base dati è necessaria per il confronto con la tabella di instradamento.

Shortest path routing

• Si assume che ad ogni collegamento della rete possa essere attribuita una lunghezza.
• La lunghezza rappresenta il costo del collegamento.
• L'algoritmo cerca il percorso più breve per ogni mittente e destinatario.
• L'implementazione può avvenire in modalità centralizzata o distribuita.
• I percorsi vengono aggiornati periodicamente per adattarsi ai cambiamenti nella rete.

Rappresentazione della rete

• Una rete è rappresentata come un grafo orientato.
• I nodi corrispondono a terminali e commutatori.
• Gli archi rappresentano i collegamenti.
• L'orientazione degli archi indica la direzione di trasmissione.
• Il peso degli archi rappresenta il costo del collegamento.

Il grafo della rete

• Una rete è un insieme di nodi di commutazione interconnessi da collegamenti.
• Per rappresentare la rete si possono usare i modelli matematici della teoria dei grafi.
• Un grafo è definito come una coppia di nodi (V, E).
• Un grafo può essere orientato o non orientato.
• Se (i,j) ∈ E, il nodo j è vicino del nodo i.

Rappresentazione di grafi

•  I nodi rappresentano i terminali e i commutatori.
•  Gli archi rappresentano i collegamenti e la loro direzione di trasmissione.

Grafo pesato

•  Un grafo pesato è un grafo G=(V,E) con un peso reale w(i,j) per ogni arco (i,j)
• 
In un grafo non orientato w(i,j) = w(j,i) e in un grafo orientato w(i,j) ≠ w(j,i).

Routing shortest path nel mondo IP

•  Quando i nodi vengono accesi conoscono solo la configurazione delle loro interfacce.
•  Con queste informazioni popolano la tabella di instradamento iniziale.
•  Per implementare il routing shortest path, i nodi utilizzano uno o più protocolli di routing per conoscere la topologia della rete e calcolare le distanze più corte.

Routing Distance Vector

• Basato su Bellman-Ford, in versione dinamica e distribuita.
• Ogni nodo scopre i suoi vicini e ne calcola la distanza da se stesso.
• Ogni nodo invia ai suoi vicini un vettore contenente la distanza stimata da tutti gli altri nodi della rete.
• È un protocollo semplice e richiede poche risorse.
• Presenta problemi di convergenza lenta e partenza lenta (cold start).
• Può soffrire di problemi di stabilità, come il conteggio all'infinito.

Esempio

• Questa sezione presenta esempi numerici o visuali.

Routing algoritmi e protocolli

• Questo capitolo introduce gli algoritmi e protocolli specifici per l'instradamento in Internet.

Cold start e tempo di convergenza

• Allo start-up le tabelle dei singoli nodi sono incomplete.
• Lo scambio di distance vector permette di creare tabelle più complete.
• L'algoritmo converge dopo un numero di passi pari al numero di nodi.

Bouncing effect

• Se un link fra due nodi A e B cade, tutti i nodi interagiscono con la stessa rete tramite altri nodi.
• I nodi possono continuare a scambiarsi inutilmente datagrammi fino a che il TTL non viene esaurito.
• Le incongruenze causate da un link caduto possono creare cicli.

Convergenza lenta

• La convergenza lenta può portare a problemi di stabilità nella connettività.

Count to infinity

• Situazione problematica in cui un'informazione errata sul costo di un percorso si propaga indefinitamente nella rete.
• I diversi rimedi proposti in realtà non sono davvero risolutivi
• Ancora presenti situazioni patologiche in cui protocolli Distance Vector convergono troppo lentamente.

Split horizon

• La tecnica Split Horizon evita le informazioni che creano loop, impedendo l'invio indietro dei dati che si sono appena ricevuti.
• In OSPF, i router non inviano informazioni di routing su collegamenti di ritorno, permettendo una maggiore robustezza.

Triggered update

• Un nodo deve inviare immediatamente le informazioni a tutti i vicini qualora si verifichi una modifica nella propria tabella di instradamento.

Ma non basta...

• I problemi di convergenza possono verificarsi anche con i rimedi proposti.
• In alcune situazioni si potrebbero formare loop.

Il routing link state

• Ogni nodo costruisce un'immagine del grafo della rete.
• Il protocollo ha lo scopo di far creare a ciascun nodo dell'immagine completa della rete.
• L'invio di informazioni di routing è fatto in modo che ciascun nodo sappia come è strutturata la rete.
• Ogni nodo calcola le tabelle di routing utilizzando un algoritmo opportuno.

Raccolta delle informazioni

• Ogni router comunica con i suoi vicini e "impara" i loro indirizzi
• Il router misura la distanza dai suoi vicini.
• Il router crea un pacchetto con lo stato delle linee (Link State Packet) contenente la lista dei suoi vicini e le lunghezze dei collegamenti.

Diffusione ed elaborazione delle informazioni

• I pacchetti LSP vengono distribuiti a tutti i router tramite flooding.
• Ogni pacchetto LSP include indirizzo del mittente, numero di sequenza e data.
• Ogni router ricevendo i LSP si costruisce l'immagine della rete.
• L'algoritmo di Dijkstra è comunemente usato per calcolare i percorsi minimi.

Esempio

• Un esempio di calcolo della distanza di percorsi più brevi usando algoritmo di Dijkstra.

Routing gerarchico

• In Internet si usa il routing gerarchico, detto Autonomous System (AS).
• Ogni network IP è contenuta in un AS o in una RA.
• I protocolli di routing tra i diversi AS sono chiamati Exterior Gateway Protocol (EGP), o meglio Border Gateway Protocol (BGP).
• I protocolli di routing all'interno di un AS invece sono chiamati Interior Gateway Protocol (IGP).

Autonomous Systems and peering

• I sottoinsiemi di Internet sono chiamati Autonomous Systems (AS).
• Internet è una rete di reti, composta da AS interconnessi.

Internet = rete di reti

• Internet viene rappresentata graficamente come un insieme di AS interconnessi.

Internet = sistemi interconnessi

• Internet viene rappresentata graficamente come un insieme di AS interconnessi.

Internet: grafo semplificato

•  Il grafo mostra i sistemi autonomi.
•  I contatti fra gli AS sono indicati con i collegamenti fra i nodi.

Il routing a livello globale

• Il routing a livello globale è un'organizzazione gerarchica di sottoinsiemi di rete autonomi.
• Ogni sottoinsieme è chiamato Autonomous System (AS).
• Le reti autonomi sono legate da punti di contatto.

Autonomous Systems

•  I sottoinsiemi in cui viene suddivisa la rete Internet sono detti Autonomous Systems (AS).
• La definizione classica di AS è un insieme di router gestiti da un'unica amministrazione che utilizza un solo protocollo di routing.

I protocolli di routing

• Gli AS devono implementare sia i protocoli di routing all'interno di un AS (Interior Gateway Protocol, o IGP), sia i protocolli di routing fra diversi AS (Exterior Gateway Protocol, o EGP).

RFC 1930

• L'evoluzione di Internet richiede una definizione più estensiva dell'AS.
• L'AS è un insieme di prefissi di rete IP gestito in modo unitario e con una ben definita politica di routing.

Esempio

• Questo capitolo presenta esempi concreti di AS e loro identificazione.

Internet Routing Registries

• I database contenenti le politiche di routing degli AS sono chiamati Internet Routing Registries.
• 
Un esempio di database è RADb.

AS 137

• Le regole di import e export definiscono quali AS possono comunicare con AS137.
• 
Gli AS ad esempio comunicano a chi possono inviare informazioni di routing.

AS20965. Regole di Import

• AS20965 riceve informazioni di routing da altri AS.

Interconnessione fra AS

• L'interconnessione fra gli AS può essere diretta (peering) o indiretta (attraverso altri AS).

Internet Service Provider (ISP)

• Un ISP fornisce connettività e servizi correlati (web, email, hosting di numeri IP e nomi di dominio) a clienti.
• La classificazione degli ISP avviene in base a diversi criteri e può includere ISP privati con finalità di lucro, senza finalità di lucro o cooperative

Internet region

• Un'Internet region è una parte di Internet che generalmente copre una nazione o un insieme di nazioni vicine.
• L'ISP possono essere nazionali o globali.

Classificazione degli ISP

• I diversi ISP possono essere classificati in base al loro ruolo e copertura della rete (Tier 1, Tier 2, Tier 3).
• Gli ISP Tier 1 hanno un'infrastruttura di rete che copre tutta una nazione.
• Gli ISP Tier 2 o Tier 3 servono aree più ristrette acquistando connettività da ISP di livello superiore.

In sintesi

• Questa sezione fornisce una rappresentazione grafica della gerarchia di interconnessione degli ISP e AS.

In Italia

• Il principale ISP Tier 1 in Italia è Telecom Italia Sparkle (AS6762).

Il Peering

• Il peering è la relazione fra due AS (comunità di rete) per scambiarsi traffico.
• Non ha carattere economico, gli AS non devono pagarsi reciprocamente.

Peering policy

• Policy ristretta: si deve chiedere esplicitamente l'autorizzazione per il peering.
• Policy aperta: i peering sono concessi di default.

In sintesi

Illustrato schematicamente la gerarchia fra i diversi tipi di ISP, specificando la struttura di interconnessione via peering, anche mostrando l'interconnessione fra ISP locale e POP.

ISP locali e POP

• Gli ISP locali forniscono servizi a gruppi di utenti co-localizzati (città, aree industriali)
• Gli ISP locali hanno un POP (Point of Presence) dove hanno l'infrastruttura di rete (router e switch).
• Collegano gli utenti alla loro infrastruttura usando reti (ADSL, fibra ottica, Wi-Fi).

Esempio

• Rappresentazione grafica di una possibile rete di un ISP locale con i suoi POP e le connessioni ai suoi utenti.

Indirizzamento

• Gli ISP gestiscono un sottoinsieme di indirizzi IP per i propri clienti.
• Gli indirizzi IP possono essere consecutivi o meno, richiedendo gestione di più prefissi di rete.

Interconnessione

• Gli ISP che coprono una medesima zona si connettono tramite peering.
• Interconnettere tutti i POP è più complesso.

Non utilizzata

• Questa sezione non contiene informazioni sostanziali; probabilmente il riferimento è ad una immagine o parte non utilizzata della presentazione.

Peering diretto tramite due POP

• Rappresentazione grafica delle connessioni peering fra due ISP.

Da Tier 3 a Tier 1

• Gli ISP di livello Tier 3 si connettono con quelli di livello Tier 1 per accedere a Internet a livello globale, usando generalmente interconnessione fra più POP e attraverso router di transito chiamati Network Service Provider o NSP.
• Possono coincidere con ISP Tier 1.

Internet Exchange

• Le Infrastrutture di scambio dati per connettere direttamente gli ISP si chiamano IXP (Internet Exchange Point).

IXP in Italia

• Si elencano i principali Internet Exchange (IX) presenti in Italia.

Interior Gateway Protocol (IGP)

• Questo è un protocollo di routing che funziona all'interno di un AS (autonomo sistema) per l'instradamento dei pacchetti.

Routing Information Protocol (RIP)

•  Protocollo distance vector, di implementazione vecchia, usato per instradamento.
•  Utilizza messaggi REQUEST e RESPONSE per scambiare informazioni di routing.
• 
Non supporta CIDR, ma solo hop count (distanza da raggiungibilità).

RIP: aggiornamento della tabella di routing

• Se un router riceve un RESPONSE da un altro router, verifica la validità dei dati (indirizzo IP e metrica) e aggiorna la sua tabella di routing.

RIP: problematiche

• Usa split horizon e triggered update, con possibilità di errori.
• Non supporta CIDR.
• È un protocollo insicuro, chiunque possa inviare dati come se fosse un router autorizzato.

La mancanza di CIDR

• Senza CIDR, i router possono confondersi di fronte alla sovrapposizione di indirizzi IP.
• RIP non gestisce il subnetting, e quindi le sottoreti.

RIP versione 2

• Aggiunto il supporto per CIDR, subnet mask.
• Gestione del campo autenticazione.
• Migliorata la compatibilità con altre versioni di RIP.
• Gestione più completa di altre versioni.

Una tipica architettura

•  Diversi router possono fungere da gateway verso diverse reti.
•  Le reti condividono una network per lo scambio delle informazioni di routing.
• 
Il traffico di dati viene distinguito dal traffico di routing.

Il traffico di routing

• Il traffico di routing si scambia sulle reti, richiedendo una gestione ottimizzata e minimizzata per non inficiare il traffico degli utenti.

Multicast

•  Si può ridurre il traffico di routing della rete usando multicast.

IP Multicast

• Utilizza indirizzi IP multicast (da 224.0.0.0 a 239.255.255.255).
• I router possono usare diversi protocolli contemporaneamente per instradare i pacchetti multicast.

The Internet Group Management Protocol (IGMP)

• Serve per dichiarare l'appartenenza ad un gruppo multicast.
• Prevede dei messaggi per iscriversi, abbandonare o valutare l'appartenenza a un gruppo.

Open Shortest Path First (OSPF)

•  Protocollo di tipo link-state per instradamento.
•  Ogni router costruisce un'immagine completa della topologia della rete.
•  In una rete ad accesso multiplo, un Designated Router (DR) si occupa di scambiare queste informazioni.

OSPF: aree di routing

• Un AS può essere suddiviso in aree (RA), interconnesse da un "backbone" (Area 0).
• Ogni area ha router interni ed un Area Border Router che le collega.

OSPF: aree di routing e tipologie di router

•  Rappresentazione grafica di un AS con le sue diverse aree e i diversi tipi di router.

Tipi di route

• Le route possono essere intra-area (all'interno di una stessa area), inter-area (tra aree diverse), o esterne (da altri protocolli).

Tipi di aree

•  Le aree OSPF possono essere normali, stub o totally stub.
•  Le aree stub hanno un solo punto di connessione all'esterno.
• 
Le aree totalmente stub hanno un Route di Default che viene propagata.

OSPF: ulteriori caratteristiche

• OSPF offre bilanciamento del carico per routing.
• Supporta autenticazione per maggiori sicurezze e crittografia.
• Supporta il routing dipendente dal tipo di servizio (TOS).

OSPF: rappresentazione di host e router

• Rappresentazione grafica di host e router in OSPF.

OSPF: tipologie di rete

• OSPF supporta reti point-to-point, broadcast multi-access, e non-broadcast multi-access.

OSPF: vicinanza e adiacenza tra router

• I router possono essere vicini o adiacenti.
• I vicini sono connessi su una stessa rete.
• I router adiacenti devono scambiare informazioni di routing.

OSPF: identificazione di router e priorità

• Ogni router OSPF deve avere un identificativo univoco (Router ID).
• Le priorità vengono assegnate ai router con uno scopo preciso per selezionare il DR.

OSPF: elezione di DR e BDR

• Il procedimento per l'elezione dei router DR e BDR, in modo da permettere lo scambio sicuro di informazioni.

OSPF: Link State Database

• Il Link State Database è la rappresentazione del grafo di rete a disposizione di ogni router.

OSPF: i protocolli

• OSPF usa il protocollo IP con un campo protocol speciale, e messaggi specifici.

OSPF: intestazione comune

• Le caratteristiche dell'intestazione dei messaggi OSPF.

OSPF: Type

• Descrizione dei vari tipi di messaggi OSPF (Hello, Database Description, Link State Request, ecc.).

OSPF: Hello protocol

• Utilizza pacchetti Hello per scoprire i vicini, eleggere DR/BDR, e monitorare i collegamenti.

OSPF: Exchange protocol

• Dopo aver stabilito le adiacenze, router adiacenti sincronizzano i loro database dei link per ottenere complete informazioni sulla rete.

OSPF: Flooding protocol

• Si usa flooding per diffondere le informazioni di stato dei collegamenti in modo rapido ed affidabile.

OSPF: sincronizzazione e aggiornamento

• Le fasi per la sincronizzazione ed aggiornamento di tutti i nodi.

Stub Area

• Area specifica dell'OSPF per facilitare le connessioni verso reti esterne, riducendo la complessità dei router.

Exterior Gateway Protocols (EGP)

• I protocolli EGP funzionano tra diversi autonomous systems (AS).

EGP: limiti

• EGP è progettato per reti ad albero, non reti a maglia.

BGP: Border Gateway Protocol

• BGP è il principale protocollo EGP per Internet, basato su connessione TCP.
• Utilizza due tipi di sessioni (eBGP e iBGP) per la comunicazione fra diversi o stessi AS.

BGP: Path Vector

• BGP è un protocollo path vector perché fornisce un cammino per raggiunger un determinato indirizzo IP, indicando tutti gli Autonomous System attraversati dal percorso.


BGP: attributi

• I diversi attributi delle informazioni nei pacchetti BGP

BGP: codifica degli attributi

• Formato dei dati sugli attributi

BGP: alcuni attributi

• Origin (Code = 1, campo well-known mandatory), identifica la fonte di un'informazione di raggiungibilità.
• AS path (Code = 2, campo well-known mandatory), elenca gli AS attraversati per raggiungere la destinazione.
• Next hop (Code = 3, campo well-known mandatory).

BGP: formato dei messaggi

• BGP utilizza un formato standard per i propri messaggi, comune alla maggior parte dei messaggi, con identificativi e campi dati specifici.

BGP: tipi di messaggio

• I vari tipi di messaggi utilizzati da BGP in diverse circostanze durante le interazioni tra i router.