topology.java

p2p仿真

/*
 * @(#)Topology.java	ver 1.2  6/20/2005
 *
 * Copyright 2005 Weishuai Yang ([e-mail]). 
 * All rights reserved.
 * 
 */

package gps.network;

import java.util.LinkedList;
import java.util.Properties;
import java.util.logging.Logger;

import gps.network.graph.Graph;
import gps.network.graph.Link;
import gps.network.graph.Node;
import gps.util.FloydWarshall;
import gps.util.LogFormatter;


/**
 * provides network topology information
 *
 * @author  Weishuai Yang
 * @version 1.0,  4/18/2005
 */
public class Topology {
	/**
	 * singleton reference to debug log
	 */
	protected static Logger mDebugLog = Logger.getLogger("Debug");
	/**
	 * singleton instance
	 */
	protected static Topology mInstance=null;
	/**
	 * matrix holding delay information between any two nodes
	 */
	protected float[][] mDelayMatrix=null;
	/**
	 * matrix holding predecessor information between any two nodes
	 */
	protected int[][] mPredecessorMatrix=null;
	/**
	 * node array
	 */
	protected Node[] mNode=null;
	/**
	 * link array
	 */
	protected Link[] mLink=null; 
	/**
	 * total node number
	 */
	protected int mTotalNodeNum=0;
	
	
	/**
	 * gets the singleton instance of topology
	 * @return topology instance
	 */
	public static synchronized Topology getInstance() {
		if(mInstance==null)
			mInstance=new Topology();
		return mInstance;
	}
	
	/**
	 * dummy constructor
	 */
	public Topology(){}
	/**
	 * resets topology
	 */
	public void reset(){
	    
        if(mNode!=null)
	        for (int i = 0; i < mNode.length; i++)
	            if(mNode[i]!=null){
	                mNode[i].reset();
	            }

        if(mLink!=null)
	        for (int i = 0; i < mLink.length; i++)
	            if(mLink[i]!=null){
	                mLink[i].reset();
	            }
	    
		mDelayMatrix=null;
		mPredecessorMatrix=null;
		mNode=null;
		mLink=null; 
		mTotalNodeNum=0;
		
	}
	/**
	 * gets delay between two nodes represented by id
	 *
	 * @param node1 source node id
	 * @param node2 destination node id
	 * @return delay
	 */
	public double getDelay(int node1, int node2){
		if(node1>mTotalNodeNum||node2>mTotalNodeNum){
			mDebugLog.severe("Node "+node1+ " or Node "+node2+"exceeds total node number!");
			return 0;
		}
		return mDelayMatrix[node1][node2];
	}


	
	/**
	 * gets delay between two nodes
	 *
	 * @param node1 source node
	 * @param node2 destination node
	 * @return delay
	 */
	public double getDelay(Node node1, Node node2){
		return getDelay(node1.getID(), node2.getID());
	}


	/**
	 * gets bandwidth of a link
	 * 
	 * @param l  the link
	 * @return bandwidth
	 */
	public double getBandwidth(Link l){
		return l.getBandwidthManager().getBandwidth();	
	}
	/**
	 * gets available bandwidth of a link
	 *
	 * @param l  the link
	 * @return available bandwidth
	 */
	public double getAvailableBandwidth(Link l){
		return l.getBandwidthManager().getAvailableBandwidth();	
	}


	/**
	 * gets the node instance from it's id
	 *
	 * @param id  node id
	 * @return node
	 * 
	 */
	public Node getNode(int id){

		if(id>mTotalNodeNum){
			mDebugLog.severe("Node "+id+ "exceeds total node number!");
			return null;
		}	
		if(mNode[id].getID()!=id)
			mDebugLog.severe("ID retrieved from "+mNode[id]+"doesn't match"+id);
		
		//if(id<=mSAgentNum){ //it should be Server
		//	if(!mNode[id].getClass().isInstance(Server.class))
		//		mDebugLog.severe("ID retrieved from "+mNode[id]+"should be Server since it's id "+id+" < "+mPAgentNum);
		//}		
		//mNode[0] is null
		return mNode[id];
	}

