[Berlin-wireless] Verbesserungen des Algorithmus in olsrd-0.4.10-cvs

onelektra onelektra
Mo Nov 21 13:30:25 CET 2005


Hi -

in der Nacht von Mittwoch auf Donnerstag letzte Woche hat Thomas ein 
neues Feature in den olsrd eingebaut von dem Wir viel für die Stabilität 
in olsr-Netzen erhoffen. Das Feature soll helfen Routing Loops zu 
vermeiden, welche auftreten wenn im Mesh Links durch Traffic gänzlich 
ausgelastet werden.

Unter diesen Umständen kann man beobachten dass der betreffende 
Datentransfer mit prima Geschwindigkeit losrennt um dann nach einigen 
Sekunden komplett zusammenzubrechen.

Die Ursache sind u.a. das Auftreten von Routing Loops. Durch den 
massiven Traffic treten auf der Funkseite sehr viele Kollisionen auf. 
Ganz besonders herb wird es, wenn in der Konfiguration der Wlankarten 
der RTS- und Fragmentationmechanismus nicht aktiviert oder konfiguriert 
ist. Die Empfehlung ist rts 250 und fragmentation 512.

Durch die Kollisionen auf dem Funkkanal gehen Nachrichten die Olsrd 
verschickt und die für die Stabilität des Netzes verantwortlich sind 
verloren.

Das ganze läuft so ab:

Durch den massiven Traffic gehen Hello-Nachrichten verloren. Die 
Linkqualität verschlechtert sich. Gleichzeitig gehen auch 
Topologienachrichten verloren. Als Folge davon ändern die Nodes die 
Routingtabellen - allerdings ohne das sie dabei auf aktuellem Stand 
wären wie gerade andere Nodes die Topologie des Meshes sehen. Die Folge 
ist die Routingtabellen sind nicht synchron und es kann sein das Nodes 
sich die Pakete im Ping-Pong hin und her schicken oder sie im (kleinen) 
Kreis herumsausen lassen. Bei jeder Weiterleitung wird im Datenpaket ein 
Zähler um die Zahl 1 heruntergesetzt (der TTL-Wert, Time to live). Wird 
der Wert 0 schmeisst der betreffende Node das Paket weg und schickt eine 
Nachricht zurück, das es hier nicht weitergeht. Die Nachricht erreicht 
irgendwann die Software die den sättigenden Datentraffic verursacht hat, 
diese spuckt dann eine Meldung aus wie 'Keine Verbindung zu xxx-host' 
oder 'Link is down'.

Unsere Überlegungen dazu:

Das Problem ist fehlende Synchronität der Routingtabellen. Eine absolute 
Sicherheit gegen Loops oder Routingfehler gibt es in einem Mesh mit 
seinen verlustbehafteten Datenverbindungen nie. Aber man kann die 
Stabilität erhöhen wenn die Topologiekontrollnachrichten öfter geschickt 
werden, so dass sie redundant sind. Am besten schickt man die 
Topologienachrichten öfter als die Hellos - viel öfter. Je öfter desto 
weniger wahrscheinlich dass Nodes Änderungen verpassen und es dann im 
Gebälk knirscht...

Wenn man die Topologienachrichten aber sehr viel öfter schickt entsteht 
das Problem dass das Netz unter diesem zusätzlichen Overhead erstickt. 
Topologienachrichten werden normalerweise über das ganze Mesh 
weitergereicht - wenn also in einem Netz von 100 Nodes jeder alle 
500_msec solche Nachrichten verschickt - die dann auch noch von jedem 
sofort weitergereicht werden, geht das mit Sicherheit nicht gut...

Glücklicherweise ist es aber gar nicht nötig das ganze Netz alle 500 
msec zuzuspammen. Wir gehen davon aus dass Routing Loops nicht grosse 
Kreise ziehen sondern in einem lokal begrenzten Raum auftreten, d.h. nur 
wenige Hops weit. Entsprechend reicht es diese öfter nur an die direkten 
und indirekten Nachbarn 2 oder 3 Hops entfernt zu schicken.

In der Praxis heisst das wir schicken alle n Sekunden TC-Nachrichten an 
unsere direkten Nachbarn. Jede 2. TC-Nachricht schicken wir an unsere 
nächstgelegenen indirekten Nachbarn, nur jede 4. TC-Nachricht geht an 
die Nachbarn die wir über 3 Hops erreichen. Nur jede 13. Nachricht wird 
an das ganze Netz verschickt.

Das Feature heisst in der Konfigurationsdatei

LinkQualityFishEye 1

Es lässt sich mit 1 anstellen und mit 0 deaktivieren.

Es steht bislang nur im aktuellen CVS zur Verfügung.

Betrachtet die Sache als experimentell. Sie ist noch nicht dokumentiert 
und steht auch noch nicht in der default olsrd.conf drin. Die 
olsrd-version mit dieser Erweiterung läuft bislang ohne Probleme im 
Dauerbetrieb in einem kleinen Mesh.

Kompatibilität zu älteren Varianten des olsrd ist gewährleistet. Es 
werden nur die TTL-Werte der TC-Nachrichten verändert und öfter 
geschickt. Die Nachbarn eines Nodes bekommen Topologiepakete mit 
TTl-Werten von 1,2,3 oder 255. Entsprechend werfen sie diese weg wenn 
die TTL zu Null wird.

Das ganze ist - wie gesagt - erstmal experimentell. Nichts desto trotz 
brennen wir auf Eure Testergebnisse :-)

Ich bin jedoch sehr zuversichtlich das olsrd sich sehr stark dadurch 
verbessert - ohne negative Nebenwirkungen. Die 'Validity'-Zeiten der 
verschiedenen Olsrd-Nachrichtentypen sollten in olsrd.conf sehr lang 
eingestellt werden. In einem Mesh mit LinkQualityFishEye kommen 
Informationen die das grosse ganze Mesh erfassen potentiell seltener an. 
Das ist auch gar nicht nötig. Wenn das Gefühl nicht täuscht gewinnen Wir 
sehr an Stabilität und reduzieren den Overhead.


cu elektra

_______________________________________________
Berlin mailing list
Berlin at olsrexperiment.de
https://olsrexperiment.de/cgi-bin/mailman/listinfo/berlin





Mehr Informationen über die Mailingliste Berlin