gridroutetable.cc

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

  if (!r.metric_valid)
    return;

  if (!next_hop->metric_valid) {
    r.metric_valid = false;
    return;
  }

  switch (_metric_type) {
  case MetricHopCount:
    if (next_hop->metric > 1)
      click_chatter("GridRouteTable: WARNING metric type is hop count but next-hop %s metric is > 1 (%u)",
		    next_hop->dest_ip.s().cc(), next_hop->metric);
  case MetricEstTxCount: 
    if (_metric_type == MetricEstTxCount) {
      if (r.metric < (unsigned) 100 * (r.num_hops() - 1))
	click_chatter("update_metric WARNING received metric (%d) too low for %s (%d hops)",
		      r.metric, r.dest_ip.s().cc(), r.num_hops());
      if (next_hop->metric < 100)
	click_chatter("update_metric WARNING next hop %s for %s metric is too low (%d)",
		      next_hop->dest_ip.s().cc(), r.dest_ip.s().cc(), next_hop->metric);
    }
    r.metric += next_hop->metric;
    break;
  case MetricCumulativeDeliveryRate:
  case MetricCumulativeQualPct:
  case MetricCumulativeSigPct:
    r.metric = (r.metric * next_hop->metric) / 100;
    break;
  case MetricMinDeliveryRate: 
    r.metric = (next_hop->metric < r.metric) ? next_hop->metric : r.metric;
    break;
  case MetricMinSigStrength:
  case MetricMinSigQuality:
    // choose weakest signal, which is largest -dBm
    // *or* choose worst quality, which is smaller numbers
    r.metric = (next_hop->metric > r.metric) ? next_hop->metric : r.metric;
    break;
  default:
    assert(0);
  }
  r.metric_valid = true;
}


bool
GridRouteTable::metric_is_preferable(const RTEntry &r1, const RTEntry &r2)
{
  assert(r1.metric_valid && r2.metric_valid);

  switch (_metric_type) {
  case MetricHopCount:
  case MetricEstTxCount: 
    return r1.metric < r2.metric;
  case MetricCumulativeDeliveryRate:
  case MetricMinDeliveryRate:
    return r1.metric > r2.metric;
  case MetricMinSigQuality: 
  case MetricMinSigStrength:
    // smaller -dBm is stronger signal
    // *or* prefer smaller quality number
    return r1.metric < r2.metric; 
  case MetricCumulativeQualPct:
  case MetricCumulativeSigPct:
  default:
    assert(0);
  }
  return false;
}


bool
GridRouteTable::should_replace_old_route(const RTEntry &old_route, const RTEntry &new_route)
{
  /* prefer a strictly newer route */
  if (old_route.seq_no() > new_route.seq_no()) 
    return false;
  if (old_route.seq_no() < new_route.seq_no())
    return true;
  
  /* 
   * routes have same seqno, choose based on metric 
   */
  
  /* prefer a route with a valid metric */
  if (old_route.metric_valid && !new_route.metric_valid)
    return false;
  if (!old_route.metric_valid && new_route.metric_valid)
    return true;
  
  /* if neither metric is valid, just keep the route we have -- to aid
   * in stability -- as if I have any notion about that....
   *
   * actually, that's fucked.  would you prefer a 5-hop route or a 
   * 2-hop route, given that you don't have any other information about
   * them?  duh.  fall back to hopcount. 
   * bwahhhaaaahahaha!!! */
  if (!old_route.metric_valid && !new_route.metric_valid) {
    // return false;
    return new_route.num_hops() < old_route.num_hops();
  }
  
  // both metrics are valid
  /* update is from same node as last update, we should accept it to avoid unwarranted timeout */
  if (old_route.next_hop_ip == new_route.next_hop_ip)
    return true;
   
  /* update route if the metric is better */
  return metric_is_preferable(new_route, old_route);
}


/*
 * expects grid LR packets, with ethernet and grid hdrs
 */
