Il livello Rete – Protocolli di routing e routing dinamico

In questo articolo, Il livello Rete – Protocolli di routing e routing dinamico, impariamo la struttura di internet, gli algoritmi ed i protocolli utilizzati dai Router per definire in modo autonomo i percorsi che devono seguire i pacchetti dall’host mittente all’host di destinazione

Indice dei contenuti

Introduzione

L’obiettivo di questo articolo è quello di capire in che modo le informazioni vengono instradate all’interno di una rete di comunicazione che può essere relativamente piccola fino a raggiungere dimensioni globali come la rete Internet.

Per questo motivo cerchiamo di capire innanzitutto in che modo possiamo “vedere” Internet da un punto di vista dei sistemi e delle reti, chi sono i fornitori dei servizi Internet ed, infine come fanno i router a scambiarsi i dati in modo autonomo.

Internet e gli ISP

Internet può essere concettualmente rappresentata come una struttura stratificata, suddivisa in tre aree principali, immaginate come cerchi concentrici:

• Area centrale (core network): costituisce il nucleo della rete Internet. In questa sezione avviene la commutazione e l’instradamento dei pacchetti tra i core router dei principali fornitori di servizi di connettività. Si tratta della parte più robusta e ad alta capacità della rete, responsabile della gestione del traffico a livello globale.
• Area intermedia o di frontiera (edge network): svolge la funzione di interfaccia tra la rete centrale e le reti degli utenti finali, come quelle domestiche o aziendali. È amministrata da fornitori di servizi di livello locale o regionale, che mettono a disposizione i loro edge router per garantire l’accesso alla rete Internet.
• Area di accesso (access network): rappresenta il punto di collegamento tra il router dell’utente (customer router) e il router del provider di riferimento. L’accesso può essere realizzato tramite diverse tecnologie di trasmissione: cavo in rame (ADSL/VDSL), fibra ottica (FTTH/FTTC), reti wireless (Wi-Fi, LTE, 5G) o sistemi satellitari.

Un Internet Service Provider (ISP) è un’organizzazione che offre connettività a Internet e servizi correlati a pagamento. Gli ISP sono organizzati in una gerarchia basata sulla loro copertura, capacità infrastrutturale e ruolo nella gestione del traffico:

• ISP di livello 1 (Tier 1):
  • occupano la posizione apicale della gerarchia;
  • sono pochi e interconnessi tra loro, formando un reticolo globale;
  • dispongono di una banda di trasmissione estremamente elevata;
  • costituiscono le dorsali (backbone) di Internet, ovvero l’infrastruttura portante che connette le diverse aree del mondo;
  • forniscono servizi agli ISP di livello inferiore.
• ISP di livello 2 (Tier 2):
  • operano a livello nazionale o regionale;
  • si connettono agli ISP di livello 1 e, in alcuni casi, ad altri ISP di pari livello;
  • acquistano servizi dagli ISP Tier 1, fungendo da intermediari tra la dorsale e i provider locali.
• ISP di livello 3 (Tier 3):
  • sono i fornitori locali che gestiscono direttamente la connettività dei clienti finali (famiglie, imprese, enti);
  • acquistano la connettività dagli ISP di livello 2;
  • rappresentano il punto di contatto diretto con l’utente e si occupano di offrire pacchetti commerciali e assistenza.

Oltre a garantire l’accesso alla rete Internet, la maggior parte degli operatori di telecomunicazioni mette a disposizione una serie di servizi complementari destinati ad ampliare le possibilità per l’utente. Tra i più diffusi si annoverano: la registrazione e la gestione dei nomi di dominio, l’hosting e la manutenzione di server dedicati o condivisi, la fornitura di caselle di posta elettronica, nonché soluzioni di sicurezza e backup dei dati.

La scelta di un Internet Service Provider (ISP) non può basarsi unicamente sul prezzo, ma deve tenere conto di molteplici fattori determinanti per la qualità complessiva del servizio, tra cui:

• Copertura geografica: la disponibilità e la qualità della connessione possono variare in base alla zona di residenza o all’area in cui opera l’utente.
• Larghezza di banda offerta: la velocità di trasmissione, sia in download sia in upload, è un parametro essenziale per garantire prestazioni adeguate alle esigenze specifiche (streaming, videoconferenze, applicazioni cloud).
• Affidabilità della connessione: la stabilità e la continuità del servizio rappresentano un requisito fondamentale, soprattutto in ambito aziendale o professionale.
• Tempo di accesso e latenza: un basso ritardo di trasmissione è cruciale per applicazioni in tempo reale come VoIP, gaming online e servizi interattivi.
• Assistenza tecnica: la disponibilità di un supporto efficiente e tempestivo costituisce un elemento di valore aggiunto, in grado di ridurre i tempi di inattività e risolvere rapidamente eventuali problematiche.
• Servizi aggiuntivi e costi: è opportuno valutare i servizi accessori inclusi (domini, hosting, posta elettronica, sicurezza) e confrontarne i costi complessivi, al fine di identificare la soluzione più adatta alle proprie necessità.

Autonomous System e gestione dell’instardamento

La rete Internet è organizzata in domini autonomi, denominati Autonomous System (AS). Ciascun AS comprende una o più reti ed è amministrato da una specifica organizzazione (ad esempio un Internet Service Provider, un ente pubblico o una grande azienda), che stabilisce regole comuni per il funzionamento interno, imponendo l’adozione di un medesimo protocollo di routing a tutte le reti appartenenti al dominio.

La gestione e la registrazione degli Autonomous System sono affidate ai Regional Internet Registry (RIR), organismi che assegnano a ciascun dominio:

• un identificativo numerico univoco, denominato ASN (Autonomous System Number);
• un insieme di indirizzi IP da utilizzare all’interno del dominio.

I RIR sono suddivisi su base geografica:

• AfriNIC: Africa;
• APNIC: Asia e Pacifico;
• ARIN: Nord America;
• LACNIC: America Latina e Caraibi;
• RIPE NCC: Europa, Medio Oriente e parte dell’Asia centrale.

Ogni Internet Service Provider (ISP) gestisce almeno un Autonomous System, attraverso il quale amministra le proprie reti e partecipa al processo di instradamento globale, contribuendo alla stabilità e alla scalabilità dell’intera infrastruttura Internet.

