dsragent.cc

CBRP协议（移动adhoc中基于分簇的路由协议）ns2下的源码

    }
  else if (Scheduler::instance().clock() - g->t < grat_hold_down_time) return;
  g->t = Scheduler::instance().clock();

  SRPacket p_copy = p;
  p_copy.pkt = allocpkt();
  p_copy.dest = p.route[0];   // tell the originator of this long source route
  p_copy.src = net_id;

  // reverse the route to get the packet back
  p_copy.route[p_copy.route.index()] = net_id;
  p_copy.route.reverseInPlace();
  p_copy.route.removeSection(0,p_copy.route.index());

  hdr_ip *new_iph =  (hdr_ip*)p_copy.pkt->access(off_ip_);
  new_iph->dst() = p_copy.dest.addr;
  new_iph->dport() = RT_PORT;
  new_iph->src() = p_copy.src.addr;
  new_iph->sport() = RT_PORT;
  new_iph->ttl() = 255;

  // shorten's p's route
  p.route.removeSection(heard_at, xmit_at);
  hdr_sr *new_srh =  (hdr_sr*)p_copy.pkt->access(off_sr_);
  new_srh->init();
  for (int i = 0 ; i < p.route.length() ; i++)
    p.route[i].fillSRAddr(new_srh->reply_addrs()[i]);
  new_srh->route_reply_len() = p.route.length();
  new_srh->route_reply() = 1;
  // grat replies will have a 0 seq num (it's only for trace analysis anyway)
  new_srh->rtreq_seq() = 0;

  hdr_cmn *new_cmnh =  (hdr_cmn*)p_copy.pkt->access(off_cmn_);
  new_cmnh->ptype() = PT_DSR;
  new_cmnh->size() += IP_HDR_LEN;

  trace("SRR %.9f _%s_ gratuitous-reply-sent %s -> %s (len %d) %s",
	Scheduler::instance().clock(), net_id.dump(),
	p_copy.src.dump(), p_copy.dest.dump(), p.route.length(), 
	p.route.dump());

  // cache the route for future use (we learned the route from p)
  route_cache->addRoute(p_copy.route, Scheduler::instance().clock(), p.src);
  sendOutPacketWithRoute(p_copy, true);
}

/*==============================================================
  debug and trace output
------------------------------------------------------------*/
void
DSRAgent::trace(char* fmt, ...)
{
  va_list ap;
  
  if (!logtarget) return;

  va_start(ap, fmt);
  vsprintf(logtarget->buffer(), fmt, ap);
  logtarget->dump();
  va_end(ap);
}


/*==============================================================
  Callback for link layer transmission failures
------------------------------------------------------------*/
struct filterfailuredata {
  nsaddr_t dead_next_hop;
  int off_cmn_;
  DSRAgent *agent;
};

int
FilterFailure(Packet *p, void *data)
{
  struct filterfailuredata *ffd = (filterfailuredata *) data;
  hdr_cmn *cmh = (hdr_cmn*)p->access(ffd->off_cmn_);
  int remove = cmh->next_hop() == ffd->dead_next_hop;
  if (remove) ffd->agent->undeliverablePkt(p,1);
  return remove;
}

