aodv.cc

一个无线自组网aodv路由的扩展版---AOMDV（多径路由协议）。

 	seqno += 2;
 	assert ((seqno%2) == 0);
 	rq->rq_src_seqno = seqno;

 	rq->rq_timestamp = CURRENT_TIME;

 	Scheduler::instance().schedule(target_, p, 0.);
}

double
AODV::PerHopTime(aodv_rt_entry *rt) {
int num_non_zero = 0, i;
double total_latency = 0.0;

 if (!rt)
   return ((double) NODE_TRAVERSAL_TIME );
	
 for (i=0; i < MAX_HISTORY; i++) {
   if (rt->rt_disc_latency[i] > 0.0) {
      num_non_zero++;
      total_latency += rt->rt_disc_latency[i];
   }
 }
 if (num_non_zero > 0)
   return(total_latency / (double) num_non_zero);
 else
   return((double) NODE_TRAVERSAL_TIME);

}

#ifndef AOMDV
void
AODV::recvRequest(Packet *p) {
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
aodv_rt_entry *rt;

  /*
   * Drop if:
   *      - I'm the source
   *      - I recently heard this request.
   */

  if(rq->rq_src == index) {
#ifdef DEBUG
    fprintf(stderr, "%s: got my own REQUEST\n", __FUNCTION__);
#endif // DEBUG
    Packet::free(p);
    return;
  } 

 if (id_lookup(rq->rq_src,rq->rq_bcast_id)) {

#ifdef DEBUG
   fprintf(stderr, "%s: discarding request\n", __FUNCTION__);
#endif // DEBUG
 
   Packet::free(p);
   return;
 }

 /*
  * Cache the broadcast ID
  */
 id_insert(rq->rq_src, rq->rq_bcast_id);

 /* 
  * We are either going to forward the REQUEST or generate a
  * REPLY. Before we do anything, we make sure that the REVERSE
  * route is in the route table.
  */
 aodv_rt_entry *rt0; // rt0 is the reverse route 
   
   rt0 = rtable.rt_lookup(rq->rq_src);
   if(rt0 == 0) { /* if not in the route table */
   // create an entry for the reverse route.
     rt0 = rtable.rt_add(rq->rq_src);
   }
  
   if ( (rq->rq_src_seqno > rt0->rt_seqno ) ||
    	((rq->rq_src_seqno == rt0->rt_seqno) && 
	 (rq->rq_hop_count < rt0->rt_hops)) ) {

   // If we have a fresher seq no. or lesser #hops for the 
   // same seq no., update the rt entry. Else don't bother.
     rt_update(rt0, rq->rq_src_seqno, rq->rq_hop_count+1, ih->src_,
     	       max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)) );

     // Reset the soft state
     rt0->rt_req_timeout = 0.0; 
     rt0->rt_req_last_ttl = 0;
     rt0->rt_req_cnt = 0;

     /* Find out whether any buffered packet can benefit from the 
      * reverse route.
      */
     assert (rt0->rt_flags == RTF_UP);
     Packet *buffered_pkt;
     while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) {
       if (rt0 && (rt0->rt_flags == RTF_UP)) {
	 assert(rt0->rt_hops != INFINITY);
         forward(rt0, buffered_pkt, NO_DELAY);
       }
     }
   } 
   // End for putting reverse route in rt table

 /*
  * We have taken care of the reverse route stuff.
  * Now see whether we can send a route reply. 
  */

 rt = rtable.rt_lookup(rq->rq_dst);

 // First check if I am the destination ..

 if(rq->rq_dst == index) {

#ifdef DEBUG
   fprintf(stderr, "%d - %s: destination sending reply\n",
                   index, __FUNCTION__);
#endif // DEBUG

               
   // Just to be safe, I use the max. Somebody may have
   // incremented the dst seqno.
   if (seqno < rq->rq_dst_seqno)
  	seqno = max(seqno, rq->rq_dst_seqno)+1;
   if (seqno%2) seqno++;

   sendReply(rq->rq_src,           // IP Destination
             0,                    // Hop Count
             index,                // Dest IP Address
             seqno,                // Dest Sequence Num
             MY_ROUTE_TIMEOUT,     // Lifetime
             rq->rq_timestamp);    // timestamp

   Packet::free(p);
 }

 // I am not the destination, but I may have a fresh enough route.

 else if (rt && (rt->rt_hops != INFINITY) && 
	  	(rt->rt_seqno >= rq->rq_dst_seqno) ) {

   assert (rt->rt_flags == RTF_UP);
   assert(rq->rq_dst == rt->rt_dst);
   assert ((rt->rt_seqno%2) == 0);	// is the seqno even?

   // CHANGE
   rt->rt_error = true;	
   // CHANGE
   sendReply(rq->rq_src,
             rt->rt_hops,
             rq->rq_dst,
             rt->rt_seqno,
             rt->rt_expire - CURRENT_TIME,
             rq->rq_timestamp);

   Packet::free(p);
 }
 /*
  * Can't reply. So forward the  Route Request
  */
 else {
   ih->src_ = index;
   ih->dst_ = IP_BROADCAST;

   rq->rq_hop_count += 1;

   // Maximum sequence number seen en route
   if (rt) rq->rq_dst_seqno = max(rt->rt_seqno, rq->rq_dst_seqno);

   forward((aodv_rt_entry*) 0, p, DELAY);
 }

}

