/*Copyright (c) 1997, 1998 Carnegie Mellon University.  All RightsReserved. Permission to use, copy, modify, and distribute thissoftware and its documentation is hereby granted (including forcommercial or for-profit use), provided that both the copyright notice and this permission notice appear in all copies of the software, derivative works, or modified versions, and any portions thereof, and that both notices appear in supporting documentation, and that credit is given to Carnegie Mellon University in all publications reporting on direct or indirect use of this code or its derivatives.ALL CODE, SOFTWARE, PROTOCOLS, AND ARCHITECTURES DEVELOPED BY THE CMUMONARCH PROJECT ARE EXPERIMENTAL AND ARE KNOWN TO HAVE BUGS, SOME OFWHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THISSOFTWARE OR OTHER INTELLECTUAL PROPERTY IN ITS ``AS IS'' CONDITION,AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULARPURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITYBE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, ORCONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OFSUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; ORBUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCEOR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE ORINTELLECTUAL PROPERTY, EVEN IF ADVISED OF THE POSSIBILITY OF SUCHDAMAGE.Carnegie Mellon encourages (but does not require) users of thissoftware or intellectual property to return any improvements orextensions that they make, and to grant Carnegie Mellon the rights to redistribute these changes without encumbrance.The AODV code developed by the CMU/MONARCH group was optimized and tuned by Samir Das and Mahesh Marina, University of Cincinnati. The work was partially done in Sun Microsystems. Modified for gratuitous replies by Anant Utgikar, 09/16/02.*///#include <ip.h>#include <aodv/aodv.h>#include <aodv/aodv_packet.h>#include <random.h>#include <cmu-trace.h>//#include <energy-model.h>#define max(a,b)        ( (a) > (b) ? (a) : (b) )#define CURRENT_TIME    Scheduler::instance().clock()//#define DEBUG//#define ERROR#ifdef DEBUGstatic int extra_route_reply = 0;static int limit_route_request = 0;static int route_request = 0;#endif/*  TCL Hooks*/int hdr_aodv::offset_;static class AODVHeaderClass : public PacketHeaderClass {public:        AODVHeaderClass() : PacketHeaderClass("PacketHeader/AODV",                                              sizeof(hdr_all_aodv)) {	  bind_offset(&hdr_aodv::offset_);	} } class_rtProtoAODV_hdr;static class AODVclass : public TclClass {public:        AODVclass() : TclClass("Agent/AODV") {}        TclObject* create(int argc, const char*const* argv) {          assert(argc == 5);          //return (new AODV((nsaddr_t) atoi(argv[4])));	  return (new AODV((nsaddr_t) Address::instance().str2addr(argv[4])));        }} class_rtProtoAODV;intAODV::command(int argc, const char*const* argv) {  if(argc == 2) {  Tcl& tcl = Tcl::instance();        if(strncasecmp(argv[1], "id", 2) == 0) {      tcl.resultf("%d", index);      return TCL_OK;    }        if(strncasecmp(argv[1], "start", 2) == 0) {      btimer.handle((Event*) 0);#ifndef AODV_LINK_LAYER_DETECTION      htimer.handle((Event*) 0);      ntimer.handle((Event*) 0);#endif // LINK LAYER DETECTION      rtimer.handle((Event*) 0);      return TCL_OK;     }                 }  else if(argc == 3) {    if(strcmp(argv[1], "index") == 0) {      index = atoi(argv[2]);      return TCL_OK;    }    else if(strcmp(argv[1], "log-target") == 0 || strcmp(argv[1], "tracetarget") == 0) {      logtarget = (Trace*) TclObject::lookup(argv[2]);      if(logtarget == 0)	return TCL_ERROR;      return TCL_OK;    }    else if(strcmp(argv[1], "drop-target") == 0) {    int stat = rqueue.command(argc,argv);      if (stat != TCL_OK) return stat;      return Agent::command(argc, argv);    }    else if(strcmp(argv[1], "if-queue") == 0) {    ifqueue = (PriQueue*) TclObject::lookup(argv[2]);            if(ifqueue == 0)	return TCL_ERROR;      return TCL_OK;    }  }  return Agent::command(argc, argv);}/*    Constructor*/AODV::AODV(nsaddr_t id) : Agent(PT_AODV),			  btimer(this), htimer(this), ntimer(this), 			  rtimer(this), lrtimer(this), rqueue() {                   index = id;  seqno = 2;  bid = 1;  LIST_INIT(&nbhead);  LIST_INIT(&bihead);  logtarget = 0;  ifqueue = 0;}/*  Timers*/voidBroadcastTimer::handle(Event*) {  agent->id_purge();  Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);}voidHelloTimer::handle(Event*) {   agent->sendHello();   double interval = MinHelloInterval +                  ((MaxHelloInterval - MinHelloInterval) * Random::uniform());   assert(interval >= 0);   Scheduler::instance().schedule(this, &intr, interval);}voidNeighborTimer::handle(Event*) {  agent->nb_purge();  Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL);}voidRouteCacheTimer::handle(Event*) {  agent->rt_purge();#define FREQUENCY 0.5 // sec  Scheduler::instance().schedule(this, &intr, FREQUENCY);}voidLocalRepairTimer::handle(Event* p)  {  // SRD: 5/4/99aodv_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->daddr());	    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#ifdef DEBUG      fprintf(stderr,"Node %d: Dst - %d, failed local repair\n",index, rt->rt_dst);#endif          }    Packet::free((Packet *)p);}/*   Broadcast ID Management  Functions*/voidAODV::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);}/* SRD */boolAODV::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 true;      } return false;}voidAODV::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;   } }}/*  Helper Functions*/doubleAODV::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);}/*  Link Failure Management Functions*/static voidaodv_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. */voidAODV::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_;#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 -Maheshwhile((p = ifqueue->filter(broken_nbr))) {     drop(p, DROP_RTR_MAC_CALLBACK);    }	    nb_delete(broken_nbr);  }#endif // LINK LAYER DETECTION}voidAODV::handle_link_failure(nsaddr_t id) {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 != INFINITY2) && (rt->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, "%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_down(rt);   }   // remove the lost neighbor from all the precursor lists   rt->pc_delete(id); }    if (re->DestCount > 0) {#ifdef DEBUG   fprintf(stderr, "%s(%f): %d\tsending RERR...\n", __FUNCTION__, CURRENT_TIME, index);#endif // DEBUG   sendError(rerr, false); } else {   Packet::free(rerr); }}voidAODV::local_rt_repair(aodv_rt_entry *rt, Packet *p) {#ifdef DEBUG  fprintf(stderr,"%s: Dst - %d\n", __FUNCTION__, rt->rt_dst); #endif    // 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);}voidAODV::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;}voidAODV::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*/voidAODV::rt_resolve(Packet *p) {struct hdr_cmn *ch = HDR_CMN(p);struct hdr_ip *ih = HDR_IP(p);aodv_rt_entry *rt; /*  *  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()); if(rt == 0) {	  rt = rtable.rt_add(ih->daddr()); } /*  * If the route is up, forward the packet   */	 if(rt->rt_flags == RTF_UP) {   assert(rt->rt_hops != INFINITY2);   forward(rt, p, NO_DELAY); } /*  *  if I am the source of the packet, then do a Route Request.