void
DSRAgent::undeliverablePkt(Packet *pkt, int mine)
  /* when we've got a packet we can't deliver, what to do with it? 
     frees or hands off p if mine = 1, doesn't hurt it otherwise */
{
  hdr_sr *srh =  (hdr_sr*)pkt->access(off_sr_);
  hdr_ip *iph = (hdr_ip*)pkt->access(off_ip_);
  hdr_cmn *cmh;

  SRPacket p(pkt,srh);
  p.dest = ID(iph->dst(),::IP);
  p.src = ID(iph->src(),::IP);
  p.pkt = mine ? pkt : pkt->copy();

  srh =  (hdr_sr*)p.pkt->access(off_sr_);
  iph = (hdr_ip*)p.pkt->access(off_ip_);
  cmh = (hdr_cmn*)p.pkt->access(off_cmn_);

  if (ID(iph->src(),::IP) == net_id)
    { // it's our packet we couldn't send
      cmh->size() -= srh->size(); // remove SR header
      assert(cmh->size() >= 0);

      handlePktWithoutSR(p, false);
    }
  else 
    { // it's a packet we're forwarding for someone, save it if we can...
      Path salvage_route;
      
      if (dsragent_salvage_with_cache
	  && route_cache->findRoute(p.dest, salvage_route, 0))
	{ // be nice and send the packet out
#if 0
	  /* we'd like to create a ``proper'' source route with the
	     IP src of the packet as the first node, but we can't actually 
	     just append the salvage route onto the route used so far, 
	     since the append creates routes with loops in them 
	     like  1 2 3 4 3 5 
	     If we were to squish the route to remove the loop, then we'd be
	     removing ourselves from the route, which is verboten.
	     If we did remove ourselves, and our salvage route contained
	     a stale link, we might never hear the route error.
	     -dam 5/13/98

	     Could we perhaps allow SRs with loops in them on the air?
	     Since it's still a finite length SR, the pkt can't loop
	     forever... -dam 8/5/98 */

	  // truncate the route at the bad link and append good bit
	  int our_index = p.route.index();
	  p.route.setLength(our_index); // yes this cuts us off the route,
	  p.route.appendPath(salvage_route); // but we're at the front of s_r
	  p.route.setIterator(our_index);
#else
	  p.route = salvage_route;
	  p.route.resetIterator();
#endif

	  if (dsragent_dont_salvage_bad_replies && srh->route_reply()) 
	    { // check to see if we'd be salvaging a packet with the
	      // dead link in it
	      ID to_id(srh->addrs[srh->cur_addr()+1].addr,
		       (ID_Type) srh->addrs[srh->cur_addr()].addr_type);
	      bool bad_reply = false;

	      for (int i = 0 ; i < srh->route_reply_len()-1 ; i++)
		{
		  if (net_id == ID(srh->reply_addrs()[i])
		      && to_id == ID(srh->reply_addrs()[i+1])
		      || (dsragent_require_bi_routes
			  && to_id == ID(srh->reply_addrs()[i])
			  && net_id == ID(srh->reply_addrs()[i+1])))
		    {
		      bad_reply = true;
		      break;
		    }
		}
	      if (bad_reply)
		{ // think about killing this packet
		  srh->route_reply() = 0;
		  if (PT_DSR == cmh->ptype() && !srh->route_request() &&
		      !srh->route_error())
		    { // this packet has no reason to live
		      trace("SRR %.5f _%s_ --- %d dropping bad-reply %s -> %s", 
			    Scheduler::instance().clock(), net_id.dump(), 
			    cmh->uid(), p.src.dump(), p.dest.dump());
		      if (mine) drop(pkt, DROP_RTR_MAC_CALLBACK);
		      return;
		    }
		}
	      
	    }

	  trace("Ssalv %.5f _%s_ salvaging %s -> %s --- %d with %s",
		Scheduler::instance().clock(), net_id.dump(),
		p.src.dump(), p.dest.dump(), cmh->uid(), p.route.dump());

	  sendOutPacketWithRoute(p, false);
	}
      else
	{ // we don't have a route, and it's not worth us doing a
	  // route request to try to help the originator out, since
	  // it might be counter productive
	  trace("Ssalv %.5f _%s_ dropping --- %d %s -> %s", 
		Scheduler::instance().clock(), 
		net_id.dump(), cmh->uid(), p.src.dump(), p.dest.dump());
	  if (mine) drop(pkt, DROP_RTR_NO_ROUTE);
	}
    }
}

#ifdef USE_GOD_FEEDBACK
static int linkerr_is_wrong = 0;
#endif

