dsrroutetable.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

    // either this is a normal source-routed packet, or a RREP or RERR
    // with a source route header

    click_dsr_source *dsr_source = (click_dsr_source *)(dsr_option);
    assert(dsr_source->dsr_type == DSR_TYPE_SOURCE_ROUTE);

    unsigned char segments = dsr_source->dsr_segsleft;
    unsigned char source_hops = dsr_source->num_addrs();

    assert(segments <= source_hops);

    int index = source_hops - segments;

    if (segments == 0) { // this is the last hop
      IPAddress dst(ip->ip_dst.s_addr);
      return dst;
    } else {
      return dsr_source->addr[index-1].ip();
    }
  }

  assert(0);
  return IPAddress();
}

// returns ip of next hop on source route; split out from forward_sr
// so we can use it when generating route error messages.  offset is
// the offset of the source route option in this packet.
IPAddress
DSRRouteTable::next_sr_hop(Packet *p_in, unsigned int offset)
{
  assert(offset + sizeof(click_dsr_source) <= p_in->length());

  click_dsr_source *dsr_source = (click_dsr_source *)(p_in->data() +
						      offset);

  // click_chatter("type is %d\n", dsr_source->dsr_type);
  assert (dsr_source->dsr_type == DSR_TYPE_SOURCE_ROUTE);

  unsigned char segments = dsr_source->dsr_segsleft;
  unsigned char source_hops = dsr_source->num_addrs();

  // click_chatter("segments %02x, source_hops %02x\n", segments, source_hops);
  assert(segments <= source_hops);

  // this is the index of the address to which this packet should be forwarded
  int index = source_hops - segments;

  if (segments == 0) { // this is the last hop
    const click_ip *ip = p_in->ip_header();
    IPAddress final_dst(ip->ip_dst.s_addr);
    return final_dst;
  } else {
    return dsr_source->addr[index].ip();
  }
}

// offset is the offset of the source route option in this packet
void
DSRRouteTable::forward_sr(Packet *p_in, unsigned int offset, int port)
{
  if (offset > p_in->length()) {
    DEBUG_CHATTER(" * offset passed to forwardSRPacket is too big!  (%d > %d)\n",
		  offset, p_in->length());
    p_in->kill();
    return;
  }

  WritablePacket *p=p_in->uniqueify();

  click_dsr_source *dsr_source = (click_dsr_source *)(p->data() +
						      offset);

  if (dsr_source->dsr_type != DSR_TYPE_SOURCE_ROUTE) {
    DEBUG_CHATTER(" * source route option not found where expected in forward_sr\n");
    p->kill();
    return;
  }

  // after we forward it there will be (segsleft-1) hops left;
  dsr_source->dsr_segsleft--;
  p->set_dst_ip_anno(next_sr_hop(p, offset));

  DEBUG_CHATTER("forward_sr: forwarding to %s\n", next_sr_hop(p, offset).unparse().c_str());

  output(port).push(p);
  return;
}

// rebroadcast a route request.  we've already checked that we haven't
// seen this RREQ lately, and added the info to the forwarded_rreq_map.
void
DSRRouteTable::forward_rreq(Packet *p_in)
{
  click_dsr *orig_dsr = (click_dsr *)(p_in->data()+
				     sizeof(click_ip));
  click_dsr_rreq *orig_rreq = (click_dsr_rreq *)(p_in->data() +
						sizeof(click_ip) +
						sizeof(click_dsr));

  int hop_count = orig_rreq->num_addrs();

  assert(ntohs(orig_dsr->dsr_len) == (sizeof(click_dsr_rreq) +
				      hop_count * sizeof(DSRHop)));

  // add my address to the end of the packet
  WritablePacket *p=p_in->uniqueify();

  p = p->put(sizeof(DSRHop));

  click_ip *ip = reinterpret_cast<click_ip *>(p->data());
  click_dsr *dsr = (click_dsr *)(p->data()+
				 sizeof(click_ip));
  click_dsr_rreq *dsr_rreq = (click_dsr_rreq *)(p->data() +
						sizeof(click_ip) +
						sizeof(click_dsr));

  dsr_rreq->addr[hop_count]._ip.s_addr = me->addr();

  EtherAddress last_eth = last_forwarder_eth(p);
  dsr_rreq->addr[hop_count]._metric = get_metric(last_eth);

  dsr_rreq->dsr_len += sizeof(DSRHop);
  dsr->dsr_len = htons(ntohs(dsr->dsr_len)+sizeof(DSRHop));

  ip->ip_ttl--;
  ip->ip_len = htons(p->length());
  ip->ip_sum = 0;
  ip->ip_sum = click_in_cksum((unsigned char *)ip, sizeof(click_ip));

  p->set_dst_ip_anno(0xffffffff);

  output(1).push(p);
}

