Algoritmi di routing in reti magliate wireless

POLITECNICO DI TORINO

III Facoltà di IngegneriaCorso di Laurea in Ingegneria delle Telecomunicazioni

Monografia di Laurea

Algoritmi di routing in retimagliate wireless

Marco Fanti

Supervisore AziendaleIng. Andrea Ghittino

Luglio 2011

Sommario

Questo documento descrive il lavoro compiuto durante il tirocinio svolto presso illaboratorio di ricerca InLab del CSP. Il documento è costituito da due parti, nellaprima si spiega nel dettaglio il protocollo di routing OSPF e brevemente il protocolloOLSR, nella seconda si mostra un’implementazione pratica di un demone OSPF edi uno OLSR su una rete magliata simulata e si analizzano le prestazioni dei dueprotocolli.

Il protocollo OLSR non è stato trattato molto nel dettaglio in quanto è già statoprovato a dovere in passato in questa azienda, in questo documento si procederà adanalizzarlo essenzialmente evidenziando i pregi e i difetti rispetto a OSPF.

ii

Indice

Sommario ii

1 Introduzione teorica a OSPF 11.1 Protocolli Link State . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Introduzione a OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2.1 Concetto di Area . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 RFC di riferimento . . . . . . . . . . . . . . . . . . . . . . . . 21.2.3 Tipi di area . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.4 Tipi di nodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.5 Contiguità dell’area Backbone . . . . . . . . . . . . . . . . . . 41.2.6 Virtual Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.7 Esempio di Automous System gestito con OSPF . . . . . . . . 5

1.3 I pacchetti OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.1 OSPF Header . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Pacchetto Hello . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.3 Protocollo Hello . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.4 Cosa sono le adiacenze . . . . . . . . . . . . . . . . . . . . . . 81.3.5 Elezione del Designated Router e del suo Backup . . . . . . . 91.3.6 Il database Link State . . . . . . . . . . . . . . . . . . . . . . 91.3.7 LSA Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.8 Router LSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.9 Network LSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.10 Summary LSA . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.11 AS-external LSA . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.12 LSA speciali per le aree NSSA . . . . . . . . . . . . . . . . . . 121.3.13 Pacchetti OSPF non Hello . . . . . . . . . . . . . . . . . . . . 131.3.14 Creazione delle adiacenze . . . . . . . . . . . . . . . . . . . . . 131.3.15 Procedura di flooding . . . . . . . . . . . . . . . . . . . . . . . 141.3.16 Procedura di Aging . . . . . . . . . . . . . . . . . . . . . . . . 161.3.17 Confrontare due LSA . . . . . . . . . . . . . . . . . . . . . . . 161.3.18 Impostazione del costo di un collegamento . . . . . . . . . . . 16

iii

1.3.19 Creazione delle tabelle di routing . . . . . . . . . . . . . . . . 171.3.20 Bilanciamento del carico con OSPF . . . . . . . . . . . . . . . 171.3.21 Considerazioni sui link virtuali . . . . . . . . . . . . . . . . . . 18

1.4 Considerazioni finali su OSPF . . . . . . . . . . . . . . . . . . . . . . 181.4.1 OSPF su reti wireless . . . . . . . . . . . . . . . . . . . . . . . 18

2 Il protocollo di routing OLSR 192.1 Metriche ETX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1.1 Calcolo delle metriche ETX . . . . . . . . . . . . . . . . . . . 192.2 Traffico di rete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Demone OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4 Configurazione di base del demone OLSRd . . . . . . . . . . . . . . . 20

3 Implementazioni di OSPF 223.1 OpenOSPFd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2 BIRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 XORP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.4 Quagga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4.1 Configurazione del demone Zebra . . . . . . . . . . . . . . . . 233.4.2 Configurazione del demone ospfd . . . . . . . . . . . . . . . . 24

4 Realizzazione dei test 284.1 Simulatore di reti NetKit . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.1.1 Installazione di Quagga e OLSRd su NetKit . . . . . . . . . . 294.2 Configurazione di OSPF per la rete del CSP . . . . . . . . . . . . . . 30

4.2.1 Divisione in aree . . . . . . . . . . . . . . . . . . . . . . . . . 304.2.2 Hello Interval e Router Dead Interval . . . . . . . . . . . . . . 314.2.3 Hello Interval e Router Dead Interval sui link virtuali . . . . . 31

4.3 Test su OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3.1 Traffico di gestione della rete . . . . . . . . . . . . . . . . . . . 324.3.2 Tempi di reazione della rete con perdita totale dei pacchetti . 324.3.3 Tempi di reazione della rete con perdita parziale dei pacchetti 334.3.4 Tempo di formazione delle adiacenze . . . . . . . . . . . . . . 44

4.4 Test su OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.5 Configurazione del demone . . . . . . . . . . . . . . . . . . . . . . . . 44

4.5.1 Traffico di gestione della rete . . . . . . . . . . . . . . . . . . . 454.5.2 Tempi di reazione della rete . . . . . . . . . . . . . . . . . . . 45

5 Conclusioni 465.1 Soluzioni proposte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

iv

A Pacchetti OSPF 48A.1 Pacchetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

A.1.1 Pacchetto Hello . . . . . . . . . . . . . . . . . . . . . . . . . . 48A.1.2 Pacchetto Database Description . . . . . . . . . . . . . . . . . 49A.1.3 Pacchetto LS-Request . . . . . . . . . . . . . . . . . . . . . . 50A.1.4 Pacchetto LS-Update . . . . . . . . . . . . . . . . . . . . . . . 50A.1.5 Pacchetto LS- Acknowledgement . . . . . . . . . . . . . . . . 51

A.2 LSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51A.2.1 LSA Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51A.2.2 Router LSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52A.2.3 Network LSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 53A.2.4 Summary LSA . . . . . . . . . . . . . . . . . . . . . . . . . . 53A.2.5 AS-External LSA . . . . . . . . . . . . . . . . . . . . . . . . . 54

B NetKit 55B.1 Requisiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55B.2 Installazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

B.2.1 Configurazione post-installazione . . . . . . . . . . . . . . . . 56B.3 Comandi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56B.4 Creare un laboratorio . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

B.4.1 File lab.conf . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57B.4.2 Esempio di file lab.conf . . . . . . . . . . . . . . . . . . . . . . 57B.4.3 Esempio di file .startup . . . . . . . . . . . . . . . . . . . . . . 58

B.5 Trasferimento file tra macchina virtuale e host . . . . . . . . . . . . . 59

C Esempi file di configurazione Quagga 60C.1 File zebra.conf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60C.2 File ospfd.conf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

C.2.1 Router interno . . . . . . . . . . . . . . . . . . . . . . . . . . 61C.2.2 Area Border Router con Link Virtuale . . . . . . . . . . . . . 62C.2.3 AS Boundary Router interno a un area . . . . . . . . . . . . . 63

Bibliografia 65

v

Capitolo 1

Introduzione teorica a OSPF

OSPF (Open Shortest Path First) è un Interior Gateway Protocol in grado di ga-rantire bassi tempi di convergenza. È usato in tutto il mondo anche per reti moltograndi, come ad esempio le backbone degli ISP.

1.1 Protocolli Link State

OSPF è fondamentalmente un protocollo di routing dinamico di tipo Link State.Con questo nome si indicano tutti quei protocolli di routing dove ogni nodo conosceesattamente la topologia dell’intero dominio di routing, ogni nodo quindi ha un da-tabase che descrive la topologia e che deve mantenersi uguale in tutto l’AutonomousSystem.

L’algoritmo di base è molto semplice e si divide in due passi eseguiti ciclicamenteda ciascun nodo della rete. Prima ogni nodo raccoglie informazioni sui collegamentia lui direttamente adiacenti, poi inoltra questi dati a tutti i nodi della rete tramite lacosiddetta procedura di flooding. Infine ogni nodo esegue l’algoritmo di Dijkstra percalcolare il percorso più breve verso ogni destinazione, questo algoritmo è consideratoabbastanza pesante, ma per il momento è l’unico a garantire che non si formino deiloop nei percorsi di instradamento.

1.2 Introduzione a OSPF

Lo svantaggio dei protocolli Link State è che al cambiamento dello stato di unsingolo collegamento tutti i nodi si devono rifare tutto il calcolo, e questo può essereveramente un problema per le reti molto grandi.

1

1 – Introduzione teorica a OSPF

1.2.1 Concetto di AreaOSPF si differenzia dalla maggior parte degli algoritmi di routing Link State perchéintroduce un livello di gerarchizzazione nella rete permettendone la divisione in di-verse aree. Ogni area è composta da un insieme di collegamenti tra i nodi, non daun insieme di nodi. Questo significa che ogni nodo può avere alcuni collegamenti ap-partenenti ad un’area e altri ad un’altra area. Esistono quindi nodi interni alle aree,cioè con tutti i collegamenti appartenenti ad una sola area, ed altri nodi cosiddettidi “bordo area”.

Le aree vengono identificate tramite numeri di unsigned int da 32 bit (a partireda 0), e per convenzione si usa la stessa notazione degli indirizzi IPv4. L’area 0quindi diventa 0.0.0.0, la 1 invece 0.0.0.1 e così via.

Questa divisione del dominio di routing, se ben fatta, porta a una riduzione delcarico di lavoro su ogni nodo, perché l’algoritmo di Dijkstra viene eseguito solamenteall’interno delle aree. I router interni ad un’area infatti non conoscono la tipologiaesterna, ma conoscono solo i costi con cui i router di bordo area possono raggiungerele varie destinazioni.

In pratica il cambiamento di un costo su un collegamento causa il ricalcolo delcammino minimo con l’algoritmo di Dijkstra solo all’interno dell’area dov’è avvenuto.I nodi esterni all’area invece in tal caso verranno a sapere dai nodi di bordo area cheè cambiato il costo con cui loro raggiungono una certa destinazione, ma il carico dilavoro da fare sarà molto minore.

Un’altro vantaggio potenziale della divisione in aree è la minore occupazione dibanda causata dal traffico di gestione del protocollo, per ottenere ciò però bisognasfruttare bene le tipologie di area esistenti.

1.2.2 RFC di riferimentoOSPF è un protocollo definito dall’IETF, quindi ci sono varie RFC che descrivonolo standard le sue estensioni aggiunte negli anni. Le più importanti sono:

RFC 2328 definisce lo standard OSPFv2, nato per le reti IPv4 e largamente usatoancora oggi nella sua forma originaria[1];

RFC 2370 definisce gli Opaque LSA, per poter estendere in futuro le funzionalitàdi OSPF;

RFC 3101 definisce il tipo di area Not-So-Stubby-Area (NSSA)[2];

RFC 5340 definisce OSPFv3, nato esplicitamente per le reti IPv6 e quindi pocoutilizzato;

2


RFC 5614 definisce un’estensione a OSPFv3 in modo che il protocollo possa sup-portare le reti Ad-Hoc radiomobili, è un documento ancora in stato speri-mentale, e non descrive tutti gli aspetti che sarebbero necessari per la suaimplementazione;

RFC 5838 definisce un’estensione ad OSPFv3 in modo che possa essere usato anchesulle reti IPv4. Questo è molto importante perché così, quando questo RFCsarà implementato, da una parte gli sviluppatori potranno concentrarsi solo suOSPFv3, dall’altra i gestori delle reti potranno usare le estensioni di OSPFv3anche sulle loro reti IPv4.

In questo documento ci concentreremo su OSPFv2 per le reti IPv4[1] che è la versionemaggiormente usata ai giorni nostri..

1.2.3 Tipi di areaVediamo di seguito le varie tipologie di area che si possono incontrare in un Auto-nomus System(AS) gestito con OSPF:

Backbone è anche chiamata area 0 perché ha sempre questo numero. È l’area checollega letteralmente tutte le altre, le quali obbligatoriamente devono averealmeno un nodo collegato a quest’area. È l’unica area che ha l’obbligo diessere sempre contigua. Tutto il traffico inter-area passa almeno da un nodoche confina con la backbone.

Aree normali conoscono tutte le reti raggiungibili esterne all’area, ma anche quelleesterne all’AS annunciate dai nodi confinanti con altri AS. I nodi interni allearee normali possono confinare con altri AS e annunciare le reti che vedonoagli altri nodi OSPF.

Stub in queste aree non vengono inoltrate informazioni sui costi per raggiungeredestinazioni esterne all’AS, ma viene pubblicizzata al posto una default route.Dentro queste aree non possono trovarsi nodi confinanti con zone non gestitecon OSPF.

Totally Stub è la tipologia consigliata quando l’area ha solo un nodo di confine conla backbone, questo perché i nodi interni all’area non sanno nulla sull’esterno.Ai nodi interni viene comunicata solo una default-route che deve servire pertutte le destinazioni esterne all’area. Questo può ridurre di molto il traffico.

Not-So-Stubby-Area (NSSA) è utilizzata quando all’area è collegata una zonanon gestita con OSPF, accessibile solo tramite l’area in questione. Queste areequindi possono confinare con zone non gestite da OSPF, a differenza delle stub.[2]

3


1.2.4 Tipi di nodo

Ogni nodo (o router) può essere di vari tipi a seconda delle aree a cui appartengonoi suoi collegamenti. In particolare si possono distinguere 4 tipi di router:

Area-Border-Router (ABR) sono quei router che fanno parte di più aree, quindisono loro ad annunciare in un’area le metriche con cui raggiungono le altrearee. Devono sempre essere connessi alla backbone, fisicamente o tramite linkvirtuali, e gestiscono un database Link State per ogni area.

Router interni sono i router che hanno tutti i collegamenti appartenenti alla stessaarea, quindi gestiscono un solo database Link State.

Autonomous-System Boundary-Router (ASBR) sono quei router che confi-nano con zone non gestite con OSPF, e hanno il compito di informare il pro-prio AS su quali reti possono raggiungere e con quale costo. Possono esseresia router interni che di bordo area.

Ogni nodo/router è identificabile all’interno del dominio di routing tramite il suoRouter ID, un numero di 32 bit che, come per le aree, viene sempre espresso conla tipica notazione degli indirizzi IPv4. Il Router ID si può anche lasciare nonconfigurato, in tal caso viene usato al posto l’indirizzo IP più alto tra tutte leinterfacce del router.

1.2.5 Contiguità dell’area Backbone

Com’è noto l’algoritmo di Dijkstra per il calcolo dei cammini minimi viene eseguitosolamente all’interno delle aree. È quindi possibile che si vadano a formare deiloop nell’instradamento tra aree che vanificherebbero i vantaggi dati dall’uso di unprotocollo link state.

Per evitare questo problema lo standard impone che tutti i router di bordo areafacciano parte della backbone, si impone poi anche che tutto il traffico transitante tradue aree (chiamato traffico inter-area) passi obbligatoriamente per l’area backbone.Ad esempio il traffico tra due ipotetiche aree A e B dovrà sempre fare il percorsoA → backbone → B.

Quest’ultimo esempio fa anche capire che l’area backbone deve per forza esserecontigua, se no sarebbe impossibile instradare verso alcune destinazioni.

Se un router facesse effettivamente parte di più aree senza essere collegato anchealla backbone, per lui sarebbe impossibile trasferire dati direttamente da un’areaall’altra senza violare l’OSPF standard.

4


1.2.6 Virtual LinkEssendoci spesso la necessità di fare aree che non potranno essere fisicamente colle-gate alla backbone, è stato inventato uno stratagemma che consente di creare “linkvirtuali” tra diversi ABR. Questi link vengono definiti tra due router di bordo areae sono idealmente visti dal demone OSPF come un’interfaccia di rete virtuale col-legata direttamente alla backbone. Il protocollo poi tratterà questi link come sefossero dei collegamenti punto-punto. Si possono vedere due esempi di link virtualiin figura 1.1 nella pagina seguente

In realtà un link virtuale non crea strane connessioni come si potrebbe pensarein un primo momento. Semplicemente tutti i pacchetti OSPF appartenenti allabackbone, quando dovranno essere trasmessi su uno di questi link, verranno speditida un ABR verso l’indirizzo IP fisico dell’altro capo del link. I pacchetti seguirannoautomaticamente il cammino minimo in quanto il percorso sarà tutto interno all’area,e verranno identificati dal ricevente come appartenenti alla backbone.

Un ABR considera “attivo” un link virtuale quando le informazioni in suo posses-so relative all’area in cui passa il link gli permettono di raggiungere l’ABR all’altrocapo.

I link virtuali non possono passare attraverso le aree stub.

1.2.7 Esempio di Automous System gestito con OSPFSi prenda ad esempio l’AS in figura 1.1 nella pagina successiva, si può notare l’area0.0.0.4 configurata come stub, ma sarebbe ancora meglio configurarla come totallystub in quanto ha solo un punto d’uscita verso l’esterno. Si evidenzia anche lapresenza di due link virtuali necessari a mantenere gli ABR delle aree 4 e 5 contiguialla backbone. Infine si noti che gli AS BR possono essere presenti all’interno ditutte le aree (escluse le stub), ma quelli interni alle aree NSSA sono usati solo percollegamenti verso piccoli AS.

1.3 I pacchetti OSPFOSPF lavora direttamente su IP e usa cinque differenti tipi di pacchetti:

1. Hello: utilizzati per scoprire e mantenere le adiacenze, sulle reti di transito (conpiù di due router) vengono anche utilizzati per eleggere un “router designato”e un suo backup (vedi 1.3.5 a pagina 9);

2. Database Description: utilizzati quando due router si vedono per la primavolta per confrontarsi i rispettivi database link state;

5


Figura 1.1. Esempio di divisione in aree di un AS gestito con OSPF. Si possononotare gli Area Border Router e gli ASBR

3. LS-Request: utilizzati per richiedere ad un router vicino delle informazioni chenel router richiedente sono assenti od obsolete;

4. LS-Update: utilizzati per trasferire ad un vicino le voci del proprio databaselink state;

5. LS-Acknowledgment: utilizzati solo per confermare la ricezione delle informa-zioni contenute nei pacchetti LS-Update.

Si precisa fin da ora che questi pacchetti viaggiano sempre da un router fino al suovicino, non vengono mai inoltrati ulteriormente. Al massimo saranno le informazioni

6


ivi contenute ad essere spacchettate e reintrodotte in altri pacchetti simili destinatiad altri router.

1.3.1 OSPF HeaderTutti i pacchetti hanno un header comune contenente i seguenti campi:• Version: indica la versione di OSPF (2 o 3);

• Type: indica il tipo di pacchetto (da 1 a 5);

• Router ID: indica il router che ha generato il pacchetto;

• Area ID: indica l’area a cui appartiene il pacchetto;

• Checksum;

• AuType: specifica se usare l’autenticazione e, se si, quale tipo usare (passwordin chiaro oppure crittografata con MD5);

• Authentication.

1.3.2 Pacchetto HelloQuesto è il pacchetto utilizzato dal protocollo Hello (vedi 1.3.3 nella pagina succes-siva), contiene i seguenti campi:• Hello Interval: tempo in secondi che trascorre al massimo tra due emissioni

successive di un pacchetto Hello;

• Router Dead Interval: indica dopo quanti secondi senza ricevere pacchettiHello si deve considerare “morto” un router vicino;

• Designated router (DR) e Backup Designated Router (BDR): indicano il DR eil BDR della rete su cui si affaccia l’interfaccia di rete, questri campi si usanosolo sulle reti non punto-punto (vedi 1.3.5 a pagina 9);

• Options: contiene vari bit ma ne sono definiti solo 2, uno indica se l’area èstub, l’altro se è NSSA;

• Elenco dei vicini: indica i router ID di tutti i nodi vicini visti tramite questainterfaccia scoperti grazie ai rispettivi pacchetti Hello.

Perché due vicini riescano effettivamente a vedersi è necessario che i campi delpacchetto, esclusa la lista dei vicini, siano uguali. Quindi non si possono configurareHello Interval e Router Dead Interval diversi su più router che si affacciano sullostesso link.

7


1.3.3 Protocollo HelloQuesto protocollo serve a scoprire i vicini su una determinata interfaccia, quindilavora in modo diverso a seconda del tipo di rete a cui essa è collegata.

Sulle reti broadcast e NBMA viene eletto un router designato (vedi 1.3.5 nellapagina successiva). Nelle broadcast ogni nodo si annuncia periodicamente inviandopacchetti Hello all’indirizzo multicast AllSPFRouters 224.0.0.5. Nelle reti NBMAinvece serve una configurazione preesistenete che istruisca il protocollo Hello su qualisono i router potenzialmente contattabili tramite l’interfaccia corrente, quindi nonesistono metodi per scoprire automaticamente i nodi vicini.

Sulle reti punto-punto non c’è nessuna procedura di elezione del router designatoquindi il protocollo Hello si limita a cercare il singolo vicino.

Le reti punto-multipunto vengono gestite dal demone OSPF come se fossero tantereti punto-punto quante sono le destinazioni raggiunte.

In ogni caso, a prescindere dal tipo di rete a cui è collegata l’interfaccia, ogni voltache viene visto un Hello proveniente da un vicino viene aggiunto il corrispondenterouter ID all’elenco dei vicini del prossimo pacchetto Hello generato.

1.3.4 Cosa sono le adiacenzeUn adiacenza è un collegamento tra due router vicini che viene usato per lo scambiodei pacchetti non Hello. Mentre gli Hello infatti vengono sempre spediti verso tuttii vicini, se no perderebbero di senso, non sempre è preferibile che anche gli altri tipidi pacchetti viaggino con indirizzi broadcast. Nelle reti di transito con più di duerouter, i router che non sono (B)DR non si scambiano mai pacchetti al di fuori diquelli Hello.

Figura 1.2. Formazione delle adiacenze in una rete di transito broadcast con 5nodi. A sinistra si può notare la topologia della rete, mentre a destra c’è il graficodelle adiacenze che si vengono a formare.

Come si può notare in figura 1.2 le adiacenze si formano solo tra il DesignatedRouter e gli altri router del dominio di broadcast. I pacchetti non Hello verrannoscambiati solo ed esclusivamente lungo questi collegamenti. In una rete punto-punto

8


o in una punto-multipunto invece due router vicini sono sempre automaticamenteadiacenti.

1.3.5 Elezione del Designated Router e del suo BackupVista l’assenza di reti di transito broadcast nella rete del CSP, non si spiegherà neldettaglio l’elezione del Designated Router per non appesantire troppo la trattazione.Per completezza è comunque meglio accennare alcuni aspetti.

Non è possibile stabilire a priori quale sarà il DR di una rete, l’unica possibilità èassegnare in fase di configurazione una certa priorità all’interfaccia del router che sipreferisce come DR. Generalmente il router con la priorità più alta riesce ad essereeletto, ma non è detto che in ogni momento il DR della rete sia lui. Si può ancheimpostare la priorità a zero, in questo caso il router non si candiderà mai al ruolodi (B)DR.

La procedura di elezione parte ogniqualvolta il pacchetto Hello di un router indicache il DR (o il BDR) è 0.0.0.0, questo significa che il nodo in questione non vedepiù il DR e quindi va rifatta l’elezione. Nel caso il BDR sia ancora visibile a tutti,nel senso che è presente in tutti i pacchetti Hello, esso comincia semplicemente adannunciare se stesso come DR, mentre la procedura di elezione andrà a selezionareun nuovo BDR tra i router rimanenti.

