dsragent.cc

在Linux下做的QuadTree的程序

	     -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
		      if (verbose_srr)
			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;
		    }
		}
	      
	    }

	  if (verbose_ssalv) 
	    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());

	  // remove size of SR header, added back in sendOutPacketWithRoute
	  cmh->size() -= srh->size(); 
	  assert(cmh->size() >= 0);
	  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
	  if (verbose_ssalv) 
	    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

//added by jinyang
static int link_error_wrong = 0;
static int link_error_right = 0;

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 (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);

  trace("SSendFailure %.9f _%s_ %d %d %d:%d %d:%d %s->%s %d %d %d %d %s",
	Scheduler::instance().clock(), net_id.dump(), 
	cmh->uid(), cmh->ptype(),
	iph->src(), iph->sport(),
	iph->dst(), iph->dport(),
	from_id.dump(),to_id.dump(),
	God::instance()->hops(from_id.getNSAddr_t(), to_id.getNSAddr_t()),
	God::instance()->hops(iph->src(),iph->dst()),
	God::instance()->hops(from_id.getNSAddr_t(), iph->dst()),
	srh->num_addrs(), srh->dump());

#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

  if (God::instance()->isNeighbor(from_id.getNSAddr_t(),to_id.getNSAddr_t())) {
      link_error_wrong++;
      trace("Slinkerror wrong %d %s->%s",link_error_wrong,from_id.dump(),to_id.dump());
  }else {
      trace("Slinkerror right %d %s->%s",link_error_right,from_id.dump(),to_id.dump());
      link_error_right++;
  }

  /* 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->prq_get_nexthop(to_id.getNSAddr_t()))) {
    r->next_ = head;
    head = r; 
  }
  // the packets are now in the reverse order of how they appeared in the IFQ
  // so reverse them again
  for(r = head, head = 0; r; r = r->next_) {  
    r->next_ = head;
    head = r; 
  }
  // now process them in order
  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