From b0108af8033748220bb10b427cba6cbb1b418ebd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magdalena=20Grodzi=C5=84ska?= Date: Fri, 10 Jan 2020 20:44:44 +0100 Subject: Add gossip girl strategies skeleton --- .../agent/modules/GossipGirlStrategies.java | 55 ++++++++++++++++++++++ 1 file changed, 55 insertions(+) create mode 100644 src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java (limited to 'src/main') 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 new file mode 100644 index 0000000..bf163d1 --- /dev/null +++ b/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java @@ -0,0 +1,55 @@ +package pl.edu.mimuw.cloudatlas.agent.modules; + +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; + +/** + round robin with the same frequency for all levels, + round robin with the frequency exponentially decreasing with level, + random with the same selection probability for all levels, + random with the selection probability decreasing exponentially with level. + */ + +public class GossipGirlStrategies { + + public enum ZoneSelectionStrategy { + ROUND_ROBIN_SAME_FREQ, + ROUND_ROBIN_EXP_FREQ, + RANDOM_UNFIORM, + RANDOM_DECR_EXP + } + + public PathName selectStrategy(PathName fullPath, ZoneSelectionStrategy selectionStrategy) { + PathName selectedPath; + ArrayList + int fullPathLength = fullPath.getComponents().size(); + + switch(selectionStrategy) { + case (ZoneSelectionStrategy.ROUND_ROBIN_SAME_FREQ): + + break; + case (ZoneSelectionStrategy.ROUND_ROBIN_EXP_FREQ): + + break; + case (ZoneSelectionStrategy.RANDOM_UNFIORM): + ArrayList> zoneProbabilities = new ArrayList<>(fullPathLength); + EnumeratedDistribution dist = new EnumeratedDistribution(); + for (int i = 1; i < fullPathLength; i++) { + zoneProbabilities.add(fullPath.); + } + break; + case (ZoneSelectionStrategy.RANDOM_DECR_EXP): + break; + default: + throw new UnsupportedOperationException("Such strategy doesn't exist"); + } + + return selectedPath; + } + + + +} -- cgit v1.2.3 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') 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 From f943acc55cfc133ad93801f3498b7662ccbe3a92 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magdalena=20Grodzi=C5=84ska?= Date: Fri, 10 Jan 2020 23:18:46 +0100 Subject: Fix strategies after adding test --- .../agent/modules/GossipGirlStrategies.java | 21 ++++++++++++++++----- 1 file changed, 16 insertions(+), 5 deletions(-) (limited to 'src/main') 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 774e509..4cd534e 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 @@ -40,16 +40,17 @@ public class GossipGirlStrategies { zoneProbabilities.add(probPair); } - uniformDist = new EnumeratedDistribution(zoneProbabilities); + expDist = new EnumeratedDistribution(zoneProbabilities); } private void initUniformZoneProbabilities() { ArrayList> zoneProbabilities; zoneProbabilities = new ArrayList<>(fullPathLength); + Double uniformProb = 1.0/fullPathLength; // TODO good direction for (int i = 0; i < fullPathLength; i++) { - Pair probPair = new Pair(fullPathComponents.get(i), 1.0); + Pair probPair = new Pair(fullPathComponents.get(i), uniformProb); zoneProbabilities.add(probPair); } @@ -77,16 +78,26 @@ public class GossipGirlStrategies { Pair nextP = roundRobinExpFreqs.get(i-1); if (2 * p.getSecond() < nextP.getSecond()) { - roundRobinExpFreqs.add(i, new Pair(p.getFirst(), p.getSecond() + 1)); + roundRobinExpFreqs.set(i, new Pair(p.getFirst(), p.getSecond() + 1)); return p.getFirst(); } } Pair rootPath = roundRobinExpFreqs.get(0); - roundRobinExpFreqs.add(0, new Pair(rootPath.getFirst(), rootPath.getSecond() + 1)); + roundRobinExpFreqs.set(0, new Pair(rootPath.getFirst(), rootPath.getSecond() + 1)); return rootPath.getFirst(); } + private String formNewPath(String selectedPath) { + String newPath = ""; + for (String pathEl : fullPathComponents) { + newPath = newPath.concat("/" + pathEl); + if (pathEl.equals(selectedPath)) + break; + } + return newPath; + } + public PathName selectStrategy(ZoneSelectionStrategy selectionStrategy) { String selectedPath = null; @@ -108,6 +119,6 @@ public class GossipGirlStrategies { throw new UnsupportedOperationException("Such strategy doesn't exist"); } - return new PathName(selectedPath); + return new PathName(formNewPath(selectedPath)); } } -- cgit v1.2.3