1.3.6 Il database Link StatePrima di cominciare a spiegare nel dettaglio i pacchetti di tipo Database Descriptione gli altri tipi di pacchetti usati da OSPF (vedi 1.3.13 a pagina 13) è essenziale saperecom’è composto il database Link State dei router e come viene compilato. Questoperché essenzialmente i pacchetti OSPF diversi dagli Hello non contengono altro cherecord completi o parziali presi dai database dei router che li creano.

I record del database si chiamano Link State Announcement (abbreviato LSA),questo perché dopo essere stati creati vengono “annunciati” agli altri router tramitela procedura di flooding (vedi 1.3.15 a pagina 14). Esistono vari tipi di LSA, condiverse funzioni in base a cosa descrivono e al router che li ha generati.

1.3.7 LSA HeaderOgni LSA ha 6 campi fissi, dei quali i primi 3 servono a distinguerlo dagli altriLSA presenti nel database, cioè si potrebbe dire che fungono da “chiave primaria”,mentre gli ultimi 3 servono per poter confrontare due LSA che descrivono lo stessaentità e decidere qual’è il più recente. Questi ultimi 3 campi entrano in azione nellaprocedura di floodind (vedi 1.3.15 a pagina 14) per poter distinguere gli LSA dascartare da quelli aggiornati.

9


Questi campi tutti insieme prendono il nome di LSA Header e sono i seguenti:

1. LS Type: il tipo di LSA (vedi 1.3.8 e successive);

2. Advertising Router : il router che ha creato l’LSA;

3. Link State ID: cambia a seconda del tipo;

4. LS Age: una stima del tempo passato, in secondi, da quando è stato creatol’LSA, è un numero di 16 bit il cui valore massimo si indica con MaxAge;

5. LS checksum: un semplice checksum dell’intero LSA;

6. LS Sequence Number : indica il numero di sequenza dell’LSA, viene incre-mentato periodicamente, ma anche e sopratutto quando cambia il contenutodell’LSA.

Nelle sezioni successive si trattano nel dettaglio i vari tipi di Link State Announ-cement, da chi vengono creati, in quale zone del dominio di routing devono esserediffusi e quali informazioni contengono in aggiunta alle 6 già specificate qui.

1.3.8 Router LSAI Router LSA vengono creati da ogni router (uno per ogni area di cui il router faparte) e descrivono tutti i link che il router ha verso l’area in cui verranno diffusi.Il campo Link State ID in questo caso indica il Router ID del creatore dell’LSA,quindi è identico al campo Advertising Router.

Il resto del contenuto dell’LSA è costituito da un elenco di link, i quali possonoessere di vari tipi, e il loro costo associato. Questo costo sarà quello che andrà poia determinare le metriche nelle tabelle di routing. A ogni link, oltre al costo, sonoanche assegnati un Link ID e un Link Data entrambi di 32 bit, Se ne può vedere ilsignificato nella tabella 1.1 nella pagina seguente.

1.3.9 Network LSAUn Network LSA è creato per ogni rete di transito dal router designato della stessa.Esso elenca semplicemente tutti i nodi che si affacciano sulla rete di transito tramiteil loro Router ID. Anche questi LSA verranno diffusi dalla procedura di flooding solonell’area in cui si trova la rete di transito.

Il Link State ID di questi LSA corrisponde all’indirizzo IP che il router designatoha sulla rete, mentre la network mask della rete è specificata nel corpo dell’LSAprima della lista dei router.

10


Tabella 1.1. I vari tipi di link elencabili in un Router-LSA con relativa descrizionee significato dei campi Link ID e Link Data

Type Descrizione Link ID Link Data

1 Linkpunto-punto

Router ID del vicino Indirizzo IP dell’interfac-cia del router (se c’è)

2 Link a una retedi transito

Indirizzo IP del DRdella rete

Indirizzo IP dell’interfac-cia

3 Link a una retestub

Indirizzo IP della re-te

Address mask della rete

4 Link virtuale Router ID del vicino Indirizzo IP dell’interfac-cia

Non viene definito nessun costo nel raggiungere i vari nodi dalla rete, perché ilprotocollo assume che il costo per raggiungere un router da una rete sia uguale azero. Quindi in OSPF i costi sono solo definiti in uscita dalle interfacce dei router.

1.3.10 Summary LSAI Summary LSA vengono creati dai router di bordo area per poter descrivere airouter interni le destinazioni che loro possono raggiungere. Ne esistono di due tipi,indicati con i valori 3 e 4 del campo LS Type. I primi descrivono il costo con cuil’ABR può raggiungere una rete, i secondi descrivono il costo con cui può raggiungereun AS Boundary-Router.

Nei due casi il formato dell’LSA è identico, cambia solo il significato del campoLink State ID, che nel tipo 3 è un indirizzo qualsiasi della rete di destinazione,mentre nel tipo 4 è il Router ID dell’AS Boundary-Router a cui fa riferimento. Èanche presente un campo network mask, utile nel caso il Summary LSA sia di tipo3, che viene settato a tutti zeri negli LSA di tipo 4.

Note sulla creazione dei Summary LSA di tipo 3

Si possono impostare i router di bordo area in modo che nascondino all’area deter-minati range di indirizzi. Nella stessa maniera si può fare in modo che più rangevengano raggruppati in un unico Summary LSA, in tal caso il costo pubblicato all’in-terno dell’area sarà uguale a quello della sottorete raggiunta con il costo maggiore.Non è necessario che il range sia completamente “occupato” dalle sottoreti raggrup-pate, quindi bisogna stare attenti a non pubblicizzare all’interno dell’area delle routeche in realtà non sono raggiungibili.

11


Note sulla creazione dei Summary LSA di tipo 4

I Summary LSA di tipo 4 non vengono creati all’interno delle aree Stub e NSSA.Al loro posto invece viene sempre creato un Summary LSA di tipo 3 settato comeDefaultDestination (route 0.0.0.0/0) e metrica uguale al parametro, configurabile,DefaultCost.

1.3.11 AS-external LSA

Gli AS-external LSA, anche detti di tipo 5, vengono creati dagli AS Boundary-Routere descrivono solo le destinazioni esterne all’Autonomous System. Per questo si puòintuire che questo tipo di LSA venga diffuso in tutte le aree eccetto quelle Stub eNSSA.

Un AS Boundary-Router genera un singolo LSA di tipo 5 per ogni destinazioneesterna che ha imparato, ad esempio tramite BGP o una configurazione statica.

Le informazioni contenute in questi LSA sono l’indirizzo della rete di destinazio-ne, contenuto nel Link State ID, l’address mask e il costo del collegamento. C’è ancheun campo Forwarding Address il quale può indicare a chi consegnare direttamente ipacchetti destinati al range specificato dall’LSA corrente.

Note sulle metriche specificate negli AS-external LSA

Oltre alla metrica che indica il costo del link, è presente anche un bit che indica se lametrica è ti tipo 1 o 2. Nel caso delle metriche di tipo 1 i router dovranno sommarea tale metrica il costo del collegamento tra loro e l’AS Boundary-Router, mentre lemetriche di tipo 2 vengono usate così come sono, ignorando il costo del percorso trail router di partenza e l’AS Boundary-Router.

1.3.12 LSA speciali per le aree NSSA

Come spiegato precedentemente gli AS-external LSA non possono essere creati e/odiffusi nella aree Stub. Le aree NSSA però sono delle aree Stub speciali che possonocontenere router collegati ad altri piccoli AS (vedi area 0.0.0.5 in fig. 1.1 a pagina 6),quindi hanno la necessità di creare AS-external LSA.

Per questo gli AS BR interni ad un’area NSSA creano degli AS-external LSA ditipo “speciale”, mettendo il numero 7 al posto del 5 nel campo LS Type. Il router dibordo area poi provvederà a convertire l’LSA in uno di tipo 5 prima di diffonderlonelle altre aree[2].

12


1.3.13 Pacchetti OSPF non HelloDi seguito viene spiegata la struttura dei pacchetti OSPF Database Description (tipo2), LS-Request (tipo 3), LS-Update (tipo 4) e LS-Acnowledgement (tipo 5).

Pachetti Database Description

Adesso che sono stati trattati tutti i tipi di LSA, si possono descrivere i pacchettiDatabase Description. Come il nome stesso suggerisce, vengono utilizzati quandodue router vicini si devono descrivere a vicenda il loro database LSA, e ciò succedequando vengono create le adiacenze (vedi 1.3.14).

Il pacchetto ha una composizione molto semplice, oltre all’intestazione OSPFè presente un campo opzioni contenete i bit Initialize, Master e More, un campoSequence Number da 32 bit più un elenco indefinito di LSA Header. Il significato elo scopo di questi campi sanno chiariti nella sezione 1.3.14.

Pacchetti LS-Request

Questi pacchetti hanno una struttura semplicissima, data dal fatto che servonosemplicemente a richiedere ad un router vicino uno o più LSA dal suo database.

Il corpo del pacchetto infatti contiene semplicemente una lista di LS Type, LinkState ID e Advertising Router. Si ricorda che questi sono i 3 campi di un LSA checonsentono di individuarlo univocamente all’interno del database Link State.

Pacchetti LS-Update

I pacchetti LS-Update sono quelli che materialmente diffondono gli LSA all’internodel dominio di routing. Gli unici dati contenuti nel body del pacchetto sono un capoche indica il numero di LSA in esso contenuto e l’elenco stesso degli LSA.

Pacchetti LS-Acknoledgement

I pacchetti LS-Acknoledgement sono quelli che richiedono meno spiegazioni, conten-gono semplicemente una lista di LSA Header e servono a confermare la ricezionedegli LSA ricevuti tramite un pacchetto LS-Update.

1.3.14 Creazione delle adiacenzeCome già spiegato in precedenza (vedi 1.3.4 a pagina 8) due router sono sempreadiacenti in una rete punto-punto, mentre nelle reti di transito non è così. In ognicaso i vari router, grazie al protocollo hello (1.3.3), sono in grado di determinare conquali router è necessario formare le adiacenze.

13


Due router vicini e che si vedono a vicenda tramite i pacchetti Hello si dice chehanno un rapporto di vicinato in stato 2-Way. Nel caso si rendano conto che devonoformare un’adiacenza, perché la rete è punto-punto o perché uno dei due è il routerdesignato, lo stato dovrà passare da 2-Way a Full, che indica la sincronizzazionecompleta dei database.

Inizialmente entrambi i router si inviano a vicenda un pacchetto Database De-scription con i bit Initialize e Master settati a 1 e senza alcun LSA Header (questipacchetti DD si dicono appunto “vuoti”). A questo punto il router con il Router IDpiù alto diventa il master della comunicazione, che avviene in questo modo:

• il Master imposta il campo Sequence Number del suo pacchetto DD e inviapacchetti contenenti tutti i suoi Header LSA, finché ha pacchetti da inviare ilbit More rimane settato ad 1;

• a ogni pacchetto del Master lo Slave risponde con un suo pacchetto DD, im-postando il campo sequence number allo stesso valore del master (in questomodo il pacchetto funge anche da ack), anche lo slave tiene il bit More a 1finché ha ancora Header LSA da inviare;

• se il Master ha finito di descrivere il suo database, continua comunque a inviarepacchetti DD vuoti incrementando solo il Sequence Number finché non ha finitoanche lo Slave, e viceversa.

Una volta che i due router si son descritti a vicenda il proprio database si invianoa vicenda i pacchetti LS Request per richiedere gli LSA mancanti o non aggiornati(vedi 1.3.17 a pagina 16). Fatto ciò i router si scambiano ancora i pacchetti LS Up-date e i relativi LS Ack. Essendo la procedura studiata in modo da essere affidabile,durante la formazione dell’adiacenza ogni pacchetto deve essere ritrasmesso se non siricevono Acknowledgement entro RxmtInterval secondi (tempo impostabile su ogniinterfaccia di ogni router).

