dsrroutetable.cc

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

								    sizeof(click_ip) + 
								    sizeof(click_dsr));

    if (dsr_option->dsr_type == DSR_TYPE_RREQ) {
      
      const click_dsr_rreq *dsr_rreq = (const click_dsr_rreq *)(p_in->data() + 
								sizeof(click_ip) + 
								sizeof(click_dsr));
      unsigned src = ip->ip_src.s_addr;
      IPAddress src_addr(src);
      IPAddress dst_addr(dsr_rreq->target.s_addr);

      DEBUG_CHATTER(" * DSR (%s): got route request for destination %s\n", 
		    this->id().cc(),
		    dst_addr.s().cc());

      // add the info from the RREQ to the linkcache
      DSRRoute request_route = extract_request_route(p_in);

      // ETX: get the metric for the last hop
      EtherAddress last_eth = last_forwarder_eth(p_in);
      request_route.push_back(DSRHop(*me, get_metric(last_eth)));
      
      for (int j=0; j<request_route.size(); j++)
	  DEBUG_CHATTER(" - %d   %s (%d)\n",
			j, request_route[j].ip().s().cc(),
			request_route[j]._metric);

      add_route_to_link_table(request_route);

      if (*me==src_addr) {
	DEBUG_CHATTER(" * I sourced this RREQ; ignore.\n");
	p_in->kill();
	return;
      } else if (*me==dst_addr) {  
	
	// this RREQ is for me, so generate a reply.
	DSRRoute reply_route = reverse_route(request_route);

	DEBUG_CHATTER(" * Generating route reply with source route:\n");
	for (int j=0; j<reply_route.size(); j++)
	  DEBUG_CHATTER(" - %d   %s (%d)\n",
			j, reply_route[j].ip().s().cc(),
			reply_route[j]._metric);
	
	issue_rrep(dst_addr, src_addr, request_route, reply_route);
	p_in->kill(); // kill the original RREQ
	
	return;
	
      } else {
	
	// this RREQ is not for me.  decide whether to forward it or just kill it.
	// reply from cache would also go here.

	if (ip->ip_ttl == 1) {
	  DEBUG_CHATTER(" * time to live expired; killing packet\n");
	  p_in->kill();
	  return;
	} // ttl is decremented in forward_rreq
	
	if (route_index_of(request_route, *me) != request_route.size()-1) {
	  // I'm in the route somewhere other than at the end (note
	  // that above, I appended myself)
	  DEBUG_CHATTER(" * I'm already listed; killing packet\n");
	  p_in->kill();
	  return;
	}

	// check to see if we've seen this request lately, or if this
	// one is better
	ForwardedReqKey frk(src_addr, dst_addr, ntohs(dsr_rreq->dsr_id));
	ForwardedReqVal *old_frv = _forwarded_rreq_map.findp(frk);
	
	// ETX:
	unsigned short this_metric = route_metric(request_route);
	if (old_frv) {
	  DEBUG_CHATTER(" * already forwarded this route request (%d, %d)\n", 
			this_metric, old_frv->best_metric);
	  if (metric_preferable(this_metric, old_frv->best_metric))
	    DEBUG_CHATTER(" * but this one is better\n");
	  else
	    DEBUG_CHATTER(" * and this one's not as good\n");
	}
	
	if (old_frv && ! metric_preferable(this_metric, old_frv->best_metric)) { 
	  DEBUG_CHATTER(" * already forwarded this route request\n");

	  p_in->kill();
	  return;
	} else {

	  // we have not seen this request before, or this one is
	  // 'better'; before we do the actual forward, check
	  // blacklist for the node from which we are receiving this.

	  ForwardedReqVal new_frv; // new entry for _forwarded_rreq_map

	  struct timeval current_time;
	  click_gettimeofday(&current_time);
	  new_frv._time_forwarded = current_time;

	  IPAddress last_forwarder = IPAddress(DSR_LAST_HOP_IP_ANNO(p_in));
	  // or:
	  //	  IPAddress last_forwarder = request_route[request_route.size()-2];

	  // click_chatter ("last_forwarder is %s\n", last_forwarder.s().cc());

	  int status = check_blacklist(last_forwarder);

	  if (status == DSR_BLACKLIST_UNI_PROBABLE) {
	    DEBUG_CHATTER(" * request came over a unidirectional link; killing\n");
	    p_in->kill();
	    return;
	  } else if (status == DSR_BLACKLIST_UNI_QUESTIONABLE) {
	    
	    if (old_frv) {
	      // if we're here, then we've already forwarded this
	      // request, but this one is better.  however, we need to
	      // issue a unidirectionality test for this link.

	      // XXX this is incorrect behavior: we don't bother with
	      // the unidirectionality test
	      DEBUG_CHATTER(" * link may be unidirectional but unidirectionality test is already issued;\n");
	      DEBUG_CHATTER(" * dropping this packet instead...\n");
	      p_in->kill();
	      return;
	    }

	    DEBUG_CHATTER(" * link may be unidirectional; sending out 1-hop RREQ\n");
	    
	    // send unicast route request with TTL of 1
	    issue_rreq(last_forwarder, 1, true);
	    new_frv.p = p_in;
	    new_frv._time_unidtest_issued = current_time;
	    
	    // while we're waiting for the test result, don't update the metric
	    // if (old_frv)
	    //   new_frv.best_metric = old_frv->best_metric;
	    // else 
	    new_frv.best_metric = DSR_INVALID_ROUTE_METRIC;

	    _forwarded_rreq_map.insert(frk, new_frv);
	    return;

	  } else {

	    if (old_frv && old_frv->p) {
	      // if we're here, then we've already forwarded this
	      // request, but this one is better and we want to
	      // forward it.  however, we've got a pending
	      // unidirectionality test for this RREQ.

	      // what we should do is maintain a list of packet *'s
	      // that we've issued tests for.

	      // XXX instead, we just give up on the potentially
	      // asymmetric link.  whether or not the test comes back,
	      // things should be ok.  nonetheless this is incorrect
	      // behavior.
	      old_frv->p->kill();
	      old_frv->p = NULL;
	    }
	    
	    DEBUG_CHATTER(" * forwarding this RREQ\n");
	    new_frv.p = NULL;
	    new_frv.best_metric = this_metric;
	    _forwarded_rreq_map.insert(frk, new_frv);
	    forward_rreq(p_in);
	    
	    return; 

	  }
	}
      }

    } else if (dsr_option->dsr_type == DSR_TYPE_RREP) {
      
      // process an incoming route request.  if it's for us, issue a reply.
      // if not, check for an entry in the request table, and insert one and
      // forward the request if there is not one.
      
      IPAddress dst_addr(ip->ip_dst.s_addr);

      // extract the reply route..  convert to node IDs and add to the
      // link cache
      DSRRoute reply_route = extract_reply_route(p_in);

      // XXX really, is this necessary?  or are we only potentially
      // making the link data more stale, while marking it as current?
      add_route_to_link_table(reply_route);
      
      DEBUG_CHATTER(" * DSR (%s): received route reply with reply route:\n",
		    this->id().cc());
      for (int i=0; i<reply_route.size(); i++)
	DEBUG_CHATTER(" - %d  %s (%d)\n",
		      i,
		      reply_route[i].ip().s().cc(),
		      reply_route[i]._metric);

      // now check for packets in the sendbuffer whose destination has
      // been found using the information from the route reply
      _sendbuffer_check_routes = true;
      _sendbuffer_timer.schedule_now();

      // remove the last forwarder from the blacklist, if present
      IPAddress last_forwarder = IPAddress(DSR_LAST_HOP_IP_ANNO(p_in));
      // click_chatter ("last_forwarder is %s\n", last_forwarder.s().cc());

	// last_sr_hop(p_in, 
	// (sizeof(click_ip)+
	//  sizeof(click_dsr)+
	//  sizeof(click_dsr_rrep)+
	//  sizeof(in_addr) * (reply_route.size()-1)));
      set_blacklist(last_forwarder, DSR_BLACKLIST_NOENTRY);

      if (dst_addr==*me) {
	// the first address listed in the route reply's route must be
	// the destination which we queried; this is not necessarily
	// the same as the destination in the IP header because we
	// might be doing reply-from-cache	
	IPAddress reply_dst = reply_route[reply_route.size()-1].ip();
	DEBUG_CHATTER(" * killed (route to %s reached final destination, %s)\n", 
		      reply_dst.s().cc(), dst_addr.s().cc());
	stop_issuing_request(reply_dst);
	p_in->kill();
	return;
      } else {
	DEBUG_CHATTER(" * forwarding towards destination %s\n", dst_addr.s().cc());
	forward_rrep(p_in); // determines next hop, sets dest ip anno, and then pushes out to arp table.
	return;
      }

    } else if (dsr_option->dsr_type == DSR_TYPE_RERR) {

      DEBUG_CHATTER(" * DSR (%s): got route error packet\n",
		    this->id().cc());
 
      // get a pointer to the route error header
      const click_dsr_rerr *dsr_rerr = (click_dsr_rerr *)dsr_option;
      
      assert(dsr_rerr->dsr_error == DSR_RERR_TYPE_NODE_UNREACHABLE); // only handled type right now
      
      const in_addr *unreachable_addr = (in_addr *)((char *)dsr_rerr + sizeof(click_dsr_rerr));
      
      // get the bad hops
      IPAddress err_src(dsr_rerr->dsr_err_src);
      IPAddress err_dst(dsr_rerr->dsr_err_dst);
      IPAddress unreachable(unreachable_addr->s_addr);
      
      // now remove the entries from the linkcache
      DEBUG_CHATTER(" - removing link from %s to %s; rerr destination is %s\n", 
		    err_src.s().cc(), unreachable.s().cc(), err_dst.s().cc());
      
      // XXX DSR_INVALID_HOP_METRIC isn't really an appropriate name here
      _link_table->update_both_links(err_src, unreachable, 0, 0, DSR_INVALID_ROUTE_METRIC);

      if (err_dst == *me) {
	DEBUG_CHATTER(" * killed (reached final destination)\n");
	p_in->kill();
      } else {
	forward_rerr(p_in);
      }

      // find packets with this link in their source route and yank
      // them out of our outgoing queue
      if (_outq) {
	Vector<Packet *> y;
	_outq->yank(link_filter(err_src, unreachable), y);
	DEBUG_CHATTER("yanked %d packets; killing...\n", y.size());
	for (int i = 0; i < y.size(); i++)
	  y[i]->kill();
      }
      
      return;

    } else if (dsr_option->dsr_type == DSR_TYPE_SOURCE_ROUTE) {

      // this is a source-routed data packet

      unsigned ip_dst = ip->ip_dst.s_addr;
      IPAddress dst_addr(ip_dst);

      DEBUG_CHATTER(" * DSR (%s): incoming data pkt for %s; dsr_type is %d\n", 
		    this->id().cc(),
		    dst_addr.s().cc(), dsr_option->dsr_type);

      // remove the last forwarder from the blacklist, if present
      IPAddress last_forwarder = IPAddress(DSR_LAST_HOP_IP_ANNO(p_in));
	                        //  last_sr_hop(p_in, 
				//	        sizeof(click_ip)+sizeof(click_dsr));
      set_blacklist(last_forwarder, DSR_BLACKLIST_NOENTRY);
      // click_chatter ("last_forwarder is %s\n", last_forwarder.s().cc());
      
      if (dst_addr == *me) {
	Packet *p = strip_headers(p_in);
	// out to the kernel
	output(0).push(p);
	return;
      } else {
	// DEBUG_CHATTER("need to forward\n",dst_addr.s().cc());
	
	// determines next hop, sets dest ip anno, and then pushes out to arp table.
	forward_data(p_in);
	return;
      }
    } else {
      DEBUG_CHATTER("unexpected packet type %d\n", dsr_option->dsr_type);
      p_in->kill();
      return;
    }
  } else if (port == 2) {

    // source-routed packet whose transmission to the next hop failed
    
    // XXXXX is the IP dest annotation necessarily set here??
    
    IPAddress bad_src = *me;
    const click_dsr_option *dsr_option = (const click_dsr_option *)(p_in->data() + 
								    sizeof(click_ip) + 
								    sizeof(click_dsr));

    unsigned int offset = sizeof(click_ip) + sizeof(click_dsr);
    IPAddress bad_dst;
	
    if (dsr_option->dsr_type == DSR_TYPE_RREQ) {
      // if this is a RREQ, then it must be a one-hop
      // unidirectionality test, originated by me, because no other
      // RREQs are unicast.
      const click_dsr_rreq *dsr_rreq = (const click_dsr_rreq *)dsr_option;
      bad_dst = IPAddress(dsr_rreq->target);
    } else {
      if (dsr_option->dsr_type == DSR_TYPE_RREP) {
	const click_dsr_rrep *dsr_rrep = (const click_dsr_rrep *)dsr_option;
	int hop_count = dsr_rrep->num_addrs();
	// DEBUG_CHATTER ("hop count is %d\n", hop_count);
	offset += sizeof(click_dsr_rrep) + hop_count * sizeof(DSRHop);
      } else if (dsr_option->dsr_type == DSR_TYPE_RERR) {
	const click_dsr_rerr *dsr_rerr = (const click_dsr_rerr *)dsr_option;
	assert(dsr_rerr->dsr_error == DSR_RERR_TYPE_NODE_UNREACHABLE); // only supported error now
	offset += sizeof(click_dsr_rerr) + sizeof(in_addr);
      }
      bad_dst = next_sr_hop(p_in, offset);
    }

    DEBUG_CHATTER(" * packet had bad source route with next hop %s\n", 
		  bad_dst.s().cc());
    
    if (dsr_option->dsr_type == DSR_TYPE_RREP) {
      DEBUG_CHATTER(" * tx error sending route reply; adding entry to blacklist for %s\n", 
		    bad_dst.s().cc());
      set_blacklist(bad_dst, DSR_BLACKLIST_UNI_PROBABLE);
    } else if (dsr_option->dsr_type == DSR_TYPE_RREQ) {
      // XXX are we only supposed to set this for failed RREPs?
      DEBUG_CHATTER(" * one-hop unicast RREQ failed\n");
      set_blacklist(bad_dst, DSR_BLACKLIST_UNI_PROBABLE);
    }

    _link_table->update_both_links(bad_src, bad_dst, 0, 0, DSR_INVALID_ROUTE_METRIC);

    const click_ip *ip = p_in->ip_header();
    unsigned src = ip->ip_src.s_addr;
    IPAddress src_addr(src);
    
    // if I generated the packet, then there is no need to send a route error
    if (src_addr == *me) {
      //      click_chatter(" * i was the source; killing\n");

      p_in->kill();
      return;
    } else { 
      // need to send a route error
      DSRRoute source_route, trunc_route, rev_route;

      // send RERR back along its original source route
      source_route = extract_source_route(p_in, offset);
      
      trunc_route = truncate_route(source_route, *me);
      if (! trunc_route.size()) {
	// this would suggest something is very broken
	DEBUG_CHATTER("couldn't find my address in bad source route!\n");
	return;
      }

      rev_route = reverse_route(trunc_route);
      issue_rerr(bad_src, bad_dst, src_addr, rev_route);

      // find packets with this link in their source route and yank
      // them out of our outgoing queue
      if (_outq) {
	Vector<Packet *> y;
	_outq->yank(link_filter(bad_src, bad_dst), y);
	DEBUG_CHATTER("yanked %d packets; killing...\n", y.size());
	for (int i = 0; i < y.size(); i++)
	  y[i]->kill();
      }

      //   // salvage the packet?
      //   if (dsr_option->dsr_type == DSR_TYPE_RREP) {
      //   	// we don't salvage replies
      //   	p_in->kill();
      //   	return;
      //   } else if (dsr_option->dsr_type == DSR_TYPE_RREQ) {
      //   	// unicast route request must be from me... this case should
      //   	// never happen.
      //   	assert(0);
      //   	return;
      //   } else if (dsr_option->dsr_type == DSR_TYPE_RERR) {
      //   	// ah, i don't know.  this is complicated.  XXX
      //   } else if (dsr_option->dsr_type == DSR_TYPE_SOURCE_ROUTE) {
      //   	salvage(p_in);
      //   	return;
      //   }

      p_in->kill();
      return;
      
    }
  }
  assert(0);
}

