OLSR

Da Skypedia.

Il protocollo OLSR (Optimized Link State Routing Protocol) è un protocollo di routing dinamico di tipo proattivo per reti mobili ad hoc. In un algoritmo proattivo viene mantenuta la topologia di tutta la rete, aggiornandola ad intervalli fissati di pochi secondi. Tutti i nodi sanno come raggiungere ogni altro nodo ad ogni istante e questo facilita l'instradamento dei pacchetti in ogni parte della rete evitando dei tempi di attesa che sarebbero richiesti in un algoritmo di tipo reattivo. Tutto ciò comporta però un continuo scambio di messaggi sulla topologia della rete e sull'evoluzione di quest'ultima per aggiornare periodicamente le tabelle di routing contenute in ogni nodo della rete.

OLSR eredita la sua stabilità dall'algoritmo Link State, ma ottimizza l'utilizzo della banda e cerca di minimizzare il pericolo di collisioni di pacchetti abbassando il flooding broadcast per il Topology Control (TC). Nell'algoritmo Link State classico i nodi si scambiano informazioni effettuando dei broadcast e si ricostruiscono localmente l'intera topologia (grafo) della rete. In pratica ogni nodo eseguiva il flooding periodico delle informazioni su tutta la rete per far sì che si propagasse su ogni nodo la conoscenza della topologia del network. L'algoritmo implementato e' quello di Dijkstra.

OLSR diminuisce la dimensione dei pacchetti TC inviando solo le informazioni su un ristretto numero di nodi vicini al nodo comunicante. Questo set di nodi prende il nome di MPR (Multipoint Relays) set. I nodi eletti come MPR hanno poi il compito di propagare in flooding l'informazione topologica e devono avere dei collegamenti bidirezionali verso i nodi vicini di un "salto" (1 hop neighbors.

Questo protocollo risulta particolarmente indicato per reti a larga scala e con alto coefficiente di clustering (reti dense). In un tale scenario un protocollo di tipo reattivo, che elegga dei "supernodi" per il controllo della topologia e il flooding, ha delle prestazioni che consentono di rendere una rete di questo tipo stabile. Ogni nodo della rete, infatti, invia periodicamente i propri messaggi di controllo e riesce a sostenere la perdita di pacchetti che può avvenire in certi intervalli temporali, perdita dovuta all'evoluzione della topologia stessa della rete e alla redistribuzione dei set MPR. Si dice inoltre che OLSR effettui un rounting "hop by hop", cioè salto dopo salto attraverso i nodi per la ricerca della destinazione di un dato pacchetto.

MANET

Rete MANET
Una rete mobile ad hoc viene chiamata MANET (Mobile Ad hoc NETwork). Essa è costituita da un insieme di nodi connessi tramite wireless links che mantengono una struttura topologica che risulta essere dinamica, data la mobilità dei nodi che la compongono. La dimensione fisica di una rete MANET dovrebbe essere più grande di quella che è la copertura wireless di ogni nodo che compone la rete, così da rendere necessario mettere in comunicazione nodi diversi attraverso degli algoritmi di routing che costruiscano percorsi formati da due o più salti (multi-hop path discovery).

Oltre a dover mantenere le classiche caratteristiche di routing delle reti cablate, un algoritmo di routing per le reti MANET deve mantenere un alto grado di risposta verso cambiamenti topologici e riuscire a mantenere un instradamento dei pacchetti stabile. Inoltre un protocollo di questo tipo deve tener conto delle stringenti caratteristiche di una rete MANET in termini di larghezza di banda, capacità di calcolo dei singoli apparati di rete e di consumo energetico degli stessi.

Reti MANET e Reti Mesh

Schema di una rete mesh
Bisogna distinguere le reti mesh dalle MANET. Nelle MANET si ipotizza che tutti i nodi siano mobili e che la topologia di rete sia in continua evoluzione, mentre nelle mesh networks i nodi sono generalmente SOHO router statici (freifunk).

Normalmente si ricade nelle mesh networks non tanto per problemi relativi al protocollo di routing ma per problemi relativi alle possibilità degli attuali dispositivi mobile. Potremmo affermare che una rete MANET è una rete pura, cioè fatta da soli dispositivi mobili che si appoggiano ad una rete ad-hoc, mentre una rete mesh è una rete ibrida che tende ad associare diversi cluster tramite injection links tra gateway di rete che forniscono anche un bridge alla rete WAN e Internet.

Reti Manet


Le caratteristiche delle MANET

  • Operating without a central coordinator
  • Multi-hop radio relaying
  • Frequent link breakage due to mobile nodes
  • Constraint resources (bandwidth, computing power, battery lifetime, etc.)
  • Instant deployment

I tipi di messaggio

OLSR utilizza pacchetti UDP per trasferire le informazioni di controllo, ogni pacchetto può contenere più di un messaggio, proveniente da mittenti differenti, per meglio sfruttare il tempo di trasmissione.