void
AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
                u_int32_t rpseq, u_int32_t lifetime, double timestamp) {
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);

#ifdef DEBUG
fprintf(stderr, "sending Reply from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG
 assert(rt);

 rp->rp_type = AODVTYPE_RREP;
 //rp->rp_flags = 0x00;
 rp->rp_hop_count = hop_count;
 rp->rp_dst = rpdst;
 rp->rp_dst_seqno = rpseq;
 rp->rp_src = index;
 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() = AF_INET;

 ch->next_hop_ = rt->rt_nexthop;

 ch->xmit_failure_ = aodv_rt_failed_callback;
 ch->xmit_failure_data_ = (void*) this;

 ih->src_ = index;
 ih->dst_ = ipdst;
 ih->sport_ = RT_PORT;
 ih->dport_ = RT_PORT;
 ih->ttl_ = NETWORK_DIAMETER;

 Scheduler::instance().schedule(target_, p, 0.);
}

void
AODV::recvReply(Packet *p) {
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;
char suppress_reply = 0;
double delay = 0.0;
	
#ifdef DEBUG
 fprintf(stderr, "%d - %s: received a REPLY\n", index, __FUNCTION__);
#endif // DEBUG

 /*
  *  Got a reply. So reset the "soft state" maintained for 
  *  route requests in the request table. We don't really have
  *  have a separate request table. It is just a part of the
  *  routing table itself. 
  */
 // Note that rp_dst is the dest of the data packets, not the
 // the dest of the reply, which is the src of the data packets.

        
 rt = rtable.rt_lookup(rp->rp_dst);
 /*
  *  If I don't have a rt entry to this host... adding
  */
 if(rt == 0) {
   rt = rtable.rt_add(rp->rp_dst);
 }

 /*
  * Add a forward route table entry... here I am following 
  * Perkins-Royer AODV paper almost literally - SRD 5/99
  */

 if ( (rt->rt_seqno < rp->rp_dst_seqno) ||   // newer route 
      ((rt->rt_seqno == rp->rp_dst_seqno) &&  
       (rt->rt_hops > rp->rp_hop_count)) ) { // shorter or better route
	
  // Update the rt entry 
  rt_update(rt, rp->rp_dst_seqno, rp->rp_hop_count+1,
		rp->rp_src, max(rt->rt_expire, (CURRENT_TIME + rp->rp_lifetime)));

  // reset the soft state
  rt->rt_req_timeout = 0.0; 
  rt->rt_req_last_ttl = 0;
  rt->rt_req_cnt = 0;
  
  if (ih->dst_ == index) { // If I am the original source
  // Update the route discovery latency statistics
  // rp->rp_timestamp is the time of request origination
		
#ifdef DYNAMIC_RREQ_RETRY_TIMEOUT
  if (rp->rp_type == AODVTYPE_RREP) {
    rt->rt_disc_latency[rt->hist_indx] = (CURRENT_TIME - rp->rp_timestamp)
                                         / (double) (rp->rp_hop_count+1);
    // increment indx for next time
    rt->hist_indx = (rt->hist_indx + 1) % MAX_HISTORY;
  }
#endif DYNAMIC_RREQ_RETRY_TIMEOUT
  }	

  /*
   * Send all packets queued in the sendbuffer destined for
   * this destination. 
   */
  Packet *buf_pkt;
  while((buf_pkt = rqueue.deque(rt->rt_dst))) {
    if(rt->rt_hops != INFINITY) {
      assert (rt->rt_flags == RTF_UP);
      forward(rt, buf_pkt, NO_DELAY);
    // Delay them a little to help ARP. Otherwise ARP 
    // may drop packets. -SRD 5/23/99
      // delay += ARP_DELAY;
    }
  }
 }
 else if (rt->rt_flags != RTF_UP) {
 // do not send a reply unless there is a forward path
  suppress_reply = 1;
 }

	
 /*
  * If reply is for me, discard it.
  */

 if(ih->dst_ == index || suppress_reply) {
   Packet::free(p);
 }
 /*
  * Otherwise, forward the Route Reply.
  */
 else {

 // Find the rt entry
   aodv_rt_entry *rt0 = rtable.rt_lookup(ih->dst_);
   // If the rt is up, forward
   if(rt0 && (rt0->rt_hops != INFINITY)) {
     assert (rt0->rt_flags == RTF_UP);
     rp->rp_hop_count += 1;
     rp->rp_src = index;

     // CHANGE
     rt->rt_error = true;	
     // CHANGE
     forward(rt0, p, NO_DELAY);
   }
   else {
   // I don't know how to forward .. drop the reply. 
#ifdef DEBUG
     fprintf(stderr, "%s: droping Route Reply\n", __FUNCTION__);
#endif // DEBUG
     drop(p, DROP_RTR_NO_ROUTE);
   }
 }
}

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;
}

