[Olsr-dev] RIB2 refactoring

Mon Dec 3 11:37:06 CET 2007

Hannes,

lets continue in english. To ask SEQNO_GREATER_THAN() for doubles/duplicates 
is fine. As long as the possiblity to run into the "does not 
forward/process" condition is unlikely and/or _if_ that happens it does not 
take too long.

The current implementation of SEQNO_GREATER_THAN() defines a quarter of the 
possible values 0-0xffff as implausible IMO. In real live, we have ~ 0.1-10 
messages per second and a hold time for status info ~ 10 - 600 seconds. The 
firmware uses a relatively moderate default timing, leads to ~ 0.5 messages 
/ sec. and 300 seconds hold time for info. The chance to run in this 
condition is 0.25 but we need to wait 0xffff/4*2 seconds == 9 hours until 
processing continues. That's too long and too likely.

We can narrow the "Impossible-Value-Window" - from 1/4 to (Holdtimeforinfo / 
average message rate). In case of the firmware's timing, this is ~ 300 * 0.5 
== 600. Everything below the last-seqno-seen is old. Everything above 
last-seqno-seen+600 is a restart. If things went bad (Chance is ~ 1/100) we 
need to wait up to 300 seconds until processing continues - which is not too 
bad becaue olsrd is not designed to restart every now and then...

// Sven-Ola

"Hannes Gredler" <(spam-protected)> schrieb im Newsbeitrag 
news:(spam-protected)
sorry list for the response in german.

Sven-Ola Tücke wrote:
> Moin Hannes,
>
> ich nehme an, dass Bernd den Patch dann in das CVS uebernimmt. Ich bau' es 
> in
> die Firmware ein, wenn ich das naechste CVS-Syncup mache (irgendwann in 
> der
> Woche).

danke !

> Mir ist nicht ganz klar, welche Drawbacks '!flat_fib_metrics' hat (also 
> warum
> wir es dem User ueberlassen wollen ober er's nimmt oder nicht). Ich 
> vermute,
> es wird viele AddRoute/DelRoute ausloesen um die Metric aktuell zu halten?

so ist es ... allerdings ist es seit dem neuen netlink code die FIB updates 
auch
nicht mehr so teuer. mein vorschlag waere dass wir es im olsrd default bei 
den
flat-metrics belassen (auf anderen platformen wie win32 und BSD ist das 
kernel-API
nicht so schnell wie netlink) und du kannst es bei neuen FFF releases per 
config
abschalten.

> Ich habe auszerdem gerade eine Optimierung wieder ausgebaut und es als
> FFF-1.6.22 'rausgestellt (Patch anbei). Hintergrund: Je nach 
> seqno=random()
> kann es stundenlang dauern, bis TC's eines neu gestarteten olsrd-Daemons 
> von
> einem Nachbarn geforwarded/verarbeitet werden. Man muss in der Zeit neu
> gestartet haben, solange die Nachbarn noch vom letzten Lauf etwas im 
> Speicher
> haben. Um das so zu machen, koennen wir evnt:

hmm das ist ein aehnliches thema wie wir es schon gestern dikutiert haben:

haette man ein resync protokoll dann wuerden beim startup alle TC/MID/HNA
messages replayed werden (inklusive der alten eigenen) womit man dann sofort
loslegen kann. (also deine option c).

ich seh das problem und dein patch ist in diesem zusammenhang ok.
waere nett wenn du in deinem kommentar auch noch die nachteile
erwaehnen koenntest. - sprich man daemmt das flooding nicht ein.

> a) Die seqno irgendwo speichern, wo sie einen Neustart/Reboot ueberlebt
> b) Die Abfrage umbauen, damit die Chance auf diesen Effekt klein ist
> c) Bei den Nachbarn anfragen, welche Seqno wir zuletzt hatten
> d) Immer bei Null anfagen und beim Wraparound dann auf 100 setzen
> e) Beim Beenden/Start jede Menge "Invalidate-me()" 'raussenden
>
> Ich vermute auch, dass die zweite SEQNO_GREATER_THAN-Abfrage (Kommentar 
> von
> dir: "It could be that a TC message spans across multiple packets") so 
> nicht
> gewuenschten Effekt hat (defragementieren tut es jedenfalls nicht oder?).

das nicht, aber anstatt das edge zu entfernen, wird es lediglich mit einem
bit als down markiert. (was nicht sehr teuer ist). kommt dann die naechste 
fragment
(innerhalb der naechsten 15 sekunden) an dann hab ich keine grossen
malloc/free tree insert/remove bewegungen. besser waere natuerlich auch
code im netz zu haben der probiert fragmentierungen zu vermeiden.
nachdem das noch einige zeit brauchen wird, habe ich mich fuer diesen
tail-end fix entschieden.

