TTLbasedCacheDecisionStrategy.java

/*
 * Copyright (c) 2005-2010 KOM – Multimedia Communications Lab
 *
 * This file is part of PeerfactSim.KOM.
 *
 * PeerfactSim.KOM 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 3 of the License, or
 * any later version.
 *
 * PeerfactSim.KOM 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.
 *
 * You should have received a copy of the GNU General Public License
 * along with PeerfactSim.KOM.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

package de.tud.kom.p2psim.impl.vehicular.caching.decision;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import de.tudarmstadt.maki.simonstrator.api.Time;
import de.tudarmstadt.maki.simonstrator.api.component.vehicular.caching.decision.CacheDecisionStrategy;
import de.tudarmstadt.maki.simonstrator.api.component.vehicular.information.AvailableInformationAttributes;
import de.tudarmstadt.maki.simonstrator.api.component.vehicular.information.PointInformation;

public class TTLbasedCacheDecisionStrategy implements CacheDecisionStrategy {
	private static final long SCALING = Time.SECOND;

	private static final double ACCURACY_FACTOR = 100000;

	private long ttl = 300 * Time.SECOND / SCALING;
	private double accuracy = 1;

	private double costWrongKeep = 1;
	private double costWrongChange = 1;

	private Object _lastDecision = false;

	public TTLbasedCacheDecisionStrategy(Map<String, String> pParams) {
		for (Entry<String, String> param : pParams.entrySet()) {
			switch (param.getKey()) {
			case "ACCURACY":
				accuracy = Double.valueOf(param.getValue());
				break;
			case "COST_RATIO":
				double ratio = Double.valueOf(param.getValue());
				costWrongChange = 2 / (ratio + 1);
				costWrongKeep = 2 - costWrongChange;
				break;
			default:
				break;
			}
		}
	}

	public double getCostWrongChange() {
		return costWrongChange;
	}

	public double getCostWrongKeep() {
		return costWrongKeep;
	}

	@Override
	public <T extends PointInformation> T decideOnCorrectInformation(
			List<T> pSimilarPointInformation) {
		if (pSimilarPointInformation.size() == 1) {
			T decision = pSimilarPointInformation.get(0);
			_lastDecision = decision.getValue();
			return decision;
		} else if (pSimilarPointInformation.size() == 0) {
			return null;
		}

		long minTimestamp = Long.MAX_VALUE;
		long maxTimestamp = 0;
		Object value = pSimilarPointInformation.get(0).getValue();
		boolean differentValue = false;
		for (T t : pSimilarPointInformation) {
			if (!t.hasAttribute(AvailableInformationAttributes.TTL)) {
				throw new AssertionError("Unable to perform TTL-based majority voting witout TTL");
			}
			long timestamp = t.getDetectionDate();

			if (timestamp < minTimestamp) {
				minTimestamp = timestamp;
			}
			if (timestamp > maxTimestamp) {
				maxTimestamp = timestamp;
			}

			if (!value.equals(t.getValue())) {
				differentValue = true;
			}
		}

		if (differentValue) {
			long difference = maxTimestamp - minTimestamp;

			if (difference == 0) {
				return pSimilarPointInformation.get(pSimilarPointInformation.size() - 1);
			}

			double rate = difference / ((double) (pSimilarPointInformation.size() - 1) * SCALING);

			rate = Math.min(rate, ttl / 20);

			double b;
			if (Boolean.FALSE.equals(_lastDecision)) {
				b = determineB(rate, 1 - accuracy, ttl, costWrongKeep, costWrongChange);
			} else {
				b = determineB(rate, 1 - accuracy, ttl, costWrongChange, costWrongKeep);
			}

			Map<Object, Double> weight = new HashMap<>();

			for (T t : pSimilarPointInformation) {
				double impact = calculateImpact(1 - accuracy, ttl, t.getDetectionDate() / SCALING, b, maxTimestamp / SCALING);

				double sumImpact = 0;

				if (weight.containsKey(t.getValue())) {
					sumImpact = weight.get(t.getValue());
				}
				sumImpact += impact;

				weight.put(t.getValue(), sumImpact);
			}

			double maxWeight = -1;
			Object maxValue = null;

			for (Object key : weight.keySet()) {
				if (weight.get(key) > maxWeight) {
					maxWeight = weight.get(key);
					maxValue = key;
				}
			}

			maxTimestamp = -1;
			T maxFitting = null;
			for (T t : pSimilarPointInformation) {
				long timestamp = t.getDetectionDate();

				if (t.getValue().equals(maxValue) && timestamp > maxTimestamp) {
					maxTimestamp = timestamp;
					maxFitting = t;
				}
			}

			_lastDecision = maxFitting.getValue();

			return maxFitting;
		} else {
			maxTimestamp = -1;
			T maxFitting = null;
			for (T t : pSimilarPointInformation) {
				long timestamp = (long) t.getAttribute(AvailableInformationAttributes.TTL);

				if (timestamp > maxTimestamp) {
					maxTimestamp = timestamp;
					maxFitting = t;
				}
			}

			_lastDecision = maxFitting.getValue();

			return maxFitting;
		}
	}

	public double calculateImpact(double errorProbability, long ttl, long time, double b, long maxTimestamp) {
		long currentTime = Time.getCurrentTime() / SCALING;
		long age = currentTime - time;
		if (errorProbability == 0) {
			if (time == maxTimestamp) {
				return 1;
			} else {
				return 0;
			}
		} else if (errorProbability == 1) {
			return 1;
		} else if (errorProbability == 0.5) {
			return (errorProbability - 1) / ttl * age + errorProbability;
		}

		return (1 - errorProbability) * (Math.exp(b * age) - Math.exp(b * ttl)) / (1 - Math.exp(b * ttl));
	}

	public double getChangeProbability(long ttl) {
		return 1 - Math.pow(0.5, 1 / (double) ttl);
	}

	public int getOptimalMessageAmountForSwitch(double changeProbability, double errorProbability, double costSlow, double costFast) {
		return (int) Math.round(Math.log(-changeProbability / Math.log(errorProbability) * costSlow / costFast) / Math.log(errorProbability));
	}

	public double determineB(double rate, double errorProbability, long ttl, double costSlow, double costFast) {
		return determineB(rate, errorProbability, ttl, costSlow, costFast, 1);
	}

	public double determineB(double rate, double errorProbability, long ttl, double costSlow, double costFast, int reversed) {
		if (errorProbability == 0 || errorProbability == 1 || errorProbability == 0.5) {
			return Double.NaN;
		}

		double b;
		double p_c = getChangeProbability((long) (ttl / rate));

		int optimalAmount = getOptimalMessageAmountForSwitch(p_c, errorProbability, costSlow, costFast);

		boolean first = true;

		double leftSide;
		double rightSide;

		double step = 5;

		if (errorProbability < 0.5) {
			b = -2 * step * reversed;
		} else {
			b = 2 * step * reversed;
		}

		int similar = 0;
		double lastDifference = -1;
		do {
			leftSide = calculateWeightingForOldState(optimalAmount, rate, errorProbability, ttl, b);
			rightSide = calculateWeightingForNewState(optimalAmount, rate, errorProbability, ttl, b);
			if (Math.abs(Math.round((rightSide - leftSide) * ACCURACY_FACTOR)) == lastDifference) {
				similar++;
			} else {
				lastDifference = Math.abs(Math.round((rightSide - leftSide) * ACCURACY_FACTOR));
				similar = 0;
			}

			if (Double.isNaN(leftSide) || Double.isNaN(rightSide) || similar > 100) {
				if (reversed != -1) {
					double determineB = determineB(rate, errorProbability, ttl, costSlow, costFast, -1);
					if (!Double.isNaN(determineB)) {
						return determineB;
					} else {
						return b;
					}
				} else {
					return Double.NaN;
				}
			}

			leftSide = Math.round(leftSide * ACCURACY_FACTOR);
			rightSide = Math.round(rightSide * ACCURACY_FACTOR);

			if (leftSide > rightSide) {
				if (b < 0) {
					b -= step;
					if (!first) {
						step *= 0.5;
					}
				} else {
					b -= step;
					step *= 0.5;
					first = false;
				}
			} else if (leftSide < rightSide) {
				if (b > 0) {
					b += step;
					if (!first) {
						step *= 0.5;
					}
				} else {
					b += step;
					step *= 0.5;
					first = false;
				}
			} else {
				break;
			}
		} while (true);

		return b;
	}

	public double calculateWeightingForOldState(int optimalMessageAmount, double rate, double errorProbability, long ttl, double b) {
		double impact = 0;
		for (int a = optimalMessageAmount + 1; a < Math.max(Math.floor(ttl / rate), optimalMessageAmount + 2); a++) {
			impact += calculateImpact(errorProbability, ttl, Time.getCurrentTime() / SCALING - (long)Math.floor(a * rate), b, 0);
		}
		return impact;
	}

	public double calculateWeightingForNewState(int optimalMessageAmount, double rate, double errorProbability, long ttl, double b) {
		double impact = 0;
		for (int a = 0; a <= optimalMessageAmount; a++) {
			impact += calculateImpact(errorProbability, ttl, Time.getCurrentTime() / SCALING - (long)Math.floor(a * rate), b, 0);
		}
		return impact;
	}
}