Instradamento

La definizione di Autonomous System nella RFC 1930 è: è un insieme di router, sotto un’unica amministrazione tecnica, che utilizzano protocolli di routing interno (protocol interior gateway) e metriche comuni per instradare i pacchetti all’interno
dell’AS e utilizza un protocollo di routing esterno (exterior gateway protocol) per
instradare i pacchetti ad altri AS

Dalla precedente definizione deduciamo che se un pacchetto viaggia in Internet potrebbe attraversare diversi AS. I router che incontrerà il pacchetto durante il tragitto tra mittente e destinatario sono responsabili del percorso che deve essere seguito dal pacchetto stesso per raggiungere la destinazione.

Il percorso viene definito in base alle informazioni contenute nelle tabelle di routing.

I dati per le tabelle di routing sono calcolati attraverso:
– algoritmi statici (con conoscenza completa della topologia di rete) o
– algoritmi dinamici (i router hanno una conoscenza parziale della rete).

Le tabelle di routing quindi possono essere aggiornate:
– in modo statico (visto nel precedente articolo)
– in modo dinamico (attraverso le informazioni che si scambiano i router). Il calcolo dei percorsi viene fatto con algoritmi adattivi che tengono conto delle continue modifiche della rete

Lo scambio dei dati tra router avviene attraverso protocolli di routing

Routing dinamico

Al crescere della rete WAN di un’organizzazione, la configurazione dei router può ancora essere effettuata con la tecnica del routing statico, ma emergono alcune limitazioni:

• nel caso in cui alcuni collegamenti siano temporaneamente guasti, o indisponibili, è richiesto un intervento manuale per modificare i percorsi di routing;
• l’eventuale aggiunta di una nuova rete in una delle sedi, se non effettuata impiegando la tecnica del subnetting, richiede la riconfigurazione dei router di tutte le sedi.

In una rete complessa i cambiamenti temporanei – dovuti ai guasti, o ll’indisponibilità di collegamenti e dispositivi a causa delle operazioni di manutenzione – o permanenti – come la creazione di una nuova rete IP nella LAN di una sede – sono relativamente frequenti e ciascuno, allo scopo di garantire la continuità di funzionamento dell’intera rete, dovrebbe essere compensato da una parziale riconfigurazione della maggior parte dei router: un compito proibitivo.

Il routing dinamico, noto anche come routing adattivo, abilita i router a scambiarsi automaticamente tra loro, utilizzando specifici protocolli di routing, informazioni sullo stato dei collegamenti e la raggiungibilità delle specifiche reti IP: sulla base delle informazioni ricevute ciascun router modifica continuamente il contenuto della propria tabella di routing per adattarlo dinamicamente ai cambiamenti che avvengono nella topologia dell’intera rete. Il routing dinamico:

• semplifica il compito dell’amministratore che, rispetto al routing statico, non ha più il compito di definire manualmente i singoli percorsi nella tabella di routing;
• si adegua automaticamente ai cambiamenti temporanei o permanenti della topologia della rete.

Esistono diversi protocolli di routing:

• protocolli di routing interni (intra-AS): permettono ai routing interni ad un AS di potersi scambiare informazione affinchè possona modificare le tabelle di routing. Questi protocolli si suddividono in base agli algoritmi che implementano:
  
  – Algoritmi di tipo Distance Vector (i router scambiano informazioni solo con gli altri router adiacenti (esempio: algoritmo di Bellman – Ford)). I protocolli appartenenti a questa classe sono, ad esempio: RIP (Router Information Protocol) e EIGRP (Enanched Interior Gateway Routing Protocol)
  
  – Algoritmi di tipo Link-State (tutti i Router conoscono l’intera topologia della rete). Appartenfono a questa categoria ad esempio il protocollo OSPF (Open Shortsest Path First)
• protocolli di routing esterni (inter-AS): Consentono l’interconnessione e lo scambio di informazioni tra due AS diversi. I router interni ad un AS non conoscono informazioni sulla rete esterna per cui c’è necessità di avere i Gateway Router (o Border Gateway Router) che sono router di frontiera per un AS e sui quali vengono implementati contemporaneamente sia protocolli intra-AS sia protocolli inter-AS. Il protocollo appartenente a questa classe che rappresenta lo standard de facto è il BGP (Border Gateway Protocol) basato su un algoritmo path-vector che verifica sostanzialmente che non ci siano loop (loop-free) e sceglie il best-path cioè il percorso con un numero minimo di AS da attraversare

Qui in basso una mappa che rappresenta e schematizza quanto detto finora:

Dunque, pensando ad Internet o ad una qualsiasi altra rete WAN essa potrebbe essere realizzata in modo che porzioni di essa implementino diversi protocolli di routing:

Algoritmi di Routing

Diamo prima alcune definizioni:

DISTANZA AMMINISTRATIVA (AD): indica l’affidabilità di una fonte di routing. Un numero più basso di AD indica maggiore affidabilità

I router utilizzano entrambe le metriche per determinare il percorso migliore. In particolare valutano prima la AD cioè quale fonte sia più affidabile e poi il costo minimo.

La Distanza amministrativa è definita da un valore (da 0 a 255) che viene associato a diversi protocolli di routing. Qui in basso una tabella con diversi protocolli e relative distanze:

Se un router riceve la stessa rotta sia da OSPF che da RIP sceglierà OSPF perchè ha una AD minore

METRICA DI COSTO: indica la qualità di un percorso in termini di alcuni parametri quali banda disponibile, latenza (ritardo), carico della rete, numero di hop (numero di salti e quindi di router che il pacchetto deve attraversare per raggiungere la destinazione)

Un percorso a costo più basso indica generalmente un percorso migliore, più efficiente e veloce. Esempio: in OSPF il parametro per calcolare il costo è la banda di un collegamento per cui un collegamento con banda maggiore avrà un costo minore.

Entrambe le metriche vengo utilizzate nel routing per determinare il percorso migliore:

1. Il router esamina prima le fonti più affidabili confrontando le AD dei percorsi che ricevono
2. Tra le rotte provenienti dalle fonti affidabili scelgono quella a costo minimo per inoltrare i pacchetti

