vivaldiclient.java

这是一个基于java编写的torrent的P2P源码

package edu.harvard.syrah.nc;

/*
 * NCLib - a network coordinate library
 * 
 * This program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; either version 2 of the License.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details (
 * see the LICENSE file ).
 * 
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
 * Place, Suite 330, Boston, MA 02111-1307 USA
 */

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.logging.Logger;

/**
 * A class that is responsible for updating the local Vivaldi coordinates, both
 * at the system and application level, and also maintaining the state of remote
 * hosts that support Vivaldi.
 * 
 * @author Michael Parker, Jonathan Ledlie
 * 
 * @param <T>
 * the type of the unique identifier of a host
 */
public class VivaldiClient<T> {

  //protected static edu.harvard.syrah.prp.Log crawler_log =
	//new edu.harvard.syrah.prp.Log(VivaldiClient.class);
  protected static Logger crawler_log = Logger.getLogger(VivaldiClient.class.getName()); 
  
  public static final boolean SIMULATION = false;
  public static boolean debug = false;
  public static boolean debugCrawler = false;
  // include even good events in output, not just problems
  public static boolean debugGood = false;

  // Old version
  public static final byte VERSION_02 = 0x02;
  // Height added
  public static final byte VERSION_03 = 0x03;
  // Changed filter percentile from 0.125 to 0.5
  // and added ping timer at 10sec
  // c_error = 0.10, c_control = 0.25
  public static final byte VERSION_04 = 0x04;
  public static final byte CURRENT_VERSION = VERSION_04;

  
	public static double COORD_ERROR = 0.10; // c_e parameter
	public static double COORD_CONTROL = 0.25; // c_c parameter

  // The last element of the coordinate is a "height" away from the Euclidean space
  public static boolean USE_HEIGHT = true;
  
  // Try to minimize our error between up to MAX_NEIGHBORS guys at once
  
    final public static int MAX_NEIGHBORS = 512;
    final protected static int WINDOW_SIZE = 64;

  // Toss remote state of nodes if we haven't heard from them for three days
  // This allows us to keep around a list of RTTs for the node even if
  // we currently aren't using its coordinate for update
    public static long RS_EXPIRATION = 3 * 24 * 60 * 60 * 1000;
    final public static long MAINTENANCE_PERIOD = 10 * 60 * 1000; // ten minutes
    // target max number of remote states kept
    // set to be larger than MAX_NEIGHBORS
    public final static int MAX_RS_MAP_SIZE = 32 * 1024;
    private long lastMaintenanceStamp = 0;

  
	public static Random random = new Random();

	// Do an update if we've moved a third of the way to our nearest known
	// neighbor
	// Lowering this value leads to more frequent updates
	// Should be less than 0.5
	public static final double APP_UPDATE_THRESHOLD = 0.1;

	// completely ignore any RTT larger than ten seconds
	public static final double OUTRAGEOUSLY_LARGE_RTT = 20000.0;

	// range from origin where pull of gravity is 1
	public static double GRAVITY_DIAMETER = 512.;
	
	// We reject remote coords with any component larger than this value
	// This is to prevent serialization problems from leaking into coords
	// we're actually going to use
	// Gravity should keep everybody within this ball
	public static double MAX_DIST_FROM_ORIGIN = 60000.;
	

	final static protected NumberFormat nf = NumberFormat.getInstance();
	final static protected int NFDigits = 3;
	static boolean haveSetFormat = false;
  
	protected final int num_dims;

	protected Coordinate app_coord;

  protected Coordinate sys_coord;
  
  // error should always be less than or equal to MAX_ERROR
  // and greater than 0
  protected double error;
  public static final double MAX_ERROR = 1.;
  
	public static boolean keepStatistics = true;
	// keeping an EWMA of some of these things gives skewed results
	// so we use a filter
	final public static int RUNNING_STAT_HISTORY = 1024;
	// 30 minutes
	//final public static long STAT_EXPIRE_TIME = 30 * 60 * 1000;
	protected WindowStatistic running_sys_error;
	protected WindowStatistic running_app_error;
	protected EWMAStatistic running_sys_dd;
	protected EWMAStatistic running_app_dd;
	protected EWMAStatistic running_neighbors_used;
	protected EWMAStatistic running_relative_diff;
	protected EWMAStatistic running_sys_update_frequency;
	protected EWMAStatistic running_app_update_frequency;
  protected EWMAStatistic running_age;
  protected EWMAStatistic running_gravity;
	protected long time_of_last_app_update = -1;

