aodv.java

AODV protocol in tcl simulated in JSim

		if(nbr_EVT == null) {
			nbr_EVT	= new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_NBR, null);
			nbr_EVT.handle = setTimeout(nbr_EVT, HELLO_INTERVAL);
			if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
				debug(" set NBR timeout: " + HELLO_INTERVAL);
		}
		AODV_BroadcastID b = new AODV_BroadcastID(id);
		b.expire = now + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
		aodv_nbr_list.addElement(b);
		seqno += 2;             // set of neighbors changed
	}

	private AODV_BroadcastID nb_lookup(long id) {
		int no = aodv_nbr_list.size();
		for (int i = 0; i < no; i++) {
			AODV_BroadcastID nbr = (AODV_BroadcastID) aodv_nbr_list.elementAt(i);
			if (nbr.src == id)
				return nbr;
		}
		return null;
	}
	
	/* Purges all timed-out Neighbor Entries - runs every
	* HELLO_INTERVAL * 1.5 seconds.
	*/
	private void nb_purge() {
		double now = getTime();
		for (int i = 0; i < aodv_nbr_list.size(); i++) {
			AODV_BroadcastID nbr = (AODV_BroadcastID) aodv_nbr_list.elementAt(i);
			if (nbr.expire <= now)
				nb_delete(nbr.src);
			else
				i++;
		}
	}

	/** Called when we receive *explicit* notification that a Neighbor
	* is no longer reachable.
	* nb_delete is called by :
	* (1) LinkBrokenEventHandler (@ no local repair)
	* (2) nb_purge (@nbr.expire <= now) 
`	*/
	public void nb_delete(long id) {
		seqno += 2;     // Set of neighbors changed
		int no = aodv_nbr_list.size();
		for (int i = 0; i < no; i++) {
			AODV_BroadcastID nbr = (AODV_BroadcastID) aodv_nbr_list.elementAt(i);
			if (nbr.src == id) {
				aodv_nbr_list.removeElement(nbr);
				break;
			}
		}
	}

	/* called by nb_delete, which periodically check whether nbr is valid */
	private void handle_link_failure(long id) {
		double now = getTime();
		AODV_RERR re = new AODV_RERR();
		re.DestCount = 0;
		int no = aodv_rt_entry_list.size();
		for (int i = 0; i < no; i++) {
			AODV_RTEntry rt = (AODV_RTEntry) aodv_rt_entry_list.elementAt(i);
			if ((rt.rt_hops != Integer.MAX_VALUE) && (rt.rt_nexthop == id) ) {
				rt.rt_seqno++;
				re.unreachable_dst[re.DestCount] = rt.rt_dst;
				re.unreachable_dst_seqno[re.DestCount] = rt.rt_seqno;
				if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
					debug(" unreach dst: " + re.unreachable_dst[re.DestCount] + " unreach dst seq: " + re.unreachable_dst_seqno[re.DestCount] + "nexthop: " + rt.rt_nexthop);
				}
				re.DestCount += 1;
				rt.rt_down();
				/* remove the RTEntry in RT*/
				aodv_removeRTEntry(rt.rt_dst);
			}
			/* remove the lost neighbor from all the precursor lists */
			rt.pc_delete(id);
		}
		if (re.DestCount > 0) {
			sendError(re, false);
		}
	}
	
	private void local_rt_repair(AODV_RTEntry rt, InetPacket p) {
		double now = getTime();
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
			debug(" repair route; dst: " + rt.rt_dst);
		}
		// Buffer the packet 
		aodv_pkt_enque(p);
		// mark the route as under repair 
		rt.rt_flags = AODV_RTEntry.RTF_IN_REPAIR;
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
			debug("sendRequest from local_rt_repair" + rt.rt_dst);
		}
		sendRequest(rt.rt_dst);
		// set up a timer interrupt
		local_repair_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_LOCAL_REPAIR, p);
		local_repair_EVT.handle = setTimeout( local_repair_EVT, rt.rt_req_timeout);
	}
	
	//////////////////////////////////////////////////////////////////////////
	// Broadcast ID Management  Functions	
	//////////////////////////////////////////////////////////////////////////	
	protected void id_insert(long id_, int bid_) {
		double now = getTime();
		if (bcast_id_EVT == null) {
			bcast_id_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_BCAST_ID, null);
			if (bcast_id_EVT != null) {
				//System.out.println("bcast_id_Evt " + bcast_id_EVT);
				bcast_id_EVT.handle = setTimeout(bcast_id_EVT, BCAST_ID_SAVE);
				if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
					debug(" set BCAST timeout: " + BCAST_ID_SAVE);
			} else 
				System.out.println("Error! Null bcast_id_EVT");
		}
		AODV_BroadcastID b = new AODV_BroadcastID(id_, bid_);
		b.expire = now + BCAST_ID_SAVE;
		bcast_id_list.addElement(b);
	}

	/* SRD */
	protected boolean id_lookup(long src_, int id_) {
		int no = bcast_id_list.size();
		for (int i = 0; i < no; i++) {
			AODV_BroadcastID id_entry = (AODV_BroadcastID) bcast_id_list.elementAt(i);
			if ((id_entry.src == src_) && (id_entry.id == id_))
				return true;
		}
		return false;
	}

	private void id_purge() {
		double now = getTime();
		for (int i = 0; i < bcast_id_list.size(); ) {
			AODV_BroadcastID id_entry = (AODV_BroadcastID) bcast_id_list.elementAt(i);
			if (id_entry.expire <= now)
				bcast_id_list.removeElement(id_entry);
			else
				i++;
		}
	}
	
	//////////////////////////////////////////////////////////////////////////
	// The Routing Table Functions
	//////////////////////////////////////////////////////////////////////////
	protected AODV_RTEntry rt_lookup(long id_) {
		int no = aodv_rt_entry_list.size();
		for (int i = 0; i < no; i++) {
			AODV_RTEntry rt_entry = (AODV_RTEntry) aodv_rt_entry_list.elementAt(i);
			if (rt_entry.rt_dst == id_)
				return rt_entry;
		}
		return null;
	}

	private void rt_delete(long id_) {
		AODV_RTEntry rt = rt_lookup(id_);
		if(rt != null) {
			aodv_rt_entry_list.removeElement(rt);
		}
	}
	
	/* the setting of rt_expire is the responsibility of the caller */
	protected AODV_RTEntry rt_add(long id_) {
		double now = getTime();
		if ( route_EVT == null ) {
			route_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_ROUTE, null);
			route_EVT.handle = setTimeout(route_EVT, ROUTE_CACHE_FREQUENCY);
			if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
				debug(" set Route timeout: " + ROUTE_CACHE_FREQUENCY + route_EVT);
		}
		AODV_RTEntry rt = rt_lookup(id_);
		if(rt != null) {
			return rt;
		}
		rt = new AODV_RTEntry(id_);
		aodv_rt_entry_list.addElement(rt);	
		return rt;
	}
	
	private void rt_purge() {
		double now = getTime();
		double delay = 0.0;

		int no = aodv_rt_entry_list.size();
		for (int i = 0; i < no; i++) {
			AODV_RTEntry rt = (AODV_RTEntry) aodv_rt_entry_list.elementAt(i);
			if ((rt.rt_flags == AODV_RTEntry.RTF_UP) && (rt.rt_expire < now)) {
				/* if a valid route has expired, purge all packets from send buffer and invalidate the route. */
				InetPacket pkt;
				while ((pkt = aodv_pkt_deque(rt.rt_dst)) != null) {
					if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
						debug(" drop pkt dst: " + rt.rt_dst);
					}
					if(isGarbageEnabled()) drop(pkt, "DROP_RTR_NO_ROUTE");
				}
				rt.rt_seqno++;
				rt.rt_down();
				
				/* remove the RTEntry in RT*/
				aodv_removeRTEntry(rt.rt_dst);
			} else if (rt.rt_flags == AODV_RTEntry.RTF_UP) {
				/* If the route is not expired, and there are packets in the sendbuffer waiting, forward them. This should not be needed, but this extra check does no harm. */
				InetPacket buffered_pkt;
				while ((buffered_pkt = aodv_pkt_deque(rt.rt_dst)) != null) {
					aodv_delay_forward(rt, buffered_pkt, delay, false);
					delay += ARP_DELAY;
				}
			} else if (aodv_pkt_find(rt.rt_dst) == true) {
				/* If the route is down and there is a packet for this destination waiting in the sendbuffer, then send out route request. sendRequest will check whether it is time to really send out request or not.	This may not be crucial to do it here, as each generated packet will do a sendRequest anyway. */
				/*debug("sendRequest from rt_purge " + rt.rt_dst); */
				sendRequest(rt.rt_dst); 
			}
		}
	}

	/** add a routing entry with specification of distance, nect hop and the timeout value */
	public void aodv_addRTEntry(long dst_, long nexthop_, double timeout_)
	{
		aodv_addRTEntry(dst_, nexthop_, timeout_, 0 /*interface */);
	}

	/** add a routing entry with specification of distance, nect hop ,the timeout value and the interface id*/
	public void aodv_addRTEntry(long dst_, long nexthop_, double timeout_, int interface_)
	{
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_ROUTE) || isDebugEnabledAt(DEBUG_AODV))
			debug("addRTEntry: dst" + dst_ +" nexthop " + nexthop_ + " timeout " + timeout_ + " if: " + interface_);
		// update the routing info. into RT
		RTKey key = new RTKey(0, 0, dst_, -1, 0, 0);
		//RTKey key = new RTKey(-1, 0, dst_, -1, -1, 0);
		AODV_RTEntry new_en = rt_lookup(dst_);
		// xxx: check whether interface is set correctly 
                /* Here we use longer timeout in RT since RT usually purges entries on time
                 * But in AODV, we check rt_purge only on every ROUTE_CACHE_FREQUENCY time,
                 * So, ther might cause inconsistency if we do not use longer timeout in RT since
                 * the entries in AODV RT might not be purged */
		addRTEntry(key, nexthop_, interface_ , new_en, Double.NaN); //timeout_ + 2*ROUTE_CACHE_FREQUENCY);
			// Tyan: since AODV purge the route itself, don't make RT do it again
	}

	/** each rt_down is associated with an aodv_removeRTEntry, rt_down is called when:
	* (1) local repair timeout which then call nb_delete
	* (2) recvError
	* (3) handle_link_failure (which is called by nb_delete)
	* (4) rt_purge 
	*/
	public Object aodv_removeRTEntry(long dst) {
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_ROUTE) || isDebugEnabledAt(DEBUG_AODV))
			debug("removeRTEntry: dst" + dst);
		return removeRTEntry(dst);
	}
	
	//////////////////////////////////////////////////////////////////////////
	// Packet Queue Management Functions
	/////////////////////////////////////////////////////////////////////////
	private void aodv_pkt_enque(InetPacket p) {
		double now = getTime();
		/* Purge any packets that have timed out.*/
		aodv_pkt_purge();
 
		if (pkt_list.size() == pkt_queue_limit_) {
			AODV_Buffered_pkt pkt = aodv_pkt_remove_head();	// decrements len_
			if (pkt.expire > now ) {
				if(isGarbageEnabled()) drop(pkt, "DROP_RTR_NO_ROUTE");
			} else {
				if(isGarbageEnabled()) drop(pkt, "DROP_RTR_QTIMEOUT");
			}
		}
		AODV_Buffered_pkt new_pkt = new AODV_Buffered_pkt(p, now + pkt_queue_timeout_);	
		pkt_list.addElement(new_pkt);
	}

	protected InetPacket aodv_pkt_deque() {
		/* Purge any packets that have timed out.*/
		aodv_pkt_purge();

		AODV_Buffered_pkt p = (AODV_Buffered_pkt) pkt_list.firstElement();
		pkt_list.removeElementAt(0);
		return p.ipkt;
	}

	protected InetPacket aodv_pkt_deque(long dst) {
		/* Purge any packets that have timed out.*/
		aodv_pkt_purge();
		int no = pkt_list.size();
		for (int i = 0; i < no; i++) {	
			AODV_Buffered_pkt pkt_ = (AODV_Buffered_pkt) pkt_list.elementAt(i);
			if (pkt_.ipkt.getDestination() == dst) {
				pkt_list.removeElementAt(i);	
				return pkt_.ipkt;	
			}
		}
		return null;
	}

	private boolean aodv_pkt_find(long dst) {
		int no = pkt_list.size();
		for (int i = 0; i < no; i++) {	
			AODV_Buffered_pkt pkt_ = (AODV_Buffered_pkt) pkt_list.elementAt(i);
			if (pkt_.ipkt.getDestination() == dst) {	
				return true;	
			}
		}
		return false;
	}

	private AODV_Buffered_pkt aodv_pkt_remove_head() {
		if (pkt_list.size() == 0) return null;
		AODV_Buffered_pkt p = (AODV_Buffered_pkt) pkt_list.firstElement();
		pkt_list.removeElementAt(0);
		return p;
	}	

	private void aodv_pkt_purge() {
		double now = getTime();
		for (int i = 0; i < pkt_list.size(); ) {
			AODV_Buffered_pkt p = (AODV_Buffered_pkt) pkt_list.elementAt(i);
			if (p.expire <= now)
				pkt_list.removeElement(p);
			else
				i++;
		}
	}
	
	/////////////////////////////////////////////////////////////////////////	
	// Helper Functions
	//////////////////////////////////////////////////////////////////////////
	private double PerHopTime(AODV_RTEntry rt) {
		int num_non_zero = 0;
		double total_latency = 0.0;

		if (rt == null) return ((double) NODE_TRAVERSAL_TIME );
		for (int i=0; i < AODV_RTEntry.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);
	}
    
    /**
     * Sets the seed of the random number generator.
     */
    public void setSeed(long seed) {
        rand.setSeed(seed);
    } 
    
}