aodv.cc

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

  rt->rt_expire = 0;

} /* rt_down function */

#endif AOMDV

void
AODV::sendError(Packet *p, bool jitter = true) {
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
    
#ifdef DEBUG
fprintf(stderr, "sending Error from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 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;
 ch->size() = IP_HDR_LEN + re->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = AF_NONE;
 ch->next_hop_ = 0;

 ih->src_ = index;
 ih->dst_ = IP_BROADCAST;
 ih->sport_ = RT_PORT;
 ih->dport_ = RT_PORT;
 ih->ttl_ = 1;

 // Do we need any jitter? Yes
 if (jitter)
 	Scheduler::instance().schedule(target_, p, 0.01*Random::uniform());
 else
 	Scheduler::instance().schedule(target_, p, 0.0);

}

#ifndef AOMDV
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);

 nre->DestCount = 0;

 for (i=0; i<re->DestCount; i++) {
 // For each unreachable destination
   rt = rtable.rt_lookup(re->unreachable_dst[i]);
   if ( rt && (rt->rt_hops != INFINITY) &&
       	(rt->rt_nexthop == ih->src_) &&
     	(rt->rt_seqno <= re->unreachable_dst_seqno[i]) ) {
	assert(rt->rt_flags == RTF_UP);
	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, rt->rt_nexthop,
		     re->unreachable_dst[i],re->unreachable_dst_seqno[i],
		     ih->src_);
#endif // DEBUG
     	rt->rt_seqno = re->unreachable_dst_seqno[i];
     	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

void
RouteCacheTimer::handle(Event*) {
  agent->rt_purge();
#define FREQUENCY 0.05 // sec
  Scheduler::instance().schedule(this, &intr, FREQUENCY + FREQUENCY*Random::uniform());
}

void
AODV::rt_purge() {
aodv_rt_entry *rt, *rtn;
double delay = 0.0;
Packet *p;

 for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
   rtn = rt->rt_link.le_next;

#ifndef AOMDV

double now = CURRENT_TIME;

   if ((rt->rt_flags == RTF_UP) && (rt->rt_expire < now)) {
   // if a valid route has expired, purge all packets from 
   // send buffer and invalidate the route.
                    
     while((p = rqueue.deque(rt->rt_dst))) {
#ifdef DEBUG
       fprintf(stderr, "%s: calling drop()\n",
                       __FUNCTION__);
#endif // DEBUG
       drop(p, DROP_RTR_RTEXPIRE);
     }
     rt->rt_seqno++;
     assert (rt->rt_seqno%2);
     rt_down(rt);
   }

#else // AOMDV

   if (rt->rt_flags == RTF_UP) {
	   rt->path_purge();
	   if (rt->path_empty()) {
     		while((p = rqueue.deque(rt->rt_dst))) {
       			drop(p, DROP_RTR_RTEXPIRE);
     		}
     		rt->rt_seqno++;
		rt->rt_seqno = max(rt->rt_seqno, rt->rt_highest_seqno_heard);
     		if (rt->rt_seqno%2 == 0) rt->rt_seqno += 1;
     		// assert (rt->rt_seqno%2);
     		rt_down(rt);
	   }
   }

#endif // AOMDV

   if (rt->rt_flags == RTF_UP) {
   // If the route is not expired,
   // and there are packets in the sendbuffer waiting,
   // forward them. This should not be needed, but this extra 
   // check does no harm.
     while((p = rqueue.deque(rt->rt_dst))) {
       forward (rt, p, NO_DELAY);
       // delay += ARP_DELAY;
     }
   } 
   else if (rqueue.find(rt->rt_dst))
     sendRequest(rt->rt_dst); 
   // CHANGE
   //else if (rt->rt_req_timeout > 0.0)
   // CHANGE
   // If the route is down and 
   // if there is a packet for this destination waiting in
   // the sendbuffer, then send out route request. sendRequest
   // will check whether it is time to really send out request
   // or not.
   // This may not be crucial to do it here, as each generated 
   // packet will do a sendRequest anyway.
 }

}

/*
   Broadcast ID Management  Functions
*/

void
BroadcastTimer::handle(Event*) {
  agent->id_purge();
  Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);
}

