aodv.cc

fso antenna model for ns2

/*
Copyright (c) 1997, 1998 Carnegie Mellon University.  All Rights
Reserved. 

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

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 DEBUG
static 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;


int
AODV::command(int argc, const char*const* argv) {
	Tcl& tcl = Tcl::instance();
	if(argc == 2)
	{
		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;
		}
		else if (strcmp(argv[1], "port-dmux") == 0) {
			dmux_ = (PortClassifier *)TclObject::lookup(argv[2]);
			if (dmux_ == 0) {
				fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__,
					argv[1], argv[2]);
				return TCL_ERROR;
			}
			return TCL_OK;
		}
		else if (strcmp(argv[1], "target") == 0) {
			if (*argv[2] == '0') {
				target_ = 0;
				return (TCL_OK);
			}
			NsObject * temp = (NsObject*)TclObject::lookup(argv[2]);
			//Remove this
			target_ = temp;
			 
			if (target_ == 0) {
				tcl.resultf("no such object %s", argv[2]);
				return (TCL_ERROR);
			}
			Target *t = new Target(*temp);
			assert(t);
			LIST_INSERT_HEAD(&targethead, t, link_);
			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);
	LIST_INIT(&targethead);

	logtarget = 0;
	ifqueue = 0;
}

/*
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();
#define FREQUENCY 0.5 // sec
	Scheduler::instance().schedule(this, &intr, FREQUENCY);
}

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->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
*/


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

/* SRD */
bool
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 true;     
	}
	return false;
}

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

/*
Helper Functions
*/

double
AODV::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 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) {
	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 -Mahesh
			while((p = ifqueue->filter(broken_nbr))) {
				drop(p, DROP_RTR_MAC_CALLBACK);
			}	
			nb_delete(broken_nbr);
		}

#endif // LINK LAYER DETECTION
}

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

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

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

void
AODV::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
*/

void
AODV::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.
	*/
	else if(ih->saddr() == index) {