Een eigen routing daemon: lvrouted

We hebben aanvankelijk OSPF gebruikt voor dynamische routering. Dat werkte in het begin erg goed. Boven een bepaalde grootte van het netwerk (+/- 30 nodes) onstonden stabiliteitsproblemen. We zijn toen tijdelijk overgegaan op StaticRouting. In het najaar van 2004 heeft Lodewijk een eigen dynamische routering programma geschreven (lvrouted). Dit blijkt uitstekend te werken. Zie de README die bij de source staat:

Hoe werkt lvrouted?

This is a very simple shortest-path routing daemon, featuring:

No per node configuration: If your network has both a well-defined routable range (for us, that's 172.16.0.0/12) and well-defined interlink netmasks (anything smaller than 28 for us), the daemon can do the right thing automatically. The first assumption is implemented in Common.min_routable and Common.max_routable, the second assumption is set in Common.interlink_netmask.

All addresses on all interfaces are examined to see if they fall within the routable range. For interlink subnets all possible addresses are treated as possible neighbors and the daemon will try to link up to daemons on those addresses.

The algorithm in this branch of the code is OSPF-like. Every node has a current spanning tree for the part of the network the node knows about. At startup, this is just the collection of local routable addresses. At some tunable interval, it derives a new tree from the trees it has received from neighbors by a breadth-first traversal of all those trees, building up a new routing table and removing superfluous nodes along the way. It then sends the new tree to its neighbors and updates the kernel routing table. A subtree is superfluous if the top address is already in the routing table (this makes it shortest-path) or is one of the node's own addresses (this solves count-to-infinity).

The trees can either be serialized using the generic ocaml Marshal module, or a handwritten serializer. The handwritten serializer assumes the routable range is 172.16.0.0/12 in that it uses the 12 fixed bits to store the number of children for a node. If your network uses a different range, either change tree_to_string() and string_to_tree() in lowlevel_c.c, or have the program use the ocaml marshaller by setting Common.use_own_marshaller to false. The handwritten marshaller uses 4 bytes per node while the ocaml marshaller uses just over 8.

For 55 nodes with 286 routable addresses, on-the-wire packets are 1172 bytes. CPU usage on a Soekris is generally a few percent, peaking to about five percent. RSS is about three to four MB.

Specifieke aannames

A couple of other assumptions about the WirelessLeiden network are in the code and would need to be adapted for other environments:

Common.ml also contains some other settings like the port to use and some timeouts. The most interesting flags are also commandline-settable.

Packet signing

A secret key can be specified on the commandline with the "-s" flag. If set and not empty, a SHA1 hash is sent prepended to the usual packet content. This hash is the hash of the concatenation of the secret key with the packet content. On receipt, the hash is checked with the rest of the packet before any interpretation of the packet contents, so attacks that try to subvert the ocaml marshal module or inject faulty data are averted.

This version sends the current time prepended to the actual data, and this is included in any signature. If a packet comes in from a neighbor that hasn't sent anything before, that timestamp is accepted as the base, and subsequent packets are only accepted if their sequence number is greater. This leaves a hole where a replayed packet will get accepted if an attacker is quicker to respond to a newly booted daemon than the legitimate neighbor. That packet would still have to have been a legitimate packet once for the hash to check out, so replaying that one is not that bad. Even if the attacker replays a whole bucketload of intercepted packets, the fun is over when the real neighbor gets its first packet through and pulls the timestamp up to beyond what the attacker has intercepted.

Lodewijk Voge

Uitrol van nieuwe versies

Hoe doe je een uitrol van nieuwe versies:

   0       CeTIM1
   1       CeTIM2
   1       CeTIM3
   2       IMI
   2       RV
   etc. 

haal de experimentele 5.3 nodes daar uit.

for i in `cat lijst | grep "^0" | sed 's/^..//'`; do
      ./update.sh $i lvrouted.opt /usr/local/sbin/lvrouted.opt
"/usr/local/etc/rc.d/lvrouted.sh restart" &
    done

let op de & daar aan het eind. alle nodes met gelijke hopcount worden dus tegelijk geupdate. als je ze serieel doet duurt het *heel* erg lang. update.sh staat in de lvrouted source tree onder tools/.

for i in `cat lijst | grep "^0" | sed 's/^..//'`; do
      ping -c 1 $i.wleiden.net
    done

de grep op. de hoogste hop count voor mij is nu 7.

individuele nodes updaten

    /usr/local/sbin/lvrouted.opt van een geupgrade node pakken,
    /usr/local/etc/rc.d/lvrouted.sh stop, oude binary voor de zekerheid
    ergens bewaren (bv hernoemen naar lvrouted.old ofzo), nieuwe binary in
    /usr/local/sbin/ zetten, /usr/local/etc/rc.d/lvrouted.sh start

voila :)

