aodv.cc

在Linux下做的QuadTree的程序

/* 
   aodv.cc
   $Id: aodv.cc,v 1.1.1.1 2000/08/28 18:40:10 jinyang 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 DEBUG
static 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
   ===================================================================== */
void
BroadcastTimer::handle(Event*)
{
        agent->id_purge();

        Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);
}

void
HelloTimer::handle(Event*)
{
        agent->sendHello();

        double interval = MinHelloInterval +
                ((MaxHelloInterval - MinHelloInterval) * Random::uniform());

        assert(interval >= 0);

        Scheduler::instance().schedule(this, &intr, interval);
}

void
NeighborTimer::handle(Event*)
{
        agent->nb_purge();

        Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL);
}

void
RouteCacheTimer::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;
}

int
AODV::command(int argc, const char*const* argv)
{
        if(argc == 2) {
                Tcl& tcl = Tcl::instance();

                if(strcasecmp(argv[1], "id") == 0) {
                        tcl.resultf("%d", index);
                        return TCL_OK;
                }
                if(strcasecmp(argv[1], "start") == 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
   ===================================================================== */
void
AODV::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.
 */
void
AODV::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.
 */
void
AODV::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
   ===================================================================== */
void
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);
}


u_int32_t
AODV::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;
}


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

/* ================================================================= */

static void
aodv_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.
 */
void
AODV::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_);
        }
#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 */
}


void
AODV::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->prq_get_nexthop(rt->rt_nexthop))) {
                        // XXX - this should probably a rt_resolve(p);
                        Packet::free(p);
                }
        }
}


void
AODV::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);
        }
}


void
AODV::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
   ===================================================================== */
void
AODV::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);
}