#endif AOMDV

/*
 * Route maintenance
 */

/*
  Link Failure Management Functions
*/

/*
 * 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);
nsaddr_t broken_nbr = ch->next_hop_;

#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->dst_ == IP_BROADCAST) ||
  //     (broken_nbr == 0) ) {
  //  drop(p, DROP_RTR_MAC_CALLBACK);
  //  return;
  //}

 /*
  * Broadcast Packets can be dropped.
  */
  if ( ((u_int32_t) ih->dst_ == IP_BROADCAST) ||
       (broken_nbr == 0) ) {
    drop(p, DROP_RTR_MAC_CALLBACK);
    return;
  }

  log_link_broke(p);

  /*
  if((rt = rtable.rt_lookup(ih->dst_)) == 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	

  {

    handle_link_failure(broken_nbr);

#ifdef AOMDV_PACKET_SALVAGING

    if ( !DATA_PACKET(ch->ptype()) ) drop(p, DROP_RTR_MAC_CALLBACK);
    else {
    // salvage the packet using an alternate path if available.
    aodv_rt_entry *rt = rtable.rt_lookup(ih->dst_);
    	if ( rt && (rt->rt_flags == RTF_UP) && (ch->aomdv_salvage_count_ < AOMDV_MAX_SALVAGE_COUNT) ) {
		ch->aomdv_salvage_count_ += 1;
	       	forward(rt, p, NO_DELAY);
	}
	else drop(p, DROP_RTR_MAC_CALLBACK);
    }
    while((p = ifqueue->prq_get_nexthop(broken_nbr))) {
    struct hdr_cmn *ch = HDR_CMN(p);
    struct hdr_ip *ih = HDR_IP(p);
    	if ( !DATA_PACKET(ch->ptype()) ) drop(p, DROP_RTR_MAC_CALLBACK);
    	else {
    	// salvage the packet using an alternate path if available.
    	aodv_rt_entry *rt = rtable.rt_lookup(ih->dst_);
    		if ( rt && (rt->rt_flags == RTF_UP) && (ch->aomdv_salvage_count_ < AOMDV_MAX_SALVAGE_COUNT) ) {
			ch->aomdv_salvage_count_ += 1;
		       	forward(rt, p, NO_DELAY);
		}
		else drop(p, DROP_RTR_MAC_CALLBACK);
	}
    }	

#else // NO PACKET SALVAGING

    drop(p, DROP_RTR_MAC_CALLBACK);
    while((p = ifqueue->prq_get_nexthop(broken_nbr))) {
    	drop(p, DROP_RTR_MAC_CALLBACK);
    }	

#endif // NO PACKET SALVAGING

  }

#endif // LINK LAYER DETECTION
}

#ifndef AOMDV

void
AODV::handle_link_failure(nsaddr_t id, bool error=true) {

aodv_rt_entry *rt, *rtn;
Packet *rerr = Packet::alloc();
struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);

 re->DestCount = 0;
 for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
   rtn = rt->rt_link.le_next; 
   if ((rt->rt_hops != INFINITY) && (rt->rt_nexthop == id) ) {
     assert (rt->rt_flags == RTF_UP);
     assert((rt->rt_seqno%2) == 0);
     rt->rt_seqno++;
     // CHANGE
     if (rt->rt_error) {
     	re->unreachable_dst[re->DestCount] = rt->rt_dst;
     	re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno;
#ifdef DEBUG
     fprintf(stderr, "%s(%f): %d\t(%d\t%u\t%d)\n", __FUNCTION__, CURRENT_TIME,
		     index, re->unreachable_dst[re->DestCount],
		     re->unreachable_dst_seqno[re->DestCount], rt->rt_nexthop);
#endif // DEBUG
     	re->DestCount += 1;
	rt->rt_error = false;
     }
     // CHANGE
     rt_down(rt);
   }
 }   

 if ( (re->DestCount > 0) && (error) ) {
#ifdef DEBUG
   fprintf(stdout, "%s(%f): %d\tsending RERR...\n", __FUNCTION__, CURRENT_TIME, index);
#endif // DEBUG
   sendError(rerr, false);
 }
 else {
   Packet::free(rerr);
 }
}

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 = INFINITY;
  rt->rt_flags = RTF_DOWN;
  rt->rt_nexthop = 0;