update 3 jan 2005

een nieuwe versie van lvrouted. grote veranderingen zijn:

en verder wat kleine bugfixes. gek genoeg lijkt de select() verandering ook voor iets minder CPU load te zorgen.

Ik vermoed nog een bug in de samenwerking tussen de ocaml GC en de C interface. De code houdt zich aan alle regels, maar toch verliest ie zachtjes aan geheugen. Ik kan het reproduceren met een kleine functie, dus ik zal het eens als ocaml bug submitten. Het kan heel goed dat dit de eerste keer is dat zo'n stuk gemixte code gebruikt wordt voor een langlopend proces op zulke kleine systemen en dat het daarom niemand eerder is opgevallen :)

Update maart 2005

Op cetim3 draait ter test een compile van de route daemon met de CVS versie van de ocaml compiler. Na wat prutsen had ik een goeie testcase en bleek er inderdaad een lek in de garbage collector te zitten. Die is er nu uit en nu is het de vraag of dat ook het lek waar de nodes last van hebben dicht.

de testcase was uiteindelijk een ordinaire

        let _ = while true do Gc.full_major () done

wat hier op een opteron 250 ongeveer 100MB per seconde lekte :)

Op 14 maart op meeste nodes update gedaan, ziet er goed uit.

Inmiddels is ocaml 3.08.3 uitgebracht, met de fix voor het geheugenlek.

Update juli 2005

{Lodewijk}

Er is nu een nieuwe versie van de route daemon, met als enige verschil met de vorige versie dat ie de bovenste zes bits in elk 32bit woord in de packets expliciet negeert. In die zes bits stopt de versie die snelheden van links in acht neemt, inderdaad de snelheid van een link naar een node. Door de huidige versie die te laten negeren (ipv te denken dat een node 836 links heeft en vervolgens crashed) kan die nieuwe versie voorzichtig en geleidelijk getest, gedebugged en geintroduceerd worden.

Verder heb ik wat zitten profilen en heb ik het CPU gebruik van lvrouted tot ongeveer de helft kunnen terugbrengen. waar cetim3 eerst piekte op 59% is dat nu %27.

De ingrepen waren:

Resetten tijd op nodes

Let op: de tijd wordt op verschillende plekken in de routing daemon gebruikt. Je kunt daardoor bijv. niet straffeloos de tijd terug zetten, dan gaat de daemon pas weer werken wanneer de tijd weer was toen je het terugzette. I.v.m. replay attacks accepteren buren alleen packets met een hogere timestamp dan ze al gezien hebben, en de daemon zelf bekijkt of het tijd is om packets rond te sturen aan de hand van wanneer 'ie dat het laatst heeft gedaan. Als je de tijd terug draait zal 'ie zelf geen packets meer sturen, en als 'ie ze toch stuurt (bv omdat je de daemon herstart) zullen de buren het niet accepteren.

Dus als je de tijd terug zet, daemon herstarten op de node zelf en op de buren. Zie ook TimeLords.

Update october 2005

Software is aangepast voor de nieuwe versie (6.0) van FreeBSD die binnenkort op de nodes gaat draaien. Dit draait op de 'proefnode' NodeMarten (21.10.2005).

De route daemon is op alle nodes geupdate. Met deze update kan het experimenteren met de versie die rekening houdt met bandbreedtes beginnen.(29.10.2005)

(5 nov 2005): De code van de experimentele route daemon lijkt onderhand niet meer te crashen en lijkt bandbreedtes goed te propageren, dus ik kan die versie voorzichtig op meer nodes aanzetten. nu draaien stadhuis1, stadhuis2 (om 5.4 te testen) en lcpl (5.0), en ik heb marten gevraagd de 6.0 versie te testen.

