dsdvroutetable.cc

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

/*
 * dsdvroutetable.{cc,hh} -- DSDV routing element
 * Douglas S. J. De Couto
 *
 * Copyright (c) 2002 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */

#include <click/config.h>
#include <stddef.h>
#include <click/confparse.hh>
#include <click/error.hh>
#include <clicknet/ether.h>
#include <clicknet/ip.h>
#include <click/standard/scheduleinfo.hh>
#include <click/router.hh>
#include <click/element.hh>
#include <click/glue.hh>
#include <click/straccum.hh>
#include <click/packet_anno.hh>
#include <elements/grid/dsdvroutetable.hh>
#include <elements/grid/linkstat.hh>
#include <elements/grid/gridgatewayinfo.hh>
#include <elements/grid/timeutils.hh>
#include <elements/wifi/txfeedbackstats.hh>


CLICK_DECLS

#define DBG  0
#define DBG2 0
#define DBG3 0

#define FULL_DUMP_ON_TRIG_UPDATE 0

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define dsdv_assert(e) ((e) ? (void) 0 : dsdv_assert_(__FILE__, __LINE__, #e))

bool
DSDVRouteTable::get_one_entry(const IPAddress &dest_ip, RouteEntry &entry)
{
  RTEntry r;
  bool res = lookup_route(dest_ip, r);
  if (res)
    entry = r;
  return res;
}

bool
DSDVRouteTable::lookup_route(const IPAddress &dest_ip, RTEntry &entry) 
{
#if ENABLE_PAUSE
  if (_paused) {
    RTEntry *r =_snapshot_rtes.findp(dest_ip);
    if (r == 0)
      return false;
#if USE_OLD_SEQ
    if (use_old_route(dest_ip, _snapshot_jiffies))
      r = _snapshot_old_rtes.findp(dest_ip);
#endif
    entry = *r;
    return true;
  }
#endif

  RTEntry *r = _rtes.findp(dest_ip);
  if (r == 0)
    return false;
#if USE_OLD_SEQ
  if (use_old_route(dest_ip, dsdv_jiffies()))
    r = _old_rtes.findp(dest_ip);
#endif
  entry = *r;
  return true;  
}

void
DSDVRouteTable::get_all_entries(Vector<RouteEntry> &vec)
{
#if ENABLE_PAUSE
  if (_paused) {
    for (RTIter iter = _snapshot_rtes.begin(); iter; iter++) {
      const RTEntry &rte = iter.value();
#if USE_OLD_SEQ
      if (use_old_route(rte.dest_ip, _snapshot_jiffies))
	vec.push_back(_snapshot_old_rtes[rte.dest_ip]);
      else
	vec.push_back(rte);
#else
      vec.push_back(rte);
#endif
    return;
    }
  }
#endif

#if USE_OLD_SEQ
  unsigned jiff = dsdv_jiffies();
#endif
  for (RTIter iter = _rtes.begin(); iter; iter++) {
    const RTEntry &rte = iter.value();
#if USE_OLD_SEQ
    if (use_old_route(rte.dest_ip, jiff))
      vec.push_back(_old_rtes[rte.dest_ip]);
    else
      vec.push_back(rte);
#else
    vec.push_back(rte);
#endif
  }
}

unsigned
DSDVRouteTable::get_number_direct_neigbors()
{
  Vector<RouteEntry> v;
  
  // delegate to avoid repeating all the pause/old seq logic
  get_all_entries(v);

  // assume all direct neighbors are one-hop neighbors, and count
  // those instead
  int num_nbrs = 0;
  for (int i = 0; i < v.size(); i++)
    if (v[i].num_hops() == 1 && v[i].good())
      num_nbrs++;
  return num_nbrs;
}


#if USE_OLD_SEQ
bool
DSDVRouteTable::use_old_route(const IPAddress &dst, unsigned jiff)
{
  if (!_use_old_route)
    return false;

  RTEntry *real = _rtes.findp(dst);
  RTEntry *old = _old_rtes.findp(dst);
#if ENABLE_PAUSE
  if (_paused) {
    real = _snapshot_rtes.findp(dst);
    old = _snapshot_old_rtes.findp(dst);
  }
#endif
#if USE_GOOD_NEW_ROUTES
  // never use an old route if the new one is better
  if (_use_good_new_route && real && old && metric_preferable(*real, *old))
    return false;
#endif
  return
    (real && real->good() &&             // if real route is bad, don't use good but old route
     old && old->good() &&               // if old route is bad, don't use it
     real->advertise_ok_jiffies > jiff); // if ok to advertise real route, don't use old route
}
#endif

DSDVRouteTable::DSDVRouteTable() : 
  GridGenericRouteTable(1, 1),
#if SEQ_METRIC
  _use_seq_metric(false),
#endif
  _gw_info(0), _metric(0), _log(0),
  _seq_no(0), _mtu(2000), _bcast_count(0),
  _max_hops(3), _alpha(88), _wst0(6000),
  _last_periodic_update(0),
  _last_triggered_update(0), 
  _ignore_invalid_routes(false),
  _hello_timer(static_hello_hook, this),
  _log_dump_timer(static_log_dump_hook, this),
  _verbose(true)
{
}

DSDVRouteTable::~DSDVRouteTable()
{

  for (TMIter i = _expire_timers.begin(); i; i++) {
    if (i.value()->scheduled())
      i.value()->unschedule();
    delete i.value();
  }
  for (TMIter i = _trigger_timers.begin(); i; i++) {
    if (i.value()->scheduled())
      i.value()->unschedule();
    delete i.value();
  }
  for (HMIter i = _expire_hooks.begin(); i; i++) 
    delete i.value();
  for (HMIter i = _trigger_hooks.begin(); i; i++) 
    delete i.value();
}

void *
DSDVRouteTable::cast(const char *n)
{
  if (strcmp(n, "DSDVRouteTable") == 0)
    return (DSDVRouteTable *) this;
  else if (strcmp(n, "GridGenericRouteTable") == 0)
    return (GridGenericRouteTable *) this;
  else
    return 0;
}

int
DSDVRouteTable::configure(Vector<String> &conf, ErrorHandler *errh)
{
  String logfile;
  int res = cp_va_parse(conf, this, errh,
			cpUnsigned, "entry timeout (msec)", &_timeout,
			cpUnsigned, "route broadcast period (msec)", &_period,
			cpUnsigned, "route broadcast jitter (msec)", &_jitter,
			cpUnsigned, "minimum triggered update period (msec)", &_min_triggered_update_period,
			cpEthernetAddress, "source Ethernet address", &_eth,
			cpIPAddress, "source IP address", &_ip,
			cpKeywords,
			"VERBOSE", cpBool, "verbose warnings and messages?", &_verbose,
			"GW", cpElement, "GridGatewayInfo element", &_gw_info,
			"MAX_HOPS", cpUnsigned, "max hops", &_max_hops,
			"METRIC", cpElement, "GridGenericMetric element", &_metric,
			"LOG", cpElement, "GridGenericLogger element", &_log,
			"WST0", cpUnsigned, "initial weight settling time, wst0 (msec)", &_wst0,
			"ALPHA", cpUnsigned, "alpha parameter for settling time computation, in percent (0 <= ALPHA <= 100)", &_alpha,
			"SEQ0", cpUnsigned, "initial sequence number (must be even)", &_seq_no,
			"MTU", cpUnsigned, "interface MTU", &_mtu,
			"IGNORE_INVALID_ROUTES", cpBool, "ignore routes with invalid metrics?", &_ignore_invalid_routes,
#if SEQ_METRIC
			"USE_SEQ_METRIC", cpBool, "use `dsdv_seqs' metric?", &_use_seq_metric,
#endif
			cpEnd);

  if (res < 0)
    return res;

  if (_seq_no & 1) 
    return errh->error("initial sequence number must be even");

  if (_timeout == 0)
    return errh->error("timeout interval must be greater than 0");
  if (_period == 0)
    return errh->error("period must be greater than 0");
  // _jitter is allowed to be 0
  if (_jitter > _period)
    return errh->error("jitter is bigger than period");
  if (_max_hops == 0)
    return errh->error("max hops must be greater than 0");
  if (_alpha > 100) 
    return errh->error("alpha must be between 0 and 100 inclusive");

  if (_mtu < sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello)) 
    return errh->error("mtu is too small to send a route ads");

  if (_log && _log->cast("GridGenericLogger") == 0) 
    return errh->error("LOG element is not a GridGenericLogger");
  if (_gw_info && _gw_info->cast("GridGatewayInfo") == 0)
    return errh->error("GW element is not a GridGatewayInfo");
  if (_metric && _metric->cast("GridGenericMetric") == 0)
    return errh->error("METRIC element is not a GridGenericMetric");

  if (_gw_info == 0 && _verbose)
    errh->warning("No GridGatewayInfo element specified, will default to not advertising as gateway");
  if (_metric == 0 && _verbose)
    errh->warning("No metric elements specified, will default to minimum hop-count");

#if SEQ_METRIC
  if (_metric && _use_seq_metric)
    errh->warning("USE_SEQ_METRIC has been specified, the specified METRIC element will be ignored");
#endif

  return res;
}

int
DSDVRouteTable::initialize(ErrorHandler *)
{
  _hello_timer.initialize(this);
  _hello_timer.schedule_after_ms(_period);
  _log_dump_timer.initialize(this);
  _log_dump_timer.schedule_after_ms(_log_dump_period); 

  check_invariants();
#if ENABLE_PAUSE
  _paused = false;
#endif
#if USE_OLD_SEQ
  _use_old_route = false;
#if USE_GOOD_NEW_ROUTES
  _use_good_new_route = false;
#endif
#endif
#if ENABLE_SEEN
  _use_seen = false;
#endif
  return 0;
}

bool
DSDVRouteTable::current_gateway(RouteEntry &gw)
{
  RTEntry best;
  bool found_gateway = false;
  Vector<IPAddress> gw_addrs;
  RTIter i = _rtes.begin();
#if ENABLE_PAUSE
  if (_paused)
    i = _snapshot_rtes.begin();
#endif  
  for ( ; i; i++) {
    if (i.value().is_gateway) 
      gw_addrs.push_back(i.value().dest_ip);
  }

  for (Vector<IPAddress>::const_iterator i = gw_addrs.begin(); i != gw_addrs.end(); i++) {
    RTEntry r;
    bool res = lookup_route(*i, r);
    dsdv_assert(res);
    if (r.is_gateway && r.good() && (!found_gateway || metric_preferable(r, best))) {
      best = r;
      found_gateway = true;
    }
  }
  if (found_gateway) {
    gw = best;
  } 
  return found_gateway;
}

void
DSDVRouteTable::insert_route(const RTEntry &r, const GridGenericLogger::reason_t why)
{
  check_invariants();
  r.check();
  
  dsdv_assert(!_ignore_invalid_routes || r.metric.good());
  
  RTEntry *old_r = _rtes.findp(r.dest_ip);
  
  // invariant check: running timers exist for all current good
  // routes.  no timers or bogus timer entries exist for bad routes.
  // hook objects exist for each timer.
  Timer **old = _expire_timers.findp(r.dest_ip);
  HookPair **oldhp = _expire_hooks.findp(r.dest_ip);
  if (old_r && old_r->good())
    dsdv_assert(old && *old && (*old)->scheduled() && oldhp && *oldhp);
  else { 
    dsdv_assert(old == 0);
    dsdv_assert(oldhp == 0);
  }

  // get rid of old expire timer
  if (old) {
    (*old)->unschedule();
    delete *old;
    delete *oldhp;
    _expire_timers.remove(r.dest_ip);
    _expire_hooks.remove(r.dest_ip);
  }
  
  // Note: ns dsdv only schedules a timeout for the sender of each
  // route ad, relying on the next-hop expiry logic to get all routes
  // via that next hop.  However, that won't work for general metrics,
  // so we install a timeout for *every* newly installed good route.
  if (r.good()) {
    HookPair *hp = new HookPair(this, r.dest_ip);
    Timer *t = new Timer(static_expire_hook, (void *) hp);
    t->initialize(this);
    t->schedule_after_ms(min(r.ttl, _timeout));
    
    _expire_timers.insert(r.dest_ip, t);
    _expire_hooks.insert(r.dest_ip, hp);
  }

#if USE_OLD_SEQ
  // if we are getting new seqno, save route for old seqno
  if (old_r && old_r->seq_no() < r.seq_no()) 
    _old_rtes.insert(r.dest_ip, *old_r);
#endif

  _rtes.insert(r.dest_ip, r);

  // note, we don't change any pending triggered update for this
  // updated dest.  ... but shouldn't we postpone it?  -- shouldn't
  // matter if timer fires too early, since the advertise_ok_jiffies
  // should tell us it's too early.

  if (_log)
    _log->log_added_route(why, make_generic_rte(r), (unsigned int) r.wst);
  check_invariants();
}

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

  // invariant check:
  // 1. route to expire should exist
  RTEntry *r = _rtes.findp(ip);
  dsdv_assert(r != 0);
  
  // 2. route to expire should be good
  dsdv_assert(r->good() && (r->seq_no() & 1) == 0);
  
  // 3. the expire timer for this dest should exist, but should not be
  // running.
  Timer **old = _expire_timers.findp(ip);
  HookPair **oldhp = _expire_hooks.findp(ip);
  dsdv_assert(old && *old && !(*old)->scheduled() && oldhp && *oldhp);

  if (_log) {
    _log->log_start_expire_handler(Timestamp::now());
    _log->log_expired_route(GridGenericLogger::TIMEOUT, ip);