dsragent.cc

柯老师网站上找到的

  /* I think we ended up sending grat route replies for source routes on 
     route replies for route requests that were answered by someone else's
     cache, resulting in the wrong node receiving the route.  For now, I 
     outlaw it.

     The root of the problem is that when we salvage a pkt from a failed
     link using a route from our cache, we break what had been an invariant
     that the IP src of a packet was also the first machine listed on the
     source route.  Here's the route of the problem that results in the 
     simulator crashing at 8.56135 when 44 recieves a route reply that
     has 24 listed as the first node in the route.

SSendFailure 8.52432 24 [10 |24 46 45 1 40 ]
S$hit 8.52432 salvaging 10 -> 40 with [(24) 44 50 9 40 ]
S$hit 8.52432 salvaging 44 -> 40 with [(24) 44 50 9 40 ]
D 8.52432 [20 42 2e 18 800] 24 DSR 156 -- 10->40 6 [0] [1 9 39] [0 0 0->0]
s 8.52438 [1b 45e 2c 18 0] 24 MAC 20
r 8.52446 [1b 45e 2c 18 0] 44 MAC 20
s 8.52454 [101b 27e 23 1b 0] 27 MAC 20
s 8.52564 [101b 27e 23 1b 0] 27 MAC 20
s 8.52580 [101b 45e 2c 18 0] 24 MAC 20
r 8.52588 [101b 45e 2c 18 0] 44 MAC 20
s 8.52589 [1c 41c 18 0 0] 44 MAC 14
r 8.52595 [1c 41c 18 0 0] 24 MAC 14
s 8.52600 [20 42 2c 18 800] 24 DSR 244 -- 10->40 5 [0] [1 9 39] [0 0 24->46]
r 8.52698 [20 42 2c 18 800] 44 DSR 216 -- 10->40 5 [0] [1 9 39] [0 0 24->46]

s 8.53947 [20 42 2c 18 800] 24 DSR 204 -- 44->40 5 [0] [1 8 39] [0 0 0->0]
r 8.54029 [20 42 2c 18 800] 44 DSR 176 -- 44->40 5 [0] [1 8 39] [0 0 0->0]
Sdebug 50 consider grat arp for [24 (44) 50 9 40 ]
SRR 8.54029 50 gratuitous-reply-sent 50 -> 44 [24 (50) 9 40 ]
SF 8.54029 44 [44 -> 40] via 0x3200 [24 |44 50 9 40 ]
s 8.54030 [1d 0 18 0 0] 44 MAC 14
r 8.54036 [1d 0 18 0 0] 24 MAC 14
s 8.54044 [101b 54f 32 2c 0] 44 MAC 20
r 8.54053 [101b 54f 32 2c 0] 50 MAC 20
s 8.54054 [1c 50d 2c 0 0] 50 MAC 14
r 8.54059 [1c 50d 2c 0 0] 44 MAC 14
s 8.54064 [20 42 32 2c 800] 44 DSR 304 -- 10->40 5 [0] [1 9 39] [0 0 24->46]
r 8.54186 [20 42 32 2c 800] 50 DSR 276 -- 10->40 5 [0] [1 9 39] [0 0 24->46]
SF 8.54186 50 [10 -> 40] via 0x900 [24 44 |50 9 40 ]

s 8.56101 [20 42 2c 18 800] 24 DSR 84 -- 50->44 2 [0] [1 4 40] [0 0 0->0]
r 8.56135 [20 42 2c 18 800] 44 DSR 56 -- 50->44 2 [0] [1 4 40] [0 0 0->0]

*/


  /* check to see if we can shorten the route being used */
  if (p.route[p.route.index()] != net_id
      && p.route[p.route.index()] != MAC_id)
    { // it's not immeadiately to us
      for (int i = p.route.index() + 1; i < p.route.length(); i++)
	if (p.route[i] == net_id || p.route[i] == MAC_id)
	  { // but it'll get here eventually...
	    sendRouteShortening(p, p.route.index(), i);
	  }
    }
}

static GratReplyHoldDown *
FindGratHoldDown(GratReplyHoldDown *hd, int sz, Path& query)
{
  int c;
  for (c = 0; c < sz; c++)
    if (query == hd[c].p) return &hd[c];
  return NULL;
}

void
DSRAgent::sendRouteShortening(SRPacket &p, int heard_at, int xmit_at)
  // p was overheard at heard_at in it's SR, but we aren't supposed to
  // get it till xmit_at, so all the nodes between heard_at and xmit_at
  // can be elided.  Send originator of p a gratuitous route reply to 
  // tell them this.
{
  // this shares code with returnSrcRouteToRequestor - factor them -dam */

  if (!dsragent_send_grat_replies) return;

  if (verbose)
    trace("Sdebug %s consider grat arp for %s", net_id.dump(), p.route.dump());
  GratReplyHoldDown *g = FindGratHoldDown(grat_hold, RTREP_HOLDOFF_SIZE, 
					  p.route);
  if (!g)
    { 
      grat_hold[grat_hold_victim].p = p.route;
      grat_hold_victim = (grat_hold_victim + 1) % RTREP_HOLDOFF_SIZE;
      g = &grat_hold[grat_hold_victim];      
    }
  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) << Address::instance().nodeshift();
  new_iph->daddr() = Address::instance().create_ipaddr(p_copy.dest.getNSAddr_t(),RT_PORT);
  new_iph->dport() = RT_PORT;
  //new_iph->src() = (p_copy.src.addr) << Address::instance().nodeshift();
  new_iph->saddr() = Address::instance().create_ipaddr(p_copy.src.getNSAddr_t(),RT_PORT);
  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;

  if (verbose) {
      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((Address::instance().get_nodeaddr(iph->daddr())),::IP);
  p.src = ID((Address::instance().get_nodeaddr(iph->saddr())),::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 (p.src == 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 =