dsdvroutetable.cc

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

  }

  // Note that for metrics other than hopcount the loop (copied from
  // the dsdv ns code) may not actually expire the dest (ip) whose
  // timeout called this hook.  That's because a node may not be its
  // own next hop in that case.  So we explicitly note that ip is
  // expired before the loop.

  Vector<IPAddress> expired_dests;
  expired_dests.push_back(ip);
  
  // Do next-hop expiration checks, but only if this node is actually
  // its own next hop.  With hopcount, it is always the case that if a
  // node n1 is some node n2's next hop, then n1 is its own next hop;
  // therefore the if() will be true.  For other metrics, there can be
  // cases where we should not expire n2 just because n1 expires, if
  // n1 is not its own next hop.
  if (r->num_hops() == 1) {
    dsdv_assert(r->next_hop_ip == r->dest_ip);
    for (RTIter i = _rtes.begin(); i; i++) {
      RTEntry r = i.value();
      if (r.dest_ip == ip)
	continue; // don't expire this dest twice!

      if (r.good() && 
	  r.next_hop_ip == ip) {
	expired_dests.push_back(r.dest_ip);
	if (_log)
	  _log->log_expired_route(GridGenericLogger::NEXT_HOP_EXPIRED, r.dest_ip);
      }
    }
  }

  unsigned int jiff = dsdv_jiffies();

  for (int i = 0; i < expired_dests.size(); i++) {
    RTEntry *r = _rtes.findp(expired_dests[i]);
    dsdv_assert(r);

    // invariant check: 
    // 1. route to expire must be good, and thus should have existing
    // expire timer and hook object.
    Timer **exp_timer = _expire_timers.findp(r->dest_ip);
    dsdv_assert(exp_timer && *exp_timer);
    HookPair **hp = _expire_hooks.findp(r->dest_ip);
    dsdv_assert(hp && *hp);

    // 2. that existing timer should still be scheduled, except for
    // the timer whose expiry called this hook
    dsdv_assert(r->dest_ip != ip ? (*exp_timer)->scheduled() : true);
    
    // cleanup pending timers
    if ((*exp_timer)->scheduled())
      (*exp_timer)->unschedule();
    delete *exp_timer;
    delete *hp;
    _expire_timers.remove(r->dest_ip);
    _expire_hooks.remove(r->dest_ip);

    // mark route as broken
    r->invalidate(jiff);
#if USE_OLD_SEQ
    RTEntry *old_r = _old_rtes.findp(r->dest_ip);
    if (old_r && old_r->good())
      old_r->invalidate(jiff);
#endif
    r->ttl = grid_hello::MAX_TTL_DEFAULT;

    // set up triggered ad
    r->advertise_ok_jiffies = jiff;
    r->need_seq_ad = true;
    r->need_metric_ad = true;
    schedule_triggered_update(r->dest_ip, jiff);
  }

  if (_log)
    _log->log_end_expire_handler();

  check_invariants();
}

void
DSDVRouteTable::schedule_triggered_update(const IPAddress &ip, unsigned int when)
{
  check_invariants();

  // get rid of outstanding triggered request (if any)
  Timer **old = _trigger_timers.findp(ip);
  HookPair **oldhp = _trigger_hooks.findp(ip);
  if (old) {
    dsdv_assert(*old && (*old)->scheduled() && oldhp && *oldhp);
    (*old)->unschedule();
    delete *old;
    delete *oldhp;
  }
  
  // set up new timer
  HookPair *hp = new HookPair(this, ip);
  Timer *t = new Timer(static_trigger_hook, (void *) hp);
  t->initialize(this);
  unsigned int jiff = dsdv_jiffies();
  t->schedule_after_ms(jiff_to_msec(jiff > when ? 0 : when - jiff));
  _trigger_timers.insert(ip, t);
  _trigger_hooks.insert(ip, hp);

  check_invariants();
}