BroadcastID*
AODV::id_insert(nsaddr_t id, u_int32_t bid) {
BroadcastID *b = new BroadcastID(id, bid);

 assert(b);
 b->expire = CURRENT_TIME + BCAST_ID_SAVE;
 LIST_INSERT_HEAD(&bihead, b, link);
 return b;
}

/* SRD */
BroadcastID*
AODV::id_lookup(nsaddr_t id, u_int32_t bid) {
BroadcastID *b = bihead.lh_first;
 
 // Search the list for a match of source and bid
 for( ; b; b = b->link.le_next) {
   if ((b->src == id) && (b->id == bid) ) {
     return b;     
   }
 }
 return NULL;
}

void
AODV::id_purge() {
BroadcastID *b = bihead.lh_first;
BroadcastID *bn;
double now = CURRENT_TIME;

 for(; b; b = bn) {
   bn = b->link.le_next;
   if(b->expire <= now) {
     LIST_REMOVE(b,link);
     delete b;
   }
 }
}

void
AODV::id_delete(nsaddr_t id, u_int32_t bid) {
BroadcastID *b = bihead.lh_first;
BroadcastID *bn;

 for(; b; b = bn) {
   bn = b->link.le_next;
   if ((b->src == id) && (b->id == bid)) {
     LIST_REMOVE(b,link);
     delete b;
   }
 }
}


/*
  Helper Functions
*/


void
LocalRepairTimer::handle(Event* p)  {  // SRD: 5/4/99
aodv_rt_entry *rt;
struct hdr_ip *ih = HDR_IP( (Packet *)p);

   /* you get here after the timeout in a local repair attempt */
   /*	fprintf(stderr, "%s\n", __FUNCTION__); */

    rt = agent->rtable.rt_lookup(ih->dst_);
	
    if (rt && rt->rt_flags != RTF_UP) {
    // route is yet to be repaired
    // I will be conservative and bring down the route
    // and send route errors upstream.
    /* The following assert fails, not sure why */
    /* assert (rt->rt_flags == RTF_IN_REPAIR); */
		
      //rt->rt_seqno++;
      agent->rt_down(rt);
      // send RERR
    /* 
      printf("Node %d: Dst - %d, failed local repair\n",index, rt->rt_dst);
    */
    }
    Packet::free((Packet *)p);
}

void
AODV::local_rt_repair(aodv_rt_entry *rt, Packet *p) {
  // fprintf(stderr,"%s: Dst - %d\n", __FUNCTION__, rt->rt_dst); 
  
  // Buffer the packet 
  rqueue.enque(p);

  // mark the route as under repair 
  rt->rt_flags = RTF_IN_REPAIR;

  sendRequest(rt->rt_dst);

  // set up a timer interrupt
  Scheduler::instance().schedule(&lrtimer, p->copy(), rt->rt_req_timeout);
}

/*
   Neighbor Management Functions
*/

void
HelloTimer::handle(Event*) {
   agent->sendHello();
   // CHANGE
   double interval = HELLO_INTERVAL + 0.01*Random::uniform();
   /*
   double interval = MinHelloInterval + 
                 ((MaxHelloInterval - MinHelloInterval) * Random::uniform());
		 */
   assert(interval >= 0);
   Scheduler::instance().schedule(this, &intr, interval);
}

