olsr.funkfeuer.at
Monday, September 17, 2007
Todays work
Many more of Sven-Ola Tückes's patches. And I localized the netlink variant of the code in src/kernel_routes.c.
¶ 4:10 PM 0 comments
Sunday, September 16, 2007
B.A.T.M.A.N. vs OLSR
Showdown between B.A.T.M.A.N. and OLSR!
At the wireless community weekend in Graz we are testing B.A.T.M.A.N. and OLSR in a 20 node mesh in parallel.
The result of the tests are that comparisons are very hard to make . Axel is still finding out how to add approx. 20 more virtual nodes to the test mesh. The problem is that both olsrd-0.5.4rc1 and batman as well as batman experimental both use very little CPU in the small 20 node mesh. Something like 0.3%. So... not much to compare unfortunately.
Since I have to leave now we had the following idea how to continue...
1. We will search for test users. Around 50 should be the minimum
2. We will ask these people to install our ssh key
3. We will install batman experimental and olsrd-0.5.4 and collect routing data
4. We will evaluate this routing data and metrik data and therefore we will be able to compare better and make further improvements.
5. The test users will then remove the ssh key again ¶ 5:28 AM 0 comments
At the wireless community weekend in Graz we are testing B.A.T.M.A.N. and OLSR in a 20 node mesh in parallel.
The result of the tests are that comparisons are very hard to make . Axel is still finding out how to add approx. 20 more virtual nodes to the test mesh. The problem is that both olsrd-0.5.4rc1 and batman as well as batman experimental both use very little CPU in the small 20 node mesh. Something like 0.3%. So... not much to compare unfortunately.
Since I have to leave now we had the following idea how to continue...
1. We will search for test users. Around 50 should be the minimum
2. We will ask these people to install our ssh key
3. We will install batman experimental and olsrd-0.5.4 and collect routing data
4. We will evaluate this routing data and metrik data and therefore we will be able to compare better and make further improvements.
5. The test users will then remove the ssh key again ¶ 5:28 AM 0 comments
B.A.T.M.A.N. vs OLSR
Showdown between B.A.T.M.A.N. and OLSR!
At the wireless community weekend in Graz we are testing B.A.T.M.A.N. and OLSR in a 20 node mesh in parallel. ¶ 5:28 AM 0 comments
At the wireless community weekend in Graz we are testing B.A.T.M.A.N. and OLSR in a 20 node mesh in parallel. ¶ 5:28 AM 0 comments
Thursday, September 13, 2007
0.5.4rc1 released
I just released olsrd-0.5.4rc1. Since I'm lazy, I just quote the release mail here:
Due to the further massive changes (a good part of it was rewritten) in the routing core to further reduce duplicated data and *lots* of malloc() and free() calls (see the changelog below for more), we ask for further testing and - thus - this is a release candidate.
It compiles and runs on Linux and Win32 (though the testing on Win32 was pretty minimal), so we are especially interested in feedback from all non-Linux systems.
The only known issues are
- warnings on x86_64 in code only used by the nameservice plugin.
- the Quagga plugin is the last with the old plugin interface version.
To quote from the changelog:
---- snip ----
QUAGGA by Immo 'FaUl' Wehrenberg <immo.olsr@do.bundessicherheitsministerium.de>
- updated to svn version 33
BMF PLUGIN by Erik Tromp <erik_tromp@hotmail.com>
- updated to 1.5.1
- updated to latest plugin interfaces changes and killed warnings (by Bernd
Petrovitsch <bernd@firmix.at>)
PATCH by Hannes Gredler <hannes@gredler.at> which rewrites the route handling.
To quote him:
---- snip ----
change list:
- get rid of separate routing tables for HNA and per-node routes, everything is
now unified in an AVL routing tree (&routingtree)
- introduce walking macros (OLSR_FOR_ALL_RT_ENTRIES()) that hide the internal
structure of the RIB for making life of the plugin authors easier.
- get rid of different SPF implementations for LQ and non-LQ code paths. a
non-LQ edge is simply substituted with a cost of 1.0
- get rid of host masks - a new data type olsr_prefix is introduced which is
basically an ip address plus a prefix length.
do not install the metric in the kernel FIB - for the kernel its pointless
if the route gets installed with a metric of N or M.
we do not need to update the kernel FIB if we have hop count only changes
(for example if there is a reroute action further downstream)
the only things which triggers a kernel FIB route update is a next hop
change (a next hop is neighboring gateway router plus an interface).
all OLSR routes are installed with a metric of 2
- separate between rt_entry and rt_path - the former is a route installed in the
kernel with an next hop. the latter is a candidate for best path selection
after SPF calculation has been done. in the rt_entry we keep a pointer to the
best_path and also to the next hop that was installed in the kernel FIB.
we always keep all originator of a route, if a route originator goes away we
can easy recompute the best path for the route.
the next hop in the rt_entry gets only updated upon a successful route_add
call - that way we always remember what next hop to delete.
stray routes should be history now.
- tweak the linked list toolkit to operate on circular lists.
- get rid of malloc calls for building the kernel update list. the list node is
now embedded in the rt_entry.
- introduce three queues (add/chg/del) for kernel updates.
- for neighbor route dependency tracking the neighbor routes are queued first or
last (depending on which queue you work on)
- rework all the plugins which directly manipulate rt entries.
- rework the plugins that read from the routing table (most notably nameserver,
httpinfo and quagga plugin)
- lots of comments that explains the intentions and purpose of this code-piece.
non RT related stuff:
- use a list rather than a tree for storing the post-SPF results, which further
improves the raw-SPF runtime.
- add display of SPF runtime (masked behind #ifdef SPF_PROFILING)
---- snip ----
And Sven-Ola Tuecke <mail2news@commando.de> fixed an instability issue on interface
up/down operations (see 102-olsrd-rt-refactoring-fixes.patch below).
PATCH by Hannes Gredler <hannes@gredler.at> which "consolidates
the link-state database and the spf-calculation in order
to calculate routes more efficiently".
To quote him (more):
---- snip ----
- use the link-state (tc) database for SPF calculations rather than
replicating the notion of vertices and edges for a SPF run.
this heavily reduces malloc() calls and shrinks the total CPU
load of the route calculation path between 60%-80%.
---- snip ----
PATCHES by Sven-Ola Tücke <mail2news@commando.de> to be found on from
http://download-master.berlin.freifunk.net/sven-ola/nylon/packages/olsrd/files/
- 102-olsrd-rt-refactoring-fixes.patch
Because you changed a lot of basics: It's time to handle a general
flaw in the routing system. Plase take a look at chk_if_changed(). This
will free() any "struct interface" pointer without warning at any time.
This is why it's possile to SEGV olsrd with a simple "ifdown xxx".
The patch replaces the (maybe) invalid pointer with an index reference
"iif_index". You can always ask the OS for a name. Please note, that I do
not have a working BSD toolchain, so I've placed an #error in the IPv6
BSD-part where the author/porter has started to hack something funny.
- 110-olsrd-double-wlancard-neigh-hack.patch:
This is a hack for Nodes having to wifi cards with the same channel,
bssid, IP-Range etc. If two nodes can see each other by means of two
possible links (here: two wifi cards with equal config), a bug is triggered
with the Neigh-is-SYM detections. This small little hack prevents this.
- 112-olsrd-nameservice-fixemptyname.patch:
This is an addon to my lat/lon stuff which will prevent olsrd from
running (oops?) if no hostname is given and the nameservice plugin
is loaded.
- 113-olsrd-dyngwplain-pluginvers5.patch:
This updates the dyngwplain plugin to the new Plugin Iface
- 140-olsrd-arprefreshed.patch:
This is a new one. Opens a packet socket and listen to UDP(698), extract
the sender MAC and refreshes the ARP cache whith that. Should speedup
especially in cases, if you initially try to use a longer routing path which
normally triggers a "ARP-Lookup-Chain".
- 106-olsrd-nameserviceparams.patch:
This patch converts more plugins to the new interface version.
- 104-olsrd-policy-routing.patch
Reworked this one to discard GPL helper functions. Also checked IPv6 and
re-included the IPC hookup. The patch adds a "RtTable [number]" for
/etc/olsrd.conf which is simply the Linux
policy routing table to use. Defaults to 254 (== main).
This patch was modified/clenaed up by <bernd@firmix.at> to use "#if"
instead of "#ifdef" as it's more robust against typos.
PATCH by Arnd Hannemann <hannemann@i4.informatik.rwth-aachen.de>
olsr_makefile_make_use_of_exename.patch
- This patch makes sure that the EXENAME variable of Makefile.inc is used
in Makefile.
PATCHES by John Hay <jhay@meraka.org.za>
- update to new FreeBSD WLAN API
- do not require /bin/bash, use /bin/sh
PATCHES and CLEANUPS by Bernd Petrovitsch <bernd@firmix.at>
- Made a function from the ME_TO_DOUBLE() macro (in src/mantissa.h).
This saves code throughout the code even on i386 and will even more
on architectures without floating point units and "-msoft-float".
- And the mathemathics in src/mantissa.h is reformulated to minimize
floating point operations to save CPU power - especially on embedded
devices.
- I rewrote the half of src/lq_packet.[ch] which deals with incoming
packets. This was triggered with performance output of gcc produced
by Sven-Ola Tuecke at CCCamp07.
This kills *lots* of (more than) superflous malloc()s and the same
number of (free()s). And it also kills some code and copying around of
data.
- converted the dyn_gw plugin to plugin interface version 5 (which leaves
the quagga plugion as the last with the old one).
- paving the way to activate -Wshadow, much more to do
- const-ify parameters here and there
- use NULL for pointers (and not "0")
- Killed "extern" declarations in (not generated) .c files
- Based on a patch by Gianni Costanzi <gianni.costanzi@gmail.com> (so credits
and thanks have to go there):
added OS_CFLAG_PTHREAD Makefile variable since gcc (on Linux) requests this
in the manual page.
Changes/additions:
- I added definitions to all OS-specific Makefile.$OS with the value similar
to the value in OS_LIB_PTHREAD (either empty or "-pthread").
- The variable is added to CPPFLAGS (and not CFLAGS) since CPPFLAGS is used
for all cpp and gcc calls (and gcc's man page indicates that it sets
variables for both of them).
---- snip ---- ¶ 4:12 PM 0 comments
Due to the further massive changes (a good part of it was rewritten) in the routing core to further reduce duplicated data and *lots* of malloc() and free() calls (see the changelog below for more), we ask for further testing and - thus - this is a release candidate.
It compiles and runs on Linux and Win32 (though the testing on Win32 was pretty minimal), so we are especially interested in feedback from all non-Linux systems.
The only known issues are
- warnings on x86_64 in code only used by the nameservice plugin.
- the Quagga plugin is the last with the old plugin interface version.
To quote from the changelog:
---- snip ----
QUAGGA by Immo 'FaUl' Wehrenberg <immo.olsr@do.bundessicherheitsministerium.de>
- updated to svn version 33
BMF PLUGIN by Erik Tromp <erik_tromp@hotmail.com>
- updated to 1.5.1
- updated to latest plugin interfaces changes and killed warnings (by Bernd
Petrovitsch <bernd@firmix.at>)
PATCH by Hannes Gredler <hannes@gredler.at> which rewrites the route handling.
To quote him:
---- snip ----
change list:
- get rid of separate routing tables for HNA and per-node routes, everything is
now unified in an AVL routing tree (&routingtree)
- introduce walking macros (OLSR_FOR_ALL_RT_ENTRIES()) that hide the internal
structure of the RIB for making life of the plugin authors easier.
- get rid of different SPF implementations for LQ and non-LQ code paths. a
non-LQ edge is simply substituted with a cost of 1.0
- get rid of host masks - a new data type olsr_prefix is introduced which is
basically an ip address plus a prefix length.
do not install the metric in the kernel FIB - for the kernel its pointless
if the route gets installed with a metric of N or M.
we do not need to update the kernel FIB if we have hop count only changes
(for example if there is a reroute action further downstream)
the only things which triggers a kernel FIB route update is a next hop
change (a next hop is neighboring gateway router plus an interface).
all OLSR routes are installed with a metric of 2
- separate between rt_entry and rt_path - the former is a route installed in the
kernel with an next hop. the latter is a candidate for best path selection
after SPF calculation has been done. in the rt_entry we keep a pointer to the
best_path and also to the next hop that was installed in the kernel FIB.
we always keep all originator of a route, if a route originator goes away we
can easy recompute the best path for the route.
the next hop in the rt_entry gets only updated upon a successful route_add
call - that way we always remember what next hop to delete.
stray routes should be history now.
- tweak the linked list toolkit to operate on circular lists.
- get rid of malloc calls for building the kernel update list. the list node is
now embedded in the rt_entry.
- introduce three queues (add/chg/del) for kernel updates.
- for neighbor route dependency tracking the neighbor routes are queued first or
last (depending on which queue you work on)
- rework all the plugins which directly manipulate rt entries.
- rework the plugins that read from the routing table (most notably nameserver,
httpinfo and quagga plugin)
- lots of comments that explains the intentions and purpose of this code-piece.
non RT related stuff:
- use a list rather than a tree for storing the post-SPF results, which further
improves the raw-SPF runtime.
- add display of SPF runtime (masked behind #ifdef SPF_PROFILING)
---- snip ----
And Sven-Ola Tuecke <mail2news@commando.de> fixed an instability issue on interface
up/down operations (see 102-olsrd-rt-refactoring-fixes.patch below).
PATCH by Hannes Gredler <hannes@gredler.at> which "consolidates
the link-state database and the spf-calculation in order
to calculate routes more efficiently".
To quote him (more):
---- snip ----
- use the link-state (tc) database for SPF calculations rather than
replicating the notion of vertices and edges for a SPF run.
this heavily reduces malloc() calls and shrinks the total CPU
load of the route calculation path between 60%-80%.
---- snip ----
PATCHES by Sven-Ola Tücke <mail2news@commando.de> to be found on from
http://download-master.berlin.freifunk.net/sven-ola/nylon/packages/olsrd/files/
- 102-olsrd-rt-refactoring-fixes.patch
Because you changed a lot of basics: It's time to handle a general
flaw in the routing system. Plase take a look at chk_if_changed(). This
will free() any "struct interface" pointer without warning at any time.
This is why it's possile to SEGV olsrd with a simple "ifdown xxx".
The patch replaces the (maybe) invalid pointer with an index reference
"iif_index". You can always ask the OS for a name. Please note, that I do
not have a working BSD toolchain, so I've placed an #error in the IPv6
BSD-part where the author/porter has started to hack something funny.
- 110-olsrd-double-wlancard-neigh-hack.patch:
This is a hack for Nodes having to wifi cards with the same channel,
bssid, IP-Range etc. If two nodes can see each other by means of two
possible links (here: two wifi cards with equal config), a bug is triggered
with the Neigh-is-SYM detections. This small little hack prevents this.
- 112-olsrd-nameservice-fixemptyname.patch:
This is an addon to my lat/lon stuff which will prevent olsrd from
running (oops?) if no hostname is given and the nameservice plugin
is loaded.
- 113-olsrd-dyngwplain-pluginvers5.patch:
This updates the dyngwplain plugin to the new Plugin Iface
- 140-olsrd-arprefreshed.patch:
This is a new one. Opens a packet socket and listen to UDP(698), extract
the sender MAC and refreshes the ARP cache whith that. Should speedup
especially in cases, if you initially try to use a longer routing path which
normally triggers a "ARP-Lookup-Chain".
- 106-olsrd-nameserviceparams.patch:
This patch converts more plugins to the new interface version.
- 104-olsrd-policy-routing.patch
Reworked this one to discard GPL helper functions. Also checked IPv6 and
re-included the IPC hookup. The patch adds a "RtTable [number]" for
/etc/olsrd.conf which is simply the Linux
policy routing table to use. Defaults to 254 (== main).
This patch was modified/clenaed up by <bernd@firmix.at> to use "#if"
instead of "#ifdef" as it's more robust against typos.
PATCH by Arnd Hannemann <hannemann@i4.informatik.rwth-aachen.de>
olsr_makefile_make_use_of_exename.patch
- This patch makes sure that the EXENAME variable of Makefile.inc is used
in Makefile.
PATCHES by John Hay <jhay@meraka.org.za>
- update to new FreeBSD WLAN API
- do not require /bin/bash, use /bin/sh
PATCHES and CLEANUPS by Bernd Petrovitsch <bernd@firmix.at>
- Made a function from the ME_TO_DOUBLE() macro (in src/mantissa.h).
This saves code throughout the code even on i386 and will even more
on architectures without floating point units and "-msoft-float".
- And the mathemathics in src/mantissa.h is reformulated to minimize
floating point operations to save CPU power - especially on embedded
devices.
- I rewrote the half of src/lq_packet.[ch] which deals with incoming
packets. This was triggered with performance output of gcc produced
by Sven-Ola Tuecke at CCCamp07.
This kills *lots* of (more than) superflous malloc()s and the same
number of (free()s). And it also kills some code and copying around of
data.
- converted the dyn_gw plugin to plugin interface version 5 (which leaves
the quagga plugion as the last with the old one).
- paving the way to activate -Wshadow, much more to do
- const-ify parameters here and there
- use NULL for pointers (and not "0")
- Killed "extern" declarations in (not generated) .c files
- Based on a patch by Gianni Costanzi <gianni.costanzi@gmail.com> (so credits
and thanks have to go there):
added OS_CFLAG_PTHREAD Makefile variable since gcc (on Linux) requests this
in the manual page.
Changes/additions:
- I added definitions to all OS-specific Makefile.$OS with the value similar
to the value in OS_LIB_PTHREAD (either empty or "-pthread").
- The variable is added to CPPFLAGS (and not CFLAGS) since CPPFLAGS is used
for all cpp and gcc calls (and gcc's man page indicates that it sets
variables for both of them).
---- snip ---- ¶ 4:12 PM 0 comments
Tuesday, September 11, 2007
bmf-1.5.1
Erik Tromp released version 1.51. of th BMF plugin. Is simply tested it (a little bit), added it and fixed the last changes on the plugin interface and some "unused" warnings.
¶ 4:15 PM 0 comments
Wednesday, September 05, 2007
Routingtable Handling Improved
Another big step on the sped improvement front. Hannes Gredler <hannes@gredler.at> pretty much rewrote the routing table handling. To quote him:
---- snip ----
change list:
And Sven-Ola Tuecke tested the beast, found and fixed an instability issue on interface up/down operations (which was referred to as http://download-master.berlin.freifunk.net/sven-ola/nylon/packages/olsrd/files/102-olsrd-rt-refactoring-fixes.patch).
For those who want to see the exact differnece, I tagged the CVS with BEFORE_RT_REFACTORING and AFTER_RT_REFACTORING.
¶ 9:04 AM 0 comments
---- snip ----
change list:
- get rid of separate routing tables for HNA and per-node routes, everything is now unified in an AVL routing tree (&routingtree)
- introduce walking macros (OLSR_FOR_ALL_RT_ENTRIES()) that hide the internal structure of the RIB for making life of the plugin authors easier.
- get rid of different SPF implementations for LQ and non-LQ code paths. a non-LQ edge is simply substituted with a cost of 1.0
- get rid of host masks - a new data type olsr_prefix is introduced which is basically an ip address plus a prefix length.
do not install the metric in the kernel FIB - for the kernel its pointless if the route gets installed with a metric of N or M.
we do not need to update the kernel FIB if we have hop count only changes (for example if there is a reroute action further downstream)
the only things which triggers a kernel FIB route update is a next hop change (a next hop is neighboring gateway router plus an interface).
all OLSR routes are installed with a metric of 2
- separate between rt_entry and rt_path - the former is a route installed in the kernel with an next hop. the latter is a candidate for best path selection after SPF calculation has been done. in the rt_entry we keep a pointer to the best_path and also to the next hop that was installed in the kernel FIB.
we always keep all originator of a route, if a route originator goes away we can easy recompute the best path for the route.
the next hop in the rt_entry gets only updated upon a successful route_add call - that way we always remember what next hop to delete.
stray routes should be history now.
- tweak the linked list toolkit to operate on circular lists.
- get rid of malloc calls for building the kernel update list. the list node is now embedded in the rt_entry.
- introduce three queues (add/chg/del) for kernel updates.
- for neighbor route dependency tracking the neighbor routes are queued first or last (depending on which queue you work on)
- rework all the plugins which directly manipulate rt entries.
- rework the plugins that read from the routing table (most notably nameserver, httpinfo and quagga plugin)
- lots of comments that explains the intentions and purpose of this code-piece.
- use a list rather than a tree for storing the post-SPF results, which further improves the raw-SPF runtime.
- add display of SPF runtime (masked behind #ifdef SPF_PROFILING)
And Sven-Ola Tuecke
For those who want to see the exact differnece, I tagged the CVS with BEFORE_RT_REFACTORING and AFTER_RT_REFACTORING.
