[Olsr-dev] [PATCH v1 1/1] lq_packet: only report a neighbour once in a hello message

Ferry Huberts (spam-protected)
Fri Jan 13 09:05:28 CET 2017


From: "Iwan G. Flameling" <(spam-protected)>

A while ago we noticed that neighbours of nodes with multiple interfaces
on the same medium report infinite costs on their links to those nodes.

This problem is 100% reproducible.

Below is the setup in which we noticed the problem.

       wlan0                                                 wlan0
       172.31.175.97/16                           172.31.175.61/16
    (((*))) ------------------------------------------------- (((*)))
       |                                                         |
       |                                                         |
       |                                                         |
   ____|___   172.29.175.97/15   ________  172.29.175.61/15  ____|____
  |         |-eth1.2580---------|        |--------eth1.2580-|         |
  | Node 97 |                   | Switch |                  | Node 61 |
  |_________|-eth2.2580---------|________|                  |_________|
              172.28.175.97/15

In this setup node 97 will report normal link costs for its (wired) links
to node 61 (see the first table below), while node 61 will report infinite
link costs for both its (wired) links to node 97 (see the second table
below).

  Table: Links (node 97)
  Local IP       Remote IP       Hyst.   LQ      NLQ     Cost
  172.29.175.97  172.29.175.61   0.000   1.000   1.000   0.100
  172.28.175.97  172.29.175.61   0.000   1.000   1.000   0.100
  172.31.175.97  172.31.175.61   0.000   1.000   1.000   1.000

  Table: Links (node 61)
  Local IP       Remote IP       Hyst.   LQ      NLQ     Cost
  172.29.175.61  172.29.175.97   0.000   1.000   0.000   INFINITE
  172.29.175.61  172.28.175.97   0.000   1.000   0.000   INFINITE
  172.31.175.61  172.31.175.97   0.000   1.000   1.000   1.000

Checking the HELLO messages that are received on node 61 from node 97,
we see the following:

  [node 61] # tcpdump -vni eth1.2580 udp port 698
  tcpdump: listening on eth1.2580, link-type EN10MB (Ethernet), capture size 262144 bytes
  06:21:23.528204 IP (tos 0xc0, ttl 1, id 42455, offset 0, flags [DF], proto UDP (17), length 80)
      172.28.175.97.698 > 255.255.255.255.698: OLSRv4, seq 0xf7c0, length 52
     Hello-LQ Message (0xc9), originator 172.31.175.97, ttl 1, hop 0
       vtime 3.000s, msg-seq 0x533d, length 48
       hello-time 1.000s, MPR willingness 3
         link-type Symmetric, neighbor-type Symmetric, len 12
           neighbor 172.29.175.61, link-quality 0.00%, neighbor-link-quality 0.00%
         link-type Unspecified, neighbor-type Symmetric, len 20
           neighbor 172.31.175.61, link-quality 0.00%, neighbor-link-quality 0.00%
           neighbor 172.29.175.61, link-quality 0.00%, neighbor-link-quality 0.00%

Node 61 receives HELLO messages from node 97 that report (amongst others):
1- a  SYMMETRIC   link-type to node 61 (172.29.175.61)
2- an UNSPECIFIED link-type to node 61 (172.29.175.61)

Clearly, this is 'confusing' and the root cause of why node 61 reports
infinite costs for the links, as shown above.

We pose that in a HELLO message the same neighbour should NEVER be
reported with conflicting information.

Proposed solution:

1- NEVER report a neighbour more than once in a HELLO message
2- Use the 'best' values for a neighbour that is reported in a HELLO
   message

This requires:

1- De-duplication of neighbours when constructing a HELLO message.

2- When a neighbour is already present in the HELLO message
   that is under construction then he 'best' values must be determined
   and those in the neighbour that is already present should only be
   overwritten if those are worse.

This patch implements that solution.

Signed-off-by: Iwan G. Flameling <(spam-protected)>
Signed-off-by: Ferry Huberts <(spam-protected)>
---
 src/lq_packet.c               |  52 ++++++++++++----
 src/lq_plugin.c               |   5 +-
 src/lq_plugin.h               |   4 +-
 src/lq_plugin_default_ff.c    |  13 +++-
 src/lq_plugin_default_ffeth.c |  13 +++-
 src/lq_plugin_default_float.c |  19 +++++-
 src/lq_plugin_default_fpm.c   |  19 +++++-
 src/olsr_protocol.h           | 136 ++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 236 insertions(+), 25 deletions(-)

