aodv.java

AODV protocol in tcl simulated in JSim

// @(#)AODV.java   12/2003
// Copyright (c) 1998-2003, Distributed Real-time Computing Lab (DRCL) 
// 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. Neither the name of "DRCL" nor the names of its contributors may be used
//    to endorse or promote products derived from this software without specific
//    prior written permission. 
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 REGENTS OR CONTRIBUTORS 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.
// 

package drcl.inet.protocol.aodv;

import java.util.*;
import drcl.inet.core.*;
import drcl.comp.*;
import drcl.data.*;
import drcl.net.*;
import drcl.inet.*;
import drcl.inet.contract.*;
import drcl.inet.data.*;
import drcl.inet.protocol.*;

/* Bug Fix for inconsistency of RT 
 * Be careful about the expire time setting. We need to keep consistency btw RT and AODV RT.
 * Whenever calling set_expire() or rt_update or refer to rt.rt_expire,
 * we also need to update the RTEntry in RT using addRTEntry.*/

/**
 * AODV.java: the main part of AODV protocols. 
 * The software is refered to:
 * 1. AODV Draft (version. 11)
 * 2. AODV class in ns-2.
 * In ns-2, 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. 
 *  
 * @author Wei-peng Chen 
 */
public class AODV extends drcl.inet.protocol.Routing implements UnicastRouting, ActiveComponent
{
	public String getName()
	{ return "aodv"; }

	public static boolean debug = false;
	public static boolean debug2 = false;

	/* AODV packet types */
	protected static final int AODVTYPE_RREQ  = 1;
	protected static final int AODVTYPE_RREP  = 2;
	protected static final int AODVTYPE_RERR  = 3;
	protected static final int AODVTYPE_RREP_ACK = 4;
	protected static final int AODVTYPE_HELLO = 5;

	/**************************************************************************************/
	/* configuration parameters, the following value are suggested in Sec. 9 */
	final static double	ACTIVE_ROUTE_TIMEOUT	= 30.0; // 50 seconds
	final static int	ALLOWED_HELLO_LOSS	= 3;  /* packets */
	final static double	ARP_DELAY		= 0.01; /* fixed delay to keep arp happy */
	final static double	DELAY			= 1.0; /* fixed delay to keep arp happy */
	final static int	BAD_LINK_LIFETIME	= 3; /* 3000 ms */
	final static int	BCAST_ID_SAVE		= 6; /* 3 seconds */
	final static double	HELLO_INTERVAL		= 1.0;  /* 1000 ms */
	final static double	MaxHelloInterval	= 1.25 * HELLO_INTERVAL;  /* 1250 ms */
	final static double	MinHelloInterval	= 0.75 * HELLO_INTERVAL;  /* 750 ms */
	// This should be somewhat related to arp timeout
	final static double	LOCAL_REPAIR_WAIT_TIME	= 0.15; //sec
	// timeout after doing network-wide search RREQ_RETRIES times
	final static int	MAX_RREQ_TIMEOUT	= 10; //sec
	final static double	MY_ROUTE_TIMEOUT	= 30.0; // 100 seconds
	final static double	NODE_TRAVERSAL_TIME	= 0.03; // 30 ms
	/* Should be set by the user using best guess (conservative) */
	final static int	NETWORK_DIAMETER = 35; // 35 hops
	// Must be larger than the time difference between a node propagates a route 
	// request and gets the route reply back.
	final static int	RREP_WAIT_TIME		= 1;  // sec
	final static int	REV_ROUTE_LIFE		= 6;	// 5  seconds
	/* No. of times to do network-wide search before timing out for MAX_RREQ_TIMEOUT sec.*/ 
	final static int	RREQ_RETRIES = 3;  
	/* Various constants used for the expanding ring search */
	final static int	TTL_START = 1;
	final static int	TTL_INCREMENT = 2;
	final static int	TTL_THRESHOLD = 7;

	final static double	ROUTE_CACHE_FREQUENCY = 0.5; // sec
	/* The maximum number of packets that we allow a routing protocol to buffer.*/
	final static int	AODV_RTQ_MAX_LEN		= 64; // packets
	/* The maximum period of time that a routing protocol is allowed to buffer a packet for.*/
	final static int	AODV_RTQ_TIMEOUT     = 30; // seconds
	static final String[] PKT_TYPES = { "NULL", "RREQ", "RREP", "RERR", "RREP_ACK", "HELLO" };

