aodv.cc

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

		}
		/*
		 * Got a new alternate disjoint path
		 */
		else if (rt0->new_disjoint_path(ih->src_, rq->rq_first_hop)) {
			if ( (rt0->rt_num_paths_ < aomdv_max_paths_) &&
		  	     (((rq->rq_hop_count+1)-rt0->path_get_min_hopcount()) <= aomdv_prim_alt_path_len_diff_)
			   ) {
     				reverse_path=rt0->path_insert(ih->src_, rq->rq_hop_count+1, CURRENT_TIME + REV_ROUTE_LIFE, rq->rq_first_hop);
				// CHANGE
				rt0->rt_last_hop_count = rt0->path_get_max_hopcount();
				// CHANGE
			}

			if (((rq->rq_hop_count+1)-rt0->path_get_min_hopcount()) > aomdv_prim_alt_path_len_diff_) {
				Packet::free(p);
				return;
			}
		}
		else if ( (rq->rq_dst == index) && 
			  ( ((erp=rt0->path_lookup_lasthop(rq->rq_first_hop))==NULL) ||
		  	    ((rq->rq_hop_count+1) > erp->hopcount)
		       	  )
		       	)  {
			Packet::free(p);
			return;
		}
	}
	else {
		Packet::free(p);
		return;
	}

	if (rt0->rt_flags == RTF_UP) {
		// 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.
 		 */
		Packet *buffered_pkt;
		while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) {
			if (rt0 && (rt0->rt_flags == RTF_UP)) {
				forward(rt0, buffered_pkt, NO_DELAY);
			}
		}
	}

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

	if (rq->rq_dst == index) {

		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
             	  	  ih->src_,    			// nexthop
             	  	  rq->rq_bcast_id,    		// broadcast id to identify this route discovery
			  ih->src_);			

		Packet::free(p);
	}
	else if ( rt &&
		  (rt->rt_flags == RTF_UP) &&
		  (rt->rt_seqno >= rq->rq_dst_seqno) ) {

		assert ((rt->rt_seqno%2) == 0);	// is the seqno even?

		if (reverse_path) {
#ifdef AOMDV_NODE_DISJOINT_PATHS
			if (b->count == 0) {
				b->count = 1;

				// route advertisement
   				if (rt->rt_advertised_hops == INFINITY) 
   					rt->rt_advertised_hops = rt->path_get_max_hopcount();

		  		AODV_Path *forward_path = rt->path_find();
				// CHANGE
				rt->rt_error = true;
				// CHANGE
   				sendReply(rq->rq_src,
       		 	          	  rt->rt_advertised_hops,
       		       		  	  rq->rq_dst,
       		       		  	  rt->rt_seqno,
       	        		  	  forward_path->expire - CURRENT_TIME,
       		  		  	  rq->rq_timestamp,
       		    		  	  ih->src_, 
       		    		  	  rq->rq_bcast_id,
				  	  forward_path->lasthop);
			}
#endif AOMDV_NODE_DISJOINT_PATHS
#ifdef AOMDV_LINK_DISJOINT_PATHS
		AODV_Path* forward_path = NULL;
		AODV_Path *r = rt->rt_path_list.lh_first;

			for(; r; r = r->path_link.le_next) {
				if (b->forward_path_lookup(r->nexthop, r->lasthop) == NULL) {
					forward_path = r;
					break;
				}
			}

			if ( forward_path &&
		    	     (b->reverse_path_lookup(reverse_path->nexthop, reverse_path->lasthop) == NULL) ) {
				b->reverse_path_insert(reverse_path->nexthop, reverse_path->lasthop);
				b->forward_path_insert(forward_path->nexthop, forward_path->lasthop);

   				// route advertisement
   				if (rt->rt_advertised_hops == INFINITY) 
   					rt->rt_advertised_hops = rt->path_get_max_hopcount();

				// CHANGE
				rt->rt_error = true;
				// CHANGE
				sendReply(rq->rq_src,
       	 		          	  rt->rt_advertised_hops,
       	      	  		  	  rq->rq_dst,
       	      	  		  	  rt->rt_seqno,
               	  		  	  forward_path->expire - CURRENT_TIME,
       	  	  		  	  rq->rq_timestamp,
       	  	  		  	  ih->src_, 
       	  	  		  	  rq->rq_bcast_id,
				  	  forward_path->lasthop);
			}
#endif AOMDV_LINK_DISJOINT_PATHS
		}
		Packet::free(p);
	}
	else {

		if (kill_request_propagation) {
		// do not propagate a duplicate RREQ
			Packet::free(p);
			return;
		}
		else {
			ih->src_ = index;

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

			// route advertisement
			if (rt0->rt_advertised_hops == INFINITY)
				rt0->rt_advertised_hops = rt0->path_get_max_hopcount();
			rq->rq_hop_count = rt0->rt_advertised_hops;
#ifdef AOMDV_NODE_DISJOINT_PATHS
			rq->rq_first_hop = (rt0->path_find())->lasthop;
#endif AOMDV_NODE_DISJOINT_PATHS

			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, 
		nsaddr_t nexthop, u_int32_t bcast_id, nsaddr_t rp_first_hop) {
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);

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

	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;
	rp->rp_bcast_id = bcast_id;
	rp->rp_first_hop = rp_first_hop;
	
	// 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_ = 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 *rt0, *rt;
BroadcastID* b = NULL;
AODV_Path* forward_path = NULL;

	if (rp->rp_dst == index) {
		Packet::free(p);
		return;
	} 

	rt = rtable.rt_lookup(rp->rp_dst);
 	if(rt == 0) {
		rt = rtable.rt_add(rp->rp_dst);
	}

	if (rt->rt_seqno < rp->rp_dst_seqno) {
     		rt->rt_seqno = rp->rp_dst_seqno;
		rt->rt_advertised_hops = INFINITY;
    		rt->path_delete();
     		rt->rt_flags = RTF_UP;
     		forward_path=rt->path_insert(rp->rp_src, rp->rp_hop_count+1, CURRENT_TIME + rp->rp_lifetime, rp->rp_first_hop);
		// CHANGE
		rt->rt_last_hop_count = rt->path_get_max_hopcount();
		// CHANGE
	}
	else if ( (rt->rt_seqno == rp->rp_dst_seqno) && 
		  (rt->rt_advertised_hops > rp->rp_hop_count) ) {

		assert (rt->rt_flags == RTF_UP);

		if ((forward_path=rt->disjoint_path_lookup(rp->rp_src, rp->rp_first_hop))) {
			assert (forward_path->hopcount == (rp->rp_hop_count+1));
			forward_path->expire = max(forward_path->expire, CURRENT_TIME + rp->rp_lifetime); 
		}
		else if ( rt->new_disjoint_path(rp->rp_src, rp->rp_first_hop) &&
		  	  (rt->rt_num_paths_ < aomdv_max_paths_) &&
		  	  ((rp->rp_hop_count+1)-rt->path_get_min_hopcount() <= aomdv_prim_alt_path_len_diff_)
			) {
     			forward_path=rt->path_insert(rp->rp_src, rp->rp_hop_count+1, CURRENT_TIME + rp->rp_lifetime, rp->rp_first_hop);
			// CHANGE
			rt->rt_last_hop_count = rt->path_get_max_hopcount();
			// CHANGE
		}
		else {
			Packet::free(p);
			return;
		}

	}
	else {
		Packet::free(p);
		return;
	}

	if (rt->rt_flags == RTF_UP) {
		// 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) {
		// I am the RREP destination

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

		/* 
		 * Find out whether any buffered packet can benefit from the 
 		 * forward route.
 		 */
		Packet *buffered_pkt;
		while ((buffered_pkt = rqueue.deque(rt->rt_dst))) {
			if (rt && (rt->rt_flags == RTF_UP)) {
				forward(rt, buffered_pkt, NO_DELAY);
			}
		}

	}

	if (ih->dst_ == index) {
		Packet::free(p);
		return;
	}

	rt0 = rtable.rt_lookup(ih->dst_);
	b=id_lookup(ih->dst_, rp->rp_bcast_id);

#ifdef AOMDV_NODE_DISJOINT_PATHS
	if ( (rt0 == NULL) || (rt0->rt_flags != RTF_UP) || (b == NULL) || (b->count) ) {
		Packet::free(p);
		return;
	}

	b->count = 1;
	AODV_Path *reverse_path = rt0->path_find();

       	ch->addr_type() = AF_INET;
	ch->next_hop_ = reverse_path->nexthop;
   	ch->xmit_failure_ = aodv_rt_failed_callback;
     	ch->xmit_failure_data_ = (void*) this;

     	// route advertisement
     	rp->rp_src = index;
     	if (rt->rt_advertised_hops == INFINITY)
     		rt->rt_advertised_hops = rt->path_get_max_hopcount();
     	rp->rp_hop_count = rt->rt_advertised_hops;
	rp->rp_first_hop = (rt->path_find())->lasthop;

     	reverse_path->expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT;

	// CHANGE
	rt->rt_error = true;
	// CHANGE
	Scheduler::instance().schedule(target_, p, 0.);
#endif AOMDV_NODE_DISJOINT_PATHS
#ifdef AOMDV_LINK_DISJOINT_PATHS
	if ( (rt0 == NULL) || (rt0->rt_flags != RTF_UP) || (b == NULL) ) {
		Packet::free(p);
		return;
	}

AODV_Path* reverse_path = NULL;
AODV_Path *r = rt0->rt_path_list.lh_first;
	for(; r; r = r->path_link.le_next) {
  		if (b->reverse_path_lookup(r->nexthop, r->lasthop) == NULL) {
			reverse_path = r;
			break;
		}
	}

	if ( reverse_path &&
	     (b->forward_path_lookup(forward_path->nexthop, forward_path->lasthop) == NULL) ) {
		assert (forward_path->nexthop == rp->rp_src);
		assert (forward_path->lasthop == rp->rp_first_hop);

		b->reverse_path_insert(reverse_path->nexthop, reverse_path->lasthop);
		b->forward_path_insert(forward_path->nexthop, forward_path->lasthop);

          	ch->addr_type() = AF_INET;
		ch->next_hop_ = reverse_path->nexthop;
   		ch->xmit_failure_ = aodv_rt_failed_callback;
     		ch->xmit_failure_data_ = (void*) this;

     		// route advertisement
     		if (rt->rt_advertised_hops == INFINITY)
     			rt->rt_advertised_hops = rt->path_get_max_hopcount();
     		rp->rp_hop_count = rt->rt_advertised_hops;
     		rp->rp_src = index;

     		reverse_path->expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT;

		// CHANGE
		rt->rt_error = true;
		// CHANGE
		Scheduler::instance().schedule(target_, p, 0.);
	}
	else {
		Packet::free(p);
		return;
	}
#endif AOMDV_LINK_DISJOINT_PATHS
}

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