A questo punto passiamo ad esaminare due algoritmi che consentono di determinare il costo minimo. Le reti che prenderemo in esame saranno rappresentate da nodi che rappresentano i router e archi che rappresentano i collegamenti. Su ogni arco è indicato un numero che rappresenta il costo di quel collegamento

L’obiettivo di ciascun algoritmo è di trasformare il grafo in albero (senza percorsi ciclici) definendo il costo minimo per ciascun percorso.

Algoritmo di Bellman-Ford

Ogni router riceve le informazioni di costo dai router adiacenti e, in base alle informazioni ricevute, modifica la propria tabella di routing affinchè i pacchetti siano inoltrati sempre sul link associato al miglior percorso.

E’ un algortmo iterativo per cui la convergenza è lenta. Ogni router memorizza in un vettore il costo per raggiungere qualsiasi altro router. Perciò è un algoritmo di tipo Distance Vector

Ipotizziamo che la rete sia quella della figura in alto.

• ITERAZIONE 0: ciascun router imposta a 0 il costo per raggiungere se stesso e a ∞ il costo per raggiungere gli altri quindi avremo la seguente situazione:

• ITERAZIONE 1: ogni router aggiorna il vettore in base ai costi verso i nodi adiacenti:

• ITERAZIONE 2: ogni router invia il vettore ai router adiacenti e aggiorna i costi se sono più convenienti.
  
  A [0, 5, 3, ∞, ∞] riceve da B [5, 0, 1, ∞, 12] –>
  – non aggiorna AC perchè 3 (costo diretto A-C) < 5 (costo A-B) + 1 (costo B-C).
  – non aggiorna AD (sempre ∞)
  – aggiorna AE perchè ∞ > 5(costo A-B) + 12 (costo A-E) –> il vettore A diventa
  A [0, 5, 3, ∞, 17]
  
  A [0, 5, 3, ∞, 17] riceve da C [3, 1, 0, 7, ∞] –>
  – aggiorna AB perchè 5 (costo diretto A-B) < 3 (costo A-C) + 1 (costo C-B).
  – aggiorna AD perchè ∞ > 3 (costo A-C) + 7 (costo C-D).
  – non aggiorna AE perchè 17 (costo A-D) ∞ –> il vettore A diventa
  A [0, 4, 3, 10, 17]
  
  
  B [5, 0, 1, ∞, 12] riceve da A [0, 4, 3, 10, 17] –>
  – non aggiorna BC perchè 1 (costo diretto B-C) < 5 (costo B-A) + 3 (costo A-C).
  – aggiorna BD perchè ∞ > 5 (costo B-A) + 10 (costo A-D)
  – non aggiorna AE perchè 12 < 5(costo B-A) + 17 (costo A-E) –> il vettore B diventa
  B [5, 0, 1, 15, 12]
  
  B [5, 0, 1, 15, 12] riceve da C [3, 1, 0, 7, ∞] –>
  – aggiorna BA perchè 5 (costo diretto B-A) < 1 (costo B-C) + 3 (costo C-A).
  – aggiorna BD perchè 15 < 1 (costo B-C) + 7 (costo C-D).
  – non aggiorna BE perchè 12 < 1 (costo B-C) + ∞ –> il vettore B diventa
  B [4, 0, 1, 8, 12]
  
  B [5, 0, 1, 15, 12] riceve da E [∞, 12, ∞, 4, 0] –>
  – non aggiorna BA perchè 5 (costo diretto B-A) < ∞.
  – non aggiorna BC perchè 1 < 17 (costo B-E) +∞ (costo E-C).
  – non aggiorna BD perchè 15 < 17 (costo B-E) + 4 (costo E-D) –> il vettore B diventa
  B [4, 0, 1, 8, 12]
  
  C [3, 1, 0, 7, ∞] riceve da A [0, 4, 3, 10, 17] –>
  – non aggiorna CB perchè 1 (costo diretto C-B) < 3 (costo C-A) + 4 (costo A-B).
  – non aggiorna CD perchè 7 < 3 (costo C-A) + 10 (costo A-D)
  – aggiorna AE perchè ∞ > 3 (costo C-A) + 17 (costo A-E) –> il vettore C diventa
  C [3, 1, 0, 7, 20]
  
  C [3, 1, 0, 7, 20] riceve da B [4, 0, 1, 8, 17] –>
  – non aggiorna CA perchè 3 < 1 (costo C-B) + 4 (costo B-A).
  – non aggiorna CD perchè 7 < 1 (costo C-B) + 8 (costo B-D).
  – aggiorna BE perchè 20 > 1 (costo C-B) + 17 (costo B-E) –> il vettore B diventa
  C [3, 1, 0, 7, 18]
  
  C [3, 1, 0, 7, 18] riceve da D[∞, ∞, 7, 0, 4] –>
  – non aggiorna CA perchè 3 (costo diretto C-A) < 7 (costo C-D) + ∞ (costo D-A) .
  – non aggiorna CB perchè 1 < 7 (costo C-D) +∞ (costo D-B).
  – aggiorna CE perchè 18 > 7 (costo C-D) + 4 (costo D-E) –> il vettore C diventa
  C [3, 1, 0, 7, 11]
  
  D [∞, ∞, 7, 0, 4] riceve da C[3, 1, 0, 7, 18] –>
  – aggiorna DA perchè ∞ > 7 (costo D-C) + 3 (costo C-A).
  – aggiorna DB perchè ∞ < 7 (costo D-C) + 1 (costo D-B).
  – non aggiorna DE perchè 4 < 18 (costo C-E) –> il vettore D diventa
  D [10, 8, 7, 0, 4]
  
  D [10, 8, 7, 0, 4] riceve da E[∞, 12, ∞, 4, 0] –>
  – non aggiorna DA perchè 10 < 4 (costo D-E) + ∞ (costo diretto E-A) .
  – non aggiorna DB perchè 8 < 4 (costo D-E) + 12 (costo E-B).
  – non aggiorna DC perchè 7 > 4 (costo D-E) + ∞ (costo E-C) –> il vettore D diventa
  D [10, 8, 7, 0, 4]
  
  E [∞, 12, ∞, 4, 0] riceve da D[10, 8, 7, 0, 4] –>
  – aggiorna EA perchè ∞ > 4 (costo E-D) + 10 (costo D-A).
  – non aggiorna EB perchè 12 (costo diretto E-B) < 4 (costo E-D) + 8 (costo D-B).
  – aggiorna EC perchè ∞ < 4 (costo E-D) + 7 (costo D-C) –> il vettore E diventa
  E [14, 12, 11, 4, 0]
  
  E [14, 12, 11, 4, 0] riceve da B[4, 0, 1, 8, 17] –>
  – non aggiorna EA perchè 14 < 12 (costo E-B) + 4 (costo B-A).
  – non aggiorna EC perchè 11 (costo E-C) < 12 (costo E-B) + 1 (costo B-C).
  – non aggiorna ED perchè 4 < 12 (costo E-B) + 8 (costo B-D) –> il vettore E diventa
  E [14, 12, 11, 4, 0]
  
  Dopo la seconda iterazione abbiamo i vettori:
  A [0, 4, 3, 10, 17], B [4, 0, 1, 8, 12], C [3, 1, 0, 7, 11], D [10, 8, 7, 0, 4]
  E [14, 12, 11, 4, 0]