  // keep the list of neighbors around for computing statistics
	protected final List<RemoteState<T>> neighbors;
  
  // note: not just part of statistics
  // this is returned to querier of our coords so he knows how stale they are
  protected long time_of_last_sys_update = -1;

	protected final ObserverList obs_list;

	protected final HashMap<T, RemoteState<T>> rs_map;

	protected final Set<T> hosts;

	protected Coordinate start_centroid;

	protected boolean updated_app_coord_at_least_once = false;

	protected final List<Coordinate> start_coords;

	protected final List<Coordinate> current_coords;

	protected Coordinate nearest_neighbor;
	protected T local_addr;
  
  
	/**
	 * Creates a new instance. Typically an application should only have one
	 * instance of this class, as it only needs one set of Vivaldi coordinates.
	 * 
	 * @param _num_dims
	 * the number of Euclidian dimensions coordinates should have
	 */
	public VivaldiClient(int _num_dims) {
		num_dims = _num_dims;

		app_coord = new Coordinate(num_dims);
    sys_coord = new Coordinate(num_dims);

		error = MAX_ERROR;
    neighbors = new ArrayList<RemoteState<T>>();
    
		obs_list = new ObserverList();
		rs_map = new HashMap<T, RemoteState<T>>();
		hosts = Collections.unmodifiableSet(rs_map.keySet());
		start_coords = new LinkedList<Coordinate>();
		current_coords = new LinkedList<Coordinate>();
    nearest_neighbor = null;
    
    //bootstrapCoordinates ();
    
    if (keepStatistics) {
			running_sys_update_frequency = new EWMAStatistic();
			running_app_update_frequency = new EWMAStatistic();
			running_sys_error = new WindowStatistic(RUNNING_STAT_HISTORY);
			running_app_error = new WindowStatistic(RUNNING_STAT_HISTORY);
			running_sys_dd = new EWMAStatistic();
			running_app_dd = new EWMAStatistic();
			running_neighbors_used = new EWMAStatistic();
			running_relative_diff = new EWMAStatistic();
      running_age = new EWMAStatistic();
      running_gravity = new EWMAStatistic();
		}
		
		if (!haveSetFormat) {
		  if (nf.getMaximumFractionDigits() > NFDigits) {
		    nf.setMaximumFractionDigits(NFDigits);
		  }
		  if (nf.getMinimumFractionDigits() > NFDigits) {
		    nf.setMinimumFractionDigits(NFDigits);
		  }
		  nf.setGroupingUsed(false);
		  haveSetFormat = true;
		}
	}

  // for debugging simulations
  public void setLocalID (T _local_addr) {
    local_addr = _local_addr;
  }
  
	// See Lua IMC 2005, Pietzuch WORLDS 2005, Ledlie ICDCS 2006
	// for description of these statistics
	protected ApplicationStatistics computeApplicationStatistics() {

		ApplicationStatistics appStats = new ApplicationStatistics();

		if (sys_coord.atOrigin() || neighbors == null ||
      neighbors.size() == 0) return appStats;    

		int rrl_wrong = 0;
		int rrl_count = 0;
		double narl_loss = 0;
		double narl_sum = 0;
		double ralp_loss = 0;
		double ralp_sum = 0;

    // TODO might want to use the app coord here so as to get the average location
    
		for (Iterator<RemoteState<T>> i = neighbors.iterator(); i.hasNext();) {
			RemoteState<T> A_rs = i.next();

			double A_rtt = A_rs.getSample();
			double A_metric = sys_coord.distanceTo(A_rs.getLastCoordinate());
			if (A_rtt > 0 && A_metric > 0) {

				for (Iterator<RemoteState<T>> j = neighbors.iterator(); j
						.hasNext();) {
					RemoteState<T> B_rs = j.next();

					if (!A_rs.addr.equals(B_rs.addr)) {

						double B_rtt = B_rs.getSample();
						double B_metric = sys_coord.distanceTo(B_rs
								.getLastCoordinate());
						if (B_rtt > 0 && B_metric > 0) {

							double rtt_diff = Math.abs(A_rtt - B_rtt);
							rrl_count++;
							narl_sum += rtt_diff;

							if ((A_rtt > B_rtt && A_metric < B_metric)
									|| (B_rtt > A_rtt && B_metric < A_metric)) {
								// oops coordinates have incorrectly ranked
								// these two guys
								rrl_wrong++;
								narl_loss += rtt_diff;
							}

							// relative latency penalty for using A,
							// which the metric says is closer,
							// when A is actually further away
							if (A_rtt > B_rtt && A_metric < B_metric) {
								ralp_loss += rtt_diff;
								ralp_sum += A_rtt;
							}
							if (B_rtt > A_rtt && B_metric < A_metric) {
								ralp_loss += rtt_diff;
								ralp_sum += B_rtt;
							}
						}
					}
				}
			}
		}

		appStats.validLinkCount = rrl_count;
		if (rrl_count > 0)
			appStats.rrl = rrl_wrong / (double) rrl_count;
		if (narl_sum > 0)
			appStats.narl = narl_loss / narl_sum;
		if (ralp_sum > 0)
			appStats.ralp = ralp_loss / ralp_sum;
		return appStats;
	}

