network.java

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

/*
 * Created on May 9, 2005
 *
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
package sim;

import broker.*;
import graph.*;
import util.*;

import java.io.*;
import java.util.*;

import com.Message;

/**
 * @author parzy
 *
 * To change the template for this generated type comment go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
public class Network {
	
	private static class Value{
		private double from;
		private double current;
		private double to;
		
		private Value(double value){
			this.from = this.current = this.to = value;
		}
		
		public String toString(){
			return ""+current;
		}
	}
	
	public static String netFile = null;
	private static double minLoad = 1d;
	private static double maxLoad = 10d;
	private static double minCommunicationCosts = 0d;
	public static double maxCommunicationCosts = 100d;
	private static double minProcessingCosts = 0d;
	public static double maxProcessingCosts = 100d;
	private static int numberOfBrokers = 100;
	private static long networkSeed = 4159234174565786444L;
	private static Random rand = new Random(networkSeed);
	private static double communicationDelayConstant = 5d;
	private static double communicationDelayFactor = 0d;
	private static double processingDelayConstant = 0d;
	private static double processingDelayFactor = 0d;
	public static int changeSteps = 1;
	public static double changeInterval = 1000.0d;
	
	public static void initializeProperties(Properties properties){
		// the overlay's input file
		netFile = properties.getProperty("netFile");
		// minimum load fraction of a broker
		minLoad = properties.getProperty("minLoad") != null ? 
				  Double.parseDouble(properties.getProperty("minLoad")) : 
			      minLoad;
		// maximum load fraction of a broker
		maxLoad = properties.getProperty("maxLoad") != null ? 
				  Double.parseDouble(properties.getProperty("maxLoad")) : 
			      maxLoad;
		// minimal communication costs of an overlay link
		minCommunicationCosts = properties.getProperty("minCommunicationCosts") != null ? 
				                Double.parseDouble(properties.getProperty("minCommunicationCosts")) : 
				                minCommunicationCosts;
		// maximal communication costs of an overlay link		                
		maxCommunicationCosts = properties.getProperty("maxCommunicationCosts") != null ? 
				                Double.parseDouble(properties.getProperty("maxCommunicationCosts")) : 
				                maxCommunicationCosts;
		// minimal processing costs of a broker		                
		minProcessingCosts = properties.getProperty("minProcessingCosts") != null ? 
				             Double.parseDouble(properties.getProperty("minProcessingCosts")) : 
				             minProcessingCosts;
		// maximal processing costs of a broker
		maxProcessingCosts = properties.getProperty("maxProcessingCosts") != null ? 
				             Double.parseDouble(properties.getProperty("maxProcessingCosts")) : 
				             maxProcessingCosts;
		// number of brokers in the overlay network
		numberOfBrokers = properties.getProperty("numberOfBrokers") != null ? 
				          Integer.parseInt(properties.getProperty("numberOfBrokers")) : 
				          numberOfBrokers;
        // delay factor for sending a message
        communicationDelayFactor = properties.getProperty("communicationDelayFactor") != null ? 
        		                   Double.parseDouble(properties.getProperty("communicationDelayFactor")) : 
        		                   communicationDelayFactor;
        // delay constant for sending a message
		communicationDelayConstant = properties.getProperty("communicationDelayConstant") != null ?
				                     Double.parseDouble(properties.getProperty("communicationDelayConstant")) :
				                     communicationDelayConstant;	
		// delay factor for processing a message
		processingDelayFactor = properties.getProperty("processingDelayFactor") != null ? 
				                Double.parseDouble(properties.getProperty("processingDelayFactor")) : 
				                processingDelayFactor;
        // delay constant for processing a message
		processingDelayConstant = properties.getProperty("processingDelayConstant") != null ? 
				                  Double.parseDouble(properties.getProperty("processingDelayConstant")) : 
				                  processingDelayConstant;	
		// number of interpolated steps during a network change		                  
        changeSteps = properties.getProperty("changeSteps") != null ? 
                      Integer.parseInt(properties.getProperty("changeSteps")) : 
	                  changeSteps;	
        // interval between two consecutive change steps              
		changeInterval = properties.getProperty("changeInterval") != null ? 
                         Double.parseDouble(properties.getProperty("changeInterval")) : 
	                     changeInterval;	                      
        // random seed for own random generator
		networkSeed = properties.getProperty("networkSeed") != null ? Long.parseLong(properties.getProperty("networkSeed")) : networkSeed;
		// the network's random generator
		rand = new Random(networkSeed);
		
		// initialize also the brokers
		Broker.initialize(properties);
	}
	
	public static Network createOverlay(Simulation sim){
		Network net;
		Graph overlay;
    	Property load;
    	Property communicationCosts;
    	Property processingCosts;
    	Property number;
		
    	int n;
    	Broker[] brokers;
    	Edge edge;
    	double l;
    	double c;
    	double p;
    	
    	overlay = new Graph();
    	load = new Property();
    	communicationCosts = new Property();
    	processingCosts = new Property();
    	number = new Property();
    	net = new Network(sim,overlay,number,processingCosts, load, communicationCosts);
    	
    	
    	n = numberOfBrokers;
    	brokers = new Broker[n];
    	for(int i = 0; i<n; i++){
    		brokers[i] = new Broker(sim, net);
    		overlay.addVertex(brokers[i]);
    		brokers[i].setProperty(number, new Integer(i+1));
    		p = (maxProcessingCosts-minProcessingCosts) * rand.nextDouble() + minProcessingCosts;
    		brokers[i].setProperty(processingCosts, new Value(p));
    		l = (maxLoad-minLoad) * rand.nextDouble() + minLoad;
    		brokers[i].setProperty(load, new Value(l));
    	}
		
    	for (int i = 0; i<n; i++) {
    		for (int j = i+1; j < n; j++) {
    			edge = new Edge(brokers[i],brokers[j]);
    			overlay.addEdge(edge);
      			c = (maxCommunicationCosts-minCommunicationCosts) * rand.nextDouble() + minCommunicationCosts;
    			edge.setProperty(communicationCosts, new Value(c));
    		}
    	}
    	
    	return net;
    }
	
	
	private Graph overlay;
	private Graph tree;
	private Property number;
	private Property communicationCosts;
	private Property processingCosts;
	private Property load;
	
	private Simulation sim;
	
	private Event changeEvent = null;
	
	
	// TODO: the whole implementation
	
	private Network(Simulation sim,
					Graph overlay, Property number, 
					Property processingCosts, Property load,
					Property communicationCosts){
		this.overlay = overlay;
		this.number = number;
		this.processingCosts = processingCosts;
		this.load = load;
		this.communicationCosts = communicationCosts;
		this.sim = sim;
	}

	public double getCommunicationCosts(Broker b1, Broker b2) {
		Value costs;
		Edge edge;
		edge = overlay.getEdge(b1,b2);
		if(edge != null) {
			costs = (Value)edge.getProperty(communicationCosts);
			if (costs != null) {
				return costs.current;
			}
		}
		return minCommunicationCosts;
	}
	
	public double getCommunicationDelay(Broker b1, Broker b2) {
		Value costs;
		Edge edge;
		edge = overlay.getEdge(b1,b2);
		if(edge != null) {
			costs = (Value)edge.getProperty(communicationCosts);
			if (costs != null) {
				return communicationDelayConstant + communicationDelayFactor * costs.current;
			}
		}
		return communicationDelayConstant;
	}
	
	public double getProcessingCosts(Broker b) {
		Value costs;
		costs = (Value)b.getProperty(processingCosts);
		if(costs != null) {
			return costs.current;
		}
		return minProcessingCosts;
	}
	
	public double getProcessingDelay(Broker b) {
		Value costs;
		costs = (Value)b.getProperty(processingCosts);
		if(costs != null) {
			return processingDelayConstant + processingDelayFactor*costs.current;
		}
		return processingDelayConstant;
	}
	
	public double getLoad(Broker b) {
		Value v;
		v = (Value)b.getProperty(load);
		if(v != null) {
			return v.current;
		}
		return minLoad;
	}
	
	public int getNumber(Broker b) {
		Integer num;
		num = (Integer)b.getProperty(number);
		if(num != null) {
			return num.intValue();
		}
		return 0;
	}
	
	public void createOldRandomTree() {
		
		Broker[] brokers;
		int n;
		Iterator it;
		Comparator comp;
		
		tree = new Graph();
		n = overlay.getNumberOfVertices();
		brokers = new Broker[n];
		it = overlay.vertexIterator();
		for(int i = 0; i < n; i++ ) {
			brokers[i] = (Broker)it.next();
		}

		comp = new Comparator() {
			public int compare(Object o1, Object o2) {
				Broker broker1 = (Broker)o1;
				Broker broker2 = (Broker)o2;
				Integer number1 = (Integer)broker1.getProperty(number);
				Integer number2 = (Integer)broker2.getProperty(number);
				return number1.compareTo(number2);
			}
		};
		Arrays.sort(brokers,comp);
		
		tree.addVertex(brokers[0]);
		for (int i=1, j=0; i<n; i++) {
			tree.addVertex(brokers[i]);
			j = rand.nextInt(i);
			tree.addEdge(overlay.getEdge(brokers[i],brokers[j]));
		}
		
		setNeighbors();
	}

	
	public void createRandomTree() {

		int r;
		LinkedList edges;
		int i;
		
		tree = new Graph();
		edges = new LinkedList();
		Edge e;
		Value vs;
		Value vt;
		Value v;
		Property component;
		double min;
		double max;
		
		for (Iterator it = overlay.edgeIterator(); it.hasNext(); ){
			edges.add(it.next());
		}
		
		i = 0;
		component = new Property();
		while(!edges.isEmpty()){
			r = rand.nextInt(edges.size());
			
			e = (Edge)edges.remove(r); 
    		vs = (Value)e.s.getProperty(component);
    		vt = (Value)e.t.getProperty(component);
    		if(vs == null){
    			vs = new Value(i++);
    			e.s.setProperty(component, vs);
    		}
    		if(vt == null){
    			vt = new Value(i++);
    			e.t.setProperty(component, vt);
    		}
    		if(vs.current == vt.current){
    			continue;
    		}
    		
    		tree.addEdge(e);
    		//System.out.println("Adding edge from "+e.s+" (Component "+vs.current+") to "+e.t+" (Component "+vt.current+") mit Interesse "+(Value)e.getProperty(ints)+" size:"+myTree.getNumberOfVertices());
    		
    		min = Math.min(vs.current,vt.current);
    		max = Math.max(vs.current,vt.current);
    		
    		for(Iterator it = tree.vertexIterator(); it.hasNext(); ){
    			v = (Value)((Broker)it.next()).getProperty(component);
    			if(v.current == max){
    				v.current = min;
    			}
     		}   		
		}
		
		setNeighbors();
	}
	
	public void createNearestNeighborTree() {
		Broker[] brokers;
		int n;
		Iterator it;
		Comparator comp;
		Broker neighbor;
		double cost;
		
		tree = new Graph();
		n = overlay.getNumberOfVertices();
		brokers = new Broker[n];
		it = overlay.vertexIterator();
		for(int i = 0; i < n; i++ ) {
			brokers[i] = (Broker)it.next();
		}

		comp = new Comparator() {
			public int compare(Object o1, Object o2) {
				Broker broker1 = (Broker)o1;
				Broker broker2 = (Broker)o2;
				Integer number1 = (Integer)broker1.getProperty(number);
				Integer number2 = (Integer)broker2.getProperty(number);
				return number1.compareTo(number2);
			}
		};
		Arrays.sort(brokers,comp);
		
		tree.addVertex(brokers[0]);
		for (int i=1; i<n; i++) {
			tree.addVertex(brokers[i]);
			neighbor = brokers[0];
			cost = getCommunicationCosts(brokers[i],neighbor);
			for(int j=1; j<i; j++) {
				if(getCommunicationCosts(brokers[i],brokers[j])<cost) {
					neighbor = brokers[j];
				}
			}
			tree.addEdge(overlay.getEdge(brokers[i],neighbor));
		}
		
		setNeighbors();
	}
	
	private void setNeighbors() {
		Broker b;
		LinkedList neighbors;
		neighbors = new LinkedList();
		for(Iterator it = tree.vertexIterator(); it.hasNext(); ) {
			neighbors.clear();
			b = (Broker)it.next();
			for(AdjacencyIterator ait = tree.vertexAdjacencyIterator(b); ait.hasNext(); ) {
				neighbors.add(ait.next());
			}
			b.setNeighbors(neighbors);
		}
	}
	
	public int size() {