ospf_qos.java

QoS in wireless sensor network

		int n_index = QoS_V_list.indexOf( new Integer(dest));
		if ( (n_index < 0) && (isDebugEnabled()) ) {
			debug("   ospf_qos_precompute: have not received lsa from dest " + dest );
			return;
		}
		for (int h = 1; h < tot_node_num; h++) {
			// find the min hop path satisfying bw_
			if( QoS_RT[n_index][h].bw >= bw_ ) {
				if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
					sb_.append("   ospf_qos_precompute: dest " + dest + " bw: " + bw_ + " hop: " + h + " next hop: " );
					for( int k = 0; k < QoS_RT[n_index][h].nexthops.size(); k++) {
						sb_.append( ((Long) QoS_RT[n_index][h].nexthops.elementAt(k)).longValue() + " " );
					}
					debug(sb_.toString());
					return;
				}
			}
		}
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			debug("   ospf_qos_precompute: no satisfied nexthop for dest " + dest + " bw: " + bw_ );
		}
	}
	
	//////////////////////////////////////////////////////////////////////////////
	// QoS metrics composition
	//////////////////////////////////////////////////////////////////////////////
	/**
	 *  make router lsa pkt to describe its neighbor 
	 *  LSA which supports QoS may carry more than one tos metric
	 */ 
	protected Router_LSA ospf_make_router_lsa (OSPF_Area area)
	{
		// Tyan: 05/08/2001, 10/18/2001
		// cancel previous refresh event if any
		if (area.lsa_refresh_timer != null) {
			cancelTimeout(area.lsa_refresh_timer);
			area.lsa_refresh_timer = null;
		}
		
		/* get links to describe */
		int i;
		int if_no = area.if_list.size();

		/* get current database copy */
		OSPF_LSA copy = area.router_lsa_self;
		OSPF_LSA_Header header;
		if (copy == null)
			header = new OSPF_LSA_Header(OSPF_ROUTER_LSA, router_id, router_id);
		else
			header = new OSPF_LSA_Header(copy.header.lsh_seqnum+1, OSPF_ROUTER_LSA, router_id, router_id);
		// dont call ospf_set_birth() as this router creates this lsa
		header.birth = (int)getTime();

		Router_LSA lsa = new Router_LSA(header);
 		lsa.from = (OSPF_Neighbor) null;
		lsa.scope = area;
		area.router_lsa_self = lsa;

		// Tyan0504: shouldn't cancel it
		/*
		// cancel delayed flood event if any
		if (flood_EVT.getObject() == area) {
			cancelTimeout(flood_EVT);
			flood_EVT.setObject(null);
		}
		*/
		
		InterfaceInfo iinfo_ ;
		for (i = 0; i < if_no; i++) {
			OSPF_Interface oif = (OSPF_Interface) area.if_list.elementAt(i);

			iinfo_ = drcl.inet.contract.IFQuery.getInterfaceInfo( oif.if_id, oif.out_port ); 

			/* if interface is not enabled, ignore */
			if (oif.state <= IFS_LOOPBACK)
				continue;

			/* if interface is stub, ignore */
			if ( oif.ospf_interface_count_full_nbr() != 0 ) {
				Router_LSA_Link rlsd = lsa.make_ospf_router_lsd (oif);
				
				// changes for QoS only
				//////////////////////////////////////////////////////////////
				if (QoS_options == OSPF_QOS_TOS_BW ) {
					double bw_ = iinfo_.getBandwidth();
					/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
						debug(" bw " + bw_ );*/

					int encrypt_bw = bw2metric(bw_);
					if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
						debug(" bw=" + bw_ + ", en_bw=" + encrypt_bw + ", oif.if_id=" + oif.if_id
										+ ", oif.out_port=" + oif.out_port + ", iinfo=" + iinfo_);

					rlsd.add_tos_metric(OSPF_QOS_TOS_BW, encrypt_bw);
				} else if (QoS_options == OSPF_QOS_TOS_DELAY ) {
					// xxx: iinfo needs to add delay info
				}
				//////////////////////////////////////////////////////////////
				
				lsa.link_no++;
				lsa.ls_link_list.addElement(rlsd);
			}
		}
		
// xxx: set E & B bit:
		
		// Tyan: 05/08/2001, 10/18/2001
		area.lsa_refresh_timer =
			setTimeout(new OSPF_TimeOut_EVT( OSPF_TimeOut_EVT.OSPF_TIMEOUT_LS_REFRESH,
									lsa ), LS_REFRESH_TIME);

		// changes for QoS only: set options bit (the least siginificant bit in the Options field)
		lsa.getHeader().set_options( (lsa.getHeader().get_options() | (0x01 << (OSPF_OPTIONS_BIT_QOS-1))) );
		
		/*
		if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			debug("   *** ospf_make_router_lsa: options " + lsa.getHeader().get_options() );
		}*/
		
		return lsa;
	}		

	/**
	 * Besides the normal operations, record the special metrics recorded in LSA
	 * for QoS path calculation 
	 */
	protected void ospf_lsdb_install ( OSPF_LSA new_lsa, OSPF_LSA old_lsa, OSPF_Area area)
	{
		super.ospf_lsdb_install( new_lsa, old_lsa, area);
		// check whether the Options value is correct
		int options_ = new_lsa.getHeader().get_options();
		/*if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			debug("   *** ospf_lsdb_install: add " + new_lsa.getHeader().lsh_id + " to QoS_V_list "
				+ " options " + options_);
		}*/

		if ( (options_ & (0x01 << (OSPF_OPTIONS_BIT_QOS-1))) == 0 ) {
			// unsupported options
			return;
		}
		// record the node to QoS_V_list, if it's new
		if ( QoS_V_list.indexOf( new Integer( new_lsa.getHeader().lsh_id )) < 0) {
			QoS_V_list.addElement( new Integer( new_lsa.getHeader().lsh_id ));
			if (isDebugEnabled() && (isDebugEnabledAt(DEBUG_SAMPLE) || isDebugEnabledAt(DEBUG_QOS))) {
			//if (isDebugEnabled() && isDebugEnabledAt(DEBUG_QOS)) {
				debug("   ospf_lsdb_install: add " + new_lsa.getHeader().lsh_id + " to QoS_V_list size()" + QoS_V_list.size());
			}
		}
		
		// set up an example to trigger the precomputation condition
		if ( (dynamic_precompute == true) && (lsa_change_times >= OSPF_QOS_LSA_CHANGE_TRIGGER_TIMES) &&
			 (new_lsa.header.lsh_type == OSPF_ROUTER_LSA) ) {
			lsa_change_times = 0;
			ospf_QoS_spf_precompute ( (OSPF_Area) new_lsa.scope ); 
		} else 
			lsa_change_times++;
	}
	

	////////////////////////////////////////////////////////////////////////////
	// QoS On-demand Path calculation
	////////////////////////////////////////////////////////////////////////////
	
	/**
	 *  RFC2328 Section 16.1 (2). 
	 *  V: newly-added vertex
	 *  Add V's neighbors to candidate list (sorted by cost) 
	 *  QoS extension: remove the links with BW less than the requirements
	 *  currently support the BW option only
	 */
	private void ospf_QoS_spf_next (OSPF_SPF_vertex V, OSPF_Area area, TreeMapQueue candidate, int now_, double bw_)
	{
		OSPF_LSA w_lsa = null;

		Router_LSA  r_lsa = (Router_LSA) V.vtx_lsa;
		int link_num = r_lsa.link_no;
		int l, i;
		Router_LSA_Link currentlink = null;

		/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
			debug(" link_num  " + link_num  );*/
		
		for ( l = 0; l < link_num; l++) {
			/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
				debug(" (" + l + ")  type " + V.vtx_lsa.header.lsh_type  );*/

			/* In case of V is Router-LSA. */
			if (V.vtx_lsa.header.lsh_type == OSPF_ROUTER_LSA) {
				currentlink = (Router_LSA_Link) r_lsa.ls_link_list.elementAt(l);

				/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
					debug("id " + currentlink.link_id );*/

				/////////////////////////////////////////////////////////////////////////////
				// QoS BW requirements: delete links with avail. BW less than the requirement
				/////////////////////////////////////////////////////////////////////////////
				int encrypt_bw_ = currentlink.get_tos_metric(OSPF_QOS_TOS_BW);
				
				/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
					debug(" en_bw " + encrypt_bw_ );*/

				double curr_bw_ = metric2bw(encrypt_bw_);
				
				/*if (isDebugEnabled() && isDebugEnabledAt(DEBUG_SAMPLE))
					debug(" en_bw " + encrypt_bw_ + " bw " + curr_bw_ );*/

				if ( curr_bw_ < bw_ )
					continue;
				/////////////////////////////////////////////////////////////////////////////
				
				/* (a) If this is a link to a stub network, examine the next
				 link in V's LSA.  Links to stub networks will be
				 considered in the second stage of the shortest path
				 calculation. */
				if (currentlink.type == LSA_LINK_TYPE_STUB)
					continue;

				/* (b) Otherwise, W is a transit vertex (router or transit
			     network).  Look up the vertex W's LSA (router-LSA or
				 network-LSA) in Area A's link state database. */
				/* (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:
						/* ref: A.4.2 explan of link id: 
						if the link type is either router or transit network,the link id will be 
						the same as the lsa link state id, in order to look up this lsa in the database */
						w_lsa = (Router_LSA) area.ls_db.ospf_lsdb_lookup (OSPF_ROUTER_LSA,
											currentlink.link_id, currentlink.link_id);
						break;
					default:
						if (isErrorNoticeEnabled())
							error("ospf_spf_next()", " *** Warn *** : Invalid LSA link type "
								+ currentlink.type);
						continue;
				} /* end of switch */
			} 

			/* (b cont.) If the LSA does not exist, or its LS age is equal
			 to MaxAge, or it does not have a link back to vertex V,
			 examine the next link in V's LSA. */
			if (w_lsa== null || w_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 (w_lsa, V.vtx_lsa) == 0 ) {
				//if (isDebugEnabled()) 
				//	debug("      Z: The LSA doesn't have a link back: " + w_lsa);
				continue;
			}

			/* (c) If vertex W is already on the shortest-path tree, examine
				the next link in the LSA. */
			if( vertex_in_tree( currentlink.link_id, area.vertex_list ) )
				continue;
						
			/* (d) Calculate the link state cost D of the resulting path
			 from the root to vertex W.  D is equal to the sum of the link
			 state cost of the (already calculated) shortest path to
			 vertex V and the advertised cost of the link between vertices
			 V and W. */

			/* calculate link cost D. */
			int dist;
			if (V.vtx_lsa.header.lsh_type == OSPF_ROUTER_LSA)
				dist = V.vtx_distance + currentlink.metric;
			else
				dist = V.vtx_distance;

			/* Is there already vertex W in candidate list? */
			// Tyan: link type and vtx type are different stories.
			OSPF_SPF_vertex CW = ospf_vertex_lookup (candidate, currentlink.link_id);//, currentlink.type);
			if ( CW == null) {
				/* Calculate nexthop to W. */
				OSPF_SPF_vertex W = ospf_vertex_lookup (area.vertex_list, currentlink.link_id);
				if (W == null) {
					W = new OSPF_SPF_vertex ();
					area.vertex_list.addElement(W);
				}
				W.set(w_lsa, dist, false);				W.parent = V; // Tyan
				ospf_nexthop_calculation (area, V, W);
				ospf_install_candidate (candidate, W);
			} else {
				/* if D is greater than. */
				if (CW.vtx_distance < dist) {
					continue;
				}
				/* equal to. */
				else if ( CW.vtx_distance == dist) {
					/* make vertex W. */
					OSPF_SPF_vertex W = new OSPF_SPF_vertex (w_lsa, dist, false);
					/* Calculate nexthop to W. */
					ospf_nexthop_calculation (area, V, W);
					/* add next hop list from W to CW */
					int hop_no = W.nexthops.size();
					for ( i = 0; i < hop_no; i++) {
						Object tmp_ = W.nexthops.elementAt(i);
						if (CW.nexthops.indexOf(tmp_) < 0)
							CW.nexthops.addElement(tmp_);
					}
					W.nexthops.removeAllElements();
				}
				/* less than. */
				else {
					/* make vertex W. */
					OSPF_SPF_vertex W = new OSPF_SPF_vertex (w_lsa, dist, false);

					/* Calculate nexthop. */
					ospf_nexthop_calculation (area, V, W);
					// Remove old vertex from candidate list. 
					// and replace it with new in vertex_list
					candidate.remove(CW);
					area.vertex_list.setElementAt(W, area.vertex_list.indexOf(CW));

					/* Install new to candidate. */
					ospf_install_candidate (candidate, W);
				}
			}
		} /* end of for each link */