È sottinteso che se per caso i due router smettono di vedersi, entrambi o solouno dei due, per più di Router Dead Interval, allora l’adiacenza muore ancora primadi nascere.

Solo una volta che l’adiacenza ha raggiunto lo stato full i due router possomomodificare i propri LSA aggiungendovi l’adiacenza.

1.3.15 Procedura di floodingLa procedura di flooding ha lo scopo di diffondere gli LSA dal router dove sono staticreati fino a tutti i nodi dell’area di appartenenza dell’LSA. Gli AS-External LSAinvece vengono diffusi in tutte le aree escluse quelle Stub e NSSA.

Questa procedura può anche essere variata leggermente in modo da eliminare unLSA dalla rete invece che diffonderlo, in questo caso prende il nome di procedura

14


di aging (vedi 1.3.16 nella pagina seguente). In ogni caso entrambe le procedurepartono dal router che ha creato l’LSA.

Primo passo della procedura

Quando un router crea un nuovo LSA o ne aggiorna uno esistente (in tal casoincrementa il relativo Sequence Number) usa i pacchetti LS-Update per comunicarliai vicini adiacenti. I pacchetti vengono sempre spediti verso l’indirizzo multicastAllSPFRouters, tranne nelle reti di transito dove non si è (B)DR sulle quali vengonospediti a AllDRouters e sui link virtuali dove vengono spediti direttamente all’IPdell’altro capo del link.

Ogni volta che un LSA viene inoltrato su un’interfaccia bisogna incrementarneil campo Age di un numero di secondi diverso da zero (predefinito a 1) impostabile.Inoltre per ogni vicino viene tenuta traccia degli LSA già inviati e non ancor con-fermati tramite LS-Ack, e se non si riceve la conferma entro RxmtInterval secondil’LSA viene ritrasmesso solo all’indirizzo IP del vicino. Il protocollo considera come“Ack impliciti” gli LS-Update contenenti l’istanza dell’LSA di cui si stava aspettandola conferma di ricezione; comunque anche in caso di ricezione di un “Ack implicito”è prudente spedire un pacchetto LS-Ack al mittente.

Passi successivi della procedura

I router che ricevono un LSA da un’adiacenza devono confrontarlo con la copia neldatabase locale (vedi 1.3.17 nella pagina successiva) e nal caso sia più recente dellacopia locale devono diffondere l’LSA lungo le altre adiacenze. In ogni caso bisognainviare un Acknowledgement al mittente.

Casi particolari della procedura di flooding

• Se si ricevono più LSA uguali (anche solo i primi 3 campi) in un piccolointervallo di secondi chiamato MinLSArrivalSeconds, l’ultimo ricevuto vienescartato senza nemmeno controllare se è più recente dell’altro.

• Se un router riceve un LSA più vecchio della sua copia locale invia la copiaaggiornata al mittente.

• Se si riceve un LSA con il campo Age uguale al massimo, allora si manda unAck al mittente, poi, se l’LSA è presente nel database locale, si inoltra a tuttele adiacenze e ad ack ricevuto si elimina dal database.

• Se si riceve un LSA che risulta creato da se stessi, ma la copia locale o haun numero di sequenza minore o non esiste proprio, allora si crea una nuova

15


istanza dell’LSA con numero di sequenza maggiore, oppure si usa la proceduradi Aging per eliminarlo dalla rete (vedi 1.3.16).

1.3.16 Procedura di AgingLa procedura di Aging viene usata per eliminare un LSA dal dominio di routing. Ènecessario ricorrere a questa procedura anche nel caso particolare in cui il numero disequenza di un LSA ha raggiuno il valore massimo e necessita di essere “riavvolto”,in questo caso si elimina l’LSA dal dominio di routing e se ne ricrea uno con numerodi sequenza minimo.

La procedura si basa sul fatto che gli LSA con età uguale a MaxAge non vengonousati per il calcolo delle tabelle di routing, ma possono essere diffusi con la proceduradi flooding e vengono eliminati dal database Link State una volta ricevuti tutti gliAck.

1.3.17 Confrontare due LSAPoter confrontare due istanze dello stesso LSA per determinarne la più recente è unrequisito essenziale per ogni protocollo di routing, sia la formazione delle adiacenze(vedi 1.3.14 a pagina 13), che la procedura di flooding (vedi 1.3.15 a pagina 14) sibasano sulla fattibilità di questo confronto.

Il primo termine di confronto è il campo Sequence Number, l’LSA con questovalore maggiore viene considerato più recente. In caso di uguaglianza ti questotermine si va a vedere il campo Age, che è considerato in questo modo:

• se solo uno dei due LSA ha etàMaxAge, quello con questa età viene consideratopiù recente

• se il campo Age differisce di un valore maggiore di MaxAgeDiff 1, allora è piùrecente l’LSA con Age minore.

In ogni altro caso i due LSA vengono considerati uguali.

1.3.18 Impostazione del costo di un collegamentoIn OSPF le metriche vengono calcolate basandosi sui costi che ogni router impostain uscita delle sue interfacce. Questi costi in uscita vengono comunicati nei RouterLSA e sono impostati staticamente sulle interfacce

L’unica possibilità di modifica dinamica dipende dalle funzionalità del demoneche implementa il protocollo, ma nello standard (RFC 2328 ) non viene specificato

1Valore non impostabile nelle implementazioni di OSPF.

16


alcun modo per variare dinamicamente il costo di un link: o il link è funzionante econ un certo costo, oppure non è funzionante.

1.3.19 Creazione delle tabelle di routingUna volta che tutti i nodi appartenenti ad un’area hanno il database sincronizzatopossono procedere a calcolarsi tutti i percorsi minimi interni all’area con l’algoritmodi Dijkstra. Per fare questo si usano solamente i Router e i Network LSA. Que-sti percorsi vengono chiamati intra-area e le relative voci della tabella di routingvengono calcolate immediatamente dopo l’esecuzione di Dijkstra.

Successivamente si procede ad analizzare i Summary LSA, eventualmente igno-rando quelli riferiti a destinazioni interne all’area. Sommando il costo del camminofino al router di bordo area al costo pubblicato nel Summary LSA, si ottiene il costototale che permette di scegliere il percorso più breve fino a destinazione. Questeroute vengono chiamate inter-area.

L’analisi degli AS-external LSA a questo punto è immediata perché si conosconogià tutte le route per le destinazioni interne all’Autonomus System.

Intervalli di tempo nel calcolo delle tabelle di routing

Visto il fatto che il cambiamento di una metrica in un Summary LSA non causa lariesecuzione di Dijkstra, si dice che l’aggiornamento delle route inter-area è incre-mentale, perché vengono aggiornate immediatamente cambiando solo la route a cuisi riferiscono.

Il cambiamento di una metrica o di un link in un Router o in un Network LSAinvece richiede necessariamente la riesecuzione dell’algoritmo di Dijkstra, per questo:

• dopo la ricezione di un LSA di tipo 1 o 2, si aspetta sempre un certo tempo(chiamato delay), in modo che si permetta l’arrivo di altri eventuali LSA,prima del ricalcolo della tabella di routing;

• è impostabile un intervallo di tempo (chiamato hold-time) minimo che devepassare tra un calcolo della tabella di routing e il successivo.

1.3.20 Bilanciamento del carico con OSPFOSPF permette di bilanciare il traffico in uscita tra due interfacce, questo è possibilegrazie alle funzionalità del kernel linux che permettono di impostare più route perla stessa destinazione. Il bilanciamento non è implementato a livello di pacchetto,ma a livello di flusso.

17


Tutto questo viene fatto automaticamente quando per una destinazione esisto-no due percorsi possibili con la stessa metrica, questo non sempre è facilmenterealizzabile, ma comunque è una possibilità da tenere in considerazione.

1.3.21 Considerazioni sui link virtualiVista la natura “speciale” dei link virtuali, è opportuno fare alcune precisazioni aloro riguardo. La prima riguarda il fatto che i due capi del link devono sempre avereun indirizzo IP assegnato, cosa non scontata nelle reti punto-punto.

Su questi collegamenti bisogna poi stare attenti a configurare il tempo di ritra-smissione, visto che il Round Trip Time può essere molto più alto che sugli altri linkfisici.

1.4 Considerazioni finali su OSPFOSPF è un buon protocollo di routing, considerati il piccolo traffico di rete e l’altavelocità di convergenza. Presenta tuttavia alcuni difetti e alcuni aspetti a cui bisognastare attenti quando si decide di usarlo per gestire un Autonomus System.

Prima di tutto bisogna stare attenti a creare le aree, perché i percorsi intra-areavengono sempre preferiti sugli inter-area, anche se questi ultimi hanno costo minoretra gli stessi nodi di partenza e destinazione. Potrebbe capitare che non sia possibiledividere le aree in modo che tutti i percorsi siano sempre i più brevi.

Similmente al problema della divisione in aree, sempre durante la progettazionedel sistema bisogna stare attenti a fare in modo che l’area backbone sia semprecontigua. Questo è l’aspetto da mantenere in maggior considerazione, perché se nonè soddisfatto semplicemente la rete non funziona. Per fare in modo che sia così ci sipuò aiutare con i link virtuali, tenendo conto del fatto che il traffico di controllo diOSPF aumenterà inevitabilmente sul percorso del link.

1.4.1 OSPF su reti wirelessOSPFv2 è studiato apposta per reti cablate, dove solitamente i link o sono comple-tamente non funzionanti oppure non perdono nessun pacchetto.

Su una rete wireless, dove il numero di pacchetti persi dipende da una miriadedi fattori, questa visione del link causa principalmente due problematiche:

• un link può passare frequentemente dallo stato di funzionante a non fuzionante,per quel che riguarda il punto di vista di OSPF;

• il costo di un link non può essere cambiato automaticamente in base al numerodi pacchetti persi o altri parametri che indicano la qualità del collegamento.

18

Capitolo 2

Il protocollo di routing OLSR

OLSR (Optimized Link State Routing Protocol) è un protocollo di routing link staterealizzato presso l’università di Oslo.

Ha la particolarità di essere realizzato apposta per le reti wireless Ad-Hoc radio-mobili, quindi supporta alcuni tipi di metriche che servono apposta per tenere contodelle problematiche introdotte da questo tipo di reti.

2.1 Metriche ETX

OLSR è stato esteso in modo da supportare le metriche ETX (Expected TransmissionCount) le quali tengono conto della percentuale di pacchetti persi su un determinatolink wireless, questo con o scopo di massimizzare la probabilità che i pacchettitrasmessi arrivino a destinazione.

2.1.1 Calcolo delle metriche ETX

Per calcolare le metriche ETX bisogna per prima cosa contare la percentuale deipacchetti Hello che si riescono a ricevere dai vicini. Se l’intervallo di Hello è lostesso in tutta la rete allora è un calcolo molto semplice, e il valore percentualeottenuto viene chiamato LinkQuality.

È molto importante conoscere la percentuale di pacchetti persi anche nell’altradirezione (dal nodo verso i vicini), la quale viene comunicata dai vicini nei loropacchetti Hello e si chiama NeighborLinkQuality.

La moltiplicazione tra NeighborLinkQuality e LinkQuality fornisce un’indicazionesulla qualità del link in termini di pacchetti persi, quindi viene usata direttamenteper il calcolo della metrica.

19

2 – Il protocollo di routing OLSR

OLSR utilizzato con le metriche ETX non seleziona il percorso più breve perarrivare a destinazione, ma quello su cui si perdono meno pacchetti. La qualità delpercorso si ottiene facilmente moltiplicando tra di loro le qualità dei link attraversati.