• ITERAZIONE 3: capito il meccanismo lavoriamo solo sui vettori
  
  A riceve da B–> controlla se AC > AB+BC –> 3 > 4 + 1 ? NO
  controlla se AD > AB+BD –> 10 > 5 + 8 ? NO
  controlla se AE > AB+BE –> 17 > 5 + 12 ? uguale, non modifica
  
  A riceve da C–> controlla se AB > AC+CB –> 4 > 3 + 1 ? uguale, non modifica
  controlla se AD > AC+CD –> 10 > 4 + 7 ? NO
  controlla se AE > AC+CE –> 17 > 4 + 11 ? SI –> A[0 , 4, 3, 10, 15]
  
  B riceve da A–> controlla se BC > BA+AC –> 1 > 4 + 3 ? NO
  controlla se BD > BA+AD –> 8 > 4 + 10 ? NO
  controlla se BE > BA+AE –> 12 > 4 + 15 ? NO
  
  B riceve da C–> controlla se BA > BC+CA –> 4 > 1 + 3 ? uguale, non modifica
  controlla se BD > BC+CD –> 8 > 1 + 8 ? uguale, non modifica
  controlla se BE > BC+CE –> 12 > 1 + 11 ? uguale, non modifica
  
  B riceve da E–> controlla se BA > BE+EA –> 4 > 12 + 14 ? NO
  controlla se BC > BE+EC –> 1 > 12 + 11 ? NO
  controlla se BD > BE+ED –> 8 > 12 + 4 ? NO
  
  C riceve da A–> controlla se CB > CA+AB –> 1 > 3 + 4 ? NO
  controlla se CD > CA+AD –> 7 > 3 + 10 ? NO
  controlla se CE > CA+AE –> 11 > 3 + 15 ? NO
  
  C riceve da B–> controlla se CA > CB+BA –> 3 > 1 + 4 ? NO
  controlla se CD > CB+BD –> 7 > 1 + 8 ? NO
  controlla se CE > CB+BE –> 11 > 1 + 12 ? NO
  
  C riceve da D–> controlla se CA > CD+DA –> 3 > 7 + 11 ? NO
  controlla se CB > CD+DB –> 7 > 7 + 8 ? NO
  controlla se CE > CD+DE –> 11 > 7 + 4 ? uguale, non modifica
  
  D riceve da C–> controlla se DA > DC+CA –> 10 > 7 + 3 ? uguale, non modifica
  controlla se DB > DC+CB –> 8 > 7 + 1 ? uguale, non modifica
  controlla se DE > DC+CE –> 4 > 7 + 11 ? NO
  
  D riceve da E–> controlla se DA > DE+EA –> 10 > 4 + 14 ? NO
  controlla se DB > DE+EB –> 8 > 4 + 12 ? NO
  controlla se DC > DE+EC –> 7 > 4 + 11 ? NO
  
  E riceve da D–> controlla se EA > ED+DA –> 14 > 4 + 10 ? uguale, non modifica
  controlla se EB > ED+DB –> 12 > 4 + 8 ? uguale, non modifica
  controlla se EC > ED+DC –> 11 > 4 + 7 ? uguale, non modifica
  
  E riceve da B–> controlla se EA > EB+BA –> 14 > 12 + 4 ? NO
  controlla se EC > EB+BC –> 11 > 12 + 1 ? NO
  controlla se ED > EB+BD –> 4 > 12 + 8 ? NO
  
  Dopo la seconda iterazione abbiamo i vettori:
  A [0, 4, 3, 10, 15], B [4, 0, 1, 8, 12], C [3, 1, 0, 7, 11], D [10, 8, 7, 0, 4]
  E [14, 12, 11, 4, 0]
