aodv.cc

在NS环境下对aodv路由协议进行仿真

    
    MN_S sends RREQ_I which is received by gwA and gwB. Both gateways send 
    RREP_Is. RREP_I from gwA is dropped (e.g. due to collision or by ARP). So 
    MN_I receives RREP_I from gwB. MN_I does not update its default route 
    because it has already a route to gwA and the route to gwB is not shorter. 
    MN_I forwards RREP_I to MN_S. MN_S think its default GW is gwB when sending
    packets to MN_I, but in fact MN_I sends the packets to gwA! So when the 
    link between MN_I and gwA breaks and MN_I sends a RERR, MN_S doesn't care 
    about the RERR (although it should) because it is not the nexthop of one of
    the advertised unreachable destinations. Thus, MN_S doesn't bring down 
    default route and continues sending packets to MN_I which dropps the 
    packets (NRTE). The problem occurs when MN_I forwards a RREP_I for gwB 
    although its own default route is gwA!
    
    The root of this problem is that ARP dropps the RREP_I! It can be solved by
    introducing a queue in ARP. But maybe RREP_Is can be dropped in another 
    way besides by ARP? In that case we must solve the problem either like 
    below or by changing the gateway selection procedure.
    
    See recvReply!
  */
  if(default_rt && default_rt->rt_flags == RTF_UP && gw_rt && 
     ih->saddr() == gw_rt->rt_nexthop) {
    rt_down(default_rt);
  }
  //*************************************************************************//
  
  if(nre->DestCount > 0) {
#ifdef DEBUG
    fprintf(stderr, "%d - sending RERR\ttime=%f s\n", index, CURRENT_TIME);
#endif // DEBUG
    sendError(rerr);
  }
  else {
    Packet::free(rerr);
  }
  
  Packet::free(p);
}



/* ======================================================================
   Packet Transmission Routines
   ===================================================================== */
void
AODV::forward(aodv_rt_entry *rt, Packet *p, double delay) {
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  
  if(ih->ttl_ == 0) {
    //My modification********************************************************//
#ifdef DEBUG
    if(gw_discovery != 0 && gw_discovery != 1) {
      fprintf(stderr, "%d - TTL=0 ==> drop packet\n", index);
    }
#endif // DEBUG
    //***********************************************************************//
    drop(p, DROP_RTR_TTL);
    return;
  }
 
  if(ch->ptype() != PT_AODV && ch->direction() == hdr_cmn::UP &&
     ((u_int32_t)ih->daddr() == IP_BROADCAST)
     || ((u_int32_t)ih->daddr() == here_.addr_)) {
    dmux_->recv(p,0);
    return;
  }
  
  if(rt) {
    assert(rt->rt_flags == RTF_UP);
   
    //My modification********************************************************//
    /*
      Update rt_expire for fixed node (FN) route and default route...
      That is, we have to update rt_expire for FN==>DEFAULT and DEFAULT==>GW!
      However, we have to update rt_expire for these entries only if they are
      going to be used. That's why we need the if statement, but the condition 
      is maybe not the best one...
    */
    rt->rt_expire = max(rt->rt_expire, CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT);
    
    aodv_rt_entry *default_rt = rtable.rt_lookup(DEFAULT);
    aodv_rt_entry *fn_rt = rtable.rt_lookup(ih->daddr());
    if(ih->daddr() != rt->rt_dst) {
      default_rt->rt_expire = max(default_rt->rt_expire, CURRENT_TIME + 
				  GWINFO_LIFETIME);
      fn_rt->rt_expire = max(fn_rt->rt_expire, CURRENT_TIME + GWINFO_LIFETIME);
    }
    //***********************************************************************//
    ch->next_hop_ = rt->rt_nexthop;
    ch->addr_type() = NS_AF_INET;
    ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction
  }
  else { // if it is a broadcast packet
    assert(ch->ptype() == PT_AODV);
    assert(ih->daddr() == (nsaddr_t) IP_BROADCAST);
    ch->addr_type() = NS_AF_NONE;
    ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction
  }
 
  if(ih->daddr() == (nsaddr_t) IP_BROADCAST) {
    // If it is a broadcast packet
    assert(rt == 0);
   
    //Jitter the sending of broadcast packets by 10 ms
    Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform());
  }
  else { // Not a broadcast packet 
    if(delay > 0.0) {
      Scheduler::instance().schedule(target_, p, delay);
    }
    else {
      // Not a broadcast packet, no delay, send immediately
      Scheduler::instance().schedule(target_, p, 0.);
    }
  }
}


