1.6 Panoramica della tecnologia Internet
2.2.2 Evoluzione delle strategie di routing in ARPANET
L’algoritmo di routing in ARPANET (poi Internet) si `e evoluto attraverso tre fasi, ciascuna delle quali ha goduto di un periodo di assestamento, durante il quale sembrava perfettamente adeguata. Successive evoluzioni nell’utiliz-zazione della rete rendevano tuttavia inadatta la soluzione, e forzavano una sua revisione che fosse compatibile con la precedente.
1a fase – Bellman-Ford con la lunghezza delle code
L’algoritmo di Bellman-Ford (1962) consente di calcolare presso ogni nodo della rete una tabella di routing locale, utilizzando informazioni su tutti i link della rete.
L’algoritmo `e ricorsivo: sia horigine il nodo locale per cui vogliamo cal-colare il miglior percorso lungo al pi`u i link verso il nodo hdest, avendo a disposizione i migliori percorsi lunghi al pi`u (i − 1) da horigine verso tutti gli altri nodi, con i relativi costi. Se non esistono cammini lunghi al pi`u (i − 1) per un certo nodo, al nodo viene associato un costo ∞. Questa informazione pu`o essere rappresentata con una matrice, ottenuta dall’iterazione preceden-te (v. tabella 2.3 per la tabella del nodo B, cio`e horigine= B al passo 2). Al primo passo (cio`e per i = 0), la matrice contiene solo ∞, salvo per la riga del nodo horigine stesso, con associato un costo 0.
Tabella 2.3Tabella di routing per il nodo B per cammini lunghi al pi`u 2
hdest cammino costo
A B-A 3
B B 0
C B-C 3
D B-D 2
E B-D-E 3
F B-C-F 8
Per ottenere la matrice per percorsi lunghi al pi`u i, per ciascuno nodo hdest della rete calcoleremo il miglior percorso Li[hdest].cammino lungo al pi`u i, ed il costo associato Li[hdest].costo. Otterremo questo calcolando, per ciascun nodo hintermedio della rete:
costo[hdest] = Li−1[hintermedio].costo + c(hintermedio, hdest)
dove la funzione c() indica la funzione che associa ad un arco il suo costo, infinito se l’arco non esiste (ad es. c(F, C) = 8 e c(B, E) = ∞). Trova-to il cosTrova-to[] minimo, quesTrova-to corrisponder`a ad un nodo intermedio ottimale hottimaleintermedio. Per concludere il minimo costo di un cammino lungo al pi`u i da horigine a hdest sar`a:
Li[hdest].costo = Li−1[hottimaleintermedio].costo + c(hottimaleintermedio, hdest)
ed il cammino corrispondente sar`a dato dalla giustapposizione del cammi-no dall’origine sicammi-no al cammi-nodo intermedio ottimale, pi`u l’arco dall’intermedio ottimale alla destinazione:
Li[hdest].cammino = Li−1[hottimaleintermedio].cammino + (hottimaleintermedio, hdest) L’iterazione prosegue sino a che la matrice resta inalterata. Allora siano certi di aver raggiunto un punto fisso, che corrisponde ad una soluzione del problema.
Il costo associato a ciascun link, nella prima versione del routing per ARPANET, `e la lunghezza della coda di spedizione sul link. Tuttavia la rapida variabilit`a di questa informazione tende a rendere instabile il routing.
2a fase – L’algoritmo di Dijkstra
La versione successiva utilizza l’algoritmo di Dijkstra(1959), e si basa sui tempi di comunicazione con i vicini. Questi vengono stimati misurando il tempo trascorso dalla spedizione di un messaggio di controllo, trasmesso a ciascun vicino a scadenze regolari, alla ricezione del riscontro dal destinatario.
Variazioni significative vengono comunicate in broadcast con un algoritmo di flooding, e portano alla modifica delle tabelle di routing.
Anche l’algoritmo di Dijkstra `e ricorsivo: si assume di avere a disposizio-ne gli i − 1 nodi pi`u vicini, in termini di costo, al nodo di partenza horigine, e si calcola l’i-esimo nodo pi`u vicino. Questa informazione pu`o essere memo-rizzata in una lista, ciascun elemento della quale contiene tre informazioni:
hdest, il nodo destinatario, cammino, il cammino per raggiungere la destina-zione, costo, il costo associato a quel cammino. La struttura ha la propriet`a di contenere solo cammini a costi minimi, ed inizialmente (i = 0) contiene solo un elemento con il nodo originario, a cui si associa il cammino vuoto, ed un costo nullo.
Per calcolare l’i-esimo elemento della struttura, si esaminano tutti i nodi della rete non raggiunti dai precedenti elementi della struttura, ma adiacen-ti a uno o pi`u di essi. Si ottengono cos`ı una serie di cammini del genere cammino(hintermedio) + (hintermedio, hdestinazione), dove cammino(hintermedio) `e gi`a contenuto in uno degli elementi della lista, e quindi ne `e noto il costo minimo, mentre hdestinazione non `e ancora raggiunto da nessun cammino nel-la lista. Di tutti i cammini ottenuti `e calconel-labile allora il costo, e tra tutti viene scelto quello di costo minimo, che costituir`a l’i-esimo elemento della struttura.
Algoritmo di routing
Filtro modifica
dei pesi
pesi utilizzati routing
pesi rilevati Sistema
Figura 2.6Un algoritmo di routing ed il feedback dalla rete
Si dimostra che il nodo raggiunto `e il pi`u vicino di quelli non ancora raggiunti (altrimenti i cammini nella lista non sarebbero i pi`u brevi), e quindi che il cammino ottenuto `e il minimo (altrimenti sarebbe gi`a stato raggiunto).
La prova dettagliata non rientra negli obiettivi del corso.
3a fase – Compensazione delle correzioni
L’aumento della velocit`a di comunicazione port`o ad un ulteriore problema, che `e tipico dei sistemi controllati da feedback.
Un sistema con feedback `e rappresentato in figura 2.6: il funzionamento, oltre ai dati provenienti dal nodo stesso, `e controllato anche da informazioni che arrivano dal sistema. Attraverso tali informazioni il nodo `e in grado di adattare il suo funzionamento allo stato del sistema. Poich´e lo stato del sistema a sua volta viene influenzato dal funzionamento del nodo, si instaura una interazione complessa tra i due. Se la reazione del nodo non `e adeguata, il sistema tende ad entrare in oscillazione, con comportamenti estremamente lontani dall’ottimalit`a.
Ci`o che accadde con la terza versione fu esattamente questo. Il fatto che l’intervallo tra le misurazioni dei ritardi fosse relativamente lungo (una deci-na di secondi) e che la risposta fosse invece istantanea port`o alla conseguenza che le correzioni apportate dall’algoritmo di routing venissero ad essere ec-cessive rispetto al comportamento ottimale. In breve, una diminuzione di performance di un certo link portava a preferirne uno alternativo,
scarican-do quello meno efficiente. L’osservazione successiva riportava una situazione opposta, ma amplificata: quello meno efficiente ora mostrava ottime presta-zione, mentre l’altro, sovraccaricato dalla modifica di routing, dava segni di congestione. Ci`o portava ad una modifica dei pesi ancora pi`u drastica, ed alla conseguente congestione dell’altro link. Una volta instaurata una alter-nanza di questo genere, il sistema si trovava in una situazione di persistente congestione.
Come in molti sistemi di controllo, la soluzione `e stata l’introduzione di ritardi e la diluizione delle correzioni. In questo modo il nodo `e in grado di sperimentare configurazioni intermedie, osservando la risposta del sistema.
In primo luogo, `e stata modificata la stima del “costo” di un singolo link:
la formula seguente incorpora sia la nozione di ritardo di comunicazione, sia quello di capacit`a del link. Infatti un link lento prossimo alla saturazione va distinto da un link ugualmente lento ma con la possibilit`a di gestire altro carico. Questa quantit`a `e detta di fattore di utilizzazione :
ρ= 2(Ts− T ) Ts− 2T
dove Ts `e il tempo di servizio stimato, dipendente solo dalla dimensione del pacchetto e dalla capacit`a della linea, mentre T `e il ritardo di comunicazione misurato, influenzato anche dai tempi di permanenza in coda.
Il fattore di utilizzazione impiegato per il calcolo del routing viene per`o mediato con quello utilizzato nell’intervallo precedente:
U(t) = ρ(t) + (k − 1)U(t − 1)
k (2.1)
cos`ı che vengono evitate variazioni repentine. Le variazioni sono tanto pi`u pigre quanto pi`u `e alto il valore della costante k, che viene determinata sperimentalmente.