2.2 Traffico di reteA differenza di OSPF, il cui traffico di gestione è molto basso, limitandosi a minu-scoli pacchetti Hello quando la situazione è “tranquilla” per poi aumentare quandobisogna comunicare le modifiche dei link ai nodi, OLSR si comporta diversamente.

In questo protocollo infatti ogni nodo invia di continuo ai vicini informazionisulle destinazioni da lui direttamente raggiungibili, e il traffico in uscita da ogninodo risulta essere praticamente invariabile qualsiasi cosa succeda.

2.3 Demone OLSRIl demone ufficiale di OLSR è sviluppato dagli stessi ideatori del protocollo1 e pre-senta un unico file di configurazione olsrd.conf, inoltre esiste un progetto che miraad aggiungere a Quagga il supporto ad OLSR2, ma al momento ha un solo svilup-patore e supporta una vecchia versione di Quagga. Oltre a non supportare ancorale metriche ETX.

2.4 Configurazione di base del demone OLSRdConfigurazione di base di un demone OLSRd (preso da www.olsr.org), su un nodocon due interfacce eth0 e eth1.

Interface "eth0" "eth1"{HelloInterval 1.0HelloValidityTime 600.0TcInterval 0.5TcValidityTime 300.0MidInterval 10.0HnaInterval 100.0HnaValidityTime 600.0}LinkQualityFishEye 0

1vedi il sito http://www.olsr.org2vedi il sito http://olsrdq.sourceforge.net/

20

http://www.olsr.org

http://www.olsr.org

http://olsrdq.sourceforge.net/

2 – Il protocollo di routing OLSR

IpVersion 4Willingness 7UseHysteresis noLinkQualityLevel 2 #indica di usare le metriche ETXPollrate 0.1TcRedundancy 2MprCoverage 1

21

Capitolo 3

Implementazioni di OSPF

In questo capitolo verranno descritte velocemente le principali implementazioni opensource del protocollo OSPF, per poi concentrarsi sull’implementazione più diffusa esupportata, cioè Quagga.

3.1 OpenOSPFd

OpenOSPFd è un’implementazione di OSPF molto diffusa, ma disponibile soltantoper il mondo BSD. Ha il pregio di essere un progetto molto semplice, in quantosi limita a supportare bene solo un protocollo di routing, a differenza delle altreimplementazioni di OSPF le quali sono delle vere e proprie suite che puntano asupportare tutti i protocolli più diffusi.

OpenOSPFd è anche ritenuto il migliore, grazie sopratutto al suo numero di lineedi codice molto esiguo (circa 12000), in termini di memoria occupata e presenza dibug[3].

3.2 BIRD

BIRD (Bird Internet Routing Daemon) è una suite di routing sviluppata dallaCharles University di Praga, implementa vari protocolli tra cui OSPF.

Presenta vari difetti, quali i pochi sviluppatori e i molti bug, però il difettoprincipale è quello di non poter cambiare al volo un’impostazione su un nodo senzadover modificare a mano i file di configurazione e riavviare il demone.

22

3 – Implementazioni di OSPF

3.3 XORPXORP (eXtensible Open Router Platform) è una suite di routing che punta a esserefacilmente estendibile per poter supportare quanti più protocolli possibile. Nono-stante a detta degli sviluppatori sia ritenuto un progetto molto ambizioso, anch’essosoffre di molti bug. Tuttavia l’implementazione di OSPF è abbastanza valida, mentrei molti bug più che altro affliggono implementazioni di altri protocolli.

Un’altra caratteristica da sottolineare è che XORP è scritto in C++ ed ha cen-tinaia di migliaia di righe di codice (oltre 600000), quindi sembrerebbe poco adattoa girare sui router rispetto ad altre suite più leggere.

3.4 QuaggaQuagga è una suite di routing nata da un fork dall’omai defunta suite Zebra. Tra isuoi punti di forza si sottolineano i fatti che ha molti sviluppatori e che è in assolutola suite di routing open source più diffusa al mondo.

Quagga presenta un demone principale, chiamato zebra, che ha il compito dimettere in comunicazione tra loro i vari demoni supportati, oltre a dover modificarela tabella di routing del kernel in base alle informazioni ricevute dai vari demoni.Zebra può anche essere usato per impostare route statiche. Il file di configurazione dizebra è molto semplice, contiene solo alcune informazioni, più che altro descrittive,delle interfacce, più eventualmente le route statiche.

Il demone OSPF si chiama semplicemente ospfd e anch’esso presenta un suo filedi configurazione, il metodo di configurazione preferibile però è usare il terminaleaccessibile tramite telnet. Questo metodo di configurazione Cisco-like (anche nellasomiglianza dei comandi) permette di configurare ospfd al volo e senza commet-tere banali errori di sintassi. Inoltre la presenza di un help in linea è molto piùpratica del dover leggersi un manuale mentre si compila un file di configurazione.Con il comando write poi si possono salvare le modifiche fatte al volo nel file diconfigurazione.

Quagga è scritto in linguaggio C. Il progetto è composto da circa 40000 righedi codice per il demone Ospfd, più 15000 righe per il demone Zebra e 35000 per lelibrerie comuni[3].

3.4.1 Configurazione del demone ZebraPer configurare il demone zebra si può agire sul file /etc/quagga/zebra.conf op-pure si accede tramite telnet alla porta 2601 (predefinita) e si entra in modalità diconfigurazione tramite i comandi enable e configure terminal. I commenti neifile di configurazione di Quagga si introducono con il carattere !.

23


Figura 3.1. La shell Cysco-like in ascolto su localhost:2604, in questo caso usatoper modificare il costo di un’interfaccia.

Di seguito un tipico file zebra.conf, si nota subito che, a parte le route statiche,la configurazione questo file non contiene niente di così fondamentale:

hostname Routerpassword zebrainterface eth0

link-detectdescription link verso Torino

interface eth1link-detectdescription link verso Milano

!Esempio di route statica (in questo caso default route)ip route 0.0.0.0/0 203.181.89.241

La definizione delle route statiche è molto scarna, infatti gli unici dati specificabilisono la route di destinazione e il gateway.

3.4.2 Configurazione del demone ospfdLa configurazione del demone ospfd può avvenire nelle stesse modalità del demonezebra, con la differenza che il file da editare si chiama ospfd.conf mentre la portapredefinita su cui è in ascolto la shell Cysco-like è la 2604.

24


Nella prima parte del file bisogna specificare le opzioni relative alle singole in-terfacce (ad esempio HelloInterval), invece nella seconda si specificano tutte leimpostazioni globali del router (Router ID, link virtuali, ecc. . . ).

Configurare le interfacce OSPF

interface ethXip ospf network point-to-point!forza ad usare l’autenticazione “sicura” MD5 su eth0ip ospf authentication message-digestip ospf message-digest-key 1 md5 password123ip ospf hello-interval 5ip ospf dead-interval 20ip ospf retransmit-interval 5!secondi da sommare al campo Age durante la spedizione dell’LSA:ip ospf transmit-delay 1

I tempi Hello Interval e Dead Interval sono già stati citati nelle specifiche, men-tre l’opzione retransmit-interval si riferisce all’intervallo di tempo che nellespecifiche è chiamato RxmtInterval (vedi 1.3.15 a pagina 15).

In questo caso si è configurato un collegamento punto-punto, ma allo stessomodo il collegamento si può impostare come point-to-multipoint, non-broadcast(cioè NBMA) oppure broadcast. Nonostante lo standard non sembrerebbe dare lapossibilità di impostare HelloInterval sotto il secondo, esiste l’opzioneip ospf dead-interval minimal hello-multiplier <2-20>la quale imposta l’Hello Interval nel pacchetto Hello a 0 secondi, il Router DeadInterval a 1 secondo e invia il numero specificato di pacchetti Hello al secondo.Questo è anche uno stratagemma che consente a nodi diversi affacciati sullo stessolink di vedersi nonostante Hello Interval non sia uguale tra tutti.

Oltre alle interfacce che si impostano in questo modo, che sono le interfaccedel router collegate agli altri router, ci sono anche le interfacce collegate alle reti“stub”, quelle che nei Router LSA vengono chiamate per l’appunto Link a una reteStub (vedi tab. 1.1 a pagina 11).

Queste interfacce si specificano in OSPF dopo la direttiva router ospf in questomodo:

router ospfpassive-interface ethX

Gli altri parametri da impostare dipendono dalla natura del router, se è sempli-cemente interno all’area, oppure se è un ABR e/o un AS BR

25


Parametri presenti in tutti i router

router ospfospf router-id 0.0.0.1log-adjacency-changes detail!si specifica a che aree appartengono le interfacce!specificando la rete a cui è collegata l’interfaccianetwork 10.0.0.4/30 area 0.0.0.1network 10.0.0.16/30 area 0.0.0.1!forza ad usare l’autenticazione message-digest MD5 sull’area 1area 0.0.0.1 authentication message-digest!da aggiungere se l’area è Stubarea 0.0.0.1 stub!da aggiungere se l’area è NSSAarea 0.0.0.1 nssa

Si noti che se l’area è Stub oppure Totally-Stub allora bisogna specificare l’opzionearea 0.0.0.1 stub anche se tale opzione interviene solo sul comportamento degliABR, mentre qui si potrebbe benissimo essere su un router interno all’area. Questoè necessario perché il campo Options del pacchetto Hello deve indicare che la rete èStub. Lo stesso discorso vale se l’area è NSSA.

Parametri esclusivi per gli Area Border Routers

router ospfospf abr-type standard!se nell’area 1 sono presenti una o più route nel range!specificato, nella backbone viene annunciato un solo LSA!con questo range:area 0.0.0.1 range 10.0.0.0/8!virtual-link attraverso l’area 1 fino al router 5area 0.0.0.1 virtual-link 0.0.0.5area 0.0.0.1 virtual-link 0.0.0.5 message-digest-key 2 md5 PWD!altri parametri del virtual linkarea 0.0.0.1 virtual-link 0.0.0.5 hello-interval 1area 0.0.0.1 virtual-link 0.0.0.5 dead-interval 5area 0.0.0.1 virtual-link 0.0.0.5 retransmit-interval 5!imposta un’area come totally-stub (dentro l’area viene!pubblicizzata solo una route di default)area 0.0.0.1 stub no-summary!costo della route di default pubblicizzata nell’area stubarea 0.0.0.1 default-cost 100

26


!area NSSA!istruisce l’ABR per convertire tutti gli LSA di tipo 7!in LSA di tipo 5 da pubblicare nella backbonearea 0.0.0.1 nssa translate-always

Il settaggio ospf abr-type standard obbliga l’ABR a comportarsi in modo stan-dard, cioè non permette l’utilizzo di percorsi inter-area che non passino per labackbone (vedi 1.2.5 a pagina 4). È possibile settare il comportamento del routercome cisco (settaggio predefinito in Quagga), in tal caso se un ABR si ritrovassesenza collegamenti con la backbone potrebbe utilizzare percorsi che passino attraver-so altre aree prima di arrivare alla backbone. Lo standard risolve questo problemacon i link virtuali.

La direttiva translate-always nell’istruzione che imposta una certa area comeNSSA impone al router di convertire sempre gli LSA di tipo 7 in LSA di tipo 5 dacomunicare nella backbone (vedi 1.3.12 a pagina 12).

Parametri esclusivi per gli AS Boundary-Routers

router ospf!redistribuisce le route specificate in zebra.conf!esclusa quella di default!redistribute static metric 100 metric-type 1!se è presente in zebra.conf, redistribuisce la!default route (0.0.0.0/0)default-information originate metric 100 metric-type 1

Al posto della direttiva static si può mettere il nome di un altro demone gestitoda Quagga, kernel oppure connected, anche se quest’ultimo caso generalmente èsconsigliato perché potrebbe portare a pubblicare più route di quelle necessarie.

27

Capitolo 4

Realizzazione dei test

