ospf_qos.java

QoS in wireless sensor network

	}

	/**
	 * On-demand version of calculating a path satisying specified requirements 
	 * to a destination. 
	 * return value: the nexthop list of the destination (interface from the src)
	 * Note that the type of elements in Vector is OSPF_SPF_vertex
	 */
	public Vector ospf_QoS_spf_on_demand_calculate ( OSPF_Area area, int dest, double bw_)
	{
		OSPF_SPF_vertex V;
		/*if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_SPF)))
			debug("   ospf_QoS_spf_on_demand_calculate: running Dijkstra for area " + area.area_id);*/

		/* Check router-lsa-self.  If self-router-lsa is not yet allocated,
			return this area's calculation. */
		if (area.ls_db.size() == 0 ) {
			if (isDebugEnabled()) debug("ospf_spf_calculate:Skip area " + area.area_id +"'s calculation due to empty router_lsa_self" );
			return null;
		}

		/* RFC2328 16.1. (1). */
		/* Initialize the algorithm's data structures. */ 
		/* Clear the list of candidate vertices. */ 
		TreeMapQueue candidate = new TreeMapQueue();

		/* Initialize the shortest-path tree to only the root (which is the
			router doing the calculation). */
		ospf_spf_init (area);
					
		V = area.spf_root;

		/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
			debug("V " + V._toString() );*/
			
		int now_ = (int)getTime();
		// Modified from OSPF: only need to reach the dest
		while ( V.vtx_id != dest ) {
			/* RFC2328 16.1. (2). */
			
			/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
				debug("calculate candidate V " + V.vtx_id  );*/
			ospf_QoS_spf_next (V, area, candidate, now_, bw_);
			
			/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
				debug("   #candidates = " + candidate.size());*/
			

			/* RFC2328 16.1. (3). */
			/* If at this step the candidate list is empty, the shortest-
			path tree (of transit vertices) has been completely built and
			this stage of the procedure terminates. */
			if (candidate.isEmpty())
				return null;

			/* Otherwise, choose the vertex belonging to the candidate list
			that is closest to the root, and add it to the shortest-path
			tree (removing it from the candidate list in the
			process). */ 
			V = (OSPF_SPF_vertex) candidate.dequeue();

			if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SPF))
				debug("   install vertex to SPF:" + V.vtx_id);
			/* Add to SPF tree. */
			/* RFC2328 16.1. (4). possible modify the routing table */
			// Tyan: all vertexes are now in vertex_list when created,
			//		make vertex intree now but modify routing table later
			//ospf_spf_install (V, area, now_);
			V.intree = true;

			/* Note that when there is a choice of vertices closest to the
		         root, network vertices must be chosen before router vertices
				 in order to necessarily find all equal-cost paths. */
			/* We don't do this at this moment, we should add the treatment
			     above codes. -- kunihiro. */

			/* RFC2328 16.1. (5). */
			/* Iterate the algorithm by returning to Step 2. */
		}
		return V.nexthops;
	}

	/////////////////////////////////////////////////////////////////////
	// QoS Precomputation
	///////////////////////////////////////////////////////////////////
	/**
	 * Appendex A. Pseudocode for the BF Based Pre-Computation Algorithm
	 * - assumes a hop-by-hop forwarding approach
	 * - does not handle equal cost multi-paths for simplicity
	 * - ***Note***: Here we only consider the bidirectional links.
	 *   During the LSA exchange process, if we have received a LSA from
	 *   a node, say A, we don't know its existence and would not calculate
	 *   a route to it.
	 * 
	 *  Local Variable:
	 *  - TT[n][h]: n:index in QoS_V_list; h:hop num
	 *  storing the max. bw and the next hop info. to this node n in the 
	 *  hth iteration. After calculation TT will be stored in QoS_RT 	
	 *  - S_prev: list of vertices that changed a bw value in the TT table
	 *  in the previous iteration.
	 *  - S_new: list of vertices that changed a bw value (in the TT table 
	 *  etc.) in the current iteration.
	 *
	 *  Each link info. (n,m) is required during the computation
	 *  can be obtained by first retrieve the router LSA from n
	 *  check each LSA link in this router LSA and get the link info.
	 *  To ensure the bidirection connectivity, we need to check the router LSA from m
	 */
	protected void ospf_QoS_spf_precompute ( OSPF_Area area )
	{
		int tot_node_num = QoS_V_list.size();
		
		if (tot_node_num == 0)
			return;

		/*if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS)))
			debug("   ospf_QoS_spf_precompute " + tot_node_num);*/
			
		///////////////////////////////////////////////////////////////////////////////////////////
		/* Fisrt Step: Initialization */
		// allocate an N*N table, here we assume the max hop # is N for simplicity
		TopologyTable[][] TT = new TopologyTable [tot_node_num][tot_node_num];
		for ( int i = 0; i < tot_node_num; i++ ) {
			for ( int j = 0; j < tot_node_num; j++ ) {
				TT[i][j] = new TopologyTable();
			}
		}
		TT[0][0].bw = QOS_INFINITY;
		
		// S_prev store the index in QoS_V_list, not the router id. Therefore, 
		// after retrieving an index from S_prev, need to map it to QoS_V_list to get router id
		Vector S_prev = new Vector();
		
		Router_LSA curr_lsa = null;
		Router_LSA next_lsa = null;
		Router_LSA_Link currentlink = null;
		double curr_bw_;
		
		// first curr_lsa is itself
		curr_lsa = (Router_LSA) area.ls_db.ospf_lsdb_lookup (OSPF_ROUTER_LSA, super.router_id, super.router_id);
		int link_num = curr_lsa.link_no;
		
		for ( int l = 0; l < link_num; l++) {
			currentlink = (Router_LSA_Link) curr_lsa.ls_link_list.elementAt(l);

			int encrypt_bw_ = currentlink.get_tos_metric(OSPF_QOS_TOS_BW);
			curr_bw_ = metric2bw(encrypt_bw_);
				
			/* (b) examine the lsa age, and check if it link back to V */
			switch (currentlink.type) {
				case LSA_LINK_TYPE_VIRTUALLINK:
				case LSA_LINK_TYPE_POINTOPOINT:
					next_lsa = (Router_LSA) area.ls_db.ospf_lsdb_lookup (OSPF_ROUTER_LSA,
											currentlink.link_id, currentlink.link_id);
					break;
				default:
					if (isErrorNoticeEnabled())
						error("ospf_QoS_spf_precompute()", " *** Warn *** : Invalid LSA link type "
												 + currentlink.type);
					continue;
			} /* end of switch */
			int now_ = (int) getTime();
			if (next_lsa== null || next_lsa.header.ospf_age_current (now_) == LSA_MAXAGE) {
				continue ; // next link
			}

			/* Examine if this LSA have link back to V */
			if ( ospf_lsa_has_link (next_lsa, curr_lsa) == 0 ) {
				continue;
			}
			// finally, set the values in TT
			// find the index in QoS_V_list
			int n_index = QoS_V_list.indexOf( new Integer(currentlink.link_id));
			if (n_index < 0) {
				if (isErrorNoticeEnabled())
					error("ospf_QoS_spf_precompute()", " unmatched node id " +
									super.router_id + " with " + currentlink.type );
			}
			TT[n_index][1].bw = Math.max( TT[n_index][1].bw, curr_bw_);
			if (TT[n_index][1].bw == curr_bw_ ) {
				TT[n_index][1].nexthops.removeAllElements();
				TT[n_index][1].nexthops.addElement(new Long(currentlink.link_id));
				TT[n_index][1].ifp = ospf_if_lookup_by_addr(currentlink.link_data);
			}
			/* update the S_prev */
			if (S_prev.indexOf(new Integer (n_index)) < 0) {
				S_prev.addElement( new Integer (n_index) );
			}
		}
		
		///////////////////////////////////////////////////////////////////////////////////////////
		// 2nd step: iterate for each hop, consider all possible number of hops
		for( int h=2; h < tot_node_num; h++) {
			Vector S_new = new Vector();
			for ( int m = 0; m < tot_node_num; m++) {
				TT[m][h].copy( TT[m][h-1]);
			}
			int prev_num = S_prev.size();
			for (int n = 0; n < prev_num; n++) {
				int n_index = ((Integer) S_prev.elementAt(n)).intValue();
				int r_id = ((Integer) QoS_V_list.elementAt(n_index)).intValue();
				curr_lsa = (Router_LSA) area.ls_db.ospf_lsdb_lookup (OSPF_ROUTER_LSA, r_id, r_id);
				
				link_num = curr_lsa.link_no;
				for ( int l = 0; l < link_num; l++) {
					currentlink = (Router_LSA_Link) curr_lsa.ls_link_list.elementAt(l);

					int encrypt_bw_ = currentlink.get_tos_metric(OSPF_QOS_TOS_BW);
					curr_bw_ = metric2bw(encrypt_bw_);
				
					/* (b) examine the lsa age, and check if it link back to V */
					switch (currentlink.type) {
						case LSA_LINK_TYPE_VIRTUALLINK:
						case LSA_LINK_TYPE_POINTOPOINT:
							next_lsa = (Router_LSA) area.ls_db.ospf_lsdb_lookup (OSPF_ROUTER_LSA,
											currentlink.link_id, currentlink.link_id);
							break;
						default:
							if (isErrorNoticeEnabled())
								error("ospf_QoS_spf_precompute()", " *** Warn *** : Invalid LSA link type "
												 + currentlink.type);
							continue;
					} /* end of switch */
					int now_ = (int) getTime();
					if (next_lsa == null || next_lsa.header.ospf_age_current (now_) == LSA_MAXAGE) {
						if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS)))
							debug("   ospf_QoS_spf_precompute null next_lsa: cur " + r_id + " next :" + currentlink.link_id );
						continue ; // next link
					}

					/* Examine if this LSA have link back to V */
					if ( ospf_lsa_has_link (next_lsa, curr_lsa) == 0 ) {
						if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS)))
							debug("   ospf_QoS_spf_precompute not bi-direction: cur " + r_id + " next :" + currentlink.link_id );
						continue;
					}
					int m_index = QoS_V_list.indexOf( new Integer(currentlink.link_id));
					if (m_index < 0) {
						if (isErrorNoticeEnabled())
							error("ospf_QoS_spf_precompute()", " unmatched node id " +
									super.router_id + " with " + currentlink.type );
					}
				
					if ( Math.min( TT[n_index][h-1].bw, curr_bw_ ) > TT[m_index][h].bw ) {
						TT[m_index][h].bw	= Math.min( TT[n_index][h-1].bw, curr_bw_ );
						TT[m_index][h].nexthops	= (Vector) TT[n_index][h-1].nexthops.clone();
						TT[m_index][h].ifp	= TT[n_index][h-1].ifp;
					} // when multiple equal-cost paths exist
					else if ( Math.min( TT[n_index][h-1].bw, curr_bw_ ) == TT[m_index][h].bw ) {			
						for (int i = 0; i < TT[n_index][h-1].nexthops.size(); i++) {
							if ( TT[m_index][h].nexthops.indexOf( new Long( ((Long) TT[n_index][h-1].nexthops.elementAt(i)).longValue() )) < 0 ) {	
								TT[m_index][h].nexthops.addElement( new Long( ((Long) TT[n_index][h-1].nexthops.elementAt(i)).longValue() ));
							}
						}					
					}
					
					if (S_new.indexOf(new Integer (m_index)) < 0) {
						S_new.addElement( new Integer (m_index) );
					}
				}
			}
			S_prev = (Vector) S_new.clone();
		}
		
		///////////////////////////////////////////////////////////////////////////////////////////		
		// 3rd step: after calculating all hops, we can store it to the routing table
		/**
		 * We can have two design choices. One is to keep TT table alive all the time.
		 * Thus, whenever a request arrives, we can find the min. hop path satisfying
		 * the bw requirement. Keep in mind that a route with max. bw might not be 
		 * the min. hop route. The second design choice is to record the max. bw route
		 * as well as the min. hop route in the routing table. 
		 * In the first choice we keep two kinds of routing table but can provide 
		 * more options for different bw requirementsthe while the second approach
		 * only keep one table but only provide one choice. Since in the second
		 * choice we need to modify the structure of routing entry, RTEntry.
		 * In this implementation, we choose the first approach for the simplicity. 
		 */
		if( QoS_RT != null) QoS_RT = null;
		QoS_RT = new TopologyTable [tot_node_num][tot_node_num];
		for (int i=1; i < tot_node_num; i++) {
			for (int j=1; j < tot_node_num; j++) 
				QoS_RT[i][j] = (TopologyTable) TT[i][j].clone();
		}		

	}
	////////////////////////////////////////////////////////////////////////////////////////
	// Supporting Functions
	
	/** transfer the value of the TOS metric (16 bits) to bandwidth value,
	    units: bits/sec, ref: sec3.2.1 */
	public static double metric2bw ( int metric) 
	{
		double exp_val = (double) (metric >> OSPF_QOS_METRIC_BW_MANT_LEN);
		return( 8*(metric & OSPF_QOS_BW_MANT_MASK) * Math.pow(OSPF_QOS_BW_BASE, exp_val) );
	}
	/* input units: bits/sec */ 
	public static int bw2metric ( double bw) 
	{
		int i;
		double bytes_val = bw / 8;
		int max_pow = 1 << OSPF_QOS_METRIC_BW_EXP_LEN;
		double max_base = Math.pow(2.0, (double) OSPF_QOS_METRIC_BW_MANT_LEN) -1;
		
		// check whether the input value is too high
		assert  bytes_val <= (max_base * Math.pow(OSPF_QOS_BW_BASE, max_pow)):
				"the input value exceeds the max. allowed value: bw=" + bw;
		
		for (i = 0; i < max_pow; i++) {
			if ( bytes_val <= (max_base * Math.pow(OSPF_QOS_BW_BASE, (double) i)) ) {
				break;
			}
		}
		int exp_val  = i;
		int mant_val = (int) (bytes_val / Math.pow(OSPF_QOS_BW_BASE, (double) i));
		return ( (int) (exp_val << OSPF_QOS_METRIC_BW_MANT_LEN) | mant_val );
	}
}