Fixed LQ MPR selection problem. Fixed LQ route addition crash.
authorThomas Lopatic <thomas@lopatic.de>
Wed, 16 Feb 2005 14:44:44 +0000 (14:44 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Wed, 16 Feb 2005 14:44:44 +0000 (14:44 +0000)
CHANGELOG
src/lq_mpr.c
src/lq_route.c
src/process_package.c
src/two_hop_neighbor_table.h

index 31f8c05..a5b26ef 100644 (file)
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,5 +1,5 @@
 This file states changes as of version 0.2.4:
-$Id: CHANGELOG,v 1.29 2005/02/16 06:52:13 kattemat Exp $
+$Id: CHANGELOG,v 1.30 2005/02/16 14:44:43 tlopatic Exp $
 
 0.4.9 ---------------------------------------------------------------------
 
@@ -99,6 +99,8 @@ BUGFIXES
   This caused olsrd not to work with global IPv6 addresses.
 - A bug in the IPv6 prefix-from IPaddr function has been fixed. This
   bug caused HNA prefixes to always be calculated to 0.
+- If a 2-hop neighbor is also a 1-hop neighbor, a bug made olsrd
+  prefer a bad direct link to a better link via an MPR.
 
 
 0.4.8 ---------------------------------------------------------------------
index 4427e5c..db3f567 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_mpr.c,v 1.8 2004/12/04 17:06:57 tlopatic Exp $
+ * $Id: lq_mpr.c,v 1.9 2005/02/16 14:44:43 tlopatic Exp $
  */
 
 #include "defs.h"
 #include "neighbor_table.h"
 #include "two_hop_neighbor_table.h"
+#include "link_set.h"
 #include "lq_mpr.h"
 
 void olsr_calculate_lq_mpr(void)
@@ -52,6 +53,7 @@ void olsr_calculate_lq_mpr(void)
   struct neighbor_entry *neigh;
   double best;
   olsr_bool mpr_changes = OLSR_FALSE;
+  struct link_entry *link;
 
   for(i = 0; i < HASHSIZE; i++)
     {
@@ -92,10 +94,36 @@ void olsr_calculate_lq_mpr(void)
 
           neigh = olsr_lookup_neighbor_table(&neigh2->neighbor_2_addr);
 
-          // it it's a neighbour and also symmetric, then skip it
+          // if it's a neighbour and also symmetric, then examine
+          // the link quality
           
           if (neigh != NULL && neigh->status == SYM)
-            continue;
+            {
+              // if the direct link is better than the best route via
+              // an MPR, then prefer the direct link and do not select
+              // an MPR for this 2-hop neighbour
+
+              // determine the link quality of the direct link
+
+              link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
+
+              best = link->loss_link_quality * link->neigh_link_quality;
+
+              // see wether we find a better route via an MPR
+
+              for (walker = neigh2->neighbor_2_nblist.next;
+                   walker != &neigh2->neighbor_2_nblist;
+                   walker = walker->next)
+                if (walker->path_link_quality > best)
+                  break;
+
+              // we've reached the end of the list, so we haven't found
+              // a better route via an MPR - so, skip MPR selection for
+              // this 1-hop neighbor
+
+              if (walker == &neigh2->neighbor_2_nblist)
+                continue;
+            }
 
           // find the connecting 1-hop neighbours with the
           // best total link qualities
index 2ce46f7..0c8459a 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.25 2005/02/14 15:54:30 tlopatic Exp $
+ * $Id: lq_route.c,v 1.26 2005/02/16 14:44:44 tlopatic Exp $
  */
 
 #include "defs.h"
 #include "tc_set.h"
 #include "neighbor_table.h"
+#include "two_hop_neighbor_table.h"
 #include "link_set.h"
 #include "routing_table.h"
 #include "mid_set.h"
@@ -325,6 +326,8 @@ void olsr_calculate_lq_routing_table(void)
   struct hna_entry *hna_gw;
   struct hna_net *hna;
   struct rt_entry *gw_rt, *hna_rt, *head_rt;
+  struct neighbor_2_entry *neigh2;
+  struct neighbor_list_entry *neigh_walker;
 
   if (ipsize == 4)
     avl_comp = avl_comp_ipv4;
@@ -350,6 +353,15 @@ void olsr_calculate_lq_routing_table(void)
         add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
                    INFINITE_ETX);
 
+  // add our two-hop neighbours
+
+  for (i = 0; i < HASHSIZE; i++)
+    for (neigh2 = two_hop_neighbortable[i].next;
+         neigh2 != &two_hop_neighbortable[i];
+         neigh2 = neigh2->next)
+      add_vertex(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
+                 INFINITE_ETX);
+
   // add remaining vertices
 
   for (i = 0; i < HASHSIZE; i++)
@@ -387,6 +399,28 @@ void olsr_calculate_lq_routing_table(void)
           }
       }
 