I protocolli di rete sono stati testati su una topologia di rete il più possibile similealla futura rete wireless del CSP. La rete attuale non è magliata, quindi la cadutadi un link non può essere aggirata in nessun modo che non sia il ripristino del linkstesso.

Il progetto per l’ammodernamento della rete prevede l’introduzione di due anelli,come si può vedere in figura 4.1 nella pagina successiva. Lo schema è volutamenteuna semplificazione, nel senso che in realtà i nodi rappresentano gruppi di rou-ter, inoltre non comprende la parte della rete che rimarrebbe non magliata dopol’ammodernamento.

4.1 Simulatore di reti NetKitPer emulare facilmente un grande numero di router ci si è serviti del programmaNetKit1, sviluppato dall’università di Roma3. Questo simulatore utilizza UML (UserMode Linux), che è una variante del kernel Linux in grado di girare in user space.Questo fa in modo che Netkit sia estremamente leggero, requisito ideale quando sidevono emulare molti nodi. Allo stesso tempo ci sono dei limiti derivanti dal fattodi non avere a disposizione una vera e propria macchina virtuale.

Possono essere avviate molteplici istanze di UML, ognuna con un numero dischede di rete arbitrario e configurabile dall’utente tramite un semplice file di con-figurazione. Nello stesso modo ogni scheda si può “collegare” a un diverso dominiodi collisione, che si potrebbe definire come un hub virtuale.

I limiti di NetKit non permettono di modificare dall’esterno i collegamenti trauna macchina virtuale e l’altra, ad esempio eliminando il collegamento o facendoperdere una certa quantità di pacchetti, quindi per fare ciò si ricorrerà ad alcunistratagemmi che si vedranno in seguito.

1http://wiki.netkit.org

28

http://wiki.netkit.org

4 – Realizzazione dei test

Figura 4.1. La rete che si andrà a simulare nell’ambiente di test. I numeri di fiancoai nodi indicano il Router ID

Non si tratterà la configurazione di NetKit, perché è abbastanza semplice, masoprattutto perché allungherebbe inutilmente la trattazione oltre ad uscire dalloscopo del presente documento.

4.1.1 Installazione di Quagga e OLSRd su NetKit

Quagga è già installato di default nell’ultima release di NetKit fornita, peccato chenon sia una versione molto recente. Questo comunque rappresenta solo un piccoloproblema, in quanto l’implementazione di OSPFv2 ormai è consolidata. C’è solo unpiccolo bug che non permette agli AS Boundary-Router di redistribuire le route delkernel o delle reti a loro direttamente connesse, quindi si sarà costretti a configuraretali router impostando le route statiche all’interno del demone Zebra.

OLSRd per contro non è installato su NetKit, quindi è stato necessario prelevarei relativi pacchetti deb dal sito della distribuzione GNU/Linux Debian e installarlia mano sulle macchine virtuali sfruttando l’utility dpkg.

29


4.2 Configurazione di OSPF per la rete del CSPPrima di cominciare a configurare Quagga sui router, è necessario fermarsi un attimoa pensare come effettuare la divisione in aree del dominio di routing.

4.2.1 Divisione in areeEssendoci essenzialmente due anelli, la tentazione sarebbe di creare un’area peranello oppure un’unica area comprendente i due anelli.

La questione della divisione in aree va studiata bene, in quanto in molti siti disupporto, compresa la mailing list di Quagga, viene suggerito che in OSPF è sempremeglio non superare i 50 router per area. Questa affermazione però non ha nessunafonte, in realtà è un limite euristico nato con tutta probabilità in anni in cui i routeravevano capacità di elaborazione molto più limitate di adesso.

Una fonte molto autorevole che ci può dare molte informazioni in proposito è ilsito internet di Cisco [4], dove si può leggere che il numero massimo di router perarea dipende soprattutto dalla potenza del processore dei router. Il traffico OSPFinfatti non varia significativamente all’aumentare della grandezza dell’area, mentreil lavoro richiesto dall’algoritmo di Dijkstra aumenta esponenzialmente.

Sempre riguardo alla capacità di calcolo del router, viene detto di stare attenti alnumero di aree collegate a un ABR in quanto tali router devono gestire un databaseper ogni area di cui fanno parte, ma questo è un problema che riguarda solo retidecisamente grandi.

Per ridurre il carico di lavoro interno ad un’area si consiglia di usare molto le areetotally stub dove possibile, ad esempio per quei rami della rete che si affaccerannosugli anelli2. Allo stesso tempo sarebbe meglio cercare di raggruppare i range diindirizzi ip interni a queste aree, in modo che nella backbone venga comunicata unasola route, questo ridurrebbe il lavoro al di fuori dell’area.

In ogni caso è molto probabile che i router del CSP siano in grado di reggere benpiù di 50 router per area.

Scelta fatta nella simulazione

Per la simulazione è stato scelto di dividere il sistema in due aree, vale a dire unaper anello. Si sarebbe potuto scegliere un anello come area backbone e uno comearea normale, ma questo avrebbe creato un sistema in un certo senso “asimmetrico”.Quindi si sono impostati entrambi gli anelli come aree normali distinte, poi i duerouter di bordo area sono stati collegati tramite un link virtuale passante all’internodi una delle due aree. Sarebbe stato più corretto creare due link virtuali tra i due

2qui si parla di rami della rete non presenti nella simulazione, in quanto fuori dagli anelli

30


router, uno passante su un’area e uno sull’altra, ma questo cambia poco ai fini dellasimulazione.

4.2.2 Hello Interval e Router Dead Interval

I tempi Hello Interval e Router Dead Interval sono particolarmente difficili da sce-gliere su una rete wireless. Visto che il protocollo OSPF è nato per reti cablate(vedi 1.4 a pagina 18), se questi parametri vengono impostati in un certo modo sirischia di contare come non funzionante un link che tutto sommato ha una perditadi pacchetti accettabile, mentre un altro settaggio potrebbe portare a contare comevalidi dei link totalmente inutilizzabili.

Per fare qualche esempio, impostando un Hello Interval di un secondo e unRouter Dead Interval di 2 secondi si avrebbe che la perdita di un solo pacchettoHello decreterebbe la caduta del link, quindi tutta la rete si riconfigurerebbe inmodo da utilizzare un altro percorso. Se però il link fosse di buona qualità, allora idue router recupererebbero in pochi secondi l’adiacenza e il collegamento verrebbe dinuovo contato come utilizzabile dal protocollo. In questa situazione quindi si avrebbeuna forte vulnerabilità dei link ai pacchetti persi, che probabilmente garantirebbeal sistema di utilizzare solo percorsi ottimi, ma allo stesso tempo genererebbe moltotraffico di controllo se molti link si mettessero a “cadere” e “rialzarsi” con moltafrequenza.

Per contro, se si aumenta il Router Dead Interval a 3 secondi devono essere persi2 pacchetti Hello di seguito per decretare che un link sia down, quindi aumenta laprobabilità che un link inadatto venga considerato valido, ma non c’è il rischio cheuna perdita isolata di un pacchetto Hello causi il dirottamento di tutto il traffico suun altro percorso.

4.2.3 Hello Interval e Router Dead Interval sui link virtuali

Sui link virtuali si devono anche impostare i due intervalli Hello e Dead. Il valore didefault è molto alto, ed è consigliato lasciarli così. Questo perché quando un ABRviene a sapere dagli altri router che non può più raggiungere l’ABR che sta all’altrocapo del link elimina direttamente l’adiacenza, senza aspettare il Dead Interval sullink virtuale.

Avere un Hello Interval molto basso quindi non serve a niente su un link virtuale,perché l’esistenza o meno del percorso all’interno dell’area si conosce già.

31


4.3 Test su OSPFIn questa sezione si vedranno i test fatti sulla rete simulata con il protocollo OSPF.Quando si parlerà di percentuale di pacchetti persi su un link, questo dato saràriferito ai pacchetti persi in entrambe le direzioni, quindi per perdita del 50% deipacchetti si intende che viene perso il 50% dei pacchetti in una direzione e il 50%nell’altra. Nella pratica è possibile che questa percentuale non coincida nelle duedirezioni (infatti OLSR considera questa possibilità), ma facendo questa assunzionesi evita di andare a complicare di molto le simulazioni.

Per introdurre una perdita di pacchetti nelle macchine emulate con NetKit èstato usato il comando tc, che in NetKit però è stato rinominato in orig-tc, il qualepermette di eliminare una certa percentuale dei pacchetti in uscita da un’interfaccia,con il comando orig-tc qdisc replace dev ethX root netem loss X%.

4.3.1 Traffico di gestione della reteIl traffico di gestione di OSPF generalmente è molto piccolo e si limita ai pacchettiHello, che nel caso di reti punto-punto hanno una dimensione di 98 byte. Ci possonoanche essere eventualmente alcuni pacchetti LS-Update che portano rispettivamenteaggiornamenti sul cambiamento di stato di una route, se il cambiamento è avvenutofuori dall’area, oppure sul cambiamento di due Router LSA, in quanto per ognivariazione di un link all’interno dell’area vengono aggiornati i 2 Router LSA deirouter che si affacciano sul link. Questi pacchetti hanno dimensioni di circa 150byte.

Il traffico OSPF invece è maggiore sulle adiacenze in fase di formazione, cioè suquei link dove due router si vedono per la prima volta, in quanto sta avvenendo unasincronizzazione tra i due rispettivi database Link State (vedi 1.3.14 a pagina 13).Questi link però non sono usati per l’instradamento del traffico fino alla fine dellaprocedura di sincronizzazione, quindi l’unico traffico che devono poter supportare èquello di OSPF che tutto sommato è molto piccolo.

4.3.2 Tempi di reazione della rete con perdita totale deipacchetti

I tempi di reazione ai guasti in una rete gestita con OSPF sono esattamente ugualial Router Dead Interval, in quanto è dopo tale intervallo di tempo che il link inquestione viene segnalato come non funzionante. La velocità è ancora maggiore incaso di guasto di un’interfaccia del router, in quanto, a seconda del fatto se il driverè in grado o no di rilevare il guasto, il nodo potrebbe aggiornare subito il suo RouterLSA senza aspettare il Dead Interval.

32


4.3.3 Tempi di reazione della rete con perdita parziale deipacchetti

Il discorso cambia se un link non è completamente down ma perde solo una certapercentuale di pacchetti (vedi 4.2.2 a pagina 31).

In questo caso sono stati effettuati vari test per verificare come viene trattatoun link al cambiare della percentuale di pacchetti persi. In particolare sono statetestate le configurazioni con Hello Interval di 1 secondo e Router Dead Interval di2 secondi, e successivamente la configurazione è stata cambiata aumentando RouterDead Interval a 3 secondi.

Per il test è stato generato traffico costante di circa 20000 Byte/s (10 KByte/sper direzione) tra il nodi PinoT e An (vedi figura 4.1 a pagina 29), poi è stataimpostata con orig-tc una certa perdita di pacchetti sul link tra i nodi CSP e ITG.Successivamente si è catturato parallelamente il traffico in transito sul link “malato”e quello sul link “sano”34. Si può così notare che il link che perde pacchetti passacontinuamente dallo stato di pienamente adiacente a non adiacente5, quindi mentreil flusso passa su questo link perde una quantità anche considerevole di pacchetti,invece se riesce a passare sul link sano non viene perso nemmeno un pacchetto.

Test con Router Dead Interval di 2 secondi

Da questo test è emerso che percentuali di pacchetti persi anche abbastanza basse,come il 5%, fanno passare il link molto frequentemente da utilizzabile a non utiliz-zabile. C’è però il pregio che già con percentuali di pacchetti persi sul 20% il linkviene usato molto poco per trasportare il traffico.

