[Ninux-Calabria] ODG 10 Dicembre 20013

Lun 9 Dic 2013 15:20:44 CET

Il 09/12/2013 13:34, Giuseppe De Marco ha scritto:
> 
> 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.

Ottima sintesi! ho già wikizzato
http://tracker.hlcs.it/projects/ninux/wiki/BATMAN_vs_OLSR

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

Coi 4 nodi che abbiamo non credo possa succedere, non so a Roma..

> 
> 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 ?

A Roma è stato fatto. Alcune zone utilizzano batman a livello di
distribuzione, e la subnet viene annunciata tramite HNA proprio come hai
detto. è descritto anche sul paper dell'architettura della rete
http://blog.ninux.org/wp-content/uploads/2012/06/NinuxRoma-RoutingArchitecture-DocumentVersion0.pdf

> 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.

Sul tuning di OLSR mi trovi impreparato XD

> 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. 

In ogni caso credo che i problemi sorgano quando si arriva ai ~1000
nodi, il che si può ovviare con un po' di pianificazione:
- mesh di distribuzione (tra apparati domestici, a 2.4GHz) utilizzano
batman-adv e contano come un unico nodo olsr
- per il routing tra isole si ulizza BGP (se si tratta di link cablato)
oppure un'altra istanza di OLSR che annuncia in HNA l'intera isola (se
link wireless).

Utilizzare un protocollo layer 2 per la dorsale invece non mi sembra
appropriato, ma sicuramente dovremmo valutare le alternative layer 3,
vale a dire babel e batman-bmx.

BTW qualcuno sa dove trovare i risultati dei test dell'utlimo battle mesh?

-- 
Vincenzo Pirrone
Twitter: @spax_arm
PGP Key ID: 5CF5047D

-------------- parte successiva --------------
Un allegato non testuale è stato rimosso....
Nome:        signature.asc
Tipo:        application/pgp-signature
Dimensione:  901 bytes
Descrizione: OpenPGP digital signature
URL:         <http://ml.ninux.org/pipermail/calabria/attachments/20131209/6da4fdef/attachment-0001.sig>