// build and send out a request for the ip
void
DSRRouteTable::issue_rreq(IPAddress dst, unsigned int ttl, bool unicast)
{
  // make a route request packet with room for gratuitious route repair rerrs

  // XXX what does the above mean?  route repair rerrs??

  unsigned payload = (sizeof(click_ip)+
		      sizeof(click_dsr)+
		      sizeof(click_dsr_rreq));
  WritablePacket *p = Packet::make(payload);

  // get header pointers
  click_ip *ip = reinterpret_cast<click_ip *>(p->data());
  click_dsr *dsr = (click_dsr*)(p->data() + sizeof(click_ip));
  click_dsr_rreq *dsr_rreq = (click_dsr_rreq*)(p->data() +
					       sizeof(click_ip) +
					       sizeof(click_dsr));

  ip->ip_v = 4;
  ip->ip_hl = sizeof(click_ip) >> 2;
  ip->ip_len = htons(p->length());
  ip->ip_id = htons(_rreq_id); // XXX eh?  why this?
  ip->ip_p = IP_PROTO_DSR;
  ip->ip_src.s_addr = me->addr();
  if (unicast)
    ip->ip_dst.s_addr = dst.addr();
  else
    ip->ip_dst.s_addr = 0xffffffff;
  ip->ip_tos = 0;
  ip->ip_off = 0;
  ip->ip_ttl = ttl;
  ip->ip_sum = 0;
  ip->ip_sum = click_in_cksum((unsigned char *)ip, sizeof(click_ip));

  dsr->dsr_next_header = 0;
  dsr->dsr_len = htons(sizeof(click_dsr_rreq));
  dsr->dsr_reserved = 0;
  dsr_rreq->dsr_type = DSR_TYPE_RREQ;
  dsr_rreq->dsr_len = 6;
  dsr_rreq->dsr_id = htons(_rreq_id);
  dsr_rreq->target.s_addr = dst.addr();

  p->set_dst_ip_anno(ip->ip_dst.s_addr);

  _rreq_id++;

  output(1).push(p);
}

