dsragent.cc

动态路由协议dsr改进算法

      p.route.resetIterator();
      if (verbose && !srh->route_request())
	{
	  trace("SO %.9f _%s_ originating %s %s", 
		Scheduler::instance().clock(), 
		net_id.dump(), packet_info.name(cmnh->ptype()), p.route.dump());
	}
    }

  p.route.fillSR(srh);

  // set direction of pkt to DOWN , i.e downward
  cmnh->direction() = hdr_cmn::DOWN;

  // let's see if we can snag this packet for flow state... ych 5/2/01
  if (dsragent_enable_flowstate &&
      p.src == net_id && !srh->route_request() && !srh->cur_addr() &&
      // can't yet decode flow errors and route errors/replies together
      // so don't tempt the system... ych 5/7/01
      !srh->route_error() && !srh->route_reply()) {
    hdr_ip *iph =  hdr_ip::access(p.pkt);
    int flowidx;
    u_int16_t flowid, default_flowid;
    double now = Scheduler::instance().clock();

    // hmmm, let's see if we can save us some overhead...
    if (dsragent_prefer_default_flow &&
	flow_table.defaultFlow(p.src.addr, p.dest.addr, flowid) &&
	-1 != (flowidx = flow_table.find(p.src.addr, p.dest.addr, flowid)) &&
	flow_table[flowidx].timeout >= now &&
	(!dsragent_prefer_shorter_over_default || 
	  flow_table[flowidx].sourceRoute.length() <= p.route.length()) &&
	!(p.route == flow_table[flowidx].sourceRoute)) {

      p.route = flow_table[flowidx].sourceRoute;
      p.route.fillSR(srh);
    }

    flowidx = flow_table.find(p.src.addr, p.dest.addr, p.route);

    if (flowidx == -1 || flow_table[flowidx].timeout < now) {
      // I guess we don't know about this flow; allocate it.
      flow_table.cleanup();
      flowid = flow_table.generateNextFlowId(p.dest.addr, true);
      flowidx = flow_table.createEntry(p.src.addr, p.dest.addr, flowid);
      assert(flowidx != -1);

      // fill out the table
      flow_table[flowidx].count = 1;
      flow_table[flowidx].lastAdvRt = Scheduler::instance().clock();
      flow_table[flowidx].timeout = now + default_flow_timeout;
      flow_table[flowidx].hopCount = 0;
      flow_table[flowidx].expectedTTL = iph->ttl();
      flow_table[flowidx].allowDefault = true;
      flow_table[flowidx].sourceRoute = p.route;
      flow_table[flowidx].nextHop = srh->get_next_addr();
      assert(srh->get_next_type() == ::IP);

      // fix up the srh for the timeout
      srh->flow_timeout() = 1;
      srh->flow_timeout_time() = default_flow_timeout;
      srh->cur_addr() = srh->cur_addr() + 1;
    } else if (flow_table[flowidx].count <= END_TO_END_COUNT ||
		flow_table[flowidx].lastAdvRt < 
		   (Scheduler::instance().clock() - min_adv_interval)) {
      // I've got it, but maybe someone else doesn't
      if (flow_table[flowidx].expectedTTL != iph->ttl())
	flow_table[flowidx].allowDefault = false;

      flow_table[flowidx].count++;
      flow_table[flowidx].lastAdvRt = Scheduler::instance().clock();

      srh->flow_timeout() = 1;
      if (dsragent_always_reestablish)
	srh->flow_timeout_time() = default_flow_timeout;
      else
	srh->flow_timeout_time() = (int)(flow_table[flowidx].timeout - now);
      srh->cur_addr() = srh->cur_addr() + 1;
    } else {
      // flow is established end to end
      assert (flow_table[flowidx].sourceRoute == p.route);
      srh->flow_timeout() = srh->cur_addr() = srh->num_addrs() = 0;
    }

    if (dsragent_always_reestablish) {
      // XXX see major problems detailed above (search for dsragent_always_re..)
      flow_table[flowidx].timeout = now + default_flow_timeout;
    }

    cmnh->next_hop() = flow_table[flowidx].nextHop;
    cmnh->addr_type() = ::IP;

    if (flow_table.defaultFlow(p.src.addr, p.dest.addr, default_flowid) &&
	flow_table[flowidx].flowId == default_flowid &&
	!srh->num_addrs() && iph->ttl() == flow_table[flowidx].expectedTTL &&
	flow_table[flowidx].allowDefault) {
      // we can go without anything... woo hoo!
      assert(!srh->flow_header());
    } else {
      srh->flow_header() = 1;
      srh->flow_id() = flow_table[flowidx].flowId;
      srh->hopCount() = 1;
    }

    trace("SF%ss %.9f _%s_ %d [%s -> %s] %d(%d) to %d %s", 
	srh->num_addrs() ? "EST" : "",
	Scheduler::instance().clock(), net_id.dump(), cmnh->uid(),
	p.src.dump(), p.dest.dump(), flow_table[flowidx].flowId,
	srh->flow_header(), flow_table[flowidx].nextHop,
	srh->num_addrs() ? srh->dump() : "");

    cmnh->size() += srh->size();
    cmnh->xmit_failure_ = srh->num_addrs() ? XmitFailureCallback : 
					     XmitFlowFailureCallback;
    cmnh->xmit_failure_data_ = (void *) this;

    assert(!srh->num_addrs() || srh->flow_timeout());
  } else {
    // old non-flowstate stuff...
    assert(p.src != net_id || !srh->flow_header());
    cmnh->size() += srh->size();

    if (srh->route_request())
      { // broadcast forward
        cmnh->xmit_failure_ = 0;
        cmnh->next_hop() = MAC_BROADCAST;
        cmnh->addr_type() = NS_AF_ILINK;
      }
    else
      { // forward according to source route
        cmnh->xmit_failure_ = XmitFailureCallback;
        cmnh->xmit_failure_data_ = (void *) this;

        cmnh->next_hop() = srh->get_next_addr();
        cmnh->addr_type() = srh->get_next_type();
        srh->cur_addr() = srh->cur_addr() + 1;
      } /* route_request() */
  } /* can snag for path state */

  /* put route errors at the head of the ifq somehow? -dam 4/13/98 */

  // make sure we aren't cycling packets
  
