aodv.java

AODV protocol in tcl simulated in JSim

	public int[] routeQueryHandler(InetPacket req_, int incomingIf_, Port inPort_)
	{
		AODV_RTEntry aodv_rt;
		aodv_rt = rt_lookup(req_.getDestination());
		if(aodv_rt == null) {
			aodv_rt = rt_add(req_.getDestination());
		}

		/* If the route is up, forward the packet */
		if(aodv_rt.rt_flags == AODV_RTEntry.RTF_UP) {
			Object rt_obj = retrieveRTEntryDest(aodv_rt.rt_dst);
			if ( rt_obj!= null && rt_obj instanceof RTEntry) { 
				RTEntry rt = (RTEntry) rt_obj;
				return rt._getOutIfs();
			} else if ( rt_obj!= null && rt_obj instanceof RTEntry[] && ((RTEntry[])rt_obj).length > 0) { 
                                RTEntry[] mul_rt = (RTEntry[]) rt_obj;
				debug("mul_rt length " + mul_rt.length );
                                // xxx: always return the first one
                                return mul_rt[0]._getOutIfs();
                         }
 			 debug("ERROR! inconsistency btw RT(empty) len: " + ((RTEntry[])rt_obj).length + " and aodv_RT " + aodv_rt + " pkt: " + req_  );
                         aodv_rt.rt_down();
		}

		/* if I am the source of the packet, then do a Route Request.*/
		if(req_.getSource() == router_id) {
			aodv_pkt_enque(req_);
			/*debug("sendRequest from ucastQueryHandler" + aodv_rt.rt_dst + "pkt " + req_);*/
			sendRequest(aodv_rt.rt_dst);
		}
		/* A local repair is in progress. Buffer the packet. */
		else if (aodv_rt.rt_flags == AODV_RTEntry.RTF_IN_REPAIR) {
			aodv_pkt_enque(req_);
		}
		/* I am trying to forward a packet for someone else to which
		 *  I don't have a route. */
		else {
			AODV_RERR re = new AODV_RERR();
			/* For now, drop the packet and send error upstream.
			 * Now the route errors are broadcast to upstream
			 * neighbors - Mahesh 09/11/99 */	
			re.DestCount = 0;
			re.unreachable_dst[re.DestCount] = aodv_rt.rt_dst;
			re.unreachable_dst_seqno[re.DestCount] = aodv_rt.rt_seqno;
			re.DestCount += 1;
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_AODV) || isDebugEnabledAt(DEBUG_RERR))) {
				debug("sending RERR: " + re + " pkt:" + req_);
				if (aodv_rt != null)
					debug("RERR RT: " + aodv_rt );
				
			}
			sendError(re, false);
			if(isGarbageEnabled()) drop(req_, "DROP_RTR_NO_ROUTE");
		}
		return null;
	}
	
	///////////////////////////////////////////////////////////////////////
	//  Receiving Routine
	///////////////////////////////////////////////////////////////////////
	/** 
	 * Handling timeout event. According to the timeout event 
	 * which can be obtained from evt_, there are different 
	 * handling functions.
	 * @param evt_ event object got from the timer port
	 */
	protected void timeout(Object evt_)
	{
		InetPacket pkt;
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_TIMEOUT)))
			debug("__timeout__ " + evt_);

		int type = ((AODV_TimeOut_EVT)evt_).EVT_Type;
		double stime = getTime();

		switch(type) {
			case AODV_TimeOut_EVT.AODV_TIMEOUT_BCAST_ID:
				if (evt_ != bcast_id_EVT) {
					error("timeout()", " ** ERROR ** where does this come from? " + evt_);
					break;
				}
				id_purge();
				bcast_id_EVT.handle = setTimeout(bcast_id_EVT, BCAST_ID_SAVE);
				if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
					debug("Time: " + stime + " set BCAST timeout: " + BCAST_ID_SAVE);
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_HELLO:
				if (evt_ != hello_EVT) {
					error("timeout()", " ** ERROR ** where does this come from? " + evt_);
					break;
				}
				sendHello();
				double interval = MinHelloInterval + ((MaxHelloInterval - MinHelloInterval) * rand.nextDouble());
				hello_EVT.handle = setTimeout(hello_EVT, interval);
				if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
					debug("Time: " + stime + " set HELLO timeout: " + interval);
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_NBR:
				if (evt_ != nbr_EVT) {
					error("timeout()", " ** ERROR ** where does this come from? " + evt_);
					break;
				}
				nb_purge();
				nbr_EVT.handle = setTimeout(nbr_EVT, HELLO_INTERVAL);
				if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
					debug("Time: " + stime + " set NBR timeout: " + HELLO_INTERVAL);
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_ROUTE:
				if (!routePurgeEnabled) break;
				if (evt_ != route_EVT) {
					error("timeout()", " ** ERROR ** where does this come from? " + evt_);
					break;
				}
				rt_purge();
				route_EVT.handle = setTimeout(route_EVT, ROUTE_CACHE_FREQUENCY);
				if (isDebugEnabled() && isDebugEnabledAt(DEBUG_TIMEOUT))
					debug("Time: " + stime + " set Route timeout: " + ROUTE_CACHE_FREQUENCY);
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_LOCAL_REPAIR: 
				pkt = (InetPacket) ((AODV_TimeOut_EVT)evt_).getObject();
				AODV_RTEntry rt = rt_lookup(pkt.getDestination());
	
				if (rt != null && rt.rt_flags != AODV_RTEntry.RTF_UP) {
					if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_TIMEOUT)) ) {
						debug("Time: " + stime + " failed local repair; dst: " + rt.rt_dst);
						debug(" local repair timeout" + "nexthop: " + rt.rt_nexthop + " pkt: " + pkt);
					}
					if (AODV_link_layer_detection == false) nb_delete(pkt.getDestination());
					handle_link_failure(pkt.getDestination());
				}
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_DELAY_FORWARD: 
				pkt = (InetPacket) ((AODV_TimeOut_EVT)evt_).getObject();
				downPort.doSending(pkt);
				break;
			case AODV_TimeOut_EVT.AODV_TIMEOUT_DELAY_BROADCAST: 
				AODV_Packet aodv_pkt = (AODV_Packet) ((AODV_TimeOut_EVT)evt_).getObject();
				broadcast( aodv_pkt, (long) router_id, Address.ANY_ADDR, true, 1/*ttl*/, CONTROL_PKT_TYPE, Address.ANY_ADDR /*nexthop*/);
				break;
		}
		return;
	}

	protected void process(Object data_, drcl.comp.Port inPort_)
	{
		// Tyan: cannot process messages from neighbor until _start() is called
		if (!isStarted()) {
			if (isGarbageEnabled()) drop(data_, "not started yet");
			return;
		}
		lock(this);
		super.process(data_, inPort_);
		unlock(this);
	}
	
  	/**
	 * Handle data arriving at the down port.
	 * According to the different packet types ( AODV Hello pkt, Database descricption
	 * pkt,Link State update pkt, LS request pkt, or LS ack pkt), different 
	 * corresponding methods can handle the packet.
	 * Note for AODV_Hello pkt will be received only once. The other hello maintaince
	 * is done by drcl.inet.core.Hello
	 *  
	 * @param date_ message body arriving at the down port.
	 * @param downPort_ down port at which messages arrive.
	 */
	public void dataArriveAtDownPort(Object data_, drcl.comp.Port downPort_) 
	{
		InetPacket ipkt_ = (InetPacket)data_;
		AODV_Packet pkt_ = (AODV_Packet)ipkt_.getBody();

		int src_ = pkt_.getRouterID(); /* router ip addr of the source */
		int rt_id = pkt_.getRouterID();
		int pkt_type = pkt_.getType();

		// if the packet is AODV pkt
		switch (pkt_type) {
			case AODVTYPE_RREQ:
				AODV_RREQ req = (AODV_RREQ) pkt_.getBody();
				recvRequest(req, ipkt_);
				break;
			case AODVTYPE_RREP:
				AODV_RREP rep = (AODV_RREP) pkt_.getBody();
				recvReply(rep, ipkt_);
				break;
			case AODVTYPE_RERR:
				AODV_RERR err = (AODV_RERR) pkt_.getBody();
				recvError(err, ipkt_);
				break;
			case AODVTYPE_HELLO:
				AODV_RREP rep_ = (AODV_RREP) pkt_.getBody();
				recvHello(rep_, ipkt_);
				break;
			default:		
				if (isDebugEnabled()) {
					debug(" Invalid AODV type" + pkt_type);
				}
				System.exit(1);
		}
	}
	
	/* ref: 8.3.1 */
	protected void recvRequest(AODV_RREQ rq, InetPacket ipkt_) {
            	int inIf_ = ipkt_.getIncomingIf();

		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREQ) || isDebugEnabledAt(DEBUG_AODV))) {
			debug(" aodv: receive RREQ: " + rq + " ipkt " + ipkt_ + " from " + ipkt_.getIncomingIf());
		}
		/* Drop if:		*  - I'm the source
		*  - I recently heard this request.
		*/
		if(rq.rq_src == router_id) {
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREQ) || isDebugEnabledAt(DEBUG_AODV))) {
				debug(" got my own REQUEST: " + rq);
			}	
			return;
		}	
		// receive duplicated RREQ
		if ( id_lookup(rq.rq_src, rq.rq_bcast_id) == true ) {
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREQ) || isDebugEnabledAt(DEBUG_AODV))){ 
				debug(" discarding request: " + rq);
			}
			return;
		}

		/* Cache the broadcast ID */
		id_insert(rq.rq_src, rq.rq_bcast_id);

		/* We are either going to forward the REQUEST or generate a
		* REPLY. Before we do anything, we make sure that the REVERSE
		* route is in the route table.		*/
		double now = getTime();
		AODV_RTEntry rev_rt; // rev_rt is the reverse route 
   
		rev_rt = rt_lookup(rq.rq_src);
		if(rev_rt == null) { 
			/* if not in the route table */
			// create an entry for the reverse route.
			rev_rt = rt_add(rq.rq_src);
		}
                /* set_expire return true if it really modify rt_expire */
                if ( rev_rt.set_expire( now + REV_ROUTE_LIFE) == true) {
                    //aodv_addRTEntry(rev_rt.rt_dst, ipkt_.getSource(), REV_ROUTE_LIFE );
                    aodv_addRTEntry(rev_rt.rt_dst, ipkt_.getSource(), REV_ROUTE_LIFE, inIf_ );
                }
                
		// If we have a fresher seq no. or lesser #hops for the 
		// same seq no., update the rt entry. Else don't bother.
		if ((rq.rq_src_seqno > rev_rt.rt_seqno ) ||
    		((rq.rq_src_seqno == rev_rt.rt_seqno) && (rq.rq_hop_count < rev_rt.rt_hops)) ) {
			// update the info. of the next hop field in the reverse route
			rev_rt.rt_update(rq.rq_src_seqno, rq.rq_hop_count, ipkt_.getSource());			
			if (rev_rt.rt_req_timeout > 0.0) {
				/* Reset the soft state and  Set expiry time to CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT. This is because route is used in the forward direction,  but only sources get benefited by this change */
				rev_rt.rt_req_cnt = 0;
				rev_rt.rt_req_timeout = 0.0; 
				rev_rt.rt_req_last_ttl = rq.rq_hop_count;
				rev_rt.rt_expire = now + ACTIVE_ROUTE_TIMEOUT;
			}
			/* update RT info */	
			//aodv_addRTEntry(rq.rq_src, ipkt_.getSource(), ACTIVE_ROUTE_TIMEOUT);
			aodv_addRTEntry(rq.rq_src, ipkt_.getSource(), ACTIVE_ROUTE_TIMEOUT, inIf_);
			/* Find out whether any buffered packet can benefit from the reverse route. May need some change in the following code - Mahesh 09/11/99 */
			InetPacket buffered_pkt;
			while ((buffered_pkt = aodv_pkt_deque(rev_rt.rt_dst)) != null) {
				if ( rev_rt.rt_flags == AODV_RTEntry.RTF_UP ) {
					aodv_delay_forward(rev_rt, buffered_pkt, 0, false);
				}
			}
		} // End for putting reverse route in rt table

		/* We have taken care of the reverse route stuff.
		* Now see whether we can send a route reply. 
		*/
		AODV_RTEntry rt = rt_lookup(rq.rq_dst);

		// First check if I am the destination ..
		if(rq.rq_dst == router_id) {
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREQ) || isDebugEnabledAt(DEBUG_AODV))){ 
				debug(" destination sending reply: " );
			}
			/*Just to be safe, I use the max. Somebody may have incremented the dst seqno. */
			seqno = (seqno > rq.rq_dst_seqno) ? (seqno + 1) : (rq.rq_dst_seqno + 1);
			if (seqno%2 == 1) seqno++;

			sendReply(rq.rq_src,	/* IP Destination */
             			 	  1,	/* Hop Count */
				  router_id,	/* Dest IP Address */
             			      seqno,	/* Dest Sequence Num */
		           MY_ROUTE_TIMEOUT,	/* Lifetime */
             		rq.rq_timestamp);	/* timestamp */
		}
		/* I am not the destination, but I may have a fresh enough route. */
		else if ( rt != null && (rt.rt_hops != Integer.MAX_VALUE) && (rt.rt_seqno >= rq.rq_dst_seqno) ) {
			sendReply(rq.rq_src,
             		     rt.rt_hops + 1,
		                  rq.rq_dst,
		                rt.rt_seqno,
		       (rt.rt_expire - now),
			   rq.rq_timestamp);	
		/* Insert nexthops to RREQ source and RREQ destination in the precursor lists of destination and source respectively */
			rt.pc_insert(rev_rt.rt_nexthop); // nexthop to RREQ source
			rev_rt.pc_insert(rt.rt_nexthop); // nexthop to RREQ destination
			// xxx: send grat RREP to dst if G flag set in RREQ
		}
		/* Can't reply. So forward the  Route Request */
		else {
			/* create a new RREQ */
			AODV_RREQ new_rq = (AODV_RREQ) rq.clone();

			ipkt_.setSource(router_id);
			ipkt_.setDestination(Address.ANY_ADDR);
			new_rq.rq_hop_count += 1;
			// Maximum sequence number seen en route
			if (rt != null) new_rq.rq_dst_seqno = (rt.rt_seqno > new_rq.rq_dst_seqno)? rt.rt_seqno : new_rq.rq_dst_seqno ;
			// replace it with broadcast
			aodv_delay_broadcast (  AODVTYPE_RREQ, new_rq, new_rq.size(), 1, null, DELAY * rand.nextDouble(), true);
			//aodv_delay_forward (  AODVTYPE_RREQ, new_rq, new_rq.size(), 1, null, DELAY * rand.nextDouble(), true);
		}
	}
		
	protected void recvReply(AODV_RREP rp, InetPacket ipkt_) {
            	int inIf_ = ipkt_.getIncomingIf();
                
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREP) || isDebugEnabledAt(DEBUG_AODV))) {	
			debug( " recv RREP: " + rp + "ipkt: " + ipkt_);
		}
		AODV_RTEntry rt;
		boolean suppress_reply = false;
		double delay = 0.0;
		double now = getTime();
	
		/*  Got a reply. So reset the "soft state" maintained for 
		*  route requests in the request table. We don't really have
		*  have a separate request table. It is just a part of the
		*  routing table itself. 
		*/
		// Note that rp_dst is the dest of the data packets, not the
		// the dest of the reply, which is the src of the data packets.
		rt = rt_lookup(rp.rp_dst);
        
		/* If I don't have a rt entry to this host... adding */
		if(rt == null) {
			rt = rt_add(rp.rp_dst);
		}

		/* Add a forward route table entry... here I am following
		* Perkins-Royer AODV paper almost literally - SRD 5/99	*/
		if ( (rt.rt_seqno < rp.rp_dst_seqno) ||   /* newer route */ 
		((rt.rt_seqno == rp.rp_dst_seqno) && (rt.rt_hops > rp.rp_hop_count)) ) { 
			/* shorter or better route */
			/* Update the rt entry, including the next hop and expire info. */
			rt.rt_update(rp.rp_dst_seqno, rp.rp_hop_count, ipkt_.getSource(), now + rp.rp_lifetime);