aodv.cc

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

aodv_rt_failed_callback(Packet *p, void *arg) {
  ((AODV*) arg)->rt_ll_failed(p);
}

/*
 * This routine is invoked when the link-layer reports a route failed.
 */
void
AODV::rt_ll_failed(Packet *p) {
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  aodv_rt_entry *rt;
  nsaddr_t broken_nbr = ch->next_hop_;
  
  //print_routing_table();
  
#ifndef AODV_LINK_LAYER_DETECTION
  drop(p, DROP_RTR_MAC_CALLBACK);
#else 
  
  /*
   * Non-data packets and Broadcast Packets can be dropped.
   */
  if(! DATA_PACKET(ch->ptype()) || (u_int32_t) ih->daddr() == IP_BROADCAST) {
    drop(p, DROP_RTR_MAC_CALLBACK);
    return;
  }
  log_link_broke(p);
  if((rt = rtable.rt_lookup(ih->daddr())) == 0) {
    drop(p, DROP_RTR_MAC_CALLBACK);
    return;
  }
  log_link_del(ch->next_hop_);
  
  
#ifdef AODV_LOCAL_REPAIR
  /* if the broken link is closer to the dest than source, 
     attempt a local repair. Otherwise, bring down the route. */
  if(ch->num_forwards() > rt->rt_hops) {
    local_rt_repair(rt, p); // local repair
    // retrieve all the packets in the ifq using this link,
    // queue the packets for which local repair is done, 
    return;
  }
  else
#endif // LOCAL REPAIR	
    {
      drop(p, DROP_RTR_MAC_CALLBACK);
      // Do the same thing for other packets in the interface queue using the
      // broken link -Mahesh
      while((p = ifqueue->filter(broken_nbr))) {
	drop(p, DROP_RTR_MAC_CALLBACK);
      }
      nb_delete(broken_nbr);
    }
  
#endif // LINK LAYER DETECTION
}

void
AODV::handle_link_failure(nsaddr_t id) {
  aodv_rt_entry *rt, *rtn;
  Packet *rerr = Packet::alloc();
  struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);
  
  //My modification********************************************//
  /*
    I added some conditions to the if statement below.
  */
  nsaddr_t send_rt_nexthop = 0;
  aodv_rt_entry *fn_rt = find_fn_entry();
  aodv_rt_entry *send_rt;
  if(fn_rt) {
    send_rt = find_send_entry(fn_rt);
  }    
  if(send_rt) {
    send_rt_nexthop = send_rt->rt_nexthop;
  }
  //***********************************************************//
  
  re->DestCount = 0;
  for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
    rtn = rt->rt_link.le_next;
    //My modification
    if(((rt->rt_hops != INFINITY2) && (rt->rt_nexthop == id))
       || (rt->rt_dst == DEFAULT && rt->rt_hops != INFINITY2 && 
	   send_rt_nexthop == id) ) {
      assert (rt->rt_flags == RTF_UP);
      assert((rt->rt_seqno%2) == 0);
      rt->rt_seqno++;
      re->unreachable_dst[re->DestCount] = rt->rt_dst;
      re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno;
#ifdef DEBUG
      fprintf(stderr, "%d - Can't reach next hop=%d, dest=%d\n", index, 
	      rt->rt_nexthop, re->unreachable_dst[re->DestCount]);
#endif // DEBUG
      re->DestCount += 1;
      rt_down(rt);
    } /*if*/
    // remove the lost neighbor from all the precursor lists
    rt->pc_delete(id);
  } /*for*/
  
  if(re->DestCount > 0) {
#ifdef DEBUG
    fprintf(stderr, "%d - sending RERR at %f s\n", index, CURRENT_TIME);
#endif // DEBUG
    sendError(rerr, false);
  }
  else {
    Packet::free(rerr);
  }
}

void
AODV::local_rt_repair(aodv_rt_entry *rt, Packet *p) {
#ifdef DEBUG
  fprintf(stderr,"%s: Dst - %d\n", __FUNCTION__, rt->rt_dst); 
#endif
  
  //My modification**********************************************************//
  /*
    draft-ietf-manet-aodv-13.txt, section 6.12:
    "To repair the link break, the node increments the sequence number for the
    destination and then broadcasts a RREQ for that destination."
  */
  rt->rt_seqno += 1;
  //*************************************************************************//
  
  // Buffer the packet 
  rqueue.enque(p);
  // mark the route as under repair 
  rt->rt_flags = RTF_IN_REPAIR;
  sendRequest(rt->rt_dst, 0x00);
  // set up a timer interrupt
  Scheduler::instance().schedule(&lrtimer, p->copy(), rt->rt_req_timeout);
}