	final static long CONTROL_PKT_TYPE = drcl.inet.InetPacket.CONTROL; // for ToS field

	/* seed setting from dcript */
    	static java.util.Random rand = new java.util.Random(7777);
    
	/** AODV router ID of this node */
	protected int	router_id = Integer.MAX_VALUE;

	protected int		seqno ;	/* initial value = 2 */
	private int		bid ;	/* broadcast id */

	private boolean	AODV_link_layer_detection = false;

	boolean routePurgeEnabled = true;
	
	//////////////////////////////////////////////////////////////////////////////
	// Inner Class
	/** AODV_BroadcastID.java
	 * 
	 * @author Wei-peng Chen
	 * @see AODV 
	 */
	class AODV_BroadcastID
	{	
		public long	src;
		public int	id;		
		public double expire; // now + BCAST_ID_SAVE s
	
		/**
		 * Constructor
		 * @param ospf_: backward OSPF reference
		 */
		AODV_BroadcastID(long src_) { src = src_; }		
		AODV_BroadcastID(long src_, int id_) { src = src_; id = id_;  }
	}

	class AODV_Buffered_pkt 
	{
		protected InetPacket 	ipkt;
		protected double	expire;
		
		AODV_Buffered_pkt(InetPacket ipkt_, double expire_) {
			ipkt = (InetPacket) ipkt_.clone();
			expire = expire_;
		}
	}
		
	//////////////////////////////////////////////////////////////////////////////
	// List variables
	
	/** BroadcastID List */
	protected Vector bcast_id_list = null ;

	/** AODV Routing Entry List */
	protected Vector aodv_rt_entry_list = null ;

	/** AODV Neighbor list */
	protected Vector aodv_nbr_list = null ;
	
	/** AODV pkt queue list */
	protected Vector pkt_list;
	
	protected int		pkt_queue_limit_;
	protected double	pkt_queue_timeout_;

	AODV_TimeOut_EVT bcast_id_EVT	= null;
	AODV_TimeOut_EVT hello_EVT	= null;
	AODV_TimeOut_EVT nbr_EVT	= null;
	AODV_TimeOut_EVT route_EVT	= null;
	AODV_TimeOut_EVT local_repair_EVT = null;

	Port ifport = createIFQueryPort();  // for Interface query service
	Port idport = createIDServicePort(); // for ID lookup service
	
	/* add one port connected diecctly to Mac module, Once a link broken
	   event happens, Mac module will directly notify AODV and ADOV will
	   handle it immediately */
	{
		createLinkBrokenEventPort();
	}

	/* Debug level to enable sampled debug messages. */
	public static final int DEBUG_SAMPLE   = 0;
	public static final int DEBUG_AODV     = 1;
	/* Debug level of sending AODV packets. */
	/** Debug level of sending AODV packets. */
	public static final int DEBUG_SEND     = 2;
	/** Debug level of showing all RREQ packets. */
	public static final int DEBUG_RREQ     = 3;
	/** Debug level of showing all RREP packets. */
	public static final int DEBUG_RREP     = 4;
	/** Debug level of showing all RERR packets. */
	public static final int DEBUG_RERR     = 5;
	public static final int DEBUG_HELLO    = 6;
	public static final int DEBUG_TIMEOUT  = 7;
	public static final int DEBUG_DATA     = 8;
	public static final int DEBUG_ROUTE    = 9;
	static final String[] DEBUG_LEVELS = {
		"sample", "aodv", "send", "rreq", "rrep", "rerr", "hello", "timeout", "data", "route"
	};
	public String[] getDebugLevelNames()
	{ return DEBUG_LEVELS; }

	// common initialization
	{
		bcast_id_list		= new Vector();
		aodv_rt_entry_list	= new Vector();
		aodv_nbr_list		= new Vector();	
		pkt_list		= new Vector();
		pkt_queue_limit_ = AODV_RTQ_MAX_LEN;
		pkt_queue_timeout_ = AODV_RTQ_TIMEOUT;
		
		seqno = 2;
		bid = 1;
	}

	public AODV()
	{ super(); }

	public AODV(String id_)
	{ super(id_); }

