gridroutetable.cc

COPE the first practical network coding scheme which is developped on click

      rt->_max_metric = _max_qual;
      rt->_min_metric = _min_qual;
    }
    else
      rt->_max_metric = rt->_min_metric = 0;

    /* make sure we don't try to use the old metric for a route */
    
    Vector<RTEntry> entries;
    for (RTIter i = rt->_rtes.begin(); i; i++) {
      /* skanky, but there's no reason for this to be quick.  i guess
         the HashMap doesn't let you change its values. */
      RTEntry e = i.value();
      e.metric_valid = false;
      entries.push_back(e);
    }
    
    for (int i = 0; i < entries.size(); i++) 
      rt->_rtes.insert(entries[i].dest_ip, entries[i]);
  }
  return 0;
}

String
GridRouteTable::print_metric_range(Element *e, void *)
{
  GridRouteTable *rt = (GridRouteTable *) e;
  
  return "max=" + String(rt->_max_metric) + " min=" + String(rt->_min_metric) + "\n";
}

int
GridRouteTable::write_metric_range(const String &arg, Element *el, 
				   void *, ErrorHandler *errh)
{
  GridRouteTable *rt = (GridRouteTable *) el;
  int max, min;
  int res = cp_va_space_parse(arg, rt, errh,
			      cpInteger, "metric range max", &max,
			      cpInteger, "metric range min", &min,
			      cpEnd);
  if (res < 0)
    return -1;

  if (max < min) {
    int t = max;
    max = min;
    min = t;
  }

  rt->_max_metric = max;
  rt->_min_metric = min;

  return 0;
}

String
GridRouteTable::print_est_type(Element *e, void *)
{
  GridRouteTable *rt = (GridRouteTable *) e;
  
  return String(rt->_est_type) + "\n";
}

int
GridRouteTable::write_est_type(const String &arg, Element *el, 
			       void *, ErrorHandler *)
{
  GridRouteTable *rt = (GridRouteTable *) el;
  rt->_est_type = atoi(((String) arg).cc());

  return 0;
}


String
GridRouteTable::print_seq_delay(Element *e, void *)
{
  GridRouteTable *rt = (GridRouteTable *) e;
  
  return String(rt->_seq_delay) + "\n";
}

int
GridRouteTable::write_seq_delay(const String &arg, Element *el, 
				void *, ErrorHandler *)
{
  GridRouteTable *rt = (GridRouteTable *) el;
  rt->_seq_delay = atoi(((String) arg).cc());

  return 0;
}


String
GridRouteTable::print_frozen(Element *e, void *)
{
  GridRouteTable *rt = (GridRouteTable *) e;
  
  return (rt->_frozen ? "true\n" : "false\n");
}

int
GridRouteTable::write_frozen(const String &arg, Element *el, 
				void *, ErrorHandler *)
{
  GridRouteTable *rt = (GridRouteTable *) el;
  rt->_frozen = atoi(((String) arg).cc());

  click_chatter("GridRouteTable: setting _frozen to %s", rt->_frozen ? "true" : "false");

  return 0;
}

String
GridRouteTable::print_links(Element *e, void *)
{
  GridRouteTable *rt = (GridRouteTable *) e;
  
  String s = "Metric type: " + metric_type_to_string(rt->_metric_type) + "\n";

  for (RTIter i = rt->_rtes.begin(); i; i++) {
    const RTEntry &r = i.value();
    if (r.num_hops() > 1)
      continue;

    /* get our measurements of the link *from* this neighbor */
#if 0
#if 0
    LinkStat::stat_t *s1 = rt->_link_stat->_stats.findp(r.next_hop_eth);
#else
    struct {
      int qual;
      int sig;
      struct timeval when;
    } *s1 = 0;
#endif

    struct timeval last;
    unsigned int window = 0;
    unsigned int num_rx = 0;
    unsigned int num_expected = 0;
    bool res1 = rt->_link_stat->get_bcast_stats(r.next_hop_eth, last, window, num_rx, num_expected);

    /* get estimates of our link *to* this neighbor */
    int tx_sig = 0;
    int tx_qual = 0;
    bool res2 = rt->_link_tracker->get_stat(r.dest_ip, tx_sig, tx_qual, last);
    double bcast_rate = 0;
    bool res3 = rt->_link_tracker->get_bcast_stat(r.dest_ip, bcast_rate, last);

    char buf[255];
    double tx_rate = num_rx;
    tx_rate -= 0.5;
    tx_rate /= num_expected;
    snprintf(buf, 255, "%s %s metric=%u (%s) rx_sig=%d rx_qual=%d rx_rate=%d tx_sig=%d tx_qual=%d tx_rate=%d\n",
	     r.dest_ip.s().cc(), r.next_hop_eth.s().cc(), r.metric, r.metric_valid ? "valid" : "invalid",
	     s1 ? s1->sig : -1, s1 ? s1->qual : -1, res1 ? ((int) (100 * tx_rate)) : -1,
	     res2 ? tx_sig : -1, res2 ? tx_qual : -1, res3 ? (int) (100 * bcast_rate) : -1);
    s += buf;
#endif
  }
  return s;
}