#ifdef DEBUG
fprintf(stderr, "%s: multipath version\n", __FUNCTION__);
#endif // DEBUG

 re->DestCount = 0;
 for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
 AODV_Path* path;
   rtn = rt->rt_link.le_next; 
   if ((rt->rt_flags == RTF_UP) && (path=rt->path_lookup(id)) ) {
     assert((rt->rt_seqno%2) == 0);

     rt->path_delete(id);
     if (rt->path_empty()) {
     	rt->rt_seqno++;
	rt->rt_seqno = max(rt->rt_seqno, rt->rt_highest_seqno_heard);
     	// 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], id);
#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.
   */

#ifdef DEBUG
fprintf(stderr, "%s: multipath version\n", __FUNCTION__);
#endif // DEBUG

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

  assert (rt->rt_seqno%2); // is the seqno odd?
  rt->rt_flags = RTF_DOWN;
  rt->rt_advertised_hops = INFINITY;
  rt->path_delete();
  rt->rt_expire = 0;

} /* rt_down function */

void
AODV::recvError(Packet *p) {
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
aodv_rt_entry *rt;
u_int8_t i;
Packet *rerr = Packet::alloc();
struct hdr_aodv_error *nre = HDR_AODV_ERROR(rerr);

#ifdef DEBUG
fprintf(stderr, "%s: multipath version\n", __FUNCTION__);
#endif // DEBUG


 nre->DestCount = 0;

 for (i=0; i<re->DestCount; i++) {
 // For each unreachable destination
 AODV_Path* path;
   rt = rtable.rt_lookup(re->unreachable_dst[i]);

   if ( rt && (rt->rt_flags == RTF_UP) &&
       	(path=rt->path_lookup(ih->src_)) &&
     	(rt->rt_seqno <= re->unreachable_dst_seqno[i]) ) {
	assert((rt->rt_seqno%2) == 0); // is the seqno even?
#ifdef DEBUG
     fprintf(stderr, "%s(%f): %d\t(%d\t%u\t%d)\t(%d\t%u\t%d)\n",
		     __FUNCTION__,CURRENT_TIME,
		     index, rt->rt_dst, rt->rt_seqno, ih->src_,
		     re->unreachable_dst[i],re->unreachable_dst_seqno[i],
		     ih->src_);
#endif // DEBUG

     	rt->path_delete(ih->src_);
	rt->rt_highest_seqno_heard = max(rt->rt_highest_seqno_heard, re->unreachable_dst_seqno[i]);
	if (rt->path_empty()) {
     		rt->rt_seqno = rt->rt_highest_seqno_heard;
     		rt_down(rt);
		// CHANGE
		if (rt->rt_error) {
     			nre->unreachable_dst[nre->DestCount] = rt->rt_dst;
     			nre->unreachable_dst_seqno[nre->DestCount] = rt->rt_seqno;
     			nre->DestCount += 1;
			rt->rt_error = false;
		}
		// CHANGE
	}
   }
 } 

 if (nre->DestCount > 0) {
#ifdef DEBUG
   fprintf(stderr, "%s(%f): %d\t sending RERR...\n", __FUNCTION__, CURRENT_TIME, index);
#endif // DEBUG
   sendError(rerr);
 }
 else {
   Packet::free(rerr);
 }

 Packet::free(p);
}
#endif AOMDV