Architettura Internet - Concetti fondamentali riassunti

E.

L’obbiettivo naturale di un algoritmo di instradamento è l’individuazione dei

percorsi meno costosi tra sorgente e destinazione, con percorso intendiamo

una sequenza di nodi tali che ciascuna delle coppie sia un arco appartenete ad

E. Il costo di un percorso è semplicemente la somma di tutti i costi degli archi

lungo il percorso. Tra gli infiniti percorsi possibili solo pochi possono essere

definiti percorsi a costo minimo. Se tutti gli archi hanno lo stesso costo, il

percorso a corso minimo è rappresentato dal percorso più breve (con meno

router).

Gli algoritmi di instradamento sono classificabili come globali e decentralizzati:

Un algoritmo di instradamento globale calcola il percorso minimo tra una

 sorgente e una destinazione avendo una conoscenza globale della rete.

Questi algoritmi sono spesso detti algoritmi link state dato che

l’algoritmo deve essere conscio del costo di ciascun collegamento della

rete

In un algoritmo di instradamento decentralizzato, il percorso a costo

 minimo viene calcolato in modo distribuito e iterativo, nessun nodo

possiede informazioni complete sul costo di tutti i collegamenti di rete

ma soltanto dei collegamenti adiacenti. Di questa tipologia tratteremo

solo l’algoritmo distance vector chiamato così perché ogni nodo elabora

un vettore di stima dei costi verso tutti gli altri nodi della rete.

Possiamo ulteriormente classificare gli algoritmi per staticità o dinamicità: negli

algoritmi di instradamento statici i percorsi cambiano molto raramente, come

risultato dell’intervento umano; negli algoritmi di instradamento dinamici i

percorsi variano al variare del volume di traffico nella rete. Gli algoritmi

dinamici rispondono meglio ai cambiamenti della rete ma sono più soggetti a

problemi di instradamento ciclico e oscillazione di percorsi.

Classifichiamo infine gli algoritmi per sensibilità al carico trasportato, tali

algoritmi prendono il nome di load-sensitive e load-insensitive. Negli algoritmi

load-sensitive i costi dei collegamenti variano dinamicamente in base alla

congestione

Algoritmo di instradamento Link state (LS)

In questo algoritmo la tipologia di rete e tutti i costi dei collegamenti sono noti

e disponibili in input all’algoritmo. Ciò si ottiene facendo inviare a ciascun nodo

pacchetti sullo stato dei suoi collegamenti a tutti gli altri nodi della rete

attraverso un algoritmo di link-state broadcast. In tal modo tutti i nodi

dispongono di una vista identica e completa della rete e ciascun nodo che

lancerà tale algoritmo otterrà gli stessi risultati.

L’algoritmo di instradamento LS è noto come algoritmo di Dijkstra e calcola il

percorso minimo da un nodo di origine a tutti gli altri nodi nella rete, è iterativo

ed ha le seguenti proprietà: dopo la k-esima iterazione, tutti i percorsi a costo

minimo sono nodi a k nodi di destinazione e questi k percorsi hanno i k costi più

bassi.

L’algoritmo consiste in un passo di inizializzazione seguito da un ciclo che viene

eseguito una volta per ogni nodo del grafo, quando termina sarà stato calcolato

il percorso a costo minimo dal nodo di origine a tutti gli altri nodi.

Complessivamente il numero totale di nodi da cercare in tutte le interazioni è

n(n+1)/2 e pertanto diciamo che nel caso peggiore un algoritmo LS ha una

complessità di origine quadratico: O(n )

2

Algoritmo di instradamento “distance vector” (DV)

L’algoritmo distance vector è iterativo, asincrono e distribuito. Distribuito nel

senso che ciascun nodo riceve parte dell’informazione da uno o più dei suoi

vicini direttamente connessi a cui, dopo aver effettuato calcoli, restituisce i

risultati. Iterativo nel senso che questo processo si ripete fino a quando non

avviene ulteriore scambio informativo tra vicini. Asincrono nel senso che non

richiede che tutti i nodi operino al passo con gli altri.

L’algoritmo è auto terminate cioè non viene fermato da alcun segnale,

semplicemente trovato il percorso si blocca. I costi minimi sono garantiti dalla

formula di Bellman-Ford.

Con l’algoritmo DV ciascun nodo x mantiene in una tabella di instradamento i

seguenti dati:

Per ciascun vicino v, il costo c(x,v)

 Il vettore delle distanze contenente le stime del costo verso tutte le

 destinazioni

I vettori delle distanze per tutti i vicini di x



Quando un nodo x riceve un nuovo vettore da qualcuno dei suoi vicini v, lo

salva e usa la formula di Bellman-Ford per aggiornare il proprio vettore.

Mentre gli algoritmi di tipo LS prevedono che ogni router sia informato dei

cambiamenti occorsi nell’intera topologia della rete, i protocolli DS sono più

leggeri: ogni router misura la distanza che lo separa dai nodi adiacenti

ricevendo i dati dai router vicini. A partire da tali dati, utilizzando l’algoritmo di

Bellman-Ford, il router costruisce la tabella di instradamento che associa ad

ogni destinazione conosciuta una stima della distanza che lo separa dalla

destinazione e il primo passo del percorso calcolato. Periodicamente poi il

router aggiorna le misure di distanza dai router adiacenti e comunica la tabella

ai vicini. Dopo sufficienti scambi di informazioni, ciascun router potrà avere una

riga per ogni altro nodo nella rete.