// start issuing requests for a host.
void
DSRRouteTable::start_issuing_request(IPAddress host)
{
  // check to see if we're already querying for this host
  InitiatedReq *r = _initiated_rreq_map.findp(host);

  if (r) {
    DEBUG_CHATTER(" * start_issuing_request:  already issuing requests for %s\n", host.unparse().c_str());
    return;
  } else {
    // send out the initial request and add an entry to the table
    InitiatedReq new_rreq(host);
    _initiated_rreq_map.insert(host, new_rreq);
    issue_rreq(host, DSR_RREQ_TTL1, false);
    return;
  }
}
// we've received a route reply.  remove the cooresponding entry from
// route request table, so we don't send out more requests
void
DSRRouteTable::stop_issuing_request(IPAddress host)
{
  InitiatedReq *r = _initiated_rreq_map.findp(host);
  if (!r) {
    DEBUG_CHATTER(" * stop_issuing_request:  no entry in request table for %s\n", host.unparse().c_str());
    return;
  } else {
    _initiated_rreq_map.remove(host);
    return;
  }
}
void
DSRRouteTable::static_rreq_issue_hook(Timer *, void *v)
{
  DSRRouteTable *r = (DSRRouteTable *)v;
  r->rreq_issue_hook();
}
void
DSRRouteTable::rreq_issue_hook()
{
  // look through the initiated rreqs and check if it's time to send
  // anything out
  Timestamp curr_time = Timestamp::now();

  // DEBUG_CHATTER("checking issued rreq table\n");

  Vector<IPAddress> remove_list;

  for (InitReqIter i = _initiated_rreq_map.begin(); i.live(); i++) {

    InitiatedReq &ir = i.value();
    assert(ir._target == i.key());

    // we could find out a route by some other means than a direct
    // RREP.  if this is the case, stop issuing requests.
    _link_table->dijkstra(false);
    Vector<IPAddress> route = _link_table->best_route(ir._target,false);
    if (route.size() > 1) { // we have a route
      remove_list.push_back(ir._target);
      continue;
    } else {
      if (diff_in_ms(curr_time, ir._time_last_issued) > ir._backoff_interval) {

	DEBUG_CHATTER("time to issue new request for host %s\n", ir._target.unparse().c_str());

	if (ir._times_issued == 1) {
	  // if this is the second request
	  ir._backoff_interval = DSR_RREQ_DELAY2;
	} else {
	  ir._backoff_interval *= DSR_RREQ_BACKOFF_FACTOR;
	  // i don't think there's any mention in the spec of a limit on
	  // the backoff, but this MAX_DELAY seems reasonable
	  if (ir._backoff_interval > DSR_RREQ_MAX_DELAY)
	    ir._backoff_interval = DSR_RREQ_MAX_DELAY;
	}
	ir._times_issued++;
	ir._time_last_issued = curr_time;
	ir._ttl = DSR_RREQ_TTL2;

	issue_rreq(ir._target, ir._ttl, false);
      }
    }
  }

  for (int j = 0 ; j < remove_list.size() ; j++) {
    _initiated_rreq_map.remove(remove_list[j]);
  }

  _rreq_issue_timer.schedule_after_msec(DSR_RREQ_ISSUE_TIMER_INTERVAL);

  check();
}


// random helper functions

DSRRoute
DSRRouteTable::reverse_route(DSRRoute r)
{
 DSRRoute rev;
 for(int i=r.size()-1; i>=0; i--) {
   rev.push_back(r[i]);
 }
 return rev;
}

DSRRoute
DSRRouteTable::truncate_route(DSRRoute r, IPAddress ip)
{
 DSRRoute t;
 for (int i=0; i < r.size(); i++) {
   t.push_back(r[i]);
   if (r[i].ip() == ip) {
     return t;
   }
 }
 return DSRRoute();
}

int
DSRRouteTable::route_index_of(DSRRoute r, IPAddress ip)
{
 for (int i=0; i<r.size(); i++) {
   if (r[i].ip() == ip)
     return i;
 }
 return -1;
}

void
DSRRouteTable::add_route_to_link_table(DSRRoute route)
{
  for (int i=0; i < route.size() - 1; i++) {
    IPAddress ip1 = route[i].ip();
    IPAddress ip2 = route[i+1].ip();

    // ETX:
    unsigned char metric = route[i+1]._metric;
    if (metric == DSR_INVALID_HOP_METRIC)
      _link_table->update_both_links(ip1, ip2, 0, 0, 9999);
    else
      _link_table->update_both_links(ip1, ip2, 0, 0, metric);

    // DEBUG_CHATTER("_link_table->update_link %s %s %d\n",
    //               route[i].unparse().c_str(), route[i+1].s().c_str(), metric);
  }
}

int
DSRRouteTable::check_blacklist(IPAddress ip)
{
  if (!_use_blacklist) return DSR_BLACKLIST_NOENTRY;

  BlacklistEntry *e = _blacklist.findp(ip);
  if (! e) {
    return DSR_BLACKLIST_NOENTRY;
  } else {
    return e->_status;
  }
}

void
DSRRouteTable::set_blacklist(IPAddress ip, int s)
{
  //  DEBUG_CHATTER ("set blacklist: %s %d\n", ip.unparse().c_str(), s);
  //  DEBUG_CHATTER ("set blacklist: %d\n", check_blacklist(ip));

  _blacklist.remove(ip);
  if (s != DSR_BLACKLIST_NOENTRY) {
    BlacklistEntry e;
    e._time_updated.set_now();
    e._status = s;
    _blacklist.insert(ip, e);
  }

  //  DEBUG_CHATTER ("set blacklist: %d\n", check_blacklist(ip));
}

