updateroutes.cc

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

      // remove the broken routes
      for (int i = 0; i < broken_rtes.size(); i++)
	assert(_rtes.remove(broken_rtes[i]));
    }
    break;
    
  default:
    break;
  }
  return packet;
}



static String 
print_rtes(Element *e, void *)
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) e;
  
  String s;
  for (UpdateGridRoutes::FarTable::iterator iter = n->_rtes.begin(); iter; iter++) {
    UpdateGridRoutes::far_entry f = iter.value();
    s += IPAddress(f.nbr.ip).s() 
      + " next_hop=" + IPAddress(f.nbr.next_hop_ip).s() 
      + " num_hops=" + String((int) f.nbr.num_hops) 
      + " loc=" + f.nbr.loc.s()
      + " err=" + (f.nbr.loc_good ? "" : "-") + String(f.nbr.loc_err) // negate loc if invalid
      + " seq_no=" + String(f.nbr.seq_no)
      + "\n";
  }
  return s;
}

static String
print_nbrs(Element *e, void *)
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) e;

  String s;
  for (UpdateGridRoutes::Table::iterator iter = n->_addresses.begin(); iter; iter++) {
    s += iter.key().s();
    s += " eth=" + iter.value().eth.s();
    s += "\n";
  }
  return s;
}

static String
print_ip(Element *e, void *)
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) e;
  return n->_ipaddr.s();
}


static String
print_eth(Element *e, void *)
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) e;
  return n->_ethaddr.s();
}


void
UpdateGridRoutes::add_handlers()
{
  add_default_handlers(false);
  add_read_handler("nbrs", print_nbrs, 0);
  add_read_handler("rtes", print_rtes, 0);
  add_read_handler("ip", print_ip, 0);
  add_read_handler("eth", print_eth, 0);
}




void
UpdateGridRoutes::get_rtes(Vector<grid_nbr_entry> *retval) 
{
  assert(retval != 0);
  expire_routes();
  for (UpdateGridRoutes::FarTable::iterator iter = _rtes.begin(); iter; iter++)
    retval->push_back(iter.value().nbr);
}


void
UpdateGridRoutes::sanity_hook(Timer *, void *thunk) 
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) thunk;
  
  if (n->_num_updates_sent > SANITY_CHECK_MAX_PACKETS)
    click_chatter("%s: sent more than %d routing updates in %d milliseconds!",
		  n->id().cc(), SANITY_CHECK_MAX_PACKETS, SANITY_CHECK_PERIOD);
  n->_num_updates_sent = 0;

  n->_expire_timer.schedule_after_ms(SANITY_CHECK_PERIOD);
}

void
UpdateGridRoutes::expire_hook(Timer *, void *thunk) 
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) thunk;

  // decrement the ages of the route entries
  /* why don't we do this is in expire_routes also?  i think i
     remember: because expire_routes gets called all the time,
     vs. this hook which is actually called on a time basis. */
  /* decrement age separately from expiring routes; we expire the
     routes often in private functions to clean up, and we may not
     want to adjust the age by a whole _period.  yes, basically the
     time handling is junky here */
  for (UpdateGridRoutes::FarTable::iterator iter = n->_rtes.begin(); iter; iter++) {
    // XXX yucky
    *((unsigned int *) &(iter.value().nbr.age)) = decr_age(iter.value().nbr.age, EXPIRE_TIMER_PERIOD);
  }
  
  Vector<grid_nbr_entry> expired_info = n->expire_routes();
  
  if (expired_info.size() > 0) {
    // make and send the packet advertising any broken routes
    n->send_routing_update(expired_info, false);
  }

  n->_expire_timer.schedule_after_ms(EXPIRE_TIMER_PERIOD);
}


Vector<grid_nbr_entry>
UpdateGridRoutes::expire_routes()
{
  /* removes expired routes and immediate neighbor entries from the
     tables.  returns a vector of expired routes which is suitable for
     inclusion in a broken route advertisement. */

  assert(_timeout > 0);
  unsigned int jiff = click_jiffies();

  // XXX not sure if we are allowed to iterate while modifying map
  // (i.e. erasing entries), so figure out what to expire first.
  typedef HashMap<IPAddress, bool> xa_t;
  xa_t expired_addresses;
  Vector<grid_nbr_entry> expired_nbrs;

  // find the expired immediate entries
  for (UpdateGridRoutes::Table::iterator iter = _addresses.begin(); iter; iter++) 
    if (jiff - iter.value().last_updated_jiffies > _timeout_jiffies)
      expired_addresses.insert(iter.key(), true);

  // find expired routing entries -- either we have had the entry for
  // too long, or it has been flying around the whole network for too
  // long, or we have expired the next hop from our immediate neighbor
  for (UpdateGridRoutes::FarTable::iterator iter = _rtes.begin(); iter; iter++) {
    assert(iter.value().nbr.num_hops > 0);
    if (jiff - iter.value().last_updated_jiffies > _timeout_jiffies ||
	iter.value().nbr.age == 0 ||
	expired_addresses.findp(iter.value().nbr.next_hop_ip)) {
      grid_nbr_entry nbr = iter.value().nbr;
      nbr.num_hops = 0;
      nbr.seq_no++; // odd numbers indicate broken routes
      nbr.age = grid_hello::MAX_AGE_DEFAULT;
      expired_nbrs.push_back(nbr);
    }
  }

  // remove expired immediate nbr entries
  for (xa_t::iterator iter = expired_addresses.begin(); iter; iter++) {
    click_chatter("%s: expiring address for %s",
                  id().cc(), iter.key().s().cc());
    assert(_addresses.remove(iter.key()));
  }

  // remove expired route table entry
  for (int i = 0; i < expired_nbrs.size(); i++) {
    click_chatter("%s: expiring route entry for %s", id().cc(), IPAddress(expired_nbrs[i].ip).s().cc());
    assert(_rtes.remove(expired_nbrs[i].ip));
  }

  return expired_nbrs;
}