void
AODV::sendRequest(nsaddr_t dst, u_int8_t flag) {
  // Allocate a RREQ packet 
  Packet *p = Packet::alloc();
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
  aodv_rt_entry *rt = rtable.rt_lookup(dst);
  assert(rt);
  
  /*
   * Rate limit sending of route requests. We are very conservative about
   * sending out route requests. 
   */
  if(rt->rt_flags == RTF_UP) {
    assert(rt->rt_hops != INFINITY2);
    Packet::free((Packet *)p);
    return;
  }
  
  if(rt->rt_req_timeout > CURRENT_TIME) {
    Packet::free((Packet *)p);
    return;
  }
  
  
  /* rt_req_cnt is the no. of times we did network-wide broadcast RREQ_RETRIES
     is the maximum number we will allow before going to a long timeout.
  */
  //==> I added the second condition to treat RREQ_Is differently!
  if((rt->rt_req_cnt > RREQ_RETRIES) && (flag != RREQ_IFLAG)) {
    rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
    rt->rt_req_cnt = 0;
    Packet *buf_pkt;
    while((buf_pkt = rqueue.deque(rt->rt_dst))) {
      drop(buf_pkt, DROP_RTR_NO_ROUTE);
    }
    Packet::free((Packet *)p);
    return;
  }
  
  //My modification**********************************************************//
  else if((rt->rt_req_cnt > RREQ_I_RETRIES) && (flag == RREQ_IFLAG)) {
    rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
    rt->rt_req_cnt = 0;
    Packet *buf_pkt;
    while((buf_pkt = rqueue.deque(rt->rt_dst))) {
      drop(buf_pkt, DROP_RTR_NO_ROUTE);
    }
    Packet::free((Packet *)p);
    return;
  }
  //*************************************************************************//
  
  //My modification**********************************************************//
  aodv_rt_entry *default_rt = rtable.rt_lookup(DEFAULT);
  if(default_rt && (default_rt->rt_flags == RTF_UP) && (rt->rt_req_cnt >= 1)) {
    /*
      If the destination is a MN that I have been communicated with before, but
      which now is unreachable - i.e. it is not in the transmission range of
      ANY mobile node in this ad hoc network.
      
      HACK!?
    */
    if(rt && rt->rt_seqno != 0) {
      rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
      rt->rt_req_cnt = 0;
      Packet *buf_pkt;
      int j = 0;
      while((buf_pkt = rqueue.deque(rt->rt_dst))) {
	++j;
	drop(buf_pkt, DROP_RTR_NO_ROUTE);
      }
      
      //For debugging
      if(j > 0) {
	fprintf(stderr, "\n===============================================\n");
	fprintf(stderr, "%d - UNREACHABLE MOBILE NODE %d! %d packets dropped "
		"at %f\n" , index, rt->rt_dst, j, CURRENT_TIME);
	fprintf(stderr, "===============================================\n\n");
      }

      Packet::free((Packet *)p);
      return;
    }
    
    /*
      Default Route exists. Network-wide search has been done once but no RREP
      received. Assume the destination node is a fixed node (FN) on Internet. 
      1. Update your route entry in the routing table to FN. 
      2. Send the packets in sendbuffer to FN, via GW.
      Future packets (see rt_resolve) should be sent to FN.
      Only intermediate nodes, that don't have any valid route to the 
      destination, will enter this else-if because the sender will
      enter else-if(ih->saddr()==index). 
      We should come here only once, after network-wide search (and if rt goes
      down?).
      
      NOTE! Don't mix *rt (entry to FN) and *default_rt (entry to Default 
      Route)!
    */
    
    //Update your route entry to FN...
    rt_update(rt, default_rt->rt_seqno, default_rt->rt_hops, DEFAULT, 
	      default_rt->rt_expire);
    
    //Send all packets queued in the sendbuffer
    double delay = 0.0;
    int j = 0;
    while((p = rqueue.deque(rt->rt_dst))) {
      // Delay them a little to help ARP. Otherwise ARP may drop packets.
      
      ++j;
      //==> I've changed "rt" to "find_send_entry(rt)".
      forward(find_send_entry(rt), p, delay);
      delay += ARP_DELAY;
    }
#ifdef DEBUG
    if(j > 0 && rt->rt_nexthop == DEFAULT) {
      fprintf(stderr,"%d - %d packet(s) destined to %d emptied from sendbuffer"
	      " at %f\n\tGW is %d (sendRequest)\n", index, j, rt->rt_dst, 
	      CURRENT_TIME, default_rt->rt_nexthop);
    }
    else if(j > 0) {
      fprintf(stderr,"%d - %d packet(s) destined to %d emptied from sendbuffer"
	      " at %f\n (sendRequest)\n", index, j, rt->rt_dst, CURRENT_TIME);
    }
#endif
    return;
  }
  //*************************************************************************//
  
  // Determine the TTL to be used this time. Dynamic TTL evaluation - SRD
  rt->rt_req_last_ttl = max(rt->rt_req_last_ttl, rt->rt_last_hop_count);
  
  if(0 == rt->rt_req_last_ttl) {
    // first time query broadcast
    ih->ttl_ = TTL_START;
  }
  else {
    // expanding ring search
    if(rt->rt_req_last_ttl < TTL_THRESHOLD)
      ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT;
    else {
      // network-wide broadcast
      ih->ttl_ = NETWORK_DIAMETER;
      rt->rt_req_cnt += 1;
    }
  }
  
  // remember the TTL used  for the next time
  rt->rt_req_last_ttl = ih->ttl_;
 
  // PerHopTime is the roundtrip time per hop for route requests.
  // The factor 2.0 is just to be safe .. SRD 5/22/99
  // Also note that we are making timeouts to be larger if we have 
  // done network wide broadcast before. 
  rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); 
  if(rt->rt_req_cnt > 0)
    rt->rt_req_timeout *= rt->rt_req_cnt;
  rt->rt_req_timeout += CURRENT_TIME;
  
  // Don't let the timeout to be too large, however .. SRD 6/8/99
  if(rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT)
    rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
  rt->rt_expire = 0;
  