diff --git a/src/lq_packet.c b/src/lq_packet.c
index d44e654..2e8e027 100644
--- a/src/lq_packet.c
+++ b/src/lq_packet.c
@@ -68,6 +68,21 @@ bool lq_tc_pending = false;
 static uint32_t msg_buffer_aligned[(MAXMESSAGESIZE - OLSR_HEADERSIZE) / sizeof(uint32_t) + 1];
 static unsigned char *const msg_buffer = (unsigned char *)msg_buffer_aligned;
 
+static struct lq_hello_neighbor * neigh_find(struct link_entry *link, struct lq_hello_message *lq_hello) {
+  struct lq_hello_neighbor *neigh;
+
+  assert(link);
+  assert(lq_hello);
+
+  for (neigh = lq_hello->neigh; neigh; neigh = neigh->next) {
+    if (ipequal(&link->neighbor_iface_addr, &neigh->addr)) {
+      return neigh;
+    }
+  }
+
+  return NULL ;
+}
+
 static void
 create_lq_hello(struct lq_hello_message *lq_hello, struct interface_olsr *outif)
 {
@@ -92,46 +107,57 @@ create_lq_hello(struct lq_hello_message *lq_hello, struct interface_olsr *outif)
   // loop through the link set
 
   OLSR_FOR_ALL_LINK_ENTRIES(walker) {
+    uint8_t link_type;
+    uint8_t neigh_type;
 
     // allocate a neighbour entry
-    struct lq_hello_neighbor *neigh = olsr_malloc_lq_hello_neighbor("Build LQ_HELLO");
+    struct lq_hello_neighbor *neigh = neigh_find(walker, lq_hello);
+    bool neigh_is_new = (neigh == NULL );
+    neigh = neigh_is_new ? olsr_malloc_lq_hello_neighbor("Build LQ_HELLO") : neigh;
 
     // a) this neighbor interface IS NOT visible via the output interface
     if (!ipequal(&walker->local_iface_addr, &outif->ip_addr))
-      neigh->link_type = UNSPEC_LINK;
+      link_type = UNSPEC_LINK;
 
     // b) this neighbor interface IS visible via the output interface
 
     else
-      neigh->link_type = lookup_link_status(walker);
+      link_type = lookup_link_status(walker);
+
+    if (neigh_is_new || link_type_compare(neigh->link_type, link_type))
+      neigh->link_type = link_type;
 
     // set the entry's link quality
-    olsr_copy_hello_lq(neigh, walker);
+    olsr_copy_hello_lq(neigh, walker, neigh_is_new);
 
     // set the entry's neighbour type
 
     if (walker->neighbor->is_mpr)
-      neigh->neigh_type = MPR_NEIGH;
+      neigh_type = MPR_NEIGH;
 
     else if (walker->neighbor->status == SYM)
-      neigh->neigh_type = SYM_NEIGH;
+      neigh_type = SYM_NEIGH;
 
     else if (walker->neighbor->status == NOT_SYM)
-      neigh->neigh_type = NOT_NEIGH;
+      neigh_type = NOT_NEIGH;
 
     else {
       OLSR_PRINTF(0, "Error: neigh_type undefined");
-      neigh->neigh_type = NOT_NEIGH;
+      neigh_type = NOT_NEIGH;
     }
 
-    // set the entry's neighbour interface address
+    if (neigh_is_new || neigh_type_compare(neigh->neigh_type, neigh_type))
+      neigh->neigh_type = neigh_type;
 
-    neigh->addr = walker->neighbor_iface_addr;
+    if (neigh_is_new) {
+      // set the entry's neighbour interface address
 
-    // queue the neighbour entry
-    neigh->next = lq_hello->neigh;
-    lq_hello->neigh = neigh;
+      neigh->addr = walker->neighbor_iface_addr;
 
+      // queue the neighbour entry
+      neigh->next = lq_hello->neigh;
+      lq_hello->neigh = neigh;
+    }
   }
   OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 }
diff --git a/src/lq_plugin.c b/src/lq_plugin.c
index a917c84..01c6e4e 100644
--- a/src/lq_plugin.c
+++ b/src/lq_plugin.c
@@ -351,13 +351,14 @@ get_linkcost_scaled(olsr_linkcost cost, bool route)
  *
  * @param target pointer to target lq_hello_neighbor
  * @param source pointer to source link_entry
+ * @param force true to force the copy, otherwise only copy when source is 'better' than target
  */
 void
-olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source)
+olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source, bool force)
 {
   assert((const char *)target + sizeof(*target) >= (const char *)target->linkquality);
   assert((const char *)source + sizeof(*source) >= (const char *)source->linkquality);
-  active_lq_handler->copy_link_lq_into_neigh(target->linkquality, source->linkquality);
+  active_lq_handler->copy_link_lq_into_neigh(target->linkquality, source->linkquality, force);
 }
 
 /**
diff --git a/src/lq_plugin.h b/src/lq_plugin.h
index 747a70c..26baba4 100644
--- a/src/lq_plugin.h
+++ b/src/lq_plugin.h
@@ -76,7 +76,7 @@ struct lq_handler {
   void (*packet_loss_handler) (struct link_entry * entry, void *lq, bool lost);
 
   void (*memorize_foreign_hello) (void *local, void *foreign);
-  void (*copy_link_lq_into_neigh) (void *target, void *source);
+  void (*copy_link_lq_into_neigh) (void *target, void *source, bool force);
   void (*copy_link_lq_into_tc) (void *target, void *source);
   void (*clear_hello) (void *target);
   void (*clear_tc) (void *target);
@@ -134,7 +134,7 @@ const char *get_linkcost_text(olsr_linkcost cost, bool route, struct lqtextbuffe
 double get_linkcost_scaled(olsr_linkcost cost, bool route);
 
 void olsr_clear_hello_lq(struct link_entry */*link*/);
-void olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source);
+void olsr_copy_hello_lq(struct lq_hello_neighbor *target, struct link_entry *source, bool force);
 void olsr_copylq_link_entry_2_tc_mpr_addr(struct tc_mpr_addr *target, struct link_entry *source);
 void olsr_copylq_link_entry_2_tc_edge_entry(struct tc_edge_entry *target, struct link_entry *source);
 void olsr_clear_tc_lq(struct tc_mpr_addr *target);
diff --git a/src/lq_plugin_default_ff.c b/src/lq_plugin_default_ff.c
index 3d6ba6a..fa617e3 100644
--- a/src/lq_plugin_default_ff.c
+++ b/src/lq_plugin_default_ff.c
@@ -70,7 +70,7 @@ static void default_lq_deserialize_hello_lq_pair_ff(const uint8_t ** curr, void
 static int default_lq_serialize_tc_lq_pair_ff(unsigned char *buff, void *lq);
 static void default_lq_deserialize_tc_lq_pair_ff(const uint8_t ** curr, void *lq);
 
-static void default_lq_copy_link2neigh_ff(void *t, void *s);
+static void default_lq_copy_link2neigh_ff(void *t, void *s, bool force);
 static void default_lq_copy_link2tc_ff(void *target, void *source);
 static void default_lq_clear_ff(void *target);
 static void default_lq_clear_ff_hello(void *target);
@@ -371,11 +371,18 @@ default_lq_memorize_foreign_hello_ff(void *ptrLocal, void *ptrForeign)
 }
 
 static void
-default_lq_copy_link2neigh_ff(void *t, void *s)
+default_lq_copy_link2neigh_ff(void *t, void *s, bool force)
 {
   struct default_lq_ff *target = t;
   struct default_lq_ff_hello *source = s;
-  *target = source->smoothed_lq;
+
+  if (force) {
+    *target = source->smoothed_lq;
+    return;
+  }
+
+  target->valueLq = MAX(target->valueLq, source->smoothed_lq.valueLq);
+  target->valueNlq = MAX(target->valueNlq, source->smoothed_lq.valueNlq);
 }
 
 static void
diff --git a/src/lq_plugin_default_ffeth.c b/src/lq_plugin_default_ffeth.c
index e78dcd7..0e9408e 100644
--- a/src/lq_plugin_default_ffeth.c
+++ b/src/lq_plugin_default_ffeth.c
@@ -72,7 +72,7 @@ static void default_lq_deserialize_hello_lq_pair_ffeth(const uint8_t ** curr, vo
 static int default_lq_serialize_tc_lq_pair_ffeth(unsigned char *buff, void *lq);
 static void default_lq_deserialize_tc_lq_pair_ffeth(const uint8_t ** curr, void *lq);
 
-static void default_lq_copy_link2neigh_ffeth(void *t, void *s);
+static void default_lq_copy_link2neigh_ffeth(void *t, void *s, bool force);
 static void default_lq_copy_link2tc_ffeth(void *target, void *source);
 static void default_lq_clear_ffeth(void *target);
 static void default_lq_clear_ffeth_hello(void *target);
@@ -410,11 +410,18 @@ default_lq_memorize_foreign_hello_ffeth(void *ptrLocal, void *ptrForeign)
 }
 
 static void