Nelle figure 4.2 e 4.3 si può vedere il traffico rispettivamente sul link sano e sullink con perdite nel caso di una percentuale di pacchetti persi del 50%.

Nelle figure 4.4 e 4.5 vengono mostrati gli stessi grafici con perdite del 40%, sipuò notare che la situazione non cambia molto da quella con perdite del 50%, inquanto il link con perdite non viene praticamente mai utilizzato per portare traffico.

Si può notare poi che nei grafici successivi la situazione cambia radicalmente,fino ad arrivare al punto (figure 4.14 e 4.15) che il traffico passa per quasi tutto iltempo sul link dove ci sono perdite del 3% dei pacchetti.

3Link sano: PinoT - Chiaves - Turu - An;Link con perdite: PinoT - ITG - CSP - An.

4Notare che il nodo PinoT non utilizza mai il percorso tramite T3 per andare verso An, perchénel farlo uscirebbe e poi rientrerebbe nell’area 2.

5Nella documentazione di OSPF i due stati vengono chiamati 1-Way e Full.

33


Figura 4.2. Traffico sul link sano mentre sul link con perdite si perdono il 50% deipacchetti (Router Dead Interval di 2 secondi).

Figura 4.3. Traffico sul link dove vengono persi il 50% dei pacchetti (RouterDead Interval di 2 secondi).


34





35




Figura 4.10. Traffico sul link sano mentre sul link con perdite si perdono il 10%dei pacchetti (Router Dead Interval di 2 secondi).

36





37




38


Test con Router Dead Interval di 3 secondi

Nei test con Router Dead Interval di 3 secondi6 si può notare come la situazionecambi abbastanza radicalmente, infatti con basse percentuali di pacchetti persi èmolto più difficile che l’adiacenza cada, visto che bisogna perdere due pacchettiHello di seguito.

Anche in questo caso le rilevazioni di traffico sono state fatte per percentuali dipacchetti persi del 50%, 40%, 30%, 20%, 10% e 5%. Non si riportano le rilevazionicon perdite di pacchetti del 3% in quanto tutte le volte che è stata provata questasimulazione il traffico è sempre passato sul link con perdite, ed effettivamente laprobabilità di pedere due pacchetti Hello di seguito in questo caso è del 0,09%.



6Hello Interval rimasto ad 1 secondo

39





40





41





42



43


4.3.4 Tempo di formazione delle adiacenzeCome spiegato nella sez. 1.3.14 a pagina 13, il procedimento di formazione dell’a-diacenza prevede lo scambio di parecchi pacchetti, a seconda della dimensione deidatabase dei router. Solo alla fine di questa procedura il link su cui si è formatal’adiacenza può essere usato per inoltrare il traffico della rete.

Le adiacenze si formano in tempi molto rapidi, nella rete di test di fig. 4.1 apagina 29 ad esempio in meno di un secondo. Al crescere della dimensione della retecomunque questo tempo dovrebbe rimanere basso perché il tempo che intercorre trala ricezione di un pacchetto e la trasmissione della risposta è molto basso.

Se però questa procedura, studiata apposta in modo che ogni pacchetto sial’acknowledgement del precedente, si interrompe a causa di un pacchetto perso, l’a-diacenza impiegherà più tempo a formarsi in misura dell’impostazione di RxmtInterval7.Perché questo è il tempo che viene aspettato da chi ha trasmesso un pacchetto perricevere l’Ack.

Se inoltre durante questo procedimento vengono persi alcuni pacchetti Hello,nel caso venga sforato il limite Router Dead Interval l’adiacenza ritorna nello sta-to 1-Way e il processo deve ricominciare da capo. Per questo all’aumentare deipacchetti persi su un link aumenta anche il tempo necessario perché si riformi unadiacenza.

4.4 Test su OLSROLSR dovrebbe comportarsi meglio di OSPF sulle reti senza fili, questo perché graziealle metriche ETX dovrebbe essere di volta in volta essere selezionato il percorsocon meno perdite di pacchetti.

4.5 Configurazione del demoneLa configurazione di ogni nodo è quella di default, visibile nella sez. 2.4 a pagina 20.Hello Interval impostato ad 1 secondo, TC Interval a mezzo secondo e MPR Cove-rage a 1. Quest’ultimo parametro va impostato a un intero maggiore di 0 tanto piùgrande quanto i nodi sono in movimento8, in questo caso i nodi sono fissi quindi 1va bene.

In passato bisognava anche specificare la grandezza di una finestra di ricezione,in quanto la qualità dei link veniva calcolata sulla base degli ultimi n pacchetti Helloricevuti e non. Dalla versione 0.5.6-rc7 del demone olsrd (attualmente siamo alla6.0) questa funzionalità sembra essere deprecata, anche se la notizia non si trova

7In Quagga questo intervallo è chiamato retransmit-interval.8Si ricorda che OLSR è un protocollo per reti radiomobili

44


sul changelog ufficiale del progetto ma su siti di progetti che al loro interno usanoolsrd[5].

4.5.1 Traffico di gestione della reteCome si è già detto nella sez. 2.2 a pagina 20 OLSR ha per sua natura un traffico digestione maggiore di OSPF. Con la configurazione scelta ogni nodo OLSR emetteda ogni sua interfaccia 2 pacchetti grandi circa 500-600 byte al secondo, quindi iltraffico è molto maggiore rispetto al traffico medio di OSPF (1000 Byte/s contro100 Byte/s).

4.5.2 Tempi di reazione della reteOLSR, almeno nelle configurazioni provate, è risultato essere molto lento nel reagireal cambio di qualità dei link.

Sia in caso di caduta totale del collegamento, sia con qualsiasi percentuale diperdita dei pacchetti, OLSR ha impiegato sempre almeno 25 secondi a selezionare ilpercorso migliore. In alcuni casi, sopratutto con percentuali di pacchetti persi sottoil 50%, i tempi sono stati molto più alti, e in qualche occasione si è continuato adusare il percorso peggiore senza che il protocollo riuscisse a selezionare il percorsodove non c’erano perdite di pacchetti.

Per completezza è stata provata anche una vecchia versione di olsrd (la 0.5.6rc7),la quale permetteva ancora di impostare la finestra di ricezione su cui calcolare laqualità del link. Tale finestra è stata impostata a 20 pacchetti Hello, cioè 20 secondi,ma la situazione non è cambiata.

45

Capitolo 5

Conclusioni

Il protocollo OSPF si è rivelato abbastanza inadeguato alle reti wireless, in quantonon è in grado di rilevare la qualità dei link e di cambiare le metriche di conseguenza.

5.1 Soluzioni propostePer risolvere questo problema si potrebbero realizzare delle soluzioni tampone, nelsenso che non intervengono sul protocollo, ma che potrebbero essere abbastanzasemplici da realizzare.

Ad esempio si potrebbe realizzazione uno script che testi periodicamente il nume-ro di pacchetti persi sul link e nel caso sia necessario modifichi i costi delle interfaccesfruttando il fatto che Quagga può essere configurato al volo.

Una soluzione più semplice, ma peggiore, potrebbe essere quella di disattivareOSPF sulle interfacce dove il numero di pacchetti persi supera una certa soglia, eriattivarlo quando la situazione rientra nella normalità.

Un altro tipo di soluzione è estendere il protocollo in modo che supporti lemetriche ETX, o comunque un altro tipo di metriche pensate per le reti wireless,questa è la soluzione adottata attualmente dai router Cisco[6].

5.2 Sviluppi futuriMentre i costruttori di router come Cisco hanno già trovato soluzioni al problema,anche lo standard si sta evolvendo, proprio per inseguire le soluzioni di Cisco.

Le estensioni future al protocollo OSPF verranno sviluppate solo per OSPFv3,inizialmente nato solo per reti IPv6, in quanto è stato recentemente proposto unostandard (RFC 5838) che permetterà a OSPFv3 di supportare anche reti IPv4[7].

Inoltre è in fase di definizione un’estensione di OSPFv3 pensata per le reti Ad-Hoc radiomobili (RFC 5614)[8]. Gli autori di questa estensione, tra i quali c’è

46

5 – Conclusioni

la Boeing, stanno sviluppando insieme alla marina militare degli Stati Uniti unavariante di Quagga in grado di supportare questa estensione[9]. Anche se questavariante di Quagga è stata rilasciata molto recentemente (maggio 2011), lo statodello sviluppo sembra essere abbastanza avanzato in quanto le release note indicanoche vengono implementate entrambe le RFC 5614 e 5838. Inoltre l’implementazioneva leggermente oltre l’RFC perché implementa anche formule per il calcolo dellemetriche che tengono conto di più fattori oltre al numero di pacchetti persi, comela banda totale teorica del link e la banda effettiva del link.

Potrebbe essere interessante testare a dovere questa variante di Quagga.

47

Appendice A

Pacchetti OSPF

In questa appendice verranno presentati gli schemi dei pacchetti OSPFv2 così comecompaiono nella reference RFC 2328[1]. Il significato dei campi dei pacchetti è giàstato spiegato nella sez. 1.3 a pagina 5.

A.1 Pacchetti

A.1.1 Pacchetto Hello0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Version # | 1 | Packet length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Router ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Area ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Checksum | AuType |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Network Mask |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| HelloInterval | Options | Rtr Pri |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

48

A – Pacchetti OSPF

| RouterDeadInterval |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Designated Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Backup Designated Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Neighbor |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

A.1.2 Pacchetto Database Description

0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Version # | 2 | Packet length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Router ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Area ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Checksum | AuType |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Interface MTU | Options |0|0|0|0|0|I|M|MS+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| DD sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| |+- -+| |+- An LSA Header -+| |+- -+| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

49


A.1.3 Pacchetto LS-Request0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Version # | 3 | Packet length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Router ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Area ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Checksum | AuType |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS type |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

A.1.4 Pacchetto LS-Update0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Version # | 4 | Packet length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Router ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Area ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Checksum | AuType |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |

50


+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| # LSAs |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LSAs |+-+ ... +-+| |

A.1.5 Pacchetto LS- Acknowledgement0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Version # | 5 | Packet length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Router ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Area ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Checksum | AuType |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Authentication |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| |+- An LSA Header -+| ... |

A.2 LSA

A.2.1 LSA Header0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS age | Options | LS type |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

51


| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS checksum | length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A.2.2 Router LSA

0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS age | Options | 1 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS checksum | length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| 0 |V|E|B| 0 | # links |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Data |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type | # TOS | metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| TOS | 0 | TOS metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Data |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

52


A.2.3 Network LSA0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS age | Options | 2 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS checksum | length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Network Mask |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Attached Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

A.2.4 Summary LSA0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS age | Options | 3 or 4 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS checksum | length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Network Mask |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| 0 | metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| TOS | TOS metric |

53


+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

A.2.5 AS-External LSA0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS age | Options | 5 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link State ID |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Advertising Router |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS sequence number |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| LS checksum | length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Network Mask |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|E| 0 | metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Forwarding address |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| External Route Tag |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|E| TOS | TOS metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Forwarding address |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| External Route Tag |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| ... |

External Route Tag non è stato spiegato perché non viene usato dal protocolloOSPF

54

Appendice B

NetKit