+  // add edges between our neighbours and our two-hop neighbours
+
+  for (i = 0; i < HASHSIZE; i++)
+    for (neigh2 = two_hop_neighbortable[i].next;
+         neigh2 != &two_hop_neighbortable[i];
+         neigh2 = neigh2->next)
+      for (neigh_walker = neigh2->neighbor_2_nblist.next;
+           neigh_walker != &neigh2->neighbor_2_nblist;
+           neigh_walker = neigh_walker->next)
+      {
+        if (neigh_walker->second_hop_link_quality >=
+            MIN_LINK_QUALITY * MIN_LINK_QUALITY)
+        {
+          neigh = neigh_walker->neighbor;
+
+          etx = 1.0 / neigh_walker->second_hop_link_quality;
+
+          add_edge(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
+                   &neigh->neighbor_main_addr, etx);
+        }
+      }
+
   // add remaining edges
 
   for (i = 0; i < HASHSIZE; i++)
@@ -483,6 +517,7 @@ void olsr_calculate_lq_routing_table(void)
 #endif
 
     // add a route to the main address of the destination node
+
     link = get_best_link_to_neighbor(&walker->addr);
 
     olsr_insert_routing_table(&vert->addr,
@@ -494,13 +529,12 @@ void olsr_calculate_lq_routing_table(void)
 
     for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
          mid_walker = mid_walker->next_alias)
-      {
-       link = get_best_link_to_neighbor(&mid_walker->alias);
-       olsr_insert_routing_table(&mid_walker->alias,
-                                 &link->neighbor_iface_addr,
-                                 if_ifwithaddr(&link->local_iface_addr),
-                                 hops);
-      }
+    {
+      olsr_insert_routing_table(&mid_walker->alias,
+                                &link->neighbor_iface_addr,
+                                if_ifwithaddr(&link->local_iface_addr),
+                                hops);
+    }
   }
 
   // add HNA routes - the set of unprocessed network nodes contains
index 6804d5a..464e454 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.30 2005/02/14 15:54:30 tlopatic Exp $
+ * $Id: process_package.c,v 1.31 2005/02/16 14:44:44 tlopatic Exp $
  */
 
 
@@ -596,11 +596,20 @@ olsr_process_message_neighbors(struct neighbor_entry *neighbor,
                       // so comparing path link quality values with ">" is
                       // equivalent to comparing ETX values with "<"
 
-                      walker->path_link_quality =
-                        link->loss_link_quality * link->neigh_link_quality *
+                      // the link quality between the 1-hop neighbour and the
+                      // 2-hop neighbour
+
+                      walker->second_hop_link_quality =
                         message_neighbors->link_quality *
                         message_neighbors->neigh_link_quality;
 
+                      // the total quality for the route
+                      // "us --- 1-hop --- 2-hop"
+
+                      walker->path_link_quality =
+                        walker->second_hop_link_quality *
+                        link->loss_link_quality * link->neigh_link_quality;
+
                       // if the link quality has changed by more than 10
                       // percent, signal
 
@@ -649,6 +658,7 @@ olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_en
 
   list_of_1_neighbors->path_link_quality = 0.0;
   list_of_1_neighbors->saved_path_link_quality = 0.0;
+  list_of_1_neighbors->second_hop_link_quality = 0.0;
 
   /* Queue */
   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
index fe2fe6a..83a95d0 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: two_hop_neighbor_table.h,v 1.11 2004/12/04 17:06:57 tlopatic Exp $
+ * $Id: two_hop_neighbor_table.h,v 1.12 2005/02/16 14:44:44 tlopatic Exp $
  */
 
 
@@ -52,6 +52,7 @@
 struct neighbor_list_entry 
 {
   struct       neighbor_entry *neighbor;
+  double        second_hop_link_quality;
   double        path_link_quality;
   double        saved_path_link_quality;
   struct       neighbor_list_entry *next;