nwstate.c

tinyos-2.x.rar

 * relaxes the neighbors of cur
 */
float getMetric(link_t *l) {
  return l->qual;
  //return ((float)l->qual / 3000.0)  + 1.0;
  //return (10. / (float)l->nobs);
}
void update_neighbors(router_t *cur) {
  link_t *l;
  router_t *otherguy;
  // clunky iterator
  for (l = cur->links; l != NULL; l = (cur == l->n1) ? l->next1 : l->next2) {
    otherguy = (cur == l->n1) ? l->n2 : l->n1;
    
    if (cur->sp.dist + getMetric(l) < otherguy->sp.dist) {
      otherguy->sp.dist = cur->sp.dist + getMetric(l);
      otherguy->sp.prev = cur;
    }
  }
}

router_t *extract_min(router_t **list) {
  router_t *r, *prev = NULL, *min = NULL, *prev_min = NULL;
  float min_dist = FLT_MAX;
  for (r = *list; r != NULL; r = r->sp.setptr) {
    if (r->sp.dist < min_dist) {
      min_dist = r->sp.dist;
      min = r;
      prev_min = prev;
    }
    prev = r;
  }

  if (min == NULL) {
    // it might be the case that not everyone is reachable.  In that
    // case, we'll just leave them unconnected.
    *list = NULL;
  } else if (prev_min == NULL) {
    // the first element was the best, set list is pointed at the second element
    *list = (*list)->sp.setptr;
  } else {
    // otherwise just remove the min element from the list
    prev_min->sp.setptr = min->sp.setptr;
  }

  return min;
}

void age_routers() {
  router_t *r;
  int max_reports = 0;
  for (r = router_list; r != NULL; r = r->next) {
    if (r->reports > max_reports) {
      max_reports = r->reports;
    }
    // debug("nwstate: node: %i reports: %i\n", r->id, r->reports);
  }
  if (max_reports == 4) {
    debug("age_routers: max: %i\n", max_reports);
    for (r = router_list; r != NULL; r = r->next) {
      if (r->reports > 0) {
        r->reports = 0;
      } else {
        // debug("nwstate: removing router 0x%x due to age %i\n", r->id, r->reports);
        // nw_inval_node(r->id);
        r->reports = 0;
      }
    }
  }
}

/*
 * compute all destinations shortest path to node v1
 */
void compute_routes(node_id_t v1) {
  router_t *r, *cur = NULL, *not_visited = NULL;
  routes_out_of_date = 0;

  for (r = router_list; r != NULL; r = r->next) {
    r->sp.dist = FLT_MAX;
    r->sp.prev = NULL;
    if (r->id == v1) {
      cur = r;
    } else {
      r->sp.setptr = not_visited;
      not_visited = r;
    }
  }
  if (cur == NULL) return;
  cur->sp.dist = 0;

  while (not_visited != NULL) {
    update_neighbors(cur);
    cur = extract_min (&not_visited);
  }
  // all the prev and distance pointers are now valid.
}

path_t *nw_get_route(node_id_t v1, node_id_t v2) {
  router_t *r, *from, *to;
  path_t *ret = NULL, *new;

  from = hashtable_search(routers, &v1);
  to   = hashtable_search(routers, &v2);

  if (from == NULL || to == NULL) return NULL;

  if (to->sp.prev == NULL || from->sp.prev != NULL || routes_out_of_date) {
    // the current set of shortest paths do not end at node v2, if we
    // haven't computed any paths yet, we will do that when the next
    // test fails.
    debug("nw_get_route: computing new routes\n");
    compute_routes(v1);
  }
  if (to->sp.prev == NULL) return NULL;

  // now the routes should be valid;
  for (r = to; r != NULL; r = r->sp.prev) {
    // this both constructs the return value and reverses the path,
    // since the prev pointers will give you the reverse path.

    // in the future routes will probably be cached.
    
    if (r != from) {
      new = (path_t *)malloc(sizeof(path_t));
      new->node = r->id;
      new->next = ret;
      new->length = (ret == NULL) ? 1 : ret->length + 1;
      new->isController = r->isController;
      ret = new;
    }
  }
  return ret;
}

void nw_free_path(path_t *r) {
  path_t *next;
  while (r != NULL) {
    next = r->next;
    free(r);
    r = next;
  }
}

// remove link from the linked list of links owned by router.
void remove_link(router_t *r, link_t *link) {
  link_t *l;
  link_t **prev = &r->links;
  for (l = r->links; l != NULL; l = (r== l->n1) ? l->next1 : l->next2) {
    if (l == link) {
      *prev = (r == l->n1) ? l->next1 : l->next2;
      return;
    }
    prev = (r == l->n1) ? &l->next1 : &l->next2;
  }
  warn("link_remove: link not removed (inconsistent state)?\n");
}

