content: /*
   * Copyright 2010 Aalto University, ComNet
   * Released under GPLv3. See LICENSE.txt for details.
   */
  package routing;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  import routing.util.RoutingInfo;
  
  import util.Tuple;
  
  import core.Connection;
  import core.DTNHost;
  import core.Message;
  import core.Settings;
  import core.SimClock;
  
  /**
   * Implementation of PRoPHET router as described in
   * <I>Probabilistic routing in intermittently connected networks</I> by
   * Anders Lindgren et al.
   *
   *
   * This version tries to estimate a good value of protocol parameters from
   * a timescale parameter given by the user, and from the encounters the node
   * sees during simulation.
   * Refer to Karvo and Ott, <I>Time Scales and Delay-Tolerant Routing
   * Protocols</I> Chants, 2008
   *
   */
  public class ProphetRouterWithEstimation extends ActiveRouter {
  	/** delivery predictability initialization constant*/
  	public static final double P_INIT = 0.75;
  	/** delivery predictability transitivity scaling constant default value */
  	public static final double DEFAULT_BETA = 0.25;
  	/** delivery predictability aging constant */
  	public static final double GAMMA = 0.98;
  	/** default P target */
  	public static final double DEFAULT_PTARGET = .2;
  
  	/** Prophet router's setting namespace ({@value})*/
  	public static final String PROPHET_NS = "ProphetRouterWithEstimation";
  	/**
  	 * Number of seconds in time scale.*/
  	public static final String TIME_SCALE_S ="timeScale";
  	/**
  	 * Target P_avg
  	 *
  	 */
  	public static final String P_AVG_TARGET_S = "targetPavg";
  
  	/**
  	 * Transitivity scaling constant (beta) -setting id ({@value}).
  	 * Default value for setting is {@link #DEFAULT_BETA}.
  	 */
  	public static final String BETA_S = "beta";
  
  	/** values of parameter settings */
  	private double beta;
  	private double gamma;
  	private double pinit;
  
  	/** value of time scale variable */
  	private int timescale;
  	private double ptavg;
  
  	/** delivery predictabilities */
  	private Map<DTNHost, Double> preds;
  
  	/** last meeting time with a node */
  	private Map<DTNHost, Double> meetings;
  	private int nrofSamples;
  	private double meanIET;
  
  	/** last delivery predictability update (sim)time */
  	private double lastAgeUpdate;
  
  
  	/**
  	 * Constructor. Creates a new message router based on the settings in
  	 * the given Settings object.
  	 * @param s The settings object
  	 */
  	public ProphetRouterWithEstimation(Settings s) {
  		super(s);
  		Settings prophetSettings = new Settings(PROPHET_NS);
  		timescale = prophetSettings.getInt(TIME_SCALE_S);
  		if (prophetSettings.contains(P_AVG_TARGET_S)) {
  			ptavg = prophetSettings.getDouble(P_AVG_TARGET_S);
  		} else {
  			ptavg = DEFAULT_PTARGET;
  		}
  		if (prophetSettings.contains(BETA_S)) {
  			beta = prophetSettings.getDouble(BETA_S);
  		} else {
  			beta = DEFAULT_BETA;
  		}
  		gamma = GAMMA;
  		pinit = P_INIT;
  
  		initPreds();
  		initMeetings();
  	}
  
  	/**
  	 * Copyconstructor.
  	 * @param r The router prototype where setting values are copied from
  	 */
  	protected ProphetRouterWithEstimation(ProphetRouterWithEstimation r) {
  		super(r);
  		this.timescale = r.timescale;
  		this.ptavg = r.ptavg;
  		this.beta = r.beta;
  		initPreds();
  		initMeetings();
  	}
  
  	/**
  	 * Initializes predictability hash
  	 */
  	private void initPreds() {
  		this.preds = new HashMap<DTNHost, Double>();
  	}
  
  	/**
  	 * Initializes inter-encounter time estimator
  	 */
  	private void initMeetings() {
  		this.meetings = new HashMap<DTNHost, Double>();
  		this.meanIET = 0;
  		this.nrofSamples = 0;
  	}
  
  	@Override
  	public void changedConnection(Connection con) {
  		super.changedConnection(con);
  
  		if (con.isUp()) {
  			DTNHost otherHost = con.getOtherNode(getHost());
  			if (updateIET(otherHost)) {
  				updateParams();
  			}
  			updateDeliveryPredFor(otherHost);
  			updateTransitivePreds(otherHost);
  		}
  	}
  
  	/**
  	 * Updates the interencounter time estimates
  	 * @param host
  	 */
  	private boolean updateIET(DTNHost host) {
  		/* First estimate the mean InterEncounter Time */
  		double currentTime = SimClock.getTime();
  		if (meetings.containsKey(host)) {
  			double timeDiff = currentTime - meetings.get(host);
  			// System.out.printf("current time: %f\t last time:  %f\n",currentTime,meetings.get(host));
  
  			nrofSamples++;
  			meanIET = (((double)nrofSamples -1) / (double)nrofSamples) * meanIET
  			+ (1 / (double)nrofSamples) * timeDiff;
  			meetings.put(host, currentTime);
  			return true;
  		} else {
  			/* nothing to update */
  			meetings.put(host,currentTime);
  			return false;
  		}
  	}
  
  	/**
  	 * update PROPHET parameters
  	 *
  	 */
  	private void updateParams()
  	{
  		double b;
  		double zeta;
  		double err;
  		boolean cond;
  		int ntarg;
  		double zetadiff;
  		int ozeta;
  		double pstable;
  		double pavg;
  		double ee;
  		double bdiff;
  		int ob;
  		int zcount;
  		boolean bcheck;
  		double pnzero;
  		double pnone;
  		double eezero;
  		double eeone;
  
  		/*
  		 * the estimation algorith does not work for timescales
  		 * shorter than the mean IET - so use defaults
  		 */
  		if (meanIET > (double)timescale) {
  			System.out.printf("meanIET %f > %d timescale\n",meanIET,timescale);
  			return;
  		}
  
  		if (meanIET == 0) {
  			System.out.printf("Mean IET == 0\n");
  			return;
  		}
  
  		System.out.printf("prophetfindparams(%d,%f,%f);\n",timescale,ptavg,meanIET);
  		b = 1e-5;
  		zeta = .9;
  		err = 0.005;
  		zetadiff = .1;
  		ozeta = 0;
  		cond = false;
  		ntarg = (int)Math.ceil((double)timescale/(double)meanIET);
  		while (cond == false) {
  			pstable = (1-zeta)/(Math.exp(b*meanIET)-zeta);
  			pavg = (1/(b*meanIET)) * (1-zeta*(1-pstable)) *
  			(1- Math.exp( -b*meanIET));
  
  			if (Double.isNaN(pavg)) {
  				pavg = 1;
  			}
  
  			if (pavg > ptavg) {
  				//System.out.printf("PAVG %f > %f PTAVG\n", pavg,ptavg);
  				if (ozeta == 2) {
  					zetadiff = zetadiff / 2.0;
  				}
  				ozeta = 1;
  				zeta = zeta + zetadiff;
  				if (zeta >= 1) {
  					zeta = 1-zetadiff;
  					zetadiff = zetadiff / 2.0;
  					ozeta = 0;
  				}
  			} else {
  				if (pavg < ptavg * (1-err)) {
  					//	System.out.printf("PAVG %f < %f PTAVG\n", pavg,ptavg);
  					if (ozeta == 1) {
  						zetadiff = zetadiff / 2.0;
  					}
  					ozeta = 2;
  					zeta = zeta-zetadiff;
  					if (zeta <= 0) {
  						zeta = 0 + zetadiff;
  						zetadiff = zetadiff / 2.0;
  						ozeta = 0;
  					}
  				} else {
  					cond = true;
  				}
  			}
  
  			//System.out.printf("Zeta: %f Zetadiff: %f\n",zeta,zetadiff);
  			ee = 1;
  			bdiff = .1;
  			ob = 0;
  			zcount = 0; // if 100 iterations won't help, lets increase zeta...
  			bcheck = false;
  			while (bcheck == false) {
  
  				pstable = (1-zeta)/(Math.exp(b*meanIET)-zeta);
  				pnzero = Math.exp(-b*meanIET) * (1-zeta) *
  				((1-Math.pow(zeta*Math.exp(-b*meanIET),ntarg-1))/
  						(1-zeta*Math.exp(-b*meanIET)));
  				pnone = Math.pow(zeta*Math.exp(-b*meanIET),ntarg) + pnzero;
  				eezero = Math.abs(pnzero-pstable);
  				eeone  = Math.abs(pnone -pstable);
  				ee = Math.max(eezero,eeone);
  
  //				System.out.printf("Zeta: %f\n", zeta);
  				//			System.out.printf("Ptarget: %f \t Pstable: %f\n",ptavg,pstable);
  				//		System.out.printf("Pnzero: %f \tPnone: %f\n", pnzero,pnone);
  				//	System.out.printf("eezero: %f\t eeone: %f\n", eezero, eeone);
  
  				if (ee > err) {
  					if (ob == 2) {
  						bdiff = bdiff / 2.0;
  					}
  					ob = 1;
  					b = b+bdiff;
  				} else {
  					if (ee < (err*(1-err))) {
  						if (ob == 1) {
  							bdiff = bdiff / 2.0;
  						}
  						ob = 2;
  						b = b-bdiff;
  						if (b <= 0) {
  							b = 0 + bdiff;
  							bdiff = bdiff / 1.5;
  							ob = 0;
  						}
  					} else {
  						bcheck = true;
  //						System.out.println("******");
  					}
  				}
  
  //				System.out.printf("EE: %f B: %f Bdiff: %f\n",ee,b,bdiff);
  				zcount = zcount + 1;
  				if (zcount > 100) {
  					bcheck = true;
  					ozeta = 0;
  				}
  			}
  		}
  		gamma = Math.exp(-b);
  		pinit = 1-zeta;
  	}
  
  	/**
  	 * Updates delivery predictions for a host.
  	 * <CODE>P(a,b) = P(a,b)_old + (1 - P(a,b)_old) * P_INIT</CODE>
  	 * @param host The host we just met
  	 */
  	private void updateDeliveryPredFor(DTNHost host) {
  		double oldValue = getPredFor(host);
  		double newValue = oldValue + (1 - oldValue) * pinit;
  		preds.put(host, newValue);
  	}
  
  	/**
  	 * Returns the current prediction (P) value for a host or 0 if entry for
  	 * the host doesn't exist.
  	 * @param host The host to look the P for
  	 * @return the current P value
  	 */
  	public double getPredFor(DTNHost host) {
  		ageDeliveryPreds(); // make sure preds are updated before getting
  		if (preds.containsKey(host)) {
  			return preds.get(host);
  		}
  		else {
  			return 0;
  		}
  	}
  
  	/**
  	 * Updates transitive (A->B->C) delivery predictions.
  	 * <CODE>P(a,c) = P(a,c)_old + (1 - P(a,c)_old) * P(a,b) * P(b,c) * BETA
  	 * </CODE>
  	 * @param host The B host who we just met
  	 */
  	private void updateTransitivePreds(DTNHost host) {
  		MessageRouter otherRouter = host.getRouter();
  		assert otherRouter instanceof ProphetRouterWithEstimation : "PRoPHET only works " +
  		" with other routers of same type";
  
  		double pForHost = getPredFor(host); // P(a,b)
  		Map<DTNHost, Double> othersPreds =
  			((ProphetRouterWithEstimation)otherRouter).getDeliveryPreds();
  
  		for (Map.Entry<DTNHost, Double> e : othersPreds.entrySet()) {
  			if (e.getKey() == getHost()) {
  				continue; // don't add yourself
  			}
  
  			double pOld = getPredFor(e.getKey()); // P(a,c)_old
  			double pNew = pOld + ( 1 - pOld) * pForHost * e.getValue() * beta;
  			preds.put(e.getKey(), pNew);
  		}
  	}
  
  	/**
  	 * Ages all entries in the delivery predictions.
  	 * <CODE>P(a,b) = P(a,b)_old * (GAMMA ^ k)</CODE>, where k is number of
  	 * time units that have elapsed since the last time the metric was aged.
  	 */
  	private void ageDeliveryPreds() {
  		double timeDiff = (SimClock.getTime() - this.lastAgeUpdate);
  
  		if (timeDiff == 0) {
  			return;
  		}
  
  		double mult = Math.pow(gamma, timeDiff);
  		for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {
  			e.setValue(e.getValue()*mult);
  		}
  
  		this.lastAgeUpdate = SimClock.getTime();
  	}
  
  	/**
  	 * Returns a map of this router's delivery predictions
  	 * @return a map of this router's delivery predictions
  	 */
  	private Map<DTNHost, Double> getDeliveryPreds() {
  		ageDeliveryPreds(); // make sure the aging is done
  		return this.preds;
  	}
  
  	@Override
  	public void update() {
  		super.update();
  		if (!canStartTransfer() ||isTransferring()) {
  			return; // nothing to transfer or is currently transferring
  		}
  
  		// try messages that could be delivered to final recipient
  		if (exchangeDeliverableMessages() != null) {
  			return;
  		}
  
  		tryOtherMessages();
  	}
  
  	/**
  	 * Tries to send all other messages to all connected hosts ordered by
  	 * their delivery probability
  	 * @return The return value of {@link #tryMessagesForConnected(List)}
  	 */
  	private Tuple<Message, Connection> tryOtherMessages() {
  		List<Tuple<Message, Connection>> messages =
  			new ArrayList<Tuple<Message, Connection>>();
  
  		Collection<Message> msgCollection = getMessageCollection();
  
  		/* for all connected hosts collect all messages that have a higher
  		   probability of delivery by the other host */
  		for (Connection con : getConnections()) {
  			DTNHost other = con.getOtherNode(getHost());
  			ProphetRouterWithEstimation othRouter = (ProphetRouterWithEstimation)other.getRouter();
  
  			if (othRouter.isTransferring()) {
  				continue; // skip hosts that are transferring
  			}
  
  			for (Message m : msgCollection) {
  				if (othRouter.hasMessage(m.getId())) {
  					continue; // skip messages that the other one has
  				}
  				if (othRouter.getPredFor(m.getTo()) > getPredFor(m.getTo())) {
  					// the other node has higher probability of delivery
  					messages.add(new Tuple<Message, Connection>(m,con));
  				}
  			}
  		}
  
  		if (messages.size() == 0) {
  			return null;
  		}
  
  		// sort the message-connection tuples
  		Collections.sort(messages, new TupleComparator());
  		return tryMessagesForConnected(messages);	// try to send messages
  	}
  
  	/**
  	 * Comparator for Message-Connection-Tuples that orders the tuples by
  	 * their delivery probability by the host on the other side of the
  	 * connection (GRTRMax)
  	 */
  	private class TupleComparator implements Comparator
  	<Tuple<Message, Connection>> {
  
  		public int compare(Tuple<Message, Connection> tuple1,
  				Tuple<Message, Connection> tuple2) {
  			// delivery probability of tuple1's message with tuple1's connection
  			double p1 = ((ProphetRouterWithEstimation)tuple1.getValue().
  					getOtherNode(getHost()).getRouter()).getPredFor(
  							tuple1.getKey().getTo());
  			// -"- tuple2...
  			double p2 = ((ProphetRouterWithEstimation)tuple2.getValue().
  					getOtherNode(getHost()).getRouter()).getPredFor(
  							tuple2.getKey().getTo());
  
  			// bigger probability should come first
  			if (p2-p1 == 0) {
  				/* equal probabilities -> let queue mode decide */
  				return compareByQueueMode(tuple1.getKey(), tuple2.getKey());
  			}
  			else if (p2-p1 < 0) {
  				return -1;
  			}
  			else {
  				return 1;
  			}
  		}
  	}
  
  	@Override
  	public RoutingInfo getRoutingInfo() {
  		ageDeliveryPreds();
  		RoutingInfo top = super.getRoutingInfo();
  		RoutingInfo ri = new RoutingInfo(preds.size() +
  		" delivery prediction(s)");
  
  		for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {
  			DTNHost host = e.getKey();
  			Double value = e.getValue();
  
  			ri.addMoreInfo(new RoutingInfo(String.format("%s : %.6f",
  					host, value)));
  		}
  
  		ri.addMoreInfo(new RoutingInfo(String.format("meanIET: %f\t from %d samples",meanIET,nrofSamples)));
  		ri.addMoreInfo(new RoutingInfo(String.format("current gamma: %f",gamma)));
  		ri.addMoreInfo(new RoutingInfo(String.format("current Pinit: %f",pinit)));
  
  		top.addMoreInfo(ri);
  		return top;
  	}
  
  	@Override
  	public MessageRouter replicate() {
  		ProphetRouterWithEstimation r = new ProphetRouterWithEstimation(this);
  		return r;
  	}
  
  }
  