dsdvroutetable.cc

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

  // send out ads and reset ``need advertisement'' flag
  Vector<RTEntry> ad_routes;
  for (int i = 0; i < triggered_routes.size(); i++) {
    if (ad_routes.size() == max_rtes_per_ad()) {
      build_and_tx_ad(ad_routes);
      ad_routes.clear();
#if DBG
      click_chatter("%s: too many routes; sending out partial triggered update (%d)\n", 
		    id().cc(), i);
#endif
    }

    ad_routes.push_back(triggered_routes[i]);

    RTEntry *r = _rtes.findp(triggered_routes[i].dest_ip);
    dsdv_assert(r);
    r->need_seq_ad = false; // XXX why not reset need_metric_ad flag as well?
    r->last_adv_metric = r->metric;
  }
  build_and_tx_ad(ad_routes); 

  _last_triggered_update = jiff;

  check_invariants();
}

bool
DSDVRouteTable::handle_update(RTEntry new_r, const bool was_sender, const unsigned int jiff)
{
  check_invariants();
  new_r.check();

  dsdv_assert(was_sender ? new_r.num_hops() == 1 : new_r.num_hops() != 1);

  if (new_r.good() && new_r.num_hops() >_max_hops)
    return false; // ignore ``non-local'' routes

  if (was_sender)
    init_metric(new_r);
  else if (new_r.good())
    update_metric(new_r);

  if (_ignore_invalid_routes && !new_r.metric.good())
    return false; // don't keep routes with invalid metrics


  RTEntry *old_r = _rtes.findp(new_r.dest_ip);
  update_wst(old_r, new_r, jiff);

  // If the new route is good, and the old route (if any) was good,
  // wait for the settling time to pass since we first heard this
  // sequence number before advertising.  Otherwise, propagate the
  // route immediately (e.g. a newly appearing node, or broken route).
  //
  // Note: I think the DSDV code in the ns simulator has this wrong.
  // See line 652 in file cmu/dsdv/dsdv.cc.  That code sets the time
  // it's ok to advertise at to the current time + 2 * wst, which
  // would be as if we were adding jiff instead of
  // new_r.last_seq_jiffies in the code below.
  if (new_r.good() && (!old_r || old_r->good())) // XXX comment implies: new_r.good() && old_r && old_r->good()
    new_r.advertise_ok_jiffies = new_r.last_seq_jiffies + msec_to_jiff((unsigned int) (2 * new_r.wst));
  else
    new_r.advertise_ok_jiffies = jiff;

#if DBG
  click_chatter("%s: XXX dest=%s advertise_ok_jiffies=%u wst=%u jiff=%d\n", 
		id().cc(), new_r.dest_ip.s().cc(),
		new_r.advertise_ok_jiffies, new_r.wst, jiff);
#endif

  if (!old_r) {
    // Never heard of this destination before
    if (new_r.good()) {
      new_r.need_metric_ad = true;
      schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
#if DBG
      click_chatter("%s: XXX scheduled brand-new route to %s to be advertised in %d jiffies from now\n", id().cc(),
		    new_r.dest_ip.s().cc(), new_r.advertise_ok_jiffies - jiff);
#endif
    }
    insert_route(new_r, was_sender ? GridGenericLogger::NEW_DEST_SENDER : GridGenericLogger::NEW_DEST);
  }
  else if (old_r->seq_no() == new_r.seq_no()) {
    // Accept if better route
    dsdv_assert(new_r.good() ? old_r->good() : old_r->broken()); // same seq ==> same broken state
#if DBG2
    click_chatter("%s: XXX checking for better route to %s from %s with same seqno %u",
		  id().cc(), new_r.dest_ip.s().cc(), new_r.next_hop_ip.s().cc(), new_r.seq_no());
    click_chatter("%s: XXX good=%s  preferable=%s", id().cc(), new_r.good() ? "yes" : "no",
		  metric_preferable(new_r, *old_r) ? "yes" : "no");
#endif
    if (new_r.good() && metric_preferable(new_r, *old_r)) {
      if (metrics_differ(new_r.metric, new_r.last_adv_metric)) {
	new_r.need_metric_ad = true;
	schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
      }
      insert_route(new_r, was_sender ? GridGenericLogger::BETTER_RTE_SENDER : GridGenericLogger::BETTER_RTE);
    }
  }
  else if (old_r->seq_no() < new_r.seq_no()) {
    // Must *always* accept newer info
    new_r.need_seq_ad = true; // XXX this may not be best, see bake-off paper
    schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
    if (metrics_differ(new_r.metric, new_r.last_adv_metric))
      new_r.need_metric_ad = true;
    insert_route(new_r, was_sender ? GridGenericLogger::NEWER_SEQ_SENDER : GridGenericLogger::NEWER_SEQ);
  }
  else {
    dsdv_assert(old_r->seq_no() > new_r.seq_no());
    if (new_r.broken() && old_r->good()) {
      // Someone has stale info, give them good info
      old_r->advertise_ok_jiffies = jiff;
      old_r->need_metric_ad = true;
      schedule_triggered_update(old_r->dest_ip, jiff);
      check_invariants();
      return false;
    }
    else if (new_r.good() && old_r->broken()) {
      // Perhaps a node rebooted?  This case is not handled by ns
      // simulator DSDV code.
      dsdv_assert(jiff >= old_r->last_expired_jiffies);
      unsigned age = jiff_to_msec(jiff - old_r->last_expired_jiffies);
      if (age > 2 * grid_hello::MAX_TTL_DEFAULT || was_sender) {
	// Assume we got a new entry, not a stale entry that has been
	// floating around the network.  Treat as newer sequence number,
	// but slightly differently: reboot implies everything could
	// be different.
	new_r.need_seq_ad = true;
	new_r.need_metric_ad = true;
	new_r.last_seq_jiffies = jiff; // not done by update_wst() becaue seq is less, so do it here
	dsdv_assert(new_r.last_updated_jiffies == new_r.last_seq_jiffies);
	schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
	insert_route(new_r, was_sender ? GridGenericLogger::REBOOT_SEQ_SENDER : GridGenericLogger::REBOOT_SEQ);
      }
    }
  }
  check_invariants();
  return true;
}