NetKit (http://wiki.netkit.org) è il simulatore di reti usato per effettuare itest. Le macchine virtuali possono essere collegate in rete tra loro oppure anche allamacchina reale attraverso un’interfaccia tap.

B.1 RequisitiNetKit funziona anche su computer molto poco potenti e con relativamente pocaram, anche solo 256 MB. L’unico requisito riguarda l’utilizzo su sistemi operativi a 64bit, essendo NetKit compilato a 32 bit, bisogna installare le librerie per poter eseguiresoftware a 32 bit (libc6-i386 e ia32-libs sono nominate nella documentazione).

B.2 InstallazionePer l’installazione bisogna procurasi da http://wiki.netkit.org/index.php/Download_Official i componenti:

• Core: contiene i comandi e un po’ di documentazione;

• File System: contiene il file system delle macchine virtuali;

• Kernel: contiene il kernel che verrà eseguito in user space per far funzionarele macchine virtuali.

Nei test sono state utilizzate rispettivamente le versioni 2.8 per il Core e il Kernel ela versione 5.2 del File System. Ognuno dei 3 componenti può avere un numero diversione differente.

I file vanno scompattati nella stessa directory, verrà creata una directory netkit.È molto impostante usare un file system che supporti i file sparsi (EXT3/4 vanno

55

http://wiki.netkit.org

http://wiki.netkit.org/index.php/Download_Official

http://wiki.netkit.org/index.php/Download_Official

B – NetKit

bene, ma ad esempio JFS e XFS no), e mentre si scompattano i file passare alcomando tar anche il parametro S che attiva il supporto ai file sparsi.

Se non si fa questo, ogni macchina virtuale occuperà 10 GB di disco.Si ricorda che NetKit usa UML (User Mode Linux), un kernel eseguito in user

space che assomiglia a una macchina virtuale, ma di fatto non si può deciderel’hardware da emulare quindi non è un vero emulatore.

B.2.1 Configurazione post-installazioneBisogna aggiornare la variabile di sistema PATH, più crearne un paio di nuove, perquesto si possono usare i comandi:

export NETKIT_HOME=/home/foo/netkitexport MANPATH=:$NETKIT_HOME/manexport PATH=$NETKIT_HOME/bin:$PATH

Aggiungere eventualmente questo comando al proprio file di configurazione dellashell (.bashrc nel caso di shell bash). Si può controllare la correttezza di questaconfigurazione entrando nella cartella di netkit ed eseguendo lo script:./check_configuration.sh

B.3 Comandivstart fa partire una singola macchina virtuale;vhalt arresta una singola macchina virtuale;lstart avvia un intero laboratorio o singole macchine che ne fanno parte;lhalt arresta un intero laboratorio o singole macchine che ne fanno parte;

B.4 Creare un laboratorioLe reti simulate in NetKit si chiamano laboratori. Per crearne uno bisogna creareuna directory vuota per ogni macchina virtuale da far partire con il nome dellamacchina virtuale. Bisogna anche creare un file di configurazione del laboratoriolab.conf che contiene la descrizione della topologia della rete e i parametri dapassare alle macchine virtuali. Per ogni macchina virtuale poi si può creare unfile nome_macchina.startup che contiene le istruzioni da eseguire sulla macchinavirtuale al suo avvio.

Tutti questi file, e le cartelle vuote con i nomi delle macchine virtuali, devonoessere messe in una cartella che sarà la cartella del laboratorio.

56

B – NetKit

B.4.1 File lab.confNel file ogni riga ha una sintassi del tipo nome_macchina[parametro] = valore

Se come parametro viene scritto un numero, quel numero indicherà una schedadi rete ethX (dove X è il numero) e il valore indicherà il nome di uno switch virtualea cui la scheda è collegata.

Se il parametro non è un numero, allora è un parametro della macchina virtuale(vedere man vstart), ad esempio la memoria ram della macchina emulata.

Per le periferiche tap vedere la pagina di manuale di vstart.

B.4.2 Esempio di file lab.confSi prende il file lab.conf usato per la rete in fig. 4.1 a pagina 29.

an[0]=n7an[1]=n6anonimo[mem]=256

csp[0]=n6csp[1]=n4csp[2]=n10csp[3]=n3csp[4]=tap,192.168.0.1,192.168.0.3csp[mem]=256

vg[0]=n10vg[1]=n15vg[2]=tap,192.168.0.1,192.168.0.2vg[mem]=256

itg[0]=n3itg[1]=n2itg[mem]=256

pinot[0]=n2pinot[1]=n1pinot[2]=n9pinot[mem]=256

t3[0]=n4t3[1]=n1

57

B – NetKit

t3[2]=n5t3[mem]=256

chiaves[0]=n9chiaves[1]=n8chiaves[mem]=256

turu[0]=n7turu[1]=n8turu[mem]=256

calvo[0]=n5calvo[1]=n11calvo[mem]=256

morra[1]=n11morra[0]=n12morra[mem]=256

alb[0]=n12alb[1]=n13alb[mem]=256

sup[0]=n13sup[1]=n14sup[mem]=256

tb1[0]=n14tb1[1]=n15tb1[mem]=256

B.4.3 Esempio di file .startupNella simulazione della rete HPWNet i file nome_macchina.startup sono stati usatiper configurare all’avvio gli indirizzi delle macchine virtuali ed avviare il demoneQuagga.

Di seguito il sile csp.startup del laboratorio che riproduce la rete in fig. 4.1 apagina 29.

#file startup della macchina CSPip addr add 10.0.0.6/30 dev eth0 brd +

58

B – NetKit

ip link set eth0 upip addr add 10.0.0.9/30 dev eth1 brd +ip link set eth1 upip addr add 10.0.0.13/30 dev eth2 brd +ip link set eth2 upip addr add 10.0.0.17/30 dev eth3 brd +ip link set eth3 upip addr add 192.168.1.2/24 dev eth4 brd +ip link set eth4 up/etc/init.d/quagga start

B.5 Trasferimento file tra macchina virtuale e hostPer trasferire i file tra macchine virtuali e macchina host si possono sfruttare lecartelle /hosthome e /hostlab in ogni macchina virtuale. La prima punta allacartella home dell’utente che ha in esecuzione la macchina virtuale, la seconda allacartella che contiene il laboratorio virtuale.

59

Appendice C

Esempi file di configurazioneQuagga

Alcuni file di configurazione presi dalla rete emulata di fig. 4.1 a pagina 29.Dove le linee finiscono con il segno %, significa che la linea era troppo lunga e

continua sulla successiva.

C.1 File zebra.confFile zebra.conf della macchina CSP ( 4.1 a pagina 29).

hostname Routerpassword zebralog file /var/log/quagga/zebra.log!interface eth0description link verso anonimolink-detect!interface eth1description link verso T3link-detect!interface eth2description link verso VGlink-detect!interface eth3description link verso ITG

60

C – Esempi file di configurazione Quagga

link-detect!interface eth4!interface lo!interface teql0ipv6 nd suppress-ra!ip forwarding!ip route 0.0.0.0/0 192.168.0.1!line vty

C.2 File ospfd.conf

C.2.1 Router internoFile ospfd.conf del router interno Morra ( 4.1 a pagina 29).

hostname ospfdpassword zebralog file /var/log/quagga/ospfd.log!interface eth0ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf hello-interval 1ip ospf dead-interval 3ip ospf retransmit-interval 3!interface eth1ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf hello-interval 1ip ospf dead-interval 3ip ospf retransmit-interval 3

61


!interface lo!interface teql0!router ospfospf router-id 0.0.0.10log-adjacency-changes detailnetwork 10.0.0.40/30 area 0.0.0.1network 10.0.0.44/30 area 0.0.0.1area 0.0.0.1 authentication message-digest!line vty

C.2.2 Area Border Router con Link VirtualeFile ospfd.conf del router ABR T3( 4.1 a pagina 29).

hostname ospfdpassword zebralog file /var/log/quagga/ospfd.log!!!interface eth0ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf cost 10ip ospf hello-interval 1ip ospf dead-interval 3ip ospf retransmit-interval 3!interface eth1ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 2 md5 area2ip ospf hello-interval 1ip ospf dead-interval 3ip ospf retransmit-interval 3!

62


interface eth2ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf hello-interval 1ip ospf dead-interval 3ip ospf retransmit-interval 3!interface lo!router ospfospf router-id 0.0.0.2ospf abr-type standardlog-adjacency-changes detailnetwork 10.0.0.8/30 area 0.0.0.1network 10.0.0.36/30 area 0.0.0.1network 10.0.0.24/30 area 0.0.0.2area 0.0.0.0 authentication message-digestarea 0.0.0.1 authentication message-digestarea 0.0.0.2 authentication message-digestarea 0.0.0.1 virtual-link 0.0.0.1 hello-interval 10 retransmit-interval 5 %transmit-delay 1 dead-interval 40area 0.0.0.1 virtual-link 0.0.0.1 message-digest-key 1 md5 area1virtual!line vty

C.2.3 AS Boundary Router interno a un areaFile ospfd.conf del router AS Boundary Router VG( 4.1 a pagina 29).

hostname ospfdpassword zebralog file /var/log/quagga/ospfd.log!interface eth0ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf hello-interval 1ip ospf dead-interval 3!

63


interface eth1ip ospf network point-to-pointip ospf authentication message-digestip ospf message-digest-key 1 md5 area1ip ospf hello-interval 1ip ospf dead-interval 3!interface eth2!interface lo!interface teql0!router ospfospf router-id 0.0.0.3log-adjacency-changes detailredistribute staticnetwork 10.0.0.12/30 area 0.0.0.1network 10.0.0.56/30 area 0.0.0.1area 0.0.0.1 authentication message-digestdefault-information originate metric 100 metric-type 1!line vty

64

Bibliografia

[1] J. Moy - Ascend Communications Inc., RFC 2328: OSPF Version 2, http://tools.ietf.org/html/rfc2328, April 1998.

[2] P. Murphy, RFC 3101: The OSPF Not-So-Stubby Area (NSSA) Option, http://tools.ietf.org/html/rfc3101, January 2003.

[3] Claudio Jeker, Internet Business Solutions AG, Design and Implementation ofOpenOSPFD, www.networx.ch/OpenOSPFD-Paper.pdf

[4] Cysco Systems, OSPF Design Guide, http://www.cisco.com/en/US/tech/tk365/technologies_white_paper09186a0080094e9e.shtml, August 2005

[5] Freifunk Firmware Changelog,http://ipkg.berlin.freifunk.net/ChangeLog, August 2008.

[6] Cysco Systems, OSPFv3 Dynamic Interface Cost Support, http://www.cisco.com/en/US/docs/ios/12_4t/12_4t15/odics_ST.html, 2007

[7] A. Lindem - Ericsson, S. Mirtorabi, A. Roy, M. Barnes - Cisco Systems, R.Aggarwal - Juniper Networks, RFC 5838: Support of Address Families in OSPFv3,http://tools.ietf.org/html/rfc5838, April 2010.

[8] R. Ogier - SRI International, P. Spagnolo - Boeing, RFC 5614: Mobile Ad HocNetwork (MANET) Extension of OSPF Using Connected Dominating Set (CDS)Flooding, http://tools.ietf.org/html/rfc5614, August 2009.

[9] P. Spagnolo, Release Notes for the Mobile Routing variant of Quagga,http://downloads.pf.itd.nrl.navy.mil/ospf-manet/quagga-0.99.17mr2.0/RELEASE_NOTES.MobileRouting, May 2011

65

http://tools.ietf.org/html/rfc2328




www.networx.ch/OpenOSPFD - Paper.pdf

http://www.cisco.com/en/US/tech/tk365/technologies_white_paper09186a0080094e9e.shtml

http://www.cisco.com/en/US/tech/tk365/technologies_white_paper09186a0080094e9e.shtml

http://ipkg.berlin.freifunk.net/ChangeLog

http://www.cisco.com/en/US/docs/ios/12_4t/12_4t15/odics_ST.html

http://www.cisco.com/en/US/docs/ios/12_4t/12_4t15/odics_ST.html



http://downloads.pf.itd.nrl.navy.mil/ospf-manet/quagga-0.99.17mr2.0/RELEASE_NOTES.MobileRouting

http://downloads.pf.itd.nrl.navy.mil/ospf-manet/quagga-0.99.17mr2.0/RELEASE_NOTES.MobileRouting

Algoritmi di routing in reti magliate wireless

Documents

Transcript of Algoritmi di routing in reti magliate wireless