dsragent.cc

动态路由协议dsr改进算法

		delete [] subnet;
	}
	assert(dstnet == NULL);
	return 0;
}


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::access(p.pkt);
  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");
    }

  bool good_reply = true;  
  //#ifdef USE_GOD_FEEDBACK
  /* check to see if this reply is valid or not using god info */
  int i;
  
  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;
      }
  //#endif //GOD_FEEDBACK

  if (verbose_srr)
    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;
  ID dest;
  for (int c = 0; c < SEND_BUF_SIZE; c++)
    {
      if (send_buf[c].p.pkt == NULL) continue;

      // check if pkt is destined to outside domain
      if (diff_subnet(send_buf[c].p.dest,net_id)) {
	dest = ID(node_->base_stn(),::IP);
	send_buf[c].p.dest = dest;
      }

      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::processUnknownFlowError(SRPacket &p, bool asDefault) {
  hdr_sr *srh = hdr_sr::access(p.pkt);
  int flowidx = -1;
  struct flow_error *fe;
  u_int16_t flowid;

  if (asDefault) {
    assert (srh->flow_default_unknown() && srh->num_default_unknown());
    fe = &srh->unknown_defaults()[srh->num_default_unknown()-1];
  } else {
    assert (srh->flow_unknown() && srh->num_flow_unknown());
    fe = &srh->unknown_flows()[srh->num_flow_unknown()-1];
    if (!flow_table.defaultFlow(fe->flow_src, fe->flow_dst, flowid))
      goto skip_proc;
  }

  /* not for us; hope it gets the right place... */
  if (fe->flow_src != (int) net_id.addr)
    return;

  if (-1 != (flowidx = flow_table.find(fe->flow_src, fe->flow_dst, 
				       asDefault ? flowid : fe->flow_id)))
    flow_table[flowidx].count = 0;

skip_proc:
  trace("SFEr %.9f _%s_ from %d re %d : %d [%d]",
	Scheduler::instance().clock(), net_id.dump(), p.src.addr, fe->flow_dst,
	asDefault ? -1 : fe->flow_id, 
	flowidx != -1 ? flow_table[flowidx].count : -1);

  if ((asDefault ? srh->num_default_unknown() : srh->num_flow_unknown()) == 1)
    return;

  SRPacket p_copy = p;
  p_copy.pkt = p.pkt->copy();

  hdr_sr *new_srh = hdr_sr::access(p_copy.pkt);
  hdr_ip *new_iph = hdr_ip::access(p_copy.pkt);
  
  // remove us from the list of errors
  if (asDefault)
    new_srh->num_default_unknown()--;
  else
    new_srh->num_flow_unknown()--;
  
  // send the packet to the person listed in what's now the last entry
  p_copy.dest = ID(fe[-1].flow_src, ::IP);
  p_copy.src = net_id;

  //new_iph->daddr() = p_copy.dest.addr;
  new_iph->daddr() = Address::instance().create_ipaddr(p_copy.dest.getNSAddr_t(),RT_PORT);
  new_iph->dport() = RT_PORT;
  //new_iph->saddr() = p_copy.src.addr;
  new_iph->saddr() = Address::instance().create_ipaddr(p_copy.src.getNSAddr_t(),RT_PORT);
  new_iph->sport() = RT_PORT;
  new_iph->ttl() = 255;

  new_srh->flow_header() = 0;
  new_srh->flow_timeout() = 0;

  // 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::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::access(p.pkt);

  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 == NS_AF_INET);
      route_cache->noticeDeadLink(ID(srh->down_links()[c].from_addr,::IP),
				 ID(srh->down_links()[c].to_addr,::IP),
				 Scheduler::instance().clock());
      flow_table.noticeDeadLink(ID(srh->down_links()[c].from_addr,::IP),
				 ID(srh->down_links()[c].to_addr,::IP));
      // I'll assume everything's of type NS_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::access(p_copy.pkt);
  hdr_ip *new_iph = hdr_ip::access(p_copy.pkt);
  
  // 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->daddr() = p_copy.dest.addr;
  new_iph->daddr() = Address::instance().create_ipaddr(p_copy.dest.getNSAddr_t(),RT_PORT);
  new_iph->dport() = RT_PORT;
  //new_iph->saddr() = p_copy.src.addr;
  new_iph->saddr() = Address::instance().create_ipaddr(p_copy.src.getNSAddr_t(),RT_PORT);
  new_iph->sport() = RT_PORT;
  new_iph->ttl() = 255;

  new_srh->flow_header() = 0;
  new_srh->flow_timeout() = 0;
      
  // an error packet is a first class citizen, so we'll
  // use handlePktWOSR to obtain a route if needed
  handlePktWithoutSR(p_copy, false);
}

#ifdef DSR_FILTER_TAP
int64_t dsr_tap = 0;
int64_t dsr_tap_skip = 0;
#endif

// Process flow state Automatic Route Shortening
void
DSRAgent::processFlowARS(const Packet *packet) {
  
  hdr_sr *srh = hdr_sr::access(packet);
  hdr_ip *iph = hdr_ip::access(packet);
  hdr_cmn *cmh = hdr_cmn::access(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_);
  u_int16_t flowid;
  int flowidx;
  int shortamt;

  assert(!srh->num_addrs());

  if (srh->flow_header()) {
    flowid = srh->flow_id();

    // do I know about this flow?
    if (-1 == (flowidx = flow_table.find(iph->saddr(), iph->daddr(), flowid)))
      return;

    shortamt = flow_table[flowidx].hopCount - srh->hopCount();
  } else {
    // do I know which flow is default?
    if (!flow_table.defaultFlow(iph->saddr(), iph->daddr(), flowid))
      return;

    // do I know about this flow?
    if (-1 == (flowidx = flow_table.find(iph->saddr(), iph->daddr(), flowid)))
      return;

    shortamt = iph->ttl() - flow_table[flowidx].expectedTTL;
  }

  // transmitter downstream from us
  if (shortamt <= 0)
    return;

  // this is a _MAJOR_ problem!!!
  if (flow_table[flowidx].sourceRoute.length() < shortamt)
    return;

  ars_table.insert(cmh->uid(), flowid, shortamt);
}

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::access(packet);
  hdr_ip *iph = hdr_ip::access(packet);
  hdr_cmn *cmh =  hdr_cmn::access(packet);
  
  if (!dsragent_use_tap) return;

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

  if (!srh->num_addrs()) {
    processFlowARS(packet);
    return;
  }

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

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

#ifdef DSR_FILTER_TAP
  /* 
   * Don't process packets more than once.  In real implementations
   * this can be done with the (IP Source, IP ID) pair, but it is
   * simpler to implement it with the global "uid" in simulation.
   */
  {
          int uid = cmh->uid();
          if(tap_uid_cache[(uid & TAP_BITMASK)] == uid) {
		  dsr_tap_skip++;
                  return;
	  }
	  dsr_tap++;
          tap_uid_cache[(uid & TAP_BITMASK)] = uid;
  }
#endif

  /* 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 g