void 
DSRAgent::xmitFailed(Packet *pkt)
  /* mark our route cache reflect the failure of the link between
     srh[cur_addr] and srh[next_addr], and then create a route err
     message to send to the orginator of the pkt (srh[0])
     p.pkt freed or handed off */
{
  hdr_sr *srh = (hdr_sr*)pkt->access(off_sr_);
  hdr_ip *iph = (hdr_ip*)pkt->access(off_ip_);
  hdr_cmn *cmh = (hdr_cmn*)pkt->access(off_cmn_);

  assert(cmh->size() >= 0);

  srh->cur_addr() -= 1;		// correct for inc already done on sending

  if (verbose) 
    trace("SSendFailure %.9f _%s_ --- %d - %s",
          Scheduler::instance().clock(), net_id.dump(), cmh->uid(), srh->dump());

  if (srh->cur_addr() >= srh->num_addrs() - 1)
    {
      trace("SDFU: route error beyond end of source route????");
      fprintf(stderr,"SDFU: route error beyond end of source route????\n");
      Packet::free(pkt);
      return;
    }

  if (srh->route_request())
    {
      trace("SDFU: route error forwarding route request????");
      fprintf(stderr,"SDFU: route error forwarding route request????\n");
      Packet::free(pkt);
      return;
    }


  ID tell_id(srh->addrs[0].addr,
	     (ID_Type) srh->addrs[srh->cur_addr()].addr_type);
  ID from_id(srh->addrs[srh->cur_addr()].addr,
	     (ID_Type) srh->addrs[srh->cur_addr()].addr_type);
  ID to_id(srh->addrs[srh->cur_addr()+1].addr,
	     (ID_Type) srh->addrs[srh->cur_addr()].addr_type);
  assert(from_id == net_id || from_id == MAC_id);

#ifdef USE_GOD_FEEDBACK
  if (God::instance()->hops(from_id.getNSAddr_t(), to_id.getNSAddr_t()) == 1)
    { /* god thinks this link is still valid */
      linkerr_is_wrong++;
      trace("SxmitFailed %.5f _%s_  %d->%d god okays #%d",
            Scheduler::instance().clock(), net_id.dump(),
            from_id.getNSAddr_t(), to_id.getNSAddr_t(), linkerr_is_wrong);
      fprintf(stderr,
	      "xmitFailed on link %d->%d god okays - ignoring & recycling #%d\n",
	      from_id.getNSAddr_t(), to_id.getNSAddr_t(), linkerr_is_wrong);
      /* put packet back on end of ifq for xmission */
      srh->cur_addr() += 1;	// correct for decrement earlier in proc 
      // make sure we aren't cycling packets
      assert(p.pkt->incoming == 0); // this is an outgoing packet
      ll->recv(pkt, (Handler*) 0);
      return;
    }
#endif

  /* kill any routes we have using this link */
  route_cache->noticeDeadLink(from_id, to_id,
			      Scheduler::instance().clock());

  /* give ourselves a chance to save the packet */
  undeliverablePkt(pkt->copy(), 1);

  /* now kill all the other packets in the output queue that would
     use the same next hop.  This is reasonable, since 802.11 has
     already retried the xmission multiple times => a persistent failure. */
  Packet *r, *nr, *head = 0;		// pkts to be recycled
  while((r = ifq->filter(to_id.getNSAddr_t()))) {
    r->next_ = head;
    head = r; 
  }
  for(r = head; r; r = nr) {  
    nr = r->next_;
    undeliverablePkt(r, 1);
  }

  /* warp pkt into a route error message */
  if (tell_id == net_id || tell_id == MAC_id)
    { // no need to send the route error if it's for us
      if (verbose) 
        trace("Sdebug _%s_ not bothering to send route error to ourselves", 
	      tell_id.dump());
      Packet::free(pkt);	// no drop needed
      pkt = 0;
      return;
    }

  if (srh->num_route_errors() >= MAX_ROUTE_ERRORS)
    { // no more room in the error packet to nest an additional error.
      // this pkt's been bouncing around so much, let's just drop and let
      // the originator retry
      // Another possibility is to just strip off the outer error, and
      // launch a Route discovey for the inner error XXX -dam 6/5/98
      trace("SDFU  %.5f _%s_ dumping maximally nested error %s  %d -> %d",
	    Scheduler::instance().clock(), net_id.dump(),
	    tell_id.dump(),
	    from_id.dump(),
	    to_id.dump());
      Packet::free(pkt);	// no drop needed
      pkt = 0;
      return;
    }

  link_down *deadlink = &(srh->down_links()[srh->num_route_errors()]);
  deadlink->addr_type = srh->addrs[srh->cur_addr()].addr_type;
  deadlink->from_addr = srh->addrs[srh->cur_addr()].addr;
  deadlink->to_addr = srh->addrs[srh->cur_addr()+1].addr;
  deadlink->tell_addr = srh->addrs[0].addr;
  srh->num_route_errors() += 1;

  if (verbose)
    trace("Sdebug %.5f _%s_ sending into dead-link (nest %d) tell %d  %d -> %d",
          Scheduler::instance().clock(), net_id.dump(),
          srh->num_route_errors(),
          deadlink->tell_addr,
          deadlink->from_addr,
          deadlink->to_addr);

  srh->route_error() = 1;
  srh->route_reply() = 0;
  srh->route_request() = 0;

  iph->dst() = deadlink->tell_addr;
  iph->dport() = RT_PORT;
  iph->src() = net_id.addr;
  iph->sport() = RT_PORT;
  iph->ttl() = 255;

  cmh->ptype() = PT_DSR;		// cut off data
  cmh->size() = IP_HDR_LEN;
  cmh->num_forwards() = 0;
  // assign this packet a new uid, since we're sending it
  cmh->uid() = uidcnt_++;

  SRPacket p(pkt, srh);
  p.route.setLength(p.route.index()+1);
  p.route.reverseInPlace();
  p.dest = tell_id;
  p.src = net_id;

  /* send out the Route Error message */
  sendOutPacketWithRoute(p, true);
}