#ifdef DEBUG
  if(flag==RREQ_IFLAG) {
    fprintf(stderr, 
	    "(%2d )\n%d - sending RREQ_I\t dst=%d\t timeout=%f s\t TTL=%d\n",
	    ++route_request, index, rt->rt_dst, rt->rt_req_timeout, ih->ttl_);
  }
  else {
    fprintf(stderr, 
	    "(%2d )\n%d - sending RREQ\t dst=%d\t timeout=%f s\t TTL=%d\n",
	    ++route_request, index, rt->rt_dst, rt->rt_req_timeout, ih->ttl_);
  }
#endif // DEBUG
  
  // Fill out the RREQ packet 
  // ch->uid() = 0;
  ch->ptype() = PT_AODV;
  ch->size() = IP_HDR_LEN + rq->size();
  ch->iface() = -2;
  ch->error() = 0;
  ch->addr_type() = NS_AF_NONE;
  ch->prev_hop_ = index;          // AODV hack
 
  ih->saddr() = index;
  ih->daddr() = IP_BROADCAST;
  ih->sport() = RT_PORT;
  ih->dport() = RT_PORT;
  
  // Fill up some more fields 
  rq->rq_type = AODVTYPE_RREQ;
  rq->rq_hop_count = 1;
  rq->rq_bcast_id = bid++;
  rq->rq_dst = dst;
  rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0);
  rq->rq_src = index;
  seqno += 2;
  assert ((seqno%2) == 0);
  rq->rq_src_seqno = seqno;
  rq->rq_timestamp = CURRENT_TIME;
  //My modification*******************//
  rq->rq_flags = flag;
  //**********************************//
  Scheduler::instance().schedule(target_, p, 0.);
}

void
AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
                u_int32_t rpseq, u_int32_t lifetime, double timestamp, 
		u_int8_t flag) {
  Packet *p = Packet::alloc();
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
  aodv_rt_entry *rt = rtable.rt_lookup(ipdst);
  assert(rt);
  
  rp->rp_type = AODVTYPE_RREP;
  //My modification*******************//
  rp->rp_flags = flag;
  //**********************************//
  rp->rp_hop_count = hop_count;
  rp->rp_dst = rpdst;
  rp->rp_dst_seqno = rpseq;
  //My modification*******************//
  //Bug fix from Riadh
  //rp->rp_src = index;
  rp->rp_src = ipdst;
  //**********************************//
  rp->rp_lifetime = lifetime;
  rp->rp_timestamp = timestamp;
  
  // ch->uid() = 0;
  ch->ptype() = PT_AODV;
  ch->size() = IP_HDR_LEN + rp->size();
  ch->iface() = -2;
  ch->error() = 0;
  ch->addr_type() = NS_AF_INET;
  ch->next_hop_ = rt->rt_nexthop;
  ch->prev_hop_ = index;          // AODV hack
  ch->direction() = hdr_cmn::DOWN;
  
  ih->saddr() = index;
  ih->daddr() = ipdst;
  ih->sport() = RT_PORT;
  ih->dport() = RT_PORT;
  ih->ttl_ = NETWORK_DIAMETER;
  
  //My modification**********************************************************//
  /*
    A mobile node (MN_S) that broadcasts a RREQ for another mobile node (MN_D)
    may receive both a RREP (from MN_D) and a RREP_I (from GW). If MN_D replies
    before GW, the RREP of MN_D can be dropped by ARP since ARP buffers only 
    one packet. Therefore, RREP_Is are delayed.
  */
  if(rp->rp_flags == RREP_IFLAG) {
    Scheduler::instance().schedule(target_, p, ARP_DELAY + 
				   0.001 * Random::uniform());
  }
  else {
    Scheduler::instance().schedule(target_, p, 0.);
  }
  //*************************************************************************//
}

void
AODV::sendError(Packet *p, bool jitter) {
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
  
  re->re_type = AODVTYPE_RERR;
  //re->reserved[0] = 0x00; re->reserved[1] = 0x00;
  // DestCount and list of unreachable destinations are already filled
  
  // ch->uid() = 0;
  ch->ptype() = PT_AODV;