Packet *
DSDVRouteTable::simple_action(Packet *packet)
{
  check_invariants();

  dsdv_assert(packet);
  unsigned int jiff = dsdv_jiffies();

  /* 
   * sanity check the packet, get pointers to headers.  These should
   * be redundant due to classifiers etc. in the Grid Click
   * configuration, but don't dis paranoia.
   */
  click_ether *eh = (click_ether *) packet->data();
  if (ntohs(eh->ether_type) != ETHERTYPE_GRID) {
    click_chatter("DSDVRouteTable %s: got non-Grid packet type", id().cc());
    packet->kill();
    return 0;
  }
  grid_hdr *gh = (grid_hdr *) (eh + 1);

  if (gh->type != grid_hdr::GRID_LR_HELLO) {
    click_chatter("DSDVRouteTable %s: received unknown Grid packet; ignoring it", id().cc());
    packet->kill();
    return 0;
  }
    
  IPAddress ipaddr((unsigned char *) &gh->tx_ip);
  EtherAddress ethaddr((unsigned char *) eh->ether_shost);

  if (ethaddr == _eth) {
    click_chatter("DSDVRouteTable %s: received own Grid packet; ignoring it", id().cc());
    packet->kill();
    return 0;
  }

  grid_hello *hlo = (grid_hello *) (gh + 1);
   
  if (_log)
    _log->log_start_recv_advertisement(ntohl(hlo->seq_no), ipaddr, Timestamp::now());
  
  // assume CheckGridHeader was used to check for truncated packets
  // and bad checksums.  Sanity check number of entries.
  int entry_sz = hlo->nbr_entry_sz;
  char *entry_ptr = (char *) (hlo + 1);
  unsigned max_entries = (ntohs(gh->total_len) - sizeof(*gh) - sizeof(*hlo)) / entry_sz;
  unsigned num_entries = hlo->num_nbrs;
  if (num_entries > max_entries) {
    click_chatter("DSDVRouteTable %s: route ad from %s contains fewer routes than claimed; want %u, have no more than %u",
		  id().cc(), ipaddr.s().cc(), num_entries, max_entries);
    num_entries = max_entries;
  }

  // maybe add new route for message transmitter, sanity check existing entry
  RTEntry *r = _rtes.findp(ipaddr);
  if (!r)
    click_chatter("DSDVRouteTable %s: new 1-hop nbr %s -- %s", 
		  id().cc(), ipaddr.s().cc(), ethaddr.s().cc()); 
  else if (r->dest_eth && r->dest_eth != ethaddr)
    click_chatter("DSDVRouteTable %s: ethernet address of %s changed from %s to %s", 
		  id().cc(), ipaddr.s().cc(), r->dest_eth.s().cc(), ethaddr.s().cc());

#if SEQ_METRIC
  // track last few broadcast numbers we heard directly from this node
  DEQueue<unsigned> *q = _seq_history.findp(ipaddr);
  if (!q) {
    _seq_history.insert(ipaddr, DEQueue<unsigned>());
    q = _seq_history.findp(ipaddr);
  }
  unsigned bcast_num = ntohl(grid_hdr::get_pad_bytes(*gh));
  q->push_back(bcast_num);
  while (q->size() > MAX_BCAST_HISTORY)
    q->pop_front();
#endif

  RTEntry new_r(ipaddr, ethaddr, gh, hlo, PAINT_ANNO(packet), jiff);
  bool inserted_new_r;

#if ENABLE_SEEN
  bool sender_saw_us = false;
  const char *c = entry_ptr;
  for (unsigned i = 0; i < num_entries; i++, c += entry_sz) {
    const grid_nbr_entry *e = (const grid_nbr_entry *) c;
    if (e->ip == _ip.addr() && e->num_hops == 1) {
      sender_saw_us = true;
      break;
    }
  }
  new_r.last_seen_jiffies = sender_saw_us ? jiff : 0;

  RTEntry *old = _rtes.findp(new_r.dest_ip);
  // If the sending node didn't see us, and has never seen us, or
  // hasn't seen us in a while, mark the sender as `seen' instead of
  // giving it a proper metric.
#if 0
  if (old)
    click_chatter("XXX %s %s snd_saw %s  old metric %u  old last seen %u\n",
		  id().cc(), ipaddr.s().cc(), sender_saw_us ? "y" : "n", old->metric.val, old->last_seen_jiffies);
  else 
    click_chatter("XXX %s %s snd_saw %s\n",
		id().cc(), ipaddr.s().cc(), sender_saw_us ? "y" : "n");
#endif
  if (_use_seen && !sender_saw_us &&
      (!old || old->metric.val() == _metric_seen || (jiff - old->last_seen_jiffies) > 3*msec_to_jiff(_period))) {
    new_r.metric = metric_t(_metric_seen, false);
    new_r.advertise_ok_jiffies = jiff;
    new_r.need_metric_ad = true;
    schedule_triggered_update(new_r.dest_ip, jiff);
    insert_route(new_r, GridGenericLogger::NEW_DEST_SENDER);
    inserted_new_r = true;
    goto after_sender_update;
  }
#endif // ENABLE_SEEN

  // insert 1-hop route
  inserted_new_r = handle_update(new_r, true, jiff);

#if ENABLE_SEEN
  after_sender_update:
#endif

  // update this dest's eth, if we inserted it into the route table
  if (inserted_new_r) {
    r = _rtes.findp(ipaddr);
    dsdv_assert(r);
    r->dest_eth = ethaddr;
  }

  // handle each entry in message
  bool need_full_update = false;
  for (unsigned i = 0; i < num_entries; i++, entry_ptr += entry_sz) {

    grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
    RTEntry route(ipaddr, ethaddr, curr, PAINT_ANNO(packet), jiff); 

    if (route.ttl == 0) // ignore expired ttl
      continue;
    if (route.dest_ip == _ip) { // ignore route to self
      if (route.broken()) // override broken route to us with new ad
	need_full_update = true;
      continue;
    }
    if (curr->next_hop_ip == (unsigned int) _ip)
      continue; // pseudo split-horizon

    handle_update(route, false, jiff);
  }

  if (_log)
    _log->log_end_recv_advertisement();

  if (need_full_update)
    send_full_update();

  packet->kill();
  check_invariants();
  return 0;
}

