dsrroutetable.cc

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

/*
 * dsrroutetable.{cc,hh}
 * Shweta Bhandare, Sagar Sanghani, Sheetalkumar Doshi, Timothy X Brown
 * Daniel Aguayo
 *
 * Copyright (c) 2003 Massachusetts Institute of Technology
 * Copyright (c) 2003 University of Colorado at Boulder
 *
 * 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 <click/package.hh>
#include <clicknet/ether.h>
#include <click/etheraddress.hh>
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/bitvector.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <clicknet/ip.h>
#include <click/router.hh>
#include <click/standard/scheduleinfo.hh>
#include "dsrroutetable.hh"
#include "dsr.hh"
#include "gridgenericmetric.hh"

CLICK_DECLS

#define DEBUG_CHATTER  if (_debug) click_chatter


DSRRouteTable::DSRRouteTable()
  : _rreq_expire_timer(static_rreq_expire_hook, this),
    _rreq_issue_timer(static_rreq_issue_hook, this),
    _sendbuffer_timer(static_sendbuffer_timer_hook, this),
    _sendbuffer_check_routes(false),
    _blacklist_timer(static_blacklist_timer_hook, this),
    _outq(0), _metric(0), _use_blacklist(true),
    _debug(false)
{
  me = new IPAddress;
  
  timeval tv;
  click_gettimeofday(&tv);
  _rreq_id = tv.tv_sec & 0xffff;

  
  add_input();  // IP packets - input 0
  add_input();  // incoming DSR packets - input 1
  add_input();  // packets for which tx failed - input 2

  add_output(); // IP packets for the kernel - output 0
  add_output(); // DSR routing packets - output 1
  add_output(); // DSR data packets - output 2
}

DSRRouteTable::~DSRRouteTable()
{
  flush_sendbuffer();
  uninitialize();

  for (FWReqIter i = _forwarded_rreq_map.begin(); i; i++) {
    ForwardedReqVal &frv = i.value();
    if (frv.p) frv.p->kill();
    frv.p = NULL;
  }

  delete me;
}

int
DSRRouteTable::configure(Vector<String> &conf, ErrorHandler *errh)
{
  // read the parameters from a configuration string 
  return (cp_va_parse(conf, this, errh,
		      cpIPAddress, "ip address", me, 
		      cpElement, "link table", &_link_table, 
		      cpKeywords,
		      "OUTQUEUE", cpElement, "SimpleQueue element", &_outq,
		      "METRIC", cpElement, "GridGenericMetric element", &_metric,
		      "USE_BLACKLIST", cpBool, "use blacklist?", &_use_blacklist,
		      "DEBUG", cpBool, "Debug", &_debug,
		      cpEnd)<0);

  if (_outq && _outq->cast("SimpleQueue") == 0)
    return errh->error("OUTQUEUE element is not a SimpleQueue");

  if (_metric && _metric->cast("GridGenericMetric") == 0)
    return errh->error("METRIC element is not a GridGenericMetric");
}

void
DSRRouteTable::flush_sendbuffer()
{
  for (SBMapIter i=_sendbuffer_map.begin(); i; i++) {
    SendBuffer &sb = i.value();
    for (int j = 0; j < sb.size(); j++) {
      sb[j].check();
      sb[j]._p->kill();
    }
    sb = SendBuffer();
  }
}

void
DSRRouteTable::check() 
{
  assert(me);

  // _link_table
  assert(_link_table);

  // _blacklist
  for (BlacklistIter i = _blacklist.begin(); i; i++)
    i.value().check();

  // _sendbuffer_map
  for (SBMapIter i=_sendbuffer_map.begin(); i; i++) {
    SendBuffer &sb = i.value();
    for (int j = 0; j < sb.size(); j++) {
      sb[j].check();
    }
  }

  // _forwarded_rreq_map
  for (FWReqIter i = _forwarded_rreq_map.begin(); i; i++)
    i.value().check();
  
  // _initiated_rreq_map
  for (InitReqIter i = _initiated_rreq_map.begin(); i; i++)
    i.value().check();
    
  // _rreq_expire_timer;
  assert(_rreq_expire_timer.scheduled());
  
  // _rreq_issue_timer;
  assert(_rreq_issue_timer.scheduled());

  // _sendbuffer_timer;
  assert(_sendbuffer_timer.scheduled());

  // _blacklist_timer;
  assert(_blacklist_timer.scheduled());    
}

int
DSRRouteTable::initialize(ErrorHandler *)
{
  // expire entries on list of rreq's we have seen
  _rreq_expire_timer.initialize(this);
  _rreq_expire_timer.schedule_after_ms(DSR_RREQ_EXPIRE_TIMER_INTERVAL);

  // expire packets in the sendbuffer
  _sendbuffer_timer.initialize(this);
  _sendbuffer_timer.schedule_after_ms(DSR_SENDBUFFER_TIMER_INTERVAL);

  // check if it's time to reissue a route request
  _rreq_issue_timer.initialize(this);
  _rreq_issue_timer.schedule_after_ms(DSR_RREQ_ISSUE_TIMER_INTERVAL);
  
  _blacklist_timer.initialize(this);
  _blacklist_timer.schedule_after_ms(DSR_BLACKLIST_TIMER_INTERVAL);
  
  return 0;
}

void
DSRRouteTable::uninitialize()
{
  _rreq_expire_timer.unschedule();
  _rreq_issue_timer.unschedule();
  _sendbuffer_timer.unschedule();
  _blacklist_timer.unschedule();
}

//
// functions to handle expiration of rreqs in our forwarded_rreq map
//
void
DSRRouteTable::static_rreq_expire_hook(Timer *, void *v)
{
  DSRRouteTable *r = (DSRRouteTable *)v;
  r->rreq_expire_hook();
}
void
DSRRouteTable::rreq_expire_hook() 
{
  // iterate over the _forwarded_rreq_map and remove old entries.

  // also look for requests we're waiting to forward (after a
  // unidirectionality test) and if the last hop is not in the
  // blacklist, then forward it.  if it's been a while since we issued
  // the direct request, kill the packet.
  //
  // give up on the unidirectionality test (and kill the packet) after
  // DSR_RREQ_UNITEST_TIMEOUT.  otherwise we might end up forwarding
  // the request long after it came to us.

  // we also kill the packet if we positively determined
  // unidirectionality -- e.g. if we get a tx error forwarding a route
  // reply in the meantime.

  struct timeval curr_time;
  click_gettimeofday(&curr_time);
  
//   click_chatter("checking\n");
  
  Vector<ForwardedReqKey> remove_list;
  for (FWReqIter i = _forwarded_rreq_map.begin(); i; i++) {

    ForwardedReqVal &val = i.value();
    
    if (val.p != NULL) { // we issued a unidirectionality test
      DSRRoute req_route = extract_request_route(val.p);

      IPAddress last_forwarder = req_route[req_route.size() - 1].ip();
      EtherAddress last_eth = last_forwarder_eth(val.p);

      int status = check_blacklist(last_forwarder);
      if (status == DSR_BLACKLIST_NOENTRY) { // reply came back
	DEBUG_CHATTER(" * unidirectionality test succeeded; forwarding route request\n");
        forward_rreq(val.p);
	
	// a) we cannot issue a unidirectionality test if there is an
	// existing metric
	//
	// b) if, after we issue a test, this RREQ comes over a
	// different link, with a valid metric, and we forward it,
	// then we essentially cancel the unidirectionality test.
	//
	// so we know that if the test comes back positive we can just
	// just calculate the route metric and call that best.
	req_route.push_back(DSRHop(*me, get_metric(last_eth)));
	val.best_metric = route_metric(req_route);

        val.p = NULL;
      } else if ((status == DSR_BLACKLIST_UNI_PROBABLE) ||
		 (diff_in_ms(curr_time, val._time_unidtest_issued) > DSR_BLACKLIST_UNITEST_TIMEOUT)) {
	DEBUG_CHATTER(" * unidirectionality test failed; killing route request\n");
	val.p->kill();
	val.p = NULL;
      }
    }

//     click_chatter("i.key is %s %s %d %d\n", i.key()._src.s().cc(), 
// 		  i.key()._target.s().cc(), i.key()._id,
// 		  diff_in_ms(curr_time, i.value()._time_forwarded));

    if (diff_in_ms(curr_time, i.value()._time_forwarded) > DSR_RREQ_TIMEOUT) {
      IPAddress src(i.key()._src);
      IPAddress dst(i.key()._target);
      unsigned int id = i.key()._id;
      DEBUG_CHATTER("RREQ entry has expired; %s -> %s (%d)\n",
		    src.s().cc(), dst.s().cc(), id);
      
      remove_list.push_back(i.key());
    }
  }
  for (int i = 0; i < remove_list.size(); i++) {
    //    click_chatter("XXX removing from forwarded rreq map\n");
    _forwarded_rreq_map.remove(remove_list[i]);
  }

//   click_chatter("exiting %d\n", DSR_RREQ_EXPIRE_TIMER_INTERVAL);
  _rreq_expire_timer.schedule_after_ms(DSR_RREQ_EXPIRE_TIMER_INTERVAL);

  check();

}


//
// functions to manage the sendbuffer
//
void
DSRRouteTable::static_sendbuffer_timer_hook(Timer *, void *v)
{
  DSRRouteTable *rt = (DSRRouteTable*)v;
  rt->sendbuffer_timer_hook();
}
void
DSRRouteTable::sendbuffer_timer_hook()
{
  //  DEBUG_CHATTER ("checking sendbuffer\n");

  struct timeval curr_time;
  click_gettimeofday(&curr_time);

  int total = 0; // total packets sent this scheduling
  bool check_next_time = false;

  for (SBMapIter i=_sendbuffer_map.begin(); i; i++) {

    SendBuffer &sb = i.value();
    IPAddress dst = i.key();

    if (! sb.size()) {
      // DEBUG_CHATTER(" * send buffer for destination %s is empty\n", dst.s().cc());
      continue;
    }

    if (_sendbuffer_check_routes) {  // have we received a route reply recently?

      // XXX should we check for routes for packets in the sendbuffer
      // every time we update the link cache (i.e. if we forward
      // someone else's route request/reply and add new entries to our
      // cache?  right now we only check if we receive a route reply
      // directed to us.
      
      DEBUG_CHATTER(" * send buffer has %d packet%s with destination %s\n",
		    sb.size(),
		    sb.size() == 1 ? "" : "s",
		    dst.s().cc());
      
      // search route for destination in the link cache first
      _link_table->dijkstra(false);
      Vector<IPAddress> route = _link_table->best_route(dst, false);
      
      if (route.size() > 1) { // found the route..
	DEBUG_CHATTER(" * have a route:\n");
	
	for (int j=0; j<route.size(); j++)
	  DEBUG_CHATTER(" - %d  %s \n",
			j, route[j].s().cc());
	
	if (total < DSR_SENDBUFFER_MAX_BURST) {

	  int k;
	  for (k = 0; k < sb.size() && total < DSR_SENDBUFFER_MAX_BURST; k++, total++) {
	    // send out each of the buffered packets
	    Packet *p = sb[k]._p;
	    Packet *p_out = add_dsr_header(p, route);
	    output(2).push(p_out);
	  }
	  
	  if (k < sb.size())
	    check_next_time = true; // we still have packets with a route
	  
	  
	  SendBuffer new_sb;
	  for ( ; k < sb.size() ; k++) {
	    // push whatever packets we didn't send onto new_sb, then
	    // replace the existing sendbuffer
	    new_sb.push_back(sb[k]._p);
	  }
	  
	  sb = new_sb;

	}
      
	// go to the next destination's sendbuffer; we don't check for
	// expired packets if there is a route for that host
	continue;

      } else {
	DEBUG_CHATTER("still no route to %s\n",
		      dst.s().cc());
      }
    }

    // if we're here, either check_routes was false (and we're being
    // called because the timer expired) or there was no route

    SendBuffer new_sb;
    for (int j = 0; j < sb.size(); j++) {
      unsigned long time_elapsed = diff_in_ms(curr_time, sb[j]._time_added);
      
      if (time_elapsed >= DSR_SENDBUFFER_TIMEOUT) {
	DEBUG_CHATTER(" * packet %d expired in send buffer\n", j);
	sb[j]._p->kill();
      } else {
	// DEBUG_CHATTER(" * packet %d gets to stay\n", i);
	new_sb.push_back(sb[j]);
      }
    }
    sb = new_sb;
    if (sb.size() == 0) {
      // if we expire the last packet in the sendbuffer with this
      // destination, stop sending RREQs
      stop_issuing_request(dst);
    }
  }

  _sendbuffer_check_routes = check_next_time;
  _sendbuffer_timer.schedule_after_ms(DSR_SENDBUFFER_TIMER_INTERVAL);

  check();
}
void
DSRRouteTable::buffer_packet(Packet *p)
{
  IPAddress dst = IPAddress(p->dst_ip_anno());
  DEBUG_CHATTER("buffering packet for %s", dst.s().cc());

  SendBuffer *sb = _sendbuffer_map.findp(dst);
  if (!sb) {
    _sendbuffer_map.insert(dst, SendBuffer());
    sb = _sendbuffer_map.findp(dst);
  }

  if (sb->size() >= DSR_SENDBUFFER_MAX_LENGTH) {
    DEBUG_CHATTER("too many packets for this host; killing\n");
    p->kill();
  } else {
    sb->push_back(p);
    DEBUG_CHATTER("%d packets for this host\n", sb->size());
  }
}


// functions to downgrade blacklist entries
void 
DSRRouteTable::static_blacklist_timer_hook(Timer *, void *v)
{
  DSRRouteTable *rt = (DSRRouteTable*)v;
  rt->blacklist_timer_hook();
}
void 
DSRRouteTable::blacklist_timer_hook()
{
  timeval curr_time;
  click_gettimeofday(&curr_time);

  for (BlacklistIter i = _blacklist.begin(); i; i++) {
    if ((i.value()._status == DSR_BLACKLIST_UNI_PROBABLE) &&
	(diff_in_ms(curr_time, i.value()._time_updated) > DSR_BLACKLIST_ENTRY_TIMEOUT)) {
      
      BlacklistEntry &e = i.value();
      
      DEBUG_CHATTER(" * downgrading blacklist entry for host %s\n", i.key().s().cc());
      
      e._status = DSR_BLACKLIST_UNI_QUESTIONABLE;
    }
  }  
  _blacklist_timer.schedule_after_ms(DSR_BLACKLIST_TIMER_INTERVAL);

  check();
}


void
DSRRouteTable::push(int port, Packet *p_in)
{   
  const click_ip *ip = p_in->ip_header();

  if (port==0) {  // IP packet from the kernel

    IPAddress dst_addr(ip->ip_dst.s_addr);

    DEBUG_CHATTER(" * DSR (%s): got IP packet with destination is %s\n", 
		  this->id().cc(),
		  dst_addr.s().cc());
    
    if (dst_addr == *me) { // for simpler debugging config
      // out to the kernel  
      output(0).push(p_in);
      return;
    }
    
    _link_table->dijkstra(false);
    Vector<IPAddress> route = _link_table->best_route(dst_addr, false);
    if (route.size() > 1) {

      DEBUG_CHATTER(" * have cached route:\n");

      for (int j=0; j < route.size(); j++)
	DEBUG_CHATTER(" - %d  %s\n", j, route[j].s().cc());
      
      // add DSR headers to packet..
      Packet *p = add_dsr_header(p_in, route);

      output(2).push(p);
      return;

    } else {

      DEBUG_CHATTER(" * don't have route to %s; buffering packet\n", dst_addr.s().cc());

      buffer_packet(p_in);
      start_issuing_request(dst_addr);

      return;

    }
    
  } else if (port==1) { // incoming packet is a DSR packet

    const click_dsr_option *dsr_option = (const click_dsr_option *)(p_in->data() +