void
XmitFailureCallback(Packet *pkt, void *data)
{
  DSRAgent *agent = (DSRAgent *)data; // cast of trust
  agent->xmitFailed(pkt);
}

#if 0

/* this is code that implements Route Reply holdoff to prevent route 
   reply storms.  It's described in the kluwer paper and was used in 
   those simulations, but isn't currently used.  -dam 8/5/98 */

/*==============================================================
  Callback Timers to deal with holding off  route replies

  Basic theory: if we see a node S that has requested a route to D
  send a packet to D via a route of length <= ours then don't send
  our route.  We record that S has used a good route to D by setting
  the best_length to -1, meaning that our route can't possibly do
  S any good (unless S has been lied to, but we probably can't know
  that).
  
  NOTE: there is confusion in this code as to whether the requestor
  and requested_dest ID's are MAC or IP... It doesn't matter for now
  but will later when they are not the same.

------------------------------------------------------------*/
struct RtHoldoffData: public EventData {
  RtHoldoffData(DSRAgent *th, Packet *pa, int ind):t(th), p(pa), index(ind)
  {}
  DSRAgent *t;
  Packet *p;
  int index;
};

void
RouteReplyHoldoffCallback(Node *node, Time time, EventData *data)
// see if the packet inside the data is still in the
// send buffer and expire it if it is
{
  Packet *p = ((RtHoldoffData *)data)->p;
  DSRAgent *t = ((RtHoldoffData *)data)->t;
  int index = ((RtHoldoffData *)data)->index;

  RtRepHoldoff *entry = &(t->rtrep_holdoff[index]);
  assert((entry->requestor == p->dest));

  // if we haven't heard the requestor use a route equal or better
  // than ours then send our reply.
  if ((lsnode_require_use && entry->best_length != -1)
      || (!lsnode_require_use && entry->best_length > entry->our_length))
    { // we send
      world_statistics.sendingSrcRtFromCache(t,time,p);
      t->sendPacket(t,time,p);
    }
  else
    { // dump our packet
      delete p;
    }
  entry->requestor = invalid_addr;
  entry->requested_dest = invalid_addr;
  delete data;
  t->num_heldoff_rt_replies--;
}

void
DSRAgent::scheduleRouteReply(Time t, Packet *new_p)
  // schedule a time to send new_p if we haven't heard a better
  // answer in the mean time.  Do not modify new_p after calling this
{
  for (int c = 0; c < RTREP_HOLDOFF_SIZE; c ++)
    if (rtrep_holdoff[c].requested_dest == invalid_addr) break;
  assert(c < RTREP_HOLDOFF_SIZE);

  Path *our_route = &(new_p->data.getRoute().source_route);
  rtrep_holdoff[c].requested_dest = (*our_route)[our_route->length() - 1];
  rtrep_holdoff[c].requestor = new_p->dest;
  rtrep_holdoff[c].best_length = MAX_ROUTE_LEN + 1;
  rtrep_holdoff[c].our_length = our_route->length();

  Time send_time = t +
    (Time) (our_route->length() - 1) * rt_rep_holdoff_period
    + U(0.0, rt_rep_holdoff_period);
  RegisterCallback(this,&RouteReplyHoldoffCallback, send_time,
		   new RtHoldoffData(this,new_p,c));
  num_heldoff_rt_replies++;
}

void
DSRAgent::snoopForRouteReplies(Time t, Packet *p)
  // see if p is a route reply that we're watching for
  // or if it was sent off using a route reply we're watching for
{
  for (int c = 0 ; c <RTREP_HOLDOFF_SIZE ; c ++)
    {
      RtRepHoldoff *entry = &(rtrep_holdoff[c]);

      // there is no point in doing this first check if we're always
      // going to send our route reply unless we hear the requester use one
      // better or equal to ours
      if (entry->requestor == p->dest
	  && (p->type == ::route_reply || p->data.sourceRoutep()))
	{ // see if this route reply is one we're watching for
	  Path *srcrt = &(p->data.getRoute().source_route);
	  if (!(entry->requested_dest == (*srcrt)[srcrt->length()-1]))
	    continue;		// it's not ours
	  if (entry->best_length > srcrt->length())
	    entry->best_length = srcrt->length();
	} // end if we heard a route reply being sent
      else if (entry->requestor == p->src
	       && entry->requested_dest == p->dest)
	{ // they're using a route reply! see if ours is better
	  if (p->route.length() <= entry->our_length)
	    { // Oh no! they've used a better path than ours!
	      entry->best_length = -1; //there's no point in replying.
	    }
	} // end if they used used route reply
      else
	continue;
    }
}

#endif 0