String
DSDVRouteTable::jiff_diff_string(unsigned int j1, unsigned int j2) {
  bool neg;
  unsigned int d = jiff_diff_as_msec(j1, j2, neg);
  String ret(d);
  if (neg)
    ret = "-" + ret;
  return ret;
}

unsigned int
DSDVRouteTable::jiff_diff_as_msec(unsigned int j1, unsigned int j2, bool &neg)
{
  neg = j2 > j1;
  return jiff_to_msec(neg ? j2 - j1 : j1 - j2);
}

String 
DSDVRouteTable::print_rtes_v(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;

  unsigned int jiff = dsdv_jiffies();

  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
#if USE_OLD_SEQ
    RTEntry f = i.value();
    if (n->use_old_route(f.dest_ip, jiff))
      f = n->_old_rtes[f.dest_ip];
#else
    const RTEntry &f = i.value();
#endif
    s += f.dest_ip.s() 
      + " next=" + f.next_hop_ip.s() 
      + " hops=" + String((int) f.num_hops()) 
      + " gw=" + (f.is_gateway ? "y" : "n")
      + " loc=" + f.dest_loc.s()
      + " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
      + " seq=" + String(f.seq_no())
      + " metric_valid=" + (f.metric.good() ? "yes" : "no")
      + " metric=" + String(f.metric.val())
      + " ttl=" + String(f.ttl)
      + " wst=" + String((unsigned long) f.wst)
      + " need_seq_ad=" + (f.need_seq_ad ? "yes" : "no")
      + " need_metric_ad=" + (f.need_metric_ad ? "yes" : "no")
      + " last_expired=" + jiff_diff_string(f.last_expired_jiffies, jiff)
      + " last_updated=" + jiff_diff_string(f.last_updated_jiffies, jiff)
      + " last_seq=" + jiff_diff_string(f.last_seq_jiffies, jiff)
      + " advertise_ok=" + jiff_diff_string(f.advertise_ok_jiffies, jiff);
#if ENABLE_SEEN
    s += " last_seen=" + jiff_diff_string(f.last_seen_jiffies, jiff);
#endif
    
    s += "\n";
  }
  
  return s;
}

