dsragent.cc

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

  hdr_cmn *cmnh =  (hdr_cmn*)rrp.pkt->access(off_cmn_);
  iph->dst() = p.dest.getNSAddr_t();
  iph->dport() = RT_PORT;
  iph->src() = net_id.getNSAddr_t();
  iph->sport() = RT_PORT;
  cmnh->ptype() = PT_DSR;
  cmnh->size() = size_;
  cmnh->num_forwards() = 0;
#endif

  /* make the route request packet */
  SRPacket rrp;
  rrp.dest = p.dest;
  rrp.src = net_id;
  rrp.pkt = allocpkt();
  hdr_sr *srh =  (hdr_sr*)rrp.pkt->access(off_sr_);
  hdr_ip *iph =  (hdr_ip*)rrp.pkt->access(off_ip_);
  hdr_cmn *cmnh =  (hdr_cmn*)rrp.pkt->access(off_cmn_);
  iph->dst() = p.dest.getNSAddr_t();
  iph->dport() = RT_PORT;
  iph->src() = net_id.getNSAddr_t();
  iph->sport() = RT_PORT;
  cmnh->ptype() = PT_DSR;
  cmnh->size() = size_ + IP_HDR_LEN; // add in IP header
  cmnh->num_forwards() = 0;

  srh->init();

  if (BackOffTest(e, time))
    { // it's time to start another route request cycle
      if (dsragent_ring_zero_search)
	{ // do a ring zero search
	  e->last_type = LIMIT0;
	  sendOutRtReq(rrp, 0);
	}
      else 
	{ // do a propagating route request right now
	  e->last_type = UNLIMIT;
	  sendOutRtReq(rrp, MAX_SR_LEN);
	}

      e->last_arp = time;
    } 
  else if (LIMIT0 == e->last_type && (time - e->last_arp) > arp_timeout)
   { // try propagating rt req since we haven't heard back from limited one
     e->last_type = UNLIMIT;
     sendOutRtReq(rrp, MAX_SR_LEN);
   }
  else
    { // it's not time to send another route request...
      if (!retry && verbose_srr)
	trace("SRR %.5f _%s_ RR-not-sent %s -> %s", 
	      Scheduler::instance().clock(), 
	      net_id.dump(), rrp.src.dump(), rrp.dest.dump());
      Packet::free(rrp.pkt); // dump the route request packet we made up
      rrp.pkt = 0;
      return;
    }
}

void
DSRAgent::sendOutRtReq(SRPacket &p, int max_prop)
  // turn p into a route request and launch it, max_prop of request is
  // set as specified
  // p.pkt is freed or handed off
{
  hdr_sr *srh =  (hdr_sr*)p.pkt->access(off_sr_);
  assert(srh->valid());

  srh->route_request() = 1;
  srh->rtreq_seq() = route_request_num++;
  srh->max_propagation() = max_prop;
  p.route.reset();
  p.route.appendToPath(net_id);

  if (dsragent_propagate_last_error && route_error_held 
      && Scheduler::instance().clock() - route_error_data_time  < max_err_hold)
    {
      assert(srh->num_route_errors() < MAX_ROUTE_ERRORS);
      srh->route_error() = 1;
      link_down *deadlink = &(srh->down_links()[srh->num_route_errors()]);
      deadlink->addr_type = AF_INET;
      deadlink->from_addr = err_from.getNSAddr_t();
      deadlink->to_addr = err_to.getNSAddr_t();
      deadlink->tell_addr = GRAT_ROUTE_ERROR;
      srh->num_route_errors() += 1;
      /*
       * Make sure that the Route Error gets on a propagating request.
       */
      if(max_prop > 0) route_error_held = false;
    }

  trace("SRR %.5f _%s_ new-request %d %s #%d -> %s", 
	Scheduler::instance().clock(), net_id.dump(), 
	max_prop, p.src.dump(), srh->rtreq_seq(), p.dest.dump());
  sendOutPacketWithRoute(p, false);
}