unsigned long
DSRRouteTable::diff_in_ms(const Timestamp &t1, const Timestamp &t2)
{
    Timestamp diff = t1 - t2;
    assert(diff.sec() < (Timestamp::seconds_type) ((1 << 31) / 1000));
    return diff.msecval();
}

// Ask LinkStat for the metric for the link from other to us.
// ripped off from srcr.cc
unsigned char
DSRRouteTable::get_metric(EtherAddress other)
{
#if 0
  unsigned char dft = DSR_INVALID_HOP_METRIC; // default metric
  if (_ls){
    unsigned int tau;
    Timestamp tv;
    unsigned int frate, rrate;
    bool res = _ls->get_forward_rate(other, &frate, &tau, &tv);
    if(res == false) {
      return dft;
    }
    res = _ls->get_reverse_rate(other, &rrate, &tau);
    if (res == false) {
      return dft;
    }
    if (frate == 0 || rrate == 0) {
      return dft;
    }

    // rate is 100 * recv %
    // m = 10 x 1/(fwd% x rev%)
    u_short m = 10 * 100 * 100 / (frate * (int) rrate);

    if (m > DSR_INVALID_HOP_METRIC) {
      click_chatter("DSRRouteTable::get_metric: metric too big for one byte?\n");
      return DSR_INVALID_HOP_METRIC;
    }

    return (unsigned char)m;
  }
#endif
  if (_metric) {
    GridGenericMetric::metric_t m = _metric->get_link_metric(other, false);
    unsigned char c = _metric->scale_to_char(m);
    if (!m.good() || c >= DSR_INVALID_HOP_METRIC)
      return DSR_INVALID_HOP_METRIC;
    return c;
  }
  else {
    // default to hop-count, all links have a hop-count of 1
    return 1;
  }
}

bool
DSRRouteTable::metric_preferable(unsigned short a, unsigned short b)
{
  if (!_metric)
    return (a < b); // fallback to minimum hop-count
  else if (a == DSR_INVALID_ROUTE_METRIC || b == DSR_INVALID_ROUTE_METRIC)
    return a; // make arbitrary choice
  else
    return _metric->metric_val_lt(_metric->unscale_from_char(a),
				  _metric->unscale_from_char(b));
}

unsigned short
DSRRouteTable::route_metric(DSRRoute r)
{
#if 0
  unsigned short ret = 0;
  // the metric in r[i+1] represents the link between r[i] and r[i+1],
  // so we start at 1
  for (int i = 1; i < r.size(); i++) {
    if (r[i]._metric == DSR_INVALID_HOP_METRIC)
      return DSR_INVALID_ROUTE_METRIC;
    ret += r[i]._metric;
  }
  return ret;
#endif

  if (r.size() < 2) {
    click_chatter("DSRRouteTable::route_metric: route is too short, less than two nodes?\n");
    return DSR_INVALID_ROUTE_METRIC;
  }
  if (!_metric)
    return r.size(); // fallback to hop-count

  if (r[1]._metric == DSR_INVALID_HOP_METRIC)
    return DSR_INVALID_ROUTE_METRIC;
  GridGenericMetric::metric_t m(_metric->unscale_from_char(r[1]._metric));

  for (int i = 2; i < r.size(); i++) {
     if (r[i]._metric == DSR_INVALID_HOP_METRIC)
      return DSR_INVALID_ROUTE_METRIC;
     m = _metric->append_metric(m, _metric->unscale_from_char(r[i]._metric));
  }
  if (m.good())
    return _metric->scale_to_char(m);
  else
    return DSR_INVALID_ROUTE_METRIC;
}

EtherAddress
DSRRouteTable::last_forwarder_eth(Packet *p)
{
  uint16_t d[3];
  d[0] = DSR_LAST_HOP_ETH_ANNO1(p);
  d[1] = DSR_LAST_HOP_ETH_ANNO2(p);
  d[2] = DSR_LAST_HOP_ETH_ANNO3(p);

  return (EtherAddress((unsigned char *)d));
}

ELEMENT_REQUIRES(LinkTable)
EXPORT_ELEMENT(DSRRouteTable)
CLICK_ENDDECLS