-default_lq_copy_link2neigh_ffeth(void *t, void *s)
+default_lq_copy_link2neigh_ffeth(void *t, void *s, bool force)
 {
   struct default_lq_ffeth *target = t;
   struct default_lq_ffeth_hello *source = s;
-  *target = source->smoothed_lq;
+
+  if (force) {
+    *target = source->smoothed_lq;
+    return;
+  }
+
+  target->valueLq = MAX(target->valueLq, source->smoothed_lq.valueLq);
+  target->valueNlq = MAX(target->valueNlq, source->smoothed_lq.valueNlq);
 }
 
 static void
diff --git a/src/lq_plugin_default_float.c b/src/lq_plugin_default_float.c
index 2e07686..f7e2031 100644
--- a/src/lq_plugin_default_float.c
+++ b/src/lq_plugin_default_float.c
@@ -59,6 +59,7 @@ static int default_lq_serialize_hello_lq_pair_float(unsigned char *buff, void *l
 static void default_lq_deserialize_hello_lq_pair_float(const uint8_t ** curr, void *lq);
 static int default_lq_serialize_tc_lq_pair_float(unsigned char *buff, void *lq);
 static void default_lq_deserialize_tc_lq_pair_float(const uint8_t ** curr, void *lq);
+static void default_lq_copy_link2neigh_float(void *t, void *s, bool force);
 static void default_lq_copy_link2tc_float(void *target, void *source);
 static void default_lq_clear_float(void *target);
 static const char *default_lq_print_float(void *ptr, char separator, struct lqtextbuffer *buffer);
@@ -74,7 +75,7 @@ struct lq_handler lq_etx_float_handler = {
 
   &default_lq_packet_loss_worker_float,
   &default_lq_memorize_foreign_hello_float,
-  &default_lq_copy_link2tc_float,
+  &default_lq_copy_link2neigh_float,
   &default_lq_copy_link2tc_float,
   &default_lq_clear_float,
   &default_lq_clear_float,
@@ -207,6 +208,22 @@ default_lq_memorize_foreign_hello_float(void *ptrLocal, void *ptrForeign)
 }
 
 static void
+default_lq_copy_link2neigh_float(void *t, void *s, bool force)
+{
+  struct default_lq_float *target = t;
+  struct default_lq_float *source = s;
+
+  if (force) {
+    memcpy(target, source, sizeof(struct default_lq_float));
+    return;
+  }
+
+  target->lq = MAX(target->lq, source->lq);
+  target->nlq = MAX(target->nlq, source->nlq);
+  target->quickstart = MAX(target->quickstart, source->quickstart);
+}
+
+static void
 default_lq_copy_link2tc_float(void *target, void *source)
 {
   memcpy(target, source, sizeof(struct default_lq_float));
diff --git a/src/lq_plugin_default_fpm.c b/src/lq_plugin_default_fpm.c
index fbfa0cf..2947f92 100644
--- a/src/lq_plugin_default_fpm.c
+++ b/src/lq_plugin_default_fpm.c
@@ -60,6 +60,7 @@ static int default_lq_serialize_hello_lq_pair_fpm(unsigned char *buff, void *lq)
 static void default_lq_deserialize_hello_lq_pair_fpm(const uint8_t ** curr, void *lq);
 static int default_lq_serialize_tc_lq_pair_fpm(unsigned char *buff, void *lq);
 static void default_lq_deserialize_tc_lq_pair_fpm(const uint8_t ** curr, void *lq);
+static void default_lq_copy_link2neigh_fpm(void *t, void *s, bool force);
 static void default_lq_copy_link2tc_fpm(void *target, void *source);
 static void default_lq_clear_fpm(void *target);
 static const char *default_lq_print_fpm(void *ptr, char separator, struct lqtextbuffer *buffer);
@@ -75,7 +76,7 @@ struct lq_handler lq_etx_fpm_handler = {
 
   &default_lq_packet_loss_worker_fpm,
   &default_lq_memorize_foreign_hello_fpm,
-  &default_lq_copy_link2tc_fpm,
+  &default_lq_copy_link2neigh_fpm,
   &default_lq_copy_link2tc_fpm,
   &default_lq_clear_fpm,
   &default_lq_clear_fpm,
@@ -224,6 +225,22 @@ default_lq_copy_link2tc_fpm(void *target, void *source)
 }
 
 static void
+default_lq_copy_link2neigh_fpm(void *t, void *s, bool force)
+{
+  struct default_lq_fpm *target = t;
+  struct default_lq_fpm *source = s;
+
+  if (force) {
+    memcpy(target, source, sizeof(struct default_lq_fpm));
+    return;
+  }
+
+  target->valueLq = MAX(target->valueLq, source->valueLq);
+  target->valueNlq = MAX(target->valueNlq, source->valueNlq);
+  target->quickstart = MAX(target->quickstart, source->quickstart);
+}
+
+static void
 default_lq_clear_fpm(void *target)
 {
   memset(target, 0, sizeof(struct default_lq_fpm));
diff --git a/src/olsr_protocol.h b/src/olsr_protocol.h
index a995db0..ed3e134 100644
--- a/src/olsr_protocol.h
+++ b/src/olsr_protocol.h
@@ -111,6 +111,83 @@ struct olsr;
 #define HIDE_LINK             4
 #define MAX_LINK              4
 
+/**
+ * Compare two link types.
+ *
+ * <pre>
+ * +-------------+------+------+--------+------+-----+
+ * |             |        link_type_new              |
+ * |             +------+------+--------+------+-----+
+ * | link_type   | HIDE | LOST | UNSPEC | ASYM | SYM |
+ * |-------------+------+------+--------+------+-----+
+ * | HIDE        |  F   |  T   |   T    |  T   |  T  |
+ * | LOST        |  F   |  F   |   T    |  T   |  T  |
+ * | UNSPEC      |  F   |  F   |   F    |  T   |  T  |
+ * | ASYM        |  F   |  F   |   F    |  F   |  T  |
+ * | SYM         |  F   |  F   |   F    |  F   |  F  |
+ * +-------------+------+------+--------+------+-----+
+ * </pre>
+ *
+ * @param link_type a link type
+ * @param link_type_new a (new) link type
+ * @return true when link_type_new is 'better' than link_type
+ */
+static INLINE bool link_type_compare(int link_type, int link_type_new) {
+  switch (link_type_new) {
+    case SYM_LINK:
+      switch (link_type) {
+        case SYM_LINK:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case ASYM_LINK:
+      switch (link_type) {
+        case SYM_LINK:
+        case ASYM_LINK:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case UNSPEC_LINK:
+      switch (link_type) {
+        case SYM_LINK:
+        case ASYM_LINK:
+        case UNSPEC_LINK:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case LOST_LINK:
+      switch (link_type) {
+        case SYM_LINK:
+        case ASYM_LINK:
+        case UNSPEC_LINK:
+        case LOST_LINK:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case HIDE_LINK:
+      return false;
+
+    default:
+      return true;
+  }
+}
+
 static INLINE const char * linkTypeToString(int type) {
   switch (type) {
     case ASYM_LINK:
@@ -140,6 +217,65 @@ static INLINE const char * linkTypeToString(int type) {
 #define MPR_NEIGH             2
 #define MAX_NEIGH             2
 
+/**
+ * Compare two neighbour types.
+ *
+ * <pre>
+ * +-------+------+-----+-----+
+ * |       |     neigh_new    |
+ * |       +------+-----+-----+
+ * | neigh | NOT  | SYM | MPR |
+ * |-------+------+-----+-----+
+ * | NOT   |  F   |  T  |  T  |
+ * | SYM   |  F   |  F  |  T  |
+ * | MPR   |  F   |  F  |  F  |
+ * +-------+------+-----+-----+
+ * </pre>
+ *
+ * @param neigh a neighbour type
+ * @param neigh_new a (new) neighbour type
+ * @return true when neigh_new is 'better' than neigh
+ */
+static INLINE bool neigh_type_compare(int neigh, int neigh_new) {
+  switch (neigh_new) {
+    case MPR_NEIGH:
+      switch (neigh) {
+        case MPR_NEIGH:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case SYM_NEIGH:
+      switch (neigh) {
+        case MPR_NEIGH:
+        case SYM_NEIGH:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    case NOT_NEIGH:
+      switch (neigh) {
+        case MPR_NEIGH:
+        case SYM_NEIGH:
+        case NOT_NEIGH:
+          return false;
+
+        default:
+          return true;
+      }
+      break;
+
+    default:
+      return true;
+  }
+}
+
 /*
  *Neighbor status
  */
-- 
2.9.3




More information about the Olsr-dev mailing list