localenvironment.java

发布/订阅系统路由重配算法,可应用于ad hoc环境

/*
 * project: RebecaSim
 * package: broker
 * file:    LocalEnvironment.java
 * 
 * version: 0.1
 * date:    11.05.2005
 * 
 * This software is part of the diploma thesis "Ein adaptives Brokernetz 
 * für Publish/Subscribe Systeme".
 */
package broker;

import java.util.*;
import graph.*;
import sim.*;
import util.*;

/**
 * TODO Insert class description here.
 *
 * @version 11.05.2005
 * @author  parzy
 */
public class LocalEnvironment{

	private static class Entry{
		double hits;
		double time;
		
		Entry(double hits, double time){
			this.hits = hits;
			this.time = time;
		}
	}
	

	private Broker bThis = null;
	private Simulation sim = null;
	private Network net = null;
	
	private Property interests = new Property();
	private double size = 0;
	private double sum = 0;
	private double average = 0;
	private double events = 0;
	
	
	
	
//	private Property parent = null;
//	private Property lastUpdate = null;
//	private Property commonEvents = null;
//	private Network net = null;
//	private double updateInterval = 4;
	

	/**
	 * Creates a new local environment for broker bThis in Simulation sim.
	 * @param bThis the local broker.
	 * @param sim the current simulation.
	 */
	public LocalEnvironment(Simulation sim, Network net, Broker bThis){
		this.bThis = bThis;
		this.sim = sim;
		this.net = net;
	}
	
	/**
	 * Sets the common interests (common notifications shared by this Broker
	 * and the broadcast's source). The environment is also updated
	 * and stale entries are removed.
	 * @param source the broadcast's source.
	 * @param hits number of common notifications.
	 */
	public void setInterest(Broker source, double hits){

		Broker broker;     // current broker
		Entry entry;       // current entry
		LinkedList nodes;  // stale brokers
		double time;       // current simulation time
		double stale;      // time before an entry gets stale
		boolean contained; // flag whether source is already contained
		//double d;
		
		// not allowed for the same broker
		if(source == bThis){
			return;
		}
		
		// determine times
		time = sim.getTime();
		stale = time - Broker.updateInterval;
		nodes = new LinkedList();
		
		// remove stale entries and update source when contained
		contained = false;
		for(ResetableIterator it = interests.getElements(); it.hasNext(); ){
			// get next broker
			broker = (Broker)it.next();
			entry = (Entry)broker.getProperty(interests);
			// update source
			if(source == broker){
				contained = true;
				// TODO change back?
//				d = (hits + entry.hits) / 2.0d;
//				sum = sum + d - entry.hits;
//				entry.hits = d;
				
				sum = sum + hits - entry.hits;
				entry.hits = hits;
				entry.time = time;
			}else{
				// store stale entry for removal
				if(entry.time < stale){
					nodes.add(broker);
					sum -= entry.hits;
					size -= 1;
				}
			}
		}

		// physical removal of stale entries
		for(Iterator it = nodes.iterator(); it.hasNext(); ){
			((Broker)it.next()).removeProperty(interests);
		}
		
		// add source, if not already contained
		if(!contained){
			source.setProperty(interests,new Entry(hits,time));
			sum += hits;
			size += 1;
		}
		
		// recalc the average
		calcAverage();
	}
	
	/**
	 * Sets the number of consumed notifications, in which this broker
	 * is interested in.
	 * @param events number of events.
	 */
	public void setEvents(double events){
		this.events = events;
		calcAverage();
	}
	
	// TODO: mit Ausarbeitung vergleichen
	/**
	 * Calculates the average number of shared events between to brokers
	 * of the environment.
	 */
	private void calcAverage(){
		average = Math.max(sum-events,0) / Math.max(size-1,1);
	}