I messaggi richiesti dalla funzionalità base di OLSR sono:

  • HELLO: inviati ad intervalli regolari, compiono le funzioni di rilevamento dei vicini, comunicazione dei nodi MPR e link sensing
  • TC: servono a comunicare informazioni topologiche dal punto di vista di ogni nodo
  • MID: usati dai nodi con piu` interfacce per dichiararne l’esistenza al resto della rete.

Per evitare che i nodi compiano trasmissioni sincronizzate (e quindi che i pacchetti collidano sulla rete provocando uno storm), l’RFC stabilisce che prima di ogni invio un nodo debba aspettare un tempo casuale.

Multipoint Relays

Selezione MPR
Ogni nodo nella rete riceve informazioni cadenziate da parte dei suoi vicini più prossimi, ma ritrasmette tali informazioni solo se esso risulta essere nel set MPR di quello stesso nodo. Ciò riduce il carico della rete e consente di evitare il flooding di messaggi di controllo. Ogni nodo seleziona il suo set MPR in modo tale che questo cada all'interno di un insieme di stazioni visibili "ad un solo salto" e ognuna di essa sia in grado di avere una comunicazione bidirezionale con nodi che risultano ricadere nell'insieme di nodi raggiungibili in due salti. Per effettuare questo calcolo ogni nodo invia dei messaggi di HELLO che contengono delle tabelle con i nodi visibili immediatamente dal nodo che invia il messaggio stesso. In tal modo, ad ogni ricezione di tali messaggi, i nodi riceventi possono controllare se ci sia o meno una comunicazione bidirezionale e quali nodi possano essere eletti nel set MPR.Questi messaggi vengono inviati ad intervalli regolari e servono a mantenere il controllo del link sensing.

Gli MPR costituiscono i ricettori e i propagatori di messaggi di controllo della rete e sono gli unici che possano ritrasmettere in broadcast tali messaggi in modo da mettere a conoscenza i nodi nel loro raggio di copertura della presenza di nodi 2-hop.

Link sensing

Ogni messaggio HELLO, come detto, serve a comunicare la propria presenza sulla rete e al contempo a condividere la propria tabella di link simmetrici e asimmetrici. Un link viene detto simmetrico quando un nodo riceve da un altro già presente nella propria tabella di routing un messaggio HELLO che contenga il proprio indirizzo. Con questa tecnica si riesce a confermare la presenza di un collegamento bidirezionale che viene mantenuto finché si ricevono messaggi HELLO che lo confermino. Un link asimmetrico è un link monodirezionale che non riceve conferma da un nodo 1-hop. Se dunque un nodo a riesce a ricevere i messaggi di b, b non è in grado di ricevere i messaggi di a. In questo caso l'algoritmo tenta di trovare un MPR che possa mettere in congiunzione i due nodi e rendere possibile la comunicazione bidirezionale.

Topology Control

Ogni nodo che abbia un MPR selector set (insieme dei nodi che hanno scelto questo come MPR) non vuoto provvede a inviare messaggi di controllo di topologia (TC-messages) periodicamente. Ogni TC-message contiene l'indirizzo del nodo generatore del messaggio e il set MPR di quest'ultimo in modo tale da propagare, settore per settore, l'informazione topologica - parziale - della rete e la presenza di nodi MPR. Con questa tecnica si riesce a calcolare un algoritmo di shortest path per il calcolo delle optimal routes. Questa tecnica di broadcast dell'informazione topologica sull'intera rete è simile al link state routing di ARPANET.

La tabella di routing

Ogni nodo mantiene una routing table che gli consente di inviare un dato pacchetto ad una data destinazione. I nodi che ricevono un TC message non fanno altro che salvare un collegamento [ultimo-salto, nodo], dove "nodo" corrisponde all'indirizzo trovato nel messaggio TC.

Se si vuole contattare un nodo remoto R si calcola in modo discendente il percorso migliore con una lista di collegamenti a ritroso del tipo:

  • [X,R]
  • [Y,X]
  • [W,Y]

Fino a trovare un collegamento tra il nodo di origini e l'insieme dei vicini di W. Fatto ciò si invia il pacchetto e la route da seguire per propagarlo nella rete. Ovviamente il percorso di route viene ricalcolato dinamicamente allorquando la rete assuma un'altra topologia durante i vari salti.

The proposed heuristic for route calculation in RFC3626 is a relatively trivial shortest-path algorithm. It can be outlined as:

  1. Add all one hop neighbors registered as symmetric to the routing table with a hop-count of 1.
  2. For each symmetric one-hop neighbor, add all two hop neighbors registered on that neighbor that has:
    • Not already been added to the routing table.
    • A symmetric link to the neighbor.
    These entries are added with a hop-count of two and next-hop as the current neighbor.
  3. Then, for every added node N in the routing table with hop-count n = 2 add all entries from the TC set where:
    • the originator in the TC entry == N
    • the destination has not already been added to the routing table
    New entries are added with a hop-count of n + 1 and next-hop as the next-hop registered on Ns routing entry.
  4. Increase n with one and do step 3 over until there are no entries in the routing-table with hop-count == n + 1
  5. For all entries E in the routing table the MID set is queried for address aliases. If such aliases exist an entry is added to the routing table with hop-count set to Es hop-count, and next-hop set to Es next-hop for every alias address.
Schema di funzionamento di OLSR

Le implementazioni

Esistono diverse implementazioni di OLSR sviluppate da enti differenti, università e ricercatori. La INRIA ha sviluppato OOLSR in C++, il Laboratorio di Ricerche Navali degli Stati Uniti sta lavorando a NROLSR e il Laboratoire de Recherche en Informatique dell'Università di Parigi-sud lavora all'implementazione di QOLSR (QoS + OLSR).

Cross-compilazione di olsrd per Android

Per effettuare la cross-compilazione ed ottenere un eseguibile di olsrd funzionante per ARM, è necessario seguire questi semplici passi:

  1. Scarica il file contenente l'NDK (Native Development Kit)
    • Nel Makefile.android dell'ultima release (0.5.6-r7) viene richiamata la versione 1.5-r1, e per compatibilità è preferibile usare quella.
  2. Estrai il contenuto dell'NDK nella cartella /usr/src/
  3. Scarica i sorgenti di olsrd
  4. Estrai i sorgenti e compila con make, passando la piattaforma utilizzata:
    • $ make OS=android build_all

All'interno della cartella dei sorgenti è possibile trovare l'eseguibile olsrd, e olsr_switch, compilati per Android.

References