void
AODV::sendHello() {
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_reply *rh = HDR_AODV_REPLY(p);

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

 rh->rp_type = AODVTYPE_HELLO;
 //rh->rp_flags = 0x00;
 rh->rp_hop_count = 0;
 rh->rp_dst = index;
 rh->rp_dst_seqno = seqno;
 rh->rp_lifetime = ALLOWED_HELLO_LOSS * HELLO_INTERVAL;

 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rh->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = AF_NONE;

 ih->src_ = index;
 ih->dst_ = IP_BROADCAST;
 ih->sport_ = RT_PORT;
 ih->dport_ = RT_PORT;
 ih->ttl_ = 1;

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


void
AODV::recvHello(Packet *p) {
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
AODV_Neighbor *nb;

 nb = nb_insert(rp->rp_dst);

 // CHANGE
 // Add a route to this neighbor
 ih->dst_ = index;
 rp->rp_src = ih->src_;
#ifdef AOMDV
 rp->rp_first_hop = index;
#endif // AOMDV
 recvReply(p);
 // CHANGE

 //Packet::free(p);
}

AODV_Neighbor*
AODV::nb_insert(nsaddr_t id) {
AODV_Neighbor *nb;

 if ( ( nb=nb_lookup(id) ) == NULL) {
 	nb = new AODV_Neighbor(id);
 	assert(nb);
	// CHANGE
 	nb->nb_expire = CURRENT_TIME + (HELLO_INTERVAL * ALLOWED_HELLO_LOSS);

 	LIST_INSERT_HEAD(&nbhead, nb, nb_link);
 }
 else {
	// CHANGE
 	nb->nb_expire = CURRENT_TIME + (HELLO_INTERVAL * ALLOWED_HELLO_LOSS);
 }

 return nb;
}

AODV_Neighbor*
AODV::nb_lookup(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) return nb;
 }
 return NULL;
}


/*
 * Called when we receive *explicit* notification that a Neighbor
 * is no longer reachable.
 */
void
AODV::nb_delete(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 log_link_del(id);

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) {
     LIST_REMOVE(nb,nb_link);
     delete nb;
     break;
   }
 }

Packet *p;

   handle_link_failure(id);

#ifdef AOMDV_PACKET_SALVAGING
    while((p = ifqueue->prq_get_nexthop(id))) {
    struct hdr_cmn *ch = HDR_CMN(p);
    struct hdr_ip *ih = HDR_IP(p);

    	if ( !DATA_PACKET(ch->ptype()) ) drop(p, DROP_RTR_HELLO);
    	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_HELLO);
	}
    }	

#else // NO PACKET SALVAGING

    while((p = ifqueue->prq_get_nexthop(id))) {
     drop(p, DROP_RTR_HELLO);
    }	

#endif // NO PACKET SALVAGING
}

void
NeighborTimer::handle(Event*) {
  agent->nb_purge();
// CHANGE
  Scheduler::instance().schedule(this, &intr, 0.05);
}


/*
 * Purges all timed-out Neighbor Entries - runs every
 * HELLO_INTERVAL * 1.5 seconds.
 */
void
AODV::nb_purge() {
AODV_Neighbor *nb = nbhead.lh_first;
AODV_Neighbor *nbn;
double now = CURRENT_TIME;

 for(; nb; nb = nbn) {
   nbn = nb->nb_link.le_next;
   if(nb->nb_expire <= now) {
     nb_delete(nb->nb_addr);
   }
 }

}

#ifdef 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 *rt0, *rt;
BroadcastID* b = NULL;
bool kill_request_propagation=false;
AODV_Path* reverse_path=NULL;

	if(rq->rq_src == index) {
		Packet::free(p);
		return;
	} 

	if ( (b=id_lookup(rq->rq_src, rq->rq_bcast_id)) == NULL)  {
	// Cache the broadcast ID
    		b=id_insert(rq->rq_src, rq->rq_bcast_id);
	}
	else kill_request_propagation = true;

	if (rq->rq_hop_count == 0) rq->rq_first_hop = index;

	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);
	}
  
	/*
	 * Create/update reverse path
	 */
	if (rt0->rt_seqno < rq->rq_src_seqno) {
     		rt0->rt_seqno = rq->rq_src_seqno;
		rt0->rt_advertised_hops = INFINITY;
    		rt0->path_delete();
     		rt0->rt_flags = RTF_UP;
     		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
	}
	else if ( (rt0->rt_seqno == rq->rq_src_seqno) &&
		  (rt0->rt_advertised_hops > rq->rq_hop_count)
		) {
	AODV_Path* erp=NULL;

		assert(rt0->rt_flags == RTF_UP);

		/*
		 * Path already exists
		 */
		if ((reverse_path=rt0->disjoint_path_lookup(ih->src_, rq->rq_first_hop))) {
			assert(reverse_path->hopcount == (rq->rq_hop_count+1));
			reverse_path->expire = max(reverse_path->expire, (CURRENT_TIME + REV_ROUTE_LIFE));