Note dat er nu dus route daemons draaien met verschillende noties van wat een betere route is. Als er meer nieuwe versies met elkaar gaan praten is het heel goed mogelijk dat er een routelus ergens ontstaat. Dat is niet anders, dat blijft zolang de twee versies tegelijk draaien. Als het allemaal goed gaat, met goed gaan als in niet crashen en betere beslissingen nemen, kan de nieuwe versie snel overal gaan draaien en dan verdwijnt dat probleem weer.

Het formaat van de boom dumps in /tmp heeft nu dus ook de bandbreedte erbij, in megabits. De huidige metric is dus dat het pad met de hoogste waarde voor de minimale bandbreedte op dat pad gedeeld door de lengte van het pad wint en een route wordt.

Update (ergens na 5 november 2005)

De versie die rekening houdt met bandbreedtes zorgde voor lussen en gaten in de routering. De lussen kwamen doordat het opdelen van bandbreedtes te fijnmazig gebeurde, waardoor er erg veel onrust in het netwerk zat. Een versie die alleen onderscheid maakt tussen "gewoon" (<=11Mbps) en "snel" (>11Mbps) zorgde vervolgens nog steeds voor gaten. Het bleek mogelijk te zijn dat, gegeven node A met buren B en C en node D ergens naast B en C, node A van node B een boom krijgt met node D zonder kind-nodes en van C een boom krijgt met node D met kind-nodes. In het oude algoritme kon dit nooit gebeuren zonder dat het pad naar D via C korter was dan het pad naar D via B, dus D's kind-nodes waren altijd bekend bij A. Het nieuwe algoritme blijkt dit niet te garanderen, het komt voor dat het pad naar D via B interessanter is dan via C, en vervolgens zijn de kind-nodes van D niet bekend bij A en is er een gat in de routering. Een mogelijke workaround is wanneer D voor de tweede keer wordt gezien (via C, met kind-nodes), D opzoeken in de uitvoer-boom en de kinderen er daar onder hangen en routes ervoor maken. Dit is in de code, maar is nog niet getest.

Update 3 januari 2007

Ik ben nu een paar dagen aan het prutsen met de score functie voor de nieuwe versie van de route daemon (nu de onderliggende techniek inderdaad goed werkt). Om te laten zien dat dat niet eenvoudig is ("gewoon" ethernet voorrang geven is niet gewoon) hier even een uitleg over de stand van zaken en wat er inmiddels geprobeerd is.

Het route algoritme neemt nu als parameter een functie die, gegeven een pad van A naar B, een score produceert. Als de score voor pad 1 beter is dan voor pad 2 wordt pad 1 gekozen. de functie heeft kennis van de bandbreedtes van de links op het pad, en de pad lengte.

De aannames en wensen die hier in deze functie verwerkt moeten worden zijn, voor zover ik op dit moment weet:

  1. de link bandbreedte moet de score beinvloeden.
  2. langere paden zijn over het algemeen slechter dan kortere paden.
  3. d'r is een punt waar 2) het wint van 1). tenminste, ik zou het raar vinden als een pad van 5 54Mbps links "beter" zou zijn dan een directe link van 11Mbps.
  4. ethernet is gratis vergeleken bij wireless.
  5. uit 1) en 4) volgt dat gegeven een pad van 11 en 11Mbps en een van 100 en 11Mbps de laatste beter is.
  6. als een pad een slechte verbinding heeft (1 of 2Mbps) dan moet het slechter scoren dan alle andere paden zonder slechte verbinding, ook als die een stuk langer zijn.
  7. de gratis in 4) is niet helemaal gratis. als je een pad neemt moet dat niet precies hetzelfde scoren als hetzelfde pad verlengd met een 100Mbps link. Als die twee wel hetzelfde zouden scoren zou het dus willekeur zijn welke gekozen wordt, en dat is onzinnig.

De eerste poging nam 2) en 1) in acht. De score was de minimale bandbreedte op het pad gedeeld door de lengte van het pad. Punten 3), 4), 6), 7) en met name 5) zaten hier niet bij. Een pad met 11 en 11 scoorde evenveel als een pad met 100 en 11.