• ITERAZIONE 4:
  A riceve da B–> controlla se AC > AB+BC –> 3 > 4 + 1 ? NO
  controlla se AD > AB+BD –> 10 > 4 + 8 ? NO
  controlla se AE > AB+BE –> 15 > 4 + 12 ? NO
  
  A riceve da C–> controlla se AB > AC+CB –> 4 > 3 + 1 ? uguale, non modifica
  controlla se AD > AC+CD –> 10 > 3 + 7 ? uguale, non modifica
  controlla se AE > AC+CE –> 15 > 3 + 11 ? SI –> A[0 , 4, 3, 10, 14]
  
  B riceve da A–> controlla se BC > BA+AC –> 1 > 4 + 3 ? NO
  controlla se BD > BA+AD –> 8 > 4 + 10 ? NO
  controlla se BE > BA+AE –> 12 > 4 + 14 ? NO
  
  B riceve da C–> controlla se BA > BC+CA –> 4 > 1 + 3 ? uguale, non modifica
  controlla se BD > BC+CD –> 8 > 1 + 8 ? uguale, non modifica
  controlla se BE > BC+CE –> 12 > 1 + 11 ? uguale, non modifica
  
  B riceve da E–> controlla se BA > BE+EA –> 4 > 12 + 14 ? NO
  controlla se BC > BE+EC –> 1 > 12 + 11 ? NO
  controlla se BD > BE+ED –> 8 > 12 + 4 ? NO
  
  C riceve da A–> controlla se CB > CA+AB –> 1 > 3 + 4 ? NO
  controlla se CD > CA+AD –> 7 > 3 + 10 ? NO
  controlla se CE > CA+AE –> 11 > 3 + 15 ? NO
  
  C riceve da B–> controlla se CA > CB+BA –> 3 > 1 + 4 ? NO
  controlla se CD > CB+BD –> 7 > 1 + 8 ? NO
  controlla se CE > CB+BE –> 11 > 1 + 12 ? NO
  
  C riceve da D–> controlla se CA > CD+DA –> 3 > 7 + 11 ? NO
  controlla se CB > CD+DB –> 7 > 7 + 8 ? NO
  controlla se CE > CD+DE –> 11 > 7 + 4 ? uguale, non modifica
  
  D riceve da C–> controlla se DA > DC+CA –> 10 > 7 + 3 ? uguale, non modifica
  controlla se DB > DC+CB –> 8 > 7 + 1 ? uguale, non modifica
  controlla se DE > DC+CE –> 4 > 7 + 11 ? NO
  
  D riceve da E–> controlla se DA > DE+EA –> 10 > 4 + 14 ? NO
  controlla se DB > DE+EB –> 8 > 4 + 12 ? NO
  controlla se DC > DE+EC –> 7 > 4 + 11 ? NO
  
  E riceve da D–> controlla se EA > ED+DA –> 14 > 4 + 10 ? uguale, non modifica
  controlla se EB > ED+DB –> 12 > 4 + 8 ? uguale, non modifica
  controlla se EC > ED+DC –> 11 > 4 + 7 ? uguale, non modifica
  
  E riceve da B–> controlla se EA > EB+BA –> 14 > 12 + 4 ? NO
  controlla se EC > EB+BC –> 11 > 12 + 1 ? NO
  controlla se ED > EB+BD –> 4 > 12 + 8 ? NO
  

• ITERAZIONE 5: vista l’ultima modifica del vettore A viene eseguita l’ultima iterazione ma nessun vettore verrà modificato e la rete converge fino ad una nuova modifica nella rete

I vettori serviranno al completamento delle tabelle di routing e a definire i percorsi migliori (evidenziati in rosso):

Conseiderando solo i link relativi ai percorsi migliori otteniamo l’albero:

Algoritmo di Dijkstra

L’algoritmo di Dijkstra è un algoritmo di routing Shortest Path (SPF) utilizzato dai router per trovare il percorso più breve e con il minor costo verso ogni altra destinazione nella rete. 

Funzionamento: Ogni router esegue in modo indipendente l’algoritmo, calcolando il cammino minimo da sé (come nodo “radice”) verso tutte le altre destinazioni. Il risultato di questo calcolo viene memorizzato nella tabella di routing del router, che indica quale sia il nodo successivo da attraversare per raggiungere una specifica destinazione lungo il cammino a costo minimo. 

L’algoritmo analizza il grafo a partire da un nodo sorgente e visita gli altri nodi una sola volta. Esso tiene traccia della distanza di ciascun nofo dal nodo di origine e aggiorna tale distanza se trova un percorso migliore.

Ad ogni istante dunque tutti i router della rete sono a conoscenza dell’intera topologia e di come raggiungere qualsiasi destinazione (non solo i nodi adiacenti)

Analizziamo, ad esempio la stessa rete di esempio che abbiamo visto in precedenza. Ad ogni nodo viene assegnata un’etichetta [c, p] dove c = costo e p=nodo di provenienza che viene eventualmente modificata appena si identifica un percorso migliore. Ipotizziamo A come nodo di origine:

• ITERAZIONE 1: Etichettiamo i nodi adiacenti ad A e segnamo A come nodo visitato. Il costo è dato dal costo del predecessore + il costo assegnato al link:

• ITERAZIONE 2: Scegliamo il nodo da visitare con costo minore (C) ed etichettiamo i nodi adiacenti ad eccezione di quelli già visitati. Segnamo C come visitato:

• ITERAZIONE 3: scegliamo di visitare B (costo minore rispetto a D), aggiorniamo l’etichetta E (unico nodo adiacente a B non ancora visitato) e segnamo B come nodo visitato

• ITERAZIONE 4: scegliamo di visitare D (costo minore rispetto a E), aggiorniamo l’etichetta E (unico nodo adiacente a D non ancora visitato) e segnamo D come nodo visitato

L’algoritmo termina perchè E non ha nodi adiacenti non visitati. Adesso partendo dall’ultimo nodo visitato e ripercorrendo a ritroso i nodi predecessori riotteniamo in definitiva lo stesso riusltato ottenuto con Bellman-Ford

Protocolli di Routing

Analizziamo ora nel dettaglio tre dei principali protocolli di routing maggiormente utilizzati. Per quanto riguarda i protocolli di classe IGP (Interior gateway protocol) studieremo

• il protocollo RIP (Routing Information Protocol), basato sull’algoritmo di Bellman-Ford quindi un protocollo Distance Vector, nelle due versioni (RIP e RIPv2)
• il protocollo OSPF (Open Shortest Path First) basato sull’algoritmo di Dijksta quindi un protocollo Link-State

Per quanto riguarda i protocolli di classe EGP (Exterior gateway protocol) studieremo:

• BGP (Border Gateway Protocol) che rappresenta lo standart de facto per il routing Inter Autonomous System

Protocollo RIP (Routing Information protocol)

Le caratteristiche principali del protocollo sono:

• aggiornamento della tabella di routing in base alle informazioni ricevute ogni 30 secondi dai router adiacenti
• metrica utilizzata: hop-count (numero di router che un pacchetto deve attraversare per raggiungere la destinazione). Per impedire loop infiniti si impone un limite massimo di salti = 15 oltre il quale si ritiene il router irraggiungibile (distanza = ∞)
• distanza amministrativa = 120
• RIPv1 non invia la subnet mask per cui non è utile nel caso di subnetting. Invia messaggi incapsulati in segmenti UDP (si appoggia a UDP come protocollo a livello trasporto) ed inviati all’indirizzo 255.255.255.255 in broadcast. Non supporta autenticazione –> protocollo non sicuro
• RIPv2 supporta la gestione delle subnet, invia messaggi all’indirizzo 224.0.0.9 in multicast e prevede autenticazione con password –> protocollo sicuro