void
GridRouteTable::add_handlers()
{
  add_default_handlers(false);
  add_read_handler("nbrs_v", print_nbrs_v, 0);
  add_read_handler("nbrs", print_nbrs, 0);
  add_read_handler("rtes_v", print_rtes_v, 0);
  add_read_handler("rtes", print_rtes, 0);
  add_read_handler("ip", print_ip, 0);
  add_read_handler("eth", print_eth, 0);
  add_read_handler("links", print_links, 0);
  add_read_handler("metric_type", print_metric_type, 0);
  add_write_handler("metric_type", write_metric_type, 0);
  add_read_handler("metric_range", print_metric_range, 0);
  add_write_handler("metric_range", write_metric_range, 0);
  add_read_handler("est_type", print_est_type, 0);
  add_write_handler("est_type", write_est_type, 0);
  add_read_handler("seq_delay", print_seq_delay, 0);
  add_write_handler("seq_delay", write_seq_delay, 0);
  add_read_handler("frozen", print_frozen, 0);
  add_write_handler("frozen", write_frozen, 0);
}


void
GridRouteTable::expire_hook(Timer *, void *thunk) 
{
  GridRouteTable *n = (GridRouteTable *) thunk;
  n->expire_routes();
  n->_expire_timer.schedule_after_ms(EXPIRE_TIMER_PERIOD);
}


Vector<GridRouteTable::RTEntry>
GridRouteTable::expire_routes()
{
  /*
   * remove expired routes from the routing table.  return a vector of
   * expired routes which is suitable for inclusion in a broken route
   * advertisement. 
   */

  /* overloading this timer function to occasionally dump full route table to log */
  _dump_tick++;
  if (_dump_tick == 50) {
    _dump_tick = 0;
    if (_log) {
      Vector<RouteEntry> vec;
      get_all_entries(vec);
      _log->log_route_dump(vec, Timestamp::now());
    }
  }
      
  assert(_timeout > 0);
  unsigned int jiff = click_jiffies();

  Vector<RTEntry> retval;

  if (_frozen)
    return retval;


  typedef HashMap<IPAddress, bool> xip_t; // ``expired ip''
  xip_t expired_rtes;
  xip_t expired_next_hops;

  Timestamp ts = Timestamp::now();
  if (_log)
    _log->log_start_expire_handler(ts);

  bool table_changed = false;

  /* 1. loop through RT once, remembering destinations which have been
     in our RT too long (last_updated_jiffies too old) or have
     exceeded their ttl.  Also note those expired 1-hop entries --
     they may be someone's next hop. */
  for (RTIter i = _rtes.begin(); i; i++) {
    if (jiff - i.value().last_updated_jiffies > _timeout_jiffies ||
	decr_ttl(i.value().ttl, jiff_to_msec(jiff - i.value().last_updated_jiffies)) == 0) {
      expired_rtes.insert(i.value().dest_ip, true);

      _extended_logging_errh->message ("expiring %s %d %d", i.value().dest_ip.s().cc(), ts.sec(), ts.usec());  // extended logging
      table_changed = true;

      if (_log)
	_log->log_expired_route(GridLogger::TIMEOUT, i.value().dest_ip);

      if (i.value().num_hops() == 1) {
	/* may be another route's next hop */
	expired_next_hops.insert(i.value().dest_ip, true);
	/* clear link stats */
	_link_tracker->remove_all_stats(i.value().dest_ip);
      }
    }
  }
  
  /* 2. Loop through RT a second time, picking up any multi-hop
     entries whose next hop is expired, and are not yet expired. */
  for (RTIter i = _rtes.begin(); i; i++) {
    // don't re-expire 1-hop routes, they are their own next hop
    if (i.value().num_hops() > 1 &&
	expired_next_hops.findp(i.value().next_hop_ip) &&
	!expired_rtes.findp(i.value().dest_ip)) {
      expired_rtes.insert(i.value().dest_ip, true);

      _extended_logging_errh->message("next to %s expired %d %d", i.value().dest_ip.s().cc(), ts.sec(), ts.usec());  // extended logging
      
      if (_log)
	_log->log_expired_route(GridLogger::NEXT_HOP_EXPIRED, i.value().dest_ip);
    }
  }
  
  /* 3. Then, push all expired entries onto the return vector and
     erase them from the RT.  */
  for (xip_t::iterator i = expired_rtes.begin(); i; i++) {
    RTEntry *r = _rtes.findp(i.key());
    assert(r);
    r->invalidate();
    r->ttl = grid_hello::MAX_TTL_DEFAULT;
    retval.push_back(*r);
  }
  for (xip_t::iterator i = expired_rtes.begin(); i; i++) {
    bool removed = _rtes.remove(i.key());
    assert(removed);
  }

  if (table_changed)
    log_route_table();  // extended logging

  if (_log)
    _log->log_end_expire_handler();

  return retval;
}


