ospf_qos.java

QoS in wireless sensor network

// @(#)OSPF_QoS.java   9/2002
// Copyright (c) 1998-2002, 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.ospf;

import java.util.*;
import java.lang.*;

import drcl.inet.data.*;
import drcl.net.*;
import drcl.util.queue.TreeMapQueue;

 /* xxx: Note that current implementation only supports BW calculation.
 *  Delay requirement is not supported. need to add delay to InterfaceInfo */

/**
 *  QoS extension to OSPF.
 *  Mainly based on RFC 2676 QoS Routing Mechanisms and OSPF Extensions.
 *  Without explicit indication.  The following reference is from RFC 2676.
 *  <p>As described in sec. 1,  the purpose of the extension is to 
 *  "Obtain the information needed to compute QoS paths and select a
 *  path capable of meeting the QoS requirements of a given request"
 *  In this QoS extension, We use two kinds of mechanism to calculate the
 *  QoS routes. One is the on-demand calculation modified from the standard
 *  Dijkstra's algorithm. The QoS considered here is bandwidth requirement.
 *  When doing the calculation, we only consider the link with avail. bw
 *  larger than the requirement. 
 *  
 *  <p>The second mechanism is the precomputation approach.
 *  It calculates the routes to each destination and obtains the max. bw on 
 *  route and the next hop info, which are recorded in the routing table.
 *  Because of the changes in the link metric, the precomputation needs to
 *  be done periodically or by event trigger.
 *  The dynamic changes in the link metrics would trigger the recalculation
 *  of all paths. However, this requires the cooperations of other
 *  signalling protocols such as RSVP or MPLS LDP. Hence, in the current stage,
 *  the extension does not handle the dynamics of metrics. We only left the 
 *  interface for the future exploration.
 *  
 *  <p>The implementation does support equal-cost paths for multiple nexthops
 *
 *  @author Wei-peng Chen
 *  @see OSPF
 */ 
public class OSPF_QoS extends drcl.inet.protocol.ospf.OSPF
{
	/** QoS Option bit (the least siginificant bit in the Options field)
	 , ref: sec. 3.1 */
	final static int OSPF_OPTIONS_BIT_QOS			= 1;	

	/** TOS type, ref: sec. 3.2 
	    backward compatible with OSPF v1 */
	final static int OSPF_QOS_TOS_BW			= 40;
	final static int OSPF_QOS_TOS_DELAY			= 48;
	
	/** # of bits of exponent and mantissa for BW in TOS metric field, 
	 *   exp is put in the MSB
	 */ 
	final static int OSPF_QOS_METRIC_BW_EXP_LEN		= 3;
	final static int OSPF_QOS_METRIC_BW_MANT_LEN		= 13;
	
	/** the base for the exponent part in TOS metric calculation */
	final static double OSPF_QOS_BW_BASE			= 8.0;
	final static int OSPF_QOS_BW_MANT_MASK			= 0x1FFF;
	final static double QOS_INFINITY				= Double.MAX_VALUE;
	
	/**	An example to show when to execute precomputation,
	 * not explicitly stated in RFC */
	final static int OSPF_QOS_LSA_CHANGE_TRIGGER_TIMES	= 50;
	
	/** Redefine Debug level of handling timeout events. */
	public static final int DEBUG_QOS  			= 8;
	static final String[] DEBUG_LEVELS = {
		"sample", "neighbor", "send", "spf", "refresh", "lsa", "ack", "timeout", "qos"
	};

	/**
	 * QoS options value for OSPF, ref: sec.3.2
	 */
	private int			QoS_options;
	/* bit of supporting periodical precompute */
	private boolean		periodical_precompute = false ;
	/* bit of supporting dynamic precompute */
	private boolean		dynamic_precompute = false ;
	