	// poor man's public struct
	class ApplicationStatistics {
		double rrl = 0;
		double narl = 0;
		double ralp = 0;
		int validLinkCount = 0;

		public ApplicationStatistics() {
		};
	}

	synchronized public String toString() {
		if (keepStatistics) {
			ApplicationStatistics appStats = computeApplicationStatistics();

			return new String("[sc=" + sys_coord + ",ac=" + app_coord + ",er="
					+ nf.format(error) + ",sys_re50="
					+ nf.format(running_sys_error.getPercentile(.5))
					+ ",sys_re95="
					+ nf.format(running_sys_error.getPercentile(.95))
					+ ",app_re50="
					+ nf.format(running_app_error.getPercentile(.5))
					+ ",app_re95="
					+ nf.format(running_app_error.getPercentile(.95))
					+ ",sys_dd=" + nf.format(running_sys_dd.get()) + ",app_dd="
					+ nf.format(running_app_dd.get()) + ",ne="
					+ nf.format(running_neighbors_used.get()) + ",rd="
					+ nf.format(running_relative_diff.get()) + ",sf="
					+ nf.format(running_sys_update_frequency.get()) + ",af="
					+ nf.format(running_app_update_frequency.get()) + ",rrl="
					+ nf.format(appStats.rrl) + ",narl="
					+ nf.format(appStats.narl) + ",ralp="
					+ nf.format(appStats.ralp) + ",age="
					+ getAge(System.currentTimeMillis()) + ",vl="
					+ nf.format(appStats.validLinkCount) +",gr=" 
          + nf.format(running_gravity.get())+",nn="
					+ nf.format(sys_coord.distanceTo(nearest_neighbor)) + "]");
		}
		else {
			return new String("[sc=" + sys_coord + ",ac=" + app_coord + ",er="
					+ nf.format(error) + ",nn="
					+ nf.format(sys_coord.distanceTo(nearest_neighbor)) + "]");
		}
	}

	synchronized public Hashtable<String, Double> getStatistics() {
		Hashtable<String, Double> stats = new Hashtable<String, Double>();
		for (int i = 0; i < num_dims; i++) {
			stats.put("sys_coord_" + i, sys_coord.coords[i]);
			stats.put("app_coord_" + i, sys_coord.coords[i]);
		}
		stats.put("er", error);
		stats.put("nn", sys_coord.distanceTo(nearest_neighbor));

		if (keepStatistics) {
			ApplicationStatistics appStats = computeApplicationStatistics();

			stats.put("rrl", appStats.rrl);
			stats.put("narl", appStats.narl);
			stats.put("ralp", appStats.ralp);
			stats.put("age", new Double (getAge(System.currentTimeMillis())));
			stats.put("vl", new Double(appStats.validLinkCount));
			stats.put("gr", running_gravity.get());
      
			stats.put("sys_re50", running_sys_error.getPercentile(.5));
			stats.put("sys_re95", running_sys_error.getPercentile(.95));
			stats.put("app_re50", running_app_error.getPercentile(.5));
			stats.put("app_re95", running_app_error.getPercentile(.95));

			stats.put("sys_dd", running_sys_dd.get());
			stats.put("app_dd", running_app_dd.get());

			stats.put("ne", running_neighbors_used.get());
			stats.put("rd", running_relative_diff.get());
			stats.put("sf", running_sys_update_frequency.get());
			stats.put("af", running_app_update_frequency.get());
		}
		return stats;
	}