void
GridRouteTable::hello_hook(Timer *, void *thunk)
{
  GridRouteTable *n = (GridRouteTable *) thunk;

  /* XXX is this a bug?  we expire some routes, but don't advertise
     them as broken anymore... */
  n->expire_routes();

  Vector<RTEntry> rte_entries;
  for (RTIter i = n->_rtes.begin(); i; i++) {
    /* because we called expire_routes() at the top of this function,
     * we know we are not propagating any route entries with ttl of 0
     * or that have timed out */

    /* if (i.value().metric_valid) */
    // have to advertise routes even if they have invalid metrics, to
    // kick-start the ping-pong link stats exchange
      rte_entries.push_back(i.value());
  }

  // make and send the packet
  n->send_routing_update(rte_entries);

  int r2 = random();
  double r = (double) (r2 >> 1);
  int jitter = (int) (((double) n->_jitter) * r / ((double) 0x7FffFFff));
  if (r2 & 1)
    jitter *= -1;
  n->_hello_timer.schedule_after_ms(n->_period + (int) jitter);
}


void
GridRouteTable::send_routing_update(Vector<RTEntry> &rtes_to_send,
				    bool update_seq, bool check_ttls)
{
  /*
   * build and send routing update packet advertising the contents of
   * the rte_info vector.  iff update_seq, increment the sequence
   * number before sending.  The calling function must fill in each
   * nbr entry.  If check_ttls, decrement and check ttls before
   * building the packet.
   */

  if (_frozen)
    return;

  unsigned int jiff = click_jiffies();

  Vector<RTEntry> rte_info = Vector<RTEntry>();

  /* 
   * if requested by caller, calculate the ttls each route entry
   * should be sent with.  Each entry's ttl must be decremented by a
   * minimum amount.  Only send the routes with valid ttls (> 0).
   */
  for (int i = 0; i < rtes_to_send.size(); i++) {
    RTEntry &r = rtes_to_send[i];
    if (check_ttls) {
      unsigned int age = jiff_to_msec(jiff - r.last_updated_jiffies);
      unsigned int new_ttl = decr_ttl(r.ttl, (age > grid_hello::MIN_TTL_DECREMENT ? age : grid_hello::MIN_TTL_DECREMENT));
      if (new_ttl > 0) {
	r.ttl = new_ttl;
	rte_info.push_back(r);
      }
    } else {
      rte_info.push_back(r);
    }
  }

  int hdr_sz = sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello);
  int max_rtes = (1500 - hdr_sz) / sizeof(grid_nbr_entry);
  int num_rtes = (max_rtes < rte_info.size() ? max_rtes : rte_info.size()); // min
  int psz = hdr_sz + sizeof(grid_nbr_entry) * num_rtes;

  assert(psz <= 1500);
  if (num_rtes < rte_info.size())
    click_chatter("GridRouteTable %s: too many routes, truncating route advertisement",
		  id().cc());

  /* allocate and align the packet */
  WritablePacket *p = Packet::make(psz + 2); // for alignment
  if (p == 0) {
    click_chatter("in %s: cannot make packet!", id().cc());
    assert(0);
  } 
  ASSERT_ALIGNED(p->data());
  p->pull(2);
  memset(p->data(), 0, p->length());

  /* fill in the timestamp */
  p->set_timestamp_anno(Timestamp::now());

  /* fill in ethernet header */
  click_ether *eh = (click_ether *) p->data();
  memset(eh->ether_dhost, 0xff, 6); // broadcast
  eh->ether_type = htons(ETHERTYPE_GRID);
  memcpy(eh->ether_shost, _eth.data(), 6);

  /* fill in the grid header */
  grid_hdr *gh = (grid_hdr *) (eh + 1);
  ASSERT_ALIGNED(gh);
  gh->hdr_len = sizeof(grid_hdr);
  gh->total_len = htons(psz - sizeof(click_ether));
  gh->type = grid_hdr::GRID_LR_HELLO;
  gh->ip = gh->tx_ip = _ip;
  grid_hello *hlo = (grid_hello *) (gh + 1);
  assert(num_rtes <= 255);
  hlo->num_nbrs = (unsigned char) num_rtes;
  hlo->nbr_entry_sz = sizeof(grid_nbr_entry);
  hlo->seq_no = htonl(_seq_no);

  hlo->is_gateway = _gw_info->is_gateway ();

  /* extended logging */
  Timestamp now = Timestamp::now();
  _extended_logging_errh->message("sending %u %ld %ld", _seq_no, now.sec(), now.usec());
  if (_log)
    _log->log_sent_advertisement(_seq_no, now);

  /* 
   * Update the sequence number for periodic updates, but not for
   * triggered updates.  originating sequence numbers are even,
   * starting at 0.  odd numbers are reserved for other nodes to
   * advertise broken routes 
   */
  assert(!(_seq_no & 1));
  if (update_seq) {
    _fake_seq_no++;
    if ((_fake_seq_no % _seq_delay) == 0)
      _seq_no += 2;
  }
  
  _bcast_count++;
  grid_hdr::set_pad_bytes(*gh, htonl(_bcast_count));

  hlo->ttl = htonl(grid_hello::MAX_TTL_DEFAULT);

  grid_nbr_entry *curr = (grid_nbr_entry *) (hlo + 1);

  char str[80];
  for (int i = 0; i < num_rtes; i++, curr++) {

    const RTEntry &f = rte_info[i];
    snprintf(str, sizeof(str), 
	     "%s %s %s %d %c %u %u\n", 
	     f.dest_ip.s().cc(),
	     f.loc.s().cc(),
	     f.next_hop_ip.s().cc(),
	     f.num_hops(),
	     (f.is_gateway ? 'y' : 'n'),
	     f.seq_no(), 
	     f.metric);
    _extended_logging_errh->message(str);

    rte_info[i].fill_in(curr, _link_stat);
  }
  
  _extended_logging_errh->message("\n");

  output(0).push(p);
}


