dsdvroutetable.cc

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

  }

  return s;
}

String
DSDVRouteTable::print_ip(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;
  return n->_ip.s();
}

String
DSDVRouteTable::print_eth(Element *e, void *)
{
  DSDVRouteTable *n = (DSDVRouteTable *) e;
  return n->_eth.s();
}

String
DSDVRouteTable::print_seqno(Element *e, void *)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) e;
  return String(rt->_seq_no) + "\n";
}

int
DSDVRouteTable::write_seqno(const String &arg, Element *el, 
			       void *, ErrorHandler *errh)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) el;
  unsigned u;
  if (!cp_unsigned(arg, &u)) 
    return errh->error("sequence number must be unsigned");
  if (u & 1)
    return errh->error("sequence number must be even");
  rt->_seq_no = u;
  return 0;
}

#if ENABLE_PAUSE
String
DSDVRouteTable::print_paused(Element *e, void *)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) e;
  return (rt->_paused ? "true\n" : "false\n");
}

int
DSDVRouteTable::write_paused(const String &arg, Element *el, 
			     void *, ErrorHandler *errh)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) el;
  bool was_paused = rt->_paused;
  if (!cp_bool(arg, &rt->_paused))
    return errh->error("`paused' must be a boolean");
  
  click_chatter("DSDVRouteTable %s: %s", 
		rt->id().cc(), rt->_paused ? "pausing packet routes (_paused = true)" : 
		"unpausing packet routes (_paused = false)");

  if (!was_paused && rt->_paused) {
    // if we are switching from unpaused to paused, take a snapshot of
    // the route table.
    rt->_snapshot_jiffies = dsdv_jiffies();
    rt->_snapshot_rtes.clear();
    for (RTIter i = rt->_rtes.begin(); i; i++)
      rt->_snapshot_rtes.insert(i.key(), i.value());
#if USE_OLD_SEQ
    rt->_snapshot_old_rtes.clear();
    for (RTIter i = rt->_old_rtes.begin(); i; i++)
      rt->_snapshot_old_rtes.insert(i.key(), i.value());
#endif
  }
  return 0;
}
#endif

String
DSDVRouteTable::print_use_old_route(Element *e, void *)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) e;

#define pb(x) ((x) ? "true" : "false")

  StringAccum sa;
#if USE_OLD_SEQ
  sa << "use old routes: " << pb(rt->_use_old_route)
     << (rt->_use_old_route ? " (don't use until advertised)" : " (use new sequence numbers immediately)") << "\n";
#endif
#if USE_GOOD_NEW_ROUTES
  sa << "use good new routes: " << pb(rt->_use_good_new_route) 
     << (rt->_use_good_new_route ? " (use good new routes immediately)" : " (wait to use good new routes)") << "\n";
#endif
#if ENABLE_SEEN
  sa << "use seen: " << pb(rt->_use_seen) 
     << (rt->_use_seen ? " (check for `seen' handshake)" : " (ignore asymmetry)") << "\n";
#endif
  return sa.take_string();
#undef pb
}

int
DSDVRouteTable::write_use_old_route(const String &arg, Element *el, 
			     void *, ErrorHandler *errh)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) el;
  unsigned u;
  if (!cp_unsigned(arg, &u))
    return errh->error("`use_old_route' must be an unsigned integer");

  bool use_good = false;
  bool use_old = false;
  bool use_seen = false;

  if (u & 1)
    use_old = true;
  if (u & 2)
    use_old = use_good = true;
  if (u & 4)
    use_seen = true;
#if USE_OLD_SEQ
  rt->_use_old_route = use_old;
  click_chatter("DSDVRouteTable %s: setting _use_old_route to %s", 
		rt->id().cc(), rt->_use_old_route ? "true" : "false");
#endif
#if USE_GOOD_NEW_ROUTES
  rt->_use_good_new_route = use_good;
  click_chatter("DSDVRouteTable %s: setting _use_good_new_route to %s", 
		rt->id().cc(), rt->_use_good_new_route ? "true" : "false");
#endif
#if ENABLE_SEEN
  rt->_use_seen = use_seen;
  click_chatter("DSDVRouteTable %s: setting _use_seen to %s", 
		rt->id().cc(), rt->_use_seen ? "true" : "false");
#endif
  return 0;
}