void
DSRAgent::returnSrcRouteToRequestor(SRPacket &p)
  // take the route in p, add us to the end of it and return the
  // route to the sender of p
  // doesn't free p.pkt
{
  hdr_sr *old_srh = (hdr_sr*)p.pkt->access(off_sr_);

  if (p.route.full()) 
    return; // alas, the route would be to long once we add ourselves

  SRPacket p_copy = p;
  p_copy.pkt = allocpkt();
  p_copy.dest = p.src;
  p_copy.src = net_id;

  p_copy.route.appendToPath(net_id);

  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;

  hdr_sr *new_srh =  (hdr_sr*)p_copy.pkt->access(off_sr_);
  new_srh->init();
  for (int i = 0 ; i < p_copy.route.length() ; i++)
    p_copy.route[i].fillSRAddr(new_srh->reply_addrs()[i]);
  new_srh->route_reply_len() = p_copy.route.length();
  new_srh->route_reply() = 1;

  // propagate the request sequence number in the reply for analysis purposes
  new_srh->rtreq_seq() = old_srh->rtreq_seq();

  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_ reply-sent %s -> %s #%d (len %d) %s",
	Scheduler::instance().clock(), net_id.dump(),
	p_copy.src.dump(), p_copy.dest.dump(), old_srh->rtreq_seq(),
	p_copy.route.length(), p_copy.route.dump());

  // flip the route around for the return to the requestor, and 
  // cache the route for future use
  p_copy.route.reverseInPlace();
  route_cache->addRoute(p_copy.route, Scheduler::instance().clock(), net_id);

  p_copy.route.resetIterator();
  p_copy.route.fillSR(new_srh);
  new_cmnh->size() += new_srh->size();
  
  /* we now want to jitter when we first originate route replies, since
     they are a transmission we make in response to a broadcast packet 
     -dam 4/23/98
     sendOutPacketWithRoute(p_copy, true); */
  tmp_pkt = p_copy.pkt;
  
  Scheduler::instance().schedule(this, p_copy.pkt, Random::uniform(RREQ_JITTER));
}

void
DSRAgent::acceptRouteReply(SRPacket &p)
  /* - enter the packet's source route into our cache
     - see if any packets are waiting to be sent out with this source route
     - doesn't free the pkt */
{
  hdr_sr *srh =  (hdr_sr*)p.pkt->access(off_sr_);
  Path reply_route(srh->reply_addrs(), srh->route_reply_len());

  if (!srh->route_reply())
    { // somethings wrong...
      trace("SDFU non route containing packet given to acceptRouteReply");
      fprintf(stderr,
	      "dfu: non route containing packet given to acceptRouteReply\n");
    }
  
  /* check to see if this reply is valid or not using god info */
  int i;
  bool good_reply = true;
  for (i = 0; i < reply_route.length()-1 ; i++) 
    if (God::instance()->hops(reply_route[i].getNSAddr_t(), 
			      reply_route[i+1].getNSAddr_t()) != 1)
      {
	good_reply = false;
	break;
      }

  trace("SRR %.9f _%s_ reply-received %d from %s  %s #%d -> %s %s",
	Scheduler::instance().clock(), net_id.dump(),
	good_reply ? 1 : 0,
	p.src.dump(), reply_route[0].dump(), srh->rtreq_seq(),
	reply_route[reply_route.length()-1].dump(),
	reply_route.dump());

  // add the new route into our cache
  route_cache->addRoute(reply_route, Scheduler::instance().clock(), p.src);

  // back down the route request counters
  Entry *e = request_table.getEntry(reply_route[reply_route.length()-1]);
  e->rt_reqs_outstanding = 0;
  e->last_rt_req = 0.0;	 

  // see if the addtion of this route allows us to send out
  // any of the packets we have waiting
  Time delay = 0.0;
  for (int c = 0; c < SEND_BUF_SIZE; c++)
    {
      if (send_buf[c].p.pkt == NULL) continue;
      if (route_cache->findRoute(send_buf[c].p.dest,
				 send_buf[c].p.route, 1))
	{ // we have a route!
#ifdef DEBUG
	  struct hdr_cmn *ch = HDR_CMN(send_buf[c].p.pkt);
	  if(ch->size() < 0) {
		drop(send_buf[c].p.pkt, "XXX");
		abort();
	  }
#endif
	  if (verbose)
	    trace("Sdebug %.9f _%s_ liberated from sendbuf %s->%s %s",
		  Scheduler::instance().clock(), net_id.dump(),
		  send_buf[c].p.src.dump(), send_buf[c].p.dest.dump(), 
		  send_buf[c].p.route.dump());
	  /* we need to spread out the rate at which we send packets
	     in to the link layer to give ARP time to complete.  If we
	     dump all the packets in at once, all but the last one will
	     be dropped.  XXX THIS IS A MASSIVE HACK -dam 4/14/98 */
	  sendOutPacketWithRoute(send_buf[c].p, true, delay);
	  delay += arp_timeout;	
	  send_buf[c].p.pkt = NULL;
	}
    }
}

