gridroutetable.cc

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

/*
 * gridroutetable.{cc,hh} -- Grid local neighbor and route tables element
 * Douglas S. J. De Couto
 *
 * Copyright (c) 2000 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 "timeutils.hh" /* includes <cmath> which may #undef NULL, so
			   must become before <cstddef> */
#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 "gridroutetable.hh"
#include "gridlogger.hh"
CLICK_DECLS

#define NEXT_HOP_ETH_FIXUP 0

bool
GridRouteTable::get_one_entry(const IPAddress &dest_ip, RouteEntry &entry) 
{
  RTEntry *r = _rtes.findp(dest_ip);
  if (r == 0)
    return false;
  
  entry = RouteEntry(dest_ip, r->loc_good, r->loc_err, r->loc,
		     r->next_hop_eth, r->next_hop_ip, 
		     0, // ignore interface number info
		     r->seq_no(), r->num_hops());
  return true;  
}

void
GridRouteTable::get_all_entries(Vector<RouteEntry> &vec)
{
  for (RTIter iter = _rtes.begin(); iter; iter++) {
    const RTEntry &rte = iter.value();
    vec.push_back(RouteEntry(rte.dest_ip, rte.loc_good, rte.loc_err, rte.loc, 
			     rte.next_hop_eth, rte.next_hop_ip, 0, // ignore interface info
			     rte.seq_no(), rte.num_hops()));
  }
}


GridRouteTable::GridRouteTable() : 
  GridGenericRouteTable(1, 1), _log(0), _dump_tick(0),
  _seq_no(0), _fake_seq_no(0), _bcast_count(0),
  _seq_delay(1),
  _max_hops(3), 
  _expire_timer(expire_hook, this),
  _hello_timer(hello_hook, this),
  _metric_type(MetricEstTxCount),
  _max_metric(0), _min_metric(0),
  _est_type(EstBySigQual),
  _frozen(false)
{
}

GridRouteTable::~GridRouteTable()
{
}



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