void
AODV::rt_update(aodv_rt_entry *rt, u_int32_t seqnum, u_int16_t metric,
	       	nsaddr_t nexthop, double expire_time) {
  rt->rt_seqno = seqnum;
  rt->rt_hops = metric;
  rt->rt_flags = RTF_UP;
  rt->rt_nexthop = nexthop;
  rt->rt_expire = expire_time;
  //print_routing_table();
}

void
AODV::rt_down(aodv_rt_entry *rt) {
  /*
   *  Make sure that you don't "down" a route more than once.
   */

  if(rt->rt_flags == RTF_DOWN) {
    return;
  }

  // assert (rt->rt_seqno%2); // is the seqno odd?
  rt->rt_last_hop_count = rt->rt_hops;
  rt->rt_hops = INFINITY2;
  rt->rt_flags = RTF_DOWN;
  rt->rt_nexthop = 0;
  rt->rt_expire = 0;
} /* rt_down function */



/* =====================================================================
   Route Handling Functions
   ===================================================================== */
//My modification************************************************************//
/*
  This function prints the routing table.
*/
void
AODV::print_routing_table() {
  aodv_rt_entry *my_rt;
  int i=1; 
  printf("Routing Table for %d\n",index);
  for(my_rt = rtable.head(); my_rt; my_rt = my_rt->rt_link.le_next) {  
    printf("%d) rt_dst=%d rt_nexthop=%d rt_hops=%d rt_seqno=%d rt_expire=%f "
	   "rt_flags=%u\n", i++,my_rt->rt_dst,my_rt->rt_nexthop,
	   my_rt->rt_hops,my_rt->rt_seqno,my_rt->rt_expire,my_rt->rt_flags);
  }
}
//***************************************************************************//


//My modification************************************************************//
/*
  This function finds the route entry that the packet(s) can be sent to.
  
  Example of a routing table for a mobile node (MN3) with address 1.0.3:
  Assume that 1.0.0 is the address of the gateway (GW), 1.0.2 is the 
  address of a mobile node (MN2) and 0.0.1 is the address of a fixed node (FN).
  Assume further that MN3 wants to communicate with FN. The next hop of FN is 
  "Default". The functions looks for "Default" and finds that the next hop for 
  "Default" is 1.0.0 and finally it finds that the next hop to 1.0.0 is 1.0.2.
  Hence, the packet(s) are sent to address 1.0.2 (MN2).
  
  Destination          Next hop
  0.0.1                Default
  Default              1.0.0
  1.0.0                1.0.2
*/

aodv_rt_entry*
AODV::find_send_entry(aodv_rt_entry *rt) {
  /*
    Return if the destination is not a fixed node. All the things below this 
    if statement should be done only when the destination is a fixed node.
  */
  if(rt->rt_nexthop != DEFAULT) {
    return rt;
  }
  
  aodv_rt_entry *default_rt = rtable.rt_lookup(DEFAULT);
  aodv_rt_entry *temp_rt = rtable.rt_lookup(default_rt->rt_nexthop);
  
  if(default_rt && temp_rt && default_rt->rt_flags == RTF_UP && 
     temp_rt->rt_flags == RTF_UP && temp_rt->rt_dst == temp_rt->rt_nexthop) {
    return temp_rt;
  }
  else if(default_rt && temp_rt && default_rt->rt_flags == RTF_UP && 
	  temp_rt->rt_flags == RTF_UP) {
    return temp_rt;
  }
  else if(default_rt->rt_flags != RTF_UP) {
    return default_rt;
  }
  else if(temp_rt->rt_flags != RTF_UP) {
    return temp_rt;
  }
  else {
    fprintf(stderr, "\n\n\n!!! aodv.cc ERROR !!!\n\n\n");
    return rt;
  }
}


aodv_rt_entry*
AODV::find_fn_entry() {
  aodv_rt_entry *rt = rtable.head();
  for(; rt; rt = rt->rt_link.le_next) {  // for each rt entry
    if(rt->rt_nexthop == DEFAULT) {
      break;
    }
  }
  return rt;
}
//***************************************************************************//