String 
DSDVRouteTable::print_rtes(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;

  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
#if USE_OLD_SEQ
    unsigned jiff = dsdv_jiffies();
    RTEntry f = i.value();
    if (n->use_old_route(f.dest_ip, jiff))
      f = n->_old_rtes[f.dest_ip];
#else
    const RTEntry &f = i.value();
#endif
    s += f.dest_ip.s() 
      + " next=" + f.next_hop_ip.s() 
      + " hops=" + String((int) f.num_hops()) 
      + " gw=" + (f.is_gateway ? "y" : "n")
      + " metric=" + String(f.metric.val())
      + " seq=" + String(f.seq_no())
      + "\n";
  }
  
  return s;
}

String
DSDVRouteTable::print_nbrs_v(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;
  
  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
    // only print immediate neighbors 
    if (!i.value().dest_eth) 
      continue;
    s += i.key().s();
    s += " eth=" + i.value().dest_eth.s();
    char buf[300];
    snprintf(buf, 300, " metric_valid=%s metric=%d if=%d",
	     i.value().metric.good() ? "yes" : "no", 
	     i.value().metric.val(), (int) i.value().next_hop_interface);
    s += buf;
    s += "\n";
  }

  return s;
}

String
DSDVRouteTable::print_nbrs(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;
  
  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
    // only print immediate neighbors 
    if (!i.value().dest_eth)
      continue;
    s += i.key().s();
    s += " eth=" + i.value().dest_eth.s();
    s += " if=" + String((int) i.value().next_hop_interface);
    s += "\n";