void
DSDVRouteTable::trigger_hook(const IPAddress &ip)
{
  check_invariants(&ip);

  // invariant: the trigger timer must exist for this dest, but must
  // not be running
  Timer **old = _trigger_timers.findp(ip);
  HookPair **oldhp = _trigger_hooks.findp(ip);
  dsdv_assert(old && *old && !(*old)->scheduled() && oldhp && *oldhp);

  unsigned int jiff = dsdv_jiffies();
  unsigned int next_trigger_jiff = _last_triggered_update + msec_to_jiff(_min_triggered_update_period);

#if DBG
  click_chatter("%s: XXX trigger_hoook(%s)\n", id().cc(), ip.s().cc());
#endif

  if (jiff >= next_trigger_jiff) {
    // It's ok to send a triggered update now.  Cleanup expired timer.
    delete *old;
    delete *oldhp;
    _trigger_timers.remove(ip);
    _trigger_hooks.remove(ip);

    send_triggered_update(ip);
#if DBG
    click_chatter("%s: XXX sent triggered update\n", id().cc());
#endif
  }
  else {
#if DBG
    click_chatter("%s: XXX too early to send triggered update (jiff=%d, next_trigger_jiff=%d, _min_triggered_update_period=%d)\n", id().cc(), jiff, next_trigger_jiff, _min_triggered_update_period);
#endif
    // it's too early to send this update, so cancel all oustanding
    // triggered updates that would also be too early
    Vector<IPAddress> remove_list;
    for (TMIter i = _trigger_timers.begin(); i; i++) {
      if (i.key() == ip)
	continue; // don't touch this timer, we'll reschedule it


      Timer *old2 = i.value();
      dsdv_assert(old2 && old2->scheduled());

      HookPair **oldhp = _trigger_hooks.findp(i.key());
      dsdv_assert(oldhp && *oldhp);

      RTEntry *r = _rtes.findp(i.key());
      if (r->advertise_ok_jiffies < next_trigger_jiff) {
	delete old2;
	delete *oldhp;
	remove_list.push_back(i.key());
      }
    }

    for (int i = 0; i < remove_list.size(); i++) {
      _trigger_timers.remove(remove_list[i]);
      _trigger_hooks.remove(remove_list[i]);
    }

    // reschedule this timer to earliest possible time -- when it
    // fires, its update will also include updates that would have
    // fired before then but were cancelled just above.
    (*old)->schedule_after_ms(jiff_to_msec(next_trigger_jiff - jiff));
  }

  check_invariants();
}


void
DSDVRouteTable::init_metric(RTEntry &r)
{
  dsdv_assert(r.num_hops() == 1);

#if SEQ_METRIC
  if (_use_seq_metric) {
    r.metric = metric_t(r.num_hops());
    DEQueue<unsigned> *q = _seq_history.findp(r.dest_ip);
    if (!q || q->size() < MAX_BCAST_HISTORY)
      r.metric = _bad_metric;
    else {
      dsdv_assert(q->size() == MAX_BCAST_HISTORY);
      unsigned num_missing = q->back() - (q->front() + MAX_BCAST_HISTORY - 1);
      if (num_missing > MAX_BCAST_HISTORY - OLD_BCASTS_NEEDED)
	r.metric = _bad_metric;
    }
    return;
  }
#endif

  if (_metric) 
    r.metric = _metric->get_link_metric(r.dest_eth, true);
  else
    r.metric = _bad_metric;
} 

void
DSDVRouteTable::update_wst(RTEntry *old_r, RTEntry &new_r, unsigned int jiff)
{
  if (old_r) {
    old_r->check();
    dsdv_assert(old_r->last_updated_jiffies <= new_r.last_updated_jiffies);
  }

  if (old_r == 0) {
    new_r.wst = _wst0;
    new_r.last_seq_jiffies = jiff;
    new_r.check();
  }
  else if (old_r->seq_no() == new_r.seq_no()) {
    new_r.wst = old_r->wst;
    new_r.last_seq_jiffies = old_r->last_seq_jiffies;
    new_r.check();
  }
  else if (old_r->seq_no() < new_r.seq_no()) {
    dsdv_assert(old_r->last_updated_jiffies >= old_r->last_seq_jiffies); // XXX failed!
    new_r.wst = _alpha * old_r->wst + 
      (100 - _alpha) * jiff_to_msec(old_r->last_updated_jiffies - old_r->last_seq_jiffies);
    new_r.wst /= 100; // since _alpha is 0-100 percent
    new_r.last_seq_jiffies = jiff;
    new_r.check();
  }
  else {
    dsdv_assert(old_r->seq_no() > new_r.seq_no());
    // Do nothing.  We will never accept this route anyway.  Well,
    // almost never.  See the reboot/wraparound handling in
    // the handle_update() function.
  }
  
  // XXX when our current route is broken, and the new route is good,
  // what happens to wst?

  // from dsdv ns code: Note that we don't touch the changed_at time,
  // so that when wst is computed, it doesn't consider the infinte
  // metric the best one at that sequence number.
}

void 
DSDVRouteTable::update_metric(RTEntry &r)
{
  dsdv_assert(r.num_hops() > 1);

  RTEntry *next_hop = _rtes.findp(r.next_hop_ip);
  if (!next_hop) {
    click_chatter("DSDVRouteTable %s: ERROR updating metric for %s; no information for next hop %s; invalidating metric",
		  id().cc(), r.dest_ip.s().cc(), r.next_hop_ip.s().cc());
    r.metric = _bad_metric;
    return;
  }

#if ENABLE_SEEN
  if (_use_seen && next_hop->metric.val() == _metric_seen) {
    r.metric = metric_t(_metric_seen, false);
    return;
  }
#endif

#if SEQ_METRIC
  if (_use_seq_metric) {
    r.metric = metric_t(r.metric.val() + next_hop->metric.val());
    return;
  }
#endif

  if (_metric)
    r.metric = _metric->prepend_metric(r.metric, next_hop->metric);
  else
    r.metric = _bad_metric;
}