Packet *
GridRouteTable::simple_action(Packet *packet)
{
  assert(packet);
  unsigned int jiff = click_jiffies();

  /* 
   * sanity check the packet, get pointers to headers 
   */  
  click_ether *eh = (click_ether *) packet->data();
  if (ntohs(eh->ether_type) != ETHERTYPE_GRID) {
    click_chatter("GridRouteTable %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("GridRouteTable %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);

  // this should be redundant (see HostEtherFilter in grid.click)
  if (ethaddr == _eth) {
    click_chatter("GridRouteTable %s: received own Grid packet; ignoring it", id().cc());
    packet->kill();
    return 0;
  }

  grid_hello *hlo = (grid_hello *) (gh + 1);
   
  // extended logging
  Timestamp ts = Timestamp::now();
  _extended_logging_errh->message("recvd %u from %s %d %d", ntohl(hlo->seq_no), ipaddr.s().cc(), ts.sec(), ts.usec());
  if (_log)
    _log->log_start_recv_advertisement(ntohl(hlo->seq_no), ipaddr, ts);
  
  if (_frozen) {
    if (_log)
      _log->log_end_recv_advertisement();
    packet->kill();
    return 0;
  }


  /*
   * add 1-hop route to packet's transmitter; perform some sanity
   * checking if entry already existed 
   */

  RTEntry *r = _rtes.findp(ipaddr);

  if (!r)
    click_chatter("GridRouteTable %s: adding new 1-hop route %s -- %s", 
		  id().cc(), ipaddr.s().cc(), ethaddr.s().cc()); 
  else if (r->num_hops() == 1 && r->next_hop_eth != ethaddr)
    click_chatter("GridRouteTable %s: ethernet address of %s changed from %s to %s", 
		  id().cc(), ipaddr.s().cc(), r->next_hop_eth.s().cc(), ethaddr.s().cc());

  /*
   * well, for now we'll just do the ping-pong on route ads.  ideally
   * we would piggyback the ping-pong data for a destination on any
   * unicast packet to that destination, using the latest info from
   * that destination.  we sould still do the ping-ponging in route
   * ads as well, in case we aren't sending data to that destination.
   * this would probably entail adding two elements: one to fill in
   * outgoing packets with the right stats, and another to pick up the
   * stats from incoming packets.  there would probably be a third
   * element which is a table to hold these stats and take care of the
   * averaging.  this could be the same as either the first or second
   * element, and should have a hook so that the routing table (*this*
   * element) can add information gleaned from the route ads.  one
   * drag is that we can't properly do the averaging -- each new
   * reading comes at a different time, not neccessarily evenly
   * spaced.  we should use some time-weighted average, instead of the
   * usual sample-based average.  the node measuring at the other end
   * of the link needs to timestamp when packet come in and it takes
   * the readings. 
   */

  /* 
   * individual link metric smoothing, or route metric smoothing?  we
   * will only smooth the ping-pong measurements on individual links;
   * we won't smooth metrics at the route level.  that's because we
   * can't even be sure that as the metrics change for a route to some
   * destination, the metric are even for the same route, i.e. same
   * set of links. 
   */

  int entry_sz = hlo->nbr_entry_sz;
  char *entry_ptr = (char *) (hlo + 1);

  /* look for ping-pong link stats about us */
#ifndef SMALL_GRID_HEADERS
  for (int i = 0; i < hlo->num_nbrs; i++, entry_ptr += entry_sz) {
    grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
    if (_ip == curr->ip && curr->num_hops == 1) {
      struct timeval tv;
      tv = ntoh(curr->measurement_time);
      _link_tracker->add_stat(ipaddr, ntohl(curr->link_sig), ntohl(curr->link_qual), tv);
      tv = ntoh(curr->last_bcast);
      _link_tracker->add_bcast_stat(ipaddr, curr->num_rx, curr->num_expected, tv);
      break;
    }
  }
#endif

  if (ntohl(hlo->ttl) > 0) {
    RTEntry new_r(ipaddr, ethaddr, gh, hlo, jiff);
    init_metric(new_r);
    if (r == 0 || should_replace_old_route(*r, new_r)) {
      if (_log)
	_log->log_added_route(GridLogger::WAS_SENDER, make_generic_rte(new_r));
      _rtes.insert(ipaddr, new_r);
      if (new_r.num_hops() > 1 && r && r->num_hops() == 1) {
	/* clear old 1-hop stats */
	_link_tracker->remove_all_stats(r->dest_ip);
      }
    }
    if (r)
      r->dest_eth = ethaddr;
  }
  
  /*
   * loop through and process other route entries in hello message 
   */
  Vector<RTEntry> triggered_rtes;
  Vector<IPAddress> broken_dests;

  entry_ptr = (char *) (hlo + 1);
  for (int i = 0; i < hlo->num_nbrs; i++, entry_ptr += entry_sz) {
    
    grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
    RTEntry route(ipaddr, ethaddr, curr, jiff);

    /* ignore route if ttl has run out */
    if (route.ttl <= 0)
      continue;

    /* ignore route to ourself */
    if (route.dest_ip == _ip)       
      continue;

    /* pseudo-split-horizon: ignore routes from nbrs that go back
       through us */
    if (curr->next_hop_ip == (unsigned int) _ip)
      continue;

    update_metric(route);

    RTEntry *our_rte = _rtes.findp(curr->ip);
    
    /* 
     * broken route advertisement 
     */
    if (curr->num_hops == 0) {

      if ((route.seq_no() & 1) == 0) {
	// broken routes should have odd seq_no
	click_chatter("ignoring invalid broken route entry from %s for %s: num_hops was 0 but seq_no was even\n",
		      ipaddr.s().cc(), route.dest_ip.s().cc());
	continue;
      }
    
      /* if we don't have a route to this destination, ignore it */
      if (!our_rte)
	continue;

      /* 
       * if our next hop to the destination is this packet's sender,
       * AND if the seq_no is newer than any information we have.
       * remove the broken route. 
       */
      if (our_rte->next_hop_ip == ipaddr &&
	  route.seq_no() > our_rte->seq_no()) {
	broken_dests.push_back(route.dest_ip);
	
	/* generate triggered broken route advertisement */
	triggered_rtes.push_back(route);

	if (_log)
	  _log->log_expired_route(GridLogger::BROKEN_AD, route.dest_ip);
      }
      /*
       * otherwise, triggered advertisement: if we have a good route
       * to the destination with a newer seq_no, advertise our new
       * information. 
       */
      else if (route.seq_no() < our_rte->seq_no()) {
	assert(!(our_rte->seq_no() & 1)); // valid routes have even seq_no
	if (our_rte->ttl > 0 && our_rte->metric_valid) {
	  triggered_rtes.push_back(*our_rte);

	  if (_log)
	    _log->log_triggered_route(our_rte->dest_ip);
	}
      }
      continue;
    }

    /* skip routes with too many hops */
    // this would change if using proxies
    if (route.num_hops() + 1 > _max_hops)
      continue;

    /* 
     * regular route entry -- should we stick it in the table?
     */
    if (our_rte == 0 || should_replace_old_route(*our_rte, route)) {
      _rtes.insert(route.dest_ip, route);
      if (route.num_hops() > 1 && our_rte && our_rte->num_hops() == 1) {
	/* clear old 1-hop stats */
	_link_tracker->remove_all_stats(our_rte->dest_ip);

#if NEXT_HOP_ETH_FIXUP
	/* fix up route entries for which this dest had been the next hop */
	Vector<RTEntry> changed_next_hop;
	for (RTIter i = _rtes.begin(); i; i++) {
	  if (i.value().next_hop_ip == route.dest_ip) {
	    RTEntry r = i.value();
	    /* some skoochy stuff here, this will make it very hard to keep track of things... */
	    r.next_hop_ip = route.next_hop_ip;
	    r.next_hop_eth = route.next_hop_eth;
	    // XXX how to calculate num_hops???, metric, etc.
	    // XXX also, last_updated_jiffies, etc.
	  }
	}	
	for (int i = 0; i < changed_next_hop.size(); i++)
	  _rtes.insert(changed_next_hop[i].dest_ip, changed_next_hop[i]);
#endif

      }
      
      if (_log)
	_log->log_added_route(GridLogger::WAS_ENTRY, make_generic_rte(route));
    }
  }

  /* delete broken routes */
  for (int i = 0; i < broken_dests.size(); i++) {
    bool removed = _rtes.remove(broken_dests[i]);
    assert(removed);
  }

  log_route_table();  // extended logging

  if (_log)
    _log->log_end_recv_advertisement();

  /* send triggered updates */
  if (triggered_rtes.size() > 0)
    send_routing_update(triggered_rtes, false); // XXX should seq_no get incremented for triggered routes -- probably?

  packet->kill();
  return 0;
}



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

  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
    const RTEntry &f = i.value();
    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.loc.s()
      + " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
      + " seq=" + String(f.seq_no())
      + " metric_valid=" + (f.metric_valid ? "yes" : "no")
      + " metric=" + String(f.metric)
      + "\n";
  }
  
  return s;
}

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

  String s;
  for (RTIter i = n->_rtes.begin(); i; i++) {
    const RTEntry &f = i.value();
    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.loc.s()
      //      + " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
      + " seq=" + String(f.seq_no())
      + "\n";
  }
  
  return s;
}

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

  return s;
}

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

  return s;
}


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


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

