/*    aodv.cc   $Id: aodv.cc,v 1.29 1998/11/19 06:23:16 dmaltz Exp $   */#include <cmu/aodv/aodv.h>#include <cmu/aodv/aodv_packet.h>#include <ip.h>#include <random.h>#include <cmu/cmu-trace.h>#define CURRENT_TIME    Scheduler::instance().clock()// #define DEBUG#ifdef DEBUGstatic int extra_route_reply = 0;static int limit_route_request = 0;static int route_request = 0;#endif/* ======================================================================   TCL Hooks   ====================================================================== */static class AODVHeaderClass : public PacketHeaderClass {public:        AODVHeaderClass() : PacketHeaderClass("PacketHeader/AODV",                                              AODV_HDR_LEN) { } } class_rtProtoAODV_hdr;static class AODVclass : public TclClass {public:        AODVclass() : TclClass("Agent/rtProto/AODV") {}        TclObject* create(int argc, const char*const* argv) {                assert(argc == 5);                return (new AODV((nsaddr_t) atoi(argv[4])));        }} class_rtProtoAODV;/* =====================================================================   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();        Scheduler::instance().schedule(this, &intr, 1 /* 60 */);}/* ===================================================================== *//* ===================================================================== */AODV::AODV(nsaddr_t id) : Agent(PT_AODV),        btimer(this), htimer(this), ntimer(this), rtimer(this), rqueue(){        bind("off_AODV_", &off_AODV_);                        index = id;        seqno = 1;        bid = 1;        LIST_INIT(&nbhead);        LIST_INIT(&bihead);        logtarget = 0;        ifqueue = 0;}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                        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) {                        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);}/* =====================================================================   Neighbor Management Functions   ===================================================================== */voidAODV::nb_insert(nsaddr_t id){        Neighbor *nb = new Neighbor(id);        assert(nb);        nb->nb_expire = CURRENT_TIME +                (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);        LIST_INSERT_HEAD(&nbhead, nb, nb_link);        seqno += 1;             // set of neighbors changed}Neighbor*AODV::nb_lookup(nsaddr_t id){        Neighbor *nb = nbhead.lh_first;        for(; nb; nb = nb->nb_link.le_next) {                if(nb->nb_addr == id)                        break;        }        return nb;}/* * Called when we receive *explicit* notification that a Neighbor * is no longer reachable. */voidAODV::nb_delete(nsaddr_t id){        Neighbor *nb = nbhead.lh_first;        rt_entry *rt;        log_link_del(id);        seqno += 1;     // Set of neighbors changed        for(; nb; nb = nb->nb_link.le_next) {                if(nb->nb_addr == id) {                        LIST_REMOVE(nb,nb_link);                        delete nb;                        break;                }        }        for(rt = rtable.head(); rt; rt = rt->rt_link.le_next) {                if(rt->rt_nexthop == id) {                        rt_down(rt);                }        }}/* * Purges all timed-out Neighbor Entries - runs every * HELLO_INTERVAL * 1.5 seconds. */voidAODV::nb_purge(){        Neighbor *nb = nbhead.lh_first;        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);                }        }}/* =====================================================================   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);}u_int32_tAODV::id_lookup(nsaddr_t id){        BroadcastID *b = bihead.lh_first;        for( ; b; b = b->link.le_next) {                if(b->src == id)                        return b->id;        }        return ID_NOT_FOUND;}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;                }        }}/* ================================================================= */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){#ifndef AODV_LINK_LAYER_DETECTION        drop(p, DROP_RTR_MAC_CALLBACK);#else        struct hdr_cmn *ch = HDR_CMN(p);        struct hdr_ip *ih = HDR_IP(p);        rt_entry *rt;        /*         * Non-data packets and Broadcast Packets can be dropped.         */        if(! DATA_PACKET(ch->ptype()) ||           (u_int32_t) ih->dst_ == IP_BROADCAST) {                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;        }#ifdef AODV_USE_LL_METRIC#ifdef AODV_USE_GOD_FEEDBACK        if(rt->rt_flags & RTF_UP &&           God::instance()->hops(index, ch->next_hop_) != 1) {#else        if(CURRENT_TIME - rt->rt_error_time > MAX_RT_ERROR_TIME)                rt->rt_errors = 0;        if(rt->rt_errors == 0)                rt->rt_error_time = CURRENT_TIME;        rt->rt_errors += 1;        if(rt->rt_flags & RTF_UP && rt->rt_errors == MAX_RT_ERROR) {#endif /* AODV_USE_GOD_FEEDBACK */#endif /* AODV_USE_LL_METRIC */                log_link_del(ch->next_hop_);                rt_down(rt);#ifdef AODV_USE_LL_METRIC        }        else {                log_link_kept(ch->next_hop_, ch->xmit_reason_);        }#endif        /*         * Try sending this packet back down through the protocol stack.         * This will result in another Route Request being issued.         */        rt_resolve(p);#endif /* AODV_LINK_LAYER_DETECTION */}voidAODV::rt_down(rt_entry *rt){        /*         *  Make sure that you don't "down" a route more than once.         */        if((rt->rt_flags & RTF_UP) == 0) {                return;        }        /*         *  As I Send Triggered Replies to my upstream neighbor's,         *  I promptly forget about them so that I don't repeat these         *  "route errors" many times.         *         *  I have seen cases where two nodes each throught that the other         *  was upstream.  This should avoid this problem.         */        {                Neighbor *nb = rt->rt_nblist.lh_first;                Neighbor *nbn;                for( ; nb; nb = nbn) {                        nbn = nb->nb_link.le_next;                        sendTriggeredReply(nb->nb_addr,                                           rt->rt_dst,                                           rt->rt_seqno);                        LIST_REMOVE(nb, nb_link);                        delete nb;                }        }        rt->rt_flags &= ~RTF_UP;        rt->rt_expire = CURRENT_TIME + BAD_LINK_LIFETIME;	/*	 *  Now purge the Network Interface queues that	 *  may have packets destined for this broken	 *  neighbor.	 */        {                Packet *p;                while((p = ifqueue->filter(rt->rt_nexthop))) {                        // XXX - this should probably a rt_resolve(p);                        Packet::free(p);                }        }}voidAODV::rt_resolve(Packet *p){        struct hdr_cmn *ch = HDR_CMN(p);        struct hdr_ip *ih = HDR_IP(p);        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->dst_);        if(rt == 0) {                rt = rtable.rt_add(ih->dst_);        }        if(rt->rt_flags & RTF_UP) {                forward(rt, p, 0 /* No Jitter */);        }        /*         *  If I am the source of the packet, then do a Route Request.         *  Otherwise, generate a Route Error.         */        else if(ih->src_ == index) {                rqueue.enque(p);                sendRequest(rt->rt_dst);        }        /*         * I am trying to forward a packet for someone else to which         * I don't have a route.         */        else {                /*                 *  Since the route is not up, I only need to notify                 *  the node from which I received this packet.                 */                sendTriggeredReply(ch->prev_hop_,                                   rt->rt_dst,                                   rt->rt_seqno);                Packet::free(p);        }}voidAODV::rt_purge(){        rt_entry *rt, *rtn;        double now = CURRENT_TIME;	        for(rt = rtable.head(); rt; rt = rtn) {                rtn = rt->rt_link.le_next;                if(rt->rt_expire <= now) {                        Packet *p;                        while((p = rqueue.deque(rt->rt_dst))) {#ifdef DEBUG                                fprintf(stderr, "%s: calling drop()\n",                                        __FUNCTION__);#endif                                drop(p, DROP_RTR_QTIMEOUT);                        }                        LIST_REMOVE(rt, rt_link);                        delete rt;                }        }}/* =====================================================================   Packet Reception Routines   ===================================================================== */voidAODV::recv(Packet *p, Handler*){        struct hdr_cmn *ch = HDR_CMN(p);        struct hdr_ip *ih = HDR_IP(p);        assert(initialized());        assert(p->incoming == 0);        if(ch->ptype() == PT_AODV) {                ih->ttl_ -= 1;                recvAODV(p);                return;        }        /*         *  Must be a packet I'm originating...         */        if(ih->src_ == index && ch->num_forwards() == 0) {                /*                 * Add the IP Header                 */                ch->size() += IP_HDR_LEN;                ih->ttl_ = IP_DEF_TTL;        }        /*         *  I received a packet that I sent.  Probably         *  a routing loop.         */        else if(ih->src_ == index) {                drop(p, DROP_RTR_ROUTE_LOOP);                return;        }        /*         *  Packet I'm forwarding...         */        else {                /*                 *  Check the TTL.  If it is zero, then discard.                 */                if(--ih->ttl_ == 0) {                        drop(p, DROP_RTR_TTL);                        return;                }        }        rt_resolve(p);}