void nw_remove_link(node_id_t n1, node_id_t n2) {
  router_t *r1 = nw_get_router(n1);
  router_t *r2 = nw_get_router(n2);
  link_t *link;
  link_key_t key;

  key.r1 = n1;
  key.r2 = n2;
  link = hashtable_search(links, &key);
  if (link != NULL) {
    routes_out_of_date = 1;

    remove_link(r1, link);
    remove_link(r2, link);
    hashtable_remove(links, &key);
    free(link);
  }
}

void nw_inval_node(node_id_t v) {
  router_t *cur;
  link_t *l, *next;
  router_t *otherguy;
  link_key_t key;
  routes_out_of_date = 1;

  cur = hashtable_search(routers, &v);
  if (cur == NULL) return;

  // remove the links from the linked lists of the other guys,
  // and delete them from the hashtable
  for (l = cur->links; l != NULL; l = (cur == l->n1) ? l->next1 : l->next2) {
    otherguy = (cur == l->n1) ? l->n2 : l->n1;
    key.r1 = v;
    key.r2 = otherguy->id;
    remove_link(otherguy, l);
    hashtable_remove(links, &key);
  }
  
  // free the link structures
  l = cur->links;
  while (l != NULL) {
    next = (cur == l->n1) ? l->next1 : l->next2;
    free(l);
    l = next;
  }
  cur->links = NULL;

  // force a route recomputation when this node is used.
  cur->sp.dist = FLT_MAX;
  cur->sp.prev = NULL;
}

/*
 * called before adding the topology from a node 
 * unsets the marked bit * in the link structures to show that they
 * have not been reported
 */ 
void nw_unmark_links(node_id_t v) {
  router_t *cur;
  link_t *l;
  routes_out_of_date = 1;

  cur = hashtable_search(routers, &v);
  if (cur == NULL) return;

  for (l = cur->links; l != NULL; l = (cur == l->n1) ? l->next1 : l->next2) {
    if (l->marked == L_REPORTED) l->marked = L_UNREPORTED;
  }

}

void nw_report_node(node_id_t v) {
  router_t *cur;

  cur = hashtable_search(routers, &v);
  if (cur == NULL) return;
  
  cur->reports++;
}

/*
 * called after processing a topology report
 *
 * removes links which were not contained by this topology report, and
 * which were not reported by the router on the other end.
 *
 */
void nw_clear_unmarked(node_id_t v) {
  router_t *cur;
  link_key_t key;
  link_t *l, *next;
  key.r1 = v;

  cur = hashtable_search(routers, &v);
  if (cur == NULL) return;

  for (l = cur->links; l != NULL; l = (cur == l->n1) ? l->next1 : l->next2) {
    if (l->marked == L_UNREPORTED) {
      // it's not marked, so it wasn't contained in the topology report
      if (((cur == l->n1) ? l->n2_reportcount : l->n1_reportcount) == 0) {
        // it has never been reported by the router on the other end, so we
        // remove the link from the topology data
        router_t *otherguy = (cur == l->n1) ? l->n2 : l->n1;
        key.r2 = otherguy->id;
        remove_link(otherguy, l);
        hashtable_remove(links, &key);
        //info("removing unmarked link, 0x%x -> 0x%x\n", cur->id, otherguy->id);
        // remove it from our own linked list
      } else {
        // it has been reported by the other size, so we just set its
        // observation count to zero.
        if (cur == l->n1)  l->n1_reportcount = 0 ;
        else l->n2_reportcount = 0;
        l->marked = L_REPORTED;
        // router_t *otherguy = (cur == l->n1) ? l->n2 : l->n1;
        //debug("unseting obs count on 0x%x -> 0x%x\n", cur->id, otherguy->id);
      }
    }
  }

  // free the links no longer in use
  l = cur->links;
  while (l != NULL) {
    next = (cur == l->n1) ? l->next1 : l->next2;
    // if its still umarked, we mean to remove it from the graph
    if (l->marked == 0) {
      remove_link(cur, l);
      free(l);
    }
    l = next;
  }


  age_routers();
}


void nw_add_controller(node_id_t node) {
  router_t *r, *thisController;

  struct topology_entry te;
  te.etx = 1;
  te.conf = 255;

  thisController = nw_get_router(node);
  if (!thisController) return;

  thisController->isController = TRUE;
  for (r = router_list; r != NULL; r = r->next) {
    if (r->isController && r != thisController) {
      te.hwaddr = htons(r->id);
      nw_add_incr_edge(node, &te);
    }
  }
}