	/**
	 * gets all nodes
	 * @return array of nodes
	 */
	public Node[] getNodes(){
		return mNode;
	}
	/**
	 * gets all links
	 * @return array of links
	 */
	public Link[] getLinks(){
		return mLink;
	}

	/**
	 * constructs topology from graph file and properties
	 * @param g graph object
	 * @param p simulator properties
	 */
	public void confNetwork(Graph g, Properties p){
		
		Properties mProperties=p;
		
		Link[] links=g.getAllLinks();
		mNode=g.getAllNodes();
		mLink=g.getAllLinks();
		
		
		mTotalNodeNum=mNode.length;

		mDelayMatrix=new float[mTotalNodeNum][mTotalNodeNum];

		for(int i=0;i<mTotalNodeNum;i++){
			for(int j=0;j<mTotalNodeNum;j++)
				mDelayMatrix[i][j]=0;
		}
		
		
		//set type of links
		for ( int i=0; i<links.length; i++ ) {
		    
		    int f=links[i].fromNode();
		    int t=links[i].toNode();
		    
		    int type = 0;
		    // link type: 0=S-S, 1=S-T, 2=T-T
            
		    if((mNode[f].getProperties().getType()==16)&&(mNode[t].getProperties().getType()==16)){
		        type=2;
		    }
		    else if((mNode[f].getProperties().getType()==16)||(mNode[t].getProperties().getType()==16)){
		        type=1;
		    }

	        links[i].getProperties().setType(type);

	        //set reference from node to link
	        mNode[links[i].fromNode()].hasLinkTo(mNode[links[i].toNode()], links[i]);
			
			//if it's not directed, also add to the other side
			if(!links[i].getProperties().getDirection())
				mNode[links[i].toNode()].hasLinkTo(mNode[links[i].fromNode()], links[i]);
    
		}
		
		
		
		float ttd = Float.parseFloat(mProperties.getProperty("DelayTT"));
		float tsd = Float.parseFloat(mProperties.getProperty("DelayTS"));
		float ssd = Float.parseFloat(mProperties.getProperty("DelaySS"));
		
		double ttb = Double.parseDouble(mProperties.getProperty("BandwidthTT"));
		double tsb = Double.parseDouble(mProperties.getProperty("BandwidthTS"));
		double ssb = Double.parseDouble(mProperties.getProperty("BandwidthSS"));
		
		double mss = Double.parseDouble(mProperties.getProperty("MSS"));
		double rtt = Double.parseDouble(mProperties.getProperty("RTT"));
		double loss = Double.parseDouble(mProperties.getProperty("P"));
		double c = Double.parseDouble(mProperties.getProperty("C"));
		
		//KBytes
		double newttb, newtsb, newssb;
		boolean cong=Boolean.parseBoolean(mProperties.getProperty("CongestionEstimation"));
		if(cong)
		{
			newttb=calcBandwidth(mss,rtt,loss,c,ttd);
			newtsb=calcBandwidth(mss,rtt,loss,c,tsd);
			newssb=calcBandwidth(mss,rtt,loss,c,ssd);
			
		}
			
		else{
			//Mbps->Bytes per sec
			newttb=ttb*1000000/(float)8;
			newtsb=tsb*1000000/(float)8;
			newssb=ssb*1000000/(float)8;
		}
		
	    //debug begin
	    StringBuffer ss=new StringBuffer("Bandwidth Information:\n CongestionEstimation:"+ cong + "\n");
	   ss.append(LogFormatter.sprintf("TT Bandwidth: % 10.5f KBytes \n", newttb/1024));
	   ss.append(LogFormatter.sprintf("TS Bandwidth: % 10.5f KBytes \n", newtsb/1024));
	   ss.append(LogFormatter.sprintf("SS Bandwidth: % 10.5f KBytes \n", newssb/1024));
	    mDebugLog.info(""+ss);
		
		for(int i=0;i<links.length;i++){
			if(links[i].getProperties().getType()==2){
				links[i].setDelay(ttd/(float)1000);
				links[i].setBandwidth(newttb);
				mDelayMatrix[links[i].fromNode()][links[i].toNode()]=ttd/(float)1000;
				mDelayMatrix[links[i].toNode()][links[i].fromNode()]=ttd/(float)1000;
			}
			else if(links[i].getProperties().getType()==1){
				links[i].setDelay(tsd/(float)1000);
				links[i].setBandwidth(newtsb);
				mDelayMatrix[links[i].fromNode()][links[i].toNode()]=tsd/(float)1000;
				mDelayMatrix[links[i].toNode()][links[i].fromNode()]=tsd/(float)1000;

			}
			else if(links[i].getProperties().getType()==0){
				links[i].setDelay(ssd/(float)1000);
				links[i].setBandwidth(newssb);
				mDelayMatrix[links[i].fromNode()][links[i].toNode()]=ssd/(float)1000;
				mDelayMatrix[links[i].toNode()][links[i].fromNode()]=ssd/(float)1000;
			}
		}


		//write to ns2 format, for experiment under ns2
		//String ns2filename=mProperties.getProperty("GraphFile");
		//ns2filename+=".tcl";
		//try{ g.writeToNS2(ns2filename);	} catch(Exception e){}



	    //debug begin
	    StringBuffer s0=new StringBuffer("Delay Information before floydwarshall:\n");
	    for(int i=0;i<mTotalNodeNum;i++){
	    	s0.append("Node "+i+" to others:");
	    	for(int j=0;j<mTotalNodeNum;j++){

	    		s0.append(LogFormatter.sprintf(" % 6.1f ms  ", mDelayMatrix[i][j]*1000));

	    	}
	    	s0.append("\n");
	    }
	    mDebugLog.info(""+s0);
	  
	    
	  FloydWarshall fwAlg = new FloydWarshall();
      fwAlg.initialize(mTotalNodeNum);
      mDelayMatrix = fwAlg.allPairsShortestPaths (mDelayMatrix);
	  mPredecessorMatrix = fwAlg.getPK();

	    //debug begin
	    StringBuffer s=new StringBuffer("Delay Information after floydwarshall:\n");
	    for(int i=0;i<mTotalNodeNum;i++){
	    	s.append("Node "+i+" to others:");
	    	for(int j=0;j<mTotalNodeNum;j++){
	    		s.append(LogFormatter.sprintf(" % 6.1f ms  ", mDelayMatrix[i][j]*1000));
	    	}
	    	s.append("\n");
	    }
	    mDebugLog.info(""+s);
	      
		mDebugLog.info("Bandwidth Information reading finish: between Transits:"+ttb+", between transit and stub:"+tsb+", between stubs:"+ssb+"\n");
	    //debug end
	}
	
	
	/**
	 * gets links between two nodes, which may or may not connect to each other
	 * @param node1 source node
	 * @param node2 destination node
	 * @return link array for links along these two nodes, null if no link exists
	 */
	public Link[] getLinksBetween(Node node1, Node node2){
		
		if(node1==node2) return null;
		
		int i=node1.getID();
		int j=node2.getID();
		
		int pre=mPredecessorMatrix[i][j];
		
		if(pre==-1){
			mDebugLog.severe("Trying to get Link between unconnected nodes: "+node1+" and "+node2);
			return null;
		}
		else if(pre==i){
			Link[] link1=new Link[1];
			link1[0]=getLinkBetween(node1, node2);
			return link1;
		}
		
		LinkedList links=new LinkedList();
		int lastpre=j;
		do{
			Link l=getLinkBetween(getNode(pre), getNode(lastpre));
		    links.addFirst(l);
		    lastpre=pre;
		    pre=mPredecessorMatrix[i][pre];

		}
		while(pre!=-1);   //because Pk[i][i]==-1
		
		Link[] ret=new Link[links.size()];
		for(int m=0;m<links.size();m++)
			ret[m]=(Link)links.get(m);
		return ret;

	}
	
	
	/**
	 * gets link between two directly connected nodes
	 * @return direct link between two nodes, null if no link exists
	 */
	public Link getLinkBetween(Node node1, Node node2){
		return node1.getLinkTo(node2);
	}
	
	
	/**
	 * calculate bandwidth through tcp formula
	 * @return calculated bandwidth
	 */
	
