diff options
3 files changed, 157 insertions, 0 deletions
diff --git a/build.gradle b/build.gradle index de9a9df..e2174a7 100644 --- a/build.gradle +++ b/build.gradle @@ -55,6 +55,8 @@ dependencies { implementation 'org.springframework.boot:spring-boot-starter-test:2.2.1.RELEASE' + implementation 'org.apache.commons:commons-math3:3.6.1' + // Use JUnit test framework testImplementation 'junit:junit:4.12' 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..4cd534e --- /dev/null +++ b/src/main/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategies.java @@ -0,0 +1,124 @@ +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.*; + +/** + 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 { + private int roundRobinSameIt; + private ArrayList<Pair<String, Integer>> roundRobinExpFreqs; + private List<String> fullPathComponents; + private int fullPathLength; + private EnumeratedDistribution<String> expDist; + private EnumeratedDistribution<String> uniformDist; + + public GossipGirlStrategies(PathName fullPath) { + fullPathComponents = fullPath.getComponents(); + fullPathLength = fullPath.getComponents().size(); + initUniformZoneProbabilities(); + initExpZoneProbabilities(); + roundRobinSameIt = 0; + initRoundRobinExpFreqs(); + } + + private void initExpZoneProbabilities() { + ArrayList<Pair<String, Double>> zoneProbabilities; + zoneProbabilities = new ArrayList<>(fullPathLength); + + // TODO check if we decrease in good direction + for (int i = 0; i < fullPathLength; i++) { + Pair<String, Double> probPair = new Pair<String, Double>(fullPathComponents.get(i), Math.exp((double) i+1)); + zoneProbabilities.add(probPair); + } + + expDist = new EnumeratedDistribution<String>(zoneProbabilities); + } + + private void initUniformZoneProbabilities() { + ArrayList<Pair<String, Double>> zoneProbabilities; + zoneProbabilities = new ArrayList<>(fullPathLength); + Double uniformProb = 1.0/fullPathLength; + + // TODO good direction + for (int i = 0; i < fullPathLength; i++) { + Pair<String, Double> probPair = new Pair<String, Double>(fullPathComponents.get(i), uniformProb); + zoneProbabilities.add(probPair); + } + + uniformDist = new EnumeratedDistribution<String>(zoneProbabilities); + } + + private void initRoundRobinExpFreqs() { + roundRobinExpFreqs = new ArrayList<>(); + for (String component : fullPathComponents) { + roundRobinExpFreqs.add(new Pair<String, Integer>(component, 0)); + } + } + + public enum ZoneSelectionStrategy { + ROUND_ROBIN_SAME_FREQ, + ROUND_ROBIN_EXP_FREQ, + RANDOM_UNFIORM, + RANDOM_DECR_EXP + } + + private String updateRoundRobinExpFreqs() { + // TODO good direction + for (int i = roundRobinExpFreqs.size() - 1; i > 0; i--) { + Pair<String, Integer> p = roundRobinExpFreqs.get(i); + Pair<String, Integer> nextP = roundRobinExpFreqs.get(i-1); + + if (2 * p.getSecond() < nextP.getSecond()) { + roundRobinExpFreqs.set(i, new Pair<String, Integer>(p.getFirst(), p.getSecond() + 1)); + return p.getFirst(); + } + } + + Pair<String, Integer> rootPath = roundRobinExpFreqs.get(0); + roundRobinExpFreqs.set(0, new Pair<String, Integer>(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; + + 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 RANDOM_UNFIORM: + selectedPath = uniformDist.sample(); + break; + case RANDOM_DECR_EXP: + selectedPath = expDist.sample(); + break; + default: + throw new UnsupportedOperationException("Such strategy doesn't exist"); + } + + return new PathName(formNewPath(selectedPath)); + } +} diff --git a/src/test/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategyTest.java b/src/test/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategyTest.java new file mode 100644 index 0000000..681483d --- /dev/null +++ b/src/test/java/pl/edu/mimuw/cloudatlas/agent/modules/GossipGirlStrategyTest.java @@ -0,0 +1,31 @@ +package pl.edu.mimuw.cloudatlas.agent.modules; + +import org.junit.Test; +import pl.edu.mimuw.cloudatlas.agent.modules.GossipGirlStrategies; +import pl.edu.mimuw.cloudatlas.model.PathName; + +import java.util.HashMap; + +public class GossipGirlStrategyTest { + + @Test + public void seeHowTheyWork() { + PathName fullPath = new PathName("/pl/mazowieckie/warszawa/ochota/mimuw"); + GossipGirlStrategies gossipGirlStrategies = new GossipGirlStrategies(fullPath); + int loopCount = 1000; + PathName selectedPath; + HashMap<PathName, Integer> freqs = new HashMap<>(); + freqs.put(new PathName("/pl/mazowieckie/warszawa/ochota/mimuw"), 0); + freqs.put(new PathName("/pl/mazowieckie/warszawa/ochota"), 0); + freqs.put(new PathName("/pl/mazowieckie/warszawa"), 0); + freqs.put(new PathName("/pl/mazowieckie"), 0); + freqs.put(new PathName("/pl"), 0); + + for (int i = 0; i < loopCount; i++) { + selectedPath = + gossipGirlStrategies.selectStrategy(GossipGirlStrategies.ZoneSelectionStrategy.ROUND_ROBIN_EXP_FREQ); + freqs.put(selectedPath, freqs.get(selectedPath) + 1); + System.out.println(selectedPath); + } + } +} |