[Olsr-dev] lsdb refactoring (2)

Hannes Gredler (spam-protected)
Wed Sep 12 12:33:38 CEST 2007


hi olsr developers,

please find attached a patch to that consolidates
the link-state database and the spf-calculation in order
to calculate routes more efficiently.

below there are measurement results taken on a pentium mobile 1300 mhz.
   [ to get those results set SPF_PROFILING in lq_route.c ]

the results are the median of 1000 SPF runs expressed in units of
microseconds based on the funkfeuer.at topology:
   [ 202 nodes / 850 edges / 360 routes ]

total	init	run	route	kernel	cleanup
1917.00	827.00	378.00	403.00	147.00	131.00  [ olsrd.0.5.1]
  382.00	  8.00	140.00	193.00	 40.00	  0.00  [ olsrd.0.5.3 + lsdb-refactoring-2]
-----------------------------------------------
   20%	  1%	 37%	 48%	 27%	  0%

change list:

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

patch is at:

http://gredler.at/download/olsrd/lsdb-refactoring-2.diff.gz

asking for review, testing and inclusion into CVS.

/hannes




More information about the Olsr-dev mailing list