void
DSRAgent::processBrokenRouteError(SRPacket& p)
// take the error packet and proccess our part of it.
// if needed, send the remainder of the errors to the next person
// doesn't free p.pkt
{
  hdr_sr *srh =  (hdr_sr*)p.pkt->access(off_sr_);

  if (!srh->route_error())
    return; // what happened??
  
  /* if we hear A->B is dead, should we also run the link B->A through the
     cache as being dead, since 802.11 requires bidirectional links 
      XXX -dam 4/23/98 */

  // since CPU time is cheaper than network time, we'll process
  // all the dead links in the error packet
  assert(srh->num_route_errors() > 0);
  for (int c = 0 ; c < srh->num_route_errors() ; c++)
    {
      assert(srh->down_links()[c].addr_type == AF_INET);
      route_cache->noticeDeadLink(ID(srh->down_links()[c].from_addr,::IP),
				 ID(srh->down_links()[c].to_addr,::IP),
				 Scheduler::instance().clock());
      // I'll assume everything's of type AF_INET for the printout... XXX
      if (verbose_srr)
        trace("SRR %.9f _%s_ dead-link tell %d  %d -> %d",
              Scheduler::instance().clock(), net_id.dump(),
              srh->down_links()[c].tell_addr,
              srh->down_links()[c].from_addr,
              srh->down_links()[c].to_addr);
    }

  ID who = ID(srh->down_links()[srh->num_route_errors()-1].tell_addr, ::IP);
  if (who != net_id && who != MAC_id)
    { // this error packet wasn't meant for us to deal with
      // since the outer entry doesn't list our name
      return;
    }

  // record this route error data for possible propagation on our next
  // route request
  route_error_held = true;
  err_from = ID(srh->down_links()[srh->num_route_errors()-1].from_addr,::IP);
  err_to = ID(srh->down_links()[srh->num_route_errors()-1].to_addr,::IP);
  route_error_data_time = Scheduler::instance().clock();

  if (1 == srh->num_route_errors())
    { // this error packet has done its job
      // it's either for us, in which case we've done what it sez
      // or it's not for us, in which case we still don't have to forward
      // it to whoever it is for
      return;
    }

  /* make a copy of the packet and send it to the next tell_addr on the
     error list.  the copy is needed in case there is other data in the
     packet (such as nested route errors) that need to be delivered */
  if (verbose) 
    trace("Sdebug %.5f _%s_ unwrapping nested route error",
          Scheduler::instance().clock(), net_id.dump());
  
  SRPacket p_copy = p;
  p_copy.pkt = p.pkt->copy();

  hdr_sr *new_srh = (hdr_sr*)p_copy.pkt->access(off_sr_);
  hdr_ip *new_iph = (hdr_ip*)p_copy.pkt->access(off_ip_);
  
  // remove us from the list of errors
  new_srh->num_route_errors() -= 1;
  
  // send the packet to the person listed in what's now the last entry
  p_copy.dest = ID(new_srh->down_links()[new_srh->num_route_errors()-1].tell_addr, ::IP);
  p_copy.src = net_id;

  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;
      
  // an error packet is a first class citizen, so we'll
  // use handlePktWOSR to obtain a route if needed
  handlePktWithoutSR(p_copy, false);
}

void 
DSRAgent::tap(const Packet *packet)
  /* process packets that are promiscously listened to from the MAC layer tap
  *** do not change or free packet *** */
{
  hdr_sr *srh =  (hdr_sr*) ((Packet *)packet)->access(off_sr_);
  hdr_ip *iph =  (hdr_ip*)((Packet *)packet)->access(off_ip_);
  hdr_cmn *cmh =  (hdr_cmn*)((Packet *)packet)->access(off_cmn_);
 

  //Jinyang: keep track of the number of packets tapped
  tapped_pkts++; 
  if (!dsragent_use_tap) return;

  if (!srh->valid()) return;	// can't do anything with it

  // don't trouble me with packets I'm about to receive anyway
  /* this change added 5/13/98 -dam */
  ID next_hop(srh->addrs[srh->cur_addr()]);
  if (next_hop == net_id || next_hop == MAC_id) return;

  SRPacket p((Packet *) packet, srh);
  p.dest = ID(iph->dst(),::IP);
  p.src = ID(iph->src(),::IP);

  // don't trouble me with my own packets
  if (p.src == net_id) return; 

  /* snoop on the SR data */
  if (srh->route_error())
    {
      if (verbose)
	trace("Sdebug _%s_ tap saw error %d",  net_id.dump(), cmh->uid());
      processBrokenRouteError(p);
    }

  if (srh->route_reply())
    {
      Path reply_path(srh->reply_addrs(), srh->route_reply_len());
      if(verbose)
	trace("Sdebug _%s_ tap saw route reply %d  %s",
	       net_id.dump(), cmh->uid(), reply_path.dump());
      route_cache->noticeRouteUsed(reply_path, Scheduler::instance().clock(), 
				   p.src);
    }

  /* we can't decide whether we should snoop on the src routes in 
     route requests.  We've seen cases where we hear a route req from a
     node, but can't complete an arp with that node (and so can't actually
     deliver packets through it if called on to do so) -dam 4/16/98 */

  if (srh->route_request()) return; // don't path shorten route requests
  // the logic is wrong for shortening rtreq's anyway, cur_addr always = 0

  if (dsragent_snoop_source_routes)
    {
      if (verbose)
	trace("Sdebug _%s_ tap saw route use %d %s", net_id.dump(), 
	      cmh->uid(), p.route.dump());
      route_cache->noticeRouteUsed(p.route, Scheduler::instance().clock(), 
				   net_id);
    }

  if (PT_DSR == cmh->ptype()) return; //  no route shortening on any
  // DSR packet

  /* 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];