	/////////////////////////////////////////////////////////////////
	// Timeout Handling Functions
	private class OSPF_QoS_TimeOut_EVT extends drcl.inet.protocol.ospf.OSPF_TimeOut_EVT {
		/* 0~8 are standard timeout event in OSPF */
		public static final int OSPF_QOS_TIMEOUT_PRECOMPUTE	= 9; 
		final String[] TIMEOUT_TYPES = {
			"HELLO", "LS_REFRESH", "MAXAGE_REACHED", "DELAY_ACK",
			"NBR_INACTIVE", "DBDESC_RETX", "LSA_RETX", "LSREQ_RETX", "DELAY_FLOOD", "PRECOMPUTE" };
			
		public OSPF_QoS_TimeOut_EVT(int tp_, Object obj_) {
			super(tp_, obj_) ;
		} 
		public String toString()
		{ return TIMEOUT_TYPES[EVT_Type] + ", " + EVT_Obj; }

	}
	OSPF_QoS_TimeOut_EVT precompute_EVT = null;
	
	/** precomputation period (unit: second) */
	private int precompute_period;
	
	protected void timeout(Object evt_)
	{
		super.timeout(evt_);
		int type = ((OSPF_TimeOut_EVT)evt_).EVT_Type;
		switch(type) {
			case OSPF_QoS_TimeOut_EVT.OSPF_QOS_TIMEOUT_PRECOMPUTE:
				if (evt_ != precompute_EVT) {
					error("QoS timeout()", " ** ERROR ** where does this come from? " + evt_);
					break;
				}
				OSPF_Area area_ = (OSPF_Area) precompute_EVT.getObject();
				ospf_QoS_spf_precompute ( area_ ); 
				break;
		}
		return;
	}

	////////////////////////////////////////////////////////////////
	// private variables for precomputation only
	private Vector QoS_V_list	= null ; /* set of vertices, router id are stored */
  
	private class TopologyTable {
		/* maximum available bandwidth (as known thus far) on a path of 
		at most h hops between vertices s and n*/
		double			bw;
		/* nexthop is the first hop on that path (a neighbor of s). Storing type: long */
		Vector			nexthops;
		/* the interfqace to the next hop from the source */
		OSPF_Interface 	ifp;
		
		TopologyTable() { bw=0; nexthops = new Vector(); ifp = null; }
		
		TopologyTable(double bw_, Vector nexthops_, OSPF_Interface ifp_) 
		{ bw=bw_; nexthops = (Vector) nexthops_.clone(); ifp = ifp_; }
		
		protected void copy( TopologyTable src) {
			bw=src.bw; nexthops = (Vector) src.nexthops.clone(); ifp = src.ifp;
		}
		protected Object clone()
		{
			TopologyTable t = new TopologyTable(bw, nexthops, ifp);
			t.bw = bw;
			t.ifp = ifp;
			return t;
		}
	}
	/** QoS_RT[1..N, 1..H]: topology table entry, whose (n,h) entry is a tab_entry 
	 *  It is created when doing precomputation 
	 */
	private TopologyTable[][] QoS_RT	= null; 
	
	/* record the lsa change times in order to trigger a precomputation */
	private int lsa_change_times			= 0;
	
	//////////////////////////////////////////////////////////////////////////////////////
	/** Constructor. */
	public OSPF_QoS()
	{
		super();

		// initialize QoS_V_list
		QoS_V_list = new Vector();
		QoS_V_list.removeAllElements();
	}

