WebLibrary Frame File Page 1

Capitolo 1. Algoritmi di forwarding e di routing

1.1. Per iniziare

1.1.1. Pre-requisiti

La fruzione ottimale di questo modulo richiede le seguenti conoscenze dibase:

il modello ISO OSI, con particolare riferimento al livello network

Può essere utile avere alcune conoscenze di un qualunque protocollo di rete dilivello network, ad esempio il protocollo IPv4.

1.1.2. Obiettivi

Al termine di questo modulo il partecipante avrà acquisito la conoscenza deiprincipali algoritmi di forwarding e di routing proposti in letteratura. Particolareenfasi saranno date alla differenza tra forwarding e routing, il routing by networkaddress, gli algoritmi di routing Distance Vector e Link State, quindi alleproblematiche di routing gerarchico e routing inter-dominio.

1.1.3. Struttura

Il modulo prevede i seguenti macroblocchi:

definizione di routing e forwarding

principali tecniche di forwarding (routing by network address, labelswapping, source routing)

principali algoritmi di routing (con particolare riferimento a DistanceVector e Link State)

scalabilità del routing e problematiche di routing gerarchico

routing inter-dominio e problematiche di policy

Il modulo comprenderà una sezione finale di domande ed esercizi perconsentire al partecipante di familiarizzare con i concetti esposti e verificare ilsuo grado di apprendimento.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Appunti dell'Ing. Fulvio Risso (http://netgroup.polito.it/teaching/trc/Routing.pdf)

WebLibrary Frame File Page 2

Mentre gli algoritmi di forwarding sono quelle che, a fronte di un pacchettoentrante in un nodo di rete, determinano qual è la migliore porta di uscita versola destinazione, gli algoritmi di routing sono quelle entità che instruiscono ogninodo ad agire in maniera coerente al fine della popolazione delle tabelle dirouting. Tra i primi ha un posto d'onore il routing by network address, nel qualela direzione di uscita viene determinata dall'indirizzo di destinazione delpacchetto, contenuto nel pacchetto stesso. Tra i secondi, invece, vanno ricordatigli algoritmi Distance Vector (ogni nodo invia tutte le informazioni che conosce aipropri vicini) e Link State (ogni nodo invia le informazioni relative ai propri vicinia tutti i nodi della rete). Il primo, molto più semplice, presenta dei problemi diconvergenza e di scalabilità; il secondo risolve questi problemi ma è molto piùcomplesso e necessita di meccanismi speciali per le reti di tipo broadcast.

Il routing gerarchico entra in gioco per risolvere i problemi di scalabilità dalmomento che su reti molto grosse neppure il Link State si rivela adeguato.Questo inserisce delle nuove regole di routing tra domini ed introduce nuoveproblematiche quali le aree partizionate. Le regole del routing gerarchico nonsono però sufficienti da un punto di vista dell'impiego su una rete molto grossacon gestori diversificati: in questo caso entrano in gioco anche problematiche dipolicy (ad esempio ammettere / disabilitare il passaggio di dati per alcunedestinazioni in un certo dominio), che vanno affrontate con algoritmi ad hoc.

1.2. Introduzione

1.2.1. Terminologia

Prima di addentrarsi all'interno della teoriadell'internetworking è utile precisare laterminologia che verrà utilizzata nel proseguo dalmomento che sono presenti nomi diversi per glistessi apparati in quanto ogni tecnologia (estandard) propone i propri. I nomi più diffusisono quelli derivati dal mondo OSI e quelliprovenienti dal mondo TCP/IP.

Nel sistema di riferimento OSI una rete dicalcolatori è un insieme di sistemi interconnessitra loro; questi sistemi seguono la seguenteterminologia:

System (oppure Node, Host, ecc.):generico dispositivo che contiene al suointerno almeno i livelli fisico, data link enetwork

End System (ES oppure End Node, DataTerminal Equipment, ecc): nodo “edge”, che agisce come mittente edestinatario finale dei dati

Intermediate System (IS oppure Router, ecc.): nodo “core”, che fornisce iltransito ai pacchetti tra la sorgente e la destinazione; solitamente nongenera dati e non è il destinatario finale dei dati (tranne nel caso di dati digestione della rete)

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.1.4. Sommario

WebLibrary Frame File Page 3

Le applicazioni che comunicano tra loroattraverso la rete risiedono negli ES, mentre gliIS svolgono funzioni di instradamento dei datigenerati dai primi. Gli IS hanno solitamente soloi livelli necessari alla funzione d’instradamento(Fisico, Data Link e Network) mentre gli ESimplementano tutti i livelli della pila OSI inquanto producono ed hanno la necessità diinterpretare correttamente i dati attraverso leapplicazioni.

In realtà anche il livello network èdiversamente sviluppato negli ES e negli IS: iprotocolli di routing (che sono una parte crucialedel livello network) non sono implementati negliES; viceversa, la necessità di realizzarefunzionalità di gestione (management) del routerrende necessaria la presenza negli IS anche diprotocolli specifici per la gestione, che sonocollocati nei livelli superiori al terzo.