Formato del messaggio RIP

• Command: può essere una richiesta o una risposta
• Version: 1 o 2 indica la versione utilizzata
• Must be zero: 2 byte a 0
• Address family Identifier AFI: RIP è progettato per trasportare informazioni di routing per diversi protocolli. Se il campo è impostato a 2 identifica una rete IP
• IP Address: contiene l’indirizzo di rete della destinazione
• Metric: contiene il numero di hop

Ogni Route Entry costituita da AFI, IP Address, Must be zero e metric è di 20 byte

Per l’header di RIPv2 i campi ed i significati sono simili ma abbiamo in più:

• Route Tag: serve per comunicare con altri protocollo di routing quindi specifica se il pacchetto è destinato esternamente ad un AS
• Subnet mask: maschera di sottorete della rete specificata in IP
• Next Hop: specifica l’interfaccia del router successivo

Il Protocollo RIP (nella versione RIPng (next generation) supporta IPv6

Configurazione RIP in un router CISCO

Protocollo OSPF (Open Shortest Path First)

Il protocollo OSPF (Open Shortest Path First), appartenente alla famiglia dei protocolli di routing link-state, è stato standardizzato per la prima volta nel 1989. OSPF utilizza come metrica, nella configurazione più comune, il rapporto tra un valore di riferimento predefinito (generalmente pari a 10⁸ bit/s) e la larghezza di banda (bandwidth) dei collegamenti tra i router

Ogni router che implementa OSPF riceve periodicamente aggiornamenti dagli altri router, servendosi delle informazioni contenute in uno specifico pacchetto dati (LSP – Link State Packet) che scambia con gli altri nodi.

LSP gli permettono di costruire e mantenere una mappa topologica della rete costantemente aggiornata. In seguito a ogni modifica nella topologia, il router esegue l’algoritmo di Dijkstra per calcolare i percorsi ottimali verso le destinazioni. Questa caratteristica rende OSPF particolarmente adatto all’impiego in reti di medie e grandi dimensioni.

I pacchetti LSP (Link State Packet) vengono trasmessi periodicamente utilizzando una tecnica detta flooding: ogni pacchetto ricevuto da un router viene inoltrato su tutte le interfacce di uscita, ad eccezione di quella da cui è stato ricevuto originariamente.

Oltre alla trasmissione ciclica, un nuovo LSP viene generato ogni volta che si verifica una variazione nello stato dei collegamenti con i nodi adiacenti. Tali variazioni possono includere, ad esempio:

• un cambiamento nello stato della connessione (attiva, congestionata, interrotta);
• l’aggiunta di un nuovo nodo alla rete;
• una modifica del costo associato a un link esistente.

Tutti i pacchetti LSP ricevuti vengono memorizzati all’interno di un database locale, chiamato Link State Database (LSDB), il quale contiene una rappresentazione completa e aggiornata della topologia della rete. Questo database costituisce la base su cui viene eseguito l’algoritmo di instradamento (come l’algoritmo di Dijkstra) per determinare i percorsi ottimali.

Attualmente, le versioni operative di OSPF sono:

• OSPFv2, utilizzata per ambienti basati su IPv4;
• OSPFv3, sviluppata per supportare IPv6

La versione 1 del protocollo, che non prevedeva il supporto per indirizzi IPv4 classless tramite netmask, è oggi considerata obsoleta.

Modalità operative

OSPF prevede due principali modalità di funzionamento:

• Single-area: modalità adatta a reti di dimensioni intermedie, prive di una struttura gerarchica. L’intera rete è considerata un’unica area all’interno della quale i router possono essere connessi in qualsiasi topologia.
• Multi-area: modalità pensata per reti di grandi dimensioni, organizzate secondo un’architettura gerarchica. Le varie aree sono interconnesse tramite una area backbone centrale, che funge da canale di comunicazione tra le aree. In questo modello, lo scambio di informazioni di routing e l’applicazione dell’algoritmo di Dijkstra avvengono all’interno di ciascuna area, riducendo il carico computazionale e migliorando l’efficienza complessiva.

Le principali caratteristiche di OSPF sono:

• è basato sull’algoritmo di Dijkstra: in fase di inizializzazione, o quando si verificano modifiche sulla rete, ogni router riceve dai router adiacenti lo stato del collegamento, aggiorna la tabella di routing, e propaga (inonda) l’aggiornamento verso gli altri router;
• la metrica è basata sulla larghezza di banda;
• la distanza amministrativa è 110;
• è ottimizzato per reti di grandi dimensioni, ha un tempo di convergenza basso, ma è complesso e consuma molte risorse in termini di elaborazione e memoria;
• supporta il subnetting, il VLSM e l’autenticazione

Configurazione del protocollo OSPF in un router Cisco

L’interprete CLI del sistema operativo Cisco IOS espone comandi separati per la configurazione dei protocolli di routing OSPFv2 per percorsi IPv4 e OSPFv3 per percorsi IPv6.

Nella configurazione delle interfacce si fa uso della WILD CARD Mask. Essa è una maschera a 32 bit che indica ai router quali bit dell’indirizzo a cui si applica devono essere presi in considerazione.

Se nella Wild Card Mask un bit è a 0 allora il corrispondente bit dell’indirizzo verrà preso in considerazione

Se nella Wild Card Mask un bit è a 1 allora il corrispondente bit dell’indirizzo non verrà preso in considerazione

In altre parole la Wild Card Mask è il complemento a 1 della Net Mask e si ottiene sottraendo da 255.255.255.255 la net Mask:

OSPFv2

I comandi riportati nella tabella seguente consentono di impostare il routing dinamico IPv4 mediante protocollo OSPFv2:

La configurazione minima del protocollo OSPFv2 è costituita dal comando #router ospf process, più i comandi #network sufficienti per abilitare la pubblicizzazione di tutte le reti IP configurate sulle interfacce del router ed, eventualmente, il comando #default-information originate nel caso che si debba propagare una default route.

OSSERVAZIONE: IOS consente l’abilitazione di istanze OSPFv2 multiple su un singolo router identificate dal numero di processo specificato. Comunque, il numero di un processo ha esclusivamente valore locale e non deve quindi corrispondere tra router distinti.

I comandi #network hanno come secondo parametro una wildcard-mask nella quale il significato dei singoli bit è opposto a quello dei singoli bit di una netmask: il valore «0» significa che il bit corrispondente dell’indirizzo IPv4 deve coincidere, mentre il valore «1» significa che il bit corrispondente dell’indirizzo viene ignorato; nella tabella seguente sono riportate le wildcard-mask più utilizzate.

OSSERVAZIONE: Nella maggior parte dei casi pratici è sufficiente identificare una rete IP con una wildcard-mask complementare rispetto alla netmask della rete IP stessa. Il comando #passive interface permette di specificare un’interfaccia del router a cui sicuramente non sono connessi altri router, come nel tipico caso di una rete LAN: di conseguenza il comando disabilita la trasmissione/ricezione dei messaggi del protocollo sull’interfaccia.

OSSERVAZIONE: Il comando #bandwidth non modifica la banda fisica dell’interfaccia, ma ne imposta il valore virtuale in modo che possa essere impiegato per la determinazione del costo del relativo collegamento: questo comando consente all’amministratore di rete di influenzare la metrica del protocollo OSPF. In alternativa, è possibile impostare direttamente il costo di un collegamento senza modificare la banda virtuale della relativa interfaccia con il comando #ip ospf cost.

OSPFv3

I comandi riportati nella tabella seguente consentono di impostare il routing dinamico IPv6 mediante protocollo OSPFv3.

La configurazione minima del protocollo OSPFv3 è costituita dai comandi #ipv6 router ospf process su tutte le interfacce per le quali si intendono pubblicizzazione le reti IP configurate ed, eventualmente, il comando #default-information originate nel caso che si debba propagare una default route.

OSSERVAZIONE: IOS consente l’abilitazione di istanze OSPFv3 multiple su un singolo router identificate dal numero di processo specificato: l’eventuale non corrispondenza tra i numeri dei processi è di conseguenza causa di malfunzionamenti inattesi. Comunque, il numero di un processo ha esclusivamente valore locale e non deve quindi corrispondere tra router distinti.

Il protocollo BGP: fondamenti e funzionamento

L’unico protocollo di tipo Exterior Gateway Protocol (EGP) attualmente adottato per interconnettere differenti Autonomous System (AS) è il BGP (Border Gateway Protocol). Si tratta di un protocollo di routing basato su vettori di percorso (Path Vector), il quale determina le rotte da seguire in base a politiche definite autonomamente da ciascun sistema. Una delle sue caratteristiche principali è la capacità di memorizzare l’intero percorso attraversato, consentendo così il corretto instradamento dei pacchetti tra più AS.

Il principale obiettivo di un router che utilizza BGP è quello di scambiare informazioni con altri router peer (processo noto come peering), al fine di acquisire l’elenco aggiornato dei Sistemi Autonomi da attraversare per raggiungere una determinata destinazione. Grazie a questo scambio continuo, ciascun AS mantiene una visione aggiornata della topologia globale della rete, adattandosi dinamicamente ai cambiamenti.

A differenza di altri protocolli, BGP non impone un’unica metrica comune a tutti i sistemi; al contrario, consente a ogni AS di definire autonomamente le proprie regole di instradamento, rendendo il processo altamente flessibile e personalizzabile.

Il processo decisionale nel BGP

Le decisioni di instradamento adottate da un router BGP si basano su tre fasi fondamentali:

1. Acquisizione dei dati

• Rotte in ingresso: informazioni sulle rotte ricevute dai router adiacenti, conservate nella Adj-RIB-in (Adjacent Routing Information Base – incoming).
• Politiche di instradamento locali: regole definite all’interno del sistema, memorizzate nella Policy Information Base (PIB), che possono includere criteri per selezionare o escludere determinati AS.

2. Elaborazione

• Valutazione delle rotte: per ciascuna rotta ricevuta, il router calcola un valore di preferenza che ne determina la priorità.
• Selezione del percorso ottimale: tra tutte le rotte disponibili per una determinata destinazione, viene scelto il percorso ritenuto più vantaggioso. In questa fase, eventuali rotte ridondanti vengono identificate e gestite per evitare la formazione di loop di instradamento, che possono compromettere le prestazioni della rete.

3. Distribuzione dei risultati

• Aggiornamento della tabella di routing locale: le rotte selezionate vengono inserite nella Loc-RIB (Local Routing Information Base), che rappresenta le rotte attive per l’instradamento dei pacchetti.
• Annuncio ai router adiacenti: i percorsi scelti vengono comunicati ai peer tramite la Adj-RIB-out (Adjacent Routing Information Base – outgoing), rendendo pubbliche le nuove rotte e mantenendo sincronizzata la rete.

Conclusioni

I CONCETTI CHIAVE

LIMITAZIONI ROUTING STATICO. Al crescere della rete WAN di un’organizzazione, la configurazione dei router può ancora essere effettuata con la tecnica del routing statico, ma emergono alcune limitazioni: la ridondanza dei collegamenti consente la comunicazione tra le varie sedi anche nel caso che alcuni di questi siano temporaneamente guasti, o indisponibili, ma è richiesto un intervento manuale per modificare i percorsi di routing; l’eventuale aggiunta di una nuova rete in una delle sedi, se non effettuata impiegando la tecnica del subnetting, richiede la riconfigurazione dei router di tutte le sedi.

ROUTING DINAMICO. Il routing dinamico, noto anche come routing adattivo, abilita i router a scambiarsi automaticamente tra loro, utilizzando specifici protocolli di routing, informazioni sullo stato dei collegamenti e la raggiungibilità delle specifiche reti IP: sulla base delle informazioni ricevute ciascun router modifica continuamente il contenuto della propria tabella di routing per adattarlo dinamicamente ai cambiamenti che avvengono nella topologia dell’intera rete. Il routing dinamico semplifica il compito dell’amministratore che, rispetto al routing statico, non ha più il compito di definire manualmente i singoli percorsi nella tabella di routing; inoltre si adegua automaticamente ai cambiamenti temporanei o permanenti della topologia della rete.

SISTEMA AUTONOMO. Un sistema autonomo, o AS (Autonomous System), è una parte della rete Internet, a sua volta costituita da più reti, gestita da un’unica organizzazione ed è identificato da un codice numerico a 16 o 32 bit definito ASN (Autonomous System Number) rilasciato dalla IANA (Internet Assigned Numbers Authority).

PROTOCOLLI IGP E EGP. I protocolli di routing dinamico che operano all’interno dei singoli AS e quelli che operano tra AS distinti appartengono a due classi diverse: i protocolli di classe IGP (Interior Gateway Protocol) scambiano le informazioni di routing all’interno di un singolo AS; i protocolli di classe EGP (Exterior Gateway Protocol) scambiano le informazioni di routing tra router di AS diversi.

ALGORITMI DEI PROTOCOLLI DI ROUTING. Ogni protocollo di routing è basato su un algoritmo di selezione dei percorsi su cui i pacchetti sono instradati per raggiungere le reti IP di destinazione e che vengono inseriti nella tabella di routing del router che esegue il protocollo stesso.

PROTOCOLLI DI ROUTING IGP. I protocolli di routing di classe IGP hanno lo scopo di scambiare informazioni tra i router di una rete al fine di rilevarne in modo autonomo i cambiamenti di topologia e modificare il contenuto delle tabelle di routing adeguandolo automaticamente alla nuova situazione.

TEMPO DI CONVERGENZA. Il tempo medio che intercorre tra un cambiamento della topologia e il momento in cui le tabelle di routing di tutti i router della rete risultano aggiornate è definito tempo di convergenza.

METRICA. Un protocollo di routing deve essere in grado di selezionare tra molti un singolo percorso, costituito da una sequenza di collegamenti tra router, in base a un criterio quantitativo che ne rappresenta la metrica.

PROTOCOLLI DISTANCE-VECTOR. I protocolli di routing di categoria distance-vector non costruiscono una mappa topologica dell’intera rete, ma si limitano, per ogni interfaccia di ciascun router, a mantenere aggiornato un vettore delle distanze – espresse in base alla metrica utilizzata – di tutte le reti IP della rete. Nel caso che la stessa rete IP sia raggiungibile da interfacce diverse di un router, viene inserita nella tabella di routing in relazione all’interfaccia per la quale la distanza è minore.

PROTOCOLLI LINK-STATE. I protocolli di routing di categoria link-state costruiscono in ogni router una mappa topologica dell’intera rete sulla base della quale determinano algoritmicamente i percorsi ottimi – in relazione alla metrica utilizzata – verso tutte le reti IP che costituiscono la rete e inseriscono le interfacce di uscita iniziali del percorso nella tabella di routing.

DISTANZA AMMINISTRATIVA. Se in alcuni router di una rete sono configurati più protocolli di routing dinamico aventi una metrica diversa, eventuali percorsi verso la stessa rete IP di destinazione rilevati da protocolli distinti non possono essere selezionati in base alla metrica. Per casi come questo viene definito un ordine di priorità tra le origini delle informazioni di routing denominato distanza amministrativa in cui le priorità più alte corrispondono a valori numerici minori.

PROTOCOLLO RIP. La prima versione del protocollo distance-vector RIP (Routing Information Protocol) è stata utilizzata fin dalla fine degli anni Ottanta. RIP adotta come metrica lo hop-count limitato a un valore massimo di 15: questo limite permette di impiegarlo oggi solo con reti di piccole dimensioni. Le versioni attualmente usate sono la versione 2 per il protocollo IPv4 e la versione ng (next generation) per il protocollo IPv6. In una rete in cui viene configurato il protocollo di routing RIP, ogni router scambia periodicamente con i router adiacenti – normalmente ogni 30 s – il contenuto della propria tabella di routing: a questo scopo viene utilizzata la porta 520 del protocollo di trasporto UDP.

ALGORITMO DI DIJKSTRA. Le informazioni scambiate tra i router che eseguono un protocollo di routing di categoria link-state consentono a ogni router di disporre di una mappa topologica aggiornata dell’intera rete. Una volta fissata la metrica, il relativo valore numerico può essere attribuito a ogni collegamento tra due router della rete e l’algoritmo pubblicato nel 1959 dal matematico e informatico olandese Edsger W. Dijkstra è in grado di determinare tutti i percorsi ottimi, cioè con il valore minimo della metrica, che vanno da uno specifico router a tutti gli altri router e, di conseguenza, a tutte le possibili reti IP di destinazione.

PROTOCOLLO OSPF. La prima versione del protocollo link-state OSPF (Open Shortest Path First) è stata standardizzata nel 1989. OSPF adotta normalmente come metrica il rapporto tra un valore di riferimento predefinito (normalmente 10⁸ bit/s) e la bandwidth dei collegamenti tra router. Ogni router che esegue il protocollo OSPF riceve dagli altri router informazioni che gli consentono di mantenere aggiornata in tempo reale una mappa topologica locale dell’intera rete sulla quale, a ogni cambiamento, viene eseguito l’algoritmo di Dijkstra per determinare i percorsi ottimi: questa caratteristica permette di impiegarlo con reti di medie e grandi dimensioni. Le versioni attualmente usate sono la versione 2 per il protocollo IPv4 e la versione 3 per il protocollo IPv6. In una rete in cui viene configurato il protocollo di routing OSPF, i router si scambiano direttamente messaggi incapsulati in pacchetti IP senza impiegare nessun protocollo di trasporto.

MODALITÀ SINGLE-AREA E MULTI-AREA. Il protocollo di routing OPSF distingue due diverse modalità operative: single-area, modalità adatta a reti di medie dimensioni in cui la rete non ha una struttura gerarchica ed è costituita da una singola area in cui i router possono essere interconnessi tra loro in un modo qualsiasi; multi-area, modalità adatta a reti di grandi dimensioni in cui la rete ha una struttura gerarchica e le varie aree comunicano tra loro esclusivamente mediante un’area backbone centrale, limitando alle singole aree lo scambio delle informazioni di routing e l’applicazione dell’algoritmo di Dijkstra per la determinazione dei percorsi ottimi.

LINK STATE ADVERTISEMENT (LSA). I messaggi LSA diffondono in tutta la rete lo stato dei singoli collegamenti (link-state): è questa l’informazione di base che consente a ogni singolo router di costruire la mappa topologica locale dell’intera rete sulla quale eseguire l’algoritmo di Dijkstra per individuare i percorsi ottimi.