	public double	calcBandwidth(double mss, double rtt, double p, double c,double delay){
		//delay is not used for calculating bandwidth in this model, but may be used in other models
	    return mss*c*1000/(rtt*Math.sqrt(p));
	};
	
	
	
	
	
///////////////following functions are depreciated ///////////////
	
	
	
	/**
	 *  setBandwidth reads bandwidth info from configuration file and set to links, needs modification
	 */
	 
	 /*
	public void setBandwidth(String file){
	    FileInputStream infile;
	    if(file==null){
			mDebugLog.severe("set bandwidth from null file");
			return;
		}
				
	    try
	    {      
			infile=new FileInputStream(file);
			BufferedReader rdr=new BufferedReader(new InputStreamReader(infile));
			String s;
			StringTokenizer tk;
			int i=0;
			
			while((s=rdr.readLine())!=null)
			{	
				s.trim();
				//not empty
				if(s.length()==0) continue;
				//not comments
				if(s.charAt(0)=='#') continue;
				
				//i is current line number, only accept line 0 for in Bandwidth, and line 1 for out Bandwidth
				if(i>1) return;					
				
				
				tk=new StringTokenizer(s,",");
				//it should contain mTotalNodeNum tokens
				if(tk.countTokens()!=mTotalNodeNum){
					mDebugLog.warning("Bandwidth config file format error! Line "+i+" is supposed to have "+mTotalNodeNum+"columns, but only have "+tk.countTokens());				
				}
			
				if(i==0)
					for(int j=1;j<=mTotalNodeNum;j++){
						double bdw=Double.parseDouble(tk.nextToken());
						mNode[j].setInBandwidth(bdw*1024);
					}
				else
					for(int j=1;j<=mTotalNodeNum;j++){
						double bdw=Double.parseDouble(tk.nextToken());
						mNode[j].setOutBandwidth(bdw*1024);
					}
				i++;
			}
			infile.close();
	    }
	    catch (FileNotFoundException e)
	    {
	      System.err.println(file + " not found");
	    }
	    catch (IOException e){
	    	System.err.println(file + " io exception");
	    }
	    catch (Exception e){
	    	System.err.println(e);
	    	e.printStackTrace();
	    }
	}
	
	
	*/
	
	
	/**
	 * setDelay reads delay info from configuration file and store in Topology, needs modificaiton	 
	 *
	 */
	
