Added experimental LinkQualityDijkstraLimit option, which prevents
authorThomas Lopatic <thomas@lopatic.de>
Thu, 17 Nov 2005 04:25:44 +0000 (04:25 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Thu, 17 Nov 2005 04:25:44 +0000 (04:25 +0000)
LQ TCs from nodes more than x1 hops away from us to trigger routing table
recalculation using Dijkstra. Instead integrate these changes into the
routing table every x2 seconds. This is to reduce CPU load. Triggering
Dijkstra too often uses up a lot of CPU cycles.

src/cfgparser/olsrd_conf.c
src/cfgparser/oparse.y
src/cfgparser/oscan.lex
src/link_set.c
src/olsr.c
src/olsr_cfg.h
src/process_package.c
src/scheduler.c
src/tc_set.c

index 0ed4187..00d1839 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_conf.c,v 1.45 2005/11/17 01:58:52 tlopatic Exp $
+ * $Id: olsrd_conf.c,v 1.46 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -453,6 +453,8 @@ set_default_cnf(struct olsrd_config *cnf)
     cnf->mpr_coverage = MPR_COVERAGE;
     cnf->lq_level = DEF_LQ_LEVEL;
     cnf->lq_fish = DEF_LQ_FISH;
+    cnf->lq_dlimit = DEF_LQ_DIJK_LIMIT;
+    cnf->lq_dinter = DEF_LQ_DIJK_INTER;
     cnf->lq_wsize = DEF_LQ_WSIZE;
     cnf->clear_screen = DEF_CLEAR_SCREEN;
 }
@@ -563,6 +565,10 @@ olsrd_print_cnf(struct olsrd_config *cnf)
    
   printf("LQ level         : %d\n", cnf->lq_level);
 
+  printf("LQ fish eye      : %d\n", cnf->lq_fish);
+
+  printf("LQ Dijkstra limit: %d, %0.2f\n", cnf->lq_dlimit, cnf->lq_dinter);
+
   printf("LQ window size   : %d\n", cnf->lq_wsize);
 
   printf("Clear screen     : %s\n", cnf->clear_screen ? "yes" : "no");
index acc6967..8e4c721 100644 (file)
@@ -38,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: oparse.y,v 1.27 2005/11/17 01:58:52 tlopatic Exp $
+ * $Id: oparse.y,v 1.28 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -149,6 +149,7 @@ static int lq_mult_helper(YYSTYPE ip_addr_arg, YYSTYPE mult_arg)
 %token TOK_MPRCOVERAGE
 %token TOK_LQ_LEVEL
 %token TOK_LQ_FISH
+%token TOK_LQ_DLIMIT
 %token TOK_LQ_WSIZE
 %token TOK_LQ_MULT
 %token TOK_CLEAR_SCREEN
@@ -200,6 +201,7 @@ stmt:       idebug
           | amprcoverage
           | alq_level
           | alq_fish
+          | alq_dlimit
           | alq_wsize
           | bclear_screen
           | vcomment
@@ -905,6 +907,15 @@ alq_fish: TOK_LQ_FISH TOK_INTEGER
 }
 ;
 