void
GridRouteTable::log_route_table ()
{
  char str[80];
  for (RTIter i = _rtes.begin(); i; i++) {
    const RTEntry &f = i.value();

    snprintf(str, sizeof(str), 
	     "%s %s %s %d %c %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());
    _extended_logging_errh->message(str);
  }
  _extended_logging_errh->message("\n");
}


int
GridRouteTable::configure(Vector<String> &conf, ErrorHandler *errh)
{
  String chan("routelog");
  String metric("est_tx_count");
  int res = cp_va_parse(conf, this, errh,
			cpInteger, "entry timeout (msec)", &_timeout,
			cpInteger, "route broadcast period (msec)", &_period,
			cpInteger, "route broadcast jitter (msec)", &_jitter,
			cpEthernetAddress, "source Ethernet address", &_eth,
			cpIPAddress, "source IP address", &_ip,
			cpElement, "GridGatewayInfo element", &_gw_info,
			cpElement, "LinkTracker element", &_link_tracker,
			cpElement, "LinkStat element", &_link_stat,
			cpKeywords,
			"MAX_HOPS", cpInteger, "max hops", &_max_hops,
			"LOGCHANNEL", cpString, "log channel name", &chan,
			"METRIC", cpString, "route metric", &metric,
			"LOG", cpElement, "GridLogger element", &_log,
			cpEnd);

  if (res < 0)
    return res;

  // convert msecs to jiffies
  if (_timeout == 0)
    _timeout = -1;
  if (_timeout > 0) {
    _timeout_jiffies = msec_to_jiff(_timeout);
    if (_timeout_jiffies < 1)
      return errh->error("timeout interval is too small");
  }
  else
    click_chatter("%s: not timing out table entries", id().cc());

  if (_period <= 0)
    return errh->error("period must be greater than 0");
  if (_jitter < 0)
    return errh->error("period must be positive");
  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");

  _extended_logging_errh = router()->chatter_channel(chan);
  assert(_extended_logging_errh);

  _metric_type = check_metric_type(metric);
  if (_metric_type < 0)
    return errh->error("Unknown metric type ``%s''", metric.cc());

  return res;
}



int
GridRouteTable::initialize(ErrorHandler *)
{
  _hello_timer.initialize(this);
  _hello_timer.schedule_after_ms(_period); // Send periodically

  _expire_timer.initialize(this);
  if (_timeout > 0)
    _expire_timer.schedule_after_ms(EXPIRE_TIMER_PERIOD);

  return 0;
}


bool
GridRouteTable::current_gateway(RouteEntry &entry)
{
  for (RTIter i = _rtes.begin(); i; i++) {
    const RTEntry &f = i.value();

    if (f.is_gateway) {
      entry = RouteEntry(f.dest_ip, f.loc_good, f.loc_err, f.loc, 
			 f.next_hop_eth, f.next_hop_ip, 0, // ignore interface info
			 f.seq_no(), f.num_hops());
      return true;
      }
  }

  return false;
}


unsigned int
GridRouteTable::qual_to_pct(int q)
{
  /* smaller quality is better, so should be a higher pct when closer to min quality */
  if (q > _max_metric)
    return 0;
  else if (q < _min_metric) 
    return 100;

  int delta = _max_metric - _min_metric;
  return (100 * (_max_metric - q)) / delta;
}

unsigned int
GridRouteTable::sig_to_pct(int s)
{
  /* large signal is better, so should be a higher pct when closer to max sig */
  if (s > _max_metric)
    return 100;
  else if (s < _min_metric) 
    return 0;

  int delta = _max_metric - _min_metric;
  return (100 * (s - _min_metric)) / delta;
}

// #define h(x) click_chatter("XXXX %d", x);
#define h(x)

bool
GridRouteTable::est_forward_delivery_rate(const IPAddress ip, double &rate)
{
  switch (_est_type) {
  case EstBySig:
  case EstByQual: 
  case EstBySigQual: {
    int sig = 0;
    int qual = 0;
    struct timeval last;
    bool res = _link_tracker->get_stat(ip, sig, qual, last);
    if (!res) {
      h(1);
      return false;
    }
    if (_est_type == EstByQual) {
      return false;
    }
    else if (_est_type == EstBySig) {
      return false;
    }
    else if (_est_type == EstBySigQual) {
      h(2);
#if 0
      click_chatter("XXX %s", ip.s().cc());
#endif
      /* 
       * use jinyang's parameters, based on 1sec broadcast loss rates
       * with 50-byte UDP packets.  
       *
       * good = delivery rate > 80%.  
       *
       * these parameters are chosen to correctly classify 85% of good
       * links as good, while only classifying 2% of bad links as
       * good.  
       */
      res = _link_tracker->get_bcast_stat(ip, rate, last);
      double z = 9.4519 + 0.0391 * sig + 0.5518 * qual;
      double z2 = 1 / (1 + exp(z));
      double thresh = 0.8;
      bool link_good = z2 > thresh;
      /* paper fuckedness: */
      if (link_good)
	rate = 1;
      else
	rate = 0.1;
      return true;
      h(3);
      if (!link_good && !res) {
	h(4);
	return false;
      }
      else if (link_good && !res) {
	h(5);
	rate = 0.8;
	return true;
      }
      else if (!link_good && res) {
	h(6);
	return true; /* rate was set in call to get_bcast_stat */
      }
      else /* link_good && res */ {
	h(7);
	if (rate < 0.8) {
	  h(8);
	  rate = 0.8;
	}
	return true;
      }
      h(9);
    }
    else {
      h(10);
      return false;
    }
  }
  case EstByMeas: {
    h(11);
    struct timeval last;
    bool res = _link_tracker->get_bcast_stat(ip, rate, last);
    return res;
    break;
  }
  default:
    h(12);
    return false;
  }
}

bool
GridRouteTable::est_reverse_delivery_rate(const IPAddress ip, double &rate)
{
  switch (_est_type) {
  case EstBySig:
  case EstByQual: 
    h(101);
    return false;
    break;
  case EstBySigQual: {
    h(102);
    RTEntry *r = _rtes.findp(ip);
    if (r == 0 || r->num_hops() > 1) {
      h(103);
      return false;
    }
#if 0
    struct timeval last;
#if 0
    LinkStat::stat_t *s = _link_stat->_stats.findp(r->next_hop_eth);
#else
    struct {
      int qual;
      int sig;
      struct timeval when;
    } *s = 0;
#endif
    if (s == 0) {
      return false;
      h(104);
    }
    double z = 9.4519 + 0.0391 * s->sig + 0.5518 * s->qual;
    double z2 = 1 / (1 + exp(z));
    double thresh = 0.8;
    bool link_good = z2 > thresh;
    
    /* paper fuckedness: */
    if (link_good)
      rate = 1;
    else
      rate = 0.1;
    return true;
    
    unsigned int window = 0;
    unsigned int num_rx = 0;
    unsigned int num_expected = 0;
    bool res = false;_link_stat->get_bcast_stats(r->next_hop_eth, last, window, num_rx, num_expected);
    if (res && num_expected > 1) {
      h(105);
      double num_rx_ = num_rx;
      /* we assume all nodes have same hello period */
      double num_expected_ = num_expected;
      rate = (num_rx_ - 0.5) / num_expected_;
    }
    else {
      h(107);
      rate = 0;
    }
    if (!link_good && !res) {
      h(108);
      return false;
    }
    else if (link_good && !res) {
      h(109);
      rate = 0.8;
      return true;
    }
    else if (!link_good && res) {
      h(110);
      return true; /* rate was set in call to get_bcast_stats */
    }
    else /* link_good && res */ {
      h(111);
      if (rate < 0.8) {
	h(112);
	rate = 0.8;
      }
      return true;
    }
#else
    rate = 0;
    return false;
#endif
  }
  h(113);
  case EstByMeas: {
#if 0
    struct timeval last;
    RTEntry *r = _rtes.findp(ip);
    if (r == 0 || r->num_hops() > 1)
      return false;
    unsigned int window = 0;
    unsigned int num_rx = 0;
    unsigned int num_expected = 0;
    bool res = _link_stat->get_bcast_stats(r->next_hop_eth, last, window, num_rx, num_expected);
    if (!res || num_expected <= 1)
      return false;
    double num_rx_ = num_rx;
    double num_expected_ = num_expected;
    if (num_rx > num_expected)
      click_chatter("WARNING: est_reverse_delivery_rate: num_rx (%d) > num_expected (%d) for %s",
		    num_rx, num_expected, r->next_hop_eth.s().cc());
    rate = (num_rx_ - 0.5) / num_expected_;
#endif
    return true;
    break;
  }
  default:
    return false;
  }
}


void
GridRouteTable::init_metric(RTEntry &r)
{
  assert(r.num_hops() == 1);

  switch (_metric_type) {
  case MetricHopCount:
    r.metric = r.num_hops();
    r.metric_valid = true;
    break;
  case MetricMinDeliveryRate:
  case MetricCumulativeDeliveryRate:
    assert(0);
    /* code to estimate our delivery rate to this 1-hop nbr goes here */
    r.metric_valid = true;
    break;
  case MetricMinSigStrength:
  case MetricMinSigQuality: 
  case MetricCumulativeQualPct:
  case MetricCumulativeSigPct: {
    int sig = 0;
    int qual = 0;
    struct timeval last;
    bool res = _link_tracker->get_stat(r.dest_ip, sig, qual, last);
    if (!res) {
      click_chatter("GridRouteTable: no link sig/qual stats from 1-hop neighbor %s; not initializing metric\n",
		    r.dest_ip.s().cc());
      r.metric = _bad_metric;
      r.metric_valid = false;
      return;
    }
    struct timeval now;
    gettimeofday(&now, 0);
    now = now - last;
    int delta_ms = 1000 * now.tv_sec + (now.tv_usec / 1000);
    if (delta_ms > _timeout) {
      click_chatter("GridRouteTable: link sig/qual stats from 1-hop neighbor %s are too old; not initializing metric\n",
		    r.dest_ip.s().cc());
      r.metric = _bad_metric;
      r.metric_valid = false;
      return;
    }
    if (_metric_type == MetricMinSigQuality) 
      r.metric = (unsigned int) qual;
    else if (_metric_type == MetricMinSigStrength)
      r.metric = (unsigned int) -sig; // deal in -dBm
    else if (_metric_type == MetricCumulativeQualPct) 
      r.metric = qual_to_pct(qual);
    else // _metric_type == MetricCumulativeSigPct
      r.metric = sig_to_pct(sig);
    r.metric_valid = true;
  }
  break;
  case MetricEstTxCount: {
#if 0
    click_chatter("XXX");
#endif
    double fwd_rate = 0;
    double rev_rate = 0;
    bool res = est_forward_delivery_rate(r.next_hop_ip, fwd_rate);
    bool res2 = est_reverse_delivery_rate(r.next_hop_ip, rev_rate);
#if 0
    char buf[255];
    snprintf(buf, 255, "YYY %s %s -- res: %s, res2: %s, fwd: %f, rev: %f",
	     r.dest_ip.s().cc(), r.next_hop_ip.s().cc(),
	     res ? "true" : "false", res2 ? "true" : "false",
	     fwd_rate, rev_rate);
    click_chatter(buf);
#endif
    if (res && res2 && fwd_rate > 0 && rev_rate > 0) {
      if (fwd_rate >= 1) {
	click_chatter("init_metric ERROR: fwd rate %d is too high for %s",
		      (int) (100 * fwd_rate), r.next_hop_ip.s().cc());
	fwd_rate = 1;
      }
      if (rev_rate >= 1) {
	click_chatter("init_metric ERROR: rev rate %d is too high for %s",
		      (int) (100 * rev_rate), r.next_hop_ip.s().cc());
	rev_rate = 1;
      }
      r.metric = (int) (100 / (fwd_rate * rev_rate));
      if (r.metric < 100) 
	click_chatter("init_metric WARNING: metric too small (%d) for %s",
		      r.metric, r.next_hop_ip.s().cc());
      r.metric_valid = true;
      h(201);
    } 
    else {
      r.metric = _bad_metric;
      r.metric_valid = false;
      h(202);
    }
    break;
  }
  default:
    assert(0);
  }
} 

void 
GridRouteTable::update_metric(RTEntry &r)
{
  if (r.num_hops() == 0)
    return; // is broken route ad

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