void
AODV::rt_resolve(Packet *p) {
  struct hdr_cmn *ch = HDR_CMN(p);
  struct hdr_ip *ih = HDR_IP(p);
  aodv_rt_entry *rt;
  
  //==> An entry to the default route...
  aodv_rt_entry *default_rt = rtable.rt_lookup(DEFAULT);
  
  /*
   * Set the transmit failure callback. That won't change.
   */
  ch->xmit_failure_ = aodv_rt_failed_callback;
  ch->xmit_failure_data_ = (void*) this;
  
  rt = rtable.rt_lookup(ih->daddr());
  
  //My modification**********************************************************//
  /*
    Internet connection broken...
  */
  if(rt && (rt->rt_nexthop == DEFAULT) && 
     find_send_entry(rt)->rt_flags != RTF_UP && index == ih->saddr()) {
    
    aodv_rt_entry *ALL_GW_rt = rtable.rt_lookup(ALL_MANET_GW_MULTICAST);
    if(ALL_GW_rt == 0) {
      rtable.rt_add(ALL_MANET_GW_MULTICAST);
    }
    rqueue.enque(p);
    sendRequest(ALL_MANET_GW_MULTICAST, RREQ_IFLAG);
    return;
  }
  //*************************************************************************//
  
  if(rt == 0) {
    rt = rtable.rt_add(ih->daddr());
  }
  
  /*
   * 1. If the route is up, forward the packet.
   *
   * My modification
   * I added the second condition: MN_S sends packets to MN_I which forwards 
   * them to GW. Then link between MN_I and GW breaks. MN_I broadcasts RERR 
   * which should be received by MN_S but the RERR is dropped due to collision.
   * MN_S keeps sending packets to MN_I, which must send another RERR because
   * it can't forward the packets. Since routes to fixed nodes don't go down 
   * (this should be changed later) MN_I must check that the route to the 
   * nexthop is up before trying to forward the packet!
   */
  if(rt->rt_flags == RTF_UP && find_send_entry(rt)->rt_flags == RTF_UP) {
    assert(rt->rt_hops != INFINITY2);
    //==> I've changed "rt" to "find_send_entry(rt)".
    forward(find_send_entry(rt), p, NO_DELAY);
  }
  /*
   * 2. If I am the source of the packet, then do a route request.
   */
  else if(ih->saddr() == index) {
    rqueue.enque(p);
    sendRequest(rt->rt_dst, 0x00);
  }
  //My modification**********************************************************//
  /*
   * 3. If valid default route exists, update route (to fixed node) and forward
   * the packet.
   *
   * Maybe we should have the condition "rt->rt_nexthop==DEFAULT"?
   */
  else if(default_rt && (default_rt->rt_flags == RTF_UP) && 
	  rt->rt_flags != RTF_IN_REPAIR && rt->rt_seqno == 0) {
    /*
      Valid 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. Forward these "future" packets 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). 
      
      Condition 3 guarantees that this function works correct also when local 
      repair is used.
      Condition 4 guarantees that this route is created recently so a MN does
      not enter this 'else if' statement although it shouldn't (e.g. when a 
      valid default route exists and this MN is trying to forward a packet to 
      another MN and the route to that MN went down recently). 
      
      NOTE! Don't mix *rt (entry to FN) and *default_rt (entry to Default 
      Route)!
    */
    rt_update(rt, default_rt->rt_seqno, default_rt->rt_hops, DEFAULT, 
	      default_rt->rt_expire);
    
    //Forward the packet to FN...
    //==> I've changed "rt" to "find_send_entry(rt)".
    forward(find_send_entry(rt), p, NO_DELAY);
  }
  
  /*
   * 4. I am trying to forward a packet for someone else to whom I don't have
   *    a route, but I'm GW ==> send RREQ. 
   */
  else if(index == thisnode->base_stn()) {
    /*
      I am trying to forward a packet for someone else to whom I don't have a
      route. But since I'm GW and I'm forwarding it means that this packet is 
      from a fixed node. So broadcast a RREQ if there is no route to the 
      destination.
    */
    rqueue.enque(p);
    sendRequest(rt->rt_dst, 0x00); 
  }
  //*************************************************************************//
  /*
   * 5. A local repair is in progress. Buffer the packet. 
   */
  else if(rt->rt_flags == RTF_IN_REPAIR) {
    rqueue.enque(p);
  }
  /*
   * 6. I am trying to forward a packet for someone else to whom I don't have
   *    a route.
   */
  else {
    Packet *rerr = Packet::alloc();
    struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);
    /* 
     * For now, drop the packet and send error upstream.
     * Now the route errors are broadcast to upstream
     * neighbors - Mahesh 09/11/99
     */	
    
    //My modification*****************************************//
    /*
      Unreachable destination is not FN, but DEFAULT...
      May be changed later...
    */
    if(rt->rt_nexthop == DEFAULT && find_send_entry(rt)->rt_flags != RTF_UP) {
      assert(find_send_entry(rt)->rt_flags == RTF_DOWN);
      re->DestCount = 0;
      re->unreachable_dst[re->DestCount] = thisnode->base_stn();
      re->unreachable_dst_seqno[re->DestCount] = find_send_entry(rt)->rt_seqno;
      re->DestCount += 1;
    }
    else {
      //*******************************************************//
      assert (rt->rt_flags == RTF_DOWN);
      re->DestCount = 0;