updateroutes.cc

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

/*
 * updateroutes.{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 "updateroutes.hh"
#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 "grid.hh"
CLICK_DECLS

UpdateGridRoutes::UpdateGridRoutes() : Element(1, 2), _max_hops(3), 
  _hello_timer(hello_hook, this), 
  _expire_timer(expire_hook, this),
  _sanity_timer(sanity_hook, this),
  _num_updates_sent(0), _seq_no(0)
{
}

UpdateGridRoutes::~UpdateGridRoutes()
{
}



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



int
UpdateGridRoutes::configure(Vector<String> &conf, ErrorHandler *errh)
{
  int res = cp_va_parse(conf, this, errh,
			cpInteger, "entry timeout (msec)", &_timeout,
			cpInteger, "Hello broadcast period (msec)", &_period,
			cpInteger, "Hello broadcast jitter (msec)", &_jitter,
			cpEthernetAddress, "source Ethernet address", &_ethaddr,
			cpIPAddress, "source IP address", &_ipaddr,
			cpOptional,
			cpInteger, "max hops", &_max_hops,
			cpEnd);
  if (res < 0)
    return res;

  // convert msecs to jiffies
  if (_timeout == 0)
    _timeout = -1;
  if (_timeout > 0) {
    _timeout_jiffies = (CLICK_HZ * _timeout) / 1000;
    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");

  return res;
}



int
UpdateGridRoutes::initialize(ErrorHandler *)
{
  //  ScheduleInfo::join_scheduler(this, errh);
  _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);

  _sanity_timer.initialize(this);
  _sanity_timer.schedule_after_ms(SANITY_CHECK_PERIOD); // Send periodically

  return 0;
}



Packet *
UpdateGridRoutes::simple_action(Packet *packet)
{
  /*
   * expects grid packets, with MAC hdrs
   */
  assert(packet);
  unsigned int jiff = click_jiffies();
  
  /*
   * Update immediate neighbor table with this packet's transmitter's
   * info.
   */
  click_ether *eh = (click_ether *) packet->data();
  if (ntohs(eh->ether_type) != ETHERTYPE_GRID) {
    click_chatter("%s: got non-Grid packet type", id().cc());
    return packet;
  }
  grid_hdr *gh = (grid_hdr *) (packet->data() + sizeof(click_ether));
  IPAddress ipaddr((unsigned char *) &gh->tx_ip);
  EtherAddress ethaddr((unsigned char *) eh->ether_shost);

  if (ethaddr == _ethaddr) {
    click_chatter("%s: received own Grid packet; ignoring it", id().cc());
    return packet;
  }

  NbrEntry *nbr = _addresses.findp(ipaddr);
  if (nbr == 0) {
    // this src addr not already in map, so add it
    NbrEntry new_nbr(ethaddr, ipaddr, jiff);
    _addresses.insert(ipaddr, new_nbr);
    click_chatter("%s: adding %s -- %s", id().cc(), ipaddr.s().cc(), ethaddr.s().cc()); 
  }
  else {
    // update jiffies and MAC for existing entry
    nbr->last_updated_jiffies = jiff;
    if (nbr->eth != ethaddr) 
      click_chatter("%s: updating %s -- %s", id().cc(), ipaddr.s().cc(), ethaddr.s().cc()); 
    nbr->eth = ethaddr;
  }
  
  /* XXX need to update (or add) routing entry in _rtes to be the
     correct one-hop entry for destination of this sender, ipaddr. */
  
  /*
   * perform further packet processing, extrace routing information from DSDV packets
   */
  switch (gh->type) {
  case grid_hdr::GRID_LR_HELLO:
    {   
      grid_hello *hlo = (grid_hello *) (packet->data() + sizeof(click_ether) + sizeof(grid_hdr));

      /*
       * update far nbr info with this hello sender info -- list sender as
       * its own next hop.
       */
      far_entry *fe = _rtes.findp(ipaddr);
      if (fe == 0) {
	// we don't already know about it, so add it
	/* XXX not using HashMap2 very efficiently --- fix later */

	/* since DSDV update packets on travel one hop, all the tx_ip
           and tx_loc transmitter info in the grid_hdr is the same as
           the sender ip and loc info */

	_rtes.insert(ipaddr, far_entry(jiff, grid_nbr_entry(gh->ip, gh->ip, 1, ntohl(hlo->seq_no))));
	fe = _rtes.findp(ipaddr);
	fe->nbr.loc = gh->loc;
	fe->nbr.loc_err = ntohs(gh->loc_err);
	fe->nbr.loc_good = gh->loc_good;
	fe->nbr.age = decr_age(ntohl(hlo->age), grid_hello::MIN_AGE_DECREMENT);
      } else { 
	/* i guess we always overwrite existing info, because we heard
           this info directly from the node... */
	// update pre-existing information
	fe->last_updated_jiffies = jiff;
	fe->nbr.num_hops = 1;
	fe->nbr.next_hop_ip = gh->ip;
	fe->nbr.loc = gh->loc;
	fe->nbr.loc_err = ntohs(gh->loc_err);
	fe->nbr.loc_good = gh->loc_good;
	fe->nbr.seq_no = ntohl(hlo->seq_no);
	fe->nbr.age = decr_age(ntohl(hlo->age), grid_hello::MIN_AGE_DECREMENT);
      }

      
      /* 
       * add this sender's nbrs to our far neighbor list.  
       */
      int entry_sz = hlo->nbr_entry_sz;
      Vector<grid_nbr_entry> triggered_rtes;
      Vector<IPAddress> broken_rtes;

      // loop through all the route entries in the packet
      for (int i = 0; i < hlo->num_nbrs; i++) {
	grid_nbr_entry *curr = (grid_nbr_entry *) (packet->data() + sizeof(click_ether) + 
						   sizeof(grid_hdr) + sizeof(grid_hello) +
						   i * entry_sz);

	if (IPAddress(curr->ip) == _ipaddr)
	  continue; // we already know how to get to ourself -- don't want to advertise some other strange route to us!

	if (IPAddress(curr->next_hop_ip) == _ipaddr)
	  continue; // pseduo-split-horizon: ignore routes from nbrs that go back through us

	if (curr->num_hops == 0) {
	  /* this entry indicates a broken route.  if the seq_no is
             newer than any information we have, AND we route to the
             specified address with this packet's sender as next hop,
             remove the broken route.  propagate broken route info.
             if the seq_no is older than some good route information
             we have, advertise our new information to overthrow the
             old broken route info we received */

	  IPAddress broken_ip(curr->ip);
	  fe = _rtes.findp(broken_ip);
	  if (fe != 0) {
	    if (ntohl(curr->seq_no) > fe->nbr.seq_no && fe->nbr.next_hop_ip == gh->ip) {
	      // invalidate a route we have through this next hop
	      grid_nbr_entry new_entry = fe->nbr;
	      new_entry.num_hops = 0;
	      // who told us about the broken route, so the
	      // pseudo-split-horizon will ignore this entry
	      new_entry.next_hop_ip = curr->ip; 
	      // broken route info should be odd seq_no's
	      new_entry.seq_no = ntohl(curr->seq_no);
	      assert((new_entry.seq_no & 1) == 1); // XXX convert this to more robust check
	      new_entry.age = decr_age(ntohl(curr->age), grid_hello::MIN_AGE_DECREMENT);
	      if (new_entry.age > 0) // don't propagate expired info
		triggered_rtes.push_back(new_entry);
	      broken_rtes.push_back(fe->nbr.ip);
	    }
	    else if (ntohl(curr->seq_no) < fe->nbr.seq_no) {
	      // we know more recent info about a route that this
	      // entry is trying to invalidate
	      grid_nbr_entry new_entry = fe->nbr;
	      assert((new_entry.seq_no & 1) == 0);
	      if (new_entry.age > 0)
		triggered_rtes.push_back(new_entry);
	    }
	  }
	  else
	    ; // else we never had a route to this broken destination anyway

	  continue;
	}

	if (curr->num_hops + 1 > _max_hops)
	  continue; // skip this one, we don't care about nbrs too many hops away

	IPAddress curr_ip(curr->ip);
	fe = _rtes.findp(curr_ip);
	if (fe == 0) {
	  // we don't already know about this nbr
	  _rtes.insert(curr_ip, far_entry(jiff, grid_nbr_entry(curr->ip, gh->ip, curr->num_hops + 1, ntohl(curr->seq_no))));
	  fe =_rtes.findp(curr_ip);
	  fe->nbr.loc = curr->loc;
	  fe->nbr.loc_err = ntohs(curr->loc_err);
	  fe->nbr.loc_good = curr->loc_good;
	  fe->nbr.age = decr_age(ntohl(curr->age), grid_hello::MIN_AGE_DECREMENT);
	}
	else { 
	  // replace iff seq_no is newer, or if seq_no is same and hops are less
	  unsigned int curr_seq = ntohl(curr->seq_no);
	  if (curr_seq > fe->nbr.seq_no ||
	      (curr_seq == fe->nbr.seq_no && (curr->num_hops + 1) < fe->nbr.num_hops)) {
	    fe->nbr.num_hops = curr->num_hops + 1;
	    fe->nbr.next_hop_ip = gh->ip;
	    fe->nbr.loc = curr->loc;
	    fe->nbr.loc_err = ntohs(curr->loc_err);
	    fe->nbr.loc_good = curr->loc_good;
	    fe->nbr.seq_no = curr_seq;
	    fe->last_updated_jiffies = jiff;
	    fe->nbr.age = decr_age(ntohl(curr->age), grid_hello::MIN_AGE_DECREMENT);
	    // if new entry is more than one hop away, remove from nbrs table also
	    if (fe->nbr.num_hops > 1)
	      _addresses.remove(fe->nbr.ip); // may fail, e.g. wasn't in nbr addresses table anyway
	  }
	}
      }
    
      if (triggered_rtes.size() > 0) {
        // send the triggered update
        send_routing_update(triggered_rtes, false);
      }