	/**
	 * Returns true, if a direct connection to the first broker on the
	 * path seems to be favorable.
	 * @param path the path to examine.
	 * @return true if a direct connection to the first broker on the path
	 *         seems to be
	 * @throws NullPointerException if interests are missing
	 */
	public boolean evaluate(Broker[] path){
		
		int n; // the path length
		
		double d;   // distance
		double p;   // processing costs
		double c;   // communication costs
		double i;   // interests
		double i2;
		double a;   // average

		// path to short
		n = path.length;
		if(n <= 2){
			return false;
		}
	
		if (Broker.heuristic == Broker.COSTS_AND_INTERESTS) {
			// initialization
			d = net.getCommunicationCosts(path[n-1],path[n-2]);
			// calculation of the distance
			for(int j = n-3; j >=0; j--){
				p = net.getProcessingCosts(path[j+1]);
				c = net.getCommunicationCosts(path[j+1],path[j]);
				i = ((Entry)path[j].getProperty(interests)).hits;
				// TODO change back
				i2 = ((Entry)path[j+1].getProperty(interests)).hits;
				a = Math.min(Math.min(i,average),i2);
				
//				a = Math.min(average,i);
				d = (i-a)/Math.max(1.0,i)*(d+p)+c;
				
				// TODO change back
				//d = c;
				//i = 1;	
				
			}
			// communication costs to compare to
			c = net.getCommunicationCosts(path[n-1],path[0]);
			//System.out.println("d: "+d+" c: "+c+" average:"+average+" sum: "+sum+" size: "+size);
			return c < d;
		}
		else if(Broker.heuristic == Broker.COSTS) {
			c = net.getCommunicationCosts(path[n-1],path[0]);
			for(int j = n-3; j >=0; j--){
				d = net.getCommunicationCosts(path[j+1],path[j]);
				if (c < d) {
					return true;
				}
			}
			return false;
		}
		else if (Broker.heuristic == Broker.INTERESTS) {
			i = getInterest(path[0]);
			//i += path[0].getInterest(path[n-1]);
			for(int j = n-2; j >=0; j--){
				d = path[j].getInterest(path[j+1]);
				//d += path[j+1].getInterest(path[j]);
				if (d < i) {
					
//					// TODO remove
//					for(int k=n-2; k>=0; k--){
//						System.out.print(path[k].getInterest(path[k+1])+" ");
//					}
//					System.out.println(" - "+getInterest(path[0]));
									
					return true;
				}
			}
			
			// old impl
//			return ((Entry)path[0].getProperty(interests)).hits > 0;
		}
		return false;
	}
	
	public void addCosts(Broker[] path, double[] costs){
		
		int n;      // path length
		int pos;    // own position in the path
		
		double d;   // distance
		double p;   // processing costs
		double c;   // communication costs
		double i;   // interests
		double i2;
		double a;   // average
		double cost;// cost of an edge
		
		// determine own position in the path
		n = path.length;
		pos = 0;
		for(int j=0; j<path.length; j++){
			if(path[j]==bThis){
				pos = j;
				break;
			}
		}
		
		if(Broker.heuristic == Broker.COSTS_AND_INTERESTS) {
			// calc distances and costs for right path, respectivly the own position
			d = 0;
			for(int j=1; j<n; j++){
				// initialize for a real neighbor
				if(j==1){
					i = ((Entry)path[(pos+j)%n].getProperty(interests)).hits;
					d = net.getCommunicationCosts(path[(pos+j-1)%n],path[(pos+j)%n]);
					
					// TODO Change back
					// i = 1;
					
					
					cost = d*i;
				}
				else{
					// other brokers on the path
					p = net.getProcessingCosts(path[(pos+j-1)%n]);
					c = net.getCommunicationCosts(path[(pos+j-1)%n],path[(pos+j)%n]);
					i = ((Entry)path[(pos+j)%n].getProperty(interests)).hits;
					//TODO change back
					i2 = ((Entry)path[(pos+j-1)%n].getProperty(interests)).hits;
					a = Math.min(Math.min(i,average),i2);
//					a = Math.min(average,i);
					d = (i-a)/Math.max(1.0,i)*(d+p)+c;
					
					// TODO change back
					//d = c;
					//i = 1;	
						
					cost = d*i;
				}
			
				// add costs
				for(int k=j; k<n; k++){
					costs[(pos+k)%n] += cost;
				}
			}
		
			// ensure a positive position
			pos += n;

			// calc distances and costs for left path, respectivly the own position
			d = 0;
			for(int j=1; j<n; j++){
				// initialize for a real neighbor
				if(j==1){
					i = ((Entry)path[(pos-j)%n].getProperty(interests)).hits;
					d = net.getCommunicationCosts(path[(pos-j+1)%n],path[(pos-j)%n]);
					
					// TODO change back 
					//i=1;
					
					cost = d*i;
				}
				else{
					// other brokers on the path
					p = net.getProcessingCosts(path[(pos-j+1)%n]);
					c = net.getCommunicationCosts(path[(pos-j+1)%n],path[(pos-j)%n]);
					i = ((Entry)path[(pos-j)%n].getProperty(interests)).hits;
					//TODO change back
					i2 = ((Entry)path[(pos+j-1)%n].getProperty(interests)).hits;
					a = Math.min(Math.min(i,average),i2);
//					a = Math.min(average,i);
					d = (i-a)/Math.max(1.0,i)*(d+p)+c;
					
					// TODO change back 
					//d = c;
					//i = 1;
					
					cost = d*i;
				}
				// add costs
				for(int k=n-j-1; k>=0; k--){
					costs[(pos+k)%n] += cost;
				}
			}
		}
		else if (Broker.heuristic == Broker.COSTS) {
			c = net.getCommunicationCosts(path[pos%n],path[(pos+1)%n]);
			costs[pos] = -c;
		}
		else if (Broker.heuristic == Broker.INTERESTS) {
			//pos += n;
			i = getInterest(path[(pos+1)%n]);
			costs[pos%n] += i;
			//i = getInterest(path[(pos-1)%n]);
			//costs[(pos-1)%n] += i;
			
			// old impl
//			i = ((Entry)path[(pos+1)%n].getProperty(interests)).hits;
//			costs[pos] += i;
//			pos += n;
//			i = ((Entry)path[(pos-1)%n].getProperty(interests)).hits;
//			costs[(pos-1)%n] += i;
			
//			// TODO remove
//			if(i == 0) {
//				//System.out.println("got out again");
//				return;
//			}
//			System.out.println("I Am "+path[pos%n]);
//			for (int x = 0; x < path.length; x++ ) {
//				System.out.print(""+path[x]+" ");
//			}
//			System.out.println();
//			for (int x = 0; x < costs.length; x++ ) {
//				System.out.print(""+costs[x]+" ");
//			}
//			System.out.println();
		}
		
		// TODO remove
//		System.out.print("Kosten bei add: ");
//		for(int x=0; x<costs.length; x++){
//			System.out.print(costs[x]+" ");
//		}
//		System.out.println();
	}
	
