[Ninux-Calabria] ODG 10 Dicembre 20013

[Giuseppe De Marco]

Scrivo due note, così evitiamo di ripeterle durante la riunione.
Sono note che poi potranno essere spese per una futura nostra
documentazione.

ROUTING

Due parole sui protocolli papabili. Vi è inoltre la volontà di
formalizzare/documentare per le newentry.

OLSR è un protocollo Link-State e Proattivo (table-driven).
Il link-state (routing basato sullo stato del collegamento) utilizza il
concetto di mappa distribuita, ossia un elenco di tutti i link della rete
con relativo costo. Tutti i routers hanno una copia di tale mappa che viene
aggiornata in continuazione


Ogni nodo, periodicamente, usa la tecnica del flooding, chiamata in
questo caso Link State Broadcast, per inviare a tramite tutti i suoi
link diretti un messaggio Link State Packet (LSP), contenente tutte le
informazioni sui link tra il mittente del messaggio e tutti i suoi vicini.
Alla ricezione di tale messaggio, ogni router, aggiorna la propria routing
table e lo rispedisce a tutti i suoi vicini diretti tranne quello da cui
arriva tale
messaggio.

In questo modo tutti i routers hanno sempre memorizzata la mappa della rete
aggiornata in una struttura ad albero ed il cammino più conveniente si
ottiene con un algoritmo shortest path ( vedi Dijkstra ).

Il fatto che OLSR sia table-driven (ovvero guidato da tabelle di scambio)
ha un vantaggio e uno svantaggio:

PRO: Tutti i possibili percorsi di routing vengono calcolati e
modificati senza sapere se verranno in futuro utilizzati ( visione a
360° della rete ). Otteniamo una tabella di routing biblica, immensa,
omnicomprensiva (impossibile da consultare senza grep !).

CONTRO: FLOOD e carico di sistema. il primo scaturisce dall'attività
di annunciazione di ogni nodo, il secondo scaturisce dal fatto che lo
"shortest-path" richiede elaborazione computazionale pari al numero di
nodi. Quindi più si espande la rete più questi due fattori crescono.
La propagazione di tutte le tabelle di tutti i nodi
riduce la banda disponibile (over-head di rete), il carico computazionale
ai dispositivi
riduce la reattività degli stessi.

Ad ogni modo per OLSRd non è necessario questo flooding venga inviato da
tutti i nodi, ma basta che
a inviarlo siano un ristretto numero di vicini del nodo comunicante.
Questo set di nodi prende il nome di MPR (Multipoint Relays) -
definito anche Optimized Flooding (MPR).

La tecnica MPR nasce dall’osservazione che in una situazione di broadcast
non ottimizzato ogni nodo riceve più volte le stesse informazioni causando
un notevole spreco di banda e di potenza di calcolo.

L ’RCF di OLSR descrive inoltre un semplice algoritmo euristico per
calcolare il
sottoinsieme di MPR. L’Optimized Flooding fa si che un nodo elegga tra i
suoi vicini (nei-
ghbor) il minimo insieme che consente di raggiungere tutti i 2-hop-neighbor
(tutti i vicini a distanza di due hop). Serve quindi capire quanti MPR deve
avere ogni nodo (tuning) e quali informazioni topologiche far distribuire ai
propri MPR: chiedo a SPAX e GIGI quali parametri vorremmo analizzare
al fine di argomentare le esperienze trascorse.

andiamo a BATMAN, questo si basa piuttosto che sul Link-State, usando
le tabelle di routing come media, sul Distance-Vector che si basa
sull’algoritmo di Bellmann-Ford.
Ogni nodo mantiene un database con le distanze minime tra se stesso e tutte
le possibili destinazioni.
A intervalli regolari invia ai nodi adiacenti un distance-vector,  un
insieme di coppie indirizzo-distanza, chiamate annunci. La distanza è
espressa come numero di hop o con criteri più generali che tengono
conto di velocità, carico e affidabilità dei collegamenti.