	public String info()
	{
		int now_ = (int)getTime();
		StringBuffer sb_ = new StringBuffer();
		try {
		//sb_.append("Router id:" + super.router_id + "\n");
		sb_.append("QoS_V_list:");
		if (QoS_V_list == null || QoS_V_list.size() == 0)
			sb_.append("<none>\n");
		else {
			sb_.append("\n");
			for (int i=0; i<QoS_V_list.size(); i++) {
				int vtx = ((Integer) QoS_V_list.elementAt(i)).intValue();
				sb_.append("   vtx" + i + ": " + vtx);
			}
		}
		sb_.append("QoS_RT: ");
		if( QoS_RT == null) {
			sb_.append("<none>\n");
		} else {
			sb_.append("\n");
			for (int i=0; i<QoS_V_list.size(); i++) {
				int vtx = ((Integer) QoS_V_list.elementAt(i)).intValue();
				for (int j=0; j< QoS_RT[i].length; j++) {
					if(  QoS_RT[i][j] != null) {
						sb_.append(" [" + i + "][" + j + "] " + vtx +" bw " + QoS_RT[i][j].bw + " next ");
						for( int k = 0; k < QoS_RT[i][j].nexthops.size(); k++) {
							sb_.append( ((Long) QoS_RT[i][j].nexthops.elementAt(k)).longValue() + " " );
						}
					}
				}	
				sb_.append("\n");
			}
		}
		}
		catch (Exception e) {
			e.printStackTrace();
		}
		return super.info() + sb_.toString();
	}
	
	public void reset()
	{
		super.reset();
		if (QoS_V_list != null) {
			QoS_V_list.removeAllElements();
			QoS_V_list = null;
		}
		QoS_RT = null;
		lsa_change_times = 0;
		
		if (periodical_precompute == true && precompute_EVT.handle != null) {
			cancelTimeout(precompute_EVT.handle);
			precompute_EVT.setObject(null);
			precompute_EVT.handle = null;
		}

	}

	/////////////////////////////////////////////////////////////////////////////
	// Interface to the public, some are temporarily creatred for demo
	/** set the tos type value for QoS extension, BW=40, DELAY=48 */

	/** Set value of TOS type, either 40( for bw) or 48 (for delay) */	
	public void set_QoS_options (int options_) 
	{
		QoS_options = options_;
	}
	
	public void show_QoS_options ( ) 
	{
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			debug( " QoS option " + QoS_options );
		}
	}

	/** Set the bit whether to enable precomputation periodically */	
	public void set_periodical_precompute_options (boolean options_, int period) 
	{
		periodical_precompute = options_;
		precompute_period = period;
		if( options_ == true) {
			// since we only support area, the following area object use the first index
			// if multiple areas are supported, this must be modified
			precompute_EVT = new OSPF_QoS_TimeOut_EVT(OSPF_QoS_TimeOut_EVT.OSPF_QOS_TIMEOUT_PRECOMPUTE, (OSPF_Area) area_list.elementAt(0));
			precompute_EVT.handle = setTimeout( precompute_EVT, precompute_period);
		}
	}
	
	/** Set the bit whether to execute precomputation according to dynamic changes,
	 * In this example, received lsa # is the reference */	
	public void set_dynamic_precompute_options (boolean options_) 
	{
		dynamic_precompute = options_;
	}
	
	/** given a destination and the required the bw, print the nexthops, on-demand version */
	public void show_QoS_ondemand_nexthop_by_bw ( int dest, double bw_) {
		int n_index = QoS_V_list.indexOf( new Integer(dest));
		if ( (n_index < 0) && (isDebugEnabled()) ) {
			debug("   ospf_qos_on_demand: have not received lsa from dest " + dest );
			return;
		}
		
		Vector nexthops_ = ospf_QoS_spf_on_demand_calculate ( (OSPF_Area) area_list.elementAt(0), dest, bw_);
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			if( nexthops_ == null) {
				debug("   ospf_qos_on_demand: no satisfied nexthop for dest " + dest + " bw: " + bw_ );
			} else {
				StringBuffer sb_ = new StringBuffer();
				sb_.append("   ospf_qos_on_demand: dest " + dest + " bw: " + bw_ +" next hops: " );
				for (int i = 0; i < nexthops_.size(); i++) {
					sb_.append( ((OSPF_SPF_vertex)nexthops_.elementAt(i)).vtx_id + " ");
				}
				debug(sb_.toString());
			}
		}
	}

	/** given a destination and the required the bw, print the nexthops, precompute version */
	public void show_QoS_precompute_nexthop_by_bw ( int dest, double bw_) {
		int tot_node_num = QoS_V_list.size();
		StringBuffer sb_ = new StringBuffer();