Fix path metric calculation
authorJonathan Kirchhoff <jonathan.kirchhoff@fkie.fraunhofer.de>
Tue, 31 Jan 2017 13:08:37 +0000 (14:08 +0100)
committerJonathan Kirchhoff <jonathan.kirchhoff@fkie.fraunhofer.de>
Tue, 31 Jan 2017 13:08:37 +0000 (14:08 +0100)
The problem was that in some occasions, the maximum link metric value RFC7181_METRIC_INFINITE was used in path metric comparisons when RFC7181_METRIC_INFINITE_PATH should have been used, causing incorrect MPR sets and possibly failing assertions during validation.

src-plugins/nhdp/mpr/mpr.c
src-plugins/nhdp/mpr/neighbor-graph-flooding.c
src-plugins/nhdp/mpr/neighbor-graph-routing.c
src-plugins/nhdp/mpr/neighbor-graph.c

index 891360e..d567061 100644 (file)
@@ -293,13 +293,16 @@ _validate_mpr_set(const struct nhdp_domain *domain, struct neighbor_graph *graph
   {
     d_y_n1 = mpr_calculate_d_of_y_s(domain, graph, n2_addr, &graph->set_n1);
     d_y_mpr = mpr_calculate_d_of_y_s(domain, graph, n2_addr, &graph->set_mpr);
+    
+    OONF_DEBUG(LOG_MPR, "d_y_n1 = %u", d_y_n1);
+    OONF_DEBUG(LOG_MPR, "d_y_n1 = %u", d_y_mpr);
 
     /*
      * Second property: For any y in N2 that does not have a defined d1(y), 
      * there is at least one element in M that is also in N1(y). This is 
      * equivalent to the requirement that d(y, M) is defined.
      */
-    assert(d_y_mpr != RFC7181_METRIC_INFINITE);
+    assert(d_y_mpr < RFC7181_METRIC_INFINITE_PATH);
 
     /*
      * Third property: For any y in N2, d(y,M) = d(y, N1).
index 75c8770..7244993 100644 (file)
@@ -167,7 +167,11 @@ _calculate_d2_x_y(const struct nhdp_domain *domain,
 static uint32_t
 _calculate_d_x_y(const struct nhdp_domain *domain,
     struct n1_node *x, struct addr_node *y) {
-  return _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
+  uint32_t cost = _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
+  if (cost >= RFC7181_METRIC_INFINITE_PATH) {
+    return RFC7181_METRIC_INFINITE_PATH;
+  }
+  return cost;
 }
 
 /**
index 19f9a30..32ea8b5 100644 (file)
@@ -163,20 +163,12 @@ _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct ad
   struct nhdp_link *lnk;
   struct nhdp_l2hop_domaindata *twohopdata;
 
-//  #ifdef OONF_LOG_DEBUG_INFO
-//  struct netaddr_str buf1;
-//#endif
-
-//  OONF_DEBUG(LOG_MPR, "Calculate d2(x,y), look for address %s", netaddr_to_string(&buf1, &y->addr));
   /* find the corresponding 2-hop entry, if it exists */
   list_for_each_element(&x->neigh->_links, lnk, _neigh_node) {
     l2hop = avl_find_element(&lnk->_2hop,
         &y->addr, l2hop, _link_node);
-//    OONF_DEBUG(LOG_MPR, "Addresses of 2hop link");
-//    mpr_print_addr_set(&lnk->_2hop);
     if (l2hop) {
       twohopdata = nhdp_domain_get_l2hopdata(domain, l2hop);
-//      OONF_DEBUG(LOG_MPR, "Got one with metric %i and address %s", l2hop->_domaindata[0].metric.in, netaddr_to_string(&buf1, &l2hop->twohop_addr));
       return twohopdata->metric.in;
     }
   }
@@ -185,7 +177,11 @@ _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct ad
 
 static uint32_t
 _calculate_d_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y) {
-  return _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
+  uint32_t cost = _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
+  if (cost >= RFC7181_METRIC_INFINITE_PATH) {
+    return RFC7181_METRIC_INFINITE_PATH;
+  }
+  return cost;
 }
 
 /**
@@ -241,10 +237,16 @@ static void
 _calculate_n1(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
   struct nhdp_neighbor *neigh;
 
+  #ifdef OONF_LOG_DEBUG_INFO
+  struct netaddr_str buf1;
+  #endif
+  
   OONF_DEBUG(LOG_MPR, "Calculate N1 for routing MPRs");
   
   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
     if (_is_allowed_neighbor_tuple(domain, neigh)) {
+      OONF_DEBUG(LOG_MPR, "Add neighbor %s in: %u", netaddr_to_string(&buf1, &neigh->originator),
+                 neigh->_domaindata[0].metric.in);
       mpr_add_n1_node_to_set(&graph->set_n1, neigh, NULL);
     }
   }
@@ -276,6 +278,7 @@ _calculate_n2(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
         avl_for_each_element(&lnk->_2hop, twohop, _link_node) {
           OONF_DEBUG(LOG_MPR, "Link status %u", lnk->neigh->symmetric);
           if (_is_allowed_2hop_tuple(domain, twohop)) {
+
 #ifdef OONF_LOG_DEBUG_INFO
             neighdata = nhdp_domain_get_l2hopdata(domain, twohop);
             OONF_DEBUG(LOG_MPR, "Add twohop addr %s in: %u out: %u",
index 3d21611..3944ef9 100644 (file)
@@ -181,7 +181,7 @@ mpr_calculate_minimal_d_z_y(const struct nhdp_domain *domain,
   struct n1_node *z_node;
   uint32_t d_z_y, min_d_z_y;
 
-  min_d_z_y = RFC7181_METRIC_INFINITE;
+  min_d_z_y = RFC7181_METRIC_INFINITE_PATH;
 
   avl_for_each_element(&graph->set_n1, z_node, _avl_node) {
     d_z_y = graph->methods->calculate_d_x_y(domain, z_node, y);
@@ -253,11 +253,21 @@ mpr_calculate_d_of_y_s(const struct nhdp_domain *domain, struct neighbor_graph *
     struct avl_tree *subset_s) {
   uint32_t d_x_y, min_cost;
   struct n1_node *node_n1;
+  
+  #ifdef OONF_LOG_DEBUG_INFO
+  struct netaddr_str buf1;
+  #endif
 
   /* determine the minimum cost to y over all possible intermediate hops */
   min_cost = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, &y->addr);
+  if (min_cost == RFC7181_METRIC_INFINITE) {
+    min_cost = RFC7181_METRIC_INFINITE_PATH;
+  }
+  OONF_DEBUG(LOG_MPR, "mpr_calculate_d_of_y_s(%s)", netaddr_to_string(&buf1, &y->addr));
+  OONF_DEBUG(LOG_MPR, "initial cost = %u", min_cost);
   avl_for_each_element(subset_s, node_n1, _avl_node) {
     d_x_y = graph->methods->calculate_d_x_y(domain, node_n1, y);
+    OONF_DEBUG(LOG_MPR, "cost via %s would be = %u", netaddr_to_string(&buf1, &node_n1->addr), d_x_y);
     if (d_x_y < min_cost) {
       min_cost = d_x_y;
     }