A partire da tali dati, utilizzando l’algoritmo di Bellman-Ford, il router
co-
struisce una tabella che associa ad ogni destinazione conosciuta la distan-
za che lo separa dalla destinazione e il primo passo del percorso calcolato.
Quando riceve il distance-vector, un nodo puù usare queste informazioni per
ricalcolare la sua tabella di routing e, a differenza dei Link-State, questo
messaggio non viene forwardato.

Con BATMAN un router ricalcola le proprie tabelle se:

• cade una linea attiva direttamente connessa
• riceve da un router vicino un annuncio per una destinazione non cono-
sciuta
• riceve da un router vicino un annuncio per una destinazione già nota,
ma a costo più basso rispetto a quello memorizzato
• riceve da un router vicino un annuncio per una destinazione che lo stesso
router aveva già annunciato precedentemente con costo più elevato
• scade il tempo massimo di vita (TTL) per una destinazione in tabella

Sicuramente a fare più paura è l'ultima condizione, ovvero la
scadenza del TTL, perchè si traduce in tempi di attesa per aspettare
che il dispositivo "sperimenti" nuovi percorsi (andando a
casaccio...Con il pericolo di creare loops...), poichè trovare il percorso
migliore richiede più tempo
non avendo l’intera topologia a disposizione per il calcolo e questa
complessità si traduce nella pratica in velocità di convergenza più bassa.

la configurazione dei router risulta molto più semplice e la
necessità di memoria (RAM) in essi è bassa poichè ogni router deve
memorizzare solo le informazioni sui collegamenti da se stesso verso gli
altri nodi
e non sull’intera rete, questo si traduce in un minor costo.

Quello che un nodo batman annuncia si chiama Originator Messages e
contiene solo il primo hop verso una destinazione (e non tutto lo
scibile come le tabelle floddate da OLSR).

A seguito della terza generazione di Batman è stata ideata la versione
Advanced che consente di gestire il routing a livello 2 per mezzo di
un modulo del kernel.

Confronti utili:

Se la rete supera le centinaia di nodi OLSR impiega molte risorse per
il calcolo del path più corto, mentre batman divide la conoscenza e
delega il routing agli hop di competenza.

Una rete mesh basata su B.A.T.M.A.N. viene inondata a intervalli regola-
ri da Originator Messages fino a che non vengono ricevuti dal destinatario
almeno una volta o finche il pacchetto non viene perso causa fine del TTL
o problemi di comunicazione. Il protocollo ritiene significativa ogni
perdita
di pacchetti per trovare il percorso migliore.

DOMANDA: è capitato che OLSR forwardasse roba vecchia di nodi andati
giù ? Con Batman questo non sarebbe possibile.

Per integrare i due, piuttosto che avere entrambi sui medesimi nodi
non sarebbe meglio e innovativo (dati gli scopi di ninux) sperimentare
soluzioni miste con l'adozione di messaggi HNA per gli annunci a
sistemi differenti (OLSR->HNA->BATMAN e viceversa).

Potremmo sperimentare newSPIG con OLSR e Capizzanux con Batman i quali
comunicano tramite HNA ? Sarebbe il primo esperimento ufficiale dentro
ninux oppure a Roma hanno già fatto ?

Prima di procedere:

Un host malintenzionato potrebbe inviare OGM che annunciano l’esisten-
za di nodi inesistenti per causare un overflow nelle tabelle di routing
degli
altri nodi e un eccessivo carico di CPU, così anche per il flooding di
OLSR.

Sappiamo bene che sicurezza e mesh non vanno daccordo ma dobbiamo
perlomeno sperimentare, adoperare, formalizzare, degli strumenti di
diagnosi semi-automatica e isolamento del problema per evitare di
avere grandi problemi in una futura grande rete.

Penso che a tale merito il routing a terra sia di aiuto.
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://ml.ninux.org/pipermail/calabria/attachments/20131209/ddca6f32/attachment-0001.html>