aodv.java

AODV protocol in tcl simulated in JSim

			/* update RT info */
			aodv_addRTEntry(rp.rp_dst, ipkt_.getSource(), rp.rp_lifetime, inIf_);
			//aodv_addRTEntry(rp.rp_dst, ipkt_.getSource(), ACTIVE_ROUTE_TIMEOUT);
			/* reset the soft state */
			rt.rt_req_cnt = 0;
			rt.rt_req_timeout = 0.0; 
			rt.rt_req_last_ttl = rp.rp_hop_count;
  
			if (ipkt_.getDestination() == router_id) { 
				/* If I am the original source
				 * Update the route discovery latency statistics
				 * rp.rp_timestamp is the time of request origination */
				rt.rt_disc_latency[rt.hist_indx] = (now - rp.rp_timestamp) / (double) rp.rp_hop_count;
				/* increment indx for next time */
				rt.hist_indx = (rt.hist_indx + 1) % AODV_RTEntry.MAX_HISTORY;
			}

			/* Send all packets queued in the sendbuffer destined for this destination. 
			* XXX - observe the "second" use of p.
			*/
			InetPacket buf_pkt;
			while ((buf_pkt = aodv_pkt_deque(rt.rt_dst)) != null) {
				if(rt.rt_hops != Integer.MAX_VALUE ) {
					if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_DATA) || isDebugEnabledAt(DEBUG_AODV))) {	
						debug( "ready to send buffered pkt " + buf_pkt + " rt:" + rt);
					}
					/* Delay them a little to help ARP. Otherwise ARP 
					 * may drop packets. -SRD 5/23/99 */
					aodv_delay_forward(rt, buf_pkt, delay, false);
					delay += ARP_DELAY;
				}
			}
		} else {	
			suppress_reply = true;		
		}

		/* If reply is not for me, forward it. */
		if(ipkt_.getDestination() != router_id && suppress_reply == false ) {
			/* create a new RREP */
			AODV_RREP new_rp = (AODV_RREP) rp.clone();
			
			 /* Find the rt entry */
			AODV_RTEntry rt0 = rt_lookup(ipkt_.getDestination());
			/* If the rt is up, forward */
			if( rt0 != null && (rt0.rt_hops != Integer.MAX_VALUE)) {
				new_rp.rp_hop_count += 1;
				new_rp.rp_src = router_id;
				aodv_delay_forward (  AODVTYPE_RREP, new_rp, new_rp.size(), 1, rt0, 0/* no delay*/, false);
				/* Insert the nexthop towards the RREQ source to
				 * the precursor list of the RREQ destination */
				rt.pc_insert(rt0.rt_nexthop); /* nexthop to RREQ source */
			} else {
			// I don't know how to forward .. drop the reply. 
				if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREP) || isDebugEnabledAt(DEBUG_AODV))) {
					debug(" dropping Route Reply: " + rp);
				}
				if(isGarbageEnabled()) drop(ipkt_, "DROP_RTR_NO_ROUTE");
			}
		}
	}

	/** receive a packet with RERR type, indicating the information of a broken link */
	public void recvError(AODV_RERR re, InetPacket ipkt_) {
        if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {	
			debug( " recv RERR: " + re + " ipkt: " + ipkt_);
		}

		AODV_RTEntry rt;		
		double now = getTime();
		AODV_RERR nre = new AODV_RERR();
		nre.DestCount = 0;
		for (int i=0; i < re.DestCount; i++) {
			/* For each unreachable destination*/
			rt = rt_lookup(re.unreachable_dst[i]);
			if ( rt != null && (rt.rt_hops != Integer.MAX_VALUE) &&	(rt.rt_nexthop == ipkt_.getSource()) &&	(rt.rt_seqno <= re.unreachable_dst_seqno[i]) ) {
				/* is the seqno even? */
				if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))) {
					debug( "dst: " + rt.rt_dst + " seq: " + rt.rt_seqno + " nexthop: " + rt.rt_nexthop + " unreach dst: " + re.unreachable_dst[i] + " unreach dst seq: " + re.unreachable_dst_seqno[i] + " src: " + ipkt_.getSource());
				}
				rt.rt_seqno = re.unreachable_dst_seqno[i];
				rt.rt_down();
				/* remove the RTEntry in RT*/
				aodv_removeRTEntry(rt.rt_dst);

				/* if precursor list non-empty add to RERR and delete the precursor list*/
				if (rt.pc_empty() == false) {
					nre.unreachable_dst[nre.DestCount] = rt.rt_dst;
					nre.unreachable_dst_seqno[nre.DestCount] = rt.rt_seqno;
					nre.DestCount += 1;
					rt.pc_delete();
				}
			}
		}

		if (nre.DestCount > 0) {
			sendError(nre, true);
		} 
	}

	/** receive a hello packet to maintain the neighbor relationship, Hello packet is only used when the 
	 *  link layer does not provide the link broken detection function */ 
	public void recvHello(AODV_RREP rp, InetPacket ipkt_) {
		double now = getTime();
		AODV_BroadcastID nb = nb_lookup(rp.rp_dst);
		if(nb == null) {
			nb_insert(rp.rp_dst);
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_HELLO) || isDebugEnabledAt(DEBUG_AODV))) {	
				debug( " recv Hello from new nbr: " + rp);
			}
		} else {
			nb.expire = now + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
		}
	}


	/////////////////////////////////////////////////////////////////////////////
	//  Sending Routine
	/////////////////////////////////////////////////////////////////////////////
	/**
	 * broadcast the RREQ pkt	
	 * ref: sec. 5.3
	 */	
	protected void sendRequest(long dst) {
		int ttl_;
		double now = getTime();
		/* Allocate a RREQ packet */
		AODV_RREQ rq = new AODV_RREQ( );
		AODV_RTEntry rt = rt_lookup(dst);
		/* Rate limit sending of Route Requests. We are very conservative about sending out route requests. */
		if (rt.rt_flags == AODV_RTEntry.RTF_UP) {
			return;
		}
		if (rt.rt_req_timeout > now) {
			return;
		}

		/* rt_req_cnt is the no. of times we did network-wide broadcast
		 * RREQ_RETRIES is the maximum number we will allow before going to a long timeout. */
		if (rt.rt_req_cnt > RREQ_RETRIES) {
			rt.rt_req_timeout = now + MAX_RREQ_TIMEOUT;
			rt.rt_req_cnt = 0;
			InetPacket buf_pkt;
			while ((buf_pkt = aodv_pkt_deque(rt.rt_dst)) != null) {
				if(isGarbageEnabled()) drop(buf_pkt, "DROP_RTR_NO_ROUTE");
			}	
			return;
		}
		// Determine the TTL to be used this time. 
		// Dynamic TTL evaluation - SRD
		rt.rt_req_last_ttl = (rt.rt_req_last_ttl > rt.rt_last_hop_count) ? rt.rt_req_last_ttl : rt.rt_last_hop_count;

		if (rt.rt_req_last_ttl == 0) {
			/* first time query broadcast */
			ttl_ = TTL_START;
		} else {
			// Expanding ring search.
			if (rt.rt_req_last_ttl < TTL_THRESHOLD) {
				ttl_ = rt.rt_req_last_ttl + TTL_INCREMENT;
			} else {
				// network-wide broadcast
				ttl_ = NETWORK_DIAMETER;
				rt.rt_req_cnt += 1;
			}
		}

		// remember the TTL used  for the next time
		rt.rt_req_last_ttl = ttl_;

		// PerHopTime is the roundtrip time per hop for route requests.
		// The factor 2.0 is just to be safe .. SRD 5/22/99
		// Also note that we are making timeouts to be larger if we have 
		// done network wide broadcast before. 
		rt.rt_req_timeout = 2.0 * (double) ttl_ * PerHopTime(rt); 
		if (rt.rt_req_cnt > 0) {
			rt.rt_req_timeout *= rt.rt_req_cnt;	
		}
		rt.rt_req_timeout += now;

		// Don't let the timeout to be too large, however .. SRD 6/8/99
		if (rt.rt_req_timeout > now + MAX_RREQ_TIMEOUT) {
			rt.rt_req_timeout = now + MAX_RREQ_TIMEOUT;
		}
		rt.rt_expire = 0;
		// Fill up some more fields. 
		rq.rq_type = AODVTYPE_RREQ;
		rq.rq_hop_count = 1;
		rq.rq_bcast_id = bid++;
		rq.rq_dst = dst;
		rq.rq_dst_seqno = (rt == null ? 0: rt.rt_seqno);
		rq.rq_src = router_id;
		seqno += 2;
		rq.rq_src_seqno = seqno;
		rq.rq_timestamp = now;
		
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREQ) || isDebugEnabledAt(DEBUG_AODV))){ 
			debug(" sending Route Request, dst:" + dst + " timeout: " + (rt.rt_req_timeout - now) + " rt: " + rt.rt_req_last_ttl +" rq: " + rq);
		}

		aodv_message_broadcast( AODVTYPE_RREQ, rq, rq.size(), ttl_);
	}
	
	protected void sendReply(long ipdst, int hop_count, long rpdst, int rpseq, double lifetime, double timestamp) {
		int ttl_;
		double now = getTime();
		/* Allocate a RREP packet */
		AODV_RREP rp = new AODV_RREP( );
		AODV_RTEntry rt = rt_lookup(ipdst);
		if ( rt == null ) {
			if (isDebugEnabled()){ 
				debug( "ERROR! reverse rt is null");		 	
			}
			return;
		}			
		rp.rp_type = AODVTYPE_RREP;
		rp.rp_hop_count = hop_count; /* if I am dest, rp_hop_count = 1 */
		rp.rp_dst = rpdst;
		rp.rp_dst_seqno = rpseq;
		rp.rp_src = router_id;
		rp.rp_lifetime = lifetime;
		rp.rp_timestamp = timestamp;
		ttl_ = NETWORK_DIAMETER;
		
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RREP) || isDebugEnabledAt(DEBUG_AODV))){ 
			debug(" sending Reply: " + rp  + " dst " + ipdst );
		}

		aodv_message_send ( AODVTYPE_RREP, rp, rp.size(), ipdst, ttl_);
	}
	
	protected void sendError(AODV_RERR re, boolean jitter) {
		int ttl_;	
		double now = getTime();
    
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_RERR) || isDebugEnabledAt(DEBUG_AODV))){ 
			debug(" sending RERR: " + re);
		}
		re.re_type = AODVTYPE_RERR;

		aodv_message_broadcast( AODVTYPE_RERR, re, re.size(), 1);
	}
	
	/** ref: sec. 8.7 Hello Message */
	protected void sendHello() {
		int ttl_;
		double now = getTime();
		/* Allocate a RREP packet */		
		AODV_RREP rh = new AODV_RREP( );
		rh.rp_type = AODVTYPE_HELLO;
		rh.rp_hop_count = 1;
		rh.rp_dst = router_id;
		rh.rp_dst_seqno = seqno;
		rh.rp_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;
		aodv_message_broadcast( AODVTYPE_HELLO, rh, rh.size(), 1);
	}

	/** send the pkt to specific neighbor on specific if */
	protected void aodv_message_send ( int type, Object body, int body_size, long dst, int ttl)
	{
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SEND))
			debug(PKT_TYPES[type] + " sent from " + router_id + " to " + dst + ": " + body);
		/* memory allocate for protocol header */
		AODV_Packet aodv_pkt = new AODV_Packet(type, router_id); 
		aodv_pkt.setBody(body, body_size);

		// should enable router alert since the reply should be forwarded by intermediate nodes	
		forward( aodv_pkt, (long) router_id, dst, true, ttl, CONTROL_PKT_TYPE);
	}

	/**
	* Send the packet to every neighbor connected to this interfac. 
	*
	* For sending packets downward, we call the forward(), defined in Protocol.java  
	* void forward(PacketBody p_, long src_, long dest_, int dest_ulp_, boolean
	* routerAlert_, int TTL, int ToS, int link_id)
	* route-lookup forwarding routerAlert is set to be true, in which the packet is sent
	* in only one hop. In this case, whatever dst is irrevelent
	 */
	protected void aodv_message_broadcast ( int type, Object body, int body_size, int ttl)
	{
		/* memory allocate for protocol header */
		AODV_Packet aodv_pkt = new AODV_Packet(type, router_id); 
		aodv_pkt.setBody(body, body_size);
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SEND))
			debug(PKT_TYPES[type] + " broadcast from " + router_id + ": " + body + "ttl " + ttl );
		/* if route alert is true, pd ignore ttl */
		broadcast( aodv_pkt, (long) router_id, Address.ANY_ADDR, true, ttl, CONTROL_PKT_TYPE, Address.ANY_ADDR /*nexthop*/);
	}

	// for non ip pkt only, created ipkt first then call standard aodv_delay_broadcast()
	protected void aodv_delay_broadcast ( int type, Object body, int body_size, int ttl, AODV_RTEntry rt, double delay, boolean bcast)
	{
		InetPacket ipkt_;
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SEND))
			debug("delay** " + PKT_TYPES[type] + " broadcast from " + router_id + ": " + body +"for time " + delay);
		/* memory allocate for protocol header */
		AODV_Packet aodv_pkt = new AODV_Packet(type, router_id); 
		aodv_pkt.setBody(body, body_size);
		if (bcast == true || delay != 0.0) {
			AODV_TimeOut_EVT aodv_bcast_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_DELAY_BROADCAST, aodv_pkt);
			aodv_bcast_EVT.handle = setTimeout( aodv_bcast_EVT, delay);
		} else {
			broadcast( aodv_pkt, (long) router_id, Address.ANY_ADDR, true, ttl, CONTROL_PKT_TYPE, Address.ANY_ADDR /*nexthop*/);
		}
	}

	// for non ip pkt only, created ipkt first then call standard aodv_delay_forward()
	protected void aodv_delay_forward ( int type, Object body, int body_size, int ttl, AODV_RTEntry rt, double delay, boolean bcast)
	{
		InetPacket ipkt_;
		if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SEND))
			debug("delay* " + PKT_TYPES[type] + " broadcast from " + router_id + ": " + body +"for time " + delay);
		/* memory allocate for protocol header */
		AODV_Packet aodv_pkt = new AODV_Packet(type, router_id); 
		aodv_pkt.setBody(body, body_size);
		if (bcast == true) {
			ipkt_ = new InetPacket((long) router_id, Address.ANY_ADDR, 0/*protocol*/, ttl, 0/*hops*/, true /*routerAlert_*/, CONTROL_PKT_TYPE/*tos_*/, 0/*id*/, 0/*flag*/, 0/*frag offset*/, aodv_pkt, aodv_pkt.size, Address.ANY_ADDR /*next_hop*/);
		} else {
			ipkt_ = new InetPacket((long) router_id, rt.rt_dst, 0/*protocol*/, ttl, 0/*hops*/, true /*routerAlert_*/, CONTROL_PKT_TYPE/*tos_*/, 0/*id*/, 0/*flag*/, 0/*frag offset*/, aodv_pkt, aodv_pkt.size);

		}
		aodv_delay_forward(rt, ipkt_, delay, bcast);
	}

	/* Packet Transmission Routines */
	protected void aodv_delay_forward(AODV_RTEntry rt, InetPacket p, double delay, boolean bcast) {
		double now = getTime();
		if(p.getTTL() == 0) {
			if(isGarbageEnabled()) drop(p, "DROP_RTR_TTL");
			return;
		}
		if (rt != null) {
			p.setNextHop( rt.rt_nexthop);
		} else { // if it is a broadcast packet, do nothing
		}
		if (bcast == true) {
			AODV_TimeOut_EVT aodv_bcast_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_DELAY_FORWARD, p);
			aodv_bcast_EVT.handle = setTimeout( aodv_bcast_EVT, delay);
		} else {
			if (delay > 0) {
				AODV_TimeOut_EVT aodv_forword_EVT = new AODV_TimeOut_EVT(AODV_TimeOut_EVT.AODV_TIMEOUT_DELAY_FORWARD, p);
				aodv_forword_EVT.handle = setTimeout( aodv_forword_EVT, delay);
			} else {
				// no delay, sendout immediately
				downPort.doSending(p);
			}
		}
	}

	//////////////////////////////////////////////////////////////////////////
	// AODV Neighbor Management  Functions	
	//////////////////////////////////////////////////////////////////////////
	private void nb_insert(long id) {
		double now = getTime();