void
UpdateGridRoutes::hello_hook(Timer *, void *thunk)
{
  UpdateGridRoutes *n = (UpdateGridRoutes *) thunk;

  /* XXX is this a bug?  we expire some routes, but don't advertise
     them as broken anymore... */
  n->expire_routes();

  Vector<grid_nbr_entry> rte_entries;
  for (UpdateGridRoutes::FarTable::iterator iter = n->_rtes.begin(); iter; iter++) {
    /* XXX if everyone is using the same max-hops parameter, we could
       leave out all of our entries that are exactly max-hops hops
       away, because we know those entries will be greater than
       max-hops at any neighbor.  but, let's leave it in case we have
       different max-hops across the network */
    /* because we called expire_routes() at the top of this function,
       we know we are not propagating any route entries with age of 0
       or that have timed out */
    rte_entries.push_back(iter.value().nbr);
  }

  // make and send the packet
  n->send_routing_update(rte_entries, true);

  // XXX this random stuff is not right i think... wouldn't it be nice
  // if click had a phat RNG like ns?
  int r2 = random();
  double r = (double) (r2 >> 1);
  int jitter = (int) (((double) n->_jitter) * r / ((double) 0x7FffFFff));
  if (r2 & 1)
    jitter *= -1;
  n->_hello_timer.schedule_after_ms(n->_period + (int) jitter);
}


void
UpdateGridRoutes::send_routing_update(Vector<grid_nbr_entry> &rte_info,
				      bool update_seq)
{
  /* build and send routing update packet advertising the contents of
     the rte_info vector.  calling function must fill in each nbr
     entry */

  _num_updates_sent++;

  int num_rtes = rte_info.size();
  int psz = sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello);
  psz += sizeof(grid_nbr_entry) * num_rtes;

  WritablePacket *p = Packet::make(psz + 2); // for alignment
  if (p == 0) {
    click_chatter("in %s: cannot make packet!", id().cc());
    assert(0);
  } 
  ASSERT_ALIGNED(p->data());
  p->pull(2);
  memset(p->data(), 0, p->length());

  p->set_timestamp_anno(Timestamp::now());

  click_ether *eh = (click_ether *) p->data();
  memset(eh->ether_dhost, 0xff, 6); // broadcast
  eh->ether_type = htons(ETHERTYPE_GRID);
  memcpy(eh->ether_shost, _ethaddr.data(), 6);

  grid_hdr *gh = (grid_hdr *) (eh + 1);
  ASSERT_ALIGNED(gh);
  gh->hdr_len = sizeof(grid_hdr);
  gh->total_len = psz - sizeof(click_ether);
  gh->total_len = htons(gh->total_len);
  gh->type = grid_hdr::GRID_LR_HELLO;
  gh->ip = gh->tx_ip = _ipaddr.addr();
  grid_hello *hlo = (grid_hello *) (gh + 1);
  assert(num_rtes <= 255);
  hlo->num_nbrs = (unsigned char) num_rtes;
  hlo->nbr_entry_sz = sizeof(grid_nbr_entry);
  hlo->seq_no = htonl(_seq_no);

  // Update the sequence number for periodic updates, but not
  // for triggered updates.
  if (update_seq) {
    /* originating sequence numbers are even, starting at 0.  odd
       numbers are reserved for other nodes to advertise a broken route
       to us.  from DSDV paper. */
    _seq_no += 2;
  }
  
  hlo->age = htonl(grid_hello::MAX_AGE_DEFAULT);

  grid_nbr_entry *curr = (grid_nbr_entry *) (hlo + 1);
  for (int i = 0; i < num_rtes; i++) {
    *curr = rte_info[i];
    curr->seq_no = htonl(curr->seq_no);
    curr->age = htonl(curr->age);
    curr++;
  }

  output(1).push(p);
}

ELEMENT_REQUIRES(userlevel)
EXPORT_ELEMENT(UpdateGridRoutes)

#include <click/bighashmap.cc>
#include <click/vector.cc>
template class HashMap<IPAddress, UpdateGridRoutes::NbrEntry>;
template class HashMap<IPAddress, UpdateGridRoutes::far_entry>;
#if 0 // now included in the new DSDV implementation, gridroutetable.cc
template class Vector<IPAddress>;
#endif
template class Vector<grid_nbr_entry>;
CLICK_ENDDECLS