	/** Enables/disables the "route purge" option.
	 * When enabled, the routing table entries are purged after some time. */
	public void setRoutePurgeEnabled(boolean e)
	{ routePurgeEnabled = e; }

	public boolean isRoutePurgeEnabled()
	{ return routePurgeEnabled; }

	// xxx:
	public String info()
	{
		return ""
				+ "routePurgeEnabled = " + routePurgeEnabled + "\n"
				;
	}
	
	public void reset()
	{
		super.reset();
		router_id = Integer.MAX_VALUE;
		bcast_id_list.removeAllElements();
		aodv_rt_entry_list.removeAllElements();
		aodv_nbr_list.removeAllElements();	
		pkt_list.removeAllElements();

		if (bcast_id_EVT.handle != null) {
			cancelTimeout(bcast_id_EVT.handle);
			bcast_id_EVT.setObject(null);
			bcast_id_EVT.handle = null;
		}
		if (hello_EVT.handle != null) {
			cancelTimeout(hello_EVT.handle);
			hello_EVT.setObject(null);
			hello_EVT.handle = null;
		}
		if (nbr_EVT.handle != null) {
			cancelTimeout(nbr_EVT.handle);
			nbr_EVT.setObject(null);
			nbr_EVT.handle = null;
		}
		if (route_EVT.handle != null) {
			cancelTimeout(route_EVT.handle);
			route_EVT.setObject(null);
			route_EVT.handle = null;
		}
	}

	// xxx:
	public void duplicate(Object source_)
	{
		super.duplicate(source_);
		AODV that_ = (AODV)source_;
	}

	protected void _start()
	{
		if (router_id == Integer.MAX_VALUE) {
			router_id = (int) IDLookup.getDefaultID(idport);
			if (isDebugEnabled() && isDebugEnabledAt(DEBUG_AODV))
				debug(" is constructed");
		}
        
		// whether need to start hello timer (and then trigger nb_timer
		// if the link layer provides the ability of link broken detection (link 802.11),
		// we don't need hello and nbr timer
		if (AODV_link_layer_detection == false ) {
			hello_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_HELLO, null);
			double interval = MinHelloInterval + ((MaxHelloInterval - MinHelloInterval) * rand.nextDouble());
			hello_EVT.handle = setTimeout(hello_EVT, interval);
			if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
				debug("setTimeout " + hello_EVT + " time " + interval);
		}
	}

	/** If calling this function in the script, that means the underlying link layer
	 *  provides the ability of detecting link broken, and then hello timer and neighbor
	 *  timer will be never used.
	 */
	public void enable_link_detection() { AODV_link_layer_detection = true; }
	public void disable_link_detection() { AODV_link_layer_detection = false; }
	
	///////////////////////////////////////////////////////////////////////
	// Event Handler
	///////////////////////////////////////////////////////////////////////
	
	/* Only non-data packets and Broadcast Packets are need to be processed */
	/** This routine is invoked when the link-layer reports a route failed. 
	 * When this function is called, there are two cases:
	 * (1) local repair => send RREQ and not send RERR => wait for reply 
	 *  => if not recv RREP, send RERR and call rt_down
	 * (2) no local repair => nb_delete => handle_link_failure => rt_down & send RERR
	 */
	public void  LinkBrokenEventHandler(InetPacket p, Port inPort_) {
		AODV_RTEntry rt;
		long broken_nbr = p.getNextHop();		
		if((rt = rt_lookup(p.getDestination())) == null) {
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
				debug("LinkBrokenEventHandler: no route, drop pkt " + p);
			}
			if(isGarbageEnabled()) drop(p, "DROP_RTR_MAC_CALLBACK");
			return;
		}

		/* if the broken link is closer to the dest than source,
 		attempt a local repair. Otherwise, bring down the route. */
		if (p.getHops() > 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, */
			/* hold the RERR, do not let src know it right now */
			return;	
		} else {
			if(isGarbageEnabled()) 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");
			}*/
			/* in nb_delete(), this node will send a RRER to the src */
			if (AODV_link_layer_detection == false) nb_delete(broken_nbr);
			handle_link_failure(broken_nbr);
		}
	}
	
	//protected int[] ucastQueryHandler(InetPacket req_, Port inPort_)