From 3e44c34a8e4af0426dd50e087dae45a06b8f50dc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magdalena=20Grodzi=C5=84ska?= Date: Fri, 10 Jan 2020 22:34:47 +0100 Subject: Add initial gossip girl strategies implementation --- .../agent/modules/GossipGirlStrategies.java | 98 +++++++++++++++++----- 1 file changed, 78 insertions(+), 20 deletions(-) (limited to 'src/main/java/pl/edu/mimuw/cloudatlas') diff --git a/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java b/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java index bf163d1..774e509 100644 --- a/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java +++ b/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java @@ -4,7 +4,7 @@ import org.apache.commons.math3.distribution.EnumeratedDistribution; import org.apache.commons.math3.util.Pair; import pl.edu.mimuw.cloudatlas.model.PathName; -import java.util.ArrayList; +import java.util.*; /** round robin with the same frequency for all levels, @@ -14,6 +14,54 @@ import java.util.ArrayList; */ public class GossipGirlStrategies { + private int roundRobinSameIt; + private ArrayList> roundRobinExpFreqs; + private List fullPathComponents; + private int fullPathLength; + private EnumeratedDistribution expDist; + private EnumeratedDistribution uniformDist; + + public GossipGirlStrategies(PathName fullPath) { + fullPathComponents = fullPath.getComponents(); + fullPathLength = fullPath.getComponents().size(); + initUniformZoneProbabilities(); + initExpZoneProbabilities(); + roundRobinSameIt = 0; + initRoundRobinExpFreqs(); + } + + private void initExpZoneProbabilities() { + ArrayList> zoneProbabilities; + zoneProbabilities = new ArrayList<>(fullPathLength); + + // TODO check if we decrease in good direction + for (int i = 0; i < fullPathLength; i++) { + Pair probPair = new Pair(fullPathComponents.get(i), Math.exp((double) i+1)); + zoneProbabilities.add(probPair); + } + + uniformDist = new EnumeratedDistribution(zoneProbabilities); + } + + private void initUniformZoneProbabilities() { + ArrayList> zoneProbabilities; + zoneProbabilities = new ArrayList<>(fullPathLength); + + // TODO good direction + for (int i = 0; i < fullPathLength; i++) { + Pair probPair = new Pair(fullPathComponents.get(i), 1.0); + zoneProbabilities.add(probPair); + } + + uniformDist = new EnumeratedDistribution(zoneProbabilities); + } + + private void initRoundRobinExpFreqs() { + roundRobinExpFreqs = new ArrayList<>(); + for (String component : fullPathComponents) { + roundRobinExpFreqs.add(new Pair(component, 0)); + } + } public enum ZoneSelectionStrategy { ROUND_ROBIN_SAME_FREQ, @@ -22,34 +70,44 @@ public class GossipGirlStrategies { RANDOM_DECR_EXP } - public PathName selectStrategy(PathName fullPath, ZoneSelectionStrategy selectionStrategy) { - PathName selectedPath; - ArrayList - int fullPathLength = fullPath.getComponents().size(); + private String updateRoundRobinExpFreqs() { + // TODO good direction + for (int i = roundRobinExpFreqs.size() - 1; i > 0; i--) { + Pair p = roundRobinExpFreqs.get(i); + Pair nextP = roundRobinExpFreqs.get(i-1); - switch(selectionStrategy) { - case (ZoneSelectionStrategy.ROUND_ROBIN_SAME_FREQ): + if (2 * p.getSecond() < nextP.getSecond()) { + roundRobinExpFreqs.add(i, new Pair(p.getFirst(), p.getSecond() + 1)); + return p.getFirst(); + } + } - break; - case (ZoneSelectionStrategy.ROUND_ROBIN_EXP_FREQ): + Pair rootPath = roundRobinExpFreqs.get(0); + roundRobinExpFreqs.add(0, new Pair(rootPath.getFirst(), rootPath.getSecond() + 1)); + return rootPath.getFirst(); + } + public PathName selectStrategy(ZoneSelectionStrategy selectionStrategy) { + String selectedPath = null; + + switch(selectionStrategy) { + case ROUND_ROBIN_SAME_FREQ: + selectedPath = fullPathComponents.get(roundRobinSameIt); + roundRobinSameIt = (roundRobinSameIt + 1) % fullPathLength; + break; + case ROUND_ROBIN_EXP_FREQ: + selectedPath = updateRoundRobinExpFreqs(); break; - case (ZoneSelectionStrategy.RANDOM_UNFIORM): - ArrayList> zoneProbabilities = new ArrayList<>(fullPathLength); - EnumeratedDistribution dist = new EnumeratedDistribution(); - for (int i = 1; i < fullPathLength; i++) { - zoneProbabilities.add(fullPath.); - } + case RANDOM_UNFIORM: + selectedPath = uniformDist.sample(); break; - case (ZoneSelectionStrategy.RANDOM_DECR_EXP): + case RANDOM_DECR_EXP: + selectedPath = expDist.sample(); break; default: throw new UnsupportedOperationException("Such strategy doesn't exist"); } - return selectedPath; + return new PathName(selectedPath); } - - - } -- cgit v1.2.3