Gli apparati reali hanno tuttavia una diversa composizione dei livelli OSIrispetto al modello ideale. Ad esempio gli end system IP sono contraddistinti dasoli 4 livelli, mentre esistono degli apparati di interconnessione (un po'particolari per la verità), i bridge, che sono contraddistinti dall'avere solamente ilivelli 1 e 2.

1.2.2. Il Livello Network

Il livello Network ha i seguenti compitifondamentali:

instradamento end-to-end dei messaggi suuna rete utilizzando un indirizzamentounivoco

localizzazione degli eventualiinstradamenti alternativi in caso di guasti

Un protocollo di livello network deve pertantoconoscere la topologia della rete, sceglieredi volta in volta il cammino migliore,eventualmente gestire il flusso dei dati e lecongestioni, infine gestire le problematichederivanti dalla presenza di più reti con tecnologiedi livello 1-2 diverse.

Il livello network è il primo livello in grado digarantire una connettività end-to-end a livello geografico; deve quindi essere ingrado di identificare univocamente ogni stazione sulla rete mediante unidentificativo apposito.

Il livello network è in grado di offrire sia servizi connessi (connectionoriented) che servizi non connessi (connectionless), dove i primi sonosolitamente implementati tramite circuiti virtuali. Le reti di estrazione"telefonica" (comprendendo in queste anche le tecnologie di reti dati propostedagli operatori di telefonia) sono forti sostenitori di questa filosofia, che èadottata nelle reti X.25, Frame Relay e ATM. La più famosa tecnologia conservizio di livello 3 non connesso è sicuramente il TCP/IP.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 4

Non tutte le tecnologie di rete rispettano ilposizionamento a livello previsto da OSI ed èfrequente trovare una disparità di collocamentodelle stesse funzioni tra il modello OSI e unacerta tecnologia. In particolare, anche se ilrouting è una funzionalià collocata da OSI nellivello network, alcune tecnologie di rete laimplementano in livelli diversi; in particolare,molte tecnologie di derivazione "telefonica"inseriscono le funzioni di instradamentoall'interno del livello 2. Ad esempio,l'instradamento viene realizzato a livello tre inX.25, DECnet, IP. Altre architetture preferisconoeffettuare l’instradamento a livello due, quali adesempio LAN estese attraverso bridge, FrameRelay, ATM e SMDS. Esiste infine una terzacategoria di reti in cui la distinzione tra i livellidue e tre non è cosi netta, questo perché gli IS,strumenti definiti dai comitati di livello due inrealtà svolgono poi funzioni tipicamente dellivello tre.

Nel seguito si farà riferimento al modello OSI classico e si assumerà quandonon diversamente specificato che il forwarding avvenga a livello network.

1.2.3. Forwarding e Routing

Per introdurre i concetti di Forwarding eRouting si presenta un esempio cheaccompagnerà le spiegazioni per tutto il presentemodulo.

Sia data una piccola rete autostradale, qualequella indicata in figura. La rete è composta distrade e punti di svincolo (i nodi tondi). Una reteautostradale efficiente dovrà anche includere uninsieme di informazioni di gestione cheserviranno al guidatore per scegliere il percorsoverso la destinazione. A questo proposito,esisterà un opportuno insieme di persone (i"segnastradisti") che, dialogando tra loro,saranno in grado di determinare i percorsi da unqualunque nodo verso qualunque località servitadalla rete. Il compito finale di queste personesarà quello di inserire in ogni nodo della retedegli opportuni cartelli di segnaletica, i qualicomprenderanno l'elenco di tutte le destinazioni e la direzione migliore daseguire per raggiungerle.

Questo processo è analogo a quello che una rete svolge a livello network eche configura la rete per recapitare correttamente tutti i dati a destinazione.Questo processo è detto routing ( instradamento ) e si occupa quindi di capirequali sono le destinazioni raggingibili, quindi far sì che tutti i nodi chepartecipano alla rete si accordino su un particolare algoritmo (ad esempio in basealla distanza minima tra due punti) che definisca univocamente i percorsi pergiungere a qualunque destinazione a partire da qualunque sorgente. Il risultatofinale del processo di routing è la creazione di una serie di informazioni locali (adesempio la tabella di routing in tecnologia IP) in ognuno dei nodi della rete, chealtro non è che un insieme di cartelli che specificano la direzione per ognipossibile destinazione.

Sia dato ora un automobilista che, presentandosi nel nodo E, vuole terminareil viaggio nel nodo B. Giunto nel nodo E, chiederà al responsabile dell'incrocio ladirezione da intraprendere per raggiungere B. Il responsabile dell'incrocio,sfruttando opportunamente le informazioni disseminate dai segnastradisti,indicherà allora all'automobilista la direzione opportuna verso B. Giunto nel nodosuccessivo (A) l'automobilista ripeterà nuovamente il procedimento, ossia

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.2.2.1. Livelli per l'instradamentoLeggere

WebLibrary Frame File Page 5

chiederà al responsabile dell'incrocio la direzione da prendere per giungere a B.Grazie al processo di disseminazione dei cartelli autostradali del puntoprecedente, l'automobilista non avrà alcun problema a giungere nel nododesiderato.

Questo processo è analogo al procedimentodi inoltro di un messaggio dati, il quale vienesmistato indipendentemente da ogni nodo in basead opportune informazioni contenute localmenteal nodo stesso (i cartelli autostradali). Questoprocesso è detto di forwarding ( inoltro ) e la suacaratteristica è quella di utilizzare le informazionidisseminate dal precedente processo di routing.In tecnologia IP, il processo di forwarding utilizzala tabella di routing per inoltrare i pacchetti versola destinazione.

Una caratteristica importante del processo diforwarding è la mancanza di conoscenza delpercorso globale. Le informazioni memorizzate inogni nodo, infatti, specificano banalmente ladirezione del prossimo passo ma non il percorsoglobale. Tuttavia questo non è un problema inquanto i dati verranno inoltrati nella direzioneopportuna nodo per nodo (il processo di routing ha già compiuto le operazioninecessarie a sincronizzare queste informazioni locali) e non è necessarioconoscere esattamente in anticipo tutto il percorso.

Ambedue i processi (routing e forwarding) sono necessari per l'operatività diuna rete. Tuttavia, mentre il secondo deve essere obbligatoriamente specificatoda ogni architettura di rete, il primo può essere demandato all'amministratore.In altre parole, una architettura di rete può non specificare un modo automaticodi disseminazione delle informazioni, ma lasciare all'amministratore della rete laresponsabilità di configurare appositamente ogni nodo (ad esempio medianteconfigurazione statica) per il processo di forwarding.

1.3. Tecniche di Forwarding

La letteratura presenta più tecniche diforwarding. Ogni architettura di rete sceglienormalmente una (o più) di queste tecniche e leadotta come preferenziali.

Le principali sono le seguenti:

Routing by Network Address

Label Swapping

Source Routing

Una possibile causa di confusione è data daltermine routing spesso presente nel nome diqueste tecniche nonostante queste sianosoluzioni di forwarding. Tuttavia, storicamente, iprocessi di routing e di forwarding non sono statidistinti a dovere, da cui questa imprecisione neinomi.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 6

Sia data la rete autostradale precedente. Sisupponga che i segnastradisti consegnino unfoglio con l'elenco di tutte le località raggiungibilisulla rete autostradale (e la relativa direzionemigliore per raggiungerle) al responsabile diincrocio. Costui, a fronte di un automobilistadesideroso di raggiungere una certa località,consulterà il proprio elenco alla ricerca dellalocalità desiderata, comunicando di conseguenzal'opportuna direzione da intraprendere. Questasoluzione richiede che in ogni incrocio siapresente un elenco che comprenderà tutte lelocalità raggiugibili e la relativa direzione daintraprendere per giungere a destinazione.L'automobilista non dovrà quindi conoscerealcunchè del percorso tranne ovviamente ladestinazione finale del viaggio: il percorso gliverrà comunicato volta per volta, da un incrocioall'altro.

Nella tecnica di forwarding by network address ogni pacchetto devecontenere l’indirizzo del nodo destinatario della comunicazione, la quale vieneusata come chiave di accesso alla tabella di routing. Ogni router sfoglia la suatabella di routing alla ricerca del percorso ottimale per quella destinazione, quindiinoltra il pacchetto secondo la regola trovata. Affinchè l'algoritmo funzioni ènecessario che l'indirizzo della destinazione sia univoco in maniera da non avereambiguità nella scelta del percorso.

Questa tecnica è molto semplice da implementare e non richiede inoltre unapreventiva fase di connessione: siccome l’indirizzo di destinazione è incluso inogni pacchetto trasmesso, non richiede la memorizzazione nei router diinformazioni di stato sul flusso dati. E’ quindi utilizzato tipicamente nei protocollinon connessi, quali ad esempio i bridge trasparenti, Decnet, IPX, IPv4 e IPv6,OSI CLNP.

Storicamente non si è identificata immediatamente con chiarezza ladifferenza tra forwarding e routing e questa tecnica è pertanto conosciuta piùspesso come routing by network address . Tuttavia, nel presente testo sipreferisce indicarla con il termine forwarding per maggiore chiarezza.

1.3.2. "Coloured Paths"

Si supponga una corsa automobilisticaall'interno della rete autostradale. A tutte lemacchine verrà dato uno speciale cartellinocolorato che identifica univocamente un percorso.Nel momento in cui una macchina si avvicina adun incrocio, un responsabile di corsa controllerà ilcartoncino colorato e, in base al colore, indicheràal concorrente la direzione in cui proseguire versola meta.

La tecnica Coloured Paths (che non èutilizzata in pratica, ma è necessaria perintrodurre il Label Swapping) segue un approccioduale rispetto alla prcedente. Mentre ilForwarding by Network Address identifica ladestinazione, qui la destinazione è sconosciuta equello che viene indicato all'interno del pacchettoè la strada da seguire. Per confrontare le duetecniche, possiamo immaginare due pellegrinimedioevali che, da Londra, si vogliano dirigere a Roma in pellegrinaggio: alprimo viene detto " Tu devi andare a Roma", mentre al secondo viene detto " Tudevi seguire la Via Francigena".

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

1.3.1. Forwarding by Network Address

WebLibrary Frame File Page 7

Questa dualità di approccio ha numerosi vantaggi (e altrettanti svantaggi,presentati successivamente): il principale è che con questa tecnica è possibiledefinire dei percorsi multipli verso la stessa destinazione, cosa che non è fattibilecon la precedente tecnica. Ad esempio (utilizzando la metafora del pellegrinoprecedente), è possibile definire due percorsi verso Roma, il primo che segue lacosta toscana da utilizzarsi esclusivamente d'inverno (quando le paludi nonerano infestate di zanzare), e il secondo che si inoltra nell'interno, da utilizzarsiquando il percorso costiero non è sufficientemente salubre. In generale, quindi,con questa tecnica è possibile definire percorsi multipli, anche contemporanei,sui quali differenziare tipologie di traffico diverse (ad esempio traffico real-timeda traffico dati classico), mentre il Forwarding by Network Address (che ha comeunico parametro di scelta la destinazione finale del pacchetto) non è in grado didifferenziare i percorsi.

Tuttavia, la tecnica Coloured Paths ha dei grossi problemi di scalabilità inriferimento all'identificazione dei percorsi, in quanto i percorsi disponibili in unarete crescono esponenzialmente con il numero di link presenti (i percorsi tra A eB potrebbero essere A-B, A-C-B, A-C-D-B, etc), richiedendo un numero moltogrosso. In seconda battuta, non è banale associare un identificativo ad un certopercorso e tenerne traccia facendo sì che tutti i nodi abbinino esattamentequell'identificativo a quel percorso. In terza battuta, nel momento in cui si rendedisponibile un nuovo percorso, è necessario localizzare un identificativo nuovo,non usato per nessun altro percorso.

Questi problemi di scalabilità fanno sì che questa tecnica (che viene peraltropresentata in questa trattazione solamente per facilitare la comprensione delLabel Swapping) non sia utilizzata, preferendo invece la tecnica del LabelSwapping che mantiene l'idea di base di identificare univocamente i percorsi, maadotta un meccanismo di identificazione basato su un vettore di identificativi(anzichè un identificativo unico per tutto il percorso), risolvendo i problemi discalabilità evidenziati poc'anzi.

La possibilità di definire esattamente i percorsi (quindi avere il pienocontrollo su di essi in termini di nodi attraversati, risorse disponibili, ecc.) fa sìche questa idea sia usata in particolare dalle tecnologie di derivazione Telco, dalmomento che queste sono storicamente molto sensibili alle problematiche diqualità e di garanzia del servizio.

1.3.3. Label Swapping

Si supponga una corsa automobilisticaall'interno della rete autostradale. A tutte lemacchine verrà dato uno speciale cartellinocolorato, da usarsi non appena ci si trovi in unincrocio. Ad ogni incrocio vi sarà un responsabiledi corsa che controllerà il cartoncino colorato e,in base al colore, indicherà al concorrente ladirezione del prossimo incrocio. In aggiunta,consegnerà alla vettura un nuovo cartoncinocolorato, da utilizzarsi in quella sede.

La metafora precedente permette diintrodurre la tecnica Label Swapping, checonsiste nell'inserimento di una particolareinformazione detta “label” (etichetta) all’internodi ogni pacchetto in transito, la qualecontribuisce ad identificare univocamente ilpercorso che verrà effettuato dal pacchetto.Tuttavia, a differenza della tecnica precedente,l'etichetta non viene mantenuta costante su tutto il percorso, ma può variare ditratta in tratta. Il percorso non verrà più identificato con un codice univoco, mada un vettore di identificativi la cui lunghezza è pari al numero di link presentinel percorso. Ad esempio, il percorso tra il nodo D e il nodo C (in figura) verràidentificato dal vettore {(P2-azzurro), (P4-giallo)}. E' da notare che questovettore contiene anche l'indicazione della porta di uscita dal nodo stesso, oltre

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere

WebLibrary Frame File Page 8

all'etichetta presente nel pacchetto; la necessità di questa ulteriore informazionesarà maggiormente chiara in seguito.

In riferimento alla figura, quando il nodo A riceve un pacchetto azzurro loinoltra sulla porta P2 mantenendo lo stesso colore. Lo stesso fa il nodo B,seguendo le indicazioni della sua routing table che dice che un pacchetto azzurroricevuto sulla porta P1 deve essere inoltrato sulla porta P4, mantenendo il coloreazzurro e permettendone quindi il recapito al nodo destinazione C. L’etichetta delpacchetto entrante (insieme alla porta di ingresso) verrà quindi usata comechiave per determinare l’instradamento del pacchetto stesso. La stessaprocedura viene adottata nel momento in cui il nodo D riceve un pacchettoazzurro. Anche in questo caso il nodo D lo inoltra sulla porta P2 mantenendo lostesso colore, così come specificato nella sua routing table. Questo stessopacchetto viene quindi ricevuto dal nodo B sulla porta P3: in base alla routingtable presente su questo nodo, un pacchetto azzurro ricevuto sulla porta P3 deveessere inoltrato sulla porta P4, ma cambiandogli il colore in giallo.

Diventa quindi evidente come il nodo C sia perfettamente in grado didistinguere i pacchetti proventienti dalle due sorgenti: i primi arriverannocolorati di azzurro, i secondi di giallo. Si noti tuttavia che in ambedue i casi ipacchetti sono partiti colorati di azzurro: tuttavia questo non causa ambiguità inquanto vengono inoltrati su link diversi; ad esempio il nodo B è perfettamente ingrado di discriminare tra i pacchetti della prima sessione e quelli della secondasessione dal momento che vengono ricevuti da due porte diverse (P1 e P3).

Si supponga ora che una terza sessione preveda l'inoltro di pacchetti entrantisul nodo A e diretti al nodo D. I pacchetti dovranno giungere con un coloredifferente all'azzurro (già in uso su quel link per la prima sessione), ad esempiorosso. Il nodo A, secondo la sua routing table, inoltrerà i pacchetti rossi sullaporta P2, mantenendone il colore rosso. Una volta giunti a B, questo nodo potràinoltrare i pacchetti rossi ricevuti dalla porta P1 sulla porta P2, cambiando colorein azzurro e recapitandoli quindi alla destinazione. Si noti che anche in questocaso non si verificano ambiguità nell'assegnazione del colore azzurro a questasessione su quest'ultima tratta: infatti la precedente sessione azzurra insistevasulla porta P4 e pertanto i pacchetti della nuova sessione (che insiste sulla portaP2) non possono essere confusi con quelli precedenti.

La tecnica Label Swapping realizza quindil'idea dell'indentificazione del percorso inmaniera decisamente più efficiente della tecnica"Coloured Paths". Infatti, il numero di etichettenecessarie (i "colori" dell'esempio) è pari almassimo numero di sessioni distinte cheinsistono su un link, dal momento che leetichette si possono riciclare su link diversi. Adesempio, la tecnologia ATM (che adotta questatecnica di instradamento) prevede un numero di24 bit (pari a 16 milioni di combinazioni) perl'identificazione delle connessioni, ed è unnumero ampiamente sufficiente e decisamentepiù ridotto rispetto allo spazio necessario peridentificare univocamente ogni destinazione (adesempio, una tecnologia basata sul forwarding byNetwork Address quale IPv6 utilizza 128 bit perl'identificazione di ogni destinazione). In secondoluogo, la decisione di quale colore utilizzare èpuramente locale al nodo: in presenza di unanuova sessione insistente su un certo link, un nodo può scegliere comeidentificativo un qualunque numero non in uso sul link stesso, informazione che èovviamente conosciuta dal nodo stesso. Ad esempio, all'arrivo della terzasessione il nodo B dovrà semplicemente controllare le etichette già in uso sul linkdi uscita utilizzato dalla sessione e sceglierne una libera, senza nessunainterazione con il nodo successivo.

La scelta puramente locale non è piàù possibile in caso di link broadcast inquanto il nodo all'altra estremità del link potrebbe vedersi recapitare duepacchetti con lo stesso colore originati da due nodi differenti sullo stesso link.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 9

Tuttavia, questa tecnica è poco utilizzata su link broadcast in quanto questi linkhanno difficoltà a fornire garanzie di servizio, che sono uno dei motivi di utilizzodel Label Swapping; in ogni caso la soluzione sarebbe relativamente banale,richiedendo semplicemente una interazione del nodo a monte con il nodo a valleper decidere l'etichetta.

Nel caso di Label Swapping non è necessario indicare in ogni pacchetto dati ilmittente dello stesso: infatti il percorso è univocamente determinario dalla fasedi preparazione del percorso, rendendo inutile questa informazione nei pacchettidati (invece richiesta nel forwarding by network address).

La tecnica Label Swapping è usataprevalentemente in tecnologie di derivazioneTelco quali X.25, Frame Relay, ATM; le eccezionialle "tecnologie di derivazione telefonica" sonoAPPN, nel mondo IBM, dove le problematiche digarazia e qualità del servizio sono tenute ingrande considerazione (e per le quali il percorsoviene dinamicamente scelto in base alle esigenzedella sessione dati) e MPLS, una tecnologia nataa metà tra il mondo IP e quello ATM, la qualedeve affrontare non solo il problema dielevatissime velocità di commutazione per lequali il label swapping è decisamente più adattorispetto al routing by network address, ma anchele nuove esigenze di qualità del servizio e diutilizzo di percorsi multipli per la stessadestinazione.

1.3.3.1. Path Setup

Prima dell'inizio della corsa, tuttavia, ènecessario che un commissario di gara provi ilpercorso, istruendo opportunamente iresponsabili di corsa a distribuire i cartoncinicolorati in maniera appropriata.

L'esempio introduce un grosso problemadelle reti di tipo Label Swapping: il percorso (equindi la preparazione dello swapping delleetichette, ossia della forwarding table) deveessere in qualche modo deciso a priori, primadell'inizio del traffico dati.

Vi sono due modalità di creazione dellaforwarding table: manuale e on-demand. Nellaprima modalità, i percorsi sono staticamenteallocati dal gestore della rete (via management).Il vantaggio è la notevole semplicità dei nodi(l'operazione di allocazione dei percorsi è fattaoccasionalmente, quindi non sono necessari meccanismi particolarmenteottimizzati ed efficienti), a scapito della flessibilità: non è possibile richiederedinamicamente l'allocazione di un percorso per esigenze specifiche a meno dipassare attraverso il gestore della rete.

Nella seconda modalità, i percorsi vengono instaurati on-demand, senzal'intermediazione del gestore di rete. In questo caso è necessarial'implementazione di nuovi protocolli di segnalazione lato utente provocandoun'aumento della complessità dei nodi a causa dell'implementazione di nuoviprotocolli e dell'allocazione dinamica dei percorsi. Ad esempio, molti apparati direte avevano enormi capacità di commutazione ma erano estremamente lentinelle operazioni di path setup con la conseguenza che entravano in crisi inpresenza di molte richieste di allocazione dei percorsi, situazione che si verificain presenza di sessioni corte, ognuna con un path setup distinto. In secondo

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere

WebLibrary Frame File Page 10

luogo, i messaggi di path-setup non possono essere inoltrati con la tecnica label-swapping, dal momento che sono loro stessi a dover creare il percorso. In questocaso è pertanto necessario affiancare, alla commutazione Label Swapping, anchel'instradamento di tipo Forwarding by Network Address (spesso su un circuitodedicato, ossia utilizzando una apposita etichetta riservata alla segnalazione) contutte le problematiche del caso dal momento che nella rete devono convivere duemeccanismi di instradamento: uno per i dati tradizionali, uno per lasegnalazione.

La tecnica Label Swapping è generalmente usata nei protocolli connessi inquanto ad ogni nuova sessione è necessario creare il percorso della stessaall’interno della rete e preparare le opportune tabelle di commutazione delleetichette in ogni nodo prima di poter inviare i dati. Per inciso, le tecnologiederivate dall’ambiente telefonico sono le più adatte a questa tecnica diinstradamento poiché prevedono normalmente una fase di connessione primadell’invio dei dati.

1.3.4. Source Routing

La tecnica di instradamento Source Routingdelega tutta la complessità dell’instradamentoall’ES il quale deve conoscere, all’atto dellegenerazione del pacchetto, quale sarà il percorsoche questo dovrà seguire per poter giungere adestinazione. Nel pacchetto dovrà quindi esserepresente un insieme di campi con l’elenco di tuttigli IS che dovranno essere attraversati. Quando ilpacchetto verrà ricevuto da un IS questoprovvederà semplicemente ad inoltrarlo al nodosuccessivo in base alla lista di nodi memorizzatanel pacchetto.

I sistemi devono quindi mantenere a bordouna tabella di instradamento contenente ledestinazioni con cui sono interessati acomunicare e che richiedono l'attraversamento dibridge. Le entry di tali tabelle vengonosolitamente calcolate in automatico tramite unprocesso di route discovery. Questo processo permette ad esempio al sistemamittente di scoprire dinamicamente il percorso per raggiungere il sistemadestinatario utilizzando dei pacchetti di esplorazione della rete.

La complessità di questa tecnica è prevalentemente delegata agli ES, mentrel'intelligenza richiesta agli IS è decisamente limitata. Questa tecnica è usatanormalmente nelle tecnologie di provenienza dal mondo IBM, ad esempio neibridge source-routing e in APPN+/HPR.

Anche se questa tecnica è scarsamente utilizzata, esistono alcune occasioniin cui la possibilità di forzare un pacchetto a seguire un certo percorso puòessere comoda (ad esempio per scegliere un percorso di uscita differente rispettoa quello standard). Per questo motivo anche tecnologie quali IPv4 e IPv6 che nelnormale funzionamento adottano il forwarding by network address, prevedonouna modalità di funzionamento di tipo Source Routing, attivabile opzionalmente.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 11

La tecnica a più larga diffusione è sicuramentel’instradamento di tipo forwarding by networkaddress in quanto permette la costruzione di ESmolto semplici (non devono conoscere nulla dicome si svolgerà il routing), e anche gli IS sonoragionevolmente semplici in quanto nonrichiedono la memorizzazione di stato persessione, oltre al fatto per cui non viene richiestaalcuna fase di setup eliminando così un notevolefattore di complessità. Tuttavia, le tabelle dirouting possono essere molto grosse (dovrannoessere memorizzate tutte le destinazioni presentisulla rete, a meno che la rete non sia organizzatagerarchicamente), ogni pacchetto dovràcontenere l'indicazione del nodo mittente e diquello destinatario (occupando parecchio spazionell'header), è difficile fornire garanzie di servizio(non esiste un modo per capire le capacità delpercorso in termini qualitativi), e non possonoessere gestiti percorsi multipli verso una stessadestinazione.

Il Label Swapping , d’altro canto, è una tecnica più complessa, ma confunzionalità decisamente più evolute. Un primo vantaggio è la scalabilità dellatabella di routing grazie alla lunghezza ridotta: vengono memorizzate solo leconnessioni attraversanti il nodo, mentre con il forwarding by network addressdevono essere memorizzate tutte le destinazioni esistenti sulla rete. Questatecnica quindi velocizza il processo di forwarding in quanto il lookup nella tabelladi instradamento avviene su un numero limitato di informazioni e può esserequindi più veloce. Un secondo vantaggio è la compattezza dell'header deipacchetti, in quanto il numero di bit necessari per trasportare l'informazioneneecessaria al processo di instradamento all'interno dei pacchetti stessi è ridotto(è sufficiente il campo label, di dimensione limitata, contro i campi sourceaddress e destination address del forwarding by network address). Inoltre ilLabel Swapping permette percorsi multipli verso una stessa destinazione (checonsentono di distribuire il traffico su più percorsi a seconda delle lorocaratteristiche) e, grazie alla fase di path setup, è possibile gestire i percorsianche in base alle loro caratteristiche di qualità dal momento che è facileintegrare nella segnalazione del percorso anche parametri di tipo qualitativo. Inparticolare, il path setup può essere realizzato in modo da verificare ladisponibilità di risorse sul percorso e di offrire quindi determinate garanzie diservizio al flusso dati richiedente, operazione impossibile con il forwarding bynetwork address.

La contropartita di queste capacità è una notevole complessità, a vari livelli.Ad esempio, la gestione della qualità del servizio richiede, oltre ad un opportunopath setup, anche la gestione di informazioni di stato in ogni nodo (ad esempioper controllare se la sessione rispetta o meno i parametri di banda dichiarati)che appesantiscono notevolmente il nodo stesso. In secondo luogo, la gestionedel path setup (quando non viene utilizzato un meccanismo di gestione manualedei percorsi) richiede la definizione sia di protocolli ad hoc, sia l'implementazionedi un secondo meccanismo di instradamento specifico per i pacchetti disegnalazione. Inoltre, la gestione dei messaggi di path setup appesantiscel'operatività degli IS ed è critico in particolar modo in presenza di sessioni ditraffico corte, in quanto forza la rete a preparare un percorso (con laconseguente complessità) anche nel caso in cui l'ammontare dei dati scambiatisia estremamente ridotto.

Le moderne tecnologie basate sul Label Swapping tendono quindi a limitarel'ammontare di messaggi di path setup definendo sessioni lunghe (ad esempioMPLS non contempla più l'apertura di un nuovo percorso per ogni singolasessione TCP, cosa che era invece prevista in ATM) e limitando gran parte deiproblemi sopra enunciati.

Il source routing è generalmente considerato poco efficiente in quantoobbliga gli ES a conoscere tutto il percorso del pacchetto. Questo è attualmenteritenuto poco opportuno in quanto gli ES dovrebbero prevalentemente curarel’aspetto applicativo (eseguire applicazioni, gestire l’interazione con gli utenti)

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.3.5. ConfrontoLeggere

WebLibrary Frame File Page 12

anziché conoscere gli aspetti interni di una rete. Nel modello source routing,quindi, gran parte della complessità è delegata agli ES, mentre nelle duetecnologie precedenti c’è un maggior equilibrio di responsabilità tra gli ES e gliIS.

Questa idea di separazione delle responsabilità è relativamente recente. Adesempio il protocollo IP, pur essendo di tipo forwarding by network address,mantiene una particolare opzione per il supporto del source routing in quantopuò essere in effetti utile in casi particolari, ad esempio quando un ES si trovi adiscriminare tra due strade e, deliberatamente, decida di scegliere una delle due.

La tecnologia dominante in questo momento è il forwarding by networkaddress; il label swapping è utilizzato soprattutto in tecnologie dati provenientida un ambito telefonico, mentre il source routing è attualmente utilizzatosolamente in casi particolari.

1.4. Algoritmi di routing

Le successive Sezioni presenteranno i principali algoritmi di routing esistentiin letteratura. Il lettore potrà spesso trovare un apparente scollamento tra quelloche viene presentato, e come funzionano i protocolli di routing moderni. Questoscollamento è derivato dal fatto che gli algoritmi tendono a non occuparsi di unanotevole serie di problematiche pratiche: ad esempio per gli algoritmiesisteranno delle destinazioni da raggiungere, mentre la pratica insegna chequeste potranno essere delle macchine utente (ES), oppure delle reti, e viadicendo.

Lo scopo di queste sezioni sarà quindi la presentazione degli algoritmi dalpunto di vista teorico, mentre il passaggio alle problematiche reali verràeffettuato nell'apposito modulo dedicato ai protocolli di routing.

1.4.1. Caratteristiche generali

Un algoritmo di routing è un processo che, inautomatico, è in grado di procedere alladisseminazione delle informazioni di routing inuna rete. Anche se gli algoritmi di routing sonoformalmente indipendenti dagli algoritmi diforwarding, in pratica tutti gli algoritmi di routingche verranno presentati suppongono unmeccanismo di inoltro del tipo forwarding bynetwork address che è quello in assoluto piùdiffuso sulle reti dati moderne. Gli algoritmidevono pertanto essere in grado di riconoscerel'elenco delle località raggiungibili, quindi inserirein ogni nodo le informazioni necessarie apermettere il processo di forwarding verso taledestinazione.

L'operazione di disseminazione deve averesostanzialmente una caratteristica di coerenza inmodo che due nodi non prendano decisionicontrapposte per quanto riguarda l'invio di dati verso una certa destinazione. Lamancanza di coerenza è deleteria in quanto può dare origine a fenomeni di loop(un pacchetto viene rimpallato ciclicamente su un insisme di più nodi), buchi neri(un pacchetto viene ricevuto da un nodo che non sa in che direzione instradarlo,perciò lo scarta) e altro ancora.

Oltre ad essere in grado di recapitare i dati a destinazione, una caratteristicaimportante di un algoritmo di routing è il riuscire a contemplare dellecaratteristiche di ottimalità nel calcolo del percorso. La scelta di un particolarepercorso non dovrà essere casuale, ma dovrà essere derivato da un determinatoalgoritmo il quale, in presenza di più percorsi possibili, sia in grado dideterminare quale è il percorso "più buono" secondo una certa metrica diriferimento.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

VIDEO: Routing Overview

WebLibrary Frame File Page 13

La metrica di riferimento è un parametro chepuò essere deciso dall'utente in completa libertà.Una metrica potrebbe essere la minimizzazionedel tempo medio di recapito di un pacchetto, lascelta del percorso più breve in termini di ISattraversati, oppure del percorso a bandamaggiore, e altro ancora. Il risultato finale delcomputo della metrica sarà il costo , un numeroche esprime la bontà (o meno) della soluzionetrovata. Il confronto di percorsi alternativi verràfatto in base al costo, portando a preferire ilpercorso a costo (secondo quella determinatametrica) minore.

I criteri con cui calcolare il costo possonoessere anche più di uno (ad esempio saràpossibile considerare il ritardo medio comecontribuente al 75% del costo globale, mentre ilrestante 25% sarà dato dalla distanza tra le duedestinazioni) e addirittura possono essere contrastanti (quali ad esempiominimizzare il ritardo medio di ogni pacchetto e contemporaneamentemassimizzare l'utilizzo delle linee, in quanto il primo si realizza minimizzando ivalori di riempimento delle code negli IS, mentre il secondo si ottienemassimizzando lo stesso parametro).

L'ottimalità, tuttavia, implica delle problematiche di complessità. Ad esempionon è detto che un algoritmo che tenga conto di più metriche contemporanee siaintrisecamente migliore di un algoritmo a metrica unica: la semplicità delsecondo potrebbe rendere il debugging più veloce, mentre i vantaggi di metrichemultiple potrebbero passare inosservati in pratica. Inoltre algoritmi troppocomplicati potrebbero richiedere tempi di calcolo inaccettabili, oppure averenecessità di risorse di memoria troppo elevate per un utilizzo in campo. A questosi deve aggiungere il fatto che solitamente gli algoritmi tendono ad aumentare lerichieste di risorse (memoria, CPU) con l'aumentare del numero di nodi collegati,ossia in base alle dimensioni della rete per cui si sta calcolando il routing. Untipico esempio di problema irrisolvibile con algoritmi ottimi che si trova inletteratura è quello del Commesso Viaggiatore (individuare il percorso miglioreche tocchi, in seguenza, tutti i nodi della rete) che è NP-Hard, e quindiintrattabile all'aumentare delle dimensioni della rete.

Le principali metriche adottate contemplano la minimizzazione del ritardo diogni pacchetto e la minimizzazione del costo di trasferimento (che può essereinteso sia in modo da evitare l’invio di pacchetti su link particolarmentedispendiosi quali quelli satellitari, sia di costruire il percorso più breve in modo daevitare lunghi percorsi del pacchetto sulla rete). Una metrica molto semplice puòessere il numero di IS attraversati: un percorso con 5 IS verrà consideratomigliore di uno con 6 IS indipendentemente dal fatto che, ad esempio, il primopercorso sia realizzato con link molto lenti e il secondo con collegamenti moltoveloci.

Metriche che tengano in considerazione il carico della rete sono più difficili damettere a punto, in quanto portano facilmente a situazioni di routing instabile. Letecniche più moderne consentono al più di operare un load balancing(bilanciamento del traffico) tra cammini paralleli.

La capacità di recapitare i pacchetti non implica automaticamente unaconoscenza dettagliata della topologia di rete: si vedrà successivamente come laprecisa conoscenza topologica sia un parametro spesso non richiesto ad unalgoritmo di routing.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 14

Un algoritmo di routing dovrebbe presentare leseguenti caratteristiche:

Semplicità: sia in riferimentoall'implementazione (semplicità implicameno possibilità di bachi), sia inriferimento all'utilizzo, in quanto gli IShanno CPU e memoria finite e devonoimpiegare la maggior parte del loro tempoa instradare pacchetti, non a calcolarenuove tabelle di instradamento

Robustezza ed Adattabilità: l'algoritmodeve funzionare su una topologia di retegenerica e non deve porre alcun vincolosulla stessa; inoltre l'algoritmo devesupportare cambiamenti di topologia senzainterrompere il funzionamento della rete;questo comprende caratteristiche di:

Fault Detection: l'algoritmo deveessere in grado di accorgersi della presenza di guasti isolandoliautomaticamente. Ad esempio un algoritmo che si affida ad unsegnale esterno (ad es. il link-up di un collegamento punto-punto)per determinare se la linea è attiva, non soddisfa al criterio delFault Detection

Autostabilizzazione: la rete deve essere in grado di convergere ainuovi percorsi di instradamento (se questi esistono) in un tempofinito senza alcun intervento esterno sulla rete (ad esempio dimanagement); l’autostabilizzazione si riferisce sia al caso in cui larete debba riconvergere a causa di un guasto, sia al caso in cuivengano aggiunti dei nuovi percorsi (aggiunta di reti, nuovi link, ...)

Robustezza Bizantina [1]: l’algoritmo deve essere in grado diaccorgersi di eventuali funzionamenti anomali dei nodi, ad esempionel caso in cui un nodo guasto propaghi delle informazioniincorrette sullo stato della rete, e ignorare tali informazioni. Lacomplicazione di questa caratteristica è la necessità di individuareun nodo che sta inviando informazioni incorrette quando questo haun comportamento del tutto regolare (le informazioni emesse sonodel tutto legittime) ma sono errate dal punto di vista topologico.Questo caso può verificarsi ad esempio qualora un hacker prendapossesso di un IS e lo forzi ad annunciare destinazioni o percorsiinesistenti

Ottimalità: nella scelta dei cammini, rispetto alle metriche prescelte;

Stabilità: la rete deve raggiungere, a regime, uno stato stabile nel qualeil routing non deve più cambiare a meno che si verifichino delle variazionidei costi o della topologia.

Equità: non devono esistere nodi “trascurati” o “danneggiati” dalla sceltadei percorsi di instradamento

Queste caratteristiche non sono sempre presenti negli algoritmi reali inquanto in determinati casi si preferisce enfatizzare una certa serie dicaratteristiche a fronte di altre. In particolare la robustezza bizantina non ègarantita dagli algoritmi attuali.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.1.1. Caratteristiche di un algoritmo

WebLibrary Frame File Page 15

Un algoritmo, supposto ideale, non contemplaalcune problematiche pratiche quali il ritardo nelconoscere una variazione di topologia, e altro. Adesempio i nodi su una rete reale non sono ingrado di accorgersi istantaneamente della messafuori servizio di un link in quanto questainformazione deve essere propagata in tempifiniti. Questo causa, per brevi intervalli, unamancanza di coerenza delle informazioni: alcuniIS avranno la conoscenza della rete secondo latopologia aggiornata, mentre altri manterrannoancora le informazioni secondo la topologiavecchia.

Questi fenomeni causano un disallineamentodelle informazioni degli IS all'interno dei periodidi transitorio, ossia i periodi necessari alla reteper tornare alla stabilità. I fenomeni più tipici chepossono accadere in questi casi in alcune partidella rete sono:

Black Hole: i pacchetti verso una datadestinazione sono inviati ad un IS il quale,non disponendo di un percorso (route) perla destinazione, li scarta

Routing Loop : alcune route innescano unpercorso circolare ed è anche conosciutocome Bouncing Effect in riferimento aipacchetti, che vengono rimbalzaticiclicamente all'interno del percorsocircolare. I loop sono ancora più pericolosidei black hole perché i pacchetti all’internodel loop circolano all’interno della retefinché non sono scartati per eccessivo“time to live”; una situazione di questotipo può portare al progressivointasamento della rete.

Il secondo problema è particolarmente grave in quanto può inficiare anche iltraffico che sarebbe portato regolarmente a destinazione dalla rete. Ad esempio,(in figura) la rete non ha problemi a trasportare traffico tra i nodi A e C.Tuttavia, a causa del routing loop tra A e B in riferimento alla destinazione D, ipacchetti destinati a D intaseranno il link rendendo problematico il recapito ditutto il traffico tra A e B, quindi anche del traffico destinato ad esempio a C. Perquesto spesso si tende a preferire un allugamento della durata del trasitorio afronte della garanzia di non generare un routing loop. Un transitorio più lungo(senza routing loop) rende peggiore il servizio per un sottoinsieme didestinazioni, mentre un transitorio più corto (ma con routing loop) può farsperimentare disservizi anche ad altre destinazioni altrimenti non toccate dalproblema.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.1.2. Problematiche di transitorio

WebLibrary Frame File Page 16

Gli algoritmi di routing si dividono in due grossigruppi:

Algoritmi non adattativi (ostatici): algoritmi che non si adattano allostato della rete in quanto utilizzano deicriteri fissi di instradamento; questo nonvuol dire che non siano in grado direcapitare correttamente i dati adestinazione, quanto che ogni IS utilizzasempre la stessa tabella di instradamentoqualunque sia la topologia e i costi dellarete

Algoritmi adattativi (o dinamici):algoritmi nei quali le tabelle diinstradamento vengono calcolate infunzione della topologia della rete e dellostato dei link; differiscono principalmenteper la modalità con cui le route sonocalcolate all’interno della rete; questa categoria comprende al suo internol'importante classe degli algoritmi di routing distribuito , alla base delrouting sulle principali reti moderne

Algoritmi gerarchici: è una categoria a parte rispetto alle precedenti inquanto affronta il problema della scalabilità del routing su grosse retiattraverso il partizionamento della rete in domini più piccoli e inserisceopportune regole di scambio di dati tra questi domini.

1.4.2.1. Routing e Backup

E' interessante notare come, soprattutto pergli algoritmi più in uso (particolarmente per ilrouting distribuito) non esista il concetto di routedi backup, tanto caro in determinate tecnologie(ad esempio l'organizzazione interna della retetelefonica). Infatti, differentemente da qeusteultime, gli algoritmi maggiormente in uso sullarete dati sono altamente dinamici e, in base aduna determinata configurazione di rete, sono ingrado di calcolare i percorsi di instradamentoottimali. A fronte di un cambiamento nellatopologia della rete (che equivale sia ad unqualunque guasto, sia anche all'inserimento nellarete di una destinazione prima non esistente)l'algoritmo calcolerà i nuovi percorsi diinstradamento, e così via. La route di backup,quindi, non ha senso di esistere grazie alladinamicità dell'algoritmo: ogni configurazione direte ha una sua peculiare forma dei percorsi diinstradamento; quando la rete cambia, i percorsiverranno ricavati di conseguenza.

Le route di backup possono invece essere utilizzate in algoritmi di tipo staticodove è necessario prevedere, a fronte di un qualunque guasto, il percorsoalternativo. Le reti dati moderne, caratterizzate da largo impiego di tecnologiedistribuite, difficilmente hanno il concetto di route di backup.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.2. Classificazione

Page 17

Il fixed directory routing (più solitamenteindicato come routing statico) appartiene allacategoria degli algoritmi non adattativi in quantonon è in grado di modificare i percorsi a fronte diun guasto (non garantisce fault-detection eautostabilizzazione, oltre che robustezzabizantina). Il pregio è tuttavia l’enormesemplicità in quanto il routing consiste in unatabella, definita staticamente dal gestore dell’ISattraverso un'operazione di management, cheindica quale è il prossimo passo per raggiungerela destinazione in esame. Il gestore ha il totalecontrollo dei percorsi del traffico sulla rete, ma ènecessario un suo intervento manuale per il lororeinstradamento in presenza di variazionitopologiche.

Il fixed directory ruoting è poco adatto adambienti con alta variazione delle route, quali adesempio le reti di backbone in cui sono frequenti le variazioni topologiche.Infatti, in caso di guasti è necessario un intervento manuale del gestore perridirigere il traffico; in alcune implementazioni, il problema della redirezione deltraffico può essere parzialmente risolto adottando tabelle di priorità che dianopiù scelte in caso di guasto ( route di backup ). Viceversa, in un ambiente pocodinamico (quali ad esempio le reti periferiche) questo algoritmo può essere unabuona scelta; inoltre questa tecnica ha il vantaggio di non generare traffico dirouting: i router non scambiano l'un l'altro alcuna informazione, lasciando ai datil'intera banda trasmissiva a disposizione.

Questa tecnica è usata con successo in reti TCP/IP e SNA, specialmente perreti non magliate e di piccole dimensioni. Infatti, la gestione manuale delletabelle di routing è molto complessa e difficoltosa, soprattutto per reti di grandidimensioni per le quali risulta del tutto impraticabile. Tuttavia, questo algoritmoè quello che consente la massima flessibilità di configurazione in quantopermette il migliore controllo sulle impostazioni di routing.

1.4.3.1. Routing Statico e Dinamico

Tra gli algoritmi non adattativi, il FixedDirectory Routing è sicuramente il più utilizzatoe, nonostante gli apparenti difetti, esistonoparecchie occasioni in cui si rivela una buonascelta. Ad esempio, esistono molte reti cheutilizzano il routing statico nella periferia e ilrouting dinamico nella zona di backbone. Infatti,come evidenziato in figura, se per sfruttare almeglio le magliature della rete è necessarioavere algoritmi di routing dinamici nella parteinterna della rete, il routing statico può risultarepiù semplice e non presentare particolarisvantaggi nelle zone più periferiche della rete.Inoltre, queste hanno solitamente topologia adalbero, ovvero esiste un solo cammino che leinterconnette al resto della rete, per cui l'utilizzodi routing dinamico non porta a grossi vantaggi inquanto quella è l'unica direzione possibile perpoter raggiungere il "resto del mondo".

Il routing dinamico invece è più adatto in zone dove la variabilità delle routeè più elevata.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.3. Fixed Directory Routing

SNA: Systems Network Architecture, protocollo di IBM®

VIDEO: Routing Centralizzato - Flooding - Isolato

Page 18

Il flooding è un altro algoritmo non adattativo, incui ciascun pacchetto in arrivo viene ritrasmessosu tutte le linee eccetto quella su cui è statoricevuto. Concepito su reti militari a prova disabotaggio, se realizzato nel modo sopradescritto massimizza la probabilità che ilpacchetto arrivi a destinazione (purchè esista unqualunque percorso disponibile), ma induce uncarico elevatissimo sulla rete. L'algoritmofunziona se i pacchetti sono dotati di un TTL chene limita la vita massima, altrimenti il carico puòdiventare infinito a fronte di un solo pacchettoimmesso nella rete.

Il Flooding, pur essendo non adattativo (unnodo non cambia il suo comportamento a frontedi variazioni di rete), ha caratteristiche dirobustezza che mancano al Fixed DirectoryRouting. Infatti questo algoritmo è in grado direcapitare correttamente il pacchetto a destinazione anche a fronte di variazioninella rete in quanto il pacchetto, prima o poi, giungerà a destinazione grazie alleinnumerevoli copie che di esso girano in rete. Ovviamente, è altamente probabileche il pacchetto giunga alla destinazione in molte copie identiche, da cui il fattoche la destinazione deve essere in grado di distiguere tra un pacchetto nuovooppure un pacchetto duplicato, già ricevuto in precedenza.

1.4.4.1. Selective Flooding

Il Selective Flooding cerca di risolvere (oquantomento limitare) i problemi del floodingtradizionale (l'altissimo carico indotto sulla rete)senza perderne i vantaggi (ottima probabilità cheil pacchetto giunga a destinazione pur inpresenza di IS che non dialogano l'un l'altro).

Una prima variante di Selective Flooding èl'algoritmo Random Walk, il quale seleziona inmodo casuale su quali linee ritrasmettere ilpacchetto. Questo algoritmo è degno di esserecitato solo in letteratura.

Nel Selective Flooding propriamente detto,ogni nodo emette i pacchetti con un numero disequenza crescente ed univoco, e ogni ISmemorizza il numero di sequenza più alto che haricevuto da ogni altra sorgente. A fronte di unpacchetto entrante, se il suo numero di sequenzaè maggiore di quello memorizzato nel nodo significherà che il pacchetto non èancora transitato nell'IS. In questo caso il nodo applica il normale algoritmo diflooding, inviandolo in tutte le direzioni tranne quella da cui è attivato. Se,viceversa, il pacchetto ricevuto ha un numero di sequenza minore o uguale a quello già memorizzato, significa che il pacchetto è già stato ricevuto (etrasmesso) una volta, quindi verrà scartato. La sua ritrasmissione sarebbe inutilein quanto quello stesso dato è già transitato una volta su quella porzione rete.

Quest'ultima miglioria permette di trasmettere efficacemente la stessainformazione a tutti i nodi, qualsiasi sia la topologia. Lo svantaggio è che talemetodo richiede memoria nei nodi, dato che bisogna memorizzare tutti ipacchetti (o almeno il numero di sequenza, se disponibile) su ogni nodo perpoter verificare se sono già passati.

Una tecnica di selective flooding è utilizzata per il calcolo delle tabelle diinstradamento sia del protocollo IS-IS (ISO 10598) che del protocollo OSPF. Inquesto caso l'overhead non è elevatissimo in quanto vengono memorizzati soloalcuni pacchetti di routing ma non i pacchetti dati che sono in proporzionepreponderanti.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.4. FloodingVIDEO: Flooding

WebLibrary Frame File Page 19

1.4.5. Routing Centralizzato

Il routing centralizzato è tra i metodiadattativi quello che più si avvicina al fixeddirectory routing. Presuppone l’esistenza di unRCC (Routing Control Center) che conosce latopologia della rete, riceve da tutti i nodiinformazione sul loro stato e su quello deicollegamenti, calcola le tabelle di instradamentoe le distribuisce. Ogni nodo mandaperiodicamente informazioni di stato (ad esempiola lista dei nodi vicini cioè raggiungibili con unsolo hop, la lunghezza delle proprie code, laquantità del traffico processato a partiredall'ultimo report): l'RCC avrà quindi unaconoscenza globale sulla rete e calcolerà le nuovetabelle di routing per tutti gli IS secondo lemetriche desiderate.

Il routing centralizzato è un metodo checonsente una gestione della rete molto accuratain quanto permette di calcolare le tabelle anchecon algoritmi molto sofisticati; inoltre ildebugging è facilitato in quanto il RCC ha sempreil pieno controllo sullo stato della rete.

Il routing centralizzato presenta tuttaviadiversi svantaggi. Innanzitutto concentra lefunzioni cruciali in un unico centro che, puressendo magari duplicato per ragioni diaffidabilità, rimane pur sempre un collo dibottiglia (la porzione di rete intorno adesso è soggetta ad un elevato volume di trafficodi servizio, informazioni di stato che arrivano alRCC e tabelle di instradamento che escono dalRCC), può richiedere una potenza elaborativanotevole, infine è un single point of failure.Inoltre ha una certa difficoltà ad adattarsi a retiin cui le condizioni di traffico varianorapidamente, mentre non è soggetto a particolaricontroindicazioni in presenza di una rete stabile. Questo metodo è comunqueusato con successo nella rete telefonica, tipicamente soggetta a tempistiche divariazione topologica piuttosto lente e dove è normalmente implementato unmonitoraggio centralizzato dell'intera rete.

1.4.6. Routing Isolato

Il routing isolato è l’opposto di quellocentralizzato: non solo manca un RCC, ma ogniIS calcola le tabelle di instradamento in modoindipendente senza scambiare informazioni congli altri IS. Il principale algoritmo di questo tipo èBackward Learning, adottato dai bridgetrasparenti (IEEE 802.1D) per scoprire latopologia della rete.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 20

1.4.6.1. Backward Learning

Nel Backward Learning l’IS acquisisce unaconoscenza indiretta della rete analizzando iltraffico che lo attraversa: se si riceve unpacchetto da parte di un nodo A attraverso uncerto link, l’IS apprende che il nodo A èraggiungibile attraverso quell’interfaccia. In altreparole l'apprendimento è "all'indietro", perchè sisfrutta l'informazione del mittente del pacchettoper risalire alla sua locazione.

Le figura presenta un esempio di questosemplice algoritmo, che ha tuttavia alcuniproblemi di funzionamento nel caso di topologiemagliate. Infatti, in mancanza di informazionispecifiche per la destinazione richiesta, ilprocesso di forwarding del nodo B adotterà latecnica di flooding. Il nodo B copierà il pacchettonelle due direzioni (verso C e verso E), nellasperanza che questo arrivi a destinazione.Questo genererà ovviamente un loop tra i nodi B,C,F,E, che verrà risoltosolamente con la morte del pacchetto per vecchiaia.

L'algoritmo di Backward Learning è quindi spesso accoppiato ad un algoritmoche riduce la topologia magliata di una rete in una topologia ad albero in modoche i loop non siano fisicamente possibili.

Il Backward Learning permette di conosceresoltanto le informazioni sui nodi "parlatori" (unnodo attivo ma silenzioso non è riconosciutodall'algoritmo) e magari aggiornare la lororaggiungibilità ad un costo minore. Invece, nonfornisce nessuna funzionalità per rivelarel’irraggiungibilità di qualche nodo; occorrelimitare la validità temporale delle entry nellatabella con degli appositi timer che vengonoinizializzati ad un dato valore ogni volta che unpacchetto in transito conferma l’entry, edecrementati automaticamente con il passare deltempo. Quando la validità temporale di una entrygiunge a zero, questa viene invalidata edeliminata dalla tabella di instradamento.

Una variazione del precedente algoritmoinclude un valore di costo che viene incrementatonel passaggio attraverso ogni IS, e che vieneinserito all'interno di ogni pacchetto. Questo costo permette di risonoscere stradealternative a costo diverso; tuttavia questa modifica, nuovamente, tiene tracciasolamente dei miglioramenti ma non dei peggioramenti nei costi dei percorsi.Anche in questo caso, quindi, è necessario inserire una soglia massima per lavalidità alle entry negli IS in modo che la rete riesca ad aggiornarecorrettamente i percorsi nel caso in cui quello migliore diventi indisponibile.

In base a questa modifica l'Intermediate System C conoscerà che A èraggiungibile in 2 hops attraverso B, e in 3 hops attraverso F (infatti riceve ilpacchetto generato da A da ambedue i percorsi). All'occorrenza, quindi, sarà ingrado di utilizzare anche il percorso alternativo a costo maggiore.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere

WebLibrary Frame File Page 21

Il routing distribuito unisce i vantaggi del routingcentralizzato ed isolato, ossia i routercomunicano tra loro per scambiarsi informazioni(la decisione non è presa solamente in base adinformazioni locali come nel routing isolato), manon esiste un RCC che coordina il tutto e larouting table viene calcolata da tutti gli IS subase paritetica. E' quindi un funzionamento ditipo peer, dove non esiste un nodo "più bello"degli altri e dove tutti cooperano alla riuscita delrisultato finale.

I due algoritmi maggiori di routing distribuitosono il Distance Vector (e la sua variante PathVector) e il Link State. Tali algoritmi sonoadottati da tutti i protocolli di routing piùmoderni; quindi, per la loro importanza, verràdedicata una sezione apposita per ognuno diessi.

1.5. Algoritmo Distance Vector

Si supponga che i segnastradisti comunichino l'un l'altro a vista, per mezzo diopportuni segnali visibili solamente a distanza limitata. Costoro, piazzatistrategicamente ad ogni incrocio, comunicano l'un l'altro tutte le informazioni inloro possesso. Così, il segnastradista del primo incrocio comunicherà tutte leinformazioni di routing (coppia località - distanza) in suo possesso a tutti i suoicolleghi che stanno in incroci adiacenti ("Io, nodo di Torino, raggiungo me stessoa costo zero"). Costoro apprenderanno di non essere soli sulla rete e, a lorovolta, comunicheranno ai loro vicini le informazioni in loro possesso ("Io, nodo diGenova, raggiungo me stesso a costo zero e Torino a costo 100"). In brevetempo, il metodo del passaparola farà sì che tutti i segnastradisti presenti nellarete autostradale conosceranno esattamente tutte le destinazioni raggiungibili eanche la direzione migliore per esse ("Io, nodo di Pisa, raggiungo me stesso acosto zero, Genova a costo 200 e Torino a costo 300").

L'esempio introduce l'essenza dell'algoritmo Distance Vector (noto anchecome algoritmo di Bellman-Ford) che si basa sul passaparola e sullacomunicazione tra soli nodi adiacenti. In altre parole, ogni nodo comunica tuttele informazioni di connettività in suo possesso a tutti gli IS adiacenti.

Si abbia la rete in figura e si supponga (persemplicità) che i nodi vengano accesicontemporaneamente. Ad esempio il nodo E (maanalogo discorso vale anche per gli altri)comunicherà ai suoi nodi adiacenti (A,F) tutto ciòche è di sua conoscenza, ossia solo sé stesso(visto che il bootstrap è appena finito). Tuttavia,A ed F riceveranno questo annuncio cheintroduce una nuova informazione di cui eranoprima all'oscuro: esiste una destinazione E equesta si raggiunge in una ben particolaredirezione (attraverso A1 per il nodo A eattraverso F1 per il nodo F). Il risultato, a questopunto, è che sia A che F capiranno di non essere isoli nodi presenti sulla rete. Per di più, siccome Aed F conoscono il costo di attraversamento deiloro link (rispettivamente A-E ed F-E, ambeduepari a 1), ricaveranno facilmente che il costo diraggiungimento della destinazione E è pari a 1per entrambi.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.4.7. Routing Distribuito

VIDEO: Routing Dinamico - Distance Vector - Bellman FordVIDEO : Distance Vector Routing

WebLibrary Frame File Page 22

L'algoritmo Distance Vector prevede ora che A edF emettano a loro volta un DV contenente tutte leinformazioni di loro conoscenza: prendendo ilsolo nodo A, l'informazione dirà che A esiste e siraggiunge a costo zero, e che sulla rete esisteanche il nodo E, raggiungibile attraverso A acosto 1. Questo annuncio giungerà a C, il qualeapprenderà l'esistenza di A, F ed E, e così via. E'possibile schematizzare l'informazione portata daogni annuncio con i seguenti punti (anche semaggiori dettagli sull'algoritmo verranno fornitidalle sezioni successive):

esiste una certa serie di destinazioniraggiungibili

queste destinazioni si possono raggiugnerein una certa direzione attravero un certonodo X (quello da cui è arrivato l'annuncio)

il costo di raggiungimento in questadirezione è ricavabile sommando, al costo riportato nell'annuncio, il costodi attraversamento del link tra il nodo in esame e il nodo adiacente X

Per comodità, negli esempi successivi si supporrà che l'attraversamento di unlink abbia costo unitario a meno che non venga esplicitamente indicato un altrovalore.

Riassumendo, l'essenza dell'algoritmo è la seguente: ogni IS comunica,solamente ai propri vicini, tutte le informazioni della rete in suopossesso.

1.5.1. Il Distance Vector

Il Distance Vector (o vettore delle distanze) èuna tabella che memorizza la coppiadestinazione-costo per ogni destinazioneconosciuta dall'IS in esame. Se, ad esempio, suuna rete sono presenti quattro possibilidestinazioni, a regime ogni IS emetterà un DVche comprenderà quattro righe nelle quali saràindicata la destinazione e il costo necessario araggiungerla partendo dall'IS in esame. L'elencodelle destinazioni sarà uguale per tutti, mentreogni nodo annuncerà valori diversi per quantoriguarda i costi. Così, seguendo l'esempio infigura (e considerando la sola destinazione A), ilDV di D conterrà una riga A,1 (il nodo Draggiunge la destinazione A a costo 1), mentre ilDV di B conterrà la riga A,1 (il nodo B raggiungela destinazione A a costo 1).

Ogni nodo annuncerà il proprio DV ai nodivicini e memorizzerà l'ultimo DV ricevuto da ogni IS adiacente. L'uso di questainformazione servirà nell'operazione di fusione del DV.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 23

Lo scopo di un qualsiasi algoritmo di routing è lagenerazione della tabella di routing. Il DistanceVector ottiene questo risultato attraversol'operazione di fusione dei Distance Vector,che consiste nel selezionare, per ognidestinazione conosciuta, il percorso in base alcosto migliore. L'operazione di fusione si basasul fatto che ogni nodo memorizza l'ultimo DVgiuntogli da ogni vicino adiacente , quindi ogninodo conoscerà i costi del percorsonodo_adiacente - destinazione per tutte ledestinazioni conosciute.

Si supponga, in figura, di considerare il nodoA. Questi ha ricevuto il DV di D, quindi saprà adesempio che la distanza D-C è pari a 2. Daquesta informazione, l'IS A sarà in grado dicapire che esisterà un percorso tra sé stesso e C:questo percorso passerà attraverso D ed avrà uncosto pari a quello necessario a raggiungere D (ossia 1), più il costo tra D e C(ossia 2), ottenendo un costo per l'intero percorso A-C pari a 3. Si supponga orache A riceva anche il DV dell'altro nodo adiacente B, nel quale troveràl'informazione (C,1), ossia che esiste un percorso tra B e C a costo 1. Il nodo A,applicando lo stesso procedimento di prima, sarà in grado di capire che esisteràun percorso alternativo A-C a costo 2, passando attraverso il nodo B. Il nodo Aavrà due possibili percorsi per raggiungere C: un primo a costo 3 (passando daD), un secondo a costo 2 (passando da B). L'operazione di fusione per questadestinazione si completerà scegliendo il percorso migliore che sarà, ovviamente,quello a costo minore.

In alcuni casi, un nodo si troverà a dover decidere tra due nodi a costouguale (ad esempio il percorso A-E può essere compiuto sia attraverso B che D).In questi casi sarà facoltà del nodo di decidere quale dei due sarà il prescelto.

L'operazione di fusione dei DV verrà ripetuta per ogni destinazioneconosciuta e comprenderà anche l'utilizzo di informazioni locali al nodo, cheverranno utilizzate dal processo di fusione, così come i DV dei nodi adiacenti.Queste informazioni locali comprenderanno tutte le informazioni che sonoconosciute direttamente dal nodo stesso: ad esempio il nodo A conoscerà sèstesso che verrà raggiunto ovviamente a costo 0. Questa informazione verràutilizzata per determinare il percorso migliore con sé stesso per la costruzionedella routing table.

Il risultato finale dell'operazione di fusione sarà la costruzione della routingtable aggiornata per il nodo in esame. Dalla routing table è immediato ricavare ilDV che il nodo A emetterà verso i suoi nodi adiacenti: esso si ricava infatti dallatabella di routing alla quale viene tolta la colonna "next hop", che non è di alcunautilità per la costruzione del DV. Anche se la figura riporta un esempio dove viene indicata la direzione di uscita dei pacchetti (ossia i link di uscita) in quantopiù intuitivo, è da ricordare che una routing table non conterrà maisemplicemente la direzione di uscita quanto il next hop. Infatti, la sola direzionenon permetterebbe di risolvere le ambiguità presenti nelle reti broadcast (adesempio le LAN) nelle quali la sola direzione di uscita è ambigua in quantopermette il raggiungimento di più nodi adiacenti.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.5.1.1. Fusione e generazione del Distance Vector

WebLibrary Frame File Page 24

L'algoritmo DV è molto semplice. Un nodoemetterà periodicamente il proprio DV verso inodi adiacenti per rinfrescare le informazioni dirouting. In aggiunta, il nodo sarà in ascoltodell'arrivo di altri DV dai nodi vicini. Alla ricezionedi un DV questo viene prima memorizzato(sostituendolo ad un eventuale DV già inmemoria ed emesso da quello stesso nodo),quindi viene ripetuta l'operazione di fusione ed,eventualmente, aggiornata la routing table. Se larouting table non varia rispetto a quellaprecedente, il DV appena ricevuto non ha portatoalcuna novità, quindi il nodo continua nel suofunzionamento normale. In caso invece la routingtable abbia qualche variazione (ad esempio unnodo viene raggiunto attraverso un percorsodiverso, oppure ad un costo diverso) vienericalcolato il DV relativo al nodo in esame epropagato a tutti i nodi adiacenti, secondo laregola del "passaparola".

I DV vengono comunque generati periodicamente, anche in presenza di unarouting table che non ha subito alcuna variazione. La generazione periodica delDV è necessaria per riconoscere l'esistenza / mancanza di una adiacenza. Adesempio, la mancanza del collegamento tra A e B viene rilevata dal fatto che, perun certo periodo di tempo, A non riceve più il DV da B: allo scadere di undeterminato timeout B verrà dichiarato irraggiungibile. La generazione periodicafa sì che l'algoritmo DV sia indipendente dai meccanismi di segnalazione dieventuali guasti ai livelli sottostanti: come visto in precedenza esistono situazioni(ad esempio spezzoni Ethernet) nelle quali non è possibile rilevare la presenza /mancanza del collegamento con un nodo prima adiacente per mezzo del solosegnale link-up proveniente dall'interfaccia fisica.

Il processo di ricalcolo della routing table viene attivato anche nel caso dellacaduta di un link direttamente connesso ad un IS (se il segnale link-up èdisponibile). Ad esempio, nel caso in cui un IS rilevi che un link direttamenteconnesso ad esso risulti inutilizzabile, cancella dalla sua memoria tutti i DVprovenienti da quella direzione in quanto non più attiva. Viceversa, se il segnalelink-up non è disponibile, è necessario attivare l'apposito timeout associato adogni DV. Quando questo timeout scade, il DV viene invalidato e viene ricalcolatala routing table.

Il ricalcolo della routing table, anche in caso di guasto, avviene sempre conla stessa procedura: fusione del DV presenti in memoria, a cui vengono aggiuntele informazioni locali. Questo procedimento, si vedrà in seguito, può portare adalcune sorprese durante i transitori.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.5.2. L'algoritmo Distance Vector

WebLibrary Frame File Page 25

Per chiarire meglio i concetti esposti inprecedenza, si definisca una rete (come quella infigura) e si simuli il comportamentodell'algoritmo DV. Si supponga allora diinizializzare la rete alimentando tutti i nodicontemporaneamente (Cold Start ). In questostato, ciascuno dei nodi è caratterizzatounicamente da una conoscenza locale, chesignifica che ciascun nodo conosce il proprioindirizzo ma ignora totalmente la topologia dellarete. La tabella di routing sarà quindi minima,caratterizzata da una singola voce, quella delnodo stesso.

Il nodo A genererà il DV che, nel casospecifico, sarà composto dall'unico valoreattualmente presente nella tabella diinstradamento, e lo invierà a tutti i nodidirettamente collegati (le adiacenze, ossia i nodiB e D), i quali vedranno ora crescere la loro conoscenza della rete.

B e D infatti aggiorneranno tutte le distanze pervenute dal DV inviato da Asommando loro il costo del link locale (assunto pari a uno). A fronte della fusionedel DV, sia B che D rileveranno una variazione nella loro tabella di routing, il cheprovocherà un'emissione del loro DV (nuovo) verso i relativi nodi adiacenti.

Le tabelle di routing cominceranno quindi a popolarsi: i nodi A, Econosceranno di avere due nuovi vicini (B,D), mentre i nodi B,C,Driconosceranno l'esistenza di un nuovo vicino (rispettivamente D,B,B). Tutti inodi emetteranno allora il DV aggiornato, e così via, fino al raggiungimento dellostato stabile, quando i DV verranno generati solamente in base al timeoutperiodico.

E' facilmente verificabile come, in questo caso, i nodi sarnno in grado diconvergere in breve tempo ricavando ciascuno la propria routing table correttacon il percorso migliore per tutte le destinazioni.

1.5.2.2. Esempio: caduta di un link

Si consideri ora il nodo A e si supponga checada il collegamento con il nodo B in figura.L'algoritmo Distance Vector, applicato come dacopione, prevede che vengano invalidati tutti iDV provenienti dal link caduti (in questo casosolo da B), quindi verrà riattivato il processo difusione.

E' importante notare, a questo proposito,come risulti estremamente conveniente lamemorizzazione dei DV dei nodi adiacenti: infattiA rileverà correttamente come il DV di B non siapiù valido (e quindi verrà scartato), ma D nonverrà interessato dal guasto e quindi sipresupporrà che la routing table di D non varieràdi conseguenza. La memorizzazione del DV di Dpermetterà quindi ad A di calcolareimmediatamente la sua routing table senzaulteriori scambi di DV tra i nodi.

E' però facile vedere come questo meccanismo, che appare estremamenteintelligente, porti a delle incongruenze inaspettate.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere e capire l'esempio

1.5.2.1. Esempio: Cold StartLeggere e capire l'esempio

D

WebLibrary Frame File Page 26

Tutti gli algoritmi di routing distribuito hannoqualche problema durante i transitori. Tuttavia, acausa di alcune caratteristiche intrinseche alDistance Vector, questo algoritmo puòenfatizzarne alcuni aspetti.

Gli aspetti indesiderati più comuni nelDistance Vector sono:

Black Hole: i pacchetti inviati ad unaparticolare destinazione per un qualchemotivo finiscono su un router sbagliato, ilquale, non disponendo di una route perquella destinazione, non sa a chi inviare ilpacchetto e pertanto decide di cestinarlo;

Bouncing Effect : è un effetto suipacchetti dati, i quali si trovano in un loopin quanto due o più routers si rimbalzanotra loro i pacchetti (dovuto ad un RoutingLoop);

Count to Infinity : è un effetto perverso del Distance Vector, nel quale irouter non si accorgono che una destinazione è diventata irraggiungibile,ma credono che sia ancora attiva anche se riconoscono che la suadistanza sta aumentando sempre di più.

I primi due effetti interessano i pacchetti dati che scorrono in quella retedurante il transitorio e sono spesso presenti (in varie forme) in tutti gli algoritmidi routing mentre il terzo, peculiare del Distance Vector, è riferito al computodelle route ed influisce aumentando la durata del transitorio. Nel caso diDistance Vector, normalmente gli effetti di Count to Infinity e Bouncing Effect simanifestano contemporaneamente.

1.5.3.1. Count to Infinity

Il Count to Infinity è purtroppo ben lungidall'essere un fenomeno raro. Un esempio èmostrato in figura, con una semplicissima retecomposta da soli 3 nodi. Il collegamento tra A e Bsi interrompe, l'IS B ricalcola la sua tabella conl'algoritmo già enunciato (invalidazione del DV diA, fusione delle informazioni locali con i DVrimanenti), e ricava che la destinazione A èancora raggiungibile, ad un costo pari a 3,attraverso il link B2.

Ad una persona umana questo appareimmediatamente come un controsenso: A non èpiù raggiungibile. Purtroppo, però, gli algoritminon hanno il senso delle persone umane e lacorretta applicazione dell'algoritmo porta proprioa questo risultato. Infatti, le uniche informazioniin possesso di B sono che il nodo stesso nonraggiunge A localmente, mentre il nodo C è ingrado di raggiungere A a costo due. Diventa immediato, per B, tentare diraggiungere A a costo 3 attraverso C. Il problema, però, è che questo guastopersevera nel non venire rilevato: infatti B, rilevato un cambiamento nella suarouting table, invierà il DV aggiornato a C, il quale rileverà che la destinazione Aè ancora raggiungibile ma a costo superiore, quindi aggiornerà la propria routingtable e invierà l'aggiornamento a B... ad libitum.

Allo stato attuale dell'algoritmo non c'è soluzione "definitiva": l'unica viapossibile è limitare questo scambio di informazioni imponendo, ad esempio, cheuna distanza superiore ad una certa soglia rappresenta un valore di nonraggiungibilità. Se, ad esempio, la soglia è posta a 16 (come in RIP), il routingloop si interromperà nel momento in cui un IS rileva che la destinazione èraggiungibile a costo 16. A quel punto la destinazione scomparirà dalla routing

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.5.3. Problemi del Distance Vector

Leggere

WebLibrary Frame File Page 27

table, di conseguenza non verrà più annunciata nel DV e la rete avrà ritrovato lasua stabilità.

Questo problema ha trovato delle parziali soluzioni tra le quali si citano loSplit Horizon e l'Hold Down; tuttavia queste tecniche non sono mai totalmenteaffidabili. Queste tecniche verranno analizzate nel proseguo.

1.5.3.2. Bouncing Effect

Lo stesso esempio della figura precedente èutile per visualizzare il fenomeno del BouncingEffect. Si supponga infatti una situazione diCount to Infinity già avviato, dove l'IS B credeche la destinazione A sia raggiungibile versodestra ad un costo 3, mentre l'IS C crede che ladestinazione A sia raggiungibile verso sinistra adun costo 4. Se un pacchetto con destinazione Aviene immesso in quella porzione di rete, essoverrà rimbalzato tra i due IS B e Cindefinitamente fin quando il pacchetto verràscartato grazie allo scadere del suo tempo di vita.Infatti B inoltrerà il dato verso C (così dice la suarouting table), il quale lo rimanderà a B, e cosìvia.

Si ricorda che il Bouncing Effect èparticolarmente pernicioso in quanto provoca unaumento del traffico di rete, influenzando ancheil traffico che invece non è interessato dal guasto (ad esempio i pacchetti chevengono inviati da B con destinazione finale C).

1.5.3.3. Conoscenza topologica

Il problema di fondo dell'algoritmo DistanceVector è la mancanza di conoscenzatopologica. In altre parole, nessuno dei nodidella rete ha idea di come la rete sia fatta:l'algoritmo si basa sul meccanismo delpassaparola ed ognuno dei nodi si fidaciecamente delle informazioni " non di primamano", informazioni che gli vengono riportate dainodi adiacenti. Nel Distance Vector, che si basasu un calcolo incrementale dei costi verso ognidestinazione, nessun nodo ha la possibilità diverificare come sia effettivamente fatta la rete equindi se il calcolo dei costi sia stato fattocorrettamente.

Si prendano ad esempio le due reti in figura:la prima è quella che origina il problema delCount to Infinity; la seconda invece non ne èaffetta. Tuttavia, il nodo B riceverà esattamentelo stesso DV da C in ambedue i casi. Infatti, nella seconda rete, il nodo Cdisporrà di due percorsi equivalenti (a costo 2) verso il nodo A: nella prima rete,quindi, l'informazione contenuta nel DV di C sarà fuorviante, mentre nellaseconda sarà completamente legittima. Tuttavia, il nodo B non avrà modo didiscriminare i due casi a causa della mancanza di informazioni topologiche: egliriceverà sempre lo stesso DV ma non avrà modo di conoscere se questo siaerrato oppure corretto.

Questo esempio dimostra come la mancanza della conoscenza topologiainserisce un problema di fondo nel funzionamento dell'algoritmo Distance Vector:questo è alla base delle affermazioni (non condivise da tutti, in verità) secondo lequali l'algoritmo Link State è intrinsecamente superiore al Distance Vector.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere

WebLibrary Frame File Page 28

1.5.4. Alcune soluzioni

I problemi precedenti sono chiaramenteeffetti non desiderati dell'algoritmo DistanceVector e si è pertanto cercato di minimizzarlimettendo a punto delle strategie che modificanoil modo di operare dell'algoritmo. Tra tutti ipossibili metodi applicabili si distinguono lo SplitHorizon, il Path Hold Down e il Route Poisoning.

Tuttavia, le soluzioni non sono mai definitivea causa della mancanza di fondo dell'algoritmoDistance Vector: nessun nodo ha la mappa dellatopologia, semplicemente ognuno coopera con glialtri per il calcolo della tabella di routing. In altreparole si troveranno sempre delle situazioni nellequali gli algoritmi aggiuntivi entrano in crisi.Tuttavia, l'aggiunta di sempre nuovi algoritmi ingrado di risolvere le lacune ancora esistentirischia di essere controproducente per lalimitazione sopra citata: ulteriori tecniche infattiappesantiscono il protocollo e tendono comunque a non renderlo affidabile al100%.

1.5.4.1. Split Horizon

Lo Split Horizon si basa su un'ideaintuitivamente molto semplice: se un nodo Craggiunge la destinazione A attraverso il nodo B,non ha senso, per B, tentare di raggiungere Aattraverso C. Secondo questa sempliceosservazione, non ha senso per C annunciare a Bla conoscenza della destinazione A dal momentoche C utilizza proprio B (che ovviamente giàconosce tale destinazione, dal momento che C haappreso dell'esistenza di A proprio da B) perraggiungerla.

Questo algoritmo porta a risolvere una certaserie di problemi tra i quali anche quelloevidenziati nella sezione precedente. Infatti, inpresenza di una rete pressochè identica a quellaprecedente (a questo proposito il nodo Dpotrebbe essere tranquillamente ignorato), ilnodo C ometterà, nei DV verso B, tutte ledestinazioni che egli raggiunge attraverso quella linea (ossia A e B). Grazie aquesto fatto il nodo B sarà in grado di calcolare immediatamente la routing tablecorretta: come si vede, infatti, non si genererà alcun count to infinity e la routingtable di B (dopo il guasto e la relativa ri-fusione dei DV) non riporterà ladestinazione A. Infatti, nel processo di fusione, il nodo B non possiederà alcunainformazione relativa alla destinazione A: nè relativamente alle informazionilocali, nè relativamente al DV ricevuto da C.

Lo Split Horizon, come si vedrà, non è però particolarmente utile in caso direti magliate; inoltre complica l'algoritmo in quanto un IS ha ora la necessità dicalcolare dei DV differenziati per ogni linea di uscita, mentre prima il DVcalcolato veniva emesso dal nodo in tutte le direzioni, senza alcuna precauzione.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 29

Dal punto di vista teorico, questa variante nonaggiunge nulla di nuovo a quanto detto nellaprecedente sezione. Infatti, in questo caso,anzichè omettere le destinazioni, queste vengonoannunciate con distanza infinita. Così, adesempio, il DV che C emetterà in direzione C1conterrà anche le destinazioni A e B (che Craggiunge proprio attraverso la porta C1) ma adun costo infinito.

Dal punto di vista pratico, invece, questamodifica ha una certa rilevanza. Ad esempio, inRIP (un semplice protocollo di routing di tipoDistance Vector del mondo IP), i DV possonoanche estendersi su più pacchetti e non sonoinoltre confermati. Nessuno può quindiassicurarsi che un DV arrivi interamente:potrebbe arrivare anche solo una parte dell'interoDV. Di conseguenza, il router aspetterà un certoperiodo di tempo (ben superiore all'intervallo di aggiornamento dei DV) prima diinvalidare una destinazione.

Con lo split horizon semplice, un IS reale (la cui implementazione segue ilmodello del RIP) non ha modo di capire se una destinazione mancante dal un DVè volutamente stata omessa (a causa del DV), oppure quel pezzo di DV si èperso per un problema sulla rete. Il Poisonous Reverse risolve invece questaambiguità: se la destinazione manca, significa che quel pezzo di DV si è persosulla rete; se invece è infinito, significa che è una destinazione che il mittente delDV raggiunge attraverso il nodo che ha appena ricevuto quel DV (oppure che èeffettivamente diventata irraggiungibile).

1.5.4.3. Split Horizon e maglie

Lo Split Horizon risolve il problema dei looptra due host ma soprendentemente non è ingrado di far fronte a loop che investono magliecomposte da più nodi in quanto ha una visionelocale della rete. Nell'esempio illustrato in figura,infatti, la rete è composta da un piccolo anellocon tre nodi: già una topologia apparentementecosì semplice non è più risolvibile tramite SplitHorizon.

Si supponga infatti la caduta del link tra A eB. Il nodo B, accortosi del guasto, ricaverà lanuova routing table che, correttamente, noncomprenderà la destinazione A (infatti i DV di C eD presenti nel nodo in esame non menzionerannoA a causa dello Split Horizon), ed invierà il nuovoDV ai nodi adiacenti (C, D). Tuttavia, sia C che Dhanno ancora memoria del precedente DV inviatodal nodo adiacente (D e C rispettivamente) cheindica una strada alternativa per raggiungere A (rispettivamente attraverso D eC).

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

1.5.4.2. Split Horizon with Poisonous Reverse

WebLibrary Frame File Page 30

I due nodi in esame, verificata la variazione dellarouting table, emetteranno il nuovo DV verso inodi adiacenti, indicado l'esistenza di un percorsoper la destinazione A: il nodo C sarà convintodell'esistenza di un percorso alternativoattraverso D, e viceversa per il nodo D.

Con il nuovo scambio di DV, tutti i nodi dellarete ricalcoleranno la nuova routing table.Tuttavia, mentre C e D riconosceranno di nonavere alcun percorso verso la destinazione Agrazie allo Split Horizon (infatti C aveva scopertol'esistenza di A tramite D, e viceversa: quindi ilnuovo DV di C verso D non conterrà ladestinazione A, per cui D si accorgerà della nonraggiungibilità di A), il nodo B, ricevuto i DV,scoprirà l'esistenza di due presunti percorsiequivalenti verso la destinazione A attraverso inodi C e D. A questo punto è chiaro ilmanifestarsi del Count to Infinity: il meccanismo dello Split Horizon non è ingrado di cancellare dalla memoria dei nodi le destinazioni non più raggiungibili inquanto la destinazione incriminata "riappare" da una direzione diversa da quellaprevista dallo Split Horizon.

1.5.4.4. Path Hold Down

Questo meccanismo è stato inserito per laprima volta all'interno del protocollo di routingIGRP, che è un protocollo che adotta l'algoritmoDistance Vector.

Questo meccanismo è molto semplice: nelmomento in cui un IS rileva il guasto di un linkmette “in quarantena” le route che utilizzanoquel link, non accettandone la modifica (econsiderandole irraggiungibili) per un certoperiodo. La quarantena deve esseresufficientemente lunga in modo da permetterealla rete di trovare un eventuale percorsoalternativo e comunicarlo con sicurezza al nodoin esame.

La figura mostra un caso di Path Hold Down:il nodo B mette in quarantena tutte le routeverso A (in questo caso solamente A), nonaccettandone la modifica e non propagando più quelle destinazioni nei suoi DV.E' evidente come non si possa formare un Count to Infinity tra i nodi B e C inquanto non esistono altri percorsi verso la destinazione. Purtroppo, però,l'algoritmo non viene attivato dai nodi C e D i quali non rilevano la caduta dellink e seguono quindi l'algoritmo Distance Vector classico, con il conseguenteformarsi di un Count to Infinity tra questi due nodi. Questo esempio mostrachiaramente come anche questo metodo sia approssimativo: il nodo che harilevato il guasto non parteciperà ad alcun loop, ma questo non implica che illoop si possa formare su uno degli altri nodi della rete a causa dello stessoguasto che il Path Hold Down cercava di limitare.

L'utilità di questo algoritmo può essere quindi discutibile. In cambio, questoalgoritmo presenta parecchi svantaggi. Innanzitutto il tempo di convergenzaaumenta in quanto il nodo non accetterà alcun aggiornamento delle route inesame fino allo scadere dell'Hold Down timer, che è definito in modo da esseresuperiore al tempo necessario per propagare a tutta la rete modifiche diconfigurazione. Inoltre, questo algoritmo non permette l'adozione di una routeche potrebbe essere legittima: se, ad esempio, esistesse un collegamento tra inodi A e C a costo 2, C annuncerebbe inutilmente questo percorso fino a quandol'Hold Down timer non ne permettebbe la modifica.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

WebLibrary Frame File Page 31

1.5.4.5. Route Poisoning

Anche questo meccanismo è statoimplementato per la prima volta in IGRPsostanzialmente come sostituto del Path HoldDown. Questo algoritmo è basatosull'osservazione che, in presenza di un Count toInfinity, il costo delle route verso una certadestinazione cresce progressivamente. L'idea èquindi quella di bloccare l'utilizzo di tutte le routeche aumentano improvvisamente di costo: laroute verrà rimessa in servizio solamente qualoradue annunci successivi confermino l'esistenza diquella route, ambedue con lo stesso costo.

Questo algoritmo è migliore del precedente inquanto più efficace (risolve più casi), ha untempo di convergenza normalmente più rapido(non è necessario aspettare l'Hold Down timerma è sufficiente che due DV successiviconfermino la stessa informazione), ma ha lastessa limitazione di scartare, a priori, anche gli annunci legittimi che peròcontengano un aumento di costo verso una determinata destinazione (a causa diun percorso diventato irraggiungibile).

1.5.5. Pregi e difetti del Distance Vector

Il vantaggio fondamentale del DistanceVector è la sua facilità di implementazione.D'altro canto, anche se alcune scuole di pensierosostengono la superiorità del Distance Vectorrispetto al Link State, si notano alcuni aspetticritici:

mancanza della conoscenza della topologiadi rete (che rappresenta il limite piùgrosso):

difficoltà nel debugging (nessunnodo ha la mappa della rete, quindiil debugging deve essere fattointerrogando progressivamente unnodo dopo l'altro, fino a localizzarel'IS responsabile del guasto);

difficoltà di capirne e prevederne ilcomportamento su reti grandi;

complessità elevata, esponenziale nel caso peggiore e normalmente

compresa tra O(n 2 ) e O(n 3 ). Questo rende improponibile l'utilizzo di talealgoritmo per reti con più di un centinaio di nodi, a meno che non vengaadottato un partizionamento gerarchico

lenta convergenza ad un instradamento stabile, dal momento chel'algoritmo converge con una velocità proporzionale a quella del link piùlento e del router più lento presenti nella rete;

presenza di numerosi casi nei quali Count to Infinity, Bouncing Effect eBlack Hole non sono evitabili, neanche con meccanismi migliorativiall'algoritmo di base;

algoritmi migliorativi tendono ad appesantire il protocollo senza garantiremai un'efficacia del 100%

necessità di definire una soglia di "infinito" relativamente bassa perlimitare il Count to Infinity, che limita l'impiego pratico di questoalgoritmo a reti piccole.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 32

Dal punto di vista pratico i protocolli basati sull'algoritmi Distance Vectorsono stati pesantemente utilizzati in passato. Attualmente si tende a preferirealgoritmi di tipo Link State, anche se si trovano numerosissimi casi di utilizzo diDV, soprattutto in reti periferiche di limitata estensione e con topologia semplice(poche maglie). Un caso importante di routing di tipo Distance Vector è ilprotocollo BGP, l'attuale protocollo di routing interdominio del mondo TCP/IP, ilquale sfrutta una particolare variante chiamata Path Vector.

1.5.6. Path Vector

L'algoritmo Path Vector è una variazionedell'algoritmo Distance Vector, dove il DV(chiamato qui Path Vector) contiene, per ognidestinazione, l'elenco dei nodi attraversati oltreal costo: ogni riga del Path Vector sarà quindicomposta di un numero maggiore di informazionirispetto al Distance Vector (si veda l'esempio infigura).

Questo accorgimento permette la costruzionedi un algoritmo molto semplice per evitare irouting loop: infatti una route viene accettatapurchè, nel percorso annunciato, non compaiagià il nodo che sta elaborando le route. Ilprotocollo più famoso di questa classe è il BGP, ilquale inserisce una ulteriore modifica: abolisce leinformazioni di costo. Questo è dovuto al fattoche su Internet ogni dominio può avere unadiversa metrica e l'operazione di sommare duecosti calcolati con due metriche diverse è chiaramente senza senso. Per questaragione il costo diventa un parametro inutile e viene omesso dagli annunci fattida questo protocollo.

1.6. Link State

Si supponga che i segnastradisti siano dotati di radio ricetrasmittenti e checomunichino tutti sulla stessa frequenza. Ognuno di essi controlla lo stato delproprio incrocio e verifica lo stato della strada fino all'incrocio successivo. Ognisegnastradista, quindi, conoscerà perfettamente lo stato dell'incrocio di suapertinenza e delle strade che portano agli incroci adiacenti. Una volta che ognunodi essi ha chiara la situazione del suo incrocio, comunicherà, via radio, questeinformazioni a tutti gli altri colleghi. Questi riceveranno le informazioni dello statodi tutte le strade tra i vari incroci della rete autostradale e saranno pertanto ingrado di determinare esattamente la topologia della stessa.

L'esempio introduce l'essenza dell'algoritmoLink State, che si basa su un broadcast delleinformazioni locali a tutti i nodi della rete. Leinformazioni locali, in questo caso, sonocomposte dallo stato di ogni collegamento tra unnodo e quelli adiacenti, informazione suppostasemplice da ottenere. In altre parole, ogni nodocomunica le sole informazioni locali in suopossesso a tutti gli altri nodi della rete.

Si supponga ad esempio la rete in figura, e sisupponga (per semplicità) che i nodi venganoaccesi contemporaneamente. Il nodo E (maanalogo discorso vale anche per gli altri)comunicherà lo stato delle sue adiacenze (cheavrà imparato attraverso un meccanismo a parte)a tutti i nodi della rete attraverso un qualchemeccanismo di "broadcast". Ogni nodo della rete(ad esempio il nodo C) sarà quindi in grado diricostruire la topologia nell'intorno del nodo E, ossia che E è adiacente ai nodi A

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

VIDEO: Routing Dinamico - Link State - LSP VIDEO: Link State Routing

WebLibrary Frame File Page 33

ed F. Se il procedimento verrà ripetuto da tutti gli altri nodi (A annuncerà la sueadiacenze, quindi F, e così via), ogni nodo riceverà queste informazionitopologiche e, facendone l'unione, sarà in grado di ricostruire l'intera topologiadella rete. Se, infine, ogni nodo annuncerà non solo le adiacenze ma anche ilcosto per il raggiugimento delle stesse, ognuno sarà in grado di ricavare, dallatopologia, il percorso migliore verso ogni destinazione.

Riassumendo, l'essenza dell'algoritmo è esattamente duale a quelladell'algoritmo Distance Vector ed è la seguente: ogni IS comunica, a tutti inodi della rete, solamente le informazioni dei link adiacenti in suopossesso.

1.6.1. Componenti dell'algoritmo Link State

L'algoritmo Link State, così come presentatonell'introduzione, è molto semplice. L'idea allabase è quella della costruzione di una "mappadistribuita", ossia ogni nodo dovrà disporre dellamappa completa della rete, che verràregolarmente aggiornata. Tuttavia lo scopo di unalgoritmo di routing non è l'ottenimento dellatopologia di rete, ma il calcolo della routing table.Questo porta ad introdurre il concetto che,nell'algoritmo Link State, dovranno cooperare piùalgoritmi intermedi per poter giungere alrisultato desiderato. In particolare, si distinguonoi seguenti componenti:

Neighbor Greetings: ogni nodo devericonoscere l'esistenza delle adiacenze

Link State (Packet): la struttura datianaloga a DV che contiene il databasedella adiacenze

Flooding: meccanismo che permette la diffusione in "broadcast" dei LS atutta la rete; può essere utilizzato un classico meccanismo di SelectiveFlooding

Algoritmo di Dijkstra o Shortest Path First (SPF): algoritmo che permettedi ricavare la tabella di routing

Bringing up Adjacencies: meccanismo per sincronizzare i database dimacchine adiacenti

1.6.1.1. Neighbor Greetings (Hello)

Il componente di Neighbor Greetings (ancheindicato come Hello) risolve l'ultimo problemadell'algoritmo Link State: il riconoscimento delleadiacenze. Infatti, fino a questo momento, si èsupposto che ogni nodo fosse in grado diriconoscere la presenza dei nodi adianenti, senzapreoccuparsi di come questo venga fatto. Iproblemi sono gli stessi già enunciati perl'algoritmo Distance Vector: è necessario chel'algoritmo si accorga autonomamente dellapresenza / mancanza dei nodi adiacenti senzaaffidarsi a meccanismi esterni quali il segnalelink-up.

Il meccanismo adottato dall'algoritmo LinkState è quindi molto simile all'invio di DV:periodicamente ogni nodo invia un messaggio aipropri vicini nei quali annuncia sè stesso. Il nodoadiacente, ricevendo il messaggio, capirà diavere un nuovo vicino e lo inserirà nel proprio Link State. Il meccanismo di inviodei messaggi ha una frequenza abbastanza elevata da permettere il

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 34

riconoscimento di una variazione nelle adiacenze in tempi ragionevoli (qualchemanciata di secondi).

1.6.1.2. Link State

Il Link State (o stato dei link) è una tabellache memorizza la coppia link-costo per ogninodo adiacente conosciuto dal nodo in esame. Unlink è univocamente determinato dal nodomittente e da quello destinazione: siccome peròogni nodo propaga le sue adiacenze, il nodomittente è implicito nel messaggio inviato sullarete. Di conseguenza, ogni riga del LS conterràun'informazione di destinazione (il nome delnodo adiacente sul quale il link termina) e ilrelativo costo. Se, ad esempio, un nodo haquattro nodi adiacenti, il nodo propagherà unpacchetto contenente quattro righecorrispondenti alle quattro adiacenze. Questopacchetto verrà propagato in flooding, il cheimplica che transiterà invariato nella reteindipendentemente dal fatto che un quasiasi nodoricevente il pacchetto lo consideri utile o meno.Quindi, a differenza del DV, il LS si diffonteràmolto velocemente nella rete in quanto i nodiintermedi lo propagheranno immediatamente senza una preventiva elaborazionedel suo contenuto.

1.6.1.3. Link State Database

Il LS database è quella struttura dati cheunisce insieme i LS ricevuti da ogni nodo. Nonesiste alcun vincolo nell'implementazione diquesta struttura, che può anche non esistere.Tuttavia questa struttura dati si rivelaestremamente efficace per il successivoalgoritmo di Dijkstra, ossia per ricavare, a partiredalla topologia, la routing table. Infatti, ogninodo può vedere il database come il grafo dellarete, dove i nodi rappresentano i router e gliarchi (con relativo costo) rappresentano i link.

E' importante ricordare che il database èassolutamente identico su tutti i nodi della retedal momento che viene costruito attraverso laricezione degli stessi pacchetti LS.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 35

L'algoritmo Link State prevede che il LS,generato attraverso il componente di NeighborGreeting, debba essere recapitato a tutte lemacchine Link State. Questa fase può esserevista come una trasmissione "broadcast", con ilproblema che questa funzione non è supportatadal livello network, mentre è spesso supportatadal livello data-link. A regime, in effetti, questotipo di trasmissione potrebbe essere simulatamandando lo stesso messaggio (in unicast) atutte le macchine elencate nelle routing table, maquesto sistema non potrebbe funzionare nellafase di tramistorio dove alcune destinazionipossono essere ancora sconosciute.

La soluzione consiste nell'utilizzare unasoluzione di flooding o meglio di SelectiveFlooding, preferito per la sua maggioreaccortezza nell'utilizzo della banda trasmissiva,per recapitare lo stesso dato a tutte le destinazioni.

1.6.1.5. Algoritmo di Dijkstra (o Shortest Path First)

E' il meccanismo che permette, a frontedell'insieme delle adiacenze, di ricavare larouting table. A rigore, non è necessarioutilizzare l'algoritmo di Dijkstra: sarebbesufficiente che tutti i nodi utilizzino lo stessoalgoritmo al fine di ottenere percorsi coerenti. Inpratica, però, questo discorso risulta puramenteaccademico e il Link State ingloba l'algoritmo SPF(che è in grado di calcolare il cammino miglioretra due nodi) per il computo della routing table.

L'algoritmo di Dijkstra è molto semplice ed èbasato sull'idea che, dato un nodo radice,esisterà sicuramente un altro nodo la cui distanzadalla radice sarà minima. In altre parole, se A èun nodo radice si selezioneranno tutte leadiacenze di questo nodo, e si sceglieràl'adiacenza che viene raggiunta a costo minore.E' evidente come, essendo la destinazione acosto minore in assoluto, non possano esistere percorsi alternativi migliori. Ilprocedimento reitera considerando le adiacenze dell'insieme dei due nodiprescelti, selezionando l'adiacenza a costo minore, e così via, memorizzando (einserendolo opportunamente nella routing table) ogni volta il percorso fatto perraggiungere quel nodo.

Dal punto di vista formale, l'algoritmo diDijkstra scompone i nodi in quattro categorie:

il nodo radice: quello per cui si stacalcolando l'instradamento

i nodi PATH: quelli per cui si è già trovatoil percorso ottimo

i nodi TEMP: quelli adiacenti, in undeterminato passo dell'algoritmo, ai nodiPATH; rappresentano quindi i nodicandidati ad entrare nell'insieme PATH

gli altri nodi, non ancora analizzatidall'algoritmo (al passo in esame).

Al termine dell'algoritmo gli insiemi PATH eTEMP saranno vuoti.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

Leggere e capire l'esempio

1.6.1.4. Flooding

VIDEO: Routing Dinamico - Algoritmo di Dijkstra VIDEO: Dijkstra's Algorithm

WebLibrary Frame File Page 36

In figura è riportato un esempio difunzionamento dell'algoritmo; si noti come inquesto esempio ogni link ha un proprio costo (icosti dei link non sono unitari). Sia A il nodoradice: si selezionano le adiacenze (passo 2),quindi, tra di esse, si seleziona quella a costominore (passo 3). Pertanto il nodo C,raggiungibile a costo 1, verrà inserito nell'insiemePATH. L'algoritmo riprenderà selezionando lenuove adiacenze per l'insieme TEMP: questavolta le adiacenze saranno i nodi B, D ed E. Ilnodo B è raggiungibile direttamente dalla radicea costo 2, mentre i nodi D ed E sono adiacenzerelative al nuovo nodo inserito in PATH ed hannorispettivamente costo (1+3) e (1+2) dalla radice.Il nodo a costo minore sarà quindi B, che vieneinserito nell'insieme PATH, e così via.

Si noti comeil risultato finale dell'algoritmo sia un albero diinstradamento che è distinto per ogni nodo radicenonostante tutti i nodi attivino l'algoritmo sullostesso database topologico. La capacità di gestirealberi di instradamento multipli è unacaratteristica peculiare del Link State, che non sitrova ad esempio nell'algoritmo di Spanning Treedove invece l'albero di instradamento è unico pertutti i nodi. Diversamente dallo Spanning Treenon ci saranno link inutilizzati: i link inattivi perun albero potranno essere attivi per un altro, ecosì via. Infine, gli alberi così ricavati sarannocoerenti tra di loro: se tutti i nodi attivanol'algoritmo a partire dallo stesso databasetopologico (fatto certo a regime, ma non duranteil transitorio), la rete verrà configurata coninstradamenti coerenti.

E'interessante infine vedere come l'algoritmo diDijkstra possa essere applicato moltosemplicemente a partire dal database topologicoin forma matriciale. L'algoritmo, in questo caso,è molto semplice:

1. Cancellare la colonna della radice (inquanto non interessano i percorsi da unqualunque nodo verso la radice)

2. Selezionare il nodo la cui distanza dallaradice è a costo minore

3. Inserirlo in PATH

4. Cancellarne la relativa colonna

5. Aggiornare i costi del nodo verso le altredestinazioni in modo da tenere conto delcosto tra la radice e il nodo stesso

6. Se esistono ancora nodi non inseriti inPATH (ossia se esistono ancora dellecolonne da cancellare), ritornare al punto 1.

Ad esempio, dopo aver cancellato la colonna della radice, il primo passoconsisterà nel selezionare la destinazione a costo minore considerandosolamente la riga relativa al nodo radice. Il nodo a costo minore sarà C: sicancellerà la relativa colonna e si aggiorneranno i costi di C verso le altredestinazioni in modo da tenere conto del costo tra A e C. Iterando ancora ilprocedimento, ora esisteranno due righe (ossia due nodi) in PATH: si sceglierà ladestinazione a costo minore all'interno delle righe di A e C. Questa destinazione

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 37

sarà B, raggiungibile direttamente da A a costo 2: si cancellerà la relativacolonna, si aggiorneranno i costi da B verso le varie destinazioni tenendo condodel costo A-B (pari a due), e così via. L'algoritmo terminerà quanto tutte lecolonne saranno state cancellate.

Nel caso di percorsi equivalenti, l'algoritmo è autorizzato a sceglierne uno deidue.

1.6.1.6. Complessità dell'algoritmo di Dijkstra

Si dimostra che la complessità algoritmicadell'algoritmo di Dijkstra è (L log L), ossiadipende fortemente dal numero di link presentinella rete. Questo è facilmente verificabiledall'enunciazione dell'algoritmo nella sezioneprecedente: il numero totale dei percorsi cheverranno considerati è proporzionale al numerodei link nella rete. Viceversa, la complessitàdell'algoritmo di Bellman-Ford è (N*L), ossiadipende in equal misura dal numero di nodipresenti sulla rete e dal numero di link. Il primoalgoritmo è quindi molto più scalabile delsecondo dal momento che un termine comparecome logaritmo.

E' importante ricordare come la complessitàsopra citata sia solo una delle componenti dellacomplessità di un eventuale protocollo LinkState: infatti l'algoritmo di Dijkstra è solo uno deitanti pezzi necessari a permettere in funzionamento dell'algoritmo Link State.

1.6.1.7. Generazione dei Link State

In teoria un LS potrebbe essere inviato allarete solamente nel momento in cui si rileva unavariazione della topologia locale, ossia qualora ilnodo riconosca di avere un nuovo vicino, oppurequando il costo verso un vicino è cambiato,oppure quanto si perde la connettività verso unvicino prima raggiungibile.

Questo però è altamente rischioso, in quantose, per un qualunque motivo, il LS non raggiungetutta la rete, non c'è alcun modo per allineare ildatabase del nodo che non ha ricevuto il LS con ilresto della rete. Per questa ragione tutti iprotocolli reali che adottano l'algoritmo LSprovvedono ad un invio periodico del LS, anchese la periodicità è di molto inferiore a quella delmeccanismo di Hello e può essere anchedell'ordine delle ore.

In tutto questo esiste ancora un problema che è la costruzione del databaseper un nodo che si attiva dopo che tutta la rete ha già scambiato i propri LS: inquesto caso il nodo dovrebbe comunque aspettare parecchio tempo prima che ilnuovo scambio di LS venga attivato, e quindi possa capire correttamente latopologia della rete.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

WebLibrary Frame File Page 38

A questo problema risponde l'algoritmo che ha ilcompito di allineare il contenuto del database didue nodi vicini, ossia il bringing up adjacencies.Questo componente permette ad un nodo dievitare di attendere l'invio del LS da parte di tuttii nodi e prevede che il nodo si attivi facendoun'apposita query ai suoi nodi vicini richiedendoloro il database. In altre parole, un nodo attivaimmediatamente la procedura di NeighborGreetings; ogni qualvolta rilevi di avere unanuova adiacenza, effettuerà una fase disincronizzazione del proprio database con il nodoadiacente in modo da essere operativo primapossibile.

Questa fase è utile anche nel caso in cui unarete si partizioni in due tronconi. Questaprocedura verrà attivata nel momento in cui laconnettività viene ripristinata, permettendo inbreve tempo di sincronizzare tutti i database dei nodi sulla rete con le stesseinformazioni di topologia. Siccome la procedura di sincronizzazione viene attivatasolamente sui due nodi cha hanno attivato l'adiacenza, rimane il problema disincronizzare la topologia anche degli altri nodi remoti (ad esempio A e D infigura). A questo proposito, i nodi che scoprono una mancanza nel loro databaseinviano alle loro precedenti adiacenze una copia del LS "nuovo" che verràpropagato in flooding sulla rete aggiornando i nodi di conseguenza.

1.6.2. Link State e reti reali

Nel caso di reti ideali, esistono un paio di problemi che il Link State, cosìcome enunciato fino ad adesso, non prende in considerazione.

1.6.2.1. Stub Network

Si supponga l'esempio in figura. Su una reteterminale giacciono due router e due host.Secondo l'algoritmo Link State, è necessario cheogni entità comunichi, nel proprio LS, l'elencodelle adiacenze. Quindi ogni router dovràcomunicare tre adiacenze (l'altro router e duehost). Tuttavia questa operazione:

è complicata da fare, in quanto gli ES nonpartecipano al processo di HELLO(normalmente gli ES non attivano alcunprocesso di routing)

è comunque ridondante, in quanto gli hostappartengono ad una rete che nonpermette il transito da nessuna parte,quindi gli host potrebbero essere sostituiticon un'unica entry contenente il nomedella rete.

Si noti che un ES è sempre considerato una entità alla periferia della rete inquanto un ES non permette il transito di traffico per conto terzi verso nessunaaltra destinazione (altrimenti sarebbe un IS). Non sia pertanto fuorviantel'affermazione "una rete che non permette il transito da nessuna parte", inquanto la stub network è intesa come l'insieme di tutti gli ES, i quali chiaramentenon permettono il transito verso altre destinazioni. Nel caso in esame, quindi, larete potrà essere modellata da una stub network, a cui accedono ambedue gli IS,e da un collegamento punto-punto tra R1 e R2 che serve per il transito versoaltre destinazioni.

I protocolli che implementano l'algoritmo Link State adottano normalmentel'idea della stub network: anzichè annunciare una adiacenza con ciascun host,annunciano una adiacenza per ogni IS, più una adiacenza per la stub network.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

NO

1.6.1.8. Bringing up adjacencies

WebLibrary Frame File Page 39

1.6.2.2. Reti broadcast

L'algoritmo Link State presenta alcunecriticità anche nel caso di reti di tipo broadcast(ad esempio le LAN) sulle quali insistono più IS.Infatti una rete broadcast può essere modellatacome una maglia completa, nel qual caso ogni ISha (N-1) adiacenze più quella verso la stubnetwork, portando il numero di link all'interno del

LS database a N 2. Questo è chiaramenteingestibile per più motivi:

il link state database diventaestremamente grosso

la complessità dell'algoritmo di Dijkstraesplode (in quanto è proporzionale alnumero di link)

la fase di Bringing up adjacencies diventaproblematica, in quanto un nuovo IS che sitrovi ad essere attivato sulla retebroadcast rileva improvvisamente N-1adiacenze, con le quali inizia (indipendentemente) una fase disincronizzazione del database.

Per questi motivi l'algoritmo Link State hadovuto esplicitamente prevedere una gestioneparticolare per le reti broadcast. La soluzioneconsiste nell'introduzione dell'idea dello pseudo-nodo, o nodo fittizio, che trasforma la rete damagliata a stellare. Ogni IS, infatti, rileverà unasola adiacenza con lo pseudo-nodo stesso il qualefarà da transito per il calcolo della topologia.

In realtà, lo pseudo nodo non è un nodoaggiuntivo inserito in sostituzione della retebroadcast, ma i protocolli reali selezionano unparticolare IS e lo designano come pseudo-nodo(designated router secondo la terminologiaOSPF).

E' evidente, in figura, il miglioramento dellasituazione per quanto riguarda il numero diadiacenze. Questa modifica "virtuale" ditopologia non influenza tuttavia il computo delle route per gli IS partecipanti allarete broadcast : l'algoritmo è sufficientemente intelligente da riconoscere, adesempio, che un pacchetto dovrà essere inviato attraverso R1-R3, senza passareper lo pseudo-nodo R4. In altre parole, lo pseudo-nodo è un meccanismo cheviene utilizzato per evitare un problema intrinseco del routing Link State, madiventa trasparente (per le macchine della rete broadcast) nel momento in cui,dal LS database, si passa alla routing table di ogni router. Viceversa, gli IS nonappartenenti alla rete broadcast credono che lo pseudo-nodo sia effettivamenteun router reale, ma questo non è un problema. Infatti, anche se un router"esterno" crede che il percorso sia R1-R4-R3, una volta che il pacchetto giungeràad R1 questo provvederà ad inviarlo direttamente ad R3, senza altri passiintermedi.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

NO

WebLibrary Frame File Page 40

L'algoritmo Link State è generalmenteconsiderato migliore rispetto al Distance Vector,nonostante sia più complicato internamente inquanto richiede molti più componenti per la suaoperabilità (ad esempio il neighbor greeting con ilcomponente di Hello, che è invece ricavato inautomatico dal Distance Vector). Tra le suecaratteristiche, l'algoritmo ha una convergenzaestremamente rapida grazie al fatto che i LS sipropagano molto velocemente sulla rete. Adifferenza dei LS, infatti, i DV vengono ricavatidalla tabella di routing, pertanto ogni nodo deveprima ricavare la tabella di routing, quindigenerare il proprio DV e propagarlo. Tutto ciòrichiede tempo; inoltre le informazioni propagatecon il "passaparola" possono essere errate,mentre il LS è generato dall'IS sorgente che, ingenerale, è abbastanza cosciente della situazioneal suo intorno. Infatti, i problemi di transitorionon si verificano tanto per LS errati, quanto per iritardi di propagazione degli stessi che fanno sì che i database di alcuni IS nonsiano allineati.

La rapida convergenza dell'algoritmo e il fatto che ogni nodo conoscaesattamente il percorso tra sè stesso e ogni destinazione implica chedifficilmente si formano dei loop. Inoltre, disporre della mappa della rete è unacosa estremamente comoda in fase di debug, quando la visualizzazione deldatabase di un qualunque IS della rete offre l'immediato panorama dello statodella rete stessa.

Dal punto di vista topologico, gli IS LinkState cooperano per mantenere aggiornata lamappa della rete, poi ognuno di essi calcolail proprio spanning tree autonomamente: ogni ISconosce pertanto tutta la topologia della rete equindi anche il percorso per qualunquedestinazione. Gli IS Distance Vector, invece,cooperano per calcolare direttamente le tabelle dirouting: ogni IS conosce solo il suo intorno eognuno di essi si fida del vicino per inviare i dativerso la destinazione, in quanto conosce solo ladirezione migliore (ossia il next hop) necessaria araggiungere qella destinazione.

La semplicità è sicuramente un punto afavore del Distance Vector, dal momento che sibasa su un unico algoritmo mentre il Link Stateingloba al suo interno numerosi componentinecessari alla sua operatività. Dal punto di vistadella memoria occupata, invece, i due algoritmisono equivalenti: ogni nodo LS memorizzerà NLink State contenenti ognuno A adiacenze,mentre ogni nodo DV memorizzerà A distancevector i quali conterranno ognuno N destinazioni.

Dal punto di vista del traffico generato,invece, il Link State presenta un certo vantaggioin quanto i messaggi di Hello, generatifrequentemente, sono molto piccoli in confrontoai Distance Vector. I Link State sono generati conuna periodicità decisamente ridotta a meno divariazioni topologiche: in una rete a regime ilLink State si dimostra quindi più efficiente daquesto punto di vista.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.6.3. Pregi e difetti del Link State

WebLibrary Frame File Page 41

1.7. Routing gerarchico

Il routing gerarchico nasce per far fronte adue problemi. Il primo, di tipo amministrativo, siriferisce al fatto che una grossa rete geograficapuò essere gestita da entità differenti: adesempio, la rete della pubblicaamministrazione italiana è gestitaautonomamente da ogni amministrazione puresistendoci dei punti di interconnessione tra diesse. Ovviamente, ogni amministrazione è tenutaal rispetto di alcuni requisiti minimi dicompatibilità: questo implica che, a fronte dialcune regole comuni, esisteranno altre sceltetecniche differenti tra una amministrazione el'altra: ad esempio in una amministrazionepiccola si potrà scegliere un algoritmo di routingdi tipo Distance Vector, in una grossa uno di tipoLink State.

Il secondo problema, di tipo tecnico, siriferisce al fatto che una grossa rete geografica non può essere gestita come unanuvola di macchine paritetiche così come teorizzano gli algoritmi Distance Vectore Link State: infatti questi algoritmi non sono in grado di operare quando ilnumero di macchine da gestire eccede un determinato livello (il traffico di routingdiventerebbe la parte preponderante del traffico sulla rete).

Questi due problemi portano all'introduzione del concetto di dominio dirouting, ossia un insieme di IS che interoperano tra di loro secondo i principi diun algoritmo di routing comune e che lavorano esattamente nel modo teorizzatoda Distance Vector e Link State. Un dominio di routing è quindi un insieme di ISadiacenti (ad esempio una "fetta" della rete globale nella sua interezza) cheadottano lo stesso algoritmo di routing.

Il problema diventa, a questo punto,determinare come questi domini di routingpossano essere interconnessi l'un l'altro perpermettere la gestione di reti molto più grosserispetto a quanto sarebbe possibile con undominio unico. Il routing di tipo gerarchicoinserisce nuove regole di routing che si vanno adaggiungere a quelle viste fino ad ora(l'ottimalità del percorso secondo una certametrica), ed assume che, all'interno di un certodominio di routing, l'instradamento dei pacchettodeve essere deciso in base al protocollo dirouting attivato. Questo implica, ad esempio, chetutti gli IS di quel dominio devono essereconcordi nel routing, che deve essere gestitoattraverso la stessa istanza del protocollo dirouting. E' possibile quindi dire chel'instradamento interno al dominio di routingsegue le regole solite, senza alcuna influenza delrouting gerarchico. Viceversa, se il mittente e ladestinazione di una comunicazione appartengono a due diversi domini di routing(instradamento esterno al dominio), il routing gerarchico prescrive che i datidebbano essere inoltrati verso il più vicino punto di uscita del dominio inizialeverso quello di destinazione, e da lì presi in consegna dagli IS dell'altro dominio.Questa nuova procedura può essere vista come una nuova regola di routing,applicabile qualora mittente e destinazione appartengano a due domini distinti.Questo implica che:

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

VIDEO: Hierarchical Routing

WebLibrary Frame File Page 42

gli IS del dominio mittente non debbanoconoscere come è fatto il dominio didestinazione: infatti il percorso dei dati neldominio mittente è determinatoesclusivamente dal percorso migliore tra ilmittente e il più vicino router di uscitaverso l'altro dominio, indipendentementeda dove la destinazione sia posizionataall'interno del dominio di destinazione; inpresenza di più punti di contatto tra i duedomini, il percorso dei dati da unasorgente verso una qualunquedestinazione appartenente al secondodominio seguirà un primo tratto comune;

il percorso globale sarà quindi datodall'unione di due percorsi "ottimizzati",quello dal mittente al più vicino router diuscita, quindi da questo alla destinazione:questo implica che il percorso globale,essendo l'unione di due ottimi locali, potrà non essere il percorso ottimo inassoluto;

ogni IS conoscerà esattamente il routing all'interno del proprio dominio(conoscerà ossia tutte le destinazioni presenti nel dominio e il costorelativo al loro raggiungimento), ma conoscerà solamente un estrattodelle informazioni presenti degli altri domini (ossia conoscerà l'elencodelle destinazioni raggiungibili ma non il loro costo). In altre parole, ogniIS avrà un orizzonte limitato in cui tutte le informazioni relative a localitàesterne al dominio compaiono incomplete, senza l'indicazione della lorodistanza.

Se ne deduce che il routing gerarchico migliora la scalabilità della rete econsente il partizionamento della rete globale in domini di routing distinti, aprezzo di possibili mancate ottimizzazioni dei percorsi. Il calcolo del percorsoottimo richiederebbe la presenza di tutte le informazioni di routing (coppiadestinazione - distanza), che implicherebbe che i due domini di routing diventinoin realtà uno solo con buona pace delle esigenze di scalabilità.

Il routing gerarchico è obbligatorio dal punto di vista dell'operatività praticadi una rete reale: per questo motivo l''idea del partizionamento di una retegenerale in domini di routing distinti è presente in tutte le architetture di rete(SNA, Decnet, IP).

1.7.1. Domini partizionati

La figura presenta un esempio di una retecomposta di due domini interconnessi tramitedue punti. E' evidente come i percorsi possanoessere non solo subottimali (ad esempio ilpercorso di andata tra B1 e A4, in quanto vieneprivilegiata la direzione di uscita dal dominio),ma anche asimmetrici (il percorso di ritorno traA4 e B1 è diverso da quello di andata).L'asimmetricità è una cosa estremamentecomune nel caso di routing gerarchico ed èfacilmente rilevabile su reti geografiche (Internetad esempio presenta numerosi casi di routingasimmetrico).

La nuova regola di routing introdotta dalrouting gerarchico introduce una problematicafinora non presente: il problema della partizioneinterna di un dominio. Infatti, secondo i dettamidel routing gerarchico, la caduta del link B1-B2provoca l'impossibilità, per A4, di recapitare i dati alla destinazione B1. InfattiA4, non conoscendo la struttura del dominio B, saprà solamente che B1 e B2fanno parte di questo dominio ma non avrà idea di come questo sia realizzato

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 43

internamente, né se esista una connettività tra B1 ed B2. Conoscendo quindil'appartenenza del nodo B1 ad un dominio esterno B, il nodo A4 invierà ilpacchetto nel dominio B più velocemente possibile. Il pacchetto sarà ricevuto daB2 il quale riconoscerà che la destinazione finale è interna al suo stessodominio, ma non disponendo di una strada per quella destinazione, scarterà ilpacchetto senza riuscire a recapitarlo.

Il problema del partizionamento dei domini è tanto più pernicioso in quanto ilnodo B1 non è isolato all'interno della rete globale dal momento che esiste unpercorso che è in grado di interconnettere B1 a qualunque altra destinazione.Purtroppo, però, questo percorso non è sfruttabile in quanto la nuova regola dirouting introdotta dal routing gerarchico ne impedisce l'utilizzo.

Il solo modo per evitare il problema è quello di creare dei domini che sianofortemente connessi al proprio interno, ossia che siano in grado di recapitare idati tra le varie destinazioni interne (anche a fronte di eventuali guasti)attraverso percorsi completamente interni al dominio: solo in questo caso lacaduta di un link interno non provoca un partizionamento del dominio.

E' interessante notare che questo problema nasce solamente con la caduta dilink interni al dominio: la caduta di un qualunque link di interconnessione tra idomini (ad esempio A1-B1 oppure A4-B2) non ha alcuna ripercussione (a parteuna diversa forma dei percorsi) sull'operatività della rete: ogni mittente sarà ingrado di colloquiare con tutte le destinazioni, interne o esterne che siano.

1.7.2. Redistribuzione

La redistribuzione è una tecnica con la qualedue domini possono realizzare il routinggerarchico. L'essenza della redistribuzione è cheun IS particolare sia contemporaneamentemembro di due domini di routing e conoscapertanto esattamente il routing in ognuno dei duedomini. A questo punto l'IS sarà in grado diprendere le informazioni di routing presenti in undominio e trasmetterle nell'altro, facendo leopportune operazioni di conversione.

Si supponga, ad esempio, il router R infigura. Questo sarà in grado di partecipare alrouting di ambedue i domini, quindi conosceràperfettamente il routing di ambo le parti. Laredistribuzione prevede che questo routerinserisca alcune informazioni apprese da undominio all'interno dell'altro, ad esempio cheistruisca i router del dominio LS dell'esistenza ditutte le destinazioni del dominio DV. La redistribuzione può essere bidirezionaleoppure in una sola direzione (ad esempio solamente le destinazioni DV vengonoinserite nel dominio LS, ma non il viceversa).

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 44

Per poter abilitare la redistribuzione non ènecessario che siano attivi due algoritmi /protocolli di routing diversi nelle due aree, masolo che queste siano tenute distinte. In altreparole ambedue le aree potranno anche avere lostesso protocollo di routing (ad esempio OSPFper il routing IP), purchè i due domini sianoseparati dal punto di vista della propagazionedegli annunci. Il compito di separazione spettaall'IS R che dovrà comportarsi come un "Gianobifronte" partecipando ad ambedue i dominisenza farli apparire come un dominio unico.L'attivazione della redistribuzione provocheràinvece un certo travaso di informazioni chetransiteranno da un dominio all'altro sotto ilcontrollo dell'IS R.

Mentre a livello teorico la redistribuzionepotrebbe implicare ad esempio anchel'inserimento di informazioni di costo in modo che ogni IS del "dominioaggregato" riesca a ricavare il percorso migliore verso la destinazione, in praticala redistribuzione viene utilizzata per realizzare il routing gerarchico el'informazione di costo di tutte le destinazioni esterne viene impostata di defaultad un valore scelto da management. Questo equivale a dire che le informazionirelative alle destinazioni esterne hanno un costo convenzionale, ossia non è piùpossibile ricavare il percorso ottimo in base a questo dato.

1.7.2.1. Perdita della conoscenza topologica

L'utilizzo della redistribuzione offre lapossibilità di diminuire l'overhead complessivo digestione del protocollo di routing. Siano dati duedomini A e B, gestiti ad esempio da un algoritmoLink State. Nel caso in cui questi domini venganointerconnessi senza distribuzione, la reterisultante sarebbe un dominio unico e tutte lemacchine del dominio B conoscerannoesattamente la forma del dominio A. Questoimplicherà che nel dominio B si propagherannouna serie di Link State packets contenentiesplicitamente la topologia di A, ossia, ognimacchina del dominio B dovrà memorizzare 5 LSaggiuntivi (il dominio A è composto da 4 nodi piùil nodo R).

L'attivazione della redistribuzione cambierà lecarte in gioco: ora i due domini sarannoeffettivamente distinti e le macchine del dominioA non comunicheranno più nulla alle macchine del dominio B. Le unicheinformazioni verranno propagate dal router R, con un unico LS "equivalente"comprendente tutte le destinazioni e il relativo costo. L'informazione propagatada R, come si vede in figura, è nettamente più compatta della precedente e nonpermette di risalire alla topologia del dominio A: infatti le macchine del dominio Bcrederanno che R abbia un collegamento punto-punto con tutte le macchine deldominio A.

L'inserimento nel LS propagato da R di un costo convenzionale anzichè ilcosto effettivo è un plus che non porta alcun vantaggio dal punto di vista dellariduzione della complessità. Il costo "convenzionale" può essere obbligatorioqualora le metriche siano diverse e non esista un meccanismo di traduzione dauna all'altra (ad esempio in un dominio si contano il numero di hops e nell'altro ilritardo in millisecondi). Tuttavia l'idea del "costo convenzionale" porta a renderepossibile una ulteriore semplificazione: se le destinazioni del dominio A possonoessere aggregate, il router R potrà propagare un LS molto ridotto annunciando ladisponibilità di tutte le destinazioni inizianti per A (convenzionalmente A*), conun nuovo abbattimento della complessità per il dominio B che si trova a dovergestire una sola riga nel LS contro le precedenti quattro.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

VIDEO: Prefix Aggregation and Subnets

WebLibrary Frame File Page 45

Nei protocolli reali ambedue le soluzioni (l'indicazione del "costo reale"piuttosto che del "costo convenzionale") sono in uso. Il processo diredistribuzione classico, che realizza il vero routing gerarchico, adotta infatti ilcosto convenzionale. Altri protocolli, tra cui OSPF, adottano invece il "costoreale" che permette, a fronte di più punti di contatto tra i due domin, di scegliereil percorso di uscita ottimale verso la destinazione, con buona pace della nuovaregola introdotta dal routing gerarchico. E' possibile dire che in questi protocollile regole del routing gerarchico vengono rilassate a fronte di una maggioreottimizzazione dei percorsi.

Il routing gerarchico presenta tuttavia il problema già visto per il DV: nessunIS ha informazioni "di prima mano" in riferimento alle destinazioni presenti inaltri domini. da questo punto di vista il routing gerarchico assomiglia al DV: ogniIS deve fidarsi dell'informazione che gli giunge dal suo border router e non c'èquindi la possibilità di controllare questa informazione.

1.7.2.2. Redistribuzione e costi

Il comando default-metric risolve il problemadella distribuzione di una informazione di routingin un altro dominio. Tuttavia rimane aperto unaltro problema, che si presenta quando ad unrouter arrivano due informazioni di routingrelative ad una determinata destinazione da dueprotocolli diversi. Il router in esame si troverà adover decidere la strada migliore confrontando ledue informazioni che non sono tuttavia affattoconfrontabili in quanto il costo è rappresentatoda metriche diverse.

Per risolvere questa ambiguità, i router Ciscodefiniscono un livello di privilegio per ogniprotocollo, evidenziato da un numero diverso daogni protocollo. Nel momento in cui un router sitrova a comparare due costi appresi conprotocolli diversi, la route migliore sarà quellacon il protocollo con costo più basso.Nell'esempio in figura, il router R privilegerà il percorso attraverso il dominioEIGRP in quanto questo protocollo ha un costo intrinseco inferiore a quello di RIP(90 contro 120).

Questo problema è correlato alla redistribuzione, ma è presente su tutti irouter che hanno contemporaneamente almeno due protocolli di routing distinti enon solo sui router che hanno la redistribuzione attivata. Il router R, ad esempio,non ha alcuna redistribuzione.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

VIDEO:Routing Protocols Overview (Distance Vector and Link-State) CCNA Part1Routing Protocols Overview (Cisco CCNA- RIP, RIPv2, EIGRP, OSPF) Part2

Page 46

Per routing inter-dominio si intende normalmentela distribuzione di informazioni di routing tradomini amministrativi distinti. In questaaccezione, quindi, un dominio non sarà una zonadella rete con una tecnologia di routingomogenea (come è stata definita nella sezioneprecedente) ma una zona della rete ancheeterogenea, sotto la responsabilità di un un'unicaunità amministrativa. Nella rete Internet questaentità amministrativa è indicata comeAutonomous System.

Il routing tra entità amministrative distinteavrà la necessità di nuove regole rispetto a quelleenunciate fino ad adesso. Infatti, tutti glialgoritmi di routing visti fino ad ora condividonoun'idea di fondo: è necessario collegare tra lorodegli IS e far sì che questi si scambino delleinformazioni in modo che tutte le localitàinterconnesse siano raggiungibili, possibilmente secondo il percorso migliore.Questa assunzione deriva dal fatto che, dal punto di vista tecnico, non esistonomotivi per scegliere una strada peggiore quando ve ne è una migliore adisposizione.

1.8.1. Altre esigenze

Dal punto di vista del routing tra entitàamministrative distinte, invece, la scelta di undeterminato percorso ha motivi economici edamministrativi prima ancora di qualsiasiconsiderazione sull'ottimalità di un percorso. Adesempio, il fatto che in IP una qualunque retepuò essere una rete di transito verso altri dominiè mal visto dai gestori di rete in quanto implicache una rete debba essere dimensionata nonsolamente in base al traffico generatolocalmente, ma anche in base al traffico deglialtri domini che utilizzano quello in esame cometransito. Ad esempio, il responsabile del dominioC (in figura) può essere danneggiato dalpassaggio di traffico tra A e B tramite il suodominio in quanto deve dimensionaremaggiormente le sue infrastrutture di rete (sia larete interna al dominio, sia soprattutto il linkgeografico tra B e C).

Una seconda esigenza molto sentita è quella della sicurezza: può essereimportante, ad esempio per istituzioni governative all'estero, poter comunicarecon la sede centrale attraverso Internet, ma con la certezza che questi datipasseranno solamente attraverso le reti di gestori fidati.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.8. Routing inter-dominio

VIDEO: Routing with Multiple Parties

WebLibrary Frame File Page 47

Dal punto di vista dell'aspetto economico, unasituazione problematica viene spesso a crearsinei punti di peering, ossia in quei punti dellarete nei quali due entità amministrative distintesi scambiano il traffico. Si supponga infatti che ildominio B sia in realtà un dominio moltoimportante, ad esempio perchè ospita al suointerno molti siti importanti della rete (adesempio www.yahoo.com, e altri). In questocaso, il gestore del dominio B avrà una forzacontrattuale non indifferente e potrà chiedereun'ammontare economico molto elevato perconsentire a chiunque di collegarsi direttamentecon il suo dominio. Infatti un'interconnessionediretta al dominio B permetterà di accederevelocemente ai siti più importanti della rete inquanto i dati non sono sottoposti a percorsitroppo arzigogolati tra mittente e destinatario. Ungestore di rete che si rispetti non potràpermettersi un accesso lento alle risorse piùimportanti della rete e sarà quindi obbligato a stipulare un accordo di peeringeconomicamente svantaggioso con il gestore B.

Viceversa, si supponga che i domini A e C siano poco importanti ed abbianodeciso di scambiarsi il traffico su base paritaria, dividendosi a metà i costi delcollegamento WAN senza alcun altro onere aggiuntivo. In presenza di una talesituazione, il dominio A trarrà un notevole vantaggio economico nel dirottare iltraffico diretto a B attraverso C, in quanto l'invio del traffico sarà a costo zero.Toccherà viceversa al gestore del dominio C pagare profumatamente l'accesso aldominio B anche per il traffico non generato da egli stesso.

L'amministratore del dominio C troverà una soluzione a questo problemamodificando ad arte i suoi annunci di routing verso il dominio disonesto. In altreparole, i router di bordo del dominio C ometteranno (negli annunci di routingverso A) di indicare la presenza di una strada verso il dominio B, forzandopertanto l'amministratore disonesto ad utilizzare l'unica strada percorribile, ossiail collegamento diretto A-B (con i relativi costi). Questo equivale all'inserimentodi una regola (o policy) che istruirà gli IS del dominio C a comportarsi in un certomodo verso la rete interna (ossia annunciando la disponibilità di una stradaverso il dominio B) e in un'altro verso l'esterno (annunciando le destinazioniconosciute in maniera parziale). In questo modo tutte le macchine interne aldominio C saranno in grado di raggiungere il dominio B, ma il dominio A nonverrà a sapere della disponibilità di questo percorso.

Tuttavia, questo meccanismo blocca solamente la propagazione delleinformazioni di routing. Infatti, l'amministratore di A può presagire che latopologia da lui conosciuta sia poco credibile e può quindi provare a forzareugualmente l'invio del traffico per B attraverso C con la conseguenza che iltraffico verrebbe comunque recapitato a destinazione. Infatti, una volta che iltraffico giungerà ad un router interno al dominio C, questo sarà in grado diprenderlo in consegna e recapitarlo correttamente a B. La soluzione "definitiva"include quindi l'abilitazione di opportuni filtri sui router di bordo di C in modo cheil traffico dati entrante soddisfi agli stessi criteri già utilizzati per le informazionidi routing. Ad esempio, i router di bordo del dominio C accetteranno solamentetraffico in ingresso diretto alle macchine interne al dominio C.

E' quindi evidente come esistano numerosi casi in cui il fattore economico (ole esigenze di sicurezza) diventi preponderante: per questo motivo il calcolo delmigliore percorso di routing interdominio è soggetto a regole che devonocomprendere la disponibilità di un collegamento fisico mediate da un insieme diregole che ne specificano in maniera opportuna la logica di utilizzo.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 48

Un altro esempio di utilizzo di routing per questoscopo può essere estrapolato analizzando unasituazione realmente accaduta nel passato. Sisupponga un grosso provider il quale raccoglie lagrande maggioranza del traffico Internet in unanazione. Questo provider dispone inoltre anchedei server più ambiti in territorio nazionale. E'evidente come i provider alternativi siano in uncerto senso obbligati a fornire ai loro clienti unaccesso veloce al provider maggiore, in quantoquesti clienti richiedono un accesso veloce ai sitipiù importanti, ospitati dal provider dominante.

Dal punto di vista del provider maggiore,invece, non c'è alcun interesse a permettere unaccesso veloce alle proprie risorse da parte diconcorrenti: questo vorrebbe dire, per lui, far sìche questi possano continuare a sopravvivere. Lascelta più conveniente per il grosso provider saràquella di impedire un accesso veloce alle sue risorse in modo da poter acquisirela (scarsa) fetta di mercato in mano alla concorrenza. I provider minori dovrannoquindi rivolgersi a provider di terze parti (ad esempio provider internazionali) perveicolare il loro traffico, i quali provvederanno poi ad immetterlo nella rete delprovider in esame, ma perdendo chiaramente in velocità di risposta (eobbligando i provider concorrenti a pagare profumatamente l'invio di questi datisul backbone internazionale).

Questo è uno dei motivi per cui, all'inizio della diffusione di Internet in Italia,una connessione web tra un sito del provider X e un utente del provider Y,magari fisicamente residenti nella stessa città, vedeva i dati transitare primaall'estero (ad esempio negli Statu Uniti), per poi essere effettivamente recapitatinella locazione desiderata.

1.8.2. Soluzioni per il routing inter-dominio

Il routing inter-dominio segue le regole delrouting gerarchico integrate con opportuneregole di carattere amministrative e necessitapertanto di protocolli ad hoc. A questo proposito,i protocolli di routing si divideranno in IGP(interior Gateway Protocol) e EGP (ExteriorGateway Protocol). I primi verranno impiegati inun dominio di routing con estensione limitata enormalmente seguiranno le regole di "routingparitetico" viste in precedenza. Ogni gestoremanterrà la possibilità di partizionare il propriodominio amministrativo in domini di routingdistinti (ad esempio il dominio C in figura),interconnessi attraverso opportuni apparaticapaci di fare la redistribuzione. La rete delsingolo gestore utilizzerà tipicamente soloinformazioni di tipo "tecnico" (ossia informazionidi connettività e costo) per decidere l'inotro deipacchetti verso le varie destinazioni. I protocolliEGP, invece, saranno utilizzati nello scambiodelle informazioni di routing tra diversi domini amministrativi e integrerannonelle loro funzionalità la capacità di gestione di regole di tipo diverso.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.8.1.1. Altro esempio: provider dominante

VIDEO: Border Gateway Protocol

WebLibrary Frame File Page 49

Questa capacità consentirà ad esempio dimascherare gli annunci di routing inviati neglialtri domini (nascondere alcuni aspetti dellaconnettività del dominio in esame), così comeconsentirà di manipolare gli annunci di routinginseriti nel dominio interno (ad esempio per far sìche venga privilegiato un percorso più lungo maritenuto più sicuro).

Affinchè questo sia possibile, è necessaria laconoscenza completa del percorso versoqualunque destinazione, operazionegeneralmente onerosa. Da questo punto di vista,ad esempio, Internet utilizza il concetto diAutonomous System per determinare il percorsoverso una certa destinazione: ogni annuncio dirouting inter-dominio comprenderà quindi lacoppia destinazione - AS path (elenco degli ASattraversati per giungere alla destinazione). Perquesto motivo un algoritmo di routing inter-dominio non può essere basatosull'algoritmo Distance Vector.

Un IS in grado di mettere in comunicazionedue domini distinti sarà quindi un oggetto ingrado di dialogare con due protocolli di routing(uno IGP e uno EGP) contemporaneamente: ilprimo gli permetterà di conoscere la topologiainterna al dominio, il secondo per conoscere ledestinazioni (e i relativi percorsi) di tutte ledestinazioni esterne. Questo oggetto dovràquindi essere in grado di trasferire parte delleinformazioni apprese da un protocollo all'altroprotocollo, eventualmente modificandoleopportunamente. Ad esempio, dovrà propagareall'esterno l'elenco delle destinazioni presentilocalmente al dominio in modo da permetterne laraggiungibilità su scala globale. Questaoperazione si baserà su un processo di decisioneche terrà conto sia delle informazioni topologiche(ricevute attraverso gli annunci di routing) sia lepolitiche amministrative, configurate a mano dalgestore.

L'output di questo processo sarà un insieme di route esterne che dovrannoessere propagate nel dominio interno, e un altro insieme di route (interne edesterne) che dovrà essere propagato attraverso il protocollo di routing EGP (attualmente BGP).

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

WebLibrary Frame File Page 50

La redistribuzione viene spesso attivataall'interno di un solo dominio amministrativo inquanto solitamente non si ha la necessità di uncontrollo così fine sulle informazioni che vengonotrasferite da un dominio all'altro. Inoltre, spesso ivari domini di routing sono sotto il controllo dellostesso amministratore, il che rende possibile lagestione di tutto il processo di redistribuzione suun router unico.

Viceversa, si supponga che la redistribuzionedebba essere fatta su domini amministratividistinti: in questo caso non è pensabile che esistaun solo router a cui accedono due amministratoridiversi. Il problema non è tanto quello per cuidue persone di due organizzazioni diverse devonocondividere lo stesso router, quanto piuttostoche, da quel router, è possibile risalire adinformazioni sull'organizzazione interna diambedue i domini, operazione che chiaramente permetterebbe ad estranei dientrare in possesso ad informazioni riservate.

Il routing tra domini amminsitrativi distinti viene pertanto solutamenterealizzato attraverso l'impiego di due diversi router, ognuno sotto il controllo diuna diversa struttura amministrativa (AS in Internet), sul quale sono abilitati idue protocolli di routing interno ed esterno , con una redistribuzionenormalmente in un solo verso (interno --> esterno). I due router di frontieradialogheranno poi tra di loro attraverso il protocollo di routing esterno,sfruttando pertanto le sue caratteristiche di gestione delle policy.

Il routing tra entità amministrative distinte ha solitamente la redistribuzioneabilitata in un solo verso in quanto spesso l'interno del dominio non ha lanecessità di conoscere esattamente tutte le destinazioni esterne. Infatti, alledestinazioni interne al dominio basta conoscere che tutto ciò che non èconosciuto internamente (il "resto del mondo") si raggiunge attraverso il router diuscita, senza sapere bene cosa sia il "resto del mondo". Viceversa, il protocollo dirouting esterno deve conoscere esattamente le reti contenute in ogni dominio(da cui la necessità della redistribuzione interno --> esterno) per poternepropagare la raggiungibilità verso gli altri domini.

1.9. Conclusioni

Il livello network deve essere in grado direcapitare un pacchetto verso una qualunquedestinazione su una rete. Per fare questo deveessere in grado di capire come è fatta la rete edeterminare il percorso migliore da ogni sorgentead ogni destinazione (routing). Inoltre, ogni ISdeve essere in grado di sfruttare questainformazione localmente per instradareopportunamente i pacchetti dati secondo leregole stabilite in precedenza (forwarding).

Gli algoritmi in assoluto più utilizzati sono ilrouting by network address per quanto riguardail forwarding, anche se la tecnologia labelswapping mostra nuovi segni di vitalità(attraverso MPLS) grazie alla necessità dielevatissime capacità di commutazione nonrealizzabili (al momento) con architetture delprimo tipo.

Per quanto riguarda gli algoritmi di routing, il Distance Vector è ancora moltoutilizzato grazie alla sua semplicità, anche se installazioni medio-grandi utilizzanoil Link-State. Nel caso di routing inter-dominio si utilizza invece frequentementeil Path Vector (nel BGP) in quanto aiuta a tenere bassa la complessità (il Path Vector è più

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006

1.8.2.1. Redistribuzione e domini amministrativi

WebLibrary Frame File Page 51

semplice da implementare e gestire rispetto ad un Link State), aspettoimportante per ambienti dove la complessità è di per sé elevata (a causa dellepolicy).

Altri algoritmi di routing vengono adottati in casi specifici: il routing statico inentità di dimensioni estremamente ridotte, il routing isolato nelle architetture diinterconnessione a livello data-link (bridging), il routing centralizzato su altre reti(ad esempio reti di derivazione telefonica).

Gli algoritmi distribuiti, accoppiati attraverso routing gerarchico, sono allabase del funzionamento di Internet. Nonostante attualmente si pongano inevidenza alcuni limiti di scalabilità, questi sono dovuti forse più all'architettura diInternet che non a demeriti propri di tali algoritmi. Infatti, il protocollo IPv6prevede l'utilizzo massicio di tali meccanismi anche se accoppiati ad una diversadistribuzione degli indirizzi che rende il tutto maggiormente scalabile.

Viceversa, una sempre maggiore enfasi viene posta in questo momento aiprotocolli di routing inter-dominio, in certi casi utilizzati anche all'interno di unsingolo dominio di routing grazie alle loro capacità di trasporto di policy. Questacaratteristica permette di realizzare servizi evoluti quali le VPN e favoriscel'adozione di tecnologie quali MPLS.

1.10. Bibliografia

[1] Leslie Lamport, Robert Shostak and Marshall Pease, The ByzantineGenerals Problem, ACM Transactions on Programming Languages andSystems, 4(3):382-401, July 1982.

Questo è un articolo classico nella letteratura degli algoritmi distribuiti.Definisce il problema dei Generali Bizantini (Byzantine General Problem)e dimostra che questo non è risolvibile per un numero di traditori pari osuperiore ad 1/3 del totale dei generali. Questo articolo analizza i modicon cui è possibile costruire dei sistemi affidabili anche a fronte di guasti(o informazioni intenzionalmente sbagliate). Riferimenti sull'argomentopossono essere trovati all'indirizzo http://www.cs.cornell.edu/gupta/byzantine.htm.

1.11. Letture fondamentali

Per chi fosse interessato a maggiori dettagli sullle problematiche di routing,le letture obbligatorie sono:

Christian Huitema, Routing in the Internet (2nd ed), Prentice Hall Ottimo libro, con una visione sia teorica (delle problematiche di routing)che pratica (dei protocolli attualmente in uso) che ne fanno un "must"nell'argomento.

Radia Perlman, Interconnections (2nd ed), Addison WesleyOttimo libro, molto più focalizzato sull'aspetto algoritmico rispetto aquello precedente. Tratta le problematiche di interconnessione anche alivello due, mentre il precedente si limita al routing vero e proprio.

file://localhost/C:/Archivio/Web/netlibrary/routing/text.htm 16.17.26 21/09/2006