bool
DSDVRouteTable::metric_preferable(const RTEntry &r1, const RTEntry &r2)
{
  // true if r1 is preferable to r2
#if DBG2
  click_chatter("%s: XXX metric_preferable valid?  1:%s  2:%s   1 < 2? %s", id().cc(),
		(r1.metric.good() ? "yes" : "no"), (r2.metric.good() ? "yes" : "no"),
		(metric_val_lt(r1.metric.val(), r2.metric.val()) ? "yes" : "no"));
  click_chatter("\tr1.metric=%u, r2.metric=%u", r1.metric.val(), r2.metric.val());
#endif

  // prefer a route with a valid metric
  if (r1.metric.good() && !r2.metric.good())
    return true;
  if (!r1.metric.good() && r2.metric.good())
    return false;
  
  // If neither metric is valid, fall back to hopcount.  Would you
  // prefer a 5-hop route or a 2-hop route, given that you don't have
  // any other information about them?  duh.
  if (!r1.metric.good() && !r2.metric.good())
    return r1.num_hops() < r2.num_hops();
  
  dsdv_assert(r1.metric.good() && r2.metric.good());
  return metric_val_lt(r1.metric, r2.metric);
}

bool
DSDVRouteTable::metric_val_lt(const metric_t &m1, const metric_t &m2)
{
  assert(m1.good() && m2.good());

  // Better metric should be ``less''
#if SEQ_METRIC
  if (_use_seq_metric) 
    return m1.val() < m2.val();
#endif

  if (_metric)
    return _metric->metric_val_lt(m1, m2);
  else
    return false;
}

bool
DSDVRouteTable::metrics_differ(const metric_t &m1, const metric_t &m2)
{
  if (!m1.good() && !m2.good()) return false;
  if (m1.good() && !m2.good())  return true;
  if (!m1.good() && m2.good())  return true;
  
  dsdv_assert(m1.good() && m2.good());
  return metric_val_lt(m1, m2) || metric_val_lt(m2, m1);
}

void
DSDVRouteTable::send_full_update() 
{
  check_invariants();
#if DBG
  click_chatter("%s: XXX sending full update\n", id().cc());
#endif
  unsigned int jiff = dsdv_jiffies();
  Vector<RTEntry> routes;
  
  for (RTIter i = _rtes.begin(); i; i++) {
    const RTEntry &r = i.value();
    if (r.advertise_ok_jiffies <= jiff)
      routes.push_back(r);
#if DBG
    else
      click_chatter("%s: XXX excluding %s\n", id().cc(), r.dest_ip.s().cc());
#endif
  }

  // send out ads and reset ``need advertisement'' flag
  Vector<RTEntry> ad_routes;
  for (int i = 0; i < routes.size() && i < max_rtes_per_ad(); 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 full dump (%d)\n", 
		    id().cc(), i);
#endif
    }

    ad_routes.push_back(routes[i]);

    RTEntry *r = _rtes.findp(routes[i].dest_ip);
    dsdv_assert(r);
    r->need_seq_ad = false;
    r->need_metric_ad = false;
    r->last_adv_metric = r->metric;
  }
  build_and_tx_ad(ad_routes);

  /* 
   * 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 
   */
  _seq_no += 2;
  _last_periodic_update = jiff;
  _last_triggered_update = jiff;
  
  check_invariants();
}

void
DSDVRouteTable::send_triggered_update(const IPAddress &ip) 
{
  check_invariants();

  // Check that there is actually a route to the destination which
  // prompted this trigger.  There ought to be since we never actually
  // take entries out of the route table; we only mark them as
  // expired.
  RTEntry *r = _rtes.findp(ip);
  dsdv_assert(r);

  unsigned int jiff = dsdv_jiffies();

  Vector<RTEntry> triggered_routes;
  for (RTIter i = _rtes.begin(); i; i++) {
    const RTEntry &r = i.value();
    
    if ((r.need_seq_ad || r.need_metric_ad) && 
	r.advertise_ok_jiffies <= jiff)
      triggered_routes.push_back(r);    
  }
#if FULL_DUMP_ON_TRIG_UPDATE
  // ns implementation of dsdv has this ``heuristic'' to decide when
  // to just do a full update.  slightly bogus, i mean, why > 3?
  if (3*triggered_routes.size() > _rtes.size() && triggered_routes.size() > 3) {
    send_full_update();
    return;
  }
#endif
  if (triggered_routes.size() == 0)
    return;