void
GridRouteTable::RTEntry::fill_in(grid_nbr_entry *nb, LinkStat *ls)
{
  check();
  nb->ip = dest_ip;
  nb->next_hop_ip = next_hop_ip;
  nb->num_hops = num_hops();
  nb->loc = loc;
  nb->loc_err = htons(loc_err);
  nb->loc_good = loc_good;
  nb->seq_no = htonl(seq_no());
  nb->metric = htonl(metric);
  nb->metric_valid = metric_valid;
  nb->is_gateway = is_gateway;
  nb->ttl = htonl(ttl);
  
  /* ping-pong link stats back to sender */
#ifndef SMALL_GRID_HEADERS
  nb->link_qual = 0;
  nb->link_sig = 0;
  nb->measurement_time.tv_sec = nb->measurement_time.tv_usec = 0;
  if (ls && num_hops() == 1) {
#if 0
    LinkStat::stat_t *s = ls->_stats.findp(next_hop_eth);
#else
    struct {
      int qual;
      int sig;
      struct timeval when;
    } *s = 0;
#endif
    if (s) {
      nb->link_qual = htonl(s->qual);
      nb->link_sig = htonl(s->sig);
      nb->measurement_time.tv_sec = htonl(s->when.tv_sec);
      nb->measurement_time.tv_usec = htonl(s->when.tv_usec);
    }
    else
      click_chatter("GridRouteTable: error!  unable to get signal strength or quality info for one-hop neighbor %s\n",
		    IPAddress(dest_ip).s().cc());

    nb->num_rx = 0;
    nb->num_expected = 0;
    nb->last_bcast.tv_sec = nb->last_bcast.tv_usec = 0;
    unsigned int window = 0;
    unsigned int num_rx = 0;
    unsigned int num_expected = 0;
    bool res = ls->get_bcast_stats(next_hop_eth, nb->last_bcast, window, num_rx, num_expected);
    if (res) {
      if (num_rx > 255 || num_expected > 255) {
	click_chatter("GridRouteTable: error! overflow on broadcast loss stats for one-hop neighbor %s",
		      IPAddress(dest_ip).s().cc());
	num_rx = num_expected = 255;
      }
      nb->num_rx = num_rx;
      nb->num_expected = num_expected;
      nb->last_bcast = hton(nb->last_bcast);
    }
  }
#else
  ls = 0; // supress compiler warning
#endif
}

ELEMENT_REQUIRES(userlevel)
EXPORT_ELEMENT(GridRouteTable)
ELEMENT_PROVIDES(GridGenericRouteTable)

#include <click/bighashmap.cc>
#include <click/vector.cc>
template class HashMap<IPAddress, GridRouteTable::RTEntry>;
template class HashMap<IPAddress, bool>;
template class Vector<IPAddress>;
template class Vector<GridRouteTable::RTEntry>;
template class Vector<GridGenericRouteTable::RouteEntry>;
CLICK_ENDDECLS