String
GridRouteTable::metric_type_to_string(MetricType t)
{
  switch (t) {
  case MetricHopCount: return "hopcount"; break;
  case MetricCumulativeDeliveryRate: return "cumulative_delivery_rate"; break;
  case MetricMinDeliveryRate: return "min_delivery_rate"; break;
  case MetricMinSigStrength: return "min_sig_strength"; break;
  case MetricMinSigQuality: return "min_sig_quality"; break;
  case MetricCumulativeQualPct: return "cumulative_qual_pct"; break;
  case MetricCumulativeSigPct: return "cumulative_sig_pct"; break;
  case MetricEstTxCount:   return "est_tx_count"; break;
  default: 
    return "unknown_metric_type";
  }
}


String
GridRouteTable::print_metric_type(Element *e, void *)
{
  GridRouteTable *n = (GridRouteTable *) e;
  return metric_type_to_string(n->_metric_type) + "\n";
}

GridRouteTable::MetricType 
GridRouteTable::check_metric_type(const String &s)
{
  String s2 = s.lower();
  if (s2 == "hopcount")
    return MetricHopCount;
  else if (s2 == "cumulative_delivery_rate")
    return MetricCumulativeDeliveryRate;
  else if (s2 == "min_delivery_rate")
    return MetricMinDeliveryRate;
  else if (s2 == "min_sig_strength")
    return MetricMinSigStrength;
  else if (s2 == "min_sig_quality")
    return MetricMinSigQuality;
  else if (s2 == "cumulative_qual_pct")
    return MetricCumulativeQualPct;
  else if (s2 == "cumulative_sig_pct")
    return MetricCumulativeSigPct;
  else if (s2 == "est_tx_count")
    return MetricEstTxCount;
  else
    return MetricUnknown;
}

int
GridRouteTable::write_metric_type(const String &arg, Element *el, 
				  void *, ErrorHandler *errh)
{
  GridRouteTable *rt = (GridRouteTable *) el;
  MetricType type = check_metric_type(arg);
  if (type < 0)
    return errh->error("unknown metric type ``%s''", ((String) arg).cc());
  
  if (type != rt->_metric_type) {
    rt->_metric_type = type;

    if (type == MetricCumulativeSigPct) {
      rt->_max_metric = _max_sig;
      rt->_min_metric = _min_sig;
    }
    else if (type == MetricCumulativeQualPct) {