String
DSDVRouteTable::print_dump(Element *e, void *)
{
  DSDVRouteTable *rt = (DSDVRouteTable *) e;
  StringAccum sa;
  for (RTIter i = rt->_rtes.begin(); i; i++) {
    sa << i.value().dump() << "\n";
  }

  return sa.take_string();
}

void
DSDVRouteTable::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("seqno", print_seqno, 0);
  add_write_handler("seqno", write_seqno, 0);
#if ENABLE_PAUSE
  add_read_handler("paused", print_paused, 0);
  add_write_handler("paused", write_paused, 0);
#endif
  add_read_handler("use_old_route", print_use_old_route, 0);
  add_write_handler("use_old_route", write_use_old_route, 0);
  add_read_handler("dump", print_dump, 0);
}

void
DSDVRouteTable::hello_hook()
{
  unsigned int msecs_to_next_ad = _period;

  unsigned int jiff = dsdv_jiffies();
  dsdv_assert(jiff >= _last_periodic_update);
  unsigned int msec_since_last = jiff_to_msec(jiff - _last_periodic_update);
  if (msec_since_last < 2 * _period / 3) {
    // a full periodic update was sent ahead of schedule (because
    // there were so many triggered updates to send).  reschedule this
    // period update to one period after the last periodic update
    
    unsigned int jiff_period = msec_to_jiff(_period);
    msecs_to_next_ad = jiff_to_msec(_last_periodic_update + jiff_period - jiff);
  }
  else {
    send_full_update();
    _last_periodic_update = jiff;
    _last_triggered_update = jiff;
  }

  // reschedule periodic update
  long r2 = random();
  long r = (r2 >> 1);
  unsigned int jitter = (unsigned int) (r % (_jitter + 1));
  if (r2 & 1) {
    if (jitter <= msecs_to_next_ad) // hello can only happen in the future
      msecs_to_next_ad -= jitter;
  }
  else 
    msecs_to_next_ad += jitter;

  _hello_timer.schedule_after_ms(msecs_to_next_ad);
}


void
DSDVRouteTable::build_and_tx_ad(Vector<RTEntry> &rtes_to_send)
{
  /*
   * Build and send routing update packet advertising the contents of
   * the rtes_to_send vector.  Requires that the nuber of entries in
   * rtes_to_send is <= the maximum number of routes that fit into a
   * single route advertisement.
   */

  int num_rtes = rtes_to_send.size();
  dsdv_assert(num_rtes <= max_rtes_per_ad());

  unsigned int hdr_sz = sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello);
  unsigned int psz = hdr_sz + sizeof(grid_nbr_entry) * num_rtes;
  dsdv_assert(psz <= _mtu);  

  /* allocate and align the packet */
  WritablePacket *p = Packet::make(psz + 2); // for alignment
  if (p == 0) {
    click_chatter("DSDVRouteTable %s: cannot make packet!", id().cc());
    dsdv_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);
  dsdv_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 ? _gw_info->is_gateway() : false;

  if (_log)
    _log->log_sent_advertisement(_seq_no, p->timestamp_anno());
  
  _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);

  for (int i = 0; i < num_rtes; i++, curr++) 
    rtes_to_send[i].fill_in(curr);

  output(0).push(p);
}