/hannes

> Am Sonntag 02 Dezember 2007 15:00:08 schrieb Hannes Gredler:
>> hi list,
>>
>> pls find attached a pointer for further CPU savings in olsrd.
>> even in large networks (>250 nodes) the avg. CPU utilization
>> does not get beyond 0.5% CPU load on standard 200Mhz WRT hardware.
>>
>> patch is at http://gredler.at/download/olsrd/rib2-refactoring2.diff
>>
>> change-list:
>>
>> - avoid the periodical rib-tree insertion
>>
>> - add a FOR_ALL_HNA_RT_ENTRIES() macro for the snmp folks
>>     (or any parties who want to walk HNA entries).
>>
>> - add an olsr_cnf option 'flat_fib_metrics' which defaults to TRUE.
>>
>>    this is as per sven-olas request who has expressed concerns
>>    that the current flap-metric style is a bit unpleasant for
>> troubleshooting.
>>
>>    note that i have not yet added the cfg file parser routine for that -
>>    just the required tweaks in the change-processing FIB code.
>>
>>    sven-ola can you complete this pls ?
>>
>> --
>>
>> asking for review, testing and inclusion.
>>
>> tx,
>>
>> /hannes
>
>
>
> ------------------------------------------------------------------------
>
> diff -Nur olsrd-0.5.4.orig/src/duplicate_set.c 
> olsrd-0.5.4/src/duplicate_set.c
> --- olsrd-0.5.4.orig/src/duplicate_set.c 2007-12-03 07:55:37.000000000 
> +0100
> +++ olsrd-0.5.4/src/duplicate_set.c 2007-12-03 08:28:25.000000000 +0100
> @@ -84,7 +84,7 @@
>   *
>   *@return positive on success
>   */
> -struct dup_entry *
> +static struct dup_entry *
>  olsr_add_dup_entry(const union olsr_ip_addr *originator, const olsr_u16_t 
> seqno)
>  {
>    olsr_u32_t hash;
> diff -Nur olsrd-0.5.4.orig/src/duplicate_set.h 
> olsrd-0.5.4/src/duplicate_set.h
> --- olsrd-0.5.4.orig/src/duplicate_set.h 2007-12-03 07:55:37.000000000 
> +0100
> +++ olsrd-0.5.4/src/duplicate_set.h 2007-12-03 08:28:25.000000000 +0100
> @@ -82,9 +82,6 @@
>  void
>  olsr_print_duplicate_table(void);
>
> -struct dup_entry *
> -olsr_add_dup_entry(const union olsr_ip_addr *, const olsr_u16_t);
> -
>  int
>  olsr_update_dup_entry(const union olsr_ip_addr *, const olsr_u16_t, const 
> union olsr_ip_addr *);
>
> diff -Nur olsrd-0.5.4.orig/src/tc_set.c olsrd-0.5.4/src/tc_set.c
> --- olsrd-0.5.4.orig/src/tc_set.c 2007-12-03 07:55:37.000000000 +0100
> +++ olsrd-0.5.4/src/tc_set.c 2007-12-03 08:30:46.000000000 +0100
> @@ -44,6 +44,7 @@
>  #include "mid_set.h"
>  #include "link_set.h"
>  #include "olsr.h"
> +#include "duplicate_set.h"
>  #include "scheduler.h"
>  #include "lq_route.h"
>  #include "lq_avl.h"
> @@ -700,11 +701,22 @@
>     * Check if we know this guy and if we already know what he has to say.
>     */
>    tc = olsr_lookup_tc_entry(&originator);
> +#if 0
> +  /* Sven-Ola: Looks like a bad idea. During olsrd startup, its seqno
> +   * is initialized using random(). We have a good chance to wait for
> +   * hours until TC messages are forwarded for a node if olsrd is re-
> +   * started while there are still tc_entries in RAM.
> +   */
>    if (tc) {
>      if (!SEQNO_GREATER_THAN(msg_seq, tc->msg_seq)) {
>        return;
>      }
>    }
> +#else
> +  if(!olsr_check_dup_table_proc(&originator, msg_seq)) {
> +      goto forward;
> +  }
> +#endif
>
>    /* Check the sender address. */
>    if (!olsr_validate_address(&originator)) {
> @@ -771,6 +783,9 @@
>    /*
>     * Last, flood the message to our other neighbors.
>     */
> +
> +forward:
> +
>    olsr_forward_message(msg, &originator, msg_seq, input_if, from_addr);
>    return;
>  }

-- 
Olsr-dev mailing list
(spam-protected)
http://lists.olsr.org/mailman/listinfo/olsr-dev 