De tweede poging was de som van de bandbreedte gedeeld door de lengte van het pad. Dit had punten 1), 2) en ook 5), maar niet 3) (namelijk: 5 54Mbps is hier / wel/ beter dan een directe 11Mbps link), 4) en 6). Ook leidde dit tot de belachelijke situatie dat als je een pad hebt je dat pad oneindig kunt verlengen met 100Mbps links om de score maar hoger te krijgen (dit was wat er gisteren mis ging met vosko1: vosko1 en vosko2 hadden blijkbaar allebei een even lange route naar proxy1, en diezelfde routes scoorden hoger *met* de ethernetlink tussen die twee erbij, dus allebei kozen ze het naar elkaar te sturen.

De derde poging was de som van de bandbreedte gedeeld door het kwadraat van de lengte. Wel punten 1), 2), 3) (een beetje in dat er inderdaad zo'n punt aan te wijzen is, maar niet handig in te stellen is) en 5. Niet 4), 6) en nadrukkelijk niet 7).

De vierde poging is de som van de bandbreedte gedeeld door de lengte kwadraat. Dit in een poging dat punt bij 3) wat naar beneden te halen, en punt 7) op te lossen. Ook heeft deze een poging punt 6) te verhelpen: er wordt een score van -1 gegeven aan een pad waar een 1Mbps of 2Mbps link in voor komt, die zijn meestal zo langzaam omdat ze ontzettend slecht zijn op dat moment. Deze versie draait nu op rv, jorg, cope, huub, vosko1 en vosko2.

In die vierde poging is ethernet niet gratis genoeg. De volgende poging, nog niet getest, telt het aantal ethernetlinks op een pad. 0.9 keer dat aantal wordt van de lengte afgehaald, zo zijn ze niet helemaal gratis maar wel erg goedkoop. Deze versie zou alle punten moeten verwerken.

Anyway, hopelijk laat dit zien dat het niet eenvoudig is, en aan welke eisen een oplossing moet voldoen. vragen als "waarom kun je niet gewoon <etc>" zijn welkom mits er ook bij staat hoe dat gewone <etc> al de bovenstaande punten oplost. Klachten dat een genomen route slechter zou zijn dan een andere zijn welkom als er ook bij staat *waarom* het slechter gevonden wordt. Op die manier kunnen de bovenstaande zeven punten aangevuld worden en de formule er op aangepast worden.

Update

Een belangrijke wens voor de score functie is dat als het een bepaald pad van A naar B als hoogste scoort, het datzelfde pad maar omgekeerd als hoogste scoort voor de route van B naar A. Als dat niet zo is krijg je nog meer asymmetrische routes dan dat er nu al zijn, en die zorgen nu vaak voor verwarring en rarigheid op de TCP laag. Het werkt allemaal wel, maar het werkt beter als routes symmetrisch zijn.

Update november 2007 'Aanpassingen voor FreeBSD 6.0'

Op een 'experimentele' node die op FreeBSD 6.0 draait kwam een probleem met lvrouted aan het licht. FreeBSD 6.0 accepteert blijkbaar de 5.4 ioctl()s om de stations uit te lezen wel, maar geeft dan vrolijk altijd 0 stations terug. ik heb nu een stuk code uit 6.0's ifconfig aangepast en nu lijkt cope het goed te doen.

Lodewijk (diff op http://svn.wirelessleiden.nl/cgi-bin/viewvc.cgi/node-config/other/lvrouted/trunk/src/lowlevel_c.c?r1=5483&r2=5706&pathrev=5706) --

Update februari 2009: optie -m toegevoegd

Tot nu toe was het zo dat een subnet breder dan een /28 niet bekeken werd voor buren. (Dat was omdat iemand mekkerde omdat er elke minuut 1 udp packet naar alle adressen in de interlink gestuurd werd en dacht dat er haxx0rz aan de gang waren (zucht).)

Er is nu een commandline optie van gemaakt, en na bijvoorbeeld een "-m 27" toe voegen aan /usr/local/etc/lvrouted.conf worden ook /27 subnetten meegenomen. ---

Aanpassing voor IRIS-type node

Hoe het nu werkt:

De boom op elke node is dus altijd een opspannende boom met, voor elke node in die boom, het pad vanaf de top van de boom naar die node altijd precies het kortste pad door het netwerk.

Dat is hoe het nu werkt. Om de IRIS nodes goed te doen, en verder te gaan aan het intelligenter omgaan met snellere links, moet het breedte-eerst gedeelte vervangen worden door een algemenere versie daarvan, met een priority queue. die code is er al, maar heeft nog alleen in experimenten gedraaid.

DynamicRouting (last edited 2009-09-28 06:29:45 by localhost)