void
DSDVRouteTable::RTEntry::fill_in(grid_nbr_entry *nb) const
{
  check();
  nb->ip = dest_ip;
  nb->next_hop_ip = next_hop_ip;
  nb->num_hops = num_hops();
  nb->loc = dest_loc;
  nb->loc_err = htons(loc_err);
  nb->loc_good = loc_good;
  nb->seq_no = htonl(seq_no());
  nb->metric = htonl(metric.val());
  nb->metric_valid = metric.good();
  nb->is_gateway = is_gateway;

  unsigned int jiff = dsdv_jiffies();
  unsigned int ttl_decrement = jiff_to_msec(good() ? jiff - last_updated_jiffies : jiff - last_expired_jiffies);
  nb->ttl = htonl(decr_ttl(ttl, max(ttl_decrement, grid_hello::MIN_TTL_DECREMENT)));
  
  /* 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;
#endif
}

void
DSDVRouteTable::log_dump_hook(bool reschedule)
{
  if (_log) {
    Vector<RouteEntry> vec;
    get_all_entries(vec);
    _log->log_route_dump(vec, Timestamp::now());
  }
  if (reschedule)
    _log_dump_timer.schedule_after_ms(_log_dump_period); 
}

String
DSDVRouteTable::RTEntry::dump() const
{
  check();

  unsigned int jiff = dsdv_jiffies();
  
  StringAccum sa;
  sa << "  curr jiffies: "  << jiff << "\n"
     << "       dest_ip: " << dest_ip.s().cc() << "\n"
     << "      dest_eth: " << dest_eth.s().cc() << "\n"
     << "   next_hop_ip: " << next_hop_ip.s().cc() << "\n"
     << "  next_hop_eth: " << next_hop_eth.s().cc() << "\n"
     << "next_hop_iface: " << next_hop_interface << "\n"
     << "        seq_no: " << seq_no() << "\n"
     << "      num_hops: " << (unsigned int) num_hops() << "\n"
     << "  last_updated: " << jiff_diff_string(last_updated_jiffies, jiff).cc() << "\n"
     << "  last_expired: " << jiff_diff_string(last_expired_jiffies, jiff).cc() << "\n"
     << "      last_seq: " << jiff_diff_string(last_seq_jiffies, jiff).cc() << "\n"
     << "  advertise_ok: " << jiff_diff_string(advertise_ok_jiffies, jiff).cc() << "\n"
     << "        metric: " << metric.val() << "\n"
     << "need_metric_ad: " << need_metric_ad << "\n"
     << "   need_seq_ad: " << need_seq_ad << "\n"
     << "           wst: " << (unsigned int) wst << "\n";
  return sa.take_string();
}

void
DSDVRouteTable::check_invariants(const IPAddress *ignore) const
{
  for (RTIter i = _rtes.begin(); i; i++) {
    const RTEntry &r = i.value();

    r.check();
    
    dsdv_assert(!_ignore_invalid_routes || r.metric.good());

    if (ignore && *ignore == i.key())
      continue;

    // check expire timer invariants
    Timer **t = _expire_timers.findp(r.dest_ip);
    HookPair **hp = _expire_hooks.findp(r.dest_ip);

    if (r.good()) {
      dsdv_assert(t);
      dsdv_assert(*t);
      dsdv_assert((*t)->scheduled());
      dsdv_assert(hp);
      dsdv_assert(*hp);
      dsdv_assert((*hp)->obj == this);
      dsdv_assert((*hp)->ip == (unsigned int) r.dest_ip);
    }
    else {
      dsdv_assert(!t);
      dsdv_assert(!hp);
    }      

    // check trigger timer invariants
    t = _trigger_timers.findp(r.dest_ip);
    hp = _trigger_hooks.findp(r.dest_ip);
    if (t) {
      dsdv_assert(*t);
      dsdv_assert((*t)->scheduled());
      dsdv_assert(hp);
      dsdv_assert(*hp);
      dsdv_assert((*hp)->obj == this);
      dsdv_assert((*hp)->ip == (unsigned int) r.dest_ip);
      // dsdv_assert(r.need_seq_ad || r.need_metric_ad); // see note for trigger invariants
    }
    else {
      dsdv_assert(!hp);
    }
  }
}

void
DSDVRouteTable::dsdv_assert_(const char *file, int line, const char *expr) const
{
  click_chatter("DSDVRouteTable %s assertion \"%s\" failed: file %s, line %d",
		id().cc(), expr, file, line);
  click_chatter("Routing table state:");
  for (RTIter i = _rtes.begin(); i; i++) {
    click_chatter("%s\n", i.value().dump().cc());
  }
#ifdef CLICK_USERLEVEL  
  abort();
#else
  click_chatter("Continuing execution anyway, hold on to your hats!\n");
#endif
}

ELEMENT_PROVIDES(GridGenericRouteTable)
EXPORT_ELEMENT(DSDVRouteTable)

#include <click/bighashmap.cc>
#include <click/vector.cc>
template class HashMap<IPAddress, DSDVRouteTable::RTEntry>;
template class HashMap<IPAddress, Timer *>;
template class Vector<DSDVRouteTable::RTEntry>;

#include <click/dequeue.cc>
template class DEQueue<unsigned>;

CLICK_ENDDECLS