	/*
	public void setDelay(String file){
		
	    FileInputStream infile;
	    if(file==null){
			mDebugLog.severe("set delay from null file");
			return;
		}
	    try
	    {      
			infile=new FileInputStream(file);
			BufferedReader rdr=new BufferedReader(new InputStreamReader(infile));
			String s;
			StringTokenizer tk;
			int i=0;
			
			while((s=rdr.readLine())!=null)
			{	
				s.trim();
				//not empty
				if(s.length()==0) continue;
				//not comments
				if(s.charAt(0)=='#') continue;
				
				//i is current node id
				i++;
				if(i>mTotalNodeNum) 
					break;
					
				
				tk=new StringTokenizer(s,",");
				//it should contain mTotalNodeNum tokens
				if(tk.countTokens()!=mTotalNodeNum){
					mDebugLog.warning("Delay config file format error! Line "+i+" is supposed to have "+mTotalNodeNum+"columns, but only have "+tk.countTokens());				
				}
			
				for(int j=1;j<=mTotalNodeNum;j++){
					float delay=Float.parseFloat(tk.nextToken());
					mDelayMatrix[i][j]=delay/1000.0;
				}
			}
			infile.close();
	    }
	    catch (FileNotFoundException e)
	    {
	      System.err.println(file + " not found");
	    }
	    catch (IOException e){
	    	System.err.println(file + " io exception");
	    }
	    catch (Exception e){
		    System.err.println(e);
	    	e.printStackTrace();
	    }
	    
	}
	*/
	/**
	 * confNetwork reads configuration and config delay and bandwidth, needs modification
	 */
	/*
	public void confNetwork(String bfile, String dfile){

		setDelay(dfile);
		setBandwidth(bfile);
	    
	}
	*/
}