Packet *
DSRRouteTable::add_dsr_header(Packet *p_in, Vector<IPAddress> source_route)
{
  int old_len = p_in->length();
  int payload;
  int i;

  // the source and destination addresses are not included
  // as hops in the source route
  assert(source_route.size() >= 2);
  int hop_count = source_route.size() - 2;
  
  payload = (sizeof(click_dsr) + 
	     sizeof(click_dsr_source) + 
	     hop_count * sizeof(DSRHop));

  DEBUG_CHATTER(" * creating DSR source-routed packet\n");
  
  // save the IP header
  click_ip *ip = (click_ip *)(p_in->data());
  click_ip old_ip;
  memcpy(&old_ip, ip, sizeof(click_ip));   //copy the old header
  
  // add the extra header size and get a new packet
  WritablePacket *p = p_in->push(payload);
  if (!p) {
    click_chatter("couldn't add space for new DSR header\n");
    return p;
  }

  ip = (click_ip *)(p->data());  
  memcpy(ip, &old_ip, sizeof(click_ip)); 
  
  // add the fixed header
  click_dsr *dsr = (click_dsr *)(p->data() + sizeof(click_ip));
  
  dsr->dsr_next_header = ip->ip_p; // save IP protocol type
  ip->ip_p = IP_PROTO_DSR; // set new protocol type to DSR
  dsr->dsr_len = htons(payload - sizeof(click_dsr));
  dsr->dsr_reserved = 0;
  
  DEBUG_CHATTER(" * add_dsr_header: new packet size is %d, old was %d \n", p->length(), old_len);
  
  // there's not really much mention of TTL in the IETF draft (other
  // than in the case of RREQs), I suppose it's sort of implicitly the
  // length of the source route.  so right now we're not checking OR
  // decrementing the TTL when forwarding (again, except in the case
  // of RREQs).
  //
  ip->ip_ttl = 255;

  ip->ip_len = htons(p->length());
  ip->ip_dst.s_addr = (unsigned)p->dst_ip_anno(); // XXX not sure I understand why we need to reset this
  ip->ip_sum = 0;
  ip->ip_sum = click_in_cksum((unsigned char *)ip, sizeof(click_ip));
  
  p->set_ip_header(ip, sizeof(click_ip));
  
  // add the source option
  click_dsr_source *dsr_source=(click_dsr_source *)(p->data()+sizeof(click_ip)+sizeof(click_dsr));
  
  dsr_source->dsr_type = DSR_TYPE_SOURCE_ROUTE;
  dsr_source->dsr_len = sizeof(DSRHop) * hop_count + 2;
  dsr_source->dsr_segsleft = hop_count;

  for (i=0; i<hop_count; i++) {
    dsr_source->addr[i]._ip.s_addr = source_route[i+1].addr();
    dsr_source->addr[i]._metric = 0; // to be filled in along the way
  }
  
  // set the ip dest annotation to the next hop
  p->set_dst_ip_anno(source_route[1].addr());   
  
  DEBUG_CHATTER(" * added source route header");