#ifdef notdef
  if (ifq->prq_length() > 25)
	  trace("SIFQ %.5f _%s_ len %d",
		Scheduler::instance().clock(),
		net_id.dump(), ifq->prq_length());
#endif
#ifdef NEW_IFQ_LOGIC
  /*
   *  If the interface queue is full, there's no sense in sending
   *  the packet.  Drop it and generate a Route Error?
   */
  /* question for the author: this seems rife with congestion/infinite loop
   * possibilities. you're responding to an ifq full by sending a rt err.
   * sounds like the source quench problem. ych 5/5/01
   */
  if(ifq->prq_isfull(p.pkt)) {
	  xmitFailed(p.pkt, DROP_IFQ_QFULL);
	  p.pkt = 0;
	  return;
  }
#endif /* NEW_IFQ_LOGIC */

  // ych debugging
  assert(!srh->flow_header() || !srh->num_addrs() || srh->flow_timeout());

  // off it goes!
  if (srh->route_request())
    { // route requests need to be jittered a bit
      Scheduler::instance().schedule(ll, p.pkt, 
				     Random::uniform(RREQ_JITTER) + delay);
    }
  else
    { // no jitter required 
      Scheduler::instance().schedule(ll, p.pkt, delay);
    }
  p.pkt = NULL; /* packet sent off */
}

void
DSRAgent::getRouteForPacket(SRPacket &p, bool retry)
  /* try to obtain a route for packet
     pkt is freed or handed off as needed, unless retry == true
     in which case it is not touched */
{
  // since we'll commonly be only one hop away, we should
  // arp first before route discovery as an optimization...

  Entry *e = request_table.getEntry(p.dest);
  Time time = Scheduler::instance().clock();

#if 0
  /* pre 4/13/98 logic -dam removed b/c it seemed more complicated than
     needed since we're not doing piggybacking and we're returning
     route replies via a reversed route (the copy in this code is
     critical if we need to piggyback route replies on the route request to
     discover the return path) */

  /* make the route request packet */
  SRPacket rrp = p;
  rrp.pkt = p.pkt->copy();
  hdr_sr *srh = hdr_sr::access(rrp.pkt);
  hdr_ip *iph = hdr_ip::access(rrp.pkt);
  hdr_cmn *cmh =  hdr_cmn::access(rrp.pkt);
  //iph->daddr() = p.dest.getNSAddr_t();
  iph->daddr() = Address::instance().create_ipaddr(p.dest.getNSAddr_t(),RT_PORT);
  iph->dport() = RT_PORT;
  //iph->saddr() = net_id.getNSAddr_t();
  iph->saddr() = Address::instance().create_ipaddr(net_id.getNSAddr_t(),RT_PORT);
  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::access(rrp.pkt); 
  hdr_ip *iph = hdr_ip::access(rrp.pkt);
  hdr_cmn *cmnh =  hdr_cmn::access(rrp.pkt);
  
  iph->daddr() = Address::instance().create_ipaddr(p.dest.getNSAddr_t(),RT_PORT);
  iph->dport() = RT_PORT;
  iph->saddr() = Address::instance().create_ipaddr(net_id.getNSAddr_t(),RT_PORT);
  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

#ifdef NEW_SALVAGE_LOGIC
	  if(p.src != net_id) {

		  assert(dsr_salvage_max_requests > 0);
		  assert(p.pkt);

		  if(e->rt_reqs_outstanding > dsr_salvage_max_requests) {
			  drop(p.pkt, DROP_RTR_NO_ROUTE);
			  p.pkt = 0;

			  // dump the route request packet we made up
			  Packet::free(rrp.pkt);
			  rrp.pkt = 0;

			  return;
		  }
	  }
#endif /* NEW_SALVAGE_LOGIC */

	  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 &&
#ifdef NEW_SALVAGE_LOGIC
	      (dsr_salvage_allow_propagating || p.src == net_id) &&
#endif
	   (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;
  }

  /* for now, no piggybacking at all, queue all pkts */
  if (!retry) {
	  stickPacketInSendBuffer(p);
	  p.pkt = 0; // pkt is handled for now (it's in sendbuffer)
  }

}

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

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

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

  hdr_sr *new_srh =  hdr_sr::access(p_copy.pkt);
  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::access(p_copy.pkt);
  new_cmnh->ptype() = PT_DSR;
  new_cmnh->size() = IP_HDR_LEN;

  if (verbose_srr)
    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); */
  {
	  double d = Random::uniform(RREQ_JITTER);
#if 0
	  fprintf(stderr, "Random Delay: %f\n", d);
#endif
	  Scheduler::instance().schedule(this, p_copy.pkt, d);
  }
}

int
DSRAgent::diff_subnet(ID dest, ID myid) 
{
	int dst = dest.addr;
	int id = myid.addr;
	char* dstnet = Address::instance().get_subnetaddr(dst);
	char * subnet = Address::instance().get_subnetaddr(id);
	if (subnet != NULL) {
		if (dstnet != NULL) {
			if (strcmp(dstnet, subnet) != 0) {
				delete [] dstnet;
				return 1;
			}
			delete [] dstnet;
		}