Variazione dei costi di trasferimento non comunicati possono causare problemi

di conteggio all’infinito dell’algoritmo che in queste circostanze farà

“rimbalzare” i pacchetti tra due nodi adiacenti. Tale situazione può essere

evitata utilizzando la poisoned reverse (inversione avvelenata): l’idea è

semplice, se il nodo z instrada tramite y per raggiungere x; allora z avvertirà y

che la sua distanza verso x è infinita anche se in realtà non lo è. Dato che y

crede che z non abbia un percorso verso x non tenterà mai di passare per z per

instradare verso x.

Confronto tra gli algoritmi LS e DV

I due algoritmi utilizzano approcci complementari nel calcolare l’instradamento.

Complessità dei messaggi: LS richiede che ciascun nodo conosca il costo

 di ogni collegamento nella rete, ciò implica un numero di |N|*|E|

messaggi che aumentano ogni qual volta avviene un cambiamento di

costo di un collegamento in quanto questo cambio va comunicato a tutti.

DV invece ad ogni interazione richiede scambi di messaggi tra nodi

adiacenti e quando cambia un costo tale cambiamento viene comunicato

ai nodi adiacenti che variano di conseguenza il percorso a costo minimo;

il tempo richiesto perché l’algoritmo converga dipende da molti fattori.

Velocità di convergenza: DV può convergere lentamente e può presentare

 cicli di instradamento; presenta anche il problema del conteggio

all’infinito

Robustezza: LS fa comunicare i router in broadcast, eventuali sbagli sono

 limitati al singolo router in errore. I nodi LS si occupano di calcolare

soltanto le proprie tabelle di inoltro e quindi i calcoli di istradamento sono

isolati. Questo fornisce un certo grado di robustezza. DV invece può

comunicare percorsi a costo minimo errati a tutte le destinazioni

Nessuno dei due algoritmi è nettamente superiore all’altro e quindi vengono

entrambi utilizzati Instradamento Gerarchico

Negli algoritmi visti ciascun router era indistinguibile dagli altri in quanto

eseguivano lo stesso algoritmo per calcolare l’instradamento attraverso la rete.

Questo modello è un po’ troppo semplicistico per problemi di scalabilità (al

crescere del numero di router, il tempo richiesto per calcolare e memorizzare le

informazioni di instradamento diventa proibitivo e algoritmi come DV non

convergerebbero mai) e autonomia amministrativa (che dal punto di vista

ideale è concessa ad ogni amministratore di rete pur mantenendo la possibilità

di connetterla alle reti esterne).

Problemi di questo tipo si risolvono organizzando i router in sistemi autonomi

(AS) composti da gruppi di router posti sotto lo stesso controllo amministrativo.

I router di un AS eseguono lo stesso algoritmo ed hanno gli uni informazioni

sugli altri; un algoritmo in esecuzione su un AS è detto protocollo di

instradamento interno al sistema autonomo (intra-AS routing protocol).

Ovviamente è necessario connettere gli AS tra loro e per farlo si utilizzano

router gateway che avranno l’ulteriore compito di inoltrare pacchetti a

destinazioni esterne.

Un AS dovrebbe conoscere le destinazioni raggiungibili attraverso gli altri AS e

quindi informare tutti i router all’interno del sistema in modo che ciascuno

possa configurare la propria tabella di inoltro per gestire le destinazioni

esterne. È proprio il intra-AS routing protocol a gestire entrambi i compiti.

In internet tutti i AS usano lo stesso protocollo intra-AS detto BGP4

BGP

Il border gateway protocol versione 4 (BGP4) è lo standard dei protocolli di

instradamento degli AS; esso mette a disposizione di ciascun AS un modo per:

Ottenere informazioni sulla raggiungibilità delle sottoreti da parte di

 sistemi confinanti

Propagare informazioni di raggiungibilità a tutti i router interni all’AS

 Determinare percorsi “buoni” verso le sottoreti



In BGP coppie di router scambiano informazioni di instradamento su

connessioni TCP semipermanenti usando la porta 179, i router ai capi di una

connessione TCP sono chiamati BGP peer. Nel caso tale connessione coinvolga

due AS verrà detta sessione esterna o eBGP; se invece i router sono entrambi

nello stesso AS sarà una sessione interna o iBGP. In BGP le distanze non sono

host ma piuttosto prefissi CIDR

Attributi dei percorsi e rotte BGP

In BGP, un AS viene identificato mediante un numero globalmente univoco

detto ASN; non tutti gli AS hanno però un numero, in particolare gli AS stub

trasportano solo traffico di cui sono sorgente o destinazione e non utilizzano

ASN. Quando un router annuncia un prefisso per la sessione include un certo

numero di attributi BGP, un prefisso e i suoi attributi è detto rotta. I principali

attributi sono:

AS_PATH che elenca i sistemi autonomi attraverso i quali è passato

 l’annuncio del prefisso

NEXT-HOP: che riporta l’interfaccia del router che inizia l’AS_PATH e viene

 utilizzato per configurare le tabelle di inoltro dei router

Quando un router riceve un annuncio di rotta utilizza le proprie politiche di

importazione per decidere se accettare o filtrare la rotta.

Se esistono due o più percorsi verso lo stesso prefisso, BGP invoca in sequenza

delle regole fino ad arrivare ad un'unica possibilità:

1. Assegna alle rotte come attributo un valore di preferenza locale e

seleziona quelli con i valori più alti

2. Tra le rot