	public int size(){
		return interests.size();
	}
	
	public double getInterest(Broker b) {
		return ((Entry)b.getProperty(interests)).hits;
	}
}



//public class LocalEnvironment extends Graph {
//	// TODO: Initialisierung
//	private Broker local = null;
//	private Property parent = null;
//	private Property lastUpdate = null;
//	private Property commonEvents = null;
//	private Network net = null;
//	private double updateInterval = 4;
//	
//	private double sum;
//	private double average;
//	private double own;
//	
//	public LocalEnvironment(Broker local){
//		this.local = local; 
//	}
//	
//	// TODO mhh, vielleicht nochmal gegenchecken
//	// TODO was machen mit common events bei ganz neuen?
//	public void refresh(Broker[] path, double time){
//		Broker last;
//		Broker current; 
//		Broker father;
//		Broker b;
//		Edge e;
//		
//		last = this.local;
//		
//		//for (Iterator it = path.iterator(); it.hasNext(); ){
//		for (int i = 1; i < path.length; i++){
//			
//			current = path[i];
//			if (containsVertex(path[i])){
//				// falls path had changed
//				if (!containsEdge(last,current)){
//					addEdge(net.getLink(last,current));
//					father = (Broker)current.getProperty(this.parent);
//					removeEdge(current, father);
//					current.setProperty(parent,last);
//				}
//			} else {
//				// falls gänzlich unbekannt
//				addVertex(current);
//				addEdge(net.getLink(last,current));
//				current.setProperty(parent,last);
//				// Mark as unknown.
//				current.setProperty(commonEvents, new Double(0.0));
//			}
//			current.setProperty(lastUpdate, new Double(time));
//		}
//	}
//	
//	// TODO besserer Name?
//	public void update(double time){
//		Broker b;
//		// tidy up and remove stale entries
//		for(Iterator it = vertexIterator(); it.hasNext(); ){
//			b = (Broker) it.next();
//			if(b.equals(local)){
//				continue;
//			}
//			if (((Double)b.getProperty(lastUpdate)).doubleValue() + 
//					updateInterval < time ) {
//				b.removeProperty(parent);
//				b.removeProperty(lastUpdate);
//				b.removeProperty(commonEvents);
//				removeVertex(b);
//			}
//		}
//	}
//	
//	public void setEvents(Broker b, double events){
//		Double oldEvents;
//		
//		if(local.equals(b)){
//			setEvents(events);
//			return;
//		}
//			
//		oldEvents = (Double) b.setProperty(commonEvents,new Double(events));
//		sum += events - (oldEvents == null ? 0.0 : oldEvents.doubleValue() );
//		
//		// recalc the average
//		calcAverage();		
//	}
//	
//	public Request optimize(Broker[] path){
//	
//		Request request;
//		double[] costs;
//		request = null;
//		costs = new double[path.length];
//		if (addCosts(path,costs)) {
//			request = new Request(path, costs);
//		}
//		return request;
//		
////		double[] costs;
////		Graph g;
////		boolean optimizable;
////		Request request;
////		
////		optimizable = false;
////		request = null;
////		costs = new double[path.length];
////		
////		// Baue einen Graphen pro Konfiguration
////		for(int i=0; i<path.length; i++){
////			g = new Graph();
////			g.addVertices(path);
////			for(int j=0, n=path.length; j<n; j++){
////				if (i==j){
////					continue;
////				}
////				g.addEdge(net.getLink(path[(n-j)%n], path[n-j-1]));
////			}
////			costs[i] = getCosts(g);
////			// sind die Kosten wirklich niedriger als jetzt?
////			optimizable = optimizable || costs[i] < costs[0];
////		}
////		// Wenn optimierbar, dann neuen Request erzeugen.
////		if(optimizable){
////			request = new Request(path, costs);
////		}
////	
////		return request;
//		
//	}
//	
//	private boolean addCosts(Broker[] path, double[] costs){
//		Graph g;
//		boolean optimizable;
//	
//		
//		optimizable = false;
//		
//		// Baue einen Graphen pro Konfiguration
//		for(int i=0; i<path.length; i++){
//			g = new Graph();
//			g.addVertices(path);
//			for(int j=0, n=path.length; j<n; j++){
//				if (i==j){
//					continue;
//				}
//				g.addEdge(net.getLink(path[(n-j)%n], path[n-j-1]));
//			}
//			costs[i] += getCosts(g);
//			// sind die Kosten wirklich niedriger als jetzt?
//			optimizable = optimizable || costs[i] < costs[0];
//		}
//		// Wenn optimierbar
//		return optimizable;
//	}
//	
//	private void calcAverage(){
//		average = Math.min(sum-own,0) / Math.min(getNumberOfVertices(),1);
//	}
//	
//	
//	public double getCosts(Graph g) {
//		double costs;
//		
//		costs = 0.0;
//		
//		for ( AdjacencyIterator ait = g.vertexAdjacencyIterator(local); 
//			  ait.hasNext(); 
//			  costs += getCosts(g,0.0,local,(Broker)ait.next()) );
//		
//		return costs;
//	}
//	
//	private double getCosts(Graph g, double lastCost, Broker last, Broker current){
//		AdjacencyIterator ait;
//		Broker next;
//		double cost;
//		double link;
//		double currentEvents;
//		double lastEvents;
//		double costs;
//		
//		link = net.getLinkCost(last, current);
//
//		lastEvents = local.equals(last) ? 0.0 : 
//			         ((Double)last.getProperty(commonEvents)).doubleValue();
//		currentEvents = ((Double)current.getProperty(commonEvents)).doubleValue();
//		
//		
//		// die Berechnung der Linkkosten!!!
//		cost = link + lastCost * ( currentEvents - 
//			   Math.min(average,Math.min(currentEvents,lastEvents)) ) /
//               Math.max(currentEvents,1.0) ;
//		
//		// Linkkosten * Anzahl der Ereignisse
//		costs = currentEvents * cost;
//		
//		// Zu den Kindern
//		for(ait = g.vertexAdjacencyIterator(current); ait.hasNext(); ){
//			next = (Broker)ait.next();
//			if(!next.equals(last)){
//				costs += getCosts(g,cost,current,next);
//			}
//		}
//		
//		return costs;		
//	}
//	
//	public void setEvents(double events){
//		this.own = events;
//		calcAverage();
//	}
//	
//}