+alq_dlimit: TOK_LQ_DLIMIT TOK_INTEGER TOK_FLOAT
+{
+  if(PARSER_DEBUG) printf("Link quality dijkstra limit %d, %0.2f\n", $2->integer, $3->floating);
+  cnf->lq_dlimit = $2->integer;
+  cnf->lq_dinter = $3->floating;
+  free($2);
+}
+;
+
 alq_wsize: TOK_LQ_WSIZE TOK_INTEGER
 {
   if(PARSER_DEBUG) printf("Link quality window size %d\n", $2->integer);
index d099bc8..852156e 100644 (file)
@@ -38,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: oscan.lex,v 1.18 2005/11/17 01:58:52 tlopatic Exp $
+ * $Id: oscan.lex,v 1.19 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -372,6 +372,11 @@ IPV6ADDR {IP6PAT1}|{IP6PAT2}|{IP6PAT3}|{IP6PAT4}|{IP6PAT5}|{IP6PAT6}|{IP6PAT7}|{
   return TOK_LQ_FISH;
 }
 
+"LinkQualityDijkstraLimit" {
+  yylval = NULL;
+  return TOK_LQ_DLIMIT;
+}
+
 "LinkQualityWinSize" {
   yylval = NULL;
   return TOK_LQ_WSIZE;
index 8f49704..38b18b5 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: link_set.c,v 1.61 2005/10/23 20:58:14 tlopatic Exp $
+ * $Id: link_set.c,v 1.62 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -967,8 +967,14 @@ static void update_packet_loss_worker(struct link_entry *entry, int lost)
     {
       entry->saved_loss_link_quality = entry->loss_link_quality;
 
-      changes_neighborhood = OLSR_TRUE;
-      changes_topology = OLSR_TRUE;
+      if (olsr_cnf->lq_dlimit > 0)
+      {
+        changes_neighborhood = OLSR_TRUE;
+        changes_topology = OLSR_TRUE;
+      }
+
+      else
+        OLSR_PRINTF(3, "Skipping Dijkstra (1)\n")
 
       // create a new ANSN
 
index fff2e66..0ce1a7e 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsr.c,v 1.46 2005/05/29 12:47:45 br1 Exp $
+ * $Id: olsr.c,v 1.47 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 /**
@@ -69,7 +69,6 @@ olsr_bool changes_topology;
 olsr_bool changes_neighborhood;
 olsr_bool changes_hna;
 
-
 /**
  * Process changes functions
  */
index d4d7269..eaaef94 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsr_cfg.h,v 1.26 2005/11/17 01:58:52 tlopatic Exp $
+ * $Id: olsr_cfg.h,v 1.27 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -55,6 +55,8 @@
 #define DEF_USE_HYST        OLSR_TRUE
 #define DEF_LQ_LEVEL        0
 #define DEF_LQ_FISH         0
+#define DEF_LQ_DIJK_LIMIT   255
+#define DEF_LQ_DIJK_INTER   0.0
 #define DEF_LQ_WSIZE        10
 #define DEF_CLEAR_SCREEN    OLSR_FALSE
 
@@ -208,6 +210,8 @@ struct olsrd_config
   olsr_u8_t                lq_level;
   olsr_u32_t               lq_wsize;
   olsr_u8_t                lq_fish;
+  olsr_u8_t                lq_dlimit;
+  float                    lq_dinter;
   struct plugin_entry      *plugins;
   struct hna4_entry        *hna4_entries;
   struct hna6_entry        *hna6_entries;
index 079f34e..207b2b8 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: process_package.c,v 1.34 2005/04/11 18:43:40 kattemat Exp $
+ * $Id: process_package.c,v 1.35 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -128,8 +128,14 @@ olsr_hello_tap(struct hello_message *message, struct interface *in_if,
         {
           link->saved_neigh_link_quality = link->neigh_link_quality;
 
-          changes_neighborhood = OLSR_TRUE;
-          changes_topology = OLSR_TRUE;
+          if (olsr_cnf->lq_dlimit > 0)
+          {
+            changes_neighborhood = OLSR_TRUE;
+            changes_topology = OLSR_TRUE;
+          }
+
+          else
+            OLSR_PRINTF(3, "Skipping Dijkstra (2)\n")
 
           // create a new ANSN
 
@@ -645,8 +651,14 @@ olsr_process_message_neighbors(struct neighbor_entry *neighbor,
                           walker->saved_path_link_quality =
                             walker->path_link_quality;
 
-                          changes_neighborhood = OLSR_TRUE;
-                          changes_topology = OLSR_TRUE;
+                          if (olsr_cnf->lq_dlimit > 0)
+                          {
+                            changes_neighborhood = OLSR_TRUE;
+                            changes_topology = OLSR_TRUE;
+                          }
+
+                          else
+                            OLSR_PRINTF(3, "Skipping Dijkstra (3)\n")
                         }
                     }
                 }
index 70e1529..81cbe34 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: scheduler.c,v 1.31 2005/10/28 18:39:33 kattemat Exp $
+ * $Id: scheduler.c,v 1.32 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -64,6 +64,14 @@ static struct timeout_entry *timeout_functions;
 static struct event_entry *event_functions;
 
 
+static void trigger_dijkstra(void *dummy)
+{
+  OLSR_PRINTF(3, "Triggering Dijkstra\n");
+
+  changes_neighborhood = OLSR_TRUE;
+  changes_topology = OLSR_TRUE;
+}
+
 /**
  *Main scheduler event loop. Polls at every
  *sched_poll_interval and calls all functions
@@ -99,6 +107,9 @@ scheduler()
   /* Global buffer for times(2) calls */
   struct tms tms_buf;
  
+  if(olsr_cnf->lq_level > 1 && olsr_cnf->lq_dinter > 0.0)
+    olsr_register_scheduler_event(trigger_dijkstra, NULL, olsr_cnf->lq_dinter, 0, NULL);
+
   pollrate = olsr_cnf->pollrate;
   interval_usec = (olsr_u32_t)(pollrate * 1000000);
 
index bb61cd6..bf86251 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.c,v 1.22 2005/05/29 12:47:46 br1 Exp $
+ * $Id: tc_set.c,v 1.23 2005/11/17 04:25:44 tlopatic Exp $
  */
 
 
@@ -303,7 +303,11 @@ olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
                   existing_dst->saved_link_quality =
                     existing_dst->link_quality;
 
-                  retval = 1;
+                  if (msg->hop_count <= olsr_cnf->lq_dlimit)
+                    retval = 1;
+
+                  else
+                    OLSR_PRINTF(3, "Skipping Dijkstra (4)\n")
                 }
 
               saved_lq = existing_dst->saved_inverse_link_quality;
@@ -320,7 +324,11 @@ olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
                   existing_dst->saved_inverse_link_quality =
                     existing_dst->inverse_link_quality;
 
-                  retval = 1;
+                  if (msg->hop_count <= olsr_cnf->lq_dlimit)
+                    retval = 1;
+
+                  else
+                    OLSR_PRINTF(3, "Skipping Dijkstra (5)\n")
                 }
             }
        }